Planning with Abstraction Hierarchies can be Exponentially Less Efficient
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Planning. Pages 1599-1604.
Abstract
It is well-known that state abstraction can speed up planning exponentially, under ideal conditions. We add to the knowledge-showing that state abstraction may likewise slow down planning exponentially, and even result in generating an exponentially longer solution than necessary. This phenomenon can occur for abstraction hierarchies which are generated automatically by the ALPINE and HIGHPOINT algorithms. We further show that there is little hope of any drastic improvement upon these algorithms-it is computationally difficult to generate abstraction hierarchies which allow finding good approximations of optimal plans.
@inproceedings{ijcai1995p206,
title = {Planning with Abstraction Hierarchies can be Exponentially Less Efficient},
author = {Bäckström, Christer and Jonsson, Peter},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {1599--1604},
year = {1995},
note = {Planning},
url = {https://ijcai.org/proceedings/1995/206},
}
TY - CPAPER TI - Planning with Abstraction Hierarchies can be Exponentially Less Efficient AU - Bäckström, Christer AU - Jonsson, Peter T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 1599 EP - 1604 UR - https://ijcai.org/proceedings/1995/206 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
