Paper deep dive
Scalable Multi-Agent Maze Traversal with Local Communication
Julian Rau, Jahir Argote-Gerald, Grace McFassel, Genki Miyauchi, Paul Trodden, Roderich Groß
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/13/2026, 3:38:58 AM
Summary
This paper proposes a distributed algorithm for Multi-Agent Maze Traversal (MAMT) in unknown, possibly cyclic graphs. The approach uses a leader-follower strategy with local communication, where one agent acts as the head executing a single-agent maze solver while others follow. The algorithm ensures collision-free navigation, is proven complete, and demonstrates scalability and efficiency in simulations with up to 625 agents.
Entities (10)
Relation Signals (10)
Genki Miyauchi → affiliatedwith → Bristol Robotics Laboratory
confidence 99% · Genki Miyauchi... Affiliation: Bristol Robotics Laboratory, University of Bristol, Bristol, UK
Grace McFassel → affiliatedwith → Technical University of Darmstadt
confidence 99% · Grace McFassel... Affiliation: Department of Computer Science, Technical University of Darmstadt, Germany
Roderich Groß → affiliatedwith → Technical University of Darmstadt
confidence 99% · Roderich Groß... Affiliation: Department of Computer Science, Technical University of Darmstadt, Germany
Jahir Argote-Gerald → affiliatedwith → The University of Sheffield
confidence 99% · Jahir Argote-Gerald... Affiliation: School of Electrical and Electronic Engineering, The University of Sheffield, UK
Paul Trodden → affiliatedwith → The University of Sheffield
confidence 99% · Paul Trodden... Affiliation: School of Electrical and Electronic Engineering, The University of Sheffield, UK
Julian Rau → affiliatedwith → Technical University of Darmstadt
confidence 99% · Julian Rau... Affiliation: Department of Computer Science, Technical University of Darmstadt, Germany
Multi-Agent Maze Traversal → solvedby → Leader-Follower Strategy
confidence 95% · We propose a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph... coordinate via local communication using leader–follower relationships
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Cave networks, pipe systems, and similar maze-like environments pose significant challenges for multi-agent navigation in unknown settings with limited communication. We propose a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph. Agents enter sequentially at a designated start node and are tasked to localize and reach an undisclosed goal while avoiding collisions. They coordinate via local communication using leader-follower relationships and leader switching. At any moment in time, exploration is performed by only one of the agents, which runs a single-agent maze solver. We prove that the algorithm is complete, that its makespan is asymptotically equivalent (in the number of agents) to that of an optimal full-knowledge strategy, and derive its time and space complexity. Simulations with up to $625$ agents show a decreasing average sum-of-fuels as the number of agents increases and demonstrate that the proposed approach outperforms a naïve baseline in which all agents independently execute the single-agent solver.
Tags
Links
- Source: https://arxiv.org/abs/2608.11895v1
- Canonical: https://arxiv.org/abs/2608.11895v1
Trouble viewing inline? Open PDF directly →
Full Text
67,984 characters extracted from source content.
Expand or collapse full text
Scalable Multi-Agent Maze Traversal with Local Communication Julian Rau OrcID: 0009-0006-0913-6555 Affiliation: Department of Computer Science, Technical University of Darmstadt, Germany julian.rau, grace.mcfassel, roderich.gross@tu-darmstadt.de Jahir Argote-Gerald OrcID: 0009-0003-1492-1329 Affiliation: School of Electrical and Electronic Engineering, The University of Sheffield, UK jaargotegerald1, p.trodden@sheffield.ac.uk Grace McFassel OrcID: 0000-0002-8568-1313 Affiliation: Department of Computer Science, Technical University of Darmstadt, Germany julian.rau, grace.mcfassel, roderich.gross@tu-darmstadt.de Genki Miyauchi OrcID: 0000-0002-3349-6765 Affiliation: Bristol Robotics Laboratory, University of Bristol, Bristol, UK g.miyauchi@bristol.ac.uk Paul Trodden OrcID: 0000-0002-8787-7432 Affiliation: School of Electrical and Electronic Engineering, The University of Sheffield, UK jaargotegerald1, p.trodden@sheffield.ac.uk Roderich Groß OrcID: 0000-0003-1826-1375 Affiliation: Department of Computer Science, Technical University of Darmstadt, Germany julian.rau, grace.mcfassel, roderich.gross@tu-darmstadt.de Affiliation: School of Electrical and Electronic Engineering, The University of Sheffield, UK jaargotegerald1, p.trodden@sheffield.ac.uk Abstract Cave networks, pipe systems, and similar maze-like environments pose significant challenges for multi-agent navigation in unknown settings with limited communication. We propose a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph. Agents enter sequentially at a designated start node and are tasked to localize and reach an undisclosed goal while avoiding collisions. They coordinate via local communication using leader–follower relationships and leader switching. At any moment in time, exploration is performed by only one of the agents, which runs a single-agent maze solver. We prove that the algorithm is complete, that its makespan is asymptotically equivalent (in the number of agents) to that of an optimal full-knowledge strategy, and derive its time and space complexity. Simulations with up to 625625 agents show a decreasing average sum-of-fuels as the number of agents increases and demonstrate that the proposed approach outperforms a naïve baseline in which all agents independently execute the single-agent solver. Keywords: Multi-Agent Maze Traversal Multi-Agent Systems and Distributed Robotics Algorithmic Completeness and Complexity 1 Introduction Many real-world scenarios require multiple agents to navigate efficiently through complex, maze-like environments such as networks of pipes [18, 27] or caves [15, 13, 19]. Coordinating such agents poses unique challenges, including the uncertainty of environments, communication restrictions, and inter-agent collisions. Environments are often modeled as graphs. If the graph is unknown a priori, its nodes and edges are locally revealed as agents traverse it. For single-agent systems, classical methods such as breadth-first search (BFS) and Trémaux’s algorithm can be employed to search the graph [3, 5, 8]. For multi-agent system, inter-agent collisions and communication have to be considered. Some studies consider agents that explore (tree or) graph environments while coordinating through beacons they place at nodes [2, 4, 9, 16] or through local or global communication [7, 12]. Except for [12], these studies provide theoretical guarantees such as completeness and exploration-time bounds but do not all consider inter-agent collisions [2, 7, 9]. Moreover, their focus is on exhaustive exploration rather than reaching specific goal nodes. The search algorithm proposed in [6] aborts in the event undisclosed goal nodes are discovered. However, it is centralized. A related problem is Multi-Agent Path Finding (MAPF), which involves identifying collision-free paths of multiple agents to designated goal nodes in a known graph environment [22, 24, 25, 26]. In classical MAPF settings, agents are assumed to have full knowledge of the graph, their own start and goal nodes, and those of other agents. Planning is typically conducted in a centralized manner [22, 24, 26]. Some MAPF variants relax these assumptions by requiring agents to discover parts of their environment or plan their paths in a distributed manner [10, 17, 20, 23], but do not permit fully unknown environments. Multi-Agent Maze Traversal (MAMT) [11, 1] is a problem that combines multiple of the aforementioned challenges. Specifically, it concerns collective, collision-free navigation of arbitrary large group of agents (i) through a unknown graph environment that is only gradually revealed through local sensing as the agents move, and (i) towards a common, undisclosed goal node. In [11], a distributed approach for MAMT is presented but assumes global communication among agents. In [1], we proposed a distributed approach requiring only local communication. It employs a leader-switching strategy by which one agent (the head) executes a single-agent maze solver to search for the goal, while all other agents choose neighboring agents to follow, thereby directly or indirectly following the head. If movement were to result in a collision, the head instead passes its role to the respective agent. Both approaches are limited to acyclic graph environments (i.e., trees) and offer no theoretical guarantees [11, 1], leaving decentralized, locally coordinated MAMT for general graphs an open problem. The contributions of this work are as follows: (i) We propose a new MAMT algorithm, based on the one presented in [1], to address the MAMT problem for general (i.e. possibly cyclic) graphs. The algorithm manages competition between agents and maintains connected communication within the swarm. It employs multiple messaging rounds per time step and diverse message types. (i) We formally prove completeness and that the makespan is asymptotically equivalent (with respect to the number of agents) to the one achieved by an optimal strategy assuming full knowledge. (i) We derive the algorithm’s time and space complexity. (iv) We validate the algorithm in simulation with up to 625625 agents, showing a decrease in average sum of fuel with growing numbers of agents, and that the algorithm outperforms a naïve baseline (where all agents run the single-agent maze solver) and approaches the performance of the full-knowledge strategy. Sections 2 and 3 define the MAMT problem and propose and analyze an algorithmic solution. Sections 4 and 5 present simulation results and conclusions. 2 Problem Formulation (a) (b) (c) Figure 1: (a) The maze is represented as a graph with start node s, goal node g (blue). Agents (green) are tasked with moving from s to g without prior knowledge of the environment. (b) Agents can only communicate with other agents that are either in an adjacent node or two nodes away with an empty node in between. (c) All agents but one choose a leader to follow, resulting in a leader-follower relation. The maze is represented as a connected, undirected graph =(,ℰ)G=(V,E), where V is the set of nodes and ℰE is the set of edges. An example graph is shown in Fig. 1a. Two nodes in this graph, s,g∈s,g , s≠gs≠ g, represent the start and the goal (blue), respectively. Node s is assumed to be a leaf in G11 1 As graphs representing real-world environments are artificially created, we assume they can be constructed accordingly.. A set of n agents, =1,…,nA=\1,…,n\, is considered, where vi[k]∈v_i[k] denotes the node that agent i∈i resides on at time k∈ℕ0k _0. We define time step k+1k+1 as the interval [k,k+1)[k,k+1). For simplicity, we omit k when it is clear from the context. At time k=0k=0, all agents are at the start (i.e., ∀i:vi[0]=s∀ i:v_i[0]=s) and one agent is considered active whereas all others are inactive. Active agents remain active indefinitely. At the precise time an active agent leaves the start node, an inactive agent present at the same node (if any) becomes active. Activation repeats until the last agent becomes active and occurs in a fixed, predetermined total order ≤ _A on A. Let active[k]⊆A^active[k] denote the set of active agents at time k. Let i[k]=u∈∣vi,u∈ℰN_i[k]= \u \v_i,u\ \ be the set of adjacent nodes of agent i. In time step k+1k+1, agent i can either move to a node in i[k]N_i[k] or remain in its current node vi[k]v_i[k]. A node v∈∖gv \g\ is occupied at time k, if ∃i∈active[k]:vi[k]=v∃ i ^active[k]:\,v_i[k]=v. A vertex conflict [25] occurs at time k if two active agents occupy the same non-goal node, that is, ∃i,j∈active[k],i≠j:vi[k]=vj[k]≠g∃ i,j ^active[k],i≠ j:v_i[k]=v_j[k]≠ g. A following conflict [25] occurs if an active agent moves to a non-goal node in the same time step that another active agent left it, formally, ∃i,j∈active[k]∃ i,j ^active[k], i≠j:vi[k]=vj[k+1]≠gi≠ j:v_i[k]=v_j[k+1]≠ g. Both vertex and following conflicts are prohibited. Note that an agent i that activates in timestep k+1k+1 is not yet active at k (i.e., i∉active[k]i ^active[k]) and therefore does not induce a following conflict with the active agent j∈active[k]j ^active[k] that left the start node in time step k+1k+1. At time k, agent i knows22 2 For ease of notation, we write iN_i as if agent i had access to the global labels of neighboring nodes, V. However, agent i can only distinguish these nodes, requiring labels that are consistent from agent i’s local perspective. (adapted from [1]): • its unique ID i • whether the node vi[k]v_i[k] it currently resides on is the goal node, vi[k]=gv_i[k]=g • if g is an adjacent node, that is, if g∈i[k]g _i[k], and if so, which edge leads to g • the subset of adjacent nodes that are currently occupied, ioccupied[k]=u∈i[k]∖g∣∃a∈active[k]:va[k]=uN_i^occupied[k]= \u _i[k] \g\ ∃ a ^active[k] v_a[k]=u \. The subset of unoccupied adjacent nodes can be obtained by iunoccupied=i∖ioccupiedN_i^unoccupied=N_i _i^occupied. Messages among agents are limited to a two-hop distance and can only pass unoccupied nodes33 3 This models constrained local communication, such as line-of-sight communication. (example shown in Fig. 1b), resulting in the undirected communication graph com=(com,ℰcom)G^com=(V^com,E^com), where com=activeV^com=A^active and [1]44 4 The expression vi=vjv_i=v_j in ℰcomE^com covers the case where two active agents reside in g. ℰcom= ^com= i,j⊆active∣i≠j∧ \\i,j\ ^active i≠ j (vi=vj∨vi,vj∈ℰ∨(iunoccupied∩junoccupied≠∅)). (v_i=v_j \v_i,v_j\ (N_i^unoccupied _j^unoccupied≠ ) ) \. Consequently, agent i can communicate with agents in its communication range i=j∈com∖i∣i,j∈ℰcomC_i= \j ^com \i\ \i,j\ ^com \ [1]. Agents can send a message via directed cast, that is, via a specified edge. Formally, when agent i sends a message via directed cast along edge vi,u∈ℰ \v_i,u \ , u∈iu _i, this message reaches all agents that currently reside in any node of the set i[u]≔w∈∣w=u∨(u∈iunoccupied∧u,w∈ℰ).U_i[u] \w w=u (u _i^unoccupied \u,w\ ) \. Agents can also send a message via (local) broadcast, that is, along all outgoing edges of their current node [1]. A broadcast message sent by agent i reaches all agents currently residing in any node of set ℬi≔⋃u∈i[u].B_i _u _iU_i[u]. A message contains the information whether it was sent via directed cast or broadcast. Agents can send and receive messages at any time. Communication is situated, allowing agent i to determine the node(s) from which a message reached the agent. An agent i that receives a directed cast message from an agent j≠ij≠ i via a shared, unoccupied, adjacent node u can determine that this directed cast came from u. If j is adjacent to i and sends a directed cast message via the edge vi,vj∈ℰ\v_i,v_j\ or vi=vjv_i=v_j, i knows that this message came from vjv_j. An agent i that receives a broadcast message that was sent by an agent j≠ij≠ i, gathers the nodes from which the broadcast reached i in the set NodesTowards(j)i_i(j) (adapted from [1]). Formally, NodesTowardsi(j)=vj,if vj=vivj∪(iunoccupied∩junoccupied),if vi,vj∈ℰiunoccupied∩junoccupied,otherwise. NodesTowards_i(j)= cases \v_j \,&if v_j=v_i\\ \v_j \∪(N^unoccupied_i ^unoccupied_j),&if \v_i,v_j\ \\ N^unoccupied_i ^unoccupied_j,&otherwise. cases All agents are tasked to reach the goal g. The following two evaluation criteria are used to measure the performance [25, 1]: (i) Makespan: The overall time it took for all agents to reach the goal, formally mink∈ℕ0∣∀a∈:va[k]=g \k _0 ∀ a :v_a[k]=g \; (i) Average sum-of-fuels: The mean number of edges traversed to reach the goal, formally 1/n∑i=1nπi1/n _i=1^n _i, where πi _i is the number of edges traversed by agent i. 1 v←sv← s, vprev←sv^prev← s, L←nilL← nil 2 // Synchronized sensing and messaging step Sense adjacent nodes 3 Broadcast and receive status messages from neighbor agents, Update C 4 if status message received from agent l then 5 L←lL← l 6 while v≠gv≠ g do 7 D←vD← v, competing←falsecompeting← false 8 // Decision making step if L=nilL=nil then 9 // Head decision step if g∈g then 10 D←gD← g 11 else 12 Dsolver←D^solver← SingleAgentMazeSolver() 13 if Dsolver∈occupiedD^solver ^occupied then 14 L←Selector(a∈∣Dsolver∈NodesTowards(a))L← Selector(\a D^solver∈ NodesTowards(a)\) 15 else if Dsolver≠D^solver≠ D then 16 Directed cast along v,Dsolver\v,D^solver\ 17 D←DsolverD← D^solver 18 Broadcast head message 19 20 else 21 D,L←ResolveConflict()D,L← ResolveConflict() 22 23 24 // Synchronized movement step move to D 25 vprev←v^prev← v, v←Dv← D 26 // Synchronized sensing and messaging step Sense adjacent nodes 27 if vprev≠v^prev≠ v then 28 Directed cast along v,vprev\v,v^prev\ 29 Broadcast status messages 30 Receive directed casts (optional) and status messages 31 Update vLprev^prev_L, C 32 33 Algorithm 1 Multi-Agent Maze Traversal Algorithm 1 Output: The node to move to D and the updated leader L 2 if h∈∣Lh=nil∧vh≠g≠∅\h L_h= nil v_h≠ g\≠ then 3 h←Selector(h∈∣Lh=nil∧vh≠g)h← Selector(\h L_h= nil v_h≠ g\) 4 // Wait for head decision step to finish Wait until directed cast (optional) and head message from h received 5 if head message contains Lh=iL_h=i then 6 7 Broadcast competing message 8 return v,nilv, nil 9 else if Directed cast from h received∨(NodesTowards(h)∩occupied≠∅)Directed cast from $h$ received ( NodesTowards(h) ^occupied≠ ) then 10 11 Broadcast competing message 12 return v, h 13 if g∈g then 14 15 Broadcast competing message 16 return g, L 17 if NodesTowards(L)∩occupied≠∅(L) ^occupied≠ then 18 19 Broadcast competing message 20 return v, L 21 competing←truecompeting← true // Compete for vLprev^prev_L Broadcast competing message 22 Wait until competing messages from all agents a∈a received 23 24 ℛ←a∈∣va≠g∧competinga∧La∈∧vLaprev=vLprevR←\a v_a≠ g competing_a L_a v^prev_L_a=v^prev_L\ 25 26 if Selector(ℛ∪i)=i($ R∪\i\$)=i then 27 return vLprev^prev_L, L // Keep leader else 28 return v, Selector(ℛ∪i) Selector($ R∪\i\$) // Update leader 29 Algorithm 2 ResolveConflict (as performed by agent i) 3 Algorithm Design We extend the approach in [1] to cyclic graphs while preserving its core algorithmic idea. In each time step (until reaching a node adjacent to the goal), one active agent (referred to as the head) employs a single-agent maze solver to explore the maze. All other active agents choose an active agent, their leader, to follow such that the resulting leader-follower-graph is a tree; hence, they directly or indirectly follow the head (Fig. 1c). All agents are assumed to possess any capabilities that are needed for the underlying single-agent maze solver in addition to the requirements discussed in Section 3.2. When generalizing this approach to cyclic mazes, additional considerations are required as multiple paths may exist between a pair of nodes. The proposed algorithm lets agents send a directed cast along a single, chosen edge, modeling directional communication along individual corridors. After an agent i moves from any node v to new node u, it sends a directed cast along edge u,v\u,v\. This informs its followers (i.e., active agents j that have agent i as their leader) about agent i’s previous node v. Additionally, the head can send a directed cast to inform any agents in its communication range of its next move. Similarly to [1], the agents can employ broadcast messages. In the present work, three types of broadcast messages are used: 1. The status message is sent once per time step by each agent i∈activei ^active and contains its ID, whether i is at the goal, (i.e., vi=gv_i=g) and i’s leader pointer Li∈(active∖i)∪nilL_i∈(A^active \i\)∪\ nil\. 2. The competing message is sent once per time step by all active non-head agents and contains only their ID and the flag competing, which indicates if they intend to move and should therefore be considered competing in potential conflicts for nodes in this time step. 3. The head message is sent once per time step by the current head agent, h, containing its ID, the flag competing, the state of the single-agent maze solver and information on the head agent at the next time step LhL_h (either nil if the current head keeps the role, and the ID of another agent otherwise). The proposed algorithm is shown in Algorithm 1, seen from the point of view of the executing agent i. It is executed by all agents in a synchronous, discrete-time manner. Subscripts i are omitted for better readability. Initialization: (Line 1) When i first becomes active, it is at node s and has no leader. (Line 2) Agent i then senses the adjacent node (as s is a leaf) to identify the neighborhood as well as if the adjacent node is the goal or if it is occupied. (Line 3) If agent i is the first agent activated, it will not receive any messages, resulting in =∅C= . If other agents have been activated before i, then there exists another active agent l that just left the start node and moved to the single adjacent node. In this case, agent i will receive a status message from l, and =lC=l. (Lines 4–5) If =lC=l, agent i will make l its leader, Li=lL_i=l. Otherwise, it keeps the leader pointer Li=nilL_i= nil and assumes the head role. While Loop: The agent executes the while loop (lines 6–28) until it reaches the goal g. Each iteration of the loop takes one time step. (Line 7) At the beginning of each time step, i resets its target node D to its current node v and competing to false. While Loop Head Decisions: (Line 8) If Li=nilL_i= nil, then agent i is the head agent. (Lines 9–10) If the goal is adjacent, i sets its target node D=gD=g. (Line 12) Else, agent i runs one step of the single-agent maze solver to determine an adjacent potential target node DsolverD^solver. (Lines 13–14) If DsolverD^solver is currently occupied by an agent j, j is chosen as the new head and leader of i. (Messages cannot pass through occupied nodes, hence Dsolver∈NodeTowards(a)D^solver∈ NodeTowards(a) will only be fulfilled for agent j, and the Selector55 5 The Selector operator is any deterministic operator that, given a set of agents A⊆A , returns the agent a∈Aa∈ A with a≤ba _Ab for all b∈A∖ab∈ A \a\. operator returns j.) Else, DsolverD^solver is either unoccupied or i’s current node, and i retains the head role. (Line 17) If DsolverD^solver is unoccupied, agent i sends a directed cast along edge v,Dsolverv,D^solver and updates its target node D accordingly. (Line 18) Then, i broadcasts a head message informing all other agents within its communication range whether one of them has been elected as the new head. While Loop Follower Decisions: (Line 20) If at time k agent i has a leader LiL_i, it executes routine ResolveConflict (discussed below), which is shown in Algorithm 2. ResolveConflict returns a target node D and the potentially updated leader LiL_i. Movement: (Lines 21-22) After completing its decision step, agent i moves synchronously with all other agents to its target node. It updates vprev^prev and v. Post-Movement Sensing and Messaging: (Lines 23–26) Agent i senses adjacent nodes. If i moved to a new node, it broadcasts a directed cast along v,vprev\v,v^prev\, and always broadcasts a status message. (Lines 27–28) Agent i receives directed casts and status messages from nearby agents and updates vLprev^prev_L and C accordingly. Agents who terminated after reaching the goal in the previous time step will not send a message, and are removed from C. Lines 23–28 are synchronized with lines 2–5 of a newly activated agent. ResolveConflict: (Line 1) Agent i checks whether the head h is in communication range and not yet at the goal. (Lines 2–3) If the head h is in communication range, agent i waits for the head message. (Lines 4–6) Agent i checks if it has been chosen to be the new head. If so, it broadcasts that it is not competing, sets its leader Li=nilL_i= nil, and sets its target to its current node. (Lines 7–9) If agent i was not chosen as the new head, it checks if the agent h is currently adjacent or will be adjacent in the next step. In this case, it sets the head as its leader, does not compete to move, and sets its target to its current node. If agent i was not chosen as the new head, it checks if it received the directed cast from h or if h is currently in an adjacent node. If either is true, i broadcasts that it is not competing, sets its leader Li=hL_i=h, and sets its target to its current node. (Lines 10–12) If the current head is not in communication range or neither of the above cases apply, agent i checks if the goal is adjacent and if so, does not compete for other nodes, maintains its current leader L, and sets its target to the goal. (Lines 13–15) Else, if its (non-head) leader is residing in an adjacent node, i keeps this leader and does not move. (Lines 16–18) If none of the above cases apply, agent i competes to move to the node previously occupied by its leader. It broadcasts competing=truecompeting= true and waits until it receives information on which agents in communication range are competing. (Line 19) Agent i determines which other agents are competing. An agent a is considered competing if it is not yet at the goal node, has signaled that competing=truecompeting= true, and wants to move to the same node as agent i. (Lines 20–23) The Selector function is called on the set of all competing agents and returns a winner. If agent i is the winner, it keeps its previous leader and selects as target the previous node of that leader. Else, i chooses the winner as its new leader and remains at its current node. (a) k=0k=0 (b) k=1k=1 (c) k=2k=2 (d) k=4k=4 (e) k=5k=5 (f) k=6k=6 (g) k=11k=11 (h) k=12k=12 Figure 2: An example of our algorithm (employing Trémaux’s algorithm). Gray nodes have been visited. k=0k=0: All agents are at start node s; agent 11 is active, claiming the head role (light green). k=1k=1: Agent 11 leaves s (now its previous node, purple arrow) following Trémaux’s algorithm (orange arrow). Agent 2 becomes active (dark green) and chooses agent 11 as leader (black arrow). k=2–4k=2--4: Agents 11 and 22 gradually navigate the maze, agent 33 becomes active. k=5k=5: Agent 22 receives the head’s directed cast and remains in its current node. Agent 11 chooses agent 22 to become the new head at k=6k=6. k=7–10k=7--10: Agent 22 transfers the head back to agent 11 which performs backtracking. k=11k=11: Agent 22 is again the head and moves to a node adjacent to the goal. k=12k=12: Agent 22 reaches the goal. Agents 11 and 33 compete for agent 22’s previous node; Agent 11 wins and moves to the node. Agent 33 chooses agent 11 as its new leader. Fig. 2 provides an example that highlights particular moments of a group of agents executing the aforementioned algorithms. 3.1 Mathematical Analysis We now prove the correctness of the algorithm and several properties. Lemma 1 At all discrete times k∈ℕ0k _0, there is exactly one agent assuming the head role. Let kw∈ℕ0∪∞k_w _0∪\∞\ be the time at which a single agent running a single-agent maze solver resides in a node adjacent to the goal for the first time. At all time steps k≤kwk≤ k_w, using the same single-agent maze solver, the head agent occupies the same node as the single agent would occupy at time k. At all times k>kwk>k_w, the head agent resides at the goal node. Proof Proof by induction: k=0k=0: At the beginning of the first time step, there is only one active agent h. h resides in the start node s≠gs≠ g as would an agent executing the single-agent maze solver and is the only head by default. k→k+1k→ k+1: An agent a that activates in time step k+1k+1 will activate only because another agent b just left the start node and moved to an adjacent node. Consequently, a is in communication range of b and will receive a status message from b, choosing b as its leader. At time k+1k+1, a is not the head. Per the induction assumption, there is exactly one head h at time k that is at the same node as a single agent executing the single-agent maze solver would be. We distinguish between three cases. Case 1: If k<kwk<k_w, h will use the single-agent maze solver to determine where to move to. If the determined adjacent node DsolverD^solver is not occupied, h will keep Lh=nilL_h= nil, set D=DsolverD=D^solver and inform agents in communication range (lines 1–1). Any agent that has h in communication range will receive the head message (line 2 of Algorithm 2). As h sent Lh=nilL_h= nil, no agent i will become the head (lines 2–2). Moreover, there is no other moment in time where an agent can set its leader to nil. As h will move to DsolverD^solver in time step k+1k+1, at time k+1k+1, there is exactly one head, agent h, which resides in the same node as a single agent executing the single-agent maze solver would. If DsolverD^solver is occupied at time k, agent h chooses the occupying agent L as its new leader and sends Lh=L_h=L to all agents in communication range via the head message. As L is occupying an adjacent node, it is in communication range of h and will wait for and receive the head message. As Lh=L_h=L, L sets its leader to nil and assumes the head role. As every agent has a unique IDID, no other agent j∈h∖Lj _h \L\ will fulfill Lh=jL_h=j and assume the head role. Consequently, at time k+1k+1, there is exactly one head, agent L, which resides in the same node as the single-agent maze solver would. Case 2: If k=kwk=k_w, then h is currently in a node adjacent to the goal. Consequently, it will move to the goal in time step k+1k+1. In doing so, it will remain the head and no other agent will receive a request to assume the head role. Case 3: If k>kwk>k_w, then h is at the goal node and no longer sending messages, and will never transfer the head. Hence, no other agent will set its leader to nil as h∈∣Lh=nil∧vh≠g=∅\h L_h= nil v_h≠ g\= . In both latter cases, at k+1k+1, there is exactly one head which resides at the goal. Lemma 2 The first visit to any node v∈∖sv \s\ is done by the current head agent. Any agent that reaches the goal will do so via the same node adjacent to the goal that was traversed by the head. Proof In the case where s and g are adjacent, at k=0k=0, there is only one active agent. This agent assumes the head role, moves to g (where it will eventually terminate). As all other agents activates afterwards, they also sense the goal being adjacent, move there and terminate. Consequently, the only node ≠s≠ s that is visited is g and it is first visited by the head. All agents move to g via s. Assume that s and g are not adjacent. Assume that there exists a node w∈∖s,gw \s,g\ that has not been visited before and is now visited by a non-head agent a. a has only two possible options to move to another node (lines 2 and 2 of Algorithm 2). Since w≠gw≠ g, a must have moved according to line 2, that is, to a node that was previously visited by its leader L, which is a contradiction to the fact that a is the first agent to visit w. Let u∈∖s,gu \s,g\ be the first node adjacent to the goal that the head agent visited. As the goal is adjacent, the head moves there from u and terminates. As shown above, no other node adjacent to the goal will be visited by any agent, as the head has already terminated at the goal. Thus, no other agent reaches a node adjacent to the goal before the head agent, and the goal node g is first visited by the head agent. Moreover, as u is the only adjacent node to the goal that is visited by any agent, it directly follows that every agent that reaches the goal will do so by traversing via u. Lemma 3 For any node v∈∖gv \g\, at all discrete times k, v is occupied by at most one active agent. If an agent leaves node v in time step k, no other agent that was already active at k−1k-1 will move to v in the same time step. In time step k, all agents competing for the same node v have the same leader. Proof Proof by strong induction: At time k=0k=0, all agents are at s, all but one are inactive and the lemma holds for any v∈∖gv \g\. Let k0∈ℕk_0 be the first time step where the head leaves the start node and hence occupies an adjacent node. As soon as the head leaves the start node, one agent a that is not the head becomes active at the start node. Again, the lemma is true. 1,2,…,k→k+11,2,…,k→ k+1: Let v∈∖gv \g\. Per induction assumption at k, there is no more than one active agent at v. There are only two options how agents can move to v: either as the (only) head (Lemma 1) moving to Dsolver=vD^solver=v or following their leader to vLprev=v^prev_L=v. In the first case, if v is currently occupied, the head h chooses the occupying (active) agent (which is only one due to the induction assumption) as new head and does not move (lines 1–1). Hence, h will not move to a node in time step k+1k+1 that is occupied at time k. If v is not occupied, h sends out a directed cast along Dsolver=vD^solver=v which all agents in h(v)U_h(v) will receive (i.e., all other agents adjacent to v). They choose h as their leader and remain in their current node. Hence, h can safely move to v without collision, that is, there is only one active agent at v at time k+1k+1. In the second case, an agent a aims to move to the previous node vLaprev=v^prev_L_a=v of its leader LaL_a. It can only do so if it received the directed cast from its leader LaL_a in the previous time step, that is, a∈La(v)a _L_a(v) and La∈aL_a _a, if it is selected by the Selector-operator, and if the head does not aim to move there in this time step. If vLaprev^prev_L_a is occupied, LaL_a must be residing there and a does not move (lines 2–2) as else, a would not have received the directed cast from LaL_a. If vLaprev^prev_L_a is unoccupied, a receives all competing messages from agents in communication range. Every non-head agent b that could move to vLaprev^prev_L_a fulfills the following: (i) b∈ab _a, as b must be adjacent to vLaprev^prev_L_a to be able to move there, so a and b are two hops away with an empty node in between, (i) vb≠gv_b≠ g as else, b would not move, (i) competingb=truecompeting_b= true, as this is only sent if b not already decided to remain in its current node nor move to g, (iv) Lb∈aL_b _a and vLbprev=vLaprev^prev_L_b=v^prev_L_a, as else, b would not aim to move to vLaprev^prev_L_a. Per induction assumption at k−1k-1, there was at most one agent residing at vLaprev^prev_L_a, which means that in time step k+1k+1, vLaprev^prev_L_a can only be the previous node of LaL_a and no other agent. Hence, every non-head agent that aims to move to and therefore competes for vLaprev^prev_L_a in time step k+1k+1 does so because LaL_a is its leader. Consequently, a has every competing agent in ℛaR_a (line 2). It directly follows that b∈ℛa⟺a∈ℛb _a a _b and ℛa∪a=ℛb∪bR_a∪\a\=R_b∪\b\. All agents competing for v choose the same agent as winner by applying the (deterministic) Selector-operator on the same set, resulting in only one agent that is allowed to move to v. Hence, at time k+1k+1, there is at most one active agent at v. As agents only move simultaneously and to currently unoccupied nodes, no other agent that is active at k will aim to move to v in time step k+1k+1 if v is occupied at k. Corollary 1 Under the algorithm, vertex and following conflicts cannot occur. Lemma 4 At all discrete times k, if an active agent a is not the head, it has its current leader LaL_a in communication range and one or more of the following three cases are true: 1. the previous node of its leader vLaprev[k]v^prev_L_a[k] is unoccupied and adjacent to va[k]v_a[k] and vLa[k]v_L_a[k] 2. the current node of a’s leader vLa[k]v_L_a[k] is adjacent to a’s current node va[k]v_a[k] 3. va[k]=vLa[k]=gv_a[k]=v_L_a[k]=g. Proof See Appendix 0.A for the complete proof. Non-head agents move to follow their leader. Agents only compete to move when their leader has moved to a non-adjacent node. An activated agent starts with their leader in an adjacent node by default, so this occurs only when a leader moves two nodes away, leaving an unoccupied node. The leader is still in communication range at this point, but may move again. Agents following this leader now compete for the unoccupied space. If an agent wins this competition, it moves to follow its leader. Otherwise, another agent moves to this space and is chosen as new leader, maintaining proximity and communication network cohesiveness. Leaders may also stop communicating when they reach a goal. In this case, agents still compete for the previously occupied node, which brings them into proximity of the goal and maintains the network connectivity for remaining agents. Lemma 5 At all discrete times k, an active agent follows the head directly or indirectly. Formally, at discrete time k, let the directed leadership graph be L[k]=(active[k],ℰL[k])T_L[k]=(A^active[k],E_L[k]), a,b∈active[k]:b is leader of a⟺(a,b)∈ℰL[k]a,b ^active[k]:b is leader of a (a,b) _L[k]. Then, L[k]T_L[k] is an in-tree [14] with the current head agent h as its root, that is, for all a∈active[k]∖ha ^active[k] \h\, there exists exactly one path to h in L[k]T_L[k]. Proof See Appendix 0.A for the complete proof. For an agent to not be following the head (either directly or indirectly), it would have to be following another agent for which no path exists leading to the head. This would require either a cycle within the tree created by following agents, or for two agents to be acting as the head. Lemma 1 shows that only one head exists at a time. A cycle in leadership can only arise when the head passes the head role to a new agent who is choosing to follow the current head. However, once an agent receives a head message informing it of its role as new head, it removes the following edge to the former head. Additionally, when agents win competitions for moving to unoccupied nodes, they maintain their leader and losing agents select the winner as their new leader, maintaining the in-tree behavior of leadership. Theorem 3.1 If a single agent executing a single-agent maze solver reaches a node adjacent to the goal for the first time in time step kg−1k_g-1, then n agents executing Algorithm 1 (using the same single-agent maze solver) reach the goal in at most kg+2(n−1)k_g+2(n-1) time steps. Proof If the goal node is adjacent to the start node, the single agent is already in an adjacent node at time k=0k=0, that is, kg=1k_g=1. Executing Algorithm 1, the first agent moves to g in the first time step (lines 1–1), that is, it will be there at k=1k=1. The newly activated agent moves to the goal in the next time step (Algorithm 2, lines 2–2), and this repeats for all other agents, that is, all agents will reach the goal at time n≤kg+2(n−1)n≤ k_g+2(n-1). Now, let s and g be not adjacent. Let w≠sw≠ s be the first node adjacent to the goal visited by the single agent in time step kg−1k_g-1. Per Lemma 1, the current head agent h is in node w at time kg−1k_g-1, moves to the goal node in the next time step, vh[kg]=gv_h[k_g]=g, and send out a final directed cast along w and status message (including that it is now at the goal node) before it terminates. This means that no other agent receives the head role after kgk_g. Let kak_a be the time step in which an agent a moves to the goal node. Let na−1n_a-1 be the number of agents that are not yet at the goal node at time kak_a. We prove the following statement via induction: If an agent a reaches the goal at kak_a, then all na≤n_a≤ n agents reach the goal in at most ka+2(na−1)k_a+2(n_a-1) time steps. na=1n_a=1: If a reaches the goal at kak_a, there are na−1=0n_a-1=0 agents left on nodes other than the goal. All agents reached the goal at ka=ka+2(na−1)k_a=k_a+2(n_a-1). na→na+1n_a→ n_a+1: If a moved to the goal at kak_a, there are (na+1)−1=na>0(n_a+1)-1=n_a>0 agents not at g. None of these agents can assume the head role (Lemmas 1 and 2). Assume that there is an agent b of these nan_a agents that is not a direct or indirect follower of a. As b is a direct or indirect follower of the head (Lemma 5), there exists exactly one path in the directed leadership graph L[ka]T_L[k_a] from b to the head h. Let the set ℬB include all agents that are between b and h on this path (especially, a∉ℬa ). If ℬ=∅B= , b is a direct follower of h. Let c∈ℬ∪bc ∪\b\ be the agent on this path that is the direct follower of h. h has already been at the goal node for at least two time steps (i.e., vprevh=gv_prev_h=g), as it must have moved there before agent a moved to w at time ka−1k_a-1. Hence, c must also be at the goal node (Lemma 4), as it cannot be adjacent to g, as w was occupied by a at ka−1k_a-1 (Lemmas 2 and 3). With the same argument, c must have been at the goal node since at least ka−2k_a-2, and if c≠bc≠ b, we can follow that the direct follower of c in ℬB is already at the goal. Continuing this down the path to b, b must already be at the goal node at time kak_a. Consequently, all nan_a agents that are not yet at the goal node are direct or indirect followers of a. This means that at time kak_a, there exists at least one direct follower b that is in a node adjacent to w. In the next time step ka+1k_a+1, b aims to move to vpreva=wv_prev_a=w. Let b b be the agent that wins against all competing agents for w, keeps a as leader (Lemma 3) and moves there at ka+1k_a+1. Then, in the next time step ka+2k_a+2, as the goal is adjacent, b b will move to g and consequently be there at time ka+2k_a+2 while na−1n_a-1 agents are not at the goal at ka+2k_a+2. Using the induction assumption, it follows that all agents reach the goal in at most (ka+2)+2(na−1)=ka+2((na+1)−1)(k_a+2)+2(n_a-1)=k_a+2((n_a+1)-1) time steps. Hence, as the head agent reaches g at time kgk_g, it follows that all n agents reaches the goal in at most kg+2(n−1)k_g+2(n-1) time steps. Theorem 3.2 Let the full-knowledge (FK) strategy be the strategy where agents have full prior knowledge of the environment. If the used single-agent maze solver is complete, the ratio R(n)=MAlgo(n)/MFK(n)R(n)=M_Algo(n)/M_FK(n) of the makespan of the proposed algorithm, MAlgo(n)M_Algo(n), relative to the one of the FK strategy, MFK(n)M_FK(n), is either R(n)=1R(n)=1 or strictly decreasing with asymptotic equivalence, limn→∞R(n)=1 _n→∞R(n)=1. Proof If the used single-agent maze solver is complete, it finds a node adjacent to the goal at time kg−1k_g-1. Per Theorem 3.1, n agents executing Algorithm 1 reach the goal at time MAlgo(n)=kg+2(n−1)M_Algo(n)=k_g+2(n-1) at the latest. If start and goal are adjacent, using Algorithm 1, at every time step, one agent reaches the goal, and all agents will have reached it at time MAlgo(n)=nM_Algo(n)=n. Having full knowledge of the environment, agents executing the full-knowledge strategy also move one-by-one to the goal, such that all agents will have reached the goal at time MFK(n)=nM_FK(n)=n. Hence, R(n)=MAlgo(n)/MFK(n)=1R(n)=M_Algo(n)/M_FK(n)=1. Now assume that s and g are not adjacent. As s is a leaf and the full-knowledge strategy needs to have no vertex or following conflicts at nodes ≠g≠ g, an agent can leave the start node only every two time steps. This means that, even when following shortest paths, an agent can move to g only every two time steps. Consequently, MFK(n)=kFK+2(n−1)M_FK(n)=k_FK+2(n-1), where kFKk_FK describes the length of the shortest path from s to g, as the first agent that left s reaches g at kFKk_FK and every two time steps later, the next agent can reach the goal. If kg=kFKk_g=k_FK, R(n)=1R(n)=1. If kg>kFKk_g>k_FK, it follows (∂nR)(n)=−2kg−kFK(kFK+2(n−1))2<0 ( _nR )(n)=-2 k_g-k_FK(k_FK+2(n-1))^2<0 and limn→∞R(n)=limn→∞kg+2(n−1)kFK+2(n−1)=limn→∞kg/(n−1)+2kFK/(n−1)+2=1. _n→∞R(n)= _n→∞ k_g+2(n-1)k_FK+2(n-1)= _n→∞ k_g/(n-1)+2k_FK/(n-1)+2=1. Hence, the makespan of Algorithm 1 is either equal or asymptotically equivalent to the one of the full-knowledge strategy with respect to n. 3.2 Time and Space Complexity Analysis Let d≔degd be the maximum degree of the graph. Space Complexity. In the worst case, an agent a is at a node with degree d, and all adjacent nodes are unoccupied, have degree d and have active agents occupying adjacent nodes. This results in at most min(n,d(d−1)) (n,d(d-1)) active agents in communication range of a, and requires (min(n,d2))O( (n,d^2)) space to store C and information sent by nearby agents. Agents must also maintain the NodesTowards list for each agent within communication range. In the worst case, an agent in a non-adjacent node sends a broadcast that reaches a via all d adjacent nodes, resulting in a worst-case size of (d)O(d) for any NodesTowards. Agents also require (d)O(d) space for occupiedN^occupied, and (1)O(1) for any other variables. Our proposed algorithm therefore requires (dmin(n,d2))O(d (n,d^2)) space. Additional spatial requirements depend on the single-agent maze solver selected (e.g., BFS has a requirement of (||)O( |V |) [8], resulting in (||+dmin(n,d2))O( |V |+d (n,d^2)), whereas Trémaux’s algorithm without marking the environment requires (|ℰ|)O( |E |) [8], giving a total of (|ℰ|+dmin(n,d2))O( |E |+d (n,d^2))). Time Complexity. Each iteration of the algorithm has a constant number of function calls that have at maximum a runtime of (min(n,d2))O( (n,d^2)). Per Theorem 3.1, the overall number of iterations depends on the single-agent maze solver and number of agents. Trémaux’s algorithm takes (|ℰ|)O( |E |) as all edges are traversed at most twice [8], BFS needs ((||+|ℰ|)2)O(( |V |+ |E |)^2) [8] as a physical agent needs to backtrack at every visited node, and a uniform random walk is expected to run in (||3)O( |V |^3) [3]. In total, the algorithm with Trémaux’s algorithm needs ((|ℰ|+n)min(n,d2))O(( |E |+n) (n,d^2)), with BFS (((||+|ℰ|)2+n)min(n,d2))O((( |V |+ |E |)^2+n) (n,d^2)) and with a uniform random walk an expected ((||3+n)min(n,d2))O(( |V |^3+n) (n,d^2)). 4 Results Figure 3: Simulations in grid mazes using Trémaux’s algorithm and BFS at times k=20k=20 and k=100k=100. Walls are dark gray, and nodes that were already visited are light gray. In this example, Trémaux’s algorithm explores a larger portion of the graph, though BFS is the first to reach the goal. Our algorithm (hereafter, MAMT) requires a single-agent maze solver to determine head movement. We evaluated MAMT with three such solvers: Trémaux’s algorithm, which explores the graph in a DFS-manner, ensuring no edge is visited more than twice; BFS, which explores the graph with increasing distance from the start node; and a uniform random walk. Simulations were conducted in square grid mazes (see Fig. 3). For every combination of maze size l×l,l∈5,15,25,35l× l,l∈\5,15,25,35\ and number of agents n∈1,5,25,125,625n∈ \1,5,25,125,625 \, a same set of 20 random mazes were simulated, with a 10410^4 steps timeout. Fig. 4 shows the makespan and sum-of-fuels performance. All trials were collision-free, and, for MAMT with Trémaux’s algorithm or BFS, all agents reached the goal. In ten trials (two for l=25l=25 and eight for OPENl=35)l=35), MAMT with random walk timed out. Although in contrast to BFS, Trémaux’s algorithm does not necessarily find a shortest path, its performance was superior to that of BFS. This result arises because Trémaux’s algorithm backtracks less extensively than BFS. As the group size increases, both makespan and average sum-of-fuels showed a tendency of approaching the mean performance of a full-knowledge strategy (i.e., omniscient agents, following a shortest path). Once the goal is found by the first agent, further agents follow at a steady rate, reducing average sum-of-fuel and the increase in makespan as the number of agents grows. Figure 4: Makespan and average sum-of-fuel for the proposed algorithm using Trémaux’s algorithm, BFS, and uniform random walk across various mazes and number of agents. Dashed lines indicate the mean values for agents following the shortest path. We evaluate MAMT against the full-knowledge strategy and a naïve baseline. For the latter, every agent a independently runs the single agent maze solver to determine its next node xax_a. The naïve baseline uses the following rules: (i) If xax_a is currently unoccupied and no other agents want to move there, a moves to this node; (i) if xax_a is currently unoccupied and at least one other agent wants to move there, the agent of minimum IDID moves there while other competing agents wait; (i) A target-cycle occurs if it exists a subset of agents ℬ⊆B and a permutation π:ℬ↦ℬπ:B with xb=vπ(b)x_b=v_π(b) ∀b∈ℬ∀ b . If such a target-cycle occurs and a is part of it, it forwards its single-agent maze solver instance to the agent that occupies its target node (and receives an instance of another agent); (iv) if xax_a is currently occupied and a is not part of a target-cycle, it waits. Figure 5: Comparison of makespan and average sum-of-fuel for MAMT and naïve strategies (each using the Trémaux’s algorithm and BFS) against the full-knowledge strategy. Trials were conducted for up to 625625 agents in 2020 mazes of size 25×2525× 25. Trials that triggered the timeout of 10410^4 time steps were excluded. Trials were performed in mazes of size 25×2525× 25 with the remaining setup unchanged. The results are shown in Fig. 5. The MAMT variants succeeded in all trials. For 125 agents, the naïve strategy using BFS timed out in 9 trials. For 625 agents, the naïve strategy with Trémaux’s algorithm timed out in 2 trials, whereas the BFS-based variant timed out in all 20 trials . As before, the superior performance between Trémaux’s algorithm compared to BFS is highly visible. The results show that with growing agent group size and the same underlying single-agent maze-solver, MAMT outperforms the naïve strategy in both makespan and average sum-of-fuels. They suggest that MAMT approaches in makespan the full-knowledge strategy as number of agents increases. The source code is available at [21]. 5 Conclusion We present an algorithm for multi-agent maze traversal, extending [1] to general graphs. We prove that if the underlying single-agent maze solver is complete, the algorithm enables all agents to reach the undisclosed goal in finite time. We prove that achieved makespan is asymptotically equivalent to that achieved by optimal, omniscient agents. We show that MAMT outperforms a naïve baseline where all agents use a single-agent maze solver. We analyze the efficacy of several single-agent search algorithms when used by MAMT. Future work includes real-world experiments [1] and robustness to communication failures. Acknowledgements This work was funded by BMFTR (Robotics Institute Germany; grant 16ME1001); EU Horizon Europe Framework Programme (“OpenSwarm”; grant 101093046); LOEWE center emergenCITY [LOEWE/1/12/519/03/05.001(0016)/72]. ChatGPT (OpenAI, Free Plan) assisted generation of code used for generating maze environments for simulation purposes, and code to plot Figures 3–5. It was also used for improving the language of the manuscript. It was not used in the design or implementation of the presented algorithm, baseline methods, or proofs. Disclosure of Interests. The authors have no competing interests to declare. References [1] J. Argote-Gerald, G. Miyauchi, J. Rau, P. Trodden, and R. Groß (2025) Design for one, deploy for many: navigating tree mazes with multiple agents. In 2025 IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS), Vol. , p. 1–7. External Links: Document Cited by: §1, §1, §2, §2, §2, §2, §2, §2, §3, §3, §5. [2] P. Brass, F. Cabrera-Mora, A. Gasparri, and J. Xiao (2011) Multirobot tree and graph exploration. IEEE Transactions on Robotics 27 (4), p. 707–717. External Links: Document Cited by: §1. [3] G. Brightwell and P. Winkler (1990) Maximum hitting time for random walks on graphs. Random Structures & Algorithms 1 (3), p. 263–276. External Links: Document Cited by: §1, §3.2. [4] F. Cabrera-Mora and J. Xiao (2012) A flooding algorithm for multirobot exploration. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 42 (3), p. 850–863. Cited by: §1. [5] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (2022) Introduction to algorithms. MIT press. Cited by: §1. [6] B. Crnković, S. Ivić, and M. Zovko (2023) Fast algorithm for centralized multi-agent maze exploration. arXiv preprint arXiv:2310.02121. Cited by: §1. [7] D. Dereniowski, Y. Disser, A. Kosowski, D. Pajak, and P. Uznański (2015) Fast collaborative graph exploration. Information and Computation 243, p. 37–49. Cited by: §1. [8] S. Even (2011) Graph algorithms. 2nd edition, Cambridge University Press. External Links: ISBN 978-0-521-73653-4 Cited by: §1, §3.2, §3.2. [9] P. Fraigniaud, L. Gasieniec, D. R. Kowalski, and A. Pelc (2006) Collective tree exploration. Networks: An International Journal 48 (3), p. 166–177. Cited by: §1. [10] M. D. Hall, A. Özdemir, and R. Groß (2020) Self-reconfiguration in two-dimensions via active subtraction with modular robots.. In Robotics: Science and Systems, Cited by: §1. [11] E. H. Kivelevitch and K. Cohen (2010) Multi-agent maze exploration. Journal of Aerospace Computing, Information, and Communication 7 (12), p. 391–405. Cited by: §1. [12] M. Linardakis, I. Varlamis, and G. Th. Papadopoulos (2024) Distributed maze exploration using multiple agents and optimal goal assignment. IEEE Access 12 (), p. 101407–101418. External Links: Document Cited by: §1. [13] J. Martz, W. Al-Sabban, and R. N. Smith (2020) Survey of unmanned subterranean exploration, navigation, and localisation. IET Cyber-Systems and Robotics 2 (1), p. 1–13. Cited by: §1. [14] K. Mehlhorn and P. Sanders (2008) Algorithms and data structures: the basic toolbox. Springer Berlin, Heidelberg. External Links: Document Cited by: Lemma 5, Proof, Proof. [15] R. R. Murphy, J. Kravitz, S. L. Stover, and R. Shoureshi (2009) Mobile robots in mine rescue and recovery. IEEE Robotics & Automation Magazine 16 (2), p. 91–103. Cited by: §1. [16] S. C. Nagavarapu, L. Vachhani, and A. Sinha (2016) Multi-robot graph exploration and map building with collision avoidance: a decentralized approach. Journal of Intelligent & Robotic Systems 83 (3), p. 503–523. Cited by: §1. [17] B. Nebel, T. Bolander, T. Engesser, and R. Mattmüller (2019) Implicitly coordinated multi-agent path finding under destination uncertainty: success guarantees and computational complexity. Journal of Artificial Intelligence Research 64, p. 497–527. Cited by: §1. [18] C. Parrott, T. J. Dodd, J. Boxall, and K. Horoshenkov (2020) Simulation of the behavior of biologically-inspired swarm robots for the autonomous inspection of buried pipes. Tunnelling and Underground Space Technology 101, p. 103356. Cited by: §1. [19] P. Petráček, V. Krátký, M. Petrlík, T. Báča, R. Kratochvíl, and M. Saska (2021) Large-scale exploration of cave environments by unmanned aerial vehicles. IEEE Robotics and Automation Letters 6 (4), p. 7596–7603. External Links: Document Cited by: §1. [20] A. Queffelec, O. Sankur, and F. Schwarzentruber (2023) Complexity of planning for connected agents in a partially known environment. Theoretical Computer Science 941, p. 202–220. Cited by: §1. [21] J. Rau, J. Argote-Gerald, G. McFassel, G. Miyauchi, P. Trodden, and R. Groß (2026) Simulation source code. Note: https://github.com/julianmrau/Multi-Agent-Maze-Traversal-on-Cyclic-Graphs Cited by: §4. [22] G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant (2015) Conflict-based search for optimal multi-agent pathfinding. Artificial intelligence 219, p. 40–66. Cited by: §1. [23] B. Shofer, G. Shani, and R. Stern (2023) Multi agent path finding under obstacle uncertainty. In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 33, p. 402–410. Cited by: §1. [24] D. Silver (2005) Cooperative pathfinding. In Proceedings of the aaai conference on artificial intelligence and interactive digital entertainment, Vol. 1, p. 117–122. Cited by: §1. [25] R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, E. Boyarski, and R. Barták (2019) Multi-agent pathfinding: definitions, variants, and benchmarks. In Proceedings of the Symposium on Combinatorial Search (SoCS), Vol. 10, p. 151–158. External Links: Document Cited by: §1, §2, §2. [26] J. Yu and S. M. LaValle (2016) Optimal multirobot path planning on graphs: complete algorithms and effective heuristics. IEEE Transactions on Robotics 32 (5), p. 1163–1177. External Links: Document Cited by: §1. [27] J. Zhang, X. Niu, A. J. Croxford, and B. W. Drinkwater (2023) Pipe inspection using guided acoustic wave sensors integrated with mobile robots. NDT & E International 139, p. 102929. External Links: ISSN 0963-8695, Document, Link Cited by: §1. Appendix 0.A Proofs of Lemmas 4–5 In the following, the full proofs of Lemmas 4–5 are presented. 0.A.1 Proof of Lemma 4 Proof Proof by induction. At k=0k=0, there is only one active agent. It assumes the head role and the lemma is true. Let k0k_0 be the first discrete time where the head is not in the start node anymore, meaning it left the start node in time step k0k_0 and is consequently in an adjacent node. As soon as the head left the start node, a new agent a that is not the head became active. As this agent then received a status message from the head, a chose the head as its leader. As the head is adjacent, a has its leader in communication range. k→k+1k→ k+1: If a was just activated at the start node in time step k+1k+1, it has LaL_a in communication range (same argument as above) and vLa[k+1]v_L_a[k+1] is adjacent. Let h be the head agent at time k. If it remains the head in time step k+1k+1, it has no leader at k+1k+1. Otherwise, there was another active agent L that occupied an adjacent node of h at k. L was then chosen to be the new head and h’s leader. As h did not leave its current node, vh[k]=vh[k+1]v_h[k]=v_h[k+1]. In the same time step, L received the head message stating that L should assume the head role, and consequently did, remaining in its current node, vL[k]=vL[k+1]v_L[k]=v_L[k+1]. Hence, L is adjacent to h and in h’s communication range at time k+1k+1. Let a be an active agent that does not assume the head role in time step k+1k+1 and was activated in an earlier time step. Per induction assumption, a had its leader LaL_a in communication range and at least one of the three cases is true at k. If va=vL=gv_a=v_L=g, neither a nor L will move in time step k+1k+1 and the lemma is true for k+1k+1. Let va≠gv_a≠ g at k. As a is not the head, it will execute Algorithm 2. If the head h is not yet at the goal and in communication range of a, a will wait for the head message from h. As a will not assume the head role, it will check if it received the head’s directed cast or if the head is already in an adjacent node and not a’s current leader. If so, a chooses h as its new leader and remains in its current node. If the directed cast was received by a, DsolverD^solver is an adjacent node of vav_a where the head will move to in this time step. If the head is already in an adjacent node vh[k]v_h[k], it can only move to a node that is at most two edges away from a. In this case, no other agent will move to vh[k]v_h[k] in time step k+1k+1 (Lemma 3). Hence, a’s new leader h is adjacent to a or two nodes away with the unoccupied node vprevh[k+1]=vh[k]v_prev_h[k+1]=v_h[k] adjacent to va[k+1]v_a[k+1] and vh[k+1]v_h[k+1], meaning that h∈ah _a at time k+1k+1. If the head is not in communication range or already at the goal, or no directed cast was received and (i) the head is not adjacent or (i) already a’s leader, a checks if the goal is adjacent. If so, the head has been at the goal for multiple time steps (Lemmas 2 and 3) and a moves there in timestep k+1k+1. As a must have moved to this adjacent node of the goal in the time step k (else it would have already moved to the goal in a previous time step), a followed its leader LaL_a there, meaning that LaL_a already resides at the goal, i.e., va[k+1]=vLa[k+1]=gv_a[k+1]=v_L_a[k+1]=g. If the goal is not adjacent to a, a checks if LaL_a resides in an adjacent node at time k. If so, a will keep LaL_a as leader and not move. Either LaL_a also remains at its current node (i.e., at time k+1k+1 a is adjacent to its leader LaL_a) or it moves to an adjacent node and no other agent moves to vLa[k]v_L_a[k] (Lemma 3) meaning that LaL_a is in communication range and its previous node vLprev[k+1]=vL[k]v^prev_L[k+1]=v_L[k] is unoccupied and adjacent to a and LaL_a at time k+1k+1. If none of the above applies (i.e., at time k the leader is two nodes away from a and the leader’s previous node vLaprev[k]v^prev_L_a[k] is unoccupied and adjacent to va[k]v_a[k] and vLa[k]v_L_a[k]), a calculates all competing agents for vLaprev[k]v^prev_L_a[k] (Lemma 3). If a is chosen as the winner, it keeps its leader and moves to vLaprev[k]v^prev_L_a[k]. As the leader remains in its current node or moves to an adjacent node, at time k+1k+1, either LaL_a is adjacent to a or two nodes away with vLaprev[k+1]=vLa[k]v^prev_L_a[k+1]=v_L_a[k] which is adjacent to a (as va[k+1]=vLaprev[k]v_a[k+1]=v^prev_L_a[k]) and no other agent moves to vLa[k]v_L_a[k] (Lemma 3), i.e., L is in communication range. If a is not selected as winner, it remains in its current node and choses the winning agent b (which moves to vLaprev[k]v^prev_L_a[k]) as new leader. hence, at time k+1k+1, a is adjacent to its new leader b and b is in a’s communication range. 0.A.2 Proof of Lemma 5 Proof Per Lemma 1, at all discrete times k only one agent has no leader. Every other agent has one leader, meaning that |ℰL[k]|=|active[k]|−1 |E_L[k] |= |A^active[k] |-1. Hence, if L[k]T_L[k] is connected, the underlying undirected graph must be a tree [14], i.e. there is never more than one path from any other node to the root node. Proof by induction. At k=0k=0, only one agent is active and assumes the head role, the lemma is true. Let k0k_0 be as in Lemma 4; after the head leaves s, the newly activated agent chooses the head as its leader. As the head moved to an adjacent node of s in time step k0k_0, it will not choose the newly activated agent as leader (Lemma 1) and the lemma is true. k→k+1k→ k+1: Assume that at time k, L[k]T_L[k] is an in-tree. There are four cases where an agent can change its leader in time step k+1k+1. We interpret every case as operation on L[k]T_L[k] and show that none change the in-tree property: (i) The head chooses another agent b to be the new head and its leader (Algorithm 1 line 1). (i) A non-head agent a chooses the current head as its new leader (Algorithm 2 line 2). (i) A non-head agent a competes with other non-head agents for the previous node of its leader and chooses the winner b as new leader (Algorithm 2 line 2). (iv) An inactive agent a activates at the start node s and chooses the agent b that just left s as its leader. Cases (i) and (i) can happen simultaneously at some time k+ϵk+ε, ϵ∈(0,1)ε∈(0,1). In case (i), the edge (h,b)(h,b) was added to ℰLE_L before h sent out the head-message. b will set its leader to nil at k+ϵk+ε after receiving the head-message, removing the edge (b,Lb)(b,L_b) from b to its old leader LbL_b. Hence, b has no outgoing edges anymore and becomes the new root. For an agent a∈active[k]∖b,ha ^active[k] \b,h\ that was a direct or indirect follower from b at time k, i.e., the unique path to h was P(a,h)[k]=P(a,b)[k]∪(b,Lb)∪P(Lb,h)[k]P(a,h)[k]=P(a,b)[k]∪\(b,L_b)\∪ P(L_b,h)[k], P(a,b)[k]=P(a,b)[k+ϵ]P(a,b)[k]=P(a,b)[k+ε] was not changed and is now the unique path to the new head b. For h, the unique path to the new head b is defined by P(h,b)[k+ϵ]=(h,b)P(h,b)[k+ε]=\(h,b)\. For an agent a≠b,ha≠ b,h that was a descendant [14] from h but not b at time k, i.e., (b,Lb)∉P(a,h)[k](b,L_b)∉ P(a,h)[k], the unique path to the new head b results from P(a,b)[k]=P(a,h)∪(h,b)P(a,b)[k]=P(a,h)∪\(h,b)\. In case (i), the edge from a to its old leader is removed and the edge (a,h)(a,h) is added. If h keeps the head role, the unique path from a to h evaluates to P(a,h)[k+ϵ]=(a,h)P(a,h)[k+ε]=\(a,h)\. If b is chosen as new head, the path to b results to P(a,b)[k+ϵ]=(a,h),(h,b)P(a,b)[k+ε]=\(a,h),(h,b)\ (see (i)). Hence, L[k+ϵ]T_L[k+ε] is an in-tree. At a later time k+δk+δ, δ∈(ϵ,1)δ∈(ε,1) case (i) may occur. In case (i), as b will keep its current leader in time step k+1k+1 (Algorithm 2 line 2, Lemma 3), the unique path to the current head h results from P(a,h)[k+δ]=(a,b)∪P(b,h)[k+δ]P(a,h)[k+δ]=\(a,b)\∪ P(b,h)[k+δ]. Even if the same update occurs along the leader chain of b, with the same argumentation there will be a unique path P(b,h)[k+δ]P(b,h)[k+δ] from b to h, i.e., L[k+δ]T_L[k+δ] is an in-tree. After moving, at time k+γk+γ, γ∈(δ,1)γ∈(δ,1) case (iv) may occur and active[k+γ]=active[k+δ]∪aA^active[k+γ]=A^active[k+δ]∪\a\. As agent a chooses b as its leader, i.e., adding edge (a,b)(a,b), the unique path to the current head h is defined by P(a,h)[k+γ]=(a,b)∪P(b,h)[k+γ]P(a,h)[k+γ]=\(a,b)\∪ P(b,h)[k+γ]. As no other leadership changes happen, at k+1k+1, L[k+1]=L[k+γ]T_L[k+1]=T_L[k+γ] is an in-tree.