Graph Potential Field  Neural Network for  Massive Agents Group-wise  Path Planning
Authors: Yueming Lyu
Xiaowei Zhou
Xingrui Yu
Ivor Tsang
Venue: Accepted by TMLR ()

Abstract: Multi-agent path planning is important in both multi-agent path finding and multi-agent reinforcement learning areas.  However, continual group-wise multi-agent path planning that requires the agents to perform as a team to pursue high team scores instead of individually is less studied.  To address this problem, we propose a novel graph potential field-based neural network (GPFNN), which models a valid potential field map for path planning.   Our GPFNN unfolds the T-step iterative optimization of the potential field maps as a T-layer feedforward neural network. Thus, a deeper  GPFNN leads to more precise potential field maps without the over-smoothing issue. A potential field map inherently provides a monotonic potential flow from any source node to the target nodes to construct the optimal path (w.r.t. the potential decay), equipping our GPFNN with an elegant planning ability. Moreover,  we incorporate dynamically updated boundary conditions into our GPFNN to address group-wise multi-agent path planning that supports both static targets and dynamic moving targets.  Empirically,  experiments on three different-sized mazes (up to $1025 \times 1025$ sized mazes) with up to 1,000 agents demonstrate the planning ability of our GPFNN to handle both static and dynamic moving targets. Experiments on extensive graph node classification tasks on six graph datasets (up to millions of nodes) demonstrate the learning ability of our GPFNN.

Published in Transactions on Machine Learning Research (03/2025)
Graph Potential Field Neural Network for Massive Agents Group-wise Path Planning
Yueming Lyu"
Lypa Yueminng@efan.a-start
Centre for Frontier AT Research Institute of High Performance Computing Agency for Science, Technology and Research, Singopore
Xiaowei Zhou
zhousiaaocii@oocccad.ccmm
College of Computer Science and Technology Ocean University of China
Xingrui Yu
yu wol.cingrui@eaaraatttta edu.sg
Centre for Frontier AT Research Institute of High Performance Computing Agency for Science, Technology and Research, Singopore
Ivor W. Tsang
Ivor Tsang Srsang&efar Bet.eeffaraaraaaeeee a-star, edu.sg
Centre for Frontier AI Research
Institute of High Performance Computing
Agency for Science, Technology and Research, Singapore
College of Computing and Data Science, Nanyang Technological University, Singapore
Reviewed on OpenReview: https: // openreview. net/ formm? id= LJHVPWN
Abstract
Multi-agent, path planning is important in both multi-agent path finding and multi-agent reinforcement learning areas. However, continual group-wise multi-agent path planning that requires the agents to perform as team to pursue high team scores instead of individually less studied. To address this problem, we propose novel graph potential field-based neural network (GPFNN), which models valid patential field map for path planning. Our GPFNN unfolds the T-step iterative optimization of the potential field maps T-layer feedforward neural network. Thus, deeper GPFNN leads to more precise potential field maps without the over-smoothing issue. A potential field map inherently provides a monotonic potential flow from any source node to the target nodes to construct the optimal path (w.r.t. the potential decay); equipping our GPFNN with an elegant planning ability. Moreover, we incorporate dynamically updated boundary conditions into our GPFNN address group-wise multi-agent path planning that supports both static targets and dynamic moving targets. Empirically, experiments on three different-sized mazes (up to 1025 x 1025 sized mazes) with up to 1,000 agents demonstrate the planning ability of our GPFNN to handle both static and dynamic moving targets. Experiments on extensive graph node classification tasks on six graph datasets (up to millions nodes) demonstrate the learning ability of our GPFNN.
1 Introduction
Multi-agent, navigation and tracking on a graph is a challenging problem in the field of artificial intelligence, machine learning and robotics, as requires coordination and cooperation among multiple agents to achieve
common goal while avoiding collisions. In this problem, multiple agents corporately move on the graph and
track their (static dynamic) (argets while avoiding collisions with each other (Sharon et al. 2015 Stern
et al.
2019 Lin et. al.] 2022 Surynek
2022. The goal to reduce the total moving cost while catching
*Corresponding author

---

Published in Transactions on Machine Learning Research (03/2025)
many targets as possible. It has many practical applications, such as in warchouse management. traffic
control, unmanned aerial vehicles (UAVs) navigation, and package delivery (Lin et. al. 2022 Surynek 2022
The multi-agent pathfinding (MAPF) is a key subarea of multi-agent navigation and tracking on graphs. It
focuses on constructing a valid path for each agent to its targets without collisions (Surynek) 2022 Felner
et al. 2017). One of the main limitations of current research on the multi-agent tracking problem is scalability.
The multi-agent pathfinding problem is known to be NP-hard, and many of the existing algorithms for solving
it have exponential time complexity in the worst case (Sharon et al. 2015 Goldenberg et al., 2014 Gordon
et al. 2021). This means that these algorithms may not be able to handle large-scale problems with many agents or complex environments.
Moreover, most of the current research on multi-agent pathfinding focuses on solving path planning for pre-assigned one-to-one agent-target pairs (Sharon et al., 2015 Goldenberg et al. 2014 Gordon et al. 2021 Tang et al.] 2024). However, in practice, many situations roquire the agents to perform as team instcad of individually. Moreover, it requires the agents continually search the remaining largets instead of stopping after reaching target, e.g., package delivery from the same company. As result, there is an increasing demand for continual group-wise multi-agent path planning. Current methods designed for one-to-one MAPF cannot be easily extended to continual group-wise multi-agent path planning because of their exponential time complexity and the requirement of an additional target assignment procedure. Finding the optimal target assignment itself is a very challenging combination optimization problem. In addition, in woal-world applications, the targets can move over time, and the agents may need to adapt their paths accordingly. Many of the existing algorithms (Sharon al. 2015 Goldenberg et al.) 2014 Tang et al.) 2024 Felner et al.j 2017 Surynek 2022 Lin et al. 2022 for MAPF assume static target, which can limit their applicability in practical settings.
To address the continual group-wise multi-agent path planning problem, we propose novel graph potential field neural network method. Our method builds upon the graph potential field (Masoud 2008). In contrast to the scalar value formulation for static planning from the start node to the target node in (Masoud 2008), we first formulate the graph potential field in a matrix form to handle multi-agents explicitly. Based on our matrix formulation, we develop our graph potential field neural network that unfolds the iterative optimization of the potential field as T-layer feedforward neural network. Furthermore, we employ a nonlinear log-sum-cxp aggregation as the nonlinear activation function instead of a linear aggregation. This not only reduces the mumeric error but also increases the learning ability of our GPENN. Moreover, we incorporate dynamically updated boundary conditions into our GPFNN to address group-wise multi-agent path planning that supports both static targets and dynamic moving targets. In addition, we further investigate the learning ability of our GPFNN on node classification tasks.
Our contributions are summarized as follows:
To the best of our knowledge, we developed the first graph potential field-based neural network (GPFNN) with planning ability. Our GPFNN unfolds T-step iterative optimization of the potential field maps
T-layer feedforward neural network. Thus, a deeper GPFNN leads to more precise potential field maps. A valid potential field map provides a monotonic potential flow from any source node to the target nodes to construct the optimal path (w.r.t. the potential decay), equipping our GPENN with a planning ability. Morcover, we incorporate dynamically updated boundary conditions into our GPFNN to address group-wise multi-agent path planning that supports both static largets and dynamic moving targets.
Our GPFNN provides general framework for both graph path planning tasks and graph learning tasks (e.g., node classification), which demonstrates both the planning ability and learning ability. This may suggest that our GPFNN may have the potential to serve as a useful neural network architecture for downstream tasks that require both planning ability and learning ability, e.g., multi-agent reinforcement learning.
Empirically, extensive experiments with up to 1,000 agents on up to 1025 x 1025 large maps with both static targets and dynamic targets demonstrate the planning ability of our GPFNN to handle
2

---

Published in Transactions on Machine Learning Research (03/2025)
group-wise multi-agent path planning. Moreover, extensive experiments node classification tasks up to millions of nodes demonstrate the learning ability of our GPFNN.
2
Related Works
2.1 Multi-agent Navigation and Tracking on Graph
The goal of multi-agent navigation and tracking on graph is to find set of collision-free paths for multiple agents to reach their respective goal locations while avoiding collisions with each other and any obstacles in the environment. Multi-agent navigation and tracking on a graph has applications in various domains, including robotics, transportation, and logistics. The problem is challenging due to the combinatorial nature of the search space and the need to ensure that the solutions satisly complex constraints and objectives.
2.1.1 Multi-agent Pathfinding (MAPF)
The multi-agent pathfinding (MAPF) is a key subarca of multi-agent navigation and tracking. The multi-agent pathfinding problem involves finding a collision-free path for group of agents from their initial positions to their respective goal positions while avoiding collisions with each other. This problem is known to be NP-hard and is of practical importance in domains such robotics, transportation, and logistics.
Recent advances in this field have led to the development of elficient algorithms for solving multi-agent navigation and tracking on a graph problems, such as Conffict-Based Search (CBS) (Sharon et al. 2015
Boyarski et al. 2015 Barer et al. 2014), Enhanced Partial Expansion A (EPEA*) Goldenberg et al. 2014] and Independence Detection (ID) Siiverr 2005).
Conflict-Basee Search (CBS) (Sharon et al. 2015) is widely used algorithm for solving the multi-agent pathfinding problem (MAPF). However, it has some limitations that can affect its performance in certain scenarios. CBS has a worst-case time complexity that is exponential in the number of agents, which can make it computationally infeasible for large-scale problems with many agents. This severely limits the practical usage of CBS for large-scale multi-agent navigation and tracking on a graph. Moreover, CBS can not handle the MAPF with dynamic targets.
Surynek 2021) introduce multi-goal multi agent path finding method by extending CBS. Specifically, the approach is based on the decoupling of the problem into two stages: goal vertex ordering stage, where the ordering of goal vertices is determined, and pathfinding stage, where paths for each agent are computed based on the determined ordering. Despite its success to some extent, it is relying on CBS, which is not salable to largo-scale multi-goal multi agent path finding problems.
Some recent works try to address different setting of MAPF. Ma al. (2018) propose to address time- constrained MAPF problems. Dergachev & Yakovlev (2022) try to address MAPF problems with different sized agents. [Svancaaa et al. (2019) and Ma (2021) study the online MAPF problems. For more detailed
recent survey of MAPF, one can check (Surynek 2022 Lin et al. 2022 In addition, one may check (ttenn
et al. 2019 for different setting and variants of MAPF problems.
A closely related subarea is the target assignment and path finding (TAPF) (Ma & Koenig 2016). Different from the pre-determined ggent-target assignment in MAPF, TAPF considers the anonymous agents case (also known as the unlabeled MAPF) that performs the assignment of each target to each agent to minimize the cost (Ma & Koenig 2016 Hoenig et al., 2018: Yu & La Valle 2012). Along this line, Ma & Koenig (2016) study the TAPF problem such that agents are partitioned into teams. Each team is given the same mumber of unique targets (goal locations) as there are agents in the team. Each agent has to move to exactly one target given to its team such that all targets are visited. A conflict-based min-cost-flow algorithm is proposed to minimize the cost. [Hoenig et al. (2018) propose to solve TAPF by leveraging K-best target assignments to create multiple search trees and employing Conflict- Based Search to resolve collisions in each tree, the proposed method is named as CBS-TA. The authors further extend CBS-TA and provide a suboptimal method, called ECBS-TA for fast approximation. Recently, Tang et al. (0033) argue that CBS-TA suffers from poor scalability the number of agents or targets increases. An incremental Target Assignment CBS
3

---

Published in Transactions on Machine Learning Research (03/2025)
algorithm is proposed for acceleration. Besides the above methods, Okumura & Défago (2021) studied the offline and online TAPF, and proposed sub-optimal algorithm, named as TSWAP, for fast computation.
Although these methods achieve good performance for TAPF problems, the problems they studied are different from our focus. The TAPF setting requires the agent to stop once it reaches the target. In contrast, we focus on the continual group-wise planning problems in which the agents that achieve (reach) the target can continue to search for the remaining targets. Moreover, our method supports handling dynamic moving targets, while most TAPF methods cannot.
Besides the research on MAPF and TAPF, many potential field based methods have been proposed for robot
navigation in physical 2D-Euclidean space (Barraquand et al. 1992: Wray et al.) 2016 Daily & Bevly 2008b
Wang & Chirikjian 2000 Masoud 2012). In particular, the harmonic polential field methods take advanlage of the property of no local optima for path planning (Kim & Khosla, 1991 Connolly et al.) 1990 Daily &
Bevly 2008a Panati et al. 2015 Szulezyński ct al.] 2011) However, few of them are developed for graph
planning Masoud 2008). More importantly, how to explore multi-agent graph planning is still unexplored.
2.2 Graph Neural Networks
Recently, graph neural networks (GNN) (Wu et al., 2020) have emerged as state-of-the-art models for graph representation learning, e.g. convolutional graph neural networks (Kipf & Welling 2017 Veličković al. 2018) for node classification tasks. Spectral-based convolutional graph neural network is one important types of convolutional graph neural networks. Spectral-based convolutional neural networks develop from graph signal processing (Shuman et al.) 2013). The key idea of this stream of methods is performing convolution in spectral domain. One typical spectral-based method is graph convolutional network (GCN) Kipf & Welling 2017). It uses the first-order approximation to define graph convolution operation, which is fast and scalable on graphs.
However, over-smoothing (Li ct al. 2018 Oono & Suzuki 2019 Chen et al. 2020 Huang et al. 2020 is found a common issue with graph neural networks (GNNs). Namely, as the depth of GNN grows, the feature of each node tends to be the same. Some methods have been proposed to tackle this issue from different perspectives. Upon vanilla GCN, GCNII (Chen et al.) 2020) solves over-smoothing by adding a skip connection from the input at each layer and adding an identity matrix to the weight matrix. RevGNN (Li el al. 2021: employs reversible connections in the design of deep GNNs, which are free memory consumption bottlenccks. (Xu et al. 2018) proposes the jumping knowledge network to adaptively concatenate the Iearned representations from each intermediate layer. (Rong et al., 2020) proposes IncepGCN that borrows the inception (Szegedy et al., 2016) network structure in computer vision into GNNs model design. Recently, Li et al. 2001 2020b); Dai et al. 2022); Zhou et al. (2024) employ the GNN to address the MAPF problems. Unlike these methods, our work is focused on group-wine wise MAPF problems. Additionally, our GPFNN is capable of handling dynamic largets, whereas existing GNN-based methods are limited to static targels. Furthermore, our GPFNN can scale to highly complex 1025x1025 mazes with dense obstacle configurations, a level of scalability that the experiments in these prior works have not achicved.
3
Graph Potential Field Neural Network
3.1 Graph Potential Field
In this section, we first introduce the graph potential field in (Masoud 2008). Then, we formulate the graph potential field in matrix form to handle multi-agents. Then, we show how to construct valid potential field features of all nodes on the graph by adding virtual boundary nodes.
Given an undirected graph g = (V,&). Let Gij denote the cost weight associated with edge eij E (the cost of moving between node i and node j ). Suppose Gj > 0 for Very E E. Let u, denote the potential associated with node for S < [V| n. The balance condition is defined as
U -u Uj 0,
(1)
Cjj
JEN()
4

---

Published in Transactions on Machine Learning Research (03/2025)
(a) 11xll-siied Moze
(b) Potential Field Map on the Maze. The brighter the color is, the closer to the excit.
(c) An Equivalent Graph
Figure 1: Illustration of a 11 x 11-sized maze, the potential field constructed by GPENN, and equivalent graph of the maze.
where (i) denote the neighbour of node i, i.e., M(1) == BiBBe E E}.
We first formulate the potential field a matrix form. Let the matrix C' with element Ci5 = .q. and the diagonal matrix D with diagonal element Da EjeN(O) a A generalized graph Laplacian matrix can be defined as
L -
(2)
The balance condition of graph potential filed in a matrix form is given in Eq. 3
Lu -I- DI-D-'Cuu-
(3)
We can see that Eq.3) has a trivial solution u u1, which the key reason of the over-smoothing issue of GNNs to construct den-eerneeet potential field. (We will discuss this with more details in section 3.3)
To get non-degenerate graph potential field for path planning, it needs to satisfy the boundary condition besides the balance condition. We associate virtual node in with each node i in the original graph G. Let O, T denote the set of virtual obstacle nodes and virtual target nodes, respectively. The boundary condition for all virtual nodes is
{
6 if the virtual node ē; belongs the obstacle set O if the virtual node ;; belongs to the target set T
(4)
where an upper bound the potential, ie., Vu, E [0, for i E (1..., ,n]
Combine both boundary condition and balance condition, we get
U1 EjEN(O Wiyy + A&b if E EjEN(O Wijli if ET
(5)
where Way ++E miy with the virtual node. We can that X; Ejen() Wij = 1.
25
is the normalized diffusion weight, and X, 1+ 1+
is the weight associated
We formulate the above conditions of a non-degenerate graph potential field in matrix form as
(I (I- - u.
where D is a diagonal matrix with diagonal element Dis 11=1+0 111++E EjEN() ey vector À [Ai, An denotes the diffusion weight of virtual nodes, and vector û [0....., Tnl" denotes the potential of virtual boundary nodes, and denotes the element-wise product operation.

---

Published in Transactions on Machine Learning Research (03/2025)
According to the property of graph potential field in (Masoud 2008). given non-degenerate graph potential field, we can find global minimum of potential (target node) from any source node greedily without suffering from local optimum.
3.2 Architecture of GPFNN
In this section, we first present a general architecture form of our GPFNN. Then, we show a particual form of our GPFNN has a linear rate of convergence to the valid potential field maps.
Our GPFNN have general architecture form as Eq.
U+1 = - (1-o)U'', (a0+0+++M++++ +MU++AUU W:)
(7)
where Ü ("i,.... Und E Raxd denotes the potential of the virtual boundary nodes in d virtual maps and A - . Aa] denotes the diffusion weights associated with the virtual nodes. and M = -D denotes the propagation matrix. And Wf. W E Rdx denotes trainable weight matrix tth layer (it can be shared across layers). The a()) denote an activation function, and is hyper-parameter such that 0 S 1.
It worth noting that each column vector ūj in Ú can be constructed by randomly assigning the type of virtual nodes (f e O or i T) or by design based on domain knowledge. Moreover, the sparse diffusion weight Wij w.r.t. cach edge in M can either be learned or fixed as prior.
Now, we show particular form of GPFNN for path planning, To construct a valid potential field map, we set W = W for t (1,..,,T)) ,T), and set (-)) as Identity map, then we obtain simple beed-forward NN architecture as Eq.
U
= =+11=
a) + a (MU* + -AO
(8)
We can see that Eq. 8 is the Richardson update with a step-size a for solving linear equation
(I U----CCU=AG
99)
Let U denote the solution of the linear equation According to the property of Richardson update (Hack busch 1994), we know that for T-step update (a layered NN), we can achieve the following linear rale of
convergence:
NUT+I-U"11
< + 'CI)) 1' UU
(10)
Se e (1 (1-))T U*|la.
where 11:112 and I|-1|æ denote the spectral norm and Frobenius norm, respectively, And p= [((-a)]+ab-1CC)) When p [111 a I +a DDDi-Clle 1, Eq.0 shows linear rate of convergence.
It is worth remarking that despite the simple NN architecture in Eq. we still learn the diffusion parameter Wij in M to adjust the cost weights associated with the edges in graph G. This can adjust the distance between nodes because even nodes connected by an edge may belong to different classes. A nice property of this simple neural network is that it maintains the linear convergence to U despite the learning parameters in M.
3.3 Relationship with current GNNs
In this section, we compare our GPFNN with current GNNs, and show that a related form of current GNNs converge linearly to a trivial feature map. In contrast, our GPFNN converge linearly to valid potential field map by satisfying boundary conditions.
Given an undirocted graph g (V,E) with adjacency matrix A and diagonal degree matrix D. The GNN layer has a general form (may have other similar variants (Wu et al. 2020)) as follows:
U++l= = (1- +aD -
(11)
6

---

Published in Transactions on Machine Learning Research (03/2025)
When set Wi W I for (1. , and set o(.) Identity map same as the setting of our GPENN, then we have the following NN architecture:
U = (1 a)U' + +aD-AU",
(12)
which is the Richardson update for solving linear equation
[3
- D D
A)U 0.
(13)
which means that all embedding feature vectors same, i.e, 21 Zn z. According to the property of Richardson update (Hackbuschi 1994). we know it
We see that U 1=T is solution of Eq. 13 2q.113
converge lincarly to the trivial solution U = 1z
follows
| U F = (ll - a) + aD-1Alle) U U
(14)
Se (1 M/T U U
where p - + valid potential field map.
This shows a over-smoothing issue in current GNNs for constructing a
Comparod our GPFNN in Eq. with GNNs in Eq. 11 our GPFNN includes a boundary condition on virtual nodes, which is the key solve the over-smoothing issue. Moreover, our GPFNN can learn the diffusion weights to handle weighted graph, while maintains the linear rate of convergence to valid potential field map.
3.4 Optimization Property for GPFNN with Nonlinear Aggregation
In previous subsection, we discuss the optimization property for GPFNN with linear activation o()). In this section, we show how our GPFNN maintain the optimization property with nonlinear aggregation.
To be simple, we assume the the cost Cjj for all edges esy E E. Then, we have X = 1 where d, denotes the degree of the node i.
When fix the weight matrix W W I, the update rule for node i with linear activation is given follows
aft = (1- a.)
Σ
u/
+
03 4 1 d
(15)
1 + d JEN(()
By setting adaptive step size a; for each node
+ d:
a; + di'
(16)
we can achieve that
ut Σ EjeN(() us + 06
u."
(17)
2+ d;
Let 9: log(u;) be mapping between di and u, for all nodes f1..... n), then have
q +1 = log exp(x)) + EeENIo exp(a)) + exp().)
(18)
2+ ++d
The connection between update rule in Eq. 17 and update rule in Eq. 18 is shown in Proposition
The
proof of Proposition T is presented in the Appendix A
1 if O iiET
Proposition Let the boundary condition of potential in original space ū. =
Let ( 119
be mapping between the log-polential q. (T:) and polential (ūs) for E V ().
di = log ((1 6) 5),
(19)
where 8 1 denotes a small constant. Then, mopping a Richardson update (Eq. 17 in original space by Eq. 199 is equivalent. to Richardson update Eq. (8) in the log-space.

---

Published in Transactions on Machine Learning Research (03/2025)
Remarks: Eq. 18
is Log-Mean-Exy nonlinear aggregation, it enables us to update the potential in the
log space instead of the original potential space. In practice, only of for i E (I,..., , is updated in the log-space. We do not need to compute the potential of in the original potential space explicitly by taking advantage of Log-Sum-Expp trick. This updating scheme can reduce the numeric issuc of floot reported in (Wray al. 2016).
With the update rule in Eq.qI8), our GPFNN maintains the optimization property. Namely, performs a T-step Richardson update in the log-space. It is worth to remark that this nonlinear update can reduce the numeric error compared with linear update in original potential space. Thus, our nonlinear update maintain significantly smaller accumulation numeric error compared linear update, especially when T is large.
4 Graph Learning Framework
In this section, we present simple architecture in GPFNN family for graph learning. We fix the weight matrix W = W = for all the T-layers, and apply the non-linear aggregation in Eq. Eq.(18) with adaptive stepsizes a = [a1. ... an] that automatically computed by Eq. (1). Remarkably, our adaptive stepsize scheme more ficxible to update each node. Moreover, it greatly saves the human efforts regarding fine-tuning the hyperparameter [a,.-..,,0 .a,] for each node.
For graph learning problems, learn the parameters of the initial potential neural network and the visual node potential neural network. Details are shown in the following subscctions.
4.1
Simple Structure of GPFNN for Graph Learning
4.1.1 Initial Potential Neural Network
The initial potential of the nodes (U") can be learned using a neural network. The architecture of the Initial Potential Neural Network (IPNN) can either be a simple lincar mapping, or a complex neural network depends on the tasks.
To compatible with the potential update Eq. 18 in log space, we employ the activation function of the last layer of IPNN:
function as the
a (2) log
I 1+ (xex)((2)
= log (1 + exp(2))
(20)
In this work, we employ a three layer architecture as our IPNN given below:
U = (ZW.):
(21)
where = [Z,, ... Zm] denotes a concatenation of m blocks. The 7th block Z given as follows:
Y Dropout(X* X 2
(22)
Y (Y W (
Mean (Y
(23)
Z. = Layer Norm
(24)
where 2i denotes the input feature of nodes after 12i-1)-hop mossage passing. X denotes the initial input node features. The ReI.U(.)), Dro)oul()), Mean(.), and LayerNorm()) denote the ReLU activation function, dropout, mean function and layer normalization function respectively. In addition, we set Wx))).
y(() Noyer
4.1.2 Visual Node Potential Neural Network
The potential of the visual nodes (Ū) can also be learned using neural network. The architecture of the Visual Node Potential Neural Network (VNPNN) can either be same as IPNN, or a more complex neural network teacher model.
8

---

Published in Transactions on Machine Learning Research (03/2025)
(a) node
Euclidean
neighbors
(b) Graph neighbors node (c) Graph neighbors node i (d) d-Feature map with different boundary conditions
with boundary condition
Figure 2: Illustration of the neighbors of node i in the Euclidean topology and the graph topology, and a d-dimensional feature map with different boundary condition on each dimension.
To compatible with the potential update Eq. Bq. in log space, we employ the Log-Sigmoit function as the activation function of the last layer of VNPNN:
(2) = log
(25)
1 exp(-2)
In this work, we employ three layer architecture as our VNPNN given below
Ô = (2W)),
(26)
where == 12,," ... Zm] denotes a concalemation of m blocks. The 4hh block Z; is given as follows:
(1) ( (
(27)
2 ReLU (1) W Y (2)
Mean (ean(Y, (1)
(28)
Z. Lorm
(29)
where X denotes the imput feature of nodes after 2)-hop message passing. X denotes the initial
input node features. In addition, we set y LayerNormi (X ( W)
4.2 Contrastive Regularization between Visual Node Potential and Initial Potential
We provide a regularization technique by introducing a regularization loss between the Visual Node Potential and Initial Potential. The contrastive loss is given as follows:
UU Ū) -
(30)
The contrastive loss la regularize the Frobenius-norm between the initial log-potential and the Visual Node log-potential. It forces the initial log-potential close to the Visual Node log-potential, which provides good prior initial log- log-potential that lcads to fast converge (for graph Richardson update). This is a nice protery that enables us to use a small number of (Richardson update) layers to achieve a near stationary global potential field.
Moreover, when the input feature representation of the same nodes for the IPNN and VNPNN different section
4.1 our loss can be viewed as contrastive learning scheme. This provides way to learn useful representations of nodes that are semantically mcaningful and invariant to certain transformations of the input graph.
5 Fast GPFNN on Grid Worlds
In this section, we show how to apply our GPFNN on grid worlds, and achieve a neat parallel local update for fast. computation. The 2D-grid worlds relate to a sparse graphs with maximum degree larger than

---

Published in Transactions on Machine Learning Research (03/2025)
Potential Field Map
MexpooIDD (3x3)
Index
Collision
MaxUnppal2D (3x3)
One slop Leckodreed Action
Gafb Agent Mask
Agent Preeita Mask
Sate Action
Agent- Position Mask
Apent
Figure 3: Illustration of Network Architecture of Action Decoder
eight. See Figure ] for an illustration. We can see that the maze in Fig ((a) has an equivalent graph in Fig [cc] Thus, computing a valid potential field on the maze (Fig [bb] leads a valid potential field on graph in Fig [(b] (with boundary condition on virtual nodes). The walls and largets mazes plays role of virtual nodes of the embedded equivalent graph.
5.1 Neat parallel local update for fast computation on grids
For 2D-grid world, the cost weight çy We set the ncat parallel local update rule similar to masked 2D average pooling (with 3 x kernel size)
g' This leads the following
of + +EEENNO 10j E V)ng + 1(j E D)a
(31)
9
for all i V, where V denotes the node-set with free update potential parameter, 1 denotes the node-set of boundary condition, and 1()) denote indicator function. See illustration in Fig [(c] The green nodes denote the free updated nodes that belong to node-set V, and the black nodes denote the boundary nodes that belongs to the node-set V.
When we employ the Log-Mean-EEse aggregation, i.e. oxx) = log / Σx exp (Ix) instead of an average map, we have update rule in a log-space for all E V as Eq. 32
exp(4))+
jeN exp (1(j
V)g +1( E D)g))
q
log
(32)
9
The update rule in Eq. 32 can be implemented by Conv2D and Log-Sun-Expp that are fast and stable in modern deep learning toolboxes.
5.2 Cooperative actions for d agents
To take cooperative actions for d agents, we construct d maps, one for each agent. The walls and target sets are the boundary conditions same for all agents. Further, for each agent we add other agents' position as the obstacle nodes to boundary conditions of the 4th map. This results in a d x w x h sized 3D-tensor, where w, denotes the width and height of the grid map. See Figure 2(d) for an illustration.
We employ the T-step update in Eq. (4.
T-layer feedforward neural network, it outputs the feature map UT d x h sized 3D-tensor, where w, h denotes the width and height of the grid map. The feature map U is then fed into an action decoder network compute each agent's action in parallel. The action decoder network computes one-step lookahead of all the agents to avoid a collision. The unsafe lookahead action will be rollback.
Our model can leverage the user preference of the priority of cach agents. When several agents take action the same position, the agent with the highest priority (largest ID in default) will indeed take action to move, and the others' lookahead action will be rollback and stay hold on.
10

---

Published in Transactions on Machine Learning Research (03/2025)
An illustration of the architecture of the action decoder network is shown in Figure 3 The agent-position-mae mask is the one-hot representation of the agents' current positions. The action decoder computes the collision map based on agents' one-step lookahead action. Then, it constructs a tatt-aggnt-maskk Agents with safo-agent-mask one perform the lookahoad action, while agents with safe-agent-mast zero remain in the old position. The action networks consists of a MaxPooling2D layer, a MaxUnPool2D layer. The MaxPooling2D layer enables to compute the maximum potential in a parallel way. The MaxUnPool2D layer is used to find the one-step lookahead position for each agent in parallel.
It is worth to noting that our GPFNN never lead to edge conflict (two agents came across the same edge). This is because each agent treat other agents' as obstacle nodes, its original position always has lower potential than the obstacle nodes. Thus, the agent will stay at the original node instead of moving to other agents along with the directly connected edge. This avoids the edge conflict.
6 Experiments
6.1 Continual Group-wise Multi-agent Path Planning for Static Targets
To evaluate the planning ability of our GPFNN, we first perform empirical studies on group-wise multi-agent path planning tasks with static targets. More specifically, in our experiments, a group of agents navigate on the map to catch a group of static targets. The agents are moving in parallel during each time step. The agents perform as team to catch as many targets possible while using as few time steps as possible. We evaluate our GPFNN on complex 2D grid mazes. We create three different-sized 2D mazes for evaluation, i.e., 129 129-sized mazes, 401 401-sized mazes, and 1025 x 1025-sized mazes. Each sive contains 100 mazes.
We run one trial for each maze among the 100 same-sized mazes with randomly generated non-overlapped targets and agents' initialized positions. For 129 x 129-sized mazes, and 401 x 401-sized mazes, we test four cases with different numbers of agents, namely, 50 agents cases, 100 agents cases, 500 agents cases, and 1000 agents cases. For the large 1025 1025-sized mazes, we test 50 agents and 100 agents cases. The number of static targets is the same the number of agents.
We compare GPFNN with related methods: Conflict-Based Search (Sharnn et al. Based Search (ECBS) (Barer et al. 2014) and Prioritized Planning (P-Planning) (Cáp et al. 2015). For all the baselines, we use the C++ codes in the Multi Robot Planning toolbox 1 For all baselines, we employ random agent-target pair assignment. In all the experiments, we set the number of layers of GPENN to 1000. The maximum moving step for GPFNN is set to 2000. The 'Time out' parameter of CBS is sct to 72, 000 seconds.
2015 Enhanced Conflict-
We employ three metric measure the effectiveness of different methods. The metric employed are listed below:
The score of each trail is defined as the number of targets been caught in the trail. We report the mean scores + Standard Deviation over all trails for evaluation.
Scores:
The success rate is defined as the percentage of the success trails over the total Irails, i.e., SR == Number of Success Traile We said success trail when all the largets in this trail have been caught.
Success Rate:
Total Number of Trails
The finishing time step of a target is the time step that the target has been caught. We report the mean Finishing Time Step + Standard Deviation over all targets caught in all trails for evaluation.
Finishing Time Steps:
The mean scores + std of different methods for 50 agents, 100 agents, 500 agents and 1000 agents cases on different sized mazes are shown in Table I We can observe that GPFNN attains near the maximum scores for each number of agent cases. It significantly perforrs CBS, ECBS and P-Planning regarding the scores. Moreover, we can see that CBS, ECBS and P-Planning obtain large scores on the small mazes,
11

---

Published in Transactions on Machine Learning Research (03/2025)
Table 1: Mean Score + std for different number of agents on different maps (larger is better)
Number of Agents
GPFNN
CBS
ECBS
P-Planning
50 + 0.00
35.55 + 3.46
37.46 3.54
100
100 = 0.00
70.63 + 5.21
73.83 = 5.96
129x129-maze
500
500 = 0.00
377.72 = 17.43
1000
1000 = 0.00
0
845.11 + 26.76
50
50 = 0.00
0
5.25
= 1.56
4.90 = 1.79
100
100 - 0.00
0
0
9.56 = 2.88
401x401-maze
500
499.92 + 0.80
0
55.89 +: 7.13
1000
1000 = 0.00
27.19 6.12
50
49.92 + 0.27
7.68 2.79
1025x1025-mazz
100
99.50 + 4.97
15.21 3.49
while they only achieve very small scores on the challenging large-sized mazes, i.e., 401 401 sized mazes and 1025 x 1025 sized mazes. This shows that these baselines cannot scale up to largo-sized maps.
More experiment results on continual group-wise path planning for static targets and dynamic targets can be found in section C and section D in the Appendix, respectively. Furthermore, we evaluate GPFNN in the TAPF sctting. The experimental results are shown in section E Morcover, we further evaluate the learning ability of our GPFNN in section in the Appendix. The results on six graph datasets (up millions of nodes) demonstrate that our GPFFN achieves competitive node classification accuracy with very small number of parameters.
7 Limitation
Currently, our work focuses on path planning for homogeneous agents. Path planning for multiple heteroge- neous agents presents more challenging problem that needs further investigation. One potential approach is to adopt hierarchical planning strategy. At the high level, our GPFNN could be utilized to perform abstract planning in homogeneous way, while at the low-level, high-resolution grids could be employed to perform a more precise, high-resolution planning tailored to the specific characteristics of the heterogeneous agents. Another limitation is that our GPFNN can not perform real-time applications that require performing path planning in seconds.
8 Conclusion and Future Work
This paper proposed a graph potential fieldbased neural net work (GPFNN) for the group-wise homogeneous multi-agent path planning. Our GPFNN unfolds the optimization steps of the potential field as a T-layer feodforward neural network. Theorctically, field map w.r.t. the depth despite learning the diffusion weights. Empirically, our GPFNN achieves superior performance for up to 1000 agents group-wise path planning on 129 x 129-sized and 401 x 401-sized complex mazes and up to 100 agents on the large-sized 1025 x 1025 mazes. Moreover, our GPFNN supports catching dynamic moving, even adversarial moving targets for 500 agents' cooperative planning on 129 x 129-sized and 401 sizesi complex mazes, and 50 agents' cooperative planning on the large-sized 1025 x 1025 mazes. The experiments on planning tasks demonstrate our GPFNN's strong group-wisc path-planning ability.
GPFNN has lincar convergence rate to valid potential
In addition, empirically evaluated the learning ability of our GPFNN on graph node classification tasks. The experiments six graph datasets demonstrate the learning ability of our GPFNN with small number of parameters. This may show the potential of our GPFFN to handle the tasks that require both planning ability and learning ability, e.g., multi-task learning that supports multi-agent path planning and node action prediction (node classification). Moreover, GPFNN may be a useful component in multi-agent reinforcement learning in tasks requiring path planning and tcam-wise cooperative actions, c.g., multi-agent RL in city package delivery, multi-agent RTS/MOBA games, etc. We leave these interesting applications as one of our future works.
12

---

Published in Transactions on Machine Learning Research (03/2025)
Acknowledgments
This work is supported by Career Development Fund (CDF) of the Agency for Science, Technology and Research (A (A*STAR) (No: C243512014).
References
Max Barer, Guni Sharon, Roni Stern, and Ariel Felner. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In Proceedings of the International Symposium Combinatorial Search, volume 5, pp. 19-27, 2014.
Jerome Barraquand, Bruno Langlois, and J-C Latombe. Numerical potential field techniques for robot path planning. IEEE transactions on systems, man, and cybernetics, 22(2):224 221-241, 1992.
Eli Boyarski, Ariel Felner, Roni Stern, Guni Sharon, Oded Betzalel, David Tolpin, and Eyal Shimony. Tebs: The improved conflict-based search algorithm for multi-agent pathfinding. In Proceedings of the International Symposium on Combinatorial Search, volume 6, pp. 223 225, 2015.
Michal Cáp, Peter Novák, Alexander Kleiner, and Martin Sclocky. Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE transactions on aulomation science and engineering, 12(3): 835-849, 2015.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1735. PMLR, 2020.
C.I. Connolly, J.B. Burns, and R. Weiss. Path planning using laplace's equation. In Proceedings, IEEE International Conference on Robotics and Automation, pp. 2102-2106 vol.3, 1990. doi: 10.1109/RO0 10.0/R 19635.
Hanqi Dai, Weining Lu, Jun Yang, and Bin Liang. Cooperative path planning of multi-agent based on graph neural network. In 2022 34th Chinese Control and Decision Conference (CCDC), pp. 5620 1620-5624, 2022. doi: N0.1109/CCDC55556. 202.2. 2022.1003438.
Robert Daily and David M. Bevly. Harmonic potential field path planning for high speed vehicles. In 2008 American Control Conference, pp. 4609-4614, 2008a. doi: N0.1109/ACC.2088.0
Robert Daily and David M Bevly. Harmonic potential field path planning for high speed vehicles. In 2008 American Control Conference, pp. 4609 4614. IEEE, 2008b.
Stepan Dergachev and Konstantin Yakovlev. Towards complete multi-agent pathfinding algorithm for large agents. In Advances in Computational Intelligence: 21st Mexicon International Conference on Artificial Intelligence, MICAI 2022, Monterrey, Merico, October 24 29, 2022, Proceedings, Part I, pp. 355 367. Springer, 2022.
Ariel Felner, Roni Stern, Solomon Shimony, Eli Boyarski, Meir Goldenberg, Guni Sharon, Nathan Sturtevant, Glenn Wagner, and Pavel Surynek. Search- based optimal solvers for the multi-agent pathfinding problem: Summary and challenges. In Proceedings of the International Sympossum Combinatorial Search, volume 8, pp. 29-37, 2017.
Jakob Foerster, Toannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. Advances in neural information processing systems, 29, 2016.
Meir Goldenberg, Ariel Felner, Roni Stern, Guni Sharon, Nathan Sturtevant, Robert C Holte, and Jonathan Schaeffer. Enhanced partial expansion a. Journal of Artificial Intelligence Research, 50:141 187, 2014.
Ofir Gordon, Yuval Filmus, and Oren Salzman. Revisiting the complexity analysis of conflict-basod scarch: New computational techniques and improved bounds. In Proceedings of the International Symposium on Combinatorial Search, volume 12, pp. 64 64-72, 2021.
13

---

Published in Transactions on Machine Learning Research (03/2025)
Wolfgang Hackbusch. Iterative solution of large sporse systems of equations, volume 95. Springer, 1994.
W. Hocnig, S. Kiesel, A. Tinka, J. Durham, and N. Ayanian. Conflict-based search with optimal task assignment. Proceedings of the International Joinl Conference on Aulonomous Agents and Mulliagent Systems, 2018. URL https://par nsf wttp/bib01oo1100731117
Wenbing Huang, Yu Rong, Tingyang Xu, Fuchum Sun, and Junzhou Huang. Tackling over-smoothing for general graph convolutional networks. arXiv preprint arXix:2008. 09864, 2020.
J.-O. Kim and P. Khosla. Real-time obstacle avoidance using harmonic potential functions. In Proceedings. 1991 TEEE International Conference on Robotics and Automation, pp. 790-796 vol.1, 1991. doi: 10.1109/
19980..191.131683.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.071 2020a.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference on machine learning, pp. 6437 6449. PMLR, 2021.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Thirly-Second AAAI conference artificial intelligence, 2018.
Qingbiao Li, Fernando Gama, Alejandro Ribeiro, and Amanda Prorok. Graph neural networks for decentralized multi-robot path planning. 2020 IEEE/RS! International Conference on Intelligent Robots and Systems (TROS), pp. 11785-11792, 2019. URL https://app semanticscholatt org www.oorrg//oroooo...o..or 2093244311
Qingbiao Li, Weizhe Lin, Zhe Liu, and Amanda Prorok. Message-aware graph attention networks for largo-scale multi-robot path planning. IEEE Robotics and Automation Letters, 6:5533-5544 2020b. URL
https://api. semanticscholar org/CorpusID: :2: 227209291
Wenhao Li, Hongjun Chen, Bo Jin, Wenzhe Tan, Hongyuan Zha, and Xiangfeng Wang. Multi-agent path finding with prioritized communication learning. In 2022 International Conference on Robotics and Automation (ICRA), pp. 10695-10701. IEEE, 2022.
Shiwei Lin, Ang Liu, Jianguo Wang, and Xiaoying Kong. A review of path-planning approaches for multiple mobile robots. Machines, 10(9):773, 2022.
Ryan Lowe, I Wu, Aviv Tamar, Jean Harb, OpenAT Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compettiive environments. Advances in neural information processing systems, 30, 2017.
Hang Ma. A competitive analysis of online multi-agent path finding, In Proceedings of the International Conference on Automated Planning and Scheduling, volume 31, pp. 234-242, 2021.
Hang Ma and Sven Koenig. Optimal target assignment and path finding for teams of agents. CoRR, 05693)
abs/1662.00569. 2016. URL http:://axxxv.or//bbb//s//
Hang Ma, Glenn Wagner, Ariel Felner, Jiaoyang Li, TK Kumar, and Sven Koenig, Multi-agent path finding with deadlines. orXiv preprinl urXiv:1806.0440 04216 2018.
Ziyuan Ma, Yudong Luo, and Hang Ma. Distributed heuristic multi-agent path finding with communication. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 8699-8700 8705. IEEE, 2021.
Ahmad A Masoud. Planning with discrete harmonic potential fields. Mobile Robots Motion Planning: New Challanges, I-TECH, Vienna, Austeria, pp. 335-360) 2008.
Ahmad A Masoud. Motion planning with gamma-harmone potential fields. IEEE Tronsactions on Aerospace and Electronic Systems, 48(4):2786 28001, 2012.
14

---

Published in Transactions on Machine Learning Research (03/2025)
Keisuke Okumura and Xavier Défago. Solving simultancous target assignment and path planning efficiently with time-independent execution. CoRR, abs/2109.04264, 2021. URL httpps:/arxxiv.rrgee www//ba/////ooooo.eo...oo..
04264
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint arXit::905.1099" 2019.
Subbash Panati, Bayanjargal Baasandorj, and Kil Chong. Autonomous mobile robot navigation using harmonic potential field. IOP Conference Series: Materials Science and Engineering, 83, 2015. URL
sttps://aap..smannticccct htt.://aia...rrrrrooroo::::::::a
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020.
Guillaume Sartoretti, Justin Kerr, Yunfei Shi, Glenn Wagner, TK Satish Kumar, Sven Koenig, and Howie Choset. Primal: Pathfinding via reinforcement and imitation multi-agent learning. IEEE Robotics and Automation Letters, 233):2378-238)) 2385, 2019.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rass. Collective classification in network data. AI magazine, 29(3):93-98 2008.
Guni Sharon, Roni Stern, Ariel Felner, and Nathan R Sturtevant. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219:40-66, 2015.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEFE signal processing magazine, 30(3):83-9) 98, 2013.
David Silver. Cooperative pathfinding. In Proceedings of the aaai conference on artificial intelligence and interactive digital entertainmend, volume pp. 117-122, 2005.
Roni Stern, Nathan Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, TK Kumar, al. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of the International Symposium on Combinatorial Search, volume 10, pp. 151 158, 2019.
Pavel Surynck. Multi-goal multi-agent path finding via decoupled and integrated goal vertex ordering. In Proceedings of the AAAI Conference on Arlificial Intelligence, volume 35, pp. 12409 12417, 2021.
Pavel Surynck. Problem compilation for multi-agent path finding: survey. In Lud De Racdt (ed.), Proceedings of the Thirly-First International Joind Conference on Arlificial Intelligence, IJCAT-22, pp- 5615 5622. International Joint Conferences on Artificial Intelligence Organization, 2022. doi: 10.24963 /tt.://///aa..222///1..2 URL https://doi. org/ 10. 24963/ijcai. 2022/783, Survey Track.
Jifi Svancara, Marek Vlk, Roni Stern, Dor Atzmon, and Roman Barták. Online multi-agent pathfinding. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 7732 7739, 2019.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818 2826, 2016.
Pawel Szulezyúski, Dariusz Pazderski, and Krzysztof R. Kozlowski. Real-time obstacle avoidance using harmonic potential functions. Journal of Automation, Mobile Robotics and Intelligent Systems, pp. 59 66, 2011. URL.
Huijie Tang, Federico Berto, and Jinkyoo Park. Ensembling prioritized hybrid policies for multi-agent pathfinding. arXiv preprint arXih:2408.07550, 2024.
Yimin Tang, Zhongqiang Ren, Jiaoyang Li, and Katia Sycara. Solving multi-agent target assignment and path finding with a single constraint tree. In 2023 International Symposium on Multi-Ron Robot and Multi- Systems (MRS), pp. 8 841, 2023. doi: 10.1109 00000///50000172222.222.22
15

---

Published in Transactions on Machine Learning Research (03/2025)
Mariju Knippenberg, Mike Holenderski, and Vlado Menkovski. Time-constrained multi-agent path finding in non-lattice graphs with deep reinforcement learning. In Asian Conference on Machine Learning, pp- 1317 1332. PMLR, 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Yunfeng Wang and Gregory Chirikjian. A new potential field method robot path planning. In Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference Robotics and Automation. Symposia Proceedings (Cal. No. 00CH37065), volume pp. 977-982. IEEE, 2000.
Kyle Hollins Wray, Dirk Ruiken, Roderic A Grupen, and Shlomo Zilberstein. Log-space harmonic function path planning. In 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1511-1516. IEEE, 2016.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on newral networks and learning systems, 32(1):4 24, 2020.
Keyulu Xu, Chenglao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453 5462. PMLR, 2018.
Jingjin Yu and Steven M. Valle. Multi-agent path planning and network flow. CoRR, abs/1204.5717, 2012. wws///////////////////////eeeee/ abs/ /////2224.5555
URL http::/arxiv.oo org/
Dongming Zhou, Zhengbin Pang, and Wei Li. Enhanced causal reasoning and graph networks for multi-agent path finding. In 2024 International Joint Conference on Neural Networks (IJCNN), pp. 1-8, 2024. doi: 10.1109 http:///CCNN000022...........
16

---

Published in Transactions on Machine Learning Research (03/2025)
Appendix
A Proof of Proposition 1
{1
ifEEO
Proposition. Let the boundary condition of potential in original space be ū;
Then, mapping
i
a Richardson update (Eq. 17 in original space by Eq. 19 is equivalent to a Richardson update Eq. 18) 18) in the log-space.
Proof. We first check the boundary condition. When i O, from the mapping Eq. we know that
q: log ((1 - 01 8) + 6)
log ((1 - (1 6) + 6) log(6)
(33)
When i E T, we know that
q = log ((1 (1
= log ((1 - 0) (1 6) + 5) = log(1) = 0
(34)
When belongs to the free node set, i.e., i V, from the mapping Eq. (19 19. and update rule Eq. 17 we know that
dt = log ((1 - -11 (1 -5) +)
u³ + ΣjEN()) uz + ihe
log ((1
)1 +
di +2
1
dg + 1
ut + EjEN(() u/ Thi
-log
)(1 (1- 00)
(35)
d;
+
di +2
((1-4)
u/ ΣjeN(e) (1-
-1 (1-
log
(1 ((-)) 6) + +6)
(36)
d4 2
+2
(1 (1-w)) u1)(1 - -8) EjEN(i) (1 - u-)))(1 8) + (11 - -.,((16))
log
+6)
(37)
+2
d: 22
(1 u1) 8) + EsEN(O) ut)(1 8) + 6) + +(1 +11-ū,)( - 5) + 5
log
(38)
d, +
dg 2
Note that exp (g)) (1 (1) 8) + for j E N(),, and exp (qf) = (1- w1) 6) + 8, and q.
log ((1 (1,(1 (1 8) + 8) it follows that
exp (q:)
+ EjEN()) exp (4)) + exp (ū:)
4. +1 = log
(39)
d; +
+2
exp (g:) + EjEN()) exp (q)) + exp (7.)
log
(40)
+2
B Demonstration of Potential Filed Constructed by GPFNN
We first show a demonstration of the potential field constructed by GPFNN in Figure 4 The number of layers of GPFNN is set to 1000 to construct the potential field. From both the Figure 4(a and Figure [bb] we can observe that the brighter the color is, the closer to the exit in the right-down corner. which shows that the potential field provides an monotonic guide from any position to the exit (if connected). This is vitally important for multi-agent path planning to construct cooperatively moving action toward the targets.
17

---

Published in Transactions on Machine Learning Research (03/2025)
0-
50
100
40
60-
200
80
250
300
350
400
80
100
120
100
200
300
400
(a) Potential Field Map on 129 x 129 sized Maze
(b) Potential Field Map
401 401 sized Maze
Figure 4: Demonstration of the potential field maps constructed by our GPFNN on a 129 x 129-sized maze
and a 401 401-sized maze. The brighter the color is, the closer to the exit.
C Continual Group-wise Multi-agent Path Planning for Static Targets
The success rate of 50 agents, 100 agents, 500 agents, and 1000 agents cases different sized mazes are shown in Table 2] We can observe that CBS, ECBS and Prioritized Planning fail to catch all the targets in any trail. This is because these methods are designed for one-to-one agent-target pair path planning. They cannot perform group-wise multi-agent path planning as a team. The planned path for each individual agent may always have a confict for complex and dense maps. As a result, they fail to catch all largets any trial on complex mazes with dense obstacles. In contrast, our GPFNN performs group-wise siip-wise multi-agent path planning tcam. Our GPFNN implicitly assigns the target to the nearby agent according to the potential field. Thus, our GPENN can handle path planning with large number of agents, while other baselines cannot.
The mean finishing time steps + std for 50 agents, 100 agents, 500 agents and 1000 agents cases on different sized mazes are shown in Table 3 We can observe that GPENN achieves smaller and smaller mean finishing time steps as the number of agents increases. This demonstrates the ability of GPFNN plan multi-agent. paths as a whole team instead of individually. Thus, when the number of agents in team gets larger, GPFNN can find better path planning that catches the largets with fewer steps. In contrast, the baselines CBS, ECBS and P-Planning all perform the multi-agent path planning for the one-to-one agent-target pairs individually instcad of cooperating as team. They only perform planning to avoid a collision but fail to cooperate as a team to catch the group-wise targets. As a result, they perform worse as the number of agents increases for group-wise multi-agent path planning. This can be observed in Table [ and Table 2 in which, CBS failed to output a path for all cases inside the time limitation (72,000 seconds). In addition, both CBS and ECBS fail to output a path for more than 100 agents on all three sized mazes within the time limitation (72,000 seconds).
In addition, P- P-Planning has a zero Success Rate to catch all the targets in each trial from Table 2 and achieves small scores from Table [ This shows that P-Planning may prioritize catching the easy targets (the closed targets) and fail to catch the challenging ones (far away targets). As a result, the mean finishing time steps over the targets successfully caught are small.
see that P-Planning obtains smaller mean finishing time steps from Table 3
Note that
Continual Group-wise Multi-agent Path Planning for Dynamic Targets
In this section, we employ our GPFNN to address the multi-agent group-wiss dynamic path planning on 2D mazes. This task is very challenging because it requires planning team instead of achieving individual
18

---

Published in Transactions on Machine Learning Research (03/2025)
Table 2: Success Rate for Different Number of Agents on Different Maps
GPFNN
CBS
ECBS
P-Planning
50
100%
0
100
100%
0
0
129x maze
500
100%
0
0
1000
100%
0
50
100%
0
100
100%
0
401x401-mazc
500
99%
0
1000
100%
0
0
50
92%
0
0
1025x1025-maze
100
99%
0
O
Table 3:
Mean Finishing Time Steps + Std for different number of Agents on different maps (Smaller is
better)
GPFNN
CBS
ECBS
P-Planning
50
22.43 + 2.50
116.18 = 79.84
122.47 + 46.80
100
15.44 + 1.28
128.21 + 78.11
121.22 43.63
1exx129-mmzz
500
5.65 + 0.27
72.43 + 68.97
1000
3.59 + 0.10
36.0 = 55.73
50
118.89 + 17.56
59.5 107.33
24.36 69.07
100
82.66 + 7.73
11.67 = 50.56
401x401-maze
500
35.35 + 37.76
14.87 = 53.67
1000
20.08 + 0.79
9.07 + 43.22
50
328.46
- 32.07
122.68 + 269.53
1025x1025-maze
100
243.25
= 17.51
46.16 = 180.13
goals. More importantly, the targets are dynamically moving, even adversarially moving, on the 2D mazes with dense obstacles.
D.1 2D-Grid World Problems Setup
In the experiments, N agents are assigned to groups and B, respectively. Both groups A and B agents are dynamically moving on the maze. The mission of group is to catch the agents in group Ouce an agent group A gets in the same position as an agent group B, group A's score plus one, and the agent of group B in this position removed. The mission of group B is catch N static targets. The static targets of group B do not move. Once an agent of group B catches a static target, group B's score plus one, and the target is removed. The group that first attains N score wins the game.
Both 129 x 129-sized mazes, 401 x 401-sized mazes, and the large 1025 x 1025-sized mazes are employed for evaluation. For 129 x 129-sized mazes and 401 x 401-sized mazes, we employ 100 mazes for evaluation, for the large 1025 x 1025-sized mazes, we employ 50 mazes for evaluation. For experiments on 129 x 129-sized mazes, 401 401-sized mazes, we set the number of agents(targots) to 500, i.c., N 500. For experiments on the large 1025 1025-sized mazes, we set N 50. For group A, we employ the policy generated by our GPFNN. For group B, three kinds of policy are employed for comparison: (1) adversarial policy using GPFNN planning to targets with group A's position information,
(2) unaware policy using GPFNN planning to targets without group A's position information, (3) random moving policy with one-step look-ahead collision checking (stay hold on collision will happen).
At cach round (time step), group A's agents first move parallel, then group B's agents move parallel. The initialed position of group A's agents, group B's agents, and the static targets of group are randomly assigned without overlap and collision.
19

---

Published in Transactions on Machine Learning Research (03/2025)
Table 4: Mean Scores + std for Group A (GPFNN) and Group B with different Policy
GPFNN vs Random Group B
GPFNN vs Unaware Group B
GPFNN vs Adversarial Group B
Group A's Score
Group B&s Score
Group A's Score
Group B's Score
Group A's Score
Group B's Score
129-maze
500 +
34.13
6.21
500 + 0
237.13 +11.60
500
251.37 13.49
10Lx401-maze
500 =
14.31 4.12
500 = 0
258. 49:11.40
500 0
311.04 + 33.59
1025x1025-mnan
50 0
0.08 1: 0.27
50 1:
36.30 1: 4.73
49.00 1: 3.58
47.04 4: 2.12
Table 5: Mean Finishing Time Steps + std of Group A (GPFNN) against Group B with different Policy
GPFNN vs Random Group B GPFNN vs Unaware Group B GPFNN vs Adversarial Group B
129x 19-mmaee
37.12 + 10.28
22.25 + 3.79
31.75 4 6.07
201x441-maz
180.10 + 39.97
125.03 + 19.44
191.54 + 40.11
1025x1025-mann
1057.68 227.93
1191.74 + 208.76
1704.12 + 429.23
D.2 Experimental Results for Group-wise Multi-agent Path Planning with Dynamic Targets
The mcan scores of Group A against Group B with different policies are shown in Table 4 From Table we can observe that Group A with GPFNN planning attains the full scores on all the cases except the case against the Adversarial Group B on 1025 x 1025-sized mazes, which shows the power of GPFNN perform the duty of Group A. Note that Group A has an advantage over Group B because of Group A can remove Group B's agents, but Group B can not remove Group A's agents. This advantage is more significant for the dense agents' cases on 129 X 129-sized mazes and 401 x 401-sized mazes.
Moreover, we can observe that Group B with GPFNN planning (Unaware Group and Adversarial Group B) achieves significantly higher scores compared with Random Group B, which shows the importance of planning. Moreover, as the maze size increases, the score of random policy decreases. Particularly, Random Group B attained almost zero scores the large 1025 x 1025-sized mazes, which shows that random walk cannot perform well on large-sized mazes. In addition, the Adversarial Group B attains higher scores on all-sized mazes than Unaware Group B, which shows the ability of GPFNN to take advantage of Group A's position information to increase the scores.
The mean finishing time of Group A catching all N largets against Group B with different policies is shown in Table 5 From Table 5 we can see that the fishing time step increases as the size of the maze increases. Morcover, the Adversarial Group B cases attain larger mean finishing steps compared with Unaware Group B, especially on the large 1025 x 1025-sized mazes, which shows that GPFNN's ' adversarial planning ability (with Group A's position information) to increase the survival time of Group B.
We provide the GIF vidco demonstrations of GPFNN Group A against Adversarial GPFNN Group B in the supplementary materials. In the demonstrations, each red point denotes each Group A's agent, each blue point denotes each Group B's agent, and each green point denotes each static target of Group B. Tn the demo of 10 agents on the 129x129-sized maze, group B (blue) first catches all the static targets (green) and wins the game. In the demo of 20 agents, 50 agents, and 100 agents case the 129x120 maze, group A (red) first catches all Group B's agents (blue) and wins the game. In the demo of 500 agents on the 401 x401-sized maze, group A (red) first catches all Group B's agents (blue) and wins the game. From these demos, we can see that for the dense agents' cases, Group A has more advantage than Group B because Group A can remove Group B's agents during the game process, but Group B can not remove Group A's agents. For the sparse agents' case, Group B with GPFNN still has a chance to win Group A with GPFNN, e.g., 10 agents case. More interestingly, we can observe Group A's team behavior in that agents cooperatively besiege Group B's agents from different roads(direction) on the mazes instead of performing catching individually as a queue.
E Evaluation planning ability in TAPF setting
We further evaluate the planning ability of our GPENN in the TAPF setting. Compared with our continual group-wise planning problems studied in section [ section [ the TAPF setting requires the agent to stop once it reaches the target. In contrast, our continual group-wise planning problems, the agents that achieve (reach) the target can continue to search for the remaining targets.
20

---

Published in Transactions on Machine Learning Research (03/2025)
Table Success Rate for Different Number of Agents on Different Maps(larger better)
GPFNN
CBS-TX TA
ECBS- TA
100%
97%
97%
50
100%
3%
87%
54x54-maze
100
97%
0
76%
200
74%
0
57%
10
100%
0
0
50
100%
0
0
250x250-maze
100
100%
0
0
200
100%
0
0
Table 7:
Mean Finishing Time Steps + Std for different number of Agents on different maps (Smaller is
better)
GPFNN
CBS-TA 70.89 + 11.07
ECBS-TA
10
178.89 + 62.56
70.95 = 11.02
50
233.12 + 50.62
91.01 + 4.32
83.63 + 7.63
54x54-maze
100
239.33 + 60.30
87.94 + 6.47
200
274.35 + 74.01
94.87 + 6.77
10
289.66 + 84.48
50
411.36 + 89.12
250x250-maze
100
458.43 43 + 98.40
200
502.65 + 103.76
We compare GPENN with Conflict-Based Search with Optimal Task Assignment (CBS-TA) (Heengg et al. 2018) and Enhanced Conflict-Based Search with Optimal Task Assignment (ECRS-TA). For all the baselines, we use the C++ codes in the Multi Robot Planning toolbox A In all the experiments, we set the number of layers of GPPNN to 1000. The maximum moving step for GPFNN is set to 3000. The "Time out" parameter of CBS-TA TA and ECBS- -CBSSTAAAEE is set to 72, 000 seconds.
We evaluate all methods on 54 x sized maze and 250 250 sized maze. The mazes used here have wider roads compared with the mazes in our continual group-wise planning setting. For each maze, we test four cases with different numbers of agents, namely, 10 agents cases, 50 agents cases, 100 agents cases, and 200 agents cases. The number of targets is set to the same number as that of the agents. For each case, we perform 100 independent trials with randomly initialized agents' and targets' positions.
The success rate for different numbers of agents on different maps are reported in Table G We can observe that GPFNN achieve consistently higher success rate compared with CBS-TA and ECBS-TA. In addition, we can see that in the 10-agent case on the 54 54 sized maze, both GPFNN and baselines achieve a high success rate. It shows that all the methods Moreover, the success rate of CBS-TA and ECBS-TA decrease fast as the number of agents increases. More importantly, CBS-TA and ECBS-TA obtain zero success rates on the 250 x 250 sized maze, while GPENN achieves 100% success rate. This demonstrates the plamning ability of GPFNN on large maps compared with CBS-TA and ECBS-TA.
perform well the small mazes with small number of agents.
The mean finishing time steps for different numbers of agents on different maps are shown in Table 7 Because the CBS-TA and ECBS-TA only output transitory files for the success cases, ie., all targets have been caught. The mean finishing time steps for both GPFNN and basclines are computed over all success trials. From Table 7 see that CBS-TA and ECBS-TA achieve smaller mean finishing lime steps compared with GPFNN on the small maze. This may show that CBS- TA and ECBS- TA can find better paths on the small mazes. Moreover, we can see that CBS-TA TA and ECBS-TA can not plan for the 250 x 250 sized maze.
21

---

Published in Transactions on Machine Learning Research (03/2025)
F
Evaluation of Learning Ability
Table 8: Graph dataset details for graph node classification.
Name
#Nodes
#Edges
Metric
Cora
2,708
5,429
Accuracy
CiteScer
3,327
4,732
Accuracy
PubMed
19,717
44,338
Accuracy
ogbn-arxiv
169,343
1,166,243
Accuracy
ogbn-produce
2,449.029
61,859,140
Accuracy
ogbn-protcins 132,534
39,561,252
ROC-AUC
We have evaluated the planning ability of our GPFNN in the previous section. In this section, we further evaluate the learning ability of our GPFNN the graph node classification tasks. The goal is to show that our GPFEN has the learning ability and, thus, it may have the potential to handle tasks that require both learning ability and planning ability. We employ simple throe-layer neural networks to learn the initial potential and visual node polential in our GPFNN.
We first evaluate our GPFNN on three large graph datasets. Namely, the ogbn-arxiv, ogbn-products, and ogbn-proteins graph datasets. The ogbn-arxiv dataset represents a citation network between all computer science papers on arXiv, where each node represents a paper and each edge represents citation between papers. The ogbn-products dataset is an Amazon product co-purchasing network, where each node represents product sold on Amazon, and each edge represents that the products are purchased together. The ogbn- proteins dataset is an undirected graph, where each node represents a protein, and each edge indicates different types of biologically meaningful associations between proteins.
To evaluate our GPFNN, we compare with GCN (Kipf Welling 2017 DeeperGCN (Li et al. 2020a and RevGNN (Li al. 2021). The classification accuracy and the number of parameters are shown in Table We report the classification accuracy and the number of parameters of GCN, DeeperGCN and RevGNN from their paper. From Table
observe that GPFNN obtains consistently higher classification accuracy and smaller nunber of parameters compared with GCN. Moreover, GPFNN achieves competitive classification accuracy on ogbn-products and ogbn-arxiv datasets, while it has a very small number of parameters compared with RevGNN. In addition, althongh GPFNN has a significantly smaller number of parameters compared with DeeperGGN, it obtains a higher classification accuracy on ogbn-products and ogbn-arxiv than DeeperGCN.
The experiments of node classification on large datasets show the potential of GPFNN on learning tasks even beyond the primary focus of GPFNN graph path planning tasks. It is interesting to extend GPFNN multi-task learning that supports multi-agent path planning and node action prediction (node classification). Such extension may naturally form a backbone for multi-agent reinforcement learning in tasks requiring path planning and cooperation, e.g., multi-agent RL in city package delivery, multi-agent games, etc. We leave this interesting application as one of our future works.
Table 9: Node Classification Accuracy % (ROC-AUC) and # Parameter of Model ogon-products
ogbn-arxiv
ogbn-proteins
Acc
72.19 = 0.14
81.70 + 0.42
74.45 + 0.17
GPFNN
Parameterr
22780
20106
13756
Acc
71.74
0.29
75.64 + 0.21
72.51 0.35
GCN Kipf & Welling
2017
Parameter
110120
103727
96880
Acc
71.92
0.16
80.98 + 0.20
85.80 + 0.17
DeeperGNN Li al.
2020a)
#arraeeter
491176
253743
2374568
Acc
73.01 + 0.31
83.07 + 0.30
87.74 + 0.13
RevGNN [Li et al.
2021
Parameter
262000
2945007
20031384
22

---

Published in Transactions on Machine Learning Research (03/2025)
Table Summary of classification accuracy (%) results with various depths.
Method
Layers
Std
Dataset
8
16
64
GCN JKNet
81.1
80.4
69.5
64.9
60.3
28.7
19.25
80.2
80.7
80.2
81.1
71.5
4.06
Cora
Incep
77.6
76.5
81.7
81.7
80.0
2.37
GCNIT
80.2
82.3
82.8
83.5
84.9
85.3
1.86
GPENN
82.46
82.31
83.20
83.20
82.81
83.38
0.44
GCN
70.8
67.6
30.2
18.3
25.0
20.0
24.05
JKNet
68.7
67.7
69.8
68.2
63.4
2.45
Citescer
Incep
69.3
68.4
70.2
68.0
67.5
1.08
GCNII* 66.
67.9
70.6
72.0
73.2
73.1
2.91
GPFNN
69.88
70.46
70.58
70.37
70.44
70.9
0.33
GCN
79.0
76.5
61.2
40.9
22.4
35.3
23.30
JKNet
78.0
78.1
72.6
72.4
74.5
2.80
Pubmed
Tncep
77.7
77.9
74.9
OOM
OOM
1.68
GCNII
77.7
78.2
78.8
80.3
79.8
80.1
1.07
GPENN
78.87
80.23
79.54
79.09
79.31
79.09
0.49
We further evaluate the effect the number of layers of GPFNN on three small graph datasets. Specifically, the Cora, CiteSeer and PubMed (Sen et al.] 2008) are employed. Cora, CiteSecr and PubMed (Sen al. 2008) citation networks, where each node is paper with bag-of-words attributes, and each edge indicates the citation relationship between papers. All the details of datasets employed are summarized in Table
We compare GPFNN with GCN Kipf & Welling, 2017 JKNet (Xu et al. 2018 IncepGCN (Rong et al. 2020
and GCNIT (Chen et al. 2020). The number of layers the empirical studies are set to (2,4, 8, 16, 32, 64 The detailed classification accuracy of different methods with different layers are shown Table I0 From Table 10 we can observe that the classification accuracy of GCN and JKNet drop as the depth increases. Moreover, we can see that GPENN achieves competitive classification accuracy compared with the state-of- the-art method GCNII. To mcasure the stability of each method over different depths of models, the standard deviation of the classification accuracy over different layers is shown in the last column in Table I0 It's easy to find that the performance of GPPNN is more stable than all baselines when the depth increases.
G Additional Related Works about Multi-agent Reinforcement Learning
Recently, several deep multi-agent reinforcement learning (MARL) methods are proposed to cooperative control of multi agent systems. In (Lowe et al.) 2017), the authors propose deep reinforcement learning settings. Foerster et al. 2016) proposes novel approach for multi-agent reinforcement learning by introducing communication between agents using a continuous message passing mechanism. The authors introduce a new architecture called CommNet, which consists a shared policy network and commuicatiio module that enables agents send and receive messages.
algorithm called MAAC for multi-agent pathfinding (MAPF) in mixed cooperative-coppeti
Recent work has explored using deep multi-agent reinforcement learning learn policies for solving MAPF. In (Sartoretti et al.) 2019) the authors propose method for multi-agent pathfinding (MAPF) that combines reinforcement learning and imitation learning. The authors introduce which leverages both individual and collective rewards to learn effective policies for MAPF. The PRIMAL algorithm consists of two phases: reinforcement learning phase and an imitation learning phase. In the reinforcement learning phase, each agent learns an individual policy that maximizes its own reward. In the imitation learning phase, agents learn collective policy by imitating the actions of an expert agent, which is centralized planner that produces paths for all agents. However, it can not scale large sized problems. addition, it can not deal with dynamic targets.
algorithm called PRIMAL,
23

---

Published in Transactions on Machine Learning Research (03/2025)
In (Ma al. 2021 the authors propose distributed heuristic approach to the (MAPF) problem. The approach is based on a centralized search that is distributed among the agents, who communicate with each other to coordinate their actions. The proposed algorithm consists of two main phases: a communictiion phase and a planning phase. In the communication phase, each agent broadcasts its current state and receives the states of its neighbors. Based on this information, the agents construct a communication graph that. reflects the current state of the environment. In the planning phase, each agent computes a local plan using a heuristic search algorithm that takes into account the current communication graph. Although the proposed method improves the scalability compared with PRIMAL, the scale of the problems is still limited. Most recently, some works (van Knippenberg et al. 2021 try to employ MARL for time-Consie Cone-Constrained MAPF on general graphs. Recent work (Li et al., 2022) combines MARL with a proposed Prioritized Communication Learning framework that uses a centralized communication ion network to facilitate communication between agents. The agents prioritize their communication channels based on the current state of the environment, and use the prioritized communication channels exchange information about their current plans and goals.
Although Deep MARL methods general and flexible to handle different tasks including MAPF problems, they suffer from scalability issue that arises when dealing with large numbers of agents. As the number of agents increases, the complexity of the joint action space grows exponentially, making it challenging to find good solutions. Moreover, current MARL methods often suffer from slow learning rates and poor sample efficiency, which can limit their applicability real-world settings.
24


Reviews:
[{"review_id": "DnGZXMiwGo", "reviewer": "Reviewer_h2q8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n- The paper is well-structured, with clear sections for theory, architecture, and experiments.\n- The addition of virtual nodes is a simple yet effective technique. It addresses key challenges in MAPF, including. 1. Over-smoothing when the problem is converted to a graph neural network framework, 2. Dynamic weighting in MAPF scenarios.\n- The empirical results demonstrate the method's potential, showcasing strong performance on small—and large-scale problems across diverse metrics.\n\n## Weaknesses:\n- The paper does not delve into how GPFNN compares against state-of-the-art GNN-based planners in terms of computational complexity, scalability, or performance. A clearer discussion or quantitative comparison would strengthen the argument for the proposed method's advantages\n- Evaluations on real-world datasets such as multi-robot path planning in warehouses or traffic management scenarios could validate the method's applicability beyond synthetic mazes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors introduce a method to tackle the multi-agent pathfinding problem (MAPF). Specifically, they draw inspiration from the graph potential field to formulate the problem. The main contribution lies in the idea of adding virtual nodes as boundary conditions to avoid trivial solutions and expand the model's capacity to work in dynamic settings. The authors also provide a theoretical analysis of the advantages of their solution and present empirical experiments to highlight the model's performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the Weakness.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rTlrGVlN5Q", "reviewer": "Reviewer_1xdK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n\n1. The GPFNN introduces a novel approach by modeling potential fields as a neural network, effectively addressing over-smoothing issues and enabling scalable optimization.\n\n2. Demonstrated success on large-scale problems, including mazes up to 1025 × 1025 and tasks involving up to 1,000 agents, highlights its capacity to handle complex and large-scale environments.\n\n3. Extensive experiments with multiple baselines show the method's superiority in terms of planning efficiency, success rates, and finishing time across various test cases.\n\n## Weaknesses:\n\n1. The experiments are confined to controlled settings, leaving its practical applicability in real-world, heterogeneous, and dynamic environments uncertain.\n\n2. The computational cost of the GPFNN's deeper architectures and multi-agent simulations is not clearly addressed, which might pose challenges for real-time applications.\n\n3. The method assumes uniform agent capabilities and objectives, which might limit its effectiveness in scenarios with heterogeneous agents or complex cooperation dynamics.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a Graph Potential Field Neural Network (GPFNN) for group-wise multi-agent path planning, addressing scalability and over-smoothing issues in existing methods. It incorporates dynamic boundary conditions and demonstrates improved performance in controlled scenarios.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please see the Weaknesses above. I would expect these points to be more clearly addressed in the conclusion. \n\n2. Add a Limitations sections where limitations such as computational costs and assumptions on agents are more clearly summarized", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "x2yVFQkeV0", "reviewer": "Reviewer_DF4B", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper offers an interesting perspective on the MAPF task by treating it as a graph of paths with obstacles and moving agents, effectively leveraging GNN architecture to exploit potential field characteristics for given problem states.\n\nWeaknesses:\n\n- The authors demonstrate insufficient awareness of the TAPF variant, despite its critical relevance. While \"target assignment\" is briefly mentioned (pp. 1-2), the paper fails to acknowledge significant prior work, including the optimal algorithm [0], CBM [1], CBS-TA [2], and TSWAP [3].\n- Argument\n    - Lists “learning ability” as part of contribution, but the experiments are not in the body but in one of Appendices.\n    - The assumption regarding potential fields is overly optimistic. The paper incorrectly suggests that valid potential fields guarantee monotonic flow and optimal paths, when in fact:\n        - Monotonicity is not guaranteed due to local minima and obstacles\n        - Potential fields only ensure feasible paths, not optimal or monotonic ones\n        - Even the cited Masoud (2008) paper does not support the claim about potential fields avoiding local minima\n    - There is no justification given as to why we would expect the *collision-free* network to perform well on other tasks like node classification.\n- Evaluation\n    - Eval is unfair, comparing the proposed method to the algorithms specifically written to solve *classic* MAPF when `libMultiRobotPlanning` clearly has task-assignment variants.\n    - With node classification as well, the quantitative comparisons aren’t fair either unless the trade-off with model size is justified; given a fixed amount of data, the performance strongly depends on model size (scaling laws).\n- Presentation\n    - It took some time just to know that this paper is about TAPF, which I could barely notice before skimming the Supplementary material\n    - Paper flow is confusing. Section 4 is devoted to graph learning represented by node classification which isn’t addressed until Appendix E and not the main point of the paper. Also, the abbreviations IPNN and VNPNN are **not** used in the Appendix.\n    - Figures 1 and 4: presenting mazes with exit goal is not very representative of MAPF; the potential field would be better with a random goal within the maze\n    - Redundantly duplicate contents in 4.1.1 and 4.1.2. Just describe the specification\n    - Many uses of `\\citep` when `\\citet` is appropriate\n    - Too many “[~]ing ability of our GPFNN” (x12?)\n    - 2nd column of Table 1 is missing its name (No. of agents)\n    - Numerous writing errors/typos.\n- Confusions\n    - I am confused by the very first sentence of abstract. Path planning and pathfinding are pretty much the same thing, and MARL is a method to tackle it.\n        \n        > Multi-agent path planning is important in both multi-agent path finding and multi-agent\n        reinforcement learning areas.\n        > \n    - Nowhere in the manuscript is it written the training details about action decoder: data, batch size, learning rate, optimizer, etc.\n    - If architecturally designed to avoid collisions, why would it fail in some cases?\n    - EPEA* is first introduced as one of multi-agent solvers just to be rejected 2 paragraphs later?\n    - It is not clear even whether the potential field network itself is optimized before or together with the action decoder. Or is it that message passing inside the GNN is expected to propagate something like state values from goals?\n    - What do you mean by a “visual node”?\n    - LSE doesn’t sound necessary when feature values are expected to vary to some extent. Wray, et al. (2016) only suggested the use of LSE for there being a precision issue around near-1 floating points. The standard average pooling feels right to me for this purpose.\n    - As in Section 4.2, is IPNN used only as a regularizer in Appendix E? You could use KL Divergence or something instead of MSE.\n    - Both section 4 and Appendix E alltogether, but it’s also not fair highlighting #Parameter of GPFNN when GCN is smaller.\n\n---\n\n[0] Yu, Jingjin, and Steven M. LaValle. \"Multi-agent path planning and network flow.\" Algorithmic Foundations of Robotics X: Proceedings of the Tenth Workshop on the Algorithmic Foundations of Robotics. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013.\n\n[1] Ma, Hang, and Sven Koenig. \"Optimal target assignment and path finding for teams of agents.\" arXiv preprint arXiv:1612.05693 (2016).\n\n[2] Hönig, Wolfgang, et al. \"Conflict-based search with optimal task assignment.\" Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. 2018.\n\n[3] Okumura, Keisuke, and Xavier Défago. \"Solving simultaneous target assignment and path planning efficiently with time-independent execution.\" Artificial Intelligence 321 (2023): 103946.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a GNN-based approach to single-group target assignment and pathfinding tasks (TAPF, also known as anonymous/unlabeled MAPF). The work has practical applications in warehouse automation, where robots need to efficiently move items regardless of specific agent-goal combinations. The proposed GPFNN seems to comprise two main networks: a GCN to sequentially convolute a given maze's graph structure and construct a potential field, and a collision-aware neural decoder that processes this potential field to generate valid actions, both for all agents. The authors evaluate GPFNN against a few widely known algorithms used for the classic MAPF task.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Although I admire the idea of solving MAPF using a GNN, I believe this paper needs a fundamental rewrite to be accepted.\n\n- [critical] Conduct a comprehensive literature review around TAPF\n- [critical] Clarify the argument structure\n- [critical] Implement fair evaluation in accordance with existing works\n- [critical] Improve presentation & writing\n    - It would also be helpful visualizing the solving process e.g., a tiny maze with two agents going home", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The major concern was about the problem setup, e.g., the lack of clarity about the difference between MAPF and TAPF settings or why the authors did not evaluate GPFNN on TAPF tasks. I suggest the authors to invest more time on alleviating this issue for their final submission. It would be great if the authors could evaluate GPFNN for the TAPF setup too. 

However, I do not think the concerns invalidate the soundness of the approach. I would like to recommend acceptance since this is an interesting submission with ideas from potential-based path planning algorithms. I believe the work is solid and convincing from the perspective of both theory and experiments.
Decision: Accept (poster)