PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Heuristic Multi-Agent Path Finding with Communication

Ziyuan Ma, Yudong Luo, Hang Ma

arXiv:2106.11365v1cs.ROcs.AIcs.MA

TL;DR

Centralized MAPF planning does not scale well, and decentralized RL can struggle with cooperation in congested settings. The paper combines deep Q-learning, shortest-path heuristic guidance, and graph-convolution communication for decentralized agents. It reports higher success rates and fewer steps than PRIMAL across the tested cases.

  • Problem

    Centralized MAPF methods do not scale well to many agents, while decentralized RL methods can struggle with deadlocks and cooperation in cluttered or congested settings.

    Source: §I · p. 1

  • Method

    The method uses independent deep Q-learning with all potential single-source shortest paths as heuristic input and graph-convolution communication between agents.

    Source: §I · p. 1, 1) Heuristic · p. 4

  • Results

    DHC outperforms PRIMAL in success rate across the reported cases and always uses fewer time steps to finish tasks.

    Source: A. Success Rate and Average Step · pp. 5–6

  • Takeaways & Limitations

    The results support using learned shortest-path guidance and agent communication for long-horizon tasks and cooperation in congested MAPF settings.

    Source: §VIII · p. 6, A. Success Rate and Average Step · p. 6

Abstract

from arXiv · show

Multi-Agent Path Finding (MAPF) is essential to large-scale robotic systems. Recent methods have applied reinforcement learning (RL) to learn decentralized polices in partially observable environments. A fundamental challenge of obtaining collision-free policy is that agents need to learn cooperation to handle congested situations. This paper combines communication with deep Q-learning to provide a novel learning based method for MAPF, where agents achieve cooperation via graph convolution. To guide RL algorithm on long-horizon goal-oriented tasks, we embed the potential choices of shortest paths from single source as heuristic guidance instead of using a specific path as in most existing works. Our method treats each agent independently and trains the model from a single agent's perspective. The final trained policy is applied to each agent for decentralized execution. The whole system is distributed during training and is trained under a curriculum learning strategy. Empirical evaluation in obstacle-rich environment indicates the high success rate with low average step of our method.

I. INTRODUCTION

MAPF is difficult to scale with centralized planning, while decentralized RL can struggle with deadlocks and cooperation in cluttered settings. The paper proposes heuristic-guided deep Q-learning with graph-convolution communication, trained distributively for decentralized execution.

I. INTRODUCTION

  • Centralized MAPF planning does not scale well to many agents, and decentralized reactive policies can deadlock or livelock in cluttered, tight environments.Prior approaches also rely on simplifying assumptions that leave simultaneous collisions and agents obstructing others after reaching goals unaddressed.Source: §I · p. 1
  • The method embeds all potential single-source shortest-path choices as heuristic input, avoiding a prescribed route and special off-route reward shaping.Agents learn from the heuristic rather than being forced to follow one individual shortest path, which may harm cooperation.Source: §I · p. 1
  • Graph convolution lets agents communicate with neighbors to support cooperation, while independent single-agent Q-learning avoids learning a joint action value.The approach uses multi-head attention as the convolutional kernel and applies the same policy to agents during decentralized execution.Source: §I · p. 1
  • The proposed learning environment follows standard MAPF by moving agents simultaneously and retaining them after they reach their goals.The paper also describes distributed training with curriculum learning; its contribution list identifies the method as scaling to many agents.Source: §I · pp. 1–2

II. PROBLEM DEFINITION

The paper defines MAPF paths and collisions, models the setting as a partially observable Markov game, and reviews Q-learning and DQN as the learning framework.

II. PROBLEM DEFINITION

  • A MAPF solution assigns each agent a collision-free path, with quality measured by the sum of agents’ arrival times at their goals.Collisions include agents sharing a vertex at the same time or traversing the same edge in opposite directions.Source: §II · p. 2

A. Partially Observable Markov Game

  • The partially observable Markov game has agents simultaneously choose actions and receive rewards and observations, each seeking to maximize expected total return.The formulation is represented by the tuple ⟨N, S, {Ai}, {Oi}, {Ri}, P, γ⟩.Source: A. Partially Observable Markov Game · p. 2

B. Q-Learning and Deep Q-Networks (DQN)

  • Q-learning estimates action values, while DQN parameterizes the action-value function with a neural network; partial observability can be handled with recurrent units.The text names LSTM and GRU as examples of recurrent units.Source: B. Q-Learning and Deep Q-Networks (DQN) · p. 2

C. Independent Q-Learning (IQL)

The related-work discussion covers independent and centralized multi-agent reinforcement learning, then reviews RL methods for MAPF that use planner guidance or communication.

C. Independent Q-Learning (IQL)

  • Independent Q-learning trains each agent’s action-value function separately while treating other agents as part of the environment.The passage notes empirical success for IQL in some multi-agent settings, including two-player pong.Source: C. Independent Q-Learning (IQL) · p. 2

A. Multi-Agent Reinforcement Learning (MARL)

  • Centralized-training methods include value decomposition and actor-critic approaches, but the described methods assume fully cooperative agents sharing one reward function.VDN and QMIX combine individual values; COMA and MADDPG use centralized critics with decentralized actors.Source: A. Multi-Agent Reinforcement Learning… · p. 2

B. Reinforcement Learning based MAPF

  • MAPF RL work includes PRIMAL and planner-guided methods, while communication approaches include graph-convolution methods such as DGN and TarMAC.MAPPER and G2RL use single-agent shortest paths with off-route penalties, which may mislead because shortest paths are not unique or globally optimal for multi-agent cases.Source: B. Reinforcement Learning based MAPF · pp. 2–3

V. LEARNING ENVIRONMENT

The learning environment is a partially observable gridworld, with observations organized as local obstacle, agent, and heuristic channels.

A. Environment Setup

  • The MAPF environment is a discrete gridworld with partial observability, random non-overlapping start and goal locations, and reachable goals.Agents move simultaneously and remain in the environment after reaching their goals.Source: A. Environment Setup · p. 3, §V · p. 3

B. Observation Representation

  • Each agent observes an ℓ×ℓ field of view smaller than the full map, represented by obstacle and nearby-agent channels.The field-of-view size is odd so the observing agent is centered.Source: B. Observation Representation · p. 3
  • Four additional heuristic channels are included in the model input, allowing the goal location to be inferred rather than supplied separately.The channels are described as part of the observation representation and detailed in the method section referenced by the passage.Source: B. Observation Representation · p. 3

C. Action Space

DHC combines a three-module recurrent Q-network with an action space and reward design intended to support collision handling and cooperation. Its model encodes observations, exchanges agent messages, and estimates action values.

C. Action Space

  • Invalid actions are not filtered; agents involved in collisions are recursively returned to previous states until no collision remains.The action space has five choices: four adjacent moves and staying still.Source: C. Action Space · p. 3

D. Reward Design

  • Movement and staying off-goal receive equal treatment, allowing an agent to wait for another to pass in complex cases.The reward design contrasts with PRIMAL and MAPPER, which penalize staying still more.Source: D. Reward Design · p. 3

A. Agent Q-Network Design

  • DHC comprises an observation encoder, communication block, and Q-network, with two identical communication blocks.The encoder uses convolutional layers and a GRU; communication uses a graph convolutional network followed by a GRU, and the Q-network produces action values.Source: §VI · p. 3, A. Agent Q-Network Design · pp. 3–4, Figure 1 · p. 4

VI. DISTRIBUTED HEURISTIC LEARNING WITH COMMUNICATION

  • DHC’s independent learning and graph-convolution communication are intended to guide reinforcement learning and foster cooperation, while allowing distributed training.Each agent’s observation is encoded, messages are exchanged through the communication module, and the resulting information supports Q-value estimates for available actions.Source: §VI · p. 3, A. Agent Q-Network Design · pp. 3–4

1) Heuristic:

DHC adds four action-specific heuristic channels to each agent’s observation, encoding potential shortest-path choices without prescribing one path.

1) Heuristic:

  • Four heuristic channels correspond to Up, Down, Left, and Right, marking locations where the associated action moves the agent closer to its goal.The channels have the same size as the field of view and are combined with the two observation channels as model input.Source: 1) Heuristic · p. 4
  • The guidance captures all potential choices from single-source shortest paths rather than embedding one specific path.The goal is the source, and the method uses single-agent path-planner information instead of a centralized planner.Source: 1) Heuristic · p. 4
  • Unlike approaches that apply an off-route penalty, DHC supplies the heuristic channels without special reward design and leaves agents to learn how to use them.The passage contrasts this with MAPPER and G2RL, which embed a specific single-agent shortest path and apply an off-route penalty.Source: 1) Heuristic · p. 4

B. Graph Convolutional Communication

DHC communicates between nearby agents using graph convolution with multi-head attention, then repeats message aggregation over two rounds to broaden the information exchanged.

B. Graph Convolutional Communication

  • Agents are graph nodes, and two nodes are neighbors when they fall within each other’s field of view.The method uses multi-head dot-product attention as the graph-convolution kernel to compute interactions among agents.Source: B. Graph Convolutional Communication · p. 4
  • Each attention head weights and sums neighboring agents’ Value vectors; concatenated head outputs pass through a neural-network layer to form the graph-convolution output.The attention relation is computed for each agent and its neighbors, including the agent itself.Source: B. Graph Convolutional Communication · p. 4
  • Communication runs for two rounds, with the first round’s GRU output becoming the initial message for the next round.Repeating the aggregation equations lets agents gradually gather more information from neighbors.Source: B. Graph Convolutional Communication · pp. 4–5

C. Multi-Agent Distributed Prioritized Experience Replay

DHC trains a single agent-perspective policy for decentralized execution and distributes experience generation through an Ape-X-style actor-learner setup with prioritized replay.

C. Multi-Agent Distributed Prioritized Experience Replay

  • A single model is trained from one agent’s perspective and then applied to every agent for decentralized execution.Other agents are treated as part of the training agent’s environment; independent Q-learning avoids learning a joint-action Q-function whose action space grows exponentially with agent count.Source: C. Multi-Agent Distributed Prioritized… · p. 5
  • The distributed setup uses 16 CPU actors to generate experience and a single GPU learner to update the network and experience priorities.Actors feed transitions into a shared prioritized replay buffer; priorities are initialized and updated from the perspective of the agent being trained, while transitions for all agents are stored for communication.Source: C. Multi-Agent Distributed Prioritized… · p. 5
  • DHC’s loss uses a multi-step temporal-difference return that combines rewards with a discounted target-network Q-value.The return is for the agent being trained, and the target network is a periodic copy of the online parameters.Source: C. Multi-Agent Distributed Prioritized… · p. 5

VII. EXPERIMENTS

Training grows from a one-agent, 10 × 10 task as success exceeds 0.9, reaching twelve agents in a 40 × 40 environment. Communication is limited to the two nearest neighbors, with exploratory actions taken only by the agent being trained.

VII. EXPERIMENTS

  • Curriculum training adds agents or increases map size when the current task’s success rate exceeds 0.9, progressing from one agent on a 10 × 10 map to twelve on a 40 × 40 map.The two task changes increase agent count by one or environment size by five.Source: §VII · p. 5
  • Communication uses each agent’s two nearest neighbors, limiting the communication scope during training.The paper motivates this choice by communication latency and bandwidth constraints.Source: §VII · p. 5
  • Only the agent being trained takes ϵ-greedy actions; other agents take no random actions to make the environment more stationary.Source: §VII · p. 5

A. Success Rate and Average Step

The method outperforms PRIMAL in success rate across the tested cases, including larger maps. It also uses fewer steps, with smaller step increases from 40 × 40 to 80 × 80 maps.

A. Success Rate and Average Step

B. With and Without Heuristic or Communication

DHC achieves the highest success rate and lowest average step against PRIMAL in sparse and tight environments. The ablations associate heuristic guidance with stronger performance on long-horizon tasks and communication with higher success rates in congested settings.

B. With and Without Heuristic or Communication

  • The baseline uses PRIMAL-format inputs, while DHC/Comm retains DHC’s input but omits its graph-convolution communication block.Both variants are distributed during training and use DHC’s training parameters.Source: B. With and Without Heuristic or… · p. 6
  • Without heuristic channels, the information-rich baseline performs sharply worse, especially on long-horizon tasks in larger environments.Fig. 5 compares the baseline with DHC/Comm for the heuristic-channel assessment.Source: B. With and Without Heuristic or… · p. 6, Figure 5 · p. 6
  • Communication makes little difference at low agent density, but DHC has much higher success rates than DHC/Comm in tight settings.The reported tight cases are 64 agents on 40 × 40 maps and 128 agents on 80 × 80 maps.Source: B. With and Without Heuristic or… · p. 6, Figure 5 · p. 6

VIII. CONCLUSIONS

  • DHC achieves the highest success rate and lowest average step against PRIMAL in both sparse and tight environments.Source: §VIII · p. 6
  • Communication scope is fixed by the number of communication agents; increasing that scope while reducing overhead and latency remains future work.Source: §VIII · p. 6
Loading 2106.11365v1…