<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}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{algorithmicx}
%===================================================================

\begin{document}

\begin{labcover}
\labtitle{Decentralized Decision Making}
\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\_decentral}
\labtoc{small}
\end{labcover}

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


%==================================================================
\section{Decentralized Decision-Making}
%==================================================================

The goal of decentralized decision-making is to allow a group of
vehicles to be tasked with a specific goal, i.e., task, with the
expectation that the vehicles will reach a consensus among themselves
without involving further human input. In some cases this can be
accomplished by a shared protocol where it is always clear what each
vehicle should do, presuming there is some minimal awareness of
ownship state relative to its collaborators, such as vehicle position.
However, in other cases, even when ownship and collaborator vehicle
positions are known, a dialog between vehicles is required to reach a
consensus. Auction-based consensus algorithms are not new, but the
method and implementation of this approached, integrated into an
existing behavior-based architecture with dynamic behavior spawning is
the focus of this portion of the work.

%====================================================================
\subsection{Static and Dynamic Behavior Configuration}

Helm behaviors, including the Convoy behavior, are configured in part
through static parameters specified at the time of mission launch, and
dynamic updates to parameters provided at run-time, as depicted in
Figure \ref{fig_behavior_updates}.

\begin{figure}[H]
    \includegraphics[width=0.65\textwidth]{figures/behavior_updates.png}
    \centering
    \caption{{\bf Behavior Inputs}: Most behavior parameters are
      provided upon startup from the mission configuration
      file. Dynamic updates may be provided at run-time from any other
      MOOS application, allowing for higher levels of planning, and
      command and control to influence the autonomy as a whole through
      changes to the behaviors. Behavior {\em templates} are used in
      cases where behaviors come into existence only upon external
      events and incoming messages to the helm. A behavior template
      may spawn several instances during the lifetime of the mission.}
    \label{fig_behavior_updates}
\end{figure}

\vspace{0.1in}
\noindent
Behaviors of the IvP Helm may be configured as {\em templates},
essentially starting the mission waiting for events to occur at
run-time to spawn one or more instances of the templated
behavior. Through this mechanism, the behavior configuration need not
know the details of the tasks involved in the the eventual spawned
behavior.  This information will arrive as run-time updates, spawning
behaviors as needed. Once the behaviors have achieved their
objectives, the spawned behaviors will be deleted and removed from
helm memory.

\vspace{0.1in}
\noindent
The support for dynamic behavior spawning, memory management, and
post-mission analysis of dynamic behavior events, is a core (perhaps
unique) strength of the helm and a key enabler for the family of swarm
behaviors. The circumstances that govern dynamic behavior spawning,
are handle through one (currently three) event managers. 

%====================================================================
\subsection{Autonomy Event Managers}

A key design goal is to minimize or eliminate any mission
configuration as a mission varies in the number vehicles, vehicle ID
names, or initial starting conditions. An operator should be able to
power on any set of vehicles in any location or position and just say
"go", where "go" includes goals for the group to achieve.  The
operator may wish to later change the goal details or parameters, but
the initial stage should amount to no more than a button-push.

\vspace{0.1in}
\noindent
A multi-vehicle collaborative mission utilizes up to three event
managers available to the IvP Helm.  The contact manager ingests
position and pose node reports of other vehicles in the field. The
obstacle manager ingests information about obstacles to be
avoided. The task manager accepts tasking either from external command
messages, or from collaborating vehicles.

\begin{figure}[H]
    \includegraphics[width=0.75\textwidth]{figures/event_managers.png}
    \centering
    \caption{{\bf Event Managers}: Event managers are MOOS apps that
      abstract a layer of complexity between communications and
      sensing systems and the behaviors of the helm. Behaviors
      register with the event managers for alerts.  The registration
      specifies the conditions and format of the desired alerts.
      Alerts typically result in the spawning of new behaviors from
      behavior templates.}
    \label{fig_event_managers}
\end{figure}



%======================================================================
\subsection{The Task Manager}
\label{sec_taskmgr}

The Task Manager coordinates incoming tasks and the spawning of proper
behaviors of the helm. It is a thin application with no logic related to
any particular task type. It is merely a broker to shield some complexity
from the helm, and it also serves as a single entity to monitor overall
task status on the vehicle across perhaps multiple tasks. The main loop
is shown in Algorithm \ref{alg_tm_main_loop}.

\vspace{0.1in}
\begin{twalgorithm}{Task Manager Main Loop}{alg_tm_main_loop}
\input{alg_tm_main_loop}
\end{twalgorithm}

\vspace{0.1in}
\noindent
Typically tasks originate from one of two sources: either a direct
command from an operator to the group of vehicles, or from a
collaborating vehicle. In the case of the convoying mission, the
initial task comes from the operator to choose a leader to lead the
convoy. The lead vehicle then initiates a task to find a follower and
so on until there are no vehicles remaining. The task manager begins a
mission knowing nothing about any tasks.

\vspace{0.1in}
\noindent
When the helm launches, task behaviors will generate a message to the
task manager to register for alerts when or if the task manager
receives certain tasks. The auctioning between vehicles, and the
auctioning algorithm for determining bids, is completely implemented
in the task behaviors.  General task behaviors are described next.

%====================================================================
\subsection{Task Behaviors}

A task behavior is a special behavior in the IvP Helm. It does not
generate an objective function to influence the vehicle
trajectory. Its sole purpose is to participate in a task auction and,
depending on the result, post output that may spawn a new behavior. A
newly spawned behavior is the usual result for a task auction that has
been won. Like any helm behavior though, many of the actions taken
upon win or lose in an auction may be configured in the mission file
and mission developers have wide latitude to improvise.

\vspace{0.1in}
\noindent
The main loop of a generic task behavior is shown in Algorithm
\ref{alg_tm_onrun} below, with much of the same logic depicted in
Figure \ref{fig_task_states}. A task behavior is meant to live briefly
and progress through the following states: \{{\em spawned, noroster,
  roster, bidding, bidwon, bidlost}\}. The {\em spawned} state is the
initial state upon spawning by the task manager. The task behavior's
first job is to retrieve a list of teammates from the contact manager,
a separate MOOS app. The request is shown on line 3 below. The contact
manager maintains information about all contacts, but this request
from a task behavior may filter the query for contacts that are of a
particular type or range. Once this request is made, the behavior
stays in the {\em noroster} state until the roster has been received.

\vspace{0.1in}
\begin{twalgorithm}{Task Behavior Main Loop}{alg_tm_onrun}
  \input{alg_tm_onrun}
\end{twalgorithm}

\vspace{0.1in}
\noindent
Once the task behavior has the roster of collaborators, it generates a
bid for the current auction and sends the bid out to the vehicles on
the roster. At this point it enters the {\em bidding} state and
remains in this state until incoming bids have been received by every
member of the roster. The function call to generate a bid, on
line 10, is where the unique nature of the task
behavior resides. Each task behavior of the IvP Helm shares the common
structure of Algorithm~\ref{alg_tm_onrun}, differing primarily by the
implementation of bid generation and the registration of information
needed for the bid generation.

\vspace{0.1in}
\begin{figure}[H]
    \includegraphics[width=0.73\textwidth]{figures/task_states.png}
    \centering
    \caption{{\bf Task Behavior Progression}: A task behavior proceeds
      through the states shown, beginning from initial spawning by the
      task manager, and generation of bids to collaborators. Depending
      on ownship bid compared to collaborators, the task behavior will
      generate further publications, i.e., flags, that will spawn the
      appropriate behavior to perform the task. The primary difference
      between different task behaviors is in the implementation of bid
      generation.}
    \label{fig_task_states}
\end{figure}

%===================================================== Encircle
\subsection{Example Mission: Encircle and Defend High Value Asset}
\label{sec_encircle}

The first mission chosen to test and demonstrate the decentralized
auction algorithms involved a multi-vehicle defense of a high-valued
asset. The high-value asset was deployed to a stationary or at
relatively slow-moving trajectory compared to the defense vehicles.
In the initial phase shown in Figure \ref{fig_hva_defense}, eight
vehicles are deployed to encircle the high-value asset at a prescribed
radius with the HVA at the center. Each vehicle receives periodic
position and trajectory updates of its collaborators, and is equipped
with a "soft" COLREGS collision avoidance behavior (respecting only
Rule 14, and reverting to CPA avoidance in other cases). A separate
app is running on each vehicle to reason about the range fore and aft
on each vehicle to the nearest collaborator. This informs the requested
speed component of the loiter behavior. In the figure, a blue wedge
between vehicles indicates equal distance between both the nearest fore
and aft collaborator on the radial trajectory encircling the HVA. 

\begin{figure}[H]
    \includegraphics[width=0.8\textwidth]{figures/hva_defense.png}
    \centering
    \caption{{\bf Swarm Defense of High Value Asset}: Phase 1: Group
      surrounds and protects a â€œhigh value assetâ€.  Vehicles are only
      aware of each otherâ€™s position, heading and speed Collision
      avoidance behaviors coordinated with mission behaviors.  Phase
      2: Members of the group intercept identified threats Vehicles
      conduct inter-vehicle auction. Selected vehicle assigned.
      Phase 3: Resume posture.}
    \label{fig_hva_defense}
\end{figure}


\vspace{0.1in}
\noindent
When a threat or set of threats emerge, the group of vehicles is tasked
with choosing a single vehicle to engage each threat. At this point
the task manager on each vehicle will spawn a task behavior to participate
in an auction associated with each threat. Vehicles are selected and
break off from the encircling defensive posture to engage with each threat.
During this period the remaining vehicles shift position to retain
equal spacing around the HVA. As each engaging vehicle completes its
task, it returns to the defensive posture, using the collision avoidance
behavior to rejoin the group. 

\vspace{0.1in}
\noindent
The software modules involved in this mission are \var{lib\_helmtask},
\var{lib\_bhv\_waypoint}, \var{pEncircle}, \var{pTaskManager},
\var{uFldTaskMonitor}, in addition to core IvP Helm apps such as the
contact manager, collision avoidance behavior, and loiter behavior.

%===================================================== Convoying
\subsection{Example Mission: Convoying}
\label{sec_convoy_auction}

The second example mission involves linear convoying. Such a mission
can be described as having two distinct phases. In the first phase,
the group of vessels has been given the command to {\em form} the
convoy, which include reaching a consensus on ordering and maneuvering
into a convoy formation. In the second phase, the goal is to {\em
  maintain} the convoy formation, including holding relative ranges
between vessels.  The latter phase is handled with a distinct behavior
in the Swarm Autonomy Toolbox discussed in Section
\ref{sec_convoy}. The ordering consensus involved in the first phase,
is handled using a cascading auction approach discussed here.


\vspace{0.1in}
\noindent
The sequence of events for a four vehicle convoy is described in
Figure \ref{fig_convoy_sequence}. The initial command originates
external to the convoy, resulting in an auction to choose a lead
vehicle. A task behavior on each vehicle participates in the bidding.
On the winning vehicle, the task behavior will (a) spawn a transiting
behavior for the lead vehicle to commence, and (b) post a task to the
remaining vehicles to choose a follower of the lead vehicle. 

\begin{figure}[ht]
    \includegraphics[width=0.68\textwidth]{figures/convoy_sequence.png}
    \centering
    \caption{{\bf Convoy Mustering}: An operator sends a single
      command to the N stationary vehicles, to traverse a set of
      waypoints. The group first holds an auction to self-identify a
      lead vehicle. The lead vehicle then begins a cascading set of
      tasks to the remaining vehicles to successively hold auctions to
      determine remaining order. On each selection the proper autonomy
      behavior is also activated - a waypoint behavior on the lead
      vehicle and the convoy behavior on the remaining N-1 vehicles.}
    \label{fig_convoy_sequence}
\end{figure}

\vspace{0.1in}
\noindent
On the vehicle winning the number two position, the task behavior
will also initiate two events. It will (a) spawn a convoying behavior
to follow the lead vehicle, and (b) post a task to the remaining
vehicle to choose a follower of the number two vehicle. This continues
until the last vehicle is identified and begins following the other
vehicles.


\begin{figure}[H]
    \includegraphics[width=0.92\textwidth]{figures/convoying_herons.png}
    \centering
    \caption{{\bf Convoy Simulation and Field Testing}: Left: (a) Five
      random starting positions are chosen on each simulation launch,
      (b) Initial command is given and vehicles self-select their
      leader and order, as in Figure \ref{fig_convoy_sequence}, (c)
      The vehicles begin to establish their ideal convoy range, (d)
      The leader has reached the first waypoint and the second vehicle
      is about to achieve the corner waypoint as well. Right: Four
      Heron Unmanned Surface Vehicles (USVs) were used for field
      experiments (top left). Four vehicles were deployed with no
      assigned roles, or control over starting positions or headings
      (top right, bottom).}
    \label{fig_convoying_herons}
\end{figure}

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

\end{document} 



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