Energy efficient multi-robot coordination

When multiple systems work in the same physical environment, it is important to ensure that no collisions occur. This thesis is focused on the centralized offline coordination of such collaborating systems, with the condition that the spatial path each system travels along is known before hand. In addition to collisions, dynamic constraints as well as optimization of a performance criterion are considered.<br /><br />The problem is decomposed into two parts, a sequencing problem and coordination subproblem. For the sequencing problem, an algorithmic improvement is proposed, where constraint propagation methods from the computer science community are introduced to improve existing mixed integer nonlinear programming methods used in mathematical programming. The coordination subproblem on the other hand is approached from a modeling perspective. By applying state space discretization and variable changes, two models are derived, one which is entirely convex. Also, a two stage abstraction approach is introduced, where dynamic programming is used to parameterize part of the problem, resulting in a much simpler model at the next stage.<br /><br />The above methods can be used for minimum energy coordination of industrial robots. Experimental results from the two robot case study are presented. In addition, the one robot case is also studied, where the execution time, robot payload and minimization criteria are varied. Furthermore, the application of the presented methods to hybrid systems is also discussed.<br /><br />Finally, the slightly different problem of minimum time stacker crane scheduling is considered. In the stacker crane problem, a number of tasks should be allocated to a set of robots moving along the same one dimensional track. Although the exact spatial path is unknown in the stacker crane problem, it is shown that in a minimum time setting, it is still possible to use state space discretization