Path planning is widely used in many fields. Applications in high-tech fields include: autonomous collision-free action of robots; UAV's obstacle avoidance and penetration flight: cruise missiles evade radar search, prevent rebound attacks and complete penetration blasting tasks. Applications in daily life include: GPS navigation; Road planning based on GIS system: urban road network planning and navigation. Applications in the field of decision management include: Vehicle Problem (VRP) in logistics management and similar resource allocation problems in resource management. Routing problems in the field of communication technology, etc. All planning problems that can be topological as a point-and-line network can basically be solved by path planning.
Basic introduction Chinese name: path planning mbth: path planning category: electronic information technology application field: high-tech, daily life, logistics management and other common algorithms: Dijkstra algorithm, genetic algorithm and other classification of path planning problems, general steps of path planning, common algorithms, traditional algorithms, graphics methods, intelligent bionic algorithm, application of path planning, shortest path planning in discrete domain, optimal path planning in discrete domain, Continuous domain global path planning, continuous domain local path planning, continuous domain traversal path planning, future development of path planning, classification of path planning problems According to the degree of mastery of environmental information, path planning can be divided into global path planning based on prior complete information and local path planning based on sensor information. Among them, from the point of view of whether the obstacle information is static or dynamic, the global path planning belongs to static planning (also called offline planning) and the local path planning belongs to dynamic planning (also called online planning). Global path planning needs to master all the environmental information and plan the path according to all the information of the environmental map; Local path planning only needs sensors to collect environmental information in real time, understand environmental map information, and then determine the map position and local obstacle distribution, so that the optimal path from the current node to a sub-target node can be selected. According to the information characteristics of the studied environment, path planning can also be divided into discrete domain path planning problem and continuous domain path planning problem. The path planning problem in discrete domain belongs to one-dimensional static optimization problem, which is equivalent to the path optimization problem after simplifying environmental information. Path planning in continuous domain is a problem in continuous multidimensional dynamic environment. The general steps of path planning are general path planning problems in continuous domain, such as dynamic path planning problems of robots and aircraft. The general steps mainly include three links: environment modeling, path searching and path smoothing. (1) environment modeling. Environmental modeling is an important part of path planning, and its purpose is to establish an environmental model that is convenient for computers to use in path planning, that is, to abstract the actual physical space into an abstract space that can be handled by the algorithm, and to realize the mapping between the two. (2) path search. In the path search stage, the corresponding algorithm is applied to find the walking path based on the environmental model, so that the predetermined performance function can obtain the optimal value. (3) The path is smooth. The path searched by the corresponding algorithm is not necessarily a feasible path that the moving body can walk, and it needs further processing and smoothing to make it a practical and feasible path. For the path planning problem in discrete domain, or the problem that path feasibility analysis has been done before environment modeling or path search, the path smoothing link can be omitted. There are many commonly used algorithms for path planning, and their application ranges are different according to their advantages and disadvantages. According to the research of common path planning algorithms in various fields, according to the discovery order and basic principles of various algorithms, the algorithms are roughly divided into four categories: traditional algorithms, graphic methods, intelligent bionic algorithms and other algorithms. Traditional algorithms Traditional path planning algorithms include simulated annealing algorithm, artificial potential field method, fuzzy logic algorithm and tabu search algorithm. (1) simulated annealing algorithm is an effective approximate algorithm for solving large-scale combinatorial optimization problems. It imitates the annealing process of solid matter, controls the continuous drop of temperature by setting initial temperature, initial state and cooling rate, and combines the characteristics of probability jump to conduct random search by using the neighborhood structure of solution space. It has the advantages of simple description, flexible use, high operation efficiency and few initial conditions, but it has the disadvantages of slow convergence and randomness, and parameter setting is the key link in the application process. (2) The artificial potential field method is a virtual force method. It imitates the motion of an object under the repulsion of gravity, and optimizes the path by establishing the repulsion function of the gravitational field with the attraction between the target point and the moving body and the repulsion between the moving body and the obstacle. The advantage is that the planned path is smooth, safe and simple to describe, but there is a local optimization problem. The design of gravity field is the key to the successful application of the algorithm. (3) Fuzzy logic algorithm network simulates the driver's driving experience, combines physiological perception and action, and obtains planning information by looking up the table according to the real-time sensor information of the system, thus realizing path planning. The algorithm conforms to people's thinking habits, eliminates mathematical modeling, facilitates the transformation of expert knowledge into control signals, and has good consistency, stability and continuity. However, it is difficult to generalize fuzzy rules, and once the fuzzy rules are determined, it is difficult to adjust them online and the adaptability is poor. The optimal membership function, control rules and online adjustment methods are the biggest problems. (4) Tabu Search Algorithm (TS) is a global step-by-step optimization algorithm, which simulates the process of human intelligence. By introducing flexible storage structure and corresponding promotion rules, the search for attending the conference is avoided, and some urgent excellent states are pardoned by flouting the criteria, thus achieving global optimization. Traditional graphics algorithms are often difficult to model when solving practical problems, and graphics methods provide basic methods for modeling. However, the general search ability of graphic methods is insufficient, and it often needs to be combined with special search algorithms. The methods of graphics include: C space method, grid method, free space method, voronoi diagram method and so on. (1) The C-space method is also called the visible space method, that is, the obstacle is unfolded into a polygon in the motion space, and the feasible straight line connection between the starting point and the ending point of the polygon (the connection through the obstacle) is taken as the path range to search for the shortest path. The advantage of C-space method is intuitive and easy to find the shortest path. The disadvantage is that once the starting point and target point change, it is necessary to reconstruct visibility and lack flexibility. That is, its local path planning ability is poor, and it is suitable for global path planning and continuous domain path planning. It is especially suitable for environment modeling in global path planning. (2) The free space method uses predefined basic shapes (such as generalized cone, convex polygon, etc.) to overcome the defect of visual normal strain difference. ) to construct a free space, and express the free space as a connected graph, and then plan the path by searching the graph. Because the changes of the starting point and the ending point are only equivalent to the changes of their positions in the constructed free space, it is only necessary to reposition and not redraw the whole diagram. The disadvantage is that many obstacles will increase the complexity of the algorithm and it is difficult to realize the algorithm. (3) Grid method, that is, the map is represented by coded grid, and the grid containing obstacles is marked as obstacle grid, otherwise it is free grid, and path search is carried out on this basis. Grid method is usually used as an environmental modeling technology for path planning. As a path planning method, it is difficult to solve complex environmental information problems and generally needs to be combined with other intelligent algorithms. (4) voronoi diagram is a basic data structure about spatial proximity. It divides the space by some basic figures called elements, and determines the edges of elements by the vertical lines between every two points. Finally, it divides the whole space into a compact voronoi diagram, and then uses this algorithm to optimize the search of the path network composed of polygonal edges. The advantage is that obstacles can be effectively avoided by enclosing obstacles in elements, and it takes time to redraw the defect map, which is not suitable for large dynamic environment. When intelligent bionic algorithm deals with the path planning problem under complex dynamic environment information, the enlightenment from nature can often play a very good role. Intelligent bionic algorithm is an algorithm discovered by people through bionics research, which is commonly used: ant colony algorithm, neural network algorithm, particle swarm optimization algorithm, genetic algorithm and so on. (1) The idea of ant colony algorithm (ACA for short) comes from the exploration of ant colony foraging behavior. Every ant will leave a certain concentration of pheromone on its path when it is foraging. The shortest path in the same time is found quickly because the ants traverse many times and the pheromone concentration is high, and the ants behind will choose the path according to the pheromone concentration, which plays a positive feedback role. The algorithm simulates the foraging behavior of ant colony and achieves the goal through iteration. It has the advantages of strong global optimization ability, essential parallelism and easy computer implementation. However, it is easy to fall into the local optimal solution due to the large amount of calculation, but it can be improved by adding elite ants. (2) Neural network algorithm is an excellent algorithm in the field of artificial intelligence, which mainly simulates the behavior of animal neural network and carries out distributed parallel information processing. But its application in path planning is not successful, because it is difficult to describe the complex and changeable environment in path planning with mathematical formulas. If neural network is used to predict the points outside the distribution space of learning samples, the effect will be very poor. Although neural network has excellent learning ability, its fatal disadvantage is poor generalization ability. However, due to its strong learning ability and good robustness, the combination with other algorithms has become a research hotspot in the field of path planning. (3) Geic algorithm (GA) is an important branch of artificial intelligence science, and it is a computational model simulating Darwin's genetic selection and natural selection. Its idea stems from the natural law of biological heredity and survival of the fittest, and it is an iterative search algorithm based on the principle of genetic genetics. The biggest advantage is that it is easy to combine with other algorithms and give full play to its own iterative advantages. The disadvantage is that the running efficiency is not high, which is not as innate as ant colony algorithm, but its improved algorithm is also the focus of current research. Path Planning Application Path Planning has a wide range of applications, such as robot arm path planning, aircraft path planning, cruise missile path planning, traveling salesman problem (TSP) and its derivative vehicle (VRP) path planning, virtual assembly path planning, path planning based on road network, electronic map GPS navigation path search and planning, routing problems and so on. The shortest path planning problem in discrete domain belongs to the shortest path planning problem in discrete domain, such as path planning problem based on road network, CPS navigation path search planning problem of electronic map, routing problem and so on. (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. The solution to these problems is to extract the required road information from complex data information, take intersections as nodes and road information as path information, build a complex topology network of path information, locate the starting point and the target point as two nodes on this topology network, and then use the path search algorithm to plan the shortest path optimization. (2) Routing problem is the focus of communication technology research. The main function of routing problem is to transmit data information smoothly from source node to target node. According to the design requirements of Qos, different weights can be set on the path and path parameters can be defined. Search the optimal path stably and efficiently in the network topology, and quickly aggregate. Real-time network congestion control, dynamic routing according to specific conditions. (3) From the perspective of shortest path planning, the characteristics of this kind of problems are similar. They are all optimal path planning problems from the known starting nodes to the target nodes with known path information (number of nodes, path parameter information, topological structure, etc.). ). The path information is mostly static information. Even if the information changes, the intelligent algorithm has enough ability to make timely emergency plans. Commonly used algorithms are: Dijkstra algorithm, A* search algorithm, simulated annealing algorithm, ant colony algorithm, genetic algorithm, particle swarm optimization algorithm, Floyd algorithm, Fallback algorithm and so on. The discrete domain ergodic optimal path problem belongs to the discrete domain ergodic optimal path problem, including virtual assembly path planning, traveling salesman problem (TSP), various vehicle problems (VRP) and logistics problems derived from it. Because the core of virtual assembly path planning is assembly sequence planning, which is a typical TSP problem. The general characteristics of this kind of problems are: the known path information is static information, and for the pedal vehicle problem, the starting point is unique, the final target node is the starting point, and there are many sub-target nodes in the middle. The vehicle is required to start from the starting point with the shortest path, traverse all sub-target nodes and return to the starting point. Of course, some problems aim at the shortest time or the least cost, so the corresponding path information can be adjusted to path time information or path cost information, and the corresponding nodes remain unchanged. In addition, there is the overall regulation problem of multi-vehicles, multi-starting points, considering the load and other factors, which is an extension of the pedal-based vehicle path planning problem. The commonly used intelligent algorithms to solve this kind of path problem are: ant colony algorithm, tabu search algorithm, simulated annealing algorithm, neural network algorithm, genetic algorithm, particle swarm optimization algorithm and so on. The global path planning problem of continuous domain belongs to the global path planning graph of continuous domain. These problems include autonomous motion path planning of manipulator, path planning of unmanned aerial vehicle and path planning of cruise missile. From the perspective of path planning, this kind of problem is how to avoid obstacles and find the shortest path to the destination within a safe range when the environmental information is known and static. Solving this kind of problem usually depends on the combination of intelligent algorithm and environmental modeling. Path planning algorithms directly applied to this kind of problems include visibility method, free space method, Voronoi diagram method, grid method, penalty function method, simulated annealing algorithm and so on. Indirect intelligence algorithms include: A* search algorithm, ant colony algorithm, genetic algorithm, particle swarm optimization algorithm, artificial potential field method and so on. Local path planning in a continuous domain The application fields of local path planning and global path planning in a continuous domain are basically the same, and the problems they face in different application fields are also different. Local planning is aimed at dynamic real-time environmental information, belongs to online planning, and needs good real-time, efficient and stable algorithms, which is the focus of current research. Path planning algorithms for this kind of problems include: ant colony algorithm, genetic algorithm, particle swarm optimization, A* search algorithm, artificial potential field method, quantum particle swarm optimization algorithm, neural network algorithm and so on. Continuous domain traversal path planning Continuous domain traversal path planning is mainly used for cleaning robots, lawn mowers, mine-sweeping robots, search and rescue robots, mineral detectors and so on. Its characteristic is that the robot needs to cover every corner of the working area with the shortest path, which requires the largest coverage and the smallest repetition rate. To solve this kind of problem, we need to model the environment first, and the most commonly used method is grid method. Later, Neumann de Carvalho and others invented template model method. The commonly used algorithms to solve such problems are: neural network algorithm, A* algorithm, genetic algorithm, particle swarm optimization algorithm, ant colony algorithm and so on. Development of Future Path Planning With the continuous development of science and technology, the environment of path planning technology will be more complex and changeable. This requires the path planning algorithm to have the ability to quickly respond to complex environmental changes. This is not a problem that can be solved by single or unilateral algorithms at present. Therefore, in the future path planning technology, in addition to the research and discovery of new path planning algorithms, the following aspects are worthy of attention: (1) Improvement of advanced path planning algorithms. Any algorithm has many difficulties in practical application, 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 shortcomings in practical application. Aiming at the shortcomings of A* algorithm in UAV path planning, Li Ji and others put forward an improved A* algorithm, which solved the problems that A* algorithm is difficult to meet the direct flight restrictions and has the minimum turning radius constraints. (2) Effective combination of path planning algorithms (i.e. hybrid algorithm). Any single path planning algorithm can't solve all practical path planning problems, especially when it involves new problems of interdisciplinary subjects. It is difficult to study the new algorithm, and the complementary advantages of the path planning algorithm provide the possibility to solve this problem. For the path planning problem of multiple space stations, Jin et al. combined ant colony algorithm with neural network method to solve it, avoiding the local minimum problem when using neural network algorithm alone. (3) The combination of environment modeling technology and path planning algorithm. However, when dealing with complex two-dimensional or even three-dimensional continuous dynamic environmental information, the algorithm can only do a limited amount. The combination of good modeling technology and excellent path planning algorithm will be 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. (4) Multi-agent parallel path planning algorithm design. With the development of science and technology, multi-agent parallel cooperation has been applied. Among them, the problem of path conflict in multi-robot cooperation and dual-manipulator cooperation has attracted more and more attention, and how to realize its collision-free path planning will become one of the hot spots in the future.