From: Stefan B. Sigurdsson (stebbi_at_cs.washington.edu)
Date: Tue Apr 22 2003 - 12:38:14 PDT
Bonet and Geffner
Planning with incomplete information as heuristic search in belief space
AAAI 2000
Summary: Presents
- A definition of planning in belief space
- A categorization of planning problems with incomplete world knowledge
- An analysis matching algorithms to categories
- Empyrical results of applying algorithms to test problems, using a tool developed by the authors
The contribution is in completeness rather than new ideas.
Key ideas:
- Belief space is the set of state space subsets. A belief state is a collection of world states with a probability attached to each element.
- The planning problem categories are as follows:
- Conformant planning starts with imperfect (probabilistic) knowledge of initial states, non-deterministic plan execution but deterministic in belief space
- Contingent planning starts with no knowledge of initial state, (limited) availability of incomplete/uncertain state observations before and during execution, non-deterministic execution in belief space
- Contingent planning becomes probabilistic if observations are extended to be probabilistic, and actions have probabilistic effects. Belief states become probability distributions over world state space subsets.
Questions:
- The belief space cardinality is exponentially larger than that of the state space. How large are the largest problems that have been tackled using the approaches described in the paper? Taking the straightforward extension of Graphplan (Blum/Furst) to handle conformant planning problems for example, does it really make sense to solve for every possible initial world state? It seems both very expensive and also likely to not lead to a solution, in case some possible (but unlikely) initial world state is a dead end. Why not cull early and shoot for statistical certainty of plan validity, instead of perfect certainty? Did I miss something?
- Same comment as above, except now make things worse by allowing state elements with values from continuous domains.
- Similar, but different; the authors comment that while extending the belief space with probability distributions takes it from exponentially larger than the world state space to infinite cardinality, this is really not that much of a problem if the distributions are sufficiently discrete. I wanted to read more about this. Is it really true? In terms of practical problems?
- I didn't get half as much out of the algorithms discussion and experiments results as I did from the mathematical modeling. The paper is quite dense, the tables don't help but they're not worse than elsewhere.
Directions:
- I like the paper, need to spend more time on it to understand fully what it says let alone be able to read between the lines, but the obvious question that arises after reading it is how relevant all of this is to real-world planning with incomplete information.
This archive was generated by hypermail 2.1.6 : Tue Apr 22 2003 - 12:38:16 PDT