04/01/03 TEMPORAL PLANNING PROBLEMS - cont. We talked about 3 planners that can solve temporal problems: 1. SAPA, which performs a progression search 2. TP4 with regression search 3. ZENO with state space search SAPA ====== One of the dillemas in scheduling actions (also in other temporal planners) is whether we should schedule an action to begin at the same time as other actions, or should we advance the clock first and then schedule an action. The minimum that we need to describe a state is: 1) literals - what is true at a current time 2) which actions are we commited to now State S = (P,M,PI,Q,t) P - set of literals true at a current time (a set of , where pi is a predicate and ti is the time of their last achievement.) M - functions representing resource values PI - set of protected persist conditions i.e. "When I go for vacation, lights at my house will turn on at 6pm and stay on til 10pm". It is similar to causal links, but with actual values, ie. <6,10> Q - event queue t - timestamp of S Undefined prefixes: -------------------- In temporal planning, actions can give effects not only after its execution, but at different times throught its execution. Additionally, some of the preconditions may be needed throughout the entire duration of its action's execution and some of the effects may persist throughout action's execution. This introduces additional difficulty level in scheduling actions. Example: A1 needs P throughout its execution and A2 deletes P. We end up with undefined prefix. |----------- | A1 | |----------- | -------- | | A2 | | -------- | When scheduling actions, we need to keep track of delayed effects, that is effects that we know will happen in the future, after a few clock advancements. For example we know that GWC doors will be locked at 8pm on Friday. Even though the action will take place later, we need to take it into consideration and make sure that we have a way of getting into GWC, if we plan any activities in that building on Friday night. This is an example of an external event. Such event would be queued in Q (see State description). An example of representing "burn_match" and "cross_cellar" in PDDL2.1: (:durative-action burn_match :parameters () :duration (= ?duration 15) :condition: (and (at start have_match) (at start have_strikepad)) :effect (and (at start have_light) (at end (not have_light)) ) ) (:durative-action cross_cellar :parameters () :duration (= ?duration 10) :condition (and (at start have_light) (over all have_light) (at start at_steps)) :effect (and (at start (not at_steps)) (at start crossing)(at end at_fuse_box) ) Example of another undefined prefix problem: What if a walk to cellar was longer than a duration of single "burn_match" action, and we wanted to burn the second match before the first one expires? | |------------- | burn_match | |------------- | | -------------- | | burn_match | | -------------- "have_light" persists throughout "burn_match" action execution. At the end of the action, en effect "not have_light" occurs. If we scheduled the two actions this way, the prefix "have_light" would be undefined. One solution is to change discrete representation of "have_light" to some function of energy or light intensity level. When we want to advance the clock, we apply a "do_nothing" action and move the clock time by this action duration. Before scheduling any new actions, we need to update State description. If goals are satisfied by a State, we found a solution. TP4: ====== In SAPA we started scheduling actions at time t0. In regression search we start scheduling at "infinite time" and regress. A similar question comes up: should be start working on all the goals simultaneously, or work on a few goals, shift the clock, work on some more goals, shift the clock, etc. We need to keep track of actions preconditions, effects, resources and avoid undefined prefixes. A nice planner feature would be to schedule cellar walk in the middle of burning a match. This is impossible with simply using SAPA or TP4. SAPA will schedule the actions: |---------------------- | burn_match | |---------------------- | |--------------- | cross_cellar | |--------------- TP4 will schedule the action in the following way: | ---------------------| | burn_match | ---------------------| | --------------| | cross_cellar | --------------| We would like to have a more robust plan, which would schedule the two action as follows: |---------------------- | burn_match | |---------------------- | | --------------- | | cross_cellar | | --------------- How can we achieve it? Normally we advance or shift the clock to the nearest event, i.e when an action produces an effect. Another approach would be to advance clock by small intevals, but what if the time measure is divided into really small intervals, or even worse - is continuous? We would achieve optimality, but we would also spend all or majority of the time just on advancing the clock. ZENO ======= Example of scheduling actions to get to the fuse box in state-space search planner ZENO: First, we look at goals: at_fuse_box "cross_cellar" supports this goal, so we schedule it: tI tG t1 t2 ---------------- | cross_cellar |--- ---------------- |causal link --------------------at_fuse_box open conditions: 1) have_light at t1 2) have_light at temporal constraints: t2, } Thus t4 must be scheduled before t3 or after t1: