Lab 4: Implementing A*

In this lab you will implement the A* algorithm for the domain in labs 2 and 3.

You will work in pairs on this lab (with provision for sections with an odd number of students). You can start with the lab 3 solution written by either student. It is expected that you will talk through the development together.

Implementing A*

Modify your Lab 3 solution by adding two methods to Rat:

    astar_path_to(self, target_location: Room) -> List[Room]
    """Returns the list of rooms from the start location to the
    target location, using A* search to find the path."""

    astar_directions_to(self, target_location: Room) -> List[str]
    """Return the list of room names from the rat's current location to
    the target location. Uses A* search."""

    rooms_visited_by_last_search(self) -> List[str]
    """Return the list of rooms visited (in any order)"""

As before, talk to your instructor if you do not have a working solution to lab 3; we will be happy to help you debug your lab 3 solution to where it can serve as a start for lab 4.

We did have to make a few more changes to existing files. Download the new versions:

• dungeon.py: This has been modified to add additional methods to check the validity of a path and so that rooms have coordinates.
• test_lab4.py: a version of the tests from lab 3. This version supports A*. It also prints all rooms visited by the rat in alphabetical order (so the order they were visited does not matter).
• lab4_main.py: a revised version of lab2_main.py designed for submitting this lab.

Notes

• We acknowledge it would have been a good idea to use subclassing for the different Rat search algorithms. That will be an improvement we will make in future years.
• Start with your BFS solution since the A* implementation will be closest to that solution.
• The collection of candidates (the paths that are yet to be searched) is usually stored as a “priority queue”. This would improve the efficiency of finding the cheapest alternative to process next. However, we are not requiring you to use priority queues in this lab; you can use a standard Python array. Removing from the fringe means removing the lowest-total-cost (counting both the length of the path and the estimated cost to get to the goal) from your fringe.
• You must write auxiliary, protected (or private) methods to keep from having too much code in astar_path_to.
• Add all additional methods, including astar_path_to and astar_directions_to, to the end of class Rat.
• You will need three pieces of information for each candidate path: the path, the cost to traverse that path, and the estimated cost to get from the last room in the path to the target. Either store this information or ensure it can be recomputed cheaply.
• Compute the cost to get to a room as the number of hallways that the rat must walk through. Thus the starting point has cost 0, each of its neighbors a cost of 1, and so on.
• Estimate the cost to get to the target by calling estimated_cost_to in class Room. This computes what is known as the manhatten distance: the distance that would be covered while sticking to the streets when going between to locations. This has been implemented by adding a coordinate system to the dungeon.
• Important As discussed in class and the textbook, a full implementation of A* needs to consider the case in which a node/room has already been visited but must be revisited due to finding a shorter path. You are not required to implement this aspect of A* for this assignment. That is, the first time you visit a room you are guaranteed there is no shorter path to the same room. This is reasonable in a grid-based dungeon with no magical passages.
• There are multiple ways to track the cost and estimate to get to a given room. One is to store tuples on the candidate list: the candidate path, the cost to get to that room from the start, and the estimated cost to get to the target. An alternative is to use a dictionary (lookup table) that stores the number of moves required to get to each room. If you store them on the candidate list, you must introduce a class to capture this information. It will be a small class - just capturing the critical information and storing it on the list. Using tuples for this sort of information would lead to many programming errors.
• The test code has been modified to be more relaxed in its check for valid paths. A* is less deterministic than other algorithms, so alternative paths which are as short as the expected path are considered correct.
• The method rooms_visited_by_last_search is used by esubmit to display all of the rooms visited during the search. The various algorithms track this information in different ways; you can probably make the data private or protected and then return that data from this method. Ensure the list is reset on each new search. Warning: still use sets to keep track of which rooms have been visited; you can write rooms_visited_by_last_search to convert the set into a list.

Additional Notes

• As before, you can add additional protected or private methods and attributes.
• test_lab4.py contains test code used by esubmit to ensure your solution works. Run those on your own machine before trying to use esubmit.

Submission

As for lab 3, submit your solution using esubmit. You will submit at least two files, your revised version of rat.py and the unchanged version of lab4_main.py. The other two files, the updated dungeon.py and test_lab4.py, are already provided by esubmit. If you do try to submit those two files, your version will be ignored.

Only ONE partner needs to submit. If both do submit at some point - reasonable when doing final debugging! - be sure the final submission is marked "OFFICIAL SUBMISSION" (in the comment block of rat.py) for just one of the two (and maybe submit an "IGNORE ME" submission for the other partner).

Note: it is likely you will have differences in your output compared to our output on this lab. In particular, the paths you compute for tests 6 and 7 are likely to be different than the paths we compute. This is because the order you visit equal-value rooms is not determined, so your solution is likely to explore slightly different rooms than ours. You may also visit a few rooms extra on test_rat_5. If you have any question about any differences in your output, contact your instructor.