Better Time Constrained Search via Randomization and PostprocessingReport as inadecuate




Better Time Constrained Search via Randomization and Postprocessing - Download this document for free, or read online. Document in PDF available to download.

planning, postprocessing, Artificial Intelligence

Additional contributors:

Subject-Keyword: planning postprocessing Artificial Intelligence

Type of item: Computing Science Technical Report

Computing science technical report ID: TR13-02

Language: English

Place:

Time:

Description: Most of the satisficing planners which are based on heuristic search iteratively improve their solution quality through an anytime approach. Typically, the lowest-cost solution found so far is used to constrain the search. This avoids areas of the state space which cannot directly lead to lower cost solutions. However, in conjunction with a post-processing plan improvement system such as ARAS, this bounding approach can harm a planner’s performance. The new anytime search framework of Diverse Any-Time Search avoids this behaviour by taking advantage of the fact that post-processing can often improve a lower quality input plan to a superior final plan. The framework encourages diversity of -raw- plans by restarting and using randomization, and does not use previous solutions for bounding. This gives a post-processing system a more diverse set of plans to work on, which improves performance. When adding both Diverse Any-Time Search and the ARAS post-processor to LAMA- 2011, the winner of the most recent IPC planning competi- tion, and AEES, the Anytime Explicit Estimation Algorithm, the performance on the 550 IPC 2008 and IPC 2011 problems is improved by almost 60 points according to the IPC metric, from 511 to over 570 on LAMA-2011, and 73 points from 440 to over 513 on AEES.

Date created: 2013

DOI: doi:10.7939-R3XW47Z9H

License information: Creative Commons Attribution 3.0 Unported

Rights:





Author: Xie, Fan Valenzano, Richard Müller, Martin

Source: https://era.library.ualberta.ca/


Teaser



Better Time Constrained Search via Randomization and Postprocessing Fan Xie and Richard Valenzano and Martin Müller Computing Science, University of Alberta Edmonton, Canada {fxie2, valenzan, mmueller}@ualberta.ca Abstract Most of the satisficing planners which are based on heuristic search iteratively improve their solution quality through an anytime approach.
Typically, the lowest-cost solution found so far is used to constrain the search.
This avoids areas of the state space which cannot directly lead to lower cost solutions.
However, in conjunction with a post-processing plan improvement system such as A RAS, this bounding approach can harm a planner’s performance. The new anytime search framework of Diverse Any-Time Search avoids this behaviour by taking advantage of the fact that post-processing can often improve a lower quality input plan to a superior final plan.
The framework encourages diversity of “raw” plans by restarting and using randomization, and does not use previous solutions for bounding.
This gives a post-processing system a more diverse set of plans to work on, which improves performance.
When adding both Diverse Any-Time Search and the A RAS post-processor to LAMA2011, the winner of the most recent IPC planning competition, and AEES, the Anytime Explicit Estimation Algorithm, the performance on the 550 IPC 2008 and IPC 2011 problems is improved by almost 60 points according to the IPC metric, from 511 to over 570 on LAMA-2011, and 73 points from 440 to over 513 on AEES. Introduction Since IPC-2008, the satisficing planning community has been using the IPC scoring function to evaluate planners. This function emphasizes both plan quality and coverage simultaneously.
Many satisficing planners such as LAMA (Richter and Westphal 2010) and Fast Downward (Helmert 2006) use an anytime approach: they attempt to quickly find an initial plan of possibly low quality, then use the remaining time to improve upon this plan.
Post-processing, as implem...





Related documents