\documentclass{article}
\include{6033-preamble}
\usepackage{graphicx,fullpage}

\begin{document}
%\title {Design Project 2 Proposal}
%\author {Dan Ports, Amanda Smith, Sarah Lieberman}
%\maketitle

\begin{center}
\par
\huge{An Autonomous System\\for Scientific Experimentation on Mars}
\vskip 1em
{\lineskip .75em
\Large{Dan Ports, Amanda Smith, and Sarah Lieberman}\par
\Large{April 13, 2004}\par
\vskip 1em
\large{6.033 Design Project 2 Proposal}\par
\large{Recitation \#9: Karger/Lesniewski-Laas}
}\end{center}


\section{Overview}
       The Mars Rover project can most easily be split into two
components: communication protocol and mission distribution and execution.
The problems associated with communication protocol are relatively
straightforward and include message authentication and error detection and
correction. Mission distribution and execution encompasses a wider range of
issues; apart from a basic distribution algorithm, we must be able to deal
with rover failure, unreliable sensors, amendments, and the scheduling of
data upload.

\section{Communications}\
            Communication protocol further breaks down into two
categories: communication on Mars (between two rovers or between the rovers
and central command) and communication to Earth (from central command).
Communication to Earth need only worry about transmission errors and
messages that are not received. The first issue can be dealt with by
including a hash with each message sent, so errors can be detected.  Also,
transmission errors can be reduced using error correcting codes.  The
second issue is addressed by verification messages. Since it takes so long
to communicate between Earth and Mars, the central command cannot wait for
verification messages between packets, but it can resend a packet if its
verification message is not received after a certain period of time. The
message hashes can also be implemented in communications between the rovers
and the central command. Additionally, message authentication on Mars, to
prevent confusion between NASA and Poodle rovers, can be implemented by
signing each message with a shared secret key known to all rovers and the
command center. Since there are no malicious entities on Mars, no
encryption or sealing is needed. Naming is trivial, because each of the
fifty rovers can be programmed with a unique number. Finally, in order to
determine whether there are other NASA devices within communication
distance, the rover or command center can broadcast a predefined "who's
here?" message. Any device which hears this message will broadcast a
message containing its identifier.


\section{Mission Execution}
\label{sec:mission-execution}

Each rover is capable of autonomously executing missions according to
parameters received from the control center. It does so by maintaining
a queue of instruction. There are three types of instructions:
\begin{itemize}
\item travel to a certain location
\item perform an experiment (e.g. taking a photo)
\item deliver a message to another rover
\item return to the control center
\end{itemize}

When a rover performs a experiment, there is a non-zero probability of
sensor failure. However, to ensure that a correct result is returned
with 95\% probability, the rover will repeat the experiment the
required number of times. For example, if taking a thermometer reading
has a 7\% probability of a sensor fault, it will be performed until
two matching results are obtained. The results obtained from each
experiment are stored in the rover's memory.

Finally, if two rovers should happen to pass within communication
range in the course of their travels, and space is available, each
rover will transmit any experimental data it has collected to the
other. This provides an additional layer of redundancy if one rover
should fail before returning its data to the control center.

\section{Mission Distribution}
\label{sec:mission-distribution}

The control center receives missions and amendments from Earth and
allocates them to rovers. Hence, it must maintain a table of
missions. Each mission comprises a set of tasks to be executed at a
certain, and is identified with a mission ID and revision number.
The control center also associates states with each mission: whether
it has been assigned, and whether it has been partially or fully
completed.

The control center also maintains a table of rovers. A rover can
be:

\begin{itemize}
\item \emph{available}, meaning it is present at the control
  center and waiting to be assigned a mission
\item \emph{busy}, meaning it is currently executing a mission
\item \emph{lame}, meaning it is currently executing a mission that
  has become moot due to an amendment
% is there a better term for this?
\item \emph{dead}, meaning that the control center has not heard from
  the rover and has presumed it to have failed
\end{itemize}
In addition, the control center keeps track of what mission, including
revision number (if any) the rover is currently executing, the time it
started, and when the rover is expected back (see below).

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.\footnote{It may also be necessary to ensure that
  the components of a scattered or scattered-cluster mission are
  executed in order. If so, this can also be done by adding extra
  information to the missions table.} This forces 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.

Whenever rovers are in the available state, missions
are assigned to them. Since all missions are treated as having equal
priority, the goal is to maximize the number of missions that are
executed before all rovers fail. Hence, we use a greedy algorithm that
ranks missions in terms of their expected time to
complete\footnote{This algorithm is simple but sub-optimal. It could
  (and probably will) be improved by taking in to account factors such
  as batching of nearby missions to minimize travel time.} This is
computed as the sum of the round-trip travel time required plus for
each experiment the product of the expected time required to execute
the experiment and the expected number of times the experiment will
need to be repeated. When a rover is available, it assigns the
``cheapest'' mission to the rover by uploading the proper instruction
and setting the state tables appropriately.

When an amendment is received from Earth, it 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. 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. If a ``lame'' rover is still executing the
mission, then it may be advantageous to dispatch another rover to tell
it to abort.\footnote{Batching would be especially useful here --- the
  two rovers could then proceed to execute the amended mission and/or
  other missions without returning to the control center.} This can be
implemented by treating the message-delivery as a mission whose
expected time to completion for scheduling purposes takes into account
both the time required for delivering the message and the time saved
by aborting the mission. If the lame rover completes the old mission,
the revision number information will indicate to the control center
that it is outdated and should probably be ignored.

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 bound of required
time to perform and repeat the experiments in 95\% of cases. 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 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.


\section{Conclusion}
\label{sec:conclusion}
This design provides for autonomous central control of a multi-rover
system in such a way that amendments, sensor and rover failure, and
poor communications are handled in a reasonable manner such that valid
scientific data will still be collected.  Some of the design choices
we have made rely on assumptions that have been presented to us about
the world this project exists in.


\end{document}