NEST Lab

Overview

This project focused on coordinating swarms of robots in large-scale scenarios, such as search and rescue. In these environments, no single robot can cover the entire area, making efficient task distribution essential. The problem was modeled as a Multiple Traveling Salesman Problem (mTSP), where a homogeneous swarm of robots had to complete a set of tasks while minimizing the total travel distance. To address this, a Mixed Integer Linear Programming (MILP) solver was used, providing an exact method for finding the optimal task allocation. The work set out to benchmark MILP’s performance and examine how its computation scales with the number of robots and tasks.

Approach

The problem was formally represented on a grid, with robots beginning at a start location, completing assigned tasks, and finishing at an endpoint. A set of tensors was defined to encode robot routes, costs, and task assignments under strict constraints to ensure that tasks were only visited once, robots did not form subtours, and all start and end conditions were respected. This formulation was implemented in MATLAB, where the decision and cost tensors were vectorized and solved using MILP optimization. To test scalability, experiments varied both the number of tasks (1–10) and robots (1–10), with each configuration repeated 10 times across randomized environments to avoid bias. Performance was evaluated by measuring average runtime and its variance, with results visualized using heatmaps to reveal underlying trends.

Results

The MILP solver consistently generated optimal schedules across all tested cases, validating its role as a reliable benchmark for multi-robot task allocation. However, the analysis showed that computation time increased super-linearly as the number of tasks or robots grew, with heatmaps revealing distinct inflection points where complexity rose sharply. While MILP guarantees optimal solutions, it does not scale well to larger swarms, making it impractical for real-time or large-scale deployments. The findings highlight the importance of alternative approaches, such as heuristic methods or neural network–based schedulers. This project not only provided a detailed characterization of MILP for MRTA but also established a baseline for comparing future algorithms.

Paper

Download Paper