  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 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. Each environmental feature is represented
geometrically using a strictly convex body with a $\mathcal{C}^1$ boundary
(e.g., superquadric). 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 needing to perform traditional collision detection.
Furthermore, by combining with a 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 the proposed framework often outperforms the sampling-based planners
in terms of computational time and success rate in finding a path through
narrow corridors for both single-body robots and those with higher dimensional
configuration spaces. Physical experiments using the proposed framework are
further demonstrated on a humanoid robot that walks in several cluttered
environments with narrow passages.
