- 193 views
- 278 downloads
Understanding and Improving Merge-and-Shrink Abstraction for Cost Optimal Planning
-
- Author / Creator
- Fan, Gaojian
-
In this thesis, we study merge-and-shrink (M&S), a flexible abstraction technique for generating heuristics for cost optimal planning. We first propose three novel merging strategies for M&S, namely, Undirected Min-Cut (UMC), Maximum Intermediate Abstraction Size Minimizing (MIASM), and Dynamic MIASM with Heuristic Quality (DM-HQ) that improve the quality of M&S heuristics for problems in International Planning Competition (IPC) domains. We also introduce a lightweight M&S method MS-lite for constructing M&S heuristics in an extremely efficient way, which can complement other, relatively expensive M&S methods. We show that the combination of MS-lite and DM-HQ substantially outperforms the previous state of the art M&S method. We then focus on how to improve search with M&S heuristics when there are diverse action costs. We first study how diverse action cost affects search without heuristics. We prove a No Free Lunch theorem showing that, under mild assumptions, when no heuristic is used the positive and negative effects of diverse costs on search are perfectly balanced. We then show that cost diversity has negative effects on M&S heuristics for IPC problems. Finally, we propose a M&S method called Merge-and-Shrink with Delta Cost Partitioning (DCP-MS) that largely reduces the negative effects of cost diversity on the impacted IPC domains.
-
- Subjects / Keywords
-
- Graduation date
- Fall 2019
-
- Type of Item
- Thesis
-
- Degree
- Doctor of Philosophy
-
- License
- 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 these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before 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.