Sample-based planners such as PRM and RRT (and a multitude of their extensions) have demonstrated remarkable success. But the “narrow passage problem” remains a signicant challenge for this family of algorithms. The reason is that, generally speaking, sample-based approaches use a strategy of sampling states in the whole conguration space, followed by collision checking. When a robot and an obstacle are found to be in collision, the corresponding sample is discarded. Then, valid state congurations are connected by edges, where each edge is sub-sampled and collision checking is done along the edge. If any of the states on the edge corresponds to a collision, the whole edge is discarded. This approach works extremely well when the obstacles in the environment are sparse. But when there is a narrow passage, an inordinate amount of computational time is spent on the samples and edges that eventually will be discarded.
Therefore this project is aimed to solve for the challenge of “narrow passage” problem by parameterizing the free space a priori, so that the safe configurations of a robot can be directly sampled without collision detection. The geometric fundamental is based on the closed-form characterization of Minkowski sums between an ellipsoid and a general body. The advantage of doing so is that the boundary of contact space between robot parts and environmental features can be evaluated in a very fast way, thereby allowing generating collision-free configurations efficiently.
The project starts from a simple configuration space SE(2), where the robot is assumed to be encapsulated by a single ellipse and only allowed to move in the plane. Then the spatial and multi-body cases are considered. The last part proposes a fast collision-free configuration generator that can compute a list of safe configurations as seeds for sampling-based planners. The spirit is to collaborate with stochastic algorithms to deal with high dimensional burdens.
Path planning has long been one of the major research areas in robotics, with PRM and RRT being two of the most effective path planners. Though they are generally very effcient, these two sample-based planners can become computationally expensive in the important special case of narrow passage problems. This paper develops a path planning paradigm which uses ellipsoids and superquadrics to respectively encapsulate the rigid parts of the robot and obstacles. The main benefit in doing this is that conguration-space obstacles can be parameterized in closed form, thereby allowing prior knowledge to be used to avoid sampling infeasible congurations, in order to solve the narrow passage problem effciently. Benchmark results for single-body robots show that, remarkably, the proposed method outperforms the sample-based planners in terms of the computational time in searching for a path through narrow corridors. Feasible extensions that integrate with sample-based planners to further solve the high dimensional multi-body problems are discussed, which will require substantial additional theoretical development in the future.
Project page
Presentation
Publication
(In preparation)