relatedWork.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related Work}\label{sec:RelatedWork}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Coverage using one robot is a canonical robotics problem \cite{choset2001coverage}. It has been studied in-depth for many applications including lawn mowing, harvesting, floor cleaning, 3D printing, robotic painting, and others. 
Coverage means that the robot has passed within one robot radius of every location in the workspace. Coverage with a swarm of robots is a key ability for a range of applications because swarms have higher fault tolerance and reduced completion time. Correspondingly, it has been studied from a control-theoretic perspective in  both centralized and decentralized approaches. For examples of each, see  \cite{zheng2005multi} and \cite{wagner1999distributed}.
%where the coverage is performed in such a way that robots are not aware of each other's existence but always cover a cell that is a non-critical point which does not disconnect the graph. 

Traditional multi-robot methods focus on extending single robot coverage techniques to multi-robot systems. Solving coverage for synchronous multi-robots using online coverage techniques such as the boustrophedon technique of subdividing the 2D space into cells as in \cite{latimer2002towards} focuses on moving the robot teams in unison until they identify obstacles in their path. 
Once that happens, the team divides into smaller teams that continue the search in the smaller cells. 
The method is similar to ours in the sense that robots try to move in the same direction as long as possible, but in our problem of interest the particles always move in the same direction and do not subdivide the space.  
The frontier cells exploration in \cite{yamauchi1998frontier} is a greedy policy that selects target locations to explore using local information from each robot, not a shared global map.
 
Fundamental problems of robot navigation in an unknown environment have also received a large amount of attention from the theoretical side.
The classic prototype is the {\em linear-search problem}, which was first proposed by Bellman \cite{B63} and, independently,
by Beck\cite{B64}: An (immobile) object is located on the real line at an unknown distance $D$ and in an unknown direction.
Because the time necessary for locating the object may be arbitrarily high (as the object may be hidden far
from the origin), a useful measure for the performance of a search strategy
is the {\em competitive ratio}: This is the supremum of the ratio
between the time the searcher actually travels and the time she would have
taken if she had known the hiding place. 
 The competitive ratio is
a standard notion in the context of online algorithms; see \cite{FW98}
for a comprehensive overview. 
For the linear-search problem, the optimal competitive ratio is 9, as was first shown by Beck and Newman \cite{BN70} and generalized by Gal~\cite{G72,G74}: The search should alternate
between going to the right and to the left, at each iteration doubling her step size. This can be extended to other scenarios: For the case in which changing direction during the course 
of the search incurs an additional cost of $d$, Demaine et al.~\cite{dfg-olstc-06} showed that an optimal strategy can 
locate an object with total cost $9D+2d$, which is optimal.
Of particular relevance for the content of this paper is 
Fekete et al.~\cite{fkn-sar-04,fkn-osar-06} for online searching by an autonomous robot in an unknown environment,
where both moving and measuring incur individual costs, and Fekete et al.~\cite{fms-mctc-10} for an (offline)
setting that studies the closely related bicriteria version of covering with travel cost.
For another recent work on mapping and coverage by a robot swarm with limited information and capabilities, see~\cite{lfm-stmrs-16}.

However, all these approaches assume a level of intelligence and autonomy in individual robots that exceeds the capabilities of many systems, including current micro- and nano-robots. Current micro- and nano-robots, such as those in~\cite{Chowdhury2015,martel2015magnetotactic,Xiaohui2015magnetiteMicroswimmers} cannot have onboard computation. Thus, we will be referring to them as {\em particles}. For these reasons, this paper focuses on centralized techniques that apply the same control input to each member of a particle swarm. A work that maps a single feature in a continuous workspace \cite{ramachandran2015optimal} is of particular interest. In the work a particle swarm is manipulated by uniform inputs. All particles move in the same direction, but, if a robot encounters the feature, it stops moving and reports the time at which it stopped. An optimal control, gradient descent technique is used to estimate the location and shape of the feature. 
In contrast to \cite{ramachandran2015optimal}, this paper maps arbitrary discrete patterns using particles with no onboard computation that can be steered and are fully observable. %In In that regard the colest  \cite{shahrokhi2016algorithms}, global control is used to shape a swarm and the convenience and mass is controlled to use swarms for high accuracy assembly. The algorithms showcased in this work show how environmental factors such as wall friction can be used to shape swarms. The usage of limited parameters to control a large swarm gives us insight into how planning must be approached for problems where large number of globally controlled robots must be used. By following the covariance of a swarm, we can see how dispersed a swarm is. This will be useful for us to determine how explorative our algorithms are, when searching the workspace.   
%Precision control requires breaking the symmetry caused by the global input.

%Symmetry can be broken using agents that respond differently to the global control, either through agent-agent reactions, see work modeling biological swarms \cite{bertozzi2015ring}, or engineered inhomogeneity  \cite{Donald2013,bretl2007,beckerIJRR2014}.
%This work assumes a uniform control with homogenous agents, as in~\cite{Becker2013b}.