The Joy of Forgetting: Faster Anytime Search via Restarting

File Size Format
64992_1.pdf 266Kb Adobe PDF View
Title The Joy of Forgetting: Faster Anytime Search via Restarting
Author Richter, Silvia; Thayer, Jordan T; Ruml, Wheeler
Publication Title ICAPS 2010 Conference Proceedings
Editor Ronen Brafman, Hector Geffner, Jorg Hoffmann, Henry Kautz
Year Published 2010
Place of publication California
Publisher The AAAI Press
Abstract Anytime search algorithms solve optimisation problems by quickly finding a (usually suboptimal) first solution and then finding improved solutions when given additional time. To deliver an initial solution quickly, they are typically greedy with respect to the heuristic cost-to-go estimate h. In this paper, we show that this low-h bias can cause poor performance if the greedy search makes early mistakes. Building on this observation, we present a new anytime approach that restarts the search from the initial state every time a new solution is found. We demonstrate the utility of our method via experiments in PDDL planning as well as other domains, and show that it is particularly useful for problems where the heuristic has systematic errors.
Peer Reviewed Yes
Published Yes
Publisher URI
Copyright Statement Copyright 2010 AAAI Press. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. Please refer to the conference's website for access to the definitive, published version.
Conference name ICAPS 2010: 20th International Conference on Automated Planning and Scheduling
Location Canada
Date From 2010-05-12
Date To 2010-05-16
Date Accessioned 2010-10-12
Language en_AU
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Artificial Intelligence and Image Processing
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice