A two level fuzzy PRM for manipulation planning

This paper presents an algorithm which extends the probabilistic roadmap (PRM) framework to handle manipulation planning. This is done by using a two level approach, a PRM of PRMs. The first level builds a manipulation graph, whose nodes represent stable placements of the manipulated objects while the edges represent transfer and transit actions. The actual motion planning for the transfer and transit paths is done by PRM planners at the second level. The approach is made possible by the introduction of a new kind of roadmap, called the fuzzy roadmap. The fuzzy roadmap contains edges which are not verified by a local planner during construction. Instead, each edge is assigned a number which represents the probability that it is feasible. Later, if the edge is part of a solution path, the edge is checked for collisions. The overall effect is that our roadmaps evolve iteratively until they contain a solution. The use of fuzzy roadmaps in both levels of our manipulation planner offers many advantages. At the first level, a fuzzy roadmap represents the manipulation graph and addresses the problem of having probabilistically complete planners at the second level. At the second level, fuzzy roadmaps drastically reduce the number of collision checks. The paper contains experimental results demonstrating the feasibility and efficiency of our scheme.