March 8 Notes taken by Megan Conway, Megan.Conway@asu.edu 12345678901234567890123456789012345678901234567890123456789012345678901234567890 Outline of upcoming classes: 3/20/00 IxTet and HSTS Read:1.IxTeT: an Integrated Approach for Plan Generation and Scheduling by Phillippe Laroie and Malik Ghallab Read first as an overview of IxTeT 2.Representation and Control in IxTeT, a Temporal Planner by Ghallab & Laruelle Concentrate on control aspect 3.Planning with sharable Resource Constraints, by Laborie & Ghallab Focus on how it detects and resolves conflicts 4.Planning in Interplanetary Space: Theory and Practice by Jonsson, Morris, Muscettola and Rajan On HSTS planner 3/22/00 Temporal CSP Beyond incomplete initial states, stochastic Notes on IxTeT & HSTS: IxTeT stands for index time tables. HSTS is the planner used by RAX (Remote Agent Experiment) Both planners use metric time. IxTeT represents time as points, while HSTS represents time as intervals. Unlike HSTS, IxTeT supports resource reasoning for sharable resources. In this case, sharable is defined as a finite capacity greater than one. CBI as defined by Smith is an condensation or umbrella for these two methods. Notes on IxTet: The IxTeT architecture, see figure 2 in IxTeT: an Integrated..., has constraint managers and analysis modules. The constraint managers are time map and variable constraints. The variable constraints fall into two general categories: co-designate and non-designate. Co-designate means two variables designate the same thing, in other word are equal. Non-designate means two variables do not designate the same thing, not equal. (*addition* IxTET does not allow for the use of metric constraints) These constraints are easily convertable to CSP. During constraint propogation on these variable bindings it checks to see if the equal constraints violate the unequal constraints Variable constraints look like: ---- on(u,v) ---- | | -----------------> | | on(x,y) ---- ---- ---- | | not on(l,m) ---- u,v,x,y,l,m are all variables. In order for the causal explanation on(u,v) to exist in the above situation the following must hold: u=x, v=y and (l not = u, m not = v) (it is enough to say either set is not equal to l and m, don't need both). In addition, variable constraints can be used to make inferences such as: Let x = {a,b,c} and y = {w, b, c} If x=y then a and w can be removed as domain choices. Let x = {a} and y ={a,c} if x not = y then y = c. For infinate domains, solving these variable constraints requires polynomial time. However, for finite domains it is np-complete. Here is why. If y not = c and x not = y then obviously a dead end has been reached because neither value can be assigned a. This creates problems. The Time Map constraint manager uses constraints like 20 < x < 25. On area of confusion about the variable managers is how it handles loose coupling. In order to handle the variable and time constraints seperately, as decribe above, each constraint must be either a time or variable constraint. However, some constraints and constraint propagation techniques (promotion, demotion, separation) may relate to both time and variable constraints. How IxTeT handles these situations is not clearly defined. Basically, IxTeT works in three stages. It thinks, it selects an action (subgoal, resource or threat) and crunches new constraints. When all variables within the plan have been assigned a value, all resources have been correctly allocated and no threats remain, IxTeT is done. In some respects IxTeT is like UCPOP. It uses causal link encodes, but only precedence relation ones. When resolving conflicts, unlike UCPOP, IxTeT does not always split the disjunction into the search space. It may occur do so at times, but not necessarily. However, each possible establishment is still placed in its own branch. (*addition* Although IxTET is capable of handling disjunctions that appear during computation, it does not allow an initial disjunctive problem. It is not very clear as to why this is so.) Representation and Control: There are analysis modules: subgoal analysis, threat analysis and resource analysis. The subgoal analyzer determines which is the next subgoal to provide for establishment. The threat analyzer tracks flaws or unsafe links that need to be fixed. The resource analyzer handles resource conflicts. In order to understand IxTeT we should concentrate on how the system picks which subgoal, threat or resource conflict to handle. Specifically, is it similiar to CSP (paranoid about picking next variable) or random like UCPOP (toss a coin and pick). There are at least 15 different selection ideas embedded in the system. However, no evaluation of these different approaches was done so it is virtually impossible to determine which are directly correlated to speed. One selection heuristic used is for action choice. Because IxTeT, like all planners, wants to backtrack as little as possible a heuristic similar to HSP or Greedy Regression Graph is used. A action is picked based on its preconditions. Not by the number of preconditions, but by how hard it would be to establish said preconditions. Handling Sharable Resources: See the notes from 3/8/00 about the difficulty in handling sharable resources. IxTeT uses a special analysis called a cut set to help detect and resolve conflicts, which is exceedingly difficult. ??'s That Remain: Why are metric constraints not included and how hard would it be to include them? Why is disjunction not allowed as part of the problem specification? Notes on Time: 2 issues relating to time: metric vs. qualitative and interval vs. point For interval time Smith defines 13 interval relationships as seen in figure 10 on page 22. (Compliment relations exist for all 7 shown except A=B). With these representations of time preconditions can be true before, after or throughout an action. An example: When driving and you're stopped at a light. The light must turn green for you to go, but it does not have to remain green the entire time you are driving (true before). However, you have to have gas during the entire driving time (true throughout). Time points can represent the same type of relationships as intervals. A contains B can be represented as timeA < timeB and timeA + durationA > timeB + durationB. However, there are differences between the two representations. For instance ---- ---- ---- | x || y || z | ---- ---- ---- x meets y, y meets z. In interval representation x does not meet z, however in point representation x does meet z. Answers to Questions on Smith Paper: What makes a algorithm a dynamic constraint satisfaction engine? property one: during execution extra constraints are added for existing variables property two: new variables with new constraints are being added. Either property satisfies definition. (*note* I believe that different authors use the term to mean different things. Be sure to recognize whether the author is describing an engine with property one, property two, or both.) Metric Quantities and creation of infinite # of possible actions: For state based encodings you must permanently decide the quantum of each state. In other words how long it will be 3 ms or 4 ms or 1 minute or... Once you've done so showing that an action occurs over an interval becomes tedious and adds a tremendous amount of constraints. Smaller quanta allow for better accuracy but severely increase the difficulty. If you can split an action so that it can be partially satisfied at different points in the plan than there is an infinite number of ways this can be done. For instance, if you want 10 gallons of gas you could put in 2 now and 8 tonight before you go home, or you could put it all in now or .. The number of possibilities never ceases. One planner that does look at splitting up a task is Zeno. Least Commitment issues: Least Commitment can be good and bad. If you make up your mind too fast than more backtracking is required, but if you don't do it at all there are too many possibilities. For example, if you plan out the next 10 years of your life you are in trouble. However, if someone asks you what you are doing on Friday and you don't have any idea you could be faced with too many choices. Joslin wrote some paper that said least commitment for actions was bad and least commitment for flaw resolution was good. Rao is not sure this paper is actually proof of the matter, but many feel it is. Miscellaneous: casual explanation: establisher that no one kills What might be represented as conjunctions in some planners may be represented as disjunctions somewhere else. Rao wonders if this is because we worry because disjunctions are hard or is it something about their representations Rao suggested that trying to model problems represented by one encoding in another encoding is a good way to understand the encoding and find similarities and differences between them. Specifically, he asked if plan space SAT encodings could be used by IxTeT? )