Heuristic Search in Belief Space

From: Alexander Yates (ayates_at_cs.washington.edu)
Date: Tue Apr 22 2003 - 00:08:42 PDT

  • Next message: Tal Shaked: "Heuristic Search in Belief Space - review"

    Review of "Planning with Incomplete Information as Heuristic Search in
    Belief Space", by Blai Bonet and Hector Geffner.

    This paper gives mathematical models, algorithms, and experimental results
    for planning without the closed world knowledge of classical planning, and
    the methods are shown to be effective for conformant planning, contingent
    planning, and probabilistic planning with partial observability (POMDPs).

    One of the main ideas of this paper is that planning with incomplete
    information can be viewed as a search problem in the space of beliefs about
    what states are possible, and that there are simple models for three
    different kinds of planning problems that fit this paradigm. This idea is
    apparently an old one, but this paper makes it explicit and coherent. A
    second contribution of the paper is to provide domain-independent heuristics
    for the three kinds of search problems in the form of solutions to relaxed
    problems that have more observability.

    I don't have a good sense for how hard these kinds of problems are and how
    good the competing algorithms are, but it doesn't seem like their algorithms
    will scale very well. Even the heuristics they're using take time
    polynomial in the size of the state space to compute, and that doesn't bode
    well for scaling up, I don't think. Also, I think the same criticism Dan
    had of the HSPr paper applies here: the experiments don't really seem to
    test any hypothesis. Rather, they simply report on run times in various
    domains.

    Possible future directions include looking at different representations
    (BDDs, ADDs) to allow the algorithms to scale better and looking for better
    heuristics or heuristics that are faster to calculate.


  • Next message: Tal Shaked: "Heuristic Search in Belief Space - review"

    This archive was generated by hypermail 2.1.6 : Tue Apr 22 2003 - 00:08:42 PDT