Assignment 2

Adaptive Navigational Planning
Assigned: September 21, 1999
Due: October 5, 1999

Introduction

In this project, you need to design an adaptive navigational planner that

  1. Plans routes on (a representation of) the Georgia Tech Campus by modifying past navigation plans
  2. stores new navigation plans in a plan memory for potential reuse in future.

You will also implement your design in a computer program (in Lisp or C), experiment with the program, and write a critique of your system design.

Problem and Problem Representation

The problem and the problem representation in this project are the same as in Project 1. That is, the adaptive planner accepts the same navigation goals, specified by the initial and final locations, as in Project 1. Its planning knowledge and method however are quite different from that in Project 1.

Knowledge and Knowledge Representation

In addition to a model (or map) of the navigation world (viz. the Georgia Tech campus), the adaptive planner has access to a plan memory. The plan memory contains plans that the planner formed in previous episodes of navigation planning. The plan memory is organized functionally, that is, the stored plans are indexed by their goals which are specified by the initial and final locations. For example, the plan to go from the intersection of 10th and atlantic to the intersection of north-avenue and 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

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. For Project 2, you may want to bootstrap the plan memory with the navigation plans created in Project 1. Thus, the plan memory may initially contain plans for the following problems:

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

Plan Retrieval

The adaptive planner solves new problems by retrieving apparently relevant plans from its plan memory and adapting them to the new problem. So one issue in adaptive planning is how to decide on the relevance of a stored plan to a given problem. The adaptive planner may use the goal of the new problem (the initial and final states) as a probe into the plan memory and compare it with the indices to the stored plans. For Project 2, you may assume that the adaptive planner decides on the relevance of a stored plan based on an exact match between either the initial states in the probe and the plan index, or the final states in the probe and the index. For example, if the goal of new problem is

((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.

If the initial/final states in the index to more than one stored plan match the initial/final states in the probe, then the choice between them can be arbitrary. For example, if the probe is specified as

((10th atlantic) (ferst-3 cheery-2))

whose initial state matches the initial states of both

((10th atlantic) (north-avenue techwood))
((10th atlantic) (10th fowler-1))

then the choice between ((10th atlantic) (north-avenue techwood)) and ((10th atlantic) (10th fowler-1)) can be arbitrary.

A special case in navigation planning is when the initial state in the probe exactly matches the final state in a plan index and the final state in the probe exactly matches the initial state in the plan index. For example, the probe may be ((north-avenue tech-parkway) (Ferst-1 State)) and the plan memory may contain a plan indexed by ((Ferst-1 State) (north-avenue tech-parkway)). For project 2, the planner will consider this plan as relevant to the current problem and retrieve it.

Plan Adaptation

As mentioned earlier, the adaptive planner solves new problems by retrieving stored plans and adapting them to meet the specifications of the new problem. A special case of plan adaptation occurs when the probe into the plan memory (the goal of the new problem) exactly matches the index to a stored plan (the goal of the stored plan). In navigation planning, for example, if the goal of the new problem is specified as

((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.

As mentioned earlier, in navigation planning, another kind of special case can occur because navigation routes often are reversible (especially if all streets are bi-directional): the initial state in the new problem may exactly match the final state in the index to a stored plan, and the final state in the new problem may exactly match the initial state in the index to a stored plan. In such cases, the stored plan can be reversed to obtain the desired solution. For example, if the new problem is ((north-avenue tech-parkway) (Ferst-1 State)), then the plan for the goal of ((Ferst-1 State) (north-avenue tech-parkway)) can be reversed to obtain the desired plan.

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-2))

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-2)). 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-2)). 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-2)). Clearly this method of goal-directed plan combination is recursive.

Multistrategy Planning

In general, there is no a priori guarantee that the above adaptive approach to navigation planning will succeed in solving a given problem. Its success would depend on the relation of the given problem with the plans available in the plan memory.

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 depending on your conclusions based on Project 1) 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.

Implementation Details

Write a function of the form

(plan-path source destination method)

where source is the start intersection, destination is the goal intersection, and method is one of the following:

:search
Use a search method. You are free to choose between DFS and BFS. (Hint: Which gives better solutions?)
:cbr
Reuse a case from memory. If no appropriate case is found, fail.
:choose
Choose between CBR and search to find a path from the source to the destination. Choose something simple. A routine that first attempts reusing a case, and on failure performs a search, will suffice.

Search you have already encountered in assignment 1. For CBR, you have to implement three steps, each as a distinct function:

retrieval
Retrieve a set of cases that might be possible to adapt for the current situation. You collected cases in assignment 1 into your case memory. Now you must retrieve old cases for reuse from that case memory. (Hint: Try to match the source/destination pair for the current problem to the source/destination pairs for the stored cases.)
evaluation
Decide which case is most likely to yield a good solution. In this map, any case can potentially be adapted to produce a solution. In general, case based reasoning may lead us to a dead end on our first attempt, so we may have to retry with another case. Your evaluation algorithm should be simple, otherwise it defeats the purpose of case-based reasoning.
adaptation
Adapt your chosen best case to take you from the source to the destination.

If any of the above steps fail, CBR fails.

Finally, when you have found a path, you must decide whether or not to store it. Note that this decision can be made at an earlier stage in case-based reasoning. If while applying CBR you find an exact match in case memory, it would not be worth storing that path all over. If you find no matches, then storing the path would be especially useful. If you have something in between, your evaluation metrics might also provide information about whether or not it is worth storing the path. Write an explicit function for handling storage that decisions if the path may be useful for future searches.

Experiments

As you design, code and run your programs, think about the following questions:

  1. What would be good test data for this project? How would you generate this data?
  2. Which planning method is easier to code? Why?
  3. Which planning method is easier to use for constructing a successful plan? Why?
  4. Which planning method leads to ``better'' plans? Why? Can you generate data to support your hypothesis? Try to do it.
  5. Which planning method is more efficient? Why? Can you generate data to support your hypothesis? Try to do it.
  6. For what class of problems, and under what knowledge conditions, does the adaptive method offer computational advantages.
  7. What other planning methods might be possible?
  8. Which planning method appears cognitively plausible to you?

Deliverables

On a paper hand in:

  1. To set up the case-memory, run your program using a search strategy for the following inputs (YOU DO NOT HAVE TO TURN THIS IN):
    1. ((10th atlantic) (north-avenue techwood))
    2. ((10th atlantic) (10th fowler-1))
    3. ((5th Plum) (north-avenue cherry))
    4. ((Ferst-1 State) (north-avenue tech-parkway))
    5. ((north-avenue williams) (10th curran))
    6. ((10th fowler-1) (ferst-3 cherry))
  2. Next run your program using a case-based strategy for the following inputs. Note for each if any case was reused, and how much effort was spent adapting the case.
    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))
  3. Turn in a print out of the case memory as it stands after step C.
  4. Clear the memory and solve the paths in C using a search strategy. Note the effort used, again.
  5. Turn in a comparison of the results. Compare the results obtained from 3 and 4. When does the search strategy work best? When does the case-based strategy work best?
  6. Include in the report an analysis of CBR for path planning. Think about issues of efficiency and scalability in particular, but don't restrict yourself to these topics.

Send your code to jimmyd@cc.gatech.edu

jimmyd@cc.gatech.edu jimmyd@cc.gatech.edu)
Last modified: Mon Oct 11 15:11:45 EDT 1999