In this paper, we investigate methods for motion planning for deformable robots. Our framework is based on a probabilistic roadmap planner. As with traditional motion planning, the planner’s goal is to find 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 inspired by physically correct behavior, but are more efficient than completely physically correct methods. Our approach can be applied in several domains, including flexible robots, computer modelling and animation, and biological simulations.