Common use of Successor Function Clause in Contracts

Successor Function. The interesting part is the successor function. Remember that the nodes in the search space represent plans, and, until a goal node is reached, each of those plans will have some flaws: open conditions and/or threats. To produce the successors of a node, what you will do is to select some flaw, and then compute all the ways of correcting (“resolving”) the flaw. Let’s consider the two types of flaws, starting with open conditions. Recall that an open condition is a precondition of some step that needs to be made true. Let (C,X) be an opencondition. There are two ways to resolve an (C,X). The simplest is to find some other step, S, already in the plan that makes the condition true (i.e., S has C on its add list). For every step S already in the plan that can be re-used to achieve the selected open condition, you will create a successor node that has an additional causal link (S,C,X), along with an additional ordering constraint that requires S to precede X. We then need to check if there is a new threat: it is possible that another step, Y, which is already in the plan, threatens the new causal link. This happens if C is on the delete list of Y, and Y is not already ordered before S or after X. (Be careful with operators such as sweep, with dusty as a precondition and dusty as a delete. You don’t want your program to think that an action threatens itself!) The other way to achieve an open condition (C,X) is to find an operator that makes it true, and then insert a new step S representing that operator into the plan. In this case, in the successor plan we again need to add a causal link and an ordering constraint between S and X. We’ve also got to add ordering constraints to ensure that S occurs between steps init and goal. We’ve got to add all of the preconditions of S to the set of open conditions. And, we’ve got to update the list of threats associated with the plan, to include any new threats that were introduced by S. That means that we need to look at the steps in the plan, to determine whether any of them delete the newly satisfied open conditions, and we need to look at all the causal links, to see if the newly inserted step deletes the propositions of any of the causal links. Remember that if there are multiple operators that can achieve the selected open condition, we will create multiple successor nodes. Now let’s consider how to resolve threats. A threat can be viewed as having four compo- nents: a producer step, a consumer step, a condition (that the producer makes true for the consumer), and a threatening step. There are two ways of resolving threats: 1. demotion: adding an ordering constraint that requires the threatening step to precede the producer 2. promotion: adding an ordering constraint that requires the consumer to precede the threatening step. The last interesting complication to our planning problem: whenever we introduce a new temporal ordering constraint, we need to make sure that it is consistent. A set of ordering constraints is consistent if three conditions hold: 1. No step precedes step ”init”. 2. Step ”goal” does not precede any step. 3. No step si precedes itself in the transitive closure of the ordering constraints. For example, you can’t have s5 before s7 and s7 before s5.