Pathfinding Algorithm Comparison In Dynamic Congested Environment

Sammanfattning

Background. Navigation is a crucial aspect in many fields today, such as video games like Real-Time Strategy (RTS) games or real-world scenarios like self-driving robots. Within these areas are dynamic environments, a common sight where multiple agents are moving around to reach different goals, which can cause congestion. Other types of pathfinding algorithms are needed to handle navigation through environments and possible changes in the environment, like congestion, static ones like A*, or dynamic ones like Dynamic A* (D*) Lite. Objectives. Throughout this thesis, a deep dive is performed into the adaptability and performance of two renowned pathfinding algorithms, A* and D* Lite, when used in a simulated dynamic environment with various numbers of agent densities that cause congestion. To determine which algorithm performs best, analyze the A*and D* Lite results from these simulations during high congestion. Methods. The main goal is to compare the results from these algorithms gained during the simulations to determine which algorithm performs best—using a custom designed simulation framework and the algorithms implemented to work for this simulation to consider other agents better when navigating the environment. This systematic experimental approach can evaluate the algorithms for their ability to navigate effectively amidst obstacles and dynamic changes caused by a high number of agents. Results. The findings revealed that while A* performs well under lower densities, it struggles with specific starting positions during higher congestion levels, resulting in it failing by getting stuck. In contrast, D* Lite consistently adapts toenvironmental changes, show casing robustness by recalculating routes on the fly and succeeding in all tested scenarios without failure. Conclusions. The thesis highlights the limitations of the A* algorithm due to it failing during certain circumstances. D* Lite showed superior adaptability and good performance in dynamic environments, showing it is suitable for applications that require a success rate to environmental changes. The research also points out the importance of using the right algorithm based on the application’s specific needs, such as success rate, performance, computational cost, etc. By performing this study has shown areas of focus regarding these algorithms for future work, either for improving the algorithms or further bettering the understanding surrounding them.