<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[onecolumn,letterpaper,11pt]{article}

%===================================================================
\input{common_latex/common_latex_packages}
\input{common_latex/common_latex_definitions}
\input{common_latex/common_latex_memo_format}
%===================================================================

\begin{document}

\begin{labcover}
\labtitle{Distributed Coverage}
%\vspace{0.17in}
%\labpng{0.65}{figures/swarmbox.png}
\vspace{0.15in}
\labdate{Nov 2023}
\vspace{0.1in}
\labauth{Michael Benjamin, mikerb@mit.edu}
\labauth{Department of Mechanical Engineering}
\labauth{MIT, Cambridge MA 02139}
\labsrc{project-pavlab/memos/memo\_swarm\_dist\_cover}
\labtoc{small}
\end{labcover}

\wikidoc{file=Memo.SwarmDistCover}
\wikidoc{auth=mikerb@mit.edu}


%===================================================== Voronoi
\section{Distributed Coverage}
%===================================================== Voronoi
\label{sec_voronoi}

In a class of missions we put under the general umbrella term {\em
  distributed coverage}, a core mission goal is to deploy $N$ vehicles
to a pre-defined shared given region. A Voronoi partition can be
observed from the set of vehicles within this region. Our overall goal
is to use the Voronoi partition to inform an algorithm, local to each
vehicle, to iteratively adjust its location to a new location that
improves certain properties of the partition. The primary property of
concern is the area of the local Voronoi cell. Generally, if the
variance in areas is small, the distribution of the vehicles over the
region is fairly uniform. An algorithm called Lloyd's algorithm can be
modified into a vehicle behavior that reasons only about the location
of neighbors, thereby forming a belief about its own local cell,
without awareness of the entire Voronoi partition. Llyod's algorithm
proceeds by iteratively moving each vehicle toward the center of its
own Voronoi cell. Variations of Lloyd's algorithm can be customize to
achieve different performance metric, or even perpetuation motion of
the field, to enhancing sensor performance. The basic idea is shown in
Figure \ref{fig_voronoi} below, from our initial development of the
algorithm in an engineering GUI (the \var{voiview} application in the
Swarm Autonomy Toolbox).

\begin{figure}[H]
    \includegraphics[width=0.76\textwidth]{figures/voronoi.png}
    \centering
    \caption{{\bf Lloyd's Algorithm Variation Engineering Model
        Simulation}: Left: An initial distribution of points in a
      convex polygon, akin to an initial vehicle deployment in a
      search region. Right: The distribution of points after several
      iterations of Lloyd's algorithm.}
    \label{fig_voronoi}
\end{figure}

\vspace{0.1in}
\noindent
The algorithm reaches a stable state when all nodes have simultaneously
reached their set point (by default the centroid of each node's
Voronoi cell). A tolerance range can be configured, to allow the nodes
to achieve their stable state sooner. 

\vspace{0.1in}
\noindent
In distributing the vehicles, the goals, or performance metrics, are
to (a) minimize the variance in area of each vehicle's Voronoi cell,
(b) minimize the time for the group to achieve a steady state, (c)
minimize the distance traveled for each vehicle, and others.  There
are three mission variations that have provided motivation due to
needs from related ongoing efforts. These are discussed next.

%=====================================================
\subsection{Distributed Environmental Monitoring}
\label{sec_voronoi_env}

In the first application area the goal is to deploy multiple vessels
to a region, each equipped with environmental sensors. In certain
aquaculture installations, real time environmental monitoring is
highly valued. We are working with a small sailboat company, Marine
Robotics, LLC, in Maryland who engage with oyster farmers in
Chesapeake Bay. We are developing the distributed coverage algorithms
described here along with autonomous sailing methods. MIT has had a
single autonomous sailboat on campus since Fall of 2021, with the goal
of deploying multiple vehicles in the next year.

\begin{figure}[H]
    \includegraphics[width=0.96\textwidth]{figures/saxis_sailing.png}
    \centering
    \caption{{\bf Distributed Environmental Monitoring}: Left: An
      autonomous sailboat by Marine Robotics LLC in Maryland. Right: A
      simulation of 11 vehicles in a region near Saxis Maryland near
      an oyster farm installation.}
    \label{fig_saxis_sailing}
\end{figure}

\vspace{0.1in}
\noindent
In this application the initial objective is to achieve a Voronoi
covering of the region of interest, optimizing the metrics of
minimizing Voronoi cell variance, travel time, and travel distance.
The extra challenge lies in achieving these objectives with a sailing
vessel which is limited by the prevailing wind direction and
magnitude
. The current approach is to implement both components of
the algorithm as distinct IvP behaviors, each optimizing their
respective performance metrics, reconciled by the multi-objective
optimization engine of the IvP helm.

%=====================================================
\subsection{Distributed Sensing for ASW}
\label{sec_voronoi_asw}

In the second application area involving the Voronoi family of
algorithms, the goal also begins with deploying multiple vessels to a
region. Rather than being deployed with environmental sensors, they
are deployed with sensors for detecting other vessels moving through
the region. This is essentially to replicate a distributed
anti-submarine warfare (ASW) domain.

\begin{figure}[H]
    \includegraphics[width=0.96\textwidth]{figures/soj.png}
    \centering
    \caption{{\bf Distributed ASW Mission}: Left: A simulated mission
      involving the Sea of Japan. Fifty vehicles are deployed from
      three distinct launch points. Right: A simulation of the 50
      deployed vehicles, at a point of near uniform coverage. The
      simulation ran on a cluster of 50 networked RasPi computers,
      periodically sharing position information between neighbors.}
    \label{fig_soj}
\end{figure}

\vspace{0.1in}
\noindent
One of our US Navy graduate students, LT Craig Evans, is developing
missions based on this scenario to include simulated sensors, and
randomly placed moving contacts through the field. Automated random
simulations are conducted, varying sensor performance, target speed,
and different patterns of movement for the deployed vehicles. LT Evans
is expecting to complete his work in August 2022.

%=====================================================
\subsection{Multi-Vehicle Mustering}
\label{sec_muster}

In the third application area involving the Voronoi family of
algorithms, the goal does not involve distributed sensing. In this
case the goal is to deploy $N$ vehicles to a {\em muster region}. This
region is also a convex polygon as in the previous two mission types,
but in this case the region is much smaller, and the goal is to
transit the group of vehicles to the region and muster, or wait until
a follow-on mission mode. The idea is to use the Voronoi algorithms in
a Muster behavior to ensure vehicles maintain a separation from each
other rather than relying purely on a collision avoidance
behavior. The collision avoidance behavior is still used, but the
Muster behavior helps avoid situations where collision avoidance
measures are needed to begin with. 

\begin{figure}[H]
    \includegraphics[width=0.9\textwidth]{figures/muster.png}
    \centering
    \caption{{\bf Four Vehicle Muster}: Four-vehicle Muster Four
      vehicles approach a muster region. As each vehicle enters the
      region the Voronoi decomposition is shown. When the first
      vehicle enters, there is only one region. When the second
      vehicle enters, there are two regions, and so on. Upon each new
      vehicle, the local regions for each vehicle may change. The
      change in local region shape affects the set point toward which
      the vehicle is driving toward.}
    \label{fig_muster}
\end{figure}

\vspace{0.1in}
\noindent
Compared to methods that assign a wait point to each vehicle, the
muster behavior is preferred for two reasons (a) the single muster
region is a simpler mission plan to construct that scales with the
number of vehicles, and (b) with the single wait-point method,
occasionally a vehicle will need to maneuver around other vehicles
that arrived at their wait point earlier.

\vspace{0.1in}
\noindent
This behavior is defined in the \var{lib\_bhv\_muster} library. It has
been field tested on four Heron USVs on the Charles River, and has
been integrated into the DARPA Sea Train autonomy system for mustering
the four vehicles in several mission sub-modes for that project.

%\small
%\nocite{bnsl11}
%\bibliographystyle{plain}
%\bibliography{biblio}
%\normalsize

\end{document} 



</pre></body></html>