Automatic Heuristic Selection, on a Problem by Problem Basis, Using an Analytical Model and In Situ Sampling

Show simple item record

dc.contributor.advisor Barley, M en
dc.contributor.author Franco Aixela, Santiago en
dc.date.accessioned 2012-04-02T20:57:48Z en
dc.date.issued 2012 en
dc.date.submitted 2012 en
dc.identifier.uri http://hdl.handle.net/2292/16434 en
dc.description.abstract One of the main drives in automated planning is to automate the translation from the knowledge level description of the problem to the symbol level implementation of a solver for that problem. The field is at the point where there are techniques that can automatically synthesize very large numbers of heuristics that can be used by heuristic search based problem solvers [Holte et al., 2005], [Edelkamp, 2006], [Culberson and Schae_er, 1994], [Haslum et al., 2007], etc. However, currently there is no a priori method available to automatically tailor them to a specific problem instance. Nor are there any automated techniques to automatically determine which heuristics are best for a problem. There are some automated techniques to generate problem specific heuristics based on in situ gathered information but they are not competitive with state-of-the-art manual heuristic selection. Currently, the state-of-the-art is for the user to determine this a priori. This is usually done by running each of the heuristics on a wide range of problems in the chosen domain. The heuristic that is best on average for the domain is then used for each problem in the domain. The current approach is empirical, this thesis explores an analytical approach; which uses a simplified run-time formula that represents the important components of the problem-solver. This formula predicts the impact of the selected heuristic subsets upon run-time. Some of the formula's parameters can be determined a priori (e.g., how long it takes to check for a goal state) while others can only be determined a posteriori. Unfortunately, finding out those values after the problem has been solved is not usually very useful. This thesis explores the possibility of using the early parts of the problem-solving task(in situ sampling) to determine approximate values for those parameters. A system called RIDA* was created to do this. The danger is that the cost of determining these approximate values may outweigh the benefits those values bring. The ideal situation is to only do as much extra work as is needed to obtain the approximate values that allow us to make a decision that saves enough work to compensate for the time invested. We found that RIDA* was competitive, and in some cases significantly faster, than manual heuristic selection. However, there are two caveats: RIDA* has a scalability issue for large heuristic sets due to the combinatorial explosion in the heuristics search space. Also RIDA*'s in situ sampling effort is currently determined a priori for the domain, it does not have an in situ mechanism to adjust its sampling effort. Both of these caveats are the subject of future directions for research. This thesis work(RIDA*) significantly advances the automation of in situ heuristic selection. Finally, RIDA* uses new data structures which significantly reduce the costs associated with in situ sampling. Significantly reducing in situ sampling costs is critical for any technique using problem-specific heuristics to be competitive with state-of-the-art manual heuristic selection. en
dc.description.uri https://researchspace.auckland.ac.nz/handle/2292/16434 en
dc.publisher ResearchSpace@Auckland en
dc.relation.ispartof PhD Thesis - University of Auckland en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.rights.uri http://creativecommons.org/licenses/by-nc-sa/3.0/nz/ en
dc.title Automatic Heuristic Selection, on a Problem by Problem Basis, Using an Analytical Model and In Situ Sampling en
dc.type Thesis en
thesis.degree.grantor The University of Auckland en
thesis.degree.level Doctoral en
thesis.degree.name PhD en
dc.rights.holder Copyright: The author en
pubs.elements-id 341493 en
pubs.record-created-at-source-date 2012-04-03 en


Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Browse

Statistics