Efficiently Dispatching Plans Encoded as Simple Temporal Problems

The Simple Temporal Problem (STP) formalism was developed to encode flexible quantitative temporal constraints, and it has been adopted as a commonly used framework for temporal plans. This chapter addresses the question of how to automatically dispatch a plan encoded as an STP, that is, how to determine when to perform its constituent actions so as to ensure that all of its temporal constraints are satisfied. After reviewing the theory of STPs and their use in encoding plans, we present detailed descriptions of the algorithms that have been developed to date in the literature on STP dispatch. We distinguish between off-line and online dispatch, and present both basic algorithms for dispatch and techniques for improving their efficiency in time-critical situations. INTRODUCTION The past decade has seen a number of advances in the field of automated planning. Along one dimension, researchers have added significant expressive power to planning representations. One of the most notable extensions has been the explicit encoding of quantitative temporal constraints, which are a crucial aspect of many real-world planning This chapter app rs in the book, Intellig nt Techniques for Planning, edited by Ioamis Vlahavas and Dimitris Vrakas. Copyright © 2005, Idea Group Inc. Copying or distributing in print or electronic forms without written permission of Idea Group Inc. is prohibited. 701 E. Chocolate Avenue, Suite 200, Hershey PA 17033-1240, USA Tel: 717/533-8845; Fax 717/533-8661; URL-http://www.idea-group.com IDEA GROUP PUBLISHING Efficiently Dispatching Plans Encoded as Simple Temporal Problems 297 Copyright © 2005, Idea Group Inc. Copying or distributing in print or electronic forms without written permission of Idea Group Inc. is prohibited. problems. At the same time, increased attention has been given to the issues involved in plan execution, which cannot be divorced from, and indeed in real-world settings must often be interleaved with, the plan generation process. Together, these two research trends have created a challenge: how does one dispatch a plan with temporal constraints, that is, determine when to perform its constituent actions so as to ensure or at least maximize the probability that all of its temporal constraints are satisfied? The difficulty of dispatching a plan depends on the nature of the plan and the environment in which it is to be executed. The simplest case arises when (1) a plan includes a specific time for the performance of each of its actions, and (2) it is to be executed in a static setting, one in which the only changes are the direct result of the plan execution itself. In this circumstance, plan dispatch is trivial: all that is required is for each action to be performed at its specified time. But most real-world planning and execution applications are not so simple. The evolution of the world is generally not fully known in advance, and thus it is difficult to give precise specifications of the times and durations of actions. Allowing for flexible constraints can make it possible to accommodate unanticipated events, but also makes dispatch more complicated, because there is no longer a unique point in time at which each action is to be performed. The Simple Temporal Problem (STP) formalism was developed to encode representation and reasoning with flexible quantitative temporal constraints (Dechter, Meiri & Pearl, 1991). This chapter presents the theory of the STP in detail, its uses for encoding plans, and algorithms for efficiently dispatching STPs in online, dynamic, and flexible ways. Other useful formalisms explicitly represent and reason with temporal uncertainty (Morris, Muscettola & Vidal, 2001; Tsamardinos, 2002; Tsamardinos, Vidal & Pollack, 2003; Vidal & Fargier, 1997; Vidal & Fragier, 1999), but the STP remains the most efficient representation to reason with and, as-of-yet, the most commonly employed in practical temporal-planning applications. In addition, STP dispatching is a key component of dispatching plans encoded in some of the other more expressive formalisms. SIMPLE TEMPORAL PROBLEM The Simple Temporal Problem (STP) is a special case of a temporal constraint satisfaction problem. The class of temporal constraint satisfaction problems was initially developed by Dean & McDermott (1987) and subsequently generalized and formalized by Dechter, Meiri & Pearl (1991). Definition 1: Simple Temporal Problem. A Simple Temporal Problem (STP) is a constraintsatisfaction problem such that V is a set of real-valued temporal variables and E is a set of constraints of the form X j – X i ≤ b ij , where X i , X j ∈ V and b ij ∈ R. In this chapter, as in much of the literature, we will, without loss of generality, make the simplifying assumption that the bounds b ij are restricted to the integers. With an STP, the temporal constraints are a set of binary and linear inequalities. For ease of presentation, we will often combine two constraints of the form X j – X i ≤ b ij and X i – X j ≤ b ji into one, writing them as –b ji ≤ X j – X i ≤ b ij or as X j – X i ∈[–b ji , b ij ]. Notice that the lower bound is negated when converted from single inequalities to interval 22 more pages are available in the full version of this document, which may be purchased using the "Add to Cart" button on the publisher's webpage: www.igi-global.com/chapter/efficiently-dispatching-plansencoded-simple/24466