# Enhanced Multi-Objective A* with Partial Expansion

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 21 references that are in the map.
- First posted on arXiv 6 Dec 2022.

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

- [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)
- [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)
- [Enhanced Multi-Objective A* Using Balanced Binary Search Trees](https://mlsanity.com/paper/2202.08992/) (2022)
- [A Conflict-Based Search Framework for Multi-Objective Multi-Agent Path Finding](https://mlsanity.com/paper/2101.03805/) (2021)

## Abstract (arXiv)

The Multi-Objective Shortest Path Problem (MO-SPP), typically posed on a graph, determines a set of paths from a start vertex to a destination vertex while optimizing multiple objectives. In general, there does not exist a single solution path that can simultaneously optimize all the objectives and the problem thus seeks to find a set of so-called Pareto-optimal solutions. To address this problem, several Multi-Objective A* (MOA*) algorithms were recently developed to quickly compute solutions with quality guarantees. However, these MOA* algorithms often suffer from high memory usage, especially when the branching factor (i.e. the number of neighbors of any vertex) of the graph is large. This work thus aims at reducing the high memory consumption of MOA* with little increase in the runtime. By generalizing and unifying several single- and multi-objective search algorithms, we develop the Runtime and Memory Efficient MOA* (RME-MOA*) approach, which can balance between runtime and memory efficiency by tuning two user-defined hyper-parameters.