MS-Lite: A Lightweight, Complementary Merge-and-Shrink Method

Authors

  • Gaojian Fan University of Alberta
  • Robert Holte University of Alberta
  • Martin Mueller University of Alberta

DOI:

https://doi.org/10.1609/icaps.v28i1.13885

Keywords:

merge-and-shrink, optimal planning, classical planning, heuristic search, merging strategy, international planning competition

Abstract

Merge-and-shrink is a general framework for creating abstraction heuristics. In this paper we present two new variations of merge-and-shrink: MS-lite and DM-HQ. MS-lite is an extremely fast merge-and-shrink that maintains only the smallest abstractions that preserve local heuristic information. MS-lite has complementary strength over other merge-and-shrink methods due to its efficiency. In addition, we show that MS-lite has little dependence on merging strategies and its eager shrinking strategy can lead to better heuristics for some planning tasks. DM-HQ features a merging criterion that utilizes information about heuristic quality to make the merging decisions. Our experiments show that combining DM-HQ and MS-lite dramatically outperforms the current state-of-the-art merge-and-shrink method by solving 75 more tasks on an International Planning Competition (IPC) benchmark set of 1499 tasks.

Downloads

Published

2018-06-15

How to Cite

Fan, G., Holte, R., & Mueller, M. (2018). MS-Lite: A Lightweight, Complementary Merge-and-Shrink Method. Proceedings of the International Conference on Automated Planning and Scheduling, 28(1), 74-82. https://doi.org/10.1609/icaps.v28i1.13885