The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True Bernhard Nebel Albert-Ludwigs-Universit at

2025-05-06 0 0 378.79KB 21 页 10玖币

侵权投诉

The Small Solution Hypothesis for MAPF on

Strongly Connected Directed Graphs Is True

Bernhard Nebel Albert-Ludwigs-Universit¨

Freiburg, Germany

nebel@uni-freiburg.de

February 13, 2023

Abstract

The determination of the computational complexity of multi-agent pathﬁnding

on directed graphs (diMAPF) has been an open research problem for many years.

While diMAPF has been shown to be polynomial for some special cases, it has

only recently been established that the problem is NP-hard in general. Further, it

has been proved that diMAPF will be in NP if the short solution hypothesis for

strongly connected directed graphs is correct. In this paper, it is shown that this

hypothesis is indeed true, even when one allows for synchronous rotations.

1 Introduction

Multi-agent pathﬁnding (MAPF), often also called pebble motion on graphs or cooper-

ative pathﬁnding, is the problem of deciding the existence of or generating a collision-

free movement plan for a set of agents moving on a graph, most often a graph generated

from a grid, where agents can move to adjacent grid cells [15]. Two examples are pro-

vided in Figure 1.

v1v2v3

Figure 1: Multi-agent pathﬁnding examples

In the left example, the circular agent Cneeds to move to v2and the square agent

Shas to move to v3.Scould move ﬁrst to v2and then to v3, after which Ccould move

to its destination v2. So, in this case, a collision-free movement plan exists. In the right

example, where additionally the triangle agent has to move to v1, there is no possible

arXiv:2210.04590v4 [cs.AI] 10 Feb 2023

way for the square and triangle agent to exchange their places, i.e., there does not exist

any collision-free movement plan.

Kornhauser et al. [13] had shown already in the eighties that deciding MAPF is

a polynomial-time problem and movement plans have polynomial length, although it

took a while until this result was recognized in the community [22]. The optimizing

variant of this problem, assuming that only one agent can move at each time step, had

been shown to be NP-complete soon after the initial result [12, 21].

Later on, variations of the problem have been studied [10]. It is obvious that all

robots that move to different empty nodes could move in parallel, which may lead to

shorter plans. Assuming coordination between the agents, one can also consider train-

like movements, where only the ﬁrst robot moves to an empty node and the others

follow in a chain, all in one time step [23, 25, 26]. Taking this one step further, syn-

chronous rotations of agents on a cycle without any empty nodes have been considered

[24, 32, 33]. And even distributed and epistemic versions have been studied [19].

Concerning plan existence and polynomial plan length, parallel and train-like move-

ments do not make a difference to the case when only simple moves are permitted. Syn-

chronous rotations are a different story altogether. There are problem instances which

cannot be solved using only simple moves, but are solvable when synchronous rota-

tions are allowed. Nevertheless, it has been shown that MAPF is a polynomial-time

problem as well [33]. Distributed and epistemic versions are more difﬁcult, however.

They are NP-complete and PSPACE-complete, respectively [19].

Optimizing wrt. different criteria turned out to be NP-complete [26, 32] for all kinds

of movements, and this holds even for planar and grid graphs [31, 4, 11]. Additionally,

it was shown that there are limits to the approximability of the optimal solution for

makespan optimizations [16].

The mentioned results all apply to undirected graphs only. However, a couple of

years ago, researchers also considered MAPF on directed graphs (diMAPF) [28], and it

has been proved that diMAPF can be decided in polynomial time, provided the directed

graph is strongly biconnected1and there are at least two unoccupied vertices [7, 6].

The general case for directed graphs is still open, though. It has only been shown that

diMAPF is NP-hard [18], but membership in NP was not established.

In general, the state space of (di)MAPF has size O(n!),nbeing the number of ver-

tices of the graph. However, for directed acyclic graphs, a quadratic upper bound for

the plan length is obvious, because steps are not reversible in this case, and so each sin-

gle agent can perform at most nsteps. This leads immediately to NP-completeness for

directed acyclic graphs. For strongly connected directed graphs, this argument is not

valid, however. It was nevertheless conjectured that plans can be polynomially bounded

[18], since this holds also for undirected graphs and for directed strongly biconnected

graphs with two empty nodes. In this paper, we will show that this small solution hy-

pothesis is indeed true.

The crucial observation is that each movement in a strongly connected directed

graph can be reversed, which essentially means that movements of single agents can

also be thought of taking place against the direction of an arc in directed graphs, some-

thing already noted by Ardizzoni et al. [1]. This implies that we can reuse almost

1This means that each pair of nodes is located on a directed cycle.

all results about undirected graphs with only a polynomial overhead in plan length—

provided we are talking about single-agent movements. However, this does not apply

to synchronous rotations. Here, a reduction to movements on the corresponding undi-

rected graph is impossible. By using techniques similar to the ones Kornhauser et al.

[13] employed, we show that any movement plan using only synchronous rotations

on strongly connected directed graphs can be polynomially bounded. Finally, we con-

sider the case, when both kinds of movements are allowed, and prove a polynomial

bound as well, which allows us to conclude that the small solution hypothesis is in-

deed true regardless of what kind of movements are possible, and therefore diMAPF is

NP-complete.

The rest of the paper is structured as follows. In the next section, we will introduce

the necessary notation and terminology that is needed for proving the small solution

hypothesis to be true. We will cover basic notation and terminology from graph theory

and permutation groups, and will formally introduce MAPF and diMAPF. In the three

subsequent sections, the small solution hypothesis will then be proven, ﬁrst for the

case of simple movements, then for the more complicated case when only synchronous

rotations are permitted, and ﬁnally for the case, when both kinds of movements are

possible. The paper ends with a short discussion of the results.

2 Notation and Terminology

2.1 Graph Theory

Agraph Gis a tuple (V, E)with E⊆ {{u, v} | u, v ∈V}. The elements of Vare

called nodes or vertices and the elements of Eare called edges. A directed graph or

digraph Dis a tuple (V, A)with A⊆V2. The elements of Aare called arcs. Graphs

and digraphs with |V|= 1 are called trivial. We assume all graphs and digraphs to be

simple, i.e., not containing any self-loops of the form {u}, resp. (u, u). Given a digraph

D= (V, A), the underlying graph of D, in symbols G(D), is the graph resulting from

ignoring the direction of the arcs, i.e., G(D) = (V, {{u, v} | (u, v)∈A}).

Given a graph G= (V, E),G0= (V0, E0)is called sub-graph of Gif V⊇V0and

E⊇E0. Similarly, for digraphs D= (V, A)and D0= (V0, A0),D0is a sub-digraph

if V⊇V0and A⊇A0.

Apath in a graph G= (V, E)is a non-empty sequence of vertices of the form

v0, v1, . . . , vksuch that vi∈Vfor all 0≤i≤k,vi6=vjfor all 0≤i < j ≤k,

and {vi, vi+1} ∈ Efor all 0≤i<k. A cycle in a graph G= (V, E)is a non-empty

sequence of vertices v0, v1, . . . , vkwith k≥3such that v0=vk,{vi, vi+1} ∈ Efor

all 0≤i<kand vi6=vjfor all 0≤i < j < k.

In a digraph D= (V, A),path and cycle are similarly deﬁned, except that the

direction of the arcs has to be respected. This means that (vi, vi+1)∈Afor all 0≤

i < k. Further, the smallest cycle in a digraph has 2 nodes instead of 3. A digraph

that does not contain any cycle is called directed acyclic graph (DAG). A digraph that

consists solely of a cycle is called cycle digraph. A digraph that consists of a directed

cycle v0, v1, . . . , vk−1, vk=v0and any number of arcs connecting adjacent nodes in

a backward manner, i.e., (vi, vi−1)∈A, is called partially bidirectional cycle graph.

A graph G= (V, E)is connected if there is a path between each pair of vertices.

A connected graph that does not contain a cycle is called tree.

Similarly, a digraph D= (V, A)is weakly connected, if the underlying graph G(D)

is connected. It is strongly connected, if for every pair of vertices u, v, there is a path

in Dfrom uto vand one from vto u. The smallest strongly connected digraph is the

trivial digraph. The strongly connected components of a digraph D= (V, A)are the

maximal sub-digraphs Di= (Vi, Ai)that are strongly connected.

2.2 Permutation Groups

In order to be able to establish a polynomial bound for diMAPF movement plans con-

taining synchronous rotations, we introduce some background on permutation groups.2

Apermutation is a bijective function over a set X σ :X→X. In what follows, we

assume Xto be ﬁnite.

A permutation has degree dif it exchanges delements and ﬁxes the rest of the

the elements in X. We say that a permutation is an m-cycle if it exchanges elements

x1, . . . , xmin a cyclic fashion, i.e., σ(xi) = xi+1 for 1≤i<m,σ(xm) = x1

and σ(y) = yfor all y /∈ {xi}m

i=1. Such a cyclic permutation is written as a list of

elements, i.e., (x1x2· · · xm). A 2-cycle is also called transposition. A permutation

can also consist of different disjoint cycles. These are then written in sequence, e.g.,

(x1x2)(x3x4).

The composition of two permutations σand τ, written as σ◦τor simply στ , is

the function mapping xto τ(σ(x)).3This operation is associative because function

composition is. The special permutation , called identity, maps every element to itself.

Further, σ−1is the inverse of σ, i.e., σ−1(y) = xif and only if σ(x) = y. The k-

fold composition of σwith itself is written as σk, with σ0=. Similarly, σ−k:=

(σ−1)kWe also consider the conjugate of σby τ, written as στ, which is deﬁned to

be τ−1στ. Such conjugations are helpful in creating new permutations out of existing

ones. We use exponential notation as in the book by Mulholland [17]: σα+β:= σασβ

and σαβ := (σα)β.

A set of permutations closed under composition and inverse forms a permutation

group with ◦as the product operation (which is associative), ·−1being the inverse

operation, and being the identity element. Given a set of permutations {g1, . . . , gi},

we say that G=hg1, . . . , giiis the permutation group generated by {g1, . . . , gi}if G

is the group of permutations that results from product operations over the elements of

{g1, . . . , gi}. We say that σ∈G=hg1, . . . , giiis k-expressible if it can be written as

a product over the generators using < k product operations. The diameter of a group

G=hg1, . . . , giiis the least number ksuch that every element of Gis k-expressible.

Note that this number depends on the generator set.

A group Fis a subgroup of another group G, written F≤G, if the elements of F

are a subset of the elements of G. In our context, two permutation groups are of par-

ticular interest. One is Sn, the symmetric group over nelements, which consists of all

permutations over nelements. A permutation in Snis even if it can be represented as a

2A gentle introduction to the topic is the book by Mulholland [17].

3Note that this order of function applications, which is used in the context of permutation groups, is

different from ordinary function composition.

product of an even number of transpositions, odd otherwise. Note that no permutation

can be odd and even at the same time [17, Theorem 7.1.1]. The set of even permuta-

tions forms another group, the alternating group An≤Sn. Since any m-cycle can be

equivalently expressed as the product of m−1transpositions, m-cycles with even m

are not elements of An.

A permutation group Gis k-transitive if for all pairs of k-tuples (x1, . . . , xk),

(y1, . . . , yk), there exists a permutation σ∈Gsuch that σ(xi) = yi,1≤i≤k. In

case of 1-transitivity we simply say that Gis transitive.

Ablock is a non-empty subset B⊆Xsuch that for each permutation σ, either

σ(B) = Bor σ(B)∩B=∅. Singleton sets and the entire set Xare trivial blocks.

Permutation groups that contain only trivial blocks are primitive.

2.3 Multi-Agent Pathﬁnding

Given a graph G= (V, E)and a set of agents Rsuch that |R|≤|V|, we say that

the injective function S:R→Vis a multi-agent pathﬁnding (MAPF) state (or simply

state) over Rand G. Any node not occupied by an agent, i.e., a node v∈V−S(R),

is called blank.

Amulti-agent pathﬁnding (MAPF) instance is then a tuple hG, R, I, T iwith G

and Ras above and Iand TMAPF states. A simple move of agent rfrom node uto

node v, in symbols m=hr, u, vi, transforms a given state S, where we need to have

{u, v} ∈ E,S(r) = uand vis a blank, into the successor state S[m], which is identical

to Sexcept at the point r, where S[m](r) = v.

If there exists a (perhaps empty) sequence of simple moves, a movement plan, that

transforms Sinto S0, we say that S0is reachable from S. The MAPF problem is then

to decide whether Tis reachable from I.

The MAPF problem is often deﬁned in terms of parallel or train-like movements

[23, 26], where one step consists of parallel non-interfering moves of many agents.

However, as long as we are interested only in solution existence and polynomial bounds,

there is no difference between the MAPF problems with parallel and sequential move-

ments. If we allow for synchronous rotations [24, 32, 33], where one assumes that all

agents in a fully occupied cycle can move synchronously, things are a bit different. In

this case, even if there are no blanks, agents can move. A rotation is a set of simple

moves M={hr1, u1, v1i, . . .,hrk, uk, vki}, where k≥3, with (1) {ui, vi} ∈ Efor

1≤i≤k, (2) ui6=ujfor 1≤i < j ≤k, (3) vi=ui+1 for 1≤i < k, and vk=u1.

Such a rotation Mis executable in Sif S(ri) = uifor 1≤i≤k. The successor state

S[M]of a given state Sis identical to Sexcept at the points r1, . . . , rk, where we have

S[M](ri) = vi.

Multi-agent pathﬁnding on directed graphs (diMAPF) is similar to MAPF, except

that we have a directed graph and the moves have to follow the direction of an arc, i.e.,

if there is an arc (u, v)∈Abut (v, u)6∈ A, then an agent can move from uto vbut

not vice versa. Since on directed graphs there are also cycles of size two, one may also

allow rotations on only two nodes, contrary to the deﬁnition of rotations on undirected

graphs. In the following, we consider both possibilities, allowing or prohibiting rota-

tions of size 2, and show that it does not make a difference when it comes to bounding

movement plans polynomially.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

TheSmallSolutionHypothesisforMAPFonStronglyConnectedDirectedGraphsIsTrueBernhardNebelAlbert-Ludwigs-Universit¨atFreiburg,Germanynebel@uni-freiburg.deFebruary13,2023AbstractThedeterminationofthecomputationalcomplexityofmulti-agentpathndingondirectedgraphs(diMAPF)hasbeenanopenresearchproblemformanyye...

展开>> 收起<<

The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True Bernhard Nebel Albert-Ludwigs-Universit at.pdf

共21页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True Bernhard Nebel Albert-Ludwigs-Universit at

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: