CS4341 Introduction to Artificial Intelligence 
Project 1 - C 2002

DUE DATE: Monday, Jan. 21 at 9 pm. 

• Project Goal
• Project Assignment
• Input Specifications
  • Sample Input Files
    • net.txt
    • second_net.txt
• Output Specifications
• Your Code
• Project Submission
• Grading
• Graduate Credit Problem

Project Goal:

    The goal of Project 1 is to help you understand exactly how different search strategies work.  You will implement each of nine net search algorithms.  Among the searches are basic searches, heuristically informed searches, and optimal searches.

Project Assignment:

• Your program must run on the CCC Unix machines
• You may use any high-level language (Java, Lisp, Prolog, C, C++, ...).
• Your program must adhere to the Input and Output Specifications.
• Your program must demonstrate the following search methods:
  • Depth 1st search
  • Breadth 1st search
  • Depth-limited search (depth-limit = 3)
  • Iterative deepening search (show all iterations, not just the iteration that succeeds)
  • Basic Branch-and-bound (= Uniform cost search) with neither Estimated Distance nor Dynamic Programming
  • Greedy search (= Best 1st search)
  • A*
  • Hill-climbing
  • Beam search (w = 2)
• All searches must terminate.
• No search results should contain any loops.

Input Specifications:

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

The net file has two sections.  The first section describes the topology of the net 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. 

• The first field is the name of a node.  All nodes are named by a single capital letter.  Therefore, the length of the first field is always one byte (one character).
• The second field is also the name of a node, and is also one character long.  In the net, this node is adjacent to the node named in the first field.
• The third field is the actual length of the connection between the node named in the first field and the node named in the second field.  It is a float value.

In total, the first section will contain as many lines as there are connections in the net.  You may assume that every net contains a node named 'S' and a node named 'G'.  You may also assume that the net 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 net (except for the goal node).  Only the heuristically informed methods should use this information.  Each line has 2 fields.

• The first field is the name of a node.  Again, it is one character.
• The second field is the estimated distance from the node named in the first field to the goal.

The net shown in Figure 4.1 on p. 64 of Winston's AI textbook, with the heuristic information given in Figure 4.5 is described by this file: net.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.

Output Specifications:

        Your program should output the trace of EACH search method, in the order listed above.  In particular, you should print the name of each node in the order it was EXPANDED, (not just explored).  When a search method backtracks past a node that has already been expanded do NOT print the name of the node again.  Also, notice that you must expand a node in order to discover anything about its neighbors (children, in a search tree), but that the heuristically informed methods are not required to expand a node when they learn the node's estimated distance to the goal.  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. Separate each node name with whitespace, and try to show the trace for one search on one line.  For example, the trace of the net shown in Figure 4.1 (p. 87) and informed with the estimates in Figure 4.5 (p. 71)would produce:

S A B C E D F G

S A D B D A E C E E B B F D F B F C E A C G

S A B D D A E

S S A D S A B D D A E S A B C E D E D A B E B F S A B C E D F D E B F D A B CE E B A C F G

S A D E B D A E F B C E B G

S D E F G

S D E F G

S D E F G

S A D B E C F G

        (Note that for branch-and-bound 'C' is expanded even though no diagram shows this in Figure 5.2 in the textbook.  This is because it has no children, but the search still had to expand node C in order to determine that.  Also, note that Figure 4.8 in the textbook is incorrect, because S-D-E-B should never be expanded.)

        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 nets!) 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.

Your Code:

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

Your solution must use a general search procedure and a general data structure ("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

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.

Project Submission:

        Project 1 is due at 9 pm on January 21,2002.  One (and only one) member of your group should submit the following files using the turnin program:

• proj1_readme.txt: Containing:
  • the names of the members of your group
  • code documentation following the Departmental Documentation Standard
  • instructions on compiling and running your program
• proj1_script.scr: A capture script of your program working on the sample file net.txt.
• The source code for your program
• Any ancillary files that your program requires

Grading:

• Your program will be tested using test files other than net.txt and second.txt.
• Each search method that works successfully and that has been correctly implemented will be worth 9 points. These 9 points are distributed in the following way:
  • 1.5 points for correctly calling the general search procedure General-Search (or the name you have given to it).
  • 3 points for handling the queue correctly according to the particular search method
  • 4.5 for running correctly over the 3 test files (1.5 for each test)
• 9 points will be for Documentation. This documentation includes both the documentation standard and code comments. Make sure you describe what parts of the code are contained in each file and a general description of how the program runs.
• 10 points will be for creating the general search procedure as described above and making each of the search methods be a call to this general procedure.
• Total: 100 points.

Graduate Credit Problem:

1. (10 points) Construct an example of a net for which all the search methods above produce different traces. That is, no two search methods produce the same trace for the net. Provide your answer in the input format specified above.

2. (10 points) Prove that A* is complete and optimal when h is an underestimate of the distance to the goal.