robotics-exercises.tex

%%%% 25.3: Robotic Perception (2 exercises, 2 labelled)
%%%% ==================================================

\begin{exercise}[mcl-biasdness-exercise]%
Monte Carlo localization is {\em biased} for any finite sample size---i.e., the
expected value of the location computed by the algorithm differs from the true expected value---because of the way 
particle filtering works. In this question, you are asked to quantify this bias.

To simplify, consider a world with four possible robot
locations: \(X=\{x_\N{1},x_\N{2},x_\N{3},x_\N{4}\}\). Initially, we draw \(N\geq \N{1}\)
samples uniformly from among those locations. As usual, it is
perfectly acceptable if more than one sample is generated for any of
the locations \(X\).  Let \(Z\) be a Boolean sensor variable
characterized by the following conditional probabilities:
\begin{eqnarray*}
P(z\mid x_\N{1}) &=& \N{{0.8}} \qquad\qquad P(\lnot z\mid x_\N{1})\;\;=\;\;\N{{0.2}} \\
P(z\mid x_\N{2}) &=& \N{{0.4}} \qquad\qquad P(\lnot z\mid x_\N{2})\;\;=\;\;\N{{0.6}} \\
P(z\mid x_\N{3}) &=& \N{{0.1}} \qquad\qquad P(\lnot z\mid x_\N{3})\;\;=\;\;\N{{0.9}} \\
P(z\mid x_\N{4}) &=& \N{{0.1}} \qquad\qquad P(\lnot z\mid x_\N{4})\;\;=\;\;\N{{0.9}}\ .
\end{eqnarray*}
MCL uses these probabilities to generate particle weights, which are
subsequently normalized and used in the resampling process. For
simplicity, let us assume we generate only one new sample in the
resampling process, regardless of \(N\).  This sample might correspond
to any of the four locations in \(X\).  Thus, the sampling process
defines a probability distribution over \(X\).

\begin{enumerate}
\item  What is the resulting probability distribution
over \(X\) for this new sample? Answer this question separately for
\(N=\N{1},\ldots,\N{{10}}\), and for \(N=\infty\).  

\item The difference between two probability distributions \(P\) and \(Q\)
can be measured by the KL divergence, which is defined as
\[
  \J{KL}(P,Q) = \sum_i P(x_i)\log\frac{P(x_i)}{Q(x_i)}\ .
\]
What are the KL divergences between the distributions in (a)
and the true posterior?

\item
What modification of the problem formulation (not the algorithm!)
would guarantee that the specific estimator above is unbiased even for
finite values of \(N\)?  Provide at least two such modifications (each
of which should be sufficient).
\end{enumerate}
\end{exercise} 
% id=25.0 section=25.3

\begin{exercise}[mcl-implement-exercise]\prgex%
Implement Monte Carlo localization for a simulated robot  with range
sensors.  A grid map and range data are available from the code repository
at \url{aima.cs.berkeley.edu}.
%% http://www.cs.cmu.edu/~thrun/16-899/data
You should demonstrate successful global
localization of the robot.
\end{exercise} 
% id=25.1 section=25.3


%%%% 25.4: Planning to Move (6 exercises, 4 labelled)
%%%% ================================================

%% \begin{figure}
%% \figbox{figures/figRobot1.eps}
%% %\centerline{\psfig{figure=figRobot1.eps}}
%% \caption{Robot configuration}
%% \label{figRobot1}
%% \end{figure}


\begin{figure}
\figboxnew{figures/figRobot2.eps}
%\centerline{\psfig{figure=figRobot2.eps}}
\caption{A Robot manipulator in two of its possible configurations.}
\label{figRobot2}
\end{figure}

\begin{exercise}[AB-manipulator-ex]
Consider a robot with two simple manipulators, as shown in 
figure~\ref{figRobot2}.
Manipulator A is a square block of side 2 
which can slide back and on a rod that
runs along the x-axis from x=$-$10 to x=10. 
Manipulator B is a square block of side 2 
which can slide back and on a rod that
runs along the y-axis from y=$-$10 to y=10. 
The rods lie outside the plane of manipulation, so 
the rods do not interfere with the movement of the blocks.
A configuration is then a pair $\la x,y\ra$ 
where $x$ is the x-coordinate of the center of manipulator A and 
where $y$ is the y-coordinate
of the center of manipulator B.
Draw the configuration space for this robot, indicating the permitted and
excluded zones.
\end{exercise} 
% id=extras-28-oct.0 section=25.4.1

\begin{uexercise}
Suppose that you are working with the robot in \exref{AB-manipulator-ex} and you are given
the problem of finding a path from the starting configuration of 
figure~\ref{figRobot2} to the ending configuration.  Consider a potential
function 
\[ D(A, \J{Goal})^2 + D(B, \J{Goal})^2 + \frac{1}{D(A, B)^2}
\]
where \(D(A,B)\) is the distance between the closest points of A and B.

\begin{enumerate} 
\item Show that hill climbing in this potential field will get
stuck in a local minimum.
\item Describe a potential field where hill climbing will solve this 
particular problem.  You need not work out the exact numerical coefficients 
needed, just the general form of the solution. (Hint: Add a term that ``rewards"
the hill climber for moving A out of B's way, even in a case like this where
this does not reduce the distance from A to B in the above sense.) 
\end{enumerate}
\end{uexercise} 
% id=extras-28-oct.1 section=25.4.1

%% \begin{iexercise} %fe-f02
%% Consider the problem of configuration space path planning in $d$ dimensions using a 
%% cell decomposition where each cell is a hypercube. Two cells are adjacent if they share (part of) a face.
%% Here are three possible algorithms, all of which run A$^*$ with a straight-line distance heuristic
%% and generate as successors only those cells in the current decomposition that are adjacent to the given cell.
%% \begin{itemize} 
%% \item Algorithm (i) uses a successor function that returns only pure free-space cells.
%% \item Algorithm (ii) uses a successor function that may return mixed free-space/obstacle cells (but no pure obstacle cells).
%% \item Algorithm (iii) is the same as (ii) except that,
%%          if the node it selects for expansion corresponds to a mixed cell, it subdivides the cell
%%          into hypercubes whose sides are exactly half the size of the original, puts the new cells back in the queue,
%%          and repeats the selection step. (For now, assume exact arithmetic.)
%% \end{itemize} 
%% \begin{enumerate}
%% \item Which algorithms are sound (i.e., return only correct solutions)?

%% \item Which algorithms are sound and complete (i.e., return a correct solution exactly when one exists)?

%% \item Are there are problems on which (i) succeeds but (iii) fails to terminate?
%% \item Briefly explain how to make algorithm (iii) $\epsilon$-complete, meaning that
%% it always finds a path if one exists that does not come within $\epsilon$ of an obstacle.
%% \end{enumerate}
%% \end{iexercise} 
%% % id=extras-28-oct.4 section=25.4.1

\begin{uexercise}[inverse-kinematics-exercise]%
Consider the robot arm shown in \figref{FigArm1}. Assume that the
robot's base element is 60cm long and that its upper arm and forearm are
each 40cm long.  As argued on
\pgref{inverse-kinematics-not-unique}, the inverse kinematics of a
robot is often not unique. State an explicit closed-form solution of
the inverse kinematics for this arm.  Under what exact
conditions is the solution unique?
\end{uexercise} 
% id=25.2 section=25.4

\begin{iexercise}[inverse-kinematics-exercise]%
Consider the robot arm shown in \figref{FigArm1}. Assume that the
robot's base element is 70cm long and that its upper arm and forearm are
each 50cm long.  As argued on
\pgref{inverse-kinematics-not-unique}, the inverse kinematics of a
robot is often not unique. State an explicit closed-form solution of
the inverse kinematics for this arm.  Under what exact
conditions is the solution unique?
\end{iexercise} 
% id=25.2 section=25.4

\begin{exercise}[voronoi-exercise]\prgex%
Implement an algorithm for calculating the
Voronoi diagram of an arbitrary 2D environment, described by an \(n\stimes n\) Boolean array.
Illustrate your algorithm by plotting the Voronoi diagram for 10 interesting maps.
What is the complexity of your algorithm?
\end{exercise} 
% id=25.3 section=25.4

\begin{exercise}[confspace-exercise]%
This exercise explores the relationship between workspace and configuration space
using the examples shown in \figref{FigEx2}.
\begin{enumerate}
\item Consider the robot
configurations shown in \figref{FigEx2}(a) through (c), ignoring the
obstacle shown in each of the diagrams. Draw the corresponding arm
configurations in configuration space. ({\em Hint:} Each arm configuration
maps to a single point in configuration space, as illustrated in
\figref{FigArm1}(b).)

\item Draw the configuration space for each of the workspace diagrams in
\figref{FigEx2}(a)--(c).  ({\em Hint:} The configuration spaces share
with the one shown in \figref{FigEx2}(a) the region that corresponds
to self-collision, but differences arise from the lack of enclosing
obstacles and the different locations of the obstacles in these
individual figures.)

\item For each of the black dots in \figref{FigEx2}(e)--(f), draw the
corresponding configurations of the robot arm in workspace. Please
ignore the shaded regions in this exercise.

\item The configuration spaces shown in \figref{FigEx2}(e)--(f) have
all been generated by a single workspace obstacle (dark shading), plus
the constraints arising from the self-collision constraint (light
shading). Draw, for each diagram, the workspace obstacle that corresponds
to the darkly shaded area.

\item \figref{FigEx2}(d) illustrates that a single
planar obstacle can decompose the workspace into two disconnected
regions. What is the maximum number of disconnected regions that can be
created by inserting a planar obstacle into an obstacle-free,
connected workspace, for a 2DOF robot? Give an example, and argue why
no larger number of disconnected regions can be created. How about a 
non-planar obstacle?
\end{enumerate}
\end{exercise} 
% id=25.4 section=25.4

\begin{figure}[t]
\threebytwofigboxnew{figures/exerciseRobot1.eps}{figures/exerciseRobot3.eps}{figures/exerciseRobot6.eps}{figures/exerciseConf2.eps}{figures/exerciseConf4.eps}{figures/exerciseConf5.eps}
\caption{Diagrams for \protect\exref{confspace-exercise}.}
\label{FigEx2}
\end{figure} 
% id=25.5 section=25.4


%%%% 25.6: Moving (3 exercises, 2 labelled)
%%%% ======================================

\begin{exercise}
Consider a mobile robot moving on a horizontal surface.  Suppose that the
robot can execute two kinds of motions:
\begin{itemize}
\item Rolling forward a specified distance.
\item Rotating in place through a specified angle.
\end{itemize}
The state of such a robot can be characterized in terms of three 
parameters $\la x,y,\phi$, the x-coordinate and y-coordinate of the robot
(more precisely, of its center of rotation) and the robot's orientation 
expressed as the angle from the positive x direction.  The action
``$Roll(D)$'' has the effect of changing state $\la x,y,\phi$ to
$\la x+D \cos(\phi), y+D \sin(\phi), \phi \ra$, and the action $Rotate(\theta)$
has the effect of changing state $\la x,y,\phi \ra$ to 
$\la x,y, \phi + \theta \ra$.

\begin{enumerate}
\item
Suppose that the robot is initially at $\la 0,0,0 \ra$ and then executes
the actions $Rotate(60^{\circ})$, $Roll(1)$, $Rotate(25^{\circ})$, $Roll(2)$.
What is the final state of the robot?

\item Now suppose that the robot has imperfect control of its own rotation,
and that, if it attempts to rotate by $\theta$, it may actually rotate by any
angle between $\theta-10^{\circ}$ and $\theta+10^{\circ}$. In that case,
if the robot attempts to carry out the sequence of actions in (A), there is
a range of possible ending states. What are the minimal and maximal values
of the x-coordinate, the y-coordinate and the orientation in the final state?

\item Let us modify the model in (B) to a probabilistic model in which,
when the robot attempts to rotate by $\theta$, its actual angle of rotation
follows a Gaussian distribution with mean $\theta$ and standard deviation
$10^{\circ}$. Suppose that the robot executes the actions $Rotate(90^{\circ})$,
$Roll(1)$.  Give a simple argument that (a) the expected value of the location
at the end is not equal to the result of rotating exactly $90^{\circ}$ and
then rolling forward 1 unit, and (b) that the distribution of locations
at the end does not follow a Gaussian.  (Do not attempt to calculate 
the true mean or the true distribution.) 

The point of this exercise is that rotational uncertainty quickly gives rise
to a lot of positional uncertainty and 
that dealing with rotational uncertainty is 
painful, whether uncertainty is treated in terms of hard intervals
or probabilistically, due to the fact that the relation between orientation
and position is both non-linear and non-monotonic.
\end{enumerate}
\end{exercise} 
% id=extras-28-oct.2 section=25.6

\begin{figure}[t]
%%\epsfxsize12cm
\figboxspacenew{10pt}{figures/robotics-pic7.eps}
\caption{Simplified robot in a maze. See \protect\exref{robot-exploration-exercise}.}
\label{FigEx3}
\end{figure} 
% id=25.6 section=25.6

\begin{exercise}[robot-exploration-exercise]%
Consider the simplified robot shown in
\figref{FigEx3}.  Suppose the robot's Cartesian coordinates are
known at all times, as are those of its goal location. However, the
locations of the obstacles are unknown. The robot can sense obstacles
in its immediate proximity, as illustrated in this figure. For
simplicity, let us assume the robot's motion is noise-free, and the
state space is discrete. \figref{FigEx3} is only one example; in
this exercise you are required to address all possible grid worlds
with a valid path from the start to the goal location.

\begin{enumerate}
\item Design a deliberate controller
that guarantees that the robot always reaches its goal
location if at all possible. The deliberate controller can memorize
measurements in the form of a map that is being acquired as the robot
moves. Between individual moves, it may spend arbitrary time
deliberating.

\item Now design a {\em reactive}
controller for the same task. This controller may not memorize past
sensor measurements. (It may not build a map!) Instead, it has to make
all decisions based on the current measurement, which includes
knowledge of its own location and that of the goal.  The time to make
a decision must be independent of the environment size or the number
of past time steps.  What is the maximum number of steps that it may
take for your robot to arrive at the goal?

\item
How will your controllers from (a) and (b) perform if any of the
following six conditions apply:
continuous state space,
noise in perception,
noise in motion,
noise in both perception and motion,
unknown location of the goal (the goal can be detected only when within sensor range),
or
moving obstacles. For each condition and each controller,
give an example of a situation where the robot fails (or explain why it cannot fail).
\end{enumerate}
\end{exercise} 
% id=25.7 section=25.6

\begin{exercise}[subsumption-exercise]%
In \figref{Fig5}(b) on \pgref{Fig5}, we encountered an augmented finite state
machine for the control of a single leg of a hexapod robot. In this
exercise, the aim is to design an AFSM that, when combined with
six copies of the individual leg controllers, results in efficient, stable locomotion.
For this purpose, you have to augment the individual leg
controller to pass messages to your new AFSM and to wait until other
messages arrive. Argue why your controller is efficient, in
that it does not unnecessarily waste energy (e.g., by sliding legs),
and in that it propels the robot at reasonably high speeds.
Prove that your controller satisfies the dynamic stability condition
given on \pgref{polygon-stability-condition-page}.
\end{exercise} 
% id=25.8 section=25.6


%%%% 25.7: Robotic Software Architectures (1 exercises, 1 labelled)
%%%% ==============================================================

\begin{exercise}[human-robot-exercise]%
(This exercise was first devised by Michael
Genesereth\nindex{Genesereth, M.~R.} and Nils Nilsson\nindex{Nilsson,
N.~J.}. It works for first graders through graduate students.)  Humans
are so adept at basic household tasks 
that they often forget how complex these tasks are. In this exercise
you will discover the complexity and recapitulate the last 30 years of
developments in robotics.\index{robot!game (with humans)}\index{game!robot (with humans)} 
Consider the task of building an arch out of three blocks. Simulate a robot 
with four humans as follows:

{\bf Brain.} The Brain direct the hands in the execution of a
plan to achieve the goal. The Brain receives input from the Eyes, but {\em cannot see the
scene directly}. The brain is the only one who knows what the goal is.

{\bf Eyes.} The Eyes report a brief description of the
scene to the Brain:
``There is a red box standing on top of a green box, which is on its
side'' Eyes can also answer
questions from the Brain such as, ``Is there a gap between the Left
Hand and the red box?'' If you have a video camera, point it at the
scene and allow the eyes to look at the viewfinder of the video camera,
but not directly at the scene.
 
{\bf Left hand} and {\bf right hand.}  One person plays each Hand.
The two Hands stand next to each other, each wearing an oven mitt on one hand,
Hands execute only simple commands from the Brain---for example,
``Left Hand, move two inches forward.'' They cannot execute commands
other than motions; for example, they cannot be commanded to ``Pick up the box.'' 
The Hands must be {\em blindfolded}. The only sensory capability they
have is the ability to tell when their path is blocked by an immovable
obstacle such as a table or the other Hand. In such cases, they can
beep to inform the Brain of the difficulty.
\end{exercise} 
% id=25.9 section=25.7



% \begin{exercise}\label{kalman-exercise}%
% This exercise requires advanced mathematical skills.
% \begin{enumerate}
% \item Derive the extended Kalman filter update equations (\ref{eqEKFLoc1}) and
% (\ref{eqEKFLoc2}) for the one-dimensional case.
% \item
% Calculate the Jacobian of the robot motion
% model \(f\) in (\ref{eqRoboticsMotionModel}) with respect to the
% state \(X_{t}\)
% \item
% Do the same for the measurement model \(h\) as
% defined in Equation (\ref{eqRoboticsSensorModel}).
% \end{enumerate}
% \end{exercise}



%#@-------------------------------------------------------------------------%
%#@-------------------------------------------------------------------------%


%#@-------------------------------------------------------------------------%
%#@-------------------------------------------------------------------------%