Not Logged In

Additive Merge-and-Shrink Heuristics for Diverse Action Costs

Full Text: 0599.pdf PDF

In many planning applications, actions can have highly diverse costs. Recent studies focus on the effects of diverse action costs on search algorithms, but not on their effects on domain-independent heuristics. In this paper, we demonstrate there are negative impacts of action cost diversity on merge-and-shrink (M&S), a successful abstraction method for producing high-quality heuristics for planning problems. We propose a new cost partitioning method for M&S to address the negative effects of diverse action costs. We investigate non-unit cost IPC domains, especially those for which diverse action costs have severe negative effects on the quality of the M&S heuristic. Our experiments demonstrate that in these domains, an additive set of M&S heuristics using the new cost partitioning method produces much more informative and effective heuristics than creating a single M&S heuristic which directly encodes diverse costs.

Citation

G. Fan, M. Müller, R. Holte. "Additive Merge-and-Shrink Heuristics for Diverse Action Costs". International Joint Conference on Artificial Intelligence (IJCAI), (ed: Carles Sierra), pp 4287-4293, August 2017.

Keywords: Planning and Scheduling: Planning Algorithms, Planning and Scheduling: Search in Planning and Scheduling, Combinatorial & Heuristic Search: Heuristic Search, Combinatorial & Heuristic Search: Combinatorial search/optimisation
Category: In Conference
Web Links: doi
  IJCAI

BibTeX

@incollection{Fan+al:IJCAI17,
  author = {Gaojian Fan and Martin Müller and Robert Holte},
  title = {Additive Merge-and-Shrink Heuristics for Diverse Action Costs},
  Editor = {Carles Sierra},
  Pages = {4287-4293},
  booktitle = {International Joint Conference on Artificial Intelligence
    (IJCAI)},
  year = 2017,
}

Last Updated: June 30, 2020
Submitted by Sabina P

University of Alberta Logo AICML Logo