A Comparative Analysis of Heuristic Pathfinding Techniques in Simulated Dynamic Environments for Autonomous Mobile Robots

Sammanfattning

Path planning in dynamic environments is an important research field for the continuous development of autonomous mobile robots. Dynamic environments contain unknown static and moving obstacles, which require the robot to find a collision-free path and avoid obstacles in real-time with low computational effort. Several nature-inspired, evolutionary computation algorithms have been developed for this cause, such as the simulated annealing algorithm. There are also more conventional graph search algorithms for path planning, and developments of those such as the D* Lite algorithm, which is suited for dynamic environments. This paper aims to compare the performance of the D* Lite algorithm with the simulated annealing algorithm in five different simulated dynamic environments with varying amount of static and moving obstacles. The metrics studied were computation time and path length. It was found that the D* Lite algorithm performed generally better, consistently generating slightly shorter paths, and often requiring less computation time. The simulated annealing algorithm parameters can be tuned to perform quite efficiently, requiring less computation time than D* Lite in some cases, while still generating path lengths close to D* Lite. A significant difference between the algorithms was the amount of variation in the results, where simulated annealing was more spread out. D* Lite performed more consistently with regard to both path length and computation time, without the risk of generating a path far from optimal solution.