CMSC 433 - Project 4: Concurrent Maze-Solver

Project Overview

For this project you'll be creating a multi-threaded maze solver using some type(s) of thread pool(s) as part of your solution. Input will be a two-dimensional rectangular maze with at most one solution. This guarantees that there will not be any cycles/loops within any maze we test. This also means that a maze might not have a solution and you'll need to test every possible dead-end to know for sure. If a path through the maze exists, your maze solver will return that, otherwise it will return null. The ultimate goal is to solve the mazes while making optimal use of the resources available (this covers both processors and memory, so take care when using recursion and thread pools). The minimal goal is to use a threadpool with at least two threads to generate the correct answer without running out of memory. When grading in done beyond the public tests, your program will be evaluated in part based on the efficiency of your solution when compared to other single-threaded solutions.

Getting Started

We've put some starter files into your CVS repository. Included in this are five single-threaded example solvers, including a few different DFS approaches using the concept of "choice points" along the way. You might find that you'll need to set up the JVM so that it allows a large stack and heap sizes for very large mazes - that information is posted with the mazes.

Maze Files

It will be CRITICALLY IMPORTANT to keep maze files OUTSIDE THE PROJECT FOLDER when you are working on this since there is size limit for submissions and anything in your project folder goes to CVS and I do not have room there for lots of copies of maze files. I suggest you put a Mazes folder on your desktop.

The following link will take you to a page with example maze files. By clicking on the following link, you agree that I can deduct 10 points from your project grade if maze files are found in your project folder. Mazes Available Here

Single Threaded Solvers

STMazeSolverDFS This is likely the best performing single-threaded solver, assuming a large enough maze is provided.

STMazeSolverDFSRec and STMazeSolverDFSIter These two implementations of the same algorithm contain elements that might be useful in an efficient multi-threaded silution. They are provided solely as examples of how the code could be written. You may use any part of them, or nothing at all if you want to approach the problem in a different way.

STMazeSolverBFS This solver performs a breadth-first search. This solution is more complicated that the others. However, since breadth-first search involves exploring from several points of the search space simultaneously, this maze solver algorithm can make a nice starting point for a multi-threaded approach.

STMazeSolverRec This is the simplest: a recursive search procedure, which performs slightly worse than the previous three. There is a danger, when using this approach on a very large maze, of running out of stack space, which is why you would need specify JVM arguments to Eclipse. This one is provided just as an example, but is likely not useful in practice.

Your Design Statement and Progress Report

Running the solvers on a maze

To run these above maze solvers and your own maze solver that you will put in the StudentMTMazeSolver class on the mazes provided or the ones you generate, use Eclipse and run Main class after modifying the filename currently hard-coded into the main method. There is also code there that you can un-comment to be able to run things from the command line, though you'll probably want to use Eclipse to recompile after each change to your code. The Main.main method will call the Main.solve method which will run all defined maze solvers on the same given maze file.

Initial Code Layout

Several classes are provided in the CVS checkout:

Position represents a location in the maze.

Direction represents the four compass directions.

Move stores a given Position and the Direction chosen from it. It also stores the Move before it. (Since the maze contains no cycles/loops, the previous move will be unique.)

Maze stores a representation of the maze and also provides methods that make querying the maze easier. For example, the Maze.getMoves() takes a Position and returns the list of Directions in which you can move if you are at that position.

The Main class supports the loading of mazes from a file and calls each maze solver listed in the solvers array of the Main.solve() method in turn on the maze provided as input. This allows you to more easily compare the timing of multiple maze-solving approaches. You'll note that all maze solvers must be subclasses of the abstract class MazeSolver.

StudentMTMazeSolver is the class that will be tested. More specifically, we will call StudentMTMazeSolver.solve(). This class has to inherit from MazeSolver. You are allowed to add any number of helper methods or classes to your solution, just make sure that StudentMTMazeSolver.solve() returns a List<Direction> containing the correct solution if there is one, or null otherwise.

Possible Algorithms

There are several algorithms that could produce good parallel solvers. One thing that is often true is that any given "choice point" (that is, a position from which multiple outgoing paths are possible) that does not lie on the solution path is likely to quickly lead to dead ends in all directions. As a result of this, statistically speaking, most of the time an exploration from a single choice point will quickly terminate (and thus run out of work) without having contributed positive information. This might suggest that if you want to make sure that your threads are each doing a fair amount of work, and some amount of useful work, it might be a good approach to have tasks consist of exploring several choice points, which should increase the amount of useful work per task.

Also, note that there are no cycles/loops in the maze; this means that if you have two points A and B in the maze, and they aren't points such that going from the starting point to B goes through A, you know that they are completely independent of each other (consider this when thinking about the synchronization of any data structures you use).

It may help to think of the maze as a tree structure, where the root is the starting point and only one of the leaves is an end point.

One approach could be to perform a depth-first exploration until there are several unexplored paths on the stack you create in that algorithm, group these together and hand them off to a thread as a task. Of course you would want to make sure you group enough of them together so that the thread has a good amount of work to do given the overhead.

You can also consider divide-and-conquer strategies. For example, each task could return a path from the current position to the end of the maze. You'd need to think about when to spawn off new tasks, then wait for them to complete; if any of them return a path, then the current node is added to that solution path and it is returned.

We want you to use thread pools in some way. You get to choose what type of thread pool and how to use it to try to reduce the amount of overhead. Remember that if a task is waiting while in the pool, that is denying access to that thread to any other scheduled tasks queued up in the pool.

One approach that has been shown to help in problems where there are two endpoints that you want to connect is to simultaneously work in from the each endpoint, hoping to meet in the middle. Of course, if things don't meet in the middle, you'll only disover that by exhaustion.

Whatever approach(es) you explore, make sure that you have a way to limit the number of threads used by the algorithm since if too many threads are spawned, the overhead of thread management can erase the benefits given by the concurrent processing. Also, you could end up exhausting memory resources and crashing! Java allows you to find out how many processors are available by calling the method Runtime.getRuntime().availableProcessors().

Grading