This paper addresses the problem of generating whole-body motions for a humanoid robot that must execute a certain task in an environment containing obstacles. The assigned task trajectory is deformable, and the planner may exploit this feature for finding a solution. Our framework consists of two main components: a constrained motion planner and a deformation mechanism. The basic idea is that the constrained motion planner attempts to solve the problem for the original task. If this proves to be too difficult, the deformation mechanism modifies the task using appropriate heuristic functions. Then, the constrained motion planner is invoked again on the deformed task. If needed, this procedure is iterated. The proposed algorithm has been successfully implemented for the NAO humanoid in V-REP.