S${}^{\ast }$: 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…