Human errors and negligence are the leading causes of vehicle collisions, and autonomous vehicles (AVs) have the potential to drastically reduce them. These autonomous vehicles must travel from point A to point B safely and efficiently, considering time, distance, energy, and other factors.
Path planning is essential to determine and evaluate plausible trajectories that support these goals. Path planning is the process of determining a collision-free path in a given environment, which in real life is often cluttered.
The complexity in path planning increases with the system’s degrees of freedom. The optimal path will be decided based on constraints and conditions, for example, considering the shortest path between endpoints or the minimum time to travel without any collisions.
Path planning can be either local or global. Global path planning aims to find the best path given a large amount of environmental data, and it works best when the environment is static and well-known to the robot. On the other hand, local path planning is usually done in unknown or dynamic environments. While the robot is moving, local path planning is done using data from local sensors.
Mobile robots, unmanned aerial vehicles (drones), and autonomous vehicles (AVs) use path planning algorithms to find the safest, most efficient, collision-free, and least-cost travel paths from one point to another.
Multiple path planning and path-finding algorithms exist, each with different applicability based on the system’s kinematics, the environment’s dynamics, robotic computation capabilities, and the availability of sensor- and other-sourced information.
Four criteria must be met for a path planning algorithm to be effective. First, in realistic static environments, the motion planning technique must always be capable of finding the best path. Second, it must be adaptable to changing conditions. Third, it must be compatible with and enhance the self-referencing strategy selected. Fourth, it needs to be as simple as possible in complexity, data storage, and computation time.
Choosing the right path planning algorithm is essential for safe and efficient point-to-point navigation. This post will explore some of the key classes of path planning algorithms used today.
1. Dijkstra Algorithm
The Dijkstra algorithm works by solving sub-problems to find the shortest path from the source to the nearest vertices. It finds the next closest vertex by keeping the new vertices in a priority-min queue and only storing one intermediate node, allowing for the discovery of only one shortest path. We can today find many versions of Improved Dijkstra’s algorithm. Every Improved Dijkstra algorithm is different to reflect the diversity of use cases and applications.
Dijkstra is a dependable path planning algorithm. It also uses a lot of memory because it calculates all possible outcomes to find the shortest path, and it can’t handle negative edges. Because most of the data required for computing the shortest path is pre-defined, the Dijkstra algorithm is most suited for a static environment and/or global path planning.
2. A* Algorithm
The A* Algorithm is a widely popular graph traversal path planning algorithm that works similarly to Dijkstra’s algorithm. But it directs its search toward the most promising states, potentially saving time. For approaching a near-optimal solution with the available data-set/node, A* is the most widely used method. It is commonly used in static environments but also dynamic environments. In the gaming industry, the A* algorithm is widely used. Thanks to artificial intelligence (AI), the A* algorithm has been improved and tailored for robot path planning, intelligent urban transportation, graph theory, and automatic control applications. It is less computationally intensive and simpler than many other path planning algorithms, and its efficiency makes it suitable for use on constrained and embedded systems.
The A* algorithm is a heuristic algorithm that finds the best path using heuristic information. The A* algorithm must search the map for nodes and apply appropriate heuristic functions to provide guidance. The two factors that govern an algorithm are the efficient resources used to perform the task and the response time or computation time taken to perform the task. When using the A* algorithm, there is a trade-off between speed and accuracy. We can reduce the algorithm’s time complexity in exchange for more memory or consume less memory for slower executions. We find the shortest path in both cases. The A* algorithm can be used to find the shortest path to an empty parking space in a crowded parking lot.
3. D* Algorithm
Path planning in partially known and dynamic environments, such as for automated vehicles, is becoming increasingly important. The D* (or Dynamic A*) algorithm generates a collision-free path among moving obstacles to solving this problem. D* is a cost map repair algorithm that uses informed incremental search to partially repair the cost map and the previously calculated cost map.
The D* algorithm processes a robot’s state until it is removed from the open list while also computing the states sequence and back pointers to either direct the robot to the goal position or update the cost owing to detected obstacles and place the affected states on the open list. The states in the open list are processed until the path cost from the current state to the goal is less than a certain threshold, at which point the cost changes are propagated to the next state, and the robot continues to follow back pointers in the new sequence towards the goal. D* is more than 200 times faster than the best re-planner. The D* algorithm’s main disadvantage is its high memory consumption compared to other D* variants.
4. Rapidly-Exploring Random Trees (RRT)
Rapidly-Exploring Random Trees (RRT) are dynamic and online algorithms that do not require a path to be specified upfront. Rather, they expand in all regions and create a path based on weights assigned to each node from start to goal. RRTs were created to address a wide range of path planning issues. They were created with non-holonomic constraints in mind (constraints that are non-integrable into positional constraints). RRTs and Probabilistic Road Maps (PRMs) have similar desirable properties and were created using few heuristics and arbitrary parameters. This results in improved performance and consistency in the outcomes.
PRMs may require connections of thousands of configurations or states to find a solution, whereas RRTs does not require any connections between states to find a solution. This helps in applying RRTs to non-holonomic and kinodynamic planning. RRTs expand by rapidly sampling the space, grow from the starting point, and expand until the tree is sufficiently close to the goal point. The tree expands to the nearest vertex of the randomly generated vertex every iteration. This closest vertex is chosen based on a distance metric. Any distance metric can be used, including Euclidean, Manhattan, etc.
5. Genetic Algorithm
Discrete path planning algorithms, such as grid-based algorithms and potential fields, require substantial CPU performance and/or require significant memory. Genetic algorithms (GA) can help you get around these limitations. Genetic algorithms, for example, have the advantage of covering a large search space while consuming minimal memory and CPU resources. They can also adapt to changing circumstances. One disadvantage is that the optimization problem solution may not always be a global minimum (e.g., the overall shortest path).
Small humanoid robots that can play football are one of the more interesting applications of genetic algorithms. The robot must be aware of the goal post to kick the ball into the goal, with the opposing team acting as an obstacle, as the robot must avoid collisions and approach the goal post to kick the ball into the goal. The robot will need to use dynamic path planning because the algorithm can be used in dynamic environments. The best solution for finding a collision-free path between two points must be updated regularly to account for environmental changes.
6. Ant Colony Algorithm
Nature has inspired computer scientists and biologists to create path planning optimization algorithms. One such derivative algorithm is the ant colony optimization (ACO) algorithm, which is based on a heuristic approach inspired by the collective behavior of trail-laying ants to find the shortest and collision-free path. In his doctoral thesis in 1992, Marco Dorigo proposed this algorithm to simulate ant foraging for food in the Ant System (AS) theory. A variety of algorithms, which are probabilistic heuristic algorithms to find the shortest path, have been developed based on the different characteristics of the problem.
7. Firefly Algorithm
The Firefly algorithm is a meta-heuristic based on the mating behavior of Fireflies. It’s a promising swarm-intelligence-based algorithm inspired by the cooperative behavior of insects or animals solving complex problems. Insect colonies are self-organized, decentralized systems that prevent a single insect from acting. The algorithm is used to solve problems in both continuous and discrete optimization. Many variants of the Firefly algorithm have been developed to tackle optimization problems efficiently, including the Modified Firefly Algorithm (MFA), which is suitable for global path planning and has produced better results because Modified Firefly replaces the fixed-size step of the Standard Firefly Algorithm with a Gaussian random walk (SFA). The Modified Firefly algorithm eliminates one of the traditional Firefly algorithm’s flaws: slow convergence.
