Waypoint Graph Based Fast Pathfinding in Dynamic Environment

摘要

Pathfinding is a fundamental task in many applications including robotics, computer games, and vehicle navigation. Waypoint graph is often used for pathfinding due to its advantage in specifying the space and obstacles in a region. Currently the waypoint graph based pathfinding suffers from large computation overhead and hence long latency in dynamic environment, where the location of obstacles may change. In this paper, we propose a fast approach for waypoint graph based pathfinding in such scenario. We eliminate unnecessary waypoints and edges to make the graph sparse. And then we design a prediction-based local method to handle the dynamic change in the environment. Extensive simulation has been done and the results show that the proposed approach outperforms existing approaches.