To: AI Students From: Eric Here is the problem I mentioned during the final lecture: ------------ "Allen STRIPS" or "Clocks 'n Blocks" Consider a hybrid system for planning that combines Allen temporal constraint propagation with the semantics of STRIPS operators. In particular, assume you have STRIPS operators defined for some domain. Each operator has a name (the action), and pre and post-conditions. The pre-conditions are prerequisites -- they must hold true in order to perform the action. The post-conditions are descriptions of states, or negations thereof; new states, and which old states get eliminated when the action is performed, respectively. Your hybrid system takes as input an Allen (i.e., temporal) network in which each interval (i.e., node) represents the execution of an action of one of the STRIPS operators. That is, the network encodes some temporal constraints between members of a set of actions that are to be performed. Your job is to write an algorithm to check whether these temporal constraints are consistent with the ordering constraints set forth by the pre- and post-conditions of the STRIPS operators. That is, the Allen network encodes temporal constraints, and the effect/precondition semantics of STRIPS operators indirectly entail further temporal constraints. There are many domains in which we may have two sources of constraints as such, in which case they need to be mutually resolved. For example, consider a planning system that determines a sequence of bureaucratic procedures (paper shuffling, meetings, etc.) to accomplish some goal, e.g., coordinating the faculty to agree on and implement the change of computer science department phones from ROLM to a less expensive phone switch. Temporal constraints may come from, for example, the availability of certain faculty who go on trips to conferences. STRIPS' conditions may come from a simple semantic model of conditions, e.g., it is necessary to attain a passing faculty vote before the chair can write a proposal. Your algorithm takes as input a temporal network with constraints. This network will have instantiated STRIPS operators associated with each node -- since they are instantiated their variables have values, e.g., WriteProposal(Kathy). It also takes the set of STRIPS operators, and a goal condition (i.e., state) as input. It must then test for consistency: can an ordering of the actions be produced that adhere to both kinds of constraints and achieves the goal? Note that in doing this, the algorithm is not only checking whether the temporal constraints are OK for the plan to work, but also whether the set of operators in the Allen net, instantiated as they are, are sufficient to achieve the goal For example, the Allen net could have 5 operations for a goal that would require at least 10, or it could have operations that don't lead to the goal. Hint: Add the conditions themselves (which result from and are prerequisites to the operators), as temporal intervals, to the Allen net. Probably give about 10-12 sentences of detail on this. A couple diagrams could help you visualize, e.g., relationships between conditions and their negations. ------------ ANSWER: If these actions are to be played out as a plan, there has to be a linear ordering of them such that when each action is to be done, its prereqs are fulfilled, and its effects are taken into account -- these effects can serve as prereqs for a future action, or, in the least, they must not conflict with needed prereqs. So, first add an interval (node) to the temporal net for each effect of each operation. These intervals are of course contrained to be met by the action that caused them. Then, you need to make sure there is an effect-interval that fulfills the prereqs for each action, and that temporal constraints are all filled. Specifically, effect-intervals must be matched to each action they can fulfill the role of prereq for, and they must be then constrained to temporally meet or contain they action that needs it. If that action causes the effect to no longer be true, it must be "meet", else it can be contain. You need to search for such a matching such that after all the temporal net constraint propagation has been done, you have a consistent (i.e., possible) network. Note that an action inverval is never added -- only effect/prereqs (i.e., states). I have left off some details here: First, there must be a system to deal with negative versus positive literals. And, second, you gotta worry about variable instantiation. By the way, there won't be any questions this involved on the final :) -Eric