[path planning] week 1: hodgepodge

Most of the traditional path planning methods are based on the description form of environment model , Take a relatively simple algorithm similar to the geometric mathematical model （ Such as geometric method 、 Heuristic algorithm ） Complete the robot path search .

Visual graph method

The visual graph method assumes that the robot and the obstacle are respectively a particle and an approximate polygon , Use the visible line segment to transform the particle 、 The target points and the vertices of the polygon are connected in an orderly combination , That is, the line cannot pass through the obstacle polygon , The robot path planning problem is transformed into a set of shortest line segments from the starting point to the target point , Always use A Algorithm or its improved algorithm searches for the shortest path . Because the search path is the line segment connecting the vertex of the obstacle , Robots are easy to collide with obstacles , When environmental obstacles 、 When there is a large amount of feature information , It takes a long time to search the path ; At the same time, the flexibility of visual graph method is poor , Poor adaptability to the environment and real-time performance , There is no guarantee that the path sought is globally optimal .
Tangent graph method is an improved method of visual graph method , The arc is represented by the tangent of the obstacle , It reduces the probability of collision between the robot and obstacles , The disadvantage is that when the robot control error is large , It is also easy to collide with obstacles ; If the error allows , When using tangent method to plan the path, the path away from obstacles is often selected to represent the arc . Visual graph method is usually combined with heuristic search algorithm to complete robot path planning , Such as A、Dijkstra etc. .

Grid method

The grid method uses two kinds of grids with different properties and numbers to describe the working environment of robots , Free grid and obstacle grid , There are no obstacles in the free grid area , The obstacle grid area contains obstacles . The robot path planning problem is transformed into an ordered set of feasible grids in the search workspace . This method takes grid as basic unit to record the environment information of robot , The larger the grid size , The coarser the description of the feature map , The worse the quality of the planned path , The bigger the error is ; The smaller the grid size , The more accurate the description of environmental obstacles , The better the quality of the planned path , But this is at the cost of a large amount of storage space and the complexity of the search algorithm , therefore , It should be based on the specific application environment , Select the appropriate grid scale and the corresponding algorithm to optimize the search grid ordered set . Grid map can describe many features of the real environment , It can also achieve optimal time and space consumption , therefore , Grid map is a widely used description method of environment map .

Artificial virtual potential field method

Virtual potential field method is an effective local path planning method [9]. The main idea is to describe the working environment of the robot as a virtual potential field , The target point is the gravitational source of the robot , The obstacle is the repulsion source of the robot , Under the combined action of two forces , The robot can avoid obstacles in real time and move to the target point along the collision free path . The artificial virtual potential field method is simple because of its mathematical principle 、 The advantages of high real-time and smooth path generation are widely used in robot local path planning , However, this method has inherent defects ： firstly , Because the planned path is based on limited local environmental information , Lack of macro self-regulation ability in the overall environment , It is easy to fall into local optimization ; second , Because the imbalance of force is the main factor of robot movement , It is very easy to achieve force balance at non target points , Thus, the target can not be reached ; third , In the narrow space between obstacles , It is easy to fall into unstable states such as wandering and shaking .

Robot intelligent obstacle avoidance path planning method

With the increase of environmental characteristic information and the difficulty of completing tasks , Robot path planning based on traditional simple geometric mathematical model is difficult to achieve ideal results , According to the habits of some creatures in nature , Apply its instinct to robot path planning , A bionic intelligent optimization algorithm is proposed , This kind of algorithm uses group behavior to find the global optimal solution in the complex solution space , It has random 、 Parallel and distributed . Because these bionic optimization algorithms have interdisciplinary optimization strategies and the potential ability to avoid falling into local optimization , It has achieved good results in the field of path planning , The representative ones are genetic algorithm and ant colony algorithm .

Genetic algorithm (ga)

Genetic algorithm is an American Michigan University's Holland JH Professor Yu 20 century 60 It was put forward at the end of the s , Other options 、 Copy 、 Operations such as crossover and mutation , An adaptive global optimization probability search algorithm is proposed to simulate the genetic and evolutionary processes of natural organisms . Genetic algorithm is an iterative algorithm , Because of its good global optimization ability and parallel computing characteristics , It is a mature method in the research of robot path planning . It selects the initial set 、 Copy 、 Operations such as crossover and mutation are iterated to obtain new solution sets , And according to individual fitness , Follow nature “ The survival of the fittest ” and “ Superior bad discard ” Principles , Guide the biological search process to “ Best adapted to the environment ” The individual of （ The best path ） Close to , And finally converge to the optimal solution （ The best path ） Or suboptimal solution （ Approximate optimal path ）.

Because the biological evolution of nature is a long process of multi group evolution , The genetic algorithm that simulates this process needs large-scale population and large search space , Early maturity and slow convergence are two major problems of genetic algorithm in robot path planning , The former will produce local optima , The latter will reduce the real-time performance of the algorithm , Affect its search path efficiency . So , A lot of research work has improved it

Ant colony algorithm

Ant colony algorithm (ACA) is a long-term and careful observation by biologists on the foraging process of ants in nature , It is found that the individuals in the biota cooperate to find the shortest path from the ant nest to the food source through an information medium . In the movement of ants looking for food , Ants leave pheromones that volatilize over time on their path , And can perceive the pheromone left by the previous generation of ants and its strength , According to the concentration of pheromone, we can guide our foraging direction , The pheromones left on the path also become the basis of information exchange between ant individuals “ medium ”. Because in equal time , The number of ants choosing the short path with higher pheromone concentration was higher , The pheromone concentration left in the shorter path will also be enhanced , According to ants “ Pheromone exchange mechanism ” The group behavior of foraging , In essence, it is a dynamic optimization process from disorder to order , Its implicit parallel processing performance has expanded its application field . Ant colony algorithm is a random search optimization method , In the process of optimization , We should gradually forget the historical information , Constantly explore new path information , That is, pheromone volatilization mechanism , It gives the ant colony the potential to innovate and explore the unknown space .

Ant colony algorithm derived from natural biological habits , The random probability selection, pheromone volatilization mechanism and positive feedback mechanism simulating the biological habits of real ants in nature are adopted , It has limitations , That is, randomness is easy to cause slow convergence of the algorithm , The positive feedback and volatilization mechanism can easily make the algorithm fall into local optimization , The key problem to be solved is in “ Explore ” and “ utilize ” To find a balance between , The search space of ant colony algorithm should be as large as possible （ That is, the randomness is large , High complexity ）, So that it can be in “ foraging ” Find the global optimal path in the process , And use prior knowledge （ Distance information 、 Heuristic information and pheromones ）, Make the system converge to the global optimum with a large probability , Its essence is to solve the contradiction between the global search ability of ant colony algorithm and its convergence to the global optimal speed , That is, the contradiction between randomness and pheromone update intensity . So , Many researchers have done a lot of in-depth research on related issues , Seek to reduce the complexity and depth of the improved optimization algorithm .

The main factors that affect the performance of ant colony algorithm are pheromone update mechanism and path search strategy , therefore , Researchers at home and abroad mainly focus on parameter optimization 、 Pheromone update mechanism and path search strategy are improved .

in addition to , Researchers have proposed many other intelligent optimization algorithms , Such as fuzzy control , Artificial bee colonies 、 neural network 、 Leapfrog algorithm 、 Immune algorithm 、 Empire rivalry counts
Law 、 Firefly algorithm 、 Fish swarm algorithm and so on .

---

What is path planning ？

Indoor path planning

• Path planning is based on the user's starting position 、 The terminal location and indoor map plan a accessible route with the shortest walking distance for users .

Robot path planning ：

• The goal of mobile robot path planning is to find a feasible and optimal path through environment awareness and active obstacle avoidance , This path does not intersect with any obstacles in a given workspace from the starting point to the end point , At the same time, the robot motion path should be optimized , Make it as short as possible 、 Smoother requirements .

Path planning steps ：

• （1） Establish the environment map model of the area with obstacles and the free moving area ;
• （2） Based on the established environment map model, choose the appropriate path search algorithm , For fast 、 Real time path planning . The generation process of path track is shown in the following figure .