CS 3361: Introduction to Artificial Intelligence
Winter 1998

In this assignment, you will be writing a program in Lisp that first plans routes to go from one location on the Georgia Tech Campus to another, and then stores the planned routes in a plan (or case) memory. A program in Lisp is a collection of Lisp functions some of which may call others (including themselves). You will write a set of such functions that together implement a case-based strategy for route planning. Combined with functions from your first assignment you will have a multi-strategy route planning program. Remember, it is a good programming practice to write many small functions that are reusable in other situations as well. You should not write one big function that does everything.

In this assignment you will make use of the stored routes (i.e. cases) that you created in the first assignment. You will implement a case-based reasoning strategy to create new plans. This new planner is called a case-based planner. In combination with your first assignment you will have developed a multi-strategy planner.

Overall Task

You should write one high level function called ms-go-from-to. (ms stands for multi-strategy.) This function will take two arguments - a goal destination (which is the same as the go-from-to function from the first assignment), and the strategy the program should use to generate a path plan. The second argument in other words ought to take one of three keyword values:

:case-based

This keyword should cause the case-based mechanism to be used.

:search

This keyword results in a plan generated using search.

:choose

Using this keyword should allow the program to choose the best strategy available. Keep the strategy simple for now - try the case-based mechanism, and if that fails try the search mechanism. (Hint: Write a second function to do the selection task. Although the selection problem is trivial now, expect it to become more significant later in the quarter.)

The Case-Based Strategy

The case-based strategy will have 3 modules:

1. Storage
2. Retrieval
3. Adaptation

Storage

If you completed the first assignment you have already done most of this. In this module you must store the results of ms-go-from-to in some long term memory construct. Each case must have two parts:

1. An index
2. A route

The index should have the initial intersection and the final intersection. It is best if this index is stored as a single unit.
e.g. ((street1 street2) (street3 street4)).

Retrieval

The retrieval module accesses memory to retrieve stored cases. In this module you should have three sub-modules:

Retriever

The retriever will take a memory probe. A memory probe is simply the information needed to retrieve a case. For our purposes:
memory-probe = an initial-state/goal-state pair
The retriever must search through the memory and apply the matcher to see if that probe matches the indexes. It should collect all of these matches and send them to the selector.

Selector

The selector will then pick one of those retrieved cases and return it. This can be as simple as taking the first case or if you choose you can order the cases based on which one is "best".

Matcher

The matcher must determine if a probe matches an index. The matcher should be able to find not only exact matches, but also partial matches. Examples:

Matching initial states:

((street1 street2) (street3 street4)) almost matches
((street1 street2) (street3 street6))

Matching goal states:

((street1 street2) (street3 street4)) almost matches
((street5 street6) (street3 street4))

Matching partial intersections:

((street1 street2) (street3 street4)) almost matches
((street1 street3) (street3 street6))

For this case there are a number of possibilities. You may want to require that 2 out of 4 streets match.

Adaptation

Once you have retrieved and selected a case, the next step is to adapt that case to fit your current problem. The adaptation module should take the retrieved case and adapt it to solve the problem. In this assignment:

• Problem = Find a route from an initial intersection to a goal intersection.
• Problem Specification = initial-intersection/goal-intersection pair

Assuming that the retrieval module has found a case that gives a partial solution to the problem, the adaptation module must complete the solution for the problem. Note that a part of a problem can itself be looked upon as an independent problem.

Some sample test cases

You should test your program with the following: