Tractable reasoning with incomplete first-order knowledge in dynamic systems with context-dependent actions

Abstract

A basic reasoning problem in dynamic systems is the projection problem: determine if a formula holds after a sequence of actions has been per-formed. In this paper, we propose a tractable1 so-lution to the projection problem in the presence of incomplete first-order knowledge and context-dependent actions. Our solution is based on a type of progression, that is, we progress the ini-tial knowledge base (KB) wrt the action sequence and answer the query against the resulting KB. The form of reasoning we propose is always log-ically sound and is also logically complete when the query is in a certain normal form and the agent has complete knowledge about the context of any context-dependent actions. 1