When Optimal is Just Not Good Enough: Fast Near-Optimal Action Cost-Partitioning

Erez Karpas, Michael Katz and Shaul Markovitch. When Optimal is Just Not Good Enough: Fast Near-Optimal Action Cost-Partitioning. In Proceedings of the 21st International Conference on Automated Planning and Scheduling, 122-129 Freiburg, Germany, 2011.

Abstract

Several recent heuristics for domain independent planning adopt some action cost partitioning scheme to derive admissible heuristic estimates. Given a state, two methods for obtaining an action cost partitioning have been proposed: optimal cost partitioning, which results in the best possible heuristic estimate for that state, but requires a substantial computational effort, and ad-hoc (uniform) cost partitioning, which is much faster, but is usually less informative. These two methods represent almost opposite points in the tradeoff between heuristic accuracy and heuristic computation time. One compromise that has been proposed between these two is using an optimal cost partitioning for the initial state to evaluate all states. In this paper, we propose a novel method for deriving a fast, informative cost-partitioning scheme, that is based on computing optimal action cost partitionings for a small set of states, and using these to derive heuristic estimates for all states. Our method provides greater control over the accuracy/computation-time tradeoff, which, as our empirical evaluation shows, can result in better performance.

Keywords: Planning, Anytime Algorithms

Secondary Keywords:

Online version:

Bibtex entry:

 @inproceedings{Karpas:2011:WOJ,
  Author = {Erez Karpas and Michael Katz and Shaul Markovitch},
  Title = {When Optimal is Just Not Good Enough: Fast Near-Optimal Action Cost-Partitioning},
  Year = {2011},
  Booktitle = {Proceedings of the 21st International Conference on Automated Planning and Scheduling},
  Pages = {122--129},
  Address = {Freiburg, Germany},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Karpas-Katz-Markovitch-ICAPS11.pdf},
  Keywords = {Planning, Anytime Algorithms},
  Abstract = {
    Several recent heuristics for domain independent planning adopt
    some action cost partitioning scheme to derive admissible
    heuristic estimates. Given a state, two methods for obtaining an
    action cost partitioning have been proposed: optimal cost
    partitioning, which results in the best possible heuristic
    estimate for that state, but requires a substantial computational
    effort, and ad-hoc (uniform) cost partitioning, which is much
    faster, but is usually less informative. These two methods
    represent almost opposite points in the tradeoff between heuristic
    accuracy and heuristic computation time. One compromise that has
    been proposed between these two is using an optimal cost
    partitioning for the initial state to evaluate all states. In this
    paper, we propose a novel method for deriving a fast, informative
    cost-partitioning scheme, that is based on computing optimal
    action cost partitionings for a small set of states, and using
    these to derive heuristic estimates for all states. Our method
    provides greater control over the accuracy/computation-time
    tradeoff, which, as our empirical evaluation shows, can result in
    better performance.
  }

  }