# Optimal Persistent Monitoring of Mobile Targets in One Dimension

Division of Systems Engineering
Boston University Jonas Hall1, Sean Andersson1,2, Christos G. Cassandras1,3
This work was supported in part by NSF under grants ECCS- 1931600,
DMS-1664644, CNS-1645681, CNS-2149511, by AFOSR under FA9550-19-1-0158, by
ARPA-E under DE-AR0001282, by NIH under 1R01GM117039-01A1, and by the
MathWorks.1Division of Systems Engineering, Boston University, USA2Division of
Mechanical Engineering, Boston University, USA3Department of Electrical and
Computer Engineering{hallj, sanderss<EMAIL_ADDRESS>
###### Abstract

This work shows the existence of optimal control laws for persistent
monitoring of mobile targets in a one-dimensional mission space and derives
explicit solutions. The underlying performance metric consists of minimizing
the total uncertainty accumulated over a finite mission time. We first
demonstrate that the corresponding optimal control problem can be reduced to a
finite-dimensional optimization problem, and then establish existence of an
optimal solution. Motivated by this result, we construct a parametric
reformulation for which an event based gradient descent method is utilized
with the goal of deriving (locally optimal) solutions. We additionally provide
a more practical parameterization that has attractive properties such as
simplicity, flexibility, and robustness. Both parameterizations are validated
through simulation.

##  I Introduction

In persistent monitoring problems, a team of autonomous agents is tasked to
monitor a given environment. The problem is closely related to coverage
control [1], the key difference being that the environment is assumed to
change dynamically, so that all points of interest must be revisited
persistently. The problem has received a lot of attention over the last decade
due to its broad applicability across a range of applications, including
environmental monitoring [2], data harvesting [3], and particle tracking [4].
Persistent monitoring problems are notoriously difficult to solve because of
highly non-convex and non-smooth costs and dynamics along with the
computational complexity due to the problem’s combinatorial nature.

In this paper we consider the persistent monitoring problem applied to a
finite number of targets in a one-dimensional connected mission space, similar
to the formulations in [5, 6]. One-dimensional mission spaces are common in
applications that involve rivers, roads in a transportation network, or power
lines, to name a few. Unlike previous work, however, in addition to an
internal state describing a measure of uncertainty, we allow _the targets
themselves to be mobile_ in the mission space. The control objective
considered is the minimization of the overall uncertainty over a finite
mission time. The uncertainty dynamics considered in this work can be viewed
as a flow model with constant input flow, whereas the output flow depends on
the target-agent distance. This model is commonly used in the literature [7,
5], though other dynamics have been discussed as well. For example, in [8],
the authors consider internal states with arbitrary linear time-invariant
dynamics, with a control applied only when an agent is monitoring the target.
In other applications, such as environmental monitoring tasks, the internal
state is modeled as a Gaussian random field [9]. Similarly, the literature
contains various performance metrics, e.g., that of maximizing the number of
observed events [2], minimizing the inter-observation time [10], or minimizing
estimation errors [9].

The persistent monitoring problem is often split into a higher and lower
level. The higher level consists of path planning and scheduling target
visiting sequences. Lan and Schwager proposed the use of rapidly-exploring
random cycles in order to find an optimal periodic trajectory [9]. Other
formulations abstract the mission space to a graph, where each node represents
a region of interest and the edges capture the travel times [10, 11]. The
graph-based formulation was further generalized in [12], in which targets were
grouped into clusters and only a single target within each cluster must be
visited. Due to the combinatorial nature of the scheduling task, the use of
mixed-integer optimization is natural [13], and its similarity to the
Traveling Salesman Problem has motivated solving the higher level scheduler
with such methods [14]. On the lower level, the problem consists of optimizing
the agents’ motion control, either along a given path, or in order to realize
a given schedule. For example, in [5] and [15], the authors optimize agent
velocities along a given path, while in [16] a configuration-based solution is
sought such that each point on a given path is revisited with a constant
frequency.

The contribution of this paper consists of advances in the one-dimensional
persistent monitoring problem of mobile targets. In particular, we prove that
the considered infinite-dimensional Optimal Control Problem (OCP) can be
reduced to an optimization problem of finite dimension, and that the OCP
always admits a solution. Though similar results can be found for static
targets, we provide novel (to the best of the authors’ knowledge) results for
mobile targets. Additionally, we provide two parametric reformulations and
utilize the Infinitesimal Perturbation Analysis (IPA) method [17] in order to
compute gradients and solve the parametric optimization problem locally.

The remainder of this paper is structured as follows. Sec. II introduces the
problem in detail and establishes the OCP (3). In Sec. III, we show how the
problem can be reduced to a finite-dimensional optimization problem. Two
parametric formulations are provided and compared in Sec. IV. By applying the
IPA calculus, we describe how perturbations of the parameters affect the cost
function in Sec. V. We also compare the parameterizations in numerical
experiments in Sec. VI. Sec. VII concludes the paper and outlines ideas for
future work.

##  II Problem Formulation

Our problem formulation builds upon the foundation of [7, 6], extending it to
include _mobile_ targets. Let $\mathcal{S}=\mathbb{R}$ be the work space in
which we consider the persistent monitoring problem over a finite time
interval $[0,T]$. We introduce a set of mobile agents
$\mathcal{A}=\\{1,2,\dots,N\\}$, and denote the position of agent
$j\in\mathcal{A}$ by $s_{j}(t)\in\mathcal{S}$. We assume that the agents
follow first-order dynamics $\dot{s}_{j}(t)=u_{j}(t)$, where each $u_{j}$
belongs to the admissible control set $\mathcal{U}=\\{[0,T]\to[-1,1]\\}$, and
the initial position $s_{j}(0)\in\mathcal{S}$ is given. In addition to the
agents, there is a set of mobile targets $\mathcal{T}=\\{1,2,\dots,M\\}$, and
we denote by $\vartheta_{i}(t)$ and $\dot{\vartheta}_{i}(t)$ the position and
velocity of $i\in\mathcal{T}$ at $t\in[0,T]$. The monitoring function of agent
$j$ for target $i$ is given by

$p_{ij}(\vartheta_{i}(t),s_{j}(t))=\max\left\\{0,1-\frac{|\vartheta_{i}(t)-s_{j}(t)|}{r_{j}}\right\\},$
(1)

where $r_{j}>0$ is the sensing range of agent $j$. The joint monitoring
function of target $i$ from all agents is then

$P(\vartheta_{i}(t),s(t))=1-\prod_{j\in\mathcal{A}}\left(1-p_{ij}(\vartheta_{i}(t),s_{j}(t))\right).$
(2)

The question remains of what is being monitored. We associate each target with
an internal state $R_{i}(t)\geq 0$ describing a measure of uncertainty. This
state is assumed to grow with a constant rate of $A_{i}>0$ when not monitored,
and to change with a dynamic rate of $A_{i}-B_{i}P(\vartheta_{i}(t),s(t))$ for
a given $B_{i}>A_{i}$ otherwise. To ensure that the uncertainty remains
nonnegative, we limit the uncertainty reduction for targets in the set
$\mathcal{Z}(t)=\\{i\in\mathcal{T}\mid
R_{i}(t)=0\mathrm{~{}and~{}}A_{i}<B_{i}P(\vartheta_{i}(t),s(t))\\}$. Thus, the
uncertainty dynamics are captured by

$f_{R_{i}}(t)=\begin{cases}0,&\mathrm{~{}if~{}}i\in\mathcal{Z}(t),\\\
A_{i}-B_{i}P(\vartheta_{i}(t),s(t)),&\text{otherwise}.\end{cases}$ (3)

The goal of the persistent monitoring problem is to minimize the overall
uncertainty, i.e., we seek a control policy which solves the OCP u ∈U^NJ(u) =
1T ∫_0^T ∑_i ∈T R_i(t) dt ˙s(t)= u(t), ˙R(t) = f_R(t).

Note that the function (3) depends on time only through $s(t)$, $R(t)$, and
$\vartheta(t)$. However, to keep notation simple, we neglect the explicit
dependence on the states, noting only that it is a function of time. This
convention will be used throughout the paper.

###### Remark 1

The choice of the monitoring function is not restricted to (1). Any monitoring
function can be chosen, as long as it a) has compact support, and b) is
monotonically increasing with the distance between its arguments. Similarly,
the results in this paper directly extend to other joint monitoring functions,
as long as they are monotonically increasing with each of the individual
monitoring functions, e.g.,
$\max_{j\in\mathcal{A}}p_{ij}(\vartheta_{i}(t),s_{j}(t))$.

##  III Optimal Control Characterization

As in previous work [6], a standard Hamiltonian analysis can be applied to (3)
to reveal that the optimal control can be expressed in a parametric form. To
better understand the structure of the problem, however, here we show the
existence of such a parametric reformulation directly. In order to prove the
main result in Thm 1 below, we first show that any control law can be adapted
to one of the form given in (4) without increasing the cost. Applying this
result repeatedly shows that any control can be replaced by one which can be
partitioned into a finite number of intervals during which the control is
either a) constant and maximal, or b) equal to the velocity of a target. From
this we conclude that there exists a compact parameter space, with which we
can ultimately show the existence of a parametrically represented optimal
control. These theoretical results rely on the following assumptions for the
motions of the targets.

###### Assumption 1

For all $t\in[0,T]$, $i,i_{1}\neq i_{2}\in\mathcal{T}$, we assume that (i)
target velocities are no larger than the maximal speed of the agents, i.e.,
their absolute velocities are bounded by one, and (ii) agents never sense two
targets at the same time, i.e., there exists $\Delta^{\mathrm{min}}>0$ such
that $|\vartheta_{i_{1}}(t)-\vartheta_{i_{2}}(t)|\geq
2\max_{j\in\mathcal{A}}\\{r_{j}\\}+\Delta^{\mathrm{min}}.$

The first assumption is fundamental, whereas the second one is of a technical
nature, without which it becomes increasingly difficult to characterize the
optimal control. However, in Sec. VI we show that the considered
parameterizations are adaptable to simultaneous sensing scenarios. Similarly,
if a target’s velocity exceeds the target control bounds, then the given
parameterization with bounded controls provides a heuristic for the more
general case. Our first lemma provides a characterization of the optimal
control over a fixed interval. Before we begin, let us denote by
‘$\mathrm{sgn}$’ the sign function that maps all negative real numbers to
negative one, zero to zero, and all positive real numbers to one.

###### Lemma 1

Let $(u,s)$ be any feasible control-trajectory pair. Consider an interval
$(t_{1},t_{2})$ over which the agent $j\in\mathcal{A}$ only ever senses one
target $i\in\mathcal{T}$. Then, there exist
$\check{t},\hat{t}\in[t_{1},t_{2}]$ such that the modified control law

$u_{j}^{\prime}(t)=\begin{cases}u_{j}(t),&\mathrm{~{}if~{}}t\notin(t_{1},t_{2}),\\\
\mathrm{sgn}\left(\vartheta_{i}(t_{1})-s_{j}(t_{1})\right),&\mathrm{~{}if~{}}t\in(t_{1},\check{t}),\\\
\dot{\vartheta}_{i}(t),&\mathrm{~{}if~{}}t\in(\check{t},\hat{t}_{\phantom{}}),\\\
\mathrm{sgn}\left(s_{j}(t_{2})-\vartheta_{i}(t_{2})\right),&\mathrm{~{}if~{}}t\in(\hat{t},t_{2}),\end{cases}$
(4)

satisfies $J(u^{\prime})\leq J(u)$.

###### Proof:

In what follows we construct a trajectory $s_{j}^{\prime}$ which coincides
with that of $s_{j}$ everywhere outside of $(t_{1},t_{2})$, and is at least as
close to target $i$ as $s_{j}$ during $(t_{1},t_{2})$. Let us begin by
capturing the signs in (4) by
$\gamma_{1}=\mathrm{sgn}(\vartheta_{i}(t_{1})-s_{j}(t_{1}))$ and
$\gamma_{2}=\mathrm{sgn}(s_{j}(t_{2})-\vartheta_{i}(t_{2}))$, which are
constant throughout this proof. We then introduce the auxiliary times

$\begin{split}\tilde{t}_{1}&=\inf\\{t>t_{1}\mid
s_{j}(t_{1})+\gamma_{1}(t-t_{1})=\vartheta_{i}(t)\\},\\\
\tilde{t}_{2}&=\sup\\{t<t_{2}\mid\vartheta_{i}(t)+\gamma_{2}(t_{2}-t)=s_{j}(t_{2})\\}.\end{split}$

Geometrically speaking, $\tilde{t}_{1}$ is the earliest arrival time at the
target (possibly infinity), and $\tilde{t}_{2}$ is the latest departure time
from the target such that the agent still reaches the point $s_{j}(t_{2})$
(possibly negative infinity). If $\tilde{t}_{1}\leq\tilde{t}_{2}$, then we set
$\check{t}=\tilde{t}_{1}$ and $\hat{t}=\tilde{t}_{2}$ (see Fig. 1). Otherwise,
the agent does not reach the target within the given interval, which implies
$\gamma_{1}=-\gamma_{2}$, and we find $\check{t}=\hat{t}$ by solving
$s_{j}(t_{1})+\gamma_{1}(\check{t}-t)-\gamma_{1}(t_{2}-\check{t})=s_{j}(t_{2})$.
The geometric interpretation of this is that the agent moves towards the
target at full speed until it must return at full speed in order to end up at
$s_{j}(t_{2})$. Solving for $\check{t}$ yields
$\check{t}=\frac{1}{2}\left(\gamma_{1}(s_{j}(t_{2})-s_{j}(t_{1}))+(t_{1}+t_{2})\right)$.
Note that $\check{t}\in[t_{1},t_{2}]$, since $|s_{j}(t_{2})-s_{j}(t_{1})|\leq
t_{2}-t_{1}$.

Now let $s_{j}^{\prime}$ be the trajectory obtained from $u^{\prime}$. By
construction, this trajectory coincides with that of $s_{j}$ everywhere
outside of $(t_{1},t_{2})$, and all other agents remain unchanged.
Additionally, we have
$|\vartheta_{i}(t)-s_{j}^{\prime}(t)|\leq|\vartheta_{i}(t)-s_{j}(t)|$ for all
$t\in(t_{1},t_{2})$. Due to the monotonicity of the monitoring functions, the
cost under $u^{\prime}$ can be no larger than that under $u$. ∎

Figure 1: Visualization of the trajectory obtained from control law (4). Note
how the agent only senses the second target over the interval $(t_{1},t_{2})$.
In view of the proof of Lemma 1, the times $\check{t}$ and $\hat{t}$ are equal
to the auxiliary times $\tilde{t}_{1}$ and $\tilde{t}_{2}$ as tracking is
achieved.

This lemma allows us to decompose an existing control into sequential phases
(or modes) in which only one target is visited. We utilize this control
modification for each individual interval to obtain a parameterized control
law. For the next lemma we introduce the ceiling function $\lceil\cdot\rceil$,
which maps each real number to the smallest integer greater than or equal to
the number itself.

###### Lemma 2

Let $(u,s)$ be any feasible control-trajectory pair. Then there exists an
alternative control law $u^{\prime}$, which satisfies $J(u^{\prime})\leq J(u)$
and is fully described by $n=5N\lceil T/\Delta^{\mathrm{min}}\rceil$
parameters.

###### Proof:

We begin with $u_{j}^{\prime}=u_{j}$ and denote by $(i_{1},i_{2},\dots,i_{k})$
the temporally ordered sequence of the sensed targets along the trajectory
$s_{j}$ satisfying $i_{\ell}\neq i_{\ell+1}$ for all $\ell$. Note that the
length of this sequence $k$ is bounded by $n=\lceil
T/\Delta^{\mathrm{min}}\rceil$ due to Assumption 1, and without loss of
generality we assume $k\geq 1$.

Similar to the target sensing sequence, we seek to find switching times
$0\leq\bar{t}_{1}\leq\dots\leq\bar{t}_{k}=T$, and thereby switching positions
$s_{j}(\bar{t}_{1}),s_{j}(\bar{t}_{2}),\dots,s_{j}(\bar{t}_{k})$, such that
$\bar{t}_{\ell}$ describes the end of the sensing phase of target $i_{\ell}$.
More precisely, $\bar{t}_{\ell}$ is defined as follows. Setting
$\bar{t}_{0}=0$, then we define for $1\leq\ell\leq k-1$ the upper bound

$\bar{t}_{\ell}^{\mathrm{max}}=\inf\\{t>\bar{t}_{\ell-1}\mid|\vartheta_{i_{\ell+1}}(t)-s_{j}(t)|=r_{j}\\},$
(5)

which is the earliest time of sensing the next target, and with that

$\bar{t}_{\ell}=\sup\\{t<\bar{t}_{\ell}^{\mathrm{max}}\mid|\vartheta_{i_{\ell}}-s_{j}(t)|=r_{j}\\}.$
(6)

By construction, agent $j$ only senses target $i_{\ell}$ along its trajectory
$s_{j}|_{(\bar{t}_{\ell-1},\bar{t}_{\ell})}$ restricted to
$(\bar{t}_{\ell-1},\bar{t}_{\ell})$. According to Lemma 1, replacing
$u_{j}^{\prime}|_{(\bar{t}_{\ell-1},\bar{t}_{\ell})}$ by (4) does not increase
the cost. This replacement yields two more parameters
$\check{t}_{\ell},\hat{t}_{\ell}$, which describe the switching times of the
modes.

Note that the new control law
$u^{\prime}_{j}|_{(\bar{t}_{\ell-1},\bar{t}_{\ell})}$ is now fully described
by the switching times $\bar{t}_{\ell-1}$, $\check{t}_{\ell}$,
$\hat{t}_{\ell}$, and $\bar{t}_{\ell}$, the sensed target $i_{\ell}$, and the
switching positions $s_{j}(\bar{t}_{\ell-1}),s_{j}(\bar{t}_{\ell})$.

Repeating this procedure for each sensed target yields a control described by
$5k$ parameters ($k$ target indices, $3k$ switching times, and $k$ switching
positions). In order to unify the dimensions across the agents, let us embed
the parameters into the respective $n$-dimensional spaces by replicating the
last parameters. This procedure is repeated for all agents, resulting in a
total number of $5Nn$ parameters. ∎

From this property, we can immediately conclude that if the OCP (3) admits a
solution, then there exists a control described by a finite number of
parameters. In order to show later that such a solution always exists, we now
prove that the resulting parameter space is compact.

###### Lemma 3

There exists a finite-dimensional and compact parameter space $\mathcal{Y}$
with functions

$T:\mathcal{U}^{N}\to\mathcal{Y}\quad\mathrm{~{}and~{}}\quad
H:\mathcal{Y}\to\mathcal{U}^{N},$ (7)

such that $J(H(T(u)))\leq J(u)$. In addition, the function $H$ can be chosen
to be continuous.

###### Proof:

Consider
$\tilde{\mathcal{Y}}=\mathcal{T}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{n}$,
and $y=(i,\bar{t},\check{t},\hat{t},s)\in\tilde{\mathcal{Y}}$. Then, define

$\mathcal{Y}_{j}=\left\\{y\in\tilde{\mathcal{Y}}\mid\bar{t}_{\ell-1}\leq\check{t}_{\ell}\leq\hat{t}_{\ell}\leq\bar{t}_{\ell},|s_{\ell-1}-s_{0}|\leq\bar{t}_{\ell-1}\forall\ell\right\\},$

where $\bar{t}_{0}=0$ and $\bar{t}_{n}=T$. The dependence on $j\in\mathcal{A}$
only affects $s_{0}=s_{j}(0)$, which is given. The full parameter space is
then defined by
$\mathcal{Y}=\mathcal{Y}_{1}\times\mathcal{Y}_{2}\times\dots\times\mathcal{Y}_{N}$.
Note that each $\mathcal{Y}_{j}$ is bounded and closed, and $\mathcal{Y}$ is
thus compact. The function $T:\mathcal{U}^{N}\to\mathcal{Y}$ is defined by the
mapping constructed in the proof of Lemma 2.

On the other hand, the function $H:\mathcal{Y}\to\mathcal{U}^{N}$ simply maps
an element $y\in\mathcal{Y}$ to the control $u^{\prime}(t)$, where

$u_{j}^{\prime}(t)=\begin{cases}\mathrm{sgn}\left(\vartheta_{i_{\ell}^{j}}(\bar{t}^{j}_{\ell-1})-s^{j}_{\ell-1}\right),&t\in[\bar{t}_{\ell-1}^{j},\check{t}_{\ell}^{j}),\\\
\dot{\vartheta}_{i_{\ell}^{j}}(t),&t\in[\check{t}_{\ell}^{j},\hat{t}_{\ell}^{j}),\\\
\mathrm{sgn}\left(s^{j}_{\ell}-\vartheta_{i_{\ell}^{j}}(\bar{t}^{j}_{\ell})\right),&t\in[\hat{t}_{\ell}^{j},\bar{t}_{\ell}^{j}).\end{cases}$
(8)

Then $H(T(u))=u^{\prime}$ as in Lemma 2, and consequently $J(H(T(u)))\leq
J(u)$.

Finally, we show that $H$ is continuous. Let $\pi_{m}\to\pi$ be any convergent
sequence in the parameter space, and let $v_{m}=H(\pi_{m})$ and $v=H(\pi)$.
Let $\varepsilon>0$ be arbitrarily small and define
$\delta=\min\\{\frac{\varepsilon}{13Nn},\frac{\tilde{\delta}}{3}\\}$, where
$\tilde{\delta}>0$ is the smallest positive distance between the target
positions and switching points that determine the signs in (8) for the
parameterization $\pi$. Then, due to the convergence in the parameter space,
there exists a $K>0$ such that the absolute value of each component of
$\pi_{m}-\pi$ is bounded by $\delta$ for all $m\geq K$. By the choice of
$\delta$, the evaluated signs in (8) agree for all parameterizations $\pi_{m}$
with $m\geq K$. Now let $(\bar{t}^{j}_{\ell-1},\bar{t}^{j}_{\ell})$ be an
interval between switching points given by the parameterization $\pi$. During
this interval the control laws $v_{m}=H(\pi_{m})$ and $v=H(\pi)$ can only
differ over six intervals of length $\delta$; one each for the beginning and
the end of the intervals in (8). Over those intervals, the control deviation
is bounded by $2$. In total we get

$\begin{split}\|v_{m}-v\|&=\sum_{j=1}^{N}\sum_{\ell=1}^{n}\int_{\bar{t}^{j}_{\ell-1}}^{\bar{t}^{j}_{\ell}}|v_{m,j}(t)-v_{j}(t)|dt\\\
&\leq Nn62\delta=12Nn\delta<\varepsilon.\end{split}$ (9)

This shows that $H$ is continuous. ∎

The fact that the parameter space is compact leads to the existence of
converging subsequences, which we utilize in the next theorem.

###### Theorem 1

Consider the OCP (3). Under Assumption 1 there exists an optimal control
$u^{\ast}\in\mathcal{U}^{N}$ and an optimal parameterization
$\pi^{\ast}\in\mathcal{Y}$ such that $H(\pi^{\ast})=u^{\ast}$.

###### Proof:

Note that the cost function $J$ is bounded. Thus, there exists an infimal cost
$J^{\ast}$ and, consequently, a sequence $(u_{k})_{k\in\mathbb{N}}$ of
controls such that $J(u_{k})\to J^{\ast}$. Denote by $T(u_{k})=\pi_{k}$ the
mapped elements of the control sequence into the parameter space
$\mathcal{Y}$. Since $\mathcal{Y}$ is compact, the mapped sequence must admit
a convergent subsequence
$\lim\limits_{m\to\infty}\pi_{k_{m}}=\pi^{\ast}\in\mathcal{Y}$. The continuity
of $H$ provides

$\lim_{m\to\infty}H(\pi_{k_{m}})=H\left(\lim_{m\to\infty}\pi_{k_{m}}\right)=H(\pi^{\ast})=u^{\ast}\in\mathcal{U}^{N},$

which ultimately shows

$J(u^{\ast})=J\left(\lim_{m\to\infty}H(\pi_{k_{m}})\right)=\lim_{m\to\infty}J\bigl{(}H(\pi_{k_{m}})\bigr{)}=J^{\ast}$

due to the continuity of the cost function. ∎

Figure 2: Comparison of the optimal (top) and practical (bottom)
parameterizations. The variables below the intervals indicate their length and
type, according to the parameterization. Dashed vertical lines represent
foreseeable mode changes due to proceeding to the next interval, whereas
dotted vertical lines depict observable mode changes due to sufficient
reduction of the tracking error.

##  IV Parametric Reformulation

The above analysis shows that the optimal control problem can be reduced to a
much simpler _parametric_ optimization problem. In what follows, we will
introduce two different parameterizations. The first one provides a
generalization of (8), and we refer to it as the optimal parameterization,
since it contains an optimal control as established in Thm 1. Its drawback is
that it requires knowledge of the target velocities, which are difficult to
estimate in practice. From a practical viewpoint, the policy (8) can be read
as stay as close to the target as possible, which motivates the alternative
practical parameterization. Though it loses optimality to some degree, it only
requires positional feedback of the targets, and has additional advantages,
such as a natural robustness towards noise, and simplicity of initialization;
details are discussed later on. We now introduce both forms for a fixed agent
$j$, while omitting the index for notational simplicity. For guidance, we
refer the reader to Fig. 2, which illustrates both formulations.

Optimal Parameterization Let us first define the set of convex combinations
$\mathcal{C}=\\{\alpha\in[0,1]^{M}\mid\sum_{i=1}^{M}\alpha_{i}=1\\}$. Next, we
introduce parameters that can be divided into switching points
$\psi_{1},\dots,\psi_{L}\in\mathcal{S}$, tracking combinations
$\alpha_{1},\dots,\alpha_{L}\in\mathcal{C}$ and tracking durations
$\phi_{1},\dots,\phi_{L}\in[0,T]$, where $L$ is some fixed integer. From this
parameterization we obtain a control

$u(t)=\begin{cases}\mathrm{sgn}(\psi_{\ell}-s(\bar{t}_{\ell-1})),&\mathrm{~{}for~{}}t\in[\bar{t}_{\ell-1},\check{t}_{\ell}),\\\
\alpha_{\ell}^{\top}\dot{\vartheta}(t),&\mathrm{~{}for~{}}t\in[\check{t}_{\ell},\bar{t}_{\ell}),\end{cases}$
(10)

where $\check{t}_{\ell}=\bar{t}_{\ell-1}+|\psi_{\ell}-s(\bar{t}_{\ell-1})|$
and $\bar{t}_{\ell}=\check{t}_{\ell}+\phi_{\ell}$, initialized with
$\bar{t}_{0}=0$.

There are two reasons why we propose the target tracking to be encoded in the
form of convex combinations. First and foremost, the feasible set of the
parametric description becomes convex. The only difficulty to overcome in an
optimization scheme is that of the cost function’s nonconvexity and
nonsmoothness. Secondly, the resulting control law has some adaptability
towards simultaneous sensing scenarios, as discussed in Sec. VI. Note that if
Assumption 1 is satisfied, then the optimal control established in Thm 1 is
contained in the parameterization by choosing convex combinations that only
select a single target at a time.

Practical Parameterization. As opposed to defining switching points in the
mission space and then matching a convex combination of target velocities, we
now propose a control law by directly tracking a convex combination of target
positions.

The parameterization is thus reduced to tracking durations
$\phi_{1},\dots,\phi_{L}\in[0,T]$ and tracking combinations
$\alpha_{1},\dots,\alpha_{L}\in\mathcal{C}$. The switching times are simply
given by $\bar{t}_{\ell}=\bar{t}_{\ell-1}+\phi_{\ell}$, which is again
initialized with $\bar{t}_{0}=0$. For $t\in[\bar{t}_{\ell-1},\bar{t}_{\ell})$
we then obtain a control

$u(t)=\min\left(1,\max\left(-1,f^{\mathrm{PI}}_{\ell}(t)\right)\right),$ (11)

via the PI-controller

$f^{\mathrm{PI}}_{\ell}(t)=K_{p}e_{\ell}(t)+K_{i}\int_{\tilde{t}_{\ell}}^{\max(t,\tilde{t}_{\ell})}e_{\ell}(\sigma)d\sigma,$
(12)

with tracking error $e_{\ell}(t)=\alpha_{\ell}^{\top}\vartheta(t)-s(t)$, and
respective proportional and integral feedback gains $K_{p}>0$ and $K_{i}>0$.
Since the integral part is useful for driving a small proportional error to
zero, we activate this part once the tracking error becomes small enough.
Thus, the starting time of the integrator part can be written as

$\tilde{t}_{\ell}=\inf\\{t\geq\bar{t}_{\ell-1}\mid|K_{p}e_{\ell}(t)|\leq\varepsilon_{\mathrm{tol}}\\},$
(13)

for some desired switching tolerance $\varepsilon_{\mathrm{tol}}\in(0,1)$. The
motivation behind this strategy is that the beginning of a new tracking
interval typically leads to a large proportional feedback gain due to the
switched tracking combination $\alpha_{\ell}$. In order to prevent integrator
windup and consequent control saturation during the PI tracking phase, under
this strategy we first track via the P-controller, switching to a PI-
controller once the tracking error becomes small enough. Note that this is a
fairly simple anti-windup scheme, with the main goal of keeping the control
law continuous and thereby the IPA analysis as tractable as possible; in
practice more standard anti-windup algorithms may be preferred.

Comparison of the parameterizations. The practical parameterization clearly
loses optimality, the degree of which depends on the position sampling rate
and the chosen feedback gains. On the other hand, the practical implementation
gives rise to attractive properties. One is the ease of initialization. Assume
that we want to initialize the system with a given visiting schedule of
targets. Then, all we have to do is decide how long we want to track each of
the targets. Trying to initialize the optimal parameterization for mobile
targets becomes tedious and complex; it requires estimates of where to
intercept the targets and where agents will end up after each tracking phase.
Such information is rarely available in practice. Additionally, the practical
implementation is naturally more robust to perturbations due to its closed
loop design.

##  V Optimizing the System Parameters

The parametric controllers introduced in the preceding section define a hybrid
system for each agent. We denote the feasible set of parameters as $\Theta$,
the precise form of which depends on the chosen parameterization. The OCP (3)
is now reduced to the parametric optimization problem

$\operatorname*{\mathrm{minimize}}_{\mathbf{\theta}\in\Theta}~{}J(\mathbf{\theta}).$

In order to perform a gradient descent method we need the gradient of $J$ with
respect to $\theta$; we find this using IPA [17]. It was shown in [7, 6] that
the derivative of the cost function with respect to the parameters is given by

$\frac{\partial
J(\mathbf{\mathbf{\theta}})}{\partial\mathbf{\theta}}=\frac{1}{T}\sum_{k=1}^{K}\sum_{i=1}^{M}\int_{\tau_{k-1}(\mathbf{\mathbf{\theta}})}^{\tau_{k}(\mathbf{\mathbf{\theta}})}\frac{\partial
R_{i}(\sigma)}{\partial\mathbf{\theta}}d\sigma,$

where $\tau_{0},\tau_{1},\dots,\tau_{K}$ describe the event times when mode
switches occur in the hybrid system, and $K$ denotes the total number of
events (note $\tau_{0}=0$ and $\tau_{K}=T$). We now denote by
$x^{\prime}(t)=\frac{\partial x(\mathbf{\theta},t)}{\partial\mathbf{\theta}}$
the Jacobian matrix, where $x=(s,R)$ is the collection of states. We point out
that the target positions and velocities could be included as states, however,
since they do not depend on the system parameters they can be omitted. We now
compute the gradients of $R_{i}$ by applying the IPA equation [17]

$\frac{d}{dt}x^{\prime}(t)=\frac{\partial f_{k}(t)}{\partial
x}x^{\prime}(t)+\frac{\partial f_{k}(t)}{\partial\theta}$ (14)

over an inter-event interval $[\tau_{k},\tau_{k+1})$ with boundary condition

$x^{\prime}(\tau_{k}^{+})=x^{\prime}(\tau_{k}^{-})+\left(f_{k-1}(\tau_{k}^{-})-f_{k}(\tau_{k}^{+})\right)\tau_{k}^{\prime}.$
(15)

Clearly, $R_{i}^{\prime}(t)=0$ if $i\in\mathcal{Z}(t)$. Otherwise, we use (14)
to obtain

$\frac{d}{dt}\frac{\partial
R_{i}(t)}{\partial\mathbf{\theta}_{j}}=-B_{i}\frac{\partial
p_{ij}(t)}{\partial s_{j}}\frac{\partial
s_{j}(t)}{\partial\mathbf{\theta}_{j}}\prod\limits_{\ell\neq
j}(1-p_{i\ell}(t)).$ (16)

The gradient of $R$ may experience discontinuities. This can only be the case
when events occur that change the dynamics of $R$. As previously shown in [7],

$\frac{\partial
R_{i}(\tau_{k}^{+})}{\partial\theta_{j}}=\begin{cases}\frac{\partial
R_{i}(\tau_{k}^{-})}{\partial\theta_{j}},&\mathrm{~{}if~{}}R_{i}(\tau_{k})\neq
0,\\\ 0,&\mathrm{~{}if~{}}R_{i}(\tau_{k})=0.\end{cases}$ (17)

The remaining unknown term in (16) is the gradient of $s$ with respect to the
system parameters. Applying (14) once again results in

$\frac{d}{dt}s^{\prime}(t)=\frac{\partial f_{k}(t)}{\partial
s}s^{\prime}(t)+\frac{\partial f_{k}(t)}{\partial\theta},$ (18)

with boundary condition

$s^{\prime}(\tau_{k}^{+})=s^{\prime}(\tau_{k}^{-})+\left(f_{k-1}(\tau_{k}^{-})-f_{k}(\tau_{k}^{+})\right)\tau_{k}^{\prime}.$
(19)

Note that the analysis up to this point was independent of the control
parameterization. We now compute the specific forms of (18) and (19)
separately for the individual parameterizations. In both cases we fix an index
$j\in\mathcal{A}$ and refrain from explicitly writing it out.

IPA for the optimal parameterization. We recall from (10) that the optimal
control is described by two modes: a) the switching mode
$f_{\ell}^{s}(t)=\mathrm{sgn}(\psi_{\ell}-s(t_{\ell-1}))$; and b) the tracking
mode $f_{\ell}^{t}(t)=\alpha_{\ell}^{\top}\dot{\vartheta}(t)$. Let
$t\in[\tau_{k},\tau_{k+1})$, and assume first that the current mode is the
$\ell$th tracking mode, i.e.,
$f_{k}(t)=\alpha_{\ell}^{\top}\dot{\vartheta}(t)$. Then the r.h.s. of (18)
vanishes, with the exception being the entries $\frac{d}{dt}\frac{\partial
s(t)}{\partial\alpha_{\ell,i}}=\dot{\vartheta}_{i}(t)$ for all
$i\in\mathcal{T}$. Otherwise, if the current mode is $f_{\ell}^{s}(t)$, then
$s^{\prime}$ is constant. We are left with having to identify the time
derivatives of the boundary condition (19). These values only have to be
computed for mode switches that change the dynamics of the agent, since
otherwise $f_{k-1}=f_{k}$ is a continuous transition between the modes. There
are precisely two cases that cause such switches: ones that are caused by
reaching a switching point and ones that are caused by finishing a tracking
period.

If the switch is triggered by reaching the switching point $\psi_{\ell}$, then
the event is endogenous and triggered by the switching function, which we
define by $g_{\ell}(s(\mathbf{\theta},t),\mathbf{\theta})=\psi_{\ell}-s(t)$,
becoming zero. Then, as shown in [17], we find

$\begin{split}\tau_{k}^{\prime}&=-\left(\frac{\partial g_{k}}{\partial
s}f_{k-1}(\tau_{k}^{-})\right)^{-1}\left(\frac{\partial
g_{k}}{\partial\mathbf{\theta}}+\frac{\partial g_{k}}{\partial
s}x^{\prime}(\tau_{k}^{-})\right)\\\
&=\mathrm{sgn}(\psi_{\ell}-s(\bar{t}_{\ell-1}))\left(\frac{\partial
g_{k}}{\partial\mathbf{\theta}}-x^{\prime}(\tau_{k}^{-})\right),\end{split}$

where $\frac{\partial g_{k}}{\partial\mathbf{\theta}}$ vanishes for all
parameters except for $\frac{\partial g_{k}}{\partial\psi_{\ell}}=1$.

On the other hand, if the switch is caused by leaving a tracking period, then
the switch is an induced event triggered at time
$\tau_{k}=\tau_{m}+\phi_{\ell}$, where $\tau_{m}$ is the most recent switching
time of the agent’s mode. From this we find that $\tau_{k}^{\prime}$ evolves
continuously except for the parameter $\phi_{\ell}$, for which the new partial
is given by $\frac{\partial\tau_{k}}{\partial\phi_{\ell}}=1$, since this
parameter did not affect any previous event times.

IPA for the practical parameterization. The practical parameterization
implicitly defines four modes: a) $f_{\ell}^{1}$ for constant positive bang
control; b) $f_{\ell}^{-1}$ for constant negative bang control; c)
$f_{\ell}^{\mathrm{P}}$ for the purely proportional tracking control while
respecting the control bounds; and d) $f_{\ell}^{\mathrm{PI}}$ for a PI
tracking control respecting the control bounds. Then, as before, we find that
$s^{\prime}$ is constant during the modes $f_{\ell}^{1}$ and $f_{\ell}^{-1}$.
Now let us assume that $f_{\ell}^{\mathrm{P}}$ is active. Then, we find
$\frac{\partial f_{k}(t)}{\partial s}=-K_{p}$, whereas $\frac{\partial
f_{k}(t)}{\partial\mathbf{\theta}}=0$ for all parameters, except
$\frac{\partial f_{k}(t)}{\partial\alpha_{\ell,i}}=K_{p}\vartheta_{i}(t)$. And
finally, if the PI-control law $f_{\ell}^{\mathrm{PI}}$ is active, then
$\frac{\partial f_{k}(t)}{\partial s}=-(K_{p}+K_{i}(t-\tilde{t}_{\ell}))$, and
again $\frac{\partial f_{k}(t)}{\partial\mathbf{\theta}}=0$ for all parameters
except

$\frac{\partial
f_{k}(t)}{\partial\alpha_{\ell,i}}=K_{p}\vartheta_{i}(t)+K_{i}\int_{\tilde{t}_{\ell}}^{t}\vartheta_{i}(\sigma)d\sigma.$

Again, the state derivatives $s^{\prime}$ may experience discontinuities due
to (19). This only occurs when an agent’s mode switches. Recall that the
controller (11) was designed to provide a continuous function during the
interval $(\bar{t}_{\ell-1},\bar{t}_{\ell})$, thus switches within the modes
of (11) do not lead to discontinuities in the state derivatives. On the other
hand, if the switch is caused by leaving the $\ell$th tracking period, then
the switch is an induced event triggered at time
$\tau_{k}=\phi_{0}+\phi_{1}+\dots+\phi_{\ell}$. We can directly compute
$\frac{\partial\tau_{k}}{\partial\alpha}=0$ and
$\frac{\partial\tau_{k}}{\partial\phi_{m}}=1$ for all $m\leq\ell$.

Finding a feasible search direction. With all gradients determined via IPA, we
are almost ready to perform a gradient descent method. However, in order for
the tracking combination constraint to remain satisfied, the step direction
with respect to the tracking constraints, denoted by $p_{\alpha}$, must be
chosen appropriately, i.e., its components must add up to zero for each
tracking period $\ell$ and agent $j$. We do so by computing a feasible step
direction via the least squares problem p_α∥ ∂J∂α \- p_α∥_2^2 0 ≤α_ℓi j +
p_α_ℓi j≤1 ∀ℓ, i, j, ∑_m=1^M p_α_ℓm j = 0 ∀ℓ,j, where $p_{\alpha_{\ell ij}}$
is the $i$th component of the step direction for agent $j$ in the $l$th
tracking period. The global solution of this convex optimization problem
yields the steepest gradient of $J$ respecting the tracking parameter
constraints. For the remaining parameters, we directly use the IPA gradients.
In order to achieve cost function descent at each iterate, we choose a step
length via the Armijo backtracking technique [18].

Figure 3: Depiction of the highly nonconvex cost (top) together with
respective local (purple) and global (green) solutions (bottom) when fixing
all but one parameter. Note that the sensing range (red) is shown around the
targets as opposed to around the agents.

Challenges in finding good local solutions Though we are now able to optimize
the system parameters over a convex set, and gradients are available for
suitable initializations, the problem remains difficult to solve due to the
local nature of the gradient descent procedure. For the one-dimensional
persistent monitoring problem for static targets, it was demonstrated that
finding the global solution of a problem with fixed target visiting sequence
is tractable [6]. Fig. 3 demonstrates that this changes drastically in the
mobile target case. The cost, even with respect to a single parameter, can be
highly nonconvex. Moreover, the cost function is in parts extremely steep,
whereas for other segments it is very flat. This combination presents a
challenge for gradient descent methods and highlights the need to select
appropriate step sizes in order to avoid stagnation and remain in the
contraction area of a desirable solution.

Another difficulty, which is typical for event based algorithms, is the
potential lack of event excitation [19]. This occurs in the persistent
monitoring problem if the agents change their modes while not sensing targets.
In such cases the IPA gradients fail to estimate the true cost gradient
resulting in a failure of the optimization scheme. Though beyond the scope of
this paper, the methods discussed in [19] could help overcome this problem.

Figure 4: Results for the same experiment as conducted in [6]. The top plot
shows the comparison of the agent trajectories obtained from the optimal
(green) and practical (purple) parameterizations. The targets are depicted in
red. The second plot shows the evolution of the target uncertainties, where
the line style specifies the target and the color specifies the used
parameterization. The third plot shows the cost reduction for the IPA
iterates.

##  VI Numerical Experiments

Comparison to existing methods. We first compare the proposed methods to the
related algorithm from [6] that was designed for static targets. We apply the
new parameterizations to a static target experiment, the globally optimal cost
of which was shown to be $J^{\ast}=25.07$ [6]. Fig. 4 shows the results for
both the optimal and practical parameterizations. The solution quality of the
practical ($25.54$) and the optimal ($25.61$) are comparable to the local
solution of the previous method ($25.54$), which indicates that the
generalized methods remain applicable to static targets as well. The fact that
the practical parameterization slightly outperforms the optimal one in this
specific case is due to local convergence behaviors, and other initializations
may lead to different results.

Simultaneous sensing scenarios. The theoretical results in this paper were
proven under the assumption that only one target could be within an agent’s
sensing range at a time. In Fig. 5 we demonstrate the fact that describing the
target tracking via convex combinations allows the proposed parameterizations
to adapt to scenarios where this assumption is violated. This allows agents to
place themselves between targets, which is particularly useful if targets are
so close to each other that they share a deadzone, i.e., an area in which an
agent can be positioned such that the uncertainty of both targets becomes non-
increasing. In such a case, the uncertainty of both targets can be driven to
zero and kept at that level, which is only possible if the agent stays within
that deadzone.

Figure 5: Simultaneous sensing experiment with two targets (red solid and
dotted) and one agent (blue solid). The sensing range (blue shaded) is shown
on the agent.

Robustness towards noise. As previously discussed in [6], the IPA analysis
provides gradients that are naturally robust towards errors in the estimation
of the uncertainty growth rate $A$. This is due to the fact that $A$ only
implicitly affects the switching times of the uncertainty dynamics without
explicitly appearing in the gradient evaluations.

In this section we want to show that the practical parameterization is
additionally robust towards noisy measurements. In particular, we assume that
each target’s positional measurement is given by
$\vartheta_{i}^{\mathrm{est}}(t)=\vartheta_{i}(t)+\kappa_{1}\nu_{i}(t)$ for
$\nu_{i}(t)\sim\mathcal{N}(0,1)$ and some scaling factor $\kappa_{1}>0$. We
ran $1000$ repetitions of a fixed persistent monitoring problem with
$M=4,N=2,T=50$, $L=4$, and randomized initial visiting sequences. We repeated
the same experiment for the optimal parameterization with noisy target
velocity estimates
$\dot{\vartheta}_{i}^{\mathrm{est}}(t)=\dot{\vartheta}_{i}(t)+\kappa_{2}\nu_{i}(t)$,
where $\mu_{i}(t)\sim\mathcal{N}(0,1)$ and $\kappa_{2}>0$. Fig. 6 compares the
cost distributions of the initializations to the resulting trajectories
obtained through the respective gradient descent methods. Both methods are
able to reduce the cost drastically, though the practical parameterization
achieves notably better results. This is due to the fact that the practical
version incorporates tracking error feedback into its control law. On the
other hand, the optimal version simply tries to copy a target’s motions,
though without validating its proximity. The practical parameterization’s
natural resiliency to noise also leads to significantly better
initializations, which in turn leads to better local solutions.

Figure 6: Depiction of the randomized experiment. The cost distribution of the
initializations is depicted in orange (optimal) and red (practical), whereas
the optimized cost distributions are shown in blue (optimal) and green
(practical).

##  VII Conclusion and Future Work

In this paper, we showed the existence of optimal solutions for the one-
dimensional persistent monitoring problem of mobile targets by reducing the
infinite-dimensional OCP (3) to a parametric optimization problem. We
characterized the optimal control, which motivated the design of an event
based optimization scheme. We then proposed a suboptimal parametric
description of the system that proved to perform robustly in various numerical
experiments.

In future work, we will consider the extension to more realistic second-order
agent dynamics, extending the problem to the infinite horizon case through the
use of periodic patterns, and the consideration of problem formulations in
two-dimensional settings.

## References

  * [1] J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage control for mobile sensing networks,” IEEE Transactions on robotics and Automation, vol. 20, no. 2, pp. 243–255, 2004.
  * [2] J. Yu, S. Karaman, and D. Rus, “Persistent monitoring of events with stochastic arrivals at multiple stations,” IEEE Transactions on Robotics, vol. 31, no. 3, pp. 521–535, 2015.
  * [3] Y. Khazaeni and C. G. Cassandras, “Event-driven trajectory optimization for data harvesting in multiagent systems,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1335–1348, 2017.
  * [4] Z. Shen and S. B. Andersson, “Tracking nanometer-scale fluorescent particles in two dimensions with a confocal microscope,” IEEE Transactions on Control Systems Technology, vol. 19, no. 5, pp. 1269–1278, 2010.
  * [5] S. L. Smith, M. Schwager, and D. Rus, “Persistent monitoring of changing environments using a robot with limited range sensing,” in 2011 IEEE International Conference on Robotics and Automation, pp. 5448–5455, IEEE, 2011\.
  * [6] N. Zhou, X. Yu, S. B. Andersson, and C. G. Cassandras, “Optimal event-driven multiagent persistent monitoring of a finite set of data sources,” IEEE Transactions on Automatic Control, vol. 63, no. 12, pp. 4204–4217, 2018.
  * [7] C. G. Cassandras, X. Lin, and X. Ding, “An optimal control approach to the multi-agent persistent monitoring problem,” IEEE Transactions on Automatic Control, vol. 58, no. 4, pp. 947–961, 2012.
  * [8] X. Yu, S. B. Andersson, N. Zhou, and C. G. Cassandras, “Scheduling multiple agents in a persistent monitoring task using reachability analysis,” IEEE Transactions on Automatic Control, vol. 65, no. 4, pp. 1499–1513, 2019\.
  * [9] X. Lan and M. Schwager, “Planning periodic persistent monitoring trajectories for sensing robots in gaussian random fields,” in 2013 IEEE International Conference on Robotics and Automation, pp. 2415–2420, IEEE, 2013\.
  * [10] S. Alamdari, E. Fata, and S. L. Smith, “Persistent monitoring in discrete environments: Minimizing the maximum weighted latency between observations,” The International Journal of Robotics Research, vol. 33, no. 1, pp. 138–154, 2014.
  * [11] S. Welikala and C. G. Cassandras, “Event-driven receding horizon control for distributed persistent monitoring in network systems,” Automatica, vol. 127, p. 109519, 2021.
  * [12] S. K. K. Hari, S. Rathinam, S. Darbha, K. Kalyanam, S. G. Manyam, and D. Casbeer, “The generalized persistent monitoring problem,” in 2019 American Control Conference (ACC), pp. 2783–2788, IEEE, 2019.
  * [13] P. Maini, K. Yu, P. Sujit, and P. Tokekar, “Persistent monitoring with refueling on a terrain using a team of aerial and ground robots,” in 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 8493–8498, IEEE, 2018.
  * [14] M. Ostertag, N. Atanasov, and T. Rosing, “Trajectory planning and optimization for minimizing uncertainty in persistent monitoring applications,” Journal of Intelligent & Robotic Systems, vol. 106, no. 1, pp. 1–19, 2022.
  * [15] C. Song, L. Liu, G. Feng, and S. Xu, “Optimal control for multi-agent persistent monitoring,” Automatica, vol. 50, no. 6, pp. 1663–1668, 2014\.
  * [16] M. Boldrer, F. Pasqualetti, L. Palopoli, and D. Fontanelli, “Multi-agent persistent monitoring via time-inverted kuramoto dynamics,” IEEE Control Systems Letters, 2022.
  * [17] C. G. Cassandras, Y. Wardi, C. G. Panayiotou, and C. Yao, “Perturbation analysis and optimization of stochastic hybrid systems,” European Journal of Control, vol. 16, no. 6, pp. 642–661, 2010.
  * [18] L. Armijo, “Minimization of functions having lipschitz continuous first partial derivatives,” Pacific Journal of mathematics, vol. 16, no. 1, pp. 1–3, 1966.
  * [19] Y. Khazaeni and C. G. Cassandras, “Event excitation for event-driven control and optimization of multi-agent systems,” in 2016 13th International Workshop on Discrete Event Systems (WODES), pp. 197–202, IEEE, 2016.

  *[OCP]: Optimal Control Problem
  *[IPA]: Infinitesimal Perturbation Analysis


# Selecting Attributes for Sport Forecasting using Formal Concept Analysis

Gonzalo A. Aranda-Corral1, Joaquín Borrego-Díaz2 Juan Galán-Páez2

1Department of Information Technology, Universidad de Huelva, Spain
<EMAIL_ADDRESS>
2Department of Computer Science and Artificial Intelligence, Universidad de
Sevilla, Spain
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

In order to address complex systems, apply pattern recongnition on their
evolution could play an key role to understand their dynamics. Global patterns
are required to detect emergent concepts and trends, some of them with
qualitative nature. Formal Concept Analysis (FCA) is a theory whose goal is to
discover and to extract Knowledge from qualitative data. It provides tools for
reasoning with implication basis (and association rules). Implications and
association rules are usefull to reasoning on previously selected attributes,
providing a formal foundation for logical reasoning. In this paper we analyse
how to apply FCA reasoning to increase confidence in sports betting, by means
of detecting temporal regularities from data. It is applied to build a
Knowledge Based system for confidence reasoning.

## Introduction

Formal Concept Analysis (FCA) Ganter & Wille (1999) is a mathematical theory
for data analysis using formal contexts and concept lattices as key tools.
Domains can be formally modelled according to the extent and the intent of
each formal concept. In FCA, the basic data structure is a formal context
(with a qualitative nature) which represents a set of objects and their
properties and it is useful both to detect and to describe regularities and
structures of concepts. It also provides a sound formalism for reasoning with
such structures, mainly Stem Basis and association rules. Therefore, it is
interesting to consider its application for reasoning with temporal
qualitative data in order to discover temporal trends Aranda-Corral et al.
(2011).

In this paper, FCA application scope is the challenge of sports betting,
specifically, the forecasting of soccer league’s results. Forecasting sport
results is a fast growing research area, because of its economic impact in
betting markets as well as for its potential application to problems with
similar behaviour (markets) Inst. Engineering and Technology (2010).
Considering sports betting as a complex system, soccer leagues represent a
challenging system with a huge amount of knowledge, available through WWW, and
its behaviour is weekly exhaustive analysed by journalists, betting companies
and supporters. Roughly speaking, three dimensions have been considered for
analysing/synthesizing prediction systems: 1)Those which analyse information
on teams (endogenous) versus those which analyse results (exogenous); 2)Those
which exploit quantitative data versus those which exploit qualitative
knowledge, and finally, 3)Statistic-based ones versus other methods. Usually,
one can work with hybrid models, and rarely with pure qualitative and
exogenous reasoning systems appear in literature, although their use is
considered for experiments (for example, frugal methods Goldstein & Gigerenzer
(2009) and based on the recognition heuristic Goldstein & Gigerenzer (2002))
or as part of hybrid systems (see e.g. Min et al. (2008)). There are two
reasons that may justify this point.

On the one hand, transformation from a large quantitative dataset to a
qualitative problem is faced with the selection of an acceptable threshold and
the discovery of better relations (see e.g. Imberman et al. (1999)). On the
other hand, a qualitative dataset must be accomplished with some amount of
information based on confidence, trust or probability of these data sets.

Figure 1: FCA based model for prediction of qualitative features of Complex
Systems

The aim of this paper is to describe all researching work made for selecting
and computing attribute sets related to soccer results, into a specific
framework: FCA, and starting from soccer match results, with no previous
analysis of any other specific attributes. This task is previous to build an
Expert System for advising sport betting which could detects some kind of
regularities on data. Concept lattices, which are computed from attribute
values, represent a mathematical structure of relationships among the concepts
which are involved in selected sport events to study. Since this method is
bet-oriented, its performance is evaluated within a confidence-based reasoning
system. This sistem increases number of hits in soccer matches forecasting,
discovering temporal trends by means of data mining and association rules
reasoning. The analysis of attributes has been used in Aranda-Corral et al.
(2011) to describe a confidence-based (and contextual) reasoning system for
forecasting sports betting. In this paper we analyse the attribute selection
problem as a problem of selection of features that shape the behaviour of the
complex system that represents professional soccer leagues. Theoretical
framework, on which this model is based on, will be presented at Aranda-Corral
et al. 2011b . Due to a really huge amount of information, attribute selection
advised by experts is mandatory. In fact, the system can be considered as a
reasoning model based on bounded rationality and recognizition heuristics. and
focused on features which were considered as important by human experts.
Therefore, the system aims to forecast results, but it is designed based on
bounded rationality models, instead of statistic models (although in the
future hybrid models will be considered.

The system is a first prototype from a more general system, which are building
to analyse qualitative features of Complex Systems (see Fig. 1), using FCA.
The idea is to isolate qualitate attributes from (past) local interactions
among components of complex system and to apply FCA tools in order to predict
properties system’s behavior in a near future.

## Background: Formal Concept Analysis

According to R. Wille, FCA Ganter & Wille (1999) mathematizes the
philosophical understanding of a concept as a unit of thoughts composed of two
parts: the extent and the intent. The extent covers all objects belonging to
this concept, while the intent comprises of all common attributes valid for
all the objects under consideration. It also allows the computation of concept
hierarchies from data tables. In this section, we succinctly present basic FCA
elements (the fundamental reference is Ganter & Wille (1999)).

A formal context $M=(O,A,I)$ consists of two sets, $O$ (objects) and $A$
(attributes) and a relation $I\subseteq O\times A$. Finite contexts can be
represented by a 1-0-table (identifying $I$ with a Boolean function on
$O\times A$). See Fig. 2 for an example of formal context about live beings.

Figure 2: Formal context, associated concept lattice and Stem Basis

The FCA main goal is the computation of the concept lattice associated to the
context. Given $X\subseteq O$ and $Y\subseteq A$ it defines

$X^{\prime}:=\\{a\in A\ |\ oIa\mbox{ for all }o\in X\\}$

$Y^{\prime}:=\\{o\in O\ |\ oIa\mbox{ for all }a\in Y\\}$

A (formal) concept is a pair $(X,Y)$ such that $X^{\prime}=Y$ and
$Y^{\prime}=X$. For example, concepts from living beings formal context (Fig.
2, left) is depicted in Fig. 2, right.

Using this Fig. 2, each node is a concept, and its intension (or extension)
can be formed by the set of attributes (or objects) included along the path to
the top (or bottom). E.g. The node tagged with the attribute Legs represents
to the concept $(\\{Legs,Mobility,NeedWater\\},\\{Cat,Frog\\})$.

In this paper it works with logical relations on attributes which are valid in
the context. Logical expressions in FCA are implications between attributes.
An implication is a pair of sets of attributes, written as $Y_{1}\to Y_{2}$,
which is true with respect to $M=(O,A,I)$ according to the following
definition. A subset $T\subseteq A$ respects $Y_{1}\to Y_{2}$ if
$Y_{1}\not\subseteq T$ or $Y_{2}\subseteq T$. It says that $Y_{1}\to Y_{2}$
holds in $M$ ($M\models Y_{1}\to Y_{2}$) if for all $o\in O$, the set
$\\{o\\}^{\prime}$ respects $Y_{1}\to Y_{2}$. In that case, it is said that
$Y_{1}\to Y_{2}$ is an implication of $M$.

###### Definition. 1

Let ${\mathcal{L}}$ be a set of implications and $L$ be an implication.

  1. 1.

$L$ follows from ${\mathcal{L}}$ (${\mathcal{L}}\models L$) if each subset of
$A$ respecting ${\mathcal{L}}$ also respects $L$.

  2. 2.

${\mathcal{L}}$ is complete if every implication of the context follows from
${\mathcal{L}}$.

  3. 3.

${\mathcal{L}}$ is non-redundant if for each $L\in{\mathcal{L}}$,
${\mathcal{L}}\setminus\\{L\\}\not\models L$.

  4. 4.

${\mathcal{L}}$ is a (implication) basis for $M$ if ${\mathcal{L}}$ is
complete and non-redundant.

It can obtain a basis from the pseudo-intents Guigues & Duquenne (1986) called
Stem Basis (SB):

${\mathcal{L}}=\\{Y\to Y^{\prime\prime}\ :\ Y\mbox{ is a pseudointent}\\}$

A SB for the formal context on live beings is provided in Fig. 2 (right). It
is important to remark that SB is only an example of a basis for a formal
context. In this paper any specific property of the SB can be used, and it can
be replaced by any implication basis.

It is possible to extend $\models$ in relation to any propositional formula
with propositional variables in $A$, by considering each object
$o\in\mathbb{M}$ as a valuation $v_{o}$ on $\mathbb{A}$ defining

$v_{o}(A)=1\Longleftrightarrow(o,A)\in\mathbb{I}$

Thus $M\models F$ if and only if for any $o\in O$ it holds that $v_{o}\models
F$.

The Armstrong rules Armstrong (1974) provides a formal basis for implicational
reasoning:

$\displaystyle\frac{}{X\rightarrow X}\ \ \ \frac{X\rightarrow Y}{X\cup
Z\rightarrow Y},\ \ \ \frac{X\rightarrow Y,\ Y\cup Z\rightarrow W}{X\cup
Z\rightarrow W}$

A set of implications is closed if and only if the set is closed by these
rules Armstrong (1974). By defining $\vdash_{A}$ as the proof relation by
Armstrong rules, it holds that the implicational bases are
$\vdash_{A}$-complete:

###### Theorem 2

Let $\mathcal{L}$ be an implicational basis for $M$, and $L$ an implication.
Then $M\models L$ if and only if ${\mathcal{L}}\vdash_{A}L$

In order to work with formal contexts, stem basis and association rules, the
Conexp111http://sourceforge.net/projects/conexp/ software has been selected.
It is used as a library to build the module which provides the implications
(and association rules) to the reasoning module of our system. The reasoning
module is a production system based on which was designed for Aranda-Corral &
Borrego-Díaz (2010). Initially it works with SB, and entailment is based on
the following result:

###### Theorem 3

Let $\mathcal{L}$ be a basis for $M$ and $\\{A_{1},\dots,A_{n}\\}\cup
Y\subseteq A$. The following conditions are equivalent:

  1. 1.

$\mathcal{S}\cup\\{A_{1},\dots A_{n}\\}\vdash_{p}Y$ ($\vdash_{p}$ is the
entailment with the production system).

  2. 2.

$S\vdash_{A}A_{1},\dots A_{n}\rightarrow Y$

  3. 3.

$M\models\\{A_{1},\dots A_{n}\\}\rightarrow Y$.

### Association rules for a a formal context

We can consider a Stem Basis as an adequate production system in order to
reason. However, Stem Basis is designed for entailing true implications only,
without any exceptions into the object set nor implications with a low number
of counterexamples in the context.

Another more important question arises when it works on predictions. In this
case we are interested in obtaining methods for selecting a result among all
obtained results (even if they are mutually incoherent), and theorem 3 does
not provide such a method. Therefore, it is better to consider association
rules (with confidence) instead of true implications and the initial
production system must be revised for working with confidence.

Researching on logical reasoning methods for association rules is a relatively
recent promising research line Balcázar (2010). In FCA, association rules are
implications between sets of attributes. Confidence and support are defined as
usual. Recall that the support of $X$, $supp(X)$ of a set of attributes X is
defined as the proportion of objects which satisfy every attribute of $X$, and
the confidence of a association rule is $conf(X\to Y)=supp(X\cup
Y)/{supp}(X)$. Confidence can be interpreted as an estimate of the probability
$P(Y|X)$, the probability of an object satisfying every attribute of $Y$ under
the condition that it also satisfies every one of $X$. Conexp software
provides association rules (and their confidence) for formal contexts.

Figure 3: Context based reasoning system

## Reasoning under contextual selection. Logical Foundations

The model (described in Aranda-Corral et al. 2011b ) is composed of events
(objects) which have a number of properties (attributes). They consitute a
universal formal context $\mathbb{M}$ (which we call monster context following
the tradition in Model Theory). Thus $\mathbb{M}$ can be considered as the
global memory from which subcontexts are extracted. Once the specific context
is considered, it is also possible to consider background knowledge $\Delta$
(in form of propositional logic formulas) which would be combined with the
knowledge extracted from formal context (Stem basis or association rules).

###### Definition. 4

Let $\mathbb{M}=(\mathbb{O},\mathbb{A},\mathbb{I})$ be the monster context,
and let $O$ be a set of objects.

  1. 1.

A context on $O$ is a context $M=(O_{1},A,I)$ where $O\subseteq
O_{1}\subseteq\mathbb{O}$

  2. 2.

A contextual selection on $O$ and $M$ is a map
$s:O\to{\mathcal{P}}(O_{1})\times{\mathcal{P}}(A)$

  3. 3.

A contextual KB for an object $o\in O$ w.r.t. a selection $s$ with confidence
$\gamma$ is a subset of association rules with confidence greater or equal to
$\gamma$ of the formal context associated to $s(o)=(s_{1}(o),s_{2}(o))$, that
is, to the context $M(s(o)):=\displaystyle(s_{1}(o),s_{2}(o),I_{\restriction
s_{1}(o)\times s_{2}(o)})$ (note that when condifence is 1 the contextual KB
is a implicational basis).

Contextual KBs is useful for entailing attributes on an object. The reasoning
model on $\mathbb{M}$ is argumentative, where the argument is based on KBs
extracted from subcontexts Aranda-Corral et al. 2011b :

###### Definition. 5

Let $L$ be an implication and $\Delta$ a background knowledge. It is said that
$L$ is a possible consequence of $\mathbb{M}$ under $\Delta$,
$\mathbb{M}\models^{\Delta}_{\exists}L$, if there exists $M$ a nonempty
subcontext of $\mathbb{M}$ such that $M\models\Delta\cup\\{L\\}$.

Note that by theorem 3, when $\Delta$ is a set of implications, it holds that
$\models_{\exists}$ is equivalent to $\vdash_{\exists}$ which is defined by:
$\mathbb{M}\vdash_{\exists}L$ if there exists $M\models\Delta$ a subcontext of
$\mathbb{M}$ such that $S\vdash_{p}L$ (where $S$ is a stem basis for $M$).

### The role of attribute selection for formal contexts

Attributes are essentials in the contextual selection to build good formal
contexts. Association rules are extracted from the contexts and those are used
by the production system. By means of these association rules and some initial
facts based on the match we want to forecast the production system infers the
confidence (probability) for each one of the three possible results of a
match, home team wins, draw or away team wins. Thus attributes constitute one
of the most important and sensitive parts of the system. They are sensitive
because on how they represent the behavior of the teams will depend the
accuracy of the inferred results.

Figure 4: Concept Lattice for the match Málaga-Sevilla (week 31, season
2009-10)

## Confidence-based reasoning system

The reasoning system works on facts of the type $(a,c)$, where $a$ is an
attribute and $c$ is the estimated probability of the trueness of $a$, which
we also call confidence (by similarity with the same term for association
rules). See Aranda-Corral et al. (2011) for a more detailed description of the
reasoning system.

The system has a module for a confidence-based reasoning system (Fig. 3). Its
entries for a match $Team_{1}$ \- $Team_{2}$ are: the contextual Knowledge
basis for a threshold given as rule set and attribute values for the current
match (except 1,X,2) as facts, all of them with a confidence (whose value
depends on the reasoning mode, see below). The production system is executed
and the output is a triple $<(1,c_{1}),(X,c_{x}),(2,c_{2})>$ of attribute,
confidence for this match. The attribute with greater confidence is selected
as the prediction. Production system execution is standard, with several modes
for confidence computing of results based in uncertain reasoning in Expert
Systems Giarratano & Riley (2005). Any attribute/fact $a$ is initialized with
confidence

$conf(a):=\displaystyle\frac{|\\{o\ :\ oIa\\}|+1}{|O|+1}$

## Attributes and formal contexts for soccer league

For both selecting data and building contexts, some assumptions on forecasting
in soccer league matches have been considered. Reconsiderations of such
decisions can be easily computed in the system. First, we consider that the
regularity of team’s behaviour only depends on the contextual selection that
has been considered. This contextual selection is obtained by taking matches
from the last $X$ weeks backwards, starting from the week just before the one
we want to forecast.Second, since FCA methods are used to discover regularity
features, thus it does not consider forecasting exceptions (unexpected
results). Therefore, the model can be considered as a starting point for
betting expert who would adjust attributes, in order to more personalised
criteria.

These attributes have to be computed and used to entail the forecasting. This
analysis is assisted by Conexp. ConExp software is used to compute and analyze
the concept laticces associated to the temporal contexts. In order to select
most interesting attributes for the system, starting from an initial
configuration, user can compute the associated concept lattice and check it.
In this way, attributes goodness (and thresholds) can be evaluated to
reconsider current attribute selection. For example, in Fig. 4, the concept
lattice associated to contextual selection for Málaga-Sevilla match is shown.
This contextual selection is obtained from a given attribute selection and
last 38 weeks matches before. In this concept lattice, the attribute
$ID\\_1\\_T\\_16$ is defined by: ’the budget of $team_{2}$ is greater than
$\gamma_{1}$ times the budget of $team_{1}$’, where $\gamma_{1}$ is the
threshold the expert must estimate. In the concept lattice we can observe that
the biggest concept containing the attributes $team_{2}\\_wins$ and
$ID\\_1\\_T\\_16$ covers the about the 10% of the objects owned by the first
attribute, therefore it is suggested to use the second attribute for reasoning
with association rules to get a prediction.

The system computes the value of an amount of attributes on objects.
Experimentally a boolean combination of attributes is possible. Once the
temporal context has been computed, the system can build contextual selections
by selecting the match and the attribute set. The selection of attributes was
made by considering four kinds of factors: those related with the
classification, the history of teams’ matches in the recent past, results of
direct matches and other non related results, as for example the difference
between team budgets. Seventeen relevant attributes were selected.The
attribute set has three special attributes, $Team_{1}$ wins (1), $Team_{2}$
wins (2) and draws (X).

With respect to data source, they are automatically extracted from RSSSF
Archive222http://www.rsssf.com. Objects are matches and attributes are a list
of features, including temporal stamp (week, year). Data was collected for the
past four years. Actually the size of the context is about 300 objects and 18
attributes (although several of them are parametrized, see section bellow).
Thus, $|I|$ is about 5,100 pairs.

## Attribute selection

We have chosen a small set of attributes with many possibilities through a few
customizable parameters. When these parameters are having set up with proper
values, the set of attributes will represent team’s logical behavior.

Recall that formal concept analysis works with qualitative attributes and all
teams information which we work with are quantitative data. Thus it is
necessary to convert quantitative attributes into qualitative ones. This task
is left to users by choosing a proper threshold to each attribute.

Before choosing the set of base attributes , we have carried out a analysis on
information about soccer results . The aim have been to discover which factors
are more influential in teams behavior and which ones are less influential.
First of all, we have collected any interesting factor found, and after
analyzing each one, individually, we have chosen most suitable ones. Examined
factors can be classified in four different categories (see Table 1): those
related to season’s classification, those related to previous team’s results,
those related to historical direct matches and any other factors. It is worth
to note that to increase possibilities of the attribute set, and considering
the Boolean nature of formal context attributes, we have added the option to
create new ones by means of logical combinations of these attributes.

According to considered factors, the system computes a base set of 18
attributes, which are customizable by some parameters. This will let us to
obtain a diverse set of attributes. In Table 2 attributes are specified. Four
parameters are used:

  * •

Threshold: Parameter to be used to translate quantitative attribute values
into qualitative ones.

  * •

Team: Recall that in the formal context considered, objects are matches but
attributes belongs to team properties. This parameter will set the team from
object (match) on which attribute will be considered. It has two possible
values: {HOME, AWAY}. Thus, usually, we will have twice each attribute at
context, once for home team and once for away.

  * •

Number of Matches: sets the number of past matches to be considered when some
attributes are computed, e.g. the ones associated to previous team results.

  * •

Kind of matches: sets past matches type to be taken into account to compute
some attributes, considering home/away team’s condition at matches. Three
possible values: {MATCHES AS HOME TEAM, MATCHES AS AWAY TEAM, ALL MATCHES}

With these parameters, and the possibility to compound attributes, it is
possible to build a detailed attributes set. Note that experiments show that
simplest and most logical attributes give a good team behavior representation.
Although we consider that a versatile attributes set, as above described, was
necessary because of a huge number of factors can determine the result of a
soccer match. Task of customizing the attribute set is left to users, and it
is the most important one in forecasting process. Thus, a basic soccer
knowledge should be required. The goodness of customization will determine
system results.

Factors | Correlation Degree | Used?
---|---|---
Associated to the classification in the league |  |
Team in the first classification level | medium/high | yes
Team in the last classification level | medium/high | yes
Difference between team’s classifications | medium/high | yes
Team was in a different league last year | medium | no
Team socred a important number of goals (in the last matches) | medium/low | no
Associated to previous results of the team |  |
Number of consecutive won matches. | high | yes
Number of consecutive lost matches. | high | yes
Number of consecutive draws. | medium | yes
Number of non consecutive won matches in previous weeks. | high | yes
Number of non consecutive lost matches in previous weeks. | high | yes
Number of non consecutive draws in previous weeks. | medium/high | yes
Points collected in previous weeks. | medium/high | yes
Factors related with directed matches (incluidas previous years) |  |
Number of wins in previous directed matchs | medium/high | yes
number of losts in previous directed matchs | medium/high | yes
number of draws in previous directed matchs | medium/high | yes
Other Factors |  |
Number of red cards collected by the team’s players. | low | no
Wheather the day and the city where the match took place | medium | no (hard to parametrize)
Motivation because of the fans support when playing as home team. | high | no (hard to parametrize, subjective)
Team hires a new coach. | high | no (only useful when new coach hired)
Some players of the team are selected for their National Team. | medium/Low | no (relevant for some nationalities)
Difference between team’s budgets. | high | yes
One or more important team’s players are injured. | medium | no (hard to automatically collect the data)
Cups collected in the lasts years. | low | no (only for a few of teams)
Table 1: Factors considered for selecting/building attributes

## Computing problems

The way of competition causes to take into account some special situations for
computing attributes values. In this section we describe the main problems
emerged and how they were fixed. Roughly speaking, these main problems
concerns to initial matches in season.

### Beginning of a new season: week 0

This problem is not hard, but as many others unavoidable, and a solution
becomes essential. It happens when computing an attribute value related to
league standings to forecast first week of a season. As any previous week has
been played yet, there is not way to build a standing table.

When teams in current season remain in the same league as last, a trivial
solution is to take into account positions and matches in last weeks of
previous season. If the team played in a higher division than last season, it
will be at the first position in the standing. Otherwise, if the team played
in a lower division, it will be considered at last position.

### Missing matches in attribute computation

Other problem, closely related to previous one, is when not enough previous
matches are available to compute an attribute. Solution pass through taking
lasts matches of last season as if they were in a continuous temporal line.
This is not so simple, because of some teams were not playing at same division
last season. Indeed, when playing in a lower or higher division, difficulty of
division changes and matches cannot be compared into the same way. Therefore,
we need to handle the situation of a team playing in a different division from
current season division.

Other troubled situation where there are not enough matches for attribute
computation is to compute results for directed matches between two teams
because of there is only a few of such matches in the data source.

For these two related situations we offer two solutions. First is to compute
attribute with a null value, but in this way we are giving a fake information
to the system. We are setting that attribute is not true but, in fact, we have
not information enought to determine it, so a better approach is required.
Chosen solution is based on adjusting attribute’s threshold. The value of this
threshold is decreased proportionally to relation between number of required
matches and number of available matches. Threshold $\gamma$ is revised by

$\gamma_{new}=\gamma_{old}\cdot\frac{\mbox{number of match results
available}}{\mbox{number of match results needed}}$

When number of required matches is too high and number of available matches is
low, it looks like we are giving fake information to system again, but our
experience shows that collateral effects of this approach are worthless
compared to compute attributes with a null value.

## Attribute selection vs expert system behaviour

In general terms, current base attribute set behavior forecast the most
possible results of a match is quite good, in regular conditions. Even so,
some experiments, in order to study attribute’s behavior, have been developed.

### Strict attributes

An attribute is strict when only a few objects can satisfy it, because of its
threshold is too high. By working with sets of strict attributes, we can
assure that they estimate the teams behavior better than other sets. Thus,
with strict attributes, we will have very reliable estimates, but just only
for very few matches, and non for most of others. In the other hand, using
less strict attributes, system will produce less reliable estimations but for
a big scope. So it is essential to find a balance between these two opposite
situations: reliability of attribute set against number of matches without
information. A good solution could be to build and use different attribute
sets, ones more strict and others less. Thus, less strict attribute sets will
be used when strict ones fail doing an estimation.

Attribute |  Configurable parameters
---|---
1) Number of non consecutive won matches in previous weeks $>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Number of Matchs$>$ $<$Matchs$>$
2) Number of non consecutive lost matches in previous weeks $>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Number of Matchs$>$ $<$Matchs$>$
3) Number of non consecutive draws in previous weeks $>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Number of Matchs$>$ $<$Matchs$>$
4) Points collected in previous matches$>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Number of Matchs$>$ $<$Matchs$>$
5) Position in the classification based on previous matches$>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Number of Matchs$>$ $<$Matchs$>$
6) Number of positions over the opponent in the classification based on previous matches$>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Number of Matchs$>$ $<$Matchs$>$
7) Number of positions under the opponent in the classification based on previous matches$>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Number of Matchs$>$ $<$Matchs$>$
8) Number of wins in previous directed matchs (included previos leagues) $>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Number of Matchs$>$ $<$Matchs$>$
9) Number of losts in previous directed matchs (included previos leagues) $>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Number of Matchs$>$ $<$Matchs$>$
10) Number of drawns in previous directed matchs (included previos leagues) $>$ threshold |  $<$threshold$>$ $<$Number of Matchs$>$ $<$Matchs$>$
11) Position in the classification $>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Matchs$>$
12) Number of positions over the opponent in the classification$>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Matchs$>$
13) Number of positions under the opponent in the classification$>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Matchs$>$
14) Number of consecutive won matches$>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Matchs$>$
15) Number of consecutive lost matches$>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Matchs$>$
16) Number of consecutive draws$>$ threshold |  $<$threshold$>$ $<$Team$>$ $<$Matchs$>$
17) Team’s budget Y times bigger than opponent’s budget (Y $>$ threshold) |  $<$threshold$>$ $<$Team$>$
18) Team’s budget Y times smaller than opponent’s budget (Y $>$ threshold) |  $<$threshold$>$ $<$Team$>$
Table 2: Attributes and parameters

## Trends towards the victory of the home team

It is a fact that, in soccer, it is more probable a victory from home team
than away team. To deal with this, we offer two different approaches. First,
modelling the teams behavior and second computing confidence values. For
modeling teams behavior (attribute set customization) it is a good practice to
use attributes with low exhaustive thresholds for home team and more exigent
threshold for attributes related to away team. Therefore, it will be easier
for home team to satisfy an attribute than away team. It is possible to
imitate this trend based on this approach.

Around 50% of played matches finish with victory of home team. This means that
the attribute value, corresponding to matches result, will be ’home team
victory’ around 50% of objects from formal context. As consequence of the
former, many rules from the inferred association rules will contain the
attribute ’result = home team victory’ within their conclusions. Thus when
forecasting a match the system will infer, in most of cases, ’home team
victory’ as consequence of overestimation confidence value for this result. It
is possible to avoid this effect easily, just applying a decreasing
(reduction) factor over confidence for ’home team victory’. It is estimated by
means of experiments.

Figure 5: KB fragment from Fig. 4

## Results

Following the process described above, an experiment was run for the Spanish
premier soccer league from 2009-10. Attributes were selected according the
experience of an expert, and contextual KB is computed (in Fig. 5 a KB
fragment for Málaga-Sevilla match is shown). From this selection
$\vdash_{\exists}$ is computed for each match in each week.

Figure 6: Correct predictions on the last 17 weeks of the season 2010-11

2009-10 season: Experiments with the system show forecasts of about 58.16% by
a contextual selection based on the previous 38 matches of each team. Such a
percentage of hits for a qualitative reasoning system may be considered as an
acceptable result comparable with expectable results of experts Goldstein &
Gigerenzer (2009); Andersson et al. (2003). Experiments with other contextual
selections shows an increase in the number of hits by about 7% in the second
half of the season. The reason is that data from the first half provides more
recent information on teams and past matches.

2010-11 season: According to the idea commented above, we have evaluated the
system in the second half of 2010-11 soccer season. A way to evaluate how good
is this forecasting sistem is comparing number of successes in our pool with
the most popular betting selections. This popular selections are collected
from the most voted results for each match, published at state agency web that
controls soccer pools. In Fig. 6 both results are compared. Our hits are in
blue and popular ones in green and last seventeen weeks from 2010-11 season
are represented. Note that Spanish soccer pools are over 15 matches.

## Conclusions and Future Work

Figure 7: Comparative of correct predictions on the whole season 2010-11.
Percentages

The challenge to detect emergent concepts for reasoning about complex systems
represents an exciting researching field. Concepts with qualitative nature are
extracted from data only considering partial features of complex system
dynamics, a partial understanding of system. In this paper, FCA is applied to
this aim with a specific application. The selection attribute problem based on
FCA-based reasoning system for sport forecasting is analysed. In fact, the
reasoning system is a computational logic model for bounded rationality. The
model is concerned with association rule reasoning and it does not use -in its
current form- more sophisticated probability tools (as for example Min et al.
(2008)). As is stated in Goldstein & Gigerenzer (1996), the theory of
probabilistic mental models assumes that inferences about unknown states of
the world are based on probability cues Brunswik (1955). It can say that
confidence of association rules extracted from subcontexts play the role of
probability cues.

Any statistical approaches have been taken into account, because of it was not
the aim of this paper. Although a comparative study of our system against C4.5
classifier has been done. For this, two different attribute selections have
been considered and used for both, C4.5 classifier and our system. The
experiment is to forecast all matches (380) in season 2010-11. In order to
stimate each match result, considering $N$ (weeks) as timestamp, previous
matches are used to build contextual selection (or trainining set in C4.5)
from weeks $N-1$ to $N-19$ (190 objects). Fig. 7 shows the percentage of
correct predictions for our system and C4.5 classifier, using both attribute
selections. Other cols are also shown: ’user’s most voted results’, local team
always win and two random generated. These ’random generated’ cols were built
assuming different weigths per result. It means, $<1:55\%,X:23\%,2:22\%>$ and
$<1:65\%,X:18\%,2:17\%>$ were used, where $1,X,2$ are the probabilities for
forecasting a match with the result: local team wins, drawn and away team
wins, respectively.

It is worth to note that, while classifier achieves highest performances
(58,68%) when number of matches increase from 190 to 380, our system reaches
this highest performance (59,74%) using only 190 instances. This conclusion is
based on our system use some fast and frugal Goldstein & Gigerenzer (1996)
methods, and these are designed to achieve aceptable results using as less as
possible resources.

The relationship of our proposal with Recognition Heuristics Goldstein &
Gigerenzer (2002) (roughly speaking, if one of the possibilities is recognized
and the other is not, then infer that the recognized object has the higher
value with respect to the criterion) is not clear. We may assert that our
model recognises trends in contexts. Trends (represented as association rules)
can be considered as a kind of recognizing method, though. The system is based
on bounded rationality models instead of statistic models, although in future
hybrid models will be considered.

In the short term, we carry on extending our system in order to be able to
combine the results of two or more attribute sets with different exigency
level. Therefore the system will return only one result and more reliable. In
the long term, we aim to extend the model in orfer to obtain a general system
to detect emergent concepts in Complex Systems

After some real betting experiments during current season (2010-2011) with one
customized attribute set, we have observed another intriguing fact. If we take
a look to number of successful predictions per week, we are able to
distinguish some groups of consecutive weeks in which number of correct
predictions is under or over the average. Recall that these predictions are
the logical inferred results by one customized attribute set. This suggests
that it could be possible to find another attribute set, with a different
parameters customization, which it will accomplish the correct predictions of
first attribute set. It means that when first attribute set produce bad
forecasting, second should produce good ones, and vice versa. The reason of
this is that each match there is not only one possible logical result. It
means, when one of firsts teams of current ranking plays against one of lasts
team, attending to ranking criteria, the logical result of this match would be
that first one wins. But if we attend to others, like first team lost last
week and second team won last 5 weeks, this results would be different. Future
works pass through for finding these complementary attribute sets and
detecting when their behaviors change during season in order to select the
proper attribute set to forecast each week.

Finally, we are also analyzing how to finde a weight for matches which allows
the system to work with matches from different divisions, simultaneously. Note
that a winning match at first division will have a higher weight than a
winning at second. This will be really useful at the beginning of season
because of we need to compute attributes related to previous matches results
and teams which are involved played at different divisions last season.

## Acknowledgements

Supported by TIN2009-09492 project of Spanish Ministry of Science and
Innovation, and Excellence project TIC-6064 of Junta de Andalucía cofinanced
with FEDER founds.

## References

  * Inst. Engineering and Technology (2010) Why Spain will win…, Engineering & Technology 5 June - 18 June 2010.
  * Alonso et al. (2008) J. A. Alonso-Jiménez, G. A. Aranda-Corral, J. Borrego-Díaz, and M. M. Fernández-Lebrón, M. J. Hidalgo-Doblado, Extending Attribute Exploration by Means of Boolean Derivatives, Proc. 6th Int. Conf. Concept Lattices and Their Applications (CLA2008), pp. 121-132 (2008).
  * Andersson et al. (2003) P. Andersson, M. Ekman, J. Edman, Forecasting the fast and frugal way: A study of performance and information-processing strategies of experts and non-experts when predicting the World Cup 2002 in soccer, Working Paper Series in Business Administration 2003:9, Stockholm School of Economics.
  * Aranda-Corral & Borrego-Díaz (2010) G. A. Aranda-Corral, J. Borrego-Díaz, Reconciling Knowledge in social tagging web services. Proc. 5th Int. Conf. Hybrid AI Systems (HAIS 2010), LNAI, vol. 6077. Springer-Verlag, Berlin, 383-390 (2010).
  * Aranda-Corral et al. (2011) G. A. Aranda-Corral, J. Borrego-Díaz, J. Galán-Páez, Confidence-Based Reasoning with Local Temporal Formal Contexts. to appear in IWANN 2011, LNCS (2011).
  * (6) G. A. Aranda-Corral, J. Borrego-Díaz, J. Galán-Páez, Bounded Rationality for Data Reasoning based on Formal Concept Analysis. To appear in DEXA Workshop DALI (2011).
  * Armstrong (1974) W. Armstrong, Dependency structures of data base relationships. Proc. of IFIP Congress, Geneva, 580-583 (1974).
  * Balcázar (2010) J.L. Balcázar, Redundancy, Deduction Schemes, and Minimum-Size Bases for Association Rules, Logical Methods in Computer Science 6(2):1-23 (2010).
  * Brunswik (1955) E. Brunswik, Representative design and probabilistic theory in a functional psychology. Psychological Review, (62):193-217 (1955).
  * Ganter & Wille (1999) B. Ganter and R. Wille. Formal Concept Analysis - Mathematical Foundations. Springer, 1999.
  * Giarratano & Riley (2005) J. C. Giarratano, G.D. Riley, Expert Systems: Principles and Programming. Brooks/Cole Publishing Co ( 2005).
  * Goldstein & Gigerenzer (1996) D. G. Goldstein, G. Gigerenzer, Reasoning The Fast and Frugal Way: Models of Bounded Rationality, Psychological Review 103(4): 650-669 (1996).
  * Goldstein & Gigerenzer (2002) D. G. Goldstein, G. Gigerenzer, Models of ecological rationality: the recognition heuristic, Psychological review, 109(1): 75-90 (2002).
  * Goldstein & Gigerenzer (2009) D.G. Goldstein, G. Gigerenzer, Fast and frugal forecasting. International Journal of Forecasting, 25, 760-772 (2009).
  * Guigues & Duquenne (1986) Guigues, J.-L., Duquenne, V.: Familles minimales d’ implications informatives resultant d’un tableau de donnees binaires. Math. Sci. Humaines 95, 5–18 (1986).
  * Imberman et al. (1999) S. P. Imberman, B. Domanski, R. A. Orchard: Using Booleanized Data To Discover Better Relationships Between Metrics. Int. CMG Conference 1999: 530-539
  * Min et al. (2008) B. Min, J. Kim, C. Choe, H. Eom, R. I. McKay, A compound framework for sports results prediction: A football case study. Know.-Based Syst. 21(7):551-562. 2008