Graph search-based pathfinding in dynamic environments

Abstract

Pathfinding is a common problem in fields such as video games and robotics and has attracted a lot of research. In pathfinding, dynamic environments consist of obstacles that can either change their position or the cost of travel. The issues dynamic environments impose on pathfinding are that previously found paths can become invalid or better paths become available. At worst the agent has to constantly compute and update its path, making slow pathfinding methods ineffective.

A* is a well-known and widely used pathfinding algorithm fit for static environments. This thesis explores how A* performs in dynamic environments compared to three of its dynamic variants D* Lite, RTD*, and AD*. These variants also use differing methods and their comparative performance is also measured.

In this thesis, pathfinding in dynamic environments is examined by building a test environment that simulates dynamically changing obstacles. The performance of pathfinding algorithms is measured in this test environment and the results are analyzed by comparing the performance of the algorithms. The effect of different environmental variables on the algorithm performance is also examined, which includes the effect of the grid type, size, and the portion of changing obstacles.