University of Chicago: Computer Science: CMSC 25000: Winter 2007: Homework #2

CMSC 25000 - Artificial Intelligence
Winter 2007
Homework #2: Due January 18, 2007

Goals

Through this assignment you will:

Implement search procedures.
Understand the close interrelationships between different search procedures.
Explore additional applications of search.

Background

Files for this homework assignment can be found here

When trying to find cheap airfares, one often encounters itineraries and routes that are convoluted to say the least. Here we exploring routing through a hypothetical airline's system to locations that may be off the beaten path. Any resemblance these routes bear to itineraries suggested by on-line travel planners is purely coincidental.

The bulk of the code for this problem set can be loaded by route-finding.scm. The large data file is in airroutes_long.scm and a smaller example is in airroutes_short.scm.

The main search function is (general-search search-problem queuing-function). This function returns a node in the goal state, if one exists, that represents a single successful path from the start to the goal. It prints out the successors as nodes are expanded.

The function (solution-nodes node '()) will return the list of airports from start to goal in the path, when node is output of the general-search function. Please use this function to display the route found to your solution node.

search-problem is a scheme structure that is defined by
- start and goal are the starting and ending nodes of the search.
- map is a list of lists, each of which includes a location name, location coordinates in list form, and a list of dotted pairs consisting of locations reachable by direct flight and their distance.
queuing-fn is a function that determines how new paths are added to the queue. As you should recall from lecture, this component has a great deal of impact on what type of search is implemented.

The variables big-airport-map and little-airport-map are bound to a lists of airports. The Romanian road map example from the text is stored as *romanian-map*.

Problem 1

Since we are searching a graph rather than a tree, there are some additional details that must be handled. To explore one of these difficulties try the following simple search: (depth-first-search 'newark 'san-francisco big-airport-map).

What problem you observe?

Fix the problem in expand and hand in your code and the output of a run on the above example to demonstrate that it works.

Problem 2

In class we discussed the relationship between depth-first and breadth-first search. We also know how irritating it is to have a large number of connecting flights, and would like to find the route with the fewest hops.

Implement a function breadth-first. Debug using the small test data set.

When your code is operational, load the big-airport-map and run (breadth-first 'newark 'san-francisco big-airport-map). Hand in your function code, and the verbose output from the run.

Problem 3

Just finding a route is useful, but we'd really prefer to find the SHORTEST route efficiently.

Implement a version of a-star search. Run your version of a-star on the above example. Consider using a hash table to implement dynamic programming.

You will probably need to modify some of the data abstractions since we are now concerned with path costs as well. We have included a function straight-line-distance to aid in your search.