A Non-uniform Sampling Approach for Fast and Efficient Path Planning
This work addresses path planning efficiency for autonomous vehicles, representing an incremental improvement by integrating a novel sampling method into an existing planner.
The paper tackles the problem of slow and inefficient path planning for autonomous vehicles by developing a non-uniform sampling approach that reduces sampling space size and eliminates collision-checking, resulting in a significantly better convergence rate and smaller memory footprint compared to standard uniform sampling in RRT*.
In this paper, we develop a non-uniform sampling approach for fast and efficient path planning of autonomous vehicles. The approach uses a novel non-uniform partitioning scheme that divides the area into obstacle-free convex cells. The partitioning results in large cells in obstacle-free areas and small cells in obstacle-dense areas. Subsequently, the boundaries of these cells are used for sampling; thus significantly reducing the burden of uniform sampling. When compared with a standard uniform sampler, this smart sampler significantly 1) reduces the size of the sampling space while providing completeness and optimality guarantee, 2) provides sparse sampling in obstacle-free regions and dense sampling in obstacle-rich regions to facilitate faster exploration, and 3) eliminates the need for expensive collision-checking with obstacles due to the convexity of the cells. This sampling framework is incorporated into the RRT* path planner. The results show that RRT* with the non-uniform sampler gives a significantly better convergence rate and smaller memory footprint as compared to RRT* with a uniform sampler.