\documentclass[10pt]{beamer}

\mode<presentation>
{
\usetheme{Goettingen}
\usecolortheme{seagull}
}

\setbeamercovered{transparent}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{times}
\usepackage{array}
\usepackage{color}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage[overlay,absolute]{textpos}
\usepackage{algorithm,algorithmic}
\usepackage{epsfig}
\usepackage{multirow}
\usepackage{multimedia}
\usepackage{hyperref}

% personal definition
\def\N{{\mathbb{N}}}
\def\R{{\mathbb{R}}}
\def\RD{{\mathbb{R}^2}}
\def\TD{{\mathbb{T}^2}}
\def\Z{{\mathbb{Z}}}
\def\D{{\mathcal{D}}}
\def\Div{\textup{div\,}}
\def\BV{\mathcal{BV}}
\def\S{\mathcal{S}}
\def\sinc{\textup{sinc}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}

\everymath{\displaystyle}

%==============================================================
\title[Swarm Robotics]
{Swarm Robotics}

\subtitle
{Communication and Cooperation over the Internet}

\author[]
{Will Ferenc, Hannah Kastein, Lauren Lieu, Ryan Wilson  Mentor: J\'er\^ome Gilles}

\date[UCLA AML REU 2011] 
{UCLA Applied Mathematics REU 2011}

\begin{document}

\begin{frame}
\titlepage
\end{frame}


%===============================================================
%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%

\subsection{Swarming}

\begin{frame}
\frametitle{Swarming}

\begin{textblock}{12.6}(0.5,12.5)
\begin{block}{\small Definition:}
\small Collective behavior of decentralized, self organized systems
\end{block}
\end{textblock}

\begin{center}
\includegraphics[scale=0.45]{../LabPictures/Fishes.png}\\
\tiny Credit: \copyright 2010 Bruce Avera Hunter, Courtesy of life.nbii.gov
\end{center}

\end{frame}

%===============================================================

\begin{frame}
\frametitle{Third Generation Micro-Cars}

\begin{textblock}{12}(0.5,1.8)
\includegraphics[scale=0.06]{../LabPictures/FrontCarReal.jpg}
\end{textblock}

\begin{textblock}{7.25}(5.5,1.4)
\begin{block}{}
\begin{itemize}
\item \small Short or long range IR sensor to detect barriers
\item 350 MHz FPGA for on-board processing (Upper Board)
\item 50 MHz ARM microcontroller for velocity and steering control (Lower Board)
\item Two radios for communication
\end{itemize}
\end{block}
\end{textblock}

\begin{textblock}{12.25}(0.5,11)
\begin{block}{}
\begin{itemize}
\item Program in C using Xilinx Studio
\item Communication between upper and lower boards
\begin{itemize}
	\item No shared memory and limited streaming variables
\end{itemize}
\end{itemize}
\end{block}
\end{textblock}

\end{frame}
%================================================================

\begin{frame}
\frametitle{Third Generation Micro-Cars}

\begin{textblock}{12}(0.48,2.0)
\includegraphics[scale=0.25]{../Captures/IsometricView}
\end{textblock}

\begin{textblock}{12}(6.45,1.5)
\includegraphics[scale=0.25]{../Captures/BottomView}
\end{textblock}

\begin{textblock}{12}(0.1,9.3)
\includegraphics[scale=0.25]{../Captures/SideView}
\end{textblock}

\begin{textblock}{12}(8.25,9)
Lower Board:
\begin{itemize}
\item  \small Transmit position (GPS)
\item  \small Steering control
\end{itemize}
\end{textblock}

\begin{textblock}{5}(8.25,11.5)
Upper Board:
\begin{itemize}
\item \small Intervehicle communication
\item \small GUI
\item \small Processing
\end{itemize}
\end{textblock}

\end{frame}

%===============================================================

\subsection{Testbed}

\begin{frame}
\frametitle{Testbed Communication Setup}

\begin{textblock}{12}(0.5,2)
\includegraphics[scale=0.3]{../LabPictures/testbedSetupDiagram.png}
\end{textblock}

\begin{textblock}{12}(0.5,12.3)
Lower board radio:\\
$\>\>\>\>\>\>\>\>\>$Tracking computer sends locations to individual cars\\
Upper board radio:\\
$\>\>\>\>\>\>\>\>\>$Intervehicle communication and GUI interface
\end{textblock}

\end{frame}

%================================================================

\begin{frame}
\frametitle{Tracking System (GPS)}

\begin{textblock}{18}(0.5,2)
\includegraphics[scale=0.3]{../LabPictures/GPS.jpg}
\end{textblock}

\begin{textblock}{18}(7.8,7.5)
\includegraphics[scale=0.2]{../LabPictures/carHAT.png}
\end{textblock}

\begin{textblock}{4.8}(8,1.65)
\begin{block}{}
\begin{itemize}
	\item Binary tags identify cars
	\item Thresholding
	\item Contour mapping
\end{itemize}
\end{block}
\end{textblock}

\end{frame} 

%=================================================================
%%%%%%%%%%%%%%%%%%%
\section{Communication}
%%%%%%%%%%%%%%%%%%%

\subsection{Peer to Peer 2010}

\begin{frame}
\frametitle{Peer to Peer 2010}

\begin{textblock}{18}(0.5,1.5)
\includegraphics[scale=0.38]{../LabPictures/peer2peer2010.png}
\end{textblock}

\begin{textblock}{14}(0.5,12.5)
\begin{itemize}
\item Finite state machine with token based broadcasting
\item Daisy Chain algorithm and coupling
\end{itemize}
\end{textblock}

\begin{textblock}{14}(8,17)
Encountered lossy transmission problems.
\end{textblock}

\end{frame}

%================================================================

\begin {frame}
\frametitle{Peer to Peer 2010}

\begin{textblock}{12}(0.5,2)
\begin{block}{Problems:}

\begin{itemize}

\item Encountered lossy transmission problems
\begin{itemize}
	\item Enters infinite receiving loop if header byte is lost
\end{itemize}

\item Internal clocks not synchronized
\begin{itemize}
	\item Resulted in interference between transmitted messages
\end{itemize}

\item Used overhead camera tracking broadcasts to locate peers
\begin{itemize}
	\item Limited streaming between lower and upper boards
\end{itemize}

\end{itemize}

\end{block}
\end{textblock}

\end{frame}

%================================================================

\subsection{Peer to Peer 2011}

\begin{frame}
\frametitle{Peer to Peer 2011}

\begin{textblock}{12.5}(0.5,2)
\begin{block}{Objective:}
\begin{itemize}
\item Set up a peer to peer network protocol for sharing information
\item Enable swarming algorithms to share data about the environment and cooperatively execute tasks
\end{itemize}
\end{block}
\end{textblock}

\begin{textblock}{12}(0.5,9)
\begin{itemize}
\item Rapidly updated information will compensate for lost messages
\end{itemize}
\end{textblock}

\end{frame} 

%================================================================
\begin{frame}
\frametitle{Peer to Peer 2011}

\begin{textblock}{12}(3.7,6.2)
\includegraphics[scale=0.35]{../LabPictures/clock.png}
\end{textblock}

\begin{textblock}{12.5}(0.5,1.1)
\begin{block}{\small Plan}
\begin{itemize}
\item \small Implement interrupt handlers for sending and receiving messages via upper board radio
\item Time-scheduled broadcasting for individual cars
\begin{itemize}
\item Requires clock synchronization
\end{itemize}
\end{itemize}
\end{block}
\end{textblock}

\end{frame}

%=================================================================

\begin{frame}{Peer to Peer 2011}
\frametitle{Peer to Peer 2011}

\begin{textblock}{8.75}(0.5,1.5)
\begin{block}{Message:}
\begin{tabular}{l||c}
 & Number of Bytes \\
\hline
\hline
Header & 1\\
\hline
Car ID & 1\\
\hline
X Coordinate & 2\\
\hline
Y Coordinate & 2\\
\hline
Heading & 2\\
\hline
IR Sensor Distance & 2\\
\hline
Terminator & 1\\
\hline
\hline
\textbf{Total} & \textbf{11}\\
\end{tabular}
\end{block}
\end{textblock}

\begin{textblock}{12.5}(0.5,10)
\begin{block}{}
\textbf{Broadcast:}\\
115200 bps $\longrightarrow$ 1.2 ms per broadcast $\longrightarrow$ 10.8 ms for 9 cars\\
\textbf{GPS and Lower Board Streaming:}\\
30 Hz $\longrightarrow$ takes 33.4 ms to update\\
\end{block}
\end{textblock}

\end{frame}

%================================================================

\begin{frame}
\frametitle{Peer to Peer 2011}

\begin{textblock}{18}(0.1,2.75)
\includegraphics[scale=0.37]{../LabPictures/shortTimeline.png}
\end{textblock}

\begin{textblock}{12.5}(0.5,7)
\begin{block}{Processing:}
Leave 1 ms after each send to parse and store the message
\end{block}
\end{textblock}

\begin{textblock}{12.5}(0.5,11)
\begin{block}{Calculation:}
Remaining time reserved for onboard calculations and commands to the lower board
\end{block}
\end{textblock}

\end{frame}

%================================================================

\begin{frame}
\frametitle{Peer to Peer 2011}

\begin{center}
\movie[height=5cm,width=8cm,loop]{}{../Videos/peerCarFollow_2011.avi}
\end{center}

\end{frame}

%================================================================
%%%%%%%%%%%%%%%%
\section{Algorithms}
%%%%%%%%%%%%%%%%

\subsection{Background}

\begin{frame}
\frametitle{Objectives}

\begin{textblock}{12}(0.5,2)
\begin{block}{Tasks}
\begin{itemize}
\item Follow a prescribed path
\item Dynamically avoid obstacles
\item Target search
\item Swarming/Multi-robot Algorithm
\end{itemize}
\end{block}
\end{textblock}

\begin{textblock}{12}(0.5,9)
\begin{itemize}
\item Robots have no apriori knowledge of map
\item Know the position of other robots updated through peer to peer communications
\end{itemize}
\end{textblock}

\end{frame}

%================================================================

\subsection{Path Planning}

\begin{frame}
\frametitle{Path Planning Algorithm}

\begin{textblock}{12}(0.5,1.75)
\begin{block}{Potential Field}
\begin{itemize}
\item \small Target emits attractive force.
\item Boundary and peers emit a repulsive force.
\item Car moves in the direction of the sum of all forces.
\end{itemize}
\end{block}
\end{textblock}

\begin{textblock}{12}(0.5,6.8)
\begin{equation*}
F=Q_r\left(C\frac{r_t}{\|r_t\|^2}+Q_r\sum_{i=1}^{K-1}\frac{r_i}{\|r_i\|^2}+\sum_{i=1}^LB_i\right)
\end{equation*}
\end{textblock}

\begin{textblock}{12}(0.5,9.5)
$Q_r$: car potential ($<0$)\\
$C$: target potential ($>0$)\\
$r_i$: vector from $i$-th car to current car\\
$r_t$: vector from target to current car\\
$K$: number of cars\\
$L$: number of boundary points\\
$B_i$: $i$-th boundary term\\
\end{textblock}

\end{frame}

%=================================================================

\begin{frame}
\frametitle{The Boundary Term, $B_i$:}  

\begin{textblock}{12}(6,1.5)
\includegraphics[scale=0.35]{../LabPictures/Boundary.png}
\end{textblock}

\begin{textblock}{5.25}(0.5,4)
\begin{itemize}
\item No boundary $i$ sensed within semicircle means $B_i=0$
\end{itemize}
\end{textblock}

\begin{textblock}{12}(0.5,7)
\begin{itemize}
\item Otherwise,
\end{itemize}
\begin{equation*}
B_i=B_r\left(\frac{r_B^{\perp}}{\|r_B\|^2}\right)
\end{equation*}
\end{textblock}

\begin{textblock}{12}(1.4,10.5)
where $B_r$ $<0$ is the barrier potential.
\end{textblock}

\begin{textblock}{12}(0.5,12)
\begin{itemize}
\item Perpendicular vector direction ($r_B^{\perp}$) is arbitrarily chosen.
\item Avoid scenario of all cars passing a boundary on the same side and creating a traffic jam.
\end{itemize}
\end{textblock}

\end{frame}

%================================================================

\begin{frame}
\frametitle{To go right or left $\ldots$ that is the question}

\begin{textblock}{12}(0.1,2.7)
\includegraphics[scale=0.3]{../LabPictures/Direction.png}
\end{textblock}

\begin{textblock}{6}(7,3)
\begin{itemize}
\item A line drawn between the target and the car separates the testbed into two regions.
\item $r_B^{\perp}$ is chosen to be a vector in the region that contains less cars.
\end{itemize}
\end{textblock}

\begin{textblock}{11}(1,9)
\textbf{Does it actually work?}
\end{textblock}

\begin{textblock}{12}(0.5,10)
\begin{itemize}
\item In simulations - Yes
\item In practice - 

Fit a curve to IR sensor data to estimate distance from the boundary. 
If the distance is below a threshold, the car will go perpendicular to its current heading.

\end{itemize}
\end{textblock}

\end{frame}

%=================================================================

\subsection{Swarming}

\begin{frame}
\frametitle{Swarming Algorithm}

\begin{textblock}{12}(0.5,2)
\begin{block}{}
\begin{itemize}
\item One car leads - the rest follow
\item Stay in formation without running into peers
\item Also uses the concept of a potential field
\end{itemize}
\end{block}
\end{textblock}

\end{frame}

%=================================================================

\begin{frame}
\frametitle{Morse Potential Equations}

\begin{textblock}{12}(1.5,2)
${\frac{dx_{i}}{dt} = v_{i}}$
\end{textblock}

\begin{textblock}{12}(1,4.5)
${m_{i} \frac{dv_{i}}{dt} = \left( \alpha - \beta \| v_{i} \| ^ {2} \right) v_{i} - \triangledown U \left( x_{i} \right) + \sum_{j = 1}^{N} C_{0} \left( v_{j} - v_{i} \right)}$
\end{textblock}

\begin{textblock}{12}(1.08,7)
${U \left( x_{i} \right) = \frac{1}{2}C_{l}\left(x_{i} - y\right)^{2} + \sum_{j=1}^{N} C_{r}e^{-\|x_{i} - x_{j}\|/l_{r}} - C_{a}e^{-\|x_{i} - x_{j}\|/l_{a}}}$
\end{textblock}

\begin{textblock}{12}(0,9)
\begin{tabular}{lrlrl}
 & & & & \\
 & $x_i$ &: $i$-th car's position & $C_0$ & : velocity alignment coefficient\\
 & $V_i$ & : $i$-th car's velocity & $C_l$ & : leader following coefficient\\
 & $y$ & : position of leader car & $C_r$ & : car repulsion coefficient\\
 & $N$ & : number of cars & $C_a$ & : car attraction coefficient\\
 & $\alpha$ & : self-propulsion & $l_r$ & : repulsion length\\
 & $\beta$ & : drag & $l_a$ & : attraction length\\
 & $U$ & : potential function & & \\
\end{tabular}
\end{textblock}

\end{frame}

%=================================================================

%%%%%%%%%%%%%%%%%%
\section{Collaboration}
%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Networking testbeds collaboration}

\begin{textblock}{12}(0.5,1.25)
\begin{block}{Serial communication with cars}
\begin{itemize}
\item \small Terminal Client C++
\item Terminal Synchronous Client Matlab
\item Cars communicate wirelessly, so intercepting communication with the computer does not interfere
\end{itemize}
\end{block}
\end{textblock}

\begin{textblock}{7}(0.5,7)
\begin{block}{Communication over internet}
\begin{itemize}
\item \small Requires Instrumentation Control Toolbox
\item Can send strings, integers, floating point numbers, even matrices of a known dimension
\end{itemize}
\end{block}
\end{textblock}

\begin{textblock}{7}(8,7.25)
\includegraphics[scale=0.35]{../LabPictures/plant.png}
\end{textblock}
\end{frame}

%===============================================================

\begin{frame}
\frametitle{Collaboration}

\begin{textblock}{12}(0.5,1.5)
\begin{block}{Network Communication}
\begin{itemize}
\item Problems
\begin{itemize}
	\item Firewall
	\item Latency to Cincinnati
	\item Port overuse
\end{itemize}
\item TCP/IP
\item Sucessful collaboration with UC
\end{itemize}
\end{block}
\end{textblock}

\begin{textblock}{12}(7,10)
\includegraphics[scale=0.5]{../LabPictures/cincinnati.png}
\end{textblock}

\end{frame}

%===============================================================

%%%%%%%%%%%%%%%%%
\section{Car Camera}
%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Camera}

\begin{center}
\includegraphics[scale=0.4]{../LabPictures/camera.png}
\end{center}

\end{frame}

%===============================================================

\begin{frame}
\frametitle{Hardware}

\begin{center}
\includegraphics[scale=0.48]{../LabPictures/pin1.png}
\end{center}

\end{frame}

%===============================================================

\begin{frame}
\frametitle{Camera Configuration}

\begin{textblock}{12}(0.5,2)
\begin{itemize}
\item Use the built in IP to configure the 94 registers on the camera
\item Registers to configure:
\begin{itemize}
\item FPS
\item Resolution
\item ACF (Flicker protection)
\item $\ldots$
\end{itemize}
\end{itemize}
\end{textblock}

\begin{textblock}{12}(2,10)
\includegraphics[scale=0.7]{../LabPictures/i2c.png}
\end{textblock}

\begin{textblock}{12}(8,8)
\includegraphics[scale=0.7]{../LabPictures/xilinx.png}
\end{textblock}

\end{frame}

%===============================================================

%%%%%%%%%%%%%%%%
\section{Conclusion}
%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Summary}

\begin{textblock}{12}(0.5,2)
\begin{block}{}
\begin{itemize}
\item Created a peer to peer network that can be combined with swarm algorithms
\item Implemented both a path planning and swarming algorithm
\item Collaboratively swarmed in simulation with University of Cincinnati
\end{itemize}
\end{block}
\end{textblock}

\end{frame}

%===============================================================

\begin{frame}
\frametitle{Future Work}

\begin{textblock}{12}(0.5,2)
\begin{block}{}
\begin{itemize}
\item Test more algorithms 
\item Test with more vehicles
\item Collaborate with another testbed using vehicles
\item Optimize interrupts so the onboard camera can function without conflicting with peer to peer
\end{itemize}
\end{block}
\end{textblock}

\end{frame}

%===============================================================

\begin{frame}
\frametitle{Acknowledgements}

\begin{textblock}{12}(0.5,2)

Rick Huang\\
\vspace{2mm}
J\'er\^ome Gilles\\
\vspace{2mm}
Andrea Bertozzi\\
\vspace{2mm}
Yasser Taima\\
\vspace{2mm}
UCLA Mathematics Computer Consulting Office (Bugs)\\
\vspace{2mm}
University of Cincinnati Cooperative Distributed Systems Lab:\\
$\>\>\>\>$Manish Kumar, Balaji Sharma\\
$\>\>\>\>$Tim Arnett, Kevin McClellan, and Kaitlyn Fleming

\end{textblock}

\end{frame}

%===============================================================

\begin{frame}
\frametitle{References}

\begin{textblock}{12}(0.5,2.5)
\tiny Y.R. Huang. ''Anteros Labs Micro-Car User Manual,'' Private Distribution, 2010.\\
\vspace{2mm}

 M. Gonzalez, X. Huang, D.S. Martinez, C.H. Hsieh, Y.R. Huang. ''A Third Generation Micro-Vehicle Testbed for Cooperative Control and Sensing Strategies,'' International Conference on Informatics in Control, Automation and Robotics (ICINCO), 2011.\\
\vspace{2mm}

A. Turan, S. Bogosyan, M. Gokasan. ''Development of a Client-Server Communication Method for Matlab/ Simulink Based Remote Robotics Experiments,'' 2006 IEEE International Symposium on Industrial Electronics.\\
\vspace{2mm}
W. Liu, Y.E. Taima, M.B. Short and A.L. Bertozzi, Multi-scale Collaborative Searching and Swarming, in the Proceedings of the 7th International Conference on Informatics in Control, Automation, and Robotics (ICINCO), Madeira, Portugal, June 2010.\\
\vspace{2mm}

B.Q. Nguyen, Y.L. Chuang, D. Tung, C. Hsieh, Z. Jin, L. Shi, D. Marthaler, A. Bertozzi, and R.M. Murray. ''Virtual Attractive-Repulsive Potentials for Cooperative Control of Second Order Dynamic Vehicles on the Caltech MVWT.'' American Control Conference, 2005, pp. 1084-1089.\\
\end{textblock}

\end{frame}

%===============================================================

\begin{frame}

\begin{center}
\Large Questions?
\end{center}
\end{frame}

%===============================================================

\end{document}