CSE 591: Planning in Stochastic,Dynamic,Metric & Incomplete Worlds Class Notes March 22nd, 2000. [notes taker:Ullas] Agenda. Read Remote Agent Experiment(RAX) paper. Compare it with the IXTET planner discussed in the previous class. Discussion: The RAX paper created lots of doubts with Dr Rao admitting that it is a different kind of a paper and so a discussion in class was the way to understand the paper. PIG & MCS --------- Q: Why & how is PIG resolving Resource Contention. A: The graph based idea of how the Resource Contention is being dealt with was not very clear at first. So the idea was discussed at length. The actions have relative ordering in RAX. The resources are specified over intervals ie as being used over an interval of time. So the interval algebra comes into picture. The Resource Capacity (Max Capacity that for eg a Machine can handle) can be looked upon as being modelled in RAX as a causal link. Hence like a causal link in a partial plan, this capacity cannot be exceeded or violated even at any single instance. Looking at Resource capacity as a Causal link two points are clear: At any point during resource planning a: either the resource capacity is overshot which means the Plan is already dead b: or the plan will give rise to a resource conflict if the next resource usage is included. If the case is b, then it can still be resolved. Conflict Vs Inconsistency ------------------------- Conflict: If a conflict is found, the plan is not dead yet. A resolution can yet be found. Inconsistency: The plan is already dead. Hence Conflict resolution is looking ahead to determine a conflict and trying to solve the problem. ---------- 5 ----------- | t1' t2' | | | 0 infinity Resource capacity = 6 | | | | ------------3------------ t1 t2 The above conflict can be resolved by having the conditions t1' > t2 or t2' < t1. Just a note: IXTET does not model the resource consumption as condition. So it resolves using only the promotion and demotion. There is no confrontation used. The method towards resolving a conflict: Do the least that can be done to resolve the conflict. PIG --- It U1 and U2 are two tasks that overlap as regards their resource usage then a edge is drawn between them. PIGS then are used to find the cliques. Clique is a connected subgraph where all the nodes are connected to form a closed path. A 3-clique graph means : A resource conflict may arise if 2 tasks or 3 tasks are exceeding the limit. The smaller the resource conflict the fewer the choices ie smaller disjunction to handle. eg. In EBL a smaller no-good allows backtracking at the higher levels which saves the backtraching from all the hundreds of lower levels thereby speeding up solution extraction. "Every conflict is a clique in PIG but not every clique need be a conflict." Thus PIPs and MCPs are a way of detecting resource conflicts. Discussion on RAX: The Plan Database is just the PLAN. The terminology is what differs. Tokens are the way actions with temporal intervals are modelled. Domain Constraints is a way of describing groups of actions instead of sinlge actions. while defining a action, the description of the actions should tell which variables are affected. Added later: It is best to think of tokens as "values" of state variables over specific intervals. Questions: 1. What is relation between Threat & RAX. 2. Is cluster-based domain constraint better than IXTET actions + HTN Schemas. [Add by nie, the notes in Dr Rao's mail That is something that should be described in an old tech report of mine N. Muscettola, "Planning the behavior of Dynamical Systems", Tech. Report CMU-RI-TR-90-10, Carnegie Mellon Universtiy, The Robotics Institute, 1990. The basic idea is to represent each block with two state variable, one for the top and one for the bottom. Block ?x top: {clear, under (?y), move_block_top} clear = the top is clear under (?y) = block ?x is under ?y move_block_top = the whole block (hence its top) is being moved bottom: {on (?y), move_block (?y ?z)} on (?y) = block ?x is on top of ?y move_block (?y ?z) = move block from ?y to ?z Table is could be considered as a degenerate block with no bottom and with the top havein only {clear} as its set of values. You then need to specify a compatibility for each value. For example, 1. ?x.top = clear <- { :compatibility_specification and { or { met_by ?x.top = under (*); met_by ?x.top = move_block_top;} or { meets ?x.top = under (*); meets ?x.top = move_block_top;} contained_by ?x.bottom = on (*) }} Meaning: This says that a block is clear either immediately after it has completed a move or another block from it and while a block can be clear only if its is on top of something. 2. ?x.top = under (?y) <- { :compatibility_specification and { met_by ?x.top = clear; meets ?x.top = clear; equals ?y.bottom = on (?x); contained_by ?x.bottom = on (*) }} Meaning: Block ?x must be clear before and after something is put on it. Simulataneously, it should be on some block. 3. ?x.top = move_block_top <- { :compatibility_specification and { met_by ?x.top = clear; meets ?x.top = clear; equals ?x.bottom = move_block (* *)}} Meaning: In order to move a block ?x, it must be clear before and after; Bottom of the block moves with the top! 4. ?x.bottom = on (?y) <- { :compatibility_specification and { met_by ?x.bottom = move_block(* ?y); meets ?x.bottom = move_block(?y *); equals ?y.top = under (?x) }} Meaning: A block would have moved to be on top of a block. 5. ?x.bottom = move_block (?y ?z) <- { :compatibility_specification and { met_by ?x.bottom = on(?y); meets ?x.bottom = on(?z); equals ?y.top = move_block_top }} Meaning: A block will be on some block before moving to some other block. ]