# A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution

Ying Feng1, Adittyo Paul1, Zhe Chen2, Jiaoyang Li1

###### Abstract

One area of research in multi-agent path finding is to determine how
replanning can be efficiently achieved in the case of agents being delayed
during execution. One option is to reschedule the passing order of agents,
i.e., the sequence in which agents visit the same location. In response, we
propose Switchable-Edge Search (SES), an A*-style algorithm designed to find
optimal passing orders. We prove the optimality of SES and evaluate its
efficiency via simulations. The best variant of SES takes less than 1 second
for small- and medium-sized problems and runs up to 4 times faster than
baselines for large-sized problems.

## Introduction

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths
that move a team of agents from their start to goal locations. MAPF is
fundamental to numerous applications, such as automated warehouses (Wurman,
D’Andrea, and Mountz 2007; Kou et al. 2020), computer games (Silver 2005), and
drone swarms (Hönig et al. 2018).

Classic MAPF models assume flawless execution. However, in real-world
scenarios, agents may encounter unexpected delays due to mechanical
differences, unforeseen events, localization errors, and so on. To accommodate
such delays, existing research suggests the use of a Temporal Plan Graph (TPG)
(Hönig et al. 2016). The TPG captures the precedence relationships within a
MAPF solution and maintains them during execution. Each precedence
relationship specifies an order for two agents to visit the same location. An
agent advances to the next location in its path only if the corresponding
precedence conditions are met. Consequently, if an agent experiences a delay,
all other agents whose actions depend on this agent will pause. Despite its
advantages of providing rigorous guarantees on collision-freeness and
deadlock-freeness, the use of TPG can introduce a significant number of waits
into the execution results due to the knock-on effect in the precedence
relationship.

In this paper, we adopt a variant of TPG, named _Switchable TPG_ (STPG)
(Berndt et al. 2020). STPG allows for the modification of some precedence
relationships in a TPG, resulting in new TPGs. To address delays, we propose
an A*-style algorithm called _Switchable-Edge Search_ (SES) to find the new
TPG based on a given STPG that minimizes the travel times of all agents to
reach their goal locations. We prove the optimality of SES and introduce two
variants: an execution-based variant (ESES) and a graph-based variant (GSES).
Experimental results show that GSES finds the optimal TPG with an average
runtime of less than 1 second for various numbers of agents on small- and
medium-sized maps. On larger maps, GSES runs up to 4 times faster than
existing replanning algorithms.

## Preliminaries

######  Definition 1 (MAPF).

Multi-Agent Path Finding (MAPF) aims to find collision-free paths for a team
of agents $\mathcal{A}$ on a given graph. Each agent $i\in\mathcal{A}$ has a
unique start location and a unique goal location. In each discrete timestep,
every agent either moves to an adjacent location or waits at its current
location. A path for an agent specifies its action at each timestep from its
start to goal locations. A collision occurs if either of the following
happens:

  1. 1.

Two agents are at the same location at the same timestep.

  2. 2.

One agent leaves a location at the same timestep when another agent enters the
same location.

A MAPF solution is a set of collision-free paths of all agents.

######  Remark 1.

The above definition of collision coincides with that in the setting of
k-robust MAPF (Atzmon et al. 2018) with $k=1$. We disallow the second type of
collision because, if agents follow each other and the front agent suddenly
stops, the following agents may collide with the front agent. Thus, this
restriction ensures better robustness when agents are subject to delays. Note
that the swapping collision, where two agents swap their locations
simultaneously, is a special case of the second type of collision.

A MAPF solution can be represented in different formats. We stick to the
following format for our discussion, though our algorithms do not depend on
specific formats.

######  Definition 2 (MAPF Solution).

A MAPF solution takes the form of a set of collision-free paths
$\mathcal{P}=\\{p_{i}:i\in\mathcal{A}\\}$. Each path $p_{i}$ is a sequence of
location-timestep tuples
$(l^{i}_{0},t^{i}_{0})\to(l^{i}_{1},t^{i}_{1})\to\cdots\to(l^{i}_{zi},t^{i}_{zi})$
with the following properties: (1) The sequence follows a strict temporal
ordering: $0=t^{i}_{0}<t^{i}_{1}<\cdots<t^{i}_{zi}$. (2) $l^{i}_{0}$ and
$l^{i}_{zi}$ are the start and goal locations of agent $i$, respectively. (3)
Each tuple $(l^{i}_{k},t^{i}_{k})$ with $k>0$ specifies a move action of $i$
from $l^{i}_{k-1}$ to $l^{i}_{k}$ at timestep $t^{i}_{k}$.

These properties force all consecutive pairs of locations $l^{i}_{k}$ and
$l^{i}_{k+1}$ to be adjacent on the graph. A wait action is implicitly defined
between two consecutive tuples. Namely, if $t^{i}_{k+1}-t^{i}_{k}=\Delta>1$,
then $i$ is planned to wait at $l^{i}_{k}$ for $\Delta-1$ timesteps before
moving to $l^{i}_{k+1}$. Additionally, $t^{i}_{zi}$ records the time when $i$
reaches its goal location, called the _travel time_ of $i$. The cost of a MAPF
solution $\mathcal{P}$ is
$cost(\mathcal{P})=\sum_{i\in\mathcal{A}}t^{i}_{zi}$, and $\mathcal{P}$ is
_optimal_ if its cost is minimum.

######  Remark 2.

Definition 2 discards the explicit representation of wait actions. This is
because, when executing $\mathcal{P}$ as a TPG (specified in the next
section), it may reduce the travel time if $\mathcal{P}$ has unnecessary wait
actions, e.g., when $\mathcal{P}$ is suboptimal.

### Related Works

Numerous recent studies on MAPF have explored strategies for managing
unexpected delays during execution. A simple strategy is to re-solve the MAPF
problem when a delay occurs. However, this strategy is computationally
intensive, leading to prolonged agent waiting time. To avoid the need for
replanning, Atzmon et al. (2018) suggested the creation of a $k$-robust MAPF
solution, allowing agents to adhere to their planned paths even if each agent
is delayed by up to $k$ timesteps. However, replanning is still required if an
agent’s delay exceeds $k$ timesteps. Atzmon et al. (2020) then proposed a
different model, called $p$-robust MAPF solutions, that ensures execution
success with a probability of at least $p$, given an agent delay probability
model. Nevertheless, planning a $k$-robust or $p$-robust MAPF solution is
considerably more computational-intensive than computing a standard MAPF
solution. Another strategy for managing delays involves the use of an
execution policy that preserves the precedence relationships of a MAPF
solution during execution (Hönig et al. 2016; Ma, Kumar, and Koenig 2017;
Hönig et al. 2019). This strategy is quick and eliminates the need for
replanning paths. However, the execution results often leave room for
improvement, as many unnecessary waits are introduced. Our work aims to
address this limitation by formally exploring the concept of optimizing
precedence relationships online (Berndt et al. 2020; Mannucci, Pallottino, and
Pecora 2021).

## Temporal Plan Graph (TPG)

In essence, we aim to optimize the passing order for multiple agents to visit
the same location. This is achieved using a graph-based abstraction known as
the TPG.

######  Definition 3 (TPG).

A Temporal Plan Graph (TPG) (Hönig et al. 2016) is a directed graph
$\mathcal{G}=(\mathcal{V},\mathcal{E}_{1},\mathcal{E}_{2})$ that represents
the precedence relationships of a MAPF solution $\mathcal{P}$. The set of
vertices is $\mathcal{V}=\\{v^{i}_{k}:i\in\mathcal{A},k\in[0,zi]\\}$, where
each vertex $v^{i}_{k}$ corresponds to $(l_{k}^{i},t_{k}^{i})$, namely the
$k^{\text{th}}$ move action in path $p_{i}$. There are two types of edges
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, where each directed edge
$(u,v)\in\mathcal{E}_{1}\cup\mathcal{E}_{2}$ encodes a precedence relationship
between a pair of move actions, namely movement $u$ is planned to happen
_before_ movement $v$.

  * •

A _Type 1 edge_ connects two vertices of the same agent, specifying its path.
Specifically, $\mathcal{E}_{1}=\\{(v_{k}^{i},v_{k+1}^{i}):\forall
i\in\mathcal{A},k\in[0,zi)\\}$.

  * •

A _Type 2 edge_ connects two vertices of distinct agents, specifying their
ordering of visiting the same location. Specifically,
$\mathcal{E}_{2}=\\{(v_{s+1}^{j},v_{k}^{i}):\forall i\neq
j\in\mathcal{A},s\in[0,zj),k\in[0,zi]\text{ satisfying
}l_{s}^{j}=l_{k}^{i}\text{ and }t_{s+1}^{j}<t_{k}^{i}\\}$.

Figure 1: Example of converting a MAPF solution to a TPG. The solid arrows in
the TPG represent Type 1 edges, and the dashed arrow represents a Type 2 edge.

######  Example 1.

Figure 1 shows an example of converting a MAPF solution into a TPG. Both
agents are planned to visit location D, and the red agent is planned to visit
D earlier than the blue agent. Consequently, there is a Type 2 edge from
$v^{\text{red}}_{3}$ to $v^{\text{blue}}_{2}$, signifying that the blue agent
can move to D only after the red agent has reached F. Note that we define Type
2 edge as $(v^{\text{red}}_{3},v^{\text{blue}}_{2})$ instead of
$(v^{\text{red}}_{2},v^{\text{blue}}_{2})$ to avoid the second type of
collision in Definition 1.

3

4Define a counter $cost$;

5 Function  _Init ${}_{\textsc{exec}}$$(\mathcal{V})$_

6 $cost\leftarrow 0$;

7 Mark vertices in $\mathcal{V}_{0}=\\{v_{0}^{i}:i\in\mathcal{A}\\}$ as
satisfied;

8 Mark vertices in $(\mathcal{V}\setminus\mathcal{V}_{0})$ as unsatisfied;

9

10Function  _Step
${}_{\textsc{exec}}$$(\mathcal{G}=(\mathcal{V},\mathcal{E}_{1},\mathcal{E}_{2}))$_

$\mathcal{S}\leftarrow\emptyset$;

_//__Vertices to be marked as satisfied_

11 forall  _$i\in\mathcal{A}:v^{i}_{zi}$ unsatisfied_ do

12 $cost\leftarrow cost+1$;

13 $k\leftarrow\min\\{k:v^{i}_{k}\text{ unsatisfied}\\}$;

14 if  _$\forall(u,v_{k}^{i})\in\mathcal{E}_{2}:u$ satisfied_ then

15 Add $v^{i}_{k}$ into $\mathcal{S}$;

16

17

18

19 return $\mathcal{S}$;

20

21Function  _Exec
$(\mathcal{G}=(\mathcal{V},\mathcal{E}_{1},\mathcal{E}_{2}))$_

22 Init${}_{\textsc{EXEC}}$($\mathcal{V}$);

23 while  _$\exists v\in\mathcal{V}:v$ unsatisfied_ do

24 $S\leftarrow$ Step${}_{\textsc{exec}}$$(\mathcal{G})$;

25 forall  _$v^{i}_{k}\in\mathcal{S}$_ do Mark $v^{i}_{k}$ as satisfied;

26

27 return _$cost$_ ;

28

Codes highlighted in blue compute $cost(\mathcal{G})$ and can be omitted for
the mere purpose of execution.

Procedure 1 TPG Execution

Codes highlighted in blue compute $cost(\mathcal{G})$ and can be omitted for
the mere purpose of execution.

### Executing a TPG

Procedure 1 describes how to execute a TPG $\mathcal{G}$, which includes a
main function exec and two helper functions $\textsc{init}_{\textsc{exec}}$
and $\textsc{step}_{\textsc{exec}}$, along with two marks “satisfied” and
“unsatisfied” for vertices. Marking a vertex as satisfied corresponds to
moving an agent to the corresponding location, and we do so if and only if all
in-neighbors of this vertex have been satisfied. The execution terminates when
all vertices are satisfied, i.e., all agents have reached their goal
locations. The _cost_ of executing $\mathcal{G}$, namely
$cost(\mathcal{G})=\textsc{Exec}(\mathcal{G})$, is the sum of travel time for
agents following $\mathcal{G}$ (while assuming no delays happen).

We now introduce some known properties of TPGs. All proofs are delayed to the
appendix. We use $\mathcal{G}$ to denote a TPG constructed from a MAPF
solution $\mathcal{P}$ as in Definition 3.

######  Proposition 1 (Cost).

$cost(\mathcal{G})\leq cost(\mathcal{P})$.

Intuitively, $cost(\mathcal{G})<cost(\mathcal{P})$ if $\mathcal{P}$ has
unnecessary wait actions and $cost(\mathcal{G})=cost(\mathcal{P})$ otherwise.

######  Proposition 2 (Collision-Free).

Executing a TPG with Procedure 1 does not lead to collisions among agents.

Next, we present two lemmas regarding deadlocks of executing a TPG, which were
used in previous work (Berndt et al. 2020; Su, Veerapaneni, and Li 2024) and
are helpful for our discussion of switchable TPGs in the next section.

######  Definition 4 (Deadlock).

When executing a TPG, a _deadlock_ is encountered iff, in an iteration of the
while-loop of Exec($\mathcal{G}$), $\mathcal{V}$ contains unsatisfied vertices
but $\mathcal{S}=\emptyset$.

######  Lemma 3 (Deadlock $\iff$ Cycle).

Executing a TPG encounters a deadlock iff the TPG contains cycles.

######  Lemma 4 (Deadlock-Free).

If a TPG is constructed from a MAPF solution, then executing it is deadlock-
free.

## Switchable TPG (STPG)

TPG is a handy representation for precedence relationships. Yet, a TPG
constructed as in Definition 3 is fixed and bound to a given set of paths. In
contrast, our optimization algorithm will use the following extended notion of
TPGs, which enables flexible modifications of precedence relationships.

######  Definition 5 (STPG).

Given a TPG $\mathcal{G}=(\mathcal{V},\mathcal{E}_{1},\mathcal{E}_{2})$, a
_Switchable TPG_ (STPG)
$\mathcal{G^{S}}=(\mathcal{V},\mathcal{E}_{1},(\mathcal{S}_{\mathcal{E}2},\mathcal{N}_{\mathcal{E}2}))$
partitions Type 2 edges $\mathcal{E}_{2}$ into two disjoint subsets
$\mathcal{S}_{\mathcal{E}2}$ (switchable edges) and
$\mathcal{N}_{\mathcal{E}2}$ (non-switchable edges) and allows two operations
on any switchable edge $(v_{s+1}^{j},v_{k}^{i})\in\mathcal{S}_{\mathcal{E}2}$:

  * •

$fix(v_{s+1}^{j},v_{k}^{i})$ removes $(v_{s+1}^{j},v_{k}^{i})$ from
$\mathcal{S}_{\mathcal{E}2}$ and add it into $\mathcal{N}_{\mathcal{E}2}$. It
fixes a switchable edge to be non-switchable.

  * •

$reverse(v_{s+1}^{j},v_{k}^{i})$ removes $(v_{s+1}^{j},v_{k}^{i})$ from
$\mathcal{S}_{\mathcal{E}2}$ and add $(v_{k+1}^{i},v_{s}^{j})$ into
$\mathcal{N}_{\mathcal{E}2}$. It switches the precedence relationship and then
fixes it to be non-switchable.

######  Remark 3.

Reversing the precedence relationship represented by $(v_{s+1}^{j},v_{k}^{i})$
produces $(v_{k+1}^{i},v_{s}^{j})$ because, based on Definition 3, Type 2 edge
$(v_{s+1}^{j},v_{k}^{i})$ indicates locations $l^{j}_{s}$ and $l^{i}_{k}$ are
the same. Thus, after reversing, vertex $v^{i}_{k+1}$ needs to be satisfied
before $v_{s}^{j}$ can be marked as satisfied.

######  Example 2.

Figure 2 shows an example of reversing an edge. After the $reverse$ operation,
edge $(v^{\text{red}}_{1},v^{\text{blue}}_{2})$ in the left TPG is replaced
with edge $(v^{\text{blue}}_{3},v^{\text{red}}_{0})$ in the right TPG.

Figure 2: Example of reversing an edge in a TPG.

Definition 5 defines a strict superclass of Definition 3. A STPG degenerates
into a TPG if $\mathcal{S}_{\mathcal{E}2}$ is empty.

######  Definition 6 ($\mathcal{G^{S}}$-producible TPG).

Given a STPG $\mathcal{G^{S}}$, a TPG is $\mathcal{G^{S}}$-producible if it
can be generated through a sequence of $fix$ and $reverse$ operations on
$\mathcal{G^{S}}$.

We now show the roadmap of our algorithm. Given a MAPF solution $\mathcal{P}$,
we construct TPG $\mathcal{G}_{0}$ from $\mathcal{P}$ as in Definition 3 and
then run Procedure 1. When a delay happens, we (1) construct a STPG
$\mathcal{G^{S}}$ based on $\mathcal{G}_{0}$ and (2) finds a TPG
$\mathcal{G}^{*}$ with
$cost(\mathcal{G}^{*})=\min\\{cost(\mathcal{G}):\mathcal{G}$ is
$\mathcal{G^{S}}$-producible$\\}$, representing an optimal ordering of agents
visiting each location, upon sticking to the original location-wise paths. We
describe Step (1) below and Step (2) in the next section.

######  Construction 1.

Assume that, during the execution of
$\mathcal{G}_{0}=(\mathcal{V},\mathcal{E}_{1},\mathcal{E}_{2})$, agent $d$ is
forced to delay at its current location $l_{c}^{d}$ for $\Delta$ timesteps. We
construct STPG $\mathcal{G^{S}}$ as follows:

  1. 1.

Construct STPG
$\mathcal{G^{S}}=(\mathcal{V},\mathcal{E}_{1},(\mathcal{S}_{\mathcal{E}2},\mathcal{N}_{\mathcal{E}2}))$
with
$\mathcal{S}_{\mathcal{E}2}=\\{(v_{s+1}^{j},v_{k}^{i})\in\mathcal{E}_{2}:$
$v_{s+1}^{j}$ is unsatisfied and $k<zi\\}$ and
$\mathcal{N}_{\mathcal{E}2}=\\{(v_{s+1}^{j},v_{k}^{i})\in\mathcal{E}_{2}:$
$v_{s+1}^{j}$ is satisfied or $k=zi\\}$.

  2. 2.

Create $\Delta$ new dummy vertices
$\mathcal{V}_{\text{new}}=\\{v_{1},\cdots,v_{\Delta}\\}$ and $(\Delta+1)$ new
Type-1 edges $\mathcal{E}_{\text{new}}=\\{(v^{d}_{c},v_{1}),$
$(v_{1},v_{2}),\cdots,(v_{\Delta-1},v_{\Delta}),(v_{\Delta},v^{d}_{c+1})\\}$
and modify $\mathcal{G^{S}}$ with
$\mathcal{V}\leftarrow\mathcal{V}\cup\mathcal{V}_{\text{new}}$ and
$\mathcal{E}_{1}\leftarrow(\mathcal{E}_{1}\cup\mathcal{E}_{\text{new}})\setminus\\{(v^{d}_{c},v^{c}_{c+1})\\}$.

If there are multiple agents delayed at the same timestep, we repeat Step 2
for each delayed agent.

######  Remark 4.

In Step 1, $(v_{s+1}^{j},v_{k}^{i})$ is non-switchable when $v_{s+1}^{j}$ is
satisfied because agent $j$ has already visited $l_{s}^{j}$.
$(v_{s+1}^{j},v_{zi}^{i})$ is non-switchable because agent $i$ must be the
last one to visit its goal location. The dummy vertices added in Step 2 are
used to account for the delays in Procedure 1.

We now show an intuitive yet crucial theorem.

######  Theorem 5.

If STPG $\mathcal{G^{S}}$ is constructed by Construction 1, then there is at
least one deadlock-free $\mathcal{G^{S}}$-producible TPG.

###### Proof.

We generate a naïve solution $\mathcal{G}_{\text{naive}}$ by $fix$ing all
switchable edges in $\mathcal{G^{S}}$. Lemma 4 ensures that $\mathcal{G}_{0}$
is deadlock-free. $\mathcal{G^{S}}$ constructed in Step 1 is identical to
$\mathcal{G}_{0}$ if we $fix$ all switchable edges. Step 2 behaves as
expanding a pre-existing edge $(v^{i}_{k-1},v^{i}_{k})$ into a line of
connecting edges, which does not create any new cycles. Therefore, by Lemma 3,
$\mathcal{G}_{\text{naive}}$ is deadlock-free. ∎

## Switchable Edge Search (SES) Framework

3

Input: STPG $\mathcal{G}^{\mathcal{S}}_{\text{root}}$

Output: TPG $\mathcal{G}$

4

5$(h_{\text{root}},\mathcal{X}_{init})\leftarrow\textsc{heuristic}(\mathcal{G}^{\mathcal{S}}_{\text{root}},\mathcal{X}_{init})$;

6

$\mathcal{Q}\leftarrow\\{(\mathcal{G}^{\mathcal{S}}_{\text{root}},\mathcal{X}_{init},0,h_{\text{root}})\\}$;

_//__A priority queue_

7

8while  _$\mathcal{Q}$ is not empty_ do

9 $(\mathcal{G}^{\mathcal{S}},\mathcal{X},g,h)\leftarrow\mathcal{Q}.pop()$;

10

11
$(\mathcal{X}^{\prime},g_{\Delta},(v_{k+1}^{i},v_{s}^{j}))\leftarrow\textsc{Branch}(\mathcal{G}^{\mathcal{S}},\mathcal{X})$;

12

13 if  _$(v_{k+1}^{i},v_{s}^{j})=\textsc{Null}$_ then return
$\mathcal{G}^{\mathcal{S}}$;

14

15 $\mathcal{G}^{\mathcal{S}}_{\text{f}}\leftarrow
fix(\mathcal{G}^{\mathcal{S}},(v_{k+1}^{i},v_{s}^{j}))$;

16

17 if  _not CycleDetection($\mathcal{G}^{\mathcal{S}}_{\text{f}}$,
$(v_{k+1}^{i},v_{s}^{j})$)_ then

18
$(h_{f},\mathcal{X}_{f})\leftarrow\textsc{Heuristic}(\mathcal{G}^{\mathcal{S}}_{\text{f}},\mathcal{X}^{\prime})$;

19
$\mathcal{Q}.push((\mathcal{G}^{\mathcal{S}}_{\text{f}},\mathcal{X}_{f},g+g_{\Delta},h_{f}))$;

20

21

22 $\mathcal{G}^{\mathcal{S}}_{\text{r}}\leftarrow
reverse(\mathcal{G}^{\mathcal{S}},(v_{k+1}^{i},v_{s}^{j}))$;

23

24 if  _not CycleDetection($\mathcal{G}^{\mathcal{S}}_{\text{r}}$,
$(v_{s+1}^{j},v_{k}^{i})$)_ then

25
$(h_{r},\mathcal{X}_{r})\leftarrow\textsc{Heuristic}(\mathcal{G}^{\mathcal{S}}_{\text{r}},\mathcal{X}^{\prime})$;

26
$\mathcal{Q}.push((\mathcal{G}^{\mathcal{S}}_{\text{r}},\mathcal{X}_{r},g+g_{\Delta},h_{r}))$;

27

28

29

30throw exception “No solution found”;

31

32Function  _CycleDetection $(\mathcal{G}^{\mathcal{S}},(u,v))$_

33 Run depth-first search (DFS) from $v$ on $red(\mathcal{G}^{\mathcal{S}})$;

34 if  _DFS visits vertex $u$_ then return true;

35 return false;

36

37

Heuristic and Branch are modules to be specified later. $\mathcal{X}$ stores
auxiliary information accompanying a STPG and will be specified later.

Algorithm 2 Switchable Edge Search (SES)

Heuristic and Branch are modules to be specified later. $\mathcal{X}$ stores
auxiliary information accompanying a STPG and will be specified later.

We describe our algorithm, _Switchable Edge Search_ (SES), in a top-down
modular manner, starting with a high-level heuristic search framework in
Algorithm 2. We define the _partial cost_ of a STPG as the cost of its
_reduced_ TPG, which is defined as follows.

######  Definition 7 (Reduced TPG).

The reduced TPG of a STPG
$\mathcal{G^{S}}=(\mathcal{V},\mathcal{E}_{1},(\mathcal{S}_{\mathcal{E}2},\mathcal{N}_{\mathcal{E}2}))$
is the TPG that omits all switchable edges, denoted as
$red(\mathcal{G^{S}})=(\mathcal{V},\mathcal{E}_{1},\mathcal{N}_{\mathcal{E}2})$.

######  Lemma 6.

The partial cost of a STPG $\mathcal{G^{S}}$ is no greater than the cost of
any $\mathcal{G^{S}}$-producible TPG.

###### Proof.

Let $\mathcal{G}$ be a $\mathcal{G}^{\mathcal{S}}$-producible TPG. Consider
running Procedure 1 on $\mathcal{G}$ and $red(\mathcal{G^{S}})$, respectively.
Since an edge appears in $red(\mathcal{G^{S}})$ must appear in $\mathcal{G}$,
we can inductively show that, in any call to $\textsc{step}_{\textsc{exec}}$,
if a vertex $v$ can be marked as satisfied in $\mathcal{G}$, then it can be
marked as satisfied in $red(\mathcal{G^{S}})$. Thus, the total timesteps to
satisfy all vertices in $red(\mathcal{G^{S}})$ cannot exceed that in
$\mathcal{G}$. ∎

As shown in Algorithm 2, SES runs A* in the space of STPGs with a root node
corresponding to the STPG $\mathcal{G}^{\mathcal{S}}_{\text{root}}$
constructed as in Construction 1. The priority queue $\mathcal{Q}$ sorts its
nodes by their $f$-values (namely $g+h$). The $f$-value of a node is defined
as the partial cost of its STPG. When expanding a node, SES selects one
switchable edge in the STPG by module Branch and generates two child nodes
with the selected edge being $fix$ed or $reverse$d. We abuse the operators
$fix$ and $reverse$ on Algorithms 2 and 2 to take a STPG and a switchable edge
as input and return a new STPG.

SES uses function CycleDetection to prune child nodes with STPGs that
definitely produce cyclic TPGs, namely STPGs whose reduced TPGs are cyclic.
Specifically, CycleDetection($\mathcal{G}^{\mathcal{S}}$, $(u,v))$ returns
true iff $red(\mathcal{G}^{\mathcal{S}})$ contains a cycle involving edge
$(u,v)$. As $\mathcal{G}^{\mathcal{S}}_{\text{root}}$ is acyclic, it holds
inductively that CycleDetection($\mathcal{G}$, $(u,v))$ returns true iff
$red(\mathcal{G}^{\mathcal{S}})$ contains _any_ cycle. This is because, when
we generate a node, we add only one new non-switchable edge, so any cycle
formed must contain the new edge.

######  Assumption 1.

The modules in SES satisfy:

  1. A1

Branch$(\mathcal{G}^{\mathcal{S}},\mathcal{X})$ outputs an updated auxiliary
information $\mathcal{X}^{\prime}$, a value $g_{\Delta}$, and a switcable edge
of $\mathcal{G}^{\mathcal{S}}$ if exists or Null otherwise.

  2. A2

Heuristic$(\mathcal{G}^{\mathcal{S}},\mathcal{X})$ computes a value $h$ such
that $g+h$ is the partial cost of $\mathcal{G}^{\mathcal{S}}$ for every node
$(\mathcal{G}^{\mathcal{S}},\mathcal{X},g,h)\in\mathcal{Q}$.

######  Theorem 7 (Completeness and Optimality).

Under Assumption 1, SES always finds a deadlock-free TPG $\mathcal{G}$ with
$cost(\mathcal{G})=\min\\{cost(\mathcal{G}):\mathcal{G}$ is
$\mathcal{G}^{\mathcal{S}}_{\text{root}}$-producible$\\}$.

###### Proof.

First, SES always terminates within a finite time because there are only
finitely many possible operation sequences from
$\mathcal{G}^{\mathcal{S}}_{\text{root}}$ to any TPG, each corresponding to a
node that can possibly be added to $\mathcal{Q}$. Second, Theorem 5 ensures
that there always exist solutions for SES since
$\mathcal{G}^{\mathcal{S}}_{\text{root}}$ is constructed as in Construction 1.
Therefore, to prove the completeness of SES, we just need to prove the
following claim: At the beginning of each while-loop iteration, for any
deadlock-free $\mathcal{G}^{\mathcal{S}}_{\text{root}}$-producible TPG
$\mathcal{G}$, there exists $\mathcal{G}^{\mathcal{S}}\in\mathcal{Q}$ such
that $\mathcal{G}$ is $\mathcal{G}^{\mathcal{S}}$-producible. Here, we abuse
the notation $\mathcal{G}^{\mathcal{S}}\in\mathcal{Q}$ to denote a node in
$\mathcal{Q}$ with STPG $\mathcal{G}^{\mathcal{S}}$. This claim holds
inductively: At the first iteration,
$\mathcal{G}^{\mathcal{S}}_{\text{root}}\in\mathcal{Q}$. During any iteration,
if some $\mathcal{G}^{\mathcal{S}}\in\mathcal{Q}$ such that $\mathcal{G}$ is
$\mathcal{G}^{\mathcal{S}}$-producible is popped on Algorithm 2, then one of
the following must hold:

  * •

$\mathcal{G}^{\mathcal{S}}$ contains no switchable edge, i.e.,
$\mathcal{G}^{\mathcal{S}}=\mathcal{G}$: SES terminates, and the inductive
step holds vacuously.

  * •

$\mathcal{G}$ is $\mathcal{G}^{\mathcal{S}}_{f}$-producible: Since
$\mathcal{G}$ is acyclic, so is $red(\mathcal{G}^{\mathcal{S}}_{f})$. Thus,
$\mathcal{G}^{\mathcal{S}}_{f}$ is added into $\mathcal{Q}$.

  * •

$\mathcal{G}$ is $\mathcal{G}^{\mathcal{S}}_{r}$-producible: This is symmetric
to the above case.

In any case, the claim remains true after this iteration. Therefore, SES
always outputs a solution within a finite time.

Finally, we prove that the output TPG $\mathcal{G}$ has the minimum cost.
Assume towards contradiction that when $\mathcal{G}$ is returned, there exists
$\mathcal{G}^{\mathcal{S}}_{0}\in\mathcal{Q}$ that can produce a better TPG
$\mathcal{G}_{\text{better}}$ with
$cost(\mathcal{G}_{\text{better}})<cost(\mathcal{G})$. Yet this is impossible
since Lemma 6 implies that such $\mathcal{G}^{\mathcal{S}}_{0}$ must have a
smaller $g+h$ value and thus would be popped from $\mathcal{Q}$ before
$\mathcal{G}$. ∎

Figure 3: Example of running ESES on the top-left STPG. The circled numbers
denote the order of generating these STPGs.

1 Auxillary information $\mathcal{X}$ is a map
$\mathcal{X}:\mathcal{A}\to[0:zi]$, where $\mathcal{X}[i]$ records the index
of the most recently satisfied vertex for agent $i$;

2

3$\mathcal{X}_{\text{init}}$ on Algorithm 2 of Algorithm 2 maps all agents to
$0$;

4$\textsc{Init}_{\textsc{exec}}$ in Procedure 1 is modified by setting
$\mathcal{V}_{0}$ to $\\{v^{i}_{k}:i\in\mathcal{A},k\leq\mathcal{X}[i]\\}$
instead of $\\{v_{0}^{i}:i\in\mathcal{A}\\}$;

5

6Function  _Branch
$(\mathcal{G^{S}}=(\mathcal{V},\mathcal{E}_{1},(\mathcal{S}_{\mathcal{E}2},\mathcal{N}_{\mathcal{E}2})),\mathcal{X})$_

7 Init${}_{\textsc{EXEC}}$($\mathcal{V},\mathcal{X}$);

8 $\mathcal{X}^{\prime}\leftarrow\mathcal{X}$;

9 while  _$\exists v\in\mathcal{V}:v$ unsatisfied_ do

10 forall  _$i\in\mathcal{A}:\mathcal{X}^{\prime}[i] <zi$_ do

$v\leftarrow v^{i}_{\mathcal{X}^{\prime}[i]+1}$;

_//__First unsatisfied vertex_

11 if  _$\exists e\in\mathcal{S}_{\mathcal{E}2}$ with $e=(v,u)$ or $(u,v)$_
then

12 return $(\mathcal{X}^{\prime},cost,e)$;

13

14

15 $\mathcal{S}\leftarrow$ Step${}_{\textsc{exec}}$$(red(\mathcal{G^{S}}))$;

16 forall  _$v^{i}_{k}\in\mathcal{S}$_ do

17 Mark $v^{i}_{k}$ as satisfied;

18 $\mathcal{X}^{\prime}[i]\leftarrow k$;

19

20

21 return $(\mathcal{X}^{\prime},cost,\textsc{Null})$;

22

23Function  _Heuristic $(\mathcal{G^{S}},\mathcal{X})$_

24 return $(\textsc{Exec}(red(\mathcal{G^{S}})),\mathcal{X})$;

25

Module 3 Execution-based Modules for ESES

## Execution-based Modules

In this and the next sections, we describe two sets of modules and prove that
they satisfy Assumption 1. We start with describing a set of “execution-based”
modules in Module 3 and refer to it as _Execution-based SES_ (ESES).

In essence, ESES simulates the execution of the STPG and branches when
encountering a switchable edge. It uses $\mathcal{X}$ to record the index of
the most recently satisfied vertex for every agent, indicating their current
locations. $\mathcal{X}$ is updated by the Branch module, which largely
ensembles Exec in Procedure 1. At the beginning of each while-loop iteration
of Branch, ESES first checks whether the next vertex of any agent is involved
in a switchable edge and, if so, returns that edge together with the updated
$\mathcal{X}^{\prime}$ and the cost of moving agents from the old
$\mathcal{X}$ to the new $\mathcal{X}^{\prime}$ [Algorithms 3 to 3], where the
cost is updated inside function Step${}_{\textsc{exec}}$. If no such edge is
found, it runs Step${}_{\textsc{exec}}$ on the reduced TPG to move agents
forward by one timestep and repeat the process.

######  Example 3.

Figure 3 shows an example of ESES.111We note that Figure 3 also works as an
example for the GSES implementation in the following section. The only
difference is that GSES does not use the notion of “(un)satisfied vertex” or
$\textsc{step}_{\textsc{exec}}$. We start with the top-left STPG ① containing
two switchable edges. ESES looks at a “horizon” containing the first
unsatisfied vertices $v^{i}_{1}$ and $v^{j}_{1}$, and then picks the adjacent
switchable edge $(v^{i}_{3},v^{j}_{1})$ to branch on. This leads to two copies
of STPGs ② and ③, containing non-switchable edge $(v^{i}_{3},v^{j}_{1})$ or
$(v^{j}_{2},v^{i}_{2})$, respectively. ESES expands on STPG ③ first as it has
a smaller $g+h$ value. The next switchable edge it encounters is
$(v^{j}_{3},v^{i}_{2})$. ESES first $fix$es it and generates TPG ④ with
$cost=10$, which is the optimal solution. When ESES $reverse$s the edge, the
resulting TPG ⑤ is pruned as it contains a cycle. Note that STPG ② will not be
expanded since it has a partial cost greater than the cost of TPG ④.

######  Proposition 8.

Module 3 satisfies Assumption 1.

###### Proof.

Assumption A1 holds by design. To prove Assumption A2, we first prove the
following claim by induction: for every node
$(\mathcal{G^{S}},\mathcal{X},g,h)\in\mathcal{Q}$, $g$ is the cost of moving
agents from their start locations to $\mathcal{X}$. This holds for the root
node with $g=0$ and $\mathcal{X}[i]=0,\forall i\in\mathcal{A}$. When we expand
a node $(\mathcal{G},\mathcal{X},g,h)\in\mathcal{Q}$, $g_{\Delta}$ returned by
Branch is the cost of moving agents from $\mathcal{X}$ to
$\mathcal{X}^{\prime}$. Thus, on Algorithms 2 and 2 of Algorithm 2, the $g$
value of the child nodes are $g+g^{\prime}$, which is the cost of moving
agents from their start locations to $\mathcal{X}^{\prime}$
($=\mathcal{X}_{f}=\mathcal{X}_{r}$). So our claim holds. Module heuristic
runs function Exec to compute the cost of moving agents from
$\mathcal{X}^{\prime}$ to their goal locations on the reduced TPG, making
$g+h$ the partial cost of $\mathcal{G^{S}}$ for every node
$(\mathcal{G^{S}},\mathcal{X},g,h)\in\mathcal{Q}$. ∎

## Graph-based Modules

We now introduce an alternative set of modules that focus on the graph
properties of a TPG. We refer to this implementation as _Graph-based SES_
(GSES). We will see later in our experiment that this shift of focus
significantly improves the efficiency of SES. We start by presenting the
following crucial theorem that provides a graph-based approach to computing
the cost of a TPG.

Given a TPG $\mathcal{G}$ and a vertex $v\in\mathcal{V}$, let $lp(v)$ denote
the longest path among the longest paths from every vertex
$v^{i}_{0},i\in\mathcal{A}$ to vertex $v$ on $\mathcal{G}$ and $|lp(v)|$
denote its length.

######  Theorem 9.

When we execute a TPG, every vertex $v$ is marked as satisfied in the
$|lp(v)|^{\text{th}}$ iteration of the while-loop of Exec in Procedure 1.

###### Proof.

We induct on iteration $t$ and prove that all vertices $v$ with $|lp(v)|=t$
are marked as satisfied in the $t^{\text{th}}$ iteration. In the base case,
$\\{v^{i}_{0},i\in\mathcal{A}\\}$ are the vertices with $|lp(v)|=0$ and are
marked as satisfied in the $0^{\text{th}}$ iteration. In the inductive step,
we assume that, by the end of the $(t-1)^{\text{th}}$ iteration, all vertices
$v$ with $|lp(v)|<t$ are satisfied, and all vertices $v$ with $|lp(v)|\geq t$
are unsatisfied. Then, in the ${t}^{\text{th}}$ iteration, every vertex $v$
with $|lp(v)|=t$ is marked as satisfied because all of its in-neighbors
$v^{\prime}$ have $|lp(v^{\prime})|<|lp(v)|=t$ and are thus satisfied. For
every vertex $v$ with $|lp(v)|>t$, the vertex right before $v$ on $lp(v)$,
denoted as $v^{\prime}$, has $|lp(v^{\prime})|=|lp(v)|-1\geq t$ and is thus
unsatisfied on Algorithm 1. Thus, every vertex $v$ with $|lp(v)|>t$ has at
least one in-neighbor unsatisfied and thus remains unsatisfied. Therefore, the
theorem holds. ∎

Hence, the last vertex $v_{zi}^{i}$ of every agent $i\in\mathcal{A}$ is marked
as satisfied in the $|lp(v_{zi}^{i})|^{\text{th}}$ iteration, namely the
travel time of agent $i$ is $|lp(v_{zi}^{i})|$. We thus get the following
corollary.

######  Corollary 10.

Given a TPG $\mathcal{G}$,
$cost(\mathcal{G})=\sum_{i\in\mathcal{A}}|lp(v_{zi}^{i})|$.

An interesting observation is that, if $lp(u)<lp(v)$ for a given TPG
$\mathcal{G}$, then adding edge $(u,v)$ to $\mathcal{G}$ does not change its
cost since adding $(u,v)$ does not change any longest paths. We thus get the
following corollary that is useful later.

######  Corollary 11.

Given a STPG $\mathcal{G^{S}}$, we compute $lp(v)$ on $red(\mathcal{G^{S}})$.
For any switchable edge with $lp(u)<lp(v)$, $fix$ing it does not change the
partial cost of $\mathcal{G^{S}}$.

We adopt the following well-known algorithm to compute $lp(v)$ on a given
deadlock-free TPG $\mathcal{G}=(\mathcal{V},\mathcal{E}_{1},\mathcal{E}_{2})$:
(1) Set $lp(v)=0,\forall v\in\mathcal{V}$. (2) Compute a topological sort of
all vertices in $\mathcal{V}$. (3) For each vertex $v$ in the topological
order, we set $lp(u)=\max\\{lp(u),lp(v)+1\\}$ for every out-neighbor $u$
(namely $(v,u)\in\mathcal{E}_{1}\cup\mathcal{E}_{2}$). The time complexity of
this longest-path algorithm is
$\mathcal{O}(\lvert\mathcal{V}\rvert+\lvert\mathcal{E}_{1}\cup\mathcal{E}_{2}\rvert)$.

1

2Auxillary information $\mathcal{X}$ is a map
$\mathcal{X}:\mathcal{V}\to[0,\lvert\mathcal{V}\rvert)$, which records $lp(v)$
for every vertex $v$;

3

4$\mathcal{X}_{\text{init}}$ on Algorithm 2 of Algorithm 2 is empty;

5

6Function  _Branch
$(\mathcal{G^{S}}=(\mathcal{V},\mathcal{E}_{1},(\mathcal{S}_{\mathcal{E}2},\mathcal{N}_{\mathcal{E}2})),\mathcal{X})$_

7 if
_$\exists(u,v)\in\mathcal{S}_{\mathcal{E}2}:\mathcal{X}[u]\geq\mathcal{X}[v]$_
then

8 return ($\mathcal{X},0,(u,v))$;

9

10 $fix$ all swtichable edges in $\mathcal{G^{S}}$;

11 return ($\mathcal{X}$, 0, Null);

12

13

14Function  _Heuristic $(\mathcal{G^{S}},\mathcal{X})$_

15 $\mathcal{X}^{\prime}\leftarrow$ $lp$-values of all vertices in
$\mathcal{V}$ on $red(\mathcal{G^{S}})$;

16

17 return
$(\sum_{i\in\mathcal{A}}\mathcal{X}[v^{i}_{zi}],\mathcal{X}^{\prime})$;

18

Module 4 Graph-based Modules for GSES

With this algorithm, we specify the graph-based modules in Module 4. In GSES,
$\mathcal{X}$ records $lp(v)$ for every vertex $v\in\mathcal{V}$ and is
updated by the Heuristic module. Since, with $\mathcal{X}$, Heuristic can
directly compute the partial cost of a given STPG, GSES does not use any $g$
values. The Branch module chooses a switchable edge $(u,v)$ with
$\mathcal{X}[u]\geq\mathcal{X}[v]$ to branch on. If no such edge exists, then,
by Corollary 11, $fix$ing all switchable edges produces a TPG with the same
cost as the current partial cost. Thus, GSES $fix$ all such edges and
terminates in this case.

######  Proposition 12.

Module 4 satisfies Assumption 1.

###### Proof.

Assumption A1 holds by design. Assumption A2 holds because of Corollary 10. ∎

Figure 4: Runtime of ESES, GSES, and k-robust CBS. The dashed lines represent
the mean of runtime, and the shaded areas denote the 0.4 to 0.6 quantile
range. For trials that exceed the $90$-second time limit, we count it as $90$
seconds.

######  Remark 5.

ESES terminates when all vertices are satisfied, which is possible only when
all Type 2 edges are non-switchable. This means that ESES has to expand on all
switchable edges before getting a solution. In contrast, GSES can have an
_early termination_ when $fix$ing all switchable edges does not change any
longest paths.

Figure 5: Numbers of nodes explored and pruned by ESES and GSES on the
warehouse map. Dashed lines represent the mean values. Shaded area between two
lines for the same algorithm indicates the portion of pruned nodes. Figure 6:
Mean costs (from the locations where the delays happened to the goal
locations) of the non-replanned, GSES-replanned, and K-Robust-CBS-replanned
solutions. The means are taken across all trials for all different numbers of
agents.

## Experiment

We use $4$ maps from the MAPF benchmark suite (Stern et al. 2019), shown in
Figure 4, with 6 agent group sizes per map. Regarding each map and group size
configuration, we run the algorithms on 25 different, evenly distributed
scenarios (start/goal locations) with 6 trials per scenario. We set a runtime
limit of 90 seconds for each trial. In each trial, we execute the TPG
constructed from an optimal MAPF solution planned by a k-Robust MAPF solver
k-Robust CBS (Chen et al. 2021) with $k=1$. At each timestep of the execution,
each agent that has not reached its goal location is subject to a constant
probability $p$ of delay. When a delay happens, we draw a delay length
$\Delta$ uniformly random from a range $[10,20]$, construct a STPG as in
Construction 1, and run our replanning algorithms. We also develop a baseline
that uses k-Robust CBS to find the new optimal solution (that takes into
account the delay length $\Delta$) when the delay happens.

We implement all algorithms in C++222Our SES code is available at
https://github.com/YinggggFeng/Switchable-Edge-Search. The modified k-Robust
CBS code that considers delays is available at
https://github.com/nobodyczcz/Lazy-Train-and-K-CBS/tree/wait-on-start. and run
experiments on a server with a 64-core AMD Ryzen Threadripper 3990X and 192 GB
of RAM.

### Efficiency

Figure 4 compares the runtime of ESES and GSES with replanning using k-Robust
CBS. In all cases, GSES runs the fastest. Most remarkably, on the random and
warehouse maps, the runtime of GSES is consistently below 1 second and does
not increase significantly when the number of agents increases, suggesting the
potential of GSES for real-time replanning applications.

### Comparing ESES and GSES

We observe from Figure 4 that, although ESES and GSES adopt the same
framework, GSES runs significantly faster than ESES. This is because the
longest paths used in GSES defines a simple but extremely powerful early
termination condition (see Remark 5), which enables GSES to find an optimal
solution after a very small number of node expansions. Figure 5 compares the
number of search nodes of ESES and GSES, where _explored nodes_ are nodes
popped from the priority queue, and _pruned nodes_ are nodes pruned by
CycleDetection. The gap between the red and grey lines (and the gap between
the purple and blue lines) indicates the effectiveness of cycle detection for
pruning unnecessary search nodes. The gap between the grey and blue lines
indicates the effectiveness of early termination as described in Remark 5.

### Improvement of Solution Cost

Figure 6 measures the cost of our replanned solution, in comparison to the
non-replanned solution produced by the original TPG and the replanned solution
produced by k-Robust CBS. We stress that our solution is guaranteed to be
optimal, as proven in previous sections, upon sticking to the original
location-wise paths, while k-Robust CBS finds an optimal solution that is
independent of the original paths. Therefore, the two algorithms solve
intrinsically different problems, and the results here serve primarily for a
quantitative understanding of how much improvement we can get by changing only
the passing orders of agents at different locations. Figure 6 shows that the
cost improvement depends heavily on the maps. For example, our solutions have
costs similar to the globally optimal solutions on the random map, while the
difference is larger on the Lak303d map.

## Conclusion

We proposed Switchable Edge Search to find the optimal passing orders for
agents that are planned to visit the same location. We developed two
implementations based on either execution (ESES) or graph (GESE)
presentations. On the random and warehouse maps, the average runtime of GSES
is faster than 1 second for various numbers of agents. On harder maps (Paris
and game maps), it also runs faster than replanning with a k-Robust CBS
algorithm.

##  Appendix A Appendix: Proofs for Section 3

We rely on the following lemma to prove Proposition 1.

######  Lemma A.

For every tuple $(l_{k}^{i},t^{i}_{k})$ in every path $p_{i}\in\mathcal{P}$,
the corresponding vertex $v^{i}_{k}$ in $\mathcal{G}$ is satisfied after the
$(t^{i}_{k})^{\text{th}}$ iteration of the while-loop of Exec in Procedure 1.

###### Proof.

We induct on the while-loop iteration $t$ and prove that any vertex
$v^{i}_{k}$ with $t^{i}_{k}\leq t$ is satisfied after iteration $t$. When
$t=0$, this holds because of $\textsc{init}_{\textsc{exec}}$. Assume that all
vertices $v^{i}_{k}$ with $t^{i}_{k}\leq t-1$ are satisfied after iteration
$t-1$. At iteration $t$, for Type 1 edge $(v^{i}_{k-1},v^{i}_{k})$,
$v^{i}_{k-1}$ is satisfied as $t^{i}_{k-1}<t^{i}_{k}\leq t$. For any Type 2
edge $(v^{j}_{s},v^{i}_{k})$, $v^{j}_{s}$ is also satisfied as
$t^{j}_{s}<t^{i}_{k}\leq t$ by Definition 3. This shows that all in-neighbors
of $v^{i}_{k}$ are satisfied after iteration $t-1$, thus $v^{i}_{k}$ is
satisfied after iteration $t$. ∎

######  Proposition 1 (Cost).

$cost(\mathcal{G})\leq cost(\mathcal{P})$.

###### Proof.

Lemma A implies that the last vertex $v_{zi}^{i}$ of every agent $i$ is
satisfied after the $(t^{i}_{zi})^{\text{th}}$ iteration, i.e., when executing
$\mathcal{G}$, the travel time of every agent $i$ is no greater than
$t^{i}_{zi}$. Thus, the proposition holds. ∎

Proposition 2 is similar to Lemma 4 in (Hönig et al. 2016) with different
terms. We include a proof for completeness.

######  Proposition 2 (Collision-Free).

Executing a TPG does not lead to collisions among agents.

###### Proof.

According to Procedure 1, we need to show that, when a vertex $v_{k}^{i}$ is
marked as satisfied [Algorithm 1], moving agent $i$ to its $k^{th}$ location
$l^{i}_{k}$ does not lead to collisions. Assume towards contradiction that
agent $i$ indeed collides with another agent $j$ at timestep $t$. Let
$v^{i}_{k}$ and $v^{j}_{s}$ be the latest satisfied vertices for agents $i$
and $j$, respectively, after the $t^{th}$ iteration of the while-loop. If $i$
and $j$ collide because they are at the same location, then
$l^{i}_{k}=l^{j}_{s}$, indicating that either edge $(v^{i}_{k+1},v^{j}_{s})$
or edge $(v^{j}_{s+1},v^{i}_{k})$ is in $\mathcal{E}_{2}$. But this is
impossible as neither $v^{i}_{k+1}$ nor $v^{j}_{s+1}$ is satisfied.

If they collide because $j$ leaves a location at timestep $t$, and $i$ enters
the same location at timestep $t$, then $v^{i}_{k}$ and $v^{j}_{s}$ are marked
as satisfied exactly at the $t^{th}$ iteration with $l^{i}_{k}=l^{j}_{s-1}$,
indicating that either $(v^{i}_{k},v^{j}_{s})$ or $(v^{j}_{s+1},v^{i}_{k-1})$
is in $\mathcal{E}_{2}$. But this is also impossible as neither $v^{i}_{k}$
nor $v^{j}_{s+1}$ was satisfied before the $t^{th}$ iteration. ∎

######  Lemma 3 (Deadlock $\iff$ Cycle).

Executing a TPG encounters a deadlock iff the TPG contains cycles.

###### Proof.

If a TPG $\mathcal{G}$ has a cycle, executing it will encounter a deadlock as
no vertices in the cycle can be marked as satisfied. If executing
$\mathcal{G}$ encounters a deadlock in the $t^{\text{th}}$ iteration of the
while-loop, we prove that $\mathcal{G}$ has a cycle by contradiction. Let
$\mathcal{V}^{\prime}$ denote the set of unsatisfied vertices, which is non-
empty by Definition 4. If $\mathcal{G}$ is acyclic, then there exists a
topological ordering of $\mathcal{V}^{\prime}$, and $\mathcal{S}$ must contain
the first vertex in the topological ordering as all of its in-neighbors are
satisfied, contradicting the deadlock condition of $\mathcal{S}=\emptyset$. ∎

######  Lemma 4 (Deadlock-Free).

If a TPG is constructed from a MAPF solution, then executing it is deadlock-
free.

###### Proof.

If a deadlock is encountered, then the execution would enter the while-loop
for infinitely many iterations, and $cost$ strictly increases in each
iteration. Thus, $cost(\mathcal{G})=\infty$. Yet, $cost(\mathcal{P})$ is
finite, contradicting Proposition 1. ∎

##  Appendix B Acknowledgement

The research at Carnegie Mellon University was supported by the National
Science Foundation (NSF) under Grant 2328671. The views and conclusions
contained in this document are those of the authors and should not be
interpreted as representing the official policies, either expressed or
implied, of the sponsoring organizations, agencies, or the U.S. government.

## References

  * Atzmon et al. (2020) Atzmon, D.; Stern, R.; Felner, A.; Sturtevant, N. R.; and Koenig, S. 2020.  Probabilistic Robust Multi-Agent Path Finding.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , 29–37.
  * Atzmon et al. (2018) Atzmon, D.; Stern, R.; Felner, A.; Wagner, G.; Barták, R.; and Zhou, N. 2018.  Robust Multi-Agent Path Finding.  In _Proceedings of the International Symposium on Combinatorial Search_ , 2–9.
  * Berndt et al. (2020) Berndt, A.; van Duijkeren, N.; Palmieri, L.; and Keviczky, T. 2020.  A Feedback Scheme to Reorder A Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph.  _ArXiv_.
  * Chen et al. (2021) Chen, Z.; Harabor, D. D.; Li, J.; and Stuckey, P. J. 2021.  Symmetry Breaking for k-Robust Multi-Agent Path Finding.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 12267–12274.
  * Hönig et al. (2019) Hönig, W.; Kiesel, S.; Tinka, A.; Durham, J. W.; and Ayanian, N. 2019.  Persistent and Robust Execution of MAPF Schedules in Warehouses.  _IEEE Robotics and Automation Letters_ , 1125–1131.
  * Hönig et al. (2016) Hönig, W.; Kumar, T. K. S.; Cohen, L.; Ma, H.; Xu, H.; Ayanian, N.; and Koenig, S. 2016.  Multi-Agent Path Finding with Kinematic Constraints.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , 477–485.
  * Hönig et al. (2018) Hönig, W.; Preiss, J. A.; Kumar, T. K. S.; Sukhatme, G. S.; and Ayanian, N. 2018.  Trajectory Planning for Quadrotor Swarms.  _IEEE Transactions on Robotics_ , 856–869.
  * Kou et al. (2020) Kou, N. M.; Peng, C.; Ma, H.; Kumar, T. K. S.; and Koenig, S. 2020.  Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 9925–9932.
  * Ma, Kumar, and Koenig (2017) Ma, H.; Kumar, T. S.; and Koenig, S. 2017.  Multi-Agent Path Finding with Delay Probabilities.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 3605–3612.
  * Mannucci, Pallottino, and Pecora (2021) Mannucci, A.; Pallottino, L.; and Pecora, F. 2021.  On Provably Safe and Live Multirobot Coordination With Online Goal Posting.  _IEEE Transactions on Robotics_ , 37(6): 1973–1991.
  * Silver (2005) Silver, D. 2005.  Cooperative Pathfinding.  In _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , 117–122.
  * Stern et al. (2019) Stern, R.; Sturtevant, N. R.; Felner, A.; Koenig, S.; Ma, H.; Walker, T. T.; Li, J.; Atzmon, D.; Cohen, L.; Kumar, T. K. S.; Boyarski, E.; and Bartak, R. 2019.  Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks.  In _Proceedings of the International Symposium on Combinatorial Search_ , 151–159.
  * Su, Veerapaneni, and Li (2024) Su, Y.; Veerapaneni, R.; and Li, J. 2024.  Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution.  In _Proceedings of the AAAI Conference on Artificial Intelligence_.
  * Wurman, D’Andrea, and Mountz (2007) Wurman, P. R.; D’Andrea, R.; and Mountz, M. 2007.  Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 1752–1759.


# Superdiffusive pulling, trapping, and assembly of colloids using nanowire
plasmons

Vandana Sharma<EMAIL_ADDRESS>Department of Physics,
Indian Institute of Science Education and Research, Pune-411008, India  Sunny
Tiwari  Department of Physics, Indian Institute of Science Education and
Research, Pune-411008, India  Diptabrata Paul  Department of Physics, Indian
Institute of Science Education and Research, Pune-411008, India  Ratimanasee
Sahu  Department of Physics, Indian Institute of Science Education and
Research, Pune-411008, India  Vijayakumar Chikkadi  Department of Physics,
Indian Institute of Science Education and Research, Pune-411008, India  G.V.
Pavan Kumar<EMAIL_ADDRESS>Department of Physics, Indian Institute of
Science Education and Research, Pune-411008, India

###### Abstract

Optical excitation of colloids can be harnessed to realize soft matter systems
that are out of equilibrium. In this paper, we present our experimental
studies on the dynamics of silica colloids in the vicinity of a silver
nanowire propagating surface plasmon polaritons (SPPs). Due to the optothermal
interaction, the colloids make a transition from a diffusive to superdiffusive
behaviour, and are directionally pulled towards the excitation point of the
nanowire. Having reached this point, they are spatio-temporally trapped around
the excitation location. By increasing the concentration of colloids in the
system, we observe multi-particle assembly around the nanowire. This process
is thermophoretically driven and assisted by SPPs. Furthermore, we find such
an assembly to be sensitive to the excitation polarization at input of the
nanowire. Numerically-simulated temperature distribution around an illuminated
nanowire corroborates sensitivity to the excitation polarization. Our study
will find relevance in exploration of SPPs-assisted optothermal pulling,
trapping and assembly of colloids, and can serve as test-beds of plasmon-
driven active matter.

##  1 Introduction

How do colloids1234behave in the vicinity of an optical and/or optothermal
potential? How can colloidal dynamics and assembly be controlled by harnessing
optical excitation? These are relevant questions in driving soft matter out of
equilibrium, where the driving force is provided by an optical excitation. In
this study, we present superdiffusive directional pulling of dielectric
colloids in the vicinity of an optically-excited metal nanowire. This movement
further leads to spatio-temporal trapping of the same colloids. Upon
increasing the concentration of the colloids, a two dimensional assembly
emerges. This emergent process is found to be sensitive to the excitation
polarization of the light illuminating the nanowire.

In this context, understanding the dynamics of colloids under such optical
excitation schemes is relevant.567 89Recently, colloidal manipulation using
optical pulling forces has also gained significant interest.10111213
Typically, colloids undergo diffusive Brownian motion. 14 Brownian motion is
relevant to the understanding of the dynamics of soft matter and biological
systems 15 as well as fabricated structures designed to mimic naturally
occurring systems.21617 The study of the physics of systems out of equilibrium
1819 is especially of pertinent interest as most of the living matter is far
from equilibrium. In this context, colloids have been extensively studied to
explore the dynamics of such systems.202122 23 The colloids have the advantage
of easy manipulation under external fields. 2425 2627 282930Conventionally,
colloids are trapped using a focused laser beam3132. Although powerful, the
conventional optical schemes are constrained by the diffraction limit of
light.33 As a complement to this, surface plasmon polaritons (SPPs) in
metallic nanostructures can facilitate radiative and non-radiative pathways
below the diffraction limit of light. 34353637 SPPs are surface
electromagnetic waves at metal-dielectric interface.38 They decay into the
dielectric medium through radiative and non-radiative channels. Radiative
channels can be harnessed for optical trapping and assembly through SPPs
momentum, and non-radiative channels of SPPs can be used for optothermal
assembly via thermophoretic394041 interactions.

Of relevance to this study is SPPs propagation along the silver nanowire.42 43
When illuminated with a focused laser beam, these single crystalline,
chemically-prepared nanowires can propagate SPPs. Given the geometry of the
nanowire, quasi-one dimensional confinement of plasmons can lead to
interesting optical and optothermal effects at sub-wavelength scales. Although
SPPs in the silver nanowire have been studied extensively in the context of
nanophotonics4445464748, their interface with soft-matter systems such as
colloids is yet to be explored in detail. 49 50 SPPs have been utilized in the
past to assemble particles on a large scale. But such studies have mainly
relied on extended 2D plasmonic platforms such as metallic films.3537

Motivated by this, herein we report the directed pulling and trapping of a
single silica colloid as well as assembly formation of colloids by utilizing a
single, silver nanowire to create a non-equilibrium environment in the system.
A laser beam (532 nm) is focused at the end of a silver nanowire, which leads
to the excitation of SPPs. In this study, we explore the transport and
trapping of single colloids (figure 1a), and multiparticle assembly (figure
1b) due to the optical excitation of the plasmonic silver nanowire. A
representative optical image of SPPs propagating in a silver nanowire at 532
nm is shown in figure 1c(i). The excitation polarization of the focused laser
beam is aligned along the nanowire axis. This leads to SPPs propagation which
out-couples at the distal end of the nanowire (dotted circle in figure 1c(i)).
The SPPs supported by the nanowire generate heat51 5253which is subsequently
released into the surrounding environment creating a temperature gradient in
the system. The subsequent dynamics of the particles is studied by looking
into the mean square displacement (MSD) of the particles. The MSD at time
$\tau$ is defined as the ensemble average:

$MSD(\tau)=<\Delta r(\tau)^{2}>=<[r(t+\tau)-r(\tau)]^{2}>.$ (1)

where, $r(t)$ is the position of the particle at time t, $\tau$ is the time
lag between two positions of the particle whose displacement is $\Delta
r(\tau),<>$ is the time-average over t and/or an ensemble-average over several
trajectories.

Figure 1: Schematic illustration of the experimental configuration. Silver
nanowires are dropcasted on the glass substrate. One end of the Ag nanowire is
excited using a 532 nm laser to excite the SPPs. The light out-couples from
the distal end of the wire. Silica colloids dispersed in milli-Q water are
dropcasted on the glass substrate. The whole system is enclosed in a 120
$\mu$m chamber. (a) Schematic illustration of the single silica particle
transport along the silver nanowire. (b) Schematic illustration of the
multiple particle assembly along the silver nanowire. (c) (i) Excitation of
SPPs along the silver nanowire when the polarization of the input laser is
along the length of the nanowire. (c)(ii) SEM image of a representative silver
nanowire used in the experiments. (d) Schematic representation of the
experimental setup. The silver nanowire is excited using a high numerical
aperture 100 X, 1.4 NA objective lens. M is the mirror. The laser beam is
expanded using a combination of lenses, L1 and L2. The polarization of the
input laser is controlled using a half wave plate. The sample is illuminated
from the top using a white light. The video is recorded by CCD after rejecting
the elastically scattered light using a 532 nm edge filter.

Calculating the MSD is an important parameter as it provides information about
the mode of displacement of the particles in the medium it is embedded in.54
There can be several modes of movement of the particle such as free diffusion,
transported or confined motion in a given fluid. For a freely diffusing
particle the MSD can be represented as:

$<\Delta r(\tau)^{2}>=2dD\tau.$ (2)

where $d$ is the number of the dimension and $D$ is the diffusion coefficient
of the particle. Depending on the micro-environment of the colloidal particle,
it can deviate from the diffusive behavior and display other dynamics known as
anomalous diffusion.555657 23 MSD of such particles can be represented by the
power law:

$<\Delta r(\tau)^{2}>=D\tau^{n}.$ (3)

where $D$ is the generalized diffusion coefficient. The exponent of $\tau$
provides information about the dynamics of the colloids. If $n>1$, the process
is superdiffusive , and if $n<1$ it represents a subdiffusive process.

##  2 Methods

###  2.1 Sample preparation and experimental design

Our experimental design constitutes a simple geometry wherein a silver
nanowire is dropcasted on a glass substrate and left to dry. The silver
nanowires are chemically synthesized using the polyol process. 58 The typical
size of the silver nanowire used in the experiments is $\approx$ 300-400 nm in
diameter and $\approx$12 $\mu$m in length. The nanowire is characterized using
scanning electron microscopy as shown in figure 1(c)(ii). The colloids consist
of 2 $\mu$m silica beads (purchased from Microspheres-Nanospheres) and 2.2
$\mu$m polystyrene beads (purchased from micro particles Gmbh). The colloids
dispersed in milli-Q water are dropcasted on the glass substrate. The whole
system is enclosed in a 120 $\mu$m spacer. Figure 1 (d) shows the schematic of
the inverted experimental setup. A 532 nm laser is expanded using a
combination of two lenses L1 and L2. A half wave plate is used to control the
input polarization of the beam. One end of the silver nanowire is excited by
tightly focusing the laser using a 100 X, 1.4 NA objective lens. The power at
the sample plane is measured to be 5 mW. The polarization of the incoming
laser is kept along the nanowire unless specified otherwise, for efficient
excitation of the SPPs. The videos are recorded by the CCD at 20 fps after
rejecting the elastically scattered light by a 532 nm edge filter.

###  2.2 Numerical simulations

The temperature distribution of the system is calculated using Finite element
method based numerical simulations (COMSOL Multiphysics) by solving
electromagnetic wave and heat transfer in solids and fluids modules in 3D. An
8 $\mu$m long silver nanowire with a diameter of 350 nm is excited using
focused 532 nm gaussian beam. The whole geometry is simulated using free
tetrahedral user defined mesh.

##  3 Results and Discussion

###  3.1 Superdiffusive dynamics of a single particle transport

A single nanowire dropcasted on a glass substrate can act as a guiding medium
for the directed motion of the colloid from its captured location to the
excitation point. The nanowire initially traps the particle at one of the
locations of the wire depending on the initial position of the particle with
respect to the wire.

Here, we demonstrate the trapping of the silica colloid from the distal end of
the nanowire. If the particle is closer to any other location of the wire when
it is in its vicinity, it will get trapped there first, and then move towards
the excitation point. One end of the silver nanowire is excited through a 100
X, 1.4 NA objective lens. The white dotted circle represents the excitation
point. Figure 2(a) shows the time series images of a silica colloid transport
along the nanowire. At t= 0 s , the colloid is freely diffusing in the water.
As it comes closer to the wire, it gets trapped at the distal end at 13 s and
starts to move along the nanowire. Within 65 s, the particle is trapped at the
excitation point (See supplementary movie S1). To analyse the dynamics of the
colloidal particle, it is essential to map out the trajectory and the
associated MSD of the particle.

Figure 2: Super diffusive dynamics of single particle transport. (a) Time
series images of the directed motion of the silica colloid along the silver
nanowire from the distal end towards the excitation point of the laser. The
polarization of the input laser is kept along the length of the silver
nanowire for efficient excitation of SPPs. Black arrows indicate the direction
of movement of the particle. The particle gets transported from one end of the
nanowire to the other end within a minute. (b) The trajectory of the colloid
is plotted. The blue arrow indicates the direction of particle transport. (c)
Mean square displacement of the colloid. Particle dynamics shows super
diffusive behavior. At a smaller lag time, the slope of the MSD curve is
approximately 1.25. At larger lag times, the slope of the curve becomes
steeper, approximately equal to 1.85. (d) Trajectory of the particle once it
is confined at the excitation point. The dotted line represents the
orientation of the nanowire with respect to the particle trajectory. (e)
Temperature distribution of the system in the x-y plane at z=0 i.e. at the
base of the nanowire. (f) A crosscut along the top of the nanowire at z=317 nm
shown in (e) as the black dotted line. The 0 in the graph corresponds to the
centre of the nanowire.

The particle is tracked from the moment it makes contact with the wire till it
is transported to the other end using Trackpy.59 The associated trajectory of
the particle is plotted in figure 2(b). The trajectory plot shows that the
motion of the particle is highly directional. The blue arrow indicates the
direction of the movement of the particle. To further investigate the nature
of the colloidal transport, we plot the MSD of the colloid on a log-log scale
for the same time interval, as shown in figure 2(c). At smaller time lags till
1 s, the colloid has a nearly diffusive behavior with the diffusion exponent
of 1.25, whereas at larger lag times the colloid displays superdiffusive
behavior with the diffusion exponent of 1.85. A diffusion exponent of more
than 1 indicates the transported movement as Brownian motion alone can not
account for such fast particle displacement. A comparative study for the
Brownian motion of the ensemble of colloids which are under no laser
excitation is given in SI figure 1(see supplementary movie S2). A similar
analysis for other particle-wire transport system is given in SI figure 2.

A previous study reported the transport of a much smaller TiO2 particle along
the nanowire, but it is not permanently trapped and is pushed away from the
excitation point into the solution. 49 In our case, once the silica colloid
reaches the excitation point, it is permanently trapped there as long as the
excitation laser is on. The trajectory of the trapped particle is shown in
figure 2(d). By turning off the laser, the particle can again be released into
the solution.

The efficient excitation of SPPs is crucial for the transport of the colloid.
When a metallic structure is irradiated by an electromagnetic field, there is
an associated heat generated in the system due to Joule heating.51 After
plasmons are launched along the nanowire, heat is generated at the excitation
point as well as along the length of the wire due to plasmon dissipation.
Consequently, the temperature of the nanowire increases and the heat is
released to the environment. The temperature distribution in the xy plane at
z=0 is shown in figure 2 (d). The system attains a total temperature increment
of $\approx$10 K at the excitation point. A plot of the temperature
distribution at the top of the wire at z=317 nm is plotted in figure 2 (e)
which shows that the temperature is highest at the excitation point of the
wire and gradually decreases along the length of the nanowire. As reported
previously34, silica colloids show thermophoretic migration from a lower
temperature to a higher temperature. When the silver nanowire is excited, a
temperature gradient is set up in the nanowire as well as its surroundings.
Initially, the particle is moving freely in the water. When the colloid comes
into the field of optothermal gradient of the system, it senses the
temperature gradient and and is pulled towards the excitation point having the
highest temperature.
To compare with a particle of different composition, and to emphasize the role
of thermophoretic interactions, experiments were also performed at the same
laser power with the polystyrene (PS) beads of size 2.2 $\mu$m (See
supplementary movie S3). PS beads have been previously reported to move from a
higher temperature to a lower temperature.6061 In our experiments, the PS
particles initially come closer to the nanowire but as they come too close,
they are repelled from the excitation point. The selective trapping of the
particles shows that thermophoresis has a contributing factor in trapping the
particle.

###  3.2 Confined dynamics of multiple colloids

A silver nanowire can not only trap and transport a single colloid but can
also be used to assemble multiple particles along its length. A concentrated
solution of silica colloids in milli-Q water was prepared so that multiple
particles can come into the field of optothermal potential simultaneously.
Figure 3 (a) shows the time series images of the gradual assembly of the
colloids along the length of the nanowire. At 0 s, two silica particles are
trapped at the excitation point. Within 32 s, ten particles are aligned along
the length of the nanowire.

Figure 3: Confined motion of multiple particles. (a) Time series images of the
gradual assembly of the colloids. Multiple layers of the colloids are formed
along the length of the nanowire within 255 s. The dotted circle indicates the
laser excitation point. The black arrow at 0 s indicates the direction of the
motion of the colloids. The white dotted region indicates the region where
colloids are tightly bound. (b) The trajectories of the particles in the white
dotted region are plotted over a time period of 150 s. (c) The averaged MSD of
all the particles is plotted as a single curve.

As shown in figure 2 (e), the temperature is higher towards the first half of
the wire closer to the excitation point. Consequently, the particles first
accumulate near the excitation end of the nanowire and start forming the
second layer on both sides of the wire at 65 s. At 255 s, we observe a two
layer formation of the colloids, which are stably trapped there as long as the
laser excitation is on. The trajectories of the multiple particles shown in
dotted white box in figure 3(a) over a period of 150 s are plotted in figure 3
(b). See supplementary movie S4 for the entire assembly process. The first
layer closer to the wire exhibits stronger confinement to the nanowire as can
be seen through the smaller spread of the trajectories of the individual
colloids. Moreover, the trajectories are more confined perpendicular to the
wire compared to along the wire. Since, the second layer of the colloids are
not bounded by a third layer, they exhibit a larger spread in the trajectories
perpendicular to the wire. The averaged MSD of all the particles is plotted in
figure 3 (c). The curve almost falls flat and saturates at large lag times
with the diffusion exponent of $\approx$ 0 indicating the confined motion of
the trapped particles. The movement of the particles is impeded and they can
not freely diffuse away from the trapped location.

###  3.3 Polarization dependence of the assembly

The heat generated by the silver nanowire can be contributed to two factors.
One is absorption by the wire, and the other is due to the generation of
SPPs62. As mentioned previously, the SPPs play a crucial role in the
generation of heat and consequently trapping the colloidal particles. Keeping
the polarization of the beam along the silver nanowire leads to efficient
excitation of SPPs as can be seen in figure 4 (a)(ii) and consequently, should
lead to faster assembly process. Figure 4(a) and 4(b) compares the extent of
the assembly for the two cases, one when the polarization of the incoming beam
is along the length of the nanowire and second, when it is perpendicular to
it.

First the polarization is kept along the nanowire and the snapshot of the
assembly is taken at 7 minutes as shown in figure 4(a)(i). Once the assembly
reaches the saturation point, the laser is switched off and the colloids are
free to redisperse into the solution. Now, the polarization of the laser is
switched to perpendicular to the wire. In this case the efficiency of
excitation of propagating plasmons is drastically reduced and no outcoupling
of the light from the distal end is observed as can be seen in figure
4(b)(ii). A snapshot of the assembly after the same time of 7 minutes is shown
in figure 4 (b)(i). A few particles near the excitation point and along the
length of the wire can be seen but there is no significant assembly of the
particles. The temperature distribution in the xy plane at z=0 is shown in
figure 4(c). A comparative temperature distribution for the both the
polarizations at the top of the wire is plotted in figure 4 (d). The assembly
process for both the polarization can be found in supplementary movie S5 and
movie S6.

Figure 4: Polarization dependence of the assembly. (a) (i) Assembly of the
colloids after 7 minutes when the polarization of the input laser is along the
length of the silver nanowire. The dotted circle indicates the laser
excitation point. (ii) Excitation of silver nanowire. The light out-couples
from the distal end of the wire. (b)(i) There is no significant assembly of
the colloids though few particles are trapped near the excitation point. (ii)
Excitation of the wire when the polarization is perpendicular to the long axis
of the wire. (c) Temperature distribution in the x-y plane at z=0, i.e. at the
base of the silver nanowire. (d) A crosscut of the temperature distribution
along the white dotted line at z= 317 nm, i.e. at the top of the nanowire is
plotted for both the orientations of the polarization. The 0 in the graph
corresponds to the centre of the nanowire.

A higher temperature increase at the excitation point is found in the case of
perpendicular polarization. It can be attributed to the fact that at the
excitation point the electric field is confined to a smaller region along the
diameter of the wire leading to more localized plasmon excitation. The near-
field electric field distribution for both the cases is shown in supplementary
figure S3. This enhances the temperature increment at this point, but the
gradual fall in the temperature is more as there is less efficient excitation
of plasmons along the nanowire and the resultant temperature increase due to
plasmon dissipation is missing when there are no propagating plasmons.

##  4 Conclusion

We have experimentally studied the transport of the silica colloid by
utilizing SPPs of a silver nanowire. The nature of the transport was found to
be superdiffusive in nature due to the optothermal pulling of colloids towards
the excitation point. Such a pulled colloid is spatio-temporally trapped at
the nanowire excitation. Upon increasing the concentration of the colloids, we
observed extended assemblies whose collective dynamics was studied and shown
to be confined in nature. This assembly process is sensitive to the excitation
polarization at nanowire input.This polarization-sensitivity was also
corroborated in the simulated temperature distribution around the nanowire,
thus indicating an intricate combination of optical and thermal effects
facilitated by the nanowire SPPs. Given that the colloids are driven out of
equilibrium by a quasi-one dimensional optothermal substrate, they may serve
as interesting test-beds for active and driven matter at sub-micron scales. We
envisage the utility of SPPs to create intriguing optothermal potentials to
drive soft matter out of equilibrium, that can complement and improvise on
conventional optical schemes.

Authors thank Pragya Kushwaha, Shailendra Kumar Chaubey and Chetna Taneja for
fruitful discussions. This work was partially funded by Air Force Research
Laboratory grant (FA2386-18-1-4118 R& D18IOA118) and Swarnajayanti fellowship
grant (DST/SJF/PSA02/2017-18) to G V PK.

The videos can be found here

https://www.youtube.com/playlist?list=PLVIRTkGrtbrszZdisE9AewKpvJABfp02f

## References

  * Palacci et al. 2013 Palacci, J.; Sacanna, S.; Steinberg, A. P.; Pine, D. J.; Chaikin, P. M. Living crystals of light-activated colloidal surfers. _Science_ 2013, _339_ , 936–940
  * Lozano et al. 2016 Lozano, C.; Ten Hagen, B.; Löwen, H.; Bechinger, C. Phototaxis of synthetic microswimmers in optical landscapes. _Nature communications_ 2016, _7_ , 1–10
  * Buttinoni et al. 2012 Buttinoni, I.; Volpe, G.; Kümmel, F.; Volpe, G.; Bechinger, C. Active Brownian motion tunable by light. _Journal of Physics: Condensed Matter_ 2012, _24_ , 284129
  * Manoharan 2015 Manoharan, V. N. Colloidal matter: Packing, geometry, and entropy. _Science_ 2015, _349_ , 1253751
  * Zaidouny et al. 2013 Zaidouny, L.; Bohlein, T.; Roth, R.; Bechinger, C. Light-induced phase transitions of colloidal monolayers with crystalline order. _Soft Matter_ 2013, _9_ , 9230–9236
  * Wei et al. 1998 Wei, Q.-H.; Bechinger, C.; Rudhardt, D.; Leiderer, P. Experimental Study of Laser-Induced Melting in Two-Dimensional Colloids. _Phys. Rev. Lett._ 1998, _81_ , 2606–2609
  * Schmidt et al. 2019 Schmidt, F.; Liebchen, B.; Löwen, H.; Volpe, G. Light-controlled assembly of active colloidal molecules. _The Journal of chemical physics_ 2019, _150_ , 094905
  * Jenkins and Egelhaaf 2008 Jenkins, M. C.; Egelhaaf, S. U. Colloidal suspensions in modulated light fields. _Journal of Physics: Condensed Matter_ 2008, _20_ , 404220
  * Dobnikar et al. 2013 Dobnikar, J.; Snezhko, A.; Yethiraj, A. Emergent colloidal dynamics in electromagnetic fields. _Soft Matter_ 2013, _9_ , 3693–3704
  * Chen et al. 2011 Chen, J.; Ng, J.; Lin, Z.; Chan, C. Optical pulling force. _Nature photonics_ 2011, _5_ , 531–534
  * Lu et al. 2017 Lu, J.; Yang, H.; Zhou, L.; Yang, Y.; Luo, S.; Li, Q.; Qiu, M. Light-induced pulling and pushing by the synergic effect of optical force and photophoretic force. _Physical review letters_ 2017, _118_ , 043601
  * Ali et al. 2020 Ali, R.; Pinheiro, F.; Dutra, R.; Neto, P. M. Tailoring optical pulling forces with composite microspheres. _Physical Review A_ 2020, _102_ , 023514
  * Li et al. 2020 Li, H.; Cao, Y.; Zhou, L.-M.; Xu, X.; Zhu, T.; Shi, Y.; Qiu, C.-W.; Ding, W. Optical pulling forces and their applications. _Advances in Optics and Photonics_ 2020, _12_ , 288–366
  * Bian et al. 2016 Bian, X.; Kim, C.; Karniadakis, G. E. 111 years of Brownian motion. _Soft Matter_ 2016, _12_ , 6331–6346
  * Frey and Kroy 2005 Frey, E.; Kroy, K. Brownian motion: a paradigm of soft matter and biological physics. _Annalen der Physik_ 2005, _14_ , 20–50
  * Lozano et al. 2018 Lozano, C.; Gomez-Solano, J. R.; Bechinger, C. Run-and-tumble-like motion of active colloids in viscoelastic media. _New Journal of Physics_ 2018, _20_ , 015008
  * Niese et al. 2020 Niese, L.; Wang, L.; Das, S.; Simmchen, J. Apparent phototaxis enabled by Brownian motion. _Soft Matter_ 2020, _16_ , 10585–10590
  * Blickle et al. 2007 Blickle, V.; Speck, T.; Lutz, C.; Seifert, U.; Bechinger, C. Einstein relation generalized to nonequilibrium. _Physical review letters_ 2007, _98_ , 210601
  * Ganguly and Chaudhuri 2013 Ganguly, C.; Chaudhuri, D. Stochastic thermodynamics of active Brownian particles. _Physical Review E_ 2013, _88_ , 032102
  * Bechinger et al. 2016 Bechinger, C.; Di Leonardo, R.; Löwen, H.; Reichhardt, C.; Volpe, G.; Volpe, G. Active particles in complex and crowded environments. _Rev. Mod. Phys._ 2016, _88_ , 045006
  * Rings et al. 2010 Rings, D.; Schachoff, R.; Selmke, M.; Cichos, F.; Kroy, K. Hot brownian motion. _Physical review letters_ 2010, _105_ , 090604
  * Su et al. 2021 Su, X.; Fischer, A.; Cichos, F. Towards Measuring the Maxwell–Boltzmann Distribution of a Single Heated Particle. _Frontiers in Physics_ 2021, _9_ , 342
  * Fernandez-Rodriguez et al. 2020 Fernandez-Rodriguez, M. A.; Grillo, F.; Alvarez, L.; Rathlef, M.; Buttinoni, I.; Volpe, G.; Isa, L. Feedback-controlled active brownian colloids with space-dependent rotational dynamics. _Nature communications_ 2020, _11_ , 1–10
  * Caciagli et al. 2020 Caciagli, A.; Singh, R.; Joshi, D.; Adhikari, R.; Eiser, E. Controlled optofluidic crystallization of colloids tethered at interfaces. _Physical Review Letters_ 2020, _125_ , 068001
  * Vialetto et al. 2021 Vialetto, J.; Rudiuk, S.; Morel, M.; Baigl, D. Photothermally Reconfigurable Colloidal Crystals at a Fluid Interface, a Generic Approach for Optically Tunable Lattice Properties. _Journal of the American Chemical Society_ 2021, _143_ , 11535–11543
  * Arya et al. 2021 Arya, P.; Umlandt, M.; Jelken, J.; Feldmann, D.; Lomadze, N.; Asmolov, E. S.; Vinogradova, O. I.; Santer, S. Light-induced manipulation of passive and active microparticles. _The European Physical Journal E_ 2021, _44_ , 1–10
  * Ghosh and Ghosh 2019 Ghosh, S.; Ghosh, A. All optical dynamic nanomanipulation with active colloidal tweezers. _Nature communications_ 2019, _10_ , 1–8
  * Tkachenko et al. 2020 Tkachenko, G.; Toftul, I.; Esporlas, C.; Maimaiti, A.; Le Kien, F.; Truong, V. G.; Chormaic, S. N. Light-induced rotation of dielectric microparticles around an optical nanofiber. _Optica_ 2020, _7_ , 59–62
  * Ghosh et al. 2019 Ghosh, S.; Biswas, A.; Roy, B.; Banerjee, A. Self-assembly and complex manipulation of colloidal mesoscopic particles by active thermocapillary stress. _Soft matter_ 2019, _15_ , 4703–4713
  * Ghosh et al. 2020 Ghosh, S.; Ranjan, A. D.; Das, S.; Sen, R.; Roy, B.; Roy, S.; Banerjee, A. Directed self-assembly driven mesoscale lithography using laser-induced and manipulated microbubbles: Complex architectures and diverse applications. _Nano letters_ 2020, _21_ , 10–25
  * Ashkin et al. 1986 Ashkin, A.; Dziedzic, J. M.; Bjorkholm, J. E.; Chu, S. Observation of a single-beam gradient force optical trap for dielectric particles. _Optics letters_ 1986, _11_ , 288–290
  * Jones et al. 2015 Jones, P. H.; Maragò, O. M.; Volpe, G. _Optical tweezers: Principles and applications_ ; Cambridge University Press, 2015
  * Melzer and McLeod 2018 Melzer, J. E.; McLeod, E. Fundamental limits of optical tweezer nanoparticle manipulation speeds. _ACS nano_ 2018, _12_ , 2440–2447
  * Sharma et al. 2020 Sharma, V.; Paul, D.; Chaubey, S. K.; Tiwari, S.; Kumar, G. P. Large-scale optothermal assembly of colloids mediated by a gold microplate. _Journal of Physics: Condensed Matter_ 2020, _32_ , 324002
  * Patra et al. 2014 Patra, P. P.; Chikkaraddy, R.; Tripathi, R. P.; Dasgupta, A.; Kumar, G. V. P. Plasmofluidic single-molecule surface-enhanced Raman scattering from dynamic assembly of plasmonic nanoparticles. _Nature communications_ 2014, _5_ , 1–8
  * Patra et al. 2016 Patra, P. P.; Chikkaraddy, R.; Thampi, S.; Tripathi, R. P.; Kumar, G. V. P. Large-scale dynamic assembly of metal nanostructures in plasmofluidic field. _Faraday discussions_ 2016, _186_ , 95–106
  * Garcés-Chávez et al. 2006 Garcés-Chávez, V.; Quidant, R.; Reece, P.; Badenes, G.; Torner, L.; Dholakia, K. Extended organization of colloidal microparticles by surface plasmon polariton excitation. _Physical Review B_ 2006, _73_ , 085417
  * Barnes et al. 2003 Barnes, W. L.; Dereux, A.; Ebbesen, T. W. Surface plasmon subwavelength optics. _nature_ 2003, _424_ , 824–830
  * Piazza and Parola 2008 Piazza, R.; Parola, A. Thermophoresis in colloidal suspensions. _Journal of Physics: Condensed Matter_ 2008, _20_ , 153102
  * Piazza 2008 Piazza, R. Thermophoresis: moving particles with thermal gradients. _Soft Matter_ 2008, _4_ , 1740–1744
  * Reichl et al. 2014 Reichl, M.; Herzog, M.; Götz, A.; Braun, D. Why charged molecules move across a temperature gradient: the role of electric fields. _Physical review letters_ 2014, _112_ , 198101
  * Shegai et al. 2011 Shegai, T.; Miljkovic, V. D.; Bao, K.; Xu, H.; Nordlander, P.; Johansson, P.; Kall, M. Unidirectional broadband light emission from supported plasmonic nanowires. _Nano letters_ 2011, _11_ , 706–711
  * Yang et al. 2016 Yang, H.; Qiu, M.; Li, Q. Identification and control of multiple leaky plasmon modes in silver nanowires. _Laser & Photonics Reviews_ 2016, _10_ , 278–286
  * Guo et al. 2019 Guo, Q.; Fu, T.; Tang, J.; Pan, D.; Zhang, S.; Xu, H. Routing a chiral Raman signal based on spin-orbit interaction of light. _Physical review letters_ 2019, _123_ , 183903
  * Johns et al. 2017 Johns, P.; Beane, G.; Yu, K.; Hartland, G. V. Dynamics of surface plasmon polaritons in metal nanowires. _The Journal of Physical Chemistry C_ 2017, _121_ , 5445–5459
  * Vasista et al. 2018 Vasista, A. B.; Jog, H.; Heilpern, T.; Sykes, M. E.; Tiwari, S.; Sharma, D. K.; Chaubey, S. K.; Wiederrecht, G. P.; Gray, S. K.; Kumar, G. V. P. Differential wavevector distribution of surface-enhanced Raman scattering and fluorescence in a film-coupled plasmonic nanowire cavity. _Nano letters_ 2018, _18_ , 650–655
  * Tiwari et al. 2020 Tiwari, S.; Taneja, C.; Sharma, V.; Vasista, A. B.; Paul, D.; Kumar, G. V. P. Dielectric microsphere coupled to a plasmonic nanowire: a self-assembled hybrid optical antenna. _Advanced Optical Materials_ 2020, _8_ , 1901672
  * Tiwari et al. 2021 Tiwari, S.; Vasista, A. B.; Paul, D.; Chaubey, S. K.; Kumar, G. V. P. Beaming Elastic and SERS Emission from Bent-Plasmonic Nanowire on a Mirror Cavity. _The Journal of Physical Chemistry Letters_ 2021, _12_ , 6589–6595, PMID: 34242502
  * Yang et al. 2016 Yang, C.; Pan, D.; Tong, L.; Xu, H. Guided transport of nanoparticles by plasmonic nanowires. _Nanoscale_ 2016, _8_ , 19195–19199
  * Nan and Yan 2019 Nan, F.; Yan, Z. Silver-nanowire-based interferometric optical tweezers for enhanced optical trapping and binding of nanoparticles. _Advanced Functional Materials_ 2019, _29_ , 1808258
  * Baffou 2017 Baffou, G. _Thermoplasmonics: Heating Metal Nanoparticles Using Light_ ; Cambridge University Press, 2017
  * Baffou and Quidant 2013 Baffou, G.; Quidant, R. Thermo-plasmonics: using metallic nanostructures as nano-sources of heat. _Laser & Photonics Reviews_ 2013, _7_ , 171–187
  * Möller et al. 2018 Möller, T. B.; Ganser, A.; Kratt, M.; Dickreuter, S.; Waitz, R.; Scheer, E.; Boneberg, J.; Leiderer, P. Fast quantitative optical detection of heat dissipation by surface plasmon polaritons. _Nanoscale_ 2018, _10_ , 11894–11900
  * Dunderdale et al. 2012 Dunderdale, G.; Ebbens, S.; Fairclough, P.; Howse, J. Importance of particle tracking and calculating the mean-squared displacement in distinguishing nanopropulsion from other processes. _Langmuir_ 2012, _28_ , 10997–11006
  * Sokolov 2012 Sokolov, I. M. Models of anomalous diffusion in crowded environments. _Soft Matter_ 2012, _8_ , 9043–9052
  * Oliveira et al. 2019 Oliveira, F. A.; Ferreira, R.; Lapas, L. C.; Vainstein, M. H. Anomalous diffusion: A basic mechanism for the evolution of inhomogeneous systems. _Frontiers in Physics_ 2019, _7_ , 18
  * Metzler et al. 2014 Metzler, R.; Jeon, J.-H.; Cherstvy, A. G.; Barkai, E. Anomalous diffusion models and their properties: non-stationarity, non-ergodicity, and ageing at the centenary of single particle tracking. _Physical Chemistry Chemical Physics_ 2014, _16_ , 24128–24164
  * Sun et al. 2003 Sun, Y.; Mayers, B.; Herricks, T.; Xia, Y. Polyol synthesis of uniform silver nanowires: a plausible growth mechanism and the supporting evidence. _Nano letters_ 2003, _3_ , 955–960
  * Allan et al. 2021 Allan, D. B.; Caswell, T.; Keim, N. C.; van der Wel, C. M.; Verweij, R. W. soft-matter/trackpy: Trackpy v0.5.0. 2021; https://doi.org/10.5281/zenodo.4682814
  * Duhr and Braun 2005 Duhr, S.; Braun, D. Two-dimensional colloidal crystals formed by thermophoresis and convection. _Applied physics letters_ 2005, _86_ , 131921
  * Braun et al. 2014 Braun, M.; Würger, A.; Cichos, F. Trapping of single nano-objects in dynamic temperature fields. _Physical Chemistry Chemical Physics_ 2014, _16_ , 15207–15213
  * Li et al. 2019 Li, Q.; Chen, L.; Xu, H.; Liu, Z.; Wei, H. Photothermal modulation of propagating surface plasmons on silver nanowires. _ACS Photonics_ 2019, _6_ , 2133–2140

Supplementary Material
Superdiffusive pulling, trapping, and assembly of colloids using nanowire
plasmons
Vandana Sharma,∗ Sunny Tiwari, Diptabrata Paul, Ratimanasee Sahu, Vijayakumar
Chikkadi and G. V. Pavan Kumar∗

Department of Physics, Indian Institute of Science Education and Research,
Pune-411008, India
∗Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Contents

  1. 1 Introduction
  2. 2 Methods
    1. 2.1 Sample preparation and experimental design
    2. 2.2 Numerical simulations
  3. 3 Results and Discussion
    1. 3.1 Superdiffusive dynamics of a single particle transport
    2. 3.2 Confined dynamics of multiple colloids
    3. 3.3 Polarization dependence of the assembly
  4. 4 Conclusion
  5. S1
    1. S1.1 S1: Brownian motion of particles
    2. S1.2 S2: Single particle transport along the nanowire
    3. S1.3 S3: Near-field electric field distribution
    4. S1.4 S4: Details of supplementary movies
  6. S2 S1: Brownian motion of particles
  7. S3 S2: Single particle transport along the nanowire
  8. S4 S3: Near-field electric field distribution
  9. S5 S4: Details on Supporting Movies

## Appendix S1

###  S1.1 S1: Brownian motion of particles

###  S1.2 S2: Single particle transport along the nanowire

###  S1.3 S3: Near-field electric field distribution

###  S1.4 S4: Details of supplementary movies

##  Appendix S2 S1: Brownian motion of particles

Figure S1: (a) Snapshot of particles undergoing Brownian motion. (b)
Trajectories of the particles over a period of 50 s. (c) Ensemble MSD of all
the particles. The diffusion exponent is 1.05. The Brownian motion of the
particles is characterized when the particles are under thermal equilibrium
i.e. there is no temperature gradient. The laser is switched off and the
motion of the particles was recorded for 50 s. The trajectories of the
particles is shown in figure S1 (b). MSD of all the particles is averaged and
plotted against lag time on a log-log scale as shown in figure S2 (c). A
diffusion coefficient of 1.05 shows that the particles are undergoing Brownian
motion.

##  Appendix S3 S2: Single particle transport along the nanowire

Figure S2: (a) Transport of a 2 $\mu$m silica colloid along the nanowire. The
two particles are marked 1 and 2 for clear distinction between them. Particle
1 is already trapped at the excitation point. The corresponding trajectories
of the two particles are plotted in S2 (b). As particle 1 is trapped at the
excitation point, its trajectory is very localized and is represented by
orange color. The trajectory of particle 2 is shown by blue color. The
corresponding MSD of the particle 2 is also shown. Taking another case, two
particles reaching the nanowire at different locations is also considered.
Figure S2 (c) shows the series of images of two particles. Particle 1 is
trapped by the wire near its middle point after which it starts to move
towards the excitation point, whereas particle 2 is captured at the distal
end. The trajectories of both the particles are shown in (d) marked by orange
(particle 1) and blue (particle 2) color. The corresponding MSD of both the
particles when they are trapped by the wire is shown in the next panel of
figure S1 (d).

##  Appendix S4 S3: Near-field electric field distribution

Figure S3: Calculated near-field electric field magnitude when one end of the
nanowire is excited with polarization along the nanowire and (b) perpendicular
to the nanowire.

##  Appendix S5 S4: Details on Supporting Movies

  1. 1.

Supporting Movie 1: Transport of a single 2 $\mu$m silica colloid from the
distal end of the nanowire to the excitation point

  2. 2.

Supporting Movie 2: 2 $\mu$m silica colloids undergoing Brownian motion.

  3. 3.

Supporting Movie 3: No trapping of 2.2 $\mu$m polystyrene beads is observed.

  4. 4.

Supporting Movie 4: Assembly process of 2 $\mu$m silica colloids.

  5. 5.

Supporting Movie 5: Assembly of silica beads when the polarization is along
the nanowire.

  6. 6.

Supporting Movie 6: Assembly of silica beads when the polarization is
perpendicular to the nanowire.