Project Website
This website contains materials for our 15-418/15-618 final project.
Project Overview
We are going to study parallelization strategies for multi-agent path planning in a simplified robotic manipulation setting, where multiple fingers of a robotic hand must move from start nodes to designated goal nodes without colliding. Our original plan centered on CBS, but our current implementation has shifted toward a greedy repair planner because exact CBS was too expensive for the benchmark regime we want to study. We now have a working sequential baseline, an OpenMP top-K parallel version, benchmark infrastructure, and SVG visualization for comparing behavior and scalability.
Current Status and Revised Schedule
Completed so far: benchmark generation, collision detection, space-time A*, greedy repair baseline, OpenMP top-K repair evaluation, correctness tests, benchmark text output, and SVG visualizations. The main change from the proposal is that we are no longer using traditional CBS as the active baseline, because it was not practical on our target instances.
- Apr 14 - Apr 17: finalize milestone report and design batched multi-commit repair (Dylan, Jongsun)
- Apr 18 - Apr 21: implement disjoint-conflict batching and greedy subset commit (Dylan, Jongsun)
- Apr 22 - Apr 25: run PSC experiments and compare sequential vs parallel versions (Dylan, Jongsun)
- Apr 26 - Apr 29: generate poster figures, including SVG examples and speedup graphs (Dylan, Jongsun)
- Apr 30 - May 3: polish poster and final report narrative around correctness vs scalability (Dylan, Jongsun)