Exploration in Greedy Best-First Search for Satisficing Planning Open Access
- Other title
- Type of item
- Degree grantor
University of Alberta
- Author or creator
- 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 of Computing Science
- Date accepted
- Graduation date
Doctor of Philosophy
- Degree level
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.
- 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.
- Date Uploaded
- Date Modified
- Audit Status
- Audits have not yet been run on this file.
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 3588799
Last modified: 2016:06:16 17:11:40-06:00
Original checksum: e75372e8fbc928b62163abb86b4b8454
Activity of users you follow