--------------------------------------------------------------------------- Note on Mar 20 Class. Note taker: Zaiqing Nie Topics: all about IxTeT Papers involved: P1. P.Laborie. "IxTeT: an Integrated Approach for Plan Generation and Scheduling" P2. P.Laborie. "Planning with Sharable Resource Constraints" P3. M.Ghallab. "Representation and Control in IxTeT, a Temporal Planner" --------------------------------------------------------------------------- Agenda Today All about IxTeT Wednesday RAX Planner Next Monday Schwalb's TCSP paper ___________________________________________________________________________ Dr Rao start the class by talking about the agenda in the classes in the next two weeks. He gave some introductions to the conceptions such as point algebra, interval algebra and point-interval algebra in TCSP paper. IxTeT based on point algebra and RAX based on interval based algebra, but some times we should conbine both of these two algebra to express some tempor constraints. For example, if there are three intervals, such that interval1 meets interval2, interval2 meets interval3, it must be the case that interval1 and interval3 are not equal(not the same), while as if all of these are point intervals, then they will be the same. Then Dr. Rao start to answer questions on IxTeT. 1. The planner only deal with the higher level actions of the HTN(Hierarchical Transition Network), the question is how to insert concrete actions? Dr.Rao:Thats a good point. Basically, the history of this is that there is a time of expansion in planning, every guy has to expand the score has to have everything the other guys did and add something new. So when these people start their project which is probably in early 90's or late 80's, at that time there are lots of HTN planners, they assume that planners must have Hierarchical Transition Networks, and so they said that they could deal with that too. Normally HTN are big pain, in the sense that if you think a plan is fine at the higher level, it may not actually be fine at the lower level. 1.1 Details of HTN planning First of all, apart from the notion of concrete actions in the domain, you also have the notion of abstract actions in the domain. So if you have block world, you might have "move", "puton" and "stack" actions, on the top of that, you might have abstract actions like "stackingblock" action. And the "stackingblock" can be used like this way: on the abstract level, you might just say "put A on B", and give the preconditions and the effects of that abstract action; at the lower(concrete) level you have to know the details, to put A on B you have to first "clear A", then "clear B", then "pick A", then "put it on B", and finally give out a state whether A is actually on the top of B. By using the idea of abstract actions, you can insert a whole plan fragment that will achieve a specific goal into the plan. 1.2 Two main advantages in HTN planning a. When you introduced the whole plan fragment corresponding to the abstract action, you made more progress than you introduce a sigle action at a time. b. You can reduce the number of failures in by failing earlier if there is some problems at the abstract level. For example, suppose it turns out that your are trying to "put A on B" and "put C on D", you are trying to achieve the two goals. now we introduces these abstract actions to the plan, and they themselves have some conflicts there is no way they can be at the plan at the same time. at that point you might say, "OK, the abstract level of the plan is dead, I will kill it and try another new abstract plan". Then you avoided lots of failures in the concrete level. 1.3 Disadvantages in HTN planning However normally there are lots of theoretical problems. For example, it may cause the case that the plan is actually dead at the abstract level, and yet it is possible to find a concretization which works. So the idea is that there is a plan which at the abstract level has some conflicts that can not be resolved at all, and yet if you actually take the abstract task and reduce it in components, it would be possible to resolve the conflicts. A example(example1): P ~R,~M Q |-------->---|A|------>---| Initial | | Goal state O--->--| |--->----O | ~P,~Q | |-------->---|B|------>---| R M Here P is the precondition of A, and ~R,~M,Q are effects of A and R is the precondition of B, and ~P,~Q,M are effects of B In this case there is no linearization that is conflict free, then we can say the plan is dead. However, suppose A and B are all abstract actions and A actually becomes A1 and A2,B becomes B1 and B2. Like the following pictures. P Q |---->--|A1|->-|A2|-->----| Initial | | Goal state O--->--| |--->----O | | |---->--|B1|->-|B2|-->----| R M The negation ~R,~M,~P and ~Q also might have distribution on the four actions. So at this level there is a linearization which will work and will give a plan at this level. In this paper, it did not actually put a action into the plan and reduce it into its components. Then they will not have all the problems in the HTN planning, but at the time they will not have any of the advantages of the HTN planner. what they are providing might be something more likely the macro-mechinism. 1.4 Another view of HTN Basically, one way of thinking about HTN planning is that you have normal actions, but the expert want to tell you what are good plans and what are bad plans, and in some sense the expert wants to give you a grammar of good plans. Not every plan which reach all of the goal states is actually a good plan. There are two ways to use this grammar. One way is to make a plan first and then see whether it is grammatically correct, if so, keep it, otherwise find another plan. Another way is try to fall the grammar into the generation and generate only grammatically correct sentence. This are the two extremes, there is a middle way, which is first to make a partial plan by using a partial planner. We can parse these partial sentences into the grammar to see whether it is dead already. There is another way of doing HTN planning, called bottom-up HTN planning, where you are allowing normal planners to generate the plans, but you are using HTN just as a grammar. What Dr.Rao told before is the top-domn HTN planner, where you have to look at both the normal actions and abstract actions, when it would have been done after it took care of all the open conditions, it has to also reduce the abstract actions. So, even though there is a plan which is consistent at the top level, it maybe failed at the concrete level. One of the interesting realization about the HTN planning was that your really think HTN planning as a grammar. Dr.Rao also talked about Monotonicity Property(also called upper ward solution property). It means that if there is a solution at the concrete level there must be at least one solution at it's abstract level. In the above example1, Monotonicity property is lost. Upper ward solution property is important if you want it to have completements. Then there is a downward solution property that means if there is a solutino at the higher level then there is a solution at the bottom level. Downward solution property is important if you want to have efficiency. 2. Initial plan In normal planning you assume that you need a dummy task called initial step, and a dummy task called final step. That is important because plans actually have extend(temporal extend), but actions do not have temporal extend, plan has temporal extend they can have multiple acitons in them, but actions themselves are point based. When the moment you actually have actions with duration then the initial plan is just a large dummy action, is basically a large interval. In the beginning of the interval certain things are true, and at the end of the interval certain things must be true. In the paper they say the initial plan is a special task, that's a single task. That may be part of your confusion, you think that a plan should have multiple acitons, at least an initial action and goal action, that is not required. Because once the action have an interval, you might be able to say that this is basically a plan task, it's extend is not know up front, it would be just as big as you want it to. and it is like the extend for the plan interval. This is actually the interval algebra ideas, every other interval that makes up of the plan, must be contented by this plan interval. That essentially saying nothing can come before the initial state, nothing can come after the goal state. So it is a funny thing, that once you have an extend, you can just have a single task, essentially a dummy task, but from the outside this could be seen as an action. 3. How to select a flaw in IxTeT, whether it is independent of it's type They don't have a uniform method, they first decide which flaw they are going to resolve, a plan can have multiple types of flaw, they can have the open condition flaw, resource conflict flaw, causal link flaw. Up front, they make a seperate decision which flaw to work on, if they decide to work on the resource flaw they know how to do it. If they decide to work on the causal link flaw, they not only know how to do it, they also have some ideas of which causal link flaw should be selected. Similiarly, if they decide to work on the open condition flaw, they have a way of comparing the different open conditions, and then pick up one open condition to work on. Then Dr.Rao use the Fig3 in P65 of paper P3 to explain how to select actions to suport open condition flaw. Then Dr.Rao reviewed the way of HSP heuristics, top-down and bottom-up way of HSP hearistics to compute the cost of different preconditions. And Dr.Rao also talked about another way to comput the costs of different proconditions: seperate the dependent preconditions to different precondition sets, and add up the heuristics of independent preconditions to compare different actions. 4. topics about choosing conflicts to solve Suppose you have a plan which have two different unsafe links, you want to decide which unsafe link to resolve first. You will reduce the candidate size by introducing disjunctive constraints to resolve the unsafe link you selected. The commitment strategy here is that you want to have the largest candidate set for the plan, because somewhere in that candidate set is a solution. In the paper P2(page1646) there is a commitment equation to estimate the commitment induced by a constraint posting. commit(P,c) = 1 - card(INST(P u {c})) / card(INST(P)) P: the partial plan, c:constraint What they are doing is that they compare the commitment of two constraints by comparing the ratio of safe linearizations(minimum candidates) eliminated by them. The term of "instantiation" in the paper are actually talking about the safe linearization in the plan. However two random plans which have the same number of safe linearization, are not necessarily have the same size of candidates. For example, the plan 0*p1*O-O and the other plan 0