Lab 1: Traffic Jam
Due Feb. 6th by midnight
Problem: How do you move the horizontal vehicles left or right
and the vertical vehicles up or down to allow the red car to exit the
grid out of the top side?
Starting point code
From now on, you will be working with a partner to complete each lab.
We will be
using Teammaker
to form teams. You can log in to that site to indicate your partner
preference. Once you and your partner have specified each other, a
GitHub repository will be created for your team.
Introduction
The objectives of this lab are to:
- Use state space search to solve a problem.
- Use heuristic knowledge to more efficiently find an optimal solution.
- Demonstrate experimentally that informed search outperforms uninformed search in terms of the number of nodes expanded.
- Demonstrate experimentally that heuristics which generate a closer approximation of the distance to the goal outperform other heuristics in terms of number of nodes expanded when using informed search.
For this lab you will modify the following files:
- UninformedSearch.py
- InformedSearch.py
- TrafficJam.py
- FifteenPuzzle.py
- HeuristicsTests.py
- experiments
Playing Traffic Jam and Fifteen Puzzle
We will be using text-based versions of the Traffic Jam and Fifteen Puzzle
games in this lab. Complete the following steps to familiarize yourself with
the games.
- Try playing the Traffic Jam game from the command line.
To invoke the traffic jam game do:
./TrafficJam.py puzzles/traffic00.txt
You will see a picture of the board and a list of valid moves you may
make (as shown below). In the case of traffic00, the gird is 6x6, but
the grid size can change between puzzles. The exit is marked by two
vertical bars. In a traffic jam puzzle, each car is represented by a
unique number. In this example, cars 1, 2, and 6 are positioned
horizontally and can only move left or right, while cars 0, 3, 4, and
5 are positioned vertically and can only move up or down. Cars may be
different lengths but are always only one grid square wide. Empty
locations are marked by a dash. The goal of the game is to move the
car labeled 0 to the exit.
| |
1 1 2 2 3 -
0 - - - 3 -
0 - - - 3 -
- - 4 - 5 -
- - 4 - 5 -
- - 4 6 6 -
a: car0 down
b: car4 up
c: car6 right
Select move (or q to quit):
You should be able to solve this particular puzzle in 7 moves.
- Try playing the Fifteen Puzzle from the command line. To invoke the fifteen puzzle game do:
./FifteenPuzzle.py puzzles/fifteen00.json
In a fifteen puzzle, each block is represented by a natural number, and the blank space is represented by a 0. The goal is to put the blocks in increasing order from the top left to the bottom right (with the blank at the bottom right. The possible moves describe how the space should move. The file
fifteen00.json contains a 2x2 puzzle that you should be able to solve in four moves:
2 3
1 0
moves: U, L
- For each game, try a couple of other starting boards from the puzzles
directory.
- Try making a puzzle of your own for each game. Be sure you can solve it. You can find other example Traffic Jam boards at Dr. Mike's Math Games for Kids.
- Open the files TrafficJam.py and FifteenPuzzle.py in an editor. Familiarize
yourself with the interface so that you can call the appropriate
methods within your search agent. Also be sure you understand how the
boards of the game are represented. For example, the board from traffic00
would be represented as:
[['1', '1', '2', '2', '3', '-'],
['0', '-', '-', '-', '3', '-'],
['0', '-', '-', '-', '3', '-'],
['-', '-', '4', '-', '5', '-'],
['-', '-', '4', '-', '5', '-'],
['-', '-', '4', '-', '6', '6']]
Once you understand how the games work you can move on to implementing
the search algorithms.
Uninformed Search
In this lab you will re-implement BFS, this time using
a Node class to create a graph-based search.
The Node class will seem like overkill for uninformed search,
but you'll see why it's necessary once you implement informed search.
- Open the file Node.py to see the class definition. Note
that each node stores:
- current board state
- parent node
- action taken to reach this state
- depth of the node in the graph
- In the file UninformedSearch.py, complete
the UninformedSearchAgent class. This
class's search() method should implement the following
algorithm. Note that the Queues.py file contains
a FIFO_Queue class that you may use.
create a node to store the initial game board
add this node to the FIFO frontier
while frontier not empty
get currNode from frontier
if currNode's state is a goal
return goal node
end if
increment the expanded node counter
if currNode's state is not in visited
add state to visited
find all possible moves from currNode's state
for each move
determine the nextState
if nextState is not in visited
create a node for nextState
add this node to the frontier
end if
end for
end if
end while
return None
- Test your uninformed search. Here is some sample output:
Once you've completed uninformed search you can move on to informed search.
Informed Search
Next you will implement A* search. The key difference between
informed searches, like A*, and uninformed searches, like BFS, is
that they estimate the cost associated with each node. For A* this
cost is the sum of how much work it took to get to a node and an
estimate of how far it is to the goal from a node.
For the both games, the cost of getting to a node will simply
be the number of actions taken, which is stored in the depth of the
node. To estimate the distance to the goal you will use a heuristic
function.
Complete the implementation of informed search as follows:
- Implement the InformedSearchAgent class. The search
algorithm is similar to the uninformed one. The key difference is
that a priority queue replaces the FIFO queue. Note that
the Queues.py file contains a Priority_Queue
class that you may use. When implementing the search function, you
can initially test it with the zeroHeuristic. This
heuristic is completely uninformative so the resulting search
reduces to BFS.
create a node to store the initial game board
add this node to the PQ frontier with a priority of 0
while frontier not empty
get currNode from frontier
if currNode's state is goal
return goal node
end if
increment the expanded node counter
if currNode's state is not in visited
add state to visited
find all possible moves from currNode's state
for each move
determine the nextState
if nextState is not in visited
create a node for nextState
set priority based on depth and the heuristic
add this node to the frontier with priority
end if
end for
end if
end while
return None
- Test your informed search using the zero heuristic, which adds no additional information. Thus the number of nodes expanded by informed search should be exactly the same as it was for uninformed search.
- ./InformedSearch.py puzzles/traffic01.txt zero
- ./InformedSearch.py puzzles/traffic05.txt zero
Now it's time to add some heuristic information. This will allow the informed search to expand less nodes to more efficiently find solutions.
Heuristics
Implement each heuristic described below. We have provided some
starting point unit tests for the heuristics in the
file HeuristicTests.py. For each heuristic, you should
include four tests using the game boards given in
the puzzles directory. To execute the tests do:
./HeuristicsTests
- Implement the blockingHeuristic function in the
file TrafficJam.py. This function takes in a Traffic Jam
Game board. It locates car0, and returns the sum of the number of
cars that are blocking car0 from reaching the exit plus the number
of rows car0 needs to move to get to the exit. For example in the
starting board for traffic01.txt there are two cars
blocking the exit and car0 needs to move up two rows to reach the
exit, so the heuristic should return 4. While in the starting
board for traffic02.txt there are three cars blocking the
exit and car0 needs to move up three rows to reach the exit, thus the
heuristic should return 6.
- Implement the betterHeuristic function in the
file TrafficJam.py. This heuristic must remain admissible (it
must underestimate the cost to the goal), but must sometimes give a
higher estimate than blockingHeuristic. Be sure to explain
your new heuristic in the function comment and give an example where
it gives a better estimate than blockingHeuristic.
- Implement the displacedHeuristic
and manhattanHeuristic functions in the file
FifteenPuzzle.py. Optionally implement
the bonusHeuristic.
- Test your informed search using all of the heuristics that
you've written. Here is some sample output. Notice that the number of
nodes expanded is much lower when using the blocking
heuristic versus the zero heuristic.
Once you've completed informed search you are ready to do some
performance testing.
Experimental Comparison
Complete the tables provided in the experiments file, and answer the questions that follow. Note that for the fifteen puzzle problems, uninformed search will become excruciatingly slow for any of the larger board sizes. Feel free to try it for yourself, though I won't ask you to record these results for the fifteen puzzle problems.
Submitting your code
To submit your code, you need to use git to add, commit, and push the
files that you modified.