Trees of Shortest Paths vs. Steiner Trees: Understanding and Improving Delete Relaxation Heuristics

Keyder, Emil; Geffner, Hector

Trees of Shortest Paths vs. Steiner Trees: Understanding and Improving Delete Relaxation Heuristics

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 1734-1738.

Abstract

Heuristic search using heuristics extracted from the delete relaxation is one of the most effective methods in planning. Since finding the optimal solution of the delete relaxation is intractable, various heuristics introduce independence assumptions, the implications of which are not yet fully understood. Here we use concepts from graph theory to show that in problems with unary action preconditions, the delete relaxation is closely related to the Steiner Tree problem, and that the independence assumption for the set of goals results in a tree-of-shortest-paths approximation. We analyze the limitations of this approximation and develop an alternative method for computing relaxed plans that addresses them. The method is used to guide a greedy best-first search, where it is shown to improve plan quality and coverage over several benchmark domains.Emil Ragip Keyder, Hector Geffner

Emil Keyder, and Hector Geffner. 2009. Trees of Shortest Paths vs. Steiner Trees: Understanding and Improving Delete Relaxation Heuristics. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09. IJCAI, 1734–1738. https://ijcai.org/proceedings/2009/289

@inproceedings{ijcai2009p289,
  title     = {Trees of Shortest Paths vs. Steiner Trees: Understanding and Improving Delete Relaxation Heuristics},
  author    = {Keyder, Emil and Geffner, Hector},
  booktitle = {Proceedings of the Twenty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-09}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Hiroaki Kitano},
  pages     = {1734--1738},
  year      = {2009},
  url       = {https://ijcai.org/proceedings/2009/289},
}

TY  - CPAPER
TI  - Trees of Shortest Paths vs. Steiner Trees: Understanding and Improving Delete Relaxation Heuristics
AU  - Keyder, Emil
AU  - Geffner, Hector
T2  - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2009
SP  - 1734
EP  - 1738
UR  - https://ijcai.org/proceedings/2009/289
ER  -