Theses and Dissertations

This project compared two optimization-based formulations for solving multi-robot task allocation problems with tether constraints. The first approach, or the ”Iterative Method,” used the common multiple traveling salesman (mTSP) formulation and implemented an algorithm over the formulation to filter out solutions that failed to satisfy the tether constraint. The second approach, named the ”Timing Formulation,” involved constructing a new formulation specifically designed account for robot timings, including the tether constraint in the formulation itself. The approaches were tested against each other in 10-city simulations and the results were compared. The Iterative Method could provide answers in 1- and 2-norm variations quickly, but its mTSP model formulation broke down and became infeasible at low city numbers. The 1-norm Timing Formulation quickly and reliably produced solutions but faced high computation times in its 2-norm manifestation. Ultimately, while the Timing Formulation is a more optimal method for solving tether-constrained task allocation problems, its reliance on the 1-norm for low computation times causes it to sacrifice some realism.