The Robotics Institute

Carnegie Mellon Robotics Institute

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.

Abstract

Path planning in dynamic environments is significantly more difficult than navigation in static spaces due to the increased dimensionality of the problem, as well as the importance of returning good paths under time constraints. Anytime planners are ideal for these types of problems as they find an initial solution quickly and then improve it as time allows. In this paper, we develop an anytime planner that builds off of Safe Interval Path Planning (SIPP), which is a fast A*-variant for planning in dynamic environments that uses intervals instead of timesteps to represent the time dimension of the problem. In addition, we introduce an optional time-horizon after which the planner drops time as a dimension. On the theoretical side, we show that in the absence of time-horizon our planner can provide guarantees on completeness as well as bounds on the sub-optimality of the solution with respect to the original space-time graph. We also provide simulation experiments for planning for a UAV among 50 dynamic obstacles, where we can provide safe paths for the next 15 seconds of execution within 0.05 seconds. Our results provide a strong evidence for our planner working under realtime constraints.

Notes

Associated Lab(s) / Group(s): Search-based Planning Laboratory

Text Reference

Venkatraman Narayanan, Michael Phillips, and Maxim Likhachev, "Anytime Safe Interval Path Planning for Dynamic Environments," Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, October, 2012.

BibTeX Reference

@inproceedings{Narayanan_2012_7344,
   author = "Venkatraman Narayanan and Michael Phillips and Maxim Likhachev",
   title = "Anytime Safe Interval Path Planning for Dynamic Environments",
   booktitle = "Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems",
   month = "October",
   year = "2012",
}

The Robotics Institute

Menu