CPSC 415 - Artificial Intelligence - Fall 2023

Program #2 — Search algorithms

Possible experience: +40XP or +50XP or even +60XP

Due: Monday, Sep. 25th, midnight (see also bonus point deadline)

Overview

In this programming assignment, you will be implementing search algorithms on a synthetic road atlas to find routes from a source to a destination. You may implement the greedy search algorithm for +40XP, Dijkstra's algorithm for +50XP, or both of these plus the A* search algorithm for +60XP. Your algorithm will be equipped with an admissible heuristic function.

The Atlas class

I have provided a Python class called Atlas to represent the map you're traversing. It's in the file atlas.py in the class's github repo.

You can instantiate an Atlas in two ways:

1. Via the constructor, to generate a random map. Give it the number of cities as an argument (10 is the default):

   tiny = Atlas()
   europe = Atlas(615)
   

2. From a file. This is useful so you can verify whether your algorithms are working properly: I'll be able to provide test atlases (see "Verifying your solution is correct," below) with their solutions, and you can check your program. Call the from_filename() class method to do this:

   arrakis = Atlas.from_filename('arrakis.atlas')
   

There are two important Atlas methods:

• get_road_dist(i,j). This method takes two arguments, which are city numbers. These numbers must be integers in the range [0,num_cities-1]. This method returns the actual road distance between the two cities, if such a road exists. If there is no road between the two cities (which happens, a lot), the method will return math.inf (infinity).
• get_crow_flies_dist(i,j). This is the heuristic function. It takes the same two arguments as above, and returns the straight-line distance between the two cities. Note that unlike get_road_dist(), this will always return a finite number, since it has nothing to do with roads, present or not. Importantly, this method is guaranteed always to return a lower number than get_road_dist() does for the same two cities. Recall that if this were not true, the heuristic wouldn't be admissible, and you couldn't use it for A* search and guarantee optimality.

Important: you are "charged" for each time you call get_road_dist() in the sense that the Atlas object keeps track of how many nodes you've expanded. This is how it "keeps score" and determines how efficient your algorithm is exploring the map. There is no charge for get_crow_flies_dist(), however; call it as many times as you like.

For what it's worth, both of the above methods are symmetric (i.e., ∀_i,j get_road_dist(i,j) = get_road_dist(j,i), and similarly for get_crow_flies_dist()) although you shouldn't make any assumptions based on this. For all you know, there could be one-way streets and warped non-Euclidean realities.

Your mission

Your job is to write a Python function called find_path(). Its first line should look like this:

def find_path(atlas, alg):

The two arguments are an atlas object (instantiated in either of the above ways) and a string with one of the values greedy, Dijkstras, or astar. The function's job is to find a path (a sequence of visited cities) between city number 0 and city number atlas.num_cities-1 using that algorithm.

Your function should return a tuple of two elements: the first of which is a list of city (node) numbers, and the second of which is the (true, not estimated) total distance of that path.

For example, suppose a 5-city Atlas is passed to your function which has the following distances between cities:

The shortest path from city 0 to 4 (which you should verify) is 0→3→2→4, which has a cost of 970. Therefore, your Dijkstra's and A* functions should return this tuple:

([0,3,2,4], 970)

(Stare at that answer until you're sure you get it.)

Note that your greedy algorithm may or may not return that path — that will depend on the values the heuristic function gives for each city. It may well return a worse path. However, the path it does return as the first entry in the tuple had better have the total distance that is reflected in the second entry in the tuple.

Getting started

Refresh your repo with the latest contents by doing a git pull operation. (Make sure all your own stuff is committed first!) Then, use the file gps.py as a starting point. Change the comments at the top of your gps.py to include your own name instead of mine. Then, make sure that when you run gps.py like this:

$ python3 gps.py 5 Dijkstras

you get output that looks like this:

INFO:root:Building random atlas with 5 cities...
INFO:root:...built.
Best path from 0 to 4 costs 970: [0, 3, 2, 4].
You expanded 0 nodes: set()

When you get this result, commit the gps.py file to your repo. You are now ready to begin implementing the find_path() function in that file.

$ python3 gps.py ten.atlas Dijkstras

$ git bundle create yourUmwUsername.git --all