#| ******************************************************************************* PRODIGY Version 2.01 Copyright 1989 by Steven Minton, Craig Knoblock, Dan Kuokka and Jaime Carbonell The PRODIGY System was designed and built by Steven Minton, Craig Knoblock, Dan Kuokka and Jaime Carbonell. Additional contributors include Henrik Nordin, Yolanda Gil, Manuela Veloso, Robert Joseph, Santiago Rementeria, Alicia Perez, Ellen Riloff, Michael Miller, and Dan Kahn. The PRODIGY system is experimental software for research purposes only. This software is made available under the following conditions: 1) PRODIGY will only be used for internal, noncommercial research purposes. 2) The code will not be distributed to other sites without the explicit permission of the designers. PRODIGY is available by request. 3) Any bugs, bug fixes, or extensions will be forwarded to the designers. Send comments or requests to: prodigy@cs.cmu.edu or The PRODIGY PROJECT, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213. *******************************************************************************|# ; Search Control Rule Evolution ; ; 1. ALREADY-THERE: (build-step) ; To infer that a location was occupied, the RMG tried to move a small block ; into this location even though a big block was already there. Clearly, this ; location was already occupied by the big block. I originally wrote the rule ; ALREADY-THERE to fix the problem until I realized that CLOSEST-SIDE-FOR- ; OCCUPIED was firing and telling the RMG to prefer the small block over the ; big block because the small block was closer to him. I changed ; CLOSEST-SIDE-FOR-OCCUPIED so that it first checks to see if a block is already ; *covering* the sqloc. Previously it only checked to see if a block's location ; was *equal* to the sqloc. ; Later on, I insisted once again that ALREADY-THERE was needed because the ; above situation occurred. However this time the culprit was SUPPORTED-NOW ; which I had just recently added. This rule was telling the RMG to prefer the ; small block since the big block was sitting in a location that would be ; supporting something later. Obviously, leaving the block in this location ; would not have upset its supporting role later. So, SUPPORTED-NOW needed ; to check that the block's location was not already covering the location ; that would be supporting something later. ; ; ; 2. SUPPORTING-OBJ: (easy-stairs) ; To build a staircase in a top-down fashion, the RMG decided to use ; block3 as the top step. In order to put block3 down, however, the ; location underneath it had to be supported. In this subgoaling step, it ; picked up block3 to use as the supporting object. Well, it put block3 down ; as the bottom step and then picked it up again to put it down as the top step. ; Since the top location was no longer supported he had to put it back ; down and try to support this location again. It is quite obvious that ; this is not quite the optimal chain of events. ; In response, I added this rule which checks to see if a block ; is in a location such that it will be supporting an object later. This check ; is done by looking on the goal stack for an object that will need to ; be above the block or if the block is already supporting an object. If so, ; then it will prefer another object. ; ; ; 3. TOWARD-SUPERGOAL: (easy-stairs) ; To build the staircase, the RMG had to move out of a location so that ; he could put down a block at this location. Since he was only concerned ; about vacating the square, he didn't care which square he moved to. ; Invariably, he chose to move to a location away from all of the objects. ; Intuitively, he should try to move toward either 1) the next object that ; he needs to pick-up, or 2) the next location that he needs to move to. ; In this case, since he was vacating a location in order to put a block in ; this location, he should have a supergoal to put a block "at" a location. ; So, I added this rule which looks for this supergoal on the goal stack ; and prefers to move the RMG to a location which is closest to the block that ; he will need to pick up. ; When I added TOWARD-SUPERGOAL, the RMG decided that the location ; closest to the block was the location that the block was sitting on. So, he ; calmly picked up the block and sat down in its location. Well, this was fine ; and dandy because his next goal was to pick up the block anyway. This was the ; right thing to do, but for the wrong reason. He should not prefer a location ; if it is already occupied. So, I added this check in TOWARD-SUPERGOAL and ; told the RMG to give it another try. This time, he decided that the location ; closest to the block was the location directly on top of the block. He ; promptly jumped on top of the block and sat down. What a bright little guy! ; The chaos that resulted when he then realized that he had to pick up the ; block he was sitting on is too horrible to mention. At this point, I added ; a clause to TOWARD-SUPERGOAL that prevents him from preferring a location ; that is directly above the block that he is going toward. Finally, he did the ; wrong thing again, but for the right reasons. ; ; ; 4. NEXT-TO-OBJ-BEFORE-VACATING: (easy-stairs) ; This rule was written to make Prodigy do the right thing for the right ; reasons in the following situation: the RMG wants to move out of the way in ; order to put the block sitting next to him in his current location. ; Intuitively, he should pick up the block first, move to the block's old ; location, and then put it down in his old location. A higher level way of ; fixing this would be to have Prodigy reorder its goals so that he would try ; to pick it up before moving out of the way. The ordering that needs to be ; changed, however, is the ordering defined by the operator PUT-DOWN. Since I ; didn't want to mess with the operator, I decided to try to capture this case ; in a search control rule. If the RMG is moving out of his location ; (presumably to put a block there), then it looks for the next object that he ; will need to pick up (i.e. the next "at" on the goal stack) and checks to see ; if this object is currently at a location that he could move to in order to ; get out of the way. Since the RMG can only move to adjacent locations, the ; object must be adjacent to him. If so, then he should prefer this location ; which will have the side effect of causing him to pick up the block first so ; that he can move there. ; ; 5. UNOCCUPIED-SQLOC-FOR-PICK-UP: (easy-stairs) ; When the RMG went to pick up a block, the rule CLOSEST-SIDE-FOR-PICK-UP ; told him to prefer locations next to the block which were closest to him. In ; this case there were two locations adjacent to the block which were both next ; to the RMG. One of them, however, was already occupied by another block. ; Since both locations were equally far, the RMG should have preferred the ; location which was empty. Since he had not already inferred that the empty ; location was vacant, however, both locations had vacant-loc as an unmatched ; condition and so he could see no difference between them. Hence, I added ; this rule to prefer a location which is currently unoccupied. Unless, of ; course, it is currently occupied by the RMG. ; ; (setq *SCR-NODE-SELECT-RULES* nil) (setq *SCR-GOAL-SELECT-RULES* '((SELECT-FIRST-GOAL (lhs (and (current-node ) (list-of-candidate-goals ) (is-first-goal ))) (rhs (select goal ))))) (setq *SCR-OP-SELECT-RULES* nil) (setq *SCR-BINDINGS-SELECT-RULES* '((PUT-DOWN-ANYWHERE (lhs (and (current-node ) (current-goal (~ (holding ))) (current-op PUT-DOWN) (known (and (at RMG ) (next-to ))))) (rhs (select bindings ( )))) (MOVE-DELETE-RMG (lhs (and (current-node ) (current-goal (~ (at RMG ))) (current-op MOVE) (known (t-adjacent-locs )))) (rhs (select bindings ( )))) )) (setq *SCR-NODE-REJECT-RULES* '((BLOCK-SUPPORT-RULE-1 (lhs (and (candidate-node ) (candidate-goal (at )) (on-goal-stack (at )) ; DONT really need KNOWN test (known (under-loc )))) (rhs (reject node ))) (DONT-CLEAR-BY-PICKING-UP (lhs (and (candidate-node ) (candidate-goal (~ (at ))) (direct-supergoal-of (~ (at )) (clear )))) (rhs (reject node ))))) (setq *SCR-GOAL-REJECT-RULES* nil) (setq *SCR-OP-REJECT-RULES* nil) (setq *SCR-BINDINGS-REJECT-RULES* nil) (setq *SCR-NODE-PREFERENCE-RULES* nil) (setq *SCR-GOAL-PREFERENCE-RULES* nil) (setq *SCR-OP-PREFERENCE-RULES* nil) (setq *SCR-BINDINGS-PREFERENCE-RULES* '((TOWARDS (lhs (and (current-node ) (current-op MOVE) (candidate-bindings ( )) (candidate-bindings ( )) (known (and (at RMG ) (distance ) (distance ) (less-than ))))) (rhs (prefer bindings ( ) ( )))) (CLOSEST-SIDE-FOR-PICK-UP (lhs (and (current-node ) (current-op PICK-UP) (candidate-bindings ( )) (candidate-bindings ( )) (known (and (at RMG ) (distance ) (distance ) (less-than ))))) (rhs (prefer bindings ( ) ( )))) (CLOSEST-SIDE-FOR-PUT-DOWN (lhs (and (current-node ) (current-op PUT-DOWN) (candidate-bindings ( )) (candidate-bindings ( )) (known (and (at RMG ) (distance ) (distance ) (less-than ))))) (rhs (prefer bindings ( ) ( )))) ;(PREFER-OBJ-ALREADY-THERE ; (lhs (and (current-node ) ; (current-op INFER-OCCUPIED-SQLOC) ; (current-goal (occupied-sqloc )) ; (candidate-bindings ( )) ; (candidate-bindings ( )) ; (known (at )))) ; (rhs (prefer bindings ( ) ; ( )))) (CLOSEST-SIDE-FOR-OCCUPIED (lhs (and (current-node ) (current-op INFER-OCCUPIED-SQLOC) (candidate-bindings ( )) (candidate-bindings ( )) (~ (equal-p )) (known (and (at RMG ) (at ) (~ (in-location )) ; not there already (at ) (distance ) (distance ) (less-than ))))) (rhs (prefer bindings ( ) ( )))) (SUPPORTING-OBJ (lhs (and (current-node ) (current-op INFER-OCCUPIED-SQLOC) (candidate-bindings ( )) (candidate-bindings ( )) (~ (equal-p )) (known (and (on-goal-stack (supported-loc )) (or (at ) (on-goal-stack (at ))) (~ (in-location )) ; not already there (under-loc ))))) (rhs (prefer bindings ( ) ( )))) ; (ALREADY-THERE ; (lhs (and (current-node ) ; (current-op INFER-OCCUPIED-SQLOC) ; (candidate-bindings ( )) ; (candidate-bindings ( )) ; (known ; (and (at ) ; (in-location ))))) ; (rhs (prefer bindings ( ) ; ( )))) (TOWARD-SUPERGOAL (lhs (and (current-node ) (current-op MOVE) (current-goal (~ (at RMG ))) (candidate-bindings ( )) (candidate-bindings ( )) (~ (equal-p )) (known (and (on-goal-stack (at )) (at ) (distance ) (distance ) (less-than ) (~ (under-loc )) (forall () (at ) (~ (in ))))))) ; (~ (is-occupied-sqloc )))))) (rhs (prefer bindings ( ) ( )))) (NEXT-TO-OBJ-BEFORE-VACATING (lhs (and (current-node ) (current-op MOVE) (current-goal (~ (at RMG ))) (candidate-bindings ( )) (candidate-bindings ( )) (~ (equal-p )) (known (and (on-goal-stack (at )) (at ) (in-location ))))) (rhs (prefer bindings ( ) ( )))) (UNOCCUPIED-SQLOC-FOR-PICK-UP (lhs (and (current-node ) (current-op PICK-UP) (candidate-bindings ( )) (candidate-bindings ( )) (known (and (is-occupied-sqloc ) (~ (at RMG )))))) (rhs (prefer bindings ( ) ( )))) ))