Multi-robot Path Planning by Predicting Structure in a Dynamic Environment

Path planning for multiple mobile robots is complicated by the presence of a dynamic environment, in which obstacles and other robots are moving.  Centralized approaches are too computationally intensive for real-time response. Decoupled approaches which perform individual preplanning, conflict resolution, and reactive obstacle avoidance for each robot, can be globally inefficient.  We propose a novel mission coordination architecture, CPAD (Checkpoint/Priority/Action Database), which performs path planning via checkpoint and dynamic priority assignment, using statistical estimates of the environment’s motion structure in order to make both preplanning and reactive behaviors more efficient.  Simulation is used to validate and illustrate the approach.