<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}

%===================================================================
% Include common packages, environments, counters etc
\input{common_latex/common_latex_packages}
\input{common_latex/common_latex_lab_format}
\input{common_latex/common_latex_definitions}
%===================================================================
\setcounter{tocdepth}{2}
%===================================================================

\begin{document}
\wikidoc{file=Lab.ClassRescue3}
\wikidoc{auth=mikerb@mit.edu}
\helplevelsubsec


%===================================================================
% Build the Cover Page in an environment style easy for wiki parsing
\begin{labcover}
\labtitle{Lab 15 - Autonomous Rescue Challenge - Part 3 }
\vspace{0.1in}
\labtitle{Handling a Changing Playing Field }
\vspace{0.1in}
\labcourse{2.680 Unmanned Marine Vehicle Autonomy, Sensing and Communications}
\vspace{0.1in}
\labpng{0.55}{figures/rescue3.png}
\vspace{0.2in}
\labdate{April 24th 2025}
\vspace{0.1in}
\labauth{Michael Benjamin, mikerb@mit.edu}
\labauth{Department of Mechanical Engineering}
\labauth{MIT, Cambridge MA 02139}
\vspace{0.12in}
\labtoc{footnotesize}
\labtocdepth{2}
\end{labcover}

%====================================================================
% Add a blank page so first body page is on the right when doubleside
%\blankpage
%====================================================================
\newpage \section{Overview and Objectives}

In the third part of the Autonomous Rescue Challenge lab we introduce
the component of adversarial competition. Hereafter in this lab there
will be two rescue robots, traversing the field of swimmers, with the
objective of reaching more swimmers than the other rescue robot.
Prior to this lab, you should have a working version of the
\app{pGenRescue} app that is capable of receiving a series of swimmer
alert messages, and is able to proceed along a path to visit all of
them. A key objective of this lab is prepare for adversarial missions, by
(a) processing information about which swimmers your adversary may have
rescued, (b) consider path generation strategies that prioritize visiting
clusters of swimmers even if they may be farther than the closest swimmer,
and (c) incorporate information about what your adversary's likely
imminent actions in your path planning considerations.

\vspace{0.1in}
\noindent
We will again work in teams of two, demonstrating one version of
\app{pGenRescue} put forth by the team.

\vspace{0.1in}
\noindent
A summary of topics:

\begin{labinfo}
\begin{packed_itemize}[2]
\item Modify your path planning app to handle added and dropped swimmers.
\item Begin adversarial simulation with a second rescue vehicle.
\item Explore strategies beyond greedy path planning by reacting to your
  adversary.
\item Prepare your PABLO for in-water experiments in the next lab.
\end{packed_itemize}
\end{labinfo}

%======================================================================
\section{Preliminaries}
%======================================================================
\label{sec_prelims}
\input{common_rescue/doc_conventions}
\input{common_rescue/update_code}
\input{common_rescue/pav_coords}
\input{common_rescue/shell_path}
\input{common_rescue/bhv_path}

%======================================================================
\newpage
\section{Running the Baseline Mission}
%======================================================================
\label{sec_baseline}

We will continue to use the same baseline mission for this next phase
of the lab.  You should also make the recommended aliases described
earlier to make it easier to navigate to this mission folder.

%======================================================================
\subsection{Running the Baseline Mission}

This mission can be run with either one or two vehicles. To start
with, try running with one vehicle:

\vspace{0.1in}
\begin{consoleverb}
  $ cd moos-ivp-2680/missions/rescue_baseline
  $ ./launch.sh --rescue --swim_file=mit_02.txt 10
\end{consoleverb}
\vspace{0.1in}

\noindent
It should look something the video in Figure
\ref{fig_swimmers_02}. It may differ because you
will be running {\em your} version of \app{pGenRescue} instead of
mine.

\vspace{0.1in}
\begin{figure}[H]
  \centering 
  \includegraphics[width=0.94\textwidth]{figures/swimmers_02.png}
  \caption{The vehicle proceeds to each point, in a greedy path tour,
    and then returns home.}
  \label{fig_swimmers_02}
  \gif{figures/swimmers_02.gif}
\end{figure}
\vspace{0.1in}

\noindent
To start with, un-rescued swimmers will be green triangles. As they
are rescued, the will turn to the color of the vehicle that has made
the rescue.


%======================================================================
\subsection{Adding and Removing Swimmers Using the GUI}
\label{sec_add_rm}

As the mission progresses, new swimmer alerts can come at any time. In
the previous lab you were asked to handle a new swimmer alert
mid-mission. And this was tested within \app{pMarineViewer} with a
left-mouse click. The mouse click would drop a new swimmer at the
mouse location and generate a new \mvar{SWIMMER\_ALERT} message shared
to the vehicles.

\vspace{0.1in}
\noindent
In this lab, we focus on the opposite. The vehicle periodically
receives \mvar{FOUND\_SWIMMER} messages as it visits each swimmer
location. This was also handled in the previous lab to ensure each
swimmer was only visited once. In this lab, the vehicle may receive
\mvar{FOUND\_SWIMMER} messages due to swimmer rescues by others. As we
prepare for adversarial missions, the \mvar{FOUND\_SWIMMER} messages
will be coming from the shore for both you and your adversary. You will
want to adjust your path to remove any swimmer already found by your
adversary.

\vspace{0.1in}
\noindent
To test this logic before introducing a second vehicle,
\app{pMarineViewer} in the \var{rescue\_baseline} mission has been
configured to use the {\em right} mouse click (ctrl left-mouse click
on a Mac) to simulate a rescued swimmer. When the right mouse click is
made, the swimmer closest to the mouse location (but within 10
meters), will be rescued. A \mvar{FOUND\_SWIMMER} message is sent to
all vehicles. It will have content that looks like:

\vspace{0.1in}
\begin{fileverb}
  FOUND_SWIMMER = id=17, finder=nature
\end{fileverb}
\vspace{0.1in}

\noindent
Your vehicle (\app{pGenRescue}) should handle this new information and
drop the swimmer from the list of swimmers to visit and generate a new
path to be sent to the behavior. In the example video below, a similar
mission is launched, but in this case, several right mouse clicks
(ctrl left-mouse click on a Mac) are performed during the mission.

\vspace{0.1in}
\noindent
When swimmers are rescued by an actual vehicle, the \var{finder} field
above will be replaced by the name of the vehicle that performed the
rescue.

\vspace{0.1in}
\begin{figure}[H]
  \centering 
  \includegraphics[width=0.94\textwidth]{figures/swimmer_found.png}
  \caption{A vehicle proceeds along a greedy path to rescue a set of
    swimmers provided prior to the vehicle departure. Along the way,
    the user selects swimmers through the GUI for removal. The vehicle
    immediately adjusts its path to drop the user-removed swimmers
    from its new path. Removed swimmers are shown in gray
    markers. Yellow markers indicate swimmers visited by the yellow
    vehicle. Green markers indicate swimmers that have yet to be
    visited or removed. The mission is run 8x faster than simulated
    real time.}
  \label{fig_swimmer_found}
\gif{figures/swimmer_found.gif}
\end{figure}
\vspace{0.1in}

\noindent
Note the edge case situation where the vehicle is proceeding toward its
final swimmer, and the final swimmer is removed prior to the vehicle
arrival. In this case the vehicle should immediately transition into
a return-home behavior.

%======================================================================
\subsection{Assignment 1 (check off) - Handle Dropped Swimmers in Your Vehicle}

Following the example in Figure \ref{fig_swimmer_found}, where
the version of \app{pGenRescue} was provided by staff, demonstrate
that your app is able to similarly handle information mid-mission
about a swimmer that has been rescued by someone other than your
vehicle.

\vspace{0.1in}
\noindent
Your mission should demonstrate:

\begin{packed_itemize}
\item The general case of dropping a swimmer with a right-click of the
  mouse (ctrl-left click on a Mac).
\item Demonstrate that dropping the last swimmer results in a return
  home behavior. 
\end{packed_itemize}

%======================================================================
\subsection{Efficiency Hints for Running the Baseline Mission}
\label{sec_hints}

Approach this lab with the mind-set that you'll be (re)launching this mission
many times. First create an alias to get to the folder:

\vspace{0.1in}
\begin{consoleverb}
alias cdrb='cd ~/moos-ivp-2680/missions/rescue_baseline
\end{consoleverb}
\vspace{0.1in}

\vspace{0.1in}
\noindent
This alias is also available on the PABLO as \var{student2680}, by virtue
of updating the \var{pablo-common} tree. 

\vspace{0.1in}
\noindent
In this mission we are still working on making sure all MOOS processes
are properly killed in all manners of launching. My preference with this
lab is to (a) kill any dangling processes and (b) clear existing log files
prior to each launch. Launching as follows may be useful:

\vspace{0.1in}
\begin{consoleverb}
  $ ktm; ./clean.sh; ./launch.sh --rescue 10
\end{consoleverb}
\vspace{0.1in}

\vspace{0.1in}
\noindent
Consider the alias:

\vspace{0.1in}
\begin{consoleverb}
alias lll='ktm; ./clean.sh; ./launch.sh'
\end{consoleverb}
\vspace{0.1in}


%======================================================================
\section{Running Adversarial Missions}
%======================================================================
\label{sec_adv}

The next step is to begin working with adversarial missions. To start
with, a two vehicle adversarial mission will be launched, where both
vehicles are using your version of \app{pGenRescue}. Essentially both
vehicles are clones in terms of their algorithm, and if run in large
enough test missions, each should win about half the time. Later in
this lab, when we return to the water, each team will launch with
their own version of \app{pGenRescue}, and presumably the team with
the most effective optimizations to \app{pGenRescue} will win. To
start with, in this section, we explore the mechanics of running
two-vehicle adversarial missions and explain how in-mission
information is presented in the GUI display windows.

%======================================================================
\subsection{Running the Default Two-Vehicle Adversarial Simulation}

In the first adversarial mission, you will run a two-vehicle version
of the baseline mission. To do this, we will launch as before using
the \var{--rescue-rescue} flag or the or the \var{-rr} flag for
short. By default, each launch will generate a new random placement of
15 swimmers in the smaller operating region (See Section
\ref{sec_coords}). We will use all the default command line switches
to run a first simulation with two vehicles:

\vspace{0.1in}
\begin{consoleverb}
  $ cd moos-ivp-2680/missions/rescue_baseline
  $ ktm; ./clean.sh; ./launch.sh -rr --rand 10
\end{consoleverb}
\vspace{0.1in}

\vspace{0.1in}
\noindent
The mission should look something like that in Figure
\ref{fig_rescue_rescue_01} below. Again, your results will look
different because (a) you are using your version of \app{pGenRescue},
(b) different random swimmer location, (c) different random starting
location.

\vspace{0.1in}
\begin{figure}[H]
  \centering 
  \includegraphics[width=0.94\textwidth]{figures/rescue_rescue_01.png}
  \caption{Two vehicles are given the same set of swimmers and
    locations. They each depart at the same time, each using a greedy
    path to traverse the set of swimmer locations and tally
    rescues. Swimmers rescued by the yellow vehicle are indicated by
    the light-yellow markers. Swimmers rescued by the red vehicle are
    indicated by light red markers. If some markers are brighter in
    color this indicates a differential between total swimmers rescued
    between the two vehicles. This mission was run at 10x realtime.}
  \label{fig_rescue_rescue_01}
  \gif{figures/rescue_rescue_01.gif}
\end{figure}
\vspace{0.1in}

\noindent
{\bf Note:} When creating a random swim file during the launch, as above
with the \var{--rand} flag, the launch script will create a temporary
fille called \var{mit\_rand.txt}. If you wish to re-run a mission using
exactly this file, you can launch with \var{--swim\_file=mit\_rand.txt}. 

%======================================================================
\subsection{Run-time Information in Two-Vehicle Simulations}

During the two-vehicle simulation, as well as in-water experiments, there
are several places to find status information.

%----------------------------------------------------------------------
\subsubsection{Visual Markers and Colors}

Perhaps the most direct information during a simulation is the swimmer
markers.  Initially they are all set to a default color, lime. This
default color is set in the \app{uFldRescueMgr} configuration block in
the shoreside mission file. As a vehicle rescues a swimmer, the marker
color is changed to the color of the vehicle. The vehicle color is set
to a unique color in simulation, and chosen based on Heron name when
running on the water. (In short, you should never have to take
measures to set vehicles to have unique colors.)

\vspace{0.1in}
\noindent
Markers will have either a light or bright color. As each vehicle
tallies rescued swimmers, the most recent markers are colored
brightly.  The first N markers for each vehicle are colored lightly,
where N is the lower common tally for the two vehicles. In this way,
you can visually see which vehicle is winning. If it is currently a
tie, all markers for both vehicles will be light. If say vehicle {\em
  abe} has one more marker than the adversary, then abe will have one
bright marker and the others will be lightly colored. And the one
bright marker will represent the swimmer most recently rescued. This
is the situation in the example in Figure
\ref{fig_rescue_rescue_01}.

%----------------------------------------------------------------------
\subsubsection{AppCasting Output of \app{uFldRescueMgr}}

The \app{uFldRescueMgr} app running on the shoreside is where all the
simulation specific to this lab takes place. The appcasting output
holds the full status details for each swimmer and each vehicle. The
output looks similar to Figure \ref{fig_ufrm_appcasting}. 

\vspace{0.1in}
\begin{figure}[H]
  \centering 
  \includegraphics[width=0.65\textwidth]{figures/ufrm_appcasting.png}
  \caption{The appcasting output of the \app{uFldRescueMgr} app will
    show the status of each swimmer, and the status of each vehicle.
    It will also confirm the configuration parameter, e.g., the prevailing
    swim file. At the bottom of the window, the most recent events
    are shown with time stamps. Events are typically when a swimmer has
    been found.}
  \label{fig_ufrm_appcasting}
\end{figure}
\vspace{0.1in}

\noindent
For the most part, in terms of marker status and vehicle tallies, you
should be able to discern what you need just from the marker colors
and brightness, but you can see all the details in the two main tables
of the appcasting output.

%----------------------------------------------------------------------
\subsubsection{AppCasting Output of \app{pGenRescue}}

You should also strongly consider building meaningful appcasting
output for your \app{pGenRescue} app. This is up to you, but it nearly
always pays off in a major way to post updates on your app's internal
state and post important events.


%======================================================================
\subsection{Assignment 2 (check off) Run Your App on Both Simulated Vehicles}

%=======================================================================
\newpage \section{Optimizing Your Path Generation}
%=======================================================================

At this point you should have a working \app{pGenRescue} which
properly handles new swimmer alerts and found swimmer messages. So far
the path planning has consisted to a greedy search algorithm. If we
stopped here, then everyone's autonomy system should have a roughly
50-50 shot of out-performing an adversary on the water or in
simulation. This is where things get fun. We consider here two ways to
begin optimizing, (1) forming a smarter path that leads to more
swimmers, in a shorter amount of time, and (2) reasoning about what
your adversary is doing in considering the generated path.

%=======================================================================
\subsection{Getting to More Swimmers More Quickly}

The greedy path tour is fairly simple to calculate and does a decent
job of quickly formulating a reasonably efficient tour. However,
consider the case in Figure \ref{fig_greedy_bad}:

\vspace{0.1in}
\begin{figure}[H]
  \centering 
  \includegraphics[width=0.65\textwidth]{figures/greedy_bad.png}
  \caption{If a greedy tour is applied, the vehicle will first head
    toward the swimmer to the south-west. However, by heading to the
    first marker east of the vehicle, several swimmers can be visited
    in rapid succession.}
  \label{fig_greedy_bad}
\end{figure}
\vspace{0.1in}

\noindent
In this case, if the vehicle proceeded to the closest swimmer, this
will yield only one rescue before reversing direction across the
field. By the time the cluster of three swimmers to the east has been
reached, they may have already been rescued by your adversary.

\vspace{0.1in}
\noindent
Consider a modified greedy algorithm that, instead of looking only at the
single next leg, looks at the next two legs. Instead of evaluating a candidate
next vertex based solely on its distance to the current point, evaluate the
vertex based on both the distance to the current point plus the distance to its
closest other vertex.

\vspace{0.1in}
\noindent
For $N$ swimmers, the run-time performance of the default
"one-vertex-look-ahead" algorithm is $O(N^2)$. This is better than the
full optimal TSP algorithm which is $O(2^N)$. The
"two-vertex-look-ahead" greedy algorithm could be implemented in
$O(N^3)$ which would still be essentially instantaneous on problems
where $N&lt;30$ as in this lab.

%=======================================================================
\subsection{Using Information about Your Adversary}

The expression "best laid plans": A proverbial expression used to
signify the futility of making detailed plans when the ability to
fully or even partially execute them is uncertain. (Wiktionary)

\vspace{0.1in}
\noindent
Consider the situation in Figure \ref{fig_concede_pts}. If the orange
vehicle planned with a greedy algorithm, it would follow the blue
vehicle to the same two swimmers, which of course would be rescued by
the blue vehicle before the orange vehicle arrived.

\vspace{0.1in}
\begin{figure}[H]
  \centering 
  \includegraphics[width=0.65\textwidth]{figures/concede_pts.png}
  \caption{If a greedy tour is applied, the orange vehicle will proceed
    the same swimmer as the green vehicle. Since both vehicles have the
    same max speed, the green vehicle will certainly rescue these two
    swimmers. The orange vehicle would be better off to consider a path
    that concedes the swimmer(s) closest to the green vehicle.}
  \label{fig_concede_pts}
\end{figure}
\vspace{0.1in}

\noindent
A vehicle, regardless of its path planning algorithm, whether it be
simple greedy, two-vertex-look-ahead, full TSP and so on, that does
not take into consideration the imminent actions of an adversary, will
likely be dominated on the field by an adversary that does.

\vspace{0.1in}
\noindent
So, what kinds of adjustments can be made, and how to get the
information to make those adjustments? Two things can be noted: your
vehicle is already performing collision avoidance with your adversary,
and your adversary is (for now) the only other vehicle in the playing
field. Collision avoidance is enabled by obtaining the position of the
contact to be avoided, in this case through the MOOS variable
\mvar{NODE\_REPORT}. In case you're wondering, {\em outgoing} node
reports, sent to your adversary, are posted locally as
\mvar{NODE\_REPORT\_LOCAL}. An incoming node report looks like:

\vspace{0.1in}
\begin{consoleverb}
  NODE_REPORT = NAME=abe,X=10.21,Y=-5.83,SPD=0,HDG=304.45,DEP=0,LAT=42.35840577,
                LON=-71.08746328,TYPE=KAYAK,COLOR=yellow,
                MODE=MODE@ACTIVE:STATION-KEEPING,ALLSTOP=clear,
                INDEX=18374,YAW=2.5403267,TIME=16509326983.74,LENGTH=4
\end{consoleverb}
\vspace{0.1in}

\noindent
The primary components of this message that will be useful will be the
position and heading. In your \app{pGenRescue} app, you can register
for the variable \mvar{NODE\_REPORT} and start by keeping track of the
contact position and heading.

\vspace{0.1in}
\noindent
Hint: In MOOS-IvP/C++ a node report is typically stored in the C++ class
\var{NodeRecord}, which will help in de-serializing the incoming messages.
Here is a code snippet with the basic idea:

\vspace{0.1in}
\begin{fileverb}
#include "NodeRecord.h"
#include "NodeRecordUtils.h"

// Presumably the below string will have arrived in OnNewMail()
string str = "NAME=abe,X=10.21,Y=-5.83,SPD=0,HDG=304.45,DEP=0,....";

NodeRecord my_record = string2NodeRecord(str);
double contact_xpos = my_record.getX();
double contact_ypos = my_record.getY();
double contact_hdg  = my_record.getHeading();
\end{fileverb}
\vspace{0.1in}

\vspace{0.1in}
\noindent
If you use this class in your code, you will also need to link to the library
\var{"contacts"} in your app's \var{CMakeLists.txt} file.

\vspace{0.1in}
\noindent
Armed with this information about your adversary, what can you do with
it?  Here are a few ideas. They all have the aim of identifying one or
more swimmers that we should {\em concede}. By conceding swimmers to
our adversary, then we can formulate a path tour over a smaller set of
swimmers and likely will be more successful since we hopefully will
not be reaching for swimmers that are not obtainable.

\begin{packed_enumerate}
\item Given the adversary position, which un-rescued swimmer is closest
  to the adversary. Concede that swimmer. Maybe concede the two
  closest swimmers, or all swimmers within say 15 meters of the
  adversary.
\item Given the adversary position {\em and heading}, which swimmers
  are close and have a relative bearing to the adversary of close to
  zero?  Concede that swimmer(s).
\item Given the adversary position, and knowledge of all remaining
  swimmers, calculate a greedy path (or any path), from the
  perspective of your adversary. Then concede the first swimmer on
  that path. Or the first N swimmers on that path. Or all swimmers in
  the first N meters on that path.
\end{packed_enumerate}

\noindent
You are not limited to the above strategies. If you have a better one,
go for it. Or perhaps try implementing one or more of these strategies
and see what other ideas come up along the way. My hunch is that some
combination of these two groups of strategies will be more effective
than either one alone.

%=======================================================================
\subsection{Trying Your Optimized Path Planning}

If you successfully create an advanced version of your
\app{pGenRescue} app, you probably want to test it, against an
adversary that is not using the advanced version.  However, the
baseline mission is structured to run two identically configured
vehicles. How do we run two differently configured vehicles?

\vspace{0.1in}
\noindent
The baseline mission has one method for handling this. This presumes
that different vehicle configurations can be set solely through
different configuration parameters for your \app{pGenRescue} app. The
\var{meta\_vehicle.moos} file contains the configuration block of the
\app{pGenRescue}:

\vspace{0.1in}
\begin{fileverb}
ProcessConfig = pGenRescue
{
#ifdef VNAME abe
	// foo = true
#elseifdef VNAME ben
	// foo = false
#else
	// foo = maybe
#endif
}
\end{fileverb}
\vspace{0.1in}

\noindent
Note that, regardless of the vehicle name, the resulting configuration
will simply have one commented line. In our two vehicle simulations,
the vehicle names will always be \var{abe} and \var{ben}. When you
have a heuristic implemented in your \app{pGenRescue}, try to enable a
configuration parameter such as \var{heuristic\_type=alpha}, and use
this configuration line in the \app{pGenRescue} block above such that
only one vehicle is using the heuristic.


%=======================================================================
\newpage \section{Instructions for Handing In Assignments}
%=======================================================================

%=======================================================================
\subsection{Requested File Structure}
\label{sec_hand_in}

The assignment for this lab is to (a) demonstrate a working mission in
simulation using your \app{pGenRescue} app that demonstrates
baseline capability of handling a two-vehicle adversarial mission, dropping
swimmers rescued by the other vehicle and re-planning accordingly, (b)
begin improving on the path planning algorithm to consider adversarial
intent, and greedy search that includes time.
You are encouraged
to use the \var{rescue\_baseline} mission in the provided
\var{moos-ivp-2680} tree, so the only addition in your codebase is the
\app{pGenRescue} app:

\vspace{0.1in}
\begin{consoleverb}
  moos-ivp-extend/
     src/
        pGenRescue
\end{consoleverb}
\vspace{0.1in}


%=======================================================================
\subsection{Due Date}

This lab should be completed by the end of day Tuesday, April 29th, 2025.

\end{document}

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