Abstract:
Planning in nondeterministic domains with temporally extended goals under partial observability is one of the most challenging problems in planning. Subsets of this problem have been already addressed in the literature. For instance, planning for extended goals has been developed under the simplifying hypothesis of full observability. And the problem of a partial observability has been tackled in the case of simple reachability goals. The general combination of extended goals and partial observability is, to the best of our knowledge, still an open problem, whose solution turns out to be by no means trivial. In this paper we do not solve the problem in its generality, but we perform a significant step in this direction by providing a solid basis for tackling it. Our first contribution is the definition of a general framework that encompasses both partial observability and temporally extended goals, and that allows for describing complex, realistic domains and significant goals over them. A second contribution is the definition of the K-CTL goal language, that extends CTL (a classical language for expressing temporal requirements) with a knowledge operator that allows to reason about the information that can be acquired at run-time. This is necessary to deal with partially observable domains, where only limited run-time "knowledge" about the domain state is available. A general mechanism for plan validation with K-CTL goals is also defined. This mechanism is based on a monitor, that plays the role of evaluating the truth of knowledge predicates.