UC Santa Cruz

Many of the motion planning algorithms require decomposing free space into convex regions in order to derive piece-wise polynomial trajectories. Using a path found by a fast graph search technique as a piece-wise linear skeleton to obtain convex regions is an effective method. However, this type of method suffers from narrow polyhedrons in that waypoints are in close proximity to obstacles, and in turn, narrow polyhedrons as constraints of a quadratic program (QP) influence the optimal solution of trajectory generating. This thesis proposes a method of enlarging polyhedrons through utilizing Artificial Potential Field to optimize the path found by Jump Point Search. Owing to enlarged convex polyhedrons, simulation results show that in some obstacle-cluttered map, trajectories generated by QP using enlarged polyhedrons as constraints become smoother, and the value of minimum snap cost function is smaller compared with that without optimizing.