Lab 1: Traffic Jam
Due Feb. 1 by midnight

Starting point code

1. First you need to run setup63 to create a git repository for the lab.

   If you want to work alone do:

   setup63-Lisa labs/01 none

   If you want to work with a partner, then one of you needs to run the following command while the other one waits until it finishes:

   setup63-Lisa labs/01 partnerUsername

   Once the script finishes, the other partner should run it on their account.

2. For the next step, only one partner should copy over the starting point code:

   cd ~/cs63/labs/01
   cp -r /home/meeden/public/cs63/labs/01/* .
   

3. Whether you are working alone or with a partner, you should now add, commit, and push these files as shown below:

   git add *
   git commit -m "lab1 start"
   git push
   

4. If you are working with a partner, your partner can now pull the changes in:

   cd ~/cs63/labs/01
   git pull
   

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). The board is always a square grid. 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.

   The states for this problem are game boards, which are represented as lists of lists. However, lists are not hashable. Therefore, you should use the getKey method to create a hashable version of the the state to store in the visited set.

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 goal 
        show the path
        return
     increment the expanded node counter
     if key of currNode's state is not in visited 
        add key to visited
        find all possible moves from currNode's state
        for each move
           determine the nextBoard
           if key of nextBoard is not in visited
              create a node for nextBoard
              add this node to the frontier
   report that the game has no solution
   

3. Here's a sample of what the showPath method should display for the puzA.txt board.

       | |
    1 2 2 - - 
    1 3 3 - - 
    1 - 0 - - 
    - - 0 - - 
    - - 0 - - 
   
   car1 down
   
       | |
    - 2 2 - - 
    1 3 3 - - 
    1 - 0 - - 
    1 - 0 - - 
    - - 0 - - 
   
   car1 down
   
       | |
    - 2 2 - - 
    - 3 3 - - 
    1 - 0 - - 
    1 - 0 - - 
    1 - 0 - - 
   
   car2 left
   
       | |
    2 2 - - - 
    - 3 3 - - 
    1 - 0 - - 
    1 - 0 - - 
    1 - 0 - - 
   
   car3 left
   
       | |
    2 2 - - - 
    3 3 - - - 
    1 - 0 - - 
    1 - 0 - - 
    1 - 0 - - 
   
   car0 up
   
       | |
    2 2 - - - 
    3 3 0 - - 
    1 - 0 - - 
    1 - 0 - - 
    1 - - - - 
   
   car0 up
   
       | |
    2 2 0 - - 
    3 3 0 - - 
    1 - 0 - - 
    1 - - - - 
    1 - - - - 
   
   Solution found in 6 moves
   Explanded 91 nodes
   

4. Here's a sample of what the showPath method should display for a board that has no solution, such as the impossible.txt board.

   This puzzle has no solution
   
       | |
    1 1 2 2 2 
    3 - - - - 
    3 - 0 4 - 
    - - 0 4 - 
    - 5 5 - - 
   

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 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.

2. 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.

   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 key of currNode's state is not in visited 
        add key to visited
        find all possible moves from currNode's state
        for each move
           determine the nextBoard
           if key of nextBoard is not in visited
              create a node for nextBoard
              set priority based on depth and the heuristic
              add this node to the frontier with priority
   report that the game has no solution
   

Experimental Comparison

Complete the table provided in the experiments file and reflect 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, can you come up with a better heuristic for the Traffic Jam Game? Remember that a valid heuristic must never overestimate the distance to the goal. Prove that your heuristic is better by showing that it outperforms the blockingHeuristic in terms of number of nodes expanded.

Next, 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?

Submitting your code

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