An Auction-based Coordination Strategy for Task-Constrained Multi-Agent Stochastic Planning with Submodular Rewards

Abstract--In many domains such as transportation and logistics, search and rescue, or cooperative surveillance, tasks are pending to be allocated with the consideration of possible execution uncertainties. Existing task coordination algorithms either ignore the stochastic process or suffer from the computational intensity. Taking advantage of the'weakly coupled' feature of the problem and the opportunity for coordination in advance, we propose a decentralized auction-based coordination strategy using a newly formulated score function which is generated by forming the problem into task-constrained Markov decision processes (MDPs). The proposed method guarantees convergence and at least 50% optimality in the premise of a submodular reward function. Furthermore, for the implementation on large-scale applications, an approximate variant of the proposed method, namely Deep Auction, is also suggested with the use of neural networks, which is evasive of the troublesome for constructing MDPs. Inspired by the well-known actor-critic architecture, two Transformers are used to map observations to action probabilities and cumulative rewards respectively. Finally, we demonstrate the performance of the two proposed approaches in the context of drone deliveries, where the stochastic planning for the drone league is cast into a stochastic price-collecting Vehicle Routing Problem (VRP) with time windows. Simulation results are compared with state-of-the-art methods in terms of solution quality, planning efficiency and scalability. Cooperative systems of multiple agents, which features a flexible structure, parallel-processing ability, and scalability, are of great interest, especially for those operating on the unmanned aerial platform [1], such as cooperative surveillance, search and rescue [2][3], border patrolling, etc. Among its various instantiations, there is a specific but widespread category of assigning tasks among team members with a global goal, followed by an independent and possibly stochastic task execution. For example, in deliveries of parcels [4], tasks are allocated to individual vehicles, and the vehicles deliver their allocated items in sequence, without interference from other executors. However, the delivery may subject to stochastic travel delays between destinations. Also, in multi-target tracking [5], agents decide the tracking targets and the best action to track based on the estimation of targe manoeuvring.