Formal Approach to Planning with Concurrent Actions and External Events.

摘要

Planning was originally formulated in the state-based framework where actions are modeled as functions from instantaneous state to state. This framework provides a simple basis for describing the different ways the agent can affect the world, but is inadequate for describing or reasoning about planning problems that involve either concurrent actions or external events, i.e., events initiated by forces and agents other than the planning agent, that may occur while the planning agent is acting. In response to these deficiencies, Allen (1984) and McDermott (1982) put forth temporal logics that can describe simultaneous events. These formalisms, however, cannot capture the ways in which the planning agent can affect the world by executing different actions. This dissertation presents a deductive logic to describe and reason about planning problems that may involve concurrent actions and external events. A semantic theory and axiomatization are provided. We exploit the complementary strengths of the state-based model and those of Allen and McDermott by extending Allen's model with a structure similar to the result function found in the state-based model. This structure captures the result produced by executing different actions at specified times with respect to a context that includes external events that may be simultaneously occurring. This provides a framework for modeling concurrent interactions between the agent's actions and external events. It also provides a simple basis for composing actions, both concurrent and sequential, to form more complex ones (i.e., plans). (kr)