# Multi-Objective Path-Based D* Lite

arXiv: https://arxiv.org/abs/2108.00710 · HTML: https://mlsanity.com/paper/2108.00710/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 27 references that are in the map.
- First posted on arXiv 2 Aug 2021.

## Builds on (most cited first, 5 of 5)

- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Approximate bi-criteria search by efficient representation of subsets of the Pareto-optimal frontier](https://mlsanity.com/paper/2006.10302/) (2020)
- [Subdimensional Expansion for Multi-objective Multi-agent Path Finding](https://mlsanity.com/paper/2102.01353/) (2021)
- [A Receding Horizon Multi-Objective Planner for Autonomous Surface Vehicles in Urban Waterways](https://mlsanity.com/paper/2007.08362/) (2020)

## Built on by (most cited first, 7 of 7)

- [Enhanced Multi-Objective A* Using Balanced Binary Search Trees](https://mlsanity.com/paper/2202.08992/) (2022)
- [URA*: Uncertainty-aware Path Planning using Image-based Aerial-to-Ground Traversability Estimation for Off-road Environments](https://mlsanity.com/paper/2309.08814/) (2023)
- [Enhanced Multi-Objective A* with Partial Expansion](https://mlsanity.com/paper/2212.03712/) (2022)
- [Search-Based Path Planning in Interactive Environments among Movable Obstacles](https://mlsanity.com/paper/2410.18333/) (2024)
- [AI-Driven Multi-Agent Vehicular Planning for Battery Efficiency and QoS in 6G Smart Cities](https://mlsanity.com/paper/2509.14877/) (2025)
- [Multi-Objective Search: Algorithms, Applications, and Emerging Directions](https://mlsanity.com/paper/2510.25504/) (2025)
- [Learning-Based Motion Planning for Dynamic Environments: From Foundational Algorithms to Emerging Paradigms](https://mlsanity.com/paper/2608.00625/) (2026)

## Abstract (arXiv)

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.