The advent of patrol robots significantly improves the efficiency of patrol tasks, reduces costs, and ensures continuity and stability in operations. Path planning plays a crucial role in the operation of patrol robots, as it must consider factors such as the distance to target points, environmental safety, road conditions, and potential obstacles to determine the optimal patrol route. An excellent path planning algorithm can enhance the efficiency of patrol robots, ensure the safety of the path, and reduce resource and energy waste.
1. Global Planning Algorithms
Common global planning algorithms include Dijkstra's algorithm, A* algorithm, and cost map algorithms. These algorithms aim to optimize the path globally to find the shortest possible route.
(1) Dijkstra's Algorithm
Dijkstra's algorithm calculates the shortest path from the starting point to all other nodes. It dynamically updates the distance information between nodes to choose the next node for expansion until the target node is reached, resulting in the shortest path across the entire map. Dijkstra's algorithm is known for its accuracy and broad applicability, as it can be used for both directed and undirected graphs and can handle edges with weights. However, it has a time complexity of O(V²), where V represents the number of nodes, making it slow for large graphs. Additionally, Dijkstra's algorithm cannot handle negative edge weights, as it assumes all edge weights are non-negative.
(2) A Algorithm*
The A* algorithm is a heuristic global path planning algorithm. It uses a custom heuristic function to estimate the cost between each node and the target, combining this with the actual cost for decision-making. A* ensures both high-quality paths and efficient searches. However, designing an effective heuristic function requires domain knowledge, and the algorithm can encounter memory issues when dealing with large search spaces.
Improved versions of the A* algorithm have been developed by incorporating concepts from potential fields, such as target attraction and obstacle repulsion, into the cost function. Smoothing techniques, like B-spline curves, are also used to create more seamless and realistic paths, which are particularly useful in scenarios where straight-line distances are similar.
(3) Cost Map Algorithm
The cost map algorithm divides the environment into grids, assigning a cost or weight to each grid. The robot can then select the optimal path based on the cost map information. Researchers have extensively studied cost map algorithms, such as the Occupancy Grid Map (OGM) algorithm, which divides the environment into grids and uses binary values to indicate the presence of obstacles. Probabilistic cost map algorithms have also been developed for path planning in uncertain environments. Some studies combine cost maps with the A* algorithm to achieve faster and more optimized path planning.
(4) Voronoi Diagram Algorithm
The Voronoi diagram algorithm divides the environment into regions centered around obstacles, assigning each point in the region to its closest obstacle. Patrol robots can use this algorithm to generate paths that stay within these regions, helping avoid obstacles while maintaining an even distribution of routes. Researchers have enhanced the traditional Voronoi diagram algorithm, especially for multi-robot path planning, by introducing extra guiding points or removing unnecessary feature points to improve path efficiency.
(5) RRT Algorithm
The Rapidly-exploring Random Tree (RRT) algorithm is a path planning algorithm based on sampling and tree structures. It generates a tree by randomly sampling and expanding nodes, gradually approaching the target point. RRT is particularly suitable for high-dimensional, non-convex spaces and has been widely applied in patrol robots' global path planning. Variants such as RRT* and RRT-Connect are also commonly used.
2. Local Planning Algorithms
Local planning algorithms, such as depth-first search, breadth-first search, and dynamic programming, are mainly used to find feasible paths for robots in local environments.
(1) Dynamic Window Approach (DWA)
This approach discretizes the robot's speed and steering space into a limited set of candidate windows. By using local perception data, DWA selects the best combination of speed and steering. It can update the robot's motion state in real-time, adapting to dynamic environments and avoiding collisions. An improved version of DWA considers obstacles both on and near the trajectory to ensure safer navigation.
(2) Model Predictive Control (MPC)
MPC creates a model to predict the robot's movement, then uses optimization to select the best control strategy. It considers the robot's dynamic and target constraints, generating smooth trajectories while avoiding obstacles. Some studies have improved MPC by applying probabilistic models or machine learning techniques, making the algorithm more accurate and stable in complex environments.
(3) Feedback Trajectory Tracking Control
Feedback control is used to adjust the robot's position and trajectory based on predefined paths. By continually modifying control inputs, the robot can adapt to environmental changes and shifting targets. Researchers have developed improved feedback trajectory tracking methods using fuzzy logic control and adaptive control theory, which enhance tracking accuracy and robustness.
(4) Obstacle Avoidance Based on Local Perception
This method uses local perception data (such as LiDAR or camera inputs) to detect nearby obstacles in real-time and apply corresponding avoidance strategies, such as rerouting or stopping. Some studies utilize deep learning to identify and classify obstacles, enhancing the robot's autonomous obstacle avoidance capabilities. Others propose potential field methods to guide the robot's movement and improve obstacle avoidance.
References
- WANG Y, YANG C, ZHOU D. A machine learning-based cost map generation method for mobile robot path planning [J]. IEEE Access, 2022, 10: 55508-55519.
- KARAMAN S, WALRAND J, FRAZZOLI E. Incremental sampling-based algorithms for optimal motion planning [C]// Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). [S.l.]: IEEE, 2010: 1720-1725.
