Efficient Black-Box Planning Using Macro-Actions with Focused Effects

Allen, Cameron; Katz, Michael; Klinger, Tim; Konidaris, George; Riemer, Matthew; Tesauro, Gerald

doi:10.24963/ijcai.2021/554

Efficient Black-Box Planning Using Macro-Actions with Focused Effects

Cameron Allen, Michael Katz, Tim Klinger, George Konidaris, Matthew Riemer, Gerald Tesauro

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4024-4031.

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

Keywords

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

Abstract

The difficulty of deterministic planning increases exponentially with search-tree depth. Black-box planning presents an even greater challenge, since planners must operate without an explicit model of the domain. Heuristics can make search more efficient, but goal-aware heuristics for black-box planning usually rely on goal counting, which is often quite uninformative. In this work, we show how to overcome this limitation by discovering macro-actions that make the goal-count heuristic more accurate. Our approach searches for macro-actions with focused effects (i.e. macros that modify only a small number of state variables), which align well with the assumptions made by the goal-count heuristic. Focused macros dramatically improve black-box planning efficiency across a wide range of planning domains, sometimes beating even state-of-the-art planners with access to a full domain model.

Cameron Allen, Michael Katz, Tim Klinger, George Konidaris, Matthew Riemer, and Gerald Tesauro. 2021. Efficient Black-Box Planning Using Macro-Actions with Focused Effects. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4024–4031. https://doi.org/10.24963/ijcai.2021/554

@inproceedings{ijcai2021p554,
  title     = {Efficient Black-Box Planning Using Macro-Actions with Focused Effects},
  author    = {Allen, Cameron and Katz, Michael and Klinger, Tim and Konidaris, George and Riemer, Matthew and Tesauro, Gerald},
  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     = {4024--4031},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/554},
  url       = {https://doi.org/10.24963/ijcai.2021/554},
}

TY  - CPAPER
TI  - Efficient Black-Box Planning Using Macro-Actions with Focused Effects
AU  - Allen, Cameron
AU  - Katz, Michael
AU  - Klinger, Tim
AU  - Konidaris, George
AU  - Riemer, Matthew
AU  - Tesauro, Gerald
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4024
EP  - 4031
DO  - 10.24963/ijcai.2021/554
UR  - https://doi.org/10.24963/ijcai.2021/554
ER  -