ERA

Download the full-sized PDF of Bootstrap Learning of Heuristic FunctionsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3QP6J

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Bootstrap Learning of Heuristic Functions Open Access

Descriptions

Other title
Subject/Keyword
Learning Heuristics
Bootstrapping
Heuristic Search
Planning
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Jabbari Arfaee, Shahab
Supervisor and department
Sandra Zilles (Computer Science, University of Regina)
Robert C. Holte (Computing Science)
Examining committee member and department
Jonathan Schaeffer (Computing Science)
Sean Gouglas (Department of History & Classics)
Department
Department of Computing Science
Specialization

Date accepted
2010-10-01T16:54:03Z
Graduation date
2010-11
Degree
Master of Science
Degree level
Master's
Abstract
We investigate the use of machine learning to create effective heuristics for single-agent search. Our method aims to generate a sequence of heuristics from a given weak heuristic h{0} and a set of unlabeled training instances using a bootstrapping procedure. The training instances that can be solved using h{0} provide training examples for a learning algorithm that produces a heuristic h{1} that is expected to be stronger than h{0}. If h{0} is so weak that it cannot solve any of the given instances we use random walks backward from the goal state to create a sequence of successively more difficult training instances starting with ones that are guaranteed to be solvable by h{0}. The bootstrap process is then repeated using h{i} instead of h{i-1} until a sufficiently strong heuristic is produced. We test this method on the 15- and 24-sliding tile puzzles, the 17- , 24- , and 35-pancake puzzles, Rubik's Cube, and the 15- and 20-blocks world. In every case our method produces heuristics that allow IDA* to solve randomly generated problem instances quickly with solutions very close to optimal. The total time for the bootstrap process to create strong heuristics for large problems is several days. To make the process efficient when only a single test instance needs to be solved, we look for a balance in the time spent on learning better heuristics and the time needed to solve the test instance using the current set of learned heuristics. %We use two threads in parallel, We alternate between the execution of two threads, namely the learning thread (to learn better heuristics) and the solving thread (to solve the test instance). The solving thread is split up into sub-threads. The first solving sub-thread aims at solving the instance using the initial heuristic. When a new heuristic is learned in the learning thread, an additional solving sub-thread is started which uses the new heuristic to try to solve the instance. The total time by which we evaluate this process is the sum of the times used by both threads up to the point when the instance is solved in one sub-thread. The experimental results of this method on large search spaces demonstrate that the single instance of large problems are solved substantially faster than the total time needed for the bootstrap process while the solutions obtained are still very close to optimal.
Language
English
DOI
doi:10.7939/R3QP6J
Rights
License granted by Shahab Jabbari Arfaee (jabbaria@cs.ualberta.ca) on 2010-09-30T20:57:20Z (GMT): Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of the above terms. The author reserves all other publication and other rights in association with the copyright in the thesis, and except as herein provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication

File Details

Date Uploaded
Date Modified
2014-04-24T23:57:23.071+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 2260318
Last modified: 2015:10:12 18:39:04-06:00
Filename: Jabbari Arfaee_Shahab_Fall 2010.pdf
Original checksum: 45fb8a689116e875165b7af9e0502003
Well formed: false
Valid: false
Status message: Lexical error offset=2249441
Page count: 103
Activity of users you follow
User Activity Date