# Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding

Carmel Shabalin  Omri Kaduri  Roni Stern

###### Abstract

Multi-agent path finding (MAPF) is the problem of finding paths for multiple
agents such that they do not collide. This problem manifests in numerous real-
world applications such as controlling transportation robots in automated
warehouses, moving characters in video games, and coordinating self-driving
cars in intersections. Finding optimal solutions to MAPF is NP-Hard, yet
modern optimal solvers can scale to hundreds of agents and even thousands in
some cases. Different solvers employ different approaches, and there is no
single state-of-the-art approach for all problems. Furthermore, there are no
clear, provable, guidelines for choosing when each optimal MAPF solver to use.
Prior work employed Algorithm Selection (AS) techniques to learn such
guidelines from past data. A major challenge when employing AS for choosing an
optimal MAPF algorithm is how to encode the given MAPF problem. Prior work
either used hand-crafted features or an image representation of the problem.
We explore graph-based encodings of the MAPF problem and show how they can be
used on-the-fly with a modern graph embedding algorithm called FEATHER. Then,
we show how this encoding can be effectively joined with existing encodings,
resulting in a novel AS method we call MAPF Algorithm selection via Graph
embedding (MAG). An extensive experimental evaluation of MAG on several MAPF
algorithm selection tasks reveals that it is either on-par or significantly
better than existing methods.

###### keywords:

Multi-agent path finding, Artificial Intelligence, Algorithm selection, Graph
embedding

††journal: Arxiv

[bgu]organization=Ben Gurion University of the Negev, addressline=Beer Sheva
blvd 1, city=Beer Sheva, postcode=84105, country=Israel

##  1 Introduction

Multi-Agent Path Finding (MAPF) is the problem of finding paths for a group of
agents, moving each agent from its initial location to a designated target
location. The main constraint in MAPF is that the agents must not collide.
MAPF has received significant interest recently in the scientific community
and in industry. Practical applications include controlling transportation
robots in automated warehouses [1], coordinating self-driving vehicles in
intersections [2], pipe-routing in gas plans [3], embedding virtual network
requests in computer networks [4], and moving characters in video games [5].
Finding an optimal solution to MAPF with respect to various optimization
criteria is known to be NP Hard [6, 7]. Nevertheless, a range of practical
algorithms that guarantee optimality exists [8, 9]. It has been shown that
these algorithms are able to find optimal solutions to MAPF problems with more
than 100 agents with less than one minute of runtime [10].

Different optimal MAPF algorithms employ different problem-solving techniques.
For example, EPEA* [11] employs a heuristic search technique, BCP [12] uses
optimization techniques, and SAT-MDD [13] compiles MAPF to Boolean
Satisfiability. Correspondingly, different solvers work best for different
MAPF instances, and no algorithm has emerged to dominate all others. The
variance in performance can be great, where some algorithms perform poorly in
some instances but significantly outperform all others in other instances. On
a recently performed extensive comparison of 5 optimal MAPF algorithms [14],
it was shown that even the least effective algorithm had some grids in which
it was able to solve instances with 4 times more agents than all other
evaluated algorithms. Thus, developing methods for selecting the best optimal
MAPF search algorithm for a given instance is a worthwhile endeavor.

The problem of determining which algorithm from a given set of algorithms is
expected to perform best on a given problem instance is known as the Algorithm
Selection (AS) problem [15, 16].111Technically, this problem is called the
_per-instance AS_ problem. Several recent works have developed AS techniques
for optimal MAPF [17, 18, 19]. They used supervised learning to train a
classifier that chooses the best optimal MAPF algorithm for a given MAPF
instance, from a portfolio of optimal MAPF algorithms that include EPEA* [11],
ICTS [20], SAT-MDD [13], CBSH [21], and Lazy CBS [22]. A key challenge faced
by all prior work on AS for optimal MAPF is how to encode a given MAPF
instance, as an input to the supervised learner. Kaduri et al. [17] proposed
to encode a MAPF problem as a vector of hand-crafted MAPF-specific features
[17], such as the average length of the shortest path between the start and
goal locations. Others [19, 18] proposed to cast a MAPF instance as an image.

Ren et al. [18] mentioned the possibility of encoding a MAPF instance as a
graph comprising the shortest paths of the different agents. However, they
consider this method to be “not a deployable algorithm selector in any
reasonable sense,” since it could not be used on any MAPF problem not observed
during training. The first contribution is a novel encoding of the MAPF
instance called FG2V, that fully utilizes the power of graph embedding
algorithms by encoding the entire graph, augmented with artificial edges
marking the start and target vertices of every agent. This embedding is done
using FEATHER [23], a modern graph embedding algorithm that can be used on-
the-fly on any given graph. The resulting embedding yields superior results in
most cases, but not always.

In general, neither FG2V nor any of the existing encodings completely captures
all aspects of the encoded MAPF instance. The second contribution is a simple
method for integrating multiple encodings, which enables a more comprehensive
encoding of the problem. This method can be used with different embeddings in
a seamless manner. The resulting AS method is called MAG. Our third
contribution is a comprehensive evaluation of MAG on a standard benchmark over
three different AS tasks, which differ in how similar are the train and test
instances. Our results show that MAG is superior to baseline methods,
demonstrating the first effective use of graph embedding for solving MAPF
problems. All our code and datasets will be made publicly available to the
community.

##  2 Background

For completeness, we provide here a brief background on MAPF, AS for MAPF, and
graph embedding.

###  2.1 MAPF

A MAPF problem instance is defined by a tuple $\langle k,G,s,t\rangle$ where
$k$ is the number of agents, $G=(V;E)$ is an undirected graph,
$s:[1\ldots,k]\rightarrow V$ maps an agent to its source vertex, and
$t:[1,\ldots,k]\rightarrow V$ maps an agent to its target vertex. Initially,
each agent is in its source vertex. In every time step, each agent either
waits in its current vertex or moves to one of the vertices adjacent to it. A
single-agent plan for agent $i$ is a sequence of move/wait actions that moves
$i$ from $s(i)$ to $t(i)$. A solution to a MAPF instance is a set of single-
agent plans, one for each agent, such that the agents do not collide with each
other. In the classical MAPF problem, the cost of a solution is either the sum
of actions in all single-agent plans or the number of actions in the longest
single-agent plan. The former cost function is known as sum-of-costs (SOC) and
the latter is known as makespan. We measured solution cost in terms of SOC in
our experiments, but most of our contributions are agnostic to the chosen cost
function. MAPF extensions that consider non-unit action costs, large agents,
and continuous time have been explored [24, 25, 26]. In this work, we focus on
classical MAPF.

Optimal classical MAPF algorithms are classical MAPF algorithms that are
guaranteed to return optimal solutions according to a predefined solution cost
function. Different optimal algorithms have been proposed for solving
classical MAPF problems. Prime examples are EPEA* [11], SAT-MDD [6], CBS [27,
21] and its many extensions, BCP [12], Lazy CBS [22], and ICTS [20]. These
algorithms apply a range of techniques: some use heuristic search on dedicated
state spaces, other compile the problem to Boolean Satisfiability (SAT) and
call an off-the-shelf SAT solver, while others borrow ideas from constraint
programming. No algorithm fully dominates the other, and different problems
are solved best with different algorithms. This raised the need for an
automated way to select which optimal MAPF solver to use for a given problem.

###  2.2 AS for MAPF

Previously proposed AS methods for MAPF followed a standard supervised
learning paradigm, and differ mainly in the type of features they extract.
Sigurdson et al. [28] and Ren et al. [18] mapped a given MAPF problem to an
image and extracted image-based features with a Convolutional Neural Networks
(CNN). Kaduri, Boyarski, and Stern [17] proposed a set of hand-crafted, MAPF-
specific features, such as the number of agents divided by the number of
unblocked cells in the grid. We refer to these features as the KBS features.
As noted above, Ren et al. [18] also explored the potential of using features
that are based on mapping the given MAPF problem to a graph and using a _graph
embedding_ method. While their exploration showed that graph embedding can
provide useful features for MAPF AS, they do not provide a practical method to
use it since it could not be used on any MAPF problem not observed during
training. We overcome this limitation in our work.

Kaduri et al. [14] distinguished between three types of AS problems for MAPF:
(1) in-grid AS, (2) in-grid-type, and (3) between-grid-type. In-grid AS means
the train and test problems are all from the same underlying graph. In-grid-
type means the train and test problems are on different grids, but their grids
have similar topologies. Between-grid-type means that graphs in the train and
test problems are completely different, e.g., training on maze-like graphs and
testing on graphs that represent roadmaps in a city. Most prior work has
focused on the in-grid AS problem, which is, of course, significantly easier.

###  2.3 Graph Embedding Algorithms

Node embedding methods are algorithms for encoding a node in a graph into a
low-dimensional continuous vector [29]. Similarly, graph embedding methods are
algorithms for encoding an entire graph $G$ into a low-dimensional continuous
vector [29], referred to as the _embedding_ of $G$. Ideally, graphs with
similar structure will have embedding that are close in terms of their
Euclidean distance. Graph embeddings have proven to be useful features for
various machine learning tasks such as classification [30].

Graph2Vec [31] is a neural graph embedding algorithm that accepts a set of
graphs and outputs an embedding for each graph by analyzing local neighborhood
of their nodes. It runs stochastic gradient descent to optimize a loss
function that ensures similar graphs in the input set of graphs will have a
similar embedding. Notably, it cannot be effectively used on other graphs
without re-training, and thus its usefulness for our purposes is limited.
FEATHER [23] is a recently proposed algorithm that serves as both a node
embedding and a graph embedding algorithm. Its embedding is based on the
likelihood of reaching each node in a random walk. Unlike Graph2Vec, it does
not require an optimization step, and can reasonably used to embed a single
graph. The embeddings created by FEATHER have shown to be effective in node-
level and graph-level machine learning tasks, such as classifying fake users
in a social network and link prediction. FEATHER has an additional positive
property that it describes isomorphic graphs with the same representation and
exhibits robustness to data corruption.

##  3 Method

In this section, we describe our AS method for choosing optimal classical MAPF
algorithms called MAPF Algorithm selection via Graph embedding (MAG). MAG
works as follows. First, it encodes the given MAPF problem as a graph. Then,
it creates an embedding of the resulting graph with FEATHER. The resulting
vector is added to a set of previously proposed MAPF-specific features
extracted from the given MAPF problem, and used to solve our AS problem using
supervised machine learning. Next, we describe each of these steps in more
detail.

###  3.1 Encoding MAPF as a Graph

We consider two ways to encode a MAPF problem $\Pi=\langle k,G,s,t\rangle$ as
a graph. The first encoding method, called G2V, was previously proposed by Ren
et al. [18]. G2V encodes $\Pi$ by extracting from $G$ that induced subgraph
that includes only nodes that are on a shortest path between the source and
the target of an agent. In more detail, G2V computes for each agent the
shortest path from its source to its target while ignoring all other agents.
Then, we construct a graph that contains only the nodes on these shortest
paths, adding an edge between any pair of nodes on these shortest paths that
have an edge between them in the original MAPF problem. Note that the
resulting graph may be disconnected.

The benefit of G2V is that the resulting graphs are significantly smaller than
$G$. However, these graphs lose information: they do not consider regions on
$G$ that are not on the agents shortest paths. These regions may be important
to consider when the corresponding MAPF problem is particularly difficult and
agents must move away from their shortest paths. To address this limitation of
G2V we propose _FullG2V_ (FG2V), which uses the entire graph $G$ to encode the
given MAPF problem. To include details about the MAPF problem beyond $G$, the
graph outputted by FG2V includes an artificial edge for every agent between
its source and target. Formally, for a MAPF problem $\langle
k,G=(V,E),s,t\rangle$ FG2V outputs the graph
$G^{\prime}=(V^{\prime},E^{\prime})$ where $V^{\prime}=V$ and
$E^{\prime}=E\cup\\{(s(i),t(i))\\}_{i=1}^{k}$. Figure 1 illustrates G2V and
FG2V on a simple MAPF problem on a 4-neighborhood grid.

Figure 1: An example of the G2V and FG2V encoding methods.

###  3.2 Embedding the Graph

To embed the encoded graph into a vector space, we used the FEATHER algorithm
[23]. FEATHER creates a graph embedding by first embedding each of the graph
nodes and then pooling the resulting vectors to a single vector of size 500.
Unlike other graph embedding techniques, it does not require a-priori
training. Consequently, the features extracted using FEATHER can be extracted
and used in a meaningful way even for graphs created for MAPF problems that
are not in the training set. This is key to allowing graph embedding features
to be used for optimal MAPF AS methods.

Note that the default pooling method in FEATHER is “mean”. This means the
graph embedding is created by taking the mean over its constituent node
embeddings. We observed that using mean pooling did not perform well in our
context, i.e., led to poor classification results when used as features. The
reason for this is that mean pooling diminishes the impact of the artificial
edges added between the source and target of each agent. Thus, MAPF problems
on the same graph yielded very similar embeddings. To overcome this, we
configured FEATHER to use “max” pooling, which emphasizes small differences
between graphs created from MAPF problems on the same grid. This yielded
significantly better results when training the AS classification model.

###  3.3 Feature Extraction and Learning

For a given MAPF problem $\Pi$, MAG uses G2V and FG2V to create two graphs
$G_{\textit{G2V}}$ and $G_{\textit{FG2V}}$ that encoding $\Pi$. Then, it
creates two graph embeddings $v_{\textit{G2V}}$ and $v_{\textit{FG2V}}$ by
applying FEATHER on these graphs. It also creates a vector $v_{\textit{KBS}}$
by extracting all the MAPF-specific features proposed by Kaduri et al. [17].
Finally, MAG concatenates $v_{\textit{G2V}}$, $v_{\textit{FG2V}}$, and
$v_{\textit{KBS}}$. The resulting vector is the features MAG uses for
training. The training process itself is a straightforward multi-class
supervised learning process, where every instance is a MAPF problem instance
and the label is the fastest algorithm for that instance within our portfolio
of algorithms. Figure 2 illustrates the feature extraction and training
process. Note that more sophisticated approaches to AS exists in other domains
[16], e.g., methods that involve runtime predictions. This is left for future
work.

Figure 2: Diagram of the MAG feature extraction and training process.

##  4 Experimental Results

In this section, we present an experimental evaluation of MAG on a standard
publicly available grid-based MAPF benchmark [32]. This benchmark contains 33
grids arranged into seven _grid types_ : video games (denoted as “game”
grids), city maps (“city”), maze-like grids (“maze”), grids arranged as rooms
with narrow doors between them (“room”), open grids (“empty”), open grids with
randomly placed obstacles (“random”), and grids that are inspired by the
structure of warehouses (“warehouse”). Figure 3 shows an example grid from
each type.222The images were taken from the MovingAI repository [33], which
hosts the grid MAPF benchmark we used [32]. The benchmark includes _scenario
files_ for each grid. Each scenario file contains source and target locations
for as many as 1,000 agents.333Every scenario file contains 1,000 pairs of
start and target locations, except for grids that are too small to occupy that
many agents. The scenario files of each grid are grouped into two sets. In the
first set of scenario files, denoted _Random_ , the agents’ source and target
locations are located purely randomly. In the second set of scenario files,
denoted _Even_ , the agents’ source and target locations are evenly
distributed in buckets of 10 agents according to the distance between each
agent’s start and target. Only the scenarios from the Even set were used, as
they represent a more diverse set of MAPF problems.

In total, the training sets in our experiments included an average 3,000
instances for each map. The entire training process (across all training set
instances) required approximately 10 to 12 hours, including feature creation,
training, and hyperparameter tuning. The runtime required for feature
extraction of a single instance was a single second on average, mostly devoted
to running FEATHER. The prediction (inference) runtime of our XGBoost model is
also extremely fast, since it is not a large deep NN. Thus, the overall
runtime required to obtain the AS predictions for all our models was
negligible compared to the running time of the chosen AS algorithms. All
experiments were run on a server with an Intel 12th Gen i7-12850HX 2.10 GHz
CPU, 64.0 GB RAM, and a 64-bit OS. We are fully committed to making the code,
datasets, and results publicly available once the paper is accepted.

Figure 3: An example grid from each of the grid types in our benchmark, From
left to right: empty, random, warehouse, game, city, maze, and room.

###  4.1 Experimental Setup

We performed three sets of experiments, one for each of the AS problem setups
defined by Kaduri et al. [14]: in-grid, in-grid-type, and between-grid-type.
To train and evaluate MAG in each setup, we used the publicly available
dataset of Kaduri et al. [14], which includes results for running a set of
optimal MAPF solvers of the entire MAPF benchmark mentioned above.
Specifically, results for the following optimal MAPF solvers are available in
this dataset: ICTS [20], EPEA* [11], SAT-MDD [13], CBSH [21], and Lazy CBS
[22]. A time limit of 5 minutes was imposed for each run. This time limit is
common in the Optimal MAPF literature [20, 27, 11].

####  4.1.1 Baselines

We compared MAG against two baselines:

  * 1.

KBS. The AS method by Kaduri, Boyarski and Stern [17], which uses only their
hand crafted features.

  * 2.

G2V. The AS method described by Ren et al.[18], which uses only the G2V
encoding. To extract features from the G2V graph, we used the FEATHER graph
embedding.444This differs from Ren et al., who used Graph2Vec. As explained
earlier, Graph2Vec is not a practical method for our problem, since it
requires knowing a-priori the graphs to embed.

We do not compare against baselines that always choose the same algorithm, as
Kaduri et al. [32] already established that such baselines yield poorer
results compared to KBS. Prior work already established that AS with the KBS
features yielded better results In addition, we performed an ablation study
for MAG, and report on results for AS methods that use different subsets of
features. Namely, FG2V \+ G2V KBS \+ FG2V KBS \+ G2V and FG2V. Note that KBS
\+ G2V \+ FG2V is exactly MAG. For training, we used XGBoost [34], a well-
known supervised learning algorithm. Preliminary experiments with other
learning algorithms, such as Logistic Regression and Random Forest, yielded
weaker results. The hyperparameters of XGBoost were tuned by performing a
4-fold cross-validation over the training set, for each AS setup.

####  4.1.2 Metrics

To measure the performance of each AS method, we considered the same metrics
as Kaduri et al. [14].

  * 1.

Accuracy (Acc). Ratio of instances where the AS method returned the fastest
MAPF algorithm.

  * 2.

Coverage (Cov). Ratio of MAPF instances solved under the 5-minutes time limit.

  * 3.

Runtime (RT). Average runtime in minutes to solve a single MAPF instance with
the selected MAPF solver.555MAPF instances that were not solved under the
5-minutes time limit were regarded as having a runtime of 5 minutes. This was
also done by prior work on AS for MAPF [17, 18].

A limitation of the RT metric is that it gives more weight to MAPF instances
that take more time to solve. To address this limitation, we propose a novel
metric that considers the runtime of an AS method with respect to the runtime
of an _Oracle_ AS method, which always selects the fastest algorithm for every
MAPF instance. No practical AS method can perform better than Oracle, which
has accuracy and coverage of 1.0, and the smallest possible runtime. We define
the _regret_ of an AS algorithm on a specific MAPF instance as the percentage
of runtime the chosen MAPF instance required over the runtime of the Oracle
for that instance. Formally, for an AS method Alg and a MAPF instance $\Pi$,
let $\textit{Alg}(\Pi)$ denote the runtime required to solve $\Pi$ using the
MAPF algorithm chosen by Alg for $\Pi$. Similarly, $\textit{Oracle}(\Pi)$ is
the runtime required to solve $\Pi$ using the MAPF algorithm chosen by Oracle.
The _regret_ of Alg for $\Pi$ is defined as follows:

$\%Rg(Alg,\Pi)=100\cdot\frac{Alg(\Pi)-Oracle(\Pi)}{Oracle(\Pi)}~{}~{}~{}$ (1)

The regret of Oracle is by definition zero, and AS methods with low average
regret values are, in general, preferred. Note that since all solvers are
optimal MAPF solvers, all solvers return solutions of exactly the same cost.
Thus, comparing solution quality is redundant.

###  4.2 In-Grid Results

| All | Avg
---|---|---
Metric | Acc | Cov | RT | Acc | Cov | RT | %Rg
KBS | 0.83 | 0.98 | 0.549 | 0.88 | 0.99 | 0.41 | 12.4
G2V | 0.81 | 0.97 | 0.589 | 0.87 | 0.98 | 0.45 | 25.4
MAG | 0.85 | 0.99 | 0.514 | 0.89 | 0.99 | 0.40 | 9.0
Oracle | 1.00 | 1.00 | 0.436 | 1.00 | 1.00 | 0.36 | 0.0
FG2V +G2V | 0.84 | 0.98 | 0.531 | 0.89 | 0.99 | 0.41 | 11.5
KBS +G2V | 0.84 | 0.98 | 0.532 | 0.89 | 0.99 | 0.40 | 9.5
KBS +FG2V | 0.85 | 0.99 | 0.513 | 0.89 | 0.99 | 0.39 | 8.1
FG2V | 0.84 | 0.98 | 0.534 | 0.88 | 0.99 | 0.41 | 11.8
Table 1: Results for the In-Grid AS setup, averaged over all test problems.

Table 1 presents the results for the in-grid AS setup experiments. The rows
correspond to different AS methods, and the columns are the metrics defined
earlier. The column groups “All” and “Avg” provide a slightly different way to
aggregate the results over all the test problems. The results under the “All”
columns are averages over all test problems, regardless of their grids and
grid types. This is how most prior work on AS for MAPF aggregated their
results. The limitation of this aggregation is that some grids in the
benchmark are smaller than others, and have fewer MAPF problems defined for
them. The results under the “Avg” columns are averages of averages, where the
results of each grid type are averaged separately and only the resulting
averages are averaged. This mitigates unwanted to bias stemming from the
number of problems in each grid type.

Consider first the results for MAG and our two main baselines, KBS and G2V.
For each metric, we highlighted the best results among these AS methods in
bold. As the results clearly show, MAG is either on par or better than these
baselines on all metrics. For example, the accuracy of MAG is 0.85 in “All”
while it is 0.83 and 0.81 for KBS and G2V, respectively. The advantage of MAG
over G2V is more significant, and more modest compared to KBS. Still advantage
is significant, especially in terms of the average regret, which is
approximately 25% smaller than KBS (9.0 vs. 12.4).

The results of our ablation study are given in the shaded rows of Table 1. The
results are very similar to MAG where there is a slight advantage for using
the KBS hand-crafted MAPF-specific features together with graph embedding
features (either KBS \+ G2V or KBS \+ FG2V). This is expected, as a more
diverse set of features is expected to be more beneficial. That being said, in
some cases some of the algorithm configurations in our ablation study
performed as well and even slightly better than the full MAG Automated methods
for algorithm configuration can potentially be used to identify the optimal
configuration for a given problem instance. This is beyond the scope of this
work.

###  4.3 In-Grid-Type and Between-Grid-Type Results

| In-Grid-Type | Between-Grid
---|---|---
Metric | Acc | Cov | RT | % Rg | Acc | Cov | RT | % Rg
KBS | 0.69 | 0.93 | 0.86 | 78.6 | 0.63 | 0.87 | 0.99 | 223.1
G2V | 0.67 | 0.92 | 0.91 | 91.8 | 0.61 | 0.86 | 1.04 | 220.7
MAG | 0.71 | 0.94 | 0.80 | 67.9 | 0.63 | 0.89 | 0.93 | 180.0
Oracle | 1.00 | 1.00 | 0.48 | 0.00 | 1.00 | 1.00 | 0.36 | 0.00
FG2V +G2V | 0.69 | 0.93 | 0.84 | 75.8 | 0.62 | 0.88 | 0.97 | 195.8
KBS +FG2V | 0.70 | 0.94 | 0.81 | 70.5 | 0.64 | 0.89 | 0.93 | 192.5
KBS +G2V | 0.70 | 0.94 | 0.82 | 71.6 | 0.65 | 0.88 | 0.94 | 181.8
FG2V | 0.66 | 0.91 | 0.90 | 87.9 | 0.62 | 0.88 | 0.95 | 176.0
Table 2: In-grid-type (left) and Between-grid-type (right) results.

The first 5 columns (left-to-right) in Table 2 present the results for the in-
grid-type AS setup experiments. Similar to Table 1, the rows are different AS
methods and the columns are different metrics, corresponding to the “Avg”
column family. We highlighted in bold the AS method, among MAG and our two
baselines, that yielded the best results in each metric. As in the in-grid
experiments, the advantage of MAG over the baselines is clear in all metrics.
For example, its average regret is 67.9 while it is 78.60 and 91.80 for KBS
and G2V respectively. To verify the statistical significance of our results,
we performed a one-sided $t$ test [35] to compare MAG against the two baseline
sets of features, KBS and G2V. This test was done over all grid types,
randomizing the selection of test and train MAPF instances for five times. The
results show that the advantage of MAG over KBS and G2V is significant in
terms of accuracy (Acc), with $p$-values of 0.035 and 0.000027, respectively.
Similarly, the advantage of MAG is also significant in terms of coverage, with
a $p$ value of 0.007 and 0.00055 for KBS and G2V, respectively. In terms of
regret, the advantage of MAG over G2V is significant ($p$ value of 0.001) but
the advantage of MAG over KBS is not significant, with a $p$ value of 0.397.

| AS Setup | In-Grid | In-Grid-Type | Between-Grid
---|---|---|---|---
Grid-type | Metric | KBS | G2V | MAG | KBS | G2V | MAG | KBS | G2V | MAG
Empty | Acc | 0.88 | 0.89 | 0.90 | 0.67 | 0.68 | 0.71 | 0.81 | 0.78 | 0.82
Cov | 1.00 | 1.00 | 1.00 | 0.97 | 1.00 | 0.99 | 1.00 | 0.99 | 1.00
%Rg | 0.90 | 0.10 | 0.80 | 3.50 | 1.00 | 1.80 | 9.50 | 17.70 | 2.50
Random | Acc | 0.91 | 0.90 | 0.91 | 0.84 | 0.79 | 0.82 | 0.78 | 0.71 | 0.73
Cov | 1.00 | 1.00 | 1.00 | 1.00 | 0.99 | 1.00 | 1.00 | 0.99 | 1.00
%Rg | 3.10 | 4.10 | 2.40 | 1.40 | 2.30 | 1.10 | 7.20 | 54.80 | 4.00
Warehouse | Acc | 0.84 | 0.84 | 0.86 | 0.64 | 0.64 | 0.67 | 0.67 | 0.62 | 0.68
Cov | 0.99 | 0.99 | 1.00 | 0.94 | 0.94 | 0.96 | 0.96 | 0.88 | 0.98
%Rg | 7.9 | 9.40 | 4.70 | 1.40 | 1.60 | 1.30 | 32.9 | 78.10 | 27.3
Game | Acc | 0.91 | 0.91 | 0.92 | 0.77 | 0.72 | 0.78 | 0.74 | 0.72 | 0.65
Cov | 0.98 | 0.98 | 0.99 | 0.92 | 0.86 | 0.92 | 0.88 | 0.89 | 0.89
%Rg | 19.2 | 21.00 | 18.00 | 1.40 | 2.30 | 1.70 | 122.0 | 113.10 | 122.00
City | Acc | 0.90 | 0.89 | 0.92 | 0.58 | 0.57 | 0.61 | 0.53 | 0.53 | 0.58
Cov | 0.99 | 0.99 | 0.99 | 0.81 | 0.83 | 0.83 | 0.90 | 0.86 | 0.88
%Rg | 10.10 | 12.40 | 7.10 | 3.10 | 3.00 | 2.90 | 136.20 | 155.60 | 146.30
Maze | Acc | 0.85 | 0.79 | 0.86 | 0.40 | 0.44 | 0.50 | 0.56 | 0.45 | 0.47
Cov | 0.98 | 0.93 | 0.99 | 0.66 | 0.62 | 0.66 | 0.71 | 0.64 | 0.66
%Rg | 31.90 | 119.30 | 20.60 | 8.20 | 9.60 | 8.40 | 398.8 | 511.40 | 483.60
Room | Acc | 0.93 | 0.90 | 0.92 | 0.63 | 0.50 | 0.66 | 0.32 | 0.43 | 0.49
Cov | 1.00 | 1.00 | 1.00 | 0.91 | 0.83 | 0.94 | 0.65 | 0.75 | 0.81
%Rg | 0.20 | 2.10 | 0.10 | 2.90 | 5.00 | 2.20 | 855.60 | 614.50 | 475.00

Table 3: Results for all AS setups, grouped by test grid type.

The ablation study results show that here too, combining the hand-crafted
features of KBS with either type of graph embedding provides the biggest
performance improvement. For example, KBS with either G2V or FG2V yields 0.70
accuracy and runtime of 0.82 or less while FG2V alone or even with G2V yielded
lower accuracy and a higher runtime. It is worth comparing the average regret
results here and in the in-grid experiments. While the regret of MAG here is
67.90 it is only 9.0 in the in-grid results. This highlights that in-grid-type
AS is a significantly harder task the in-grid AS, since it requires
generalizing from different grids (although from the same type).

The rightmost 4 columns in Table 2 present the results for the between-grid-
type AS setup experiments. The first trend we observe is that the overall
results for all algorithms are significantly worse compared to all other AS
setups (in-grid and in-grid-type). For example, the average regret of MAG in
the in-grid-type results is 67.9 but it is 180 in between-grid results.
Similarly, MAG accuracy dropped from 0.71 to 0.63. Recall that the regret and
accuracy of MAG in the in-grid was 9.0 and 0.89, respectively. These
differences are expected, since in the between-grid experiments, the training
set did not include any grid of the tested type, which makes the
classification problem significantly harder.

In terms of the comparison with our baselines, the general trend we observed
so far continues in the between-grid setup: MAG is either on par or better
than the baselines in all metrics. For example, its average runtime and regret
are 0.93 and 180 while it is 0.99 and 220.7 for the next best baseline,
respectively. The ablation study results are less conclusive in this setup. In
terms of accuracy, we still see the benefit in combining KBS features with
graph embedding features over only using graph embedding features. However,
the lowest average regret is achieved when only using MAG. In fact, some
subsets of MAG features actually outperform MAG on some metrics. For example,
using only FG2V yields lower accuracy than the full MAG but a slightly lower
average regret (176 vs. 180). However, these differences are relatively small.

###  4.4 Grid Types Analysis

Table 3 provides a deeper insight into the results of our in-grid, in-grid-
type, and between-grid experiments. Here, the results — accuracy, coverage,
and regret — are grouped by grid types. For example, the results in the row
“City” show the average results over test problems that are on grids of type
“City”. The rows correspond to the test grid type, and the columns correspond
to the AS setup and evaluated algorithm. While MAG is still, in general, the
best-performing algorithm, in some grid types and metrics it is not,
especially in the between grid setup. This is most evident in the results for
Maze grids, where the accuracy, coverage, and regret of KBS— 0.56, 0.71, and
398.8, respectively — are better than the corresponding results of MAG which
were 0.47, 0.66, and 483.6. A possible explanation for this is that MAPF
solutions in Maze grids are significantly different from MAPF solutions in
grids from other grid types. Maze grids have many narrow corridors, and
consequently avoiding conflicts between agents often requires one agent to
make a large detour.

Interestingly, MAG performs well on City grids in the in-grid AS setup. This
suggests it is able to learn how to act in such grids, if they are given to it
for training. The in-grid results for Maze grids provide another interesting
insight when comparing the results of MAG and G2V. As can be seen, the
difference in this grid type between MAG and G2V is most pronounced: the
accuracy, coverage, and regret of G2V are 0.79, 0.93, and 119.3, respectively,
while they are 0.86, 0.99, and 20.6 for MAG. The poor performance of G2V in
Maze grids is understandable: in such grids agents often follow paths that are
significantly different from their shortest paths to avoid collisions. Such
paths are not encoded by G2V.

###  4.5 Feature Importance

Figure 4: Feature importance for the XGBoost model created for MAG in the in-
grid (top), in-grid-type (middle), and between-grid (bottom) setups.

Figure 4 plots a feature importance analysis performed on the prediction
models created by MAG for each of the AS setups. The importance of the
different features was measured by the coefficient learned for it by the
learning algorithm. The features are listed on the x-axis, where the first 20
features are the KBS features, the next 500 features are the G2V features, and
the last 500 features are the FG2V features. Within each feature family
(KBS,G2V, and FG2V), the features are sorted by their importance.

Our main observation is that each feature family has some features that are
important. This suggests that there is useful information in all types of
features, which corresponds to the successful results of MAG. Another
observation is that each feature family includes features whose importance is
close to zero. This suggests that applying feature selection method based on
weights may be effective. When comparing the different AS setups, it seems
that as the AS setup becomes more challenging, the set of features that are
important is reduced, and the importance of more features is close to zero.
This may suggest that additional types of features may be needed to get better
results for the harder AS setups.

##  5 Conclusion and Future Work

We proposed MAG, the first practical approach to optimal MAPF algorithm
selection based on graph embedding. MAG uses two encodings of the MAPF problem
as a graph, one that encodes the entire graph and one that encodes only the
shortest paths and their immediate vicinity. To work efficiently on new MAPF
problems, MAG utilizes a modern graph embedding algorithm that does not need
a-priori training. MAG also uses hand-crafted MAPF-specific features, as
suggested by prior work. The combination of graph-embedding features and hand-
crafted features leads to strong state-of-the-art AS for optimal MAPF. In an
extensive set of experiments on a standard benchmark, we showed that MAG
outperforms existing baselines almost always. In the easiest AS setup, In-
Grid, the advantage of MAG is limited. However, in the more challenging AS
setups, In-Grid-Type and Between-Grid, the advantage of MAG is more
significant, with more than 20% advantage in terms of average regret. Our
results also highlight that the between-grid AS setup is particularly
challenging, and can be the focus of future work. Another important future
work is to combine our graph-embedding based AS model with image-based AS
models, such as MAPFASTER [19].

## References

  * [1] P. R. Wurman, R. D’Andrea, M. Mountz, Coordinating hundreds of cooperative, autonomous vehicles in warehouses, AI magazine 29 (1) (2008) 9–9.
  * [2] J. Li, T. Hoang, E. Lin, H. Vu, S. Koenig, Intersection coordination with priority-based search for autonomous vehicles, in: AAAI Conference on Artificial Intelligence (AAAI), 2023, pp. 11578–11585.
  * [3] G. Belov, W. Du, M. G. de la Banda, D. Harabor, S. Koenig, X. Wei, From multi-agent pathfinding to 3d pipe routing, in: Symposium on Combinatorial Search (SoCS), 2020, pp. 11–19.
  * [4] Y. Zheng, H. Ma, S. Koenig, E. Kline, S. Kumar, Priority-based search for the virtual network embedding problem, in: International Conference on Automated Planning and Scheduling (ICAPS), 2023, pp. 472–480.
  * [5] H. Ma, J. Yang, L. Cohen, T. Kumar, S. Koenig, Feasibility study: Moving non-homogeneous teams in congested video game environments, in: AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), Vol. 13, 2017, pp. 270–272.
  * [6] P. Surynek, An optimization variant of multi-robot path planning is intractable, in: AAAI Conference on Artificial Intelligence, 2010, pp. 1261–1263.
  * [7] J. Yu, S. M. LaValle, Structure and intractability of optimal multi-robot path planning on graphs, in: AAAI Conference on Artificial Intelligence, 2013, pp. 1443–1449.
  * [8] P. S. Daniel Kornhauser, Gary Miller, Coordinating pebble motion on graphs, the diameter of permutation groups, and applications, in: Annual Symposium on Foundations of Computer Science (FOCS), 1984, pp. 241–250.
  * [9] P. Surynek, A novel approach to path planning for multiple robots in bi-connected graphs, in: IEEE International Conference on Robotics and Automation, 2009, pp. 3613–3619.
  * [10] J. Li, D. Harabor, P. J. Stuckey, H. Ma, G. Gange, S. Koenig, Pairwise symmetry reasoning for multi-agent path finding search, Artificial Intelligence 301 (2021) 103574.
  * [11] M. Goldenberg, A. Felner, R. Stern, G. Sharon, N. R. Sturtevant, R. C. Holte, J. Schaeffer, Enhanced partial expansion A*, J. Artif. Intell. Res. 50 (2014) 141–187.
  * [12] E. Lam, P. Le Bodic, D. Harabor, P. J. Stuckey, Branch-and-cut-and-price for multi-agent path finding, Computers & Operations Research 144 (2022) 105809.
  * [13] P. Surynek, A. Felner, R. Stern, E. Boyarski, Efficient sat approach to multi-agent path finding under the sum of costs objective, in: European Conference on Artificial Intelligence (ECAI), 2016, pp. 810–818.
  * [14] O. Kaduri, E. Boyarski, R. Stern, Experimental evaluation of classical multi agent path finding algorithms, in: International Symposium on Combinatorial Search (SoCS), 2021, pp. 126–130.
  * [15] J. R. Rice, The algorithm selection problem, in: Advances in computers, Vol. 15, Elsevier, 1976, pp. 65–118.
  * [16] P. Kerschke, H. H. Hoos, F. Neumann, H. Trautmann, Automated algorithm selection: Survey and perspectives, Evolutionary computation 27 (1) (2019) 3–45.
  * [17] O. Kaduri, E. Boyarski, R. Stern, Algorithm selection for optimal multi-agent pathfinding, in: International Conference on Automated Planning and Scheduling, Vol. 30, 2020, pp. 161–165.
  * [18] J. Ren, V. Sathiyanarayanan, E. Ewing, B. Senbaslar, N. Ayanian, MAPFAST: A deep algorithm selector for multi agent path finding using shortest path embeddings, in: International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2021, pp. 1055–1063.
  * [19] J.-M. Alkazzi, A. Rizk, M. Salomon, A. Makhoul, Mapfaster: A faster and simpler take on multi-agent path finding algorithm selection, in: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2022, pp. 10088–10093.
  * [20] G. Sharon, R. Stern, M. Goldenberg, A. Felner, The increasing cost tree search for optimal multi-agent pathfinding, Artificial intelligence 195 (2013) 470–495.
  * [21] A. Felner, J. Li, E. Boyarski, H. Ma, L. Cohen, T. S. Kumar, S. Koenig, Adding heuristics to conflict-based search for multi-agent path finding, in: International Conference on Automated Planning and Scheduling (ICAPS), Vol. 28, 2018, pp. 83–87.
  * [22] G. Gange, D. Harabor, P. J. Stuckey, Lazy cbs: implicit conflict-based search using lazy clause generation, in: International Conference on Automated Planning and Scheduling (ICAPS), Vol. 29, 2019, pp. 155–162.
  * [23] B. Rozemberczki, R. Sarkar, Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models, in: ACM International Conference on Information and Knowledge Management (CIKM), 2020, pp. 1325–1334.
  * [24] D. Atzmon, Y. Zax, E. Kivity, L. Avitan, J. Morag, A. Felner, Generalizing multi-agent path finding for heterogeneous agents, in: International Symposium on Combinatorial Search (SoCS), Vol. 11, 2020, pp. 101–105.
  * [25] A. Andreychuk, K. Yakovlev, P. Surynek, D. Atzmon, R. Stern, Multi-agent pathfinding with continuous time, Artificial Intelligence (2022).
  * [26] J. Li, P. Surynek, A. Felner, H. Ma, T. S. Kumar, S. Koenig, Multi-agent path finding for large agents, in: AAAI Conference on Artificial Intelligence, Vol. 33, 2019, pp. 7627–7634.
  * [27] G. Sharon, R. Stern, A. Felner, N. R. Sturtevant, Conflict-based search for optimal multi-agent pathfinding, Artificial Intelligence 219 (2015) 40–66.
  * [28] D. Sigurdson, V. Bulitko, S. Koenig, C. Hernandez, W. Yeoh, Automatic algorithm selection in multi-agent pathfinding, arXiv:1906.03992 (2019).
  * [29] P. Goyal, E. Ferrara, Graph embedding techniques, applications, and performance: A survey, Knowledge-Based Systems 151 (2018) 78–94.
  * [30] R. You, Z. Guo, L. Cui, X. Long, Y. Bao, S. Wen, Cross-modality attention with semantic graph embedding for multi-label classification, in: AAAI conference on artificial intelligence, Vol. 34, 2020, pp. 12709–12716.
  * [31] A. Narayanan, M. Chandramohan, R. Venkatesan, L. Chen, Y. Liu, S. Jaiswal, Graph2Vec: Learning distributed representations of graphs, arXiv:1707.05005 (2017).
  * [32] R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. Kumar, et al., Multi-agent pathfinding: Definitions, variants, and benchmarks, in: International Symposium on Combinatorial Search (SoCS), Vol. 10, 2019, pp. 151–158.
  * [33] N. Sturtevant, Benchmarks for grid-based pathfinding, Transactions on Computational Intelligence and AI in Games 4 (2) (2012) 144 – 148.
URL http://web.cs.du.edu/~sturtevant/papers/benchmarks.pdf

  * [34] T. Chen, C. Guestrin, XGBoost: A scalable tree boosting system, in: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, p. 785–794.
  * [35] D. Semenick, Tests and measurements: The t-test, Strength & Conditioning Journal 12 (1) (1990) 36–37.