CMSC 471

Artificial Intelligence

due 10/1/2007

Implementing search (100 pts.)

In this assignment, you will implement and compare several search techniques.





Write and compare three search methods: breadth-first search with checking for repeated states, greedy search, and A* search. You should write three functions, BF-search, greedy-search, and A*-search, that each take a single argument--the name of a city on the map--and search for the shortest path to Bucharest. (More generally, one could write a function that took two cities and searched for a path from one to the other, but then you would need straight-line distances between every pair of cities.)  The search functions should return the following values:
  1. The number of nodes expanded
  2. The cost of the path found
  3. The path from the start to the goal as a list of city names.

Use the Lisp function values to return these values.

The heuristic function h(n) that is used by the A* and greedy search algorithms (i.e., the estimate of the distance to the goal) should be the straight-line distance to Bucharest.


Results to Report

You should turn in your code using the submit facility. Please create a single file containing all of the code, including the code provided by the instructor with this assignment. Name this file <Lastname><Firstname>HW2.lisp. For example, I would turn in a file named EatonEricHW2.lisp.

You should submit your code to cs471 hw2. For details on using the submit utility, see The hw2 project will expire at exactly 1:00pm on the due date (the same time class starts). After that time, your submission is considered late (regardless of whether you submit code identical to the hardcopy printout you turn-in in-class), and you must submit it to hw2-late instead. For example, I would type submit cs471 hw2 EatonEricHW2.lisp to turn in my homework. I highly suggest that you submit your code file often, both to test that the submission procedure works and to keep a backup copy of your progress.

In addition, you should turn in, in hardcopy, both a printout of your code (formatted as neatly as possible) and the results table of the three search functions applied to each city in Romania (as the first argument) for a path to Bucharest (the goal city), using the following table format as a guideline.

You should also write a brief summary of your findings, comparing the performance of the algorithms, and discussing particular cases where one of the algorithms performs better than the others. (This summary can be anywhere from a few short paragraphs to one or two pages.) This should be a well-written analysis of your results in the form of a mini-report.

You must write a Lisp function called hw2 that loads all appropriate files, initializes all data structures, runs the appropriate searches, collects the results and prints them out in a table like this. If it's easier, you can provide the same information in a different format, as long as it's clearly readable, all of the data shown below is given, and you show the results for the 20 cities in alphabetical order. A (very) incomplete version of the hw2 function is included with the utilities described below. Hint: the bulk of this function will likely be a loop that runs all of the algorithms on all of the cities and gathers the results in some central place, then outputs the tabular data.

In the case where a search method fails to find a path, you should indicate the lack of a result (e.g., with "--" , NIL, or "FAILURE") in the corresponding table entry.
City name #nodes / BFS # nodes / greedy # nodes / A* Path cost / BFS Path cost / greedy Path cost / A*


Provided Map Utilities

In an effort to help you get started, I have written the following utilities which you will find useful in implementing this homework. The utilities are available in hw2-utilities.lisp. These utilities implement data structures and functions to represent and manipulate a map. You may choose to modify this provided code however you wish. You will also likely find that you need to write several utility functions of your own as you complete this assignment. Here is a description of the provided utilities:
  1. A city data structure, created using defstruct, with the following attributes:
    1. The name of the city (represented as a symbol)
    2. The neighbors of the city (represented as an association list of neighbor / distance dotted pairs)
    3. The straight-line distance from this city to the goal city.
  2. A global variable, *all-cities*, that contains a hash table that will store the cities. Initially, the hash table is empty.
  3. Functions read-cities and read-neighbors that will read the cities, neighbors, and distances from two files I've provided for the map of Romania (the example used beginning page 95 of the textbook):
  4. The following map manipulation functions:
  5. Here is a brief example of using the data structures. I recommend everyone try this example out! Here's what you should type into lisp after you start it from the shell.
    1. (load "hw2-utilities.lisp")
    2. (read-cities "cities.txt")
    3. (all-cities)
    4. (read-neighbors "neighbors.txt")
    5. (city-neighbor-list 'oradea)
    6. (closest-neighbor 'sibiu)
    7. (get-city-struct 'pitesti)
    8. (neighbors-within-distance 'rimnicu_vilcea 90)

The neighbors-within-distance function is incomplete. I provided the function with most of my comments, but without the code. You must fill in the code for this function as part of this homework assignment. It will give you practice using the map data structures before you launch into implementing the search algorithms. When doing your implementation, look at the other provided utility functions for inspiration.

The first thing you should do in completing this assignment is read the provided code in detail to understand it. Read it slowly, look up the usage of every lisp command you don't understand immediately, and then read it through several more times. If anyone still needs help understanding it, please see me in person. However, if you want me to help you understand it, you must first make a real effort to try to understand it yourself.


Implementation Suggestions

Before reading these suggestions, it would be a good idea to design your own approach.  However, here are some suggestions for how to go about implementing the search methods in an efficient and reasonably elegant way. (You are not required to follow these suggestions.)

This assignments was adapted by Eric Eaton from a set of two assignments by Tim Finin and Marie desJardins.