Distributed Optimization Algorithms for Multi-Agent Mission Planning: Convergence Analysis and Performance Benchmarking

Abstract

Multi-agent mission planning requires coordinated optimization of trajectories, task sequences, and resource allocation across distributed agents without centralized computation, demanding algorithms that converge to high-quality solutions while respecting communication and computational constraints. This paper presents comprehensive convergence analysis and performance benchmarking of distributed optimization algorithms for multi-agent planning problems. We systematically examine algorithmic approaches including distributed gradient descent and its accelerated variants, alternating direction method of multipliers (ADMM) decomposing coupled constraints, consensus-based optimization where agents iteratively refine solutions through local averaging, and dual decomposition methods exploiting problem structure. The study develops rigorous convergence analysis for each algorithm class, establishing convergence rates, optimality guarantees, and conditions under which global optima are achieved. Particular attention is devoted to non-convex mission planning problems where trajectory dynamics and collision avoidance constraints violate convexity, examining local convergence properties and escape mechanisms from suboptimal solutions. We analyze the impact of network topology on convergence, demonstrating how graph connectivity, diameter, and spectral properties affect algorithm performance. The paper presents extensive performance benchmarking across representative mission scenarios: coordinated area coverage optimizing sensor placement, multi-target tracking with dynamic task assignment, and collaborative payload delivery with timing constraints. Benchmark environments systematically vary problem scale (5-50 agents), coupling strength between agent decisions, communication graph topology, and presence of dynamic obstacles. Performance metrics encompass solution quality relative to centralized optimization, convergence time measured in iterations and wall-clock time, communication overhead quantified by message count and bandwidth, and scalability characteristics. Comparative results reveal that ADMM variants achieve superior solution quality with 5-15% optimality gaps but require more communication rounds, while consensus-based methods offer faster convergence with moderate optimality loss. We investigate asynchronous algorithm variants accommodating heterogeneous agent computation speeds and unreliable communication. The paper examines warm-starting strategies and adaptive parameter tuning for improved convergence.