  Path planning has long been one of the major research areas in robotics, with
PRM and RRT being two of the most effective classes of path planners. Though
generally very efficient, these sampling-based planners can become
computationally expensive in the important case of "narrow passages". This
paper develops a path planning paradigm specifically formulated for narrow
passage problems. The core is based on planning for rigid-body robots
encapsulated by unions of ellipsoids. The environmental features are enclosed
geometrically using convex differentiable surfaces (e.g., superquadrics). The
main benefit of doing this is that configuration-space obstacles can be
parameterized explicitly in closed form, thereby allowing prior knowledge to be
used to avoid sampling infeasible configurations. Then, by characterizing a
tight volume bound for multiple ellipsoids, robot transitions involving
rotations are guaranteed to be collision-free without traditional collision
detection. Furthermore, combining the stochastic sampling strategy, the
proposed planning framework can be extended to solving higher dimensional
problems in which the robot has a moving base and articulated appendages.
Benchmark results show that, remarkably, the proposed framework outperforms the
popular sampling-based planners in terms of computational time and success rate
in finding a path through narrow corridors and in higher dimensional
configuration spaces.
