I forgot a very important point during the presentation. This work has been achieved in collaboration with: +Daeun Song and Young J. Kim from Ewha Womens University +Pierre Fernbach from PAL Robotics (LAAS CNRS at the time when the work was done) +Andrea Del Prete From Trento University +Nicolas Mansard from LAAS - CNRS Sincere apologies to them Also I mixed things up when I talked about presolve methods in Mixed Integer Programms. Presolve methods do not increase the complexity of the problem, on the contrary they remove variables and simplify the combinatorics (hence the comparison with guide-path planning approaches).