Multi-Agent Search-Type Problems on Polygons

Konstantinos Georgiou
Research supported in part by NSERC Discovery grant.
Caleb Jones
Jesse Lucier

Department of Mathematics, Toronto Metropolitan University, Toronto, Ontario, Canada.

Konstantinos Georgiou[1]  [5]
Caleb Jones[1]  [5]
Jesse Lucier[1]  [5]

[5]Research supported in part by NSERC of Canada.

[1]
Department of Mathematics,
Toronto Metropolitan University,
Toronto, ON, Canada,

We present several advancements in search-type problems for fleets of mobile agents operating in two dimensions under the wireless model. Potential hidden target locations are equidistant from a central point, forming either a disk (infinite possible locations) or regular polygons (finite possible locations). Building on the foundational disk evacuation problem, the disk priority evacuation problem with $k$ Servants, and the disk $w$-weighted search problem, we make improvements on several fronts.
First we establish new upper and lower bounds for the $n$-gon priority evacuation problem with $1$ Servant for $n \leq 13$, and for $n_k$-gons with $k=2, 3, 4$ Servants, where $n_2 \leq 11$, $n_3 \leq 9$, and $n_4 \leq 10$, offering tight or nearly tight bounds. The only previous results known were a tight upper bound for $k=1$ and $n=6$ and lower bounds for $k=1$ and $n \leq 9$.
Second, our work improves the best lower bound known for the disk priority evacuation problem with $k=1$ Servant from $4.46798$ to $4.64666$ and for $k=2$ Servants from $3.6307$ to $3.65332$.
Third, we improve the best lower bounds known for the disk $w$-weighted group search problem, significantly reducing the gap between the best upper and lower bounds for $w$ values where the gap was largest. These improvements are based on nearly tight upper and lower bounds for the $11$-gon and $12$-gon $w$-weighted evacuation problems, while previous analyses were limited only to lower bounds and only to $7$-gons.

Mobile Agents, Evacuation, Priority Evacuation, Disk, Polygons, Wireless Model

§ INTRODUCTION

Search theory is a branch of operations research that focuses on determining optimal strategies for locating targets amid uncertainty and limited information, with search and rescue missions being a prime example. Traditional search requires an agent to identify the target quickly, while evacuation missions need the entire fleet to gather at the hidden target. In some scenarios, only a specific agent must reach the target, or agents with different significance factors influence the solution's quality. Theoretical foundations for these problems date back to the 1960s and have been revitalized by recent advancements in robotics. The field now integrates tools from online algorithms, mobile agent distributed computing, operations research, discrete mathematics, and optimization.

Theoretically, autonomous mobile agents are modeled as volumeless entities navigating discrete domains (networks or graphs) or continuous domains (2D or 3D Euclidean spaces). In continuous domains, possible target locations shape the geometric search areas, including lines, disks, circles, squares, rectangles, and triangles. Significant progress has been made, yielding elegant distributed algorithms for mobile agent computing and technical arguments for impossibility results. However, achieving tight upper and lower bounds remains challenging, with many problems still lacking optimal solutions.

This work is the first to systematically explore a continuous search space with discrete target locations. We study priority evacuation, an asymmetric search problem where a distinguished agent, the Queen, must reach the hidden item, aided by other agents, the Servants. The possible target locations form regular $n$-gons, and we provide upper and lower bounds, often tight, for various $n$ values and numbers of Servants. This problem has been previously studied for the line with $1$ Servant and the disk with any number of Servants. As a result, we improve the best lower bounds for the disk evacuation problem with $1$ and $2$ Servants. Additionally, we improve the best lower bounds known for the so-called $w$-weighted search problem on a disk. These improvements are based on new, and nearly tight bounds for the $w$-weighted search problem on $11$-gons and $12$-gons.

§.§ Related Work

The field of search problems dates back to the 1960s and has since developed a robust theoretical framework, detailed in various books and surveys [1, 2, 3, 28, 40, 51]. Initially, the focus was on optimizing objectives for single searchers [9, 52], but with the rise of robotic fleets, multi-searcher problems have gained prominence [22, 54].

The linear search problem is a classic example studied extensively for both single [6, 13] and multiple searchers [16]. Variations aim at minimizing the weighted average of search completion times [49]. Other one-dimensional search settings include searching along rays [14], anomalous terrains [35], graphs [5], and for multiple objects [12, 21].

In the past decade, attention has shifted to two-dimensional search problems, exploring domains like polygons [39], disks [22], planes [38], regular polygons [26], equilateral triangles and squares [7, 18, 34, 43], arbitrary triangles [44], and $\ell_p$ unit disks [48]. Variations involve different communication models and searcher specifications, such as face-to-face communication [15, 30, 36], varying searcher speeds [8], searching for multiple exits [54], and diverse communication capabilities [31, 41, 42]. Fault tolerance has also been studied, addressing issues like faulty agents and Byzantine faults in [10, 11, 23, 29] and in [32, 33, 47, 55].

Research has also explored non-standard objectives, including multi-objective search problems [17], competitive algorithmic approaches [4], and trade-offs between information and cost [53]. Studies have also considered time and energy
trade-offs [24, 25], and search-and-fetch problems in two dimensions [45, 46].

§.§ Closely Related Work, Improvements and Significance of New Contributions

Our work extends and improves a series of studies on search-type problems where possible hidden target locations lie on a unit disk, assuming instantaneous communication between agents under the wireless model. The initial study designed search trajectories to minimize the time for the last agent to reach the target, known as the disk evacuation problem [22]. This foundational study yielded mostly optimal results.

Subsequent research focused on designing search trajectories for a distinguished agent to evacuate quickly, with other agents, termed Servants, assisting. These disk priority evacuation problems were examined for $k=1,2,3$ Servants [26] and for $k\geq 4$ Servants [27]. Notably, significant gaps existed between the upper and lower bounds. The lower bound of 4.38962 for $k=1$ Servant relied on lower bounds for evacuating the significant agent from a $6$-gon, with the $n$-gon (as $n$ approaches infinity) approximating the disk priority evacuation problem.[The possible target placements on a disk are uncountable many, whereas for every $n$, the vertices of an $n$-gon are finite many. However, for every $\epsilon>0$, there is large enough $n$  so that every target placement on the disk is no more than $\epsilon$ away from a target placement on the $n$-gon.]
A tight upper bound for the $6$-gon priority evacuation was also provided.

An extension introduced in [50] considered the $w$-weighted group search on a disk with two agents ($w \in [0,1]$), where $w=0$ corresponds to the disk priority evacuation problem with $k=1$ Servant. The paper provided upper and lower bounds, with gaps diminishing as $w \rightarrow 0$. Their lower bound relied on $w$-weighted group search bounds on $n$-gons with $n \leq 7$, but no upper bounds for the discrete domain were reported. They also provided lower bounds for the $n$-gon priority evacuation problem with $n \leq 9$, improving the [26] lower bound to 4.46798 for the disk priority evacuation problem with $k=1$ Servant.

We derive a number of improved results:
(i) We provide upper and lower bounds for the $n$-gon priority evacuation problem with one Servant for $n \leq 13$, achieving nearly tight or tight results (previously only $n=6$ upper bounds and $n \leq 9$ lower bounds were known).
(ii) We study priority evacuation on $n_k$-gons for $k=2,3,4$ Servants, with $n_2 \leq 11$, $n_3 \leq 9$, and $n_4 \leq 10$, offering tight or nearly tight bounds. No prior results were known.
(iii) We improve the best lower bound for the disk priority evacuation problem with $1$ Servant from 4.46798 [50] to 4.64666.
(iv) We present the first improved lower bound for the disk evacuation problem with $2$ Servants from 3.6307 [26] to 3.65332.
(v) We improve the lower bounds for the disk $w$-weighted group search problem of [50] for all $w \in [0,0.7]$.
(vi) Motivated by the fact that the previous improved lower bounds were obtained as corollaries to the
$w$-weighted search problem on $n$-gons for $n=12$, we are the first to provide upper and lower bounds for the $11$-gon and the $12$-gon $w$-weighted evacuation problem for all $w \in [0,1]$, achieving tight or nearly tight results.

Our priority evacuation upper bounds are accompanied with search trajectories that resemble the best trajectories known for disk evacuation problems. Despite remaining gaps, this gives further indication that the known search trajectories may be optimal.

§.§ Paper Organization

In Section <ref>, we introduce key notation and terminology.
The formal definition of the problems we study, along with a formal description of our results can be found in Section <ref>. These results pertain to the $n$-gon priority evacuation problem with $k$ Servants nk, the disk priority evacuation problem with $k$ Servants k, the $n$-gon $w$-weighted search problem wn, and the disk $w$-weighted search problem w. The proofs of our results for all these problems appear in the subsequent sections.
Indeed, in Section <ref> we present formulations and relaxations for solving nk (the same machinery is also applied later to wn).
Then, in Section <ref> we discuss lower bounds on nk, and in Section <ref> upper bounds on the same problem.
Equipped with the lower bounds on nk, we show improved lower bounds on k, $k=1,2$ in Section <ref>. Then, in Section <ref> we justify the reported upper and lower bounds for problems wn and w. Finally, in Section <ref>, we conclude with some open questions.
Due to space limitations, many details have been moved to the appendix, and proper citations can be found for any omissions.

nk		n-gon priority evacuation with k Servants

k		disk evacuation with k Servants

w		weighted disk evacuation with 1 servant, with weight $w=0.5$

wn	n-gon weighted evacuation with 1 servant and weight $w=0.5$

0n = n1

§ PRELIMINARIES

§.§ Notation & Terminology

We use $\|\cdot\|_2$ to denote the Euclidean norm over $\mathbb{R}^2$. For $n\in \mathbb{N}$, let $\mathcal{P}_n$ denote the set of all permutations of $\{1,\ldots, n\}$. We define $\mathcal{B}^n_k$ as the set of all $n$-dimensional $(k+1)$-ary strings, i.e., $\{0,\ldots,k\}^n$, so $\mathcal{B}^n_1$ is the set of $n$-dimensional binary strings.

We use the term unit speed trajectory to refer to a continuous and differentiable function $\tau: \mathbb{R}_+ \to \mathbb{R}^2$ that induces a speed of at most 1. Specifically, if $\tau(t)=(\tau_1(t), \tau_2(t))$, then $\tau(t)$ is 1-Lipschitz continuous, meaning it satisfies $\| \tau(t_1)- \tau(t_2) \|_2 \leq |t_1 - t_2|$ for all $t_1, t_2 \in \mathbb{R}_+$.

In this work, $n$-gons exclusively refer to regular $n$-polygons inscribed in circles of radius 1. For convenience, we consider $n$-gons and the circle as embedded in the 2-dimensional Euclidean space. Thus, for a fixed $n$, the vertices of the $n$-gon are represented as
V^n_i := \left( \cos\left(2i\pi/n\right), \sin\left(2i\pi/n\right) \right),
i=1,\ldots, n.
It follows that for all $i,j \in \{1,\ldots,n\}$, we have
\|V^n_i - V^n_j\|_2 = 2 \sin\left( \tfrac{\pi}{n} \cdot \mathrm{mod}(|i-j|,n) \right),
and that the edges of the $n$-gon have length $2 \sin\left( \tfrac{\pi}{n} \right)$.

Parameter $n$ will denote the number of vertices of the $n$-gon, and $k$ will denote the number of Servants in our search problem involving $k+1$ mobile agents. The following set will be useful in our later formulations:
\mathcal{X}^n_k := \{0,\ldots,k\} \times \{1,\ldots,n\},
which corresponds to pairs of agents and $n$-gon vertices in the multi-agent search problem we are considering.

§.§ Problem Definition & Main Contributions Made Formal

Polygon Priority Evacuation:
We study the Polygon Priority Evacuation Problem nk on $n$-gons with $k$ Servants, a multi-agent search problem where the hidden target lies in a discrete domain, specifically $n$-gons. In this search problem, the host space is the Euclidean 2-dimensional space (modeled for convenience as a Cartesian plane), and the searchers are $k+1$ unit speed agents. Among these agents, one is labeled $0$ and is distinguished as the Queen, while the other agents, labeled $1,2,\ldots,k$, are called Servants. We consider a regular $n$-gon with vertices $V^n_i$, $i=1,\ldots,n$, inscribed in a unit radius disk and centered at the origin $O=(0,0)$. The orientation of the $n$-gon is known to the agents, i.e. to the algorithm.

Agent movements are determined by unit speed trajectories $\tau_i:\mathbb{R}_+ \to \mathbb{R}^2$, where the initial placements of the agents $\tau_i(0)$ are algorithmic choices, $i=0,\ldots,k$. The agents' movements are feasible if for each polygon vertex $j \in \{1,\ldots,n\}$, there exists an agent $i \in \{0,\ldots,k\}$ and time $t'=t'(j) \in \mathbb{R}_+$ such that $\tau_i(t') = V^n_{j}$ (i.e., every polygon vertex is eventually visited by some agent). For each polygon vertex $j \in \{1,\ldots,n\}$, we denote by $T_j$ the smallest such $t'$, calling it the visitation time of vertex $j$. The cost of the feasible solution $\{\tau_i\}_{i \in \{0,\ldots,k\}}$, referred to as the priority evacuation cost, is defined as
\max_{j \in \{1,\ldots,n\} }
\left\{
T_j +\| V^n_j - \tau_0( T_j ) \|_2
\right\}
and the objective is to minimize that cost.

Next, we provide a high-level explanation of the above model. By definition, the agents' specifications correspond to the so-called wireless communication model, which allows them to share information instantaneously. All $k+1$ agents contribute to searching for a hidden target, often referred to as the exit, located at one of the vertices of the $n$-gon.

The optimal solution to the problem, should the position of the exit be known, is $1$. However, in this online problem, the hidden exit is identified only when any of the $k+1$ agents visit the corresponding $n$-gon vertex (unknown to the agents), and subsequently, all agents are notified accordingly. For an exit placement, the cost of a solution is given by the time that the Queen evacuates, i.e., when she reaches the hidden exit, ignoring thereafter the whereabouts of the $k$ Servants.
Compatible with worst-case analysis, the overall performance of a feasible solution is defined as the worst-case Queen evacuation time over all exit placements.

In this work, we provide upper and lower bounds on nk with $k=1,2,3,4$ Servants over $n$-gons, and for various values of $n$. All our results are summarized in the next theorem, which is our first main contribution.

[Our positive and negative results provide only the first 5 digits of our computations, even though our numerical evaluations extend to at least 10 digits of accuracy. Often, we also have closed-form expressions, involving algebraic and trigonometric operations, that describe these numbers. However, for larger values of $n$, these expressions become too extensive to be informative, and hence we omit them.]

For $k=1,2,3,4$, and for various values of $n$,
Priority Evacuation Problem nk can be solved in time $u^n_k$.
Also, no algorithm for the problem has evacuation cost less than $l^n_k$.
The upper bounds $u^n_k$, and the lower bounds $l^n_k$ appear in Table <ref>.
Moreover, for $n$-gons $n=12,13$, we have
$u^{12}_1 =3.38511$, $l^{12}_1 =3.38486$,  and $u^{13}_1 =3.36362$, $l^{13}_1 =3.36361$.

$k$$n$     3     4     5     6     7     8     9     10     11
1      1.73205
1.      2.14626
1.01175      2.71441
1.       2.86603
1.       2.97391
1.00768       3.02649
1.00776       3.21891
1.       3.21549
1.0089       3.35919
2      1.00000
1.       1.70711
1.       1.90211
1.       2.00000
1.       2.14027
1.02726       2.25951
1.00968       2.37176
1.00802       2.38956
1.00482       2.50211
3      1.00000
1.       1.00000
1.       1.55017
1.00736       2.00000
1.0718       1.86777
1.01361       1.91342
1.       1.91362
1.03393       NA
NA       NA
4      1.00000
1.       1.00000
1.       1.00000
1.       1.5000
1.       1.64960
1.       1.76537
1.04507       1.68404
1.00911       1.65153
1.02070       NA

Summary of our upper and lower bound results for nk.
Every entry is populated with the upper bound $u^n_k$, the lower bound known $l^n_k$ , and the corresponding optimality gap, i.e. $u^n_k/l^n_k$. Therefore a reported gap of $1.0$ corresponds to an optimal result. For $n=12,13$, we only have results for n1, and we report them separately.
However, for these $n$-gons, the optimality gaps are $1.00007$ and $1.0$, respectively.
The only values known before were $u^6_1$, and $l^n_1$ for $n\leq 9$.

Disk Priority Evacuation:
Our second contribution pertains to improved lower bounds for the disk priority evacuation problem with $k$-Servants, which we denote by k.
The problem k was first considered in [26] for $k=1,2,3$ Servants, and in [27] for $k \geq 4$ Servants. For completeness, we include the definition of the problem by adapting the description of nk. The primary difference between the two problems is that in the disk evacuation problem, the hidden exit can lie anywhere on the perimeter of the unit radius disk.
Moreover, the agents' starting positions are at the origin, i.e., for the feasible unit speed trajectories $\tau_i:\mathbb{R}_+ \to \mathbb{R}^2$, we have $\tau_i(0)=O=(0,0)$, for $i=0,\ldots,k$. We quantify the positioning of the exit by some $\theta \in [0,2\pi]$, corresponding to the exit placement
P_\theta := \left( \cos(\theta), \sin(\theta) \right).
Then, for a feasible solution $\{\tau_i\}_{i=0,\ldots,k}$, we require that for each $\theta$, there exists an agent $i \in \{0,\ldots,k\}$ and a time $t' \in \mathbb{R}_+$ such that $\tau_i(t') = P_\theta$. For each exit placement $\theta$, we denote by $T({\theta})$ the smallest corresponding time $t'$. The evacuation cost of the feasible solution $\{\tau_i\}_{i \in \{0,\ldots,k\}}$ is then defined as
\sup_{\theta \in [0,2\pi)}
\left\{
T({\theta}) + \| P_{\theta} - \tau_0(T({\theta})) \|_2
\right\}
and the objective is to minimize this cost.

Our second main contribution are new lower bounds for k which are summarized in the next statement.

No algorithm for k has evacuation cost
less than $4.64666$ for $k=1$,
and less than $3.65332$ for $k=2$.

For an informative perspective, we summarize in Table <ref>
all previous best upper and lower bounds known for k.

$k$		    $1$ 						    $2$ 						    $3$ 						    $4$
Upper Bound     $4.81854$ [26]	     $3.8327$ [26]	    $3.3738$ [26]			     3.30129 [27]
Lower Bound     $4.56798$ [50]	     $3.6307$ [26]	    $3.2017$ [26]	     $2.91322$  [27]

Summary of best upper and lower bound results known for k, prior to our work.
Contrast the upper and lower bound values to the improved lower bounds of Theorem <ref>.

Polygon and Disk $w$-Weighted Search
Our third contribution pertains to a search problem where the objective is the arithmetic weighted average of the termination times of $2$ mobile agents, first considered in [50]. In this problem, the hidden item lies either in the unit radius disk and the $2$ agents start from the center of the disk, or it lies on a vertex of an $n$-gon, and the initial placement of the $2$ agents is an algorithmic choice. Having the feasible trajectories identified exactly as in n1 and 1, the cost of the solution is instead defined as the arithmetic weighted average of the times that the $2$ agents reach the hidden item. Indeed, for each $w\in [0,1]$ and feasible trajectories $\tau_0,\tau_1$, and for the exit placement $x$, let $T_i(x)$ denote the time that agent $i=0,1$ reaches $x$. The $w$-weighted search cost for input $x$ is defined as $(T_0(x) +w\cdot T_1(x))/(1+w)$.

For the $n$-Gon $w$-Weighted Search Problem wn, the objective is to minimize $\max_x \tfrac{T_0(x) +w\cdot T_1(x)}{1+w}$, where $x$ ranges over all $n$ vertices of the $n$-gon.
Similarly, for the Disk $w$-Weighted Search Problem w, the objective is to minimize $\sup_x \tfrac{T_0(x) +w\cdot T_1(x)}{1+w}$ and the supremum is considered over all points $x$ on the perimeter of the disk.
From these definitions, it is immediate that setting $w=0$ results in the priority evacuation objective with $1$ Servant, i.e. that
0n is equivalent to problem n1,
and that 0  is equivalent to problem 1.

nk		n-gon priority evacuation with k servants

k		disk evacuation with k servants

w		weighted disk evacuation with 1 servant, with weight $w=0.5$

wn	n-gon weighted evacuation with 1 servant and weight $w=0.5$

0n = n1

The main contribution pertaining to the $w$-weighted search objective is an improvement to the previously best lower bound known for the disk. The result is obtained numerically, and is quantified in the next statement.

Each of the purple and brown curves in Figure <ref> is a lower bound to the w, for all $w\in [0,1]$.[The lower bounds were computed for values of $w$ from $0$ to $1$ with step size $0.01$.]

Known upper bounds compared to our improved lower bounds for w.
The blue curve (labeled $a$) depicts the best upper bound known [50]. The green curve (labeled $c$) depicts the previously best lower bound known, by a reduction to w7. The orange line (labeled $b$) depicts a universal lower bound of $1+\pi$ also proved in [50].
The purple and black curves (labeled $d,e$, respectively) are new lower bounds on w by a reductions to w11  and w12, respectively (hence the maximum of them applies).
The lower bounds were calculated for values of $w\in[0,1]$ starting from $0$ and with step size $0.01$.

As indicated before, the lower bounds on w are obtained via reductions to wn.
The best lower bound achieved as $w$ ranges in $[0,1]$ were obtained for $n=11,12$. We are therefore motivated to report upper and lower bounds for w11 and w12, demonstrating that our analysis is (nearly) tight. This is quantified in the following statement.

For values of $w\in [0,1]$, Figure <ref> shows upper and lower bounds
to the wn problem, for $n=11,12$.
[The lower bounds were computed for values of $w$ from $0$ to $1$ with step size $0.01$.
The upper bounds were computed for values of $w$ from $0$ to $1$ with step size $0.02$, hence we only depict them as points.

Upper and lower bound obtained for w11 (left hand-side) and w12 (right hand-side). Starting from $w=0$, the lower bounds were obtained with $w$ step size of $0.01$ and the upper bounds with $w$ step size of $0.02$.

§ FORMULATIONS & RELAXATIONS TO NK

Our contributions are based on the observation that the optimal solution to the nk problem can be found using a Non-Linear Program (NLP), assuming we know the order in which the polygon vertices are visited and the identities of the agents who first visit those vertices. This idea was first implemented in [50] for $k=1$ Servants, primarily to provide lower bounds for 1, the disk priority evacuation problem with 1 Servant, and for the disk $w$-weighted search problem. Here, we extend this approach to provide upper and lower bounds also for nk for $k=2,3,4$ and various values of $n$, improving the known lower bounds for 1 and introducing the first lower bound improvements for k for $k=2$.

First, we introduce some terminology to clarify the notation. For any feasible solution $\{\tau_i\}_{i \in \{0,\ldots,k\}}$ to nk, each vertex $V^n_i$ of the $n$-gon is visited by some agent. Let permutation $\rho \in \mathcal P_n$ be the ordered list of vertices by their visitation times, where vertex $V^n_{\rho_i}$ has the $i$'th smallest visitation time (ties are broken arbitrarily). Define $s \in \mathcal B^n_k$ as the $(k+1)$-ary string where $s_i$ is the label of the agent visiting $\rho_i$. Thus, the corresponding feasible solution to nk is called an $(s,\rho)$-algorithm. We begin with the following observation.

The optimal solution to nk is an $(s,\rho)$-algorithm, for some $s\in \mathcal B^n_k$ and $\rho \in \mathcal P_n$.

For fixed $s,\rho$, we show next how to find the optimal $(s,\rho)$-algorithm to nk.

To that end, consider the following Non Linear Program (NLP) on variables $t_1, \ldots, t_n$ and $d_{r_1,r_2}$, where $r_1,r_2 \in \mathcal X^n_k $.

\begin{align}
\min &~\max_{j \in \{1,\ldots, n\}}
\left\{
t_j + d_{(0,j),(s_j,j)}
\right\}
\tag{$\textsc{NLP}^n_k(s,\rho)$}  \label{equa:nlp}   \\
s.t.: ~& t_{j+1} -t_j  \geq d_{(i,j+1),(i,j)}, ~~j\in \{0,\ldots,n\}, i\in\{0,\ldots,k\}  \label{eq: speed const} \\
%& d_{(s_j,j),(s_k,k)} = \| V^n_{\rho_j} - V^n_{\rho_k} \|_2, ~~j,k \in \{1,\ldots,n\} \notag \\
& d_{(i,0),(s_l,l)} = 1, ~~l \in \{1,\ldots,n\}, i\in\{0,\ldots, k\} \label{eq: initial placement} \\
& d_{(s_j,j),(s_l,l)} = 2 \sinn{ mod(|\rho_j-\rho_l|,n) \cdot \tfrac{\pi}n  }, ~~j,l \in \{1,\ldots,n\} \label{eq: fixed dist const} \\
& t_0=-1, t_1 = 0 \label{eq: fixed time const} \\
& \left(\mathcal X^n_k,d \right)~\textrm{is a metric space}  \label{eq: metric const} \\
& \left(\mathcal X^n_k,d \right)~\textrm{is isometrically embeddable to}~ \left(\reals^2, \|\cdot\|_2 \right) \label{eq: emb const}
\end{align}

eq: speed const

eq: initial placement

Fix $s\in \mathcal B^n_k$ and $\rho \in \mathcal P_n$.
Then the optimal value to <ref> equals the cost of the optimal $(s,\rho)$-algorithm to nk.[For our lower bound arguments, we only need that the the optimal value to <ref> is a lower bound to the cost of the optimal $(s,\rho)$-algorithm.]

First we show how to find a feasible solution to <ref> starting from a feasible $(s,\rho)$-algorithm to nk.
For this, consider an $(s,\rho)$-algorithm to nk along with its corresponding trajectories $\{\tau_i\}_{i \in \{0,\ldots,k\}}$ (i.e. feasible unit speed trajectories).
We design a feasible solution to <ref> with objective cost equal to $c$.
For convenience, we modify the definition of nk so that all agents start from the centre of the $n$-gon, and then we subtract 1 from the total evacuation time.
Since the $n$-gon is inscribed in a unit radius disk, and the first agent will need to reach the first vertex as soon as possible, the two problems are equivalent.
This is done by setting $t_0=-1$, and $0$ in the index refers the $0$'th visited location, which in this case is the origin, hence all agents are equidistant from the $n$-gone vertices, satisfying (<ref>).
More generally, the intended meaning of the variables is that $t_i$ equals the time that vertex $\rho_i$ (i.e. the $i$-th in time order visited vertex) is visited by agent $s_i\in \{0,\ldots,k\}$.
Moreover the execution of an algorithm produces movements for every placement of the exit. Since the exit is not known to the algorithm, two executions of the algorithm
are identical for as long as the exit is not visited yet.

For this reason, we consider an execution of the algorithm in which only the last visited vertex is the one with the exit.
At time $t_j$, we consider point $A_{i,j}\in \reals^2$ to be the positioning of agent $i$, when vertex $s_j$ is visited.
Clearly we have that these points, equipped with the $\ell_2$ metric define a metric space, by definition, embeddable in $(\reals^2,\ell_2)$.
Moreover, denote the distance of points $A_{i,j}, A_{i',j'}$ by $d_{(i,j),(i',j')}$.

With these evaluations in mind, we observe that constraints (<ref>) are satisfied because each agent is moving at speed at most 1.
Constraint (<ref>) is satisfied because each vertex is visited by some agent, and the distance between the positions of the corresponding agents when they visit these vertices equals the distances between these vertices (in other words, because $A_{s_j,j} = \rho_j$). And indeed, $2 \sinn{ mod(|\rho_j-\rho_k|,n) \cdot \tfrac{\pi}n  }$ equals the distance of $n$-gon vertices $\rho_j,\rho_l$.

Next observe that without loss of generality, we may assume that at the beginning of the execution of the search algorithm, some agent lies on some vertex (recall that the initial positioning of the agents is an algorithmic choice).
If not, we can reset the clock when the first vertex is visited, resulting in lower termination cost.
Therefore, constraint (<ref>) is satisfied as well. As for constraints (<ref>), it is satisfied by construction, while constraint (<ref>) is redundant.

We are left to argue that the objective quantifies correctly the worst case cost. For this we observe that if the exit is placed at the $j$-th visited vertex, which by definition is done by agent $s_j$ at time $t_j$, then the Queen at point $A_{0,j}$ needs to travel $\|A_{0,j}-A_{s_j,j}\|_2=d_{(0,j),(s_j,j)}$ to go the exit.
Hence, $t_j + d_{(0,j),(s_j,j)}$ measures correctly the running time of the search algorithm, and the objective of the NLP correctly considers the maximum, among all placements of the exit, as the overall termination time.

Second we show that an optimal solution to <ref> corresponds to a feasible trajectory for nk.
For this, we note that constraints (<ref>), (<ref>) and (<ref>) identify an embedding of the regular $n$-gon on the 2-dimensional Cartesian plane,
where also by (<ref>), all agents are initially placed at its centre.

We now design the trajectories for the $k+1$ agents, having them all starting from the centre of the $n$-gon, and then subtracting 1 from the evacuation cost
(this is equivalent to allowing agents starting from anywhere within the unit disk).
Using the embedding (<ref>) implied by (<ref>), we mark on the plane points that we identify as $(i,j)$, for each agent $i\in \{0,\ldots,k\}$ and each time interval $j\in\{0,\ldots,n\}$.
Note, have one time interval for each vertex being discovered, and an additional one, for the initial placement of the agents who “discover” the origin.
We let agent $i$ move along line segments with endpoints $(i,j)\rightarrow (i,j+1)$, $j=0,\ldots,n-1$. These trajectories visit indeed all vertices of the $n$-gon,
where specifically, due to the definition of configuration $s\in \mathcal B^n_k$ and $\rho \in \mathcal P_n$ and constraint (<ref>).
It remains to observe that (<ref>) imposes that these trajectories are indeed at most unit speed, showing this way that the trajectories are feasible to nk.
Now observe that in an optimal solution, and for each $j=0,\ldots,n$, at least one of the constraints (<ref>) has to be tight for some $i$, as otherwise one would be able to reduce the value of the objective.
Effectively, this shows that each $t_i$ can be thought as the time that vertex $\rho_i$ is visited, hence also showing that the objective <ref> quantifies correctly the cost of the derived feasible trajectory.

We note that while formulation <ref> can be effectively coded as an NLP in any programming language, solving it optimally remains a challenge.
Due to the non-convex nature of the program, unless a sophisticated method specifically tailored to the NLP is implemented, it is impossible to guarantee a global solution.
Indeed, solvers can only ensure that the returned solution is a local optimizer.
Motivated by that, we relax <ref> into a tracktable optimization problem. This idea is borrowed again from [50].

The relaxation of <ref> where constraint (<ref>) is omitted (denoted as $\textsc{LP}^n_k(s,\rho)$), is a Linear Program.

The linearization of the objective of <ref> is possible by the standard trick of replacing the objective by that of minimizing $y$, where $y$ is a brand new variable, along with the constraints

y \geq t_j + d_{(0,j),(s_j,j)}, ~j=1,\ldots,n.

Hence, it remains to show that the requirement that $\left(\mathcal X^n_k,d \right)$ is a metric space, is actually a polyhedron in variables $d$. This is indeed possible, since $\mathcal X^n_k$ is finite, and variable $d$ is indexed by $X^n_k \times X^n_k$. That is, we may think of $d: \mathcal X^n_k \times \mathcal X^n_k \mapsto \reals$ as a metric, hence identified by the properties that

- $d_{r_1,r_2} \geq 0$, for $r_1,r_2 \in \mathcal X^n_k$, and inequality is tight for  $r_1=r_2$,

- $d_{r_1,r_2} = d_{r_2,r_1}$, for $r_1,r_2 \in \mathcal X^n_k$

- $d_{r_1,r_2}+d_{r_2,r_3} \geq d_{r_1,r_3}$, for $r_1,r_2,r_3 \in \mathcal X^n_k$.

The advantage of considering $\textsc{LP}^n_k(s,\rho)$ is that the optimization problem can be solved efficiently, and moreover, every solution (even numerical and computer-based) comes with a certificate of global optimality, unlike what can be accomplished for the NLP.
For given $s,\rho$, let $obj^n_k(s,\rho)$ be the optimal solution to $\textsc{LP}^n_k(s,\rho)$.
Since the LP is a relaxation of <ref>, we see that $obj^n_k(s,\rho)$ is a lower bound on the optimal solution to <ref>, which is also a lower bound on the evacuation cost of the optimal $(s,\rho)$ algorithm for nk.
Since also the optimal solution to nk is some $(s,\rho)$-algorithm, we obtain the following.

The optimal cost for solving nk is at least $\min_{s,\rho} obj^n_k(s,\rho)$, where $obj^n_k(s,\rho)$ denotes the optimal solution to $\textsc{LP}^n_k(s,\rho)$.

§ LOWER BOUNDS ON NK

We present our findings on the lower bounds for the polygon priority evacuation problem nk for $k=1,2,3,4$ and various values of $n$.
This section serves as the proof of the lower bounds mentioned in Theorem <ref>.
For each $n$ and $k$, our results for nk are obtained by applying Corollary <ref>, specifically by solving $\textsc{LP}^n_k(s,\rho)$ for all $s \in \mathcal B^n_k$ and $\rho \in \mathcal P_n$, and reporting the smallest value. Our work extends the results presented by [50], which covered only the case of $k=1$ and $n \leq 9$.

A brute force consideration of Corollary <ref> suggests that one needs to solve $c_{n,k}:=n! (k+1)^n$ linear programs, each with $\Omega\left( n^2k^2 \right)$ variables and $\Omega\left( n^3k^3 \right)$ constraints. The number of configurations presents a challenge, reaching $c_{9,1}=1.8 \cdot 10^8$ LPs for $n=9$ and $k=1$, the limit configuration considered in [50]. Part of our contribution was to efficiently handle the $c_{n,k}$ configurations. The strategies implemented to reduce the number of configurations include:

* Assuming that the first visited vertex is vertex 1 and that the second visited vertex is $j \leq \lceil n/2\rceil$.

* Omitting configurations that provably result in weak lower bounds, based on the necessity for agents to visit the vertices suggested by configuration $(s,\rho)$, and omitting the last evacuation step by the Queen. For this we use the following observation.

The cost of an optimal priority  algorithm on the $n$-gon with $k$ Servants does not exceed $\min\left\{1+\left(\lceil\tfrac{n}{k}\rceil-1\right)e_n,2+\left(\lceil\tfrac{n}{k+1}\rceil-1\right)e_n\right\}$.

It suffices to provide two naive evacuation algorithms $\mathcal{A}_1$ and $\mathcal{A}_2$ with costs at most $1+\left(\lceil\tfrac{n}{k}\rceil-1\right)e_n$ and $2+\left(\lceil\tfrac{n}{k+1}\rceil-1\right)e_n$ respectively, where $e_n$ is the length of a regular $n$-gon inscribed in a unit radius circle.

For algorithm $\mathcal{A}_1$, the Queen starts at the origin and each of the $k$ Servants start at vertices of the $n$-gon, spaced as “evenly” as possible.
The Servants move clockwise along a shortest path to the next adjacent vertex in the $n$-gon until every vertex has been searched (and hence the exit is found).
Then, the Queen moves to the exit, which takes time $1$. No Servant will need to search more than $\lceil\tfrac{n}{k}\rceil$ distinct vertices of the $n$-gon, so the exit is found in time at most $\left(\lceil\tfrac{n}{k}\rceil-1\right)e_n$ (recall that each Servant searches a vertex at time $0$ and moving to an adjacent vertex can be done in time $e_n$).
Hence, the cost of $\mathcal{A}_1$ is at most $1+\left(\lceil\tfrac{n}{k}\rceil-1\right)e_n$.

For algorithm $\mathcal{A}_2$, each agent (including the Queen) starts on a vertex of the $n$-gon, spaced as “evenly” as possible.
The agents move clockwise along a shortest path to the next adjacent vertex in the $n$-gon until every vertex has been searched.
Then, the Queen moves to the exit, which takes time at most $2$, since the worst case scenario is that the Queen is opposite the exit when it is found.
Since there are $k+1$ agents searching for the exit, no agent will need to search more than $\lceil\tfrac{n}{k+1}\rceil$ distinct vertices of the $n$-gon, so the exit is found in time at most $\left(\lceil\tfrac{n}{k+1}\rceil-1\right)e_n$. Hence, the cost of $\mathcal{A}_2$ is at most $2+\left(\lceil\tfrac{n}{k+1}\rceil-1\right)e_n$.

Given certain sub-optimal permutations $\rho$ and identity strings $s$, Lemma <ref> can be used to quickly determine their sub-optimality. In particular, if the trajectory of any one agent is of length greater than the cost of $\mathcal{A}_1$ or $\mathcal{A}_2$, then no $(s,\rho)$-algorithm can be optimal, and hence can be omitted when computing lower bounds.

* Considering only strings $s \in \mathcal B^n_k$, for which if the Queen visits two vertices at consecutive time stamps, then no other Servant visits any vertex afterwords (since it is always better than Servants should visit their assigned vertices without breaks).

* Considering that Servants are identical, thus making configurations invariant under the renaming of Servants.

We combined these strategies with a practical implementation for solving the LPs using Julia's JuMP Clp interface, an efficient open-source linear programming solver [19, 37].
Each LP solution comes with a proof of optimality, quantified by a dual gap, ensuring accuracy to at least 10 decimal digits.
Additionally, where applicable, we preset specific variables to known optimal values (e.g., the visiting times of initially visited vertices by distinct Servants are zero, as Servants start at polygon vertices without loss of generality).
This technique significantly reduced the running time for many instances. Most importantly, we processed the different LPs using parallel threading, always tracking the tentatively lowest value achieved. For subsequent configurations, we solved the corresponding LP only if the cost of visiting the polygon vertices by the agents, as per the configuration (excluding the final evacuation cost), was lower than the tentative lowest value, further expediting the running time of our numerical calculations.
These strategies allowed us to handle values of $(n,k)$ as high as $(13,1)$ or $(10,4)$, corresponding to $5.1 \cdot 10^{13}$ and $3.5 \cdot 10^{13}$ configurations, respectively. However, these methods were insufficient to address other values of $(n,k)$ such as $(10,3)$ with seemingly fewer $c_{10,3}= 3.8 \cdot 10^{12}$ configurations. We suspect that for certain values of $n$ and $k$, the naive bounds used to avoid solving certain LPs were not stringent enough.

In Tables <ref>, <ref>, <ref> and <ref>
below, we summarize the findings for computing $l^n_k := \min_{s,\rho} obj^n_k(s,\rho)$, where $obj^n_k(s,\rho)$ denotes the optimal solution to $\textsc{LP}^n_k(s,\rho)$.
Specifically, we use $l^n_k$ as the reported lower bound for nk, as per Corollary <ref>.
For small values of $n$ we occasionally observe values of the LP which are provably lower than the universal lower bound of $1$. We explain this later, but we note that this is compatible with that the LP is a relaxation to the corresponding NLPs. Whenever this happen, we report the correct lower bound of $1$.
For each $n$ and $k$ for which this lower bound is reported, we also provide the minimizing configuration $(s,\rho)$, which is also used as guidance for our upper bound results later.
We report the minimum valued LP with 15 decimal digits, thus providing a numerical evaluation for the lower bound $l^n_k$ for nk.
For many of these values, and due to some tight results presented next, we have identified concrete representation of many of these numbers. For instance:
\min_{s,\rho} obj^5_2(s,\rho)= \sqrt{(5+\sqrt{5})/2} \approx 1.90211303
\min_{s,\rho} obj^5_3(s,\rho)= \sqrt{5-2\sqrt{5}}/2 \approx 1.53884176.
However, many of these numerical values have impractically long representations, and for this reason, we choose not to include them in this exposition.

Finally, as evident from the numerical values in Theorem <ref>, many of our lower bounds are matched or nearly matched with upper bounds.
Hence, provably, for some configurations $(s,\rho)$ (specifically those determining the lower bound for nk), we have that <ref> and $\textsc{LP}^n_k(s,\rho)$ have the same optimal solution, indicating that the relaxations exhibit no gap. Since the LP relaxation to the NLP was obtained as a metric embedding relaxation, by dropping the constraint of embeddability in $\reals^2$, and retaining the $\ell_2$ distances only between polygon vertices, one might be tempted to check whether the metric space of the optimal LP solutions is indeed embeddable in $(\reals^2, \ell_2)$.
This can be done efficiently by solving a Positive Semidefinite Program that computes the minimum distortion required to embed any given metric into $(\reals^2, \ell_2)$, with a distortion equal to 1 corresponding to affirmative embeddability. Moreover, a distortion equal to 1 would actually provide a matching upper bound without explicitly describing the evacuation algorithm. However the minimum possible distortion in many cases is provably greater than $1$, even when the metric is restricted to the positioning of the Queen alone. Therefore, this phenomenon provides a solid explanation as to why in many cases we were unable to provide matching upper and lower bounds.

$n$		    		$\min_{s,\rho} obj^n_1(s,\rho)$	   		$\rho$	   	$s$

3			   	1.7320508075688772			   	(1,2,3)	    (1,0,1)

4			   	2.121320343559643			   	(1,2,4,3)	    (1,0,1,0)

5			   	2.7144122731725724			   	(1,4,5,3,2)	    (1,0,1,0,0)

6$^{\star}$		    2.8660253779249727		   	(1,2,6,3,5,4)	    (1,0,1,0,1,0)

7$^{\star}$		    2.95125017805582		   	(1,2,3,7,4,6,5)	    (0,1,1,0,1,0,1)

8$^{\star}$		    3.003207375377086		   	(1,2,3,8,4,6,5,7)	    (0,1,1,0,1,0,1,0)

9$^{\star}$		    3.218913730099321		   	(1,2,9,3,8,4,7,5,6)	    (1,0,1,0,1,0,1,0,1)

10			    3.1871244937949434		   	(1,2,10,3,9,4,8,6,7,5)	    (1,0,1,0,1,0,1,0,1,0)

11			    3.3557769107573536		   	(1,2,3,11,10,4,9,5,8,6,7)	    (1,0,0,1,1,0,1,0,1,0,0)

12			    3.3848655006886306		   	(1,2,3,12,4,11,10,5,9,8,6,7)	    (1,0,0,1,0,1,1,0,1,1,0,1)

13			    3.3636191025088142		   	(1,2,13,3,4,12,5,11,6,7,9,8,10)	    (0,1,0,1,1,0,1,0,1,1,0,1,0)

Lower bounds for n1, i.e., $n$-gon priority evacuation with 1 Servant. Values of $n$ labeled with $^{\star}$ indicate known evaluations reported previously in [50].

$n$		    		$\min_{s,\rho} obj^n_2(s,\rho)$	   		$\rho$	    	$s$

3	   	0.8660254037844386	   	(1,2,3)	    (1,2,0)

4	   	1.7071067811865475	   	(1,2,3,4)	    (1,2,0,0)

5	   	1.9021130325903068	   	(1,2,3,5,4)	    (1,2,0,1,2)

6	   	1.9999999999999993 	   	(1,3,5,4,2,6)	    (1,2,0,2,1,0)

7	   	2.0834826998207037	   	(1,3,7,2,6,4,5)	    (1,0,2,1,2,0,2)

8	   	2.2378405106469064	   	(1,3,2,8,4,5,7,6)	    (1,2,0,1,2,2,1,0)

9	   	2.3528883263148823	   	(1,2,5,3,9,6,4,8,7)	    (1,2,0,2,1,0,2,1,1)

10	   	2.3781074994199956	   	(1,5,2,3,10,6,9,4,7,8)	    (1,0,2,2,1,0,1,2,0,1)

11	   	2.4629185509183094	   	(1,2,9,3,11,8,10,4,6,5,7)	    (1,2,0,2,1,0,1,2,0,2,0)

Lower bounds for n2, i.e., $n$-gon priority evacuation with 2 Servants. All results are novel.

$n$		    		$\min_{s,\rho} obj^n_3(s,\rho)$	   		$\rho$ 	   	$s$

3	   	0.8660254037844386	   	(1,2,3)	    (1,2,0)

4	   	1.0		   	(1,2,3,4)	    (1,2,3,0)

5	   	1.5388417685876266	   	(1,2,5,4,3)	    (1,2,3,0,2)

6	   	1.866025403784437	   	(1,3,5,4,6,2)	    (1,2,3,2,3,1)

7	   	1.8426953904169392	   	(1,3,6,2,4,7,5)	    (1,2,3,1,2,3,2)

8	   	1.9134171618254483	   	(1,5,3,8,4,2,7,6)	    (1,2,3,1,2,3,1,0)

9	   	1.8508331567966465	   	(1,2,4,6,5,3,9,8,7)	    (1,2,3,0,3,2,1,1,0)

Lower bounds for n3, i.e., $n$-gon priority evacuation with 3 Servants. All results are novel.

$n$		    		$\min_{s,\rho} obj^n_4(s,\rho)$	num	   		$\rho$		   	$s$

3	   	0.8660254037844386	   	(1,2,3)	    (1,2,0)

4	   	1.0 	   	(1,2,3,4)	    (1,2,3,0)

5	   	0.9510565162951532	   	(1,2,5,4,3)	    (1,2,3,4,0)

6	   	1.4999999999999991	   	(1,4,6,5,2,3)	    (1,2,3,4,1,2)

7	   	1.6495989607031372	   	(1,3,7,2,5,4,6)	    (1,2,3,4,0,2,3)

8	   	1.6892463972414653	   	(1,3,8,6,5,2,7,4)	    (1,2,3,4,4,2,3,4)

9	   	1.6688480396635432	   	(1,3,5,9,4,2,8,6,7)	    (1,2,3,4,2,1,4,3,3)

10	   	1.618033988749892	   	(1,4,5,9,3,6,10,2,7,8)	    (1,2,3,4,2,3,4,1,3,0)

Lower bounds for n4, i.e., $n$-gon priority evacuation with 4 Servants. All results are novel.

§ UPPER BOUNDS ON NK

For each $n,k$, we prove Theorem <ref> by presenting feasible search trajectories to nk for the $k+1$ agents and performing a worst case analysis. Due to the large number pairs $(n,k)$ for which we report results, we move all the details to Section <ref>. In this section we demonstrate our techniques by discussing the solution to 91, which is also one of the upper bounds that is provably optimal.
For this, we also standarize the notation we will use for all other upper bounds that we present in the Appendix.

When considering a solution to nk, we fix some $(s,\rho)\in \mathcal X^n_k $ and then we describe the $(s,\rho)$-algorithm together with its analysis based on a figure (depicting the trajectories) and a table giving trajectories' details and performing the worst case analysis. Next we describe the notation that is used in the figures and the tables, e.g.
Figure <ref> and Table <ref>.

Recall that permutation element $\rho_i$ denotes the $i^{th}$ discovered vertex, which is visited by agent $s_i\in \{0,\ldots,k\}$.
Servants move always at full speed $1$ over the prescribed vertices, and hence no further detail on their movements is required.
Their whereabouts are irrelevant after they have visited all their assigned vertices.
We denote the length of a regular $n$-gon edge inscribed in the unit radius disk as $e_n=2\sin(\pi/n)$, and we denote the origin by $\cal{O}$.
Vertices of the $n$-gon where previously denoted as $V^n_j$, $j=1,\ldots,n$.
In order to ease notation, we drop the superscript, whenever $n$ is clear from the context, and in our figures we simply write $V_j$.

We use the colour red to denote the trajectory of the Servant(s), while the colour blue is used to denote the trajectory of the Queen.
Moreover, we use square vertices to denote the placements of the exits which induce the maximum evacuation time for any given search trajectory.
We use a solid line to denote the trajectory the agents follow.
We use a dashed line to show when the Queen deviates from the prescribed trajectory to evacuate at an announced exit that yields the maximum evacuation time.

We let $t_i$ denote the first time when vertex $\rho_i$ is discovered by an agent.
We denote by $Q^{(i)}$ the location of the Queen at time $t_i$.
We use segments with endpoints of the form $Q^{(i)},Q^{(i+s)}$ to indicate that the Queen has stayed put at point $Q^{(i+s)}$ from time $t_{i+1}$ and until $t_{i+s}$
Also, the tables inlcude $d(Q^{(i)},Exit)$ which is the distance between the Queen and exit, when the exit is placed at vertex $\rho_i$.

The trajectories of the $(s,\rho)$-algorithms are formally given in tables.
For each $i \in \{1,\ldots,n\}$, we specify the location of the Queen at time $t_i$. Together with the Queen's distance to vertex $\rho_i$, they define the evacuation cost for the exit placement $\rho_i$.
Whenever the positioning of the Queen is not a vertex, or a self-evident point, we define it formally either as an abstract expression, or as the solution to a formal non-linear system (similarly to how upper bounds have been described for all previous positive results to priority evacuation problems).
In the reported trajectory tables, cost entries indicated by $*$ denote the worst case evacuation time for the provided trajectory, over all exit placements.
Now we discuss the solution details to 91.

[Upper Bound to 91]
For 91, we use $s=(1,0,1,0,1,0,1,0,1)$ and $\rho=(1,2,9,3,8,4,7,5,6)$, see also Figure <ref> and Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (7.7,6.4) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (1.7,9.8) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-5,8.7) ;
[fill=black] (c) circle (0.105) node [above] $V_3$;
(d) at (-9.4,3.4) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-9.4,-3.4) ;
[fill=black] (e) circle (0.105) node [below left] $V_5$;
(f) at (-5,-8.7) ;
[fill=black] (f) circle (0.105) node [below left] $V_6$;
(g) at (1.7,-9.8) ;
[fill=black] (g) circle (0.105) node [below right] $V_7$;
(h) at (7.7,-6.4) ;
[fill=black] (h) circle (0.105) node [below right] $V_8$;
(i) at (10,0) ;
[fill=black] (i) circle (0.105) node [above right] $V_9$;

[line width=0.25mm, black] (10,0)–(7.7,6.4)–(1.7,9.8)–(-5,8.7)–(-9.4,3.4)–(-9.4,-3.4)–(-5,-8.7)–(1.7,-9.8)–(7.7,-6.4)–(10,0);

at (a) (7.7,6.4) ;
[fill=red] (a) circle (0.25) node [below left] $S^{(2)}$;
at (i) (10,0) ;
[fill=red] (i) circle (0.25) node [below right] $S^{(4)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (h) at (7.7,-6.4) ;
[above right] at (h.south east) $S^{(5)}$;

[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (g) at (1.7,-9.8) ;
[below left] at (g.south east) $S^{(7)}$;

[line width=0.5mm, red, mid arrow] (7.7,6.4) – (10,0);
[line width=0.5mm, red, mid arrow] (10,0) – (7.7,-6.4);
[line width=0.5mm, red, mid arrow] (7.7,-6.4) – (1.7,-9.8);

at (b) (1.7,9.8) ;
[fill=blue] (b) circle (0.25) node [below] $Q^{(2)}$;
at (c) (-5,8.7) ;
[fill=blue] (c) circle (0.25) node [below right] $Q^{(4)}$;

(j) at (-8,2.8) ;
[fill=blue] (j) circle (0.25) node [right] $Q^{(5)}$;
at (d) (-9.4,3.4) ;
[fill=blue] (d) circle (0.25) node [below left] $Q^{(6)}$;
(k) at (-5.8,-0.9) ;
[fill=blue] (k) circle (0.25) node [right] $Q^{(7)}$;
at (e) (-9.4,-3.4) ;
[fill=blue] (e) circle (0.25) node [above left] $Q^{(8)}$;
at (f) (-5,-8.7) ;
[fill=blue] (f) circle (0.25) node [above right] $Q^{(9)}$;
[line width=0.5mm, blue, mid arrow] (1.7,9.8) – (-5,8.7);
[line width=0.5mm, blue, mid arrow] (-5,8.7) – (-8,2.8);

[line width=0.5mm, blue] (-8,2.8)  – (-9.4,3.4) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;
[line width=0.5mm, blue, mid arrow] (-9.4,3.4) – (-5.8,-0.9);
[line width=0.5mm, blue, mid arrow] (-5.8,-0.9) – (-9.4,-3.4);
[line width=0.5mm, blue, mid arrow] (-9.4,-3.4) – (-5,-8.7);

[dashed] [line width=0.5mm, blue] [-latex] (-8,2.8) – (7.7,-6.4);
[dashed] [line width=0.5mm, blue] [-latex] (-5.8,-0.9) – (1.7,-9.8);

A search trajectory for 91.
Trajectory details can be found in Table <ref>.
The Queen waits at $V_3$ for an amount of time such that the Queen arrives at $Q^{(5)}$ at time $2e_9$. The position of $Q^{(5)}$ has been adjusted for clarity.

$i$     Agent     Vertex     $t_i$     $Q^{(i)}$     $d(Q^{(i)} , Exit)$     Cost

1     $S_1$     $V_1$     0     $V_2$     $e_9$     $e_9$

2     $Q$     $V_2$     0     $V_2$     0     $2\sin(\tfrac{\pi}{9})$

3     $S_1$     $V_9$     $e_9$     $V_3$     $\sqrt{3}$     $e_9+\sqrt{3}$

4     $Q$     $V_3$     $e_9$     $V_3$     0     $e_9$

5     $S_1$     $V_8$     $2e_9$     $(-0.83682,0.28263)$     1.85083     ${3.21891}^*$

6     $Q$     $V_4$     1.48686     $V_4$     0     1.48686

7     $S_1$     $V_7$     $3e_9$     $(-0.57635,-0.09099)$     1.16679     ${3.21891}^*$

8     $Q$     $V_5$     2.49374     $V_5$     0     2.49374

9     $Q$     $V_6$     3.17778     $V_6$     0     3.17778

Trajectories' details for the upper bound of 91;
see Figure <ref>.

For the formal description of Queen's positions, we define points $Q^{(5)}$ and $Q^{(7)}$ as convex combinations of the points, $V_4$ and $V_8$, and $V_4$ and $V_7$, respectively.
Thus, $Q^{(5)}=(1-l_1)V_4+l_1V_8$ and $Q^{(7)}=(1-l_2)V_4+l_2V_7$, for some $l_1,l_2\in[0,1]$. $l_1$ and $l_2$ are obtained as the solution to the following non-linear system

\begin{align}
&        l_1\| V_4 -V_8\|+l_2\| V_4-V_7\|=e_9     \label{k1n9eq1new} \\
&        (1-l_1)\| V_4 -V_8\|=l_1\| V_4 -V_8\|+(1-l_2)\| V_4-V_7\|+l_2\| V_4-V_7\|         \label{k1n9eq2new}
\end{align}

The solution to the above system satisfies $l_1\| V_4 -V_8\|\leq e_9$.
(<ref>) is derived by imposing that the time taken by the Queen to travel from $Q^{(5)}$ to $V_4$ to $Q^{(7)}$ is exactly $e_9$.
Moreover, (<ref>) is derived by equating the evacuation times for when the exit is placed at $V_8$ and $V_7$. It follows that $l_1=0.06031$ and $l_2=0.32635$.

§ IMPROVED LOWER BOUNDS ON K FOR $K=1,2$

This section provides the proof of our second main contribution, as stated in Theorem <ref>.
The key element in this proof is the following lemma, first utilized in [26] and restricted to $k=1$.

The following is true for all $n \geq 3$.
Let $l_{n,k}$ be a lower bound on nk.
Then, no algorithm for k has evacuation cost less than
$1+ 2\pi/((k+1)n) + l_{n,k}$.

Fix $\epsilon>0$, along with an algorithm for k.
We let the search algorithm run for time $1+t - \epsilon$, where $t=2\pi/((k+1)n)$
We claim that there is an $n$-gon $P_n$ inscribed in the DISK, such that none of its vertices has been explored.

Indeed, let $S$ denote the subset of the disk searched by the $k+1$ agents. Because each agent needs time 1 to go the perimeter,
and no agent has searched more than $t - \epsilon$, we have that $|S| \leq (k+1)(t - \epsilon) $.

Now consider an arbitrary placement (inscription) of the n-gon $P_n$ in the disk.
For any $\phi\in [0,2\pi/n)$, consider the corresponding rotation of $ P_n$ by $\phi$, and define the set

$$D=\{ \phi \in [0,2\pi/n): ~\textrm{at least one vertices of}~P_n\textrm{, rotated by}~\phi,~\textrm{has been visited}\}.$$

Note that all rotations $\phi \in [0,2\pi/n)$ correspond to distinct $n$-gons, and the trajectories of the $n$-gon vertices over these rotations cover disjoint parts of the perimeter of the disk.
Hence, assuming that for every rotation $\phi \in [0,2\pi/n)$ of $P_n$, at least one vertices of that $P_n$ has been visited, we conclude that $|D|=2\pi/n$, and hence
that for the searched space we have $|S|\geq 2\pi/n$.
Together with that $|S| \leq (k+1)(t - \epsilon) $, we conclude that $2\pi/n \leq (k+1)(t-\epsilon)$, a contradiction for $t=2\pi/((k+1)n)$.

Hence, we showed that for every $\epsilon>0$, that can also be chosen to be arbitrarily small,
after the algorithm for k runs for time $1+4\pi/((k+1)n) - \epsilon$, there is a $n$-gon with the property that none of its vertices has been explored.
The $n$-gon can be presented then to the algorithm, and hence, the additional time required to terminate is that of solving the evacuation problem for $P_n$.
Overall, we showed that k requires time
$1+ 4\pi/((k+1)n) + l_{n,k}'-\epsilon$, for every $\epsilon>0$.

We can now prove Theorem <ref> using Lemma <ref> and the lower bounds established by Theorem <ref>.
For this, we utilize the already derived bounds of nk for $n \geq 6$, and we summarize the induced lower bounds for k in Table <ref>, which are in agreement with those reported in Theorem <ref>.
The star $*$ next to some lower bounds indicates an improvement upon the previous best results known. Bold text indicates the best result for a fixed $k$, and over all values of $n$ for which a lower bound to nk was available.
There is no improvement in the state-of-the-art with this method for $k=3,4$, but we still report the derived lower bounds for completeness.

$k$$n$     6     7     8     9     10     11     12     13     Best Previous LB
1     4.38962     4.40005     4.3959     4.56798     4.50128      4.64138     4.64666$^*$     4.60528      4.56798 [50]
2    3.34907      3.38268     3.49964     3.5856     3.58755     3.65332$^*$     NA     NA     3.6307 [26]
3     3.12782     3.06709      3.10977     3.02537     3.10814     NA     NA     NA     3.2017 [26]
4     2.70944     2.82912     2.84633     2.80847     2.74369     NA     NA     NA     2.91322 [27]

Lower bounds on k as derived as immediate corollaries of Lemma <ref> and Theorem <ref>.
Entries with NA correspond to values of $(n,k)$ for which no lower bound to nk was derived, and hence these parameters are not applicable to our current argument.

§ UPPER AND LOWER BOUNDS ON WN & IMPROVED LOWER BOUNDS ON W

In this section, we describe the derivation of values in Figures <ref> and <ref>, leading to Theorems <ref> and <ref>. Setting $k=1$, we begin with a modification to <ref> to model wn for all $n \geq 3$ and $w \in [0,1]$. Note that 0n coincides with problem n1. The feasible trajectories of the two agents are characterized by the same series of constraints. The objective of wn, as defined in Section <ref>, is to minimize
\max_{j \in \{1,\ldots, n\}} \left\{ t_j + \tfrac{d_{(0,j),(s_j,j)} + w \cdot d_{(1,j),(s_j,j)}}{1+w} \right\}.
Importantly, the objective remains linear in variables $d$. Therefore, similar to our approach in Lemma <ref>, dropping constraint <ref> results in a Linear Program, whose optimal solution provides a lower bound to the optimal $(s,\rho)$-algorithm for wn. We denote this Linear Program as $\textsc{wLP}^n(s,\rho)$, and its optimal solution as $wobj^n(s,\rho)$. The following lemma was used in [50] only for $n \leq 7$.

No algorithm for w has a cost less than $1 + \frac{\pi}{n} + \min_{(s,\rho) \in \mathcal{X}^n_1} wobj^n(s,\rho)$, for all $n \geq 3$.

Figure <ref> shows the known upper bound for w and the known lower bounds obtained by applying Lemma <ref> with $n=7$. As described in Section <ref>, our contribution includes pushing the computational boundaries for computing $\min_{(s,\rho) \in \mathcal{X}^n_1} wobj^n(s,\rho)$ for larger $n$, reaching $n=12$ for the $w$-weighted search problem. We compute lower bounds on wn for $w$ starting from $0$ with a step size of $0.01$. These linear programs were solved using Julia's JuMP Clp solver [19, 37]. The strongest lower bounds were obtained for $n=11$ and $n=12$, with different $n$-gon lower bounds dominating for different values of $w$. Figure <ref> depicts the new and stronger lower bounds obtained by applying Lemma <ref> for $n=11$ and $n=12$.

The new lower bounds are stronger than the straightforward lower bound of $1 + \pi$ reported in [50] for all $w \in [0,0.7]$, and represent an improvement over the previously best lower bound known for the same range of $w$. More importantly, the gap between the previously best upper and lower bounds is now reduced by more than half for all $w \in [0,0.5]$. This discussion concludes the statements in Theorem <ref>.

Next, we justify and motivate Theorem <ref>. The argument used to derive Theorem <ref> relies on the computed lower bounds for wn, which were obtained using LP relaxations to the exact formulations for determining optimal $(s,\rho)$-algorithms. If these relaxations introduced a significant gap, the lower bound argument would not be tight, modulo the reduction proposed in Lemma <ref>. Therefore, for $w \in [0,1]$ and $n=11,12$, we aim to find upper bounds for wn. If these bounds match the derived lower bounds, it would show that the lower bound analysis is tight, and further improvement would require a different technique or higher values of $n$.

Despite the lower bounds on $\min_{(s,\rho) \in \mathcal{X}^n_1} wobj^n(s,\rho)$ being obtained for various $(s,\rho) \in \mathcal{X}^n_1$ as $w$ ranged over $[0,1]$, computing upper bounds can be done using fixed configurations $(s,\rho) \in \mathcal{X}^n_1$. For $n=11$, we use $s=(1,0,0,1,1,0,1,0,1,0,1)$ and $\rho=(1,2,3,11,10,4,9,5,8,6,7)$, while for $n=12$, we use $s=(1,0,1,0,1,0,1,0,1,0,1,0)$ and $\rho=(1,2,12,3,11,4,10,5,9,6,8,7)$. For these configurations, we compute a numerical solution to the Non-Linear Program (<ref>) using the objective of wn, from $w=0$ with a step size of $0.02$. The numerical solutions were obtained using Julia's JuMP Ipopt [20, 37], which uses an interior point method for solving NLPs. Although these solutions are only guaranteed to be locally optimal, they correspond to feasible search trajectories (which may not be optimal). Nevertheless, in Figure <ref>, the derived upper and lower bounds are tight or nearly tight, similar to what we observed for nk.

§ DISCUSSION

In this work, we made several lower bound improvements for well-known multi-agent search problems. Our results are obtained by novel upper and lower bounds, often tight or nearly tight, for searching hidden items where target locations form regular $n$-gons.
We extend existing techniques to larger $n$-gons and more agents, addressing significant computational challenges. Our contributions also lie in overcoming these challenges. The tightness of our results for $n$-gons show that further improvements in lower bounds on disk-related search problems require either increasing \(n\) or changing the lower bound techniques.
The tight bounds are based on solutions to LP relaxations inspired by metric embedding relaxations, which relax Non-Linear Programs (NLPs). We observed that these relaxations often impose no gap, even though the solutions may induce metric-related discrepancies. Investigating this phenomenon and strengthening the LPs to model optimal search algorithms more would be valuable.
Finally, our techniques apply to other search problems, especially those with asymmetric objectives. It remains to be seen if these techniques can be adapted for the face-to-face search problems, where good lower bounds still elude us.

[1]
R. Ahlswede and I. Wegener.
Search problems.
John Wiley & Sons, Inc., 1987.

[2]
S. Alpern, R. Fokkink, L. Gasieniec, R. Lindelauf, and V. Subrahmanian.
Search Theory: A Game Theoretic Perspective.
Springer, 2013.

[3]
S. Alpern and S. Gal.
The Theory of Search Games and Rendezvous.
Kluwer, 2003.

[4]
S. Angelopoulos, C. Dürr, and S. Jin.
Best-of-two-worlds analysis of online search.
In R. Niedermeier and C. Paul, editors, 36th International
Symposium on Theoretical Aspects of Computer Science, STACS 2019, March
13-16, 2019, Berlin, Germany, volume 126 of LIPIcs, pages 7:1–7:17.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.

[5]
S. Angelopoulos, C. Dürr, and T. Lidbetter.
The expanding search ratio of a graph.
Discret. Appl. Math, 260:51–65, 2019.

[6]
R. Baeza Yates, J. Culberson, and G. Rawlins.
Searching in the plane.
Information and Computation, 106(2):234–252, 1993.

[7]
I. Bagheri, L. Narayanan, and J. Opatrny.
Evacuation of equilateral triangles by mobile agents of limited
communication range.
In F. Dressler and C. Scheideler, editors, ALGOSENSORS 2019,
volume 11931 of Lecture Notes in Computer Science, pages 3–22.
Springer, 2019.

[8]
E. Bampas, J. Czyzowicz, L. Gasieniec, D. Ilcinkas, R. Klasing, T. Kociumaka,
and D. Pajak.
Linear search by a pair of distinct-speed robots.
Algorithmica, 81(1):317–342, 2019.

[9]
A. Beck.
On the linear search problem.
Israel Journal of Mathematics, 2(4):221–228, 1964.

[10]
P. Behrouz, O. Konstantinidis, N. Leonardos, A. Pagourtzis, I. Papaioannou, and
M. Spyrakou.
Byzantine fault-tolerant protocols for (n, f)-evacuation from a
In International Symposium on Algorithmics of Wireless
Networks, pages 87–100. Springer, 2023.

[11]
A. Bonato, K. Georgiou, C. MacRury, and P. Prałat.
Algorithms for p-faulty search on a half-line.
Algorithmica, pages 1–30, 2022.

[12]
P. Borowiecki, S. Das, D. Dereniowski, and L. Kuszner.
Distributed evacuation in graphs with multiple exits.
In J. Suomela, editor, Structural Information and Communication
Complexity - 23rd International Colloquium, SIROCCO 2016, Helsinki, Finland,
July 19-21, 2016, Revised Selected Papers, volume 9988 of Lecture Notes
in Computer Science, pages 228–241, 2016.

[13]
P. Bose and J.-L. De Carufel.
A general framework for searching on a line.
Theoretical Computer Science, 703:1–17, 2017.

[14]
S. Brandt, K.-T. Foerster, B. Richner, and R. Wattenhofer.
Wireless evacuation on m rays with k searchers.
Theor. Comput. Sci, 811:56–69, 2020.

[15]
S. Brandt, F. Laufenberg, Y. Lv, D. Stolz, and R. Wattenhofer.
Collaboration without communication: Evacuating two robots from a
In International Conference on Algorithms and Complexity, pages
104–115. Springer, 2017.

[16]
M. Chrobak, L. Gasieniec, T. Gorry, and R. Martin.
Group search on the line.
In G. F. Italiano, T. Margaria-Steffen, J. Pokorný, J.-J.
Quisquater, and R. Wattenhofer, editors, SOFSEM, volume 8939 of Lecture Notes in Computer Science, pages 164–176. Springer, 2015.

[17]
H. Chuangpishit, K. Georgiou, and P. Sharma.
A multi-objective optimization problem on evacuating 2 robots from
the disk in the face-to-face model; trade-offs between worst-case and
average-case analysis.
Information, 11(11):506, 2020.

[18]
H. Chuangpishit, S. Mehrabi, L. Narayanan, and J. Opatrny.
Evacuating equilateral triangles and squares in the face-to-face
Comput. Geom, 89:101624, 2020.

[19]
Clp: Coin-or linear programming solver.
Accessed: 2024-06-04.

[20]
Ipopt: Interior point optimizer.
Accessed: 2024-06-19.

[21]
J. Czyzowicz, S. Dobrev, K. Georgiou, E. Kranakis, and F. MacQuarrie.
Evacuating two robots from multiple unknown exits in a circle.
In ICDCN, pages 28:1–28:8. ACM, 2016.

[22]
J. Czyzowicz, L. Gasieniec, T. Gorry, E. Kranakis, R. Martin, and D. Pajak.
Evacuating robots via unknown exit in a disk.
In F. Kuhn, editor, DISC 2014, volume 8784 of Lecture
Notes in Computer Science, pages 122–136. Springer, 2014.

[23]
J. Czyzowicz, K. Georgiou, M. Godon, E. Kranakis, D. Krizanc, W. Rytter, and
M. Wlodarczyk.
Evacuation from a disc in the presence of a faulty robot.
In S. Das and S. Tixeuil, editors, SIROCCO 2017, volume 10641
of Lecture Notes in Computer Science, pages 158–173. Springer, 2017.

[24]
J. Czyzowicz, K. Georgiou, R. Killick, E. Kranakis, D. Krizanc, M. Lafond,
L. Narayanan, J. Opatrny, and S. Shende.
Energy Consumption of Group Search on a Line.
In C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi,
editors, 46th International Colloquium on Automata, Languages, and
Programming (ICALP 2019), volume 132 of Leibniz International
Proceedings in Informatics (LIPIcs), pages 137:1–137:15, Dagstuhl, Germany,
2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[25]
J. Czyzowicz, K. Georgiou, R. Killick, E. Kranakis, D. Krizanc, M. Lafond,
L. Narayanan, J. Opatrny, and S. Shende.
Time-energy tradeoffs for evacuation by two robots in the wireless
Theoretical Computer Science, 852:61–72, 2021.

[26]
J. Czyzowicz, K. Georgiou, R. Killick, E. Kranakis, D. Krizanc, L. Narayanan,
J. Opatrny, and S. Shende.
Priority evacuation from a disk: The case of n= 1, 2, 3.
Theoretical Computer Science, 806:595–616, 2020.

[27]
J. Czyzowicz, K. Georgiou, R. Killick, E. Kranakis, D. Krizanc, L. Narayanan,
J. Opatrny, and S. Shende.
Priority evacuation from a disk: The case of $n\geq 4$.
Theoretical Computer Science, 846:91–102, 2020.

[28]
J. Czyzowicz, K. Georgiou, and E. Kranakis.
Group search and evacuation.
In Distributed Computing by Mobile Entities, pages 335–370.
Springer, 2019.

[29]
J. Czyzowicz, K. Georgiou, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny,
and S. Shende.
Search on a line by byzantine robots.
International Journal of Foundations of Computer Science,
32(04):369–387, 2021.

[30]
J. Czyzowicz, K. Georgiou, E. Kranakis, L. Narayanan, J. Opatrny, and
B. Vogtenhuber.
Evacuating Robots from a Disk Using Face-to-Face Communication.
Discrete Mathematics & Theoretical Computer Science, vol.
22 no. 4, Aug. 2020.

[31]
J. Czyzowicz, R. Killick, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny,
D. Pankratov, and S. Shende.
Group evacuation on a line by agents with different communication
ISAAC 2021, pages 57:1–57:24, 2021.

[32]
J. Czyzowicz, R. Killick, E. Kranakis, and G. Stachowiak.
Search and evacuation with a near majority of faulty agents.
In SIAM Conference on Applied and Computational Discrete
Algorithms (ACDA21), pages 217–227. SIAM, 2021.

[33]
J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, and J. Opatrny.
Search on a line with faulty robots.
Distributed Comput, 32(6):493–504, 2019.

[34]
J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. M.
Wireless autonomous robot evacuation from equilateral triangles and
In S. Papavassiliou and S. Ruehrup, editors, 14th International
Conference, ADHOC-NOW, volume 9143 of Lecture Notes in Computer
Science, pages 181–194. Springer, 2015.

[35]
J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. M.
Linear search with terrain-dependent speeds.
In D. Fotakis, A. Pagourtzis, and V. T. Paschos, editors, Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens,
Greece, May 24-26, 2017, Proceedings, volume 10236 of Lecture Notes in
Computer Science, pages 430–441, 2017.

[36]
Y. Disser and S. Schmitt.
Evacuating two robots from a disk: a second cut.
In International Colloquium on Structural Information and
Communication Complexity, pages 200–214. Springer, 2019.

[37]
I. Dunning, J. Huchette, and M. Lubin.
Jump: A modeling language for mathematical optimization.
SIAM review, 59(2):295–320, 2017.

[38]
O. Feinerman and A. Korman.
The ants problem.
Distributed Computing, 30(3):149–168, 2017.

[39]
S. P. Fekete, C. Gray, and A. Kröller.
Evacuation of rectilinear polygons.
In W. Wu and O. Daescu, editors, Combinatorial Optimization and
Applications - 4th International Conference, COCOA 2010, Kailua-Kona, HI,
USA, December 18-20, 2010, Proceedings, Part I, volume 6508 of Lecture
Notes in Computer Science, pages 21–30. Springer, 2010.

[40]
P. Flocchini, G. Prencipe, and N. Santoro, editors.
Distributed Computing by Mobile Entities, Current Research in
Moving and Computing, volume 11340 of Lecture Notes in Computer
Springer, 2019.

[41]
K. Georgiou, N. Giachoudis, and E. Kranakis.
Evacuation from a disk for robots with asymmetric communication.
In 33rd International Symposium on Algorithms and Computation
(ISAAC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.

[42]
K. Georgiou, N. Giachoudis, and E. Kranakis.
Evacuation from a disk for robots with asymmetric communication.
In 33rd International Symposium on Algorithms and Computation
(ISAAC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.

[43]
K. Georgiou and W. Jang.
Triangle evacuation of 2 agents in the wireless model.
In International Symposium on Algorithms and Experiments for
Wireless Sensor Networks, pages 77–90. Springer, 2022.

[44]
K. Georgiou and W. Jang.
Triangle evacuation of 2 agents in the wireless model.
In Algorithmics of Wireless Networks: 18th International
Symposium on Algorithmics of Wireless Networks, ALGOSENSORS 2022, Potsdam,
Germany, September 8–9, 2022, Proceedings, pages 77–90. Springer, 2022.

[45]
K. Georgiou, G. Karakostas, and E. Kranakis.
Search-and-fetch with 2 robots on a disk: Wireless and face-to-face
communication models.
Discrete Mathematics & Theoretical Computer Science, 21, 2019.

[46]
K. Georgiou, G. Karakostas, and E. Kranakis.
Treasure evacuation with one robot on a disk.
Theoretical Computer Science, 852:18–28, 2021.

[47]
K. Georgiou, E. Kranakis, N. Leonardos, A. Pagourtzis, and I. Papaioannou.
Optimal circle search despite the presence of faulty robots.
In F. Dressler and C. Scheideler, editors, ALGOSENSORS 2019,
volume 11931 of Lecture Notes in Computer Science, pages 192–205.
Springer, 2019.

[48]
K. Georgiou, S. Leizerovich, J. Lucier, and S. Kundu.
Evacuating from $\ell_p$ unit disks in the wireless model.
Theoretical Computer Science, 944:113675, 2023.

[49]
K. Georgiou and J. Lucier.
Weighted group search on a line & implications to the priority
evacuation problem.
Theoretical Computer Science, 939:1–17, 2023.

[50]
K. Georgiou and X. Wang.
Weighted group search on the disk & improved lower bounds for
priority evacuation.
In 35th International Workshop on Combinatorial Algorithms
(IWOCA'24), Lecture Notes in Computer Science, page to appear, 2024.

[51]
R. Hohzaki.
Search games: Literature and survey.
Journal of the Operations Research Society of Japan,
59(1):1–34, 2016.

[52]
J. M. Kleinberg.
On-line search in a simple polygon.
In SODA, volume 94, pages 8–15. Citeseer, 1994.

[53]
A. Miller and A. Pelc.
Tradeoffs between cost and information for rendezvous and treasure
J. Parallel Distributed Comput, 83:159–167, 2015.

[54]
D. Pattanayak, H. Ramesh, P. S. Mandal, and S. Schmid.
Evacuating two robots from two unknown exits on the perimeter of a
disk with wireless communication.
In Proceedings of the 19th International Conference on
Distributed Computing and Networking, pages 1–4, 2018.

[55]
X. Sun, Y. Sun, and J. Zhang.
Better upper bounds for searching on a line with byzantine robots.
In Complexity and Approximation, pages 151–171. Springer,

§ ALGORITHMIC DETAILS FOR THE UPPER BOUNDS ON NK

§.§ Polygon Priority Evacuation with $1$ Servant

Before we give the upper bound details for n1, we present all relevant figures.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (-5,8.7) ;
[fill=black] (a) circle (0.105) node [above left] $V_1$;
(b) at (-5,-8.7) ;
[fill=black] (b) circle (0.105) node [below left] $V_2$;
(c) at (10,0) ;
[fill=black] (c) circle (0.105) node [above] $V_3$;

[line width=0.25mm, black] (10,0)–(-5,8.7)–(-5,-8.7)–(10,0);

[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (a) at (-5,8.7) ;

(b) at (-5,-8.7) ;
[fill=blue] (b) circle (0.45);
[diamond, draw=blue, fill=blue, minimum size=0.15cm, inner sep=0] (c) at (10,0) ;

[line width=0.5mm, blue, mid arrow] (-5,-8.7) – (10,0);
[dashed] [line width=0.5mm, blue] [-latex] (-5.1,-8.7) – (-5.1,8.7);

A search trajectory for 31.
Trajectory details can be found in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (0,10) ;
[fill=black] (a) circle (0.105) node [above right] $V_1$;
(b) at (-10,0) ;
[fill=black] (b) circle (0.105) node [above left] $V_2$;
(c) at (0,-10) ;
[fill=black] (c) circle (0.105) node [below left] $V_3$;
(d) at (10,0) ;
[fill=black] (d) circle (0.105) node [above right] $V_4$;
[line width=0.25mm, black] (10,0)–(0,10)–(-10,0)–(0,-10)–(10,0);

at (a) (0,10) ;
[fill=red] (a) circle (0.45);
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (d) at (10,0) ;
[line width=0.5mm, red, mid arrow] (0,10) – (10,0);

at (b) (-10,0) ;
[fill=blue] (b) circle (0.45);
(e) at (3.7,-3.7) ;
[fill=blue] (e) circle (0.45);
[diamond, draw=blue, fill=blue, minimum size=0.15cm, inner sep=0] (c) at (0,-10) ;
[line width=0.5mm, blue, mid arrow] (-10,0) – (3.7,-3.7);
[line width=0.5mm, blue, mid arrow] (3.7,-3.7) – (0,-10);
[dashed] [line width=0.5mm, blue] [-latex] (3.7,-3.7) – (10,0);

A search trajectory for 41.
Trajectory details can be found in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (3.1,9.5) ;
[fill=black] (a) circle (0.105) node [above right] $V_1$;
(b) at (-8.1,5.9) ;
[fill=black] (b) circle (0.105) node [left] $V_2$;
(c) at (-8.1,-5.9) ;
[fill=black] (c) circle (0.105) node [left] $V_3$;
(d) at (3.1,-9.5) ;
[fill=black] (d) circle (0.105) node [below left] $V_4$;
(e) at (10,0) ;
[fill=black] (e) circle (0.105) node [above right] $V_5$;

[line width=0.25mm, black] (10,0)–(3.1,9.5)–(-8.1,5.9)–(-8.1,-5.9)–(3.1,-9.5)–(10,0);

at (a) (3.1,9.5) ;
[fill=red] (a) circle (0.45);
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (e) at (10,0) ;
[line width=0.5mm, red, mid arrow] (3.1,9.5) – (10,0);

at (d) (3.1,-9.5) ;
[fill=blue] (d) circle (0.45);
(f) at (-4.6,-4.8) ;
[fill=blue] (f) circle (0.45);
at (c) (-8.1,-5.9) ;
[fill=blue] (c) circle (0.45);
[diamond, draw=blue, fill=blue, minimum size=0.15cm, inner sep=0] (b) at (-8.1,5.9) ;
[line width=0.5mm, blue, mid arrow] (3.1,-9.5) – (-4.6,-4.8);
[line width=0.5mm, blue, mid arrow] (-4.6,-4.8) – (-8.1,-5.9);
[line width=0.5mm, blue, mid arrow] (-8.1,-5.9) – (-8.1,5.9);
[dashed] [line width=0.5mm, blue] [-latex] (-4.6,-4.8) – (10,0);

A search trajectory for 51.
Trajectory details can be found in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (5,8.7) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (-5,8.7) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-10,0) ;
[fill=black] (c) circle (0.105) node [above left] $V_3$;
(d) at (-5,-8.7) ;
[fill=black] (d) circle (0.105) node [below left] $V_4$;
(e) at (5,-8.7) ;
[fill=black] (e) circle (0.105) node [below right] $V_5$;
(f) at (10,0) ;
[fill=black] (f) circle (0.105) node [above right] $V_6$;

[line width=0.25mm, black] (10,0)–(5,8.7)–(-5,8.7)–(-10,0)–(-5,-8.7)–(5,-8.7)–(10,0);

at (a) (5,8.7) ;
[fill=red] (a) circle (0.45);
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (f) at (10,0) ;
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (e) at (5,-8.7) ;
[line width=0.5mm, red, mid arrow] (5,8.7) – (10,0);
[line width=0.5mm, red, mid arrow] (10,0) – (5,-8.7);

at (b) (-5,8.7) ;
[fill=blue] (b) circle (0.45);
(g) at (-7,0) ;
[fill=blue] (g) circle (0.45);
at (c) (-10,0) ;
[fill=blue] (c) circle (0.45);
(h) at (-2.5,-4.3) ;
[fill=blue] (h) circle (0.45);
at (d) (-5,-8.7) ;
[fill=blue] (d) circle (0.45);
[line width=0.5mm, blue, mid arrow] (-5,8.7) – (-7,0);
[line width=0.5mm, blue] (-7,0)  – (-10,0) node[currarrow,blue,pos=0.5,xscale=-1,sloped,scale=0.75] ;

[line width=0.5mm, blue, mid arrow] (-10,0) – (-2.5,-4.3);
[line width=0.5mm, blue, mid arrow] (-2.5,-4.3) – (-5,-8.7);
[dashed] [line width=0.5mm, blue] [-latex] (-7,0) – (10,0);
[dashed] [line width=0.5mm, blue] [-latex] (-2.5,-4.3) – (5,-8.7);

A search trajectory for 61.
Trajectory details can be found in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (6.2,7.8) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (-2.2,9.7) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-9,4.3) ;
[fill=black] (c) circle (0.105) node [above left] $V_3$;
(d) at (-9,-4.3) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-2.2,-9.7) ;
[fill=black] (e) circle (0.105) node [below left] $V_5$;
(f) at (6.2,-7.8) ;
[fill=black] (f) circle (0.105) node [below right] $V_6$;
(g) at (10,0) ;
[fill=black] (g) circle (0.105) node [above right] $V_7$;

[line width=0.25mm, black] (10,0)–(6.2,7.8)–(-2.2,9.7)–(-9,4.3)–(-9,-4.3)–(-2.2,-9.7)–(6.2,-7.8)–(10,0);

(b) at (-2.2,9.7) ;
[fill=red] (b) circle (0.45);
(c) at (-9,4.3) ;
[fill=red] (c) circle (0.45);
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (d) at (-9,-4.3) ;
[line width=0.5mm, red, mid arrow] (-2.2,9.7) – (-9,4.3);
[line width=0.5mm, red, mid arrow] (-9,4.3) – (-9,-4.3);

(a) at (6.2,7.8) ;
[fill=blue] (a) circle (0.45);
(g) at (10,0) ;
[fill=blue] (g) circle (0.45);
(h) at (3.3,-5.5) ;
[fill=blue] (h) circle (0.45);
(f) at (6.2,-7.8) ;
[fill=blue] (f) circle (0.45);
[diamond, draw=blue, fill=blue, minimum size=0.15cm, inner sep=0] (e) at (-2.2,-9.7) ;
[line width=0.5mm, blue, mid arrow] (6.2,7.8) – (10,0);
[line width=0.5mm, blue, mid arrow] (10,0) – (3.3,-5.5);
[line width=0.5mm, blue, mid arrow] (3.3,-5.5) – (6.2,-7.8);
[line width=0.5mm, blue, mid arrow] (6.2,-7.8) – (-2.2,-9.7);
[dashed] [line width=0.5mm, blue] [-latex] (3.3,-5.5) – (-9,-4.3);

A search trajectory for 71.
Trajectory details can be found in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (7.1,7.1) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (0,10) ;
[fill=black] (b) circle (0.105) node [above right] $V_2$;
(c) at (-7.1,7.1) ;
[fill=black] (c) circle (0.105) node [above left] $V_3$;
(d) at (-10,0) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-7.1,-7.1) ;
[fill=black] (e) circle (0.105) node [below left] $V_5$;
(f) at (0, -10) ;
[fill=black] (f) circle (0.105) node [below right] $V_6$;
(g) at (7.1,-7.1) ;
[fill=black] (g) circle (0.105) node [below right] $V_7$;
(h) at (10,0) ;
[fill=black] (h) circle (0.105) node [above right] $V_8$;

[line width=0.25mm, black] (10,0)–(7.1,7.1)–(0,10)–(-7.1,7.1)–(-10,0)–(-7.1,-7.1)–(0, -10)–(7.1,-7.1)–(10,0);

at (b) (0,10) ;
[fill=red] (b) circle (0.45);
at (c) (-7.1,7.1) ;
[fill=red] (c) circle (0.45);
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (d) at (-10,0) ;
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (e) at (-7.1,-7.1) ;
[line width=0.5mm, red, mid arrow] (0,10) – (-7.1,7.1);
[line width=0.5mm, red, mid arrow] (-7.1,7.1) – (-10,0);
[line width=0.5mm, red, mid arrow] (-10,0) – (-7.1,-7.1);

at (a) (7.1,7.1) ;
[fill=blue] (a) circle (0.45);
at (h) (10,0) ;
[fill=blue] (h) circle (0.45);
(i) at (4.2,-4.9) ;
[fill=blue] (i) circle (0.45);
at (f) (0, -10) ;
[fill=blue] (f) circle (0.45);
(j) at (0,-7.5) ;
[fill=blue] (j) circle (0.45);
[diamond, draw=blue, fill=blue, minimum size=0.15cm, inner sep=0] (g) at (7.1,-7.1) ;
[line width=0.5mm, blue, mid arrow] (7.1,7.1) – (10,0);
[line width=0.5mm, blue, mid arrow] (10,0) – (4.2,-4.9);
[line width=0.5mm, blue, mid arrow] (4.2,-4.9) – (0, -10);
[line width=0.5mm, blue] (0, -10)  – (0,-7.5) node[currarrow,blue,pos=0.5,xscale=1,sloped,scale=0.75] ;

[line width=0.5mm, blue, mid arrow] (0,-7.5) – (7.1,-7.1);
[dashed] [line width=0.5mm, blue] [-latex] (4.2,-4.9) – (-10,0);
[dashed] [line width=0.5mm, blue] [-latex] (0,-7.5) – (-7.1,-7.1);

A search trajectory for 81.
Trajectory details can be found in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (7.7,6.4) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (1.7,9.8) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-5,8.7) ;
[fill=black] (c) circle (0.105) node [above] $V_3$;
(d) at (-9.4,3.4) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-9.4,-3.4) ;
[fill=black] (e) circle (0.105) node [below left] $V_5$;
(f) at (-5,-8.7) ;
[fill=black] (f) circle (0.105) node [below left] $V_6$;
(g) at (1.7,-9.8) ;
[fill=black] (g) circle (0.105) node [below right] $V_7$;
(h) at (7.7,-6.4) ;
[fill=black] (h) circle (0.105) node [below right] $V_8$;
(i) at (10,0) ;
[fill=black] (i) circle (0.105) node [above right] $V_9$;

[line width=0.25mm, black] (10,0)–(7.7,6.4)–(1.7,9.8)–(-5,8.7)–(-9.4,3.4)–(-9.4,-3.4)–(-5,-8.7)–(1.7,-9.8)–(7.7,-6.4)–(10,0);

at (a) (7.7,6.4) ;
[fill=red] (a) circle (0.45);
at (i) (10,0) ;
[fill=red] (i) circle (0.45);
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (h) at (7.7,-6.4) ;

[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (g) at (1.7,-9.8) ;

[line width=0.5mm, red, mid arrow] (7.7,6.4) – (10,0);
[line width=0.5mm, red, mid arrow] (10,0) – (7.7,-6.4);
[line width=0.5mm, red, mid arrow] (7.7,-6.4) – (1.7,-9.8);

at (b) (1.7,9.8) ;
[fill=blue] (b) circle (0.45);
at (c) (-5,8.7) ;
[fill=blue] (c) circle (0.45);

(j) at (-7,3.5) ;
[fill=blue] (j) circle (0.45);
at (d) (-9.4,3.4) ;
[fill=blue] (d) circle (0.45);
(k) at (-5.8,-0.9) ;
[fill=blue] (k) circle (0.45);
at (e) (-9.4,-3.4) ;
[fill=blue] (e) circle (0.45);
at (f) (-5,-8.7) ;
[fill=blue] (f) circle (0.45);
[line width=0.5mm, blue, mid arrow] (1.7,9.8) – (-5,8.7);
[line width=0.5mm, blue, mid arrow] (-5,8.7) – (-7,3.5);

[line width=0.5mm, blue] (-7,3.5)  – (-9.4,3.4) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;
[line width=0.5mm, blue, mid arrow] (-9.4,3.4) – (-5.8,-0.9);
[line width=0.5mm, blue, mid arrow] (-5.8,-0.9) – (-9.4,-3.4);
[line width=0.5mm, blue, mid arrow] (-9.4,-3.4) – (-5,-8.7);

[dashed] [line width=0.5mm, blue] [-latex] (-7,3.5) – (7.7,-6.4);
[dashed] [line width=0.5mm, blue] [-latex] (-5.8,-0.9) – (1.7,-9.8);

A search trajectory for 91.
Trajectory details can be found in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (8.1,5.9) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (3.1,9.5) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-3.1,9.5) ;
[fill=black] (c) circle (0.105) node [above] $V_3$;
(d) at (-8.1,5.9) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-10,0) ;
[fill=black] (e) circle (0.105) node [above left] $V_5$;
(f) at (-8.1,-5.9) ;
[fill=black] (f) circle (0.105) node [below left] $V_6$;
(g) at (-3.1,-9.5) ;
[fill=black] (g) circle (0.105) node [below] $V_7$;
(h) at (3.1,-9.5) ;
[fill=black] (h) circle (0.105) node [below right] $V_8$;
(i) at (8.1,-5.9) ;
[fill=black] (i) circle (0.105) node [below right] $V_9$;
(j) at (10,0) ;
[fill=black] (j) circle (0.105) node [above right] $V_{10}$;

[line width=0.25mm, black] (10,0)–(8.1,5.9)–(3.1,9.5)–(-3.1,9.5)–(-8.1,5.9)–(-10,0)–(-8.1,-5.9)–(-3.1,-9.5)–(3.1,-9.5)–(8.1,-5.9)–(10,0);

at (a) (8.1,5.9) ;
[fill=red] (a) circle (0.45);
at (j) (10,0) ;
[fill=red] (j) circle (0.45);
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (i) at (8.1,-5.9) ;
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (h) at (3.1,-9.5) ;
at (g) (-3.1,-9.5) ;
[fill=red] (g) circle (0.45);
[line width=0.5mm, red, mid arrow] (8.1,5.9) – (10,0);
[line width=0.5mm, red, mid arrow] (10,0) – (8.1,-5.9);
[line width=0.5mm, red, mid arrow] (8.1,-5.9) – (3.1,-9.5);
[line width=0.5mm, red, mid arrow] (3.1,-9.5) – (-3.1,-9.5);

at (b) (3.1,9.5) ;
[fill=blue] (b) circle (0.45);
at (c) (-3.1,9.5) ;
[fill=blue] (c) circle (0.45);

(k) at (-6,4.5) ;
[fill=blue] (k) circle (0.45);
at (d) (-8.1,5.9) ;
[fill=blue] (d) circle (0.45);
(l) at (-6.5,0.1) ;
[fill=blue] (l) circle (0.45);
at (f) (-8.1,-5.9) ;
[fill=blue] (f) circle (0.45);
at (e) (-10,0) ;
[fill=blue] (e) circle (0.45);
[line width=0.5mm, blue, mid arrow] (3.1,9.5) – (-3.1,9.5);

[line width=0.5mm, blue, mid arrow] (-3.1,9.5) – (-6,4.5);

[line width=0.5mm, blue] (-6,4.5)  – (-8.1,5.9) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;
[line width=0.5mm, blue, mid arrow] (-8.1,5.9) – (-6.5,0.1);
[line width=0.5mm, blue, mid arrow] (-6.5,0.1) – (-8.1,-5.9);
[line width=0.5mm, blue, mid arrow] (-8.1,-5.9) – (-10,0);

[dashed] [line width=0.5mm, blue] [-latex] (-6,4.5) – (8.1,-5.9);
[dashed] [line width=0.5mm, blue] [-latex] (-6.5,0.1) – (3.1,-9.5);

A search trajectory for 101.
Trajectory details can be found in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (8.4,5.4) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (4.2,9.1) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-1.4,9.9) ;
[fill=black] (c) circle (0.105) node [above] $V_3$;
(d) at (-6.5,7.6) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-9.6,2.8) ;
[fill=black] (e) circle (0.105) node [above left] $V_5$;
(f) at (-9.6,-2.8) ;
[fill=black] (f) circle (0.105) node [below left] $V_6$;
(g) at (-6.5,-7.6) ;
[fill=black] (g) circle (0.105) node [below left] $V_7$;
(h) at (-1.4,-9.9) ;
[fill=black] (h) circle (0.105) node [below right] $V_8$;
(i) at (4.2,-9.1) ;
[fill=black] (i) circle (0.105) node [below right] $V_9$;
(j) at (8.4,-5.4) ;
[fill=black] (j) circle (0.105) node [below right] $V_{10}$;
(k) at (10,0) ;
[fill=black] (k) circle (0.105) node [above right] $V_{11}$;

[line width=0.25mm, black] (10,0)–(8.4,5.4)–(4.2,9.1)–(-1.4,9.9)–(-6.5,7.6)–(-9.6,2.8)–(-9.6,-2.8)–(-6.5,-7.6)–(-1.4,-9.9)–(4.2,-9.1)–(8.4,-5.4)–(10,0);

at (a) (8.4,5.4) ;
[fill=red] (a) circle (0.45);
at (k) (10,0) ;
[fill=red] (k) circle (0.45);
at (j) (8.4,-5.4) ;
[fill=red] (j) circle (0.45);
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (i) at (4.2,-9.1) ;
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (h) at (-1.4,-9.9) ;
[line width=0.5mm, red, mid arrow] (8.4,5.4) – (10,0);
[line width=0.5mm, red, mid arrow] (10,0) – (8.4,-5.4);
[line width=0.5mm, red, mid arrow] (8.4,-5.4) – (4.2,-9.1);
[line width=0.5mm, red, mid arrow] (4.2,-9.1) – (-1.4,-9.9);

at (b) (4.2,9.1) ;
[fill=blue] (b) circle (0.45);
at (c) (-1.4,9.9) ;
[fill=blue] (c) circle (0.45);
at (d) (-6.5,7.6) ;
[fill=blue] (d) circle (0.45);
(l) at (-7,3.5) ;
[fill=blue] (l) circle (0.45);
at (e) (-9.6,2.8) ;
[fill=blue] (e) circle (0.45);
(m) at (-7.4,-0.6) ;
[fill=blue] (m) circle (0.45);
at (f) (-9.6,-2.8) ;
[fill=blue] (f) circle (0.45);
at (g) (-6.5,-7.6) ;
[fill=blue] (g) circle (0.45);
[line width=0.5mm, blue, mid arrow] (4.2,9.1) – (-1.4,9.9);
[line width=0.5mm, blue, mid arrow] (-1.4,9.9) – (-6.5,7.6);
[line width=0.5mm, blue, mid arrow] (-6.5,7.6) – (-7,3.5);
[line width=0.5mm, blue] (-7,3.5)  – (-9.6,2.8) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;

[line width=0.5mm, blue] (-9.6,2.8)– (-7.4,-0.6) node[currarrow,blue,pos=0.55,xscale=1,sloped,scale=0.75] ;

[line width=0.5mm, blue] (-7.4,-0.6)– (-9.6,-2.8) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;
[line width=0.5mm, blue, mid arrow] (-9.6,-2.8)– (-6.5,-7.6);
[dashed] [line width=0.5mm, blue] [-latex] (-7,3.5) – (4.2,-9.1);
[dashed] [line width=0.5mm, blue] [-latex] (-7.4,-0.6) – (-1.4,-9.9);

A search trajectory for 111.
Trajectory details can be found in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (8.7,5) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (5,8.7) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (0,10) ;
[fill=black] (c) circle (0.105) node [above left] $V_3$;
(d) at (-5,8.7) ;
[fill=black] (d) circle (0.105) node [above] $V_4$;
(e) at (-8.7,5) ;
[fill=black] (e) circle (0.105) node [above left] $V_5$;
(f) at (-10,0) ;
[fill=black] (f) circle (0.105) node [above left] $V_6$;
(g) at (-8.7,-5) ;
[fill=black] (g) circle (0.105) node [left] $V_7$;
(h) at (-5,-8.7) ;
[fill=black] (h) circle (0.105) node [below left] $V_8$;
(i) at (0,-10) ;
[fill=black] (i) circle (0.105) node [below right] $V_9$;
(j) at (5,-8.7) ;
[fill=black] (j) circle (0.105) node [below right] $V_{10}$;
(k) at (8.7,-5) ;
[fill=black] (k) circle (0.105) node [below right] $V_{11}$;
(l) at (10,0) ;
[fill=black] (l) circle (0.105) node [above right] $V_{12}$;

[line width=0.25mm, black] (10,0)–(8.7,5)–(5,8.7)–(0,10)–(-5,8.7)–(-8.7,5)–(-10,0)–(-8.7,-5)–(-5,-8.7)–(0,-10)–(5,-8.7)–(8.7,-5)–(10,0);

at (a) (8.7,5) ;
[fill=red] (a) circle (0.45);
at (l) (10,0) ;
[fill=red] (l) circle (0.45);
at (k) (8.7,-5) ;
[fill=red] (k) circle (0.45);
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (j) at (5,-8.7) ;
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (j) at (0,-10) ;
at (h) (-5,-8.7) ;
[fill=red] (h) circle (0.45);
[line width=0.5mm, red, mid arrow]  (8.7,5) – (10,0);
[line width=0.5mm, red, mid arrow] (10,0) – (8.7,-5);
[line width=0.5mm, red, mid arrow] (8.7,-5) – (5,-8.7);
[line width=0.5mm, red, mid arrow] (5,-8.7) – (0,-10);
[line width=0.5mm, red, mid arrow] (0,-10) – (-5,-8.7);

at (b) (5,8.7) ;
[fill=blue] (b) circle (0.45);
at (c) (0,10) ;
[fill=blue] (c) circle (0.45);
at (d) (-5,8.7) ;
[fill=blue] (d) circle (0.45);
(m) at (-6.5,4.4) ;
[fill=blue] (m) circle (0.45);
at (e) (-8.7,5) ;
[fill=blue] (e) circle (0.45);
(n) at (-6.6,1.4) ;
[fill=blue] (n) circle (0.45);
(o) at (-7.6,-1.7) ;
[fill=blue] (o) circle (0.45);
at (f) (-10,0) ;
[fill=blue] (f) circle (0.45);
at (g) (-8.7,-5) ;
[fill=blue] (g) circle (0.45);
[line width=0.5mm, blue, mid arrow] (5,8.7) – (0,10);
[line width=0.5mm, blue, mid arrow] (0,10) – (-5,8.7);
[line width=0.5mm, blue, mid arrow] (-5,8.7) – (-6.5,4.4);
[line width=0.5mm, blue] (-6.5,4.4)  – (-8.7,5) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;

[line width=0.5mm, blue] (-8.7,5) – (-6.6,1.4) node[currarrow,blue,pos=0.55,xscale=1,sloped,scale=0.75] ;

[line width=0.5mm, blue] (-6.6,1.4) – (-7.6,-1.7) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;

[line width=0.5mm, blue] (-7.6,-1.7) – (-10,0) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;
[line width=0.5mm, blue, mid arrow] (-10,0) – (-8.7,-5);
[dashed] [line width=0.5mm, blue] [-latex] (-6.5,4.4) – (5,-8.7);
[dashed] [line width=0.5mm, blue] [-latex] (-6.6,1.4) – (0,-10);

A search trajectory for 121.
Trajectory details can be found in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (8.9,4.6) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (5.7,8.2) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (1.2,9.9) ;
[fill=black] (c) circle (0.105) node [above] $V_3$;
(d) at (-3.5,9.4) ;
[fill=black] (d) circle (0.105) node [above] $V_4$;
(e) at (-7.5,6.6) ;
[fill=black] (e) circle (0.105) node [above] $V_5$;
(f) at (-9.7,2.4) ;
[fill=black] (f) circle (0.105) node [above left] $V_6$;
(g) at (-9.7,-2.4) ;
[fill=black] (g) circle (0.105) node [below left] $V_7$;
(h) at (-7.5,-6.6) ;
[fill=black] (h) circle (0.105) node [below left] $V_8$;
(i) at (-3.5,-9.4) ;
[fill=black] (i) circle (0.105) node [below left] $V_9$;
(j) at (1.2,-9.9) ;
[fill=black] (j) circle (0.105) node [below] $V_{10}$;
(k) at (5.7,-8.2) ;
[fill=black] (k) circle (0.105) node [below right] $V_{11}$;
(l) at (8.9,-4.6) ;
[fill=black] (l) circle (0.105) node [below right] $V_{12}$;
(m) at (10,0) ;
[fill=black] (m) circle (0.105) node [above right] $V_{13}$;

[line width=0.25mm, black] (10,0)–(8.9,4.6)–(5.7,8.2)–(1.2,9.9)–(-3.5,9.4)–(-7.5,6.6)–(-9.7,2.4)–(-9.7,-2.4)–(-7.5,-6.6)–(-3.5,-9.4)–(1.2,-9.9)–(5.7,-8.2)–(8.9,-4.6)–(10,0);

at (b) (5.7,8.2) ;
[fill=red] (b) circle (0.45);
at (c) (1.2,9.9) ;
[fill=red] (c) circle (0.45);
at (d) (-3.5,9.4) ;
[fill=red] (d) circle (0.45);
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (e) at (-7.5,6.6) ;
[diamond, draw=red, fill=red, minimum size=0.15cm, inner sep=0] (f) at (-9.7,2.4) ;
at (g) (-9.7,-2.4) ;
[fill=red] (g) circle (0.45);
at (h) (-7.5,-6.6) ;
[fill=red] (h) circle (0.45);
[line width=0.5mm, red, mid arrow] (5.7,8.2) – (1.2,9.9);
[line width=0.5mm, red, mid arrow] (1.2,9.9) – (-3.5,9.4);
[line width=0.5mm, red, mid arrow] (-3.5,9.4) – (-7.5,6.6);
[line width=0.5mm, red, mid arrow] (-7.5,6.6) – (-9.7,2.4);
[line width=0.5mm, red, mid arrow] (-9.7,2.4) – (-9.7,-2.4);
[line width=0.5mm, red, mid arrow] (-9.7,-2.4) – (-7.5,-6.6);

at (a) (8.9,4.6) ;
[fill=blue] (a) circle (0.45);
at (m) (10,0) ;
[fill=blue] (m) circle (0.45);
at (l) (8.9,-4.6) ;
[fill=blue] (l) circle (0.45);

(n) at (6,-6) ;
[fill=blue] (n) circle (0.45);
at (k) (5.7,-8.2) ;
[fill=blue] (k) circle (0.45);
(o) at (2.2,-5.8) ;
[fill=blue] (o) circle (0.45);
(p) at (-2,-7.1) ;
[fill=blue] (p) circle (0.45);
at (i) (-3.5,-9.4) ;
[fill=blue] (i) circle (0.45);

(q) at (-4.5,-7) ;
[fill=blue] (q) circle (0.45);
at (j) (1.2,-9.9) ;
[fill=blue] (j) circle (0.45);
[line width=0.5mm, blue, mid arrow] (8.9,4.6) – (10,0);
[line width=0.5mm, blue, mid arrow] (10,0) – (8.9,-4.6);

[line width=0.5mm, blue] (8.9,-4.6) – (6,-6) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;

[line width=0.5mm, blue] (6,-6)  – (5.7,-8.2) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;
[line width=0.5mm, blue, mid arrow] (5.7,-8.2) – (2.2,-5.8);
[line width=0.5mm, blue, mid arrow] (2.2,-5.8) – (-2,-7.1);
[line width=0.5mm, blue, mid arrow] (-2,-7.1) – (-3.5,-9.4);

[line width=0.5mm, blue] (-3.5,-9.4)  – (-4.5,-7) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;

[line width=0.5mm, blue, mid arrow] (-4.5,-7) – (1.2,-9.9);

[dashed] [line width=0.5mm, blue] [-latex] (6,-6) – (-7.5,6.6);
[dashed] [line width=0.5mm, blue] [-latex] (2.2,-5.8) – (-9.7,2.4);

A search trajectory for 131.
Trajectory details can be found in Table <ref>.

§.§.§ 31

We use $s=(1,0,0)$ and $\rho=(1,2,3)$.
The agents' trajectories show in Figure <ref> and in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (-5,8.7) ;
[fill=black] (a) circle (0.105) node [above left] $V_1$;
(b) at (-5,-8.7) ;
[fill=black] (b) circle (0.105) node [below left] $V_2$;
(c) at (10,0) ;
[fill=black] (c) circle (0.105) node [above] $V_3$;

[line width=0.25mm, black] (10,0)–(-5,8.7)–(-5,-8.7)–(10,0);

[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (a) at (-5,8.7) ;
[above right] at (a.south east) $S^{(1)}$;

(b) at (-5,-8.7) ;
[fill=blue] (b) circle (0.25) node [below right] $Q^{(1)}$;
[diamond, draw=blue, fill=blue, minimum size=0.25cm, inner sep=0] (c) at (10,0) ;
[below right] at (c.south east) $Q^{(2)}$;

[line width=0.5mm, blue, mid arrow] (-5,-8.7) – (10,0);
[dashed] [line width=0.5mm, blue] [-latex] (-5.1,-8.7) – (-5.1,8.7);

A search trajectory for 31.
Trajectory details can be found in Table <ref>.

$i$     Agent     Vertex     $t_i$     $Q^{(i)}$     $d(Q^{(i)} , Exit)$     Cost

1     $S_1$     $V_1$     0     $V_2$     $e_3$     ${\sqrt{3}}^*$

2     $Q$     $V_2$     0    $V_2$     0     0

3     $Q$     $V_3$     $e_3$     $V_3$     0     ${\sqrt{3}}^*$

Trajectories' details for the upper bound of 31; see Figure <ref>.

§.§.§ 41

We use $s=(1,0,1,0)$ and $\rho=(1,2,4,3)$.
The agents' trajectories show in Figure <ref> and in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (0,10) ;
[fill=black] (a) circle (0.105) node [above right] $V_1$;
(b) at (-10,0) ;
[fill=black] (b) circle (0.105) node [above left] $V_2$;
(c) at (0,-10) ;
[fill=black] (c) circle (0.105) node [below left] $V_3$;
(d) at (10,0) ;
[fill=black] (d) circle (0.105) node [above right] $V_4$;
[line width=0.25mm, black] (10,0)–(0,10)–(-10,0)–(0,-10)–(10,0);

at (a) (0,10) ;
[fill=red] (a) circle (0.25) node [left] $S^{(1)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (d) at (10,0) ;
[below right] at (d.south east) $S^{(2)}$;
[line width=0.5mm, red, mid arrow] (0,10) – (10,0);

at (b) (-10,0) ;
[fill=blue] (b) circle (0.25) node [below left] $Q^{(1)}$;
(e) at (3.7,-3.7) ;
[fill=blue] (e) circle (0.25) node [below right] $Q^{(2)}$;
[diamond, draw=blue, fill=blue, minimum size=0.25cm, inner sep=0] (c) at (0,-10) ;
[below right] at (c.south east) $Q^{(3)}$;
[line width=0.5mm, blue, mid arrow] (-10,0) – (3.7,-3.7);
[line width=0.5mm, blue, mid arrow] (3.7,-3.7) – (0,-10);
[dashed] [line width=0.5mm, blue] [-latex] (3.7,-3.7) – (10,0);

A search trajectory for 41.
Trajectory details can be found in Table <ref>.

$i$     Agent     Vertex     $t_i$     $Q^{(i)}$     $d(Q^{(i)} , Exit)$     Cost

1     $S_1$     $V_1$     0     $V_2$     $e_4$     $e_4$

2     $Q$     $V_2$     0     $V_2$     0     0

3     $S_1$     $V_4$     $e_4$     $(\tfrac{1}{2}(-1 + \sqrt{3}),\tfrac{1}{2}(1-\sqrt{3}))$     $-1+\sqrt{3}$     ${-1+\sqrt{2}+\sqrt{3}}^*$

4     $Q$     $V_3$     $-1+\sqrt{2}+\sqrt{3}$     $V_3$     0     ${-1+\sqrt{2}+\sqrt{3}}^*$

Trajectories' details for the upper bound of 41; see Figure <ref>.

The evacuation time is maximized when the exit is placed at either $V_3$ or $V_4$. The point $Q^{(3)}$ is found by equating the evacuation times for both above placements of the exit. Moreover, $Q^{(3)}$ is given as the solution to the following non-linear system

\begin{align}
&       \| V_3 -Q^{(3)}\| =\| V_4-Q^{(3)} \| 	        \label{k1n4eq1} \\
&       \| V_2 -Q^{(3)}\|=e_4		        \label{k1n4eq2}
\end{align}

(<ref>) is found by equating the evacuation times for when the exit is placed at $V_3$ and $V_4$. Similarly, (<ref>) is derived from imposing that the distance the Queen travels from $Q^{(2)}$ to $Q^{(3)}$ is exactly $e_4$.

§.§.§ 51

We use $s=(1,0,1,0,0)$ and $\rho=(1,4,5,3,2)$.
The agents' trajectories show in Figure <ref> and in Table <ref>.
Note that the Queen waits a $V_4$ for a time such that the Queen reaches $Q^{(3)}$ at time $e_5$.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (3.1,9.5) ;
[fill=black] (a) circle (0.105) node [above right] $V_1$;
(b) at (-8.1,5.9) ;
[fill=black] (b) circle (0.105) node [left] $V_2$;
(c) at (-8.1,-5.9) ;
[fill=black] (c) circle (0.105) node [left] $V_3$;
(d) at (3.1,-9.5) ;
[fill=black] (d) circle (0.105) node [below left] $V_4$;
(e) at (10,0) ;
[fill=black] (e) circle (0.105) node [above right] $V_5$;

[line width=0.25mm, black] (10,0)–(3.1,9.5)–(-8.1,5.9)–(-8.1,-5.9)–(3.1,-9.5)–(10,0);

at (a) (3.1,9.5) ;
[fill=red] (a) circle (0.25) node [below left] $S^{(1)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (e) at (10,0) ;
[below right] at (e.south east) $S^{(2)}$;
[line width=0.5mm, red, mid arrow] (3.1,9.5) – (10,0);

at (d) (3.1,-9.5) ;
[fill=blue] (d) circle (0.25) node [below right] $Q^{(1)}$;
(f) at (-4.6,-4.8) ;
[fill=blue] (f) circle (0.25) node [above] $Q^{(2)}$;
at (c) (-8.1,-5.9) ;
[fill=blue] (c) circle (0.25) node [below] $Q^{(3)}$;
[diamond, draw=blue, fill=blue, minimum size=0.25cm, inner sep=0] (b) at (-8.1,5.9) ;
[below right] at (b.south east) $Q^{(4)}$;
[line width=0.5mm, blue, mid arrow] (3.1,-9.5) – (-4.6,-4.8);
[line width=0.5mm, blue, mid arrow] (-4.6,-4.8) – (-8.1,-5.9);
[line width=0.5mm, blue, mid arrow] (-8.1,-5.9) – (-8.1,5.9);
[dashed] [line width=0.5mm, blue] [-latex] (-4.6,-4.8) – (10,0);

A search trajectory for 51.
Trajectory details can be found in Table <ref>.
Note that the Queen waits a $V_4$ for a time such that the Queen reaches $Q^{(2)}$ at time $e_5$.

$i$     Agent     Vertex     $t_i$     $Q^{(i)}$     $d(Q^{(i)} , Exit)$     Cost

1     $S_1$     $V_1$     0     $V_4$     $2\sin(\tfrac{2\pi}{5})$    $2\sin(\tfrac{2\pi}{5})$

2     $Q$     $V_4$     0     $V_4$     0     0

3     $S_1$     $V_5$     $e_5$     $(-0.46353,-0.47553)$     1.53884     ${2.71441}^*$

4     $Q$     $V_3$     1.53884     $V_3$     0     1.53884

5     $Q$     $V_2$     2.71441     $V_2$     0     ${2.71441}^*$

Trajectories' details for the upper bound of 51; see Figure <ref>.

The evacuation time is maximized when the exit is placed at either $V_2$ or $V_5$. The point $Q^{(3)}$ is found by equating the evacuation times for both above placements of the exit. Note that we require that $Q^{(3)}$ is a convex combination of the points $V_3$ and $V_5$, where $Q^{(3)}=(1-l)V_3+lV_5$, and $l\in [0,1]$. The value of $l$ can be found by solving the following equation $(1-2l)\| V_3 -V_5 \| = e_5$, asserting that the evacuation times for when the exit is placed at $V_5$ and $V_2$ have to be equal. It follows that $l=0.19098$

§.§.§ 61

We use $s=(1,0,1,0,1,0)$ and $\rho=(1,2,6,3,5,4)$.
The agents' trajectories show in Figure <ref> and in Table <ref>.
The Queen waits at $Q^{(3)}$ until time $e_6$ has elapsed.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (5,8.7) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (-5,8.7) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-10,0) ;
[fill=black] (c) circle (0.105) node [above left] $V_3$;
(d) at (-5,-8.7) ;
[fill=black] (d) circle (0.105) node [below left] $V_4$;
(e) at (5,-8.7) ;
[fill=black] (e) circle (0.105) node [below right] $V_5$;
(f) at (10,0) ;
[fill=black] (f) circle (0.105) node [above right] $V_6$;

[line width=0.25mm, black] (10,0)–(5,8.7)–(-5,8.7)–(-10,0)–(-5,-8.7)–(5,-8.7)–(10,0);

at (a) (5,8.7) ;
[fill=red] (a) circle (0.25) node [below left] $S^{(1)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (f) at (10,0) ;
[below right] at (f.south east) $S^{(2)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (e) at (5,-8.7) ;
[below left] at (e.south east) $S^{(4)}$;
[line width=0.5mm, red, mid arrow] (5,8.7) – (10,0);
[line width=0.5mm, red, mid arrow] (10,0) – (5,-8.7);

at (b) (-5,8.7) ;
[fill=blue] (b) circle (0.25) node [below right] $Q^{(1)}$;
(g) at (-8.7,0) ;
[fill=blue] (g) circle (0.25) node [right] $Q^{(2)}$;
at (c) (-10,0) ;
[fill=blue] (c) circle (0.25) node [below left] $Q^{(3)}$;
(h) at (-2.5,-4.3) ;
[fill=blue] (h) circle (0.25) node [above right] $Q^{(4)}$;
at (d) (-5,-8.7) ;
[fill=blue] (d) circle (0.25) node [below right] $Q^{(5)}$;
[line width=0.5mm, blue, mid arrow] (-5,8.7) – (-8.7,0);
[line width=0.5mm, blue] (-8.7,0)  – (-10,0) node[currarrow,blue,pos=0.5,xscale=-1,sloped,scale=0.75] ;

[line width=0.5mm, blue, mid arrow] (-10,0) – (-2.5,-4.3);
[line width=0.5mm, blue, mid arrow] (-2.5,-4.3) – (-5,-8.7);
[dashed] [line width=0.5mm, blue] [-latex] (-8.7,0) – (10,0);
[dashed] [line width=0.5mm, blue] [-latex] (-2.5,-4.3) – (5,-8.7);

A search trajectory for 61.
Trajectory details can be found in Table <ref>.
The Queen waits at $Q^{(2)}$ until time $e_n$ has elapsed.

$i$     Agent     Vertex     $t_i$     $Q^{(i)}$     $d(Q^{(i)} , Exit)$     Cost

1     $S_1$     $V_1$     0     $V_2$     $e_6$     $e_6$

2     $Q$     $V_2$     0     $V_2$     0     0

3     $S_1$     $V_6$     $e_6$     $(-\tfrac{\sqrt{3}}{2}, 0)$     $1+\tfrac{\sqrt{3}}{2}$     ${2+\tfrac{\sqrt{3}}{2}}^*$

4     $Q$     $V_3$     $2-\tfrac{\sqrt{3}}{2}$     $V_3$     0     $2-\tfrac{\sqrt{3}}{2}$

5     $S_1$     $V_5$     $2e_6$     $(-\tfrac{1}{4},-\tfrac{\sqrt{3}}{4}) $     $\tfrac{\sqrt{3}}{2}$     ${2+\tfrac{\sqrt{3}}{2}}^*$

6     $Q$     $V_4$     $\tfrac{5}{2}$     $V_4$     0     $\tfrac{5}{2}$

Trajectories' details for the upper bound of 61;
see Figure <ref>.

The evacuation time is maximized when the exit is placed at either $V_6$ or $V_5$. The point $Q^{(3)}$ and $Q^{(5)}$ are found by equating the evacuation times for both above placements of the exit. Moreover, we require that the points $Q^{(3)}$ and $Q^{(5)}$ are convex combinations of the points, $V_3$ and $V_6$, and $V_3$ and $V_5$, respectively.

Hence, we require that $Q^{(3)}=(1-l_1)V_3 +l_1V_6$ and $Q^{(5)}=(1-l_2)V_3+l_2V_5$, for $l_1,l_2\in [0,1]$.
We determine $l_1$ and $l_2$ by solving to the following system.

\begin{eqnarray}
&    (1-l_1) \| V_6-V_3 \|-(1-l_2)\| V_5-V_3 \|=e_6 	\label{k1n6eq1} \\
&    l_1 \| V_6-V_3 \| + l_2 \| V_5-V_3 \| =e_6	\label{k1n6eq2}
\end{eqnarray}

(<ref>) is derived from equating the evacuation times for when the exit is placed at $V_6$ and $V_5$. Similarly, (<ref>) is derived by imposing that the time taken by the Queen to travel from $Q^{(3)}$ to $V_3$ to $Q^{(5)}$ is $e_6$. It follows that $l_1=\tfrac{1}{2}(1-\tfrac{\sqrt{3}}{2})$ and $l_2=\tfrac{1}{2}$.

§.§.§ 71

We use $s=(0,1,1,0,1,0,0)$ and $\rho=(1,2,3,7,4,6,5)$.
The agents' trajectories show in Figure <ref> and in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (6.2,7.8) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (-2.2,9.7) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-9,4.3) ;
[fill=black] (c) circle (0.105) node [above left] $V_3$;
(d) at (-9,-4.3) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-2.2,-9.7) ;
[fill=black] (e) circle (0.105) node [below left] $V_5$;
(f) at (6.2,-7.8) ;
[fill=black] (f) circle (0.105) node [below right] $V_6$;
(g) at (10,0) ;
[fill=black] (g) circle (0.105) node [above right] $V_7$;

[line width=0.25mm, black] (10,0)–(6.2,7.8)–(-2.2,9.7)–(-9,4.3)–(-9,-4.3)–(-2.2,-9.7)–(6.2,-7.8)–(10,0);

(b) at (-2.2,9.7) ;
[fill=red] (b) circle (0.25) node [below] $S^{(1)}$;
(c) at (-9,4.3) ;
[fill=red] (c) circle (0.25) node [below left] $S^{(2)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (d) at (-9,-4.3) ;
[below left] at (d.south east) $S^{(3)}$;
[line width=0.5mm, red, mid arrow] (-2.2,9.7) – (-9,4.3);
[line width=0.5mm, red, mid arrow] (-9,4.3) – (-9,-4.3);

(a) at (6.2,7.8) ;
[fill=blue] (a) circle (0.25) node [below left] $Q^{(1)}$;
(g) at (10,0) ;
[fill=blue] (g) circle (0.25) node [below right] $Q^{(2)}$;
(h) at (3.3,-5.5) ;
[fill=blue] (h) circle (0.25) node [below left] $Q^{(3)}$;
(f) at (6.2,-7.8) ;
[fill=blue] (f) circle (0.25) node [below left] $Q^{(4)}$;
[diamond, draw=blue, fill=blue, minimum size=0.25cm, inner sep=0] (e) at (-2.2,-9.7) ;
[below right] at (e.south east) $Q^{(5)}$;
[line width=0.5mm, blue, mid arrow] (6.2,7.8) – (10,0);
[line width=0.5mm, blue, mid arrow] (10,0) – (3.3,-5.5);
[line width=0.5mm, blue, mid arrow] (3.3,-5.5) – (6.2,-7.8);
[line width=0.5mm, blue, mid arrow] (6.2,-7.8) – (-2.2,-9.7);
[dashed] [line width=0.5mm, blue] [-latex] (3.3,-5.5) – (-9,-4.3);

A search trajectory for 71.
Trajectory details can be found in Table <ref>.

$i$     Agent     Vertex     $t_i$     $Q^{(i)}$     $d(Q^{(i)} , Exit)$     Cost

1     $Q$     $V_1$     0     $V_1$     0     0

2     $S_1$     $V_2$     0     $V_1$     $e_7$     $e_7$

3     $S_1$     $V_3$     $e_7$     $V_7$     $2\sin(\tfrac{3\pi}{7})$     $e_7+2\sin(\tfrac{3\pi}{7})$

4     $Q$     $V_7$     $e_7$     $V_7$     0     $e_7$

5     $S_1$     $V_4$     $2e_7$     $(0.33162,-0.55344)$     1.23838     ${2.97391}^*$

6     $Q$     $V_6$     2.10614     $V_6$     0     2.10614

7     $Q$     $V_5$     2.97391     $V_5$     0     ${2.97391}^*$

Trajectories' details for the upper bound of 71;
see Figure <ref>.

The evacuation time is maximized when the exit is placed at either $V_4$ or $V_5$. The point $Q^{(5)}$ is found by equating the evacuation times for both above placements of the exit. The point $Q^{(5)}$ is given as the solution to the following non-linear system

\begin{eqnarray}
&        \| Q^{(5)}-V_4 \| -\| Q^{(5)}-V_6\|=e_7	        \label{k1n7eq1} \\
&        \| Q^{(5)}-V_7 \| = e_7        \label{k1n7eq2}
\end{eqnarray}

(<ref>) is derived by equating the evacuation times for when the exit is placed at $V_4$ and $V_5$.
Similarly, (<ref>) is derived by imposing that the time taken for the Queen to travel from $V_7$ to $Q^{(5)}$ is exactly $e_7$.

§.§.§ 81

We use $s=(0,1,1,0,1,0,1,0)$ and $\rho=(1,2,3,8,4,6,5,7)$.
The agents' trajectories show in Figure <ref> and in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (7.1,7.1) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (0,10) ;
[fill=black] (b) circle (0.105) node [above right] $V_2$;
(c) at (-7.1,7.1) ;
[fill=black] (c) circle (0.105) node [above left] $V_3$;
(d) at (-10,0) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-7.1,-7.1) ;
[fill=black] (e) circle (0.105) node [below left] $V_5$;
(f) at (0, -10) ;
[fill=black] (f) circle (0.105) node [below right] $V_6$;
(g) at (7.1,-7.1) ;
[fill=black] (g) circle (0.105) node [below right] $V_7$;
(h) at (10,0) ;
[fill=black] (h) circle (0.105) node [above right] $V_8$;

[line width=0.25mm, black] (10,0)–(7.1,7.1)–(0,10)–(-7.1,7.1)–(-10,0)–(-7.1,-7.1)–(0, -10)–(7.1,-7.1)–(10,0);

at (b) (0,10) ;
[fill=red] (b) circle (0.25) node [below] $S^{(1)}$;
at (c) (-7.1,7.1) ;
[fill=red] (c) circle (0.25) node [below right] $S^{(2)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (d) at (-10,0) ;
[below left] at (d.south east) $S^{(3)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (e) at (-7.1,-7.1) ;
[above right] at (e.south east) $S^{(5)}$;
[line width=0.5mm, red, mid arrow] (0,10) – (-7.1,7.1);
[line width=0.5mm, red, mid arrow] (-7.1,7.1) – (-10,0);
[line width=0.5mm, red, mid arrow] (-10,0) – (-7.1,-7.1);

at (a) (7.1,7.1) ;
[fill=blue] (a) circle (0.25) node [below left] $Q^{(1)}$;
at (h) (10,0) ;
[fill=blue] (h) circle (0.25) node [below right] $Q^{(2)}$;
(i) at (4.2,-4.9) ;
[fill=blue] (i) circle (0.25) node [above left] $Q^{(3)}$;
at (f) (0, -10) ;
[fill=blue] (f) circle (0.25) node [below left] $Q^{(4)}$;
(j) at (0,-8.9) ;
[fill=blue] (j) circle (0.25) node [above left] $Q^{(5)}$;
[diamond, draw=blue, fill=blue, minimum size=0.25cm, inner sep=0] (g) at (7.1,-7.1) ;
[above left] at (g.south east) $Q^{(6)}$;
[line width=0.5mm, blue, mid arrow] (7.1,7.1) – (10,0);
[line width=0.5mm, blue, mid arrow] (10,0) – (4.2,-4.9);
[line width=0.5mm, blue, mid arrow] (4.2,-4.9) – (0, -10);
[line width=0.5mm, blue] (0, -10)  – (0,-8.9) node[currarrow,blue,pos=0.5,xscale=1,sloped,scale=0.75] ;

[line width=0.5mm, blue, mid arrow] (0,-8.9) – (7.1,-7.1);
[dashed] [line width=0.5mm, blue] [-latex] (4.2,-4.9) – (-10,0);
[dashed] [line width=0.5mm, blue] [-latex] (0,-8.9) – (-7.1,-7.1);

A search trajectory for 81.
Trajectory details can be found in Table <ref>.

$i$     Agent     Vertex     $t_i$     $Q^{(i)}$     $d(Q^{(i)} , Exit)$     Cost

1     $Q$     $V_1$     0     $V_1$     0     0

2     $S_1$     $V_2$     0     $V_1$     $e_8$     $e_8$

3     $S_1$     $V_3$     $e_8$     $V_8$     $2\sin(\tfrac{3\pi}{8})$     $\sqrt{2(2+\sqrt{2})}$

4     $Q$     $V_8$     $e_8$     $V_8$     0     $e_8$

5     $S_1$     $V_4$     $2e_8$     $(0.41287,-0.49099)$     1.49575     ${3.02649}^*$

6     $Q$     $V_6$     2.18614     $V_6$     0     2.18614

7      $S_1$     $V_5$     $3e_8$     $(0,-0.89004$)     0.76039     ${3.02649}^*$

8     $Q$     $V_7$     3.02649     $V_7$     0     ${3.02649}^*$

Trajectories' details for the upper bound of 81;
see Figure <ref>.

The evacuation time is maximized when the exit is placed at either $V_8$, $V_5$, or $V_7$. The points $Q^{(5)}$ and $Q^{(7)}$ are found by equating the evacuation times for all above placements of the exit. The points $Q^{(5)}$ and $Q^{(7)}$ are given as the solution to the following non-linear system

\begin{eqnarray}
&        \| Q^{(5)}-V_8 \| = e_8		  \label{k1n8eq1}\\
&        \| Q^{(5)}-V_6 \| +\| Q^{(7)}-V_6 \| = e_8		    \label{k1n8eq2}\\
&      \| Q^{(7)}-V_7 \|-\| Q^{(7)}-V_5 \| =0		  \label{k1n8eq3} \\
&        \| Q^{(5)}-V_4 \|-\| Q^{(7)}-V_5 \|=e_8		    \label{k1n8eq4}
\end{eqnarray}

(<ref>) is derived by imposing that the time taken by the Queen to travel from $V_8$ to $Q^{(5)}$ is exactly $e_8$.
(<ref>) is derived by imposing that the time taken by the Queen to travel from $Q^{(5)}$ to $V_6$ to $Q^{(7)}$ is exactly $e_8$.
(<ref>) is derived by equating the evacuation times for when the exit is placed at $V_7$ and $V_5$.
(<ref>) is derived by equating the evacuation time for when the exit is placed at $V_4$ and $V_5$.

§.§.§ 91

We use $s=(1,0,1,0,1,0,1,0,1)$ and $\rho=(1,2,9,3,8,4,7,5,6)$.
The agents' trajectories show in Figure <ref> and in Table <ref>.
The Queen waits at $V_3$ for an amount of time such that the Queen arrives at $Q^{(5)}$ at time $2e_9$.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (7.7,6.4) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (1.7,9.8) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-5,8.7) ;
[fill=black] (c) circle (0.105) node [above] $V_3$;
(d) at (-9.4,3.4) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-9.4,-3.4) ;
[fill=black] (e) circle (0.105) node [below left] $V_5$;
(f) at (-5,-8.7) ;
[fill=black] (f) circle (0.105) node [below left] $V_6$;
(g) at (1.7,-9.8) ;
[fill=black] (g) circle (0.105) node [below right] $V_7$;
(h) at (7.7,-6.4) ;
[fill=black] (h) circle (0.105) node [below right] $V_8$;
(i) at (10,0) ;
[fill=black] (i) circle (0.105) node [above right] $V_9$;

[line width=0.25mm, black] (10,0)–(7.7,6.4)–(1.7,9.8)–(-5,8.7)–(-9.4,3.4)–(-9.4,-3.4)–(-5,-8.7)–(1.7,-9.8)–(7.7,-6.4)–(10,0);

at (a) (7.7,6.4) ;
[fill=red] (a) circle (0.25) node [below left] $S^{(2)}$;
at (i) (10,0) ;
[fill=red] (i) circle (0.25) node [below right] $S^{(4)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (h) at (7.7,-6.4) ;
[above right] at (h.south east) $S^{(5)}$;

[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (g) at (1.7,-9.8) ;
[below left] at (g.south east) $S^{(7)}$;

[line width=0.5mm, red, mid arrow] (7.7,6.4) – (10,0);
[line width=0.5mm, red, mid arrow] (10,0) – (7.7,-6.4);
[line width=0.5mm, red, mid arrow] (7.7,-6.4) – (1.7,-9.8);

at (b) (1.7,9.8) ;
[fill=blue] (b) circle (0.25) node [below] $Q^{(2)}$;
at (c) (-5,8.7) ;
[fill=blue] (c) circle (0.25) node [below right] $Q^{(4)}$;

(j) at (-8,2.8) ;
[fill=blue] (j) circle (0.25) node [right] $Q^{(5)}$;
at (d) (-9.4,3.4) ;
[fill=blue] (d) circle (0.25) node [below left] $Q^{(6)}$;
(k) at (-5.8,-0.9) ;
[fill=blue] (k) circle (0.25) node [right] $Q^{(7)}$;
at (e) (-9.4,-3.4) ;
[fill=blue] (e) circle (0.25) node [above left] $Q^{(8)}$;
at (f) (-5,-8.7) ;
[fill=blue] (f) circle (0.25) node [above right] $Q^{(9)}$;
[line width=0.5mm, blue, mid arrow] (1.7,9.8) – (-5,8.7);
[line width=0.5mm, blue, mid arrow] (-5,8.7) – (-8,2.8);

[line width=0.5mm, blue] (-8,2.8)  – (-9.4,3.4) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;
[line width=0.5mm, blue, mid arrow] (-9.4,3.4) – (-5.8,-0.9);
[line width=0.5mm, blue, mid arrow] (-5.8,-0.9) – (-9.4,-3.4);
[line width=0.5mm, blue, mid arrow] (-9.4,-3.4) – (-5,-8.7);

[dashed] [line width=0.5mm, blue] [-latex] (-8,2.8) – (7.7,-6.4);
[dashed] [line width=0.5mm, blue] [-latex] (-5.8,-0.9) – (1.7,-9.8);

A search trajectory for 91.
Trajectory details can be found in Table <ref>.
The Queen waits at $V_3$ for an amount of time such that the Queen arrives at $Q^{(5)}$ at time $2e_9$. The position of $Q^{(5)}$ has been adjusted for clarity.

$i$     Agent     Vertex     $t_i$     $Q^{(i)}$     $d(Q^{(i)} , Exit)$     Cost

1     $S_1$     $V_1$     0     $V_2$     $e_9$     $e_9$

2     $Q$     $V_2$     0     $V_2$     0     $2\sin(\tfrac{\pi}{9})$

3     $S_1$     $V_9$     $e_9$     $V_3$     $\sqrt{3}$     $e_9+\sqrt{3}$

4     $Q$     $V_3$     $e_9$     $V_3$     0     $e_9$

5     $S_1$     $V_8$     $2e_9$     $(-0.83682,0.28263)$     1.85083     ${3.21891}^*$

6     $Q$     $V_4$     1.48686     $V_4$     0     1.48686

7     $S_1$     $V_7$     $3e_9$     $(-0.57635,-0.09099)$     1.16679     ${3.21891}^*$

8     $Q$     $V_5$     2.49374     $V_5$     0     2.49374

9     $Q$     $V_6$     3.17778     $V_6$     0     3.17778

Trajectories' details for the upper bound of 91;
see Figure <ref>.

The evacuation time is maximized when the exit is placed at either $V_8$ or $V_7$. The points $Q^{(5)}$ and $Q^{(7)}$ are found by equating the evacuation times for both above placements of the exit. The points $Q^{(5)}$ and $Q^{(7)}$ are given as convex combinations of the points, $V_4$ and $V_8$, and $V_4$ and $V_7$, respectively.
Thus, we require that

$Q^{(5)}=(1-l_1)V_4+l_1V_8$ and $Q^{(7)}=(1-l_2)V_4+l_2V_7$, for some $l_1,l_2\in [0,1]$. The values for $l_1$ and $l_2$ are given as the solution to the following non-linear system

\begin{eqnarray}
&      l_1\| V_4 -V_8\|+l_2\| V_4-V_7\|=e_9	    \label{k1n9eq1}\\
&      (1-l_1)\| V_4 -V_8\|=l_1\| V_4 -V_8\|+(1-l_2)\| V_4-V_7\|+l_2\| V_4-V_7\|.		        \label{k1n9eq2}
\end{eqnarray}

The solution to the system above satisfies $l_1\| V_4 -V_8\|\leq e_9$.
Moreover, (<ref>) is derived by imposing that the time taken by the Queen to travel from $Q^{(5)}$ to $V_4$ to $Q^{(7)}$ is exactly $e_9$.
Similarly, (<ref>) is derived by equating the evacuation times for when the exit is placed at $V_8$ and $V_7$.
It follows that $l_1=0.06031$ and $l_2=0.32635$.

§.§.§ 101

We use $s=(1,0,1,0,1,0,1,0,1,0)$ and $\rho=(1,2,10,3,9,4,8,6,7,5)$.
The agents' trajectories show in Figure <ref> and in Table <ref>.
The Queen waits at $V_3$ for an amount of time such that the Queen arrives at $Q^{(5)}$ at time $2e_{10}$. The position of $Q^{(5)}$ has been adjusted for clarity.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (8.1,5.9) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (3.1,9.5) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-3.1,9.5) ;
[fill=black] (c) circle (0.105) node [above] $V_3$;
(d) at (-8.1,5.9) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-10,0) ;
[fill=black] (e) circle (0.105) node [above left] $V_5$;
(f) at (-8.1,-5.9) ;
[fill=black] (f) circle (0.105) node [below left] $V_6$;
(g) at (-3.1,-9.5) ;
[fill=black] (g) circle (0.105) node [below] $V_7$;
(h) at (3.1,-9.5) ;
[fill=black] (h) circle (0.105) node [below right] $V_8$;
(i) at (8.1,-5.9) ;
[fill=black] (i) circle (0.105) node [below right] $V_9$;
(j) at (10,0) ;
[fill=black] (j) circle (0.105) node [above right] $V_{10}$;

[line width=0.25mm, black] (10,0)–(8.1,5.9)–(3.1,9.5)–(-3.1,9.5)–(-8.1,5.9)–(-10,0)–(-8.1,-5.9)–(-3.1,-9.5)–(3.1,-9.5)–(8.1,-5.9)–(10,0);

at (a) (8.1,5.9) ;
[fill=red] (a) circle (0.25) node [below left] $S^{(1)}$;
at (j) (10,0) ;
[fill=red] (j) circle (0.25) node [below left] $S^{(2)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (i) at (8.1,-5.9) ;
[left] at (i.south east) $S^{(3)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (h) at (3.1,-9.5) ;
[below left] at (h.south east) $S^{(5)}$;
at (g) (-3.1,-9.5) ;
[fill=red] (g) circle (0.25) node [above right] $S^{(6)}$;
[line width=0.5mm, red, mid arrow] (8.1,5.9) – (10,0);
[line width=0.5mm, red, mid arrow] (10,0) – (8.1,-5.9);
[line width=0.5mm, red, mid arrow] (8.1,-5.9) – (3.1,-9.5);
[line width=0.5mm, red, mid arrow] (3.1,-9.5) – (-3.1,-9.5);

at (b) (3.1,9.5) ;
[fill=blue] (b) circle (0.25) node [below] $Q^{(1)}$;
at (c) (-3.1,9.5) ;
[fill=blue] (c) circle (0.25) node [below] $Q^{(2)}$;

(k) at (-7,5) ;
[fill=blue] (k) circle (0.25) node [below right] $Q^{(3)}$;
at (d) (-8.1,5.9) ;
[fill=blue] (d) circle (0.25) node [below left] $Q^{(4)}$;
(l) at (-6.5,0.1) ;
[fill=blue] (l) circle (0.25) node [below right] $Q^{(5)}$;
at (f) (-8.1,-5.9) ;
[fill=blue] (f) circle (0.25) node [right] $Q^{(6)}$;
at (e) (-10,0) ;
[fill=blue] (e) circle (0.25) node [below left] $Q^{(7)}$;
[line width=0.5mm, blue, mid arrow] (3.1,9.5) – (-3.1,9.5);

[line width=0.5mm, blue, mid arrow] (-3.1,9.5) – (-7,5);

[line width=0.5mm, blue] (-7,5)  – (-8.1,5.9) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;
[line width=0.5mm, blue, mid arrow] (-8.1,5.9) – (-6.5,0.1);
[line width=0.5mm, blue, mid arrow] (-6.5,0.1) – (-8.1,-5.9);
[line width=0.5mm, blue, mid arrow] (-8.1,-5.9) – (-10,0);

[dashed] [line width=0.5mm, blue] [-latex] (-7,5) – (8.1,-5.9);
[dashed] [line width=0.5mm, blue] [-latex] (-6.5,0.1) – (3.1,-9.5);

A search trajectory for 101.
Trajectory details can be found in Table <ref>.
The Queen waits at $V_3$ for an amount of time such that the queen arrives at $Q^{(3)}$ at time $2e_{10}$. The position of $Q^{(3)}$ has been adjusted for clarity.

$i$     Agent     Vertex     $t_i$     $Q^{(i)}$     $d(Q^{(i)} , Exit)$     Cost

1     $S_1$     $V_1$     0     $V_2$     $\tfrac{1}{2}(-1+\sqrt{5})$     $\tfrac{1}{2}(-1+\sqrt{5})$

2     $Q$     $V_2$     0     $V_2$     0     0

3     $S_1$     $V_{10}$     $e_{10}$     $V_3$     $2\sin(\tfrac{3\pi}{10})$     $\tfrac{1}{2}(-1+\sqrt{5})+2\sin(\tfrac{3\pi}{10})$

4     $Q$     $V_3$     $e_{10}$     $V_3$     0     $\tfrac{1}{2}(-1+\sqrt{5})$

5     $S_1$     $V_9$     $2e_{10}$     $(-0.79237,0.57569)$     1.97942     ${3.21549}^{*}$

6     $Q$     $V_4$     1.2506     $V_4$     0     1.2506

7     $S_1$     $V_8$     $3e_{10}$     $(-0.65457,0.01064)$     1.36138     ${3.21549}^{*}$

8     $Q$     $V_6$     $4e_{10}$     $V_6$     0     $4e_{10}$

9     $S_1$     $V_7$     $4e_{10}$     $V_6$     $e_{10}$     $5e_{10}$

10     $Q$     $V_5$     $5e_{10}$     $V_5$     0     $5e_{10}$

Trajectories' details for the upper bound of 101;
see Figure <ref>.

The evacuation time is maximized when the exit is placed at either $V_9$ or $V_8$. The points $Q^{(5)}$ and $Q^{(7)}$ are found by equating the evacuation times for both above placements of the exit. The points $Q^{(5)}$ and $Q^{(7)}$ are given as the solution to the following non-linear system

\begin{eqnarray}
&        l\| V_4-V_9\| + \| Q^{(7)}-V_4\|=e_{10}	        \label{k1n10eq1}\\
&      (1-l)\| V_4-V_9\|-\| Q^{(7)}-V_8\|=e_{10}.	      \label{k1n10eq2}\\
&	      \| V_3-((1-l)V_4+lV_9)\| + t =e_{10}		                    \label{k1n10eq3}\\
\end{eqnarray}

(<ref>) is derived by imposing that the time taken by the Queen to travel from $Q^{(5)}$ to $V_4$ to $Q^{(7)}$ is exactly $e_{10}$.
(<ref>) is derived by imposing equating the evacuation times for when the exit is placed at $V_8$ and $V_9$.
(<ref>) is derived by imposing that the Queen arrives at $Q^{(5)}$ at time $2e_{10}$. Note that $t$ denotes the total time the Queen spends waiting, given as $t=e_{10}-\| Q^{(5)}-V_3\|$.
It follows that $l=0.01029$.

§.§.§ 111

We use $s=(1,0,0,1,1,0,1,0,1,0,0)$ and $\rho=(1,2,3,11,10,4,9,5,8,6,7)$.
The agents' trajectories show in Figure <ref> and in Table <ref>.

mid arrow/.style=
postaction=decorate, decoration=markings, mark=at position 0.6 with latex

(a) at (8.4,5.4) ;
[fill=black] (a) circle (0.105) node [above] $V_1$;
(b) at (4.2,9.1) ;
[fill=black] (b) circle (0.105) node [above] $V_2$;
(c) at (-1.4,9.9) ;
[fill=black] (c) circle (0.105) node [above] $V_3$;
(d) at (-6.5,7.6) ;
[fill=black] (d) circle (0.105) node [above left] $V_4$;
(e) at (-9.6,2.8) ;
[fill=black] (e) circle (0.105) node [above left] $V_5$;
(f) at (-9.6,-2.8) ;
[fill=black] (f) circle (0.105) node [below left] $V_6$;
(g) at (-6.5,-7.6) ;
[fill=black] (g) circle (0.105) node [below left] $V_7$;
(h) at (-1.4,-9.9) ;
[fill=black] (h) circle (0.105) node [below right] $V_8$;
(i) at (4.2,-9.1) ;
[fill=black] (i) circle (0.105) node [below right] $V_9$;
(j) at (8.4,-5.4) ;
[fill=black] (j) circle (0.105) node [below right] $V_{10}$;
(k) at (10,0) ;
[fill=black] (k) circle (0.105) node [above right] $V_{11}$;

[line width=0.25mm, black] (10,0)–(8.4,5.4)–(4.2,9.1)–(-1.4,9.9)–(-6.5,7.6)–(-9.6,2.8)–(-9.6,-2.8)–(-6.5,-7.6)–(-1.4,-9.9)–(4.2,-9.1)–(8.4,-5.4)–(10,0);

at (a) (8.4,5.4) ;
[fill=red] (a) circle (0.25) node [below left] $S^{(1)}$;
at (k) (10,0) ;
[fill=red] (k) circle (0.25) node [below left] $S^{(2)}$;
at (j) (8.4,-5.4) ;
[fill=red] (j) circle (0.25) node [above left] $S^{(3)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (i) at (4.2,-9.1) ;
[below left] at (i.south east) $S^{(4)}$;
[diamond, draw=red, fill=red, minimum size=0.25cm, inner sep=0] (h) at (-1.4,-9.9) ;
[below left] at (h.south east) $S^{(6)}$;
[line width=0.5mm, red, mid arrow] (8.4,5.4) – (10,0);
[line width=0.5mm, red, mid arrow] (10,0) – (8.4,-5.4);
[line width=0.5mm, red, mid arrow] (8.4,-5.4) – (4.2,-9.1);
[line width=0.5mm, red, mid arrow] (4.2,-9.1) – (-1.4,-9.9);

at (b) (4.2,9.1) ;
[fill=blue] (b) circle (0.25) node [below left] $Q^{(1)}$;
at (c) (-1.4,9.9) ;
[fill=blue] (c) circle (0.25) node [below] $Q^{(2)}$;
at (d) (-6.5,7.6) ;
[fill=blue] (d) circle (0.25) node [below right] $Q^{(3)}$;
(l) at (-8.2,2.2) ;
[fill=blue] (l) circle (0.25) node [right] $Q^{(4)}$;
at (e) (-9.6,2.8) ;
[fill=blue] (e) circle (0.25) node [below left] $Q^{(5)}$;
(m) at (-7.4,-0.6) ;
[fill=blue] (m) circle (0.25) node [below right] $Q^{(6)}$;
at (f) (-9.6,-2.8) ;
[fill=blue] (f) circle (0.25) node [above left] $Q^{(7)}$;
at (g) (-6.5,-7.6) ;
[fill=blue] (g) circle (0.25) node [above right] $Q^{(8)}$;
[line width=0.5mm, blue, mid arrow] (4.2,9.1) – (-1.4,9.9);
[line width=0.5mm, blue, mid arrow] (-1.4,9.9) – (-6.5,7.6);
[line width=0.5mm, blue, mid arrow] (-6.5,7.6) – (-8.2,2.2);
[line width=0.5mm, blue] (-8.2,2.2)  – (-9.6,2.8) node[currarrow,blue,pos=0.55,xscale=-1,sloped,scale=0.75] ;

[line width=0.5mm, blue, mid arrow] (-9.6,2.8)– (-7.4,-0.6);
[line width=0.5mm, blue, mid arrow] (-7.4,-0.6)– (-9.6,-2.8);