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

Kenny Chour, Sivakumar Rathinam, Ramamoorthi Ravi

TL;DR

This paper introduces S, a novel framework for efficiently finding approximate shortest paths that visit a set of required goals in a graph. By combining ideas from heuristic search and approximation algorithms for the Traveling Salesman Problem, S offers a 2-approximation guarantee and demonstrates significant improvements in performance over existing methods in terms of expanded nodes and computation time.

What Problem Does This Paper Address?

The paper tackles the Multi-Goal Path Finding (MGPF) problem. Imagine a robot needing to navigate a warehouse to pick up several items (goals) in a specific order, starting from its charging station and ending at a delivery point. The challenge is to find the shortest possible path that visits all these required "goal" locations, not necessarily in a predefined order. This problem is a generalization of the classic Traveling Salesman Problem and is known to be NP-hard. Existing approximation algorithms for MGPF typically involve constructing a Steiner tree (a minimum-cost tree connecting specific nodes) and then transforming it into a path. The efficiency and quality of these algorithms heavily depend on the Steiner tree construction step. This paper aims to improve this crucial step by developing a new heuristic-based approximation framework.

Methods

The core of the paper is the S (Steiner) framework, which enhances the Steiner tree construction phase of MGPF approximation algorithms. It draws inspiration from A* search and its bidirectional variants, integrating heuristic information to guide the search for the Steiner tree.

The framework has two main variants:

  • S*-unmerged: This variant uses a unidirectional A*-like search. Each goal node (and the start/end nodes) maintains its own search state (open and closed sets, g and f costs). These individual searches expand outwards, and when paths between different goal nodes are confirmed, they are considered for inclusion in the Steiner tree.
  • S*-merged: This variant is more sophisticated. It groups terminals (start, end, and goals) into components. Instead of individual searches, components nominate nodes with the lowest f-cost. When components merge, their search states are combined. This approach is inspired by Kruskal's algorithm for Minimum Spanning Trees.

Both variants rely on a UpdateSteinerTree procedure that ensures the Steiner tree construction adheres to two key properties: (SP) paths confirmed are indeed least-cost paths, and (K) adding paths to the tree does not create cycles and respects Kruskal's condition. The paper also details three specific "path confirmation criteria" for the S*-merged variant, based on established bidirectional search techniques (Bi-HS, Bi-BS, and Meet-in-the-Middle (MM)).

Datasets

The authors evaluated their algorithms on instances derived from the Multi-Agent Path Finding (MAPF) library. Specifically, they used five different 8-neighbor type grid maps: "den312d", "empty-32-32", "maze-32-32-4", "orz601d", and "random-64-64-10". For each map, they generated problem instances with varying numbers of terminals (10, 20, 30, 40, 50).

Key Insights and Ideas

  • Heuristics are crucial for MGPF: Integrating heuristic information, similar to how A* works for single-goal pathfinding, significantly reduces the search space for Steiner tree construction, leading to fewer expanded nodes.
  • Merging components can be more efficient: The S-merged variant, which groups terminals into components and merges them, generally outperforms the S-unmerged variant in terms of expanded nodes. This suggests that a more global view of connectivity among terminals is beneficial.
  • Meet-in-the-Middle (MM) is a strong choice for MGPF: The S*-MM variant, which leverages the MM search strategy for path confirmation, consistently performed the best among the proposed algorithms, especially when using strong heuristics.
  • Re-prioritization can help, but at a cost: The "re-prioritization" steps in the algorithms, while reducing expanded nodes, can slightly increase computation time. This trade-off needs careful consideration.
  • Heuristic quality matters: Stronger heuristics (higher weighting factor 'w') lead to fewer expanded nodes, demonstrating the effectiveness of good heuristic estimates.

Key Results

  • The proposed S framework provides 2-approximation algorithms* for MGPF.
  • The S-MM variant (using Meet-in-the-Middle for path confirmation) consistently expanded significantly fewer nodes than conventional solvers (like naive Kruskal's) and the S-unmerged variant.
  • For instances with 50 terminals and strong heuristics (w=1), S-MM expanded the least number of nodes* and had competitive computation times.
  • With re-prioritization enabled, the number of expanded nodes was reduced by nearly 50% on average.
  • The a-posteriori guarantees (ratio of found solution cost to a lower bound) were generally lower than the theoretical 2-approximation ratio, indicating good practical performance.

Limitations and Future Work

  • Computational Cost of Re-prioritization: While beneficial for reducing expanded nodes, the re-prioritization steps add computational overhead. The authors suggest exploring more efficient data structures for open sets to mitigate this.
  • Generalizability: The authors acknowledge that their framework might not outperform conventional solvers on every single instance.
  • Future Work: The authors suggest exploring decentralized implementations of the S* framework and investigating alternative data structures for faster implementations. They also mention that other bidirectional search methods could be explored in the future.

Summary updated

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.
BibTeX
@inproceedings{chour2021s,
  author = {Kenny Chour and Sivakumar Rathinam and Ramamoorthi Ravi},
  title = {{S*: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding}},
  booktitle = {Icaps},
  year = {2021},
}
Figure