Decentralized dynamic task allocation for UAVs with limited communication range

08/31/2018
by   Marc Pujol-Gonzalez, et al.
0

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 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset