Abstract
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.
Introduction
The Multi-Goal Path Finding (MGPF) problem is a critical challenge in robotics and logistics, where an agent must visit a set of target locations (terminals) with minimal total travel cost. This problem is a generalization of the Steiner Traveling Salesman Problem and is known to be NP-Hard. While traditional 2-approximation algorithms exist, they often rely on Steiner tree constructions that do not leverage heuristic information, leading to exhaustive and inefficient searches in large-scale environments.
In this paper, we introduce the $S^*$ (Steiner) framework. By integrating heuristic search techniques like A into the Steiner tree construction phase, $S^*$ significantly reduces the search space while maintaining a theoretical 2-approximation guarantee. This approach allows the algorithm to "steer" the search toward goals, avoiding the blind expansion characteristic of traditional primal-dual or Kruskal-based methods.
The S* Framework
The $S^*$ framework operates by maintaining two fundamental properties: the Shortest Path (SP) property and Kruskal’s condition (K). These ensure that the resulting Steiner tree is of high quality despite the heuristic-driven pruning. The framework is implemented in two primary variants:
- $S^*$-unmerged: Each goal terminal maintains its own "open" and "closed" sets, effectively running independent A* searches to connect with other goals.
- $S^*$-merged: This variant treats goals as components that grow and merge upon meeting, similar to Kruskal’s algorithm. Within this variant, we evaluate three sub-strategies based on bi-directional search stopping criteria:
- $S^*$-HS: Utilizes the $f_{min}$ rule from bi-directional heuristic search.
- $S^*$-BS: Employs a $g_{min}$ rule, mimicking classic primal-dual algorithms.
- $S^*$-MM: Incorporates "Meet-in-the-Middle" (MM) logic, which often provides the most aggressive pruning.
Experimental Evaluation
We evaluated the $S^*$ framework using the Multi-Agent Path Finding (MAPF) benchmark library on various 8-neighbor grid maps, including complex environments like den312d and randomized obstacle maps like random-64-64-10. Tests were conducted with terminal counts ($N$) ranging from 10 to 50.
Results and Discussion
The $S^*$ framework demonstrated a profound reduction in the search space compared to baseline methods. In the complex den312d map with 50 goals, the Naive Kruskal algorithm expanded approximately 120,000 nodes. In contrast, the $S^*$-MM variant required only 1,200 expansions—a 100-fold improvement in efficiency.
Quantitatively, the $S^*$ variants consistently outperformed traditional solvers in both node expansions and total runtime as the number of terminals increased. While the theoretical guarantee is a 2-approximation, empirical results showed that the actual solution costs were typically within 1.8x to 1.9x of the optimal lower bound.
We also observed that an optional re-prioritization step could further reduce node expansions by up to 50%, although it introduces additional computational bookkeeping. The $S^*$-MM variant proved to be the most robust, particularly in scenarios where heuristic estimates were less accurate.
Conclusion
The $S^*$ framework successfully bridges the gap between heuristic search and Steiner tree approximation. By directing the search frontiers using heuristic information, $S^*$ achieves massive reductions in computational overhead without sacrificing the 2-approximation guarantee. Future work will explore decentralized implementations of $S^*$ for multi-robot systems and the use of more advanced data structures to further optimize open set management.
Summary updated