We have done preliminary research on the algorithm and chose to slightly modify our project’s scope. Rather than do D* as we originally intended, we have decided to change the algorithm slightly to D* Lite. D* Lite is derived more from A* than from D*, but utilizes some of the same concepts in order to achieve the same goal.

So far, our main objectives have been to generate graphs to run our D* algorithm on as well as to get a D* Lite sequential algorithm running. In terms of generating graphs, we have managed to load random graphs as well as parse graphs that are pre-loaded in .txt files. We have also begun working on the graphics interface for the graphs in order to easily visualize the speed of our algorithm, depicted here:


We have obtained a copy of the D* Lite algorithm in C++ here, implemented as described here, and have done some preliminary measurements for the latency of sequential D* Lite.

We believe that the goals we stated in the proposal are achievable, and that the “nice to haves” in our proposal may be possible depending on hurdles we encounter in the next few weeks. As far as producing a parallel algorithm that runs on a CPU, we believe that it is possible and should be our main concern. Producing an algorithm that runs on a GPU will require some more time and analysis in order to compete in quality with the CPU algorithm, and so this may not be done by the due date. Other parts such as running it on a map/graph to note speedup are certainly possible, and will contribute to our final presentation.

We wish to have a parallel D* Lite algorithm that runs on a CPU, and a 2D map generator to act as our test harness. The 2D map generator’s graphical component will depend highly on how much time we have at the end (for polish). If we have extra time, we would also like to implement a parallel D* Lite algorithm to run on a GPU.

We plan to show our D* Lite algorithm running in real time on a pre-loaded graph alongside a sequential implementation of the algorithm. While we will also include graphs and analysis of the speedup on the parallel algorithm, the graphical component will most likely be the most visually appealing portion of our deliverable.

Time Taken to Traverse Randomly Generated Unknown Map:
25x25: 1.502~2.015 ms
25x101: 1.692~12.472 ms
101x101: 4.776~103.257 ms
201x201: 158.824~2586.648 ms

Issues that may arise include synchronization problems in the algorithm, as well as workload balancing. These issues are embedded in the parallelization of the D*Lite algorithm. The sooner these hurdles are overcome, the sooner we can make improvements to the presentation as well as possibly implementing a parallel algorithm for the GPU.

(4/18-4/22) SARAH will finish implementing the graphics interface and world generation to properly showcase our parallelized D* Lite algorithm. PETER will begin parallelizing D*Lite on the CPU using OpenMP.

(4/23-4/27) PETER will continue improving D* Lite concurrency and parallelism on CPU. SARAH will create the test harness.

(4/28-5/1) PETER will implement dynamic maps to run our algorithm on. SARAH will test D*Lite on variable graphs and check for best and worse case scenarios.

(5/1-5/4) SARAH and PETER will both debug and finetune the algorithm for possibly minor speedups.

(5/5-5/9) Final tests and data analysis. Write up final report. Prepare for the competition!

*We expect that if time permits, we will also port our CPU solution to GPU and improve performance on that platform.