Path planning
Path planning problem classification
According to the degree of grasp of environmental information, path planning can be divided into global path planning based on a priori complete information and local path planning based on sensor information. Among them, from the perspective of whether obtaining obstacle information is static or dynamic, global path planning is static planning (also called offline planning), and local path planning is dynamic planning (also called online planning). Global path planning needs to master all environmental information, and perform path planning based on all the information in the environmental map; local path planning only requires sensors to collect environmental information in real time, understand the environmental map information, and then determine the location of the map and its local obstacles Distribution, so that the optimal path from the current node to a certain sub-target node can be selected.
According to the information characteristics of the research environment, path planning can be divided into path planning problems in the discrete domain and path planning problems in the continuous domain. The path planning problem in the discrete domain is a one-dimensional static optimization problem, which is equivalent to the route optimization problem after simplified environmental information; while the path planning problem in the continuous domain is a problem in a continuous multi-dimensional dynamic environment.
General steps of path planning
General path planning problems in the continuous domain, such as dynamic path planning problems of robots and aircraft, etc. The general steps mainly include environment modeling and path planning. The three links of search and path smoothing.
(1) Environmental modeling. Environmental modeling is an important part of path planning. The purpose is to establish an environment model that is convenient for the computer to use for path planning, that is, to abstract the actual physical space into an abstract space that can be processed by algorithms, and realize mutual mapping.
(2) Path search. The path search stage is to apply the corresponding algorithm to find a walking path on the basis of the environment model, so that the predetermined performance function obtains the optimal value.
(3) The path is smooth. The path searched by the corresponding algorithm is not necessarily a feasible path that a moving body can walk, and it needs further processing and smoothing to make it a practical and feasible path.
For path planning problems in the discrete domain, or path feasibility analysis problems that have been done before environmental modeling or path search, the path smoothing link can be omitted.
Commonly used algorithms
There are many methods of path planning, and their scope of application is also different according to their own advantages and disadvantages. According to the research of common path planning algorithms in various fields, according to the sequence of various algorithm discovery and the basic principles of the algorithm, the algorithms are roughly divided into four categories: traditional algorithms, graphics methods, intelligent bionics algorithms and other algorithms.
Traditional algorithm
Traditional path planning algorithms include: simulated annealing algorithm, artificial potential field method, fuzzy logic algorithm, tabu search algorithm, etc.
(1) Simulated Annealing (SA) is an effective approximation algorithm suitable for large-scale combinatorial optimization problems. It imitates the annealing process of solid materials, controls the continuous decrease of temperature by setting the initial temperature, initial state and cooling rate, combines the probability of sudden jump characteristics, and uses the neighborhood structure of the solution space to perform random search. It has the advantages of simple description, flexible use, high operating efficiency, and fewer initial conditions, but it has the defects of slow convergence and randomness. Parameter setting is a key link in the application process.
(2) The artificial potential field method is a virtual force method. It imitates the movement of objects under gravitational repulsion. The target point and the moving body are gravitational forces, and the moving body and obstacles are repulsive forces. The path is optimized by establishing the gravitational field repulsion field function. The advantage is that the planned path is smooth and safe, and the description is simple, but there is a problem of local optimization. The design of the gravitational field is the key to the successful application of the algorithm.
(3) The fuzzy logic algorithm network simulates the driver’s driving experience, combines physiological perception and action, and obtains planning information through look-up tables based on the system’s real-time sensor information, thereby realizing path planning. The algorithm conforms to human thinking habits, eliminates the need for mathematical modeling, and facilitates the conversion of expert knowledge into control signals, with good consistency, stability and continuity. However, it is difficult to summarize fuzzy rules, and once the fuzzy rules are determined, it is difficult to adjust online, and the adaptability is poor. Optimal membership function, control rules and online adjustment methods are the biggest problems.
(4) Tabu search algorithm (TS) is a global stepwise optimization algorithm, which is a simulation of human intelligence process. By introducing a flexible storage structure and corresponding promotion rules to avoid attendee searches, and pardoning some urgent good states by defying the rules, in order to achieve global optimization.
The method of graphics
Traditional algorithms often have difficult modeling problems when solving practical problems. The method of graphics provides the basic method of modeling, but graphics The method generally has insufficient search capabilities, and often requires a combination of specialized search algorithms. Graphics methods include: C-space method, grid method, free space method, voronoi diagram method, etc.
(1) The C-space method is also known as the viewable space method, which is to expand the obstacle into a polygon in the motion space, and connect the starting point, the end point and the feasible straight line between all the polygon vertices (not passing through The line of obstacles) is the path range to search for the shortest path. The advantage of the C-space method is that it is intuitive and easy to find the shortest path; the disadvantage is that once the starting point and the target point change, the visible view must be reconstructed, which lacks flexibility. That is, its local path planning ability is poor, and it is suitable for global path planning and path planning within a continuous domain. Especially suitable for environment modeling in global path planning.
(2) The free space method uses pre-defined basic shapes (such as generalized cones, convex polygons, etc.) to construct free space, and expresses the free space as a connected graph, aiming at the defect of poor strain in the viewable method , And then plan the path by searching the graph. Since the start point and the end point change, it is only equivalent to their position change in the constructed free space, and only needs to be repositioned instead of redrawing the entire graph. The disadvantage is that many obstacles will increase the complexity of the algorithm, and the algorithm will be difficult to implement.
(3) The grid method, that is, the coded grid is used to represent the map, and the grid containing obstacles is marked as an obstacle grid, otherwise it is a free grid, which is Basically make path search. Grid method is generally used as an environmental modeling technology for path planning. As a method for path planning, it is difficult to solve the problem of complex environmental information, and generally needs to be combined with other intelligent algorithms.
(4) The voronoi diagram is a basic data structure about the spatial proximity relationship. It uses some basic graphics called elements to divide the space. The edge of the element is determined by the vertical line between every two points, and finally the entire space is divided into a compact Voronoi diagram, and then the algorithm is used to determine the edge of the polygon. The formed path network performs an optimal search. The advantage is that it encloses obstacles in the element, which can realize effective obstacle avoidance. The redrawing of the defect map is time-consuming, so it is not suitable for large-scale dynamic environments.
Intelligent bionics algorithm
When dealing with path planning problems under complex and dynamic environmental information, inspiration from nature can often play a very good role. Intelligent bionics algorithm is the algorithm that people discover through bionics research. Commonly used are: ant colony algorithm, neural network algorithm, particle swarm algorithm, genetic algorithm, etc.
(1) Ant Colony Algorithm, (Ant Colony Algorithm for short ACA) The idea comes from the exploration of the foraging behavior of ant colonies, each ant will leave a certain amount on the path it walks when foraging. Concentration of pheromone, the shortest path in the same time is due to the high pheromone concentration due to the number of ant traversals, and the subsequent ants will choose the path based on the pheromone concentration, which plays a positive feedback role. Therefore, the pheromone The shortest path with high concentration will soon be discovered. The algorithm uses iteration to simulate the foraging behavior of the ant colony to achieve its goal. It has the advantages of good global optimization ability, inherent parallelism, and easy implementation by computer, but it has a large amount of calculation and is easy to fall into a local optimal solution, but it can be improved by adding elite ants and other methods.
(2) Neural network algorithm is a very excellent algorithm in the field of artificial intelligence. It mainly simulates animal neural network behavior and performs distributed parallel information processing. However, its application in path planning is not successful, because the complex and changeable environment in path planning is difficult to describe with mathematical formulas. If neural networks are used to predict points outside the learning sample distribution space, the effect must be very poor. . Although neural network has excellent learning ability, poor generalization ability is its fatal flaw. However, due to its strong learning ability and robustness, its combined application with other algorithms has become a research hotspot in the field of path planning.
(3) Genetic Algorithms (GA) is an important research branch of contemporary artificial intelligence science. It is a computational model that simulates Darwinian genetic selection and natural elimination in the biological evolution process. Its idea originates from the natural law of biological genetics and the survival of the fittest, and is an iterative search algorithm implemented in accordance with the principles of genetic genetics. The biggest advantage is that it is easy to combine with other algorithms and give full play to the advantages of its own iteration. The disadvantage is that the computational efficiency is not high, and it is not as good as the ant colony algorithm. It has inherent advantages, but its improved algorithm is also a research hotspot.
Path planning applications
The application fields of path planning are very wide, such as: path planning of robot manipulators, aircraft trajectory planning, cruise missile path planning, traveling salesman problem (TSP) And its derived various vehicle (VRP) path planning, virtual assembly path planning, path planning based on road network, electronic map GPS navigation path search and planning, routing issues, etc.
The shortest path planning problem in the discrete domain
The problems belonging to the shortest path planning in the discrete domain include: path planning based on road network, electronic map CPS navigation path search planning Problems, routing problems, etc.
(1) Path planning based on road network and GPS navigation based on electronic map can be regarded as a path planning problem based on GIS (Geographical Information System). The solution to these problems is to extract the required road information from the complex data information, take the intersection as the node and the road information as the path information, construct a complex path information topology network, and locate the starting point and the target point as this topology network Go to the two nodes, and then use the path search algorithm to plan the shortest path optimization.
(2) The routing problem is the focus of research in the field of communication technology. The main function of the routing problem is to smoothly transfer data information from the source node to the target node. According to the design requirements of Qos, different weights can be set on the path to define the path parameters. Search for the optimal path stably and efficiently in the network topology, and quickly converge. Real-time network congestion control, dynamic routing selection based on specific conditions.
(3) From the perspective of shortest path planning, the characteristics of this type of problem are similar. They are all based on known path information (number of nodes, path parameter information, topology, etc.). Knowing the optimal path path planning problem from the starting node to the target node, the path information is mostly static information. Even if the information changes, the intelligent algorithm has enough ability to make timely contingency planning. Commonly used algorithms are: Dijkstra algorithm, A* search algorithm, simulated annealing algorithm, ant colony algorithm, genetic algorithm, particle swarm algorithm, Floyd algorithm, Fallback algorithm, etc.
The ergodic optimal path problem in the discrete domain
The problems that belong to the ergodic optimal path in the discrete domain include: virtual assembly path planning, traveling salesman problem (TSP) As well as the various vehicle problems (VRP) and logistics problems derived from it. Because the core of virtual assembly path planning is the problem of assembly sequence planning, and the problem of sequence planning is a typical TSP problem.
The general characteristics of this type of problem are: the known path information is static information. For the single-vehicle problem, the starting point is unique, the final target node is the starting point, and there are multiple sub-target nodes in the middle. The vehicle is required to start from the starting point with the shortest path, and return to the starting point after traversing all sub-target nodes. Of course, some problems are based on the shortest time or the least cost as the planning goal. For such path planning problems, the corresponding path information can be adjusted to path time information or path cost information, and the corresponding node remains unchanged. In addition, there are also overall control issues with multiple vehicles, multiple starting points, and load considerations. Such issues are based on the extended application of single-vehicle path planning.
Commonly used intelligent algorithms to solve such path problems are: ant colony algorithm, tabu search algorithm, simulated annealing algorithm, neural network algorithm, genetic algorithm, particle swarm algorithm, etc.
The problem of global path planning in the continuous domain
The problems that belong to the global path planning chart in the continuous domain include: autonomous movement path planning of robot manipulators, and UAV flight path Planning, cruise missile trajectory planning, etc. From the perspective of path planning, such problems are all known environmental information, and the environmental information is static information, how to avoid obstacles within a safe range to find the shortest path to the destination.
Solving such problems usually relies on the combination of intelligent algorithms and environmental modeling. Path planning algorithms directly applied to such problems include: viewable method, free space method, Voronoi diagram method, grid method, penalty function method, simulated annealing algorithm, etc. Intelligent algorithms used indirectly include: A* search algorithm, ant colony algorithm, genetic algorithm, particle swarm algorithm, artificial potential field method, etc.
The problem of local path planning in the continuous domain
The application fields of local path planning and global path planning in the continuous domain are basically the same, and they are in the right environment in their application fields. Different, solve different problems. Local planning is the dynamic real-time environmental information, which belongs to online planning. The algorithm requires good real-time, high efficiency, and stability, which is a hot research topic.
Path planning algorithms applied to such problems include: ant colony algorithm, genetic algorithm, particle swarm algorithm, A* search algorithm, artificial potential field method, quantum particle swarm algorithm, neural network algorithm, etc.
The ergodic path planning problem in the continuous domain
The ergodic path planning in the continuous domain is mainly used in: cleaning robots, lawn trimmers, minesweeping robots, search and rescue robots, Mineral detectors, etc. Its characteristic is: the robot needs to use the shortest path to cover every corner of the working area, requiring the largest coverage and the smallest repetition rate. To solve such problems, environment modeling is required. The most commonly used method is the grid method. Later, Neumann de Carvalho R et al. invented the template model method.
The commonly used algorithms to solve such problems are: neural network algorithm, A* algorithm, genetic algorithm, particle swarm algorithm, ant colony algorithm, etc.
Future development of path planning
With the continuous development of science and technology, the environment for path planning technology will become more complex and changeable. This requires the path planning algorithm to have the ability to quickly respond to changes in the complex environment. This is not a single or unilateral algorithm that can solve the problem. Therefore, in the future path planning technology, in addition to the research and discovery of new path planning algorithms, there are also the following parties that deserve attention:
(1) Improvement of advanced path planning algorithm. Any kind of algorithm has many difficulties in the actual application process, especially its own limitations. For example: A* algorithm as a heuristic search algorithm has the characteristics of good robustness and fast response, but it still has drawbacks in practice. Regarding the drawbacks of A* algorithm when it is applied to UAV trajectory planning, Li Ji Et al. proposed an improved A* algorithm, which solved the problem that the A* algorithm is difficult to meet the direct flight restrictions and has the limitations of the aircraft's minimum turning radius.
(2) Effective combination of path planning algorithms (ie hybrid algorithms). No single path planning algorithm can solve all path planning problems in practical applications, especially when it comes to new interdisciplinary problems, it is difficult to study new algorithms. The complementary advantages of path planning algorithms are to solve this problem. Provides the possibility. For the path planning problem of multiple space stations, Jin Feihu and others combined the ant colony algorithm and the neural network method to solve this problem, and avoided the local minimum problem when the neural network algorithm was used alone.
(3) Combination of environmental modeling technology and path planning algorithm. For complex two-dimensional or even three-dimensional continuous dynamic environment information, what the algorithm can do is limited. The combination of good modeling technology and excellent path planning algorithm will become a way to solve this problem. Such as the combination of grid method and ant colony algorithm, the combination of C-space method and Dijkstra algorithm, etc.
(4) Multi-agent parallel path planning algorithm design. With the development of science and technology, the parallel collaboration of multi-agents has been applied. Among them, the problem of path conflicts in multi-robot collaboration and dual-manipulator collaboration is getting more and more attention, and how to realize its collision-free path planning will become one of the hot spots of future research.
