Parallelizing Maze Generation and Particle Filtering Proposal

We plan to parallelize random maze generation and particle filtering. Maze generation has a nice dual interpretation with graph search algorithms. Through openMP and MPI interface, we want to efficently implement maze generation using sequential and parallel graph algorithms. After creating a maze, particle filtering, a method to determine the location of a robot, will be used to navigate through this maze. The aim of this project is to identify axis of parallelism learned through tools developed from 15418

Background

There are many algorithms out there for maze generation, most of which are graph-based or recursive-division-based (https://en.wikipedia.org/wiki/Maze_generation_algorithm). Graph-based algorithms generally use stacks/queues to keep track of nodes that it has to visit. However, this strategy does not scale well for graphs with large depth. We plan to parallelize this graph-based generation, where multiple threads will generate parts of the maze while communicating with each other about the path they have generated, and the remaining paths. Why maze generation? Maze generation can be applied to random game developement and world generation.

The second part of our project deals with finding an entry/exit from the maze from the perspective of a robot if it exists. The robot would be able to get a 360-degree view from its current position learn it's location. To implement this, we assume that the robot knows the entire map space, and it's relative observations of its current location, but does not know it's absolute location. In this view, we can represent the robot initially being in a uniform distribution of all locations. This is known as particle filtering. First, we transition each particle uniformly at random. Next the robot itself takes a snapshot of it's relative location. This could include features such as how many walls there are, which direction are the walls located, etc... Finally, we update our belief on where the particles are and resample based on that distribution. The whole process repeats until we figure out where the robot lies with high probability. Particle filtering is used in roombas, a self-service cleaning robot in common households.

The Challenge

For the maze generation, the complexity lies in the tradeoff between communication/computation and correctness for graph-based algorithms. In this case, the ‘correct’ answer should allow the maze to converge to a solution quickly, but communicating the track of visited paths, and calculating new paths over a graph would be challenging. For OpenMP, we could just provide the ‘root’ node of the visited path to other path generators, but the challenge would increase with MPI. Moreover, the generators should avoid traversing the same path more than once, or generating paths that are next to each other. In terms of locality, as we move in a DFS or as we are backtracking, we could lose locality, since the graph as we move downwards in the y-axis, we could move out one cache line. We will carefully consider the options on how to reduce this with our graph generator.

Particle filtering has inherent parallelsim to transition and update the probabilites of every particle. However, there are implicit synchronization barriers so that one particle sample isn't ahead of another particles sample. Furthermore, there isn't a clear way to parallelize how the robot will move once it determines its location. Instead, we may want to add multiple robots in the maze

The Wikipedia page provides some high-level references on different generation algorithms. We plan to backtrack from the page and find out the original citations for the maze generators. Unfortunately, most references weren’t linked at the bottom of the Wiki page. We plan to use the provided sequential implementations as a baseline.

For particle filtering, we will refer to these slides courtesy of MIT. These slides outline the basic algorithm for particle filtering

We plan to use the GHC machines for most of our development tasks. We would largely benefit from using the PSC machines, so we can run on higher thread counts, and witness large parallelism and faster generation/traversal, or work with larger mazes.

Goal 1: Maze Generation
The user will be able to see the maze being generated in real-time with increasing thread counts on both openMP and MPI.
Goal 2: Robot traversal
The user will be able to see the robot ‘figure’ a path in the maze. The movement of the robot will be faster with increasing thread counts.
Goal 3: Multi-robot traversal (speculative)
Mulitple robots will traverse the graph and finally converge on a path if one exists. In the case of multiple paths, there will be a tie-breaker.

OpenMP and MPI are good choices since we have a good balance of communication/communication between the generators and finding the path for a robot. We considered CUDA, but the task pool for random maze generation isn't large enough to warrant the creation of many CUDA threads. In addition, we don’t expect graphic intense issues for our program. If we did some type of block-based graph generator, CUDA might be useful, or if our graph was really really huge. However, we may consider the use of CUDA for our particle generator since each particle may have its own thread.