General Optimization Framework for Recurrent Reachability Objectives

1 Introduction

In mobile robot path planning, the terrain is represented as a directed graph where the vertices are robot positions, the edges correspond to possible robot moves, and every edge is assigned the corresponding traversal time. A moving strategy specifies how the robot moves from vertex to vertex, and it can be deterministic or randomized.

In this work, we concentrate on infinite-horizon path planning problems where the robot performs a recurring task such as surveillance or periodic maintenance. The standard tool for specifying infinite-horizon objectives are frequency-based objective functions parameterized by the limit frequency of visits to the vertices. Unfortunately, these functions are insufficient for expressing subtle optimization criteria used in specific areas such as robotic patrolling, and cannot faithfully capture all crucial properties of randomized strategies such as deviations/variances of relevant random variables. The latter deficiency represents a major problem often resolved indirectly by considering only deterministic strategies, even in scenarios where randomization achieves strictly better performance and is easy to implement (see Example 1).

Our Contribution. We design and investigate a class of recurrent reachability objective functions based on the following parameters:

1. the limit frequency of edges;
2. the expected time to hit a given set of vertices from another given vertex;
3. the expected square of the time to hit a given set of vertices from another given vertex.

∗ contact author ⟨tony@fi.muni.cz⟩

Note that using (1), one can express the frequency of visits to vertices, and (2) and (3) allow to express the variance and standard deviation of the time to hit a given set of vertices from another given vertex. Thus, the recurrent reachability objective functions can "punish" large deviations from the expected values, allowing for balancing performance with stochastic stability.

Computing an optimal moving strategy for a given recurrent reachability objective is computationally hard. One can easily reduce the NP-hard Hamiltonian cycle problem to the problem of deciding whether the minimum of a certain recurrent reachability objective function is bounded by a given constant. This means there is no efficient strategy synthesis algorithm with optimality guarantees unless P = NP.

We design a strategy synthesis algorithm based on gradient descent applicable to arbitrary recurrent reachability objectives involving piecewise differentiable continuous functions. The algorithm efficiently computes a finite-memory randomized strategy where the memory is used to "remember" some relevant information about the history of visited vertices. Although the (sub)optimality of this strategy is not guaranteed for the reasons mentioned above, our experiments show that the algorithm can solve instances requiring non-trivial insights and produce solutions close to theoretical optima.

Thus, we obtain a general and efficient optimization framework for an expressively rich class of non-linear infinitehorizon objectives capable of solving problems beyond the reach of existing methods.

1.1 Motivating Example

In this section, we give an example illustrating the limitations of frequency-based objectives and deterministic strategies, and we show how randomization and recurrent reachability objectives help to overcome these problems.

In robotic patrolling, some vertices in the terrain graph are declared as targets, and the robot aims to discover possible intrusions at the targets. One standard measure for the protection achieved by a given moving strategy is the maximal average idleness of a target [Huang , 2019;

Almeida et al., 2004; Portugal and Rocha, 2011]. In the language of Markov chains, this corresponds to the maximal renewal time of a target, i.e., maxτ∈T 1/fτ , where T is the set of all targets and fτ is the frequency of visits to τ (recall that 1/fτ is the expected time of revisiting τ).

Existing works about minimizing idleness aim at constructing a deterministic moving strategy, i.e., a cycle in the underlying graph [Huang et al., 2019; Almeida et al., 2004; Portugal and Rocha, 2011]. The next example shows that using randomized strategies brings additional benefits that have not been exploited so far.

Example 1. Consider the graph of Fig. 1a with two targets τ1, τ2 where traversing every edge takes one time unit. Let σb be a deterministic strategy alternately visiting τ1 and τ2, see Fig. 1b. Then, both τ1 and τ2 are revisited in 6 time units, and the maximal renewal time is 6.

At first glance, it seems the robot cannot do any better. However, consider the randomized strategy σc of Fig. 1c. When the robot comes to v1 from τ1, it returns to τ1 with probability x. With the remaining probability 1 - x, it continues to v2. A symmetric decision is taken when the robot comes to v2 from τ2.

As x → 1 in σc, the frequency of visits to τ1, τ2 approaches 1/4, i.e., the renewal time of τ1, τ2 approaches 4. However, pushing x close to 1 results a strategy where the robot needs very long time to move from τ1 to τ2 (and vice versa). Such a strategy is clearly not appropriate for surveillance purposes. So, we may refine the objective and minimize the maximum of renewal times and the expected time of visiting one target from the other (note that this recurrent reachability objective is not frequency-based). A simple computation reveals that the optimal choice is then setting x = (5-√17)/4, yielding the maximum ≈ 5.56. This strategy does not have the above defect and outperforms the deterministic strategy σb.

Another way of eliminating the "defect" of σc for x → 1 is to control the variance of the renewal time of τ1, τ2, which approaches ∞ as x → 1. Using recurrent reachability objectives, this can be expressed as, e.g., minimizing a weighted sum of the maximal renewal time and the maximal variance of renewal time. Thus, one may trade the value of renewal time with its stochastic stability.

1.2 RelatedWork

The finite-horizon path planning problem involving finding a feasible path between two given positions is one of the most researched subject in mobile robotics (see, e.g., [Choset, 2005; LaValle, 2006]). Recent technological advances motivate the study of infinite-horizon path planning problems where the robot performs an uninterrupted task such as persistent data-gathering [Smith et al., 2011] or patrolling [Huang et al., 2019; Almeida et al., 2004; Portugal and Rocha, 2011]. The (classical) vehicle routing problem and the generalized traveling salesman problem [Toth and Vigo, 2001] can also be seen as infinite-horizon path planning problems. The constructed strategies were originally meant for humans (drivers, police squads, etc.) and hence they are deterministic. The only exception is adversarial patrolling based on Stackelberg equilibria [Sinha et al., 2018; Yin et al., 2010] where randomization was soon identified as a crucial tool for decreasing the patroller's predictability.

The existing objectives studied in infinite-horizon path planning problems are mostly based on long-run average quantities related to vertex frequencies or cycle lengths, such as mean payoff or renewal time (see, e.g., [Puterman, 1994]). General-purpose specification languages for infinite-horizon objectives are mostly based on linear temporal logics (see, e.g., [Patrizi et al., 2011; Wolff et al., 2014; Ulusoy et al., 2014; Bhatia et al., 2010]). A formula of such a logic specifies desirable properties of the constructed path, and may include additional mechanisms for identifying a subset of optimal paths. The optimality criteria are typically based on distances between vertices along a path, and the constructed strategies are deterministic.

To the best of our knowledge, the recurrent reachability objective functions represent the first general-purpose specification language allowing to utilize the benefits of randomized strategies and even specify tradeoffs between performance and stochastic stability. Even in a broader context of stochastic programming, the existing works about balancing quantitative features of probabilistic strategies have so far been limited to some variants of mean payoff and limit frequencies [Br´azdil et al., 2017]. These results are not applicable in our setting due to a different technical setup. Furthermore, our specification language is not limited to frequency-based objectives.

2 The Model

In the rest of this paper, we use N and N+ to denote the sets of non-negative and positive integers. The set of all probability distributions over a finite set A is denoted by Dist(A). A distribution ν over A is positive if ν(a) > 0 for all a ∈ A, and Dirac if ν(a) = 1 for some a ∈ A.

A finite-state Markov chain is a pair M = (S, P) where S is a finite set of states and P : S × S → [0, 1] is a stochastic matrix where the sum of every row is equal to 1. A bottom strongly connected component (BSCC) of M is a maximal B ⊆ S such that for all s, t ∈ B we have that s can reach t with positive probability (i.e., P m(s, t) > 0 for some m ∈ N), and every t reachable from a state of B belongs to B.

We assume familiarity with basic results of ergodic theory and calculus that are recalled at appropriate places.

2.1 TerrainModel

The terrain is modeled as a finite directed graph G = (V,E, tm) where the vertices of V correspond to robot's positions, the edges E ⊆ V × V are possible moves, and tm: E → N+ specifies the traversal time of an edge. Later, we adjoin additional parameters to edges and vertices modeling the costs, importance, etc.

We require that G is strongly connected, i.e., for all v, u ∈ V there is a path from v to u. We write u → v instead of (u, v) ∈ E.

2.2 Moving Strategy

Let us fix a graph G = (V, E, tm), and let M be a non-empty set of memory states. Intuitively, memory states are used to "remember" some information about the history of visited vertices. Since infinite-memory is not implementable, from now on we restrict ourselves to finite-memory strategies.

A robot's configuration (v,m) is determined by the currently visited vertex v and the current memory state m. We use Conf = V ×M to denote the set of all configurations. A configuration of the form (v,m) is written as ̂ v.

When the robot visits a vertex, the next move is chosen randomly according to the current configuration. Formally, a moving strategy for G with memory M is a function σ: Conf →Dist(Conf) such that σ(̂ v)(̂ u) > 0 only if v → u. If σ(̂ v) is a Dirac distribution for every ̂ v ∈ Conf , we say that σ is deterministic.

Every moving strategy σ determines a Markov chain Gσ where Conf is the set of states and P(̂ v, ̂ u) = σ(̂ v)(̂ u). The edges of Gσ are defined by ̂ v → ̂ u iff v → u. Note that some edges may have zero probability, i.e., σ(̂ v)(̂ u) = 0, but the BSCCs of Gσ are determined by the edges with positive probability (see the above definition of Markov chain). The traversal time of an edge ̂ v → ̂ u is the same as in G, i.e., equal to tm(v, u).

2.3 Recurrent Reachability Objectives

For the rest of this section, we fix a graph G = (V,E, tm) and a finite set M of memory states.

Atomic Expressions

We start by introducing basic expressions used to construct recurrent reachability objectives.

A walk in Gσ is an infinite sequence w = ̂ v0, ̂ v1, . . . such that ̂ vi → ̂ vi+1 for all i ∈ N. Let C ⊆ Conf. We say that w hits C in time t if t = ∑m-1 i=0 tm(vi, vi+1), where m is the least index j such that ̂ vj ∈ C. If there is no such j, we put t =∞. For all ̂ v ∈ Conf and C ⊆ Conf , we use T(̂ v→C) to denote the expected hitting time of C by a walk initiated in ̂ v (if ̂ v ∈ C, then T(̂ v→C) = 0), and T2 (̂ v→C) to denote the expected square of the hitting time of C by a walk initiated in ̂ v. Furthermore, for every walk w = ̂ v0, ̂ v1, . . . and every edge ̂ e = ̂ v → ̂ u, we define the frequency of ̂ e along w as the limit percentage of time spent by executing ̂ e along w, i.e.,

where #̂ e(̂ v0, . . . , ̂ vm+1) is the number of occurrences of ̂ e in the prefix ̂ v0, . . . , ̂ vm+1. It follows from basic results of Markov chain theory that the above limit is defined for almost all walks (i.e., with probability one), and almost all walks w that hit the same BSCC of Gσ have the same F(̂ e, w).

Syntax

Recurrent reachability objective functions are closed-form expressions over numerical constants and atomic expressions of the formT(̂ v→C), T2 (̂ v→C), F(̂ e), and p(̂ e) obtained by using

• addition, multiplication, min, and max that may take arbitrarily many arguments;
• division, where the denominator is an expression over numerical constants and atomic expressions of the form F(̂ e), p(̂ e) built using addition and multiplication.
• other differentiable functions such as square root that are defined for all non-negative arguments.

When defining the arguments of sums, products, min, and max, we may refer to special sets Ac and Ae consisting of active configurations and edges, respectively, whose semantics is defined in the next paragraph.

A recurrent reachability optimization problem is a problem of the form minimize R or maximize R, where R is a recurrent reachability objective function.

Ergodicity

Infinite-horizon objective functions are typically independent of finite prefixes of runs and the initial configuration can be chosen freely. Hence, the objective value for Gσ actually depends only on the objective values attained in the "best" BSCC of Gσ. From now on, we only consider recurrent reachability objective functions R satisfying this condition (this is equivalent to requiring that R can be optimized by an ergodic strategy where Gσ is strongly connected).

Evaluation

Let σ be a moving strategy for G with memory M, and let B be a BSCC of Gσ. For a given recurrent reachability function R, we use R[B] to denote the value of R in B, defined by structural induction as follows:

• atomic expressions T(̂ v→C), T2 (̂ v→C), F(̂ e), and p(̂ e) are evaluated in the way described above (p(̂ e) is the probability of ̂ e assigned by σ). In particular, note that F(̂ e) where ̂ e = ̂ v→̂ u can be positive only if ̂ v, ̂ u ∈ B.
• The set Ac of active configurations is equal to B, and the set Ae of active edges consists of all (̂ v, ̂ u) such that ̂ v, ̂ u ∈ B and σ(̂ v)(̂ u) > 0.
• The addition, multiplication, min and max are evaluated in the expected way. If the set of arguments is parametrized by Ac or Ae, it is constructed for the set of configurations and edges defined in the previous item.

In some cases, R[B] can be undefined (see Section 4).

Finally, we define the σ-value of the objective minimize R or maximize R as the minimal or the maximal R[B] such that B is a BSCC of Gσ where R[B] is defined (if there is no such B, then the σ-value in undefined).

3 Examples

To demonstrate the versatility of recurrent reachability objectives, we present selected examples of concrete objective functions. The list is by no means exhaustive-we show how to capture some of the existing infinite-horizon optimization criteria and how to extend them to control various forms of stochastic instability caused by randomization. Let us emphasize that our aim is to illustrate the expressive power of our optimization framework, not to design the most appropriate objectives capturing the discussed phenomena.

For this section, we fix a graph G = (V, E, tm) and a finite set M of memory states. For a given subset U ⊆ V , we use C U to denote the subset U ×M of configurations.

For simplicity, in the first two subsections we assume that the traversal time of every edge is 1.

Mean Payoff

As a warm-up, consider the concept of mean payoff, i.e., the long-run average payoff per visited vertex. Let α: V → N+ be a payoff function. The goal is to minimize the mean payoff for α. This is formalized as minimize MP, where

Here, Out(̂ v) is the set of all out-going edges of ̂ v. Hence, F (̂ v) is the limit frequency of visits to ̂ v.

Minimizing mean-payoff is computationally easy. However, the costs of vertices visited by an optimal strategy can significantly differ from the mean payoff (i.e., the costs are not distributed sufficiently "smoothly" along a walk). If "smoothness" is important, it can be enforced, e.g., by the objective minimize MP + β · DMP, where β is a suitable weight and

is the standard deviation of the costs per visited vertex. Similarly, we can formalize objectives involving multiple cost/payoff functions and enforce some form of "combined smoothness" if appropriate.

Renewal Time

Let T ⊆ V be a set of targets, and consider the problem of minimizing the maximal renewal time of a target. First, for every ̂ τ ∈ C T , let

where F(·) is defined by (3). Hence, P(̂ τ) is the percentage of visits to ̂ τ among all visits to configurations of C τ , assuming that the denominator is positive. Then, the renewal time of τ , denoted by ERen(τ) is given by

and the expected square of the time needed to revisit τ, denoted by QRen(τ), is expressible as

Minimizing the maximal renewal time is then formalized as minimize maxτ∈T ERen(τ). However, this simple objective does not take into account possible deviations of the renewal time from its mean. This can be captured, e.g., by expressing the standard deviation as

and using minimize maxτ∈T (ERen(τ ) + β · DevRen(τ )) for a suitable weight β.

Patrolling

Let T ⊆ V be a set of targets, and α: T→N+ a function assigning to every target its importance. The damage caused by an attack at a target τ (such as setting a fire) is given as α(τ) · t where t is the time to discover the attack by the robot. The patrolling objective is to minimize the expected damage.

Patrolling problems are studied for adversarial and nonadversarial environments. In the first case, there is an active Attacker knowing the robot's strategy and observing its moves. For the Attacker, an appropriate moment to initiate an attack is when the robot leaves a vertex and starts walking along some edge ̂ v→̂ u. The objective is to minimize the expected damage over all possible attacks, i.e.,

Note that (9) conveniently uses the set Ae of active edges to restrict the max only to "relevant" edges used by the strategy.

In non-adversarial patrolling, the attacks are performed by "nature". Let π be a distribution over T specifying the attack chance (such as the probability of spontaneous ignition). Then, minimizing the expected damage is expressible as minimize EDam, where the function EDam is defined as

Note that if τ is attacked when the robot walks along ̂ v→̂ u, then the robot is in the middle of this edge on average. Hence, the average time to reach τ is tm(v, u)/2 +T(̂ u→C τ ).

Again, we can express the variances/deviations of the relevant random variables (incl. the variance of the expected damage of (10)). These expressions are relatively long, but their construction is straightforward.

4 The Algorithm

The algorithm is based on gradient descent: It starts with a random initial strategy and then repeatedly evaluates the objective function R and modifies the current strategy in the direction of the gradient ∇R (or -∇R for minimization). After a number of iterations, the strategy attaining the best objective value is returned.

Let σ be a moving strategy for a graph G. We show how to evaluate and differentiate R[B] for a given BSCC B of Gσ. The atomic expressions are obtained as unique solutions of linear equations systems. More concretely, for a target set C, active configurations Ac and edges Ae, we have that T(̂ v→C) and T2 (̂ v→C) are undefined for ̂ v ̸∈ Ac. If ̂ v ∈ Ac and Ac ∩ C = ∅, then T(̂ v→C) = T2 (̂ v→C) = ∞.

If Ac ∩ C ̸= ∅, then for every ̂ v ∈ Ac we fix a variable X̂ v and an equation

Then, the tuple of all T(̂ v→C), where ̂ v ∈ Ac, is the unique solution of this system.

Similarly, if Ac ∩ C ̸= ∅, then the tuple of all T2 (̂ v→C), where ̂ v ∈ Ac, is the unique solution of the system where to each ̂ v ∈ Ac, we assign a variable Ŷ v and an equation

where γ(̂ v, ̂ w) = tm(v, w)(tm(v, w) + 2T( ̂ w→C)) + Y ̂ w. To compute the edge frequencies, we fix a variable Ẑ v for every ̂ v ∈ Ac, and an equation

This system, together with the equation ∑̂ v∈Ac Ẑ v = 1, has a unique solution F where F(̂ v) is the frequency of visits to ̂ v. For each edge ̂ e = (̂ v, ̂ w) ∈ Ae, we set D(̂ e) = F(̂ v) · σ(̂ v)( ̂ w) · tm(v, w) and we get

For the other edges ̂ e ̸∈ Ae, we have that F(̂ e) = 0. The value of R[B] is then obtained from the atomic expressions in the straightforward way (when some atomic expression used in R is undefined or the denominator of some fraction of R is zero in B, then R[B] is undefined).

Next, we need to calculate the gradient ∇R. As objectives are, by design, allowed to use only smooth operations with min and max over atomic expressions, the derivatives of R w.r.t. these atomic expressions are well defined almost everywhere. Solutions of systems of linear equations depend smoothly on the parameters and the derivatives of our atomic expressions w.r.t. σ can be calculated as solutions of other linear systems. We use PyTorch Library [Paszke et al., 2019] and its automatic differentiation in our implementation.

However, a na¨ıve update σ ± λ∇R for a step size λ almost never yields a probability distribution (i.e., a valid strategy). The standard approach is to produce strategies from real-valued coefficients by a Softmax function. Any update of these coefficients then leads to a well-defined strategy. The drawback of Softmax is that the resulting distributions never contain zeros (i.e., the strategies always use all edges).

To reach all possible strategies, we cut the small probabilities at a certain threshold (and normalize) by Cutoff function. However, as edges with zero probabilities are excluded from Ae, discontinuities in the objective may occur. For instance, in Patrolling objective (9), the term tm(v, u) is present for an edge ̂ v→̂ u if σ(̂ v)(̂ u) > 0 and drops to zero if σ(̂ v)(̂ u) = 0.

In other words, objective R as a function of real-valued coefficients is a smooth function on an open set with possible jumps at the boundary. In order to make the boundary values accessible by the gradient descent, we relax our discontinuous R to a smooth one, say R∗ . For instance, in Patrolling objective (9), we multiply tm(u, u) by a factor

Algorithm 1 Strategy optimization

coefficients ← Init() for step ∈ steps do strategy ← Softmax(coefficients) // Evaluating relaxed objective and its gradient value←Eval(R∗ , strategy) coefficients.grad ← Gradient(value) // Gaussian noise and Adam optimizer's step coefficients.grad += Noise(step) coefficients += Step(coefficients.grad, step) // Strategy evaluation strategy ← Cutoff(Softmax(coefficients)) value←Eval(R, strategy) Save value, strategy return strategy with the lowest/highest value

HardTanh(εσ(̂ v, ̂ u)), which interpolates the values 0 and 1 continuously. Moreover, for a more efficient gradient propagation, we replace each min and max with their relaxed variants as in [Klaska et al., 2018].

The final algorithm is described in Algorithms 1. Strategy coefficients are initialized at random. In every step, we compute the relaxed objective R∗ value of the current strategy and update the coefficients based on the gradient ∇R∗ using Adam optimizer [Kingma and Ba, 2015]. We also add a decaying Gaussian noise to the gradient. Then, we round the strategy using Cutoff and compute its true objective value R. Algorithms 1 can be run repeatedly to increase the chance of producing a strategy with better value.

The algorithm is efficient because it does not involve any computationally demanding tasks, but it does not guarantee (sub)optimality of the constructed strategies. This is unavoidable due to the NP-hardness of some of the recurrent reachability objectives.

5 Experiments

There is no previous work setting the baseline for evaluating the quality of strategies produced by our algorithm. Therefore, we selected two representative examples where the tradeoffs between performance and stability are not easy to discover, but the functionality of the synthesized strategies can still be analyzed by hand and compared against the best achievable outcomes identified by theoretical analysis. 1

Mean Payoff

We minimize the objective MP + β · DMP defined in (2) and (4) for the graph of Fig. 2. The graph contains three cycles with the corresponding MP and DMP as in the table of Fig. 2.

For almost every β, the objective's minimizer is precisely one of the three cycles. More precisely, it is the cycle 7-0-5-7 for all β ∈ [0, ϱ1], the cycle 7-6-5-7 for all β ∈ [ϱ1, ϱ2], and the cycle 7-6-7 for all β ∈ [ϱ2,∞), where ϱ1 ≈ 0.73 and ϱ2 ≈ 1.16. Ideally, our algorithm should find the corresponding cycle for every β.

1 The code for reproducing the results is available at https:// gitlab.fi.muni.cz/formela/2022-ijcai-optimization-framework. See also the latest version at https://gitlab.fi.muni.cz/formela/regstar.

The algorithm outcomes are shown in Fig. 3. For every β, we perform 100 trials (i.e., construct 100 strategies with one memory state), and report the corresponding MP + β · DMP value. The value of the best strategy achieved for a given β is represented by a "circle"; the other "crosses" represent the values of non-optimal strategies. Observe that the circles agree with the ideal outcomes.

Renewal Time

Consider the graph of Fig. 4a. We minimize the objective maxτ∈T (ERen(τ) + β · DevRen(τ)) defined in (6) and (8). The outcomes of our algorithm for two memory states are shown in Fig. 5. For each β ranging from 0 to 0.3, we run 100 trials and report the expected renewal time and the corresponding standard deviation of the resulting 100 strategies; the best values are highlighted by solid dots. The values of the obtained strategies are concentrated near the best one, showing the stability of the optimization.

For smaller β, the constructed strategies have a smaller renewal time but large deviation, and they work as shown in Fig. 4b. That is, they tend to re-visit τ1 from v1 and τ2 from v2. As x, y → 1, the maximal renewal time approaches 40 and the standard deviation approaches ∞.

For larger β, where the standard deviation is punished more severely, the algorithm tends to decrease x, y. Note that for x = y = 0, the strategy of Fig. 4b becomes deterministic with renewal time 60 and zero deviation. However, this point is not reached by the curve of Fig. 5. The reason is that for β ≈ 0.27, the algorithm discovers and strongly prefers a completely different strategy, which goes through v3 instead (see Fig. 4c), with maximal renewal time 52 and zero deviation (this is the best strategy with zero deviation).

6 Conclusion

The obtained optimization framework for recurrent reachability objectives is applicable not only to graphs, but also to Markov decision processes without any additional effort. Here, the randomization introduced by the strategies is combined with the "inherent randomization" of the model. Here, stochastic instability cannot be removed completely, and a precise understanding of the principal limits of this effort is a challenging direction for future research.

Acknowledgements

This work is supported by the Czech Science Foundation, Grant No. 21-24711S, and from Operational Programme Research, Development and Education - Project Postdoc2MUNI No. CZ.02.2.69/0.0/0.0/18 053/0016952.