This paper introduces a new method for planning safe motions for complex systems such as humanoid robots. Motion planning can be seen as a Semi-Infinite Programming problem (SIP) since it involves a finite number of variables over an infinite set of constraints. Most methods solve the SIP problem by transforming it into a finite programming one by using a discretization over a prescribed grid. We show that this approach is risky because it can lead to motions which violate one or several constraints. Then we introduce our new method for planning safe motions. It uses Interval Analysis techniques in order to achieve a safe discretization of the constraints. We show how to implement this method and use it with state-of-the-art constrained optimization packages. Then, we illustrate its capabilities for planning safe motions for the HOAP-3 humanoid robot.