CMSC 671
Artificial Intelligence -- Fall 2001
HOMEWORK THREE
out 9/25/01 due 10/11/01
http://www.cs.umbc.edu/671/fall01/hw/hw3.html
PART I. Implementing search (100 pts.)
In this assignment, you will implement and compare several search techniques.
Reminders:
-
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.
-
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.)
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 take as arguments the names of a city on the map and searches 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
-
A list of the cities visited in the search tree
-
The path between the two cities
-
The cost of the path found
Use the Lisp function values to return these four values. h(n),
the heuristic function for A* search, 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 from homework
#2. 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.)
In the case where a search method fails to find a path, indicate the lack
of result with "--" in the corresponding table entry.
| City name |
#nodes / BFS |
# nodes / greedy |
# nodes / A* |
Path / BFS |
Path / greedy |
Path / A* |
Path cost / BFS |
Path cost / greedy |
Path cost / A* |
| Arad |
|
|
|
|
|
|
|
|
|
| Bucharest |
|
|
|
|
|
|
|
|
|
| ... |
|
|
|
|
|
|
|
|
|
| Vaslui |
|
|
|
|
|
|
|
|
|
| Zerind |
|
|
|
|
|
|
|
|
|
Implementation Suggestions
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.