# Enhanced Multi-Objective A* Using Balanced Binary Search Trees

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 18 Feb 2022.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Multi-Objective Graph Heuristic Search for Terrestrial Robot Design](https://mlsanity.com/paper/2107.05858/) (2021)
- [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)
- [Multi-Objective Path-Based D* Lite](https://mlsanity.com/paper/2108.00710/) (2021)
- [Bi-objective Search with Bi-directional A*](https://mlsanity.com/paper/2105.11888/) (2021)

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

- [Enhanced Multi-Objective A* with Partial Expansion](https://mlsanity.com/paper/2212.03712/) (2022)
- [Heuristic Search for Path Finding with Refuelling](https://mlsanity.com/paper/2309.10796/) (2023)
- [Search-Based Path Planning in Interactive Environments among Movable Obstacles](https://mlsanity.com/paper/2410.18333/) (2024)
- [OPMOS: Ordered Parallel Algorithm for Multi-Objective Shortest-Paths](https://mlsanity.com/paper/2411.16667/) (2024)
- [Resource Constrained Pathfinding with A* and Negative Weights](https://mlsanity.com/paper/2503.11037/) (2025)

## Abstract (arXiv)

This work addresses a Multi-Objective Shortest Path Problem (MO-SPP) on a graph where the goal is to find a set of Pareto-optimal solutions from a start node to a destination in the graph. A family of approaches based on MOA* have been developed to solve MO-SPP in the literature. Typically, these approaches maintain a "frontier" set at each node during the search process to keep track of the non-dominated, partial paths to reach that node. This search process becomes computationally expensive when the number of objectives increases as the number of Pareto-optimal solutions becomes large. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by incrementally constructing balanced binary search trees within the MOA* search framework. We first show that our approach correctly finds the Pareto-optimal front, and then provide extensive simulation results for problems with three, four and five objectives to show that our method runs faster than existing techniques by up to an order of magnitude.