Search

Stable matching in a community consisting of men and women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley, who designed the celebrated “deferred acceptance” algorithm for the problem.

We consider two-person zero-sum stochastic games with signals, a standard model of stochastic games with imperfect information. The only source of information for the players consists of the signals they receive; they cannot directly observe the state of the game, nor the actions played by their opponent, nor their own actions. We are interested in the existence of almost-surely winning or positively winning strategies, under reachability, safety, Büchi, or co-Büchi winning objectives, and the computation of these strategies when the game has finitely many states and actions. We prove two qualitative determinacy results. First, in a reachability game, either player 1 can achieve almost surely the reachability objective, or player 2 can achieve surely the dual safety objective, or both players have positively winning strategies. Second, in a Büchi game, if player 1 cannot achieve almost surely the Büchi objective, then player 2 can ensure positively the dual co-Büchi objective. We prove that players only need strategies with finite memory . The number of memory states needed to win with finite-memory strategies ranges from one (corresponding to memoryless strategies) to doubly exponential, with matching upper and lower bounds. Together with the qualitative determinacy results, we also provide fix-point algorithms for deciding which player has an almost-surely winning or a positively winning strategy and for computing an associated finite-memory strategy. Complexity ranges from EXPTIME to 2EXPTIME, with matching lower bounds. Our fix-point algorithms also enjoy a better complexity in the cases where one of the players is better informed than their opponent. Our results hold even when players do not necessarily observe their own actions. The adequate class of strategies, in this case, is mixed or general strategies (they are equivalent). Behavioral strategies are too restrictive to guarantee determinacy: it may happen that one of the players has a winning general strategy but none of them has a winning behavioral strategy. On the other hand, if a player can observe their actions, then general, mixed, and behavioral strategies are equivalent. Finite-memory strategies are sufficient for determinacy to hold, provided that randomized memory updates are allowed.

Two-player, turn-based, stochastic games with reachability conditions are considered, where the maximizer has no information (he is blind) and is restricted to deterministic strategies whereas the minimizer is perfectly informed. We ask the question of whether the game has maxmin value of 1 in other words we ask whether for all \(\epsilon >0\) there exists a deterministic strategy for the (blind) maximizer such that against all the strategies of the minimizer, it is possible to reach the set of final states with probability larger than \(1-\epsilon \). This problem is undecidable in general, but we define a class of games, called leaktight half-blind games where the problem becomes decidable. We also show that mixed strategies in general are stronger for both players and that optimal strategies for the minimizer might require infinite-memory.

We study the existence of different notions of value in two-person zero-sum repeated games where the state evolves and players receive signals. We provide some examples showing that the limsup value (and the uniform value) may not exist in general. Then we show the existence of the value for any Borel payoff function if the players observe a public signal including the actions played. We also prove two other positive results without assumptions on the signaling structure: the existence of the $\sup$ value in any game and the existence of the uniform value in recursive games with nonnegative payoffs., Comment: Published at http://dx.doi.org/10.1214/14-AAP1095 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

International audience; The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton, are there words accepted with probability arbitrarily close to 1? This problem was proved undecidable recently; to overcome this, several classes of probabilistic automata of different nature were proposed, for which the value 1 problem has been shown decidable. In this paper, we introduce yet another class of probabilistic automata, called leaktight automata, which strictly subsumes all classes of probabilistic automata whose value 1 problem is known to be decidable. We prove that for leaktight automata, the value 1 problem is decidable (in fact, PSPACE-complete) by constructing a saturation algorithm based on the computation of a monoid abstracting the behaviours of the automaton. We rely on algebraic techniques developed by Simon to prove that this abstraction is complete. Furthermore, we adapt this saturation algorithm to decide whether an automaton is leaktight. Finally, we show a reduction allowing to extend our decidability results from finite words to infinite ones, implying that the value 1 problem for probabilistic leaktight parity automata is decidable.

In a recent paper de Alfaro, Henzinger and Majumdar [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] observed that discounting successive payments, the procedure that is employed in the classical stochastic game theory since the seminal paper of Shapley [L.S. Shapley. Stochastic games. Proceedings Nat. Acad. of Science USA, 39:1095–1100, 1953], is also pertinent in the context of much more recent theory of stochastic parity games [L. de Alfaro and R. Majumdar. Quantitative solution to omega-regular games. In STOC'01, pages 675–683. ACM Press, 2001. final version to appear in Journal of Computer and System Sciences, L. de Alfaro, T.A. Henzinger, and O. Kupferman. Concurrent reachability games. In FOCS'98, pages 564–575. IEEE Computer Society Press, 1998, L. de Alfaro and T.A. Henzinger. Concurrent ω-regular games. In LICS'00, pages 142–154. IEEE Computer Society Press, 2000] which were proposed as a tool for verification of probabilistic systems. We show that, surprisingly perhaps, the particular discounting used in [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] is in fact very close to the original ideas of Shapley. This observation allows to realize that the specific discounting of [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] suffers in fact from some needless restrictions. We advocate that dropping the constraints imposed in [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] leads to a more general and elegant theory that includes parity and mean payoff games as particular limit cases.

International audience; The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2-1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2-1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running in time O(d * n^{2d}*MeanGame) to compute the set of almost-sure winning states from which the objective can be ensured with probability 1, where n is the number of states of the game, d the number of priorities of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states in 2-1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective).

We study optimal strategies in two-player stochastic games that are played on a finite graph, equipped with a general payoff function. The existence of optimal strategies that do not make use of memory and randomisation is a desirable property that vastly simplifies the algorithmic analysis of such games. Our main theorem gives a sufficient condition for the maximizer to possess such a simple optimal strategy. The condition is imposed on the payoff function, saying the payoff does not depend on any finite prefix (shift-invariant) and combining two trajectories does not give higher payoff than the payoff of the parts (submixing). The core technical property that enables the proof of the main theorem is that of the existence of $$\epsilon$$ ϵ -subgame-perfect strategies when the payoff function is shift-invariant. Furthermore, the same techniques can be used to prove a finite-memory transfer-type theorem: namely that for shift-invariant and submixing payoff functions, the existence of optimal finite-memory strategies in one-player games for the minimizer implies the existence of the same in two-player games. We show that numerous classical payoff functions are submixing and shift-invariant.

The value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there observational strategies that achieve the reachability objective with probability arbitrarily close to 1? This problem was shown undecidable recently. Our contribution is to introduce a class of partially observable Markov decision processes, namely \(\sharp-acyclic\) partially observable Markov decision processes, for which the value 1 problem is decidable. Our algorithm is based on the construction of a two-player perfect information game, called the knowledge game, abstracting the behaviour of a \(\sharp\)-acyclic partially observable Markov decision process \({\mathcal M}\) such that the first player has a winning strategy in the knowledge game if and only if the value of \({\mathcal M}\) is 1.

This paper introduces and investigates decision problems for numberless probabilistic automata, i.e. probabilistic automata where the support of each probabilistic transitions is specified, but the exact values of the probabilities are not. A numberless probabilistic automaton can be instantiated into a probabilistic automaton by specifying the exact values of the non-zero probabilistic transitions.

International audience; This paper reports about the robotic installation set up by the Rhoban Project in the French pavilion of the Expo 2012 of Yeosu, Korea ([6]). The installation has consisted in a humorous show involving humanoid robots and anthropomorphic arms, with the illusion of life as a guideline. We emphasized natural compliant motion and physical interaction in order to make the show attractive. The design raised some issues dealing with robustness of robots, but also with the realism of the motions and the synchronization of the robots with the music.

We consider the task of controlling in a distributed way a Zielonka asynchronous automaton. Every process of a controller has access to its causal past to determine the next set of actions it proposes to play. An action can be played only if every process controlling this action proposes to play it. We consider reachability objectives: every process should reach its set of final states. We show that this control problem is decidable for tree architectures, where every process can communicate with its parent, its children, and with the environment. The complexity of our algorithm is l-fold exponential with l being the height of the tree representing the architecture. We show that this is unavoidable by showing that even for three processes the problem is EXPTIME-complete, and that it is non-elementary in general.

We study turn-based quantitative multiplayer non zero-sum games played on finite graphs with reachability objectives. In such games, each player aims at reaching his own goal set of states as soon as possible. A previous work on this model showed that Nash equilibria (resp. secure equilibria) are guaranteed to exist in the multiplayer (resp. two-player) case. The existence of secure equilibria in the multiplayer case remained and is still an open problem. In this paper, we focus our study on the concept of subgame perfect equilibrium, a refinement of Nash equilibrium well-suited in the framework of games played on graphs. We also introduce the new concept of subgame perfect secure equilibrium. We prove the existence of subgame perfect equilibria (resp. subgame perfect secure equilibria) in multiplayer (resp. two-player) quantitative reachability games. Moreover, we provide an algorithm deciding the existence of secure equilibria in the multiplayer case., Comment: 32 pages. Full version of the FoSSaCS 2012 proceedings paper

The value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there strategies that achieve the reachability objective with probability arbitrarily close to 1? This problem was shown undecidable recently. Our contribution is to introduce a class of partially observable Markov decision processes, namely #-acyclic partially observable Markov decision processes, for which the value 1 problem is decidable. Our algorithm is based on the construction of a two-player perfect information game, called the knowledge game, abstracting the behaviour of a #-acyclic partially observable Markov decision process M such that the first player has a winning strategy in the knowledge game if and only if the value of M is 1.

The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton A, are there words accepted by A with probability arbitrarily close to 1? This problem was proved undecidable recently. We sharpen this result, showing that the undecidability result holds even if the probabilistic automata have only one probabilistic transition. Our main contribution is to introduce a new class of probabilistic automata, called leaktight automata, for which the value 1 problem is shown decidable (and PSPACE-complete). We construct an algorithm based on the computation of a monoid abstracting the behaviours of the automaton, and rely on algebraic techniques developed by Simon for the correctness proof. The class of leaktight automata is decidable in PSPACE, subsumes all subclasses of probabilistic automata whose value 1 problem is known to be decidable (in particular deterministic automata), and is closed under two natural composition operators., Comment: arXiv admin note: significant text overlap with arXiv:1104.3054

International audience; 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.

International audience; We study turn-based quantitative multiplayer non zero-sum games played on finite graphs with reachability objectives. In such games, each player aims at reaching his own goal set of states as soon as possible. A previous work on this model showed that Nash equilibria (resp. secure equilibria) are guaranteed to exist in the multiplayer (resp. two-player) case. The existence of secure equilibria in the multiplayer case remained, and is still an open problem. In this paper, we focus our study on the concept of subgame perfect equilibrium, a refinement of Nash equilibrium well-suited in the framework of games played on graphs. We also introduce the new concept of subgame perfect secure equilibrium. We prove the existence of subgame perfect equilibria (resp. subgame perfect secure equilibria) in multiplayer (resp. two-player) quantitative reachability games. Moreover, we provide an algorithm deciding the existence of secure equilibria in the multiplayer case.

International audience; This paper tackles three algorithmic problems for probabilis- tic automata on finite words: the Emptiness Problem, the Isolation Prob- lem and the Value 1 Problem. The Emptiness Problem asks, given some probability 0 ≤ λ ≤ 1, whether there exists a word accepted with prob- ability greater than λ, and the Isolation Problem asks whether there exist words whose acceptance probability is arbitrarily close to λ. Both these problems are known to be undecidable [8, 2, 3]. About the Empti- ness problem, we provide a new simple undecidability proof and prove that it is decidable for automata with one probabilistic transition and undecidable for automata with as few as two probabilistic transitions. The Value 1 Problem is the special case of the Isolation Problem when λ = 1 or λ = 0. The decidability of the Value 1 Problem was an open question. We show that the Value 1 Problem is undecidable. Moreover, we introduce a new class of probabilistic automata, ♯-acyclic automata, for which the Value 1 Problem is decidable.

International audience; We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (both players interact simultaneously); and (b) turn-based (both players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. In this work we present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games.

International audience; Asynchronous automata are parallel compositions of finite- state processes synchronizing over shared variables. A deep theorem due to Zielonka says that every regular trace language can be represented by a deterministic asynchronous automaton. In this paper we improve the construction, in that the size of the obtained asynchronous automaton is polynomial in the size of a given DFA and simply exponential in the number of processes. We show that our construction is optimal within the class of automata produced by Zielonka-type constructions. In particular, we provide the first non trivial lower bound on the size of asynchronous automata.

We present a new algorithm for solving Simple Stochastic Games (SSGs). This algorithm is based on an exhaustive search of a special kind of positional optimal strategies, the f-strategies. The running time is O( |VR|! ċ (|V ||E| + |p|) ), where |V |, |VR|, |E| and |p| are respectively the number of vertices, random vertices and edges, and the maximum bit-length of a transition probability. Our algorithm improves existing algorithms for solving SSGs in three aspects. First, our algorithm performs well on SSGs with few random vertices, second it does not rely on linear or quadratic programming, third it applies to all SSGs, not only stopping SSGs.

International audience; We present a new algorithm for solving Simple Stochastic Games (SSGs), which is fixed parameter tractable when parametrized with the number of random vertices. This algorithm is based on an exhaustive search of a special kind of positional optimal strategies, the f-strategies. The running time is , where and are respectively the number of vertices, random vertices and edges, and the maximum bit-length of a transition probability. Our algorithm improves existing algorithms for solving SSGs in three aspects. First, our algorithm performs well on SSGs with few random vertices, second it does not rely on linear or quadratic programming, third it applies to all SSGs, not only stopping SSGs.

International audience; Markov decision processes (MDPs) are controllable discrete event systems with stochastic transitions. The payoff received by the controller can be evaluated in different ways, depending on the payoff function the MDP is equipped with. For example a \emph{mean--payoff} function evaluates average performance, whereas a \emph{discounted} payoff function gives more weights to earlier performance by means of a discount factor. Another well--known example is the \emph{parity} payoff function which is used to encode logical specifications~\cite{dagstuhl}. Surprisingly, parity and mean--payoff MDPs share two non--trivial properties: they both have pure stationary optimal strategies~\cite{CourYan:1990,neyman} and they both are approximable by discounted MDPs with multiple discount factors (multi--discounted MDPs)~\cite{dealf:2003,neyman}. In this paper we unify and generalize these results. We introduce a new class of payoff functions called the priority weighted payoff functions, which are generalization of both parity and mean--payoff functions. We prove that priority weighted MDPs admit optimal strategies that are pure and stationary, and that the priority weighted value of an MDP is the limit of the multi--discounted value when discount factors tend to $0$ simultaneously at various speeds.

International audience; Markov decision processes (MDPs) are controllable discrete event systems with stochastic transitions. Performances of an MDP are evaluated by a payoff function. The controller of the MDP seeks to optimize those performances, using optimal strategies. There exists various ways of measuring performances, i.e. various classes of payoff functions. For example, average performances can be evaluated by a mean-payoff function, peak performances by a limsup payoff function, and the parity payoff function can be used to encode logical specifications. Surprisingly, all the MDPs equipped with mean, limsup or parity payoff functions share a common non-trivial property: they admit pure stationary optimal strategies. In this paper, we introduce the class of prefix-independent and submixing payoff functions, and we prove that any MDP equipped with such a payoff function admits pure stationary optimal strategies. This result unifies and simplifies several existing proofs. Moreover, it is a key tool for generating new examples of MDPs with pure stationary optimal strategies.

International audience; We introduce stochastic priority games - a new class of perfect information stochastic games. These games can take two different, but equivalent, forms. In stopping priority games a play can be stopped by the environment after a finite number of stages, however, infinite plays are also possible. In discounted priority games only infinite plays are possible and the payoff is a linear combination of the classical discount payoff and of a limit payoff evaluating the performance at infinity. Shapley games and parity games are special extreme cases of priority games.

International audience; Inspired by the paper of de Alfaro, Henzinger and Majumdar about discounted $\mu$-calculus we show new surprising links between parity games and different classes of discounted games.

International audience; Reactive systems are often modelled as two person antagonistic games where one player represents the system while his adversary represents the environment. Undoubtedly, the most popular games in this context are parity games and their cousins (Rabin, Streett and Muller games). Recently however also games with other types of payments, like discounted or mean-payoff , previously used only in economic context, entered into the area of system modelling and verification. The most outstanding property of parity, mean-payoff and discounted games is the existence of optimal positional (memoryless) strategies for both players. This observation raises two questions: (1) can we characterise the family of payoff mappings for which there always exist optimal positional strategies for both players and (2) are there other payoff mappings with practical or theoretical interest and admitting optimal positional strategies. This paper provides a complete answer to the first question by presenting a simple necessary and sufficient condition on payoff mapping guaranteeing the existence of optimal positional strategies. As a corollary to this result we show the following remarkable property of payoff mappings: if both players have optimal positional strategies when playing solitary one-player games then also they have optimal positional strategies for two-player games.

International audience; This paper examines two players' turn-based perfect-information games played on infinite graphs. Our attention is focused on the classes of games where winning conditions are boolean combinations of the following two conditions: (1) the first one states that an infinite play is won by player $0$ if during the play infinitely many different vertices were visited, (2) the second one is the well known parity condition generalized to a countable number of priorities. We show that, in most cases, both players have positional winning strategies and we characterize their respective winning sets. In the special case of pushdown graphs, we use these results to show that the sets of winning positions are regular and we show how to compute them as well as positional winning strategies in exponential time.

We consider infinite antagonistic games over finite graphs. We present conditions that, whenever satisfied by the payoff mapping, assure for both players positional (memoryless) optimal strategies. To verify the robustness of our conditions we show that all popular payoff mappings, such as mean payoff, discounted, parity as well as several other payoffs satisfy them.

We study Markov decision processes (one-player stochastic games) equipped with parity and positive-average conditions. In these games, the goal of the player is to maximize the probability that both the parity and the positive-average conditions are fulfilled. We show that the values of these games are computable. We also show that optimal strategies exist, require only finite memory and can be effectively computed.

This paper introduces and investigates decision problems for numberless probabilistic automata, i.e. probabilistic automata where the support of each probabilistic transitions is specified, but the exact values of the probabilities are not. A numberless probabilistic automaton can be instantiated into a probabilistic automaton by specifying the exact values of the non-zero probabilistic transitions. We show that the two following properties of numberless probabilistic automata are recursively inseparable: - all instances of the numberless automaton have value 1, - no instance of the numberless automaton has value 1., Conference version: MFCS'14

The autonomy of robots heavily relies on their ability to make decisions based on the information provided by their sensors. In this dissertation, decision-making in robotics is modeled as continuous state and action markov decision process. This choice allows modeling of uncertainty on the results of the actions chosen by the robots. The new learning algorithms proposed in this thesis focus on producing policies which can be used online at a low computational cost. They are applied to real-world problems in the RoboCup context, an international robotic competition held annually. In those problems, humanoid robots have to choose either the direction and power of kicks in order to maximize the probability of scoring a goal or the parameters of a walk engine to move towards a kickable position., Afin d'être autonomes, les robots doivent êtres capables de prendre des décisions en fonction des informations qu'ils perçoivent de leur environnement. Cette thèse modélise les problèmes de prise de décision robotique comme des processus de décision markoviens avec un espace d'état et un espace d'action tous deux continus. Ce choix de modélisation permet de représenter les incertitudes sur le résultat des actions appliquées par le robot. Les nouveaux algorithmes d'apprentissage présentés dans cette thèse se focalisent sur l'obtention de stratégies applicables dans un domaine embarqué. Ils sont appliqués à deux problèmes concrets issus de la RoboCup, une compétition robotique internationale annuelle. Dans ces problèmes, des robots humanoïdes doivent décider de la puissance et de la direction de tirs afin de maximiser les chances de marquer et contrôler la commande d'une primitive motrice pour préparer un tir.

Small humanoid robots are often affected by many flaws : mechanical wraps and backlashes, electrical issues and motor control problems. This work is aimed at applying machine learning methods to deal with the flaws of the real robot. More precisely, improving the odometry accuracy and generated motion stability is studied. This thesis is highly guided and inspired by the participation of the Rhoban team (Rhoban Football Club) to the international RoboCup competition. Since 2011, the team has been competing each year in a soccer tournament within the fully autonomous small humanoid robots (Kid-Size) league. Proprioceptive odometry estimates the robot displacements from its internal sensors (no camera is used) whereas predictive odometry simulates the displacements created from a sequence of walk orders. Two corrective methods are proposed for the two kinds of odometries. The first one is based on a non parametric regression (LWPR) and a motion capture setup. The second one optimizes (CMA-ES) a linear corrective model without needing any external measure system. The proprioceptive odometry is essential to the localization of the robot on the soccer field. The predictive odometry is used to train a control policy for the walk motion. The generation of very dynamic motions like walking or kicking the ball is difficult due to the biped balance constraint and the many servomotor flaws. To start, kick motions are generated by optimization (CMA-ES) and evaluated based on the inverse dynamic model of the robot. The implementation of a physics simulator has been started. The objective is make the real behaviour of the robot to catch up the target trajectory by correcting the motion within the simulator., Les petits robots humanoïdes sont généralement soumis à de nombreuses imperfections : déformations et jeux mécaniques, défauts électriques et problèmes d'asservissements moteurs. L'objet de ces travaux est l'utilisation de techniques d'apprentissage pour compenser les imperfections du robot réel. L'amélioration de la précision de l'odométrie et de la stabilité de mouvements générés est étudiée. Cette thèse est fortement guidée et inspirée par la participation de l'équipe Rhoban (Rhoban Football Club) à la compétition internationale de robotique, la RoboCup. Depuis 2011, l'équipe concourt chaque année dans la ligue des petits robots humanoïdes complètement autonomes (Humanoid Kid-Size) dans un tournoi de football robotique. L'odométrie proprioceptive estime les déplacements du robot à partir de ses capteurs internes (la caméra n'est pas utilisée) alors que l'odométrie prédictive simule les déplacements engendrés par une séquence donnée d'ordres du mouvement de marche. Deux méthodes de correction sont ici proposées pour les deux odométries. La première se fonde sur une technique de régression non paramétrique (LWPR) et un système externe de capture de mouvement. La deuxième optimise (CMA-ES) un modèle de correction linéaire sans ne nécessiter aucun autre dispositif de mesure. L'odométrie proprioceptive est essentielle à la localisation du robot sur le terrain de football alors que l'odométrie prédictive permet d'entraîner hors ligne une politique de contrôle de la marche. La synthèse de mouvements très dynamiques tels que la marche ou le tir est rendue difficile par la forte contrainte de stabilité bipède et les imperfections des servomoteurs. Des mouvements de tir sont tout d'abord générés par optimisation (CMA-ES) et évalués au travers du modèle dynamique inverse du robot. Le développement d'un simulateur physique a été commencé. Le but est de réduire la distance entre le comportement réel et désiré du robot par correction des mouvements au sein du simulateur.