High Clearance Collision-Free Paths

Path Planning is one of the widely investigated research areas in computational geometry and robotics. Given a set of polygonal obstacles inside a rectangular box, and start & goal points, the path planning problem is to construct a collision-free path connecting the start point to the goal point. We review existing well known algorithms for solving the path planning problem. We propose new approaches for constructing a collision-free path with high clearance from obstacles. The main idea of the proposed algorithm is the appropriate generation free-region nodes which can be processed to construct high clearance paths. Neighbors of free-region nodes are carefully joined to obtain a connected graph outside the obstacles. Standard graph searching algorithms are applied in the constructed connected graph to obtain high-clearance paths. We also present methods to remove a few free-region nodes to further increase clearance from obstacles. Finally, we present experimental results on the construction of high-clearance collision-free paths