A Parallel Randomized Path Planner for Robot Navigation

摘要

Computation of a collision-free path for a movable object among obstacles is an important problem in the fields of robotics, CIM and AI. Various automatic task level programming systems can be build for robot guidance, teleoperation, assembly and disassembly among others, if a suitable method for motion planning is available. In the basic variation of motion planning, the task is to generate a collision-free path for a movable object among known and static obstacles. Classically the problem was defined for a rigid 6 degrees-of-freedom body as 'the piano mover's problem'. However, the majority of the research has been conducted in the field of robotics, often under the title of path planning. Rapidly-Exploring Random Trees (RRTs) are a recently developed representation on which fast continuous domain path planners can be based. In this work, we have built a parallel path planning system based on RRTs that interleaves planning and execution, first evaluating it in simulation and then applying it to physical robots. Our distributed algorithm, PRRT (parallel RRT), introduces a parallel extension of previous RRT work, the process splitting and parallel cost penalty search with a comment on Real Time Stagnancy reduction, which improves re-planning efficiency, decreases latency involved in finding feasible paths and the quality of generated paths. PRRT is successfully applied to a real-time multi-robot system. In this paper we illustrate how it is possible to implement a parallel version of RRT based motion planner which yields optimal speed up.