As mentioned in previous project descriptions, the four design projects in this class are based on an experimental navigation planning system called Router that was developed at Georgia Tech in the early 1990s and is presently embodied in a real robot called Stimpy. At the end of the four projects, each of you will have developed your own ``micro-Router'' system. In this, the fourth and final project, you will explore several issues related to failure-driven learning in the context of micro-Router that you have been developing in the first three projects.
The world, in general, is dynamic. Thus, even if a problem solver, such as micro-Router, begins with complete and correct knowledge of the world, after a while the problem solver's knowledge would no longer be complete and correct, and it will start producing plans that fail upon execution in the world. Hence, as the world evolves. the problem solver needs to adapt itself. The detection of a failure points to the need and provides the opportunity to learn so that the problem solver can avoid the same failure in the future.
Failures can be of many kinds. One important kind of failure is called expectation failure. Let us suppose that micro-Router's 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 contruction activity, for example).
Intersection A Intersection B
street X |--------|-----------~~~---------------|------------|
(East, West) Blocked
Given a navigation problem, micro-Router may (mistakenly) produce a plan which specifies travel on street X between A and B. Clearly, this plan would fail upon exection. This is an example of expectation failure. Note that this kind of expectation failure can occur whether micro-Router 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, micro-Router may have used a past plan that specified travel on street X between A and B.
The next question is how might micro-Router 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 micro-Router even if we had access to a robot), let us imagine an "oracle" that provides information about the failure. The oracle first supplies micro-Router 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 orcale 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 micro-Router with this kind of feedback.
Given feedback on the failure of a plan, (at least) two kinds of learning are possible. First, the model of the world can be revised to reflect that cause for the plan failure. For example, suppose micro-Router begins with the following representation for Atlantic Drive:
(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 travelling from
10th to Ferst-1. Micro-Router 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.
One of the many issues in learning is maintaining the consistency of knowledge. For example, suppose that a navigation plan fails because traversal on street X between intersections A and B is not allowed in the world. Suppose also that micro-Router revises its model to reflect this. But now the old plans in its plan memory that specify travel on street X between A and B are inconsistent with the revised model. One way of handling this issue of knowledge inconsistency is to revise all the knowledge in the planner. For example, micro-Router may revise not just the model but all old plans in the plan memory that specify travel on street X between A and B. But if the the number of plans in memory is large, this can be prohibitively expensive.
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 micro-Router 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) micro-Router 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.
For this assignment, you will be building off the work you did for assignment 2, rather than assignment 3. 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)))))
Your task is to write seven functions:
(plan-path src dest)
:choose
method, as defined in assignment 2. It should return a path that takes into account all
known failure points.
(execute-plan src path)
(plan-succeeded-p failures)
execute-plan, and decide if
the plan has succeeded.
(learn-from-failures failures)
execute-plan, and update the
map to include the new failure points.
(add-failure-point intersection1
intersection2)
execute-plan to test for.
(initialize-failures)
There is an important distinction between the world and the planner that must be realized in
the program. There is the set of failures out in the real world, and there is a set of failures
the planner knows about. Some of the functions listed operate on the knowledge of the planner,
while others operate on the state of the world. plan-path is contained entirely
within the planner, and must operate on the planner's model of the
world. execute-plan should model the world itself. plan-succeeded-p
is a knowledge agnostic module that resides in the planner. learn-from-failures
helps move observations about the world into the planner's internal knowledge
base. add-failure-point notes a new failure point in the world. This failure
should not appear in the planner's knowledge base until execute-plan uncovers the
failure in a future run. initialize-failures should reset all failures in the
planner's world model as well as in the world. In other words, it should reset the entire
system.
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
As you design, code and run your programs, think about the following questions:
In class, on paper:
Mail the code for your program to jimmyd@cc.gatech.edu. send it as plain text, not uuencoded. It can be in C or LISP. If you do it in C, note that I will compile and run it on the CoC machine Boise. Make sure it runs there for the least hassle. It's okay to paste it into the body of the message. But MAKE SURE YOUR LINES DON'T WRAP. Keep them short.