This repository contains source code to support our paper "Collaborative Task Allocation for Heterogeneous Multi-Robot Systems Through Iterative Clustering".
Multi-robot systems face the challenge of efficiently allocating teams of heterogeneous robots to tasks. The task allocation problem is complicated by collaborative interactions between robots where teams of robots developemergent capabilities that enable them to complete tasks that would be inefficient or impossible for individual robots. To address these challenges, we present an iterative clustering algorithm for collaborative task allocation in heterogeneous multi-robot systems. This approach partitions the computationally intractable global optimization problem into smaller, tractable subproblems by iteratively forming clusters of robots and tasks, then optimizing assignments within each cluster. By ensuring robots remain clustered with their currently assigned tasks, we guarantee monotonic improvement in overall utility with each iteration. We analyze the convergence of the algorithm and characterize how cluster size constraints determine which suboptimal assignments could trap the algorithm. In simulation, iterative clustering consistently outperforms simulated annealing, and a group-based auction in both computation time and solution quality, and outperforms a hedonic game approach in solution quality.
Create the conda environment:
conda env create -f environment.yml
conda activate icmrtaThe below scripts test how cluster size limits affect the performance of the algorithm.
To test cluster size effects on utility per iteration:
python tests/cluster_size_comparison_iterations.py
To test cluster size effects on utility over time:
python tests/cluster_size_comparison_time.py
For small-scale problems, the clustering methods can be directly compared against optimal solutions. The tests/iteration_optimal_compared.py script directly compares the solutions produced by iterative clustering against the optimal solution for 500 randomly generated problems with nu = 10 robots and mu = 5 tasks.
python tests/iteration_optimal_compared.py| Method | Exact Optimal Matches (%) | Average Utility Ratio (%) |
|---|---|---|
| Random Iterative Clustering | 99.6 | 99.9 |
| Heuristic Iterative Clustering | 99.0 | 99.9 |
To evaluate the iterative clustering algorithm's effectiveness on a larger problem with nu = 50 robots and mu = 25 tasks, the random and heuristic iterative clustering algorithms are compared against group-based auction, hedonic game, and simulated annealing approaches. Overall, heuristic clustering outperformed the other methods, closely followed by random clustering.
python tests/method_time_comparison.py
The scalability of both the random and heuristic iterative clustering algorithms is tested on four problem sizes with results averaged over 100 trials. Random clustering scaled more efficiently than heuristic clustering due to the computational cost of calculating the heuristics for cluster formation.
python tests/scalability_test.py