Beamlets

Beamlets constructs the beamlet graph used to solve shortest-path problems subject to curvature constraints. A beamlet is a line segment joining two points on the boundary of a dyadic square, so a recursive dyadic partition of the environment yields a multiscale dictionary of segments that carries orientation and elongation as well as scale and locality — properties that an isotropic cell decomposition cannot express. Searching over that dictionary rather than over cell adjacencies gives paths whose curvature can be constrained directly, because each edge of the graph is already a geometric segment with a direction.

The implementation builds the dyadic structure, the beamlet dictionary and the resulting graph, and is written in C++.

Reference

O. Arslan, P. Tsiotras and X. Huo, “Solving Shortest Path Problems with Curvature Constraints Using Beamlets,” IEEE/RSJ International Conference on Intelligent Robots and Systems, San Francisco, CA, Sept. 25–30, 2011, pp. 3533–3538. doi:10.1109/IROS.2011.6048546

Related work is described on the Multiresolution and Multiscale Methods for Control and Planning project page.

Visit the GitHub repository for the source code.