PLANNING, SITUATION CALCULUS, ANSWER EXTRACTION, MONKEY & BANANAS We have studied some basics of AI search techniques, and logic. One motivation for both of these was their role in planning: how an agent can start with a KB and a goal, and come up with a plan for how to achieve that goal by means of a sequence of actions that, one by one, change the state of the world into one where the goal has been achieved. So, this is a search problem. But if the problem can be specified in terms of logic, then there is a chance that the search can be carried out by a specialized logic engine that then lets us focus on the careful specification of the KB rather than the details of the search. This is the basis for the situation-calculus, due to McCarthy and Hayes (and implemented by Cordell Green) in 1969. SITUATION CALCULUS In the "sit-calc", an action is represented by means of a function f that takes a state of the world, s, as input and returns another state s' as output: s' is the state the world will be in after that action has been performed when the world was in state s. Since the action of f may involve various specific things in the world, it will also have other arguments in addition to s. Here is an example, with the action "push": At(x,y,s) -> At(x,y,push(x,y,loc,s)) Intuitively, this says that if an entity x happens to be where entity y is, in world state s, and if while in that state s, x performs a push action on y (to some location loc), this will change the world to a new state -- written as push(x,y,loc,s) -- in which x is still where y is. This is an example of a so-called "frame axiom", stating that a certain fluent -- in this At(x,y,_) -- is *not* changed when the state changes due to x pushing y. The *if* part of this -- At(x,y,s) -- is a *precondition* for push: in order to push something, one must be where it is. And the postcondition of this axiom is that x is still where y is. Of course, when pushing something, the more interesting point is that the object being pushed moves to the location it is pushed to: At(x,y,s) -> At(y,loc,push(x,y,loc,s)) So this is a *change axiom*: it tell us how a push changes things. One might think that what a robot's KB really needs is info about all the changes that occur when an action is done. But of course it is just as important to know what does NOT change; whatever the resulting world state is, one needs to know enough about it to be able to decide on appropriate actions. For instance, if a potted plant is on a table in the center of the room, and if we want it to get more sunlight, we might push the table close to a window. However, this will only work if the plant moves along with the table as we push it. We need to know that the fluent OnTable(plant,_) remains true when the state changes as the result of the push. Why not just assume that a fluent does not change unless we know it will change? That is a good idea, but not so easy to make it work out in practice. It requires either: 1. knowing all changes that actions can cause, or 2. knowing "enough" about typical or important changes so that the ones one doesn't know won't cause difficulties, or 3. having really good error-detection and correction algorithms to clean up whatever messes arise from such difficulties. Here are further examples of frame axioms: If we push a table toward a window, the walls do not fall down; the air does not leave the room; the table does not change color or weight; we do not die. These may sound silly. But when we flip a switch on the wall, the ceiling lights go on -- so things not in direct contact can affect each other, and in ways that on the face of it are not related: what does an up-down motion of a one-inch piece of plastic on the wall have to do with the presence or absence of light coming from the ceiling? -- and why not light from the floor? So, there would seem to be a lot of special knowledge that we have, about what does and does not happen. In fact, the frame axioms that might be needed for a given planning problem can vastly outnumber all other axioms. Worse, in some cases it appears to be impossible to completely write them all down, even in principle. One speaks of the "frame problem" as the difficulty in dealing with the need for such axioms. We will say a little more about this later. EXAMPLE: the Monkey and Bananas Problem As we have seen, this problem involves a room, fruit F suspended from the ceiling, a movable box B, and a monkey M. Actions are: push, goto, climb, grasp. Fluents are: On, Has, At. The initial situation is s_0. The location on the floor just under the fruit is L. The monkey cannot reach the fruit except by standing on the box (while the box is positioned at L). The goal is a state s in which Has(M,F,s) is true; or at least to prove there is such a state: (Exists s) Has(M,F,s). Here are axioms describing the initial state, and the effect of actions on fluents (loc is a variable representing possible floor locations): INIT: -On(M,B,s_0) Change axioms: 1. -On(M,B,s) -> At(M,B,goto(M,B,s)) [wherever you go, there you are] 2. On(M,B,s) & At(B,L,s) -> Has(M,F,grasp(M,F,s)) 3. At(M,B,s) -> At(B,loc,push(M,B,loc,s)) [M is wherever it is pushed] 4. At(M,B,s) -> On(M,B,climb(M,B,s)) [you are on what you climb] Frame axioms: 5. At(M,B,s) -> At(M,B,push(M,B,loc,s)) [pusher stays with pushed object] 6. At(B,loc,s) -> At(B,loc,climb(M,B,s)) [climbing does not move B] NG (negated goal): (Forall s)-Has(M,F,s) Now we need to put all the axioms and the negated goal into CNF: INIT: -On(M,B,s_0) 1. On(M,B,s) v At(M,B,goto(M,B,s)) 2. -On(M,B,s) v -At(B,L,s) v Has(M,F,grasp(M,F,s)) 3. -At(M,B,s) v At(B,loc,push(M,B,loc,s)) 4. -At(M,B,s) v On(M,B,climb(M,B,s)) 5. -At(M,B,s) v At(M,B,push(M,B,loc,s)) 6. -At(B,loc,s) v At(B,loc,climb(M,B,s)) NG: -Has(M,F,s) Then we try to prove the null clause from the above. Below is a start, where numbers in parens indicate results of resolution steps. Note that when the same variable (such as s) occurs in two different wffs being resolved, one has to be renamed since they need not have the same meaning. INIT Ax1 -On(M,B,s_0) On(M,B,s) v At(M,B,goto(M,B,s)) \ / [s is unified with s_0] Ax3 (7) At(M,B,goto(M,B,s_0)) -At(M,B,s) v At(B,loc,push(M,B,loc,s)) \ / [s unifies with goto(M,B,s_0)] (8) At(B,loc,push(M,B,loc,goto(M,B,s_0))) ... and so on; eventually we also need this step: NG Ax2 -Has(M,F,s') -On(M,B,s) v -At(B,L,s) v Has(M,F,grasp(M,F,s)) \ / [s' unifies with grasp(M,F,s)] (12) -On(M,B,s) v -At(B,L,s) The overall pattern that results is this: INIT Ax 1 \ / Ax3 7 Ax5 \ / \ / Ax6 8 9 Ax4 NG Ax2 \ / \ / \ / 10 11 12 and then two more resolutions are needed (11 with 12, and that result with 10) to get the null clause. (Details of the full proof are left as an exercise.) OK, fine. This proves the monkey can get the fruit: there is a state s where Has(M,F,s) holds. But how does the monkey do it? What is the sequence of actions -- i.e., the "plan" -- that gets there? That after all is what we want. ANSWER EXTRACTION There is a trick that can be used in the resolution process, that finds the bindings (unifications) that are done to the state s in NG that lead to the null clause; and these are precisely the actions, in sequence, that make up the plan. Here is how it works, in a simpler example: How to break an egg: drop it! Now let's do this in sit-calc: INIT: Holding(egg,s_0) Goal: (Exists s)Broken(egg,s) NG: -Broken(egg,s) Axiom: Holding(egg,s) -> Broken(egg,drop(egg,s)) CNFs: Holding(egg,s_0) -Broken(egg,s) -Holding(egg,s) v Broken(egg,drop(egg,s)) Proof of null clause: Holding(egg,s_0) -Holding(egg,s) v Broken(egg,drop(egg,s)) \ / [s unifies with s_0] Broken(egg,drop(egg,s_0)) -Broken(egg,s) \ / [s unifies with drop(egg,s_0)] null Trick ("answer extraction") to get the plan: when NG is used, conjoin with it the goal itself: NG **v G**, as in -Broken(egg,s) **v Broken(egg,s)** where **...** is used to tell us that we do NOT want to resolve that part away. The purpose of the ***v G*** is to keep track of all the things the s in NG changes into via unifications during the proof. But since NG is not even there at the end (only null is left) we need something like **v G** to keep a record. So here is the proof again, with answer extraction: Holding(egg,s_0) -Holding(egg,s) v Broken(egg,drop(egg,s)) \ / [s unifies with s_0] Broken(egg,drop(egg,s_0)) -Broken(egg,s) **v Broken(egg,s)** \ / [s unifies with drop(egg,s_0)] {v Broken(egg,drop(egg,s_0))} So now instead of getting null, we get the record of what s has become: a full description of the state that makes G true. And so the plan here is drop(egg,s_0). Note that the example above brought in **v G** almost at the end; but it needs to come in wherever NG is brought in, early, late, or middle. So, we now have seen how situation calculus can solve planning problems. But it is not perfect, due to the frame problem, and also because it needs a full-scale theorem-proving engine (which can be slow, and in general can encounter infinite-depth proof trees). And it shares -- with most other approaches to planning and reasoning -- difficulties in dealing sensibly with an inconsistent KB. PROLOG is, by the way, NOT a full-scale FOL engine. It uses only so-called Horn clauses as axioms; these are wffs of the special form P :- Q1,Q2,...,Qn [read: P if Q1 & Q2 & ... & Qn ] which is equivalent to -Q1 v -Q2 v ... v -Qn v P. That is, at most one non-negated predicate expression may occur as a conjunct. This means that even the simple wff P v Q is not a Horn clause and cannot be used as an axiom in PROLOG. PROLOG tends to be very efficient, but this is in large part due to its restriction to Horn clauses. There has been much research in pushing this constraint aside in various ways. Note that the Monkey & Bananas problem, in the form we presented it above, has one axiom whose CNF is not a Horn clause (can you see which?). PLANNING IN GENERAL In many cases, a planning problem does not need the full rich language of FOL (as used in sit-calc); then simpler planning mechanisms can be used. A famous one is STRIPS. STRIPS does not reason about how situations change as actions are performed. Instead KB simply keeps a record of the *current* state of the world and has fixed rules about what changes to make to that, for every action that might be applied. So if a fluent -- say AT(B,L) -- is true now (i.e., in the KB), and if the climb(M,B) action is done, then ON(M,B) becomes true (is entered into the KB, and -ON(M,B) is removed if it was there). And for that action nothing else is done; hence AT(M,L) is left in the KB, and no special axiom is needed. Thus STRIPS in effect assumes a fluent does not change unless it has a rule saying it will change. So there is no frame problem for STRIPS (unless deciding which additions and removals to make is considered a problem, as it might well be). This is fine as far as it goes. But in STRIPS situations (or states) are not only not reasoned about, they are not even represented (notice above that fluents ON, AT etc have no situation variables s, as they do in sit-calc). In fact, there are no quantified variables in STRIPS. So that means statements about states in general cannot even be expressed (such as the goal of finding ALL states with a certain property) or even a single state with the property that all eggs (say) are broken. Why not add quantifiers to STRIPS? Well, then it becomes FOL, and to make use of such quantified wffs one needs inference rules, and we are back where we started. Still, STRIPS is great for certain things. It was a key part of the early and famous "SHAKEY" robotics research program at SRI in the 1970s. SHAKEY was a robot (that was a bit unsteady as it rolled about, hence it's unflattering name). Using STRIPS (and lots of other nifty then-state-of-the-art technical machinery, including vision, navigation algorithms, and so on) SHAKEY was able to make and carry out plans to move about in a laboratory to find objects it was told to look for or go to. AI planning is now a huge field of research, and we have barely scratched the surface (same as we did for AI search, and also for AI logic). We will end this section with a few further comments about the planning subfield: Often, a particular planning problem naturally decomposes into a high-level sketch and low-level detail. Here is an example: suppose you need to get from DC to San Francisco. A high-level plan could simply be: fly there. That is not greatly different from the goal (get from DC to SF), but it does at least give some indication of what kind of (high-level) action to be done (use an airplane). But to do *that* there are preconditions (be at BWI airport, say) and further actions (take a taxi) to get preconditions to be true, and so on. Of course, one does still have to do all the lower-level actions (pack, call a cab, etc), so this might not seem very different from what we would do in sit-calc or STRIPS. But now think about the other end of the trip: when the plane lands, we are not in SF, but at SFO airport, and we need to call a taxi there too (or maybe use a shuttle, or whatever the situation at the end turns out to require). It not only is not necessary to plan out those end-of-trip details now (before we start enacting the early parts of the plan: packing, getting to BWI), but may not even be possible (since we might not know about ground transportation at SFO, or might not want to commit to those details yet). So we do "hierarchical" planning, roughing out a general sketch of the broad activities, then refine it. This can be automated, and the methodology uses what are called HTNs: hierarchical task networks. HTNs can make planning easier to describe and manage, in focusing the processing on a smaller set of issues at a given moment. They lend themselves to plan re-use or adjustment when a given plan no longer works under slightly changed conditions; it may be that the high-level parts are ok and only a low-level change is needed, for instance. Your next project (Project 2) will involve hierarchical planning. Here are a few other issues (among many others): multi-agent planning; how to ensure that the time taken to plan won't leave too little time to act; and what to do when the expectations that a plan is based on turn out to be incorrect. The last of these is related to something McCarthy called "elaboration tolerance", namely the ease with which we can "modify a set of facts expressed in the formalism to take into account new phenomena or changed circumstances". And that bring us to the topic of commonsense reasoning, which we will address next.