Project 1

Heuristic Search for Route Finding
Assigned: August 23, 2004
Due: September 13, 2004 (2:00pm in class)

Introduction

This projects deals with an intelligent agent that can plan routes for navigating the Georgia Tech campus by car. You need to design the agent and implement your design in a computer program, experiment with the program, and write a critique of your agent design.  

The Problem

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). The map shows all the main roads on the campus as well as the (approximate) distances between any two intersections.

Knowledge Representation

There are several issues that your agent design will need to address. For example, how might the agent represent the roads and their directions, intersections between roads and distances between intersections? One way of addressing some of these issues is to assume that the superpose a a rectangular grid on the map and to use a four-directional qualitative compass so that all roads are in the North, East, South, or West directions. For simplicity, you may also assume that all roads allow bi-directional flow of traffic.

This however raises another issue: how to represent curved roads? One solution is to decompose a curved road (such as Ferst) into linear segments (such as Ferst-1, Ferst-2 ...) that lie along the axes of the fourth-directional qualitative compass.

Route Finding

Given the above knowledge representation, the next issue is how may the agent find a route from a give initial state to a given goal state? Your task is to use the Greedy and the A* search techniques discussed in class for route finding. Note that different methods offer different trade-offs between computational efficiency (time and space) and solution quality (goodness of the planned route).

Input-Output

Your agent should take as input the specification of an initial state and a goal state. The states in the problem are intersections between roads. For this project, program input will be of the form 

     ((10th atlantic) (north-avenue techwood))

where the initial state is the intersection between 10th and Atlantic, and the final state is the intersection between North-avenue and Techwood.

The route finder should output a route from the initial state to the goal state. If more than one path is possible, then it should try to return a good path, where the goodness of a path is characterized by its closeness to an optimal path.

Deliverables

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. ):

  1. The output of your program given the following inputs
    1. ((10th atlantic) (north-avenue williams))
    2. ((10th atlantic) (5th techwood))
    3. ((5th fowler-1) (north-avenue cherry))
    4. ((ferst-1 state) (4th atlantic))
    5. ((5th techwood) (north-avenue tech-parkway))
    6. ((6th-1 mcmillan) (8th-1 hemphill))
  2. A critique of your agent design including
  3. Experimental data to back up your findings, presented appropriately
  • Your source code emailed to Joshua Jones
    • You should feel free to use any language you like to implement the project. If you plan to use anything other than a very common language (LISP, C/C++, Java...), please check with the TA first. It is required that the code run on one of the CoC systems, such as gaia or helsinki, as this is where the code will be tested. Also, your program must accept input in the standard format. For some languages, this may mean that you need to write a little bit of parsing code, but this should not be very difficult.

    Grading Criteria

    Functionality

  • 25%: Greedy Search
  • 25%: A*
  • 25%: Experiment design, throroughness of comparison

    Writeup

  • 15%: Critique

    Style

  • 5%: Readable output
  • 5%: Readable code style, documentation.