SIPP: Safe interval path planning for dynamic environments
Authors:
- 1 May 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10504729,p. 5628-5635
Abstract
Robotic path planning in static environments is a thoroughly studied problem that can typically be solved very efficiently. However, planning in the presence of dynamic obstacles is still computationally challenging because it requires adding time as an additional dimension to the search-space explored by the planner. In order to avoid the increase in the dimensionality of the planning problem, most real-time approaches to path planning treat dynamic obstacles as static and constantly re-plan as dynamic obstacles move. Although gaining efficiency, these approaches sacrifice optimality and even completeness. In this paper, we develop a planner that builds on the observation that while the number of safe timesteps in any configuration may be unbounded, the number of safe time intervals in a configuration is finite and generally very small. A safe interval is a time period for a configuration with no collisions and if it were extended one timestep in either direction, it would then be in collision. The planner exploits this observation and constructs a search-space with states defined by their configuration and safe interval, resulting in a graph that generally only has a few states per configuration. On the theoretical side, we show that our planner can provide the same optimality and completeness guarantees as planning with time as an additional dimension. On the experimental side, in simulation tests with up to 200 dynamic obstacles, we show that our planner is significantly faster, making it feasible to use in real-time on robots operating in large dynamic environments. We also ran several real robot trials on the PR2, a mobile manipulation platform.Keywords
This publication has 9 references indexed in Scilit:
- Generalized velocity obstacles2009
- Time-bounded lattice for efficient planning in dynamic environments2009
- Smooth path planning in constrained environments2009
- Greedy but Safe Replanning under Kinodynamic Constraints2007
- Anytime path planning and replanning in dynamic environments2006
- Roadmap-based motion planning in dynamic environmentsIEEE Transactions on Robotics, 2005
- Safe motion planning in dynamic environments2005
- Randomized Kinodynamic Motion Planning with Moving ObstaclesThe International Journal of Robotics Research, 2002
- The dynamic window approach to collision avoidanceIEEE Robotics & Automation Magazine, 1997