% -*- TeX-master: "dp2.tex" -*-
% $Id: mission-distribution.tex,v 1.4 2004/05/06 16:51:44 dan Exp $

The mission distribution subsystem constitutes the logic that runs on
the control center. It receives missions and amendments from Earth,
and efficiently allocates them to rovers. In addition to basic
distribution, it accounts for possible rover failure, schedules
experiment repetition to account for sensor failure, and allows for
mission amendments.

The mission distribution subsystem allocates \emph{assignments} to
rovers. An assignment is a sequence of instructions for one rover that
must be executed in order, i.e. ``travel to location 37.33, -121.03;
take a photo; travel to location 37.45, -120.82; take another photo;
return to the control center''. The instruction format is described in
Section~\ref{sec:mission-execution} and
Table~\ref{tab:instruction-format}. Each assignment is transmitted by
the control center to a rover, which then executes the assignment and
returns the results to the control center. The process by which rovers
execute assignments is described in detail in
Section~\ref{sec:mission-execution}

\subsection{State Information}
\label{sec:distribution-state}

In order to manage the allocation of missions to rovers, the central
controller must keep track of the current state of the system at all
times. To accomplish this, it maintains two state tables: a table of
rover states, and a table of mission states.

The table of mission states primarily associates a mission ID with the
list of \emph{tasks} required to complete the mission. We define a
task to be a tuple consisting of an experiment, and the location at
which it needs to be performed; in addition, we associate with each
task record a list of the assignments that involve it. We also
associate additional data with each mission, as in
Table~\ref{tab:mission-state}. To deal with amendments, as in
Section~\ref{sec:new-missions}, we give each mission record a revision
number. We also track dependencies --- missions that must be completed
before this one -- for each mission; since we split scattered and
scattered-cluster missions into their individual components (see
Section~\ref{sec:new-missions}), this ensures that the components are
executed in order. Finally, we introduce the notion of a
\emph{priority value} for the mission, which captures the relative
importance of each mission. This is used in the scheduling algorithm,
and is described extensively in Section~\ref{sec:priority-values}.

\begin{table}[htbp]
  \centering
  \begin{tabular}{|c|c|}
    \hline
    \textbf{Field} & \textbf{Type} \\
    \hline
    Mission ID & integer \\
    Revision number & integer \\
    Tasks & list of task records (experiment/position/assignments) \\
    Dependencies & list of mission IDs \\
    Priority value & integer \\
    \hline
  \end{tabular}
  \caption{Mission state table fields}
  \label{tab:mission-state}
\end{table}

The table of rover states associates each rover's ID number with its
current status. There are four possible states each rover can be in:

\begin{itemize}
\item \emph{available}, meaning it is present at the control
  center and waiting to be given an assignment
\item \emph{busy}, meaning it is currently executing an assignment
\item \emph{lame}, meaning it is currently executing an assignment
  that has become moot due to a mission amendment
\item \emph{dead}, meaning that the control center has not heard from
  the rover and has presumed it to have failed
\end{itemize}

For rovers that are not in the available state, we associate with them
their current assignment (an assignment record), and the time at which
it was assigned. We also compute the expected return time, which is
the sum of the start time, the required travel time for the
assignment, and the sum of the predicted times required to complete
each experiment.

\begin{table}[htbp]
  \centering
  \begin{tabular}{|c|c|}
    \hline
    \textbf{Field} & \textbf{Type} \\
    \hline
    Rover ID & integer \\
    Rover state & 2-bit state type (see above) \\
    Current assignment & assignment record \\
    Start time & time \\
    Expected return time & time \\
    \hline
  \end{tabular}
  \caption{Rover state table fields}
  \label{tab:rover-state}
\end{table}


\subsection{Mission Scheduling and Assignment Algorithm}
\label{sec:scheduling-and-assignment}

The control center assigns missions to available rovers. It does so by
periodically checking which rovers are in the available state: at
regular intervals, it sends out a ``who's-here?'' message. It gathers
responses from the nearby rovers, and once a short timeout period has
elapsed, begins assigning missions to any nearby rovers that are in
the available state, according to the rover state table.

Mission scheduling is performed by a greedy algorithm. Our algorithm
is designed to meet the principal design objective of \emph{maximizing
  useful work}. We assume that rovers will fail using a memoryless
failure model having a mean time to failure of 100 days, and this
failure is independent of whether the rovers are active or idle.
Hence, in order to complete the maximum amount of work before all
rovers fail, it is optimal to have all the rovers doing as much work
as often as possible; idle rovers are ``wasted resources.''

The basic greedy algorithm is augmented by three additional
concepts. Priority values are used to express the relative priority of
missions; this scheme allows the most valuable missions to be executed
first. If beneficial, multiple missions may be \emph{batched} and
executed sequentially by the same rover. Finally, if additional rovers
remain idle with no missions to execute, they may be assigned to
cooperate with some other rover on an assignment that can be executed
in parallel.

\subsubsection{Priority Values}
\label{sec:priority-values}

In particular, we would like to accomplish the most useful work as
quickly as possible. This concept of relative utility is expressed by
the priority value associated with each mission. This is an extension
to the design specifications, but it has several important properties
that make it a natural addition. The first is the very likely
possibility that all missions are not of equal value. Second, even in
the original non-prioritized case, it neatly resolves the ambiguity of
whether each mission has the same value, or whether longer missions
are inherently more valuable than shorter ones: in the former case,
each mission can be assigned the same priority value, and in the
latter case each mission can be given a priority value proportional to
its length. It also allows NASA to provide low-priority experiments
that will be executed only if rovers are available, which can help
ensure that rovers are never idle. Finally, though we do not
explicitly address starvation in this design (we presume that
higher-valued missions really are valued higher, and hence should be
prioritized over others), it is easy to imagine a solution that would
address starvation by incrementing the priority values for missions
that have been in the queue longer.

Accordingly, we rank available assignments in terms of the quotient
$\left(\frac{\mbox{priority value}}{\mbox{required time}}\right)$, and
  assign them greedily. We define a procedure \proc{Greedy-Select}
  that takes a list of assignments, ranks them, and selects the
  highest-ranked. We will use this to iteratively assign the mission
  with highest quotient to the first available rover, and eliminate it
  from the available mission pool.


\subsubsection{Batching}
\label{sec:batching}

We also allow for \emph{batching} of multiple missions when it is
advantageous. That is, we may consider having a rover execute one
mission, then proceed to execute a different mission without returning
to the control center first. The advantage of this scheme is obvious:
if the two missions take place close together, more work can be
accomplished in the same time, since we avoid the overhead of having
to travel along the possibly-circuitous route from one mission site
back to the control center then to the second mission site. The
drawback is that the rover will be away from the control center
longer, and the probability that it will fail while executing its
assignment increases accordingly. Moreover, a rover failure has the
potential to be more catastrophic because it can cause the data for
\emph{all} the missions it is executing to be lost, not just a single
mission.

We attempt to quantify the benefit or cost of a particular batching
assignment of two missions $a$ and $b$ using this reasoning, in the
following equation:

\begin{multline*}
  \proc{Travel-Time}(\proc{End}(a) \to \proc{Start}(b))
- 
\shoveleft{  \proc{Travel-Time}(\proc{End}(a) \to \id{control-center} \to
  \proc{Start}(b))  }
  \\
\shoveleft{>
  \proc{Work-Required}(a) * \id{failure-probability} *}\\
  \shoveleft{ (\proc{Travel-Time}(\proc{End}(a) \to \proc{Start}(b))\; 
          +\proc{Work-Required}(b)}\\
         \shoveleft{ +\proc{Travel-Time}(\proc{End}(b) \to \id{control-center})
          -\proc{Travel-Time}(\proc{End}(a) \to \id{control-center})}
        )
\end{multline*}

This equation takes into account the benefit of the time saved by
traveling from $a$'s endpoint directly to $b$, rather than through the
control center, and weighs it against the product of the probability
that the rover will fail in the extra time it spends performing
mission $b$, with the work from mission $a$ that would be lost in such
a failure.

Before performing mission assignments, the mission distributor on the
control center first examines all pairs of available missions, and
evaluates whether it would be beneficial to batch them using this
metric. If so, it joins the two, and then repeats the process to see
if there are any other missions it would be beneficial to batch with
the pair. When we join two assignments together, we sum their priority
values; this reflects that the new assignment will be doing more
useful work. This process is repeated until no further beneficial
batchings remain.


\subsubsection{Cooperative Execution}
\label{sec:cooperative-rovers}

Our scheduling approach is optimized for the case in which there are
more unassigned missions than available rovers. In this case, it can
assign one rover per mission (and sometimes one rover per multiple
missions, when batching can be performed), selecting the missions that
provide the greatest benefit the most rapidly. This process ensures
that the most limited resource, rover time, is allocated effectively.

It is reasonable to assume that more missions will be available than
rovers. First, it is always possible for NASA to upload more missions
to ensure an ample supply is available. Since we divide scattered and
scattered-cluster missions into their component parts
(Section~\ref{sec:new-missions}), the mission distributor actually has
more missions in its queue than were transmitted by NASA. Finally, as
rovers inevitably fail, the number of remaining rovers will dwindle,
so that eventually there will be more missions than rovers, even if
originally more rovers than missions were available.

However, a recent amendment to the specifications proclaimed that at
any given time there would be approximately 25 missions either being
executed or waiting to be distributed. Hence, when we have a mission
available that requires some experiment to be performed repeatedly in
order to achieve the desired failure probability, we allow for
multiple rovers to be cooperatively assigned to the same mission.

Though this is not optimal in terms of maximizing useful work done,
since both rovers will incur the overhead of traveling to the
appropriate location, it allows missions to be performed more rapidly.
Additionally, the multiple rovers provide redundancy: if one rover
fails while performing the experiment, its previous results will have
been replicated onto the other rovers, minimizing the amount of result
data lost. It is certainly appropriate to perform cooperative
execution if idle rovers are available at the control center, since
their time would otherwise go to waste.

The algorithm in Figure~\ref{fig:cooperative-pseudocode} is used to
determine whether to assign rovers cooperatively to a mission
assignment. First, there must be rovers available and no outstanding
unassigned missions. Next, each assignment that has been previously
assigned to another rover is considered. The assignment must have
fewer rovers executing it than the maximum number of repetitions
required for any experiment in the assignment. The algorithm also
takes into account how long it has been since the previous rovers were
assigned to that mission: if the rovers had been assigned a long time
in the past, they may be almost complete executing the mission, and
there is no point to assigning more rovers to it. Hence, we take the
sum of the times since all previous rovers had been given that
assignment, divide it by the duration of the experiment requiring the
most repetitions, and subtract that from the maximum number of
repetitions required. If the resulting number of repetitions is
greater than 1, the assignments will be considered for cooperative
execution. If multiple assignments satisfy this criterion, the
allocation will be performed greedily using the same metric as for
normal assignments.

\begin{figure}[htbp]
  \centering
  \begin{codebox}
    \Procname{\proc{Assign-Cooperative-Assignments}()}
    \li \While rovers are available \textbf{and} no missions are unassigned
    \li \Do
      $\id{available-assignments} \gets \{\}$
      \li \For \id{assignment} \textbf{in} \id{busy-rover-assignments}
      \li \Do
        $x \gets
        \proc{Maximum-Number-of-Repetitions-in}(\id{assignment})$
        \li $x \gets x -
        \proc{Number-of-Rovers-Currently-Executing}(\id{assignment})$
        \li \If $x > 1$
        \li \Then
          $\id{available-assignments} \gets \id{available-assignments} \;\cup
          \; \{\id{assignment}\}$
      \End
      \End
    \li $\id{selected-assignment} \gets \proc{Greedy-Select}(assignments)$
    \li \proc{Assign}(\id{selected-assignment}, first available rover)
    \End
    \end{codebox}
  \caption{Cooperative assignment pseudocode}
  \label{fig:cooperative-pseudocode}
\end{figure}

\subsubsection{The Algorithm}
\label{sec:distributing-algorithm}

The mission distributing algorithm is presented in
Figure~\ref{fig:distributing-algorithm}. The mission distributor first
takes the list of available mission assignments, and batches them
together whenever appropriate. It then ranks the assignments in terms of
the quotient of their priority value and the required time-to-execute,
and greedily assigns them to available rovers. If all missions are
assigned and additional rovers remain, they will be considered for
cooperative assignment execution (as described above).

\begin{figure}[htbp]
  \centering
  \begin{codebox}
    \Procname{\proc{Distribute-Missions}()}
    \li \Comment Initialize the list of possible assignments from the
    available missions list
    \li $\id{assignments} \gets \{\}$
    \li \For $\id{mission}$ \textbf{in} \id{unassigned-missions}
    \li \Do
          $\id{assignments} \gets \id{assignments} \;\cup\;
            \{\id{mission}.\mbox{tasks}\}$
        \End
   \li
   \li \Comment Batch assignments together when beneficial
   \li \Comment Beneficial batchings are identified using the
   equation in Section~\ref{sec:batching}
   \li \While $\proc{Identify-Beneficial-Batchings}(\id{assignments})
            \neq \emptyset$
   \li \Do
         $\{a,b\} \gets
         \proc{First}(\proc{Identify-Beneficial-Batchings}(\id{assignments}))$
   \li   $\id{batched-assignment} \gets \proc{Join-Assignments}(a,b)$
   \li   $\id{assignments} \gets \id{assignments} \;\cup\;
         \{\id{batched-assignment}\} \; \setminus \; \{a,b\}$
       \End
   \li
   \li \Comment Greedily assign rovers to missions
   \li \While rovers are available \textbf{and} $\id{assignments} \neq
   \emptyset$
   \li   \Do
           $\id{selected-assignment} \gets \proc{Greedy-Select}(assignments)$
   \li     \proc{Assign}(\id{selected-assignment}, first available
           rover)
   \li     $assignments \gets assignments \;\setminus\;
   \{\id{selected-assignment}\}$
         \End
   \li
   \li \If rovers are still available
   \li   \Do
          \proc{Assign-Cooperative-Assignments}()
         \End
     
  \end{codebox}
  \caption{Mission distribution algorithm pseudocode}
  \label{fig:distributing-algorithm}
\end{figure}

\subsection{Result Collection}
\label{sec:result-collection}

The control center handles the task of retrieving mission results from
rovers that have completed their assignments, and transmitting this
data to NASA on Earth. When a rover returns to and locates the control
center, it begins a transmission to the control center. It then
transmits the contents of its mission results buffer to the control
center. This is a sequence of mission results, each tagged with
appropriate metadata: the location and type of experiment performed,
the mission ID and revision number of the mission that the experiment
was performed for, the ID number of the rover that performed the
experiment, and the time at which the experiment was performed.

When a mission result is received, the control center adds it to a
queue of results awaiting transmission back to Earth. The only
exception is if the same result --- with identical metadata, including
the performing-rover and timestamp --- is already in the queue. In
this case, the duplicate result is simply discarded. In all other
cases, the result is queued for transmission. We do so even if the
result is presumed to be invalid due to a sensor fault, since the
scientists at NASA may wish to attempt to recover meaningful data or
diagnose the faulty sensor for it. Similarly, we also return results
even if they may no longer be meaningful due to an amendment, since
the results may still be useful and it seems wasteful to simply
discard them. In doing so, we make the assumption that there is
adequate bandwidth (albeit high latency and limited availability) to
transmit all the data; if this is not the case, it may be necessary to
discard presumed-invalid results.

The control center is periodically queried by NASA on Earth to see if
there are any mission results available. If so, it transmits all
available mission results. Once the results are acknowledged, they are
deleted from the control center's queue. If all results pertaining to
a mission have been completed and transmitted to Earth, and no rovers
are currently assigned to that mission, the mission may be considered
complete and removed from the mission status table.

\subsection{Handling Rover Failures}
\label{sec:rover-failures}


Rovers can fail unpredictably. The control center can only detect
failures when it fails to receive any response from the rover. There
must therefore be a time after which the control center assumes the
rover has failed if no response has been received. We compute this
time by summing the required travel time and the time required to
perform and repeat the experiments. We then apply a ``slack'' scaling
factor that accounts for inaccuracies in travel and experiment times
estimate. The value of this scaling factor depends, of course, on the
quality of the estimates being used, and should be chosen accordingly.


The control center periodically iterates through the list of rovers,
and checks whether the difference between the current time and the
time that rover's mission was assigned is greater than the maximum
time previously mentioned. If the mission has not been completed by
this time, it is marked unassigned and the rover assigned to it is
marked dead. If it turns out that the rover was in fact still
operating, and it returns after being previously marked dead, the
experiment results will be downloaded, the mission marked completed,
and any new rover assigned to that mission treated as lame, as though
a mission amendment had been received. The second set of mission
results will still be returned to Earth, as described in
Section~\ref{sec:result-collection}.

We originally considered the possibility of sending a ``interceptor''
rover to travel to the location of the lame rover and inform it that
its mission has been made moot by an amendment. The two rovers could
then either return to the control center for a new assignment, or
proceed to execute the next mission. Though this could conceivably
eliminate some of the wasted time used by lame rovers that continue to
execute missions that are no longer relevant, it is fraught with
complexities and we concluded that it would be impractical. First, it
is not always beneficial to send an interceptor rover; if the lame
rover has almost completed executing its mission, the minimal time
savings will be nullified by the time required to send the
interceptor. More troublesome, it is non-trivial to correctly deliver
a message. The location of the target rover must be ascertained, and
this becomes impractical because of the number of variables
involved. The travel time and experiment execution times are only
estimates, so it is impossible to compute with complete certainty
where the rover will be found at a certain time. If the interceptor
does not find its target rover where it was expected to be, it cannot
determine whether the rover has failed, or whether it has simply
finished its earlier tasks more quickly or slowly than expected. In
light of these complexities, we opted not to use this approach.


\subsection{New Missions and Amendments}
\label{sec:new-missions}

When a mission is received, it is added to the mission table in the
unassigned state. Scattered and scattered-cluster missions are broken
up into their individual or cluster components, and these are treated
as separate missions. Dependency lists, as described in
Section~\ref{sec:distribution-state} are used to ensure that the
individual components of each scattered mission are executed in order.
This allows rovers to return to the control center to offload their
data between parts of the scattered mission, minimizing the amount of
data that will be lost if the rover fails. The tradeoff here is
between the time that will be lost traveling back to the control
center instead of directly between the two mission locations, and the
expected increase in the amount of work that will need to be redone if
the rover fails. Fortunately, this tradeoff is accounted for by the
batching algorithm (Section~\ref{sec:batching}). If it is ultimately
beneficial for a rover to travel directly between two mission
locations, it will do so; otherwise, it will travel first to the
control center. The priority value of a scattered or scattered-cluster
mission is divided among the new component missions, proportionally to
the amount of work in each mission.

When an amendment is received from Earth, the mission distributor
updates the mission table with the new parameters and increments the
mission's revision number.  If the mission is still unassigned, no
further processing is necessary; the newly-revised mission will be
distributed by the assignment algorithm when it is appropriate to do
so. If the mission has already been assigned or completed, then the
modified portions of the mission will be rescheduled as though it were
a new mission. Any rover that is currently executing the old revision
of the mission will be marked ``lame''.  If the lame rover completes
the old mission, the revision number information will indicate to the
control center that it is an outdated revision and is not satisfactory
for the purpose of marking the mission as completed. The results,
however, will still be sent back to Earth, since they may still be of
some value.

If any rovers are currently in the available state when new missions
or amendments are received, the mission distributor will re-run the
assignment algorithm to appropriately assign the new missions to the
available rovers.



% LocalWords:  rovers rover's
