LiU Electronic Press
Full-text not available in DiVA
Author:
Jonsson, Peter (Linköping University, The Institute of Technology) (Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory)
Haslum, Patrik (Linköping University, The Institute of Technology) (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab)
Bäckström, Christer (Linköping University, The Institute of Technology) (Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory)
Title:
Towards efficient universal planning: A randomized approach
Department:
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory
Linköping University, The Institute of Technology
Publication type:
Article in journal (Refereed)
Language:
English
Publisher: Elsevier
Status:
Published
In:
Artificial Intelligence(ISSN 0004-3702)(EISSN 0374-2539)
Volume:
117
Issue:
1
Pages:
1-29
Year of publ.:
2000
URI:
urn:nbn:se:liu:diva-47724
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-47724
Subject category:
Engineering and Technology
SVEP category:
TECHNOLOGY
Abstract(en) :

One of the most widespread approaches to reactive planning is Schoppers' universal plans. We propose a stricter definition of universal plans which guarantees a weak notion of soundness, not present in the original definition, and isolate three different types of completeness that capture different behaviors exhibited by universal plans. We show that universal plans which run in polynomial time and are of polynomial size cannot satisfy even the weakest type of completeness unless the polynomial hierarchy collapses. By relaxing either the polynomial time or the polynomial space requirement, the construction of universal plans satisfying the strongest type of completeness becomes trivial. As an alternative approach, we study randomized universal planning. By considering a randomized version of completeness and a restricted (but nontrivial) class of problems, we show that there exists randomized universal plans running in polynomial time and using polynomial space which are sound and complete for the restricted class of problems. We also report experimental results on this approach to planning, showing that the performance of a randomized planner is not easily compared to that of a deterministic planner.

Available from:
2009-10-11
Created:
2009-10-11
Last updated:
2011-02-24
Statistics:
9 hits