Disruption-Limited Planning for Robot Navigation in Dynamic Environments

Path planning in the presence of dynamic obstacles is a fundamental problem in robotics with widespread applications. A typical approach to such problems is that a robot predicts the trajectories of dynamic obstacles, and plans its path while avoiding them. Such a formulation becomes limiting though for scenarios where an agent cannot complete its task efficiently, without disrupting the movement of dynamic obstacles. For example, when merging in heavy traffic or navigating through crowded corridors. In this paper, we propose a paradigm for planning in dynamic environments, called Disruption-Limited Planning (DLP), that allows a robot to disrupt the motions of dynamic obstacles in order to accomplish its task. DLP builds on the premise that while a robot may have to disrupt others’ trajectories to achieve its goals, it should try to limit the disruption. DLP assumes that it can estimate others’ response to its own actions/plans, and plans its own path while ensuring that no other agents’ disrupted trajectory cost gets worse than w-times their initial trajectory costs. While our formulation is motivated by the Stackelberg competitions, we show that DLP can be both more expressive and computationally more efficient compared to a Stackelberg planner. We present DLP paradigm, develop its efficient implementation based on A*, analyze its theoretical properties, and apply it to multiple planning in dynamic environment problems, including x,y,time planning, planning for self-driving, and planning for arm manipulation. We compare DLP with purely altruistic, purely egocentric, and optimal Stackelberg planners, demonstrating the efficacy of DLP over these alternatives.