Local Bidding Strategies for Reactive and Scalable Auction-Based Multi-Agent Coordination

This article proposes local bidding strategies for autonomous agents participating in an auction-based multi-agent coordination system, in order to improve the scalability and reactivity of the architecture in large-scale coordination scenarios. Based on a careful analysis of the reactivity requirements and the computational costs of the central auctioneer (costs for solving Linear Integer Programs) and the local agents (costs for path-planning and task execution), this article explores the idea of each agent bidding for a subset of available tasks that are locally relevant to the agent. Each agent first employs a computationally light euclidean distance-based and percentile-based screening method to choose a subset of available tasks, followed by a more computationally complex, but realistic path-planning based cost-estimation and bidding for the chosen subset. The proposed strategy not only reduces the overall computational cost at the agents, but also at the central auctioneer, by reducing the size of the combinatorial optimization problems and the overall communication requirements of the architecture, thereby improving the scalability and reactivity of the overall system. It is shown that, through a one-time simulation-guided design of the bidding parameters, the improved reactivity and scaling is achieved while retaining the optimality or near-optimality of the resulting task-allocation. The performance of the proposed bidding strategies is evaluated in two large-scale simulation scenarios and the reduction in computational costs and the near-optimality of the task allocation is demonstrated.