Assignment #2 Blind and Heuristic Search Methods
FUNDAMENTALS OF ARTIFICIAL INTELLIGENCE - CS161
Programming Assignment #2 Blind Search Methods
Due Monday Oct 26 at 11:59pm

Crossing the Bridge

Four people want to get to the other side of a river by crossing a narrow bridge. A maximum of two people may cross at a time. It is nighttime, so someone must carry the single flashlight during each crossing. One of them takes 1 minute to cross the bridge, another takes 2 minutes, another takes 5 minutes, and the last takes 10 minutes to cross. Call them persons 1, 2, 5, and 10, respectively. If two people cross the bridge together, they must walk at the pace of the slower one. So, if persons 5 and 10 cross together, they take 10 minutes to get to the other side. (If person 5 crosses by himself, it takes 5 minutes.) How long does it take all four people to get to the other side? Of course, it depends on how they do it. From the initial state (1, 2, 5, and 10 on the same side with the flashlight) there are ten possible crossing actions: 1 crosses alone, 2 crosses alone, 5 crosses alone, 10 crosses alone, 1 and 2 cross, 1 and 5 cross, 1 and 10 cross, 2 and 5 cross, 2 and 10 cross, or 5 and 10 cross. (If two people cross, it doesn't matter which one holds the flashlight.)

Here is an example solution: 

1 and 10 go across 10 minutes 
1 goes back with light 1 minute 
1 and 5 go across 5 minutes 
1 goes back with light 1 minute 
1 and 2 go across 2 minutes 
Total 19 minutes
For this problem, 19 minutes is a solution, but is not the fastest one. They could cross the bridge in 17 minutes total (you might want to verify this by hand). For breadth-first search, depth-first search, and depth-first-iterative-deepening search, we're going to assume that the goal is to complete the task in N minutes or less. Any solution that satisfies this is an acceptable goal solution.

For this problem, you must implement the solutions to the Crossing the Bridge problem using

  1. breadth-first search (BFS),
  2. depth-first search (DFS), and
  3. depth-first-iterative deepening search (DFIDS).
Name your top-level functions BFSCrossing, DFSCrossing, and DFIDSCrossing, respectively.

Your functions should be able to handle people crossing the bridge with different costs, not just 1, 2, 5, and 10. For example, an instance of this problem with costs '(1, 3, 7, 12) and a total time of 21 could be given as the two arguments to your functions. (The 2nd argument means that 21 minutes or less is an acceptable solution.)

For each of the search routines, avoid returning to states that have already been visited on the current solution path i.e., there should be no repeated states in a solution.) Also, for BFS, DFS, and DFIDS, don't expand a node if its path cost is already over the chosen time limit. You will have to keep track of the total minutes taken.

Your programs will be called as such (the number of people might change):

(BFSCrossing '(1 2 5 10) 16) (the last argument is the goal time of N minutes)

(DFSCrossing '(1 4 6 10) 20)

(DFIDSCrossing '(2 3 5 7) 18)

The output of your programs should look like this (shown for formatting purposes, not an actual answer): 

>(BFSCrossing '(1 2 5 10) 19) 
returns
(19 (1 10) (1) (1 5) (1) (1 2))
The interpretation is
  1. Total time Cost = 19
  2. Move 1 and 10 across (0 + 10 = 10 minutes)
  3. Move 1 back (10 + 1 = 11 minutes)
  4. Move 1 and 5 across (11 + 5 = 16 minutes)
  5. Move 1 back (16 + 1 = 17 minutes)
  6. Move 1 and 2 across (17 + 2 = 19 minutes)
If a solution cannot be found within the prescribed time limit (the last argument to your function), your functions should return nil

The way to approach this problem is to consider the state space, operators, goal test and path costs:

State space: One way to think about this is that any of the four people could be at one side of the bridge, while the rest are at the other side. There are thus 2^4 = 16 distinct states. This is equal to the number of ways to choose people to be on one side of the bridge: (C(4,0) + C(4,1) + C(4,2) + C(4,3) + C(4,4) = 16).

Possible operators: The possible operators are all the ways to have one or two people go from one side of the bridge to the other. Taking any action will move the state from one to another of the above states.

Goal test: Has everyone crossed to the other side of the bridge?

Initial state: All people are on one side of the river.

Path cost: The cost of an operator is how long it takes for the slowest person traveling to cross the bridge. 

The TA may run the program with several different numbers of people and crossing costs. Remember that some approaches may not find a solution (also, some problems don't have solutions.) 

Grading

You will receive a 0 if it looks like you just did not spend much time on it. But generally, the grading breakdown is as follows:

  1. 25 - style and commenting as it looks on SEAS.
  2. 15 - your code matches the specifications for the inputs and outputs of the functions as they are described in the homework (if they are described).
  3. 20 - your code outputs the correct answers for the cases.
  4. 25 - your code correctly implements the algorithm.
  5. 10 - your code correctly loads into the SEAS GCL interpreter without anything breaking.
  6. 5 - your submission matches the filename specifications as mentioned in the homework.

What to Submit

Submit everything electronically. In all files include your name and SID.

  1. hw2.lisp which contains your well-commented and well-formatted functions BFSCrossing, DFSCrossing, and DFIDSCrossing and any helper functions used.
  2. hw2execution.txt which contains a log of you testing your code with the inputs suggested by the homework prompt.