Thesis Project - Dynamic Task Reassignment

This repository contains a ROS 2 based multi-agent bidding system for dynamic task reassignment. The project implements a distributed bidding agent architecture where heterogeneous drones can bid on tasks (including combo bids for task sequences) and coordinate task allocation through a decentralized auction mechanism.

Overview

The system consists of:

• Bidder Agent: Core ROS 2 node that manages bidding logic, task processing, fault handling, precondition enforcement, and communication
• Bid Calculator: Computes bid values for single tasks, task sequence permutations, and insertion-based marginal-cost bids. Supports precondition-aware slot constraints when inserting new tasks into existing schedules
• Assignment Solver: Exhaustive backtracking solver that finds the optimal set of non-overlapping bids maximizing task coverage (primary) and minimizing makespan (secondary), with precondition constraint validation
• Bid Storage Manager: In-memory storage (using std::unordered_map) for bid entries, task details, and assignment tracking
• Path Planner: Polymorphic path planning with support for different drone types (Multirotor, Fixed-Wing) via PathPlannerFactory. Integrates environment data (mission area, no-fly zones)
• Simulator: Time-stepped movement simulation with trapezoidal velocity profiles and remaining operation time countdown
• Drone Status: Tracks drone state, position, speed, remaining operation time, capabilities, current task assignments, and scheduled position (effective start position for bid cost estimation)
• Config Loader: YAML-based configuration system for heterogeneous drone fleets
• Publisher / Subscriber: ROS 2 pub/sub layer handling bids, tasks, drone status, simulation ticks, fault injection, initial assignments, environment data, and simulation restarts
• Custom ROS 2 Messages: Task, Bid, DroneStatus, Environment, FaultInjection, RestartSim, SimTick, InitAssignment, RequestAssignment

Drone Fleet Configuration

The system supports heterogeneous drone swarms with different capabilities. Drone configurations are defined in config/drone_config.yaml:

drone_configs:
  - config_id: "multirotor_big"
    type: "multi_rotor"
    max_operation_time_sec: 5400.0
    min_remaining_operation_time_after_bid_sec: 1800.0
    critical_remaining_operation_time_sec: 600.0
    movement_speed_mps: 10.0
    acceleration_mps2: 2.0
    capabilities: ["gps", "camera", "thermal"]

  - config_id: "multirotor_small"
    type: "multi_rotor"
    max_operation_time_sec: 5400.0
    min_remaining_operation_time_after_bid_sec: 1800.0
    critical_remaining_operation_time_sec: 600.0
    movement_speed_mps: 10.0
    acceleration_mps2: 3.0
    capabilities: ["gps", "camera"]

  - config_id: "fixed_wing"
    type: "fixed_wing"
    max_operation_time_sec: 9000.0
    min_remaining_operation_time_after_bid_sec: 1800.0
    critical_remaining_operation_time_sec: 600.0
    movement_speed_mps: 15.0
    acceleration_mps2: 1.0
    capabilities: ["gps", "camera"]

Drone Types

• multi_rotor: Can hover, fly direct paths, suitable for precision tasks
• fixed_wing: Higher speed and efficiency, but cannot hover (turning radius constraints, Dubins-like path estimation)
• vtol: Hybrid capabilities (currently uses multirotor path planner)

Configuration Parameters

Parameter	Description
config_id	Unique identifier for this drone configuration
type	Drone type: multi_rotor, fixed_wing, or vtol
max_operation_time_sec	Maximum operation time budget in seconds
min_remaining_operation_time_after_bid_sec	Minimum operation time that must remain after a bid is accepted (reserve buffer)
critical_remaining_operation_time_sec	Operation time threshold below which the drone is considered critically low
movement_speed_mps	Cruise speed in meters per second
acceleration_mps2	Acceleration in meters per second squared
capabilities	List of capabilities: gps, camera, thermal

Requirements

System Requirements

• Operating System: Linux (Ubuntu 22.04 recommended)
• ROS 2: Humble Hawksbill or compatible version
• CMake: Version 3.16 or higher
• C++ Compiler: C++17 compatible (GCC 9+ or Clang 10+)

ROS 2 Dependencies

# Core ROS 2 packages
sudo apt install ros-humble-rclcpp
sudo apt install ros-humble-std-msgs
sudo apt install ros-humble-geometry-msgs
sudo apt install ros-humble-unique-identifier-msgs
sudo apt install ros-humble-rosidl-default-generators

System Libraries

# fmt library for string formatting
sudo apt install libfmt-dev

# Boost libraries (filesystem, program_options, system, uuid)
sudo apt install libboost-all-dev

# yaml-cpp for configuration loading
sudo apt install libyaml-cpp-dev

Python Dependencies (for testing tools)

# Ensure Python 3 and pip are installed
sudo apt install python3 python3-pip

# ROS 2 Python client library (usually installed with ROS 2)
sudo apt install ros-humble-rclpy

Additional Setup

Correct Git History to ignore pure formatting commits in git blame

git config blame.ignoreRevsFile .git-blame-ignore-revs

Installation

1. Install All Dependencies

# Install system dependencies
sudo apt update
sudo apt install -y \
    cmake \
    build-essential \
    libfmt-dev \
    libboost-all-dev \
    libyaml-cpp-dev

# Install ROS 2 dependencies (assuming ROS 2 Humble is already installed)
sudo apt install -y \
    ros-humble-rclcpp \
    ros-humble-std-msgs \
    ros-humble-geometry-msgs \
    ros-humble-unique-identifier-msgs \
    ros-humble-rosidl-default-generators \
    ros-humble-rclpy

2. Source ROS 2 Environment

source /opt/ros/humble/setup.bash

3. Build the Project

# From project root directory
mkdir -p build
cd build
cmake ..
make

Running the Application

Start the Simulation Clock

The simulation clock must be running for drones to process ticks and move. Start it before launching agents:

# Default: 10 Hz tick rate, 1x real-time speed
python3 tools/sim_clock.py

# Custom tick rate and speed
python3 tools/sim_clock.py --rate 20 --speed 2.0

# Non-interactive mode (for scripts/background use)
python3 tools/sim_clock.py --no-interactive

Interactive controls (while running):

Key	Action
p	Pause / Resume simulation
s	Step one tick (while paused)
+	Increase speed by 0.5×
-	Decrease speed by 0.5×
r	Reset simulation time to 0
q	Quit

Start a Single Agent

# Source ROS 2 environment
source /opt/ros/humble/setup.bash

# Run from build directory with default configuration (multirotor_small)
cd build
./drone_agent

# Run with a specific drone configuration
./drone_agent --ros-args -p drone_config_id:=multirotor_big -p config_file:=drone_config.yaml

Start a Drone Swarm

Use the provided launch script to start multiple agents with different configurations:

# Make the script executable (first time only)
chmod +x launch/launch.sh

# Start all configured drones (runs in background)
./launch/launch.sh

# Check status of running agents
./launch/launch.sh status

# Stop all running agents
./launch/launch.sh stop

The launch script reads drone configurations from config/drone_config.yaml and spawns one agent per configuration. Edit the DRONE_CONFIGS array in the script to change which drones are launched. Log files are written to /tmp/drone_agent_pids/.

ROS 2 Parameters

Parameter	Type	Default	Description
drone_config_id	string	"multirotor_small"	ID of drone config to load from YAML
config_file	string	"drone_config.yaml"	Name of the configuration file

Testing Tools

Python scripts are provided in the tools/ directory for testing the system.

Publish Tasks

# Publish a single task with defaults
python3 tools/publish_task.py

# Publish with custom values
python3 tools/publish_task.py --type go_to --goal-x 50 --goal-y 100 --goal-z 15

# Publish multiple tasks (goal coordinates are offset per task)
python3 tools/publish_task.py --count 5

# Custom capabilities and state
python3 tools/publish_task.py --capabilities camera gps --state pending

Publish Bids

# Publish a single random bid
python3 tools/publish_bid.py

# Publish with specific values
python3 tools/publish_bid.py --value 100.0

# Publish multiple bids
python3 tools/publish_bid.py --count 5

# Publish a combo bid for multiple tasks (sequence)
python3 tools/publish_bid.py --task-ids "UUID1" "UUID2"

Simulation Clock

# Start the simulation clock (required for drone movement)
python3 tools/sim_clock.py

# Custom settings
python3 tools/sim_clock.py --rate 20 --speed 2.0

Custom Message Definitions

Task.msg

unique_identifier_msgs/UUID task_id
string task_type
geometry_msgs/Vector3 goal_location
string[] capability_requirements
string current_state
unique_identifier_msgs/UUID[] precondition_task_ids
unique_identifier_msgs/UUID route_predecessor_task_id

Bid.msg

# Supports single-task and combo (multi-task sequence) bids
unique_identifier_msgs/UUID agent_id
unique_identifier_msgs/UUID[] task_ids
float64[] seconds_to_complete    # Estimated completion time for each sub-combo
float64 bid_value
int32 total_bids_from_agent      # Used for early assignment trigger

DroneStatus.msg

unique_identifier_msgs/UUID drone_id
geometry_msgs/Vector3 current_location
float32 average_speed
float32 current_speed
string drone_type
string current_state
string[] capabilities
unique_identifier_msgs/UUID current_task_id
unique_identifier_msgs/UUID[] task_backlog
int32 battery_level

SimTick.msg

float64 sim_time           # Total elapsed simulation time in seconds
float64 delta_time         # Time since last tick in seconds
uint64 tick_count           # Monotonic tick counter
float64 time_scale          # Simulation speed multiplier (1.0 = real-time)

InitAssignment.msg

unique_identifier_msgs/UUID drone_id
Task[] tasks

RequestAssignment.msg

bool make_assignment
int32 num_tasks
uint64 rng_key
bool use_capabilities
bool use_dependencies

Environment.msg

string environment_type         # Mission Area, No-Fly-Zone (Polygon), No-Fly-Zone (Circle)
geometry_msgs/Vector3[] vectors # Mission Area: 2 vectors (min/max), Polygon: N vertices, Circle: 1 center
float64 radius                  # For No-Fly-Zone (Circle)

FaultInjection.msg

unique_identifier_msgs/UUID drone_id
bool fault

RestartSim.msg

bool restart_simulation

ROS 2 Topics

Topic	Message Type	Direction	Description
/tasks	thesis_project/msg/Task	Pub & Sub	Task announcements and state updates (pending, unplanned, assigned, in_progress, completed, failed)
/bids	thesis_project/msg/Bid	Pub & Sub	Agent bids on tasks (single-task and combo bids)
/drone_status	thesis_project/msg/DroneStatus	Pub & Sub	Drone status broadcast (1 Hz); subscribed to track active drones for early assignment trigger
/sim_tick	thesis_project/msg/SimTick	Sub	Simulation clock ticks driving movement and task processing
/init_assignment	thesis_project/msg/InitAssignment	Sub	Initial task assignments at simulation start
/environment	thesis_project/msg/Environment	Sub	Mission area and no-fly zone definitions
/fault_injection	thesis_project/msg/FaultInjection	Sub	Inject drone failures for resilience testing
/restart_sim	thesis_project/msg/RestartSim	Sub	Reinitialize all agents and clear state

Project Structure

├── CMakeLists.txt              # Main CMake configuration
├── package.xml                 # ROS 2 package manifest
├── cmake_settings.cmake        # Build type and compile_commands.json settings
├── depends.cmake               # Dependency configuration (Boost, ROS 2, fmt, yaml-cpp)
├── sources.cmake               # Source file definitions
├── compile_commands.json       # Compilation database (symlink to build/)
├── .clang-format               # Code formatting configuration
├── .git-blame-ignore-revs      # Git blame ignore list for formatting commits
├── .gitignore                  # Git ignore rules
├── config/                     # Configuration files
│   └── drone_config.yaml       # Drone fleet definitions
├── launch/                     # Launch scripts
│   └── launch.sh               # Shell script to launch/stop/status drone swarm
├── msg/                        # Custom ROS 2 message definitions
│   ├── Task.msg
│   ├── Bid.msg
│   ├── DroneStatus.msg
│   ├── Environment.msg
│   ├── FaultInjection.msg
│   ├── InitAssignment.msg
│   ├── RequestAssignment.msg
│   ├── RestartSim.msg
│   └── SimTick.msg
├── src/                        # C++ source files
│   ├── main.cpp                    # Entry point, ROS 2 parameter handling, config file discovery
│   ├── bidder_agent.cpp/hpp        # Core agent node (task processing, fault handling, precondition enforcement, assignment)
│   ├── assignment_solver.cpp/hpp   # Exhaustive backtracking solver for task-to-drone assignment with precondition validation
│   ├── bid_calculator.cpp/hpp      # Bid computation for single tasks, task permutations, and insertion-based marginal-cost bids
│   ├── bid_storage_manager.cpp/hpp # In-memory bid/task storage and assignment tracking
│   ├── drone_status.cpp/hpp        # Drone state, position, battery, capabilities, scheduled position management
│   ├── config_loader.cpp/hpp       # YAML drone configuration loader
│   ├── path_planner.cpp/hpp        # Polymorphic path planners (Multirotor, FixedWing) + factory
│   ├── publisher.cpp/hpp           # ROS 2 publishers (drone status, bids, task state changes)
│   ├── subscriber.cpp/hpp          # ROS 2 subscribers (bids, tasks, drone status, sim ticks, environment, faults, init assignments, restarts)
│   ├── simulator.cpp/hpp           # Movement simulation with trapezoidal velocity profiles + factory
│   ├── logger.hpp                  # Thread-safe colored logging with file output support
│   └── utils.hpp                   # Enums (TaskState, DroneState, DroneType, Capability, TaskType), structs (Point, Task, Bid, SimTick, MissionArea, NoFlyZonePoly, NoFlyZoneCirc), helper functions
├── tools/                      # Python testing tools
│   ├── publish_task.py             # Publish demo tasks to /tasks
│   ├── publish_bid.py              # Publish demo bids to /bids
│   ├── sim_clock.py                # Interactive simulation clock publisher
│   ├── cpp_template/               # C++ template files
│   └── network_monitor_app/        # Network monitoring application
└── build/                      # Build output directory

Architecture

Bidding and Assignment

The system implements a decentralized auction-based task allocation:

1. Task Reception: When tasks arrive on /tasks, each agent calculates bids for all permutations of the task batch (single tasks and sequences up to a configurable max combo size). If the drone already has assigned tasks, insertion-based bidding is used to compute marginal costs of adding new tasks into the existing schedule
2. Bid Calculation: The BidCalculator uses the drone's PathPlanner to estimate completion time for each task sequence from the drone's effective start position (last scheduled task's destination, or current GPS position if idle). Drones missing required capabilities produce infinite-cost bids. Precondition constraints are respected when generating permutations and determining valid insertion slots
3. Bid Exchange: Bids are published on /bids (including a total_bids_from_agent count) and all agents store received bids in their local BidStorageManager
4. Assignment Solving: An early trigger fires when all active drones (tracked via /drone_status subscriptions) have reported their bid counts and all expected bids have been received. A 20-second timeout acts as a safety fallback. The AssignmentSolver uses exhaustive backtracking search that maximizes task coverage (primary) and minimizes makespan (secondary), with pruning optimizations and precondition constraint validation
5. Task Execution: Assigned tasks are executed sequentially, respecting precondition ordering (tasks whose preconditions are not yet completed are deferred). The Simulator moves the drone toward each goal location using trapezoidal velocity profiles

Path Planning

The system uses polymorphic path planners to support different drone types:

• PathPlanner (base class): Euclidean distance-based time and energy estimation
• MultirotorPathPlanner: Direct-path planning for multirotors (can hover, fly straight lines)
• FixedWingPathPlanner: Accounts for turning radius constraints using Dubins-like path estimation ($R = v^2 / (g \cdot \tan(\theta))$ with 45° max bank angle)

The appropriate planner is automatically selected based on drone type via PathPlannerFactory.

Simulation

The system uses a centralized simulation clock (sim_clock.py) that publishes SimTick messages. On each tick:

• The Simulator updates drone position using a trapezoidal velocity profile (acceleration → cruise → deceleration)
• Remaining operation time is decremented by incoming simulation tick duration
• Task completion is detected when the drone reaches the goal location

Note: Drone-type-specific simulators (MultirotorSimulator, FixedWingSimulator) and SimulatorFactory exist in the codebase but are not currently used at runtime; all agents use the base Simulator class.

Fault Tolerance

• Fault Injection: A /fault_injection message marks a specific drone as FAILED. All other agents then:
  1. Identify the failed drone's uncompleted tasks
  2. Find tasks on any drone (including themselves) whose preconditions depend on the failed drone's uncompleted tasks
  3. Remove affected dependent tasks from their own assigned list if present
  4. Combine the failed drone's tasks and all dependent tasks into a single replan batch
  5. If the drone already has an existing schedule, use insertion-based bidding (marginal cost) instead of full rebidding
• Simulation Restart: A /restart_sim message reinitializes all agents, clearing task and bid state

Task Preconditions and Dependencies

Tasks can declare precondition dependencies via the precondition_task_ids field in the Task message. This enables ordered task chains (e.g., task B requires task A to be completed first):

• Bid Generation: The BidCalculator only generates permutations that respect precondition ordering
• Assignment Solving: The AssignmentSolver validates that all precondition tasks are assigned (to any drone) before accepting a solution that includes a dependent task
• Task Execution: The BidderAgent checks arePreconditionsMet() before starting each task; blocked tasks are deferred until their preconditions are globally completed
• Fault Recovery: When a drone fails, tasks on other drones whose preconditions depended on the failed drone's work are also replanned

Route Succession Constraint

Tasks can declare a strict route predecessor via route_predecessor_task_id. If set for task B, then task A=route_predecessor_task_id and B must be:

• assigned to the same drone,
• executed in direct order A -> B,
• with no task between them.

Enforcement points:

• Bid Generation: route-successor tasks are only generated directly after their predecessor
• Insertion Bidding: insertions cannot split an existing route predecessor/successor pair
• Assignment Solving: solutions violating same-drone or direct adjacency are rejected
• Task Execution: if predecessor A has just completed, successor B is forced as the next task

Insertion-Based Bidding

When a drone already has assigned tasks and new tasks arrive (e.g., during fault recovery), the system uses insertion-based bidding rather than full rebidding:

• BidCalculator::calculateBidsWithInsertion() finds the optimal insertion points for new tasks into the existing schedule
• BidCalculator::findBestInsertion() uses a greedy cheapest-insertion heuristic with precondition-aware slot constraints
• Already in-progress tasks are locked and cannot be reordered
• The bid value represents the marginal cost of adding the new tasks

Environment System

The system supports environment definitions received via the /environment topic:

• Mission Area (MissionArea struct): Bounding box defined by min/max corners constraining drone movement
• No-Fly Zones - Polygon (NoFlyZonePoly struct): Polygonal restricted areas defined by vertex lists
• No-Fly Zones - Circle (NoFlyZoneCirc struct): Circular restricted areas defined by center point and radius

Environment data flows from the subscriber through the BidderAgent to the BidCalculator and PathPlanner for future path cost integration.

Adding New Drone Configurations

1. Add a new entry to config/drone_config.yaml
2. Add the config_id to the DRONE_CONFIGS array in launch/launch.sh
3. Rebuild is not required for config changes

This README was updated on June 9th, 2026.