Probabilistic Roadmap Motion Planning for Deformable Objects¤

In this paper, we investigate methods for motion plan-ning for deformable robots. Our framework is based on a probabilistic roadmap planner. As with traditional motion planning, the planner's goal is to ¯nd a valid path for the robot. Unlike typical motion planning, the robot is allowed to change its shape (deform) to avoid collisions as it moves along the path. We propose a two-stage approach. First an `approximate ' path which might contain collisions is found. Next, we attempt to correct any collisions on this path by deforming the robot. We propose and analyze two methods for performing the deformations. Both techniques are in-spired by physically correct behavior, but are more e±cient than completely physically correct methods. Our approach can be applied in several domains, including °exible robots, computer modelling and animation, and biological simula-tions.