Type-WA*: Using Exploration in Bounded Suboptimal Planning

Eldan Cohen; Richard Valenzano; Sheila McIlraith

IJCAI 2021poster1 citations

Type-WA*: Using Exploration in Bounded Suboptimal Planning

Eldan Cohen, Richard Valenzano, Sheila McIlraith

Abstract

Previous work on satisficing planning using greedy best-first search (GBFS) has shown that non-greedy, randomized exploration can help escape uninformative heuristic regions and solve hard problems faster. Despite their success when used with GBFS, such exploration techniques cannot be directly applied to bounded suboptimal algorithms like Weighted A* (WA*) without losing the solution-quality guarantees. In this work, we present Type-WA*, a novel bounded suboptimal planning algorithm that augments WA* with type-based exploration while still satisfying WA*'s theoretical solution-quality guarantee. Our empirical analysis shows that Type-WA* significantly increases the number of solved problems, when used in conjunction with each of three popular heuristics. Our analysis also provides insight into the runtime vs. solution cost trade-off.

Planning and Scheduling: Planning AlgorithmsPlanning and Scheduling: Search in Planning and SchedulingHeuristic Search and Game Playing: Heuristic Search

BibTeX

@inproceedings{ijcai2021p557,
  title     = {Type-WA*: Using Exploration in Bounded Suboptimal Planning},
  author    = {Cohen, Eldan and Valenzano, Richard and McIlraith, Sheila},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Zhi-Hua Zhou},
  pages     = {4047--4053},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/557},
  url       = {https://doi.org/10.24963/ijcai.2021/557},
}