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

Authors

  • Kenny Chour Texas A & M University
  • Sivakumar Rathinam Texas A & M
  • Ramamoorthi Ravi Carnegie Mellon University

DOI:

https://doi.org/10.1609/icaps.v31i1.15950

Keywords:

Applications And Case Studies Of Planning And Scheduling Techniques, Classical Planning Techniques And Analysis, Plan Recognition, Plan Management And Goal Reasoning

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.
ICAPS-21 Proceedings Cover

Downloads

Published

2021-05-17

How to Cite

Chour, K., Rathinam, S., & Ravi, R. (2021). S*: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 85-93. https://doi.org/10.1609/icaps.v31i1.15950

Issue

Vol. 31 (2021): Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling

Section

Main Track