Regression in the presence of incomplete information and sensing actions, and its application to conditional planning
Chitta R. Baral, Tuan Le · 2004
In this dissertation, a state-based regression function for planning domains where an agent does not have complete information and may have sensing actions is presented. Both binary and multi-valued domains are considered, and the 0-approximation [SB01] is employed to define regression with respect to that semantics. In binary domains, the use of 0-approximation means using 3-valued (True, False, and Unknown) states. In multi-valued domains, each fluent in a state is assigned an unknown value or a value in a finite set of the fluent's prescribed values. Although planning using this approach is incomplete with regard to the full semantics, it is adopted to have a lower complexity. The soundness and completeness of the regression formulation in regard to the definition of progression is presented. More specifically, the dissertation shows that a plan obtained through regression for a planning problem is indeed a progression solution of that planning problem, and that for each plan found through progression, using regression one obtains that plan or an equivalent one. A contingent planner that utilizes the regression function is then developed and the soundness and completeness of the planning algorithm is proved. Heuristic measures are also employed to improve the planning performance. Experimental results with respect to several well-known planning problems in the literature and self-created domains are presented.