Efficient communication is critical for decentralized Multi-Robot Path Planning (MRPP), yet existing learned communication methods treat all neighboring robots equally regardless of their spatial proximity, leading to diluted attention in congested regions where coordination matters most. We propose Relation enhanced Multi Head Attention (RMHA), a communication mechanism that explicitly embeds pairwise Manhattan distances into the attention weight computation, enabling each robot to dynamically prioritize messages from spatially relevant neighbors. Combined with a distance-constrained attention mask and GRU gated message fusion, RMHA integrates seamlessly with MAPPO for stable end-to-end training. In zero-shot generalization from 8 training robots to 128 test robots on 40x40 grids, RMHA achieves approximately 75 percent success rate at 30 percent obstacle density outperforming the best baseline by over 25 percentage points. Ablation studies confirm that distance-relation encoding is the key contributor to success rate improvement in high-density environments. Index Terms-Multi-robot path planning, graph attention mechanism, multi-head attention, communication optimization, cooperative decision-making
Figures & tables
Figure 1. Illustration of MAPF constraints: vertex collisions, edge collisions, and swap collisions among agents must all be avoided. Three diagrams illustrating MAPF collision types that must be avoided: two agents occupying the same vertex (vertex collision), two agents traversing the same edge in opposite directions (edge collision), and two adjacent agents swapping positions (swap collision).
Method
Year
Move
Wait a
Wait b
Coll.
Ego-goal
All-goal
Block
Oscil.
Deviate
PRIMAL
2019
↓
↓
→
↓
–
↑
↓
–
–
GNN
2020
–
–
–
–
–
–
–
–
–
MAPPER
2020
↓
↓
↓
↓
↑
–
–
↓
↓
G2RL
2020
↓
–
–
↓
–
↑
–
–
–
PRIMAL2
2021
↓
↓
→
↓
↑
–
–
–
–
MAGAT
2021
–
–
–
–
–
–
–
–
–
Table 1. Comparison of Reward Designs in RL-based MAPF Methods.
Figure 2. MARL modeling paradigms for MAPF: MG, POMG, and Dec-POMDP. Schematic comparing three multi-agent RL modeling paradigms for MAPF: a Markov Game with full observability, a Partially Observable Markov Game where each agent sees a local view, and a Dec-POMDP that adds a conditional observation distribution.
Action
Reward
Move (up/down/left/right)
−0.3
Stay (at goal / off goal)
0.0 / −0.3
Collision
−2.0
Blocking
−1.0
Table 2. Reward Settings
Figure 3. Architecture of the rmha communication module. Block diagram of the RMHA communication module: local observations are combined with Manhattan-distance embeddings, fed through query and key projections, masked by the communication radius, and aggregated via multi-head attention to produce updated messages.
Figure 4. Network architecture of rmha integrated with MAPPO. Full network architecture of RMHA combined with MAPPO, showing the convolutional observation encoder, LSTM temporal fusion, distance-aware multi-head attention communication block, and the four output heads producing policy, value, message vector, and a blocking flag.
Parameter
Value
Training agent count
8
Action count
5
Max episode length
256
FOV size
3
World size
(10,40)
Obstacle probability
(0.0,0.5)
Table 3. Experimental Parameters
Figure 5. A 10×10 grid world with 30% obstacle density and 8 agents. Colored squares indicate start positions; colored circles indicate goals; gray circles represent obstacles; the red dashed box shows the 3×3 FOV. Example 10-by-10 grid world used for training, with 30 percent obstacle density and 8 agents. Colored squares mark agent start positions, colored circles mark their goals, gray circles mark static obstacles, and a red dashed box outlines the 3-by-3 field of view.
Figure 6. Success rate of rmha under different agent counts. Line plot showing the success rate of RMHA as the number of agents increases from 16 to 128, with the model trained only at 8 agents. Success rate decays gradually but avoids collapse at the largest scale.
Figure 7. Communication ablation: training reward curves. Training reward curves over time for three ablation variants: MAPPO without communication, MAPPO with graph communication, and RMHA. The two communication-enabled variants converge faster and more stably than MAPPO alone.
Figure 8. Communication ablation: success rate comparison. Two bar charts comparing success rate at 0, 15, and 30 percent obstacle density. Left: MAPPO without communication versus graph communication; graph communication wins at every density. Right: graph communication versus RMHA; RMHA wins by a larger margin as density increases.
Figure 9. Success rate comparison across algorithms on Warehouse and City/Game maps. Grouped bar chart comparing success rate of ODrM*, SCRIMP, DHC, PICO, and RMHA on Warehouse and City/Game maps at 0, 15, and 30 percent obstacle complexity. RMHA maintains the highest success rate as complexity grows.
Figure 10. Maximum goals reached across algorithms on Warehouse and City/Game maps. Grouped bar chart of maximum goals reached (out of 128) for each baseline and RMHA across Warehouse and City/Game maps. SCRIMP and RMHA hold above 120 even at 30 percent density while PICO and DHC drop sharply.
Figure 11. Global trajectory comparison: rmha (left) vs. MAPPO (right). Side-by-side overhead view of agent trajectories on the same grid. The RMHA panel on the left shows well-organized, non-overlapping paths; the MAPPO panel on the right shows tangled paths and stalled agents.
Figure 12. Deadlock resolution in a narrow corridor. At T1 , agents A and B enter a conflict; the baseline leads to deadlock by T2 – T3 . Under rmha , agent A yields at T3 , allowing B to pass, and both proceed by T4 . Four-step storyboard of two agents A and B meeting head-on in a narrow corridor. The baseline leaves them deadlocked at steps T2 and T3, while under RMHA agent A yields sideways at T3 so agent B passes, and both reach their goals by T4.