Overview

Route planning is an intuitive task, one that applies equally to humans or robots, pedestrians and drivers. We all generate route plans on a regular basis. Online systems like Google Maps or Rand McNally Online automate the task of finding a route for driving from place to place. Route planning is an easy domain to explore brute-force and heuristic state-space search algorithms, but such algorithms may not scale up to large map domains. The time required to generate a route plan from scratch may be prohibitive. A route planner using case-based reasoning (CBR) stores many routes in its case memory, and generates new routes by adapting routes it already knows. It learns by storing the newly generated routes in its case memory. In this project students will explore search-based route planning, then augment the planner with a case-based learner whose goal is to avoid generating routes from scratch whenever possible. They will test out different methods for storing routes in the case memory, for determining similarity between route problems, and for adapting old routes to new problems efficiently. They will compare the time required for search-based planning versus case-based planning.

The central goal of this project is to examine the trade-offs between different approaches to the same problem and, in the process, to understand how both state-space search and case-based reasoning work. In particular, the students will:
  • Learn the case-based reasoning process, and how to apply it to route planning.
  • Learn basic brute-force search algorithms, like Best-First and A*, and experiment with heuristics to understand their role in improving efficiency.
  • Experience the problems of algorithm complexity with state-space search on a real-world problem.
  • Experiment with alternative methods for handling the "hard" parts of CBR: similarity assessment and quality adaptation.
  • Perform comparative analyses of alternate approaches to route planning, evaluating the trade-offs and ultimate outcomes.
Students should have experience with programming, and should understand informal analyses of algorithm complexity: CS2 should suffice, or even CS1 if it included any discussion of algorithm analysis. Experience with object-oriented programming would be helpful, but not required. Programming may take place in Java, C++ or Python.
For an understanding of state-space search, the relevant chapters of any AI textbook would suffice. For instance, chapters 3 and 4 of Artificial Intelligence; A Modern Approach, 2nd edition, by Stuart Russell and Peter Norvig, 2003. An examination of Dijkstra's Algorithm could be included, many CS2 books or an Algorithm Analysis text would be fine. For background on case-based reasoning, a source focused on CBR may be needed. A good choice are chapters 1 and 2 of Case-Based Reasoning: Experiences, Lessons, & Future Directions, edited by David B. Leake, 1996. There are many relevant articles in the research literature, a few are listed below:
  • Stuart Russell and Peter Norvig. Artificial Intelligence: a modern approach, 2nd ed. Prentice Hall, Upper Saddle River, NJ, USA, 2003.
  • Leake, ed. Case-Based Reasoning: Experiences, Lessons, & Future Directions. AAAI Press/MIT Press, 1996.
  • McGinty and Smyth. Collaborative Case-Based Reasoning: Applications in Personalised Route Planning, in Case-Based Reasoning Research and Development: 4th International Conference on Case-Based Reasoning, Proceedings of ICCBR 2001, Vancouver, BC, Canada, July 30 - August 2, 2001. Published in the Lecture Notes in Computer Science series, Springer, 2001.
  • Kruusmaa and Willemson. Covering the Path Space: A Casebase Analysis for Mobile Robot Path Planning, in Knowledge-Based systems, Volume 16, Issues 5-6, July 2003, pages 235-242.
Offshoots from this project could move toward more complex planning methods, learning good heuristics for search-based algorithms, route plans for robotics, or human-computer interaction/natural language processing issues related to how a route is presented to a human user.
The detailed project description is available in the PDF file CBRRoutes.pdf. You will need the free Adobe Acrobat Reader to view this file.
Background material on basic graph search may be found in graphbasics.pdf.

Project assignments are given in: Supporting files include:
  • ProjPhase1Files.zip, containing code relevant to the A* part of the assignment.
  • ProjPhase2Files.zip, containing all relevant code for CBR and A* parts.
  • Maps.zip, containing some sample maps, relating to the provided code.
  • Images.zip, containing all the images from the PDF documents.
Supporting code in Java will be added in the future.

This project may be adapted by providing more or less of the code for the described project. Faculty wanting additional code should contact Susan Fox personally. This project is very open-ended, leading ultimately to open research questions involving representing, retrieving, and adapting route information.
This is a 2-week module, but could be spread to take three weeks, if desired.

Week One: Route-Finding with A*
Reading: Sections 4.1-4.2 from Russell and Norvig
Project: Phase 1: Implement and test A* with provided map code
Day 1: Route-finding as a graph search
Day 2: A* search
Day 3: Finish A* and discuss pros and cons

Week Two: Route-Finding with Case-Based Reasoning
Reading: Chapter 2 from Leake, Kruusmaa and Willemson, McGinty and Smyth
Project: Phase 2: Implement a case-based route planner, using nearest-neighbor similarity and simple adaptation strategies
Day 4: Introduce CBR and discuss applications to route generation
Day 5: Discuss case segmentation and similarity assessment
Day 6: Discuss route plan adaptation strategies

Week Three: Analysis
Day 7: Class discussion on the pros and cons of each approach, and when one might choose one over the other