Planning with incomplete information - review

From: Parag (parag_at_cs.washington.edu)
Date: Tue Apr 22 2003 - 10:58:01 PDT

  • Next message: Sumit Sanghai: "Planning with incomplete information : Review"

    Planning with Incomplete Information as Heuristic Search in Belief Space
    Blai Bonet and Hector Geffner

    The paper formulates the problem of planning with with incomplete
    information as a heuristic search in belief space and gives a
    couple of interesting algorithms for performing the search.

    The authors do a great job of first specifying a model
    for formulating the classical planning as a heuristic
    search in state space and then extending the idea to
    more complex domains like conformant planning and
    contingent planning, by introducing the notion of
    belief space. Under the models defined, the conformant
    planning as well contingent planning can be viewed as
    deterministic planning problems (in the belief space)
    and hence, many of the standard search techniques can
    easily be extended to handle these domains. They even
    extend the idea to the case of probabilistic contingent
    planning. And the whole appraoch given seems to be
    very systematic and mathematical.

    I had some problems with the experimental section. First,
    I had to go through it several times, before I could make
    out what are they trying to convey. As already pointed
    out, probably results could have better been represented
    in the form of graphs. I also felt that there was too
    much use of acronyms for defining the planning domains
    i.e. BT, BMTC, BTUC, BTC etc. and it was difficult to make
    out what corresponds to what.

    Another question about the probabilistic planning that I have
    is - the authors do not seem to report the performance of
    any other planners when they talk about probabilistic
    domains. Is it that their's is the first planner which
    handles these domains?

    For future work - the authors mention using h=0 as their
    heuristic function along with hdp, and in some of
    the problem domains (like sorting networks), they report
    that hdp offers no extra advantage. If one could identify
    such domains, where hdp offers no advantage over h=0,
    then one could save a lot of preprocessing time(reported
    as one of the bottolnecks) by not calculating hdp at all.

    Another direction could be, in case of probablistic planning,
    to analyze the tradeoff between how much close the final solution
    is to optimal and the level of discretization - which would
    determine how much to discrtize (thereby reducing the size
    of search space a lot) versus how close we want to be
    to the optimal.


  • Next message: Sumit Sanghai: "Planning with incomplete information : Review"

    This archive was generated by hypermail 2.1.6 : Tue Apr 22 2003 - 10:58:02 PDT