Papers › S^*: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding
S^*: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding
Kenny Chour, Sivakumar Rathinam, Ramamoorthi Ravi
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections