ERA

Download the full-sized PDF of Exploration in Greedy Best-First Search for Satisficing PlanningDownload the full-sized PDF

Analytics

Share

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

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

Exploration in Greedy Best-First Search for Satisficing Planning Open Access

Descriptions

Other title
Subject/Keyword
Artificial Intelligence
Heuristic Search
Planning
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Xie, Fan
Supervisor and department
Holte, Robert (Computing Science)
Müller, Martin (Computing Science)
Examining committee member and department
Bulitko, Vadim (Computing Science)
Helmert, Malte (University of Basel)
Friggstad, Zachary (Computing Science)
Department
Department of Computing Science
Specialization

Date accepted
2016-01-08T13:26:50Z
Graduation date
2016-06
Degree
Doctor of Philosophy
Degree level
Doctoral
Abstract
This thesis proposes, analyzes and tests different exploration-based techniques in Greedy Best-First Search (GBFS) for satisficing planning. First, we show the potential of exploration-based techniques by combining GBFS and random walk exploration locally. We then conduct deep analysis on how flaws in heuristics impact GBFS’s performance. Uninformative Heuristic Regions (UHRs) and Early Mistakes (EMs) for GBFS are analyzed and illustrated on a number of International Planning Competition (IPC) benchmarks. Corresponding solutions, namely Greedy Best-First Search with Local Exploration (GBFS-LE) and Type-based Greedy Best-First Search (Type-GBFS), are proposed and shown to outperform GBFS substantially. While this thesis mainly focuses on improving coverage (number of problems solved) with exploration-based techniques, we also introduce the Diverse Anytime Search (DAS) framework, which reduces unproductive time and improves plan quality by randomized exploration. Finally, we integrate these techniques and build the new satisficing planner Jasper, which ranked 4th of 20 planners in the Sequential Satisficing track of IPC-2014 and solved the largest number of problems among non-portfolio-based planners.
Language
English
DOI
doi:10.7939/R3MC8RN1C
Rights
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
Citation for previous publication
F. Xie, H. Nakhost, and M. Müller. Planning via random walk-driven local search. In Lee McCluskey, Brian Williams, José Reinaldo Silva, and Blai Bonet, editors, Proceeedings of the Twenty-Second International Conference on Automated Planning and Scheduling (ICAPS-2012), pages 315–322, 2012.F. Xie, R. Valenzano, and M. Müller. Better time constrained search via randomization and postprocessing. In Proceedings of the Twenty-Third Inter- national Conference on Automated Planning and Scheduling, ICAPS 2013, Rome, Italy, June 10-14, 2013, pages 269–277, 2013.F. Xie, M. Müller, and R. Holte. Adding local exploration to Greedy Best- First Search in satisficing planning. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pages 2388–2394, 2014.F. Xie, M. Müller, and R. Holte. Jasper: the art of exploration in Greedy Best First Search. In M. Vallati, L. Chrpa, and T. McCluskey, editors, The Eighth International Planning Competition (IPC-2014), pages 39–42, 2014.F.Xie, M.Müller, R.Holte, and T. Imai. Type-based exploration with multiple search queues for satisficing planning. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pages 2395–2402, 2014.F. Xie, M. Müller, and R. Holte. Understanding and improving local exploration for gbfs. In Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling, ICAPS 2015, Jerusalem, Israel, June 7-11, pages 244–248, 2015.

File Details

Date Uploaded
Date Modified
2016-01-08T20:27:01.574+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 3588799
Last modified: 2016:06:16 17:11:40-06:00
Filename: saved_as_pdfa.pdf
Original checksum: e75372e8fbc928b62163abb86b4b8454
Activity of users you follow
User Activity Date