Decentralized dynamic task allocation for UAVs with limited communication range
This addresses coordination challenges for UAV teams in applications like surveillance or delivery, offering a practical improvement over existing methods.
The paper tackles the problem of decentralized dynamic task allocation for UAVs with limited communication range by modeling it as a sequence of Markov Random Field problems and using the Max-Sum algorithm, achieving up to a 16% reduction in average service time and reducing the gap between decentralized and centralized techniques by 25% in worst-case scenarios.
We present the Limited-range Online Routing Problem (LORP), which involves a team of Unmanned Aerial Vehicles (UAVs) with limited communication range that must autonomously coordinate to service task requests. We first show a general approach to cast this dynamic problem as a sequence of decentralized task allocation problems. Then we present two solutions both based on modeling the allocation task as a Markov Random Field to subsequently assess decisions by means of the decentralized Max-Sum algorithm. Our first solution assumes independence between requests, whereas our second solution also considers the UAVs' workloads. A thorough empirical evaluation shows that our workload-based solution consistently outperforms current state-of-the-art methods in a wide range of scenarios, lowering the average service time up to 16%. In the best-case scenario there is no gap between our decentralized solution and centralized techniques. In the worst-case scenario we manage to reduce by 25% the gap between current decentralized and centralized techniques. Thus, our solution becomes the method of choice for our problem.