Setting goals and determining their associated plans of action have long been considered fundamental aspects of intelligent behaviour. Much of the work in the artificial intelligence research area of planning has made simplifying assumptions and thereby neglected important real­world dimensions. It is the intent of this thesis to relax two of these assumptions and discuss their implications on the planning process. We explore the modeling of plans of action in a temporal setting and consider the execution of those plans in a dynamic environment.

Temporal consistency criteria for plans are set forth and their associated algorithms are discussed in terms of their time complexity. We present a polynomial-time algorithm for determining the temporal consistency of partial-order plans. For dynamic plan execution, we present an algorithm which leads to a minimal amount of replanning. Both algorithms are planner-independent and have been implemented to enhance a classical, partial-order planner.