% -*- TeX-master: "dp2.tex" -*-
% $Id: mission-execution.tex,v 1.3 2004/05/06 14:10:43 dan Exp $

Each rover is capable of autonomously executing missions according to
parameters received from the control center. It does so by maintaining
a queue of instructions, known as an \emph{assignment}. There are three
types of instructions:

\begin{itemize}
\item travel to a certain location
\item perform an experiment (e.g. taking a photo)
\item return to the control center
\end{itemize}

\begin{table}[htbp]
  \centering
  \begin{minipage}{4.5in}
    \centering
    \begin{tabular}{|c|c|}
      \hline
      \textbf{Field} & \textbf{Type} \\
      \hline
      Instruction number & integer \\
      Instruction type & 2-bit instruction typecode (see above) \\
      Arguments\footnote{Destination to travel to, or type of
      experiment to perform and experiment parameters, depending on
      instruction type} & variable \\
      Required repetitions\footnote{For perform-experiment
      instructions only} & integer \\
      Associated mission ID & integer \\
      Associated mission revision number & integer \\
      \hline
    \end{tabular}
  \end{minipage}
  \caption{Instruction data format}
  \label{tab:instruction-format}
\end{table}

The rover also maintains a table of results. Each result contains
metadata that identifies the experiment, the mission the experiment
was performed for, and the rover performing the experiment, as in
Table~\ref{tab:result-format}. This ensures that it is possible to
identify which experimental results are unique, even when different
rovers perform the same experiment or deliver the same results back to
the command center.

\begin{table}[htbp]
  \centering
  \begin{tabular}{|c|c|}
    \hline
    \textbf{Field} & \textbf{Type} \\
    \hline
    Experiment & type of experiment and arguments \\
    Experiment location & location \\
    Experiment timestamp & time \\
    Associated mission ID & integer \\
    Associated mission revision number & integer \\
    Performing rover ID & integer \\
    \hline
  \end{tabular}
  \caption{Result data format}
  \label{tab:result-format}
\end{table}

The rover proceeds linearly through its queue of instructions,
executing the first instruction and removing it from the queue once
completed. To perform experiments that require multiple repetitions,
the rover performs the experiment until it has gathered the correct
number of copies of the result in its result table. After each
experiment execution is completed, it exchanges experiment results with
any other rovers that are in range (i.e. other rovers performing the
same experiment), and incorporates any of their results into its
result table. This allows for multiple rovers to work cooperatively on
the same mission (Section~\ref{sec:rover-cooperation}).

\subsection{Sensor Failure}
\label{sec:sensor-failure}

When a rover performs a experiment, there is a non-zero probability of
sensor failure. We assumethat when a sensor fails, the faulty
readings are uniformly distributed over the possible sensor range, and
thus there will be no pattern in bad readings.  Thus, when readings
match, it is more likely that they are both correct than that they are
both wrong.  The number of readings that would have to agree in order
to be confident in their value depends to some extent on the
probability of failure.  So, to ensure that a correct result is
returned with 95\% probability (or whatever certainty rate the
scientists deem reasonable), the rover will repeat the experiment a
certain number of times.

We will use the thermometer as an example for
how this number can be computed.


\paragraph{Example}   The thermometer's fault rate is
given as 7\%.  If we merely took 2 readings, then if one or more of
the readings were bad there would be no way to tell which was correct.
However, if we took three readings, this would give us a 98.60\%
chance of having at least 2 good results.  Therefore, we could just
send all 3 readings back in the data, and have a 98.60\% chance of
giving the scientists usable data.  This number was obtained by
finding the probability of having 2 good results, plus the probability
that all 3 readings are good.  With $n$ experiments and a probability
$p$ of success, the probability of having $k$ successes is given by
the following formula:
\[ \binom{n}{k}p^k (1-p)^{(n-k)} \]
And so the probability of having \emph{at least} $k$ successes is
\[ \sum_{i = k}^n \binom{n}{i} p^i (1-p)^{(n-i)} \]

So, for each sensor, we just need to calculate beforehand a value of
$n$ that will give us a sufficient chance of having at least $k =
\left\lceil\frac{n}{2}\right\rceil$ reliable readings. This approach
requires only knowledge of the failure probability $p$. The rover
itself does not have to analyze data in any way. The advantage of
this approach is simple: the rover does not need to have any
knowledge of how to interpret the mission results. Instead, the
results can be evaluated by the scientists on Earth, who are
presumably better equipped to identify and analyze correct results. If
they deem the experiment results to be unsatisfactory, the mission can
be re-inserted into the queue of missions to perform, forcing the
mission to be repeated.

\subsection{Rover Cooperation}
\label{sec:rover-cooperation}

In some cases where an experiment must be repeated, multiple rovers
may be sent out together.  In this case, when a rover finishes an
experiment, it will send its results to all the other rovers within
communications range, and receive any results from the other rovers.
When a rover has all $n$ required data points, it will move on to the
next instruction, which is probably to return to central control.  If
one of the rovers fails during this time, then the other rovers will
not be affected because they are not waiting for any responses from
that rover.

\subsection{Data Exchange}
\label{sec:data-exchange}

Finally, if two rovers should happen to pass within communication
range in the course of their travels, each rover will transmit any
experimental data it has collected to the other. If a rover does not
have enough room for the additional data, then the data from the other
rover will simply be discarded.  The probability of rovers running
into each other randomly is small, given the number of rovers, the
size of the crater, and their relatively small communication radius,
but the probability of meeting is non-zero. In particular, there may
be points of interest in the crater which the rovers pass by
disproportionately often: locations near which many experiments are
performed, or on paths to and from the control center.  Having
duplicates of experimental data being carried by other rovers can only
help the chance of that data being brought back to the control center,
and does not have any negative side effects.  If one rover fails
before returning to the control center, the data may make its way back
via one of the other rovers.  This extra layer of redundancy might not
have a very large effect on the overall performance of the system, but
it will have some positive effect for very little cost, so therefore
it is worthwhile to implement it.

The one confusion that might arise from this aspect of the design is
the possibility of multiple copies of an experiment reaching control
center.  If the data for a given experiment is already in the result
tables, and is listed with the metadata, then the new data
should be interchangeable for the old, and thus unimportant.
Therefore, it can be simply discarded. 