01
introduction
The movement behavior of a mobile robot is determined by its autonomous navigation system, which mainly consists of four modules: perception, planning, control, and localization. The perception module is the bridge connecting the robot and its environment, and its function is to "read and extract" environmental content. The planning module is the bridge connecting perception and control, and its function is to "analyze and understand" environmental content and output executable control commands based on user goals and needs. Therefore, the perception and planning modules are the key to determining the intelligence level of the navigation system.
Figure 1.1 Schematic diagram of motion planning (Image source: http://wiki.ros.org/navigaTIon)
Motion planning has always been a classic research hotspot in the field of robotics, with numerous scholars and research institutions conducting in-depth studies on the scientific problems involved. Motion planning algorithms have different research focuses depending on the application scenario. For example, in the gaming field, the motion planning requirements for a game task moving from point A to point B are low memory consumption and good real-time performance, while the path quality requirements may be too high. In the field of global planning, such as applications like Baidu Maps, the focus is on how to quickly find a feasible path from the starting point to the destination, without paying attention to the details of the entire path. However, in the process of robot movement, the focus needs to be on the quality of the trajectory curve.
Attentive readers may have noticed that the planning here all relies on maps, and the paths are based on maps. Different maps use different planning algorithms, which can be found in "A Brief Overview of the Current Status of Robot Environmental Perception Research" which explains the different types of maps and their corresponding characteristics and applicable scenarios.
In addition, path planning also includes path search. Path search is not only used to search for paths, but also to search for targets, such as drug structures. Intelligent algorithms are used to search for drug molecular structures in a specified region, given initial conditions and screening conditions.
To enhance the autonomous movement capabilities of robots in different scenarios, numerous motion planning algorithms applicable to various environments have emerged. This article will categorize these algorithms according to their principles and sort them by research timeline, summarizing the progress and achievements in this research field.
02 Research and Analysis of Programming Algorithms
Before the analysis, we need to clarify some concepts: What is the relationship between motion planning, trajectory planning, and path planning?
Path planning refers to generating a path curve on a map connecting a starting point and an ending point. This path curve will not intersect with obstacles on the map and all points must remain within the feasible region. The path curve can be represented by a discrete sequence of points:
In the formula, (xk, yk) represents the location of the path point in the map coordinate system.
Trajectory planning, as the name suggests, involves generating a trajectory curve on a map connecting a starting point and an ending point. This trajectory curve is a composite curve combining a path curve and a velocity curve; in other words, the trajectory curve Traj contains information such as position, velocity, and time. After discretization, it can be represented as:
In the formula, (xt, yt) represents the position of the path point at time t in the map coordinate system, and (vt, wt) represents the robot's velocity at time t.
In a narrow sense, motion planning is very similar to trajectory planning. The difference lies in the fact that different robots have different kinematic/dynamic models, such as multi-axis robotic arms and mobile robots. Motion planning requires first planning the trajectory curve mentioned above, and then combining it with the dynamic model to convert the trajectory curve into the motion control curve of each motor. The motor is then controlled to move along the control curve to achieve the robot moving along the planned target trajectory curve.
<Back to the main topic>
As shown in Figure 2.1, motion planning research mainly focuses on optimizing and solving planning models with multiple objectives, multiple variables, and multiple constraints. There are many objective requirements, including hard constraints on the model, such as the trajectory curve needing to satisfy the constraints of the robot's kinematics and dynamics model, as well as obstacle avoidance constraints. In other words, the most basic requirement for the trajectory curve is that the robot can actually follow the movement without collision. On the other hand, soft constraints for planning requirements include good real-time performance, good dynamic adaptability, and low computational cost. These constraints vary depending on the application scenario, and the user experience also differs, hence the term soft constraints.
Figure 2.1 General model of motion planning
Furthermore, for mobile robots with nonholonomic constraints (see "Motion Model and Application Analysis of Two-Wheel Differential Drive Robot"), finding the optimal path in an environment with distributed obstacles is an NP-hard problem. That is, for any scenario, it is not guaranteed that the optimal solution can be found in polynomial time. Therefore, most planning algorithms pursue suboptimal solutions or local optima.
Motion planning research has a long history and numerous algorithms exist. Besides the many constraints mentioned above, what are the current research challenges in motion planning?
The author believes that one of the difficulties is how to handle the optimization problem of paths and velocity curves with coupling relationships. There are three common approaches:
1) Complete Path-Velocity Decoupling: Simply generating a smooth path and then using a curve tracking algorithm to control the robot's movement results in weak dynamic obstacle avoidance performance.
2) Path-velocity iterative optimization: First, a collision-free path (static obstacle avoidance) is generated, then a stable collision-free velocity curve is generated based on the path (dynamic obstacle avoidance), and the optimal trajectory curve is generated through iterative optimization algorithm. This method reduces the optimization dimensionality and improves optimization efficiency.
3) Path-velocity "bundling" optimization: Taking into account all constraints and optimization objectives, the optimal trajectory curve is generated. The trajectory generated by this method is very good, but there are problems such as the difficulty in constructing the optimization model and the low optimization efficiency.
Many scholars have designed and improved numerous motion planning algorithms for different application scenarios and needs. The author divides common motion planning algorithms into four main categories: graph planning algorithms, spatial sampling algorithms, curve interpolation fitting algorithms, and biomimetic intelligent algorithms.
Next, I will introduce the overview of these four subclasses of planning algorithms one by one.
2.1 Graph Programming Algorithm
Most graph planning algorithms discretize the environment model, such as a grid graph, where the discrete nodes describe the corresponding states, establish connections between nodes, and solve for the optimal path.
As shown in Figure 2.2, graph planning algorithms are divided into three categories according to different path generation methods, with graph search algorithms being the main one, as well as BUG algorithm and potential force algorithm.
For detailed analysis, please refer to "A Brief Overview of the Current Status of Robot Graph Planning Algorithm Research".
(Please view the image in landscape mode)
Figure 2.2 Overview of the development path of graph planning algorithms
2.2 Spatial Sampling Algorithm
Spatial sampling algorithms can be divided into two categories based on the sampling space: state space sampling and motion space sampling.
As shown in Figure 2.3, state-space sampling-based algorithms can quickly generate paths in large-area, high-dimensional spaces, including RRT and PRM algorithms, and have probabilistic completeness. Their main steps include random sampling, metric connection, collision detection, and path lookup.
Algorithms based on motion space sampling sample at equal intervals in velocity space and select the best control command through an evaluation function to drive the robot's motion. These algorithms mainly include CVM-type algorithms and DWA-type algorithms.
For detailed analysis, please refer to "A Brief Overview of the Current Status of Research on Robot Spatial Sampling Algorithms".
(Please view the image in landscape mode)
Figure 2.3 Overview of the development path of spatial sampling algorithms
2.3 Curve Interpolation Fitting Algorithm
Most of the paths generated by the above-mentioned graph planning algorithm and spatial sampling algorithm have discontinuous curvature such as inflection points and sharp turns, which affects the smoothness of robot motion. Therefore, it is necessary to comprehensively consider the hard constraints of the model and the soft requirements of actual planning in order to improve the smoothness of the path.
Figure 2.4 CHOMP Programming Algorithm
As shown in Figure 2.4, curve interpolation fitting algorithms have significant advantages in curve smoothing control and optimization. According to the curve generation method and type, they can be divided into three categories: interpolation-based planning algorithms, special curve-based planning algorithms, and optimization-based planning algorithms. These algorithms have wide applications in fields such as autonomous driving.
For detailed analysis, please refer to "A Brief Overview of the Current Status of Research on Robot Curve Interpolation Fitting Algorithms".
2.4 Bionic Intelligent Algorithm
In addition to the planning algorithms based on classical models mentioned above (graph programming algorithm, spatial sampling algorithm, and curve interpolation fitting algorithm), there are also neural networks, fuzzy logic, and natural inspiration-based algorithms (genetic algorithm, particle swarm optimization algorithm, ant colony optimization algorithm, etc.) for robot motion planning problems, which are gradually becoming research hotspots.
As shown in Figure 2.5, compared with classical algorithms, intelligent algorithms can better adapt to uncertain and incomplete information in complex dynamic environments, but require an early learning stage and high computational costs, making them suitable for large robots, such as unmanned vehicles.
For detailed analysis, please refer to "A Brief Overview of the Current Status of Research on Intelligent Bionic Path Planning Algorithms for Robots".
Figure 2.5 Fuzzy System Architecture for Path Planning
03
Discussion of Planning Algorithm Characteristics
In Table 3-1, the author summarizes and compares the main advantages and disadvantages of different types of algorithms, and their application scenarios also differ.
Graph planning and spatial sampling algorithms have been able to generate collision-free paths in many scenarios, with gradually improving real-time performance and dynamic adaptability. However, most algorithms still suffer from poor path quality and failure to consider dynamic constraints.
Curve interpolation fitting algorithms are perfectly suited to this purpose, and can easily generate trajectory curves with good continuity.
Most biomimetic intelligent algorithms suffer from instability in real-time performance and convergence when dealing with planning problems in dynamic environments, resulting in limited practical applications.
Current research approaches typically involve first using graph planning algorithms and spatial sampling algorithms to generate global or initial paths, and then using curve interpolation and fitting algorithms to comprehensively consider both system constraints and optimize the generation of high-quality trajectories.
Table 3-1 Comparison of Advantages and Disadvantages of Motion Planning Algorithms (Click or view larger image in the original text)
Note: Relevant references can be found in "Research on the Design of Integrated Perception and Planning System for Vehicle-like Robots".
04
Conclusions and Outlook
This paper classifies common planning algorithms into four categories based on their characteristics, and comprehensively compares and analyzes these four subcategories of planning algorithms from aspects such as real-time performance, computational cost, model complexity, environmental adaptability, path curve quality, and trajectory length.
There are many types of motion planning algorithms, and their application scenarios vary. This article only analyzes and summarizes some motion planning algorithms from the perspective of mobile robots, which can only be considered as the tip of the iceberg in the field of motion planning.
We will gradually delve deeper into the discussion and analysis of some classic algorithms in the future.
