LiU Electronic Press
Full-text not available in DiVA
Author:
Warnquist, Håkan (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab) (Linköping University, The Institute of Technology) (APD)
Kvarnström, Jonas (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab) (APD)
Doherty, Patrick (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab) (Linköping University, The Institute of Technology)
Title:
Iterative Bounding LAO*
Department:
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab
Linköping University, The Institute of Technology
Publication type:
Conference paper (Refereed)
Language:
English
In:
Proceedings of the 19th European Conference on Artificial Intelligence (ECAI)
Publisher: IOS Press
Series:
Frontiers in Artificial Intelligence and Applications, ISSN 0922-6389; 215
Pages:
341-346
Year of publ.:
2010
URI:
urn:nbn:se:liu:diva-59883
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-59883
ISBN:
978-1-60750-605-8, 978-1-60750-606-5
Subject category:
Computer Science
SVEP category:
Computer science
Abstract(en) :

Iterative Bounding LAO* is a new algorithm for epsilon- optimal probabilistic planning problems where an absorbing goal state should be reached at a minimum expected cost from a given initial state. The algorithm is based on the LAO* algorithm for finding optimal solutions in cyclic AND/OR graphs. The new algorithm uses two heuristics, one upper bound and one lower bound of the optimal cost. The search is guided by the lower bound as in LAO*, while the upper bound is used to prune search branches. The algorithm has a new mechanism for expanding search nodes, and while maintaining the error bounds, it may use weighted heuristics to reduce the size of the explored search space. In empirical tests on benchmark problems, Iterative Bounding LAO* expands fewer search nodes compared to state of the art RTDP variants that also use two-sided bounds.

Available from:
2010-09-29
Created:
2010-09-29
Last updated:
2013-08-29
Statistics:
22 hits