Reasoning About Partially Observed Actions

Abstract

Partially observed actions are observations of action execu-tions in which we are uncertain about the identity of ob-jects, agents, or locations involved in the actions (e.g., we know that action move(?o,?x,?y) occurred, but do not know?o,?y). Observed-Action Reasoning is the problem of rea-soning about the world state after a sequence of partial obser-vations of actions and states. In this paper we formalize Observed-Action Reasoning, prove intractability results for current techniques, and find tractable algorithms for STRIPS and other actions. Our new algorithms update a representation of all possible world states (the belief state) in logic using new logical constants for un-known objects. A straightforward application of this idea is incorrect, and we identify and add two key amendments. We also present successful experimental results for our algorithm in Blocks-world domains of varying sizes and in Kriegspiel (partially observable chess). These results are promising for relating sensors with symbols, partial-knowledge games, multi-agent decision making, and AI planning. 1