Introduction

Part 1 - The Problem and Problem Representation

Your navigational planner should take as input the specification of an initial state and a goal state. The states in the problem are intersections between roads. For instance, the input to the program could be of the form

     (10th atlantic) (north-avenue techwood)

i.e., the initial state is the intersection between 10th and Atlantic, and the final state is the intersection between North-avenue and Techwood.

The planner should output a route from the initial state to the goal state. If more than one path is possible, then it should return any one of them (which may or may not be optimal path). Thus, for going from (10th atlantic) to (north-avenue techwood), the output could resemble something like this:

(((10th atlantic)) ;; initial state
 (10th (10th fowler-1)) ;; operator and result state
 (fowler-1 (5th fowler-1))
 (5th (5th techwood))
 (techwood (north-avenue techwood))) ;; final state

Part 1 - Knowledge Representation

• The name of the street
• names of all the streets with which it intersects

    (atlantic 10th peachtree-place 8th-2 ferst-1 4th)

(Note again the simplifications: curved streets such as Ferst are decomposed into linear segments Ferst-1, Ferst-2 etc. Also, Northside Drive which continues as Tech-Parkway is simply called Tech-Parkway.)

(((10th atlantic)(north-avenue techwood)) ;; the index
 (10th (10th fowler-1))
 (fowler-1 (5th fowler-1))
 (5th (5th techwood))
 (techwood (north-avenue techwood))) ;; the path

As the adaptive planner solves new navigation problems, it stores the new navigation plans in the plan memory. Thus, the plan memory grows with new episodes of navigation planning. You may want to bootstrap the plan memory with some navigation plans; thus, the plan memory may initially contain plans for the following problems:

((10th atlantic) (north-avenue techwood))
((10th atlantic) (10th fowler-1))
((5th fowler-1) (north-avenue cherry))
((ferst-1 state) (north-avenue tech-parkway))
((10th tech-parkway) (5th fowler-1))
((10th fowler-1) (ferst-3 cherry))

Part 1 - Plan Retrieval

((ferst-1 state) (ferst-2 6th-1))

then the planner decides that the plan indexed by ((ferst-1 state) (north-avenue tech-parkway)) is relevant to the problem because of the exact match between the initial states. Similarly, if the new problem is

((10th curran) (5th fowler-1))

then the planner decides that the plan for ((10th tech-parkway) (5th fowler-1)) is relevant because of the exact match between the final states.

Part 1 - Plan Adaptation

((ferst-1 state) (north-avenue tech-parkway))

then this goal exactly matches the goal of a plan stored in the plan memory. In such cases, the stored plan directly provides a solution to the problem, and problem solving reduces to the retrieval of the stored plan and extraction of the solution.

In general, however, plan adaptation can be quite complex. One method (of many potential methods) for adapting navigation plans is goal-directed plan combination. In this method, the goal of the old plan is compared with the goal of the new problem, and the difference between them is set up as a subgoal. The subgoal is now used a probe into the plan memory, a relevant plan is retrieved and combined with the old plan. For example, if the goal of the new problem is specified as

((10th atlantic) (ferst-3 cherry))

then this may lead to retrieval of the plan for ((10th atlantic) (10th fowler-1)). The retrieval of this plan may lead to the formation of the subgoal of ((10th fowler-1) (ferst-3 cherry)). Next, when this subgoal is used as a probe into the plan memory, it may lead to the retrieval of the plan for ((10th fowler-1) (ferst-3 cherry)). Finally, this plan can be concatenated with the plan for ((10th atlantic) (10th fowler-1)) to obtain the desired plan for the given goal of ((10th atlantic) (ferst-3 cherry)). Clearly this method of goal-directed plan combination is recursive.

Part 1 - Plan Storage

You need to store the plans created by your planner in a plan memory. Again, you may want to index the stored plans by their initial and final locations. So, for example, the path to go from 10th atlantic to north-avenue techwood may be stored something like this:

(((10th atlantic)(north-avenue techwood)) ;; the index
 (10th (10th fowler-1))
 (fowler-1 (5th fowler-1))
 (5th (5th techwood))
 (techwood (north-avenue techwood))) ;; the path

Part 1 - Multistrategy Planning

If, at any given stage in adaptive planning, the planner cannot find a plan relevant to the current goal (or subgoal), then the planner may take invoke the methods of depth-first or breadth-first search (your choice) to form the navigation plan. This implies that the final plan may be result of two using different strategies. For example, the planner may use the adaptive approach to find a partially matching plan, form a subgoal, and then use the search method to complete the partial plan

Part 2 - Plan Failures

Failures can be of many kinds. One important kind of failure is called expectation failure. Let us suppose that the current model of the world specifies that a given street X allows traversal between intersections A and B.

                      Intersection A              Intersection B
street X          |--------|-----------------------------|------------|
(East, West)

Let us also suppose that this knowledge is incorrect: street X in the real world does not allow travel between A and B (due to construction activity, for example).

                     Intersection A               Intersection B
street X          |--------|-----------~~~---------------|------------|
(East, West)                         Blocked

Given a navigation problem, the planner may (mistakenly) produce a plan which specifies travel on street X between A and B. Clearly, this plan would fail upon execution. This is an example of expectation failure. Note that this kind of expectation failure can occur whether the system uses the method of model-based search or plan adaptation (or some combination of the two) to produce the navigation plan. In adaptive planning, for example, the planner may have used a past plan that specified travel on street X between A and B.

The next question is how might planner detect the failure? This requires an embodiment of the system on a mobile robot equipped with motor and perceptual faculties. Since we do not have access to such a robot (nor the time to embody planner even if we had access to a robot), let us imagine an "oracle" that provides information about the failure. The oracle first supplies planner with a goal, then receives a navigation plan from the system, next executes the plan in the real world, and finally provides the system with feedback on the execution of the plan.

The question now becomes precisely what feedback might the oracle provide? Let us suppose that the oracle begins with giving the following navigation goal to the system:

(10th atlantic) (north-avenue techwood)

The system gives the oracle the following navigation plan.

(((10th atlantic)) ;; initial state
 (10th (10th fowler-1)) ;;
 (fowler-1 (5th fowler-1))
 (5th (5th techwood))
 (techwood (north-avenue techwood))) ;; final state

Suppose that the oracle executes the plan, reaches the plan segment (5th (5th techwood)) and finds that 5th street is blocked between fowler-1 and techwood so that it is not possible to reach techwood. The oracle may then give the following feedback:

((((10th atlantic)) Success)
 ((10th (10th fowler-1)) Success)
 ((fowler-1 (5th fowler-1)) Success)
 ((5th (5th techwood)) Failure)
 ((techwood (north-avenue techwood)) Unknown))

Thus, the oracle may give feedback in the form of the outcome of the execution of each plan step in serial order until either the entire plan has been executed successfully or the execution of some plan segment fails. In this project, of course, you are the oracle. So, you will provide the planner with this kind of feedback.

Part 2 - Model Revision

   (Atlantic (10th Ferst-1 4th))

Now suppose that the oracle provides the following information as part of the feedback on some navigation plan:

   (...
    ((... (10th Atlantic)) Success)          ; We can reach (10th Atlantic)
    ((Atlantic (Atlantic Ferst-1)) Failure)  ; We can't go down Atlantic
    ...)

This indicates that it is not possible to use Atlantic for traveling from 10th to Ferst-1. planner may now revise the representation of the Atlantic Drive to reflect this. The new representation may look something like this:

   (Atlantic (10th Ferst-1 4th) (Blocked 10th Ferst-1))

You can design your own representation if you wish. But note that you do not want to just drop 10th and Ferst-1 from the list of intersections because a street that is blocked today may become unblocked tomorrow because of the dynamic nature of the world.

A second kind of learning from plan failures involves storing the failed plan in a "failed plan memory" so that the next time the planner encounters a similar problem it can be reminded of the past failure and can avoid making the same mistake again.

For this project, you want to focus on the first kind of learning, i.e., on revising the spatial model of the navigation world.

Part 2 - Plan Verification

Another possibility is to let the knowledge be inconsistent but to revise the problem solving so that it takes care of the inconsistency. Again, suppose that a navigation plan fails because traversal on street X between intersections A and B is not allowed in the world, and that planner revises its model to reflect this. So, some old plans in its plan memory may now be inconsistent with the revised model.

Suppose further that at this stage (of learning and memory) planner is given a new navigation problem. The system attempts to solve the new problem in the usual way, possibly involving both search and adaptation methods. It thus generates a tentative, candidate plan for the new problem. Now before giving this plan as output, it can verify the candidate plan by simulation. That is, it can verify the candidate plan against the current model of the world by tracing through the plan steps and making sure they are consistent with model. If this verification task succeeds, then the candidate plan can be given as output. If not, the candidate plan can be fixed.

Part 2 - Implementation Details

In other words, there is only a single level map, and your task is to add functionality to deal with plan failures. This is your top level function:

(defun plan-loop (src dest)
  (let* ((path (plan-path src dest))
         (failures (execute-plan src path)))
    (cond ((plan-succeeded-p failures) path)
          (t (learn-from-failures failures)
             (plan-loop src dest)))))

This function is a recursive function that initializes the variable path using plan-path and failures using execute-plan. It then tests for success using plan-succeeded-p (on failures), returning path if it did, or else calling learn-from-failures on failures if it did not, and recursing (i.e. looping). The top of the next loop starts out with plan-path and execute-plan again.

These functions are explained below.

In addition to writing your basic planner as given in the first part of the assignment, Your task is to write seven functions to handle plan failure and adaption:

(plan-path src dest)

Plan a path from source to destination. This call should execute the :choose method, as defined in the original planner. It should return a path that takes into account all known failure points

(execute-plan src path)

Execute a plan to take you from source to destination. The return value of this function should be as it has been specified above.

(plan-succeeded-p failures)

This function should look at the return value of execute-plan, and decide if the plan has succeeded.

(learn-from-failures failures)

This function should take the return value of execute-plan, and update the map to include the new failure points.

(add-failure-point intersection1 intersection2)

This function should take two adjacent intersections, and add a new failure point for execute-plan to test for.

(initialize-failures)

This function should remove all the failures that have been noted.

A sample interaction is presented below. Your program should be able to replicate this interaction.

=> (add-failure-point '(10th atlantic) '(atlantic peachtree-place))
T

=> (plan-path '(10th atlantic) '(atlantic peachtree-place))
(((10TH ATLANTIC)) (ATLANTIC (ATLANTIC PEACHTREE-PLACE)))

=> (execute-plan '(10th atlantic)
                    '(((10th atlantic)) (atlantic (atlantic peachtree-place))))
((((10TH ATLANTIC)) SUCCESS)
 ((ATLANTIC (ATLANTIC PEACHTREE-PLACE)) FAILURE))

=> (plan-succeeded-p '((((10th atlantic)) success)
                          ((atlantic (atlantic peachtree-place)) failure)))
NIL

=> (learn-from-failures '((((10th atlantic)) success)
                             ((atlantic (atlantic peachtree-place)) failure)))
T

=> (plan-path '(10th atlantic) '(atlantic peachtree-place))
(((10TH ATLANTIC)) (10TH (10TH STATE)) (STATE (STATE PEACHTREE-PLACE))
 (PEACHTREE-PLACE (ATLANTIC PEACHTREE-PLACE)))

=> (execute-plan '(((10th atlantic)) (10th (10th state))
                      (state (state peachtree-place))
                      (peachtree-place (atlantic peachtree-place))))
((((10TH ATLANTIC)) SUCCESS)
 ((10TH (10TH STATE)) SUCCESS)
 ((STATE (STATE PEACHTREE-PLACE)) SUCCESS)
 ((PEACHTREE-PLACE (ATLANTIC PEACHTREE-PLACE)) SUCCESS))

=> (plan-succeeded-p '((((10th atlantic)) success)
                          ((10th (10th state)) success)
                          ((state (state peachtree-place)) success)
                          ((peachtree-place (atlantic peachtree-place))
                           success)))
T

Note that, after the add-failure-point function is called, this example merely traces the execution of plan-loop above.

Part 2 - Issues

• Given a plan failure, what might be better from the viewpoints of memory, problem solving, and learning: updating the model or updating the plan memory (or both)? Why?
• Might it better to validate a plan retrieved from memory against the model immediately after retrieval (i.e., before adaptation)? Why?
• How would a planner discover that failure modes (i.e. street closures) that had been found are no longer valid?

Deliverables

For your basic planning program (Part 1 of the assignment):

1. The output of your program given the following inputs
   1. ((10th atlantic) (north-avenue williams))
   2. ((10th atlantic) (5th techwood))
   3. ((5th fowler-1) (north-avenue cherry))
   4. ((ferst-1 state) (4th atlantic))
   5. ((5th techwood) (north-avenue tech-parkway))
   6. ((6th-1 mcmillan) (8th-1 hemphill))
2. A print out of the case memory as it stands after the project is completed.
3. A critique of your system including
4. Experimental data to back up your findings, presented appropriately

1. Some data and test cases demonstrating the operation of your implementation of failure recovery.
2. A critique of your system design.
3. An analysis of the effect of failure recovery on efficiency.

1. Your source code