← Back to Home

GATAR

Graph-based Decentralized Task Allocation for Multi-Robot Target Localization

IEEE Robotics and Automation Letters (RA-L) 2024

Juntong Peng Hrishikesh Viswanath Aniket Bera

Department of Computer Science, Purdue University

Paper arXiv Code BibTeX

System overview: UAVs and UGVs localizing targets around obstacles — By exploiting comparative advantages, a collaborative multi-robot system localizes targets efficiently. The UAV can fly over the ground obstacle while the UGV must navigate around it, so the target inside the U-shaped obstacle is better assigned to the UAV.

TL;DR

GATAR is a decentralized graph neural operator that allocates localization targets across mixed teams of ground (UGV) and aerial (UAV) robots by aggregating information from each robot's neighbors. A heterogeneity-aware preprocessing step encodes how the robot types differ, and a single trained model handles teams of 2 to 12 robots while outperforming baseline architectures.

Method

GATAR architecture and heterogeneity-aware preprocessing — The model takes the observable environment, targets, obstacles and robots as input, aggregates information through the V-cycle graph attention network, and outputs the x-y location of the target assigned to each robot, which can be used for path planning.

Heterogeneity-aware observation preprocessing

Robots differ in perception (whether ground obstacles occlude their line of sight) and mobility (whether ground obstacles impede them). Each robot encodes both into a four-channel spatial feature map: a reward map that favours regions reachable by short paths, a Gaussian target map centred on each observed target, a Boolean map of observed obstacles, and the pixel-wise product of the reward and target maps. The reward for robot $i$ moving to a location $l$ in its observed region $E_i$ is

$$R_{i,l} = \frac{v_i}{d_{i,l} + \epsilon},$$

where $v_i$ is the robot's velocity and $d_{i,l}$ the length of the shortest path to $l$.

Graph Attention Task Allocator

Robots exchange their local features with every neighbor inside a communication radius. To capture long-range information with linear complexity, GATAR adapts the V-cycle of the Multipole Graph Kernel Network: the radius graph is decomposed into levels, information is passed down and back up through them, and each level uses multi-head graph attention to weight a varying number of neighbors. The residual V-cycle structure also counters over-smoothing, which would otherwise assign the same task to every robot in a neighborhood. The model is trained with supervision from a centralized greedy expert, and runs fully decentralized at test time.

Results

Task allocation on a real-world map

Task allocation around Columbus Circle, New York City — A grid world built from a bird's-eye image of Columbus Circle by Central Park, Manhattan. Red points are randomly distributed targets; blue squares and green triangles are UGVs and UAVs initially located around the roundabout; grey squares are obstacles such as buildings and shrubs.

Communication range and team size

Effect of communication range and comparison with greedy and random allocation — (a) 90th-percentile and (b) median distance from the predicted targets to the expert's targets as the communication range grows. (c) 90th-percentile distance of GATAR against greedy and random task allocation, across team compositions from 1 UAV + 1 UGV to 6 UAVs + 6 UGVs.

Against learned baselines

Method	90-pct. dist. ↓	median dist. ↓	mean dist. ↓
GATAR	4.3928	0.8156	1.6308
GNN	4.5618	0.8755	1.7180
GNN + V-Cycle	4.6152	0.8452	1.6996
MAGAT	5.4553	0.8588	1.8746

Distance between predicted and expert-assigned targets, 6 UAVs + 6 UGVs.

Citation

@article{peng2024graph,
  title   = {Graph-based Decentralized Task Allocation for Multi-Robot Target Localization},
  author  = {Peng, Juntong and Viswanath, Hrishikesh and Bera, Aniket},
  journal = {IEEE Robotics and Automation Letters},
  year    = {2024}
}