Skip to content Skip to navigation
Masters Defense
4/14/2017 04:30 pm

Optimize Paths For Hexagon-based Multi-agent Environment

Yang Yu, Computer Science

Defense Committee: Jingjin Yu(chair), Abdeslam Boularias, Kostas Bekris


Sometimes, there is enough space for two paths between convex obstacles. However, based on the shape of hexagon and obstacles, there may be only one path or no path between obstacles. I want to increase paths for such situations. This is useful especially when the map graph is not connected. There are two key points here. One is how to calculate the new paths. The other one is how to link the new paths to the original environment. For the first problem, the algorithm can determine the candidate edges to do the Minkovskisum and then take the new edges gotten from Minkovskisum as the new paths' trajectories. For the second problem, the intersection points between environment edges and new paths can be regarded as the candidate endpoints of new edges. And the system will pick the nearest points which is far enough from the other obstacles as the endpoints. In the implementation part, I use VisiLibity and boost libraries to help me make this algorithm a general algorithm, which means this algorithm can be applied regardless of the convex obstacles' number and shape.