Collision Detection and Path Planning

In the field of robotics, how to determine the optimal path to the destination is a critical problem because an optimal path can help to reduce energy consumption of the robot, bring down the risk of damage and so on. Label correcting algorithm is one of many algorithm designed for path planning. It can guarantee an optimal path. However, in practice, not only energy but also time is precious. In complicated cases, LCA and other methods based on it is still too slow to balance the time efficiency and other metrics. Therefore, some faster methods, like Rapid-exploring Random Tree, are proposed to boost the speed by providing a sub-optimal path. In this project, I implemented six algorithms, collision detection based on Minkowski difference and winding number, A, RRT, RRT, RRT-Connect and RRT*-Connect, to compare them with seven different environments and discussed their advantages and disadvantages. Link

Algorithm	Result	Time (s)
A*		3.85
RRT		0.47
RRT*		2.19
RRT-Connect		0.09
RRT-Connect*		1.21