-----------NOTES 3-25-2003----------- Today’s class introduced Metric Temporal Planning. We are leaving the STRIPS environment and begin tackling some of the most challenging domains in AI planning, not to mention that simple classical planning is already very hard. -----------TEMPORAL PLANNING----------- Let’s first define Temporal Planning (TP). Temporal planning is only slightly different from the classical planning environment in that it allows actions to have durations. Funny enough, temporal planning relates more to the way we live than classical planning does. In fact, classical planning is very unusual in the real world; imagine completing your CSE574 midterm in no more than an instance, we could only dream of that ;) Action represented in the classical domain (instantaneous) . a: action a a Action represented in the temporal planning domain (durative) |______________| Sa: start time of action a Sa Ea Ea: end time of action a <------Da------> Da: duration of action a In temporal planning durations can be static, dynamic and even uncertain. Duration often depends on the context. For example, the time to fill your gas tank depends on how empty the tank is to begin with. Durative actions also add complexity to decisions about its preconditions and effects. For example, when are the preconditions needed? How long are they needed for? And when are its effects released? For example, some preconditions must hold at a certain point in time, whereas other preconditions must hold over a period of time. Take a look at the "PhD graduation" example, a prerequisite of graduation is that you will pass your qualification exams, but you will have to figure out when you want to complete it. If not specified otherwise, we will assume that all preconditions are needed at the start of an action and must hold during its entire duration. In addition, all action effects will become available only at the end of the action. -----------CONCURRENCY------------ Consider the following two plans: Plan 1: a1 – a2 – a3 (needs 3 steps) / a1 \ Plan 2: \ a2 / - a3 (needs 2 steps) Plan 2 allows parallelism, however in temporal planning we refer to this as concurrency. Concurrency is a very important issue in temporal planning. Consider a plan P that contains ten actions a1,..., a10, each with its own duration D1,..., D10, then Q1. What would be the minimum makespan (total execution time)? and Q2. What would be the maximum makespan? A1. The makespan can never be shorter than the length of the action with the largest duration. A2. The makespan can be larger than the sum of the length of all actions if the plan has idle time. Idle time occurs when actions do not start right after each other; think of a bank teller gossiping with his colleague in between servicing customers. In fact, the makespan can be infinitely large; there can be infinitely long idle time. In summary: makespan(P) >= max(D1,..., D10) If makespan(P) = sum(D1,..., D10), then P is a strictly serial plan If makespan(P) > sum(D1,..., D10), then P must contain idle-time Planned idle (or slack) time may not always be a bad thing as it can sometimes improve the robustness of the plan. For example, think of a plan involving going to Los Angeles (LA) by airplane. You can go to the airport just 5 minutes before departure, or 2 hours before departure, or maybe 3 days before departure. -----------QUALITY METRICS------------ Quality metrics introduced in this class are makespan, cost, and robustness. Note that often times these quality measures are conflicting and tradeoffs have to be made. One might prefer going to LA using a cheap but longer option (i.e. driving in a car), another one might prefer going to LA using a fast but more expensive option (i.e. flying by airplane). Plan optimization with multiple quality metrics is very much user dependent, the user’s preference will favor some plans over others. -----------RESOURCE PLANNING------------ Resource planning (RP) involves resources like fuel in a car, a particular machine that can perform one operation at a time, time available for your CSE574 midterm, etc). Resources bring constraints to the actions that make use of it. Therefore, a solution is defined as a plan that achieves all the goals while satisfying all the resource constraints. Modeling issues: How to model resource availability (especially over the duration of an action)? Planning issues: How to efficiently reason with continuous quantities during planning? Resources can behave both as continuous quantities (i.e. fuel level in your tank) and discrete quantities (i.e. number of available machines). -----------METRIC TEMPORAL PLANNING------------ MTP = TP + RP or in other words, metric temporal planning (MTP) is temporal planning with recourses. Some existing metric temporal planners: * HSTS: domain-customized partial-order-based planner (used in NASA’s deep space one mission) * IxTET: domain independent partial-order-based planner (does not use heuristics) * Zeno: domain independent partial-order-based planner (does not use heuristics) * TLPlan: domain-customized progression based planner * SAPA: domain independent progression based planner (does use heuristics) Some existing temporal planners * TGP: Graphplan based * TPG: Graphplan based * LPGP: Graphplan and LP based Some existing resource planners * LPSAT: SAT and LP based * GRT-R * Kautz-Walser: LP based Subset of temporal and resource constraints * TP4 * Resource-IPP LPGP and LPSAT are "loosely-coupled" systems. LPGP connects SAT to LP solvers, whereas LPGP connects Graphplan to LP solvers. The advantage of loosely-coupled systems is that they try to use the best of both worlds. It should be clear that pretty much every approach that has been used in classical planning has been extended and used in metric temporal planning. There are some interesting tradeoffs in the existing approaches. For example, partial order planners are the easiest to extend to support the concurrency needed for durative actions, in fact, partially ordered plans are already concurrent. It is much harder to extend partial order planners to support the handling with resources. Progression based planners are easiest to extend to support resource consuming actions, but harder to extend to support time handling concurrency.