Homework 2: The Rush Hour Problem (60 Points)

Chris Tralie

Click here to see the competition results

Learning Objectives

  • Translate algorithm specifications into code
  • Implement tree and graph versions of classical search algorithms on an abstract search space using object oriented paradigms in Python

Background

This assignment was inspired heavily by an assignment I did 11 years ago when I first took AI. You will use classical search techniques to solve the rush hour problem. This is a game where you have to move rectangular "cars" on a grid out of the way to make room for a red car to reach an exit. Below is an interactive example, courtesy of Valerie Lu.

To translate this into a problem that a computer can understand, we'll use the classical search framework. In this case, our model is as follows:

  • A state is a fixed configuration of cars on the board
  • A goal state is a state in which the red car overlaps with the exit (Note that there may be multiple valid goal states)
  • A neighboring state is a state that we can reach by moving one of the cars by a single step without hitting any other cars.

Like all search problems in this framework, we can think of this like a graph. Below is an interactive example where each state is shown as a node and neighboring states are connected by an edge. We simply have to find a path from the starting state to a goal state.

Starter Code

Click here to download the starter code that you will fill in for this assignment. This code has just enough for you to represent the state of a puzzle board and to load in puzzles, but you'll have to build the core functionality for searching from scratch.

Here's what you need to know about the code

  • An object of type Car holds 4 pieces of information: the row that the car starts on (i), the column that the car starts on (j), the length of the car L, and whether the car is oriented horizontally (horiz). If it is not oriented horizontally, then it is oriented vertically. For example, if we had the car i = 1, j = 2, L = 3, horiz=False on a 6x6 grid, it would be at this location

    If instead we had i = 4, j = 1, L = 4, horiz=True, the car would be at this location

  • The State class encapsulates all information that's needed to fully specify a configuration of the board, including the following 4 pieces of information:
    • A variable N which indicates the size of the grid (e.g. N = 6 is a 6x6 grid).
    • A goal location goal, which is a 2-element list [i, j] indicating the row and column, respectively, of the location on the grid the red car has to touch to have reached the goal.
    • A list of Car objects called cars which stores all of the cars currently on the board. The first car in the list will always be the red car that needs to get to the exit
    • A variable prev which you can use later in BFS tree search, BFS graph search, and A* search to keep track of which states came before this state.

  • A helper method called get_state_grid has been provided that returns a 2D array indicating which cells of the grid are occupied. A cell i, j has the number k if the car at index k in the cars list overlaps with that cell, or -1 otherwise. For example, below is its puzzle with this 2D array superimposed

  • A helper method called get_state_hashable has been provided which returns the grid as a string which uniquely identifies the board, and which will be useful later in the BFS graph search and A* search tasks to see if a state has already been visited

Jupyter

It is probably easiest to test this in Jupyter. You can setup Jupyter to automatically reload any modules that you import. If you create your Jupyter notebook in the same folder as rush.py, then here's some code that will load Valerie Lu's "hard puzzle"

As you can see in this example, it's possible to plot the states that you're working with to help you debug, and these notebooks are a very convenient way to view such plots. You can also simply print the states if you want. In this case, the array returned from get_state_grid() will simply be printed out in a human readable format

What To Turn In

When you are finished, upload your rush.py code to Canvas, along with an explanation of your heuristic and a proof that it is admissible. Also indicate the answer to these questions with your submission:

  • Did you work with a buddy? If so, who?
  • Are you submitting your heuristic to the class competition? If so, what name or pseudonym would you like to use on the class web site?

Part 1: Breadth-First Tree Search

Goal Node (5 Points)

NOTE: For simplicity of implementation, you can assume that the goal car is horizontally oriented, but you should be able to handle any length car.

Create a method that returns True if the state is a goal node and False otherwise. You can use this later as a helper method when you're implementing your search techniques.

As an example, supposing that your method is called is_goal, here's what you should get for one of the regular puzzles

And here's what you should get if the red car does happen to be at is goal state

Neighboring States (10 Points)

Write a method to create a list of State objects which represent neighboring states of this state. For example, the first state of jams/3.txt has 5 neighbors. Supposing that your instance method is called get_neighbors, the code below will plot these 5 neighbors in Jupyter

Note: Your neighbors may not come out in the same order as mine, and that's fine as long as they're all there.

Hint: To make this easier, you might want to take advantage of the provided methods get_state_grid and clone. You can use clone to make a deep copy of the current state that you can then change to turn it into a neighboring state by moving one of the cars in the copy. To figure out which cars can move, you can use the grid you get back from get_state_grid to check to see if there's empty space each car can move into.

Breadth-First Tree Search (15 Points)

Now that you have a way of generating neighbors and figuring out which states are the goal, you should fill in the instance method solve that returns a list of states leading from the beginning of the puzzle to a goal node. You can accomplish this by implementing breadth-first tree search. You'll need to take it one step further than simply a goal exists, however; you will also need to show all of the steps of a solution that get there. In particular, before you push a state onto the queue, you should update its prev variable to store where it came from. Then you can trace back from the goal node you found to the start node.

Hint: You can use a regular list to implement a queue in python. The pop() method takes something off of the end, and if you say pop(0) it will take something off of the beginning. Recall also that append() puts something on the end

The solution below is to a very easy puzzle where a brown car just needs to move down one space to make way for the blue goal car to reach the exit

Below is the "easy" example from Valerie Lu's app. Don't even try this until you get the "very easy" example above working...tree search is already starting to take a while on this one.

Note: Your solution may not be exactly the same as mine if your neighbors don't come out in the same order, but it should have 9 steps.

Part 2: Smarter Searching

In this part, you will build much powerful solvers by remembering things and using human knowledge to help guide the problem.

NOTE: If you want to get really fancy with your code, there's a way to implement these three tasks with only one method that accepts a function handle to compute the heuristic at a state (where for BFS graph search the heuristic would always be 0). But it's OK to repeat code as needed to keep it simple if you don't see how to do this.

Breadth-First Graph Search (10 Points)

Add an instance method solve_graph that remembers states that were already visited and does not add them to the queue. You should either use a dictionary with dummy values or a python set. Be sure to use something hashable, like str(state) or state.get_state_hashable to represent your state. If this works properly, you should be able to solve all of the provided puzzles in a reasonable amount of time.

A* Search (10 Points)

Implement A* search in an instance method called solve_astar using a simple heuristic called the blocking heuristic hB(s), which is

  • hB(S) = 0 if the goal car is at the goal when the board is in state S
  • hB(S) = 1 if the goal car is not at the goal but there's nothing in the way when the board is in state S
  • hB(S) = 2 if the goal is not at the goal and there is at least one car in between it and the goal when the board is in state S
Amazingly, if you've done this properly, you should see an improvement in performance on all of the puzzles. To be sure, you should keep track of the number of nodes that get added to the queue, and this number should be smaller with A* and the blocking heuristic than it is with graph search.

Below are the results I got for total number of nodes added for graph search, compared to the number of nodes added for A* search with the blocking heuristic. You may not get exactly the same results depending on what order you add your neighbors in, but you should see an overall improvement. Also, be sure that the number of steps in the solution you find is the same between BFS and A*; they should both find a solution which is optimal. I've indicated what the length of this solution is in the right two columns of the table below:

Puzzle Path BFS Graph A* Blocking Heuristic Improvement BFS Optimal Steps A* Optimal Steps
0 jams/1.txt 1072 1061 11 17 17
1 jams/2.txt 3374 2447 927 15 15
2 jams/3.txt 832 814 18 34 34
3 jams/4.txt 435 416 19 23 23
4 jams/5.txt 2666 2493 173 19 19
5 jams/6.txt 2173 1951 222 19 19
6 jams/7.txt 4805 3257 1548 22 22
7 jams/8.txt 951 951 0 23 23
8 jams/9.txt 789 545 244 18 18
9 jams/10.txt 2370 2105 265 33 33
10 jams/11.txt 856 843 13 57 57
11 jams/12.txt 1072 880 192 34 34
12 jams/13.txt 10915 10354 561 33 33
13 jams/14.txt 15768 12206 3562 35 35
14 jams/15.txt 527 525 2 33 33
15 jams/16.txt 2913 2587 326 42 42
16 jams/17.txt 2190 2159 31 48 48
17 jams/18.txt 1636 1614 22 61 61
18 jams/19.txt 516 490 26 45 45
19 jams/20.txt 2119 1463 656 19 19
20 jams/21.txt 264 262 2 50 50
21 jams/22.txt 4875 4547 328 47 47
22 jams/23.txt 2862 2549 313 50 50
23 jams/24.txt 4350 4227 123 51 51
24 jams/25.txt 8901 8816 85 53 53
25 jams/26.txt 4853 4801 52 50 50
26 jams/27.txt 3006 2805 201 58 58
27 jams/28.txt 2216 1948 268 52 52
28 jams/29.txt 4329 4300 29 55 55
29 jams/30.txt 1170 1170 0 56 56
30 jams/31.txt 4022 3905 117 70 70
31 jams/32.txt 628 605 23 63 63
32 jams/33.txt 4100 3911 189 78 78
33 jams/34.txt 4423 4401 22 72 72
34 jams/35.txt 3941 3837 104 76 76
35 jams/36.txt 2827 2475 352 64 64
36 jams/37.txt 1954 1947 7 66 66
37 jams/38.txt 4042 3784 258 78 78
38 jams/39.txt 3987 3801 186 83 83
39 jams/40.txt 3102 2897 205 82 82

Designing Your Own Consistent Heuristic (10 Points)

In this section, you will design your own heuristic h(S) that's superior to the blocking heuristic (i.e. not the trivial "zero heuristic"), and you'll implement it in an instance method called solve_myastar. Your heuristic should be consistent. In this context, since moving a car is a cost of 1, this means that

\[ h(S) \leq h(N) + 1 \] \[ h(G) = 0 \]

where N is any neighboring node of a state S, and G is the goal state. In other words, the heuristic should never increase by more than one after moving a car by a single space.

You should test your heuristic to make sure that it performs better than the blocking heuristic overall. Then, you should submit a brief description of your heuristic, along with a proof that it's consistent.

Class Competition

To sweeten the deal, we will have a class competition to see who can solve unknown puzzles in the fewest amount of loops, and the winner will get extra credit. So you should think hard about how to design a good heuristic in the last part of the assignment if you want to win big.

To control things, I will be focused on the A* procedure itself, and I will specifically be counting how many times you add something to a queue (or multiple queues if you're doing something bidirectional to try to squeeze out more performance). If you don't reach the optimal cost on a particular puzzle, then your loop penalty will automatically be set to infinity! So make sure you don't get so fancy that you lose sight of an optimal solution. We'll have a score for each puzzle for each submission.