Multi-Objective Path-Based D* Lite

April 2022

Multi-Objective Path-Based D* Lite

Authors:

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

Abstract:

Incremental graph search algorithms such as D* Lite reuse previous, and perhaps partial, searches to expedite subsequent path planning tasks. In this article, we are interested in developing incremental graph search algorithms for path finding problems to simultaneously optimize multiple objectives such as travel risk, arrival time, etc. This is challenging because in a multi-objective setting, the number of "Pareto-optimal" solutions can grow exponentially with respect to the size of the graph. This article presents a new multi-objective incremental search algorithm called Multi-Objective Path-Based D* Lite (MOPBD*) which leverages a path-based expansion strategy to prune dominated solutions. Additionally, we introduce a sub- optimal variant of MOPBD* to improve search efficiency while approximating the Pareto-optimal front. We numerically evaluate the performance of MOPBD* and its variants in various maps with two and three objectives. Results show that our approach is more efficient than search from scratch, and runs up to an order of magnitude faster than the existing incremental method for multi-objective path planning.
@article{Ren-2022-131914,
author = {Zhongqiang Ren And Sivakumar Rathinam And Maxim Likhachev And Howie Choset},
title = {Multi-Objective Path-Based D* Lite},
journal = {Proceedings of IEEE Robotics and Automation Letters},
year = {2022},
month = {April},
volume = {7},
number = {2},
pages = {3318 - 3325},
keywords = {Heuristic Search, Incremental Search},
}
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.