Multi-Robot Task Allocation (MRTA) Simulation

This repository contains the source code and the final report for my internship project at the Supervisory Control Group, Eindhoven University of Technology (TU/e). This project involves a custom-developed 2D simulator for the comparative analysis of various task allocation algorithms and supervisory control layers for multi-robot systems.

---

Table of Contents

• Abstract
• Features
• Requirements
• Installation & Setup
• How to Run
• Report
• Acknowledgements
• License

---

Abstract

Efficient task allocation in dynamic multi-robot systems presents a significant challenge, often forcing a trade-off between the theoretical optimality of centralized planners and the robustness of decentralized heuristics. This project presents a comprehensive empirical analysis of this trade-off, conducted within a custom-developed 2D simulation environment. We systematically evaluate the performance of three foundational task allocation algorithms—a myopic Greedy heuristic, the globally optimal Hungarian algorithm, and a decentralized Market-Based approach—under four distinct scenarios with varying spatial and temporal task distributions.

The core of our contribution lies in the implementation and analysis of advanced supervisory control layers designed to enhance these baseline algorithms. We demonstrate the critical role of a foundational safety supervisor (iSupCon) for preventing deadlocks, analyze the impact of a reactive Dynamic Task Swapping (DTS) layer, and introduce a novel, strategic Utility-based Supervisor whose parameters are systematically tuned using Bayesian Optimization. Our results reveal that the most effective strategy is not a single algorithm but a synergistic architecture that combines a flexible base-layer with an intelligent, adaptive supervisor.

---

Features

• Custom 2D Grid Simulator: Built from scratch in Python using the Pygame library for full control and flexibility.
• Custom 2D Grid Simulator: Built from scratch in Python and Pygame for full control.
• Multiple Task Allocation Algorithms:
  • Greedy Assignment: A fast, heuristic-based baseline.
  • Hungarian Algorithm: A globally optimal, centralized planner.
  • Market-Based Approach: A decentralized, auction-based mechanism.
• Advanced Supervisory Control Layers:
  • iSupCon: A foundational safety layer for collision and deadlock avoidance.
  • Dynamic Task Swapping (DTS): A reactive supervisor for on-the-fly re-assignment.
  • Utility-Based Supervisor: A strategic meta-controller that balances multiple objectives.
• Systematic Parameter Tuning:
  • Implementation of Bayesian Optimization to find the optimal weights for the Utility-based Supervisor.
• Diverse Experimental Scenarios: Four challenging scenarios were designed to test algorithms under varying conditions of spatial and temporal task distribution. The heatmaps below visualize the task density (spawn probability) for each scenario.

Scenario 1 (Uniform, Steady)	Scenario 2 (Uniform, Burst)
Scenario 3 (Clustered, Steady)	Scenario 4 (Clustered, Burst)

---

Requirements

This project is built with Python and relies on several key scientific and visualization libraries.

• Python Version: 3.9+
• Core Libraries:
  • pygame for the simulation and visualization engine.
  • numpy and scipy for numerical operations and core algorithms (like the Hungarian method).
  • matplotlib for generating the performance plots.
  • scikit-optimize for the Bayesian Optimization process.

---

Installation & Setup

1. Clone the Repository

git clone https://github.com/Trkkhrmn/Multi-Robot-Task-Allocation-Simulation.git
cd mrta-simulation

2. Set Up a Virtual Environment

1. Create the virtual environment

python -m venv venv

2. Activate the virtual environment

source venv/bin/activate # On macOS/Linux
venv\Scripts\activate # On Windows

3. Install Dependencies

pip install -r requirements.txt

---

How to Run

Running an experiment is straightforward. All you need to do is edit the configuration variables at the top of the main.py script and then run the file.

Configure Your Experiment

Open the main.py file in a text editor. At the very top, you will find the main configuration block:

# Choose the scenario to run (1-4)
# 1: Uniform Steady, 2: Uniform Burst, 3: Clustered Steady, 4: Clustered Burst
SCENARIO_ID_TO_RUN = 1

# Choose the main allocation algorithm
# Options: "Greedy", "Hungarian", "Market-Based", "Utility-Based"
ALGORITHM_CHOICE = "Greedy"

# Choose the supervisory layer
# Options: "iSupCon", "DTS", "NoSupervisor"
SUPERVISOR_CHOICE = "iSupCon"

Simply change the values of these three variables to set up the experiment you want to run.

Run the Script

Once you have configured the variables, save the main.py file and run it from your activated virtual environment's terminal:

python main.py

The simulation window will appear, and the results will be printed to the console upon completion.

Configuration Examples

Here are the variable settings for some of the key experiments from the report:

1. Example 1: Market-Based algorithm enhanced with DTS

SCENARIO_ID_TO_RUN = 4 # or any other scenario
ALGORITHM_CHOICE = "Market-Based"
SUPERVISOR_CHOICE = "DTS"

2. Example 2: The final, optimized Utility-based Supervisor

SCENARIO_ID_TO_RUN = 1 # or any other scenario
ALGORITHM_CHOICE = "Utility-Based"
SUPERVISOR_CHOICE = "None" # The Utility-Based supervisor has its own logic

---

Report

The complete analysis, methodology, results, and discussion of this project are detailed in the final report.

You can find the full PDF report on ResearchGate.

Permanent DOI Link: https://doi.org/10.13140/RG.2.2.16388.18560

---

Acknowledgements

This project was conducted under the supervision of Associate Professor Michel Reniers and Assistant Professor Martijn Goorden at the Supervisory Control Group, TU/e. I am deeply grateful for their invaluable guidance and support.

---

License

This project is licensed under the Creative Commons Attribution 4.0 International License. See the LICENSE file for more details.

Copyright (c) 2025, Tarık Kahraman

---