Type-WA*: Using Exploration in Bounded Suboptimal Planning

Cohen, Eldan; Valenzano, Richard; McIlraith, Sheila

doi:10.24963/ijcai.2021/557

Type-WA*: Using Exploration in Bounded Suboptimal Planning

Eldan Cohen, Richard Valenzano, Sheila McIlraith

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4047-4053.

https://doi.org/10.24963/ijcai.2021/557

Keywords

Planning and Scheduling: Planning Algorithms
Planning and Scheduling: Search in Planning and Scheduling
Heuristic Search and Game Playing: Heuristic Search

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.

Eldan Cohen, Richard Valenzano, and Sheila McIlraith. 2021. Type-WA*: Using Exploration in Bounded Suboptimal Planning. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4047–4053. https://doi.org/10.24963/ijcai.2021/557

@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    = {Prof. 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},
}

TY  - CPAPER
TI  - Type-WA*: Using Exploration in Bounded Suboptimal Planning
AU  - Cohen, Eldan
AU  - Valenzano, Richard
AU  - McIlraith, Sheila
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4047
EP  - 4053
DO  - 10.24963/ijcai.2021/557
UR  - https://doi.org/10.24963/ijcai.2021/557
ER  -