In general humanoid robots have a torso with a head, two arms and two legs Some humanoid robots may also have a 'face', with 'eyes' and 'mouth' Step 3

31 2 4 6 -1 q 2 , q 8 [rad] 2 4 6 -0.2 0.2 q 3 , q 9 [rad] 2 4 6 -1 -0.5 q 4 , q 10 [rad] Temps [s] 0 2 4 6 0.5 1 1.5 q 5 , q 11 [rad] 0 2 4 6 -1 -0.5 0 q 6 , q 12 [rad] 0 2 4 6 -0.2 0 0.2 q 7 , q 13 [rad] Temps [s]

Outline of the presentationo

  Context and problem formulation  Humanoid robotics  Origin of Humanoid robots  Humanoid robots over the years  Humanoid robots of today  Problem formulation o Our demonstrators  SHERPA : A two-leg walking robot  HOAP3 : A humanoid robot o Optimal Pattern generation  Related work  Proposed solution  Simulation results o Walking control  Summary of the study  Proposed solution  Simulation results o Towards human-like walking  One basic idea  Related work  Why human like walking  Main steps of our developed study . Chemori (LIRMM, CNRS -Univ. Montpellier 2, France) ICEECA 2012 -khenchela, Algeria 10 Some features of a Humanoid Robot The characteristics features of a humanoid Robot include:  Autonomous learning  Avoiding harmful situations to people, and itself  Safe interacting with human beings and the environment A humanoid robot or an anthropomorphic robot is a robot with an overall appearance, based on that of the human body, allowing interaction with made-for-human tools or environments.

Origin

  Karel Capek coined the term Robot In 1941: Isaac Asimov proposed Three Laws of Robotics In 1948: Norbert Wiener formulated the principle of Cybernetics In 1969: Miomir Vukobratovic proposed the theory of Zero Moment Point (ZMP) In 1973: Waseda University (Tokyo) developed WABOT-1, which was capable to communicate with a person in Japanese, could do distance and direction measurements using sensors, artificial ears, eyes and as well as an artificial mouth In 20 th century (end) many robots have been proposed : Greenman in 1983, WABOT-2 in 1984, WHL-11 in 1985, the musician robot-WASUBOT in 1985, series of seven biped robots called E0-E6 by Honda in 1986, the full scale anthromorphic robot-MANNY in 1989, with 42 degrees of freedom, Honda's P1 through P3 in 1993, HADALY and WABIAN in 1995, SAIKA in 1996 and ASIMO by Honda in 2000. In 21 st Century, further additions were done by Sony's QRIO in 2001, HOAP and ACTROID in 2003, PERSIA and KHR-1 in 2004, PKD android and WAKAMARU in 2005, TOPIO in 2007, Justin, KT-X and NEXI in 2008, SURALP in 2009, Robonaut-2, SURENA-II and HRP-4C in 2010 phases : Single support & double support  1 transition : impact with ground (instantaneous) Single support Double support Impact We need to control the robot on the whole cycle What we need for that ? problems to be resolved : Pattern generation and control design for walking . Chemori (LIRMM, CNRS -Univ. Montpellier 2, France) ICEECA 2012 -khenchela, Algeria 18 dof : 18 (6dof/leg) + 6 dof (position/orientation)  3 rotations (hip)  1 rotation (knee)  2 rotations (ankle) Actuation : 3 modules / leg For each module :  2 AC brushless motors  Cable differential joints Transparent actuation (low inertia & backdrivable) . Chemori (LIRMM, CNRS -Univ. Montpellier 2, France) ICEECA 2012 -khenchela, Algeria 22 HOAP3 : Architecture 28 dof : 6 dof/leg -6dof/arm -3dof/head -1dof/body al. 2001] [Hong et al. 2009] [Tang et al. 2007] [Ferreira et al. 2009] [Lee, 2007] 2MLIPM [Albert et al. 2002] 3MLIPM [Takenaka et al. 2009] Biomchanics [Bruneau et al. 1998] Motion capture [Harada, 2009] [Kim et al. 2009] [Takano et al. 2007] Polynomial functions [Zaier et al. 2007] Neural networks [Yang et al. 2007] Van Der Pol [Katoh et al. 1984] Sinusoidal [Zhao et al. 2008] FFT [Yamaguchi et al. 2008] Speaker : A. Chemori (LIRMM, CNRS -Univ. Montpellier 2, France) ICEECA 2012 -khenchela, Algeria 27 Objective Assumptions Method & application Design and development of a pattern generator for stable dynamic walking A1: Walking on a horizontal ground without obstacles A2: walking cycle (SS+imact phases), no DS phase Method 1 : B-Spline functions with control points Method 2 : B-Spline functions with boundary conditions & interpolated points Application : Walking robot SHERPA Speaker : A. Chemori (LIRMM, CNRS -Univ. Montpellier 2, France) ICEECA 2012 -khenchela, Algeria 28 B-Spline with boundary conditions & interpolated points Integration of the proposed solution in a simulator  Simulation results without optimization  Trajectories optimization  Simulation results with optimization . Chemori (LIRMM, CNRS -Univ. Montpellier 2, France) ICEECA 2012 -khenchela, Algeria



  Study of the influence of the upper limbs (torso & arms) on dynamic stability and energy consumption during walking Human walking study  Gather human walking data Step • Pattern generator design (based on human walking data) Step • Control architecture (controller + stabilizer) Step • Implementation on a humanoid robot (HOAP3)  Kinematics & kinetics of human walking  Energy & muscle activity during walking  Simulation of Walking  … etc Human walking How we can acquire data on human walking ? -Gait Marker Placement Speaker : A. Chemori (LIRMM, CNRS -Univ. Montpellier 2, France) ICEECA 2012 -khenchela, Algeria 56 Context : A joint French-Italian project  LIRMM(France) / LABLAB (Italy) Objective : Human walking analysis  Effects of upper limbs on human walking walking at different speeds -35 markers using Plug-in Gait template (a) -Reconstruction of movement using Vicon Nexus (b) -Estimation of CoM using Lifemod (c) Motion capture system Reflective marker Is the process of recording movement, and translate that movement to a digital model Basic idea of the proposed solution  Proposed human data base pattern generator  Simulation results

  . H. Walking Basic idea of the proposed solution What happen if we apply directly human data to the humanoid robot ? ZMP is outside the polygon of support  unstable waking ! was implemented in the robot simulator Human walking data used for upper body For a three-step walking scenario starting from rest proposed control scheme Use of human data with scaling of the CoM trajectories Simulation scenario 3 : Human data with CoM scaling

Related work

Human-Data based schemes


Context Human data Control Scheme Experiments Conclusion Context Human data Control Scheme Experiments Conclusion

Context

Human data Control Scheme Experiments Conclusion

Objective : Use of whole body control to perform different tasks Use of human data in the control scheme Include the robot's dynamics in the control scheme  dynamic stability

Control scheme

Humanoid robot

Reference Trajectories or Motion parameters

Issued from human motions

Our main objective

Related work

Human Human data based whole body motion control using offline calculation [Nakaoka et al., 2003[Nakaoka et al., , 2005] ] Data from human motion capture are used as motion primitives to produce postural imitation (only postural motions, no walking).

[ Harada et al., 2009] Data from human motion capture are used to find gait's parameters.

[ Suleiman et al., 2008] Data from human motion capture are first scaled to humanoid joint position, then an optimization with constraint is used.

: Offline computations allows optimized motions : Offline computation do not allow reactive motions Human data based whole body motion control using online calculation [Schaal, 1999 ;Schaal et al., 2003 ;Calderon & Hu, 2005] Data from human motion capture are used to feed a learning system to produce accurate movement primitives.



  State of art of human-based control  Limitations of human-based control o Proposed control scheme  Basic idea of the proposed control scheme  Prioritized tasks  Tasks definition  ZMP-based nonlinear stabilizer  Summary of the proposed control scheme o Real-time experimental results  Our demonstrator : HOAP-3 Robot  Scenario 1 : Squat-like motions  Scenario 2 : Online adaptation towards slope variation  Scenario 3 : Dynamic walking motions  Scenario 4 : Toward dynamic walking on irregular ground o Conclusion & future work It helps building several muscles in legs  A cyclic motion  Alternating two positions  Stand position with extended arms  Sit position bent knees Is one of the main gaits of locomotion  Typically slower than running.  Alternating the legs  Only one foot may leave contact/ground  There is also a period of double-support

[

  Yamane & Hodgins, 2009 ; Yamane et al., 2010] Two controllers are used in this application. First controller : a balance controller. Second controller : joint space trajectory tracking [Montecillo-Puente et al., 2010] Data from human motion capture are performed in real time to produce postural imitation (postural motion, no walking). : Reactive motions using feedback from sensors : No walking motions are reproduced  Basic idea of the proposed control scheme  Prioritized tasks  Tasks definition  ZMP-based nonlinear stabilizer  Summary of the proposed control scheme Task formalism is used to control a robot for tracking several objectives  In the operational space  Use the high redundancy of robots  Concept initially proposed by [Nakamura 1987] and [Siciliano 1991]  The task formalism has been used recently in humanoid robotics  In [Sentis et al 2006] for multi-contact dynamic motions  In [Mansard 2009] has generalized the formalism by using the addition and removal of tasks during the control execution  In the literature, several tasks are needed to produce stable whole-body motions  In this work, the proposed architecture is focused on only 4 main tasks o Task 1 :The relative feet position and orientation tracking, o Task 2 : CoM position tracking with nonlinear ZMP regulation, o Task 3 : Body orientation and the o Task 4 : Joints' limits avoidance 6 dof/leg -6dof/arm -3dof/head -1dof/body Electronic boards inside Speaker: D. GALDEANO (LIRMM / UM2, France) HLR 2014 (Heidelberg, Germany) proposed solution :  Whole body motion  Continuous control framework  Natural and smooth motions Proposed Solution: Task based whole-body control (i) the CoM with a nonlinear ZMP regulation, (ii) the relative pose of robot's feet, (iii) the body orientation and (iv) joint's limit avoidance Validation: Real-time experiments on HOAP-3 humanoid robot Future work : Validation for more complex tasks  Interaction with human  Use of human data  Improve the ZMP regulation  Experiments on HRP4 robot

of human-based control Context Human data Control Scheme Experiments Conclusion

 Motion Capture system  State of art of human-based control  Limitations Speaker: D. GALDEANO (LIRMM / UM2, France) HLR 2014 (Heidelberg,

Germany) 8 Context Human data Control Scheme Experiments Conclusion

	Motion Capture system
	Context: Walking motion analysis project
	LABLAB, University of Rome Foro Italico, Pr. Capozzo, Department of
	Human Movement and Sports Sciences.
	Equipment : 1 host PC
	10 Vicon cameras
	3 Forces plates

Context Human data Control Scheme Experiments Conclusion

	Study: 15 Subjects
	Different walking speed
	35 markers using Plug-in Gait template
	Reconstruction of movement using Vicon Nexus
	Estimation of CoM

using Lifemod Motion Capture system Context Human data Control Scheme Experiments Conclusion


Dong Quan

Patrick Loiseau

Alonso Silva

Combinatorial Bandits for Sequential Learning in Colonel Blotto Games

The Colonel Blotto game is a renowned resource allocation problem with a long-standing literature in game theory (almost 100 years). However, its scope of application is still restricted by the lack of studies on the incompleteinformation situations where a learning model is needed. In this work, we propose and study a regret-minimization model where a learner repeatedly plays the Colonel Blotto game against several adversaries. At each stage, the learner distributes her budget of resources on a fixed number of battlefields to maximize the aggregate value of battlefields she wins; each battlefield being won if there is no adversary that has higher allocation. We focus on the bandit feedback setting. We first show that it can be modeled as a path planning problem. It is then possible to use the classical COMBAND algorithm to guarantee a sub-linear regret in terms of time horizon, but this entails two fundamental challenges: (i) the computation is inefficient due to the huge size of the action set, and (ii) the standard exploration distribution leads to a loose guarantee in practice. To address the first, we construct a modified algorithm that can be efficiently implemented by applying a dynamic programming technique called weight pushing; for the second, we propose methods optimizing the exploration distribution to improve the regret bound. Finally, we implement our proposed algorithm and perform numerical experiments that show the regret improvement in practice.

I. INTRODUCTION

The Colonel Blotto game (henceforth, CB game) is a classical resource allocation problem where players simultaneously distribute a fixed number of troops (indivisible resources) on a certain number of battlefields to maximize the aggregate value of battlefields they win, each battlefield being won by the player who allocates the most resources to it. The CB game can be used to model a vast range of practical situations, e.g., allocating security forces in security ( [START_REF] Arce | Weakest-link attacker-defender games with multiple attack technologies[END_REF], [START_REF] Chia | Colonel blotto in the phishing war[END_REF]); allocating broadcasting time in advertisement ( [START_REF] Masucci | Strategic resource allocation for competitive influence in social networks[END_REF]); allocating shared spectrum in wireless networks ( [START_REF] Hajimirsaadeghi | A dynamic colonel blotto game model for spectrum sharing in wireless networks[END_REF]) and allocating resources to persuade voters in politics ( [START_REF] Llorente-Saguer | Pure strategy nash equilibria in non-zero sum Colonel Blotto games[END_REF]).

The CB game was first introduced by [START_REF] Borel | La théorie du jeu et les équations intégrales à noyau symétrique[END_REF] in 1921 and has been extensively studied after, especially in recent years. In particular, the Nash equilibrium of the relaxed continuous version (where resource allocations can be fractional) was studied by [START_REF] Gross | A continuous Colonel Blotto game[END_REF], [START_REF] Roberson | The Colonel Blotto game[END_REF], [START_REF] Schwartz | The heterogeneous Colonel Blotto game[END_REF] under different assumptions. For the discrete version (with indivisible troops), [START_REF] Behnezhad | Faster and simpler algorithm for optimal strategies of Blotto game[END_REF] proposed polynomial (but still expensive) algorithms to compute the exact equilibrium whereas [START_REF] Vu | Efficient computation of approximate equilibria in discrete Colonel Blotto games[END_REF] proposed a much faster algorithm to compute an approximate equilibrium. All these works, however, only consider the full information one-shot game setting. 1 In most of the applications, the most natural setting is an incomplete information repeated game. For example, in advertising, one can consider an online marketing campaign which once per day reviews how the marketing campaign performs and based on this information, learns a better strategy. Resources and strategies of the adversaries are usually unknown or need to be estimated by the learner; especially in the dynamic setting. The question is then how to design a good sequential resource allocation policy.

The CB game has a specific combinatorial structure and the most natural way to model sequential learning in this game is to use the Combinatorial Bandit (henceforth, CBAND) framework, defined as follows: at each stage t within a time horizon T , the learner chooses a vector p t in her action set S ⊂ {0, 1} E , for an E ∈ N; then a loss vector t ∈ [0, 1] E is generated by the adversaries; the learner suffers a scalar loss L (p t ) = ( t ) p t . The learner's objective is to minimize her expected regret R T , i.e., the difference between her cumulative loss and that of her single best-action in hindsight, formally defined as follows:

Importantly, in CBAND, the feedback that the learner receives at the end of each stage is under the bandit setting: the learner's only observation when stage t ends is the scalar loss L (p t ). This is the most generic informationsetting considered in the literature. This setting covers many applications of the CB game; e.g., in advertising, the total profit of selling a product can be easily observed while it is much harder to keep track of the partial profit of each ad (simultaneously promoting that product). COMBAND algorithm, proposed by [START_REF] Lugosi | Combinatorial bandits[END_REF], is a classical algorithm for solving CBANDs. It provides a regret guarantee of the order O( T E log |S|) that improves significantly than naively using other standard Multi-armed Bandit algorithms. In the CB game (modeled as a CBAND), E is polynomial in the number of battlefields and troops while |S| is exponential in terms of these parameters. However, applying directly COMBAND, we face two important challenges.

a) Challenge 1: Computation Issue: The main problem with the COMBAND algorithm is that in general, it cannot be implemented efficiently (its running time is in O(|S|T )). However, in some special cases, there are techniques that allow us to efficiently implement variants of this algorithm. The path planning problem (henceforth, PPP) is such an example: each action is equivalent to a path on a graph and the loss of a chosen path equals to the aggregation of losses of edges on that path. In PPPs, [START_REF] Sakaue | Efficient bandit combinatorial optimization algorithm with zero-suppressed binary decision diagrams[END_REF] recently proposed an efficient variant of COMBAND running in O(E 2 T ) based on the weight-pushing technique (introduced by [START_REF] Takimoto | Path kernels and multiplicative updates[END_REF]). However, this algorithm has a redundancy in representation (involving 5 sub-algorithms) and is still non-trivial to be implemented. A direct application of COMBAND to the CB model is impractical; can we find a new representation of CB game to obtain a path planning model allowing an efficient implementation of COMBAND? If the answer is positive, we also desire a simpler representation of this efficient algorithm.

b) Challenge 2: Optimizing Exploration Distribution: COMBAND mixes an exploitation procedure (updated according to an unbiased loss estimator) with an "exploration distribution" on the action set. The regret bound given by COMBAND algorithm depends directly on the choice of an exploration distribution to be used. For PPPs (and also for CB games), the optimal exploration distribution remains unknown (this is an open question proposed by [START_REF] Lugosi | Combinatorial bandits[END_REF]).

Our Contributions: In this paper, we provide the first analysis of sequential learning in CB games. The action set of the CB game can be represented by a special graph; thus, we can model it as a PPP. Focusing on this model, our contribution is twofold: (i) Based on the weight pushing technique, we construct a simple algorithm, called EDGE(µ), that can be efficiently implemented and it guarantees a polynomial regret bound in terms of the CB game's parameters; (ii) We propose a fast method to compute an exploration distribution that can be used as the input of EDGE(µ) to improve the regret bound. Numerical experiments are conducted to illustrate this improvement, both in terms of the performance and the computation time.

Although in this work, we focus only on the CB game, note that our setting is more general. Our results can be extended to PPPs with general graphs that includes many other resources allocation games and multi-task online optimization. Note finally that [START_REF] Combes | Combinatorial bandits revisited[END_REF] proposed another variant of COMBAND (mixing with ideas of the OSMD algorithm proposed by [START_REF] Audibert | Regret in online combinatorial optimization[END_REF]), called the COMBEXP algorithm, that improves the complexity of COMBAND in several cases while maintaining the regret guarantees. However, PPP is not explicitly considered in [START_REF] Combes | Combinatorial bandits revisited[END_REF] and it remains an open question whether any arbitrary instance of the PPP satisfies the condition such that COMBEXP can be efficiently implemented (i.e., the convex hull of the action set can be represented by a polynomial number of linear equations and linear inequalities). Therefore, COMBAND is still the state-of-the-art algorithm for our considering problem. Moreover, COMBEXP also uses the uniform exploration distribution that is sub-optimal in PPPs (see also [START_REF] Lugosi | Combinatorial bandits[END_REF]); thus, our second contribution in finding better exploration distributions is relevant.

Notation: Throughout the paper, we use bold symbols (e.g., x) to denote (column) vectors with subscript indexes (e.g., x i ) to denote its elements. On the other hand, the superscript t refers to the stage and the notation [k] denotes the set {1, 2, . . . , k}, for any k ∈ N \ {0}. In graphs, we use the notation e ∈ p to refer that the edge e belongs to the path p. Finally, denotes the transpose matrix/vector and M k×k is the set of all real matrices with dimension k × k .

II. PRELIMINARIES

In this section, we review the standard COMBAND algorithm (proposed by [START_REF] Lugosi | Combinatorial bandits[END_REF]). We also highlight its drawbacks that need be improved. A pseudo-code of COMBAND, written in our notation, is given as Algorithm 1.

Algorithm 1: COMBAND(µ) for CBAND. At each stage t, COMBAND keeps a weight w t (p) for each action p and it samples an action (line 5) from a distribution, called d t , mixing between an "exploitation" distribution ν t (normalization of the action weights) and an "exploration" distribution µ (unchanged over time). An unbiased estimator ˆ t ∈ [0, 1] E , based on the "co-occurrence" matrix C t := E p∼d t [pp ] ∈ M E×E , is used to estimate the loss vector t . Then, the action weights are updated by the exponential rule using these estimated losses (line 9).

Input: S ⊂ {0, 1} E , T ∈ N, γ ∈ [0, 1], η > 0, distribution µ on S. 1 ∀p ∈ S,
In COMBAND, the exploration distribution µ is chosen a priori and it can be any arbitrary distribution on S such that S is spanned by the support of µ. Importantly, the performance guarantee of COMBAND depends directly on the choice of µ; to highlight this, we henceforth parameterize COMBAND with µ and use the notation COMBAND(µ). Consider the matrix M (µ) = E p∼µ pp , we denote by λ * [M (µ)] the smallest nonzero eigenvalue of M (µ) and let n := max{ p 1 , p ∈ S}. An upper-bound of the expected regret given by this algorithm is stated as follows.

Theorem 2.1: In any CBAND problem, the COMBAND(µ) algorithm with appropriate parameters yields an expected regret

R T ≤ 2 [2n/(E • λ * [M (µ))]+1] T E log(|S|).
This theorem is extracted from Theorem 1 in [START_REF] Lugosi | Combinatorial bandits[END_REF] and is rewritten here under our notation. Trivially, the larger λ * [M (µ)] is, the better the regret bound that COMBAND(µ) guarantees. The problem of optimizing µ and λ * [M (µ)] in general CBANDs (and particularly for PPPs) remains an open question (see [START_REF] Lugosi | Combinatorial bandits[END_REF] for several positive examples). Regarding the computation complexity of COMBAND, given a time horizon T , it runs in O(|S| • T ). Since |S| is exponential in terms of E, it is inefficient to implement COMBAND. This is due to the weights-updating step (line 9), the sampling step (line 5) and the computation of the co-occurrence matrix (line 7). We will analyze these steps in Section IV and provide alternative procedures to improve them in the sequential learning model of Colonel Blotto games.

III. COMBINATORIAL BANDIT MODEL OF LEARNING IN COLONEL BLOTTO GAMES

We consider a sequential learning problem that involves a learner, A adversaries, n battlefields and a time horizon T (n ≥ 2 and T > 0 are known by the learner, A ≥ 1). Each battlefield i ∈ [n] has a fixed value b i > 0 (hidden from the learner) and we assume normalized values, that is

n i=1 b i = 1. At each stage t ∈ [T ]
, the learner faces a decision problem of distributing m troops (m ≥ 1 is fixed) towards the battlefields while the adversaries simultaneously allocate theirs. The learner's allocations have to satisfy the budget constraint, that is she chooses a strategy p t in the action set S := {p ∈ N n :

n i=1 p i = m}. 2 For any i ∈ [n],
the element p i of strategy p represents the quantity of troops she allocates to battlefield i. At the end of time t, the learner suffers a loss L (p t ) equal to the sum of values of battlefields that she loses, i.e., where there is at least one adversary having strictly higher local allocation than her. Without loss of generality, in case there are players who have tie allocations which are the highest in battlefield i, the value b i is shared equally among them. When t ends, the learner observes the scalar number L(p t ) but she does not know which battlefield she lost or won nor the strategies that the adversaries used (the bandit feedback). Note that the incurred loss is bounded, i.e., L(p t ) ≤ 1, ∀p t , ∀t. The cumulative loss T t=1 L(p t ) is computed and the learner's objective is to minimize her expected regret (defined in (1)). Henceforth, we refer to this model as CB(m, n) problem.

It is important to note that the size of the learner's strategy set is |S| = n+m-1 n-1 = O(2 min{n-1,m} ), that is exponential in terms of m (or n). Our objective is to design an algorithm guaranteeing an expected regret that is sub-linear in T and polynomial in terms of m and n while its complexity is also polynomial in m, n, and T .

A. Layered Graph and Learning in CB Games as PPPs

In this section, we restate the formulation of CB(m, n) as a PPP that allows an efficient implementation of COMBAND. To do this, for each CB(m, n) game, we design a special directed acyclic graph, called G m,n , such that there exists a one-to-one mapping between the action set S and the set of all paths of G m,n ; we call this the layered graph. 3 The illustration of an instance of such a graph is presented in Figure 1. The proof of existence of G m,n can be intuitively seen in Figure 1 and a formal definition is as follows (note that this definition is extracted from [START_REF] Vu | Colonel blotto and hide-and-seek games as path planning problems with side observations[END_REF]).

i ∈ [n -2],
there is a directed edge from node (i, j 1 ) to node

(i + 1, j 2 ) (of Layer (i + 1)) if 0 ≤ j 1 ≤ j 2 ≤ m.
Battlefield 1

Battlefield 2

Battlefield n = 3 Let N denote the set containing all nodes of G m,n (including the source and destination nodes). G m,n has E = (m+1) [4+(n-2)(m+2)]/2 = O(nm2 ) (directed) edges that are arranged into n layers. Each edge represents an allocation of a certain number of troops toward a certain battlefield: the edge from node (i, j 1 ) to node (i + 1, j 2 ) represents the allocation of player that puts (j 2 -j 1 ) troops to battlefield i+1, for any i ∈ {0, . . . , n-1}; for instance, in Figure 1, the edge from (1, 0) to (2, 3) represents allocating 3 troops to Battlefield 2. We denotes E the set containing all the edges. Hereinafter, referring to the layered graph, we simplify the notations and use the term "paths" to indicate the paths starting from s and ending at d if there is no other explicit explanation. We define the set P ⊂ {0, 1} E containing all such paths and

P := |P| = |S| = n+m-1 n-1 = O(2 min{n-1,m} ). Given a strategy p ∈ S ⊂ [0, m] n ,
we slightly abuse the notation and re-use p = (p e ) e∈E to denote the E-dimension 0-1vector that represents the path equivalent to this strategy. Particularly, ∀e ∈ E, p e = 1 if and only if edge e belongs to path p and p e = 0 otherwise.

Finally, for the sake of completeness, we write down formally the PPP that is equivalent to the CB(m, n) model. At each stage t, the allocations of the learner and the adversaries to the battlefields determine a scalar loss t e ∈ [0, 1] (following the rule of the CB game) embedded on each edge e ∈ E of the graph G m,n . The learner has to choose a path p t ∈ P ⊂ {0, 1} E in G m,n . The learner then suffers a loss L(p t ) = t p t = e∈p t t e which equals the sum of losses from all edges belonging to the chosen path p t . At the end of stage t, the learner only observes the scalar loss L(p t ) of her chosen path but she does not know the loss of each edge. Henceforth, we focus our analysis on this model and we refer to it as PATHCB(m, n) to distinguish with CB(m, n).

IV. EFFICIENT ALGORITHM FOR PATH PLANNING PROBLEMS

In this section, we revisit a standard dynamic programming technique, called weight pushing. This technique is the basic for the efficient implementation of COMBAND algorithm in PPPs. The first idea of weight pushing technique could be tracked back to [START_REF] Örgy | The on-line shortest path problem under partial monitoring[END_REF] and [START_REF] Takimoto | Path kernels and multiplicative updates[END_REF] although it was only applied to efficiently sample a path in PPPs according to updating-rules based on the weights of edges. Recently, [START_REF] Sakaue | Efficient bandit combinatorial optimization algorithm with zero-suppressed binary decision diagrams[END_REF] proposed an application of weight pushing to compute the co-occurrence matrix C t in polynomial time in E; particularly for COMBAND in PPPs with the Zero-suppressed Binary Decision Diagrams. This computation requires 5 subalgorithms that involves heavy notations and unneccessary complexity for our setting. We restate the technique with the notations and parameters of PATHCB(m, n) and propose a more computationally efficient version of COMBAND.

A. Paths and Edges' Weights

In PPPs, we call the action weights w t (p) involved in COMBAND as the path weights and recall that w t+1 (p) := w t (p)e -η( ˆ t ) p . At stage t, for each edge e ∈ E, we define the edge weight w t e such that w 1 e := 1, ∀e (by convention) and w t+1 e := w t e • e -η( ˆ t e ) . It is trivial to deduce that w t (p) = e∈p w t e , ∀p ∈ P, t ∈ [T ], i.e., the weight of a path is the product of weights of all edges belong to it. The basic idea of weight pushing is to keep track of the paths weights (there is an exponential number of them) via the edges weights (only a polynomial number of them) by exploiting the structure of the graph. Now, let us denote by P (u,v) the set of all paths starting from node u and ending at node v. Then, for each pair of nodes (u, v) ∈ N × N , at stage t, we define H t (u, v) := p∈P (u,v) e∈p w t e . Intuitively, H t (u, v) is the sum of weights of all paths from node u to node v. Importantly, by conventionally setting H t (u, u) := 1, ∀u ∈ N and H t (u, v) = 0 if P (u,v) = ∅, we can compute all the quantities H t (u, v) in O(E) time via the following procedure (see also [START_REF] Örgy | The on-line shortest path problem under partial monitoring[END_REF]): we first re-label the nodes set by N = {s = u 0 , u 1 , . . . , d = u N } such that if there exists an edge connecting u i to u j then i < j. Then, for any v ∈ N , recursively for u ∈ {v -1, v -2, . . . , s := 0}, we can compute H t (u, v).

B. Sampling by Edges' Weights

Inspired by Theorem 3 in [START_REF] Örgy | The on-line shortest path problem under partial monitoring[END_REF], we can design an algorithm, denoted WP Algorithm (WP stands for weight pushing), that takes w t (e), e ∈ E as inputs and outputs a path in P. More importantly, the probability that a path p is an output of the WP Algorithm at stage t is exactly ν t (p)-the exploitation distribution defined in COMBAND. We rewrite this algorithm under our notation as Algorithm 2. In Algorithm 2, we denote by e [u,v] the edge connecting from node u to node v and by C(u) := {u > u : e [u,u ] ∈ E} the set of all direct children of u. Add u k+1 to the set Q.

Output: p t ∈ P going through all nodes in P.

C. Co-occurrence Matrix Computation

We now turn our focus to the matrix C t := Ep∼d t [pp ] needed to be computed at each stage t in the COMBAND(µ) algorithm. A direct computation of this matrix involves a sum of P terms, that leads to the inefficiency of COMBAND(µ). We first consider the following assumption on µ:

Assumption 1: There exists a set of edges weights we > 0, e ∈ E such that for each path p * ∈ P, we have µ(p * ) = e∈p * we / p∈P ( e∈p we ).

Intuitively, if µ satisfies Assumption 1, there exists a set of edges weights such that each path weight (according to µ) equals to the multiplication of the weights of the corresponding edges. Note that the uniform distribution on P (used by most of works in the literature) satisfies Assumption 1. Now, we observe that each entry C t e1,e2 equals to the probability that a chosen path p t ∼ d t contains both edges e 1 and e 2 (hence the name co-occurrence matrix). Formally, we have C t e1,e2 = p∈P d t (p)p e1 p e2 = {p:e1,e2∈p} d t (p). Now, we define M (ν t ) := E p∼ν t (p) [pp ] and M (µ) = E p∼µ(p) [pp ]-the co-occurrence matrices corresponding to distribution ν t and µ, respectively. From the definition of d t (p) in COMBAND(µ), we can rewrite

C t = (1 -γ)M (ν t ) + γM (µ). (2)
Therefore, to efficiently compute C t , we need to efficiently compute M (ν t ) and M (µ). We do this by designing an algorithm, called Algorithm 3, based on the quantities H t (u, v) computed in the previous section. Algorithm 3 runs in O(E 2 ) time. M (ν t ) can always be computed by Algorithm 3 with input w t e , e ∈ E. On the other hand, if µ satisfies Assumption 1, M (µ) can also be computed by Algorithm 3.

Note that, we keep a generic notation in this algorithm: the input we , e ∈ E refers to any configuration of edges weights, not only those with the specific forms w t e under the exponential updating rule. The output M (µ w) is the cooccurrence matrix corresponding to the distribution µ w that draws a path p * with probability .

µ w(p * ) = e∈p * we / p∈P ( e∈p we ). (3
In Algorithm 3, we also drop the superscript t in the notation of H(u, v); these quantities can be efficiently computed (with inputs we ) similar to H t (u, v) (with inputs w t e ). The main intuition of Algorithm 3 is that if a path p contains an edge e 1 = e [u1,v1] , then p also has to contain a path from node s to node u 1 and a path from node v 1 to node d. Similarly, if a path p simultaneously contains the edges e 1 = e [u1,v1] and e 2 = e [u2,v2] , then p also contains a path from node s to node u 1 , a path from node v 1 to node u 2 and a path from node v 2 to node d.

D. EDGE -An Computationally Efficient Algorithm

We now combine the techniques presented in the previous sections into a modified variant of COMBAND. This novel algorithm, denoted EDGE, works on edges instead of paths. We also parameterize EDGE(µ) with each corresponding exploration distribution µ. Its pseudo code is given in Algorithm 4. We conclude this section with the following proposition. Proposition 4.1: With the same choices of γ and η, the expected regret of EDGE(µ) is equal to that of COMBAND(µ) in PPPs; thus, EDGE has the same regret bound as indicated in Theorem 2.1. Given a distribution µ on P that satisfies Assumption 1, EDGE(µ) runs in O(n 2 m4 T ); this is in contrast with COMBAND(µ) that runs in O(exp(n)T ).

V. OPTIMIZING THE EXPLORATION DISTRIBUTION AND NUMERICAL EVALUATION

In this section, we investigate the exploration distribution µ that is used in both COMBAND(µ) and EDGE(µ). Recall the notation λ * [M ] for the smallest non-zero eigenvalue of a matrix M . In Theorem 2.1, the regret bound is of order O(λ * [M (µ)] -1/2 ); therefore, to minimize this bound, we need to search for µ that maximizes λ * [M (µ)]. In several CBAND problems (see [START_REF] Lugosi | Combinatorial bandits[END_REF]), the uniform distribution on the action set, denoted µ uni , was proven to yield an optimal choice to use in COMBAND. However, it is not the case for general PPPs and particularly for PATHCB(m, n): the eigenvalue λ * [M (µ uni )] may be of order Ω(P -1 ) which yields a regret upper-bound that is exponentially large in terms of the number of edges (an example can be found in [START_REF] Lugosi | Combinatorial bandits[END_REF]). Nevertheless, in all previous works that apply the COMBAND algorithm to PPPs, e.g. [START_REF] Örgy | The on-line shortest path problem under partial monitoring[END_REF] and [START_REF] Sakaue | Efficient bandit combinatorial optimization algorithm with zero-suppressed binary decision diagrams[END_REF], µ uni is used. Moreover, since it requires that γ ≤ 1, the bound given in Theorem 2.1 can only be obtained if

T ≥ [n log(P )] / (λ * [M (µ)]) 2 E n + 2 λ * [M (µ)]
(parameters tuned by [START_REF] Lugosi | Combinatorial bandits[END_REF]). If λ * [M (µ)] is too small, COMBAND(µ) and EDGE(µ) can only work with extremely large time horizon T , which is impractical. For these reasons, the choice of exploration distribution to use in these algorithms is crucial.

Formally, let us label the paths in P by p 1 , p 2 , . . . , p P , we consider an eigenvalue-optimization problem as follows (its search space is P -dimensional):

maximize λ * P i=1 x i • p i p i (4)
subject to x ∈ [0, 1] P , P i=1

x i = 1. (5)
It is suggested in [START_REF] Lugosi | Combinatorial bandits[END_REF] that the problem (4)-( 5) can be solved by casting it into a semi-definite programming problem (SDP). An explicit formulation of this SDP can be found in Appendix VII-A. In principle, this SDP can be solved exactly to find a distribution µ that maximizes λ * [M (µ)]. However, in practice, this SDP formulation still cannot be solved efficiently due to the fact that the feasible set still has dimension P and that it contains a constraint relating to a summation of P terms. In our simulation, standard SDP solvers 4 take a long running time to solve this SDP problem even with small instances and they easily run into computationally memory issues with moderate instances.

A. Derivative-free Optimization and Change of Search Space

The challenge is to find a fast method that provides an exploration distribution µ to be used in EDGE(µ) that guarantees a sufficiently good regret-bound. Moreover, it is desired to be able to efficiently sample a path from µ (line 6 in Algorithm 4) and to efficiently compute the matrix M (µ) in order to compute C t (line 8 in Algorithm 4). To do this, we reformulate the problem (4)- [START_REF] Lugosi | Combinatorial bandits[END_REF] to reduce the dimension of the search space. We consider the following problem whose search space is E-dimensional:

max w∈[0,∞) E λ * (M (µ w)). (6)
Here, we recall the notation µ w-the distribution on the paths set (defined in (3) for each w ∈ [0, ∞) E ) such that each path weight is the multiplication of the corresponding edges weights. Therefore, for each feasible solution of ( 6), say w * , we can construct a corresponding feasible solution µ w * of ( 4)-( 5); moreover, the objective function of ( 6) at w * equals to that of ( 4)-( 5) at µ w * . The construction of µ w * is in O(P ) time, but we do not need to explicitly do so in order to run EDGE algorithm with µ w * . Instead, since µ w * is guaranteed to satisfy Assumption 1, we can use the WP Algorithm to sample efficiently a path from µ w * and use Algorithm 3 to compute efficiently M (µ w * ). Therefore, we can solve ( 6) to (implicitly) find an exploration distribution and use it efficiently in EDGE. Although [START_REF] Chia | Colonel blotto in the phishing war[END_REF] reduces significantly the dimension of the search space comparing to (4)-( 5), this formulation loses the structure that allows us to apply standard convex optimization algorithms. 5 Therefore, in this work, we use derivativefree algorithms to heuristically solve [START_REF] Chia | Colonel blotto in the phishing war[END_REF]. Despite the fact that the solution found by this method may not be optimal, we can still guarantee that this solution is at least as good as the uniform distribution that is often used in the stateof-the-art algorithms (we initialize our algorithm with µ uni ). Moreover, although the search space in (6) may not cover the whole search space in (4)-( 5), the solution found in [START_REF] Chia | Colonel blotto in the phishing war[END_REF] (might be corresponding to a sub-optimal for (4)-( 5)) is guaranteed to be efficiently embedded with EDGE; on the other hand, even if we found an optimal solution of ( 4)-( 5), it does not guarantee to be efficiently used in EDGE. A diagram explaining the intuition of our method to solve (6) can be found in Figure 2. We can use any derivativefree optimization solver that goes with specific strategies of sampling new points and justifying the current-best solution.

We denote µ free the distribution corresponding to the solution of (6) found by our derivative-free method 6 and note that λ * (M (µ free )) ≥ λ * (M (µ uni )). Finally, as a corollary of Theorem 2. and runs in O(n 2 m 4 T ) time. 5 The function giving the smallest non-zero eigenvalue of a matrix M (µw) from an input w is not known to be convex or concave. 6 Take we = 1, ∀e ∈ E (corresponding to µ uni ) as the initialization point.

B. Numerical Evaluation

We conduct several experiments to evaluate the performance of EDGE and measure the effect of optimizing the exploration distribution. 7 In these experiments, without loss of generality, a learner, having m troops, plays a repeated CB game on n battlefields with a single adversary who has m A troops. We define a special adversary, called the extreme-strong adversary: an adversary having m A = (n-1)(m+1)+(m-1) troops, she "blocks" n -1 battlefields (each has a value equal to ε/(n-1)) by allocating m+1 troops to them and allocating m-1 troops to a certain battlefield i with value b i = 1-ε (unknown to the learner). In this case, the losses on all paths are always 1 except for the single path representing that the learner allocates all m troops to battlefield i; this path yields the loss ε. We choose this adversary to follow an example in [START_REF] Lugosi | Combinatorial bandits[END_REF] illustrating why µ uni fails to guarantee a good regret bound in PPPs. The algorithms need to "explore" the low-loss path as soon as possible to reduce the regret.

We use the ZOOPT solver8 (see [START_REF] Liu | Zoopt/zoojl: Toolbox for derivative-free optimization[END_REF]) embedded with sRACOS algorithm ( [START_REF] Hu | Sequential classification-based optimization for direct policy search[END_REF]) as the derivative-free optimization solver to heuristically solve (6) (its output is µ free ). Our experiments run on an Intel Core i5-7300U CPU@ 2.60GHz and 8.00GB RAM. Each instance is run 5 times and the average results are reported.

In the first experiment, we compare the running time between COMBAND and EDGE and the results confirm that COMBAND takes exponential time while EDGE runs in polynomial time in terms of m and n; these results are reported in Figure 3 (the numbers of edges and paths in the corresponding G m,n are also reported for the sake of comparison). Next, we compare the performances of EDGE when it uses µ uni and µ free as the exploration distribution. Figure 4(a) (yaxes is drawn with log-scale) illustrates the trade-off between the time spending to find µ free and the improvement in the eigenvalues and the upper-bounds predicted by Theorem 2.1. Note that the smaller the ratios bound free /bound uni and λ uni /λ free are, the more improvement that EDGE(µ free ) provides comparing to EDGE(µ uni ). Finally, we compare the performance of EDGE(µ uni ) and EDGE(µ free ) by their actual regrets (see Figure 4(b)). Note that to efficiently compute the best hindsight loss (it is non-trivial), we apply a dynamic programming algorithm extracted from [START_REF] Vu | Efficient computation of approximate equilibria in discrete Colonel Blotto games[END_REF] that finds the best response against a set of allocations of the adversary. We observe that the actual regret of EDGE(µ free ) is better than EDGE(µ uni ); as m increases, the difference between these regrets also increases. For example, for instance m = 3, n = 6 and T = 10 5 , the ratio (Regret uni -Regret free )/Regret uni equals 28% while this ratio of instance m = 5, n = 10, T = 10 5 is 38%. Note that EDGE(µ free ) can run with larger instances (in m, n) but we choose not to report here since EDGE(µ uni ) is unavailable in these instances (it requires extremely large T ). Besides the extreme-strong adversary, for this experiment, we also consider several other adversary's strategies (see Appendix VII-B for more details) and we notice that the results from these cases are similar to that of the extreme-strong adversary case.

VI. CONCLUSION

In this work, we present the EDGE algorithm for learning in the Colonel Blotto game that is modeled as a path planning problem. EDGE improves the regret guarantees compared to benchmark algorithm thanks to our proposed method finding an improved exploration distribution. Moreover, our algorithm is always efficiently implementable. This work not only extends the scope of application of the Colonel Blotto game in practice (even for large instances) but also can be applied to more general path planning problems.

VII. APPENDIX A. SDP Formulation of the Exploration-Distribution Optimization Problem

To formulate the problem (4)-( 5) into a SDP, we first observe that for any distribution µ such that the paths set P is spanned by the support of µ, the matrix M (µ) always has a fixed number of zero eigenvalues (denoted K) and this number can be easily computed. 9 Therefore, the problem of maximizing λ * [M (µ)] is equivalent to maximizing the sum of K + 1 smallest eigenvalues of M (µ) which is formulated as: minimize (K + 1)s + Tr(Z) [START_REF] Combes | Combinatorial bandits revisited[END_REF] subject to Z 0 (8)

Z + P i=1 x i • p i p i + sI E 0. (9)
Here, x ∈ [0, 1] P and r, s ∈ R, Z ∈ M E×E are the variables. I E is the identity matrix and the notation X 0 indicates that the matrix X is positive semi-definite. This is trivially deduced from the Linear Matrix Inequalities representation of the sum of K + 1 largest eigenvalues of the matrix (see e.g., [START_REF] Nesterov | Interior-pointpolynomial methods in convexprogramming[END_REF], [START_REF] Vandenberghe | Semidefinite programming[END_REF]).

B. Additional Numerical Experiments

Besides the extreme-strong adversary, we also consider two other adversary's strategies: the uniform-adversary (resp. the battlefields-wise adversary) who at each time t repeatedly draws a battlefield by uniform distribution (resp. draws battlefield i with probability b i / j∈[n] b j ) then allocates one troop to that battlefield until he runs out of troops (m A = m). For this experiment, the battlefields' values b i are generated uniformly from [0, 8]. For each instance with different parameters m, n and adversary's strategies, we run each algorithm EDGECB(µ uni ) and EDGECB(µ box ) 5 times and the average results of their actual regret are reported in Figure 5.

  Definition 3.1 (Layered Graph): The graph G m,n is a DAG that contains: (i) N := 2+(m+1)(n-1) nodes that are arranged into n+1 layers. Layer 0 has only one node s := (0, 0), called the source node and Layer n contains one node d := (n, m), called the destination node. Each Layer i ∈ [n -1] contains m + 1 nodes whose labels are ordered from left to right by (i, 0), (i, 1), . . . , (i, m). (ii) There are directed edges from the source node s to all nodes in Layer 1 and from all nodes in Layer n -1 to the destination node d. For any Layer

Fig. 1 .

 1 Fig. 1. The graph G 3,3 corresponding to the game with m = n = 3. Each path from s to d represents a strategy in S; e.g., the bold-blue path represents the strategy (0, 0, 3) while the dash-red path represents the strategy (2, 0, 1).

Algorithm 2 :

 2 WP Algorithm: Sampling by edges' weights. Input: G m,n , t ∈ [T ], w t e , ∀e ∈ E. 1 Initialize Q := {0}, u 0 = s and k = 0. 2 for k ≤ n do 3 Sample a node u k+1 from C(u k ) with probability w t e [u k ,u k+1 ] H t (u k+1 , d) H t (u k , d).

4

 4

Algorithm 4 :

 4 EDGE(µ) Algorithm for PATHCB. Input: m, n, T ∈ N,γ ∈ [0, 1], η > 0, distribution µ. 1 ∀e ∈ E, w 1 e := 1. 2 for t = 1, 2, . . . , T do 3 Adversaries play (unobserved by the learner).

4

  Sample β from Bernoulli distribution B(γ).

Fig. 2 .

 2 Fig. 2. Diagram illustrating the derivative-free optimization.

  1 and Proposition 4.1, we have: Proposition 5.1: In PATHCB(m, n), with appropriate parameters γ and η, EDGE(µ free ) guarantees R T ≤ O n 2T λ * [M (µ free )]

mFig. 3 .

 3 Fig. 3. COMBAND(µ free ) vs EDGE(µ free ); n = 2m, T = 40000 fixed.

  n = 2m, T = 40000 fixed. T Regret (b) The actual regrets.

Fig. 4 .

 4 Fig. 4. Performances evaluation of EDGE(µ uni ) and EDGE(µ free ).

Fig. 5 .

 5 Fig. 5. The actual regrets of EDGE(µ uni ) and EDGE(µ free ).

  Suffer and observe the loss L(p t ) = t p t ≤ 1.Compute C t := E p∼d t [pp ] ∈ M E×E .

			w 1 (p) := 1.
	2 for t = 1, 2, . . . , T do
	3	Adversaries choose the loss vector t (unobserved
		by the learner).
	4 5	∀p ∈ S, ν t (p) := w t (p)/ q∈S [w t (q)]. Sample and play p t according to
		d t (p) = (1-γ)ν t (p)+γµ(p).
	8	Compute the estimated loss
		ˆ t	:= L(p t ) C -1 t p t = t (p t ) C -1 t p t .

6 7 9 ∀p ∈ S, w t+1 (p) := w t (p)e -η( ˆ t ) p .

)

  Algorithm 3: Co-occurrence matrix computation.Input: G m,n , we , ∀e ∈ E. 1 Compute H(u, v) := p∈P (u,v) e∈p we , ∀u, v ∈ N .2 for e 1 = e [u1,v1] ∈ E do

	3	M (µ w) e1,e1 =	H(s,u1) we 1 H(v1,d) H(s,d)	.
	4	for e 2 = e [u2,v2] ∈ E, e 2 > e 1 do
	5	M (µ w) e1,e2 =	H(s,u1) we 1 H(v1,u2) we 2 H(v2,d) H(s,d)

A few works studied dynamic settings of the game, but only limited to two or three stages and they focus on asynchronous allocations ([9],[START_REF] Powell | Sequential, nonzero-sum "blotto": Allocating defensive resources prior to attack[END_REF]).

The constraint n i=1 p i ≤ m is sometimes considered in the literature. However, since unallocated troops do not contribute to the payoff, the learner always has incentives to use all her troops.

This term is inspired by a graph proposed by[START_REF] Behnezhad | Faster and simpler algorithm for optimal strategies of Blotto game[END_REF] that looks similar to Gm,n; however, it is used for a completely different purpose and it also contains more edges and paths than Gm,n (that are not useful in this work).

for e 1 , e 2 ∈ E, e 2 < e 1 do M (µ w) e1,e2 = M (µ w) e2,e1 . Output: The matrix M (µ w).

CVXOPT solver, available at https://cvxopt.org/ and Mosek solver https://www.mosek.com/, both use primal-dual interior points methods.

Our code is given at https://github.com/dongquan11/BanditColonelBlotto.

Available at https://zoopt.readthedocs.io/en/latest/. We run it in 100E iterations; this stopping criterion is recommended by[START_REF] Hu | Sequential classification-based optimization for direct policy search[END_REF]; moreover, this criterion is enough to solve (6) optimally in our experiments with small instances (m, n ≤ 3).

Rank(M (µ)) < E is the size of the largest linear independent subset of P, which is fixed and only depends on the structure of the layered graph Gm,n. Rank-nullity theorem implies that K is also fixed. We can compute K by computing rank of any particular matrix, say M (µ uni ).


Agnieszka Peszek

Apoloniusz Tyszka

Hilbert's 10th Problem for solutions in a subring of Q

Keywords: 2010 Mathematics Subject Classification: 03D25, 11U05 Craig Smoryński's theorem, Diophantine

come

Introduction and basic lemmas

Yuri Matiyasevich's theorem states that the set of all Diophantine equations which have a solution in non-negative integers is not recursive, see [START_REF] Yu | Hilbert's tenth problem[END_REF]. Martin Davis' theorem states that the set of all Diophantine equations which have at most finitely many solutions in positive integers is not recursive, see [START_REF] Davis | On the number of solutions of Diophantine equations[END_REF]. Craig Smoryński's theorem states that the set of all Diophantine equations which have at most finitely many solutions in non-negative integers is not recursively enumerable, see [4, p. 104, Corollary 1] and [5, p. 240].

Let P denote the set of prime numbers, and let

P = {p 1 , q 1 , r 1 , p 2 , q 2 , r 2 , p 3 , q 3 , r 3 , . . .}, where p 1 < q 1 < r 1 < p 2 < q 2 < r 2 < p 3 < q 3 < r 3 < . . . Lemma 1. For a non-negative integer x, let ∞ i=1 p α i i • q β i i • r γ i i
be the prime decomposition of x + 1. For every positive integer n, the mapping which sends x ∈ N to

(-1) α 1 • β 1 γ 1 + 1 , . . . , (-1) α n • β n γ n + 1 ∈ Q n is a computable surjection from N onto Q n .
Let s n : N → Q n denote the surjection defined in Lemma 1.

Lemma 2. For every infinite set R ⊆ Q, a Diophantine equation D(x 1 , . . . , x n ) = 0 has no solutions in x 1 , . . . , x n ∈ R if and only if the equation D(x 1 , . . . , x n ) + 0 • x n+1 = 0 has at most finitely many solutions in x 1 , . . . , x n+1 ∈ R.

Let R be a subring of Q with or without 1. By H 10 (R), we denote the problem of whether there exists an algorithm which for any given Diophantine equation with integer coefficients, can decide whether or not the equation has a solution in R.

A positive solution to H 10 (R) implies that the set of all

Diophantine equations with a finite number of solutions in R is recursively enumerable

In the next three lemmas we assume that {0} R ⊆ Q and r • Z ⊆ R for every r ∈ R. Every non-zero subring R of Q (with or without 1) satisfies these conditions.

Lemma 3. There exists a non-zero integer m ∈ R.

Proof. There exist m, n

∈ Z \ {0} such that m n ∈ R. Hence, m = m n • n ∈ (Z \ {0}) ∩ R. Lemma 4. Let m ∈ (Z \ {0}) ∩ R. We claim that for every b ∈ R, b 0 if and only if the equation y • b -m 2 - 4 i=1 y 2 i = 0 is solvable in y, y 1 , y 2 , y 3 , y 4 ∈ R.
Proof. If b = 0, then for every y, y 1 , y 2 , y 3 ,

y 4 ∈ R, y • b -m 2 -y 2 1 -y 2 2 -y 2 3 -y 2 4 = -m 2 -y 2 1 -y 2 2 -y 2 3 -y 2 4 -m 2 < 0 If b 0, then b = p q
, where p ∈ N \ {0} and q ∈ Z \ {0}. In this case, we define y as m 2 • q and observe that

m 2 • q = (m • q) • m ∈ R as m • q ∈ R and m ∈ Z. Hence, y • b = (m 2 • q) • p q = m 2 • p ∈ m 2 • (N \ {0})
By Lagrange's four-square theorem, there exist

t 1 , t 2 , t 3 , t 4 ∈ N such that y • b -m 2 m 2 = t 2 1 + t 2 2 + t 2 3 + t 2 4 Therefore, y • b -m 2 -(m • t 1 ) 2 -(m • t 2 ) 2 -(m • t 3 ) 2 -(m • t 4 ) 2 = 0, where m • t 1 , m • t 2 , m • t 3 , m • t 4 ∈ R.
Lemma 5. We can uniquely express every rational number r as r / r, where r ∈ Z, r ∈ N \ {0}, and the integers r and r are relatively prime. If r ∈ R, then r ∈ R.

Proof. For every r ∈ R, r = r • r ∈ r • Z ⊆ R.

Lemma 6. Let R be a non-zero subring of Q with or without 1. We claim that for every T 0 , . . . , T k ∈ R n and for every x 1 , . . . , x n ∈ R, the following product

(r 1 , . . . , r n ) ∈ {T 0 , . . . , T k } n i=1 x i • r i -r i 2 (1)
differs from 0 if and only if (x 1 , . . . , x n ) {T 0 , . . . , T k }. Product (1) belongs to R.

Proof. The last claim follows from Lemma 5.

Lemma 7. Let R be a non-zero subring of Q (with or without 1) such that there exists an algorithm which for every (a, b) ∈ Z × (Z \ {0}) decides whether or not a b ∈ R. Let ρ n : Q n → R n denote the function which equals the identity on R n and equals (0, . . . , 0) outside R n . We claim that for every positive integer n the function ρ n • s n : N → R n is surjective and computable.

Theorem 1. Let R be a non-zero subring of Q (with or without 1) such that Hilbert's 10th Problem for solutions in R has a positive solution. We claim that the set of all Diophantine equations with a finite number of solutions in R is recursively enumerable.

Proof. By Lemma 3, there exists a non-zero integer m ∈ R. For every (a, b) ∈ Z × (Z \ {0}), the solvability in R of the equation b • xa = 0 is decidable. Hence, for every (a, b) ∈ Z × (Z \ {0}) we can decide whether or not a b ∈ R. By Lemmas 4 and 6, the answer to the question in Flowchart 1 is positive if and only if the equation D(x 1 , . . . , x n ) = 0 is solvable in R n \ {θ(0), . . . , θ(k)}. Hence, by Lemma 7, the algorithm in Flowchart 1 halts if and only if the equation D(x 1 , . . . , x n ) = 0 has at most finitely many solutions in R.

3 If the set of all Diophantine equations with a finite number of solutions in R is recursively enumerable, then H 10 (R) has a positive solution

Starting from this moment up to the end of Theorem 2, we assume that R is an infinite subset of Q and there exist computable functions τ 1 , τ 2 : N → Z which satisfy

(∀n ∈ N τ 2 (n) 0) ∧ τ 1 (n) τ 2 (n) : n ∈ N = R
In other words, the function N n τ -→ τ 1 (n) τ 2 (n) ∈ R is surjective and computable. Hence, the function (τ, . . . , τ) : N n → R n is surjective and computable.

Lemma 8. Let σ n : Q n → N n denote the function which equals the identity on N n and equals (0, . . . , 0) outside N n . We claim that for every positive integer n the function (τ, . . . , τ) • σ n • s n : N → R n is surjective and computable.

Theorem 2. If the set of all Diophantine equations which have at most finitely many solutions in R is recursively enumerable, then there exists an algorithm which decides whether or not a given Diophantine equation has a solution in R.

Proof. Suppose that {S i = 0} ∞ i=0 is a computable sequence of all Diophantine equations which have at most finitely many solutions in R. By Lemma 2, the execution of Flowchart 2 decides whether or not a Diophantine equation D(x 1 , . . . , x n ) = 0 has a solution in R. The flowchart algorithm uses a computable surjection ϕ : N → R n (which exists by Lemma 8).

Harvey Friedman conjectures that the set of all polynomials of several variables with integer coefficients that have a rational solution is not recursive, see [START_REF] Friedman | Complexity of statements[END_REF]. Harvey Friedman conjectures that the set of all polynomials of several variables with integer coefficients that have only finitely many rational solutions is not recursively enumerable, see [START_REF] Friedman | Complexity of statements[END_REF]. These conjectures are equivalent by Theorems 1 and 2 taking R = Q.

Acknowledgement. Agnieszka Peszek prepared two flowcharts in TikZ. Apoloniusz Tyszka wrote the article. The article was presented at the Jubilee Congress for the 100th anniversary of the Polish Mathematical Society held in Kraków, Poland, September 3-7, 2019. An older and longer version of this article appeared in Scientific Annals of Computer Science 29 (2019), no. 1, 101-111, http://www.info.uaic.ro/en/sacs_articles/ on-the-relationship-between-matiyasevichs-and-smorynskis-theorems/. The article's DOI 10.7561/SACS.2019.1.101 does not link to the article.

is solvable in x 1 , . . . , x n , y, y 1 , y 2 , y 3 , y 4 ∈ R ?

Print "The equation D x 1 , . . . , x n = 0 has at most finitely many solutions in R"

Theorem 1 remains true when R = {0}.

The flowchart algorithm depends on m ∈ (Z \ {0}) ∩ R. For a constructive proof of Theorem 1, we must compute an element of (Z \ {0}) ∩ R. By Lemma 7, the function ρ n • s n : N → R n is computable and surjective. We compute the smallest i ∈ N such that (ρ n • s n )(i) starts with a non-zero integer. This integer belongs to (Z \ {0}) ∩ R.

Start

Input a Diophantine equation D(x 1 , . . . , x n ) = 0

The flowchart algorithm always terminates because there exists a non-negative integer i such that (D(x 1 , . . . ,

Indeed, for every Diophantine equation D(x 1 , . . . x n ) = 0, the flowchart algorithm finds a solution in R, or finds the equation D(x 1 , . . . , x n ) + 0 • x n+1 = 0 on the infinite list [S 0 , S 1 , S 2 , . . .] if the equation D(x 1 , . . . , x n ) = 0 is not solvable in R.

Corollary. Theorem 2 for R = N implies that Craig Smoryński's theorem follows from Yuri Matiyasevich's theorem.


Projection of the CoM relative to the support polygon [START_REF] Nunez | Étude de la commande des mouvements dynamiques d'un robot humanoïde[END_REF] Projection of the ZMP relative to the support polygon [START_REF] Nunez | Étude de la commande des mouvements dynamiques d'un robot humanoïde[END_REF] CoM is the mean location of all masses of the robot links

OG = m i OG i
Static stability criterion ZMP is the point where the vertical reaction force intersects the ground ZMP(t) = f (q(t), q(t), q(t), f e (t))

Dynamic stability criterion

B-splines

Objective Find a trajectory : T = x(t), t ∈ [0, t f ] under a set of constraint :

           x(0) = x 0 ẋ(0) = ẋ0 x(t f ) = x f ẋ(t f ) = ẋf x(t i ) = x i

B-splines

Illustration example

Constraints : 3MLIPM [START_REF] Feng | Biped robot walking using three-mass linear inverted pendulum model[END_REF] Reduce the dynamic of the robot to the dynamic of a point mass. The three masses linear inverted pendulum model "3 Mass Linear Inverted Pendulum Model (3MLIPM)" [START_REF] Feng | Biped robot walking using three-mass linear inverted pendulum model[END_REF]

           x(0) = 4 x(1) = 8 x(2) = 6 ẋ(0) = 0 ẋ(2) = 3 B-splines MATLAB function : csape( [0,1,2], [4,8,6],[1,1],[0,3]) t 0 = 0, t i = 1, t f =

First contribution

First limitation of the 3MLIPM model : The dynamic stability is not guaranteed Proposed improvement : Optimization with respect to ZMP Principle : optimal value of mass m 1 and its position z 1 :

ẑ1 m1 = Arg Min   z 1 m 1   Max α(x zmp -x dzmp ) 2 + β(y zmp -y dzmp ) 2
This optimization aims to find the best fit between the desired and the computed ZMP.

Second contribution

Second limitation of the 3MLIPM model : Change of walking direction is not allowed Proposed improvement : Modification of the hip trajectory Principle : the hip trajectory is modified as follow :

Ω(t) = - R 2 cos( πt T ) t ∈ [0, T ]
with T : half step period and R : amplitude of rotation. The modification of the hip trajectory allows a change of walking direction.

First

  phases Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work The three masses linear inverted pendulum model Motion in sagittal plane Motion in frontal planeThe three masses linear inverted pendulum model "3 Mass Linear Inverted Pendulum Model (3MLIPM)"[START_REF] Feng | Biped robot walking using three-mass linear inverted pendulum model[END_REF] GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work The three masses linear inverted pendulum model Motion in sagittal plane Motion in frontal plane Motion in sagittal plane Dynamic of 3MLIPM in the sagittal planex i :Cartesian position of mass m i in x axis z i :Cartesian position of mass m i in z axis Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , linear inverted pendulum model Motion in sagittal plane Motion in frontal plane Motion in sagittal plane Dynamic of 3MLIPM in the sagittal plane 3 i=1 m i ẍi z i = 3 i=1 m i gx i x i :Cartesian position of mass m i in x axis z i :Cartesian position of mass m i in z axis Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , linear inverted pendulum model Motion in sagittal plane Motion in frontal plane Motion in sagittal plane Dynamic of 3MLIPM in the sagittal plane 3 i=1 m i ẍi z i = 3 i=1 m i gx i bẍ1 + d ẍ3 = ax1 + x3 x i :Cartesian position of mass m i in x axis z i :Cartesian position of mass m i in z axis Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , linear inverted pendulum model Motion in sagittal plane Motion in frontal plane Motion in sagittal plane Dynamic of 3MLIPM in the sagittal plane 3 i=1 m i ẍi z i = 3 i=1 m i gx i bẍ1 + d ẍ3 = ax1 + x3 Choose a trajectory for the swinging foot x i :Cartesian position of mass m i in x axis z i :Cartesian position of mass m i in z axis Motion in sagittal plane Dynamic of 3MLIPM in the sagittal plane 3 i=1 m i ẍi z i = 3 i=1 m i gx i bẍ1 + d ẍ3 = ax1 + x3 Choose a trajectory for the swinging foot Motion of the three masses x i :Cartesian position of mass m i in x axis z i :Cartesian position of mass m i in z axis Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , linear inverted pendulum model Motion in sagittal plane Motion in frontal plane Motion in frontal plane Dynamic of 3MLIPM in the frontal plane x i :Cartesian position of mass m i in x axis z i :Cartesian position of mass m i in z axis Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , linear inverted pendulum model Motion in sagittal plane Motion in frontal plane Motion in frontal plane Dynamic of 3MLIPM in the frontal plane 3 i=1 m i ÿi z i = 3 i=1 m i gy i x i :Cartesian position of mass m i in x axis z i :Cartesian position of mass m i in z axis Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , linear inverted pendulum model Motion in sagittal plane Motion in frontal plane Motion in frontal plane Dynamic of 3MLIPM in the frontal plane 3 i=1 m i ÿi z i = 3 i=1 m i gy i u ÿ1 -vy1 = w x i :Cartesian position of mass m i in x axis z i :Cartesian position of mass m i in z axis Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , linear inverted pendulum model Motion in sagittal plane Motion in frontal plane Motion in frontal plane Dynamic of 3MLIPM in the frontal plane 3 i=1 m i ÿi z i = 3 i=1 m i gy i u ÿ1 -vy1 = w 3D trajectories of hip and ankles x i :Cartesian position of mass m i in x axis z i :Cartesian position of mass m i in z axis Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , linear inverted pendulum model Motion in sagittal plane Motion in frontal plane Motion in frontal plane Dynamic of 3MLIPM in the frontal plane 3 i=1 m i ÿi z i = 3 i=1 m i gy i u ÿ1 -vy1 = w 3D trajectories of hip and ankles Inverse kinematics → Joints space trajectories x i :Cartesian position of mass m i in x axis z i :Cartesian position of mass m i in z axis

  Comparison of the original pattern generator with the improved one

	2011 Developed simulator First scenario : Straight walking HLR 2011 WORKSHOP Second scenario : Change of walking direction Video February, 14 th , 2011 Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work 1 Context and motivation Outline 2 SHERPA walking robot 3 Basic 3MLIPM pattern generator 4 Limitations and improvements 5 Simulation results 6 Conclusion and Future work Speaker: David GALDEANO (galdeano@lirmm.fr) HLR 2011 WORKSHOP Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work Developed simulator First scenario : Straight walking Second scenario : Change of walking direction Video Developed simulator Proposed scenarios : Scenario 1 : Straight walking Scenario 2 : Change of walking direction Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work Developed simulator First scenario : Straight walking Second scenario : Change of walking direction Video First scenario : Straight walking Stability analysis through ZMP Without optimization With optimization Optimization ⇒ Improvement of the stability margins Joints' positions Joints' velocities Change of walking direction Characteristics : Joints' trajectories are periodic Discontinuities in joints' velocities Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work Developed simulator First scenario : Straight walking Second scenario : Change of walking direction Video Second scenario : Change of walking direction Stability analysis through ZMP Without optimization With optimization f Instable dynamic walking Stable dynamic walking Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work Developed simulator First scenario : Straight walking Second scenario : Change of walking direction Video Second scenario : Change of walking direction Stability analysis through ZMP Without optimization With optimization f Instable dynamic walking Stable dynamic walking Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work Developed simulator First scenario : Straight walking Second scenario : Change of walking direction Video Video Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work Outline Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP Context and motivation SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work Conclusion Motivation : Design and implementation of a pattern generator for dynamically stable walking Deals with : Stability of dynamic walking 3D Movements Complex nonlinear dynamics Low CoM position (no torso) Proposed solution : A pattern generator based on a 3 masses simplified model Stability margin improvement using optimization Change of walking direction is allowed Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 SHERPA walking robot Basic 3MLIPM pattern generator Limitations and improvements Simulation results Conclusion and Future work Future work Future work can include... Real-time implementation of the proposed pattern generator on the biped robot SHERPA Development of a hybrid Position/Force controller to stabilize dynamic walking (in progress) Combine the hybrid Position/Force controller with the developed pattern generator Test the effectiveness of controller for walking on uneven ground HLR 2011 WORKSHOP Context and motivation Compare this approach to other pattern generators	22 23 29 30

Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP Second scenario : Change of walking direction Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP Optimization ⇒ Dynamic walking stability is guaranteed Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP

& & & & & & & a

Speaker: David GALDEANO (galdeano@lirmm.fr) February, 14 th , 2011 HLR 2011 WORKSHOP


Roxanne Cesarini

Nathan Francis

published or not. The documents may come     Copyright Settelments, economy and mobility in the Ecrins massif during the Middle Ages

In the Byaisse and Fournel valleys (Freissinières and L'Argentièrela-Bessée, Hautes-Alpes), archaeological research was initiated in the 1990s, in parallel with paleoenvironmental studies. Although important work has been conducted on the aristocracy in the upper Durance Valley and the mining sectors at high altitudes, data remain incomplete on the occupation of mountains in the Middle Ages. This is why the chronological limits of this thesis are between the 8th and 16th centuries.

This work, conducted in close collaboration with the Parc National des Écrins, aims to shed light on the socio-economic mechanisms of medieval populations in mountains. In this way, it questions the link between settlements, economic activities, their mobility and that of humans, herds and products in the Middle Ages.

This mountain context offers a plurality of sources that require an appropriate method :

Archaeological approach : is being developed to high-rise occupations to document the different forms of settlement and to draw their evolution. It is enriched by a series of interviews with the local population to learn more about land use and management. The archaeological excavation of hamlets and agropastoral structures is envisaged to document the mobility of the settlement and to observe the relationships between the upper and lower part of the valley. Surveys are currently being carried out to identify sites that would be interesting to excavate.

Experimental approach : to characterise the different structures the classical sedimentary approach will be coupled with a chemical analysis of soils. All this will be used to establish a functional typology which, enriched by other corpora, will encourage reflection on the way mountain pastures are occupied over a very long period of time and on a European scale.

Text-based approach : to identify economic activities, define resource management and document the mobility of people, herds and products, archival sources are used. All textual information is recorded in a relational database to be able to model networks and different forms of mobility. For the time being, the mobility of people and herds has been addressed through the study of Vaudoise heresies, summering, wintering and fairs.

Finally, this work will offer a synthesis on the evolution of the medieval landscape based on the archaeological and historical data collected, enriched by palaeoenvironmental and cartographic documentation covering the long period from the Middle Ages to the present day. Thesis field

  25th meeting of the EAA: Session #199: Rethinking the Interpretation of Vertical Past Land Use on Mountain Environments Settlements, economy and mobility in the Ecrins massif during the Middle Ages: first results of a doctoral research Roxanne CESARINI (PhD student, Aix Marseille Univ, CNRS, LA3M, Aix-en-Provence, France), in coll. with Nathan FRANCIS (indepent illustrator, Bruxelles, Belgium)


B Lasbouygues

J Schindler

S Engels

P Maurine
email: pmaurine@lirmm.fr

N Azémard
email: azemard@lirmm.fr

D Auvergne
email: auvergne@lirmm.fr

Continuous representation of the performance of a CMOS library

In a standard industrial approach the timing performance verification is obtained using a tabular method that necessitates a great amount of simulations. They must specify, for each drive in each logic family: the load, the input slope, the temperature and the supply voltage sensitivity, for each edge, of the transition time and propagation delay. Extending a logical effort like based model of timing performance of CMOS structures we show in this paper that it is possible to define a specific performance representation allowing a continuous representation of the performance sensitivity of a complete family. We describe the parameter calibration procedure and validate the proposed representation on a 0.13µm process by comparing the performance sensitivity deduced from this representation to sensitivity values obtained from electrical simulations performed with the full process model of the foundry.

Introduction

The complete characterization of the timing performance of a library involves a huge number of simulations. The performance of each gate on a path, for each loading and control condition, is obtained from an interpolation between a set of predefined values. These values are determined from electrical simulations performed for a limited number of design conditions, such as load, input transition time, supply voltage value and operating temperature [START_REF]Timing Library Format References[END_REF]. Characterizing each edge of the transition time and the propagation delay of each library cell, for typically five loading and input ramp conditions, involves 100 simulations. Then considering the process corners, with different supply voltage and temperature values imposes to simulate thousand of points to characterize a logic function designed with different drives. This huge number of simulations just allows to represent the design space with few loading and control conditions. Intermediate conditions must then be interpolated using a linear characteristic equation (Synopsys) :

f(τ IN ,C L )=Aτ IN +BC L +Cτ IN CL+D).
It is well recognized that the transition time and the propagation delay exhibit a nonlinear variation with respect to the control and loading conditions. This imposes variable simulation steps because interpolating in this range may induce significant errors. Usually the largest error occurs for the smallest values of the load and the input transition time. It is clear that the relative accuracy, obtained with a tabular method, is strongly dependent on the granularity of the table that is not necessarily constant but must cover a significant part of the design range. For that, indications for defining the granularity and the coverage of the design space must be available. In this paper we propose a continuous representation of the timing performance of a CMOS library. This representation defines the propagation delay time and output transition time sensitivities of the cells to the design space parameters, such as the load, the input transition time, the supply voltage and the temperature values. The performance model is presented in part 2. In part 3 we detail the calibration method to be used on a specific process. Application is given in part 4 to a 0.13µm STM process, before to conclude in part 5.

. Model

Gate switching delay

An accurate delay model must be input slope dependent and must distinguish between falling and rising signals. Considering the input-to-output coupling effect [START_REF] Jeppson | Modeling the influence of the transistor gain ratio and the input-to-output coupling capacitance on the CMOS inverter delay[END_REF], the input slope effect can be introduced in the propagation delay as:

) i ( t ) C C C 2 1 ( ) 1 i ( 2 v ) i ( t ) i ( t ) C C C 2 1 ( ) 1 i ( 2 v ) i ( t LHstep L M M NHL I TP LH HLstep L M M NLH I TN HL + + + - τ = + + + - τ = . (1)
τ INHL,LH is the duration time of the input signal, generated by the controlling gate, C M the coupling capacitance between the input and output nodes [START_REF] Meyer | Semiconductor Device Modeling for CAD[END_REF], that can be evaluated or directly calibrated from SPICE simulation. Indexes (i), (i-1) refers to the location of the cell in the array.

Inverter transition time.

The output transition time (defining the input transition time of the following cell) of a CMOS structure [START_REF] Mead | Introduction to VLSI systems[END_REF] can be obtained from the modeling of the charging (discharging) current that flows during the switching process of the structure and from the amount of charge (C L .V DD ) to be exchanged with the output node as:

PMax DD L outLH NMax DD L outHL I V C I V C ⋅ = τ ⋅ = τ . ( 2
)
C L is the output load and V DD the supply voltage value. In (2) the output voltage variation has been supposed linear and the driving element considered as a constant current generator delivering the maximum current available in the structure. To evaluate the maximum current available in the structure two controlling conditions must be considered, the fast and slow input control ranges.

In the fast input range the switching current exhibits a constant and maximum value:

( ) P TN, DD P N, P N, Fast MAX V V W K I - ⋅ ⋅ = (3)
obtained for deep submicron from the Sakurai's representation [START_REF] Sakurai | Alpha-power model, and its application to CMOS inverter delay and other formulas[END_REF] with α=1. Here K N,P is an equivalent conduction coefficient to be calibrated on the process. From (2,3) we obtain the expression of the transition time for a fast input control condition as:

IN L Fast outLH IN L Fast outHL C C R k ) k 1 ( C C ) k 1 ( ⋅ ⋅ + ⋅ τ = τ ⋅ + ⋅ τ = τ (4)
(4) represents an extension of the logical effort model [START_REF] Sutherland | Logical Effort: Designing Fast CMOS Circuits[END_REF] for non symmetrical inverters. τ is a unit delay characterizing the process, k=W P /W N the inverter configuration ratio and R the speed ratio between electron and holes. In the slow input range the input and output voltages vary simultaneously. The resulting short circuit between N and P transistors decreases the current value available at the output. Considering the symmetry property of the current wave shape, this new value of the maximum current available can easily be obtained as:

LH , HL IN L 2 DD P N, P N, Slow MAX C V W K I ⋅ ⋅ ⋅ = . ( 5
)
Developing ( 2) with ( 5) and ( 4) gives for a falling output edge:

( )

INLH Fast outHL DD TN DD Slow outHL V V V τ ⋅ τ ⋅ - = τ (6)
with an equivalent expression for a rising edge. As shown in ( 4), for a well-defined inverter structure, in the Fast input range, the output transition time only depends on the ratio load/ inverter input capacitance.

In the Slow range, the output transition time exhibits an extra input duration time dependency that reflects the complete inter-stage interaction in an array of inverters or gates. This is illustrated in Fig. 1 where we represent the transition time for output falling and rising edges, for different values of the configuration ratio, versus the input transition time value τ IN . As shown the values of the transition time, calculated from the maximum value of ( 4) and [START_REF] Sutherland | Logical Effort: Designing Fast CMOS Circuits[END_REF], are in good agreement with the simulated one.

2.3

Extension to gates. It is obtained [START_REF] Sutherland | Logical Effort: Designing Fast CMOS Circuits[END_REF] by reducing each gate to an equivalent inverter. The current available from the N (P) parallel array of transistors is evaluated as the maximum current of an inverter with identically sized transistors. The array of N (P) series-connected transistors is modeled as an input voltage controlled current generator with a current capability reduced by a factor DW HL,LH . This reduction factor (DW) is defined as the ratio of the current available in an inverter to that of a seriesconnected array of transistors of identical size. 2) and (3) gives:

        - - ⋅ =         - ⋅ ⋅ = τ TP DD TN DD P N TN DD DD N V V V V K K R V V V K L Cox (9)
Eq.9 gives the supply voltage sensitivity of the transition time and of the propagation delay (1).

2.5 Temperature sensitivity. Can be included in the model considering both the mobility and the threshold voltage variations described in [START_REF] Sze | Physics of Semiconductor Devices[END_REF][START_REF] Power | An Investigation of MOSFET Statistical and Temperature Effects[END_REF]:

) ( V ) ( V K K nom Tnom T XT nom nom θ - θ δ - = θ       θ θ ⋅ = θ . ( 10
)
K and V T are respectively the conductivity factor and the threshold voltage, Θ nom , Θ, represent the reference and the targeted temperature, XT and δ are the temperature coefficients of the mobility and threshold voltage.

Coupling ( 9) and (10) a general expression for the τ supply voltage and temperature sensitivity can be obtained:

Tnom DDnom Tnom DD DDnom DD XT nom nom DD V V ) nom ( V V 1 V V ) , V ( - θ - θ δ + - ⋅                 θ θ = τ θ τ (11)
The different parameters of (11) can directly be determined from specific simulation conditions that we will define in the next part.

Continuous representation and Calibration

3. 1 Uniform representation. Let us now consider the case of rising edges applied to the input of gates. As it can be deduced from [START_REF] Mead | Introduction to VLSI systems[END_REF][START_REF] Sutherland | Logical Effort: Designing Fast CMOS Circuits[END_REF][START_REF] Power | An Investigation of MOSFET Statistical and Temperature Effects[END_REF], in the Fast input range, τ OUT FAST is characteristic of the inverter structure (gate) and of its load. Considering the sensitivity of the different expressions to the input slope, τ OUT FAST can be used as an internal reference of the output transition time of the considered structure. In this condition we can write:

            τ τ ⋅ - = τ τ Fast outHL INLH DD TN DD Fast outHL outHL V V V 1 Max ) Inv ( ( 12
)
Normalizing the output transition time with respect to τ outHL Fast , used as a reference, the resulting expression only depends on the input transition time. It is configuration ratio and load independent. Similar results are obtained for gates and the representation of propagation delay. This is illustrated in Fig. 2 where we represent, using τ OUT FAST as a reference, the output transition time variations for the complete family of inverters of a 0.25µm library. As expected all the curves pile up on the same one, representing the output transition time sensitivity to the input transition time. The final value for each specific cell is then directly obtained from the evaluation of τ OUT FAST , in (4), that contains the structure and load dependency. e) Using the inverter as a reference the parameters k and DW are determined from τ Gate /τ Inv . f) Eq.9 determines the supply voltage sensitivity.

g) The temperature parameters, XT and δ are obtained from the preceding steps realized at different temperature values.

Application to a 0.13µm library

We have applied this method to a 0.13µm library from STM. In this work we just considered the simple gates, an Inverter with 7 different drives, a Nand and a Nor with two and three inputs and 5 different drives. Initially the timing performance (transition time and propagation delay) of all these elements has been characterized from electrical simulations. They are available in tables (TLF, STF) that give, for each edge of the transition time and the propagation delay of each element, for 3 temperature and supply voltage values, the corresponding performance for 5 different values of the load and the input transition time.

We have determined on the different tables the values of the technology parameters and plot in Fig3 to 5, examples of the variation of the transition time and the propagation delay of different logic families. As shown, the performance variation of all the elements of each family can be represented by one curve described by one of the preceding equation.

In Table 1 we compare the τ supply voltage and temperature sensitivity calculated from (9,12) to the value deduced from the simulated values on the look up tables. As shown we obtain an excellent agreement between calculated and simulated values for all the considered supply voltage and temperature range. Theses variations can then be completely represented by (12) as:

58 . 0 ) 298 ( 10 2 62 . 0 V 1 2 . 1 V 298 ) , V ( 3 DD DD 65 . 1 DD - θ ⋅ + - ⋅       ⋅       θ = τ θ τ - (13)
Where the different coefficients have been directly determined following the procedure given in part 3.

Conclusion

Extending of the logical effort model, from physical considerations, we have defined a simple but accurate representation of the timing performance of the simple CMOS structures and their temperature and supply voltage sensitivity. We have introduced a new way of a continuous representation of these performances, allowing to model the complete load and input ramp sensitivity by one curve. We gave a method to calibrate the parameters of this representation that has been completely validated on a 0.13µm process for different temperature and supply voltage conditions. The extension of this representation to complex gates is under progress. V DD (V)

Fig. 1 .

 1 Fig.1. Illustration of the output transition time sensibility to the input transition time τ IN .

4

 4 the explicit form of the logical effort[START_REF] Sutherland | Logical Effort: Designing Fast CMOS Circuits[END_REF]. Note that depending on the input range and on the rank of the controlled input, for a given gate, it may have different values.. Considering eq.7, the output transition time of a gate is easily obtained under the generic expression of [6Supply voltage sensitivity. As shown in (4), τ represents the output transition time of an ideal inverter (without parasitic capacitance) designed with identical transistors and loaded by an identical one. Developing (4) from (

Fig. 2 .

 2 Fig.2. Full representation of the output transition time variation of the 7 inverters of a 0.25µm library. 3.2 Parameter extraction method. As shown in Fig.2 and (1,8,12) it appears that the output transition time and the propagation delay of all the gates of a library can be characterized with a reduced set of electrical simulations. a) The τ value is obtained from the output transition τ HL (falling edge) of an heavily loaded inverter (with a known configuration ratio k) controlled by a fast input ramp (τ IN < τ OUT ). b) R is obtained from the ratio τ LH /τ HL . c) For small load the variation of the apparent τ value determines the value of Cpar and C M . d) In the slow input range (τ IN > τ OUT ), varying τ IN determines the input slope sensitivity (6).e) Using the inverter as a reference the parameters k and DW are determined from τ Gate /τ Inv . f) Eq.9 determines the supply voltage sensitivity.g) The temperature parameters, XT and δ are obtained from the preceding steps realized at different temperature values.

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig.3.Output transition time representation of the 7 inverters of a 0.13µm process

Table 1 .

 1 Voltage and temperature sensitivity of the τ parameter, XT=1.65, δ = 2.10 -3 .

	τ	1.08	1.2	1.32
		Model Simul. Model Simul. Model Simul.
	Temp. (°K)	233 4.26 3.92 3.86 3.56 3.02 3.3 298 4.59 4.56 4.05 4.05 3.69 3.66 398 5.16 5.45 4.85 4.93 4.62 4.58