UC Santa Cruz

Motion planning is the task of finding a sequence of feasible motions for a robot to transform from an initial state to a goal state avoiding collisions. Modern motion planner algorithms for non-holonomic vehicles typically rely on graph search or sampling-based techniques. However, graph search methods quickly become ineffective as the computational complexity scale exponentially to map size. Sampling-based methods have the shortcomings of creating highly suboptimal paths or having high run-times. This thesis introduces a new hierarchical motion planner, LIDAR A*, that features an online visibility-based decomposition and search process. It incrementally analyzes regional maps with locally simulated 2D LIDAR scans to search for the shortest opening gateway sequence toward the goal. These sequential gateways are used to guide the simulation of a robust local motion planner to generate a smooth and kinematic friendly path. Experiments show this method significantly reduces the number of nodes minimizing computation time while generating a near-optimal path compared to the recently proposed RRT-based algorithms.