A case study of disjunctive programming: Determining optimal motion trajectories for a vehicle by mixed-integer optimization

Abstract: This report considers an application of mixed-integer disjunctive programming (MIDP)where a theoretical robot can jump from one point to another and where the number ofjumps is to be minimized. The robot is only able to jump to the north, south, east andwest. Furthermore, the robot should also be able to navigate and jump around or across anypotential obstacles on the way. The algorithm for solving this problem is set to terminatewhen the robot has reached a set of end coordinates. The goal of this report is to find amethod for solving this problem and to investigate the time complexity of such a method.The problem is converted to big-M representation and solved numerically. Gurobi is theoptimization solver used in this thesis. The model created and implemented with Gurobiyielded optimal solutions to problems of the form above of varying complexity. For most ofcases tested, the time complexity appeared to be linear, but this is likely due to presolvingperformed by Gurobi before running the optimization. Further tests are needed to determinethe time complexity of Gurobi’s optimization algorithm for this specific type of problem.