Multi-Objective Safe-Interval Path Planning with Dynamic Obstacles

June 2022

Multi-Objective Safe-Interval Path Planning with Dynamic Obstacles

Authors:

Zhongqiang Ren, Sivakumar Rathinam, Maxim Likhachev, and Howie Choset

Abstract:

Path planning among dynamic obstacles is a fundamental problem in Robotics with numerous applications. In this work, we investigate a problem called Multi-Objective Path Planning with Dynamic Obstacles (MOPPwDO), which requires finding collision-free Pareto-optimal paths amid obstacles moving along known trajectories while simultaneously optimizing multiple conflicting objectives, such as arrival time, communication robustness and obstacle clearance. Most of the existing multi-objective A*-like planners consider no dynamic obstacles, and naively applying them to address MOPPwDO can lead to large computation times. On the other hand, efficient algorithms such as Safe-Interval Path Planing (SIPP) can handle dynamic obstacles but for a single objective. In this work, we develop an algorithm called MO-SIPP by leveraging both the notion of safe intervals from SIPP to efficiently represent the search space in the presence of dynamic obstacles, and search techniques from multi-objective A* algorithms. We show that MO-SIPP is guaranteed to find the entire Pareto-optimal front, and verify MO-SIPP with extensive numerical tests with two and three objectives. The results show that the MO-SIPP runs up to an order of magnitude faster than the conventional alternates.
@article{Ren-2022-132312,
author = {Zhongqiang Ren And Sivakumar Rathinam And Maxim Likhachev And Howie Choset},
title = {Multi-Objective Safe-Interval Path Planning with Dynamic Obstacles},
journal = {Proceedings of IEEE Robotics and Automation Letters},
year = {2022},
month = {June},
volume = {7},
number = {3},
pages = {8154 - 8161},
keywords = {Motion and path planning},
}
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.