Lab 0: State Space Search on Logic Puzzles
Due Thursday, Feb. 3rd by 11:59 pm

Starting point code

For this first lab, you will work individually.

First change into your directory for this class. Then clone the GitHub repository for lab0, replacing USERNAME with your username:

    cd cs63
    git clone git@github.swarthmore.edu:cs63-s22/lab0-USERNAME.git
  

Introduction

The objectives of this lab are to:

• (re)acquaint you with object-oriented programming in Python
• (re)acquaint you with breadth-first search
• help you start thinking about search as an AI problem

For this lab you will:

• implement an efficient version of breadth-first search using a dictionary
• apply your search to the Water Pitcher Problem
• formulate the Missionaries and Cannibals Problem for search
• apply your search to the Missionaries and Cannibals Problem

Review the starting point code

Your lab0 repo should contain six files. Read through and familiarize yourself with each file. You do not need to implement any functionality in the first four files, however feel free to add your own test cases to them. Details on what you need to implement in the last two files are provided in the next sections.

1. queue.py implements a Queue data structure. Make sure that you understand how it works. At the bottom of the file is some test code. Execute this file (python3 queue.py) to see the test results. You will need to use a queue when implementing breadth-first search.
2. node.py implements a basic Node class for storing search information. You will create nodes and add them to the Queue during your search.
3. problemState.py defines an abstract class (or in other words an interface). Your search implementation will assume that all problems to be solved will inherit from this abstract class.
4. pitcher.py implements a class called PitcherState that inherits from ProblemState. Once you complete your implementation of search, you can test it on this problem.
5. searchAgent.py contains an incomplete implementation of a search agent that uses BFS to solve logic problems. You must complete this.
6. missionaries.py contains an incomplete implementation of a class called MissionaryState. You must complete this.

Implementing searchAgent.py

Open the file searchAgent.py and complete the implementation of the class definition. You'll need to write the constructor, a search method, and a helper method for building up the path to the solution. The comments within each method provide guidance about how to proceed. You're welcome to create additional helper methods as needed.

In particular, the method executeSearch() should implement the following breadth-first search algorithm:

# NOTE: the constructor will initialize the queue and dictionary
while queue not empty
   remove node from queue
   if state in node equals the goal state
      return node
   end if
   apply the operators to get all valid successors
   for each successor
      if key of successor is not in unique states dictionary
         add key of successor to dictionary
         create a node for the successor
         add node to queue
      end if
   end for
end while
return None

Testing searchAgent.py

You can execute the pitcher.py file to test your search agent:

    python3 pitcher.py
  

Add at least three more test cases and verify the results. Once your are confident that your search agent is working correctly, you can move on to the next section.

Implementing missionary.py

Open the file missionary.py, and complete the implementation of the class definition. Notice that the MissionaryState class inherits from the abstract class ProblemState and is therefore required to provide concrete definitions for a number of methods, in a similar way to the PitcherState class. In fact, feel free to model your solution to MissionaryState on the PitcherState class. However, there is one key difference between the operators for the Missionary and Cannibals problem and the Water Pitcher problem. The operators for the Water Pitcher problem always lead to valid next states. You'll need to determine a way to recognize invalid Missionary and Cannibal states and avoid returning them as successors.

NOTE: Be careful that you do not hard code any particular number of missionaries or cannibals into your code. You can assume that for every version of the problem the boat can hold at most two people, but the numbers of missionaries and cannibals can vary.

Comment your code clearly. Explain the purpose of every class variable that you create.

Testing missionary.py

At the bottom of the file missionary.py, start by adding two test cases. The first should be the problem we discussed in class where three missionaries and three cannibals start on the left bank. This should be solvable in eleven steps. The second should be the unsolvable problem where four missionaries and four cannibals start on the left bank.

You can execute the missionary.py file to test whether your search agent can also find solutions to this logic puzzle:

    python3 missionary.py
  

Add some additional test cases of your own invention. Try some larger numbers. For instance, can 10 missionaries and 9 cannibals make it across the river safely?

Submitting your code

To submit your code, use git to add, commit, and push the files that you modified.