FURI | Spring 2022

Optimal Task-Allocation Algorithms for Multi-Tethered (MuTheR) Robots: Traditional Versus Timing Formulation

This project compared two optimization-based formulations for solving multi-robot task allocation problems with tether constraints. The first method used the common multiple traveling salesman formulation and implemented an algorithm over the formulation to filter out solutions that failed to satisfy the tether constraint, while a new formulation — the Timing Formulation — was designed to specifically account for robot timings, including the tether relations as formal constraints. After testing the models in 10 city simulations, the Timing Formulation was found to find more optimal solutions at the exchange of greater computation time.