Planar Waypoint Generation and Path Finding in Dynamic Environment

Abstract

Path Planning stands in basic positions in robotics, game AI and navigation. Previous solutions generally focused on decompose the environment into grid-like map, which is large in proportion to the size and complexity of the environment, and thus the efficiency of graph construction, update and path-finding suffers. We proposed a waypoint generation method to discretize the environment into a waypoint graph. By utilizing waypoint filtering and edge sparsification, we control the size of waypoint graph to be relatively small without sacrifice path quality in path finding. Our method limits the length of edge, and thus supports fast local update for dynamic environment. Experiments show that our way can fast generate the waypoint graph from continuous environment, and update it locally and dynamically. By integrating with physics engine, we also support path finding for multiple agents in a dynamic environment.