# Bi-objective Search with Bi-directional A*

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 19 references that are in the map.
- First posted on arXiv 25 May 2021.

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

- [Enhanced Multi-Objective A* Using Balanced Binary Search Trees](https://mlsanity.com/paper/2202.08992/) (2022)
- [Enhanced Methods for the Weight Constrained Shortest Path Problem](https://mlsanity.com/paper/2207.14744/) (2022)
- [Enhanced Multi-Objective A* with Partial Expansion](https://mlsanity.com/paper/2212.03712/) (2022)
- [Multi-Objective Search: Algorithms, Applications, and Emerging Directions](https://mlsanity.com/paper/2510.25504/) (2025)
- [Approximate Multi-Objective Search Under Rulebooks](https://mlsanity.com/paper/2608.04398/) (2026)

## Abstract (arXiv)

Bi-objective search is a well-known algorithmic problem, concerned with finding a set of optimal solutions in a two-dimensional domain. This problem has a wide variety of applications such as planning in transport systems or optimal control in energy systems. Recently, bi-objective A*-based search (BOA*) has shown state-of-the-art performance in large networks. This paper develops a bi-directional and parallel variant of BOA*, enriched with several speed-up heuristics. Our experimental results on 1,000 benchmark cases show that our bi-directional A* algorithm for bi-objective search (BOBA*) can optimally solve all of the benchmark cases within the time limit, outperforming the state of the art BOA*, bi-objective Dijkstra and bi-directional bi-objective Dijkstra by an average runtime improvement of a factor of five over all of the benchmark instances.