Probability-Tuned Market-Based Allocations for UAV Swarms Under Unreliable Observations

Unmanned aerial vehicle (UAV) swarms are becoming increasingly attractive as highly integrated miniature sensors and processors deliver extraordinary performance. The employment of UAV swarms on complex real-life tasks has motivated exploration on allocation problems involving multiple UAVs, complex constraints, and multiple tasks with coupling relationships. Such problems have been summarized domain independently as multirobot task allocation problems with temporal and ordering constraints (MRTA/TOC). The majority of MRTA/TOC works have hitherto focused on deterministic settings, while their stochastic counterparts are sparsely explored. In this article, allocation problems incorporating classification uncertainty of targets and soft ordering constraints of tasks are considered. To address such problems, a novel market-based allocation algorithm, the probability-tuned market-based allocation (PTMA), is proposed. PTMA consists of iterations between two phases: 1) the first phase updates local perception of global situational awareness and 2) the second phase is a market-based allocation scheme with embedded artificial randomness to locally generate allocation results. Under reasonable assumptions on classification uncertainty, the proposed PTMA algorithm is proven to guarantee a superior performance compared with conventional auctions, verifying the feasibility of using randomness to counter randomness theoretically. Three groups of numerical experiments have been conducted to assess the performance of the proposed PTMA. The first group of experiments compares PTMA with the consensus-based auction algorithm (CBAA), the chance-constrained CBAA, and the PTMA-I (specialization of PTMA with the Identity matrix), on simulated task scenarios with varying degrees of classification uncertainty. The second group evaluates the stability of PTMA. The third group tests the scalability of PTMA on expanded task scenarios. Simulation results demonstrate a satisfactory performance in effectiveness, robustness, stability, and scalability of the proposed PTMA.