A Two Level Fuzzy PRM
Christian L. Nielsen, Lydia E. Kavraki · 2000
This paper presents an al~~orithm iuhich e:ctends the piabahilastic roadnimp (PRM) framework to h2andle manipulataon plnnnin,g. This is done by using a two level approrich, a PRM of PRMs. The first level builds a m,anipulatiors graph, whose nodes represent stable placements of the manipiilated objects while the edges repres:aent tramfer and transit actions. The actual motion plnnming for th.e tran,sfer and transit path.s is done hj PRM plannw-s 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 whach, are not verified by a local planner during con,struction. Instead, each edge is assigned a mniber which, represents the probability that it is feasible. Later, if the edge is part of a solution, path, the ed.9e is checked for collisions. The oile~all effect is that our roadmaps evolve iteratively untd they con,taan a solution. Th,e use of fuzzy roadmaps in, both, levels of our manipulation, planner oflers many advantages. At the first level, a fuzzy roadmap represents the manvpiilation graph, and addresses the problem of having probnbilisticallg complete plann,ers at the second level. At the second level, fuzzy roadm4aps drastically reduce the number of collision ch,ecks. The paper contains experimental rcm1t.F demonstratin.g the fea:nsabilat?J and eficienq of our scheme.