SIPP: Safe Interval Path Planning for Dynamic Environments - Robotics Institute Carnegie Mellon University

SIPP: Safe Interval Path Planning for Dynamic Environments

Mike Phillips and Maxim Likhachev
Conference Paper, Proceedings of (ICRA) International Conference on Robotics and Automation, pp. 5628 - 5635, May, 2011

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.

BibTeX

@conference{Phillips-2011-109569,
author = {Mike Phillips and Maxim Likhachev},
title = {SIPP: Safe Interval Path Planning for Dynamic Environments},
booktitle = {Proceedings of (ICRA) International Conference on Robotics and Automation},
year = {2011},
month = {May},
pages = {5628 - 5635},
}