Learning and Exploiting Progress States in Greedy Best-First Search

Patrick Ferber; Liat Cohen; Jendrik Seipp; Thomas Keller

IJCAI 2022poster6 citations

Learning and Exploiting Progress States in Greedy Best-First Search

Patrick Ferber, Liat Cohen, Jendrik Seipp, Thomas Keller

Abstract

Previous work introduced the concept of progress states. After expanding a progress state, a greedy best-first search (GBFS) will only expand states with lower heuristic values. Current methods can identify progress states only for a single task and only after a solution for the task has been found. We introduce a novel approach that learns a description logic formula characterizing all progress states in a classical planning domain. Using the learned formulas in a GBFS to break ties in favor of progress states often significantly reduces the search effort.

Search: Heuristic SearchPlanning and Scheduling: Learning in Planning and SchedulingPlanning and Scheduling: Search in Planning and SchedulingSearch: Search and Machine Learning

BibTeX

@inproceedings{ijcai2022p657,
  title     = {Learning and Exploiting Progress States in Greedy Best-First Search},
  author    = {Ferber, Patrick and Cohen, Liat and Seipp, Jendrik and Keller, Thomas},
  booktitle = {Proceedings of the Thirty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-22}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Lud De Raedt},
  pages     = {4740--4746},
  year      = {2022},
  month     = {7},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2022/657},
  url       = {https://doi.org/10.24963/ijcai.2022/657},
}