Journal
IEEE ROBOTICS AND AUTOMATION LETTERS
Volume 7, Issue 2, Pages 3318-3325Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/LRA.2022.3146918
Keywords
Motion and path planning; planning under uncertainty
Categories
Funding
- National Science Foundation [2120219, 2120529]
- Direct For Computer & Info Scie & Enginr
- Div Of Information & Intelligent Systems [2120529] Funding Source: National Science Foundation
- Direct For Computer & Info Scie & Enginr
- Div Of Information & Intelligent Systems [2120219] Funding Source: National Science Foundation
Ask authors/readers for more resources
This article introduces a new multi-objective incremental search algorithm called MOPBD*, which leverages path-based expansion strategy to prune dominated solutions. A sub-optimal variant of MOPBD* is also introduced to improve search efficiency while approximating the Pareto-optimal front. Numerical evaluations 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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available