From: Stefan B. Sigurdsson (stebbi_at_cs.washington.edu)
Date: Thu Apr 10 2003 - 15:32:16 PDT
Summary - this paper presents improvements on the HSP approach to planning in STRIPS-like domains. HSP executes a forward search from the initial state through the problem state space to the goal. The search problem is reduced using a cost heuristic that approximates the number of steps necessary to reach the goal from a given state. This paper identifies the necessity of computing heuristics when visiting a new state as a key inefficiency in HSP. The authors propose a different technique called HSPr which is based on a single, forward propagating cost estimation, followed by a regression search backwards from the goal that is directed by the already-computed heuristics. The experimental results presented show that HSPr is efficient compared with HSP and Blackbox and also generalizes to a large set of planning problems.
Key ideas
- The main insight here is that a Graphplan-like forwards preparation followed by backwards search would yield performance improvements over HSP. The more efficient heuristics computation is exploited in the selection of the (separate) regression search algorithm. This same insight is also turned upside-down to arrive at an interesting interpretation of Graphplan as particular form of a heuristic search planner.
Questions
- The discussion of mutually exclusive pairs and the comparison with Graphplan is not very detailed. An evaluation of the effects of decreasing the size of the initial set of pairs to consider for mutex determination would have been good. A more thorough discussion of the effects of the different approaches to mutex determination used in Graphplan and HSPr could also have been quite interesting.
- To me the paper would have been a lot better read if the authors had included an example or some form of illustration of how the HSPr scheme works in practice. The mathematical presentation is nice, but as the paper stands I was left with the impression that an independent reproduction of the HSPr experiments would require the reader to fill in a lot of gaps in the details. I was happy with the clarity of the experimental results though - the tables worked well for me.
Directions
- The authors point towards a study into Graphplan as a heuristic search planner, this sounded interesting although perhaps not likely to result in fundamental discoveries.
- The authors also point towards the derivation of better heuristics as an area for further research. Has there been progress in this area? While reading the paper and trying to understand the implications of an additive heuristic vs. the max heuristic that approximates the cost of achieving a set of goals (atoms) with the cost of achieving the most expensive atom, I started wondering about some kind of statistical or probabilistic middle ground in-between. A probabilistic computation of goal cost heuristics could be loaded with the distribution of individual atom costs and the likely overlap between different step sequences. Is this wildly dumb? Has somebody tried something like this?
This archive was generated by hypermail 2.1.6 : Thu Apr 10 2003 - 15:32:17 PDT