On the Completeness of Approximation Based Reasoning and Planning in Action Theories with Incomplete Information

Tran Son, Phan Huy Tu

In this paper, we study the completeness of the 0-approximation for action theories with incomplete information. We propose a sufficient condition for which an action theory under the 0-approximation semantics is complete with respect to the possible world semantics. We then introduce the notion of decisive sets of fluents, based on which an action theory can be modified into another action theory such that the modified action theory under the 0-approximation is complete with respect to the original theory. We present a polynomial time algorithm for computing decisive sets for action theories and use it in the development of a sound and complete conformant planner. Finally, we compare our planner with other state-of-the-art conformant planners.

Subjects: 1.11 Planning; 11. Knowledge Representation

Submitted: Mar 1, 2006

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.