  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.
