Real-time randomized path planning for robot navigation

September 2002

Real-time randomized path planning for robot navigation

Authors:

James Bruce and Manuela Veloso
Conference Paper
Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems

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.
@conference{Bruce-2002-8565,
author = {James Bruce And Manuela Veloso},
title = {Real-time randomized path planning for robot navigation},
booktitle = {Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2002},
month = {September},
volume = {3},
pages = {2383 - 2388},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.