Multi-Agent Path Finding with Prioritized Communication Learning

Many works employed MARL or deep learning (DL) methods to solve the MAPF problem. The typical PRIMAL method [7] introduced MARL firstly, and combined behavior cloning from a dynamically coupled planner to accelerate the training procedure. Further the PRIMALc [18] extended PRIMAL from 2D to 3D search space. PRIMALc introduced “agent modeling” technique to assist path planning by predicting the actions of other agents in a decoupled manner. Recently, PRIMAL₂ [9] extended PRIMAL to the lifelong MAPF (LMAPF) scenario, in which each agent will be immediately assigned a new goal once upon reaching their current goal. [8] proposed the MATS method which employed the multi-step ahead tree-search strategy in single-agent reinforcement learning (SARL) and imitation learning scheme to fit the results of the tree search strategy to solve the MAPF problem. BitString [19] and DHC [20] introduced the communication-based learning scheme based on end-to-end training procedure, but under fixed communication topology.

Prioritized planning [21] can be considered as a decoupled approach, where agents are ordered by predefined priorities. Fixed predefined priorities are assigned to all agents globally while all collisions are resolved according to these priors before the movements begin. Specially, the priorities can be assigned arbitrarily [3, 22, 23] or handcrafted  [21]. Heuristic methods can also be utilized to assign priorities, e.g., [24, 25, 26]. Further, some local orderings can assign temporary priorities to some agents in order to resolve collisions on the fly. This kind of method requires all agents to follow their assigned paths, while if an impasse is reached the priorities are assigned dynamically to determine which agent to wait [27, 28]. In order to improve the solution quality, many existing works attempt to elaborately explore the space of all total priority orderings. Some works explored this space randomly by generating several total priorities ordering as part of a hill-climbing scheme [23], instead of ergodically which can be enumerated for only up to $3$ agents [28]. Recently, CBSw/P [14] enumerated the sub-space (of all local priority orderings) as part of a conflict-driven combinatorial search framework.

The implicit priority learning phase aims to imitatively learn implicit priorities from classical coupled planner. In this paper, we utilize the ODrM* as the targeted classical coupled planner, which is considered as the state-of-the-art MAPF method [11]. Further, we introduce the behavior cloning [7, 8, 9, 18] to enhance the training procedure efficiency from the perspectives of both convergence speed and training performance. To emphasis, the behavior cloning shares the same low-level parameters with the implicit priority learning model, while this mutual restriction will benefit to the effectiveness of both implicit priority learning and behavior cloning [30, 31]. As follows, we will introduce the detailed procedure of this phase, while training datasets need to be constructed first.

Imitation Dataset Construction: Each agent’s observation and action spaces are the similar as previous work [7, 9]. The training sets $\mathcal{D}_{imp}$, $\mathcal{D}_{imt}$ for the implicit priority learning and the behavior cloning training respectively can be constructed based on the solutions of the classical coupled planner, i.e., the ODrM*. In every priority learning episode, given the $k$-th randomly generated MAPF instance $\mathcal{F}_{k}:=\langle G_{k},s_{k},g_{k}\rangle$, the ODrM* method will obtain a solution, i.e., the set of all single-agent plans $\{\tau^{i}_{k}\}$($i=1,\cdots,N$). By assuming the makespan of the solution is $T_{k}$, all position-position pairs $\{\tau^{i}_{k}[t],\pi^{i}_{t}(\tau^{i}_{k}[t])\}$($i=1,\cdots,N$) can be calculated through unfolding all single-agent plans $\{\tau^{i}_{k}\}$. At each timestep $t$, current positions $\{\tau^{i}_{k}[t]\}$ and corresponding goals $g_{k}$ of all agents can be combined to construct $\mathcal{D}_{imt}$, i.e.,

$$\mathcal{D}_{imt}:=\{o_{m},a_{m}\}_{m=1}^{|\mathcal{D}_{imt}|},\quad{\textstyle{|\mathcal{D}_{imt}|=N\times\sum_{k=1}^{K}T_{k}}},$$

where $o_{m}$ denotes the observations constructed by $\{\tau^{i}_{k}\}$($i=1,\cdots,N$) within the same scheme as [7, 9], and $a_{m}$ denotes the actions obtained by calculating the difference between two consecutive positions $\{\tau^{i}_{k}[t],\pi^{i}_{t}(\tau^{i}_{k}[t])\}$.

Further, we construct the ground-truth implicit priorities of each observation $o_{m}$ according to the following steps. Based on the observations of each agent $i$ with its goal $g_{k}(i)$, the next optimal action set $\mathcal{A}^{i}_{k}[t+1]$ is established through a greedy strategy (the next optimal action is the action that can touch the goal at the fastest speed without considering other agents). If the agent is at the goal, then the optimal action set is empty. Considering the optimal action set and the output action of ODrM*, the implicit priority $p_{m}$ of $o_{m}$ can be calculated via following two rules: i) the action is “no-movement”: the priority $p_{m}$ is set to be high ($p_{m}=1$) if the optimal action set is empty, otherwise is set to be low ($p_{m}=0$); ii) the action is “movement”: the priority $p_{m}$ is set to be high ($p_{m}=1$) if the action is in the optimal action set, otherwise is low ($p_{m}=0$). The dataset $\mathcal{D}_{imt}$ is constructed accordingly,

$$\mathcal{D}_{imp}:=\{o_{m},p_{m}\}_{m=1}^{|\mathcal{D}_{imp}|},\quad{\textstyle{|\mathcal{D}_{imp}|=N\times\sum_{k=1}^{K}T_{k}}}.$$

Network Structure and Training Procedure: With the obtained training dataset, we further establish the implicit priority learning model and the behavior cloning model structures as in Figure 3. These two neural networks share the same low-layer parameters with different output-heads. It is worth noting that messages from other agents are set to be the input of the neural network in Figure 3. The corresponding messages are generated through the outputs (the “message” output-head in the Figure 3) of other agents. The objective agents of sending the obtained messages are determined by the dynamic communication topology generated in the following prioritized communication learning phase.

The above-mentioned neural network is parameterized by $\theta$ and denoted as $\mathcal{I}_{\theta}$. The output message, predicted priority and prediction action are denoted as $e_{m}:=\mathcal{I}^{e}_{\theta}(o_{m})$, $\hat{p}_{m}:=\mathcal{I}^{p}_{\theta}(o_{m})$ and $\hat{a}_{m}:=\mathcal{I}^{\pi}_{\theta}(o_{m},\{e_{m}\})$ respectively. In the training procedure¹¹1The predicted priorities are utilized to construct the communication topology in the prioritized communication learning phase. To strengthen the stability of the communication learning procedure, PICO introduces a similar target network as in [32] and [33]. The target network is updated with a slow-moving average of the online network., the loss function is set to be

$$\mathcal{L}_{p}=\alpha_{imp}\mathcal{L}_{imp}+\mathcal{L}_{imt},$$

(1)

where $\alpha_{imp}$ denotes the penalty parameter and

	$\displaystyle\mathcal{L}_{imp}$	$\displaystyle=\!\!{\textstyle{-\frac{1}{|\mathcal{D}_{imp}|}\!\!\sum_{m=0}^{|\mathcal{D}_{imp}|-1}\!\left[p_{m}\log(\hat{p}_{m})+(1\!-\!p_{m})\log(1\!-\!\hat{p}_{m})\right],}}$
	$\displaystyle\mathcal{L}_{imt}$	$\displaystyle=\!\!{\textstyle{-\frac{1}{|\mathcal{D}_{imt}|}\sum_{m=0}^{|\mathcal{D}_{imt}|-1}\sum_{c=0}^{|\mathcal{A}|-1}a_{m}[c]\log(\hat{a}_{m}[c]),}}$

where $|\mathcal{A}|$, $a_{m}[c]$ and $\hat{a}_{m}[c]$ represent the action space’s size, the $c$-th element in $a_{m}$ and $\hat{a}_{m}$ respectively.

For the multi-agent learning problem, one of the key challenges is to encourage each agent to be selfless, while it might be detrimental to the immediate return maximization. This challenge is usually denoted as social dilemma [34] and exists conspicuously in MAPF [12]. Many algorithms have been proposed to alleviate this problem in multi-agent learning [35, 36, 37, 38], however rarely few works pay attention to MAPF problem. PICO method introduces additional blocking prediction tasks together with message exchanging to alleviate the social dilemma similar with the learning-based PRIMAL [7]. Furthermore, an on-goal prediction task is introduced to establish an accurate perception of whether the agent has reached the goal. Ablation studies show that the blocking prediction task can obtain better results when paired with the on-goal prediction task. These two tasks can provide more supervision signals from different perspectives for both implicit priority learning and behavior cloning learning, which also can help to learn better representations of the local observations.

Dynamic Prioritized Communication Topology: In order to achieve proper integration of implicit priority and communication learning, PICO introduces the classic ad-hoc routing protocol, i.e., cluster-based routing protocol (CBRP [39]) into the overall framework. CBRP employs the “weight” attributes attached to each agent to construct a cluster-based communication topology, which can be dynamically updated once the agent weights change. The high-weight agent becomes the center of the cluster, receives messages from all low-weight agents in the cluster, and broadcasts it to all low-weight agents after post-processing. Agents with low weights become affiliated members and make decisions based on the messages broadcast from the cluster‘s central agent. PICO chooses CBRP as the fundamental communication topology construction algorithm in MAPF because as long as the artificially defined weights in CBRP are replaced by the obtained implicit priorities, the integration of priority and communication learning can be properly realized.

Specifically, CBRP usually takes a cluster radius $d$ to establish the structured communication topology. Each member agent can confirm whether others have larger weights or contain central agents within its receptive area. If no such agent is found, this agent is elected as a central agent; otherwise, its role is kept. Meanwhile, each central agent checks whether other centrals exist in radius $d$. If no such agent is found or the found centrals’ weights are smaller than its weights, its role is kept; otherwise, it downgrades to a member agent. After a sufficient number of rounds, all agents are separated into clusters with one central agent in each cluster. This cluster-based communication topology inherits the classic planners’ idea of avoiding planning only in the agent’s neighborhood but also achieves the centralization-decentralization trade-off in MARL. The illustration diagram of CBRP is shown in Figure 4.

Network Structure and Training Procedure: PICO employs the A3C [40] as the backbone of communication-based MARL. The observation space is the same as the implicit priority learning phase. We employ the different action space from the prioritized communication learning phase for the reason that the agent may execute invalid actions. If there are static obstacles, other agents, or beyond the map’s boundary at the position reached by an agent’s following action, such an action is called invalid. Actions are sampled only from valid actions in training. Previous results in [41, 12] show that this technique enables a more stable training procedure, compared with giving negative rewards to agents for selecting invalid moves. Moreover, the reward function is same as [7]. The network structure is consistent with previous phase as shown in Figure 3. In the training procedure, the parameters of “priority”, “blocking”, and “on-goal” three output-heads are fixed. The predicted value by the “value” output-head is denoted as $\hat{v}_{m}:=\mathcal{I}^{v}_{\theta}(o_{m},a_{m})$. The parameters are updated to minimize the Bellman error between the predicted value and the discounted return, i.e.,

$$\mathcal{L}_{v}={\textstyle{\frac{1}{|B|}\sum_{m=0}^{|B|-1}\left(\hat{v}_{m}-R_{m}\right)^{2}}},\quad R_{m}:={\textstyle{\sum_{i=0}^{k}\gamma^{i}r_{t+i},}}$$

where $t$ denotes the timestep of $o_{m}$, $|B|$ is the mini-batch size, and $\gamma$ is the discount factor. An approximation of the advantage function $A_{\theta}(o_{m},a_{m})$ by bootstrapping the value function is used to update the policy. An entropy term $\mathcal{H}(\mathcal{I}^{\pi}_{\theta}(o_{m},\{e_{m}\}))$ is further introduced to encourage exploration and discourage premature convergence [42]. The loss function of this prioritized communication learning phase can be denoted as

	$\displaystyle\mathcal{L}_{\pi}=-{\textstyle{\frac{1}{|B|}\sum_{m=0}^{|B|-1}}}$	$\displaystyle\big{[}\log\mathcal{I}^{\pi}_{\theta}\big{(}a_{m}\mid o_{m},\{e_{m}\}\big{)}A_{\theta}(o_{m},a_{m})$
		$\displaystyle\quad-\sigma_{\mathcal{H}}\cdot\mathcal{H}\big{(}\mathcal{I}^{\pi}_{\theta}(o_{m},\{e_{m}\})\big{)}\big{]},$

where $A_{\theta}(o_{m},a_{m})=\sum_{i=0}^{k-1}\gamma^{i}r_{t+i}+\gamma^{k}\mathcal{I}^{v}_{\theta}\left(o_{k+t}\right)-\hat{v}_{m}$ and $\sigma_{\mathcal{H}}$ denotes a small positive entropy weight.