Lab 1: Traffic Jam
Due Jan. 30th by midnight

Starting point code

cd ~/cs63/labs
git clone git@...

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.

For this lab you will modify the following files:

• puzzles/mypuz.txt
• UninformedSearch.py
• InformedSearch.py
• experiments

Playing Traffic Jam

We will be using a text-based version of the Traffic Jam game in this lab. Complete the following steps to familiarize yourself with the game.

1. Try playing a version of this game on the board depicted at the top of this lab. To invoke the game do:

   ./TrafficJam.py puzzles/biggerA.txt
   

   You will see a picture of the board and a list of valid moves you may make (as shown below). In this case the gird is 6x6, but the grid size can change between puzzles. The exit is marked by two vertical bars. 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.

2. Try a couple of other starting boards from the puzzles directory.

3. Open the file puzzles/mypuz.txt and make a puzzle of your own. Be sure you can solve it. You can find other example boards at Dr. Mike's Math Games for Kids.

4. Open the file TrafficJam.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 above would be represented as:

   [['1', '1', '2', '2', '3', '-'],
    ['0', '-', '-', '-', '3', '-'],
    ['0', '-', '-', '-', '3', '-'],
    ['-', '-', '4', '-', '5', '-'],
    ['-', '-', '4', '-', '5', '-'],
    ['-', '-', '4', '-', '6', '6']]
   

Uninformed Search

In this lab you will re-implement BFS, this time using a Node class to create a graph-based search.

1. Open the file Node.py to see the class definition. Note that each node stores the current state, a pointer to the parent node, the action taken to reach this state, and the depth of the node in the graph.

2. 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 
        show the path
        return
     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
   report that the game has no solution
   

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 Traffic Jam Game 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:

1. 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 test 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 
        show the path
        return
     increment the expanded node counter
     if currNode's state is not in visited 
        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
   report that the game has no solution
   

2. Implement the blockingHeuristic function. 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 puzA.txt there are two cars blocking the exit and car0 needs to move up 2 rows to reach the exit, so the heuristic should return 4. While in the starting board for puzB.txt there are three cars blocking the exit and car0 needs to move up 3 rows to reach the exit, thus the heuristic should return 6.

   Test that your heuristic returns the correct values for all the game boards given in the puzzles directory.

3. Implement the betterHeuristic function. This heuristic must remain admissible (it must underestimate the cost-to-go), 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.

Once you've completed informed search you are ready to compare the performance of the two search methods.

Sample Output

• ./UninformedSearch.py puzzles/puzA.txt
• ./InformedSearch.py puzzles/puzA.txt blocking
• ./UninformedSearch.py puzzles/puzE.txt
• ./InformedSearch.py puzzles/puzE.txt blocking

Experimental Comparison

Complete the table provided in the experiments file. The columns for 'Informed expanded' and 'Percent gain' should be based on the blockingHeuristic. You should add two columns to the table: one for the number of states expaned and one for the percent gain with your better heuristic. Here is an empty table with the extra columns added. You should calculate percent gain as (1 - A* / BFS) * 100. After the table, add a paragraph reflecting on when A* shows the largest gains over BFS.

Extra Challenge

This is not required, and should only be attempted once you have completed the required portions of this lab.

First, try implementing greedy search (only considering the heuristic value, and ignoring the cost so far). How does this affect path length? Number of nodes expanded?

Next, come up with a puzzle on which greedy search performs badly but A* search performs well. There will be a Piazza post for sharing such puzzles; a small bonus will be awarded for particularly good puzzles.

Submitting your code

cd ~/cs63/labs/01
git add UninformedSearch.py InformedSearch.py experiments
git add puzzles/mypuz.txt
git commit
git push