Conformant Planning Heuristics Based on Plan Reuse in Belief States

Cai Dunbo, Jigui Sun, Minghao Yin

Conformant planning involves generating plans under the condition that the initial situation and action effects are undeterministic and sensing is unavailable during plan execution. Bonet and Geffner has shown that conformant planning can be transformed into a search problem in the space of belief states. Since then, heuristic based conformant planning has become a promising approach. Following the direction, some effective heuristics, such as those introduced in MBP, Conformant-FF and POND, were proposed. An additive heuristic that obtains the heuristic value of a given belief state by summing the heuristic value of each world state is sensitive to the progress of the search procedure and often guides a search algorithm efficiently. However, it suffers from the problem of overestimating the distances-to-goal of belief states and therefore leads to overlong plans generally. One of the reasons is that the additive heuristic does not take into account relationships between different world states in a belief state. For example, an action sequence for one world state may have progressive effects on others. In this work, we use plan reuse information to make the additive heuristic more reasonable. The information is discovered with the aid of a classical planning heuristic function and in a real time learning style. The resulted heuristic is tested on a conformant planning system that is implemented as an extension of the classical planner Fast Downward to the conformant setting. Preliminary results show that our heuristic is promising in getting better plans on tasks where plan reuse possibilities exist.

Subjects: 1.11 Planning; 15. Problem Solving

Submitted: Apr 7, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.