Distributed Auction Algorithm for Decentralised Mobile Manipulators

Project Overview

Distributed auction algorithm for decentralised task allocation in dual mobile manipulators performing independent and collaborative assembly tasks. Extends the Zavlanos, Spesivtsev and Pappas (2008) theoretical framework with time-weighted consensus protocols, task dependency management, and failure recovery mechanisms.

Developed as a BEng Mechatronics Engineering dissertation at the University of Gloucestershire, investigating the gap between mathematical auction theory and practical multi-robot coordination under realistic communication constraints.

System architecture for decentralised control of dual mobile manipulators

Technical Implementation

Algorithm Architecture

The core system implements a distributed auction algorithm where each robot independently calculates bids for available tasks using a multi-factor cost function:

bid_ij = α₁·d_factor + α₂·c_factor + α₃·capability_match
         - α₄·workload_factor - α₅·energy_factor
         + global_balance_factor + unassigned_bonus + iteration_factor

Factors include Euclidean distance, configuration transition cost, capability matching via dot product similarity, workload distribution across robots, and energy consumption estimates. All factors are normalised before weighting.

Price updates follow an ε-complementary slackness formulation with adaptive epsilon scaling based on task oscillation count to dampen cycling. State agreement across robots uses a time-weighted consensus protocol with exponential decay weighting based on information age:

x_consensus = x_i + Σ γ·exp(-λ·Δt)·(x_j - x_i)

Task Dependencies

Tasks are modelled as a directed acyclic graph (DAG) with cycle prevention, a cap of 3 prerequisites per task, and transitive dependency removal to simplify the graph structure. Topological ordering determines execution sequencing.

Failure Recovery

Dual-method failure detection combines heartbeat monitoring with progress tracking. On failure detection, orphaned tasks are identified and a recovery auction runs with modified bid weights:

b_r_ij = b_ij + β₁·(1 - progress) + β₂·criticality + β₃·urgency

Criticality is measured by the number of downstream dependent tasks in the DAG.

Technologies

Primary implementation: Python (auction algorithm, simulation engine, statistical analysis, GUI)
Proof-of-concept verification: MATLAB/Simulink
Planned but not completed: ROS2 Humble / Gazebo 11 (TurtleBot3 Waffle Pi with OpenMANIPULATOR-X) — pivoted away due to platform integration challenges
Optional acceleration: PyTorch for GPU-accelerated batch bid computation
Analysis: SciPy, statsmodels (ANOVA, regression), pandas, seaborn, matplotlib
Task graph: NetworkX for DAG representation and critical path analysis
GUI: PyQt5 with matplotlib integration for real-time visualisation

Experimental Design

Full factorial design across four control variables with 30 repetitions per combination:

Factor	Levels
Task count (K)	4, 8, 16, 32
Communication delay (τ)	0, 50, 200, 500 ms
Packet loss (p_loss)	0, 0.1, 0.3, 0.5
Epsilon (ε)	0.01, 0.05, 0.2, 0.5

Response variables: makespan, message count, optimality gap, recovery time. Statistical analysis via ANOVA, regression modelling, and 95% confidence intervals.

Results

Convergence and Scaling

Auction results showing price convergence, task assignments, and workload distribution

The algorithm achieved stable task allocations within approximately 25 to 30 iterations for 10 to 15 task scenarios, with monotonically increasing prices stabilising at equilibrium.

Effect of task count on makespan with 95% confidence intervals

Makespan scaled near-linearly from approximately 17.5 to 67 time units as tasks increased from 4 to 32.

Communication Robustness

Effect of communication delay on convergence iterations

Convergence time remained consistent at approximately 148.8 iterations across all tested delays from 0 to 500ms. The system remained functional under 50% packet loss. Message complexity scaled as O(K) compared to O(K²) for centralised approaches.

Comparative Performance

Effect of epsilon on optimality gap versus theoretical 2-epsilon bound

Against a centralised baseline (exhaustive search for K ≤ 8, greedy heuristic for larger problems), the distributed algorithm achieved a 0.85 performance ratio for K ≤ 8, degrading to approximately 0.72 at K = 32.

Factor Analysis

Factor significance and effect size analysis across experimental variables

ANOVA revealed task count as the dominant factor affecting performance, with effect sizes of 2.079 on optimality gap and 1.445 on makespan. Communication delay had negligible impact. Regression analysis confirmed a strong negative correlation between message count and optimality gap.

Limitations

The research identified several critical implementation issues that represent the gap between theoretical guarantees and practical behaviour:

Optimality gap discrepancy: The MATLAB implementation produced an optimality gap of approximately 43, far exceeding the theoretical 2ε bound. The Python implementation showed a negative gap of approximately −0.72, suggesting centralised baseline calibration issues. Both indicate that the ε-complementary slackness conditions are not properly maintained in the bid and price update mechanism.

Epsilon insensitivity: ANOVA reported p = 1.0 for epsilon across all Python metrics, meaning epsilon had no statistically measurable effect on any response variable. This points to an implementation inconsistency in how epsilon influences the price update rule, despite epsilon being explicitly included in the price formula.

Recovery mechanism failure: Recovery time was reported as zero across all configurations. Logic errors in recovery completion detection prevented validation of the theoretical O(|T_f|) + O(b_max/ε) bound. The recovery auction runs but its completion is not correctly detected.

Premature convergence: The algorithm occasionally terminated with unassigned tasks because the convergence criteria prioritised assignment stability over task allocation completeness.

ROS/Gazebo platform challenges: The planned high-fidelity simulation on ROS2 Humble with Gazebo 11 could not be completed due to package compatibility issues, build failures, and integration complexity with the TurtleBot3 and OpenMANIPULATOR-X stack. This prevented sim-to-real validation.

Future Work

Redesign the epsilon integration in the price update mechanism and validate convergence against theoretical bounds
Implement explicit state tracking for recovery with deterministic completion detection
Enhance convergence criteria to enforce complete task allocation before termination
Develop adaptive parameter auto-tuning using problem size and topology characteristics
Scale beyond two robots to evaluate communication topology effects
Revisit ROS2/Gazebo integration for physical robot validation
Add look-ahead planning for critical path-aware dependency handling
Investigate multi-team coordination with hierarchical auction structures