• Learning Objectives
• Starter Code
• What To Turn In
• Part 1: Breadth-First Tree Search
  • Goal Node (5 Points)
  • Neighboring States (10 Points)
  • Breadth-First Tree Search (15 Points)
• Part 2: Smarter Searching
  • Breadth-First Graph Search (10 Points)
  • A* Search (10 Points)
  • Designing Your Own Consistent Heuristic (10 Points)
  • Class Competition

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?
• How long did this take you? I'm simply using this to gauge if things are too easy, too hard, or just right.
• Any feedback to help improve the assignment for future students? Alternatively, if there's nothing you would change, let me know what specifically worked for you about it so I know to keep doing things like that.

Part 1: Breadth-First Tree Search

Goal Node (5 Points)

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 h_B(s), which is

• h_B(S) = 0 if the goal car is at the goal when the board is in state S
• h_B(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
• h_B(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 he 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 decrease 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.