Material Detail

Effective Heuristics and Belief Tracking for Planning with Incomplete Information

Effective Heuristics and Belief Tracking for Planning with Incomplete Information

This video was recorded at 21st International Conference on Automated Planning and Scheduling. Conformant planning can be formulated as a path-finding problem in belief space where the two main challenges are the heuristics to guide the search, and the representation and update of beliefs. In the translation-based approach recently introduced by Palacios and Geffner, the two aspects are handled together by translating conformant problems into classical ones that are solved with classical planners. While competitive with state-of-the-art methods, the translation-based approach runs however into three difficulties. First, complete translations are expensive for problems with high width; second, incomplete translations can generate infinite heuristic values for problems that are solvable; and third, aspects that are specific to the conformant setting, such as the cardinality of beliefs, are not accounted for. In this work, we build on the translation-based approach but not for solving conformant problems with a classical planner but for deriving heuristics and computing beliefs in the context of a standard belief-space planner. For this, a novel translation KSi is introduced that is always complete, but which is sound for problems with width bounded by i. A new conformant planner, called T1, builds then on this translation for i=1, extending the heuristic that results with a second heuristic obtained from invariant "one of expressions". A number of experiments is performed to compare T1 with state-of-the-art conformant planners.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.