Exploration in Greedy Best-First Search for Satisficing Planning

• Author / Creator

  Xie, Fan

• 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.

• Subjects / Keywords

  • Heuristic Search
  • Planning
  • Artificial Intelligence

• Graduation date

  Spring 2016

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3MC8RN1C

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. 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.