%\documentclass{llncs}
\documentclass[11pt,onecolumn,oneside]{article}
\usepackage{llncsdoc}
\usepackage{amsfonts,stmaryrd}
\usepackage{wasysym}
\usepackage{dsfont}
\usepackage{float}
\usepackage{amssymb}
\usepackage{multirow}
\usepackage{fancyvrb}
\usepackage{wrapfig}
\usepackage{soul} %Strike through text package
\usepackage[export]{adjustbox} %figure left align
\usepackage{graphicx,subfigure}

\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{condition}[thm]{Condition}
\newtheorem{proof}[thm]{Proof}

%\setlength{\intextsep}{10pt plus 2pt minus 2pt}
\setlength{\evensidemargin}{0.05in}
\setlength{\oddsidemargin}{0.05in}
\setlength{\marginparwidth}{0.6in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.3in}
\addtolength{\parskip}{0.0 cm}

\setlength{\topmargin}{0.25in}

\begin{document}


\section{Detailed Use Case: Search and Rescue Mission}

In this section we use the example mentioned in \cite{usecase}, as a use case. 

As part of a search and rescue mission, consider an activity called SRM, in which a group of vehicles fly
together from a rendezvous point to the target search area. In this activity, the group selects a path
from the available paths for traveling to the target area, flies together along the path through a series of
way-points to the target position, and then transmits a message to the forward air controller to indicate
their arrival, while waiting until the group receives authorization to engage the target search area.

The paths available for travel to the target area are each only available for a predetermined window of
time, which is important to consider when selecting one of these paths. In addition, the timing of the
SRM activity is bound by externally imposed requirements. There are both sequential and concurrent
threads of activities during the activity.

Next we detail specific execution to demonstrate the exact operation of our proposed scheme.

Let $P_1, P_2, P_3, P_4, P_5$ and $P_6$ be the way-points of the selected path and, $P_1$ and $P_6$ be the starting and end points. Fig. \ref{Figure S1}(A) provides all the possible ways to traverse along the path from $P_1$ to $P_6$. Weights on each edge give the maximum travel time between the points. Our aim is to successfully execute the mission with best possible traversing path without violating the network's constraints. The constraints on the path needs to be monitored online to ensure the mission will be achieved without any undesired behavior. The system will be given with temporal patterns.

\begin{figure}[htb!]
  \centering
      \includegraphics [width=15cm] {Figure S1.pdf}
      \caption{Preprocessing phase of a temporal pattern graph $G(TP)$}
  \label{Figure S1}
\end{figure}
%
%\begin{figure}[htb!]
%  \centering
%      \includegraphics [width=15cm] {Figure S2.pdf}
%      \caption{Temporal pattern graph $G(TP)$ with 0-edges}
%  \label{Figure S2}
%\end{figure}
%
%\begin{figure}[htb!]
%  \centering
%      \includegraphics [width=15cm] {Figure S3.pdf}
%      \caption{Preprocessing phase of graph $G(TP)$ with 0-edges}
%  \label{Figure S3}
%\end{figure}
%
%\begin{figure}[htb!]
%  \centering
%      \includegraphics [width=15cm] {Figure S4.pdf}
%      \caption{Result of temporal  pattern graph $G(TP)$ after preprocessing phase}
%  \label{Figure S4}
%\end{figure}

A Temporal Pattern $TP$ is a tuple $(A, C)$ is represented by a pattern graph $G(TP)$. Where $A = (P_1, P_2, ... , P_n)$ is a sequence of typed events and $C$ is a set of temporal constraints, such that each $c \in C$ is a tuple $(P_i, P_j,\omega)$, where the time interval between the events $Pi$ and $Pj$ is at most $\omega$. The events in $A$ define the graph nodes, and the constraints in $C$ define edges. A constraint $e = (P_i, P_j, \omega)$ where $i < j$ is a directed edge from $Pi$ to $Pj$ with weight $\omega$. If there is no constraint between $P_i$ and $P{i+1}$ for some $I$, we define an edge $(P_i, P_j, \infty)$, where $\infty$ signifies that any finite time may pass between $P_i$ and $P_{i+1}$. An edge between consecutive events is a simple edge $(Ex: P3 \longrightarrow P4)$ and any other edge is an over-passing edge $(Ex: P3 \longrightarrow P5s)$.

A token represents a sub-sequence of the execution, partially matching the temporal pattern. An algorithm is proposed to detect sporadic pattern matches and discard a token at the very first constraint check after it becomes obsolete. A preprocessing phase and an on-line detection phase are the two phases of the pattern detection paradigm. The preprocessing phase will yield an equivalent temporal pattern in a more restrictive form. Implementation of a preprocessing phase of pattern constraints is illustrated in Fig. \ref{Figure S1}. Here, the pattern constraint set is reduced to the minimum while maintain the temporal constraint semantics. We compute the shortest path from $P_i$ to $P_j$ for $1 < i < n-1$ and $i+1 < j < n$. Then we update $G$ by removing over-passing edges and update the weight of every edge to be the weight of the shortest path between its ends.

The on-line detection phase will utilize a many-state automaton to keep track during the system's
operation of execution sub-sequences partially matching a pattern. Two approaches namely, Deadline
scheme and History scheme are introduced for monitoring patterns online.

In deadline scheme, every token $tkn$ is associated with a minimum heap and a dynamic hash table. If $tkn$
resides on an event $P_i$ and the next chronological event in the pattern $P_{i+1}$ occurs at time $t$, we first check $tkn$ against the simple edge $(P_i, P_{i+1})$. If the constraint does not hold, $tkn$ is discarded from the automaton whose states are the pattern events. At any given time in the execution, an event may hold several tokens.

Let us assume we have three tokens $T_1$, $T_2$ and $T_3$ are on the given temporal pattern. Let the sub-
sequences of these tokens be $P_1 \longrightarrow P_2 \longrightarrow P_3$, $P_1 \longrightarrow P_3 \longrightarrow P_4 \longrightarrow P_5$ and $P_3 \longrightarrow P_5 \longrightarrow P_6$ respectively. To avoid missing a possible pattern match, we handle the tokens by the events they are on, from late to early
(reason for this is as follows: Say we have tokens on events $P_1$ and $P_2$, and the type of events $P_2$ and $P_3$ is $t_1$. If $t_1$ type event occurs then we handle the token on $P_1$ first, it will discard the token on $P_2$, although that token may spawn a token on $P_3$). This will ensure the detection of temporal pattern in the first instance during an execution.

In the history scheme, we may simply keep a history of the time points when a token reaches events,
and each time a token is spawned on an event, we compare the history with temporal constraints of
over-passing edges whose destinations are the current event. If it matches, the token will be executed or
otherwise discard.

It is discussed in the manuscript with calculations and an example that, the deadline scheme will be
efficient in case if the pattern graph has less number of over-passed edges or otherwise history scheme is
effective.


\begin{thebibliography}{10}
%23
\bibitem{usecase}
Phil Kim, Brian C. Williams and Mark Abramson:
Executing Reactive, Model-based Programs through Graph-based Temporal Planning, in {\it{Proceedings of the 17th international joint conference on Artificial intelligence}}, (1) (2001) 487-493.
\end{thebibliography}
\end{document} 
