Real-time randomized path planning for robot navigation

Abstract

Mobile robots often must find a trajectory to another position in their environment, subject to constraints. This is the problem of planning a path through a continuous domain Rapidly-exploring random trees (RRTs) are a recently developed representation on which fast continuous domain path planners can be based. In this work, we build a path planning system based on RRTs that interleaves planning and execution, first evaluating it in simulation and then applying it to physical robots. Our planning algorithm, ERRT (execution extended RRT), introduces two novel extensions of previous RRT work, the waypoint cache and adaptive cost penalty search, which improve replanning efficiency and the quality of generated paths. ERRT is successfully applied to a real-time multi-robot system. Results demonstrate that ERRT is significantly more efficient for replanning than a basic RRT planner, performing competitively with or better than existing heuristic and reactive real-time path planning approaches. ERRT is a significant step forward with the potential for making path planning common on real robots, even in challenging continuous, highly dynamic domains.