NotesFAQContact Us
Search Tips
ERIC Number: ED555784
Record Type: Non-Journal
Publication Date: 2012
Pages: 307
Abstractor: As Provided
Reference Count: N/A
ISBN: 978-1-3035-1152-3
On Belief State Representation and Its Application in Planning with Incomplete Information, Nondeterministic Actions, and Sensing Actions
To, Son Thanh
ProQuest LLC, Ph.D. Dissertation, New Mexico State University
"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. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page:]
ProQuest LLC. 789 East Eisenhower Parkway, P.O. Box 1346, Ann Arbor, MI 48106. Tel: 800-521-0600; Web site:
Publication Type: Dissertations/Theses - Doctoral Dissertations
Education Level: N/A
Audience: N/A
Language: English
Sponsor: N/A
Authoring Institution: N/A