CMSC 471

PART I. Implementing search (100 pts.)

Artificial Intelligence -- Fall 2002

HOMEWORK THREE
out 9/25/01 due 10/11/01

Reminders:

Assignment

Results to Report

Implementation Suggestions

http://www.cs.umbc.edu/courses/undergraduate/471/fall02/hw/hw3.html

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

Do your own work! Any code you turn in should be your own.
Indicate whether you worked with anyone else or received any help on the concepts in this homework. (As the grading policy states, you may discuss the assignment with other students, but must indicate this in your homework, and must write your own code yourself.)
Don't forget to do error checking and to document your code.
Use the function names indicated here, so that we can test your code online.
Be sure your code works in CLISP, even if you use another Lisp environment for development.
Be sure that your code for homework #2 works before you start this assignment. If you couldn't get your code to work, you can borrow from the solution handed out in class. (If you do borrow this code, I strongly suggest spending some time making sure you understand it thoroughly before you start extending it for this homework assignment.)

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 four values:

The number of nodes expanded
The cost of the path found

Use the Lisp function values to return these four values. h(n), the heuristic function 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.

You should turn in your code using the submit facility. Please create a single file containing all of the code, including the code from homework #2 (whether you reuse your own code or use the code provided as a solution). Name this file hw3-NAME.lisp, where NAME is your first name.

In addition, you should turn in, in hardcopy, both a printout of your code and the results of the three search functions applied to each city in Romania (as the first argument) and Bucharest (as the second argument), using the following table format as a guideline. (You can write a Lisp function to collect these results and print out a table like this, or you can run the functions for each city and then create the table manually. 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. Hint: you will probably want to write a testing 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*

Arad

Bucharest

...

Vaslui

Zerind

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 paragraph to a page or two.)

City name

#nodes / BFS

# nodes / greedy

# nodes / A*

Path cost / BFS

Path cost / greedy

Path cost / A*

Before reading these suggestions, it would be a good idea to design your own approach. However, if you get stuck or want a "reality check," 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.)

Modify the city data structure from Homework #2 to add a new field, visited, for marking which cities have already been visited in the search.
Create a new data structure to represent a node in the search tree. This structure should have attributes pointing to the structures of the node's parent (empty for the root), the children of the node, and the city it represents. You may also want to include other attributes for bookkeeping purposes, such as the path so far, and the path cost.
Implement the generic search strategy presented in the textbook that was reviewed in class. This function should take (at least) a city name and a queuing function as arguments. You may want to implement it to take other arguments as well (for example, the map and the expansion function). Your specialized search methods should invoke this generic search function with the appropriate arguments.
Implement the function expand-node, which takes a node in the search tree and generates its children. Think about whether you want to use the same expand-node function for all three search strategies, or implement two or three different versions.
Implement three queueing functions, one for breadth-first search, one for greedy search, and one for A* search. This function should take the current node list and the list of nodes generated by expand-node, and return an updated node list. Note that these queueing functions need to check for duplication of states.