Regression with Incomplete Information and Sensing Actions: a State-based Regression Approach for Conditional Planning with Binary and Multi-valued Domains

In this book the 0-approximation semantics is used to define regression in domains where an agent does not have complete information about the world, and may have sensing actions. The author started with domains having only Boolean fluents and formally related the definition of regression with the earlier definition of progression . Planning using such regression would not only give correct plans but also would not miss plans. A search algorithm for generating conditional plans was presented as an example application of the defined regression. Several heuristics and mutex computations were explored to handle sensing actions. Experimental results with respect to several planning examples were also presented. The results obtained for binary domains were then extended to multi-valued domains. In particular, a regression function for multi-valued domains was defined and its soundness and completeness was formally proved. To simplify the formulation, the STRIPS-like action representation and fluents with finite domains were employed.