Most agents can acquire information about their environments as they operate. A good plan for such an agent is one that not only achieves the goal, but is also executable, i.e., ensures that the agent has enough information at every step to know what to do next. In this paper, we present a formal account of what it means for an agent to know how to execute a plan and to be able to achieve a goal. Such a theory is (...) a prerequisite for producing specifications of planners for agents that can acquire information at run time. It is also essential to account for cooperation among agents. Our account is more general than previous proposals, correctly handles programs containing loops, and incorporates a solution to the frame problem. It can also be used to prove programs containing sensing actions correct. (shrink)

A dynamic domain consists of a set of legal states and a transition function that maps states to states. AI formalisms for specifying dynamic domains have so far focused on describing the effects of actions, that is, the transition functions. In this paper we propose a notion of characteristic set of position systems for the purpose of describing legal states. A position system for a type of objects is a set of properties that are mutually exclusive, and that in each (...) state, every object of the type must satisfy exactly one of these properties called its position under the position system. A set of position systems, one for each type of objects in the domain, is characteristic if there is a one-to-one mapping between legal states and sets of objects’ positions under these position systems. These position systems are useful for reasoning about these dynamic systems including planning. In particular, we show that once we have characteristic sets of position systems for a dynamic domain, planning can be done by writing rules about when to move objects from one position to another. (shrink)