The purpose of this assignment is to introduce more aspects of the case-based reasoning paradigm. So far, you have dealt with three aspects:
This assignment shall introduce additional concepts in CBR:
These ideas are present in most CBR systems in some form.
Your task will be to extend the program from assignment 2 to include these new concepts. The finished program ought to be able to do:
You should write one high level function called
ms-go-from-to. (ms stands for multi-strategy.) This function
will take three arguments - a start intersection, a goal intersection and a
keyword argument. The keyword argument takes one of the following
values:
:learn
:test
The structure of cases must also be modified. They now must have at least three parts:
(start-intersection goal-intersection)
pair that is used for retrieving a case.
Utility, as presented in this assignment, is intended to be a measure of the usefulness of a case, a case being a particular route. We would like it to capture some intuition of how useful a street is in getting from one point on the map to another. The motivation behind including a utility value for the cases is to capture the situation where a person picks his or her favorite street or path as a means for exploring some new area. Imagine you have just moved to a new neighborhood. Initially, you know nothing about navigating its streets. You start building a case memory of places you have been to, and over time develop a preference for some street or route in the neighborhood. You tend to use this path as a reference for navigating through still unknown parts of the neighborhood. In time, your case memory becomes rich enough that the usefulness of this path dwindles. Can a simple utility score attached to the cases in memory capture this complex phenomenon?
The utility scores would find use in picking the best case in the retrieval process. Maintaining utility can be as complex as you choose to make it. The following is a simple example, the minimum we would expect in the program you write. When a new case is constructed, assign it a utility of 1. Each time the case is used, it's utility must be updated based on how well it performed. If a path could be constructed that did not involve very much adaptation and/or repair, increase the utility by, say, 10%. If on the other hand the case went through extensive repair, decrease the utility of the case by, say, 10%.
Another reason utility scores (or some other type of measure) is often attached to cases because of the so-called utility problem in case-based reasoning. The case base grows to the point where searching through and selecting a good case becomes extremely inefficient and tedious. This might occur in this path planning program as well. Consider the situation where you have travelled to almost every intersection on the map from 10th and Atlantic. Then, given a goal intersection starting from 10th and Atlantic, searching for the right case might take time comparable to doing a BFS. It is an empirical question whether the utility scores as used in this assignment can help with such a situation.
The task of retrieval is to locate the most appropriate case in memory. In the last program, the retrieval process involved picking the best case given some start intersection and some goal intersection. In addition, you will now have to consider how you ought to use the utility score in conjunction with the match quality to pick the best case to adapt. The task of the sub-modules thus becomes:
The planner currently goes through a relatively trivial process while deciding which strategy to use. In this assignment, you will decide on some criteria that will determine the strategy to use. You have two strategies available - search and case-based reasoning. The choice of which strategy to use ought to depend on the quality of the case retrieved. The selection of strategy itself ought to be encoded as a set of rules. The format of the rules would depend on the manner in which you choose to combine the result of the matcher with the case's utility. Some sample rules are given below, based on the combination technique introduced while discussing the selector in the retrieval module.
Adaptation in this assignment is identical to that in assignment 2. To reiterate, 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:
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.
You will have noticed that the cases built using the case-based strategy can be far from optimal. The task of detecting errors in the solution constructed is called evaluation, while repair is the process of correcting those errors. These tasks are sometimes independent, but in this problem you will find that the two are closely associated. Hence they have been included under a single module.
Evaluation consists of eliminating unnecessary steps in the solution produced. (This is also probably the best place to evaluate the performance of the case in the quality of the path it produced.) There are two types of optimization opportunities that must be tested:
Repair consists of eliminating the cycles and near cycles.
Storage must add the new path to the case-base, just as in the previous assignments. The minimal structure of a case has been described earlier.
This assignment requires significant changes to the existing program. Each of these changes can be done in a number of different ways. We also end up with a correspondingly large number of design decisions to make, each of which can be turned into an experiment. It is extremely easy to get overwhelmed by the number of choices available. Therefore, it will be necessary for you to select a small set of choices to concentrate your efforts on.
In other words, select a single topic as your focus. An example might be the task of efficiently managing the cases in case memory. (This is only an example. The assignment does not have that many choices to be made about the manner in which storage works.) Your experiments would then all be focused on design choices that effect storage. This will help you think about one aspect of this problem, and learn more about it.
There is a significant new constraint imposed on the representation used. Pay careful attention to it. There is also a significant amount of programming to do in this assignment. First complete the minimal requirements of the program, then begin experimenting.
Stage 1: Run the following tests on your program:
Stage 2: Select some aspect of the program to study, and design experiments that study the effects of various tradeoffs in the design on that aspect. Emphasize the aspect you have chosen in your writeup! Talk about why the aspect you have chosen is significant to the program, and discuss how the experiments relate to that aspect.