WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS4341 Introduction to Artificial Intelligence 
Project 1 - A Term 2017

Prof. Carolina Ruiz and Ahmedul Kabir 

Due Date: Canvas submission by Monday, Sept. 11th, 2017 at 11:00 pm. 
------------------------------------------

Project Goal:

The goal of this homework is to help you understand exactly how different search strategies work.  You will implement each of eight graph search algorithms.  Among the searches are basic searches, heuristically informed searches, and optimal searches.

In particular, the search strategies included in this project are:

  1. Depth 1st search
  2. Breadth 1st search
  3. Depth-limited search (use depth-limit = 2)
  4. Iterative deepening search (show all iterations, not just the iteration that succeeds)
  5. Uniform cost search (= Branch-and-bound)
  6. Greedy search (= Best 1st search)
  7. A*
  8. Hill-climbing (use the version of hill-climbing without backtracking)
  9. Beam search (use w = 2)

Project Assignment:

For illustration purposes, suppose that you need to find a path between S and G in the following graph. See the description of this graph input format below. 
S M 15
S A 1
M G 15
A I 5
A C 2
A B 50
C E 1
C D 10
I J 4
J K 50
J L 5
K L 5
L M 35
#####
S 22
M 14
I 10
J 8
K 6
L 4
E 18
C 16
D 20
A 12
B 24

A picture of this graph is included below. Note that the (under)estimated distance of each node to the goal is included inside the node. (Special thanks to Peter Mardziel for creating this picture).

Write a computer program that implements the general search algorithm described in class and in the textbook.

Input Specifications:

    Your program must read the graph to be searched from a file.  The format of the file is as follows:

The graph file has two sections.  The first section describes the topology of the graph and the weights (costs, distances) of the paths between nodes.  The second section provides heuristic estimates for the distances from each node to the goal node.

In the first section, each line contains all the information about one connection between two adjacent nodes.  Each of these lines has 3 fields, and each field is separated by whitespace. 

In total, the first section will contain as many lines as there are connections in the graph.  You may assume that every graph contains a node named 'S' and a node named 'G'.  You may also assume that the graph is finite (of course).  These are the starting and goal nodes, respectively.  After the first section there will be a line separating the two sections.  This line will contain only 5 pound signs.  i.e. "#####"

The second section contains heuristic information about each node in the graph (except for the goal node).  Only the heuristically informed methods should use this information.  Each line has 2 fields.

As an example consider the graph in the file: graph.txt

S A 3.0
S D 4.0
A B 4.0
B C 4.0
A D 5.0
B E 5.0
D E 2.0
F E 4.0
G F 3.0
#####
S 11.0
A 10.4
D 8.9
B 6.7
E 6.9
C 4.0
F 3.0
Please note that after F 3.0 there is a newline character. Also, note that the (under)estimate of the distance between the goal state G and itself is always 0 and hence not included in the file.

Output Specifications:

Your program should output the trace of EACH search method, in the order listed above. In particular, you should print:

In uninformed search methods, the children of a node should be considered ordered in alphabetical order, that is if a node has children D, B, and F, then B will considered the 1st (or leftmost) child, D the 2nd (or middle) child, and F the last (or rightmost) child of the node. In informed search methods where cost/value of a path is considered (e.g., uniform (= branch-and-bound), greedy search, A*, hill climbing, and beam search), and you need to decide the order of the paths in the queue according to their values (either f, g, or h values), follow the sorting procedure below:

For example, the output of your program when the input is the graph described in graph.txt should be:
The search ends when the goal node is expanded. Therefore if the goal is reached, it will be the last node listed. Since some of these searches are not complete (even for finite graphs!) it will be possible that the goal is not found. In this case, the trace will end with the last node expanded before the search terminated, followed by a "failure to find path between S and G" message.

For another example of the expected output see Solutions to old HW1. (The search trees are depicted there just for illustration purposes, but are not part of the output. Note also that those solutions use a different convention for depth-limited search and iterative deepening - the level numbers there are "inflated" by 1, as discussed in class. Ignore the Hill-climbing output as it uses backtracking while in this project you are using Hill-Climbing without backtracking.)

Your Code:

Your program (or an accompanying script, as described in your program documentation) must accept the name of the file to read the graph from.  For example, your program could be run by typing "java Search graph.txt" or "search graph.txt" or "runsearch graph.txt"

Your solution must use a general search procedure and a general data structure (that we'll refer to in class and in this project statement as "the queue") so that each of the search strategies calls the general search procedure with a parameter specifying which search method to use.  That is, you must have a procedure that implements the following pseudo-code (adapted from Russell's and Norvig's textbook):

   function General_Search (problem, search-method) returns either a solution or failure
        queue = Make-Queue(Make-Node(problem.initial-state))
        loop do
            if queue is empty then return failure
            node =Remove-Front(queue)
            if State[node] is a solution of problem then return State[node]
            opened-nodes= Expand(node)
            queue= opened-nodes added to queue according to search-method
        end

Your procedure implementing this pseudo-code must be named General_Search as shown above.

More details about this general procedure will be given in class. For an example of how to implement each of the search strategies as a call to this general procedure, see Russell's and Norvig's online code. Although you are welcome to look at their code to guide the design of your program, you MUST submit your own original code.

Note that in order to avoid loops, you need to store not just the name of node being explored in your "queue", but also the path used to arrive to that node from the source node, as it is done in the sample traces shown above.

Project Submission:

Submit on Canvas the following files by the submission deadline:

Project Grading:

Optional Bonus Problem: