Cette thèse porte sur un certain nombre de problèmes algorithmiques motivés par la planification temporelle automatisée et la vérification formelle des systèmes réactifs et finis. Nous nous sommes concentrés sur les méthodes théoriques des jeux pour obtenir de nouvelles connaissances, des limites de complexité améliorées et des algorithmes plus rapides pour les modèles suivants: réseaux temporels hyper, réseaux conditionnels Simples / Hyper temporels, jeux de mise à jour, jeux Muller McNaughton et jeux Mean Payoff / This dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verification of reactive and finite state systems. We focused on game theoretical methods to obtain novel insights, improved complexity bounds, and faster algorithms for the following models: Hyper Temporal Networks, Conditional Simple/Hyper Temporal Networks, Update Games, Muller McNaughton Games, and Mean Payoff Games

Les mouvements volontaires sont accompagnés par des ajustements posturaux anticipateurs (APAs). Leur rôle consiste à prévenir et à compenser de possibles perturbations du corps provoquées par l’exécution du mouvement. Des études antérieures ont montré que la coordination posture / mouvement est modifiée selon que le mouvement est exécuté le plus rapidement possible en réponse à un signal externe (réactif :TRS), ou que le mouvement est auto-initié (prédictif :AI). L’objectif de ce travail est d’examiner le mode de coordination posture / mouvement impliqué dans une situation d’anticipation-coïncidence (AC) lors de l’exécution de mouvements simples et complexes, et ensuite, comparer ce mode aux modes TRS et AI. Trois études expérimentales ont été menées pour vérifier si : (1) les modes de coordination, obtenus sur des gestes simples, s’étendent à des mouvements complexes ; (2) le mode de coordination en AC dépend des caractéristiques temporelles du mobile utilisé dans la tâche ; (3) les commandes impliquant les APAs et le mouvement focal sont associées ou dissociées en fonctions des contraintes temporelles TRS et AC. Ainsi, nous avons démontré que : (1) les stratégies de coordination posture / mouvement s’appliquent sur les mouvements complexes ; (2) la prédictibilité du moment de déclenchement dans la condition AC rapproche celle-ci de la situation AI ; (3) les différences de coordination entre les conditions réactive (TRS) et prédictives (AC, AI) sont liées à des différences dans les mécanismes de préparation consistant à dissocier les commandes posturales et focales en situation prédictive et à associer ces commandes dans la situation réactive. Les implications théoriques qui émergent de ces résultats sont discutées. / Voluntary movements are generally accompanied by anticipatory postural adjustments (APAs). They are centrally generated as a feedforward mechanism to counteract the mechanical effects of predicted balance perturbations. Previous studies showed that the coordination between posture and movement is modified depending on whether the movement is performed in a reactive temporal pressure (TRS) or in a self-initiated (AI) manner. The aim of this thesis is to examine the coordination of posture and movement in anticipation-coincidence (AC) timing tasks in simple and complex movements, and then to compare this mode to the TRS and AI modes. Three experiments was achieved to verify : (1) whether simple movement coordination modes can be extended to complex movements ; (2) whether the temporal characteristics of the mobile used in the task modifies the coordination in AC condition ; (3) to which extent the motor commands of APAs and the focal movement are coupled in response to the TRS and AC temporal pressures. Results show that: (1) the different strategies of coordination between posture and movement are extended to the complex tasks; (2) the predictable timing of movement execution in the AC condition generates behaviours closer to those observed in AI condition; (3) the differences in the coordination between the reactive (TRS) and the predictive (AC, AI) conditions are related to the difference in the preparatory processes which consists on the dissociation of postural and focal commands in the predictive situations, and the association of this motor commands in the reactive situation. Theoretical implications emerging from these results are discussed.

Neste estudo foi analisado o efeito de distância, velocidade, tamanhos do disco e do alvo, e massas do disco e da manopla, sobre o desempenho motor em movimentos requisitando rapidez e precisão. Para tanto, foram analisadas as características cinemáticas da tarefa de projetar um disco a um alvo com movimento de contato balístico, empunhando uma manopla. Os movimentos foram desempenhados sobre uma base plana e filmados com câmera optoeletrônica de alta freqüência. O estudo foi conduzido em seis experimentos com um grupo único de participantes. Os resultados indicaram que os modelos de controle motor que têm sido empregados para analisar a relação velocidade-precisão em tarefas mais simples não foram apropriados para explicar o comportamento da tarefa utilizada. O controle motor na tarefa demonstrou ser dinâmico e flexível, frente às diferentes restrições de movimento. As seguintes estratégias de controle foram sugeridas na explicação dos resultados: sincronização da maior velocidade e do instante de contato manopla-disco, manutenção na proporção entre as fases aceleração-desaceleração, maior inércia e menor impacto para aumentar a estabilidade de movimento, e o controle da velocidade e da precisão em dimensões independentes. A análise das ações articulares demonstrou as particularidades das estratégias utilizadas pelo sistema no movimento em função das variáveis manipuladas. Em conjunto, esta seqüência de experimentos permitiu uma compreensão mais ampla das estratégias de controle motor empregadas em movimentos com alta demanda de velocidade e de precisão / In this study it was analyzed the effect of distance, velocity, disc and target width, disc and manipulandum mass, over motor control of a rapid and accurate movement. For such, it was analyzed the kinematic characteristics of the task of launching a disc to a target using a ballistic movement, performed with a manipulandum. Movements were performed on a flat surface and filmed with a high frequency optoelectronic camera. The study was conducted through six experiments with a single group of participants. Analysis of results indicated that models of motor control that has been used to analyze speed-accuracy tradeoff in simpler tasks were not appropriate to explain the observed behavior in the task used. Motor control in the task showed to be dynamic and flexible, regarding the several constraints manipulated. The follow strategies of control were suggested to explain the results: synchronization of the peak velocity and the instant of disc-manipulandum contact, maintenance of the proportion between the acceleration-deceleration phases, greater inertia and minor impact to increase movement stability, and control of velocity and accuracy of independent dimensions. The prediction of Analysis of joint actions showed the particularities of the strategies used by the system on movement as a function of the manipulated variables. Together, this study sequence of experiments allowed for a deeper comprehension of the control strategies used in the control of rapid and accurate movements

Neste estudo foi analisado o efeito de distância, velocidade, tamanhos do disco e do alvo, e massas do disco e da manopla, sobre o desempenho motor em movimentos requisitando rapidez e precisão. Para tanto, foram analisadas as características cinemáticas da tarefa de projetar um disco a um alvo com movimento de contato balístico, empunhando uma manopla. Os movimentos foram desempenhados sobre uma base plana e filmados com câmera optoeletrônica de alta freqüência. O estudo foi conduzido em seis experimentos com um grupo único de participantes. Os resultados indicaram que os modelos de controle motor que têm sido empregados para analisar a relação velocidade-precisão em tarefas mais simples não foram apropriados para explicar o comportamento da tarefa utilizada. O controle motor na tarefa demonstrou ser dinâmico e flexível, frente às diferentes restrições de movimento. As seguintes estratégias de controle foram sugeridas na explicação dos resultados: sincronização da maior velocidade e do instante de contato manopla-disco, manutenção na proporção entre as fases aceleração-desaceleração, maior inércia e menor impacto para aumentar a estabilidade de movimento, e o controle da velocidade e da precisão em dimensões independentes. A análise das ações articulares demonstrou as particularidades das estratégias utilizadas pelo sistema no movimento em função das variáveis manipuladas. Em conjunto, esta seqüência de experimentos permitiu uma compreensão mais ampla das estratégias de controle motor empregadas em movimentos com alta demanda de velocidade e de precisão / In this study it was analyzed the effect of distance, velocity, disc and target width, disc and manipulandum mass, over motor control of a rapid and accurate movement. For such, it was analyzed the kinematic characteristics of the task of launching a disc to a target using a ballistic movement, performed with a manipulandum. Movements were performed on a flat surface and filmed with a high frequency optoelectronic camera. The study was conducted through six experiments with a single group of participants. Analysis of results indicated that models of motor control that has been used to analyze speed-accuracy tradeoff in simpler tasks were not appropriate to explain the observed behavior in the task used. Motor control in the task showed to be dynamic and flexible, regarding the several constraints manipulated. The follow strategies of control were suggested to explain the results: synchronization of the peak velocity and the instant of disc-manipulandum contact, maintenance of the proportion between the acceleration-deceleration phases, greater inertia and minor impact to increase movement stability, and control of velocity and accuracy of independent dimensions. The prediction of Analysis of joint actions showed the particularities of the strategies used by the system on movement as a function of the manipulated variables. Together, this study sequence of experiments allowed for a deeper comprehension of the control strategies used in the control of rapid and accurate movements

Le domaine de la planification de tâches a vu de rapides développements au cours de la dernière décennie et des planificateurs sont maintenant capable de trouver des plans de centaines actions en quelques secondes. Malgré ces importants progrès, les systèmes robotiques dépendent toujours d'une architecture réactive avec peu de capacités de délibération sur les futures actions qu'il pourraient faire. Dans cette thèse, nous soutenons qu'une intégration réussie d'un planificateur avec un système robotique ne peut être réussie que si le planificateur a la capacité de raisonner sur des modèles temporels et hiérarchiques. Le temps est en en effet une ressource centrale pour énormément d'activité autonomes tandis que les aspects hiérarchiques sont critiques pour l'intégration de modules de délibération à différents niveau d'abstraction, dans lequel on reçoit une vue très abstraite d'une activité qui doit être affinée jusqu'à des commandes motrices. Comme première étape dans cette direction, nous commençons par présenter un modèle pour la planification temporelle qui unifie les approches génératives et hiérarchiques. Au centre de ce modèle sont des patrons d'actions temporelles, complétées par une spécification d'un état initial et de l'évolution attendue de l'environnement. De plus, notre modèle permet la spécification de connaissance hiérarchique sur tout ou partie du domaine. Ainsi, notre modèle généralise les approches génératives et HTN tout en supportant une représentation explicite du temps. Ensuite, nous introduisons un algorithme de planification adapté au modèle proposé. Pour supporter les caractéristiques hiérarchiques, nous étendons l'approche classique de planification en l'espace des plan, notamment utilisée dans les planificateurs basés sur les CSP, avec les notions de tâches et de décomposition. L'approche est implémentée dans FAPE (Flexible Acting and Planning Environment) conjointement avec des techniques pour l'analyse automatique de problèmes. Celles-ci sont utilisées au cours de la planification pour guider la recherche d'une solution. Nous montrons que FAPE a des performances comparables avec les meilleurs planificateurs actuels quand utilisé dans une optique de planification générative. L'ajout d'information hiérarchique permet de les surpasser en augmentant encore les performances. Nous étudions ensuite les méthodes habituellement utilisées pour raisonner sur l'incertitude temporelle en planification. Nous relâchons les suppositions classiques d'observabilité totale et proposons des techniques pour raisonner sur les observations nécessaires pour maintenir un plan exécutable. Nous montrons que les dites observations peuvent être détectées durant la planification et traitées incrémentalement en considérant les actions de perceptions appropriées. Pour finir, nous discutons de la place du système de planification proposé comme composant central pour le contrôle d'un robot. Nous démontrons que la prise en compte explicite du temps facilite le monitoring et l'exécution d'actions quand le système doit prendre en compte des événements contingents qui nécessitent d'être observés. Nous bénéficions également des représentations hiérarchiques et par contraintes qui facilitent la réparation de plan et la possibilité d'affiner un plan durant l'exécution. / The field of AI planning has seen rapid progress over the last decade and planners are now able to find plan with hundreds of actions in a matter of seconds. Despite those important progresses, robotic systems still tend to have a reactive architecture with very little deliberation on the course of the plan they might follow. In this thesis, we argue that a successful integration with a robotic system requires the planner to have capacities for both temporal and hierarchical reasoning. The former is indeed a universal resource central in many robot activities while the latter is a critical component for the integration of reasoning capabilities at different abstraction levels, typically starting with a high level view of an activity that is iteratively refined down to motion primitives. As a first step to carry out this vision, we present a model for temporal planning unifying the generative and hierarchical approaches. At the center of the model are temporal action templates, similar to those of PDDL complemented with a specification of the initial state as well as the expected evolution of the environment over time. In addition, our model allows for the specification of hierarchical knowledge possibly with a partial coverage. Consequently, our model generalizes the existing generative and HTN approaches together with an explicit time representation. In the second chapter, we introduce a planning procedure suitable for our planning model. In order to support hierarchical features, we extend the existing Partial-Order Causal Link approach used in many constraintbased planners, with the notions of task and decomposition. We implement it in FAPE (Flexible Acting and Planning Environment) together with automated problem analysis techniques used for search guidance. We show FAPE to have performance similar to state of the art temporal planners when used in a generative setting. The addition of hierarchical information leads to further performance gain and allows us to outperform traditional planners. In the third chapter, we study the usual methods used to reason on temporal uncertainty while planning. We relax the usual assumption of total observability and instead provide techniques to reason on the observations needed to maintain a plan dispatchable. We show how such needed observations can be detected at planning time and incrementally dealt with by considering the appropriate sensing actions. In a final chapter, we discuss the place of the proposed planning system as a central component for the control of a robotic actor. We demonstrate how the explicit time representation facilitates plan monitoring and action dispatching when dealing with contingent events that require observation. We take advantage of the constraint-based and hierarchical representation to facilitate both plan-repair procedures as well opportunistic plan refinement at acting time.