# S^*: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 26 references that are in the map.
- First posted on arXiv 15 Mar 2021.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions](https://mlsanity.com/paper/1703.03868/) (2017)

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

- [MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding](https://mlsanity.com/paper/2103.09979/) (2021)
- [Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions](https://mlsanity.com/paper/2205.04548/) (2022)

## Abstract (arXiv)

We combine ideas from uni-directional and bi-directional heuristic search, and approximation algorithms for the Traveling Salesman Problem, to develop a novel framework for a Multi-Goal Path Finding (MGPF) problem that provides a 2-approximation guarantee. MGPF aims to find a least-cost path from an origin to a destination such that each node in a given set of goals is visited at least once along the path. We present numerical results to illustrate the advantages of our framework over conventional alternates in terms of the number of expanded nodes and run time.