On Delaying Collision Checking in PRM Planning: Application to Multi-Robot Coordination

This paper describes the foundations and algorithms of a new probabilistic roadmap (PRM) planner that is: single-query—instead of pre-computing a roadmap covering the entire free space, it uses the two input query configurations to explore as little space as possible; bi-directional—it explores the robot's free space by building a roadmap made of two trees rooted at the query configurations; and lazy in checking collisions—it delays collision tests along the edges of the roadmap until they are absolutely needed. Several observations motivated this strategy: (1) PRM planners spend a large fraction of their time testing connections for collision; (2) most connections in a roadmap are not on the final path; (3) the collision test for a connection is most expensive when there is no collision; and (4) any short connection between two collision-free configurations has high prior probability of being collision-free. The strengths of single-query and bi-directional sampling techniques and those of delayed collision checking reinforce each other. Experimental results show that this combination reduces planning time by a large factor, making it possible to efficiently handle difficult planning problems, such as problems involving multiple robots in geometrically complex environments. This paper specifically describes the application of the planner to multi-robot planning and compares results obtained when the planner uses a centralized planning approach (PRM planning is then performed in the joint configuration space of the robots) and when it uses a decoupled approach (the PRM planner is invoked several times, first to compute a path of each robot independent of the others, and then to coordinate those paths). On a simulated six-robot welding station combining 36 degrees of freedom, centralized planning has proven to be a much more effective approach than decoupled planning.