\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{6}

% title command
\newcommand{\mytitle}[1]{\begin{center} {\Large Artificial Intelligence -- 
6.034 Problem Set \psnum \\ Juliet Bourne -- Section R1 -- #1} \\ 
\vspace{-.1in}
\rule{6in}{.5mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace{.15in}\noindent{\fbox{\large\bf Problem #1}}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
% newpage setup command 
\newcommand{\mynewpage}{\newpage\noindent
\begin{center}
{\Large 6.034 Problem Set \psnum -- Juliet Bourne -- {\bf Page \thepg}}
\rule{6in}{.5mm}
\end{center}
\addtocounter{pg}{1}}
% see-page command
\newcommand{\seepage}{\noindent See page \rule{.2in}{.1mm} for the
computer output.}

\begin{document}

\mytitle{11/12/90}

\prob{1}

\subprob{A} The correct configuration obstacles look like this:

\vspace*{3.5in}

\subprob{B} {\bf POSSIBLY-OPTIMAL?} selects only the edges that can
possibly be on an optimal path since it eliminates all of the edges
which points {\em into} an object. It does this by testing to see
whether the incident angle of the proposed edge lies within the range of
angles of both vertices involved. If it does not, then that implies that
the edge leads into an object and therefore can't be optimal. The
optimal edges are those that go tangentially around obstacles.

Not using the {\bf POSSIBLY-OPTIMAL?} test for edges, the maximum number
of edges (which may not be physically possible for a certain set of
objects) of a visibility graph for $n$ {\em convex} obstacles each
having $k$ vertices is $n \cdot k + n \cdot k^2$ for $n > 1$. This
arises when all the vertices of all the objects can see all the vertices
of all the other objects. This is a possible, but very rare, physical
situation.  Each object has $k$ edges connecting its vertices, which is
where the $n\cdot k$ comes from. 

Using {\bf POSSIBLY-OPTIMAL?}, the maximum number of edges is $n \cdot
k + n\cdot 2k$, since, even in the extreme case of every vertex seeing
every vertex of other objects, it is not possible for a vertex to have
more than two edges (other than the ones connecting vertices of the same
object).

\mynewpage

\prob{2}

\subprob{A}

\vspace*{1.5in}

\beq
x_1 = l_1 \cos \theta & \; \; \; & y_1 = l_1 \sin \theta \\
x_2 = r \sin \theta & \; \; \; & y_2 = r \cos \theta \\
x = x_1 - x_2 & = & l_1 \cos \theta - r \sin \theta \\
y = y_1 + y_2 & = & l_1 \sin \theta + r \cos \theta
\eeq

\subprob{B}

\vspace*{1.5in}

\beq
\gamma + \theta = \tan{}^{-1} \frac{y}{x} & \; \; \; & \gamma =
\tan{}^{-1} \frac{r}{l_1} \\
\theta & = & \tan{}^{-1} \frac{y}{x} - \tan{}^{-1} \frac{r}{l_1} \\
r^2 + l_1^2 & = & x^2 + y^2 \\
r^2 & = & x^2 + y^2 - l_1^2 \\
r & = & \sqrt{x^2 + y^2 - l_1^2}
\eeq

\subprob{C} No. There is only one $r,\theta$ pair that can reach a given
$(x,y)$. This is because the first link is a fixed length, $l_1$, and
the second link is fixed 90 degrees relative to the first link. There is
only one tangent that passes through $(x,y)$.

\mynewpage

\subprob{D} Workspace for the manipulator:

\vspace*{3in}

\subprob{E} Yes, it is possible in principle since we can convert an
$r,\theta$ pair to a unique $(x,y)$ pair. 

\subprob{F}

\end{document}


