%A Jiankun HE,Xishun ZHAO %T Reasoning about actions with loops via Hoare logic %0 Journal Article %D 2016 %J Front. Comput. Sci. %J Frontiers of Computer Science %@ 2095-2228 %R 10.1007/s11704-016-5158-6 %P 870-888 %V 10 %N 5 %U {https://journal.hep.com.cn/fcs/EN/10.1007/s11704-016-5158-6 %8 2016-09-07 %X

Plans with loops are more general and compact than classical sequential plans, and gaining increasing attentions in artificial intelligence (AI). While many existing approaches mainly focus on algorithmic issues, few work has been devoted to the semantic foundations on planning with loops. In this paper, we first develop a tailored action language AKL, together with two semantics for handling domains with non-deterministic actions and loops. Then we propose a sound and (relative) complete Hoare-style proof system for efficient plan generation and verification under 0- approximation semantics, which uses the so-called idea offline planning and on-line querying strategy in knowledge compilation, i.e., the agent could generate and store short proofs as many as possible in the spare time, and then perform quick query by constructing a long proof from the stored shorter proofs using compositional rule. We argue that both our semantics and proof system could serve as logical foundations for reasoning about actions with loops.