| Sponsor |
Tucker Balch and Karsten Schwan tucker@cc.gatech.edu schwan@cc.gatech.edu 216 MARC |
| Area | OS and Intelligent Systems |
Problem
Note: this project should only be attempted by someone either familiar
with Java or willing to take extra time to learn Java. A proficient C
or C++ programmer should not have too much trouble.
Path planning is a classic AI problem, especially for robot navigation. In this project you will explore issues in path planning, parallel programming and Java.
The problem is for you to develop an efficient routine that plans a path across a two dimensional field with obstacles. Next, you will split the algorithm into several "threads" that accomplish the planning in parallel.
The map that you plan over is a simple plain text file. The first two items in the file are the X and Y dimensions of the map, the map follows. An `O' is an obstacle, a `G' is the goal (only one per map) and `S' is the starting point. Here is an example map:
10 10 OOOOOOOOOO O G O O O O O O O O OOOOOOOO O O O O O S O OOOOOOOOOO
The robot starts at the `S' and must navigate to the `G' by moving from cell to cell. Both lateral and diagonal moves are allowed, but you may never move through an `O'. Lateral moves cost 1.0 while diagonal moves cost sqrt(2.0). The optimal path minimizes the travel cost for the robot.
Step 1.
Write a program in Java to automatically generate random maps of arbitrary size and obstacle coverage. You will use these maps to test your path planner. Note that it is entirely possible to generate maps that cannot be solved.
Step 2.
Write a path planner in Java that takes a text map as input, computes a path (not necessarily the optimal path), and prints out the computed path and computation time. Here is an example output:
>java planner map.txt OOOOOOOOOO O G O O * O O * O O * O O*OOOOOOOO O * O O * O O ***S O OOOOOOOOOO 18989 microsecondsDo not include reading the map, printing the output or initializing variables and arrays in the timing. Only include the actual computation time.
Step 3.
OK this is the hard part. Revise your algorithm so that it is executed by several concurrent threads. The threads are activated at runtime, with the number of threads being given as an argument. The format of the output for this program should be identical to the earlier version.
Don't spend much time refining your program. We are more interested in your ability to analyze what you've done and suggest improvements than in writing perfect code. It is only necessary for your program to find "a" solution, not the optimal. Also, it is very likely that the parallel version of your program will find different solutions for the same map.
Step 4.
Gather data. Generate 10 100x100 random maps. Run your program on each map with 1, 2, 4, 8, 16, 32 and 64 threads. For each number of threads average the times and plot the results.
Bonus.
Run the same experiment on a multiprocessor Ultra using the latest JDK from Sun that supports parallel threads. You will need to contact Prof Schwan to get access to one of these machines. We do not anticipate you will have time to complete this step in the time allotted for the project, but if you have nothing else to do try it...
Background