A Boyer

S Ben Dhia

Effect of Electrical Stresses on Digital Integrated Circuits Power Integrity

Keywords: Integrated circuits, power integrity, accelerated aging, ICEM modelling I

Recent studies have shown that integrated circuit aging modifies electromagnetic emission significantly. The proposed paper aims at evaluating the impact of aging on the power integrity of digital integrated circuits and clarifying its origin. On-chip measurements of power supply voltage bounces in a CMOS 90 nm technology test chip are combined with electric stress to characterize the influence of aging on power integrity. Simulation based on ICEM modeling modified by an empirical coefficient in order to take into account the circuit aging is proposed to model the evolution of the power integrity induced by device aging.

INTRODUCTION

Recently, many publications have forecast a decrease of new CMOS technology device lifetime down to few years [START_REF] Srinivasan | The impact of technology scaling on lifetime reliability[END_REF], with anticipated appearance of hard or soft failures due to wear-out mechanisms (e.g. hot carrier injection, negative bias instability, electromigration…) [START_REF] Mcpherson | Reliability trends with advanced CMOS scaling and the implications for design[END_REF] [START_REF] White | Scaled CMOS technology reliability user's guide[END_REF]. The drift of the electrical characteristics of semiconductor devices can have direct consequences on integrated circuit electromagnetic emission and power integrity (PI). Recently, some publications have shown that accelerated aging tests such as high or low temperature operating life, thermal cycling, or electrical overstress induce a significant variation of electromagnetic emission produced by power supply units [START_REF] Montanari | Impact of thermal stress on the characteristics of conducted emissions[END_REF], high side switch devices [START_REF] Boyer | Characterization of the evolution of IC emissions after accelerated aging[END_REF] or I/O buffers [START_REF] Ben Dhia | Characterization of the electromagnetic modelling drifts of a nanoscale IC after accelerated life tests[END_REF]. However, these studies do not address the evolution of power integrity and do not clarify the origins of emission change.

This paper intends to clarify the impact of IC aging on PI experimentally and by simulation. A test chip designed in Freescale CMOS 90 nm technology, which includes a digital core and on-chip sensors dedicated to the measurement of power supply voltage fluctuations, has been developed to characterize the evolution of PI vs. time. In order to explain the effect of IC aging on power integrity, an equivalent model of the circuit based on the Integrated Circuit Emission Model (ICEM) approach [START_REF]Models of Integrated Circuits for EMI behavioral simulation -ICEM-CE, ICEM Conducted Emission Model[END_REF] is developed to simulate the PI. A simple empirical coefficient is introduced in the model to simulate the evolution of the PI with time. The paper is organized as follows: after a description of the circuit under test, on-chip sensors and experimental set-up, the measurements of the evolution of the power supply voltage bounces are presented. Then, the proposed modeling approach of the circuit power PI is described and, finally, simulation and measurement results are compared in order to validate both our hypothesis about PI evolution with time and the proposed model.

II. EXPERIMENTAL SET-UP

A. Test chip description

A dedicated test chip has been designed in Freescale CMOS 90 nm technology for IC emission and susceptibility modeling, and characterization of aging impact on EMC of ICs. In particular, the test chip includes a digital core with a dedicated power supply voltage equal to 1.2 V. This structure is a basic 100-stage shift register, synchronized by a 40 MHz clock.

B. On-chip voltage sensor

In order to monitor the voltage drops on the power supply of the digital core, an on-chip voltage sensor is placed along the power supply rail of the core. This sensor is able to measure the waveform of voltage bounce across non accessible nodes with a precise time resolution (up to 15 ps). Its analog bandwidth is equal to 10 GHz. Its principle and its implementation in the test chip are explained in [START_REF] Boyer | Characterizing circuit susceptibility with on-chip sensors[END_REF]. In order to prevent noise coupling with the digital core, the designed sensor has a dedicated power supply and is isolated from the IC substrate by a buried N layer. Due to its small input capacitance (4 fF), the sensor is not intrusive and does not alter the performance of the tested block. Although the electrical stress applied to the circuit under test can partially alter the performances of the sensor, it can be recalibrated before any measurements. The calibration process is necessary to compensate effects of imperfections due to non ideal behavior and mismatch on voltage and frequency responses.

C. Description of the experimental set-up

The experiment is based on a measure-stress-measure flow, which consists in applying electrical stress on the circuit under test and interrupts the stress during short period regularly for characterization purpose. With this procedure, the characteristics of the circuit are monitored at various degree of aging.

The choice of stress conditions (stress voltage and duration) is based on a preliminary failure analysis of MOS devices developed in this technology [9] [10]. For DC stress voltages ranging from 3 to 4 V and applied between drain and source of NMOS and PMOS devices, significant degradations of threshold voltage and carrier mobility are induced due to HCI and/or NBTI after several hundreds of seconds. The amount of degradation is related to stress voltage, duration, transistor geometry and gate oxide thickness. A 3.6 V electrical stress is applied during 120 minutes in order to validate the influence of the stress voltage on power integrity change. Sensor measurements of power supply voltage fluctuations are performed after each stress interval. The sensor is not supplied during stress phases in order to reduce its aging. Recalibration is done after each stress period, although experimental characterizations have not shown any significant degradation of the sensor.

III. EXPERIMENTAL RESULTS: EVOLUTION OF POWER INTEGRITY AFTER ELECTRICAL STRESS

A. Initial measurement of power integrity

B. Impact of electrical stress on digital core power integrity

After stress, the core remains operational and its quiescent current has not changed. However, the core timing characteristics have evolved. A specific part of the core has been designed to measure the propagation delay through one D-latch and 100 inverters. The propagation delay through the core after stress increases up to 31 % depending on the stress duration. The electrical stress applied on core power supply accelerates wear-out mechanisms such as HCI and/or NBTI. They increase the propagation delay of each gate of the core. Fig. 2 presents the power supply voltage bounces measured by the on-chip sensor before and after 3.6 V stresses. A -30 % reduction of the peak-to-peak amplitude is observed d. The waveform of the signal is also modified. The first peak is less steep. The period of the resonance oscillation has not changed. Its amplitude is reduced, but it is still damped at the same rate. This observation indicates that the package inductance, the equivalent capacitance of the digital and resistance linked to the power distribution network (PDN) have not been affected by the electrical stress significantly. This hypothesis is confirmed by impedance measurement of the PDN with a vector network analyzer, as shown in Fig. 3. Whatever the electrical stress amplitude and duration, the impedance of the circuit power distribution network remains constant over a large frequency range. Fig. 3. Measurements of the impedance of the power distribution network of the digital core before and after electrical stress From these experimental results, the following hypothesis can be proposed to explain the evolution of power integrity of the circuit: the reduction of power supply voltage bounce is only linked to the change of transient current produced by the core activity. Wear-out mechanisms accelerated by electrical stress have reduced mobility of carrier in MOS devices so the switching transient current has been spread. The consequence is a reduction of the high frequency content of the switching transient current, which has a direct impact not only on power integrity but also on conducted emission. The next part intends to validate this hypothesis by the modeling of the evolution of the power integrity due to circuit aging.

IV. MODELING OF DIGITAL CORE AGING EFFECT ON POWER INTEGRITY

A. Model construction and validation

The model construction is based on ICEM approach [START_REF]Models of Integrated Circuits for EMI behavioral simulation -ICEM-CE, ICEM Conducted Emission Model[END_REF]. The model includes two main parts: the internal activity (IA) block which models the transient current produced by circuit operation, and the power distribution network (PDN) which models the filtering effect of the transient current due to IC and package.

A linear model based on an equivalent RLC circuit is proposed for the PDN. The parameters of the model are extracted from measurements. The passive element values are fitted from an impedance measurement between Vdd and Vss pins of the digital core made with vector network analyzer, as shown in Fig. 3. A very simple approach is used for IA modeling: two triangular waveform current sources describe the current produced at each clock edge. Even though such a waveform is quite simplistic, it provides a good estimation of the actual current waveform which can be tuned without a precise analysis of the circuit power consumption. The waveforms of the IA current source are fitted from current and Vdd bounce measurements. For each current source, only four parameters are adjusted: current peak minimum and maximum I0 and I1, rise and fall times Tr and Tf of the peak. Fig. 4 presents a simplified structure of the ICEM model of the digital core. 5 presents a comparison between measurement and simulation of the power supply voltage bounce before electrical stress. The simulated waveform is similar in term of peak-to-peak amplitude, pseudo-oscillation period and damping. Although the correlation between measured and simulated curves is not totally perfect, the model offers a sufficient accuracy for the aim of the study. A better correlation would rely on a more complex transient current waveform, extracted from a precise analysis of the power consumption of the digital core.

B. Simulation of electrical stress impact on power integrity

Wear-out mechanisms accelerated by electrical stress tends to degrade carrier mobility and threshold voltage of MOS devices which constitutes the gates of the digital core. It leads to a reduction of the saturation current of MOS devices and an increase of the propagation delay. In other words, it leads to a spreading of the current pulse induced by the switching of the gates of the digital core. However, as the charge transfer associated to each gate switching does not change after stress, the product between current pulse duration and current pulse amplitude remains constant. In order to take into account the aging of the circuit in the ICEM model, the following simple methodology is proposed. Only three parameters of the equivalent current sources in IA block are changed to spread the current pulse created by the digital core: the rise and fall times Tr and Tf of the current pulse are increased while its amplitude i is reduced by an empirical coefficient δ called "degradation ratio", as shown by equations 1 and 2. If δ is equal to 0, it means that the digital core is not degraded and the current pulse is not spread. If δ increases, a larger amount of degradation is considered and the current pulse is spread. In our ICEM model, the same degradation ratio is applied on both current sources of the IA block.

i stress = i initial .(1-δ), 0 ≤ δ ≤ 1

(1)

t r stress = t r initial /(1-δ), 0 ≤ δ ≤ 1 (2)
By simulation, the effect of δ on the power integrity can be studied. A first study consists in finding the peak-to-peak amplitude of the power supply voltage fluctuation vs. the applied δ. Fig. 6 presents the evolution of the peak-to-peak amplitude of the power supply bounce when δ is increased in both current sources symmetrically. The result confirms that the power supply bounce is reduced when the current pulse is spread. However, we need to confirm that our approach is able to model the evolution of the power supply voltage waveform correctly by a comparison with the on-chip measurements done in stressed cores. Although the coefficient δ is empirical and its value for a given amount of stress is unknown initially, the curve shown in Fig. 9 can help us to choose a reasonable value. From on-chip measurement results, a value of δ is selected to obtain the same voltage fluctuation amplitude. Fig. 7 presents the comparison between the measurements and simulations of the power supply voltage bounces before and after the stress condition described in part II.C. The coefficient δ is set to 0.58 to model the effect of the 3.6 V stress applied for 120 minutes. The correlation between measurement and simulation curves is acceptable. Our basic ICEM model modified by the empirical degradation ratio is able to reproduce the evolution of the power supply voltage bounce with a reasonable accuracy.

These results confirm the relevance of our hypothesis about the origin of the evolution of the power integrity after circuit aging accelerated by an electrical stress. The degradation mechanisms induced a MOS device level tends to spread the current pulse produced by the switching of the gates of the digital circuit, leading to a decrease of the power supply voltage bounce. Moreover, these results demonstrate that the evolution of the power integrity can be predicted by a correct modeling of the change of the circuit current consumption. A complex methodology based on an accurate prediction of the power consumption from the circuit netlist combined with the modeling of MOS device degradation mechanisms could provide an accurate estimation of the evolution of the power supply voltage bounce. However, a more simple and non confidential approach based on an ICEM model affected by an empirical coefficient to take into account the IC aging can also provide a reasonable estimation of the evolution of the power integrity.

V. CONCLUSION

The proposed paper aims at clarifying the impact of circuit aging on power integrity. Electrical stresses applied on a digital circuit lead to a reduction of the power supply voltage bounce. This improvement is linked to a change of the transient current linked to the circuit activity. This hypothesis has been confirmed by the modeling of the circuit activity based on ICEM approach. The impact of the electrical stress on the transient consumption is modeled by an empirical coefficient. This basic and non confidential model reproduces the power supply voltage bounces with an acceptable accuracy. This type of modeling approach could also be used to predict the evolution of conducted emission from digital integrated circuits, as shown in [START_REF] Ben Dhia | Characterization of the electromagnetic modelling drifts of a nanoscale IC after accelerated life tests[END_REF].

Fig 1

 1 presents the power supply voltage fluctuations produced by the digital core activity measured by the on-chip sensor. Positions of clock edges are indicated. Rapid droops appears at each clock switching. These events are linked to the rapid current demand from every gates and latches of the core. A damped oscillation with a pseudo-period equal to 4.5 ns follows the first rapid current impulsion. It is linked to the antiresonance produced by on-chip capacitor and package inductor (see part V for more details). This type of noise is also measured on Vss node. Similar voltage fluctuations are also measured on the ground node of the circuit.

Fig. 1 .

 1 Fig. 1. Measurement of the power supply voltage bounce of the digital core

Fig. 2 .

 2 Fig. 2. Evolution of the corepower supply voltage bounce after 120 minutes of 3.6 V electrical stress

Fig. 4 .

 4 Fig. 4. ICEM model of the digital core SPICE transient simulations are performed to compute the waveform of the power supply of the digital core and extract the peak-to-peak amplitude of the voltage fluctuation. Fig.5presents a comparison between measurement and simulation of the power supply voltage bounce before electrical stress. The simulated waveform is similar in term of peak-to-peak amplitude, pseudo-oscillation period and damping. Although the correlation between measured and simulated curves is not totally perfect, the model offers a sufficient accuracy for the aim of the study. A better correlation would rely on a more complex transient current waveform, extracted from a precise analysis of the power consumption of the digital core.

Fig. 5 .

 5 Fig. 5. Comparison between measurement and simulation of the digital core power supply voltage bounce before electrical stress

Fig. 6 .

 6 Fig. 6. Simulated evolution of the peak-to-peak amplitude of the power supply voltage bounce vs. degradation ratio

Fig. 7 .

 7 Fig. 7. Comparison between simulated power supply voltage bounce after 120 minutes of 3.6 V electrical stress

ACKNOWLEDGMENT

The authors would like to thank Bertrand Vrignon and John Shepherd from Freescale Semiconductor, Toulouse, for test chip development and their constant support.


Hugo Gimbert
email: hugo.gimbert@labri.fr

Wiesław Zielonka
email: wieslaw.zielonka@liafa.jussieu.fr

Blackwell-Optimal Strategies in Priority Mean-Payoff Games

We examine perfect information stochastic mean-payoff games -a class of games containing as special sub-classes the usual mean-payoff games and parity games. We show that deterministic memoryless strategies that are optimal for discounted games with state-dependent discount factors close to 1 are optimal for priority mean-payoff games establishing a strong link between these two classes.

Introduction

One of the recurring themes in the theory of stochastic games is the interplay between discounted games and mean-payoff games. This culminates in the seminal paper of Mertens and Neyman [START_REF] Mertens | Stochastic Games[END_REF] showing that mean-payoff games have a value and this value is the limit of the values of discounted games when the discount factor tends to 1. Note however that optimal strategies in both games are very different. As shown by Shapley [START_REF] Shapley | Stochastic games[END_REF] discounted stochastic games admit memoryless optimal strategies. On the other hand mean-payoff games do not have optimal strategies, they have only ε-optimal strategies and to play optimally players need an unbounded memory.

The connections between discounted and mean-payoff games become much tighter when we consider perfect information stochastic games (games where players play in turns). As discovered by Blackwell [START_REF] Blackwell | Discrete dynamic programming[END_REF], if the discount factor is close to 1 then optimal memoryless deterministic strategies in discounted games are also optimal for mean-payoff games (but not the other way round). Thus both games are related not only by their values but also through their optimal strategies. Blackwell's result extends easily to two-player perfect information stochastic games.

What happens if instead of mean-payoff games we consider parity games -a class of games more directly relevant to computer science [START_REF]Automata, Logics, and Infinite Games[END_REF]? In particular, are parity games related to discounted games?

It is well known that deterministic mean-payoff games and parity games are related, see [START_REF] Björklund | Memoryless determinacy of parity and mean payoff games: a simple proof[END_REF]. The first insight that there is some link between parity games and discounted games is due to de Alfaro at al. [START_REF] De Alfaro | Discounting the Future in Systems Theory[END_REF]. It turns out that parity games are related to multi-discounted games with multiple discount factors that depend on the state. This should be compared with discounted games with a unique, state independent, discount factor which are used in the study of mean-payoff games.

Like in the classical theory of stochastic games, we examine what happens when the discount factors tend to 1, the idea is that in the limit we want to obtain parity games. Note that if we have several state dependent discount factors λ 1 , . . . λ k then there are two possibilities to approach 1:

• we can study the iterated limit lim λ 1 →1 . . . lim λ k →1 when discount factors tend to 1 one after another (i.e. first we go to 1 with the discount factor λ k associated with some group of states, when the limit is reached then we go to 1 with the next discount factor λ k-1 etc.,

• another possibility it to examine a simultaneous limit when all factors go to 1 at the same time but with different rates, this will be made precise in Section 4.

The first approach is easier to handle than the second but it leads to weaker results, in particular we lose the links between optimal strategies in discounted games and optimal strategies in parity games. We began our examinations of relations between discounted and parity games in [START_REF] Gimbert | Deterministic priority mean-payoff games as limits of discounted games[END_REF][START_REF] Gimbert | Applying Blackwell optimality: priority mean-payoff games as limits of multi-discounted games[END_REF] where we limited ourselves to deterministic games. Already this preliminary work revealed that the natural framework for such a study goes far beyond parity games. In fact parity games are related to a very particular restricted class of discounted games and when we examine all multi-discounted games then at the limit we obtain a new natural class of games -priority mean-payoff games. This new class contains the usual mean-payoff games and parity games as special subclasses.

The next natural step is to try to extends the results that hold for deterministic games to perfect information stochastic games. In two papers [START_REF] Gimbert | Perfect information stochastic priority games[END_REF][START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF] we obtained some partial results in this direction. In [START_REF] Gimbert | Perfect information stochastic priority games[END_REF] we considered a class of games that contains parity games but does not contain mean-payoff games. We showed that such games can be seen as an iterated limit of discounted games -a limit in a very strong sense, not only the value of the discounted games converges to the value of the parity game but also optimal strategies in one class are inherited by the class of games obtained in the limit. But these results are not satisfactory for two reasons, the class of games for which we were able to carry our study is too restrictive. This class involves some technical restrictions on discounted games, which are natural for parity games, but not so natural for discounted games. The second problem comes from the fact that [START_REF] Gimbert | Perfect information stochastic priority games[END_REF] uses the iterated limit of discount factors and not the more interesting simultaneous limit.

In the second paper [START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF] we considered priority mean-payoff games in full generality, with no artificial restrictions, and we examined directly the limit with the discount factors tending to 1 with different rates rather than the iterated limit. However [START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF] deals only with one-player games and it examines only games values, the paper does not provide any relation between optimal strategies in multi-discounted games and optimal strategies in the priority mean-payoff games in the limit.

In the present paper we remove all restrictions imposed in [START_REF] Gimbert | Perfect information stochastic priority games[END_REF][START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF]. We consider the full class perfect information stochastic priority mean-payoff games and we show that such games are a limit of discounted games with discount factors tending to 1 with the rates depending on the priority. Not only at the limit the value of the discounted game equals to the value of the priority mean-payoff game but also optimal deterministic memoryless strategies in discounted games turn out to be optimal in the the corresponding priority mean-payoff game.

The interest in such a result is threefold. First we think that establishing a very strong link between two apparently different classes of games has its own intrinsic interest.

Discounted games were thoroughly studied in the past and our result shows that algorithms for such games can, in principle, be used to solve parity games (admittedly all depends on how much the discount factor should be close to 1 in order that two types of games become close enough, and this remains open).

Another point concerns the stability of solutions (optimal strategies and games values) under small perturbations. When we examine stochastic games then the natural question is where the transition probabilities come from? If they come from an observation then the values of transition probabilities are not exact. On the other hand algorithms for stochastic games use only rational transition probabilities thus even if we know the exact probabilities we replace them by close rational values. What is the impact of such approximations on solutions, are optimal strategies stable under small perturbations? Usually we tacitly assume that this is the case but it would be better to be sure. Since Blackwell-optimal strategies studied in Section 4 are stable under small perturbations of discount factors (because they do not depend on the discount factor) this adds some credibility to the claim that Blackwell optimal strategies are stable for parity games.

And the last point. Blackwell invented Blackwell optimality because he was not satisfied with the notion of optimal strategies for mean-payoff Markov decision processes. However the same can be said about parity games, we defer examples to the final section. The paper is organized as follows. In Section 2 we introduce stochastic games in general, we define the notions of value and optimal strategies. Section 3 we examine discounted games. The main result in this section shows that if discount factors are close to 1 then optimal strategies stabilize (Blackwell optimality). In Section 5 we introduce the class of priority mean-payoff games -this is the principal class of games examined in this paper. Parity games and mean-payoff games are just very special subclasses of this class. In Section 6 we prove the main result of the paper stating that deterministic memoryless strategies optimal for discounted games for discount factors sufficiently close to 1 are optimal in derived priority mean-payoff games.

Stochastic Games with Perfect Information

Notation. In this paper N stands for the set of positive integers, N 0 = N ∪ {0}, and R + is the set of positive real numbers.

For each finite set X , D (X ) is the set of probability distributions over X , i.e. it is the set of mappings p : X → [0, 1] such that ∑ x∈X p(x) = 1. The support of p ∈ D (X ) is the set {x ∈ X : p(x) > 0}.

Games and Arenas

Two players Max and Min are playing an infinite game on an arena. An arena is a tuple

A = (S, S Max , S Min , A, (A(s)) s∈S , δ ),
where a finite set of states S is partitioned in two sets, the set S Max of states controlled by player Max and the set S Min of states controlled by player Min. For each state s ∈ S there is a non-empty finite set A(s) of actions available in s, A = s∈S A(s). Players Max and Min play on A an infinite game. If at stage i ∈ N 0 the game is in a state s i ∈ S then the player controlling s chooses an action from A(s) and a new state s i+1 is chosen with probability specified by the transition mapping δ . Transition mapping δ maps each pair (s, a), where s ∈ S and a ∈ A(s), to an element of D (S). Intuitively, if in a state s and an action a is executed then δ (s, a)(t) gives the probability that at the next stage the game is in state t. To simplify the notation we shall write δ (s, a,t) rather than δ (s, a)(t).

Throughout the paper we assume that all arenas are finite, i.e. the sets of states and actions are finite. An arena is said to be a one-player arena controlled by player Max if, for every state s controlled by Min, the set A(s) is a singleton (in particular if all states are controlled by Max then A is a one-player arena controlled by Max). One-player arenas controlled by player Min are defined similarly.

A finite (resp. infinite) play in the arena A is a non-empty finite (resp. infinite) sequence of states and actions in (SA) * S (resp. in (SA) ω ). In the sequel "play" without any attribute will be used as a synonym of "infinite play".

Payoffs

After an infinite play player Max receives a payoff from player Min. The objectives of the players are opposite, the goal of Max is to maximize the payoff while player Min wants to minimize the payoff.

The payoff can be computed in various ways. For example in a mean-payoff game each state is labeled with a real number called the reward and after an infinite play the payoff of player Max is the limit of mean values of the sequence of rewards. In a parity game, each state is labeled with an integer called a priority and player Max receives payoff 0 or 1 depending on the parity of the highest priority seen infinitely often. In both examples, the way the payoffs are computed is independent from the transitions rules of the game (the arena), it depends uniquely on the play.

Thus formally a payoff function is a mapping

u : (SA) ω → R
from infinite plays to real numbers.

A game is a couple Γ = (A , u) made of an arena and a payoff function. Usually we consider not a particular game but rather a class of games. In this case arenas are endowed with some additional structure, usually some labeling of states or actions (for example rewards as in mean-payoff games or priorities as in parity games) and this labeling is used to define the payoff for games in the given class.

Strategies

Playing a game the players use strategies. A strategy for player Max is a mapping σ : (SA) * S Max → D (A) such that for every finite play p = s 0 a 0 s 1 a 1 . . . s n with s n ∈ S Max , the support of σ (p) is a subset of the actions available in s n , i.e. for all a ∈ A, if σ (p)(a) > 0 then a ∈ A(s n ).

Strategies for player Min are defined similarly and denoted τ.

Certain types of strategies are of particular interest. A strategy is deterministic if it chooses actions in a deterministic way, and it is memoryless if it does not have any memory, i.e. choices depend only on the current state of the game, and not on the past history. Formally: Definition 1. A strategy σ of player i ∈ {Min, Max} is said to be:

• deterministic if, ∀p ∈ (SA) * S i , if σ (p)(a) > 0 then σ (p)(a) = 1,
• memoryless if, ∀t ∈ S i and p ∈ (SA) * , σ (pt) = σ (t).

For any finite play p ∈ (SA) * S and an action a ∈ A we define the cones O(p) and O(pa) as the sets consisting of all infinite plays with prefix p and pa respectively.

In the sequel we assume that the set of infinite plays (SA) ω is equipped with the σ -field B((SA) ω ) generated by the collection of all cones O(p) and O(pa). Elements of this σ -field are called events. Moreover, when there is no risk of confusion, the events O(p) and O(pa) will be denoted simply p and pa.

Suppose that players Max and Min are playing accordingly to strategies σ and τ. Then after a finite play s 0 a 1 . . . s n the probability of choosing an actions a n+1 is either σ (s 0 a 1 . . . s n )(a n+1 ) or τ(s 0 a 1 . . . s n )(a n+1 ) depending on whether s n belongs to S Max or to S Min . Fixing the initial state s ∈ S these probabilities and the transition probability δ yield the following probabilities

P σ ,τ s (s 0 ) = 1 if s 0 = s 0 if s 0 = s (1)
is the probability of the cone O(s 0 ),

P σ ,τ s (s 0 a 1 . . . s n a n+1 | s 0 a 1 . . . s n ) = σ (s 0 a 1 . . . s n )(a n+1 ) if s n ∈ S Max τ(s 0 a 1 . . . s n )(a n+1 ) if s n ∈ S Min (2)
is the conditional probability of O(s 0 a 1 . . . s n a n+1 ) given O(s 0 a 1 . . . s n ) and

P σ ,τ s (s 0 a 1 . . . s n a n+1 s n+1 | s 0 a 1 . . . s n a n+1 ) = δ (s n , a n+1 , s n+1 ) (3)
is the conditional probability of the cone O(s 0 a 1 . . . s n a n+1 s n+1 ) given the cone O(s 0 a 1 . . . s n a n+1 ). Ionescu Tulcea's theorem [START_REF] Shiryayev | Probability[END_REF] implies that there exists a unique probability measure P σ ,τ s on the measurable space ((SA) ω , B(SA) ω ) satisfying ( 1), ( 2) and (3).

Optimal strategies

Let A = (S, S Max , S Min , A, (A(s)) s∈S , δ ) be an arena. In the sequel we assume that all payoff mappings u : (SA) ω → R are bounded and measurable (for measurability we assume that (SA) ω is equipped with the σ -field described in the preceding section and R is equipped with the σ -field B(R) of Borel sets).

Given an initial state s and strategies σ and τ of Max and Min the expected value of the payoff

u under P σ ,τ s is denoted E σ ,τ s [u].
A strategy σ ♯ for player Max is said to be optimal in a game (A , u) if for every state s,

inf τ E σ ♯ ,τ s [u] = sup σ inf τ E σ ,τ s [u] . Dually a strategy τ ♯ of player Min is optimal if sup σ E σ ,τ ♯ s [u] = inf τ sup σ E σ ,τ s [u], for each state s. In general, val s (u) := sup σ inf τ E σ ,τ s [u] ≤ inf τ sup σ E σ ,τ s [u] := val s (u)
but when these two quantities are equal then the state s is said to have the value val s (u) = val s (u) = val s (u), denoted also val s (u, A ) whenever mentioning explicitly the arena is needed. Under the hypothesis that u is measurable and bounded, Martin's theorem [START_REF] Martin | The determinacy of Blackwell games[END_REF] guarantees that every state has a value. Notice however that Martin's theorem does not guarantee the existence of optimal strategies.

Discounted Games

Arenas for discounted games are equipped with two mappings defined on the set S of states. The discount mapping λ : S -→ [0, 1)

associates with each state s a discount factor λ (s) ∈ [0, 1) and the reward mapping

r : S -→ R (4)
maps each state s to a real valued reward r(s).

The payoff

u λ : (SA) ω -→ R
for discounted games is calculated in the following way. For each play p = s 0 a 0 s 1 a 1 s 2 a 2 . . .

∈ (SA) ω u λ (p) = (1 -λ (s 0 ))r(s 0 ) + λ (s 0 )(1 -λ (s 1 ))r(s 1 ) + λ (s 0 )λ (s 1 )(1 -λ (s 2 ))r(s 2 ) + . . . = ∞ ∑ i=0 λ (s 0 ) . . . λ (s i-1 )(1 -λ (s i ))r(s i ) . (5)
Usually when discounted games are considered it is assumed that there is only one discount factor, i.e. that there exists λ ∈ [0, 1) such that λ (s) = λ for all s ∈ S. But for us it is essential that the discount factor depends on the state.

Shapley [START_REF] Shapley | Stochastic games[END_REF] proved 1 that Theorem 2 (Shapley). Discounted games (A , u λ ) over finite arenas admit optimal deterministic memoryless strategies for both players.

Interpretations of discounted games

The rather obscure formula 5 can be interpreted in several ways. The usual economic interpretation is the following. The reward r(s) represents the payoff that player Max receives if the state s is visited. But a given sum of money is worth more now than in the future, visiting s i at stage i is worth λ (s 1 ) . . . λ (s i-1 )r(s i ) rather than r(s i ) (visiting s i is worth r(s i ) only the first day). With this interpretation ∑ ∞ i=0 λ (s 0 ) . . . λ (s i-1 )r(s i ) represents the accumulated total the payoff that player Max receives during an infinite play. However, with this interpretation it is difficult to assign a meaning to the factors (1 -λ (s i )) and such factors are essential when we consider the limit of u λ with discount factors tending to 1.

In his seminal paper [START_REF] Shapley | Stochastic games[END_REF] Shapley gives another interpretation of (5) in terms stopping games. Suppose that at a stage i a state s i is visited. Then with probability 1 -λ (s i ) the nature can stop the game. Since we have assumed that 0 ≤ λ (s) < 1 for all s ∈ S, the stopping probabilities are strictly positive which implies that the game will eventually stop with probability 1 after a finite number of steps.

If the game stops in s i then player Max receives from player Min the payment r(s i ) and this ends the game. Thus here player Max receives the payoff only once, when the game stops and the payoff is determined by the last state.

If the game does not stop in s i then there is no payment at this stage and the player controlling the state s i chooses an action to execute.

Note that λ (s 0 ) . . . λ (s i-1 )(1 -λ (s i )) gives the probability that the game has not stopped in any of the states s 0 , . . . , s i-1 but it does stop in the state s i . Since this event results in the payment r(s i ), [START_REF] Gimbert | Applying Blackwell optimality: priority mean-payoff games as limits of multi-discounted games[END_REF] represents in this interpretation the payoff expectation for an infinite play s 0 a 0 s 1 a 1 s 2 a 2 . . . during the stopping game.

Another related interpretation making a direct link between discounted games and mean-payoff games is the following. We transform the discounted arena A into a new arena A ⋆ by attaching to each state s ∈ S a new state s ⋆ . We set r(s ⋆ ) = r(s), i.e. each new adjoined state has the same reward as the corresponding original state.

In the new arena A ⋆ we incorporate the discount factors directly into the transition probabilities. Recall that, for each state s ∈ S of the original arena A , δ (s, a, s ′ ) was the probability of going to a state s ′ if an action a is executed in s. In the new arena A ⋆ this probability is set to δ ⋆ (s, a, s ′ ) = λ (s)δ (s, a, s ′ ).

On the other hand we set also δ ⋆ (s, a, s ⋆ ) = (1 -λ (s)), i.e. in A ⋆ with probability 1 -λ (s) the execution of a in s leads to s ⋆ (note that for fixed a the probabilities sum up to 1). Each new state s ⋆ is absorbing, there is only one action available in each s ⋆ , we note it ⋆, and this action leads with probability 1 back to s ⋆ . This situation is illustrated by the following picture.

We consider the mean-payoff game played on A ⋆ , i.e. the game with the payoff u r (s

0 a 0 s 1 a 1 . . .) = lim sup k 1 k+1 ∑ k i=0 r(s i ).
Such a game played on A ⋆ ends with probability 1 in one of the starred states s ⋆ and then the mean-payoff is simply r(s ⋆ ) = r(s). Intuitively, stopping in s with the payoff r(s) in the stopping game is the same as going to s ⋆ and looping there infinitely with the same mean-payoff r(s ⋆ ). Thus a discounted game can be seen as a mean-payoff game played on an arena where with probability 1 we end in some absorbing state. If discount factors tend to 1 then this means that, intuitively, we cut off the absorbing starred states of A ⋆ .

Blackwell optimality

We will consider what happens if the discount factors tend to 1. The novelty in comparison with the traditional approach is that we consider the situation where discount factors of different states tend to 1 with different rates.

A rational discount parametrization is a family of mappings λ t = (λ t (s)) s∈S , such that for each state s,

• t → λ t (s) is a rational2 mapping of t,

• there exists 0 < ε < 1 such that λ t (s) ∈ [0, 1) for all t ∈ [1 -ε, 1) (note that since the set of states is finite we can choose the same ε for all states),

• lim t↑1 λ t (s) = 1.

A typical example of a rational parametrization is the canonical rational discount parametrization defined in the following way. For each state s we fix a natural number π(s) ∈ N called the priority of s and a positive real number w(s) ∈ (0, ∞) called the weight of s. Then the canonical parametrization is defined as

λ t (s) = 1 -w(s)(1 -t) π(s) , for s ∈ S,t ∈ R. (6)
We will consider discounted games where discount factors are given by a rational discount parametrization.

Theorem 3 (Blackwell optimality). Let us fix an arena

A of a discounted game and let λ t be a rational discount parametrization for A . Let val s (u λ t ) be the value of a state s ∈ S for λ t in the game (A , u λ t ).

Then there exists 0 < ε < 1 such that, for each state s,

(1) for t ∈ (1 -ε, 1), t → val s (u λ t ) is a rational function of t and

(2) if σ ♯ and τ ♯ are optimal deterministic memoryless strategies for some t ∈ (1 -ε, 1) then σ ♯ and τ ♯ are optimal for all t ∈ (1 -ε, 1).

In the sequel we call strategies σ ♯ and τ ♯ Blackwell optimal for a rational discount parametrization λ t if σ ♯ and τ ♯ are deterministic memoryless strategies satisfying part (2) of Theorem 3.

Let us note that Theorem 3 exhibits a curious property of discounted games discovered by Blackwell [START_REF] Blackwell | Discrete dynamic programming[END_REF] 3 . By Theorem 2 we know that for each fixed t the discounted game with payoff u λ t has optimal memoryless deterministic strategies, but obviously such strategies depend on t. Theorem 3 asserts that for t ∈ (1 -ε, 1) the situation stabilizes and optimal deterministic memoryless strategies do not depend on t. Since Blackwell optimality is usually proved only for Markov decision processes with a unique discount factor for all states, see [START_REF] Hordijk | Blackwell Optimality[END_REF] for example, we decided to include the complete proof of Theorem 3. Note however that our proof follows closely the one used for Markov decision processes.

The proof of Theorem 3 is based on the following lemma that will be useful also in the next section.

Lemma 4. Let t → λ t be a rational discount parametrization and let σ , τ be deterministic memoryless strategies. Then, for each state s, and for t sufficiently close to 1, E σ ,τ s u λ t is a rational function of t.

Proof. The proof is standard but we give it for the sake of completeness. The set R S×S of functions from S × S into real numbers can be seen as the set of square real valued matrices with rows and columns indexed by S. In particular R S×S is a vector space with natural matrix addition and scalar multiplication. However, matrix multiplication defines also a product on R S×S , for M, N ∈ R S×S , MN is an element

U of R S×S with entries U [s ′ , s ′′ ] = ∑ s∈S M[s ′ , s]N[s, s ′′ ]. We endow R S×S with a norm, for M ∈ R S×S , ||M|| = max s ′ ∈S ∑ s ′′ ∈S |M[s ′ , s ′′ ]|. It can be easily shown that ||MN|| ≤ ||M|| • ||N|| for M, N ∈ R S×S and
R S×S is a complete metric space for the metric induced by the norm || • ||, see Section 3.2.1 of [START_REF] Stroock | An Introduction to Markov Processes[END_REF] for a proof.

On the other hand, we consider also the vector space R S of functions from S into R, they can be seen as column vectors indexed by states. Of course if M ∈ R S×S and v ∈ R S then Mv ∈ R S , where

(Mv)[s] = ∑ s ′ ∈S M[s, s ′ ]v[s ′ ] for s ∈ S.
We equip R S with a norm, for v ∈ R S , ||v|| ∞ = max s∈S |v[s]|. The norms on R S×S and R S are compatible in the sense that we have

||Mv|| ∞ ≤ ||M|| • ||v|| ∞ .
Let σ , τ be deterministic memoryless strategies for players Max and Min and let λ t be a rational discount parametrization. We define

δ (s ′ , s ′′ ) = δ (s ′ , σ (s ′ ), s ′′ ) if s ′ ∈ S Max , δ (s ′ , τ(s ′ ), s ′′ ) if s ′ ∈ S Max , for s ′ , s ′′ ∈ S.
Thus δ defines transition probabilities of the Markov chain obtained when we fix the strategies σ and τ.

In the sequel M will denote the element of R S×S defined in the following way

M[s ′ , s ′′ ] = λ t (s ′ )δ (s ′ , s ′′ ), for s ′ , s ′′ , ∈ S (7)
Let I ∈ R S×S be the identity matrix, i.e. I[s ′ , s ′′ ] is 1 if s ′ = s ′′ and 0 otherwise. We shall show that for t close to 1 the matrix (I -M) is invertible and

(I -M) -1 = ∞ ∑ i=0 M i . ( 8
)
First we show that the series on the right-hand side of (8) converges.

Let λ M = max s∈S λ t (s). Then for t sufficiently close to 1 we have ||M|| ≤ λ M < 1 and, for k < l,

|| l ∑ i=k M i || ≤ l ∑ i=k ||M|| i ≤ l ∑ i=k (λ M ) i = λ k M -λ l+1 M 1 -λ M ---→ k,l→∞
0 since, by the definition of a rational discount parametrization, 0 ≤ λ M < 1 for t sufficiently close to 1. Thus the series ∑ ∞ i=0 M i satisfies the Cauchy condition and the convergence follows from the completeness of the norm || • ||. Now it suffices to note that

(I -M) -1 • k ∑ i=0 M i -I = M k+1 and ||M k+1 || ≤ ||M|| k+1 ≤ λ k+1
M ---→ k→∞ 0 which yields [START_REF] Gimbert | Pure and Stationary Optimal Strategies in Perfect-Information Stochastic Games[END_REF].

Let (S i ) ∞ i=0 be the stochastic process giving the state at stage i. Then

E σ ,τ s u λ t = E σ ,τ s ∞ ∑ i=0 λ t (S 0 ) • • • λ t (S i-1 )(1 -λ t (S i ))r(S i ) = lim k→∞ E σ ,τ s k ∑ i=0 λ t (S 0 ) • • • λ t (S i-1 )(1 -λ t (S i ))r(S i ) (9)
where the second equality follows from the Lebesgue dominated convergence theorem.

Let v be an element of R S defined as

v[s] = (1 -λ t (s))r(s), for s ∈ S.
An elementary induction on i shows that, for s, s ′ ∈ S,

E σ ,τ s λ t (S 0 ) • • • λ t (S i-1 )|S 0 = s, S i = s ′ = M i [s, s ′ ],
i.e. the entry [s, s ′ ] of the i-th power of M is the expectation of λ t (S 0 ) • • • λ t (S i-1 ) under the condition that S 0 = s and S i = s ′ . This yields

(M i v)[s] = ∑ s ′ ∈S M i [s, s ′ ] • v[s ′ ] = ∑ s ′ ∈S E σ ,τ s λ t (S 0 ) • • • λ t (S i-1 )|S 0 = s, S i = s ′ • (1 -λ t (s ′ ))r(s ′ ) = E σ ,τ s [λ t (S 0 ) • • • λ t (S i-1 )(1 -λ t (S i ))r(S i )|S 0 = s] . ( 10
)
Taking the sum from i = 0 to k on both sides of (10) and next the limit with k tending to infinity, using ( 9) and ( 8), we obtain

E σ ,τ s u λ t = ((I -M) -1 v)[s].
But the elements of the matrix I -M are rational functions of t, thus Cramer's rule for matrix inversion show that (I -M) -1 has also rational elements, and since the elements of v are also rational functions we can see that E σ ,τ s u λ t is a rational function of t.

Proof of Theorem 3. According to Lemma 4, and since discounted games admit optimal deterministic memoryless strategies, (1) is a consequence of (2).

We prove (2) as follows.

Let X be the set of all tuples (q, σ , τ, σ ′ , τ ′ ), where q is a state, σ , σ ′ are deterministic memoryless strategies for player Max and τ, τ ′ are deterministic memoryless strategies for player Min. Note that for finite arenas X is finite. Let λ t be a rational discount parametrization and let 0 < ε < 1 be such that λ t (s) ∈ (0, 1) for all states s and all t ∈ (1 -ε, 1).

For each (q, σ , τ, σ ′ , τ ′ ) ∈ X we consider the function Φ q,σ ,τ,σ ′ ,τ ′ : (1 -ε, 1) → R defined by:

t → Φ q,σ ,τ,σ ′ ,τ ′ (t) = E σ ,τ q u λ (t) -E σ ′ ,τ ′ q u λ (t) .
According to Lemma 4, Φ q,σ ,τ,σ ′ ,τ ′ (t) is a rational function of t for t sufficiently close to 1. Since a rational function can change the sign (cross the x-axis) only finitely many times there exists

ε 1 = ε 1 (q, σ , τ, σ ′ , τ ′ ) > 0 such that the sign of Φ q,σ ,τ,σ ′ ,τ ′ (t) does not change in the interval (1 -ε 1 , 1). Let ε 2 = min{ε} ∪ {ε 1 (q, σ , τ, σ ′ , τ ′ ) : (q, σ , τ, σ ′ , τ ′ ) ∈ X }.
Since X is finite the minimum on the right is taken over a finite set of positive numbers and we conclude that ε 2 > 0 Let us take any t ∈ (1 -ε 2 , 1). Let σ ♯ , τ ♯ be optimal deterministic memoryless strategies in the discounted game (A , u λ t ) (Theorem 2). Then, in particular, we have

E σ ,τ ♯ q u λ t ≤ E σ ♯ ,τ ♯ q u λ t ≤ E σ ♯ ,τ q u λ t (11)
for all deterministic memoryless strategies σ , τ. We can rewrite [START_REF] Martin | The determinacy of Blackwell games[END_REF] as Φ q,σ ♯ ,τ ♯ ,σ ,τ ♯ (t) ≥ 0 and Φ q,σ ♯ ,τ,σ ♯ ,τ ♯ (t) ≥ 0. However if these inequalities hold for some t ∈ (1 -ε 2 , 1) then we have seen that they hold for all t ∈ (1 -ε 2 , 1). Therefore [START_REF] Martin | The determinacy of Blackwell games[END_REF] holds for all t ∈ (1 -ε 2 , 1). Finally Theorem 2 implies that if [START_REF] Martin | The determinacy of Blackwell games[END_REF] holds for all deterministic memoryless strategies σ and τ (with fixed deterministic memoryless σ ♯ and τ ♯ ) then it holds for all strategies σ , τ4 .

Priority mean-payoff games

In mean-payoff games the players try to optimize (maximize/minimize) the mean value of the payoff received at each stage. In such games the reward mapping

r : S -→ R (12)
gives, for each state s, the payoff received by player Max when s is visited. The payoff of an infinite play is defined as the limit of the means of daily payments:

u r (s 0 s 1 s 2 . . .) = lim sup k 1 k + 1 k ∑ i=0 r(s i ) , (13)
where we take lim sup rather than the simple limit since the latter may not exist. We slightly generalize mean-payoff games by equipping arenas with a new mapping

w : S -→ R + (14)
associating with each state s a strictly positive real number w(s), the weight of s. We can interpret w(s) as the amount of time spent in state s upon each visit to s. In this setting r(s) should be seen as the payoff by a time unit when s is visited, thus the weighted mean payoff received by player Max is

u r,w (s 0 s 1 s 2 . . .) = lim sup k ∑ k i=0 w(s i )r(s i ) ∑ k i=0 w(s i ) . ( 15
)
Note that in the special case when the weights are all equal to 1, the weighted mean value (15) reduces to [START_REF] Shapley | Stochastic games[END_REF].

As a final ingredient we add to the arena a priority mapping

π : S -→ N (16)
assigning to each state s a positive integer priority π(s).

We define the priority of a play p = s 0 a 0 s 1 a 1 s 2 a 2 . . . as the smallest priority appearing infinitely often in the sequence π(s 0 )π(s 1 )π(s 2 ) . . . of priorities visited in p:

π(p) = lim inf i π(s i ) . ( 17
)
For any priority α, let 1 α : S -→ {0, 1} be the indicator function of the set {s ∈ S | π(s) = α}, i.e.

1 α (s) = 1 if π(s) = α 0 otherwise. ( 18
)
Then the priority mean-payoff of a play p = s 0 a 0 s 1 a 1 s 2 a 2 . . . is defined as

u r,w,π (p) = lim sup k ∑ k i=0 1 π(p) (s i ) • w(s i ) • r(s i ) ∑ k i=0 1 π(p) (s i ) • w(s i ) . ( 19
)
In other words, to calculate priority mean payoff u r,w,π (p) we take weighted mean payoff but with the weights of all states having priorities different from π(p) shrunk to 0. (Let us note that the denominator ∑ k i=0 1 π(p) (s i ) • w(s i ) is different from 0 for k large enough, in fact it tends to infinity since 1 π(p) (s i ) = 1 for infinitely many i. For small k the numerator and the denominator can be equal to 0 and then, to avoid all misunderstanding, it is convenient to assume that the indefinite value 0/0 is equal to -∞.)

In the sequel the couple (w, π) consisting of a weight mapping and a priority mapping will be called a weighted priority system.

Let us note that priority mean-payoff games are a vast generalization of parity games. In fact parity games correspond to a very particular case of priority mean-payoff games, we recover the usual parity games when we set for each state s, w(s) = 1 and r(s) = 1 if π(s) is even and r(s) = 0 if π(s) is odd.

Theorem 5. Priority mean-payoff games over finite arenas admit optimal deterministic memoryless strategies for both players.

Proof. The proof of Theorem 5 relies on the transfer theorem proved in [START_REF] Gimbert | Pure and Stationary Optimal Strategies in Perfect-Information Stochastic Games[END_REF]. This theorem states the following: if a payoff function u admits optimal deterministic memoryless strategies in all one-player perfect information stochastic games over finite arenas equipped with payoff u or -u, then all two-player perfect information stochastic games over finite arenas with payoff u have also optimal deterministic memoryless strategies for both players.

In [START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF], we proved that one-player games equipped with the payoff function u r,w,π have optimal deterministic memoryless strategy. It remains to prove the same for one-player games equipped with the payoff function -u r,w,π :

-u r,w,π (s 0 s 1 s 2 • • • ) = lim inf k -∑ k i=0 1 π(p) (s) • w(s i ) • r(s i ) ∑ k i=0 1 π(p) (s i ) • w(s i ) . ( 20
)
Let us denote -r the reward mapping defined by (-r)(s) = -r(s). Then,

u -r,w,π (s 0 s 1 s 2 • • • ) = lim sup k -∑ k i=0 1 π(p) (s) • w(s i ) • r(s i ) ∑ k i=0 1 π(p) (s i ) • w(s i ) . ( 21
)
The expected values of -u r,w,π and u -r,w,π coincide on Markov chains, because in a Markov chain, the limsup in ( 21) is almost-surely a limit, see the proof of Theorem 7, page 8 of [START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF]. Since for every play, -u r,w,π (p) ≤ u -r,w,π (p), this implies that in a one-player arena, every deterministic memoryless strategy optimal for the payoff function u -r,w,π is optimal for the payoff function -u r,w,π as well, and these two games have the same values and the same deterministic memoryless optimal strategies. This completes the proof.

6 From rationally parametrized discounted games to priority mean-payoff games

Priority mean-payoff derived from rational discount parametrization

The aim of this short subsection is to show how a rational discount parametrization induces in a canonical way a weighted priority system. Let λ t be a rational discount parametrization. The fact that lim t↑1 (1 -λ t (s)) = 0 implies that for each state s, the function t → 1 -λ t (s) factorizes as g s (t)(1 -t) π(s) where π(s) ∈ N is a positive integer constant and t → g s (t) is a rational function such that g s (1) = 0. Moreover since 1 -λ t (s) is positive for t ∈ (1 -ε, 1), g s (t) is also positive in the same interval and by continuity of g s (t), g s (1) > 0. Now, for each state s, take π(s) defined above as the priority of s and w(s) := g s (1) as the weight of s. We say that (w, π) defined in this way is the weighted priority system derived from the rational discount parametrization λ t .

Limit of a discounted game

The following theorem establishes a remarkable link between discounted games and weighted priority mean-payoff games. Roughly speaking it shows that the latter are the limit of discounted games, the limit not only in the sense of game values (part (a)) but also the optimality of strategies is preserved in the limit. Theorem 6. Let A be a fixed arena and let t → λ t be a rational discount parametrization for A . Let (w, π) be the weighted priority system derived from λ t . Finally let σ ♯ and τ ♯ be deterministic memoryless Blackwell optimal strategies for the discounted game (A , u λ t ). Then (a) for each state s, lim t↑1 val s (u λ t ) = val s (u r,w,π ), where val s (u λ t ) is the value of the game (A , u λ t ) and val s (u r,w,π ) is the value of the game (A , u r,w,π ), and (b) if σ ♯ and τ ♯ are Blackwell optimal memoryless deterministic strategies for the discounted game (A , u λ t ) then σ ♯ and τ ♯ are optimal for the priority mean-payoff game (A , u r,w,π )

Let us note that part (a) of Theorem 6 was proved in [START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF] but only for one-player games 5 (Markov decision processes).

However, in [START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF] we were unable to establish any result linking optimal strategies for discounted games with optimal strategies of weighted priority games. Thus the main achievement of the present paper is part (b) of Theorem 6.

The following result was proved in [START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF] (Theorem 7 in [START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF]):

Lemma 7. Let λ t be a rational discount parametrization and let (w, π) be the derived weighted priority system. Then for each state s and for all deterministic memoryless strategies σ , τ:

lim t↑1 E σ ,τ s u λ (t) = E σ ,τ s [u r,w,π ] .
Proof of Theorem 6. We begin with part (b). Let σ ♯ , τ ♯ be Blackwell optimal deterministic memoryless strategies for λ t . Let σ and τ be any deterministic memoryless strategies of players Max and Min. Then

E σ ,τ ♯ s u λ t ≤ E σ ♯ ,τ ♯ s u λ t ≤ E σ ♯ ,τ s u λ t .
Taking the limit with t ↑ 1 we get by Lemma 7

E σ ,τ ♯ s [u r,w,π ] ≤ E σ ♯ ,τ ♯ s [u r,w,π ] ≤ E σ ♯ ,τ s [u r,w,π ] ,
which shows that σ ♯ and τ ♯ are optimal in the class of deterministic memoryless strategies. But Theo- rem 5 implies that for priority mean-payoff games strategies optimal in the class of deterministic memoryless strategies are optimal also when all strategies are allowed. This terminates the proof of (b). Obviously (a) follows from (b) and from Lemma 7. Theorem 6 stated that Blackwell optimal strategies are also optimal for priority mean-payoff games. The converse is not true, the notion of Blackwell optimal strategies is strictly more restrictive.

Optimal but not Blackwell optimal strategies

We illustrate this with the game presented in Figure 1. Here we have two states s Max , s Min controlled respectively by players Max and Min. Both states have the same weight 1 which is omitted. The left state has priority π = 2 and reward r = 0, the right state has priority π = 1 and reward r = 1, thus essentially this is the usual parity game with two priorities. Both players have two deterministic memoryless strategies. The optimal strategy for player Min is to take action "left". With this strategy state s Max with priority 1 is visited infinitely often and since this is the minimal priority in this games the resulting payoff will 0 whatever the strategy of player Max. Player Max can play "top" or "right", in both cases if player Min uses the strategy described above the payoff is 0 thus both strategies are optimal for Max. Now let us consider the associated discounted game with the canonical parametrization. Thus the discount factor of s Max is λ t (s Max ) = 1 -(1 -t) π(s Max ) = t while the discount factor for s Min is λ t (s Min ) = 1 -(1t) π(s Min ) = 1 -(1t) 2 . For player Min the optimal strategy is still to always play "left". For player Max the strategies "right" and "top" are now different. For example if we start from s Max then playing "top" will result in payoff 0 since we will visit only the state s Max with reward 0. On the other hand playing "right" we will visit infinitely often the state s Min with a positive reward, thus for discounted games playing "right" is strictly better for Max than playing "top" and the strategy where Max plays "right" is the only Blackwell optimal strategy.

The main motivation behind Blackwell optimal strategies comes from the following observation (due to Blackwell). Consider a mean-payoff game controlled completely by player Max and suppose that there are only two possible infinite plays. The first play begins with a long but finite sequence of rewards 0 followed by an infinite sequence of rewards 1. The mean payoff for such history is 1, the initial sequence of 0 does not count on the limit. Consider now the second play which is an infinite sequence of rewards 1, without any 0. Here also the mean payoff is also 1. Thus player Max is indifferent between two histories. But from the point of view of Maximizer clearly the second history is better than the first one, one prefers to have the reward 1 each day rather than to begin with the reward 0. This difference is captured by Blackwell optimality.

Figure 1 :

 1 Figure 1: A parity game. Player Max has two deterministic memoryless optimal strategies but only one of them is Blackwell optimal.

In fact, Shapley considered a much larger class of stochastic games. For these games he proved that both players have memoryless optimal strategies. For perfect information games his proof yields optimal strategies that are also deterministic.

Rational in the sense that λ t (s) is a quotient of two polynomials of t.

In fact Blackwell[START_REF] Blackwell | Discrete dynamic programming[END_REF] considered only one-player games with the same discount factor for all states.

In other words, for discounted games being optimal in the class of memoryless deterministic strategies implies being optimal in the class of all strategies.

In fact,[START_REF] Gimbert | Limits of multi-discounted Markov decision processes[END_REF] shows that the convergence of game values holds not only for rational parametrizations but for any "reasonable" parametrization of discount factors.


Nassim Kaldé

Olivier Simonin

Discrete Voronoi-like Partition of a Mesh on a Cellular Automaton in Asynchronous Calculus

Keywords: asynchronous computing, cellular automata, ambient intelligence, distributed systems, spatial computing, voronoi diagram calcul asynchrone, automate cellulaire, intelligence ambiante, systèmes distribués, calcul spatial, diagramme de voronoi

This report presents an approach for asynchronously computing a Voronoi skeleton in a decentralized fashion on a regular grid of cells with a von Neumann neighborhood. To our knowledge, no previous work asynchronously solves this problem in a decentralized fashion. The methods given in this paper describe algorithms for extracting an area voronoi diagram skeleton and a pseudo line-like voronoi diagram skeleton. Algorithms are implemented in simulation and executed on maps in which we consider different kind of sources defined as polygonal shapes. Such work can be useful for robotic navigation.

Introduction

We are interested in computing Voronoi like partition of the environment using an asynchronous mesh of processing and sensing units. Ambient intelligence [START_REF] Boekhorst | Ambient intelligence, the next paradigm for consumer electronics: how will it affect silicon?[END_REF] relies on numerous processing units located and communicating in a same environment. Designing algorithms for self-organizing systems that can handle communication between the units, are scalable and simply work in such environments is part of the domain of spatial computing [START_REF] Maignan | Convex Hulls on Cellular Spaces: Spatial Computing on Cellular Automata[END_REF] where the data is distributed in the network and the computing can be done in various synchronization modes.

The environment on which we focus is a typical lattice of a cellular automaton (CA), each cell has 4 direct neighbors. A common formalization of this lattice is given in [START_REF] Adamatzky | Voronoi-like partition of lattice in cellular automata[END_REF]. A 2D CA is a tuple F =< A, Q, u 1 , f >, with u 1 being the von-Neumann neighborhood, i.e. a mapping that associates each cell c ij in A, to itself and its North, East, South and West neighbors.

2D Cellular Automaton : F

(1)

F =< A, Q, u 1 , f > A : a matrix of cells (dimension m × n)
Q : a set of states of a cell u 1 : a cellular neighborhood A → A 5

f : a local rule of evolution Q 5 → Q

The automaton evolves in discrete time by applying a global rule of evolution F on its matrix of cells A, as shown in [START_REF] Barraquand | Numerical potential field techniques for robot path planning[END_REF] and [START_REF] Blum | A Transformation for Extracting New Descriptors of Shape[END_REF].

F t =< A, Q, u 1 , f > t =< A t , Q, u 1 , f > (2)
F t+1 =< F (A t ), Q, u 1 , f >=< A t+1 , Q, u 1 , f > (3)
In this paper, we study CA which are not synchronized. We consider that the automaton evolves at each step by randomly selecting an individual cell on the grid (4) and executes its local evolution rule, cf. [START_REF] Maignan | Convex Hulls on Cellular Spaces: Spatial Computing on Cellular Automata[END_REF]. We call this evolution mode, the simple asyncronous mode. Only one cell c updates its state at t + 1 by applying the local rule of evolution f on its neighborhood at time t.

A t+1 = {c ∈ A|∃!c ∈ A : c t+1 = c t } (4)
c t+1 = f (u t 1 (c)) (5)
Here, we address the problem of asynchronously computing Voronoi-like diagrams using a CA. Several papers already cover the problem of computing Voronoi tesselations or Voronoi skeleton synchronously. This work presents the consequences of asynchronous computing on these approaches, showing how they fail. Then we propose methods to obtain similar results in simple asynchronous mode. We tackle the problem by adapting some synchronous methods to asynchronous computation. Section II of this report exposes some works related to computation of Voronoi diagrams and skeletonization. The third section shows the limitation of the basic approaches to solve the problem in the simple asynchronous mode. Section IV is our contribution, it explains how we can adapt some prior works to this challenge. Then, section V evaluates this work in simulation. We conclude by giving a short table that presents the results of the different methods and our method depending on different criteria.

Related Work

Voronoi partition of lattices and Voronoi skeleton extraction have given birth to numerous studies since the 17th century when René Descartes fragmented space maps into Voronoi-like regions. Skeletonization was investigated as a new shape descriptor by Blum in [START_REF] Blum | A Transformation for Extracting New Descriptors of Shape[END_REF], he introduced the well-know fire-propagation on a grass field metaphor as a model to compute the skeleton of a shape. We give the common definitions of the discrete generalized Voronoi diagram [START_REF] Okabe | Spatial tessellations: Concepts and applications of Voronoi diagrams[END_REF] and skeleton of a contour [START_REF] Pépin | Intelligent tiles -putting situated multi-agents models in real world[END_REF] as a reminder.

The Voronoi discrete diagram V D is a set of Voronoi regions V R(S i ), it represents a tesselation of the matrix of cells A. The region V R(S i ) of a seed area S i is formed by the cells c kl which are closer to this seed area than any other seed area.

Generalized Voronoi Diagram : V D (6) V D = {V R(S 1 ), ..., V R(S n )} V R(S i ) = {c kl /d(c kl , S i ) ≤ d(c kl , S j ), ∀j = i} S i ⊂ A, 0 < k ≤ m, 0 < l ≤ n, d(a, b) a metric
The Voronoi discrete skeleton V S of a contour C is the set of cells c ij which are at the ridges in distance map of the cells c kl supporting C, see [START_REF] Thiel | Les distances de chanfrein en analyse d'images : fondements et applications[END_REF]. These skeleton cells can be defined as the breaking cells of a synchronous wave propagated from the contour [START_REF] Pépin | Intelligent tiles -putting situated multi-agents models in real world[END_REF]. In other words, they are the loci where at least two wave fronts meet.

Voronoi Skeleton : V S

V S = {c ij /|{c kl ∈ C/d(c ij , c kl ) = w(c ij )}| ≥ 2} C ⊂ A, 0 < i, k ≤ m, 0 < j, l ≤ n w(p) distance to C (7)
In the domain of CA, the techniques used for computing the Voronoi diagram or skeleton are synchronous. We begin by introducing two common approaches: the first one is based on the fire propagation metaphor [START_REF] Adamatzky | Voronoi-like partition of lattice in cellular automata[END_REF], and the second one is known as wavefront expansion [START_REF] Barraquand | Numerical potential field techniques for robot path planning[END_REF]. The principle of the former approach is quite simple: the fire starts its propagation from the boundaries of fire sources and travels to the next neighbors synchronously. When two fire fronts meet on a same cell, this cell is a part of the Voronoi skeleton. The second approach is quite similar as it propagates a front, which is a wave growing from the boundaries of the wave sources. At each step the wave value increases. And when two waves collide on the same cell, this cell is in the Voronoi skeleton. To abstract, the fire is unaltered while crossing the environment (constant wave) whereas the wave grows steadily during its expansion.

To our knowledge, there is no reference to Voronoi skeleton extraction or Voronoi diagram computed in an asynchronous mode. We focus on Voronoi skeleton extraction in the rest of this paper because we are interested in exploiting this structure as roads for robotic navigation on discretized floor in future works. The Voronoi skeleton can be formulated as a set of bisectors between seed areas. Thus, the basic case of Skeleton extraction is the bisector extraction between two isolated seeds.

Next section introduces the definition of discrete bisector and gives a few more details about two common synchronous approaches and how they fail to extract bisectors asynchronously.

Inria 3 Limitation of Syncronous Computation

In this part we will focus on bisector extraction and explain why the presented techniques do not work for asynchronous computing. We examine two approaches by providing the expected bisector and the computed bisector to discuss its validity.

The common mathematical definition of a bisector is not adapted to discrete computation. We refer to the discrete definitions given in [START_REF] Adamatzky | Voronoi-like partition of lattice in cellular automata[END_REF]. The bisector Bis of cells a and b is defined as the set of cells c such that the distances, from c to a and c to b, differ by at most 1, formally in [START_REF] Thiel | Les distances de chanfrein en analyse d'images : fondements et applications[END_REF]. The distance used here is the Manhattan distance d 1 .

Bis(a, b) = {c ∈ A : |d 1 (a, c) -d 1 (b, c)| ≤ 1} (8)
d 1 (c ij , c kl ) = |k -i| + |l -j| 3

Principle

The principle applied here is the following: each seed cell has a unique identifier and this identifier is synchronously propagated to the neighboring cells on the lattice. When a cell receives an identifier, it stores this information forever, disabling any further update. Cells receiving two different identifiers at the same time are exactly equidistant to two seeds separated by an odd distance. Cells receiving only one identifier but located at the boundaries of an identified region are also considered equidistant (modulo 1) to two seeds separated by an even distance. In synchronous calculus, these cells support the bisector between the two seeds.

Synchronous Fire

Figure 1.a shows an example of an expected identifier map, computed synchronously following this principle. Cells colored in yellow/red have stored the identifier coming from the dark green/dark red source. This map represents two regions of a Voronoi diagram, and the bisector between these regions is in orange. Here the seeds are separated by an odd distance. Thus, simultaneously receiving different identifiers is sufficient to determine that a cell is on the bisector. Thanks to the synchronism, a simple CA with 4-state cells can compute this bisector, details are available in [START_REF] Adamatzky | Voronoi-like partition of lattice in cellular automata[END_REF].

Limitation

It is clear that this principle of identifier propagation is not wise in asynchronous computing. The underlying assumption, in synchronous calculus, is that the computed frontier between identified regions is the effective bisector between the seeds. But, by randomly updating a unique cell at each step, this assumption does not hold true. And the computed identifier map will probably not converge to the expected identifier map.

Figure 1.b. presents a computed identifier map, obtained by applying the fire principle asynchronously. By randomly selecting a cell to update on the lattice at each step, we can propagate identifiers and fix them onto the cells. The result illustrates a fire propagation influenced by random wind variation, not a fire constant propagation.

The regions in red and yellow are not the correct Voronoi regions, neither has the extracted frontier converged to the expected bisector.

Wavefront Expansion with Distance Map

0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2

Principle

The method exposed now is based on a distance map. The distance map used is a d 1 map on which each cell locally computes its Manhattan distance to the closest seed(s), see Fig. 2.a. It can be computed synchronously by the wavefront expansion algorithm presented in [START_REF] Barraquand | Numerical potential field techniques for robot path planning[END_REF]. The procedure is divided into the following steps:

1. Non-seed cells are set to infinity 2. Seed cells are set to 0 to start the wave propagation

A gradient is built by increasing the values of the nearest yet unreached cells

During this procedure, a list of currently considered cells is maintained, representing the wavefront. Cells on which the fronts collide belong to the bisector according to a threshold on the distance between the identified seeds.

Synchronous Wave

Figure 2.a illustrates the expected result of a 9-step synchronous diffusion from two seeds. In red/yellow the Voronoi region of the dark red/dark green source is shown. Cells colored in orange represent the bisector between the two seeds.

Limitation

First of all, the idea of extracting a bisector by selecting front meeting cells does not stand in simple asynchronous mode. The reason is still that asynchronous fronts can possibly meet on cells which do not support the bisector.

Nevertheless, computing a distance map can be achieved asynchronously. The asynchronous gradient rule G that provides such a distance map is expressed in [START_REF] Panagiotis G Tzionas | Collision-free path planning for a diamond-shaped robot using two-dimensional cellular automata[END_REF]. It simply updates the distance of a cell c to its closest seed(s) by adding one to the minimum distance computed by its neighbors. The expected distance map is provided as soon as the rule has converged.

G(c) : c.d 1 ← m+1, if c not seed 0, else. (9)
m = min ni∈u1(c) (n i .d 1 )
But, when we try to exploit this gradient to identify front meeting cells, it is not sufficient to isolate a full bisector, see Fig. 2.b. Each cell has a local knowledge of the gradient variation in its u 1 neighborhood. We classify these different gradient patterns into 4 different rotation invariant classes of relief. Therefore, seeds in dark red are local minima, cells in orange are local maxima, and cells in red are unidirectional minima. In this counterexample, when it comes to bisector extraction, only the local maxima class is informative (orange). Here, the two micro-sources have created a kind of macro-source that emits its own wave. The two asynchronous waves merge and do not collide, we call this phenomenon the waves fusion.

We can now state that for the simple asynchronous evolution, firefronts are subject to random wind variation and wavefront collisions are sometimes not detectable due to the phenomenon of waves fusion. Next section provides a working asynchronous method for computing identifier maps. It is based on the idea that using an convergent asynchronous gradient computation enables to build an identifier map at the same time. Thus a true identifier map can be computed asynchronously as soon as the gradient converges to the real distance map.

Our Contribution

First, this section presents a method for asynchronously computing an identifier map in a decentralized fashion. It requires to build a gradient at the same time and provides a basic Voronoi tesselation. Then, we introduce a rule to asynchronously extract a Voronoi skeleton as the set of bisectors between the computed Voronoi regions.

Identifier Map and Convergent Gradient

To overcome the weaknesses (random wind, waves fusion) noticed earlier, we design a procedure that allows to compute a correct identifier map in asynchronous calculus.

Asynchronous propagation rule

For this, we use both the gradient (d 1 ) and identifier (id) as a couple of information for each cell c. Each cell updates the received identifier until the gradient has converged in the whole network. This couple is asynchronously propagated from the sources onto the lattice of cells using the new rule P r (10). By combining both previous synchronous ideas into rule P r, we obtain a correct asynchronously computed identifier map in Figure 3.b. To fix the good identifiers in the cells, we wait until the d 1 map has converged. After convergence, a Voronoi region (red/yellow) is correctly identified as a set of cells owning the same seed identifier.

P r(c)

: (c.d 1 , c.id) ← (m+1, u), if c not seed (0, c.id), else. (10)
m = min ni∈u1(c) (n i .d 1 ) u = {k.id|k ∈ u 1 (c), k.d 1 = m} 4.1.2 Asynchronous propagation example 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2
The bisector is then extracted as the frontier between two Voronoi regions. This simple mechanism of bisector extraction is detailed next as we use it to extract skeleton cells.

Inria

Skeleton extraction

Skeleton extraction is achieved by marking the bisectors of the Voronoi regions. In the following, we introduce a rule to allow local asynchronous emergence of the skeleton cells.

Skeleton extraction rules

An intuitive way to extract the frontier between two Voronoi regions is by marking the boundaries of these regions. Skeleton extraction works similarly, if we define the skeleton as the set of frontiers between Voronoi regions. In a cell centered view, a skeleton cell owns an identifier which is different from the identifier of at least one of its neighbors. This first rule Sk formalizes this intuition in (11), but the extracted skeleton is thick.

Sk(c) : c.sk ← 1, if (∃n ∈ u 1 (c)/n.id = c.id) 0, else. (11)
Therefore, we design another rule for thinner skeleton extraction in (12). This rule is based on the discrete bisector definition, two types of bisector cells exist. The first type corresponds to cells wich are exactly equidistant to two sources, and the second one represents (modulo 1) equidistance to sources. From a cell centered view, first type skeleton cells receive exactly 2 identifiers (set skel to 1). Second type skeleton cells receive one or less identifier and have a neighbor which owns only one but different identifer (set skel to 2).

Sk(c) : c.sk ←    1, if |c.id| > 1 2, if |c.id| ≤ 1 ∧ (∃n ∈ u 1 (c)/|n.id| = 1 ∧ n.id = c.id) 0, else. (12)
Next, we show the results for all cases of two simple seeds bisector extraction using Rule Sk (12). In order to exhibit each kind of possible bisector we reproduce the examples from [START_REF] Adamatzky | Voronoi-like partition of lattice in cellular automata[END_REF]. Six cases are generated by varying the spacing between two simple seeds according to odd or even d 1distance, horizontally or vertically. The thin bisectors extracted using (12) are given in Figure 4. Cases 1, 2, 3 and 6 are for odd distances between the seeds, the bisector has a thickness of one cell. For the cases 4 and 5, the bisector has a thickness of two cells because the distance between the seeds is even.

Examples

Application

Area Voronoi Diagram

We can already compute a basic area Voronoi diagram [START_REF] Okabe | Spatial tessellations: Concepts and applications of Voronoi diagrams[END_REF], without synchronization, by identifiying seeding areas instead of isolated source cells, see Fig. 5.

Area Identification

Source areas emerge by aggregating contiguous source cells during a phase of area identification consensus. The area identifier combines each aggregated cell identifier, using rule Aid presented in (13). This local rule allows two contiguous sources to update their identifier by combining the previous ones. After a certain amount of time, every cell in a same contiguous area share the same identifier. Identifier based skeleton extraction works in simple asynchronous mode for an area Voronoi diagram. Each cell executes 3 steps: the first one is the area identification, which is followed by the identifier propagation; and finally the skeleton extraction itself (resp. by the rules Aid, P r, Sk. For example, Fig. 5.a represents two source areas (green and red ) and a skeleton in orange. For the simple maze in Fig. 5.b, no skeleton is extracted because the seeds are all contiguous and represent a single area (green). In Fig. 5.c, an orange skeleton is extracted between the two seeding areas (in green and red ).

Limitation for robotic navigation

These examples bring forward the fact that the skeleton extraction of an area Voronoi diagram is not satisfying for establishing maximum-clearance roadmaps useful in robotic navigation. In the context of robotic navigation on the area Voronoi skeleton, a robot could not navigate into the light green maze (Fig. 5b), neither enter the dark red concavity (Fig. 5c). These issues are directly related to the definition of the area Voronoi diagram. More complete skeletons can be extrated by considering the line Voronoi diagram.

Line Voronoi Diagram

In this section, we show how to compute a line-like Voronoi diagram [START_REF] Okabe | Spatial tessellations: Concepts and applications of Voronoi diagrams[END_REF] and extract the associated skeleton, see Fig. 7. First, the idea is to generate inner bisectors between the edges of a shape for obtaining a more complete skeleton. Thus we discuss edge identification which requires to isolate the edges located on the contour of a diffusion area. Then we illustrate the mechanisms of edge identification consensus and line voronoi skeleton extraction.

Edge Identification

In our approach we consider an identifier for each side or face of an area as studied earlier in [START_REF] Panagiotis G Tzionas | Collision-free path planning for a diamond-shaped robot using two-dimensional cellular automata[END_REF]. Therefore, each area of diffusion now creates multiple identifiers. As an hypothesis of simplification, we decide to identify horizontal, vertical and diagonal contour lines only. So the model presented here will only work for sources with diagonal, vertical or horizontal faces.

Classes and Local Patterns Each cell uses a local mask m i to identify its edge type, the set of masks M is given in Table 1. These masks are classified into 6 classes of rotational symmetry. And elements in a same class share the same behavior for face identification. For the sake of simplicity we design the function Class i which maps the cell to its edge class, see (14). Edge Identification This procedure is called an edge identification consensus, see (15). It is a consensus-decision-making which requires communications and delay before every cell on the edge agree on a common identifier. Detailed consensus rules are given in appendix. It is important to notice that Class II and Class V I cells own multiple identifiers (up to 4) depending on the direction of propagation.

Cl(c) : c.cl ← Class i (c, M ) if c seed 0 else. (14)
Eid(c, d) : c.id ← Eid i (c, d), if c.cl = Class i c.id, else. (15)

Example

To recapitulate, when one cell is selected, it executes the 3 following steps : edge identification, identifier propagation and skeleton extraction. Edge identification To illustrate how the Eid rule works, we identify edges step by step on an example of a source area, presented in Fig. 6: a) A gray polygonal shaped source area which will emit multiple identifiers onto the lattice.

b) Blue and yellow sub-areas appear on the contour. Each color represents an edge identified by Eid V for Class V cells. Cells with a same color now possess the same identifier.

c) Blue and yellow sub-areas have expanded. New edges in Green and red were identified. Some corner cells now possess two identifiers for belonging to two perpendicular edges.

d) A last color (aqua) appears to identify a diagonal edge. Corners and full cells worked together to identify this line. Class V I cells act as intermediates between corners that cannot communicate in u 1 neighborhood.

Identifier propagation and skeleton extraction

The extracted skeleton is evolving dynamically according to the distance-identifier map. It is correct as soons as the asynchronously computed map converges. For our example, the map and skeleton are given in Fig. 7. In Fig. 7a, the edges are already colored according to the previous step of identification consensus. Now these edges act as sources and the free cells around them are colored according to the computed distance-identifier map. This map is computed by using P r again (10). Fig. 7b presents the skeleton extracted using (12) In the next section we show in simulation the skeletons extracted on different maps using an area voronoi diagram or a line voronoi diagram. Our purpose is to use these skeletons as maximum-clearance paths for robotic navigation.

Inria 6 Experiments

First, we present the simulator used for our experiments. Then, we show the different cases of thick and thin bisector extractions. And finally, we give the emergent skeleton computed on different maps using an area voronoi diagram or a line voronoi diagram. Some of the maps used in simulation are taken from [START_REF] Adamatzky | Voronoi-like partition of lattice in cellular automata[END_REF][START_REF] Panagiotis G Tzionas | Collision-free path planning for a diamond-shaped robot using two-dimensional cellular automata[END_REF] and others were created especially for this work. These maps expose the drawbacks of area voronoi skeleton regarding robotic navigation. Also, it shows that thinner line skeletons are interesting when it comes to narrow passages.

Simulator

We use the simulator SmartTiles (project gforge.inria.fr) for our experiments, it simulates a network of intelligent tiles. It was developped and is still maintained by Olivier Rochel from the SED Engineers Team. The rules for identification, propagation and skeleton extraction presented in this report were implemented in Python for synchronous and asynchronous modes. In the next section, we present the different cases of bisector extraction using thick extraction or thin extraction.

Bisectors

We present the results of Sk for thick (11) or thin (12) bisector emergence.

The bisectors given in Fig. 8 were obtained by applying the first rule of extraction which selects the boundary cells of a Voronoi region. As we mention earlier in this report, the bisectors computed with this rule are thick. It has motivated us to develop a rule for extracting thinner skeletons. Now we use the second extraction rule, which isolates thin bisectors by differenciating strict equidistance and modulo 1-equidistance from the sources. When a cell has a different identifier from one of its neighbors, it emerges as a boudary cell. Thin bisectors are colored in white, and their 4-connexity dilatation in yellow on Fig. 9. The bisector extracted for each case are complete and have the minimum thickness allowed in our model.

We give more details about the spacing choices between two sources a and b. Let

Area Skeleton

In this section, we present our results in simulation regarding skeleton/navigation roads extraction using area Voronoi diagrams.

Fig. 10 represents the thick skeleton associated to area Voronoi diagrams for different maps. Maps a and d exhibit no skeleton at all, this is explained by the fact that only one contiguous area is identified for these maps. On the opposite, the other maps produce a diagram and the extracted skeleton is shown in white. Two areas were computed for c and e, 9 for b and 13 for f . As pointed earlier, the skeleton extracted in map e does not enter concave shapes. For an application in robotic navigation, no roads are available for 2 of the environments, and even when provided they cannot enter concave shapes.

Line Skeleton

In this part, we give the obtained skeleton extracted using line Voronoi diagrams on the same maps.

We can observe thick skeletons extracted from line Voronoi diagrams in Fig. 11. Roads are available for each map and also enter concave shapes. These first aspects are satisfying but the extracted skeleton is too thick. For instance in maps b, d and e, the roads are close to obstacles. Therefore, we also provide the thinner skeletons in Fig. 12, we can consider these skeletons as maximum clearance roadmaps. This section summarizes the quality criteria satisfied by the skeleton extraction methods presented in this report. Then we discuss perspectives regarding robotic navigation using line Vononoi skeleton on smart floors.

Perspectives

In this report, we have shown how dynamic roadmaps can be extracted asynchronously in a decentralized fashion using a network of floor sensors. We can mention an application of robotic navigation using a floor equipped with smart tiles [START_REF] Pépin | Intelligent tiles -putting situated multi-agents models in real world[END_REF], in which each tile has its own sensors, processing unit and memory. Applying our work in such ambient intelligent environments can represent an interesting realization for robotic navigation.

. 1 Fire

 1 Propagation with Identifier(a) synchronous mode (b) asynchronous mode

Figure 1 :

 1 Figure 1: Identifier map computing with two seeds (dark red/dark green), two Voronoi regions (red/yellow), one discrete bisector (orange)

  asynchronous mode, colors are relief patterns

Figure 2 :

 2 Figure 2: Distance map computing with two seeds (dark red/dark green), one discrete bisector (orange)

Figure 3 :

 3 Figure 3: Distance-gradient only in synchronous mode (a) and Distance-Identifier mix in asynchronous mode (b)

Figure 4 :

 4 Figure 4: Bissector Extraction Cases for two seeds a (red) and b (green)

  Aid(c, d) : c.id ← c.id ∪ d.id, if c, d seeds c.id, else.

Figure 5 :

 5 Figure 5: Area Voronoi diagrams skeleton extractions

Figure 6 :

 6 Figure 6: Edge identification process

Figure 7 :

 7 Figure 7: Line Voronoi diagram and skeleton extraction

  s x = |x a -x b | and s y = |y ay b |. If s x = s y we have two cases, s x is an odd or even distance. On the other hand, if s x = s y we have |{odd, even} 2 | = 4 more cases.

Figure 8 :

 8 Figure 8: Thick Bisector Extraction Cases

Figure 9 :

 9 Figure 9: Thin Bisector Extraction Cases

Figure 10 :

 10 Figure 10: Thick Skeleton for Area Voronoi Diagram

Figure 11 :Figure 12 :

 1112 Figure 11: Thick Skeleton for Line Voronoi Diagram

1 Fire 4 . 2 5

 1425 Propagation with Identifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.1.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.1.2 Synchronous Fire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.1.3 Limitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 Wavefront Expansion with Distance Map . . . . . . . . . . . . . . . . . . . . . . 6 3.2.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2.2 Synchronous Wave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2.3 Limitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 Our Contribution 8 4.1 Identifier Map and Convergent Gradient . . . . . . . . . . . . . . . . . . . . . . . 8 4.1.1 Asynchronous propagation rule . . . . . . . . . . . . . . . . . . . . . . . . 8 4.1.2 Asynchronous propagation example . . . . . . . . . . . . . . . . . . . . . 8 Skeleton extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 4.2.1 Skeleton extraction rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Application 10 5.1 Area Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.1.1 Area Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.1.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.1.3 Limitation for robotic navigation . . . . . . . . . . . . . . . . . . . . . . . 10 5.2 Line Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.2.1 Edge Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.2.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6 Experiments 13 6.1 Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.2 Bisectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.3 Area Skeleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.4 Line Skeleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7 Conclusion 17 7.1 Qualitative comparison of the different methods . . . . . . . . . . . . . . . . . . . 17 7.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Inria RESEARCH CENTRE NANCY -GRAND EST 615 rue du Jardin Botanique CS20101 54603 Villers-lès-Nancy Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Table 1 :

 1 Classes and source patterns

	I Isolated	II Corners
	III Lines	IV Extremities
	V Directions	VI Full

  7.1 Qualitative comparison of the different methodsOur method for skeleton extraction LineV D2 satisfies the criterion of synchronous/asynchronous calculus on a static or dynamic map (moving obstacles). Moreover, dilating the skeleton also allows to satisfy the criterion of 4-connexity in certain cases. Here is a table comparing the methods depending on qualitative criteria.

		Sync. Async. Centr. Decentr. Stat. Dynam. 4-Conn.
	LineVD2	Ok	Ok	Ok	Ok	Ok	Ok	Ok
	Barraquand [2]	Ok	-	Ok	-	Ok	-	?
	Tzionas [9]	Ok	-	-	Ok	Ok	-	-
	Adamatzky [1]	Ok	-	-	Ok	Ok	-	-

RR n°8547

Inria

Appendix

Class

Id presented to neighbor d