text:
\subsubsection*{References}}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage[linesnumbered,ruled]{algorithm2e}

\usepackage[a-2u]{pdfx}
\begin{filecontents}{klaska_195.xmpdata}
\Author{David Kla\v ska and Antonn Ku\v cera and V\'it Musil and Vojt\v ech {\v R}eh\'ak}
\Title{Regstar: Efficient Strategy Synthesis for Adversarial Patrolling Games}
\Subject{Proceedings of Conference on Uncertainty in Artificial Intelligence, 2021}
\end{filecontents}

\usepackage{tikz}
\tikzstyle{stoch}=[circle,thick,draw,minimum size=1.5em,inner sep=0em]
\tikzstyle{max}=[rectangle,thick,draw,minimum size=1.5em,inner sep=0em]
\tikzstyle{tran}=[thick,draw,->,>=stealth,rounded corners]
\tikzstyle{loop left}=[tran, to path={.. controls +(150:.8)
	and +(210:.8) .. (\tikztotarget) \tikztonodes}]
\tikzstyle{loop right}=[tran, to path={.. controls +(30:.8)
	and +(330:.8) .. (\tikztotarget) \tikztonodes}]
\tikzstyle{loop above}=[tran, to path={.. controls +(60:.5)
	and +(120:.5) .. (\tikztotarget) \tikztonodes}]
\tikzstyle{loop below}=[tran, to path={.. controls +(240:.8)
	and +(300:.8) .. (\tikztotarget) \tikztonodes}]

\input{macros}

\title{Regstar: Efficient Strategy Synthesis for Adversarial Patrolling Games}

\author[1]{David Kla\v{s}ka}
\author[1]{Anton\'{\i}n Ku\v{c}era}
\author[1]{V\'{\i}t Musil}
\author[1]{Vojt\v{e}ch {\v{R}}eh\'{a}k}

\affil[1]{%
Faculty of Informatics,
Masaryk University,
Brno, Czech Republic}

\begin{document}

\maketitle

\begin{abstract}
We design a new efficient strategy synthesis method applicable to adversarial patrolling problems on graphs with arbitrary-length edges and possibly imperfect intrusion detection.
The core ingredient is an efficient algorithm for computing the value and the gradient of a function assigning to every strategy its ``protection'' achieved.
This allows for designing an efficient strategy improvement algorithm by differentiable programming and optimization techniques.
Our method is the first one applicable to real-world patrolling graphs of reasonable sizes.
It outperforms the state-of-the-art strategy synthesis algorithm by a margin.
\end{abstract}

\section{Introduction}
\label{sec-intro}

\emph{Patrolling games} are a special type of security games where a mobile
Defender moves among vulnerable targets and aims to detect possible
ongoing intrusions initiated by an Attacker. The targets are modelled as
vertices in a directed graph where the edges correspond to admissible
Defender's moves. At any moment, the Attacker may choose some target
$\tau$ and initiate an intrusion (attack) at~$\tau$.
Completing this intrusion takes $d(\tau)$ time units,
and if the Defender does not visit $\tau$ in time,
he is penalized by utility loss determined by the cost of~$\tau$.

In \emph{adversarial} patrolling games
\citep{VAT:adversarial-patrolling,AKK:multi-robot-perimeter-adversarial,Agmon2009,BGA:large-patrol-AI,Basilico2009,MunozdeCote2013,SLESSLIN2019},
the Attacker knows the Defender's strategy and can even observe the Defender's
moves\footnote{The Defender may choose the next move randomly according to a
distribution specified by its moving strategy. Although the Attacker knows the
Defender's strategy (\ie, the distribution), it \emph{cannot} predict the way
of resolving the randomized choice.}. These assumptions are particularly
appropriate in situations where the actual Attacker's abilities are
\emph{unknown} and the Defender is obliged to guarantee a certain level of
protection even in the worst case. This naturally leads to using
\emph{Stackelberg equilibrium}
\citep{DBLP:conf/ijcai/SinhaFAKT18,yin2010stackelberg} as the underlying
solution concept, where the Defender/Attacker play the roles of the
leader/follower, \ie, the Defender commits to a moving strategy $\gamma$, and
the Attacker follows by selecting an appropriate counter-strategy~$\pi$. The \emph{value} of $\gamma$, denoted by~$\operatorname{Val}(\gamma)$, is the expected Defender's utility guaranteed by $\gamma$ against an arbitrary Attacker's strategy. Intuitively, $\operatorname{Val}(\gamma)$ corresponds to the ``level of protection'' achieved by~$\gamma$.

\begin{figure}[b]
	\centering
	\includegraphics[width=\linewidth]{map_Montreal_crop_3}
	\caption{We synthesize an efficient strategy for patrolling the net of Montreal's ATMS.}
\label{F:atms}
\end{figure}

The basic algorithmic problem in patrolling games is to compute a Defender's strategy $\gamma$ such that $\operatorname{Val}(\gamma)$ is as large as possible. Since general history-dependent strategies are not algorithmically workable (see \sect{sec-Defender-strategy}), recent works \citep{KL:patrol-regular,DBLP:conf/atal/KlaskaKLR18} concentrate on computing \emph{regular} strategies where the Defender's decisions depend on finite information about the history of previously visited vertices. As \citet{KL:patrol-regular} observed, regular strategies provide better protection than \emph{memoryless} strategies where the Defender's decision depends only on the currently visited vertex. However, the mentioned algorithms apply only to patrolling graphs where all edges have the \emph{same} length (traversal time). A longer distance between vertices can be modelled only by adding a sequence of auxiliary vertices and edges, quickly pushing the resulting graph's size beyond the edge of feasibility (see \sect{sec-experiments}). Even the currently best algorithm of \citet{DBLP:conf/atal/KlaskaKLR18} fails to solve small real-world patrolling graphs such as a network of selected ATMs in Montreal (\fig{F:atms}).

\paragraph{Our contribution}

\begin{enumerate}
\item We prove that \textbf{regular Defender's strategies} are not only better than memoryless strategies, but they are \textbf{arbitrarily close} to the power of general strategies.
Therefore, the scope of strategy synthesis can be safely restricted to regular strategies.
This resolves the open question of previous works.

\item We design an efficient \textsc{Regstar}\xspace\footnote{REGular STrategy ARchitect.} algorithm for computing regular Defender's strategies in general patrolling graphs with edges of \textbf{arbitrary length}.
\textsc{Regstar}\xspace applies to scenarios with \textbf{imperfect intrusion detection}, where the probability of discovering an intrusion at a target~$\tau$ by the Defender visiting $\tau$ is not necessarily equal to one.

\item We validate \textsc{Regstar}\xspace experimentally.
We compare \textsc{Regstar}\xspace against the best existing algorithm when applicable, and
we perform a set of \textbf{real-life experiments} demonstrating its strengths and limits.
\end{enumerate}

We depart from the fact that the function $\operatorname{Val}$ assigning the protection value to a given regular Defender's strategy is \emph{differentiable}.
The very heart of our algorithm is a novel, efficient procedure for computing the value and the gradient of $\operatorname{Val}$.
Since the size of the closed-form expression representing $\operatorname{Val}$ is exponential, the task is highly non-trivial.
We apply differentiable programming techniques and design an efficient strategy improvement algorithm for regular strategies based on gradient ascent.
The \textsc{Regstar}\xspace algorithm randomly generates many initial regular strategies, improves them, and returns the best strategy.

The efficiency of \textsc{Regstar}\xspace is evaluated experimentally in \sect{sec-experiments}.
In the first series of experiments, we compare the efficiency of \textsc{Regstar}\xspace against the algorithm of~\citet{DBLP:conf/atal/KlaskaKLR18}.
In the second series, we demonstrate the applicability of \textsc{Regstar}\xspace to a real-world patrolling graph with 18 targets corresponding to selected ATMs in Montreal.
In the last series, we document the power of regular strategies on patrolling graphs modelling buildings with corridors and offices.
Here, the information about the history of visited vertices is crucial for achieving reasonable protection.

Experiments prove that \textsc{Regstar}\xspace outperforms the method of~\citet{DBLP:conf/atal/KlaskaKLR18} and can solve instances far beyond the reach of this algorithm.
Our approach adopts the \emph{infinite horizon} patrolling game model, and therefore it does not suffer from the scalability issues caused by increasing the time bound in finite-horizon security games (see \sect{sec-related} for more comments).
For practical applications, solving patrolling graphs with about 20--30 targets seems sufficient, as the protection achievable by a single Defender becomes low for a higher number of targets, and the patrolling task needs to be solved by multiple Defenders\footnote{Patrolling by multiple Defenders is studied independently, see, \eg, \citep{Beynier:multiagent-patrol,GEW:multiple-defenders}}.

\section{Related Work}
\label{sec-related}

Patrolling games are a special type of \emph{security games} where game-theoretic concepts are used to determine the optimal use of limited security resources \citep{Tambe:book}.
Security games with static allocation have been studied in, \eg, \citep{JKKOT:massive-security-games,JKKOT:optimal-resource-massive-security-games,PJMOPTWPK:Deployed-ARMOR,TRKOT:IRIS,DBLP:conf/aaai/XuWVT18,DBLP:conf/ijcai/XuJSRDT15,DBLP:conf/aaai/GanAVG17}.
For patrolling games, where the Defender is mobile, most of the existing works assume the Defender is following a \emph{positional} strategy that depends solely on the current position of the Defender \citep{BGA:large-patrol-AI}.
Since positional strategies are weaker than general history-dependent strategies, there were also attempts to utilize the history of the Defender's moves.
This includes the technique of duplicating each node of the graph to distinguish internal states of the Defender (for example, \citet{AKK:multi-robot-perimeter-adversarial} consider a direction of the patrolling robot as a specific state; this is further generalized in \citet{bosansky2012-aaaiss}).
Another concept is higher-order strategies \citep{Basilico2009}, where the Defender takes into account a bounded sequence of previously visited states.
In our work, we use regular strategies \citep{KL:patrol-regular,DBLP:conf/atal/KlaskaKLR18}, where the information about the history of Defender's moves is abstracted into finitely many memory elements.

The existing strategy synthesis algorithms for patrolling games are based either on (1) mathematical programming with non-linear constraints, or (2) restricting the graph topology to some manageable subclass, or (3) strategy improvement, or (4) reinforcement learning.
The first approach (see, \eg, \citep{BGA:large-patrol-AI,Basilico2009,bosansky2011aamas}) suffers from scalability issues. In \citet{bosansky2011aamas}, the authors consider mobile targets, which forces the strategy to be time-dependent. \citet{BGA:large-patrol-AI} consider higher-order strategies in theory, but they perform experiments with positional strategies only due to computational infeasibility (one can easily construct examples where positional strategies are weaker than regular strategies and the protection gap is up to 100\%. The experiments of \citet{VAT:adversarial-patrolling} are also limited to positional strategies. \citet{SLESSLIN2019} make full use of the history, yet they study only perimeters (\ie, cycles), so their approach does not apply to graphs with arbitrary topologies.

The second approach applies only to selected topologies, such as lines, circles \citep{AKK:multi-robot-perimeter-adversarial,AgmonKK08-2}, or fully connected graphs with unit distance among all vertices \citep{BKR:patrol-Internet}.
The third approach has been applied only to patrolling graphs with edges of unit length.
The algorithm of \citet{KL:patrol-regular} requires a certain level of human assistance because the underlying finite-state automaton gathering the information about the Defender's history must be handcrafted.
\citet{DBLP:conf/atal/KlaskaKLR18} overcome this limitation by designing an automatic strategy synthesis algorithm, and it is the most efficient strategy synthesis procedure existing before our work. There is a high-level similarity to our algorithm because both use a variant of gradient ascent and construct regular strategies. However, the internals of the two algorithms is different. The core of our method is a novel procedure for computing the value and the gradient of the value function. In particular, our algorithm avoids the blowup in the number of states when modeling real-world patrolling scenarios with variable length edges. This allows for processing instances far beyond the reach of the algorithm of \citet{KKLR:patrol-gradient}, as documented experimentally in \sect{sec-Montreal}.

The fourth approach has been successful mainly for games with the finite horizon \citep{WSYWSJF:Patrolling-learning,DBLP:conf/aaai/KarwowskiMZGA19} and suffers from the exponential blowup in the number of finite paths with the increasing time bound.

\section{Patrolling Games}
\label{sec-patrolling}

We recall the standard model of adversarial patrolling games and fix the notation used.

\paragraph{Patrolling graphs}
\label{sec-graphs}

A \emph{patrolling graph} is a tuple $G = (V,T,E,\mathit{time},d,\alpha,\beta)$, where
\begin{itemize}
	\item $V$ is a non-empty set of \emph{vertices};
	\item $T \subseteq V$ is a non-empty set of \emph{targets};
	\item $E \subseteq V \times V$ is a set of \emph{edges};
	\item $\mathit{time}\colon E\to\mathbb{N}$ denotes the time to travel an edge;
	\item $d\colon T\to\mathbb{N}$ specifies the time to complete an attack;
	\item $\alpha\colon T\to\mathbb{R}_+$ defines the costs of targets;
	\item $\beta\colon T\to(0,1]$ is the probability of a successful intrusion detection.
\end{itemize}
For short, we write $u\to v$ instead of $(u,v)\in E$, and denote $\alpha_{\max}=\max_{\tau\in T} \alpha(\tau)$ and $d_{\max}=\max_{t\in T} d(t)$.
In the sequel, let $G$ be a fixed patrolling graph.

\subsection{Defender's strategy}
\label{sec-Defender-strategy}

A Defender's strategy is a recipe for selecting the next vertex.  In general,
the Defender may choose the next vertex randomly depending on some information
about the history of previously visited vertices.

Let $\mathcal{H}$ be the set of all finite paths in $G$, including the empty path~$\lambda$.
A \emph{Defender's strategy} for $G$ is a function $\gamma\colon\mathcal{H}
\rightarrow \mathit{Dist}(V)$ where $\mathit{Dist}(V)$ is the set of all probability
distributions on~$V$ such that whenever $\gamma(h)(v) > 0$, then either $h = \lambda$ or $u \rightarrow v$ where $u$ is the last vertex of~$h$. Note that $\gamma(\lambda)$ corresponds to the initial distribution on $V$.

Unrestricted Defender's strategies may depend on the whole history of previously visited vertices when
selecting the next vertex, and they may not be finitely representable.

\subsection{Attacker's strategy}

We consider the same patrolling game as in \citet{KKR:patrol-drones}, where the time is spent by moving along the edges.
We also use the same notion of Attacker's strategy, assuming that, in the \emph{worst case}, the Attacker can determine the next edge taken by the Defender \emph{immediately} after the Defender leaves the currently visited vertex.
This means that the Attacker's decision is based not only on the history of visited vertices but also on edge taken next.

The Attacker cannot gain anything by delaying his attack until the Defender arrives
at the next vertex.
Therefore we can assume an attack is initiated at the moment
when the Defender leaves the currently visited vertex.
Furthermore, the Attacker can attack \emph{at most once} during a play\footnote{Even if the Attacker can perform another attack after completing the previous one, the best choice the Defender is to follow an optimal strategy constructed for the single attack scenario.
This is no longer true when the Defender has to spend some time responding to the discovered attack \citep{SLESSLIN2019} or when multiple Attackers can perform several attacks concurrently.}.

An \emph{observation} is a finite sequence $o =
v_1,\ldots, v_n$, $v_n {\rightarrow} v_{n+1}$, where $v_1,\ldots, v_n\in\mathcal{H}$.
The set of all observations is denoted by $\Omega$.
An \emph{Attacker's strategy} for a patrolling graph $G$ is a function
$\pi\colon \Omega \rightarrow \{\mathit{wait},\mathit{attack}_\tau:\tau\in T\}$. We require that
if $\pi(v_1,\ldots, v_n,v_n {\rightarrow} u) = \mathit{attack}_\tau$ for some $\tau \in T$,
then $\pi(v_1,\ldots, v_i,v_i {\rightarrow} v_{i+1}) = \mathit{wait}$ for all $1\leq
i<n$ ensuring that the Attacker can attack at most once.

\subsection{Evaluating Defender's strategy}

\newcommand\Eval{\operatorname{Eval}}

Let $o = v_1,\ldots, v_n$, $v_n {\rightarrow} v_{n+1}$, $n\ge 1$, be an observation, $\tau\in T$ a target and consider an attack at $\tau$ after observing~$o$.

By $\textit{Path}(o,\tau)$ we denote the set of all finite paths $u$ from $v_{n+1}$ to $v_{n+1+k}=\tau$ of the length $k\ge 0$ such that the total time needed to traverse from $v_n$ to $\tau$ along $u$ does not exceed~$d(\tau)$.

For $u\in\textit{Path}(o,\tau)$, let $\Eval(\tau\mid u)$ be the value defended at $\tau$ when the Defender discovered the attack in the last vertex of $u$.
The probability of detecting the attack at $\tau$ after traversing $u$ equals $(1-\beta(\tau))^{\#_\tau(u)-1} \cdot \beta(\tau)$, where $\#_\tau(u)$ stands for the number of visits to $\tau$ along $u$.
Indeed, since the intrusion detection is not perfect, the Defender failed to discover the attack at the first $\#_\tau(u)-1$ trials with the probability $1-\beta(\tau)$ and succeeded at the last one with the probability~$\beta(\tau)$.
Specially, when $\beta=1$ and $\#_\tau(u)=1$, the factor becomes $0^0$, interpreted as~$1$.
Therefore, as $\alpha(\tau)$ denotes the cost of $\tau$,
\begin{equation}
	\Eval(\tau\mid u)
		= \alpha(\tau) \cdot (1-\beta(\tau))^{\#_\tau(u)-1} \cdot \beta(\tau).
\end{equation}

The \emph{protection} achieved by $\gamma$ against an attack at~$\tau$ initiated after observing~$o$ is defined as
\begin{equation}
  \mathbf{P}^{\gamma}(\tau\mid o)
		= \!\!\sum_{u \in \textit{Path}(o,\tau)} \operatorname{Prob}^\gamma(u\mid o) \cdot \Eval(\tau\mid u),
\end{equation}
where $\operatorname{Prob}^\gamma(u \mid o)$ is the probability of performing~$u$ after observing~$o$, \ie,
\begin{equation}
	\operatorname{Prob}^\gamma(u\mid o)
		= \prod_{i=1}^{k} \gamma(v_1,\ldots,v_{n+i})(v_{n+i+1}).
\end{equation}
Similarly, we use $\operatorname{Prob}^\gamma(o)$ to denote the probability that observation~$o$ occurs, \ie,
\begin{equation}
\operatorname{Prob}^\gamma(o)
= \prod_{i=0}^{n} \gamma(v_1,\ldots,v_{i})(v_{i+1}).
\end{equation}
Now let $\pi$ be an Attacker's strategy.
For every $\tau \in T$, let $\mathit{Att}(\pi,\tau)$ be the set of all $o\in\Omega$ such that $\pi(o)=\mathit{attack}_\tau$.
The \emph{expected Attacker's utility} for $\gamma$ and $\pi$ is defined as
\begin{equation}
	\mathbb{E}U_A(\gamma,\pi)
	= \sum_{\tau \in T} \sum_{o\in\mathit{Att}(\pi,\tau)}
				\!\!\operatorname{Prob}^{\gamma}(o) \cdot \bigl[\alpha(\tau) - \mathbf{P}^{\gamma}(\tau\mid o)\bigr].
\end{equation}
Note that $\mathbb{E}U_A(\gamma,\pi)$ corresponds to the expected amount ``stolen'' by the Attacker.
Consistently with \citet{DBLP:conf/atal/KlaskaKLR18}, the \emph{expected Defender's utility} is defined as
\begin{equation} \label{eq-EUD}
   \mathbb{E}U_D(\gamma,\pi)
	 	= \alpha_{\max} - \mathbb{E}U_A(\gamma,\pi)\,.
\end{equation}

The Defender/Attacker aims to maximize/minimize the expected protection $\mathbb{E}U_D(\gamma,\pi)$, respectively.
The \emph{value} of a given Defender's strategy $\gamma$  is the expected protection guaranteed by $\gamma$ against an \emph{arbitrary} Attacker's strategy, \ie,
\begin{equation} \label{E:val-def}
	\operatorname{Val}_G(\gamma)  =  \inf_{\pi} \ \mathbb{E}U_D(\gamma,\pi)\,.
\end{equation}
Maximal protection achievable in $G$ is then
\begin{equation}
  \operatorname{Val}_G = \sup_\gamma \operatorname{Val}_G(\gamma)\,.
\end{equation}

\section{The Method}

Our approach consists of three stages.
First, since the value function from \eqref{E:val-def} is not a priori
tractable, we analyze the value of \emph{regular strategies} for $G$.
This yields a closed-form differentiable value function.
Secondly, we design an \emph{efficient algorithm} that computes the value function and its gradient. This is the heart of our contribution.
Finally, we combine these elements into the \textsc{Regstar}\xspace algorithm, which \emph{generates the best regular strategies} via gradient ascent.

\subsection{Regular Defender's strategies}
\label{sec-reg-strategies}

An algorithmically workable subclass of Defender's strategies are
\emph{regular} strategies used by~\citet{KL:patrol-regular,DBLP:conf/atal/KlaskaKLR18}.
In this concept, the information about the history of visited
vertices is abstracted into a \emph{finite} set of memory elements assigned to each vertex.

Formally, we turn vertices $v\in V$ of $G$ into \emph{eligible pairs}
$\dhat{V}=\{(v,m): v\in V,\,1\le m\le \mem(v)\}$
in which the memory sizes $\mem\colon V\to\mathbb{N}$ are fixed.
A \emph{regular Defender's strategy} for $G$ is a function $\sigma\colon\dhat{V}\to\mathit{Dist}(\dhat{V})$
satisfying $\sigma(v,m)(v',m')>0$ only if $v\to v'$.
Intuitively, the Defender traverses the vertices of $G$ updating memory elements and thus ``gathering''
some information about the history of visited vertices. The probability that $v'$ with information represented by $m'$ is visited after the current $v$ with information~$m$ is given by $\sigma(v,m)(v',m')$.
A regular strategy $\sigma$ is called
\emph{deterministic-update} if $\sigma(v,m)(v',m_1)>0$ and $\sigma(v,m)(v',m_2)>0$ imply $m_1=m_2$.
This means that when the Defender is in $(v,m)$, he may randomize to choose the next vertex $v'$,
but the next memory element is then determined uniquely by $(v,m)$ and~$v'$.

For a regular strategy $\sigma$, we derive an expression $\operatorname{RVal}_G(\sigma)$ which corresponds to the value of $\sigma$
against an Attacker who can observe even the current memory element. This approach is consistent with the worst-case paradigm discussed in \sect{sec-intro},
as it is not clear whether the Attacker is capable of that. We show that the expression $\operatorname{RVal}_G(\sigma)$ is indeed a lower bound on $\operatorname{Val}_G(\sigma)$
(\ie, $\sigma$'s value against an Attacker who \emph{cannot} observe the current memory element, \cf. \eqref{E:val-def})
and under reasonable assumptions, they are equal (Claim~\ref{T:val}).
Since $\operatorname{RVal}_G(\sigma)$ is in a closed form, this makes regular strategies algorithmically workable.
Furthermore, we show that regular strategies can achieve protection \emph{arbitrarily close} to the \emph{optimal} protection achievable by unrestricted strategies. Thus, they offer a convenient trade-off between optimality and tractability.

\begin{theorem} \label{thm-reg}
Let $G$ be a patrolling graph and $\mathit{Reg}$ the class of all regular Defender's strategies in $G$.
Then
\begin{equation}
	\sup_{\sigma \in \mathit{Reg}} \operatorname{Val}_G(\sigma) = \operatorname{Val}_G
\end{equation}
\end{theorem}

\begin{figure}[tb]
\centering
\begin{tikzpicture}[scale=.7, every node/.style={scale=.7}, x=1cm, y=1cm]
\node [circle,fill=black,inner sep=1.5pt,label=$\lambda$] (eps) at (0,0) {};
\draw[thick] (eps) -- (-1.7,-4);
\draw[thick] (eps) -- (1.5,-4);
\node [circle,fill=black,inner sep=1.5pt,label=above right:$\bar{h}$,label=below left:$T_{\bar{h}}$] (barh) at (-.1,-1.5) {};
\draw[thick] (barh) -- +(-.3,-1) -- +(.3,-1) -- (barh);
\node [circle,fill=black,inner sep=1.5pt,label=above right:$hv$,label=below left:$T_{hv}$] (h) at (.11,-3.3) {};
\draw[thick] (h) -- +(-.3,-1) -- +(.3,-1) -- (h);
\draw[thick,dotted,->] (eps) -- (barh);
\draw[thick,dotted,->] (barh) -- (h);
\node [draw=none,label={optimal strategy $\gamma$}] (a) at (0,-5.2) {};
\begin{scope}[xshift=4.5cm]
\node [circle,fill=black,inner sep=1.5pt,label=$\lambda$] (eps) at (0,0) {};
\draw[thick] (eps) -- (-1.7,-4);
\draw[thick] (eps) -- (1.7,-4);
\node [circle,fill=black,inner sep=1.5pt,label=above right:$\bar{h}$,label=below left:$T_{\bar{h}}$] (barh) at (-.1,-1.5) {};
\draw[thick] (barh) -- +(-.3,-1) -- +(.3,-1) -- (barh);
\node [circle,fill=black,inner sep=1.5pt] (h) at (.11,-3.3) {};
\draw[thick,dotted,->] (eps) -- (barh);
\draw[thick,dotted,->] (barh) -- (h);
\draw[thick,dashed,rounded corners,->] (h) -- +(.4,0) |- (barh);
\node [draw=none,label={strategy $\sigma_\delta$}] (a) at (0,-5.2) {};
\end{scope}
\end{tikzpicture}
\caption{Folding $\gamma$ into $\sigma_\delta$.}
\label{fig-folding}
\end{figure}

\begin{proof}[Proof (sketch)]
First, we fix an \emph{optimal} Defender's strategy $\gamma : \mathcal{H} \rightarrow \mathit{Dist}(V)$  satisfying $\operatorname{Val}_G(\gamma) = \operatorname{Val}_G$ (the existence of $\gamma$ has been proven in \citep{BHKRA:Patrol-strategy-arxiv}).

To every history $h$, we associate a finite tree $T_h$ of depth $d_{\max}$ such that:
\begin{itemize}
\item The set of nodes contains all histories $h'$ such that $hh'$ is also a history and the length of $h'$ is bounded by $d_{\max}$;
\item The root of $T_h$ is the empty history $\lambda$;
\item $h' \tran{x} h'v$ is an edge of $T_h$ iff the distribution $\gamma(hh')$ selects the vertex $v$ with probability~$x>0$.
\end{itemize}
We say that histories $h,\bar{h}$ are \emph{$\delta$-similar} for a given $\delta > 0$ iff $h,\bar{h}$ end in the same vertex and the trees $T_h$ and $T_{\bar{h}}$ are the same up to $\delta$-bounded differences in edge probabilities. Observe that one can construct a fixed sequence of finite trees $T_1,\ldots,T_n$ such that \emph{every} $T_h$ is \mbox{$\delta$-similar} to some $T_i$, where the $n$ depends just on $G$ and $\delta$. Furthermore, we say that a history $h$ \emph{has $\delta$-similar prefix $\bar{h}$} iff $h = \bar{h}w$ where $h,\bar{h}$ are $\delta$-similar and the length of $w$ is larger than $d_{\max}$.

Let $H_\delta$ be the set of all histories $h$ such that $\operatorname{Prob}^\gamma(h)>0$ and no prefix of $h$ (including $h$ itself) has a $\delta$-similar prefix. Observe that the maximal length of such a history is bounded by
$n\cdot(d_{\max} {+}1)$ where the $n$ is defined above, and hence $H_\delta$ is a finite set. Let $\mem$ be a function assigning  $|H_\delta|$ memory elements to every vertex. To simplify our notation, we identify memory elements with the elements of $H_\delta$. Now consider the regular strategy $\sigma_\delta$ defined as follows: for every eligible pair $(v,h)$, we have that  \mbox{$\sigma_\delta(v,h)(v',h') = x$} iff $\gamma(\hat{h})(v') = x$ and $h' = \hat{h}$, where
\begin{equation*}
	\hat{h} =
		\begin{cases}
			\bar{h} & \mbox{if $hv$ has a $\delta$-similar prefix $\bar{h}$,} \\
			hv      & \mbox{otherwise}.
		\end{cases}
\end{equation*}
Intuitively, $\sigma_\delta$ is obtained by ``folding'' the optimal
strategy~$\gamma$ after encountering a history $hv$ with a $\delta$-similar
prefix $\bar{h}$, see \fig{fig-folding}.

The proof is completed by showing that $\lim_{\delta \rightarrow 0^+}
\operatorname{Val}_{G}(\sigma_\delta) = \operatorname{Val}_G$. This is intuitively plausible, because
$\sigma_\delta$ becomes more similar to $\gamma$ for smaller $\delta$. However,
the argument also depends on the subgame-perfect property of optimal
strategies.

Since $\sigma_\delta$ is a deterministic-update regular strategy,
Theorem~\ref{thm-reg} holds even for the subclass of deterministic-update
regular strategies.
\end{proof}

Let us fix a regular strategy $\sigma$. For convenience, we write
$\sigma(\dhat u,\dhat v)$ for $\sigma(\dhat u)(\dhat v)$.
The set of \emph{eligible edges} $\dhat E$ consists of all edges
$e\in\dhat V\times\dhat V$ such that $\sigma(e)>0$. These are
exactly the edges actually used by the Defender.
A finite sequence of eligible pairs
$u=(v_1,m_1),\dots,(v_n,m_n)$ is called an \emph{eligible path} if
$v_1,\dots,v_n$ is a path in $G$. The probability of executing $u$
is
\begin{equation}
	\operatorname{Prob}^\sigma(u) = \prod_{i=1}^{n-1} \sigma\bigl((v_i,m_i),(v_{i+1},m_{i+1})\bigr)
\end{equation}
For $e=((v,m),(v_1,m_1))\in\dhat E$ and $\tau\in T$, let $\textit{Path}(e,\tau)$ denote
the set of all eligible paths $(v_1,m_1),\dots,(v_k,m_k)$ such that
$v_k=\tau$, $k\ge 1$ and the traversal time of the path $v,v_1,\dots,v_k$ is
at most~$d(\tau)$.

We can now express the value of a regular strategy $\sigma$
as follows:
\begin{equation} \label{E:rval}
	\operatorname{RVal}_G(\sigma)
		= \alpha_{\max} -
			\max_{e\in\hat E,\,\tau\in T}\bigl\{\alpha(\tau) - \mathbf{P}^\sigma(e,\tau)\bigr\},
\end{equation}
where
\begin{equation} \label{E:P-sigma}
\mathbf{P}^\sigma(e,\tau)
= \sum_{u\in\textit{Path}(e,\tau)} \operatorname{Prob}^\sigma(u)\cdot \Eval(\tau\mid u).
\end{equation}

\begin{claim} \label{T:val}
Let $\sigma$ be a regular strategy.
Then
\begin{equation} \label{E:val-sigma}
\operatorname{Val}_G(\sigma) \geq \operatorname{RVal}_G(\sigma)
\end{equation}
Moreover, if the graph $(\dhat V,\dhat E)$ is strongly connected
and $\sigma$ is deterministic-update, then the above holds with equality.

\end{claim}

\begin{proof}[Proof (sketch)]
It is easy to observe that the edge lengths, the target cost $\alpha(\tau)$ and
the detection probability $\beta(\tau)$ are correctly accounted for in the
definition of $\mathbf{P}^\sigma(e,\tau)$.  The rest of the argument is the same
as in~\citep{KL:patrol-regular,DBLP:conf/atal/KlaskaKLR18}.
\end{proof}

A regular strategy $\sigma$ depends only on reasonably many variables $\sigma(e)$, $e\in\dhat E$.
Hence we identify $\sigma$ as an element of $\mathbb{R}^{|\dhat E|}$.
The function $\operatorname{RVal}_G\colon\mathbb{R}^{|\dhat E|}\to\mathbb{R}$ of variable $\sigma$ is differentiable up to the set where the points of maxima in \eqref{E:val-sigma} are not unique.

Claim~\ref{T:val} equips us with a closed-form formula for strategy evaluation. Hence, it enables us to apply methods from differentiable programming to obtain the value of a strategy and its sensitivity to the change of the input.

\subsection{Strategy evaluation}

We describe our algorithm that evaluates $\operatorname{RVal}_G$ and its gradient at
a given point $\sigma$.  According to \eqref{E:val-sigma}, we first evaluate
all the protection values $\mathbf{P}^\sigma(e,\tau)$ and their gradients
$\nabla\mathbf{P}^\sigma(e,\tau)$.  The value $\operatorname{RVal}_G(\sigma)$ and its gradient
should then be simply the smallest of all values and its gradient.  In
practice, we replace this minimum with its ``soft'' version. The details are
addressed in \sect{S:optim}.

\paragraph{Computing $\mathbf{P}^\sigma$ and $\nabla\mathbf{P}^\sigma$}
Given $e\in\dhat E$ and $\tau\in T$,
a naive approach based on \emph{explicitly constructing}
$\mathbf{P}^\sigma(e,\tau)$
is inevitably inefficient, because the set $\textit{Path}(e,\tau)$ may contain
exponentially many different paths.
We overcome this problem by performing a search on the graph
during which (sub)paths with the same endpoints and the same traversal time
are ``aggregated'' into a single term, resulting in a more compact
representation of $\mathbf{P}^\sigma(e,\tau)$ and $\nabla\mathbf{P}^\sigma(e,\tau)$.
The search is guided by a min-heap $\mathcal{H}$, similarly as in Dijkstra's shortest path algorithm.
However, unlike in Dijkstra's, where the search is initiated from each vertex at most once,
we must consider \emph{all} paths from $e$ to $\tau$ whose traversal time does not exceed $d(\tau)$,
and we must keep track of their probability and the corresponding gradient.
To that purpose, each item of $\mathcal{H}$ corresponds to a certain \emph{set} of paths.
Moreover, instead of initiating the search at $e$, we initiate it at $\tau$
and search the graph backwards. This trick allows us to compute $\mathbf{P}^\sigma(e,\tau)$
for a given $\tau\in T$ and \emph{all} $e\in\dhat E$ at once, thereby saving
a factor of $|\dhat E|$ in the resulting time complexity.

In particular, for any $(v,m)\in\dhat V$ and $t\leq d(\tau)$, let
$\mathcal{L}_{v,m,t}$ denote the set of all paths which start at $(v,m)$,
end at $(\tau,\cdot)$ and have traversal time $t$. Further, for any
$\mathcal{L}\subseteq\mathcal{L}_{v,m,t}$, let
\begin{equation}
\mathbf{P}^{\sigma}(\mathcal{L})
= \sum_{u \in \mathcal{L}} \operatorname{Prob}^\sigma(u) \cdot \Eval(\tau\mid u)
\end{equation}
As a result of the search, each $\mathcal{L}_{v,m,t}$ is partitioned into pairwise
disjoint sets $\mathcal{L}_1,\ldots,\mathcal{L}_k$ in such a way that the sets $\mathcal{L}_i$
are in one-to-one correspondence with the items of $\mathcal{H}$.
In \alg{alg-dynamic}, each $\mathcal{L}_i$ is represented
by a tuple $(v,m,t,p,\pgrad)$ where $p$ and
$\pgrad$ correspond to the value and the gradient of
$\mathbf{P}^{\sigma}(\mathcal{L}_i)$ at $\sigma$, respectively.
Then, writing $e=((v',m'),(v,m))$, the value of $\mathbf{P}^{\sigma}(e,\tau)$ (cf. \eqref{E:P-sigma})
can be computed as the sum of $\mathbf{P}^{\sigma}(\mathcal{L}_{v,m,t})$ over all $t\leq d(\tau)-\mathit{time}(v',v)$
where $\mathbf{P}^{\sigma}(\mathcal{L}_{v,m,t})$ is computed as the sum of $\mathbf{P}^{\sigma}(\mathcal{L}_i)$
over the sets $\mathcal{L}_i$ that form the partition of $\mathcal{L}_{v,m,t}$.
The gradient is computed analogously.
In \alg{alg-dynamic}, we also use two auxiliary arrays $\mathcal{V}$ and $\mathcal{G}$ for
storing the value and the gradient of $\mathbf{P}^{\sigma}(\mathcal{L}_{v,m,t})$
for all $(v,m)\in\dhat V$ and the currently examined traversal time $t$.

The body of the main loop (lines~\ref{line-initH}--\ref{line-end-z}) is
executed for every $\tau\in T$ and computes $\mathbf{P}^\sigma(e,\tau)$ and
$\nabla\mathbf{P}^\sigma(e,\tau)$ for every $e\in\dhat E$.
The correctness of the algorithm follows from the fact that
after executing line~\ref{line-set-l}, for every $(v,m)\in\dhat V$ we have that
\newcommand\pe{\;\texttt{+=}\;}
\newcommand\te{\;\texttt{*=}\;}
\newcommand\ee{\;\texttt{=}\;}
\SetAlFnt{\small}
\begin{algorithm}[h!]
	\SetAlgoLined
	\DontPrintSemicolon
	\SetKwInOut{Parameter}{parameter}\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
	\SetKwData{C}{C}\SetKwData{D}{D}\SetKwData{MX}{M}\SetKwData{f}{f}
	\SetKw{Or}{or}
	\SetKw{And}{and}
	\SetKw{Not}{not}
	\SetKwData{Array}{array of}
	\SetKwData{Rat}{Rat}
	\SetKwData{Der}{Der}
	\SetKwData{MinHeap}{min-heap of Paths}
	\SetKwData{Index}{indexed by}
	\SetKwProg{Macro}{macro}{:}{}
	\Input{A patrolling graph $G$, a regular strategy $\sigma$}
	\Output{The sets $\{\mathbf{P}^\sigma(e,\tau)\}$ and $\{\nabla\mathbf{P}^\sigma(e,\tau)\}$}
	\BlankLine
	\makebox[2em][l]{$\mathbf{P}^\sigma$} : \texttt{array}  \makebox[0em][l]{ indexed by edges $\dhat E$ and targets $T$} \;
	\makebox[2em][l]{$\nabla\mathbf{P}^\sigma$} : \texttt{array} \makebox[0em][l]{ indexed by edges $\dhat E$ and targets $T$} \;

	\makebox[1em][l]{$\mathcal{V}$} : \texttt{array} \mbox{ indexed by eligible pairs $\dhat V$} \;
	\makebox[1em][l]{$\mathcal{G}$} : \texttt{array} \mbox{ indexed by eligible pairs $\dhat V$} \;
	\makebox[1em][l]{$\mathcal{H}$} : \texttt{min-heap} \mbox{ of tuples $(v,m,t,p,\pgrad)$ sorted by $t$}    \;
    \BlankLine
    set all elements of $\mathbf{P}^\sigma$ to $0$ and $\nabla\mathbf{P}^\sigma$ to $\vec 0$\;

	\ForEach{$\tau \in T$}{
		set $\mathcal{H}$ to empty heap\; \label{line-initH}
		\ForEach{$m$ such that $(\tau,m)\in\dhat V$}{\label{initH-start}
		   $\mathcal{H}.\mathit{insert}(\tau,m,0,\alpha(\tau)\beta(\tau),\vec{0})$\;
		}\label{initH-end}

	    \While{\Not $\mathcal{H}.\mathit{empty}$}{\label{line-loop-H-start}
	       set all elements of $\mathcal{V}$ to 0 and $\mathcal{G}$ to $\vec{0}$ \;\label{line-AB-init}
	       $\ell \ee \mathcal{H}.\mathit{peek}.t$\;\label{line-set-l}

	       \Repeat{$\mathcal{H}.\mathit{empty}$ \Or $\mathcal{H}.\mathit{peek}.t > \ell$}{\label{line-AB-start}
	       	   $(v,m,t,p,\der) \ee \mathcal{H}.\mathit{pop}$ \;
	       	   $\mathcal{V}(v,m) \pe p$ \;
	       	   $\mathcal{G}(v,m) \pe \der$ \;
	       }\label{line-AB-end}

           \ForEach{$(v,m)$ such that $\mathcal{V}(v,m) > 0$\label{line-vm-start}}{
               \ForEach{$e \ee ((v',m'),(v,m))\in\dhat E$}{
							 		$t \ee \mathit{time}(v',v)$\;
               	  \uIf{$\ell + t \leq d(\tau)$}{
               	  	 $\mathbf{P}^\sigma(e,\tau) \pe \mathcal{V}(v,m)$\;\label{line-A-inc}
               	  	 $\nabla\mathbf{P}^\sigma(e,\tau) \pe \mathcal{G}(v,m)$\;\label{line-B-inc}
               	     $p \ee \mathcal{V}(v,m) \cdot \sigma(e)$ \;\label{line-p-start}
               	     \lIf{$v'=\tau$}{
               	     	$p \te 1-\beta(\tau)$
                     }\label{line-p-end}
               	     \ForEach{$e' \in\dhat E$\label{line-der-init}}{
               	     	 $\der(e') \ee \sigma(e)\cdot\mathcal{G}(v,m)(e')$\; \label{line-cder-start}
                         \lIf{$e' = e$}{
                        	$\der(e') \pe \mathcal{V}(v,m)$
                        }
               	         \lIf{$v' = \tau$}{
														$\der(e') \te 1-\beta(\tau)$
                         }\label{line-cder-end}
                     }\label{line-der-end}
               	     $\mathcal{H}.\mathit{insert}(v',m',\ell+t,p,\der)$\;\label{line-H-insert}
               	  }
               }
           } \label{line-vm-end}
        } \label{line-end-z}\label{line-loop-H-end}
	}
	\Return $\mathbf{P}^\sigma$, $\nabla\mathbf{P}^\sigma$
	\caption{Compute $\mathbf{P}^\sigma$ and $\nabla\mathbf{P}^\sigma$}
	\label{alg-dynamic}
\end{algorithm}
\begin{equation} \label{E:p1}
	\mathbf{P}^{\sigma}(\mathcal{L}_{v,m,\ell})
		= \sum_{(v,m,\ell,p,\pgrad) \in \mathcal{H}} p
\end{equation}
and
\begin{equation} \label{E:p2}
	\nabla\mathbf{P}^{\sigma}(\mathcal{L}_{v,m,\ell})
		= \sum_{(v,m,\ell,p,\pgrad) \in \mathcal{H}} \pgrad,
\end{equation}
which can be proved by induction on the number of iterations
of the loop at lines~\ref{line-loop-H-start}--\ref{line-loop-H-end}
(the value of $\ell$ assigned at line~\ref{line-set-l}
always increases between successive iterations).

\paragraph{Complexity analysis}
Let $\Lambda$ be the total number of pairwise different $t$'s for which there exists $u \in \textit{Path}(e,\tau)$ with traversal time equal to $t$.
Note that there are at most $|\dhat E| \cdot \Lambda$ items in $\mathcal{H}$, so each heap operation takes time $\mathcal{O}(\log(|\dhat E| \cdot \Lambda))$.
An analysis of the main loop (lines~\ref{line-initH}--\ref{line-loop-H-end}) reveals that the time complexity of \alg{alg-dynamic} is
\begin{equation}
	\mathcal{O}\bigl(|T|\cdot |\dhat E|^2 \cdot \Lambda \cdot (|\dhat E| + \log(|\dhat E| \cdot \Lambda)\bigr)\,.
\end{equation}
The size of $\Lambda$ plays a crucial role.
It stays reasonably small even if $G$ contains ``long'' edges.
In the worst case, $\Lambda$ can be equal to $d_{\max}$, but this is rarely the case in practice.
Clearly,  the traversal time of every $u \in \textit{Path}(e,\tau)$ is at least $t_{\min}=\min_{v\to v'} \mathit{time}(v,v')$; and for many other $t$'s between $1$ and $d_{\max}$, there may exist no $u \in \textit{Path}(e,\tau)$ with traversal time equal to $t$.
This also explains why applying the algorithm of \citet{DBLP:conf/atal/KlaskaKLR18} to the modified graph obtained from $G$ by splitting the long edges into sequences of unit-length edges is far less efficient than applying our algorithm directly to $G$. Such modification increases the number of vertices very quickly, even if $\Lambda$ is small.
This is confirmed experimentally in \sect{sec-experiments}.

\subsection{\textsc{Regstar}\xspace\ algorithm}
\label{S:optim}

Having a fast, efficient and differentiable algorithm for strategy evaluation
enables us to apply gradient ascent methods.  For a given patrolling graph $G$
and fixed memory sizes $\mem$, we start with strategy $\sigma$ having its
values assigned randomly. Then, in an optimization loop,
we examine $\operatorname{RVal}_G(\sigma)$ and modify $\sigma$ in the direction of its gradient
until no gain is achieved (see \alg{alg-grad}).

The \textsc{Regstar}\xspace algorithm constructs a Defender's strategy by running \alg{alg-grad}
repeatedly for a given number of random $\sigma$ and selecting the best outcome. This results in high-quality strategies, as experimental results confirm.

\paragraph{Normalization}

By definition, a regular strategy $\sigma$ is a bunch of probability
distributions.  A modification of $\sigma$ by an update vector $\xi$ can (and
does) violate this property. A workable solution then requires the use of a
normalization.  Our normalization procedure $N_1(\sigma)$ crops all
elements of $\sigma$ into the interval $[0,1]$ and then returns $\sigma(\dhat
v)/|\sigma(\dhat v)|$ for every $\hat v\in \dhat V$, where $|\sigma(\dhat v)| =
\sum_{(\dhat v,v)\in\dhat E} \sigma(\dhat v, v)$.  The function $\sigma\mapsto
N_1(\sigma)$ is again differentiable at almost every point $\sigma$.
Therefore, the composition of normalization and evaluation results in a
differentiable algorithm whose gradient is, by the chain rule, the composition
$\nabla\operatorname{RVal}_G(N_1(\sigma))\cdot\nabla N_1(\sigma)$.

Prior works \citep{KL:patrol-regular,DBLP:conf/atal/KlaskaKLR18} omitted this step assuming
that the parameter space is the set of normalized strategies.  They
implicitly modify their gradients in order that the update results in a
normalized strategy. This approach can be modelled in our setting by
considering different ``pivoted'' normalization, denoted by
$N_p(\sigma)$. It crops the values as well and, for $\dhat v\in\dhat V$,
$N_p(\sigma)(\dhat v,v)$ equals to $\sigma(\dhat v,v)$ for all $(\dhat v,v)\in\dhat
E$ except one ``pivot'', say $v_p$, for which $\sigma(\dhat v,v_p) =
1-\sum_{(\dhat v,v)\in\dhat E,v\ne v_p} \sigma(\dhat v,v)$.

Pivoting normalization $N_p$ yields very sparse gradients $\nabla N_p$ in oppose to $\nabla N_1$ and filters the signal propagation back to~$\sigma$.
This potentially slows down the optimization, as demonstrated in our experiments (see the supplementary material).

\SetAlFnt{\small}
\begin{algorithm}[tb]
	\SetAlgoLined
	\DontPrintSemicolon
	\SetKwInOut{Parameter}{parameter}
	\SetKwInOut{Input}{input}
    \SetKwInOut{Output}{output}
	\SetKw{Or}{or}
	\SetKw{And}{and}
	\SetKwFunction{normalize}{Normalize}
	\SetKwFunction{step}{Step}
	\Input{A patrolling graph $G$, a regular strategy $\sigma$}
	\Output{A regular strategy $\sigma'$}
	\BlankLine
    \Repeat{$\operatorname{RVal}_G(\sigma')-p\le \text{threshold}$}{
    	$(\sigma, \nabla\sigma) = \normalize(\sigma)$ \;
			$(p, \nabla p) = \operatorname{RVal}_G(\sigma)$ \;
	    $\sigma' = \step(\sigma, \nabla p\cdot\nabla\sigma)$ \; \label{line-step}
    }
		\Return $\sigma'$ \;
	\caption{Strategy optimization.}
	\label{alg-grad}
\end{algorithm}

\paragraph{Minima softening}

So far, we supposed that $\operatorname{RVal}_G(\sigma)$ returns a value
$\mathbf{P}^\sigma(e,\tau)$ that attains the minimal value. Therefore, only the
top candidate is taken into account in the optimization. In contrast, one can
consider more competitors $\mathbf{P}^\sigma(e,\tau)$ that are close to the
minima and optimize for them simultaneously. We implement the very same
``softening'' method as in the baseline algorithm
\citep{DBLP:conf/atal/KlaskaKLR18}.

\paragraph{Strategy update}

In each optimization step, we update the strategy $\sigma$ by
a proportion of the proper gradient $\xi=\nabla\operatorname{RVal}_G\cdot\nabla N_1$.
We use the same scheduling as proposed by \citet{DBLP:conf/atal/KlaskaKLR18},
where a variant of an update $\sigma'=\sigma+(1-\delta)^k\xi$ is being
used.

\section{Experiments}
\label{sec-experiments}

In many natural patrolling scenarios, the targets are distinguished geographic locations (banks, patrol stations, ATMs, tourist attractions, etc.). The connecting edges model the admissible moves of patrolling units (drones, police cars, etc.).
Such graphs naturally contain edges of varying traversal time.

All the existing strategy improvement algorithms are designed for patrolling graphs with edges of unit traversal time.
They can be applied to graphs with general topology once every ``long'' edge is replaced with a path consisting of edges of the unit length passing through fresh auxiliary vertices.
We will apply this modification to graphs when necessary, without further notice.

In the first experiment, we compare the efficiency of \textsc{Regstar}\xspace against currently the best \textsc{Baseline}\xspace \citep{DBLP:conf/atal/KlaskaKLR18}.
In the second experiment, we demonstrate the capability of \textsc{Regstar}\xspace on a real-world patrolling problem that is far beyond the
limits of \textsc{Baseline}\xspace. In the last experiment, we examine the impact of available memory size on the protection achieved by \textsc{Regstar}\xspace.

\begin{figure}[t]
	\centering
	\includegraphics[width=\linewidth]{Exp1_graph_no_labels}
\caption{Comparison of \textsc{Regstar}\xspace against \textsc{Baseline}\xspace. The time (in secs., logscale) needed
to finish 50 optimization runs on various graphs is shown. The timeout is~1600~s.}
\label{fig-exp1}
\end{figure}

\subsection{Comparison to Baseline}
\label{sec-baseline}

We consider patrolling graphs where ten targets are selected randomly from $n \times n$ grid.
The traversal time between two vertices corresponds to their $L^1$ distance\footnote{We use the $L^1$ (taxicab, Manhattan) distance instead of Euclidean distance because the former is considered as a better approximation of commuting distance.}.
For each $n = 4,\ldots,9$, we randomly select five graphs $G_n(1),\ldots,G_n(5)$.
Thus, we obtain a collection of 30 patrolling graphs.
Note that these graphs tend to contain longer edges with the increased~$n$.
The targets' cost is selected randomly between 180 and 200, and intrusion detection is perfect.
The time needed to complete an attack is the same for all targets in $G_n(i)$, and it is set to a value for which the Defender can achieve a reasonably high protection ($d(\tau)=\mathit{time}_{\max} +\mathit{time}_{\text{avg}}+3$, where $\mathit{time}_{\max}$ and $\mathit{time}_{\text{avg}}$ is the maximal and the average traversal time of an edge).
For each $G_n(i)$, we report the total running time \textsc{Regstar}\xspace and \textsc{Baseline}\xspace need to improve the same set of 50 randomly generated initial regular strategies.
The timeout was set to 1600~s.
This is repeated 10 times for every $G_n(i)$, outcoming 20 accumulated times shown in \fig{fig-exp1}.
Note that the time scale is \emph{logarithmic}.

Observe that \textsc{Regstar}\xspace terminates in about 100--200 seconds in all cases while \textsc{Baseline}\xspace reaches the timeout even for some $G_7(i)$ graphs and for \emph{all} $G_9(i)$ graphs.
This demonstrates that \textsc{Regstar}\xspace outperforms the \textsc{Baseline}\xspace.
When both algorithms terminate, the achieved protection values are about the same.

\subsection{Patrolling an ATM network}
\label{sec-Montreal}

We examine a patrolling graph where the vertices correspond to selected ATMs in Montreal (\fig{F:atms}).
All parameters of the graph are chosen in the same way as in \sect{sec-baseline}, except for $d(\tau)=2*\mathit{time}_{\max} +\mathit{time}_{\text{avg}}$ and imperfect intrusion detection, which is set randomly to a value between~0.8~and~1.

Note that the corresponding graph adjustment needed to run the \textsc{Baseline}\xspace results in more than
3 thousand auxiliary vertices, far beyond its limits. \citet{DBLP:conf/atal/KlaskaKLR18} claim that \textsc{Baseline}\xspace can solve instances with about 100 vertices.

The results achieved by \textsc{Regstar}\xspace are summarized in \tab{tab-experiment2}.
For $m = 1,\ldots,4$ we randomly generate 100 initial regular strategies where every vertex is assigned~$m$ memory elements.
We report the best and the average protection value achieved by \textsc{Regstar}\xspace, the percentage of runs for which the resulting value reached at least $90\%$ of the best value (labeled ``close''), and the average number of iterations and time needed by one \textsc{Regstar}\xspace run.

Note that even for $m=4$, the algorithm can improve one strategy in about~20 mins.
The number of runs for which the optimization produces a high-value strategy is consistently very high and increases with $m$.

\begin{table}[tbp]
	\centering\small
	\caption{Analysis of \textsc{Regstar}\xspace on Montreal's ATMs.}
	\begin{adjustbox}{max width=\linewidth}
	\begin{tabular}{ccccr@{\ }lr@{\ }l}
		\toprule
			$m$ & $\operatorname{RVal}_\text{best}$ & $\operatorname{RVal}_\text{avg}$ & close (\%) & \multicolumn{2}{c}{iter} & \multicolumn{2}{c}{time (s)} \\
			\midrule
			1 & 64 & $57\pm3$ & 46 & 280&$\pm$ 30  & 5&$\pm$ 1 \\
			2 & 75 & $70\pm2$ & 83 & 684&$\pm$ 41  & 79&$\pm$ 8 \\
			3 & 80 & $77\pm2$ & 100 & 1045&$\pm$ 60 & 360&$\pm$ 58 \\
			4 & 81 & $79\pm1$ & 100 & 1346&$\pm$ 75 & 1250&$\pm$ 196 \\
			\bottomrule
	\end{tabular}
	\end{adjustbox}
	\label{tab-experiment2}
\end{table}

\subsection{Patrolling an office building}

\begin{table*}[t]
	\centering
	\small
	\caption{Analysis of \textsc{Regstar}\xspace on office buildings.}
	\begin{tabular}{c|ccr@{\ }l|ccr@{\ }l|ccr@{\ }l}
		\toprule
  \multirow{2}{*}{$m$} &
  \multicolumn{4}{c|}{One floor}&
  \multicolumn{4}{c|}{Two floors}&
  \multicolumn{4}{c}{Three floors}\\
			    & $\operatorname{RVal}_\text{best}$ & close (\%) & \multicolumn{2}{c|}{time (s)}
                & $\operatorname{RVal}_\text{best}$ & close (\%) & \multicolumn{2}{c|}{time (s)}
                & $\operatorname{RVal}_\text{best}$ & close (\%) & \multicolumn{2}{c}{time (s)}\\
			\midrule
			1
        & 27 & \phantom{0}6  & $0.02$ & $\pm$ 0.01
        & 32 & 29 & $0.6$ & $\pm$ $ 0.5$
        & 29 & 3\phantom{.0}  &  $2$ & $\pm$ $1$\\
			2
        & 41 & 28 & $1.2$ &$ \pm$ $ 0.5$
        & 37 & 35 & $11$ &$ \pm$ $ 8$
        & 32 & 5\phantom{.0}  & $10$ & $ \pm$ $16$\\
			3
        & 44 & 84 & $4.8$ &$\pm$ $2.1$
        & 45 & 30 & $47$  & $\pm$ $44$
        & 44 & 0.5 & $78$ &$ \pm$ $142$\\
			4
        & 47 & 83 & $11.7$ &$ \pm$ $5.8$
        & 53 & \phantom{0}4  & $102$ &$ \pm$ $ 118$
        & 44 & 3\phantom{.0}  & $238$ &$ \pm$ $ 469$\\
			5
        & 47 & 75 & $24.7$ &$ \pm$ $ 14.2$
        & 56 & 12 & $236$ &$ \pm$ $ 283$
        & 50 & 0.5 & $286$ &$ \pm$ $ 635$\\
			6
        & 47 & 65 & $45.2$ &$\pm$ $ 32.8$
        & 57 & 11 & $268$ &$ \pm$ $ 420$
        & 55 & 0.5 & $641$ &$  \pm$ $ 1557$\\
			7
        & 51 & 45 & $74.8$ &$ \pm$ $ 64.8$
        & 58 & 18 & $543$ &$ \pm$ $ 877$
        & 53 & 1\phantom{.0}  & $1278$ &$  \pm$ $ 3414$\\
			8
        & 52 & 22 & $112.0$ &$ \pm$ $ 111.8$
        & 59 & \phantom{0}9  & $515$ &$ \pm$ $ 1116$
        & 56 & 1\phantom{.0}  & $1486$ &$  \pm$ $ 4466$\\
			\bottomrule
	\end{tabular}
	\label{tab-experiment3}
\end{table*}
We consider three office buildings with one, two, and three floors.
On each floor, there are ten offices alongside a corridor.
Stairs connect the floors on both sides of the corridors.

\label{sec-buildings}

\begin{figure}[tb]
\centering
\begin{tikzpicture}[scale=.5, every node/.style={scale=0.6}, x=1.7cm, y=1.25cm]
	\foreach \x in {1,2,3,4}{
        \foreach \y in {0,2,3,5,6,8}{
			\node [max] (r\x\y) at (\x,\y)  {};
        };
        \foreach \d/\y/\u in {0/1/2,3/4/5,6/7/8}{
			\node [stoch] (c\x\y) at (\x,\y)  {};
            \draw [tran,-] (c\x\y) -- node[left] {$5$} (r\x\u);
            \draw [tran,-] (c\x\y) -- node[left] {$5$} (r\x\d);
        };
    };
    \foreach \y/\f in {1/{$1^{\textit{st}}$},4/{$2^{\textit{nd}}$},7/{$3^{\textit{rd}}$}}{
        \node [max] (r0\y) at (0,\y)  {};
        \node [max] (r5\y) at (5,\y)  {};
        \draw [tran,-] (r0\y) -- node[above] {$5$} (c1\y);
        \draw [tran,-] (r5\y) -- node[above] {$5$} (c4\y);
        \node at (6,\y) {\f \textrm{ floor}};
        \foreach \x/\r in {1/2,2/3,3/4}{
           \draw [tran,-] (c\x\y) -- node[above] {$2$} (c\r\y);
        }
    }
    \draw [tran,-,rounded corners] (c11) -- +(-.7,1) -- node[left] {10} +(-.7,2) -- (c14);
    \draw [tran,-,rounded corners] (c14) -- +(-.7,1) -- node[left] {10} +(-.7,2) -- (c17);
    \draw [tran,-,rounded corners] (c41) -- +(.7,1) -- node[right] {10} +(.7,2) -- (c44);
    \draw [tran,-,rounded corners] (c44) -- +(.7,1) -- node[right] {10} +(.7,2) -- (c47);
\end{tikzpicture}
\caption{A building with three floors connected by stairs.}
\label{fig-building}
\end{figure}

The building with three floors is shown in \fig{fig-building}.
The squares represent the offices, and the circles represent the corridor locations where the Defender may decide to visit the neighbouring offices.
The ``long'' edges represent stairs.
Every office's cost is set to 100, and the probability of successful intrusion detection is 0.9.
The time needed to complete an intrusion is set to 100, 200, and 300 for the building with one, two, and three floors, respectively.

The outcomes achieved by \textsc{Regstar}\xspace are summarized in \tab{tab-experiment3}.
For every building and every \mbox{$m\in\{1,\ldots,8\}$}, 200 runs were processed with
all nodes having $m$ memory elements.
We report the best value found, the percentage of runs for which the resulting value reached at least $90\%$ of the best value (labeled ``close''), and the average runtime.

We observe that the achieved protection substantially increases with more memory elements.
This is because the considered patrolling graphs are relatively sparse, and ``remembering'' the history of previously visited vertices is inevitable for arranging optimal moves.
In contrast, the patrolling graphs of ATM networks presented in \sect{sec-Montreal} are fully connected, and the extra memory elements have not brought many advantages.

The \textsc{Regstar}\xspace algorithm discovers the relevant information about the history fully automatically.
To examine this capability, we again consider the building with one floor, but we change the probability of successful intrusion detection to~1 and increase the attack time to~112 units.
This is \emph{precisely} the time the Defender needs to visit every target before an arbitrary attack is completed to achieve a \emph{perfect} protection equal to 100.
The Defender must schedule his walk to visit every office precisely once and with appropriate timing.

This experiment (see \tab{tab-experiment4}) show that \textsc{Regstar}\xspace can indeed discover this ``clever'' walk.
For every $m\in\{1,\ldots,8\}$, 500 runs were processed.
The third column shows the percentage of runs resulting in a perfect protection strategy.
Observe that \emph{four} memory elements are sufficient to achieve perfect protection, and the chance of discovering a perfect strategy further increases with more memory elements.

\begin{table}[t]
	\centering
	\footnotesize
	\caption{Reaching perfect protection for a one-floor office building with tight attack time.}
	\begin{tabular}{cccr@{\ }l}
		\toprule
		 $m$ & $\operatorname{RVal}_\text{best}$ & close (\%) & \multicolumn{2}{c}{time (s)} \\
			\midrule
			1 & \phantom{0}34  & \phantom{11.}0    & 0.05 &$\pm$ 0.03   \\
			2 & \phantom{0}50  & \phantom{11.}0    & 2.1  &$\pm$ 1.0   \\
			3 & \phantom{0}55  & \phantom{11.}0    & 8.6  &$\pm$ 4.8   \\
			4 & 100 & \phantom{1}1.2  & 20   &$\pm$ 13   \\
			5 & 100 & \phantom{1}5.0  & 37   &$\pm$ 31   \\
			6 & 100 & 12.2 & 73   &$\pm$ 67   \\
			7 & 100 & 11.8 & 107  &$\pm$ 122   \\
			8 & 100 & \phantom{1}8.6  & 119  &$\pm$ 180   \\
			\bottomrule
	\end{tabular}
	\label{tab-experiment4}
\end{table}

\section{Conclusion}
\label{sec-concl}

Our efficient and differentiable regular-strategy evaluation algorithm proved to apply to patrolling graphs with arbitrary edge lengths and imperfect intrusion detection.
The experimental results are encouraging and indicate that high-quality Defender's strategies can be constructed by optimization methods in a reasonable time for real-world
scenarios.

Our experiments also show that the current optimization methods do not often converge to the best possible strategy.
This suggests that an extra performance could be gained in exploration and improvement on the optimization side.

In Theorem~\ref{thm-reg}, we proved that regular strategies \emph{approximate} the optimal strategy to arbitrary precision $\varepsilon>0$. The needed memory size depends on $\varepsilon$. We evaluated various memory sizes $m$ experimentally from $m=1$ up to the highest computable values in \sect{sec-Montreal} and \sect{sec-buildings}. Finding the best $m$ (or even proving that regular strategies achieve the optimality) is a challenging open problem.

\paragraph*{Acknowledgment}

Research was sponsored by the Army Research Office and was accomplished under
Grant Number W911NF-21-1-0189.
This work was supported from Operational Programme Research, Development and
Education - Project Postdoc2MUNI (No.\ CZ.02.2.69/0.0/0.0/18\_053/0016952).

\paragraph*{Disclaimer}

The views and conclusions contained in this document are those of the authors
and should not be interpreted as representing the official policies, either
expressed or implied, of the Army Research Office or the U.S.\ Government. The
U.S.\ Government is authorized to reproduce and distribute reprints for
Government purposes notwithstanding any copyright notation herein.

\clearpage

redpajama_set_name: RedPajamaArXiv


text:
\section{The results}
\vspace{6mm}
\centerline{\bf 3.~Results}
\vspace{2mm}

Here, we present some results for the total \crss\ and effective $ab$-mass
spectra in different channels $\gamma p\to (ab)p$ , estimated in the models
of Section~2. We calculate only resonance amplitudes, i.e., the final $ab$
system is produced from $a_0/f_0$ decays, and neglect any possible
background terms to the $\gamma p\to (ab)p$ amplitudes. However, it is
interesting to compare the results for the \crss\ obtained using different
approaches.

\vspace{2mm}
\centerline{\bf 3.1~Cross sections}
\vspace{2mm}

First, we obtain the predictions from Model~A; then, we have the radiative
widths $\Gamma(S\to\gamma V)$ to input into the calculation of the $\ssvg$
vertices $I_{\svg}$ in Eq.~(\ref{2}). Here, we may use the results from the
quark model used in Ref.~\cite{Donn}. In this model, assuming the $a_0$
and $f_0$ mesons to be $q\bar q\,(^3P_0)$  states, one obtains results which
depend on the $q\bar q$ flavor configuration.  For the isovector state
$a^0_0=(u\bar u-d\bar d)/\sqrt{2}$~ this gives
\be
	\Gamma(a_0\to\gamma\omega)=125~{\rm keV},~~~
	\Gamma(a_0\to\gamma\rho)=\frac{1}{9}\,\Gamma(a_0\to\gamma\omega)=14~{\rm keV}.
	\label{11}
\ee
Considering three different $q\bar q$ configurations for the isoscalar $f_0$ meson,
denoted as
\be
	f_0(1)=\frac{1}{\sqrt{2}}\,(u\bar u\!+\!d\bar d),~~
	f_0(2)=\frac{1}{\sqrt{6}}\,(u\bar u\!+\!d\bar d\!-\!2s\bar s),~~
	f_0(3)=\frac{1}{\sqrt{3}}\,(u\bar u\!+\!d\bar d\!+\!s\bar s),
	\label{12}
\ee
one has
\be
	\ba{l}
	\Gamma(f_0(1)\!\to\!\gamma\rho)=3\,\Gamma(f_0(2)\!\to\!\gamma\rho)=
	\frac{3}{2}\Gamma(f_0(3)\!\to\!\gamma\rho)=\Gamma(a_0\!\to\!\gamma\omega),
	\\ \rptt
	\Gamma(f_0(1)\!\to\!\gamma\omega)=3\,\Gamma(f_0(2)\!\to\!\gamma\omega)=
	\frac{3}{2}\Gamma(f_0(3)\!\to\!\gamma\omega)=\Gamma(a_0\!\to\!\gamma\rho).
	\ea
	\label{13}
\ee
The case $f_0=s\bar s$ gives
$\Gamma(f_0\!\to\!\gamma\rho/\omega)\sim\sin^2\theta$, where $\theta$ is
the $\phi-\omega$-mixing angle. The angle $\theta$ is assumed to be small
and this case is not considered here.

The \crss\ $\sigma(ab)$ (in $\mu b$) for different channels are shown in
Table~1.
The results of Model~A are given for three variants 1), 2), and 3), where
$f_0$ is taken as the $f_0(1)$, $f_0(2)$ and $f_0(3)$ states, respectively.
The \crs\ $\sigma(\pi^0\eta)$ slightly depends on the variants of the $f_0$
states (\ref{12}) due to $a_0-f_0$ mixing, while the main contribution comes
from the $a_0$-production amplitudes. The \crss\ $\sigma(\pi\pi)$ are mainly
determined by the $f_0$-production terms, and are more sensitive to the
$f_0$ variants (\ref{12}).  Models~B and C give comparable values for the
\crs\ but much smaller ones than those obtained from Model~A.

\vspace{2mm}
\begin{center}
\centerline{Table 1}
\vspace{1mm}
\centerline{Cross section $\sigma(ab)$ in $\mu b$ for the photoproduction
 of the meson pair $ab$}
\centerline{via $f_0$ and $a_0$ at $\ega=1.6$~GeV, for the models
 described in the text.}
\vspace{2mm}

\begin{tabular}{|c|c|c|c|c|}
\hline\rpt Model & $\pi^0\eta$ &  $\pi^0\pi^0$ & $\pi^+\pi^-$ & $K^+K^-$
\\
\hline\rpt ~~~~1) & 12.21 & 2.59 & 5.12 & 2.58 \\
 A,~2) & 12.08 & 0.86 & 1.70 & 1.28 \\
 ~~~~3) & 12.15 & 1.73 & 3.42 & 1.97
\\
\hline\rpt B & 0.234 & 0.093 & 0.184 & 0.083
\\
\hline\rpt C & 0.444 & 0.070 & 0.138 & 0.072
\\ \hline\end{tabular}\end{center}

For some comparison with existing data we present in Fig.~\ref{fig:as}
the cross section $\sigma(\pi^0\eta)$ versus total centre-of-mass energy
$\sqrt{s}=W(\gamma p)$ in Model~B for two sets of $a_0/f_0$ parameters
(solid and dashed curves, see figure caption).  Here, open circles show
the $a_0(980)p$ contribution to the $\pi^0\eta p$  channel, obtained
through a partial-wave analysis (PWA) of the data on $\gamma p\to\pi^0\eta
p$ in Ref.~\cite{Horn}. Thus, the model results essentially depend on
$a_0/f_0$ parameters, but Model~B is in rough agreement with the ``data"
(open circles). The cross sections from Model~A are too large and not
shown in Fig.~\ref{fig:as}. Note also that $W(\gamma p)=1.97$~GeV for
the energy of interest $\ega=1.6$~GeV.

Concerning the other channels, there are recent CLAS high-statistics data
on the reaction $\gamma p\to \pi^+\pi^- p$ at $\ega=3.0-3.8$~GeV~\cite{Batta}.
The PWA results of Ref.~\cite{Batta} give, in particular, the contribution
of the $s$-wave system $(\pi^+\pi^-)_s$ with clear evidence of the $f_0(980)$
structure.  One should also mention the old hydrogen $\gamma p\to K^+K^-p$
data~\cite{Barber}, where the $s$-wave $(K^+K^-)_s$ cross section and
possible contributions of a scalar resonance ($M_{\pi\pi}\sim 1$~GeV) were
estimated.

Generally, the photoproduction processes of scalars should be analyzed in
the full approach which incorporates the resonance and background terms
and utilizes unitarity. For example, the background tree
$\rho,\omega$-exchange amplitudes for $\pi\pi$, $\pi\eta$, and $\eta\eta$
channels were taken into account in Ref.~\cite{Donn}, and their contribution
was found to be comparable with the resonance terms in the corresponding mass
intervals. Analogous tree amplitudes supplemented with $s$-wave meson-meson
final state interaction (FSI) were considered for the $\pi\pi$ and $K\bar K$
photoproduction in Refs.~\cite{Szczepan}, where the cross sections for
$s$-wave $(\pi\pi)_s$ and $(K\bar K)_s$ pairs were estimated.

In the present paper, we leave the inclusion of such background
processes for future work and study the $a_0-f_0$-mixing effect which
is produced by the resonance amplitudes.

\vspace{3mm}
\centerline{\bf 3.2~Mass spectra}
\vspace{2mm}

The results for the total \crss\ given in Table~1 exhibit a strong
model dependence, but are only weakly sensitive to the $a_0-f_0$ mixing.  As
mentioned above, the $a_0f_0$ vertex $\lambda$~(\ref{8}) sharply depends
on the mass $W$ and peaks close to the $K\bar K$ thresholds.

The mass spectra for the two channels $\pi^0\eta$ and $\pi^+\pi^-$ at the
beam-photon energy $\ega=1.6$~GeV are presented in Fig.~\ref{fig:6}. The
results are given for two models, A (variant 1) and B with the $a_0/f_0$
parameters from the ``KK" version~(see, Eqs.~(A.4)).  All the plots in
Fig.~\ref{fig:6} exhibit two kinds of phenomena: the ``cusp" effects at
the $K\bar K$ thresholds and $a_0-f_0$-mixing. The latter is seen as the
differences of solid and dashed curves. The ``cusp" effects look more
pronounced in the $\pi\pi$ channel than in the $\pi\eta$ one, essentially
because the $f_0$ has larger coupling to the $K\bar K$ channels than the
$a_0$.

Models~A and B in Fig.~\ref{fig:6} give quite similar shapes of mass
spectra. To get some view of model dependence of the results, we present
some other predictions for the same channels in Fig.~\ref{fig:7}.  The
plots $a$ and $b$ show the mass spectra obtained in Model~A (variant 2,
i.e., $f_0=f_0(2)$ in Eq.~(\ref{12})) with the same ``KK" variant of
the $a_0/f_0$ parameters. Here, since the radiative widths
$\Gamma(f_0\!\to\!\gamma\rho/\omega)$ for $f_0(2)$ is 3 times smaller
than for $f_0(1)$, the $d\sigma/dM(\pi\pi)$ is also getting $\sim 3$
smaller in comparison with that in plot $b$ of Fig.~\ref{fig:6}.

The plots $c$ and $d$ in Fig.~\ref{fig:7} show the results from Model~A
(variant~1), but with the no-structure (``NS") variant of the $a_0/f_0$
parameters. In the ``NS" version, both constants $g_{aK^+K^-}$ and
$g_{fK^+K^-}$ are smaller (the latter by $\sim$ one order of magnitude)
than their ``KK"- version values (see Eqs.~(A.4)). Thus, the ``cusp"
effects as well as the $a_0-f_0$-mixing (note that the $a_0f_0$
vertex~(\ref{8}) $\lambda\sim g_{aK^+K^-}g_{fK^+K^-}$) are hardly
visible in this case.

Fig.~\ref{fig:8} shows the effective $K^+K^-$ mass spectra in the reaction
$\gamma p\!\to\!(K^+K^-)p$ at the same photon energy. Here we give the
results of the same four variants of the model calculations as in
Figs.~\ref{fig:6} and~\ref{fig:7} (see figure caption).  Plot $d$ shows
the results obtained with the ``NS" version of the $a_0/f_0$ parameters.
$a_0-f_0$-mixing is also suppressed here due to smaller couplings of
the resonances to the $K\bar K$ channels.  Thus, we see that the IB
$a_0-f_0$-mixing effect essentially depends on the $a_0/f_0$
parameters, in particular on the $a_0$ and $f_0$ couplings to the
$K\bar K$ channel.

  From an experimental point of view, one can not measure the reaction
discussed with ``switched off" isospin-breaking effects in order to
observe any difference in the mass spectra like those between the
solid and dotted curves in Figs.~\ref{fig:6}-\ref{fig:8}. Thus, we
also need to study the charged channels, where mixing is absent, say,
$a^+_0$ photoproduction in $\gamma p\!\to\!(\pi^+\eta)n$, in parallel
with the neutral channels to compare the results.

\vspace{5mm}
\centerline{\bf 4.~Conclusion}
\vspace{3mm}

The photoproduction of the neutral scalars $a_0(980)$ and $f_0(980)$ on
a proton target at energies close to threshold were considered in
the $\pi\eta$, $\pi\pi$, and $K\bar K$ channels. The main aim of the
paper is to study the possibility of observing $a_0-f_0$ mixing in
these processes.  Several models of $a_0/f_0$ photoproduction were
considered with $a_0-f_0$ mixing included through the $K\bar K$-loop
mechanism of $a_0-f_0$ transition. The total cross sections of
different channels were estimated and appeared to be very model
dependent. Model~B, incorporating $\rho$ and $\omega$-exchange
diagrams and a $K\bar K$-loop mechanism for $a_0/f_0$ photoproduction,
demonstrates rough agreement with the data on the $a_0$ contribution
to the $\gamma p\to\pi^0\eta p$ cross section.

The two-meson mass spectra are examined for observation of
$a_0-f_0$-mixing. The most interesting case is the $\gamma p\to\pi^0\eta
p$ channel.  Here, the $\pi^0\eta$-effective-mass spectrum demonstrates
a sharp (mixing) effect (Fig.~\ref{fig:6}), i.e., rapid behavior of
the $d\sigma/dM$ in the narrow ($\sim 8$~MeV) mass interval, for the
case of $a_0/f_0$ parameters, taken from ``kaon loop" fits of
Refs.~\cite{KLO1,KLO2}. The effect is sensitive to the $a_0/f_0$
parameters.

Both aspects, the $\ssvg$ vertex $I_{\svg}$ (see Eq.~(\ref{2})), which
affects the photoproduction cross section of scalars, and the
$a_0-f_0$-mixing vertex $\lambda$ (\ref{8}), are important to understand
the nature of scalar mesons $a_0(980)$ and $f_0(980)$. We expect this
study to be continued in a more complete model, incorporating also
the background amplitudes for the given channels.

\vspace{3mm}
\centerline{\bf Acknowledgments}
\vspace{3mm}

The authors are thankful to M.~Amaryan and S.~Prakhov for many
useful discussions concerning the experimental possibilities to
measure $a_0/f_0$ photoproduction and E.~Oset for useful references.
This work was supported in part by the U.S. Department of Energy
Grant No.~DE--FG02--99ER41110 and the DFG under grant SFB 1044.
A.~E.~K. thanks grant NS--3172.2012.2 for partial support.

\vspace{3mm}
\begin{flushright}
{\bf Appendix}
\end{flushright}

\centerline{\bf A.1~Scalar meson propagators}
\vspace{2mm}

The propagators of scalars reads
$$
	G_S=(W^2-m^2_S+iW\,\Gamma_S(W))^{-1},
~~~~
	\Gamma_S(W)=\sum_{ab}\Gamma_{sab}(W).
\eqno{(\rm A.1)}
$$
The total width $\Gamma_S(W)$ is the sum of partial widths
$\Gamma_{sab}(W)$ of the $s$-wave decays $S\!\to\!ab$, and
$$\Gamma_{\!sab}(W)=\frac{g^2_{sab} q_{ab}}{8\pi W^2},~~~~~
ab=\biggl\{
\ba{ll}
	\pi^0\eta,\,K^+\!K^-\!,\,K^0\bar K^0 & (S=a^0_0) \\
	\pi\pi\!,~~\,K^+\!K^-\!,\,K^0\bar K^0 & (S=f_0)
\ea.
	\eqno{(\rm A.2)}
$$
Here, $g_{sab}$ is the coupling constant of the scalar $S$ to $ab$ channel;
$$
	q_{ab}=\sqrt{\frac{1}{4W^2}\,(W^2\!-m^2_+)(W^2\!-m^2_-)+i0},~~~~~
	m_{\pm}=m_a\pm m_b,
\eqno{(\rm A.3)}
$$
where $q_{ab}$ is the relative momentum in the $ab$ system with
effective mass $W$, and $m_a$ ($m_b$) is the mass of particle $a$ ($b$).
The value $q_{ab}$ in Eq.~(A.3) is also defined in the region below
threshold, i.e., $q_{ab}=i|\,q_{ab}|$ at $W\!<\!m_a\!+\!m_b$.

The $a_0(980)$ and $f_0(980)$ parameters are taken from the analyses
of $\phi(1020)\!\to\!\pi^0\eta\gamma$~\cite{KLO1} and
$\phi\!\to\!\pi^0\pi^0\gamma$~\cite{KLO2}. The results were obtained
for two variants of fits -- ``kaon loop" (``KK") and ``no structure"
(``NS") models:

$$
\ba{llcl}
{\rm ``KK"}\!\!: & m_a\!=983~{\rm MeV}, & g_{a\pi\eta}=2.8~{\rm GeV}, &
                     g_{aK^+K^-}\!=2.16~{\rm GeV};
\\ \rptt
{\rm ``KK"\!\!}: & m_f\!=976.8~{\rm MeV}, & g_{f\pi^+\pi^-}\!=-1.43~{\rm GeV}, &
                  g_{fK^+K^-}\!=3.76~{\rm GeV};
\\ \rptt
{\rm ``NS":} & m_a\!=983~{\rm MeV}, & g_{a\pi\eta}=2.2~{\rm GeV}, &
                     g_{aK^+K^-}\!=1.57~{\rm GeV};
\\ \rptt
{\rm ``NS"}\!: & m_f\!=984.7~{\rm MeV}, & g_{f\pi^+\pi^-}\!=1.31~{\rm GeV}, &
g_{fK^+K^-}\!=0.40~{\rm GeV}
\ea
\eqno{(\rm A.4)}
$$
($g_{aK^0\bar K^0}\!=-g_{aK^+K^-}$,~ $g_{fK^0\bar K^0}\!=g_{fK^+K^-}$).

\vspace{3mm}
\centerline{\bf A.2~Reaction amplitude squared}
\vspace{2mm}

{\bf Models~A,B}.
The reaction amplitude $M$ can be written as
$$
	M=\bar u_2(A+\hat B)u_1,
	\eqno{(\rm A.5)}
$$
where
$$
	A=a_1[(\eps k)(q,p_1+p_2)-(qk)(\eps,p_1+p_2)],~~~~
	\hat B=a_3[(\eps k)\hat q-(qk)\hat\eps],
$$ $$
	a_1=\sum_{S,V} \frac{G_S\, g_{sab}f_V}{t-m^2_V}\,I_{SV},~~~
	a_2=\sum_{S,V} \frac{G_S\, g_{sab}g_V}{t-m^2_V}\,I_{SV},~~~
	a_3=2ma_1+a_2.
$$
The modulus squared of the amplitude for unpolarized particles
reads
$$
	\overline{|M|^2}=\frac{1}{2}\,{\rm Tr}\,
	\{(A^*\!+\hat B^*)(\hat p_2\!+m)((A\!+\hat B)(\hat p_1\!+m)\}
	~~~ (\hat B^*\!\equiv B^*_{\mu}\gamu),
	\eqno{(\rm A.6)}
$$
where the trace Tr$\{\cdots\}$ is averaged over photon polarizations.
To simplify calculations we impose gauge condition $\eps_0\!=\eps_3\!=0$
on the photon four-vector $\eps$. Thus, the total set of useful scalar
products with four-vector $\eps$ is
$$
	(\eps q)=(\eps p_1)=0,~~ (\eps p_2)=-(\eps k)=(\beps \bfk_{\perp}),~~ \eps^2=-1.
	\eqno{(\rm A.7)}
$$
Finally, from Eq.~(A.6), making use of Eq.~(A.7), we arrive at
$$
	\overline{|M|^2}=2(\,|\,a_2|^2\!-|\,a_1|^2 t) (qp_{1\!})^2 k^2_{\perp}-|\,a_3|^2 (qk)^2 t,
	\eqno{(\rm A.8)}
$$
where substitution $(\eps k)^2\to\half k^2_{\perp}$ is used for unpolarized photon.
The factors $(qp_{1\!})^2 k^2_{\perp}$ and $(qk)^2$ in Eq.~(A.8) can be written as
$$
(qp_{1\!})^2 k^2_{\perp}=\frac{1}{4}s(t_2-|t|)(|t|-t_1),~~~~
(qk)^2=\half(W^2-t),
$$
where $t_1$ and $t_2$ are the kinematical boundaries for $|t|$ ($t_1\!<\!|t|\!<\!t_2$).

\vspace{2mm}
{\bf Model~C}.
Making use of Eqs.~(A.7) and Dirac equations for nucleon spinors $u_1$ and
$\bar u_2$, one can rewrite the amplitude in Eq.~(\ref{7}) in the form
$$
	M=\bar u_2\left[\,2a_u (\eps p_2)+(a_s+a_u)\,\hat q\hat\eps\,\right]u_1.
	\eqno{(\rm A.9)}
$$
Calculations for unpolarized particles give
$$
	\overline{|M|^2}=4\left[\,|\,a_s\!+\!a_u|^2(qp_1)(qp_2)+
	k^2_{\perp} [\,|\,a_u|^2(m^2\!+(p_1,p_2\!-q))-{\rm Re}(a^+_sa_u)(qp_1)]\right].
	\eqno{(\rm A.10)}
$$

\newpage
\vspace{3mm}
\centerline{\bf A.3~Loop function $I(a,b)$}
\vspace{2mm}

The loop function $I(a,b)$, which enters the $\ssvg$ vertex $I_{svg}$
in Eq.~(\ref{6}), can be written as the integral
$$
	I(a,b)=\int\limits^1_0 dz \int\limits^{1-z}_0 dy \frac{yz}{c-i0},~~~
	c=1-z(1-z)a-yz(b-a).
$$
Calculations give (see, also \cite{Close,Donn})
$$
	I(a,b)=\frac{1}{2(a-b)}+\frac{a}{2(a-b)^2}\,[J(b)-J(a)]
      +\frac{1}{2(a-b)^2}\,[f(b)-f(a)],
	\eqno{(\rm A.11)}
$$
where
$$
\ba{lll}
	1)~J(a)=x(L-i\pi), & f(a)=-(L-i\pi)^2, & (a>4);
	\\ \rptt
	2)~J(a)=2xA, & f(a)=4A^2,  & (0<a<4);
\\ \rptt
	3)~J(a)=xL, & f(a)=-L^2, & (a<0);
	\ea
$$
$$
	x=\sqrt{\left|\frac{a-4}{a}\right|},~~~ L=\ln\left|\frac{1+x}{1-x}\right|,
	~~~A=\arcsin\frac{\sqrt{a}}{2}.
$$

\newpage
\centerline{\bf References}
\vspace{-15mm}