Distributed Market-Based Task Allocation for Swarm Robotics

EPFL ENG-466: Distributed Intelligent Systems (Final Project)

This repository contains the simulation codebase and modeling scripts for a multi-robot task allocation system. The scenario involves a heterogeneous team of rescue robots tasked with providing medical or psychological support to victims in an obstructed post-disaster environment.

The project explores and evaluates Centralized and Fully Distributed market-based coordination strategies under strict battery and communication constraints.

Key Features

• Decentralized Coordination (Gossip Protocol): In the distributed architecture, robots self-allocate tasks without a central auctioneer. We implemented a multi-hop gossip protocol with a Time-To-Live (TTL) mechanism and history buffers to achieve local consensus and resolve bidding conflicts while avoiding broadcast storms.
• Multi-Step Task Planning: To optimize efficiency, robots utilize an A* pathfinding algorithm over a custom visibility graph. This is combined with a cheapest-insertion heuristic (an online Traveling Salesperson Problem approximation) to let robots chain multiple tasks together dynamically.
• Cost-Aware Bidding: Robots bid on tasks based on a custom cost function that accounts for path distance, robot-task specialization matching, and remaining battery life.
• Multi-Level Modeling: Alongside the submicroscopic Webots simulation, the repository includes Python models abstracting the system into Microscopic (Probabilistic Finite State Machine) and Macroscopic (difference equations) levels to validate population dynamics and battery depletion rates.

Tech Stack

• C++ (C++17): Robot controllers, A* path planning, and peer-to-peer communication logic.
• Webots: 3D physics simulation and environment.
• Python: Data analysis and multi-level mathematical modeling.

Repository Structure

• /controllers/ - C++ source code for the Webots controllers.
  • epuck_cent / supervisor_cent: Centralized auctioneer and bidder logic.
  • epuck_dist / supervisor_dist: Distributed peer-to-peer gossip and self-allocation logic.
  • common/: Shared logic including the A* planner, geometry, and communication structs.
• /worlds/ - Webots environment files (project4.wbt).
• /Modeling/ - Python scripts for macroscopic and microscopic validation.
• /protos/ - Custom E-puck robot and environment definitions.

How to Run

1. Ensure Webots is installed on your system.
2. Clone this repository.
3. Open worlds/project4.wbt in Webots.
4. Compile the controllers (either via the Webots IDE built-in compiler or by running make in the respective controller directories).
5. Run the simulation. You can switch between Centralized and Distributed architectures by changing the assigned controllers in the Webots scene tree.