Systematic Comparison of Path Planning Algorithms using PathBench
Path Planning is an optimization problem to create the shortest path from place to place. The father of Path Planning, Edsger W. Dijkstra, once said, “What’s the shortest way to travel from Rotterdam to Groningen?” Many algorithms have been made to solve this path planning problem, like Dijkstra’s, A*, RRT, and RRT Connect, and more research is ongoing to create new algorithms. Google Maps uses A* to find the shortest path from place to place. Autonomous vehicles rely on path planning algorithms, like RRT and RRT Connect. Also, Minecraft uses A* to navigate mobs to the player. The paper “Systematic Comparison of Path Planning Algorithms using PathBench”, written by Hao-Ya Hsueh, Alexandru-Iosif Toma, Hussein Ali Jaafar, Edward Stow, Riku Murai, Paul H.J. Kelly, and Sajad Saeedi, compares different path planners on the novel PathBench, with platform-specific maps, real-world maps, and video game maps.
The main path planning algorithms we cover are Dijkstra’s Algorithm, A*, RRT, and RRT Connect. Dijkstra’s algorithm is effective at moving in a tree-like pattern through adjacent paths. It then finds the shortest path out of all of them. The main limitation of Dijkstra’s is that it is very expensive to compute and apply. On the other hand, A* is a path algorithm that finds possible paths in the direction of the destination. A* also estimates the cost of moving from the starting point to the final goal, increasing efficiency compared to algorithms like Dijkstra’s. RRT creates a tree on a random point that creates branches with the goal of a branch reaching the endpoint (where branches can create more branches, and so forth). RRT-connect is widely considered to be the more efficient version of RRT, because it creates two separate starting branches: one from the starting point and one from the ending point. RRT-connect’s branches’ goal, unlike RRT’s branch’s goal of reaching the end point, is to eventually connect somewhere in the middle.
The paper itself aims to test PathBench, a platform that can use 2-dimensional and 3-dimensional spaces and tests with a 3D map, a PathBench map, and a game path. Out of these, A* shone as a clear winner for the most efficient planner, with Dijkstra being a close second for its success rates. PathBench allows us to test and use software that can be useful in 2-dimensional and 3-dimensional environments. It also allows us to figure out which software is the best one for everyday use in video games and real environments. The results showed that out of all the software, A* was the most efficient and fastest one. It had a 99.4% success rate, and its speed was 0.106 seconds on PathBench. In the real city environment, it had a 100% success rate and took around 3.816 seconds. In the video game environment, it also had a 100% success rate, but it took around 31.567 seconds. Dijkstra has similar success rates, but took much longer. However, only for video games, d-sPRM performed similarly to Dijkstra, having an average performance in PathBench and in the city environment. Interestingly, d-RRT performed the worst in all three environments in terms of success rate and time taken, while d-RRT-connect performed quite well and matched some of Dijkstra’s performance.
The paper clearly explained how they conducted experiments using PathBench by providing details in both words and detailed graphs and illustrations. A* is the benchmark testing algorithm for all the PathBench maps because of its efficiency. The ways that we can use the PathBench vary greatly, but the main use of testing different algorithms in varied environments is to evaluate and compare different algorithms across different environments, as the results may differ with each environment. (For example, even though A* is used in each map to find the fastest route, in 3D maps A* takes much longer to find the best path because it has to explore more nodes than in 2D maps.) The results can be used to further improve online services that implement these algorithms, such as A* for GPS services, RRT types for motion planning simulations, and Dijkstra’s for maze solvers. This matters for path planning and beyond as it helps to find the most overall efficient algorithm, its conclusion providing information improving services that use such algorithms.
Path planning’s biggest strength is its many algorithms being able to be used for many cases. Some use cases include self-driving cars finding their way around the city, or an NPC in a video game navigating its surroundings. These algorithms can also be used for different problems. In many cases, certain algorithms are more useful than others. For example, A* was the quickest and most efficient out of all of them. In a real city and video game environment, A* had a 100% success rate. A* was also much faster than the others, like Dijkstra’s, even though they had similar success rates. Another example is d-RRT, which performed the worst out of all the algorithms in both categories. On the other hand, d-RRT-connect performed well and matched average-performing algorithms like Dijkstra’s, which is why it is considered superior to d-RRT.
PathBench’s flexibility allows people to test planners in both two-dimensional and three-dimensional environments using only one platform. This removes the need of having to switch between different platforms to test different environment types, creating a consistent testing place. The results showed that each planner completed navigating a PathBench environment in under 10 seconds, which is significantly faster compared to how the planners performed in the other environments (where completion times averaged to about 20 seconds). The faster navigation speed in PathBench environments allows researchers to evaluate planners’ performance across both 2-dimensional and 3-dimensional spaces more efficiently and, in turn, on a larger scale. Overall, PathBench is one of, if not the most effective, platforms for uniform, large-scale experimentation with path planning.