Various projects and musings by Mason Smith
In classical motion planning, one tries to compute paths between components in the configuration space of a known environment. For the special case of point objects in a polygon environments, one can use cellular decomposition, a roadmap technique, for path planning. This project, implemented jointly with Chunche Peng and Lea Kunesh, was a C++/MATLAB implementation of vertical cellular decomposition (VCD).
The project was split up as follows:
The code will be uploaded soon.
We implemented the algorithm largely as specified in Planning Algorithms, by LaValle in C++. We used the A* algorithm, implemented in MATLAB, to search the constructed roadmap. The interactive visualization is also programmed in MATLAB.
The VCD algorithm requires the environment to be in general position. Specifically, no two points can share the same x-coordinate. This could be alleviated by adding random deltas to every x-coordinate in the program, but this correction is not present in our implementation.