The Role of Macros in Tractable Planning over Causal Graphs
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1936-1940.
Abstract
The complexity of existing planners is bounded by the length of the resulting plan, a fact that limits planning to domains with relatively short solutions. We present a novel planning algorithm that uses the causal graph of a domain to decompose it into subproblems and stores subproblem plans in memory as macros. In many domains, the resulting plan can be expressed using relatively few macros, making it possible to generate exponential length plans in polynomial time. We show that our algorithm is complete, and that there exist special cases for which it is optimal and polynomial. Experimental results demonstrate the potential of using macros to solve planning domains with long solution plans.
@inproceedings{ijcai2007p312,
title = {The Role of Macros in Tractable Planning over Causal Graphs},
author = {Jonsson, Anders},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {1936--1940},
year = {2007},
url = {https://ijcai.org/proceedings/2007/312},
}
TY - CPAPER TI - The Role of Macros in Tractable Planning over Causal Graphs AU - Jonsson, Anders T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 1936 EP - 1940 UR - https://ijcai.org/proceedings/2007/312 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
