This projects deals with an adaptive planner for navigating the Georgia Tech campus. You need to implement your design in a computer program (see the discussion of programming languages and environments), experiment with the program, and write a critique of your system design. A second part asks you to plan around failure and change your knowledge of the world accordingly.
Let us suppose that an intelligent agent is given a map of the Georgia Tech campus (even if the map is only rough and approximate). For simplicity, let us assume that the map is in the form of a rectangular grid, i.e., all roads are either North and South, or West and East. Let us also assume that curved roads (such Ferst) are divided into linear segments (such as Ferst-1, Ferst-2 ...) that lie along the North-South and West-East axes. In addition, let us assume that all roads allow bi-directional flow of traffic.
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
One way of representing of the map is to have a list in which each element is the representation for one street. One such element could including the following information:
In this project, you may assume that the names of the streets with which a given street intersects are listed in order from North to South or East to West. For example, the representation for Atlantic Drive may look like:
(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.)
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. 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))
You may add other bootstrap plans but you may not add additional bootstrap plans that intefere with the test cases
listed at the bottom of the assignment. You will lose credit for doing so.
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.
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.
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.
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
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) 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
The world, in general, is dynamic. Thus, even if a planner begins with complete and correct knowledge of the world, after a while the planner'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 planner needs to adapt itself. The detection of a failure points to the need and provides the opportunity to learn so that the planner 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 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.
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 planner 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
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.
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 planner 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, planner 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 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.
Important Note: The details provided in this section assume that you are using Common LISP. If you decide to use a different language, you are welcome to translate the code below into that language and to change the details of how your system interacts with the user to a form which is more appropriate to the language you have chosen.
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)))))
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 srcdest):choose method, as defined in the original planner.
It should return a path that takes into account all known failure
points. (execute-plan srcpath)(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:
For this project we are providing lists of explicitly approved servers, languages, and compilers. You can develop your systems in any environment that you like, but it is strongly recommended that you thoroughly test your system under an approved compiler before you turn it in and that you explicitly document what server you tested on and exactly what you typed to do this testing. Programs which prove difficult to compile or run will receive substantially reduced credit, if any. If you have an extremely compelling reason why you want to use a different language or platform, send email to the TA and it will be considered on a case-by-case basis. The following Georgia Tech servers are explicitly approved for use on this project:
/usr/local/bin/gcc [C/C++ - gcc version egcs-2.91.66]
/usr/local/bin/g++ [C/C++ - gcc version egcs-2.91.66]
/opt/SUNWspro/bin/cc [C - WorkShop Compilers 4.2]
/usr/ucb/cc [C - Solaris Berkeley-compatibility]
/bin/javac [Java 1.1.8]
/usr/local/jdk1.2/bin/javac [Java 1.2]
/usr/local/jdk1.3/bin/javac [Java 1.3]
/usr/local/bin/lispworks [Common LISP - Lispworks 3.2.2]
/usr/local/bin/lispworks-4.1 [Common LISP - Lispworks 4.1]
/usr/local/bin/scheme [Scheme - MIT Scheme 7.3.0]
Makefiles are strongly encouraged (as needed). Whether or not you use a Makefile, you must completely and precisely specify exactly how to compile and run your program.
On paper in class (IMPORTANT NOTE: This must be physically turned in on paper. We will not print it out for you and if you only submit electronic copies, you will receive no credit for this portions of the assignment. We are not bluffing this time.):
For your basic planning program (Part 1 of the
assignment):
((10th atlantic) (north-avenue williams))((10th atlantic) (5th techwood))((5th fowler-1) (north-avenue cherry))((ferst-1 state) (4th atlantic))((5th techwood) (north-avenue tech-parkway))((6th-1 mcmillan) (8th-1 hemphill))By email to megak@cc.gatech.edu :
Marty Geier (megak@cc.gatech.edu)
Originally created by Bill Murdock