\documentclass[journal]{IEEEtran}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{makeidx}
\usepackage{graphicx}
\usepackage{booktabs}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{url}
\usepackage{color}
\usepackage{url}
\usepackage{color}
\newcommand{\eat}[1]{}
\newenvironment{definition}[1][Definition]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\begin{document}
\title{A Modern Chase Algorithm}
\author{Piyush~Kaushik,
Shrisha~Rao,~\IEEEmembership{Member, IEEE}, %
\thanks{S. Rao is with the International Institute of Information Technology}
}
\markboth{IEEE Systems Journal}%
{Kaushik \MakeLowercase{\textit{et al.}}: Comparison of Bouguer's Ship Analysis}%
\maketitle
\begin{abstract}
Pursuit and evasion tends to be incorporated in human nature from a very long time with a very huge range of activities. Here, we are going to create an intelligent chase algorithm, which uses two basic approaches. After which we will use the newly created equations to simulate both approaches and provide graphical results. This analysis is based upon the fact that in modern days we can estimate the speed of a moving object and then chase it down depending upon its speed. We will also be taking the accuracy of such estimation in picture and depending upon a certain accuracy and other inputs the simulation will provide the result and performance of both the approaches.
\end{abstract}
\begin{IEEEkeywords}
Pursuit-Evasion, Escape-Chase, pursuit graphs, speed estimation, chase algorithm.
\end{IEEEkeywords}
\section{Introduction}
\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.6]{1.JPG}
\caption{Classic Ship Analysis}\label{Saturation}
\end{center}
\end{figure}
The above figure is the basis of Pierre Bouguer's pirate ship analysis. It was one for the very first analysis in the field of pursuit-evasion. In this, Bouguer considered a pirate ship chasing down a merchant ship.\cite{bogdan2009pursuit} Here, at time t = 0, there is a pirate ship at (0,0) which is chasing down a merchant ship at $x_{0}$ distance. The speed of both ships is $v_{p}$ and $v_{m}$ respectively and any given time the pirate ship moves towards the merchant ships position only. Thus a tangent at the path of pirate ship will always meet the merchant ship. At time t if the pirate ship is at (x,y) then the equation of y(x) can be calculated as,\cite{nahin2012chases}
\begin{equation}\label{xx}
\begin{split}
y(x)& = (n/(1-n^{2})) * x_{0} + [1/2 * (x_{0}-x)]*\\
& [(1-(x-x/x_{0})^{n}/(1+n) - (1-x/x_{0})^{-n}/(1-n)]\\
& n = v_{m}/v_{p}
\end{split}
\end{equation}
Here, differential model of pursuit evasion is used to fetch a saddle equilibrium and generate the capture point if exists. But the issue with differential pursuit evasion is that there might be more than one method possible to solve the problem. It involves the determination of optimal strategies. There are few concerns with the above equation, first is, it assumes that pirate ship is situated perpendicular to the motion of merchant ship which might not always be possible and second is that it doesn't address the possibility of both ships having different starting Y-axis co-ordinates. Another issue is with the rule of pursuit which is being followed is optimal or not. As we know in modern days, there is speed estimation technology exists for ships as well as other pursuers.\cite{liu2012ship} So we will be creating new derivations to accommodate these concerns and provide an analysis for which of the two approaches is going to result in better outcome, given certain inputs.\\
There has been some work in the field of creating and simulating a chase as \cite{katsev2011mapping}
analyzes a simple robot with local sensors that moves in an unknown polygonal environment. The robot can execute wall-following motions and can traverse the interior of the environment only when following parallel to an edge. Also \cite{warren2010perceiving} a virtual avatar is programmed to pursue or evade the participant in an ambulatory virtual environment. Both of these researches have been highly useful in the robotics and self driven chases. But when it comes to implementation for mobile devices or machines with less processing power, they prove to be less practical. So here we are proposing a simple yet powerful chase algorithm, which will take Bouguer's analysis as basis implement modern estimation approach in it as well.
\section{Theory and Concept}
To create an efficient model, we need to take every case into our consideration that might occur during a chase, be it angular or linear deviation or both. Now, in our model we are using two basic approaches of chase-\\
\\
\ 1. When pursuer is always moving towards the evader. In this case, if at any point of time if we construct a tangent across the path of pursuer then it will definitely concatenate evader's position at that moment.\\This approach is named traditional, as it follows the traditional concept of moving towards your goal.
\\
\\
\ 2. Whereas in a more modern approach, the pursuer moves towards the point where he thinks the evader will be at the time he will reach there.\\ In other words, the pursuer tries to guess the speed of evader then determine a capture point and move towards it.\\
\\
Both of the two approaches are efficient for a chase, and it is obvious that if the pursuer is able to determine the speed of evader accurately, then the modern approach is always going to be the better of the both. But it is not the case as we have already discussed $\delta$. So depending upon the value of delta anyone of the above two approaches may be better than the other.\\\\
In our model, we have created an intelligent chase algorithm which will consider both the approaches at any given situation and then it will determine which one to use. The results generated from such hybrid method are more efficient than both the above pure methods.\\
\subsection{Terminology}
\subsubsection*{Pursuer}
At any given point of time, the coordinates of pursuer will be stored as $(x_{p},y_{p})$, $\vec v_{p}$ is the velocity and the magnitude of his speed will be as $v_{p}$.\\
\subsubsection*{Evader}
Similarly, At any given point of time, the coordinates of evader will be stored as $(x_{e},y_{e})$, $\vec v_{e}$ is the velocity and the magnitude of his speed will be as $v_{e}$.\\
\subsubsection*{Other}
$(x_{s},y_{s})$ is going to be the final capture point for the given situation, and $n = v_{e}/v_{p}$ is the speed ratio of pursuer and evader, $\delta$ is the inaccuracy by which pursuer is determining the speed of evader.
\subsection{Traditional Approach}
As discussed above, the tradition pursuit analysis gives us the result based upon the concept that initially the pursuer is at (0,0) and evader is at $(0,x_{m})$. But that might not be the usual case,
\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.5]{2.JPG}
\caption{A more Generic situation}\label{Saturation}
\end{center}
\end{figure}
As seen in the fig.2, Initially the pirate ship is considered at $(x_{p},y_{p})$ and the merchant ship is at $(x_{e},y_{e})$ with speeds $v_{p} and v_{e}$.
Now the new equation for such scenario will be
\begin{equation}\label{xx}
\begin{split}
y(x)& = (n/(1-n^{2})) * (x_{e}-x_{p}) + [1/2 * (x_{e}-x_{p}-x)]*\\
& [(1-(x-x_{p})/(x_{e}-x_{p}))^{n}/(1+n) - \\
& (1-(x-x_{p})/(x_{e}-x_{p}))^{-n}/(1-n)]\\
\end{split}
\end{equation}
\subsubsection{Distance Deviation}
It is not compulsory for both the pursuer and evader to be in same line, i.e. $y_{e}=y_{p}=y_{'}$. We can compute the capture point for such case by reverse engineering the traditional formula.
\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.6]{3.JPG}
\caption{Distance Deviation}\label{Saturation}
\end{center}
\end{figure}
Here in fig.3 we know that when evader is at $(x_{e},y_{e})$ and pursuer is at $(x_{p},y^{p})$ then we need to get the value of $x_{c}$ in the graph and after that we will get the hypothetical starting position, which in turn can be used to calculate the capture point.
\begin{equation}\label{xx}
\begin{split}
y_{p}& = y_{c} + (n/(1-n^{2})) * (x_{e}-x_{c}) + [1/2 * (x_{e}-x_{c}-x_{p})]*\\
& [(1-(x_{p}-x_{c})/(x_{e}-x_{c}))^{n}/(1+n) - \\
& (1-(x_{p}-x_{c})/(x_{e}-x_{c}))^{-n}/(1-n)]\\
\end{split}
\end{equation}
here $(x_{c},y_{c})$ can be estimated, after which we can calculate the capture point for such case.
\subsubsection{Angular Deviation}
Apart from linear variation, there might be some angular deviation followed by merchant ship.
\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.6]{4.JPG}
\caption{Angular Deviation}\label{Saturation}
\end{center}
\end{figure}
As shown in the fig.4 there is a variation of $\theta$. This situation can be solved by using the rotation of the axis w.r.t (0,0). The co-ordinates for any point P(x,y) will be
\begin{equation}\label{xx}
\begin{split}
x^{'}& = x * \cos\theta + y * \sin\theta \\
y^{'}& = -x * \sin\theta + y * \cos\theta \\
\end{split}
\end{equation}
Then we will use the same equations (1 and 2) to get the capture point, and then convert the co-ordinates back to the original axis.
\subsection{Modern Approach}
In this, the chaser is aware of the speed of target, with certain accuracy. In the traditional example of pirate ship analysis, the pursuers will always be aware of the speed of merchant ship $v_{e}$ with inaccuracy of $\delta$\\
Using the above information, the pursuer can calculate the nearest capture point and move towards it in linear shortest path motion.
\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.6]{5.JPG}
\caption{Modern Approach}\label{Saturation}
\end{center}
\end{figure}
Here in fig.5, $(x_{e},y_{s})$ is the capture point which can be generated as,\\
Case-1. $\delta$ = 0\\
In this case $\delta$ = 0, means the pursuer is able to measure the speed accurately.
\begin{equation}\label{xx}
\begin{split}
(y_{s}-y_{e})/v_{e}& = ((x_{e} - x_{p})^{2} + (y_{s} - y_{p})^{2})^{1/2}/v_{p}\\
\end{split}
\end{equation}
The only unknown in the above equation is $y_{s}$, and it can be solved as a quadratic equation. Out of which one solution will be $(<y_{p})$ which can be ignored.\\
Case-2. $\delta_{i}$ is positive\\
In such case, the measured speed will be more than the actual speed of merchant ship. So the pirate ship will reach the capture point earlier than the merchant ship and it has to move towards merchant ship for some time.\\
Here the measured speed of merchant ship = $v_{e}$\\
and actual speed is $v_{e} - \delta_{i}*v_{e}$\\
So the total time here,\\
\begin{equation}\label{xx}
\begin{split}
(y_{s}-y_{e})/v_{e} + ((y_{s}-y_{e})/v_{e})* \delta_{i}*v_{e} * (v_{p} + v_{e} - \delta_{i}*v_{e})\\
\end{split}
\end{equation}
Case-3. $\delta_{i}$ is negative\\
Similarly as above case, after reaching the capture point, the pirate ship has to trail behind merchant ship.
\\
Here the measured speed of merchant ship = $v_{e}$\\
and actual speed is $v_{e} + \delta_{i}*v_{e}$\\
So the total time here,\\
\begin{equation}\label{xx}
\begin{split}
(y_{s}-y_{e})/v_{e} + ((y_{s}-y_{p})/v_{e})* \delta_{i}*v_{e} * (v_{p} - v_{e} - \delta_{i}*v_{e})\\
\end{split}
\end{equation}
\textit{Distance Deviation} in this approach won't require any special calculation, similarly \textit{Angular Deviation} can be handled by the same axis rotation method.
\section{Model}
\subsection{Basic Algorithm}
A basic algorithm, is the one that follows any one of the two approaches throughout the scenario. Which means that if it is set for the traditional approach then it will keep on following that until we have reached the capture point. Another assumption that is taken into consideration is that in the case of such basic algorithm, we are taking "delta" as zero when following the modern method. Which means that pursuer is accurately able to determine the speed of evader.\\
\subsubsection*{Inputs} $(x_{p},y_{p}), (x_{e},y_{e}), v_{p}, v_{e}, \theta$ at t=0 (Starting Values)\\
\subsubsection*{Stack} The stack is something which is going to play a pivotal role, it is going to reflect the changes in evader's speed and angle over the period of time. Each entry in the stack can be considered as $t_{d}$ (Time when the deviation occurs), $ang_{d}$ (angular deviation), $vel_{d}$ (velocity deviation). The stack can be considered as the part of the input, if there is a smart algorithm which is written by the perspective of evader then there is going to be no need to keep the stack values as they will be automatically generated from the evader algorithm.\\
\subsubsection*{Output} $(x_{s},y_{s}), T$ (Total time taken in the chase).\\
\begin{algorithm}
\caption{Basic Algorithm}\label{basic}
\begin{algorithmic}[1]
\State\textit{Initialize $\theta$ and } $t \gets 0$
\While{\textit{$(x_{p},y_{p}) != (x_{e},y_{e})$ }}
\If {$y_{p} = y_{e}$}
\State $e_{q} \gets NO DEV$
\Else
\State $e_{q} \gets DEV$
\EndIf
\If{\textit{Stack.top = null}}
\State $capture(e_{q}, (x_{p},y_{p}), (x_{e},y_{e}), \theta, t, v_{p}, v_{e})$
\State $return(t,(x_{p},y_{p}))$
\Else
\If{$Stack.top(t_{d}) = t $}
\State $move(e_{q}, (x_{p},y_{p}), (x_{e},y_{e}), \theta, t, v_{p}, v_{e}, ang_{d}, vel_{d})$
\State $Stack.pop()$
\Else
\State $move(e_{q}, (x_{p},y_{p}), (x_{e},y_{e}), \theta, t, v_{p}, v_{e}, 0, 0)$
\EndIf
\EndIf
\State $t++$
\EndWhile
\State \Return $(x_{p},y_{p}), t$
\end{algorithmic}
\end{algorithm}
Here, once we have provided the valid inputs to the above algorithm, it runs the while loop until both evader and pursuer have not met. In the loop we are using a variable $e_{q}$ which determines whether there is any distance deviation or not. It simply acts as a flag.\\
There are two different functions used in the above algorithm,\\
\subsubsection*{1.Move} Used to move both the pursuer and evader in their direction at a distance of unit time quantum.\\
\subsubsection*{2.Capture} Used to finish the algorithm, if there are no more runtime deviations and returns the capture point as well as total time taken.\\
\\
Algorithm 3, details about the capture function, it applies the previous equations, based upon the requirement. Move function follows the same conditions, with a little change that instead of finishing the whole chase, it return the values of $(x_{p},y_{p}), (x_{e},y_{e})$ after one time quantum only.\\
\begin{algorithm}
\caption{Move$(e_{q}, (x_{p},y_{p}), (x_{e},y_{e}), \theta, t, v_{p}, v_{e}, ang_{d}, vel_{d})$}
\begin{algorithmic}[1]
\State\textit{Update $v_{e} \gets v_{e} + vel_{d}$}
\State\textit{$\theta \gets \theta + ang_{d}$}
\State\textit{return $(x_{p},y_{p}), (x_{e},y_{e})$ with single quantam movement.}
\end{algorithmic}
\end{algorithm}
\\
\begin{algorithm}
\caption{Capture$(e_{q}, (x_{p},y_{p}), (x_{e},y_{e}), \theta, t, v_{p}, v_{e})$}
\begin{algorithmic}[1]
\If {$\theta = 0$}
\State\textit{No angular deviation}
\If{$ e_{q} = 0 $}
\State\textit{No distance deviation either.}
\State\textit{Use eq.2 and return $(x_{p},y_{p})$}
\Else
\State\textit{Distance deviation exists.}
\State\textit{Use eq.3 and return $(x_{p},y_{p})$}
\EndIf
\Else
\State\textit{Angular deviation exists}
\State\textit{Use eq.4 to rotate axis over $\theta$}
\If{$ e_{q} = 0 $}
\State\textit{No distance deviation either.}
\State\textit{Use eq.2 and rotate axis back.}
\State\textit{return $(x_{p},y_{p})$}
\Else
\State\textit{Distance deviation exists.}
\State\textit{Use eq.3 and rotate axis back.}
\State\textit{return $(x_{p},y_{p})$}
\EndIf
\EndIf
\end{algorithmic}
\end{algorithm}
The difference between these two functions is that, if there are no more deviations in the speed or angle of evader in future then it is better to finish the algorithm. Whereas on the other hand if there are some future deviations then we must only move towards the next coordinates.\\
\\ Now using above functions, algorithm first checks which one of the previous equations is applicable in existing situation broadly basic or deviation the rest of the classification is taken care inside move and capture functions. Once equation type is determined, it checks if the stack is empty. If true that means, there are no further deviations in the future and we can simply call the capture function and finish algorithm. Else it checks whether the current time is same as the time on which deviation is supposed to happen and depending upon that it calls the move function with certain parameters.
\subsection{Delta}
As discussed earlier, if pursuer is able to determine the speed of evader accurately then all we need is basic algorithm only which is going to run on modern approach. But that can't be normal case, there must always be some inaccuracy, it has been observed that even in latest radar speed estimations there is some inaccuracies.\cite{tunaley2003estimation}\cite{shang2010low}\\
Here we will be using two different values of delta-\\
\subsubsection{$\delta_{p}$} This value is calculated with time and is known to the pursuer as his existing inaccuracy.\\
\subsubsection{$\delta_{i}$} Inaccuracy associated with ith iteration in stack.\\
\begin{equation}
\delta_{p} = \delta_{p} + |\delta_{i}|/(i+1)
\end{equation}
\subsection{Hybrid Algorithm}
For these reason, there is a requirement of a hybrid algorithm which incorporates best of both methods. This algorithm compares both methods at each iteration and then pick the one which is best suitable for current values. It also keep on updating $\delta_{p}$ with each iteration.\\
This algorithm is almost similar to basic algorithm with a few changes-\\\\
1. There is a $\delta_{i}$ associated with each iteration of stack, which is unknown to pursuer until $t<=t_{d}$\\\\
2. There is a new function named compare, which actually takes both derivations of basic algorithms and runs them on the input. After which it provides which algorithm is better suited for current case.\\\\
3. There is a new variable called algo, which is used to hold the information or output of compare function.\\\\
\begin{algorithm}
\caption{Hybrid Algorithm}\label{hybrid}
\begin{algorithmic}[1]
\State\textit{Initialize $\theta$, $\delta_{p}$ and } $t \gets 0$
\While{\textit{$(x_{p},y_{p}) != (x_{e},y_{e})$ }}
\If {$y_{p} = y_{e}$}
\State $e_{q} = BASIC$
\Else
\State $e_{q} = DEV$
\EndIf
\State $compare(e_{q}, (x_{p},y_{p}), (x_{e},y_{e}), \theta, t, v_{p}, v_{e}, 0, 0)$
\State\textit{Set algo}
\If{\textit{Stack.top = null}}
\State $capture(algo, e_{q}, (x_{p},y_{p}), (x_{e},y_{e}), \theta, t, v_{p}, v_{e})$
\State $return(t,(x_{p},y_{p}))$
\Else
\If{$Stack.top(t_{d}) = t $}
\State $compare(e_{q}, (x_{p},y_{p}), (x_{e},y_{e}), \theta,t, v_{p}, v_{e},$ \State $ ang_{d}, vel_{d})$
\State\textit{Set algo}
\State $move(algo, e_{q}, (x_{p},y_{p}), (x_{e},y_{e}), \theta, t, v_{p}, v_{e},$ \State $ ang_{d}, vel_{d})$
\State $Stack.pop()$
\State\textit{Update $\delta_{p}$}
\Else
\State $move(algo, e_{q}, (x_{p},y_{p}), (x_{e},y_{e}), \theta, t, v_{p}, v_{e}, 0, 0)$
\EndIf
\EndIf
\State $t++$
\EndWhile
\State \Return $(x_{p},y_{p}), t$
\end{algorithmic}
\end{algorithm}
\subsection*{Complexity}
The complexity of both hybrid and basic algorithm, depends upon the iterations stored in the stack. If the input stack is empty, i.e. the speed and angle of evader is going to stay same through out the chase then capture point and total time can be calculated by using previous derived equations in a single step.\\
On the other hand, when there are some entries in stack, then the algorithm is going to run one time quantum at a time until the stack is empty.
\begin{itemize}
\item Best Case- O(1), Stack is empty.
\item Worst case- O(MAX($t_{d}$)), where MAX($t_{d}$) is the time associated with the last iteration stored in stack.
\end{itemize}
Here as similar to the basic algorithm, we can see that first the equation type is determined in current situation. Once done, a compare function is called and value of $algo$ variable is set. This value is going to change only if there is some iteration on the top of stack for $t=t_{d}$. In such case compare function is called again, this time with the values of stack as well and accordingly $algo$ is set again.\\
After which move or capture functions are called, depending upon the situation.\\
\section{Future work}
Both the algorithms have been implemented in C++ and are working perfectly.
1. As suggested, I am trying to implement these algorithms in higher dimensions.\\
2. I am also working upon creating an android chase game which will use the hybrid algorithm.\\
3. Obstacles can also be introduced with following types-
\subsubsection{•} Avoidable- These obstacles will only change the speeds of pursuers and evaders without changing their paths.\\
\subsubsection{•} Unavoidable- These obstacles will effect both speed and directions of agents.\\
\subsubsection{•} Application in mobile gaming as an intelligent chase algorithm.\\
\section{Conclusion}
Here, we have used one of the first pursuit-evasion equation and used it to derive a new modern chase algorithm. Which can be highly useful to provide basic chase intelligence in devices with processing constraints.
\bibliographystyle{IEEEtran}
\begin{thebibliography}{100} % 100 is a random guess
\bibitem{nahin2012chases} Nahin, Paul J. Chases and escapes: the mathematics of pursuit and evasion. Princeton University Press, 2012.
\bibitem{warren2010perceiving}Warren, William, and Jonathan Cohen. "Perceiving pursuit and evasion by a virtual avatar." Journal of Vision 10, no. 7 (2010): 1041-1041.
\bibitem{katsev2011mapping} Katsev, Max, Anna Yershova, Benjamin Tovar, Robert Ghrist, and Steven M. LaValle. "Mapping and pursuit-evasion strategies for a simple wall-following robot." Robotics, IEEE Transactions on 27, no. 1 (2011): 113-128.
\bibitem{liu2012ship} Liu, F., F. Zhao, W. Yu, L. Shi, and R. Wang. "Ship detection and speed estimation based on azimuth scanning mode of synthetic aperture radar." Radar, Sonar |\& Navigation, IET 6, no. 6 (2012): 425-431.
\bibitem{tunaley2003estimation} Tunaley, James KE. "The estimation of ship velocity from SAR imagery." In Geoscience and Remote Sensing Symposium, 2003. IGARSS'03. Proceedings. 2003 IEEE International, vol. 1, pp. 191-193. IEEE, 2003.
\bibitem{shang2010low} Shang, Shang, and Zhang Ning. "Low speed target detection with short CIT in HF surface wave radar." In Signal Processing Systems (ICSPS), 2010 2nd International Conference on, vol. 2, pp. V2-499. IEEE, 2010.
\bibitem{blinn2005solve} Blinn, James F. "How to solve a quadratic equation." IEEE computer graphics and applications 25, no. 6 (2005): 76-79.
\end{thebibliography}
\end{document}
