CPSC 415 - Artificial Intelligence - Fall 2023

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

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

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.

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:

- 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)

- 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*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.`get_road_dist()`does for the same two cities.

**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

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

0 | ∞ | 983 | 154 | ∞ |

∞ | 0 | 554 | ∞ | ∞ |

983 | 554 | 0 | 458 | 358 |

154 | ∞ | 458 | 0 | ∞ |

∞ | ∞ | 358 | ∞ | 0 |

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.

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.

Here are some sample atlas files, in order to verify that your A* solution is finding the optimal path (and optimally):

File | # cities | Optimal path | Greedy path | Optimal length | Greedy length | #
nodes (Dijkstra) | #
nodes (A*) |
# nodes (greedy) |
---|---|---|---|---|---|---|---|---|

ten.atlas | 10 | 0→3→8→9 | 0→3→8→9 | 2425.4 | 2425.4 | 5 | 4 | 4 |

fifty.atlas | 50 | 0→29→22→43→49 | 0→29→22→43→49 | 1269.6 | 1269.6 | 43 | 6 | 4 |

hundred.atlas | 100 | 0→98→7→99 | 0→89→63→99 | 1087.8 | 1224.8 | 82 | 6 | 8 |

thousand.atlas | 1000 | 0→19→615→664→122→999 | 0→842→771→477→701→190→53→999 | 651.2 | 1081.8 | 392 | 23 | 9 |

twothousand.atlas | 2000 | 0→369→1877→1999 | 0→22→1999 | 230.0 | 236.6 | 244 | 3 | 2 |

To try these files, run your program with the atlas filename instead of the number of nodes, like this:

$ python3 gps.py ten.atlas Dijkstras

Carefully note that **in order to get credit for either solution, the
number of nodes you expand must not exceed the number listed in the table,
above.** If you were to exceed that number, that would indicate your
algorithm is not working optimally, and will (probably) take forever to
complete on any sizeable graph.

My test script will assume that you have implemented all three algorithms.
If you do not, please return the string "`Unimplemented`" from your
function if it is called with an `alg` value you did not code.

You will turn this assignment in by attaching a git bundle to an email. (A
"git bundle" is essentially a portable, zipped-up git repo.) The subject line
of the email should be "**CPSC 415 Program #2 turnin**".

To do this, **first make sure that all your code is checked into git.**
Running "`git status`" and ensuring your workspace is clean is a great
way to do that. Then, bundle up your git repo:

$ git bundle create yourUmwUsername.git --all

and send me the `yourUmwUsername.git` file as an email attachment.
(Please do not name it *literally* "`yourUmwUsername.git`"
Substitute your actual UMW username. For instance,
"`jsmith3.git`".)

- +1XP if your repo has your initial commit of
`gps.py`(with the comment changed) on or before**September 18th** - +1XP if your repo has at least one
non-trivial commit on or before
**September 19th** - +1XP if your repo has non-trivial commits on
**at least four (4) different dates**

Note: the definition of "non-trivial" is "whatever Stephen deems is non-trivial."

Come to office hours, or send me email with subject line "**CPSC 415
Program #2 help!!**"