\documentclass{beamer}
\setbeamertemplate{navigation symbols}{}

\usetheme{Montpellier}

\beamersetuncovermixins{\opaqueness<1>{25}}{\opaqueness<2->{15}}
\begin{document}
\title{Dynamic Networks: Robots, Agents, and Topology Manipulation}  
\author{David Ko}
\date{\today} 
\begin{frame}
\titlepage
\end{frame}

\begin{frame} \frametitle{Table of Contents}\tableofcontents
\end{frame}

\section{Mobile Agents}
\begin{frame}
\frametitle{What is a mobile agent?}
\begin{enumerate}
\item Special case of a general "software agent"
	\begin{itemize}
	\item A piece of software
	\item Autonomous
	\item Intellegent
	\item Acts "on behalf of" agency or other entity
	\end{itemize} \pause
\item Mobile agents are mobile: The code can migrate itself and portions of its execution state to other physical locations. \pause
\item Mobile agents operate out of agencies. Agencies are software platforms that provide services and an execution environment to mobile agents.
\end{enumerate}
\end{frame}

\begin{frame}
\frametitle{Agency Overview}
\begin{figure}
\includegraphics[width=3in]{images/agency_overview.png}
\caption{Agency Overview}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Why use mobile agents?}
Some commonly cited reasons to use the mobile-agent paradigm of computation: (from Wikipedia)
\begin{itemize}
\item Reduce network load: Processing on data may be done in place, rather than collecting data at a central location. \pause
\item Parallel processing: Multiple agents may cooperate operating on different hosts. \pause
\item Dynamic adaptation: Agents may choose actions dependent on the state of their current host. \pause
\item Tolerant to network faults: Able to operate in a network with fluctuating connectivity. \pause
\item Flexible Maintenance: To change an agent's actions, only one copy of source must be updated as opposed to each computational host which may host the agency.
\end{itemize}
\end{frame}

\subsection{Example Usage}
\begin{frame}
\frametitle{Data processing example}
Traditional data allocation method: 

\includegraphics[height=3in]{images/network.png}
\end{frame}
\begin{frame}
\frametitle{Data processing example}
Traditional data allocation method:

\includegraphics[height=3in]{images/agent_animation__download/frame1.png}
\end{frame}
\begin{frame}
\frametitle{Data processing example}
Traditional data allocation method:

\includegraphics[height=3in]{images/agent_animation__download/frame2.png}
\end{frame}
\begin{frame}
\frametitle{Data processing example}
Traditional data allocation method:

\includegraphics[height=3in]{images/agent_animation__download/frame3.png}
\end{frame}

\begin{frame}
\frametitle{Data processing example}
Agent based method:

\includegraphics[height=3in]{images/network.png}
\end{frame}
\begin{frame}
\frametitle{Data processing example}
Agent based method:

\includegraphics[height=3in]{images/agent_animation/frame1.png}
\end{frame}
\begin{frame}
\frametitle{Data processing example}
Agent based method:

\includegraphics[height=3in]{images/agent_animation/frame2.png}
\end{frame}
\begin{frame}
\frametitle{Data processing example}
Agent based method:

\includegraphics[height=3in]{images/agent_animation/frame3.png}
\end{frame}
\begin{frame}
\frametitle{Data processing example}
Agent based method:

\includegraphics[height=3in]{images/agent_animation/frame4.png}
\end{frame}
\begin{frame}
\frametitle{Data processing example}
Agent based method:

\includegraphics[height=3in]{images/agent_animation/frame5.png}
\end{frame}

\begin{frame}
\frametitle{Why use mobile agents?}
Mobile agents are being used and/or researched for use in the following fields:
\begin{itemize}
\item Telecom industry \pause
\item Manufacturing \pause
\item Mapping \pause
\item Data Mining \pause
\item Autonomous mobile robotics
\end{itemize}
\end{frame}

\subsection{Agency Platforms}
\subsubsection{JADE}

\begin{frame} 
\frametitle{Java Agent Development Framework (JADE) }
\begin{itemize}
\item Ported to mobile phones, palmtops, ... anything that supports Java. \pause
\item Agent programming paradigm is based on ``behaviours''. \pause
	\begin{itemize}
	\item Each agent typically has at least one behaviour. \pause
	\item Each agent may supports complex extendable behaviours which may run in parallel. \pause
	\item Behaviours may be triggered by events (receipt of a message, for example), they may be cyclic, or customized by the programmer. 
	\end{itemize} \pause
\item Uses a centralized agency communication scheme. A single agency is
designated the main container. All other containers communicate with the main
one. \pause
\item Designed for application level agent interaction and communication. \pause
\item Compliant with the Foundation for Intellegent Physical Agents (FIPA). (More on this later)
\end{itemize}
\end{frame}

\subsubsection{Mobile-C}

\begin{frame}
\frametitle{Mobile-C}
\begin{itemize}
\item Mobile-C is an agency platform developed at the Integration Engineering Laboratory at UC Davis. \pause
\item Mobile-C supports C/C++ agents. \pause
\item Mobile-C is designed to be \pause
	\begin{itemize}
	\item Lightweight \pause
	\item Low level \pause
	\item Interpretive 
	\end{itemize}\pause
\item Ported to major operating systems and architectures, including the ARM architecture for tiny computers. \pause
\item Agent programming paradigm is functional, in the C language. \pause
\item Like JADE, Mobile-C is also compliant with FIPA standards.
\end{itemize}
\end{frame}

\subsubsection {FIPA}
\begin{frame}
\frametitle{FIPA}
\begin{enumerate}
\item FIPA is an organization founded in the mid 90's to help formulate standards for agent communication. \pause
\item FIPA has written standards for communication message format as well as certain protocols. \pause
\item Since both Mobile-C and JADE are FIPA compliant, they may exchange messages with each other. \pause
\end{enumerate}
\end{frame}

\section{Mobile Robots and Network Topology}

\begin{frame}
\frametitle{Some of my interests}
\begin{itemize}
\item Mobile Agents. \pause
\item Autonomous mobile robots. \pause
\item Robot swarm behaviour. \pause
\end{itemize}
Some important aspects for an autonomous robot system to work:
\begin{itemize}
\item Autonomy. \pause
\item Robot Intellegence. \pause
\item Swarm Intellegence. \pause
\item Robot Cooperation. \pause
\item Fault Tolerance. \pause
	\begin{itemize}
	\item Robustness of individual robots. \pause
	\item Robustness of swarm. Must have reliable communication! 
	\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{What applications are well suited for autonomous mobile robots?}
Autonomous swarms of mobile robots are well suited to many applications including:
\begin{itemize}
\item Exploration applications. \pause
	\begin{itemize}
	\item Scientific, extra planetary, etc. \pause 
	\item Search and rescue \pause
	\item Military 
	\end{itemize}\pause
\item Data collection 
\end{itemize}\pause
In each case, robust robot communication is essential. The robot communication
network must be fault tolerant.
\end{frame}


\subsection{Preliminary work done by Basu}
\begin{frame}
\frametitle{Preliminary work done by Basu}
\begin{itemize}
\item Proposed that in order to be fault tolerant, a robot network should be biconnected. In other words, the network should contain no cut vertices.
\item Robot connectivity determined by limited communication range.
\item Robots in a robot network may physically move to ensure a biconnected network.
\item Cases presented by Basu include:
	\begin{itemize}
	\item Linear contraction case.
	\item Two dimensional contraction case.
	\item Two dimensional block movement case.
	\end{itemize}
\end{itemize}
\end{frame}

\subsubsection{Linear Contraction Case}

\begin{frame}
\frametitle{Linear Contraction Case}
Minimize
\begin{equation}
D_{total} = \sum^{N}_{i = 1} \left| x_i - p_i \right|
\end{equation}
With the following constraints:
\begin{eqnarray}
x_1 &\ge& p_1 \\
x_N &\le& p_N \\
x_i - x_{i-1} &\ge& 0,~ 2 \le i \le N \\
x_i - x_{i-2} &\le& 1,~ 3 \le i \le N 
\end{eqnarray}
\end{frame}

\subsubsection{2-D Contraction Case}
\begin{frame}
\frametitle{2-D Contraction Case}
2-D analog of the linear case.
\begin{enumerate}
\item Calculate ``center of mass'' of all robots. \pause
\item Each robot begins to move towards the center at a speed proportional to
its distance from the center. Those that are farther away move faster and vise
versa. \pause
\item Eventually, the network will become biconnected.
\end{enumerate}
\end{frame}

\subsubsection{2-D Block Movement Case}
\begin{frame}
\frametitle{2-D Block Movement Case}
\begin{enumerate}
\item Divide graph into a bipartite graph of blocks and cut vertices. \pause
\item Block with most nodes is deemed the root block. \pause
\item Other blocks move toward the root block, thereby eliminating cut vertices.
\end{enumerate}
\end{frame}

\begin{frame}
\frametitle{2-D Block Movement Case}
\begin{figure}
\includegraphics[width=3in]{images/basu_bipartite.png}
\caption{Basu's decomposition of a graph into a bipartite block tree.}
\end{figure}
\end{frame}

\subsubsection{Issues with Basu's algorithms}

\begin{frame}
\frametitle{Issues with Basu's algorithms}
\begin{itemize}
\item Requires global knowledge of network topology. \pause
\item Assumes homogenous robots in a homogenous environment. \pause
	\begin{itemize}
	\item 2-D contraction and block movement may leave edgebots behind due to speed fluctuations,
	limitations. \pause
	\end{itemize}
\item 2-D block movement still moves many bots unnecessarily. \pause
\item 2-D block movement requires flocking. Flocking is not trivial! \pause
\item Movement iteratively based on largest block. \pause
	\begin{itemize}
	\item Not only does the algorithm need to know the global topology at the
	beginning of the algorithm, it needs to recalculate it after every block
	movement.
	\end{itemize}
\end{itemize}
\end{frame}

\subsection{Localized Movement Control for Fault Tolerance of Mobile Robot Networks}

\begin{frame}
\frametitle{A Better Algorithm}
\begin{itemize}
\item Das et. al. propose a localized robot movement control algorithm to create 
fault tolerant robot networks. \pause
\item The algorithm is localized in the sense that each robot only knows/cares about
its p-hop neighbors.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{p-hop neighbors}
\begin{figure}
\includegraphics[width=3in]{images/p-hop.png}
\caption{The 2-hop network of a certain node.}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Critical Nodes}
\begin{itemize}
\item If a node is a cut vertex within its p-hop subgraph, it is considered a critical node. \pause
\item All global cut vertices will be a p-hop critical node. \pause
\item Authors state that 80\% of locally critical nodes are also globally
critical. (For p=3)
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Critical Node Availability}
\begin{itemize}
\item Authors define a critical node as being ``available'' if it has non-critical neighbors. \pause
\item Otherwise, the node is ``non-available''. \pause
\item A node is defined as a ``critical head'' if 
	\begin{itemize}
	\item It is available AND 
	\item it has the highest ID of its available critical neighbors OR it has no available critical neighbors
	\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Network Fault Cases}
The authors divide up the possible ways in which cut vertices may exist in a network into
three seperate cases.
\begin{enumerate}
\item A critical node exists with no critical neighbors. \pause
\item A critical node exists with one critical neighbor. \pause
\item A critical node exists with many critical neighbors.
\end{enumerate}
\end{frame}

\begin{frame}
\frametitle{Case 1: A Critical Node with No Critical Neighbors}
\begin{itemize}
\item Critical node chooses one node from each subgraph. \pause (What if there are more than two subgraphs?) \pause
\item Critical node commands the two selected nodes to move toward each other until they become neighbors. \pause
\item The original cut vertex is no longer a cut vertex. Topology information is shared to check 
if new critical nodes were formed. \pause
\item Iterate if there are still critical nodes remaining or if new critical nodes were created.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Case 1: A Critical Node with No Critical Neighbors}
\begin{figure}
\includegraphics[width=3in]{images/case1.png}
\caption{Node movement for a critical node with no critical neighbors.}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Case 2: A Critical Node with One Critical Neighbor}
\begin{itemize}
\item Critical nodes know about each other due to ``critical announcement packets''. \pause
\item Critical node with higher ID (aka Critical Head) takes charge. Critical node with lower ID idles. \pause
\item Critical Head divides local network into two seperate subgraphs, A and B, such that A contains the other critical node. \pause
\item Critical Head directs a non-critical node in subgraph B toward the other critical node until they become neighbors.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Case 2: A Critical Node with One Critical Neighbor}
\begin{figure}
\includegraphics[width=3in]{images/case2.png}
\caption{Node movement for a critical node with one critical neighbor.}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Case 3: A Critical Node with Many Critical Neighbors}
\begin{itemize}
\item Critical heads identify themselves. \pause
\item Critical heads choose a neighbor who is a critical node to pair with. \pause
\item Critical heads invoke the Case 2 algorithm: Move a non-critical neighbor in the non-critical subgraph towards the chosen neighbor.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Case 3: A Critical Node with Many Critical Neighbors}
\begin{figure}
\includegraphics[width=3in]{images/case3.png}
\caption{Node movement for a critical node with one critical neighbor.}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Case 3: A Critical Node with Many Critical Neighbors}
\begin{figure}
\includegraphics[width=3in]{images/case3b.png}
\caption{Node movement for a critical node with one critical neighbor.}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Case 3: A Critical Node with Many Critical Neighbors}
\begin{figure}
\includegraphics[width=3in]{images/case3c.png}
\caption{Node movement for a critical node with one critical neighbor.}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Will there always be a critical head in a non-biconnected network?}
\begin{itemize}
\item Lemma 1: There exists non-critical nodes in any connected network. \pause
\item Theorem 1: If the network is connected but not biconnected then it has a \textit{either} a critical node with no critical neighbors \textit{or} a critical head. \pause
\item Proof: \pause
	\begin{itemize}
	\item According to Lemma 1, there exist non-critical and critical nodes in the network. \pause
	\item Since the network is connected, some critical nodes must be connected to some non-critical nodes. These critical nodes are deemed ``available''. \pause
	\item The available critical node with the largest ID must be by definition a critical head.
	\end{itemize}
\end{itemize} 
\end{frame}

\begin{frame}
\frametitle{Why is this algorithm cool?}
\begin{itemize}
\item The algorithm is locally executed. It is a peer to peer algorithm, similar to early versions
of Gnutella. There is no need for global topology knowledge. \pause
\item Fixing false positive cut vertices may not be a bad thing. If a node is locally critical,
it may be worthwile to reinforce it.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Issues? Future work ideas?}
\begin{itemize}
\item Message flooding \pause
\item Message oscillation \pause
\item Each bot needs to know physical location of all its p-hop neighbors. GPS? Triangulation? \pause
\item Error handling? What if a bot can't move as directed? Will a critical bot wait forever for a node to move? \pause
\item How representative is the random initial placement of bots in the simulation to real life? In the real world, bots may be deployed from a single point. Will they ever reach a ``random'' distribution?  \pause
\item What if bots deployed from a single location approach a ring type topology? Then will every bot
think they are a critical node? Lemma 1 and Theorem 1 consider the entire network, not the p-hop subgraph!
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{New research ideas}
\begin{itemize}
\item Agents are able to migrate from bot to bot \pause
\item What if we designate a small number of agents to be independent
``leader'' agents who can intellegently move other bots around at will with no
regard for topology? What if we could migrate the leader agents to the edge of
the network? Could we then have the leader bots direct the entire network by
``dragging'' it around? Essentially, what if critical nodes \textit{are}
permitted to move?  
\end{itemize} 
\end{frame}

\begin{frame}
\frametitle{Leader Agent/Bot}
\begin{figure}
\includegraphics[width=3in]{images/leader_bot.png}
\caption{Conceptual drawing of a leader bot ``dragging'' a biconnected robot network.}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{The End}
Questions? Comments? \\

Thanks for your time!

\end{frame}
\end{document}
