Search Programming Assignment – CS 416

For this programming assignment, you will create a set of search algorithms for finding solutions to the 15-puzzle.

Problem description:

The 15-puzzle is a slightly larger version of the 8-puzzle discussed in Russell & Norvig:

 5 1 2 4 6 A 3 7 9 C 8 D E B F

Initial state

 1 2 3 4 5 6 7 8 9 A B C D E F

Goal state

The 15-puzzle has a higher average branching factor than the 8-puzzle, but the maximum branching factor is the same (4).

Assignment summary:

The search algorithms you are expected to implement are:

·        Breadth-first search (BFS)

·        Depth-first search (DFS) – depth-first search needs to check for cycles, or a solution will most likely never be found.

·        Either:

o       Depth-limited search (DLS) and Iterative deepening, or

o       Bidirectional search (BDS)

·        Greedy best-first search (GBFS), for h(1) and h(2) mentioned in Russell & Norvig

·        A*, for h(1) and h(2) mentioned in Russell & Norvig

·        One of:

o       Iterative deepening A* (IDA*)

o       Recursive Best-First search (RBFS)

o       Simplified Memory-bounded A* (SMA*)

Assignment skeleton:

You will be given a set of classes, written in C++, that are to provide the basis for these search algorithms. The classes we provided are intended to serve several purposes: they should make the work somewhat easier to complete, they should reinforce the concept that all of these algorithms are more alike than different, and they should help guide your program design. You are not to modify these classes without permission. The classes are:

·        TreeSearch: implements a simple search algorithm based on figure 3.9 in Russell & Norvig. This class should be used by all of your search algorithms, although some search algorithms (e.g., Iterative deepening and IDA*) will require multiple passes through the algorithm.

o       The class relies heavily on the classes Problem and Search to perform the search.

o       The algorithm returns a Solution, with statistics.

·        Problem: an abstract base class that provides a basis for the FifteenProblem class you are required to implement. This class is responsible for determining what states are solutions, as well as which states are successors to other states.

o       The class relies heavily on the classes SearchNode, SearchNodeSet, and SearchState.

·        SearchState: contains information about a state in the problem. This state matches the use of the term in Russell & Norvig, section 3.3. Both the initial state and goal state are SearchStates.

·        SearchNode: contains information about a node in the problem. This node matches the use of the term in Russell & Norvig, section 3.3.

o       This algorithm also generates some statistics.

·        SearchNodeSet: a linked-list of SearchNodes. This should not be confused with the Fringe class used by Search methods. This set is generated by the expand() method of the Problem class, and for this assignment will never hold more than four SearchNodes.

·        SearchAction: contains information about the action required to get from one node to another. Seemingly irrelevant for FifteenProblem, but important for later extensibility.

·        Search: an abstract base class that provides a basis for the BFS, DFS, DLS, BDS, GBFS, AStar, et al. classes you are required to implement. These classes are responsible for determining which node to explore next.

o       Search relies heavily on the Fringe class.

o       Some implementations of Search (e.g., GBFS, AStar) rely on the Heuristic class.

o       Some implementations of Search (but not all) will need to set the Solution class’s cutoff to true.

·        Fringe: an abstract base class that contains the nodes that have been created but not yet explored. The details of the Fringe will depend greatly on the search algorithm. BFS will want a Fringe that resembles a queue. DFS (and others) will want a Fringe that resembles a stack. GBFS (and others) will want a Fringe that will be able to return the node with the smallest heuristic value. This Fringe can be a binary search tree, a Fibonacci heap, or any other structure capable of returning a “smallest” node.

o       Fringes will want their own nodes that will be storing:

§         a SearchNode

§         possibly a next node, or a left and right child node

§         possibly a heuristic value (this should not be calculated multiple times for a single node)

·        Heuristic: an abstract base class that provides a basis for the MisplacedTiles (AKA h1) and ManhattanDistance (AKA h2) heuristics used by the informed search techniques.

·        Solution: contains whether or not success occurred. If success did not occur contains whether or not a cutoff occurred. If success did occur, Solution contains the final SearchNode of the solution, which will implicitly contain the entire solution, since each SearchNode refers back to its parent. Also contains the number of nodes accessed as well as maximum fringe.

·        Also provided is the Helper.h/cpp functions that help with parts of the solution. The function isNormalSolution() returns if the solution is of the form “123456789ABCDEF “ or of the form “123456789ABCDFE “. Use this function to make sure you look for the right solution to the problem. The PrintSolution function should be used for outputting all of the solution and statistics.

The skeleton can be found at http://www.cs.virginia.edu/~cs416/Assignments/Assign1/FifteenSkel.tgz (Unix/Linux) or http://www.cs.virginia.edu/~cs416/Assignments/Assign1/FifteenSkel.zip (Windows).

Assignment specifics:

You are to create the following classes:

·        FifteenProblem: this class should inherit Problem.

·        BFS: this class should inherit Search

·        DFS: this class should inherit Search

·        One of:

o       DLS: this class should inherit Search

o       BDS: this class should inherit Search

·        GBFS: this class should inherit Search

·        AStar: this class should inherit Search

·        RBFS or IDAStar if those search methods are chosen: these classes should inherit Search

·        MisplacedTiles: this class should inherit Heuristic

·        ManhattanDistance: this class should inherit Heuristic

For the benefit of the grading, please expand all nodes in the following order:

·       Right – (space moves right)

·       Down – (space moves down)

·       Left – (space moves left)

·       Up – (space moves up)

You should create a program that takes as an input the initial state of the 15-problem as well as which search method to use. The main() method can either reside in the FifteenProblem.cpp file or in a driver file, if you prefer. You may use either a Unix/Linux based C++ compiler, or a Microsoft based C++ compiler. If you choose to use the Microsoft based C++ compiler, you will want to create a console application. The name of the compiled program should be FifteenProblem for Unix/Linux or FifteenProblem.exe for Windows.

The program should accept the following inputs in the following format:

·        initialstate searchmethod options

Examples include:

·        “123456789AB DEFC” BFS

·        “123456789AB DEFC” DFS

·        “123456789AB DEFC” DLS 2

·        “123456789AB DEFC” AStar h2

·        “123456789AB DEFC” SMAStar h2 4000

Input Details:

·        The initial state should contain sixteen characters, namely the digits 1-9, letters A-F, and a space, in any order.

·        The search method can be: BFS, DFS, DLS, ID, BDS, GBFS, AStar, IDAStar, RBFS, SMAStar.

·        Options are only relevant for DLS (depth-limited search), where the option specifies the maximum depth to explore, AStar, where the option specifies which heuristic to use, and SMAStar, where the options specify the heuristic to use and the maximum number of nodes to have in memory. (The nodes in memory are not just the nodes in the fringe. Ancestors of relevant nodes also need to be stored in memory.)

The output should contain:

·        A description of each state from initial to goal, or a message indicating that either a failure or a cutoff occurred. (Can a failure occur without a cutoff for this problem?) The description for the BFS example listed above would look like:

1234

5678

9AB

DEFC

1234

5678

9ABC

DEF

·        The depth of the solution, if a solution was found.

·        The number of nodes expanded.

·        The maximum size of the fringe.

·        The number of states accessed.

·        The number of nodes created.

·        The number of nodes deleted.

This output can be generated by using the PrintSolution method in helper.cpp. Please make sure to use it for the purpose of simplified grading.

Hints:

·        The successors of a state in this problem depend greatly on the position of the blank spot. Rather than think about which tiles can move into the blank spot, try considering where the blank spot can move. Certain numerical qualities about this position will determine whether or not the blank can move left, right, up, or down. If a blank spot moves up, then its location is being swapped with the location above it.

·        The heuristics can be generated by comparing the state being evaluated to the goal state. The number of misplaced tiles is easily calculated in time linear to the number of tiles in the puzzle, but the simple solution to the Manhattan distance requires time quadratic to the number of tiles in the puzzle.

Feedback:

As with any assignment, we cannot foresee all possible sources of confusion. E-mail cs416@cs.virginia.edu with any questions or comments about the assignment. However, in general such e-mails will not be answered directly. Rather, this section of this document will be updated to reflect those questions or comments worth addressing (i.e., those not addressing problems specific to a student’s particular block of code, etc.), so check back before e-mailing us to make sure you issue has not already been addressed.

Ï    Do we need to use a particular algorithm to implement the individual searches in Bidirectional search?

Ñ    No

Ï    Since I know that h2 dominates h1, do I need to calculate h1 anyway?

Ñ    Yes

Ï    Can I use the fact that h1 & h2 always return integers?

Ñ    Yes

Ï    Should the program expect inputs on the command line, or via user interaction?

Ñ    Command line

Ï    Will all submitted boards be solvable?

Ñ    Yes, because with the use of the function “isNormalSolution()” you can always use the proper goal state. All puzzles are solvable to either of the two states. (“123456789ABCDEF “ or “123456789ABCDFE “)

Ï    I’ve created a new SearchAction (SearchActionWithDesc), and for the 15-problem, I only need four of them – one for each possible type of move. My problem is that the SearchNode destructor is deleting its SearchAction. I know I could create a new one for each SearchNode, but (1) that wastes space and time, and (2) it requires implementing an overloaded == operator if I want to determine if two SearchActions are equal. May I modify SearchNode so that it does not delete its SearchAction?

Ñ    Absolutely. You should definitely do this.

Ï    Do I have to make sure that my algorithm is not leaking any memory?

Ñ    Absolutely. You should definitely do this. Every good algorithm should be able to clean up all of the memory it used. If memory leaks are allowed, the program may exhibit unstable behavior for harder problems. Thus programs may be graded on residual memory leaks. If you would like to check if your program leaks memory you may use one of these two methods:

On windows:
Put an extra set of brackets around main() and add call to _CrtDumpMemoryLeaks():
#include<crtdbg.h>
int main(int argc, char **argv) {
{ ... your main code goes here... }
_CrtDumpMemoryLeaks();
}

On Unix/Linux:

Install the package called “valgrind” and run your program like this (unfortunately not installed on blue/cobra):

valgrind ./prog.exe "123456789ABC DFE" BFS

Ï    I’m using STL containers within my fringe classes for ease of coding. These classes have a built-in size() function that I’d like to use, but that means adding a size() function to my fringe so that I can access the STL container’s size() function. May I add this function?

§         STL containers are definitely not required, but are allowed.

§         My BFS (for example) class increments the m_fringeSize variable whenever anything is inserted into the fringe, and decrements it whenever anything is removed from the fringe, so it does not actually need to calculate the size of the fringe when the fringeSize() method is invoked. You do NOT want to use a size() function that has to do this, but the STL containers are probably savvy enough that they are likewise maintaining an internal variable rather than calculating the size when asked.

§         Finally, you can (and should) modify your BFSFringe (for example) without actually modifying Fringe if you want to add this functionality.

Ï    Can you give me any idea about how our main should work?

Ñ    Sure. After figuring out which options to use, you should have code that is similar to:

FifteenProblem * test = new FifteenProblem(argv[1]);

Search * method = new DLS(atoi(argv[3]));

TreeSearch * solve = new TreeSearch(test, method);

Solution * soln = solve->findSolution();

cout << test->SolutionDesc(soln);

For clarity’s sake, I’ve removed the code that determines which method to use, as well as code that verifies the arguments are valid, etc.

Ï    What exactly does number of states accessed mean?

Ñ    The number of states accessed refers to:

1.      The number of states compared against the goal state, plus

2.      The number of states compared against other states (e.g., when determining if a cycle exists)

This is important in helping to understand how checking for cycles adds to the time complexity.

Ï    Are you going to compile and run our solutions after we turn them in?

Ñ    I reserve the option to compile and run the solutions you turn in. My desire is to not have to do this if your solutions are perfect during the demonstration. If I have to compile, I will compile first on cobra. If that doesn't work, I will then compile on blue. (I'm not expecting most students to have access to cobra.) For Windows solutions, I’ll be using my office computer. If that doesn’t work, I’ll try a computer in Thornton stacks.

Ï    Can you explain how the different destructors do/should work?

Ñ    Sure. I’ll try to do it from a bottom-up approach.

First, I’ll mention the classes that are in the skeleton:

1.      SearchState makes a deep copy of the description passed to it during it construction, which means that it is responsible for deleting this copy when it is deleted. (By deep copy I mean that it allocates new memory and copies the data into that new memory location. A shallow copy means just storing the pointer, which really isn’t a copy at all.)

2.      SearchNode makes a deep copy of the SearchState passed to it during its construction, which means that it is responsible for deleting this copy when it is deleted. It also deletes its parent, if it is an only child.

3.      Solution will delete the node it contains even though it only had a shallow copy of it. This node should never have a child, so we don’t have to worry about it being deleted by that process, but we do want to make sure it’s not deleted by some other process. Depending on the order that other things are deleted (e.g., your Fringe), deleting this node might cause all of its ancestors to get deleted as well.

4.      TreeSearch deletes the expanded SearchNodeSet after everything has been removed from it.

Now, I’ll mention the classes that you are responsible for creating:

5.      Your Search is responsible for deleting its Fringe.

6.      Your Fringe is responsible for deleting all SearchNodes in it. (If you have a root FringeNode, you can delete this and have it recurse.) There are two reasons that you must be careful here:

1.      You do not want SearchNodes to be deleted when you’re removing FringeNodes for purpose of expansion.

2.      The Fringe (or FringeNode) only made a shallow copy, so you do not want the process that created them, or any other process, deleting them. Normally, you shouldn’t have to worry about them being deleted by their children because nodes in the Fringe typically don’t have any children. Depending on your implementation, this might become a concern for RBFS.

7.      Your main() routine is responsible for deleting its FifteenProblem, its Solution, its Search method, and its TreeSearch.

8.      Of course, as there are many possible ways to implement this, there might be other deletion concerns as well.

Ï    Can we create a FringeNode that will hold both a SearchNode and its heuristic? If so, how can our Fringe’s insert() method accept a heuristic, since Fringe is part of the skeleton?

Ñ    You can create any type of class that will make it easier to solve the assignment. I can tell you that I created an AStarFringeNode that did indeed have a heuristic value stored with it. In my case, AStarFringe’s insert() method did not accept a heuristic, but rather calculated the heuristic value and passed it on to AStarFringeNode. You could, however, add an additional insert() method to AStarFringe and have it take a heuristic if you like. Or, in the other direction, you could have your AStarFringeNode calculate the heuristic value in its constructor. Of course, this means that at whatever level you do this, that level will have to know what the heuristic is. Again, for my solution, my constructor for AStarFringe takes a heuristic as an argument.

Ï    How should we call TreeSearch multiple times for iterative deepening and its relatives?

Ñ    ID can use the DLS search method with increasing levels of depth. You don’t actually even have to create an ID search class if you find that it is unnecessary.

Ï    How do I read command line arguments?

Ñ    For the signature of your main() routine, use

int main(int argc, char * argv[])

Then argc is the number of command line arguments, including the name of the program, argv[0] is the name of the program, argv[1] is the first argument following the program name, etc.

Ï    Can you be more specific about deletions? Specifically, when should SearchNodes be deleted?

Ñ    Theoretically, there are three times you might need to delete a SearchNode:

1.      If a SearchNode cannot be expanded, it should be deleted.

2.      If a SearchNode cannot be added to the fringe (e.g., because it contains a cycle), it should be deleted.

3.      When your fringe is deleted, all SearchNodes in it should be deleted.

I say theoretically, because for the 15-problem, the first case will never happen. So, what if when a SearchNode is expanded none of its children can be added to the fringe? When the last of those children is deleted (due to the second case), the parent will be deleted by that child’s destructor. (See SearchNode.cpp).
Submission:

You must demonstrate a working solution for at least 2 of the search methods (although it would strongly benefit you to demonstrate working solutions for all search methods) on either Monday, September 27th, or Tuesday, September 28th between 3 and 5 PM. There will be eight 30-minute slots on these days containing a maximum of 10 people each. Slots will be assigned in a first-come, first-serve manner. Naturally, these demonstrations cannot take more than 3 minutes each on average. If you are unable to find a slot that matches your schedule please let us know as soon as possible as this will provide an extra burden on us. Although this demonstration is required, it is intended primarily for your benefit and will not affect your final grade on the assignment.

The source code and supporting files need to be submitted in compressed form no later than 9 AM on Monday, October 4th. Use the URL http://www.cs.virginia.edu/~cs416/submit.html to submit your actual assignment.

·        If you are submitting a Linux/Unix solution:

o       The name of the file you submit should be FifteenProblem.tgz. As the name suggests, it should be a gzipped tarball. To create a gzipped tarball, type “gtar –cvzf FifteenProblem.tgz README Makefile *.cpp *.h”

o       The solution needs to be able to compile and run on blue.unix.

o       Be sure to include a Makefile, so that all I need to type to compile your submission is “make”.

o       The name of the executable should be FifteenProblem. Upper case “F”, lower case “ifteen”, upper case “P”, lower case “roblem”.

o       The README file should contain your name and any information that might be helpful in the assessment of your submission.

·        If you are submitting a Microsoft solution:

o       The name of the file you submit should be FifteenProblem.zip. As the name suggests, it should be a zip file. You can use WinZip, or even regular “zip” on blue.unix (or even gtar). If you don’t know how to do this, see the Linux/Unix directions, but be sure to include any other files that might be necessary for me to compile your solution. (E.g., *.dsp and *.dsw)

o       The name of the executable should be FifteenProblem.exe. Upper case “F”, lower case “ifteen”, upper case “P”, lower case “roblem.exe”.

o       The README file should contain your name, what version of MS C++ you were using (i.e., v6.0 or .NET – let me know if neither of these work for you), and any information that might be helpful in the assessment of your submission.

You may submit either the file FifteenProblem.tgz for Linux/Unix solutions or FifteenProblem.zip for Windows versions.

Students have five late days to use during the course of the semester. Each late day buys you a 24 hour extension.