CheckMyTex
Problems by file
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━┓
┃ File ┃ Count ┃
┡━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━┩
│ /main.tex │ 11 │
│ /00-Abstract.tex │ 1 │
│ /01-Introduction.tex │ 24 │
│ /02-ModelAndPreliminaries.tex │ 4 │
│ /03-Algorithm.tex │ 37 │
│ /04-Analysis.tex │ 10 │
│ /05-Experiments.tex │ 20 │
│ /06-Conclusion.tex │ 2 │
└───────────────────────────────────────────────────────────────┴──────────────┘
Problems by type
┏━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━┓
┃ Tool ┃ Rule ┃ Count ┃
┡━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━┩
│ chktex │ Warning: Command terminated with space. │ 2 │
│ │ Warning: No italic correction (`\/') found. │ 10 │
│ │ Warning: Delete this space to maintain correct │ 22 │
│ │ pagereferences. │ │
│ │ Warning: Non-breaking space (`~') should have been │ 5 │
│ │ used. │ │
│ │ Warning: Intersentence spacing (`\@') should │ 1 │
│ │ perhaps be used. │ │
│ │ Warning: You should enclose the previous │ 2 │
│ │ parenthesis with `{}'. │ │
│ aspell │ SPELLING │ 20 │
│ languagetool │ UPPERCASE_SENTENCE_START │ 1 │
│ │ DOUBLE_PUNCTUATION │ 1 │
│ │ SOME_OF_THE │ 2 │
│ │ ET_AL │ 2 │
│ │ EN_COMPOUNDS │ 1 │
│ │ SENT_START_CONJUNCTIVE_LINKING_ADVERB_COMMA │ 1 │
│ │ LARGE_NUMBER_OF │ 1 │
│ │ MISSING_COMMA_AFTER_INTRODUCTORY_PHRASE │ 1 │
│ │ UNIT_SPACE │ 1 │
│ Proselint │ after_the_deadline.redundancy │ 1 │
│ │ typography.symbols.sentence_spacing │ 1 │
│ │ weasel_words.very │ 1 │
│ CleverrefCheck │ CREF │ 22 │
│ SIUNITX │ SIUNITX │ 11 │
└────────────────┴─────────────────────────────────────────────────────┴───────┘
────────────────────────────────── /main.tex ───────────────────────────────────
0 \documentclass[letterpaper, 10 pt, conference]{ieeeconf} % Comment this
line out if you need a4paper
1 %\documentclass[a4paper, 10pt, conference]{ieeeconf} % Use this line
for a4 paper
2 \IEEEoverridecommandlockouts % This command is
only needed if
>>> [chktex] Warning: Command terminated with space.
3 % you want to use
the \thanks command
4 \overrideIEEEmargins % Needed to meet
printer requirements.
>>> [chktex] Warning: Command terminated with space.
...
59 \textcolor{blue}{\footnotesize \textsf{#1}}
60 }
61
62 %\renewcommand{\todo}[1]{} %% remove comments to hide TODOs
63
64 \DeclareCaptionType{copyrightbox}
>>> [aspell] Check spelling of word 'copyrightbox'. Suggestions: copyright box,
copyright-box, copyrights, copyright's, paintbox. Occurrences in text: 1
>>> [languagetool] This sentence does not start with an uppercase letter.
...
87
88 \title{\LARGE \bf Distributed Cohesive Control for Robot Swarms:\\
89 Maintaining Good Connectivity in the Presence of Exterior Forces}
90
91 \author{
92 Dominik Krupke$^{1}$,
>>> [aspell] Check spelling of word 'Dominik'. Suggestions: Dominick, Dominic,
Dominica, Domino, Dominion. Occurrences in text: 1
93 Maximilian Ernestus$^{1}$,
94 Michael Hemmer$^{1}$, and
95 S\'andor~P.~Fekete$^{1}$%
96 %\thanks{*This work was not supported by any organization}% <-this % stops
a space
97 %\thanks{$^{1}$ M. Ernestus is on his own, free from the burden of
institutions, searching for truth. {\tt\small maximilian@ernestus.de}}%
98 \thanks{$^{1}$S. Fekete, M. Hemmer, and D. Krupke are with the Computer
Science Department, TU Braunschweig, Braunschweig, Germany, which is also
where
>>> [aspell] Check spelling of word 'Krupke'. Suggestions: Krupp, Karaoke,
Kruger, Gripe, Crupper. Occurrences in text: 1
>>> [aspell] Check spelling of word 'Braunschweig'. Suggestions: Brunswick,
Branchlike, Brushwork, Bronchitic, Brunswick's. Occurrences in text: 2
>>> [aspell] Check spelling of word 'Braunschweig'. Suggestions: Brunswick,
Branchlike, Brushwork, Bronchitic, Brunswick's. Occurrences in text: 2
99 M. Ernestus carried out his work. {\tt\small maximilian@ernestus.de,
s.fekete@tu-bs.de, mhsaar@gmail.com, d.krupke@tu-bs.de}}%
>>> [aspell] Check spelling of word 'Ernestus'. Suggestions: Ernest's,
Earnests, Earnest's, Ernesto's, Ernst's. Occurrences in text: 1
...
161 %\input{05-DualGraphNavigation.tex}
162 %\input{05-Implementaion.tex}
163 \input{05-Experiments.tex}
164 \input{06-Conclusion.tex}
165 \section*{Acknowledgment}
166 We thank James McLurkin and SeoungKyou Lee for many helpful conversations.
>>> [aspell] Check spelling of word 'SeoungKyou'. Suggestions: Senghor, Snugly,
Sejong, Songbook, Sung. Occurrences in text: 1
167
168 \addtolength{\textheight}{-12cm} % This command serves to balance the
column lengths
>>> [languagetool] Insert a space between the numerical value and the unit
symbol.
─────────────────────────────── /00-Abstract.tex ───────────────────────────────
...
1 %Write a very short summary. Hardly any problem definition.
2 %Main contributions.
3 We present a number of powerful local mechanisms for maintaining
4 a dynamic swarm of robots with limited capabilities
5 and information, in the presence of external forces and permanent node
failures.
6 We propose a set of local {\em continuous} algorithms that together produce
a
>>> [chktex] Warning: No italic correction (`\/') found.
───────────────────────────── /01-Introduction.tex ─────────────────────────────
0
1 \section{Introduction}
2 \label{sec:introduction}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
4 %it would look weird. There's actually written policy about this.}
5
6 Consider a swarm of robots that needs to remain connected.
7 There is no central control and no knowledge of the overall environment.
8 This environment is hostile: The swarm is being pulled apart by external
forces,
9 stretching it into a number of different directions, so it is in danger of
breaking up.
>>> [Proselint] warning: Redundancy. Use 'number of' instead of 'number of
different'. Suggestion: number of
10 Individual robots are weak, with limited sensing, limited communication,
and limited connectivity;
11 even worse, each robot's expected lifetime is limited by random, permanent
failures, which may
12 destroy connectedness and functioning of the swarm as a whole.
>>> [aspell] Check spelling of word 'connectedness'. Suggestions: conceitedness,
concreteness, conceitedness's, concreteness's. Occurrences in text: 2
...
17 In this paper, we study swarm mechanisms that achieve these conflicting
goals.
18 Just like in the paper by Lee and McLurkin~\cite{lee2014distributed}, we
aim for algorithms that
19 (1) maintain connectivity, (2) are fully distributed, and
20 (3) achieve cohesiveness, i.e., a well-coordinated behavior and
21 state for all robots.
22 While \cite{lee2014distributed} present a
>>> [chktex] Warning: Non-breaking space (`~') should have been used.
23 set of rules (based on crucial elements such as boundary recognition and
boundary forces~\cite{McLurkin})
24 that achieve a ``fat'', well-rounded swarm shape even in the presence
25 of obstacles, this is no longer desirable in the presence of multiple
outside forces
26 that pull the swarm apart, as illustrated in
Figure~\ref{fig:experimentpicture}. As a consequence,
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
37
38 \begin{figure}[t]
39 \centering
40 \includegraphics[width=0.9\columnwidth]{./example}
41 \caption{A robust robot swarm emulating a Steiner tree between five
diverging attachment points.}
42 \label{fig:experimentpicture}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
43 \end{figure}
44
45 \subsection{Related Work.}
>>> [languagetool] Two consecutive dots
46 \label{ssec:related_work}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
47 One of the earliest works on flocking is Reynold's pioneering work
\cite{Reynolds}.
>>> [chktex] Warning: Non-breaking space (`~') should have been used.
48 In recent years, a considerable number of aspects and objectives have
extended this perspective.
49 We highlight only some of the ensuing papers, showing how they differ from
our perspective.
>>> [languagetool] If the text is a generality, 'of the' is not necessary.
50
51 A basic component of flocking is volumetric control, as presented by
52 Spears~\cite{Spears}: robots use local potential field controllers (with
attractive and repulsive
53 forces) for constructing a regular lattice with a corresponding base
density~\cite{Olfati-Saber2006, andrew}.
54 This does not necessarily preserve {\em connectivity}~\cite{Balch, heyes,
Spears}. While the latter can be side-stepped
>>> [chktex] Warning: No italic correction (`\/') found.
55 by simply assuming that robots are always connected~\cite{hong}, we aim for
connectivity
56 as a requirement, which is vital in a fully distributed setting in which
deterministic recovery from disconnectedness
57 may be impossible.
58
59 Some of the ideas of Olfati-Saber~\cite{Olfati-Saber2006} form the basis of
our work and are discussed
>>> [languagetool] If the text is a generality, 'of the' is not necessary.
60 in more detail further down. In~\cite{Olfati-Saber2006} and other work,
however, robots do utilize gobal information,
>>> [aspell] Check spelling of word 'gobal'. Suggestions: global, goal,
gobble, Gable, gable. Occurrences in text: 1
61 e.g., the position of a guide robot in a shared coordinate
frame~\cite{Olfati-Saber2006, yao, hung, hung2}
62 or environmental potential~\cite{Gazi}.
63 Instead of the potentials, Cortes~et.~al.~\cite{cortes} and
Magnus~et.~al.~\cite{magnus}
>>> [languagetool] Misplaced dot.
>>> [aspell] Check spelling of word 'Magnus'. Suggestions: Magnums, Magus,
Magnum, Margins, Ma gnus. Occurrences in text: 1
>>> [languagetool] Misplaced dot.
64 used Voronoi tessellation.
>>> [aspell] Check spelling of word 'Voronoi'. Suggestions: Moroni, Verona,
Boron, Corona, Moron. Occurrences in text: 1
...
70
71 The final property is ``cohesiveness'' of the overall swarm: all robots
72 should maintain a unified state, such as desired distance or
73 orientation; see~\cite{Olfati-Saber2006} for a formal definition.
74 As described in~\cite{McLurkin}, detecting and maintaining a swarm boundary
is of particular
75 importance for maintaining swarm cohesiveness and connectedness.
>>> [aspell] Check spelling of word 'connectedness'. Suggestions: conceitedness,
concreteness, conceitedness's, concreteness's. Occurrences in text: 2
76 This is based on and related to work in the field of
77 wireless sensor networks (WSNs), which has considered many geometric
settings in which a
78 large swarm of stationary nodes is faced with the task of achieving a
large-scale overall goal,
79 while the individual components can only operate locally,
80 based on limited individual capabilities and information
(\cite{Fekete2006}, \cite{Kroller2006}).
>>> [chktex] Warning: Non-breaking space (`~') should have been used.
...
84 algorithms for static sensor networks, including distributed boundary
detection.
85
86 Beyond the involved properties and paradigm, the overall goal for the swarm
can also be described
87 as a distributed optimization problem: Maintain a generalized Steiner tree
with limited edge lengths
88 that connects a moving set of terminals.
89 To the best of our knowledge, only Hamann and Wörn \cite{raey}
>>> [chktex] Warning: Non-breaking space (`~') should have been used.
...
91 For static terminals, they start with an exploratory network; as soon as
92 all terminals are connected, only best paths are kept and locally
optimized.
93
94 Even in a centralized and static setting with full information, we have to
deal with a generalization
95 of the well-known NP-hard problem of finding a good Steiner
tree~\cite{garey1977complexity}.
96 More specifically, we are faced with the {\em relay placement problem}: the
input is a set of
>>> [chktex] Warning: No italic correction (`\/') found.
97 sensors and a number $r \ge 1$, the communication range of a relay.
98 The objective is to place a minimum number of relays so that between every
pair
99 of sensors is connected by a path \emph{through sensors and/or relays}.
100 The best known theoretical performance bound for this NP-hard problem was
given by Efrat et al.~\cite{efg-iaarp-08},
101 who presented a $3.11$-approximation algorithm; they also showed a
worst-case lower bound of 3
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
...
107 %while the rest of the exploratory network is removed.
108 %Moreover, Saltenis \cite{journals/informaticaLT/Saltenis99} simulates
109 %idealized soap films in a serialized algorithm as a Steiner tree
heuristic.
110 %In his experiments it mostly produced close results within a linear time
111 %with respect to the number of terminals.
112 More specific references are given in Section~\ref{sec:alg:base}, where
they are used as
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
115
116 \subsection{Our contribution}
117 We propose a set of local, self-stabilizing algorithms that maintain a
dynamic and robust network between leader robots.
118 The algorithms ensure that the swarm adopts the directions of multiple
leaders, while preserving a uniform
119 thickness along the edges of the Steiner tree.
120 We demonstrate the usefulness of this approach by simulations with a swarm
of 400 robots, five
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
──────────────────────── /02-ModelAndPreliminaries.tex ─────────────────────────
0 \section{Preliminaries}
1 %\paragraph{Problem Description.}
2 \label{sec:problem_definition}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
3 We consider a finite set of robots $\mathcal{R}$. A subset
4 $\mathcal{L}\subsetneq \mathcal{R}, |\mathcal{L}|\ll |\mathcal{R}|$ of them
5 is forced to pursue externally controlled trajectories. For simplicity,
6 we call these {\em leader robots}; note that they have no control over their
trajectories,
>>> [chktex] Warning: No italic correction (`\/') found.
...
10 the swarm connected, even in the presence of random robot failures and
arbitrary leader movements.
11 %The communication between the robots is restricted by line of sight and
constrained to a limited range of only about 10 times the robot diameter.
12 Thus, the overall shape of the swarm should form a ``thick'' Steiner
13 tree among the leaders with the
14 robots $\mathcal{R}\setminus \mathcal{L}$ evenly distributed along the
edges, as shown
15 in Figure~\ref{fig:experimentpicture}.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
27 %\paragraph{Robot Model.}
28 Robots have the shape of circles; two of them are connected
29 when within a maximum distance and with an unobstructed line of sight.
30 Robots know the relative positions and orientations of their neighbors
31 and can communicate asynchronously.
32 Each robot has a unique ID; leader IDs are easily made known to all others.
>>> [chktex] Warning: Intersentence spacing (`\@') should perhaps be used.
────────────────────────────── /03-Algorithm.tex ───────────────────────────────
0 \section{Algorithm}
1 \label{sec:alg}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
2 The proposed approach consists of a set of local self-stabilizing mechanisms
that either detect a condition or induce a force.
3 The weighted sum of the induced forces determines the robot motion; input
for the local mechanisms
4 of the local state and environment of the robot, output is a value for
current
5 robot motion. In principle, these mechanisms are continuous.
6 (Our simulator described later updates at 60 Hz.)
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
...
11 %The algorithm is inspired by the Steiner tree approximations of soap films
(\cite{Hwang1992}): %Remark: Hwang does only mention this model, but the
referred paper is not available and I do not like to cite blind.
12 %If a construction of two parallel plates with posts between them is put
into soapy water and pulled out again, a thin soap film between the posts
remains that approximates the Euclidean Steiner tree due to the boundary
tension.
13 %The boundary tension minimizes the boundary length, which for constant
volume minimizes the edge lengths.
14
15 %Overview of whole algorithm
16 We first discuss the base behavior of the robots in
Section~\ref{sec:alg:base}; because it has trouble with generating a
non-convex swarm shape, it
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
18 This is subsequently improved by leader forces, stability improvement and
thickness contraction.
19 %The active manipulation of this water droplet by leader robots is
discussed in Section~\ref{sec:alg:leader}.
20 %The produced Steiner tree like shape is made more stable by compression in
Section~\ref{sec:alg:stability}.
21
22 \subsection{Base Behavior}
23 \label{sec:alg:base}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
37 and Demaine~\cite{McLurkin}, which determines if a robot lies
38 on the boundary and also identifies small holes by using the average angle.
39 In principle, the method allows the robots to distinguish exterior and
40 interior boundaries and determine their size, but the limited precision and
the
41 convergence time limit this usage, so we only use it to detect and ignore
small holes.
42 Doing the latter is crucial for thickness and density computation, see
Section~\ref{sec:alg:stability}.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
48 \end{itemize}
49 %\todo[inline]{More Details}
50
51 %Description of the result of the base swarm
52 The base swarm is similar to a water droplet and converges towards a circle
after some time.
53 The robots are well connected to the swarm and there are no attachments, as
can be seen in Figure~\ref{fig:baseswarm}.
>>> [languagetool] This word is normally spelled with a hyphen.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
61 \begin{subfigure}[b]{0.2\textwidth}
62 \includegraphics[width=\textwidth]{./baseswarm}
63 \caption{After}
64 \end{subfigure}
65 \caption{The base swarm forms the swarm similar to a water drop}
66 \label{fig:baseswarm}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
75 %\vspace{-8mm}
76 %\end{wrapfigure}
77 %
78 However, for diverging leaders the base behavior (movement consensus by
flocking)
79 without any other forces rapidly loses connectivity when the target density
no longer suffices to cover the convex hull of leader robots.
80 Figure~\ref{fig:baseleader} depicts a situation in which the swarm is about
to lose convexity.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
>>> [Proselint] warning: More than two spaces after the period; use 1 or 2.
Suggestion: None
81 For stronger control and more variable shapes, leader forces are
introduced.
82 \begin{figure}[tbh]
83 \centering
84 \includegraphics[width=0.8\columnwidth]{./convex2}
85 \caption{The base behavior without leader forces has trouble with
staying connected after losing convexity.}
86 \label{fig:baseleader}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
87 \end{figure}
88
89 \subsection{Leader Forces}
90 \label{sec:alg:leader}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
95 Therefore, each robot needs to find an appropriate balance between the
influence of different leaders.
96 %Merging of leader forces
97 For $\ell\in\mathcal{L}$, let $c_\ell: \mathcal{R}\rightarrow\mathbb{R}^2$
be the force
98 on a specific robot and let $d_\ell:\mathcal{R}\rightarrow \mathbb{N}$ be
its distance to $\ell$.
99 The leader forces on robot $r$ are combined as follows:
100 \[ \sum_{\ell\in \leaderset}c_\ell(r)\frac{d_\ell(r)^{-1}}{\sum_{\ell'\in
\leaderset}d_{\ell'}(r)^{-1}}.\]
>>> [chktex] Warning: You should enclose the previous parenthesis with `{}'.
>>> [chktex] Warning: You should enclose the previous parenthesis with `{}'.
101 See Figure~\ref{fig:leadersmoothing} for an illustration.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
109
110 \begin{figure}[tbh]
111 \centering
112 \includegraphics[width=0.45\textwidth]{./linearLeader}
113 \caption{A one-dimensional scenario with two leaders (red) moving in
opposite directions.}
114 \label{fig:leadersmoothing}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
135 On the other hand, moving towards the leader causes a deformation of the
swarm
136 and can be used to control its shape when multiple leaders are used, but
137 regions close to the leaders suffer from ``compression'', which can be
harmful. A
138 combination of both methods with a smooth transition between velocity
matching
139 close to the leaders and leader pursuit when further away (see
140 Figure~\ref{fig:leaderforce}) has a positive influence in the context of
multiple leaders,
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
142
143 \begin{figure}[tbh]
144 \centering
145 \includegraphics[width=0.4\textwidth]{./sigmoidal}
146 \caption{With increasing distance to the leader, the effect shifts from
velocity matching to leader pursuit.}
147 \label{fig:leaderforce}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
174 %Assuming that this neighbor points into the direction of the leader, we
use the direction to the neighbor to smooth the leader's direction.
175
176
177
178 %Help Signal
179 Additionally we provide leaders with too few neighbors with an attraction
force, so they do not lose connection to the swarm.
>>> [languagetool] A comma may be missing after the conjunctive/linking adverb
'Additionally'.
180 This attraction spreads over some distance, but decreases exponentially.
181
182 %\todo[inline]{Maybe add some missing details}
183
184 \subsection{Stability Improvement}
185 \label{sec:alg:stability}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
191 in effect, this works similar to compression stockings.
192 In the following, we give a heuristic for thickness computation and
compression. %in Section~\ref{sec:alg:stability:thickness}.
193 In order to let the flocking algorithm handle this compression without
destroying the regular distribution,
194 %\todo{frag...?? Wrong word, isn't it??}
195 we sketch a density distribution heuristic later in this Section.
%~\ref{sec:alg:stability:density}.
196 A comparison of a swarm with and without the stability improvement can be
seen in Figure~\ref{fig:comparison};
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
197 Figure~\ref{fig:comparison2} shows a comparison for the same scenario with
failure rate $0.008$ per second and robot.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
...
219 %\includegraphics[width=0.45\textwidth]{./overview.pdf}
220 %\resizebox{0.8\textwidth}{!}{\input{./overview.eps_tex}}
221 \caption{A comparison of strategies for the same example, for a swarm
with $n=400$ and failure rate $0$. As indicated, columns correspond to
strategies {\sc Base}, {\sc Leader}, and {\sc All}.
222 Rows show the swarms at times $T=200$, $T=2000$, $T=3000$, $T=5000$,
$T=7600$, $T=12,000$, with 60 steps per simulated second. When a swarm is
no longer shown, it has become disconnected
223 right after the previous time step.}
224 \label{fig:comparison}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
233 \hspace*{-3cm}$T=4200$\hspace*{-3cm} & $T=4400$ \hspace*{-3cm}&
$T=5400\hspace*{-3cm}$ & $T=5600$ \hspace*{-3cm}\\
234 \vspace*{-1.5cm}
235 \hspace*{-3cm}\swarme{4200}{Leader} \hspace*{-3cm}&
\swarme{final}{Leader} \hspace*{-3cm}& \hspace*{-3cm}& \hspace*{-3cm}\\
236 \hspace*{-3cm}\swarme{4200}{All} \hspace*{-3cm}& \swarme{4400}{All}
\hspace*{-3cm}& \swarme{5400}{All} \hspace*{-3cm}& \swarme{final}{All}
\hspace*{-3cm}\\
237 \end{tabular}
238 \caption{A comparison of strategies for the example from
Figure~\ref{fig:comparison}, for a swarm with $n=400$, with 60 steps per
simulated second and failure rate $0.008$ per second.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
239 The upper line shows the swarm with strategy {\sc Leader}, the lower shows
strategy {\sc All}. As shown, the swarm loses connectivity at $T=4400$
({\sc Leader}),
240 or $T=5600$ ({\sc All}).}
241 \label{fig:comparison2}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
242 \end{figure*}
243
244 \paragraph{Thickness Contraction}
245 \label{sec:alg:stability:thickness}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
246
247 %Thickness
248 We define the local thickness at a robot as the radius of the largest hop
circle containing it.
249 A hop circle of radius~$h$ with robot~$c$ as circle center is the set of
all robots with a hop count
250 $\leq h$ to $c$; only robots with distance equal to $h$ may be on the
boundary.
251 An example is highlighted in blue in Figure~\ref{fig:thickness}.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
262 \begin{figure}
263 \centering
264 \includegraphics[width=0.45\textwidth]{./thickness}
265 \caption{Thickness determination ($b(r)/t(r)/h(r)$)
266 for a limb part. The red edges fulfill the Gabriel graph condition. A
largest \emph{hop circle} is marked in blue.}
267 \label{fig:thickness}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
274 For this heuristic evaluation of the thickness~$t(r)$ of a robot~$r$, we
need the hop distance~$b(r)$ from the boundary
275 and the circle center distance~$h(r)$.
276 Computing the hop distance to the boundary for each robot can easily be
achieved
277 by setting $b(r)$ to 0 for all robots on the boundary, while all others
take the minimum of their neighbors plus one, as follows
278 \[b(r)=\begin{cases} 0 & \text{$r$ on boundary}\\\min\{b(n)+1\mid n \in
N'_r\} & \text{else}\end{cases}\]
279 Small holes, that occur frequently but also vanish quickly, are excluded
from the boundary, otherwise the value can become too instable.
>>> [aspell] Check spelling of word 'instable'. Suggestions: unstable,
unstably, in stable, in-stable, ins table. Occurrences in text: 1
280 The thickness $t(r)$ is determined as the maximum $b(r)$ within some range
$h(r)$, as follows.
281 \[t(r):=\max \{ \{b(r)\} \cup \{t(n)\mid n\in N'_r \wedge t(n)+\lambda
\geq h(n)\}\},\]
282 where $\lambda\in \mathbb{N}$ is a small constant (e.g. $\lambda=2$) that
tackles the problem of irregular boundaries.
283 If $r$ is a circle center ($t(r)=b(r)$), then the circle center
distance~$h(r)$ is $0$.
284 Otherwise, \[h(r):=\min\{ h(n)+1 \mid n\in N'_r\wedge t(n)=t(r) \}\]
285 An example is shown in Figure~\ref{fig:thickness}.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
296 %Now that we have determined the thickness $t(r)$ we can induce a
thickness dependent compression force on boundary robots.
297 %Each boundary robot presses against the neighbor from which it obtained
its $h(r)$ value with a force linear to the thickness value.
298 %Boundaries of small holes are excluded again and boundaries of large
holes are only kept as we can not distinguish them reliable enough from
the exterior boundary.
299
300 \paragraph{Density}
301 \label{sec:alg:stability:density}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
302 %Intro
303 The local density of a robot refers to the number of neighbors in relation
to its observable area as shown in Figure~\ref{fig:observablearea}.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
305 By introducing an attraction to low and repulsion from high local density
neighbors, the overall swarm density is maintained at a specific
homogeneous level.
306 \begin{figure}[tbh]
307 \centering
308 \includegraphics[width=0.7\columnwidth]{./observablearea}
309 \caption{The observable area of a robot. The impact of hidden robots
intersecting this area is ignored.}
310 \label{fig:observablearea}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
313 %\begin{wrapfigure}{r}{0.2\textwidth}
314 % \vspace{-6mm}
315 % \includegraphics[width=0.20\textwidth]{./observablearea}
316 % \vspace{-9mm}
317 %\end{wrapfigure}
318 It is determined by dividing the number of neighbors by the roughly
calculated observable area, cf.~Figure~\ref{fig:observablearea}.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
328 For overall balance, we assume its space to be the average space between
two clockwise sequential neighbors that do not form an exterior area.
329 A robot can lie on multiple boundaries or multiple times on the same;
however, this is a sign of a sparse distribution, so we only disregard the
largest one.
330 All further exterior areas are fully included and thus lower the density.
331
332 %Averaging - NEW
333 The calculated observable area is sometimes not quite accurate, as the
local knowledge is very limited.
>>> [Proselint] warning: Substitute 'damn' every time you're inclined to write
'very'; your editor will delete it and the writing will be just as it should be.
Suggestion: None
334 Small heterogeneities can let the values vary strongly.
>>> [aspell] Check spelling of word 'heterogeneities'. Suggestions:
heterogeneity's, heterogeneity, heterogeneous, hydrogenates. Occurrences in
text: 1
─────────────────────────────── /04-Analysis.tex ───────────────────────────────
0 \section{An Analytic Result}
1 \label{sec:theo}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
2
3 Before describing the performance of our approach simulation results, we
discuss
4 a related result from theoretical computer science, showing the analytic
difficulty
5 of our underlying scenario, even for a centralized, static offline scenario
without node failures.
6 In this setting, Efrat et al.~\cite{efg-iaarp-08} considered the {\em relay
placement problem},
7 in which a given, static set of transmitters (called {\em terminals}) with
limited communication
>>> [chktex] Warning: No italic correction (`\/') found.
8 range must be connected by a set of more powerful {\em relays}; the
objective is
>>> [chktex] Warning: No italic correction (`\/') found.
9 to minimize the number of these relays for achieving connectivity. Clearly,
this corresponds
10 directly to the achievable scaling factor for which a connected arrangment
is possible:
>>> [aspell] Check spelling of word 'arrangment'. Suggestions: arrangement,
arraignment, arrangements, arrangement's, rearrangement. Occurrences in text:
1
...
16 \includegraphics[width=0.72\textwidth]{./screamshot}
17 %\input{./screamshot.png}%\\.performances.tex}
18 \caption{Relative performance of the different strategy combinations,
19 measured by achievable Steiner tree size before disconnection occurs,
compared
20 to a hypothetical static offline optimum for the remaining live robots.
Shown are median
21 (bold) along with first and third quartiles. The failure rate is the
>>> [aspell] Check spelling of word 'quartiles'. Suggestions: quarterlies,
quarrels, quadrilles, quarters, quartos. Occurrences in text: 2
22 probability of {\em each} robot to die within the next simulated second,
consisting of 60 time steps.
>>> [chktex] Warning: No italic correction (`\/') found.
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
23 Clearly, the strategies are robust and adaptive; the full set
24 of strategies does particularly well in adjusting to leader motion and
robot failures.}
25 \label{fig:performance}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
30 To this date, the best known approximation factor for relay placement is
the following.
31
32 %\begin{theorem}
33 \bigskip
34 {\bf Theorem~IV.1} (Efrat et al.~\cite{efg-iaarp-08})
35 There is a 3.11-approxi\-ma\-tion algorithm for minimum relay placement.
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
36 %\end{theorem}
37
38 \bigskip
39 Note that this is a result for a guaranteed worst-case performance
40 of an algorithm, so we can hope to do better in specific settings.
41 However, we are also faced with a large number of additional difficulties
that
>>> [languagetool] Specify a number, remove phrase, or simply use "many" or
"numerous"
───────────────────────────── /05-Experiments.tex ──────────────────────────────
0 \section{Simulation Results}
1 \label{sec:experiments}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
2
3 %>> New Intro"
4 We validated our approach by conducting experiments with a set of
5 five leaders stretching out a swarm of 400 robots until it disconnects.
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
6 The performance is measured against the length of the minimal
7 Steiner tree on disconnection (calculated by the Geosteiner
>>> [aspell] Check spelling of word 'Geosteiner'. Suggestions: Steiner,
Costner, Ghosting, Easterner, Westerner. Occurrences in text: 1
8 software \cite{warme2001geosteiner}), divided
>>> [chktex] Warning: Non-breaking space (`~') should have been used.
9 by the theoretically maximal possible length estimated by
10 $|\mathcal{R}'|*\operatorname{range}$, where $\mathcal{R}'$
11 are the robots that did not fail yet.
12 This would correspond to an optimal but extremely fragile
13 Steiner tree in which {\em any} node failure disconnects the swarm.
>>> [chktex] Warning: No italic correction (`\/') found.
14 Thus, the best possible value of 1 is completely elusive,
15 in addition to being the result of an NP-hard offline optimization
16 problem.
17
18 For comparison we tested three configurations:
>>> [languagetool] A comma is probably missing here.
19 \Base---only the base behavior as discussed in Section~\ref{sec:alg:base};
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
20 \Lead---the basic behavior enriched by leader forces as discussed in
21 Section~\ref{sec:alg:leader};
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
22 \All---the final configuration that also incorporates Density and
23 Thickness Contraction as presented in Section~\ref{sec:alg:stability}.
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
52 %Different failrates are assumed for the robots; therefore the number of
robots which determine the upper bound can vary.
53
54 %For each addition of a new algorithm to the base behavior and four
different failrates, 100 trails are run to determine first second and third
quartile of the observed performance.
55
56 %Simulator
57 Our benchmark tests were carried out with 60 iterations per simulated
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
...
64 giving the swarm robots the opportunity to react.
65
66 %\todo[inline]{The parameters of the simulation seem reasonable but a bit
arbitrary, especially speed of leaders vs. other robots (is that necessary?
what happens without?). Are the parameters representative of McLurkin's
thesis, for example? Did you run experiments with other values, e.g. with
faster (or slower) robots, thereby increasing McLurkin's Robot Speed Ratio?
I imagine you can't present a lot of this in a EuroCG abstract, but there
are a lot of questions here which I hope you address in the talk and a
longer paper.}
67
68 %Results
69 For each configuration we conducted 100 random trials on a range of
different failure rates; note that
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
70 a failure rate of $0.006$ per second corresponds to an expected lifetime of
about 167 seconds, meaning that out of 400 robots,
71 on average about every 0.4 seconds one of them breaks down for good.
72 Figure~\ref{fig:performance}
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
73 depicts the resulting performance for all three strategies; in each case,
we show the median performance,
74 with corridors around the bold curves indicating first and third quartiles.
The top part of Figure~\ref{fig:performance}
>>> [aspell] Check spelling of word 'quartiles'. Suggestions: quarterlies,
quarrels, quadrilles, quarters, quartos. Occurrences in text: 2
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
75 gives the performance relative to a hypothetical offline optimum {\em
without} robot failures, which is extremely fragile:
>>> [chktex] Warning: No italic correction (`\/') found.
76 as this solution is only a tree, {\em any} robot failure or uneven
distribution will immediately disconnect it.
>>> [chktex] Warning: No italic correction (`\/') found.
77 The ratio of 0.3215 (corresponding to the performance of a
3.11-approximation algorithm for relay placement)
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
78 is also indicated for better reference. The bottom part of
Figure~\ref{fig:performance} gives the relative performance,
>>> [CleverrefCheck] Prefer using cleveref's \cref or \Cref instead of native
\ref.
...
81 sudden disconnection due to fatal robot failure events, indicating
excellent
82 ability to adapt. %overall absolute deterioration is almost exclusively
83 %due to a diminishing number of live robots, which cannot be prevented by
any strategy.
84
85 Comparing the individual strategy components, the results show that leader
forces already produce decent swarm behavior,
86 with survivability four times higher than for the base forces.
>>> [aspell] Check spelling of word 'survivability'. Suggestions:
serviceability, survivable, suitability, survivalist, sociability.
Occurrences in text: 1
87 Without robot losses, it reaches about 30\% of the length of the
hypothetical optimum, which is quite close to the theoretical
>>> [SIUNITX] Use siunitx to get nice and uniform numbers (\num{} at least for
>=10 000) and units (\SI{}{} for all sizes).
────────────────────────────── /06-Conclusion.tex ──────────────────────────────
0 \section{Conclusion}
1 \label{sec:conclusion}
>>> [chktex] Warning: Delete this space to maintain correct pagereferences.
...
8 One of them is to extend our methods to heterogeneous
9 swarms with different kinds of robots. In that setting, an even more
structured, hierarchical
10 approach may be able to combine the strengths of centralized methods
11 (which are better suited to keep track of unbalanced situations) with the
benefits
12 of decentralized mechanisms (which are more robust against failure of key
components).
13 Clearly, this looks promising in scenarios in inhomogeneous environments,
in which
>>> [aspell] Check spelling of word 'inhomogeneous'. Suggestions: in
homogeneous, in-homogeneous, homogeneous, inharmonious, indigenous.
Occurrences in text: 1