The GPS illustrates the idea of solving a problem using a process called means-ends analysis, where the problem is stated in terms of what we want to happen. We can solve a problem if we can find some ways to eliminate “the difference between what I have and what I want”.

In means-ends analysis, the problem solver begins by evisioning the end (the ultimate goal), and then determines the best strategy for attaining the goal in its current situation.

“They assume the end and consider how and by what means it is attained; and if it seems to be produced by several means they consider by which it is most easily and best produced, while if it is achieved by one only they consider how it will be achieved by this and by what means this will be achieved, till they come to the first cause, which in the order of discovery is last… and what is last in the order of analysis seems to be first in the order of becoming”.

1. describe
   
2. specify
   
3. implement
   
4. test
   
5. debug and analyze
   

• Represent state of world (“what I have”) or the goal state (“what I want”) as set of conditions.
  
• A list of allowable operators. An operator is a struct composed of:
  
  1. an action
     
  2. a list of preconditions (states)
     

  3. a list of effects, where effect means
     

     • Add a condition from the current state.
       
     • Or, delete a condition from current state.
       

     Thus, a list of effects can be split into add-list and delete-list. Suppose we have an operation “drive-son-to-school”, its definition will be like:
     

     (make-op :action 'drive-son-to-school
              :preconds '(son-at-home car-works)
              :add-list '(son-at-school)
              :del-list '(son-at-home))
     

     It means after we apply this operation with precondition that “son-at-home” and “car-at-home” are already in our current state:
     

     • We remove “son-at-home” from our current state.
       
     • We add “son-at-school” to our current state.
       
• GPS problem = starting state + goal state + a set of known operators.
  If all conditions in the goal state can all be achieved, then the problem is solved.
  

• A single goal condition can be achieved:
  

  1. If it is already in the current state.
     
  2. Otherwise, we try to find some appropriate operator and apply it.
     

  Where, an operator is appropriate if it adds the goal into the current state(goal is in the add-list).
  

• We can apply an operator if we can achieve all the preconditions.
  

GPS-v01
Notice the recursion between achieve and apply-op. That is the key point to understand mean-end anaylsis. A goad could be achieved if:

• It is already in current state.
  
• Or, if there is an appropriate operation leading to that goal and we apply such an operation. However, before we apply an operation, we must achieve all the preconditions (So, we have to set each precondition as goal and achieve it).
  

• AI programming is more about discover more about the problem area. The problem definition is not clear.
  
• Traditional programming is more like construction of a building. The definition is clearly defined.
  

1. The clobbered sibling goal problem.
   
   • In our goal (A, B), we want to achieve both A and B. But our GPS interprete it as achieve A, then achieve B.
     
   • Sometimes achieving one goal can undo another, previously achieved goal.
     
   • That is, have-money and son-at-school are sibliing goals.
     

   • How to fix it?
     

     ;; Replace our (every #'achieve goals) with
     (defun achieve-all (goals)
       "Try to achieve each goal, then make sure they still hold."
       (add (every #'achieve goals)
            (subsetp goals *state*)))
     

     Think: How to improve to recover from a clobbered goal?
     

2. The leaping before you look problem.
   
   • The problem is trying to solve (jump-off-cliff land-safely). It would jump first, and only discover that it has no operator to land safely.
     
   • It arises because the planning and execution are interleaved. In another word, once the action is taken and *state* is irrevocably changed.
     
   • A solution could be: replace single global state with distinct local state variables.
     
3. The recursive subgoal problem.
   

   • If we add this extra operator, the GPS could goes into loop infinite.
     

     (make-op :action 'ask-phone-number
              :preconds '(in-communication-with-shop)
              :add-list '(know-phone-number))
     

     • Know-phone-number need in-communication-with-shop as precondition. While in action telephone-shop, in-communication-with-shop need prerequisite know-phone-number, so on and so on.
       
     • It is caused by trying to solve a problem in terms of itself.
       
     • One solution is to keep track of all the goals that are being worked and give up if it seems a loop in the goal stack.
       
4. The lack of intermidate information problem.
   

Main changes differ from version01:

1. GPS now return resulting states instead of printing messages when each operator is applied.
   
2. Change global state to use local state, so major functions will need to pass local state as extra variable.
   
3. Introduce global stack to solve the recursive subgoal problem.
   

Functions that return nil as an indication of failure and return some useful value otherwise are known as semipredicates. They are error prone when nil might be constructed as a useful value. 3 constraints must be considered to prevent this:

1. Decide if nil could ever be a meaningful value.
   
2. Insure that user can’t corrupt the program by supplying nil as a value.
   
3. Insure that program can’t supply nil as a value.
   

• I think GPS is basically doing graphical search.
  
  • In traditional graphical search, such as from vertex A to vertex M, the A and M are themself the inital state and ending state. In GPS, the inital state and ending state (goal) are list of conditions. Each action, moving from vertex x to vertex y is either added or/and delete a condition from its current state and the search ended when its current state contains all conditions defined as goal.
    
  • In traditional graph search, we can move from vertex x to vertex y if there an edge between them. In GPS, this edge is defined as operation (add, delete list + preconditions). Each action’s preconditions constraits us to follow certain edges, so we can move from A to Z one edge after another if the current goal is on the edge’s add-list.