On belief state representation and its application in planning with incomplete information, nondeterministic actions, and sensing actions

Belief state refers to the set of possible world states satisfying the agent's (usually imperfect) knowledge. The use of belief state allows the agent to reason about the world with incomplete information, by considering each possible state in the belief state individually, in the same way as if it had perfect knowledge. However, the number of states in a belief state is generally exponential. It is crucial to represent belief state in a compact form for: (i) facilitating more efficient reasoning methods and (ii) improving the scalability of applications of reasoning about belief states, especially those that need to consider and maintain a large (possibly exponential) number of belief states as planning. The question is then how to compute successor belief states after executing actions with conditional effects under a compact representation.;This dissertation proposes the use of compact formulae as belief state representations and a general methodology for defining a transition function, that can efficiently compute exact successor belief states under an arbitrary representation after executing actions without enumerating states in each belief state. This is novel and significant as defining such a transition function for even a concrete representation other than belief state is particularly challenging due to context-dependent action effects in presence of incomplete information and not explored by other works. The transition function is proved to be optimal in term of the minimum number of intermediate formulae, necessarily defined in the function, that impacts the complexity of the function. This work then develops three alternative representations along with their transition functions, by means of the general methodology, and investigates the complexity of the functions.;The proposed representation methods are then applied to conformant and contingent planning. A new AND/OR forward search with novel pruning techniques are also developed for contingent planning solutions. The experiments demonstrate a superior performance of the resulting planners compared with other state-of-the-art planners. However, the new planners that use different representations perform differently. This work identifies the features that impact the performance of a representation and the classes of problems on which the representation performs well or poorly. These results confirm the necessity to adapt the representation of the belief state depending on the specific class of problems being considered as well as the importance of the general methodology and the set of representations proposed in this thesis.