A Single-Query Bi-Directional Probabilistic Roadmap Planner with Lazy Collision Checking

This paper describes a new probabilistic roadmap (PRM) path planner that is: (1) single-query — instead of pre-computing a roadmap covering the entire free space, it uses the two input query configurations as seeds to explore as little space as possible; (2) bidirectional — it explores the robot’s free space by concurrently building a roadmap made of two trees rooted at the query configurations; (3) adaptive — it makes longer steps in opened areas of the free space and shorter steps in cluttered areas; and (4) lazy in checking collision — it delays collision tests along the edges of the roadmap until they are absolutely needed. Experimental results show that this combination of techniques drastically reduces planning times, making it possible to handle difficult problems, including multi-robot problems in geometrically complex environments.