Faculté des sciences et techniques de l'ingénieur STI, Section de microtechnique, Institut d'ingénierie des systèmes I2S (Laboratoire de systèmes autonomes 1 LSA1)

Behaviour design in microrobots : hierarchical reinforcement learning under resource constraints

Asadpour, Masoud ; Siegwart, Roland (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2006 ; no 3682.

Ajouter à la liste personnelle
    Summary
    In order to verify models of collective behaviors of animals, robots could be manipulated to implement the model and interact with real animals in a mixed-society. This thesis describes design of the behavioral hierarchy of a miniature robot, that is able to interact with cockroaches, and participates in their collective decision makings. The robots are controlled via a hierarchical behavior-based controller in which, more complex behaviors are built by combining simpler behaviors through fusion and arbitration mechanisms. The experiments in the mixed-society confirms the similarity between the collective patterns of the mixed-society and those of the real society. Moreover, the robots are able to induce new collective patterns by modulation of some behavioral parameters. Difficulties in the manual extraction of the behavioral hierarchy and inability to revise it, direct us to benefit from machine learning techniques, in order to devise the composition hierarchy and coordination in an automated way. We derive a Compact Q-Learning method for micro-robots with processing and memory constraints, and try to learn behavior coordination through it. The behavior composition part is still done manually. However, the problem of the curse of dimensionality makes incorporation of this kind of flat-learning techniques unsuitable. Even though optimizing them could temporarily speed up the learning process and widen their range of applications, their scalability to real world applications remains under question. In the next steps, we apply hierarchical learning techniques to automate both behavior coordination and composition parts. In some situations, many features of the state space might be irrelevant to what the robot currently learns. Abstracting these features and discovering the hierarchy among them can help the robot learn the behavioral hierarchy faster. We formalize the automatic state abstraction problem with different heuristics, and derive three new splitting criteria that adapt decision tree learning techniques to state abstraction. Proof of performance is supported by strong evidences from simulation results in deterministic and non-deterministic environments. Simulation results show encouraging enhancements in the required number of learning trials, robot's performance, size of the learned abstraction trees, and computation time of the algorithms. In the other hand, learning in a group provides free sources of knowledge that, if communicated, can broaden the scales of learning, both temporally and spatially. We present two approaches to combine output or structure of abstraction trees. The trees are stored in different RL robots in a multi-robot system, or in the trees learned by the same robot but using different methods. Simulation results in a non-deterministic football learning task provide strong evidences for enhancement in convergence rate and policy performance, specially in heterogeneous cooperations.
    Résumé
    Afin de vérifier les modèles des comportements collectifs de certains animaux, des robots ont été programmés pour implémenter les modèles et les confronter avec de vrais animaux dans une société-mixte. Cette thèse décrit la conception de la hiérarchie comportementale d'un robot miniature, capable d'interagir avec des blattes et participer à leurs décisions collectives. Les robots sont contrôlés par un contrôleur hiérarchique comportemental dans lequel des comportements complexes sont établis en combinant des comportements plus simples par des mécanismes de fusion et d'arbitrage. Les expériences dans la société-mixte confirment la similitude entre les modèles collectifs de la société-mixte et ceux de la vraie société animale. D'ailleurs, les robots peuvent induire de nouveaux comportements collectifs par la modulation de quelques paramètres comportementaux. Les difficultés dans l'établissement manuel de la hiérarchie comportementale et l'impossibilité de l'améliorer, nous ont poussés à tirer avantage des techniques d'apprentissage, afin de concevoir la hiérarchie des comportements et leurs coordination d'une manière automatisée. Nous avons conçu une méthode de Q-Learning compacte pour des micro-robots en tenant compte de contraintes de mémoire et de puissance de calcul, et nous avons essayé d'apprendre la coordination des comportements par cette méthode. La composition du comportement est encore faite manuellement. Cependant, le gros problème de la dimensionnalité rend l'introduction de ce genre d'apprentissage peu convenable. Malgré le fait que l'optimisation de ces méthodes pourrait temporairement accélérer l'apprentissage et élargir leurs possibilités d'applications, leur scalability et l'application réelle reste une question. Dans les prochaines étapes, nous appliquons des techniques d'apprentissage hiérarchiques pour automatiser la composition et la coordination parmi des comportements. Dans certaines situations, beaucoup de caractéristiques de l'espace des états pourraient être non pertinentes pour l'apprentissage du robot. Faire abstraction de ces caractéristiques et en découvrir la hiérarchie peuvent aider le robot à apprendre la hiérarchie comportementale plus rapidement. Nous formalisons le problème d'abstraction automatique d'états avec une heuristique différente, et décrivons trois nouveaux critères de séparation qui permettent d'adapter les techniques d'apprentissage par arbre de décision pour l'abstraction d'état. La performance de ces techniques est prouvée par des résultats de simulations dans les environnements déterministes et non déterministes. Les résultats des simulations montrent des améliorations encourageantes du nombre d'étapes d'apprentissage requises, de la performance du robot, la taille des arbres d'abstraction appris, et le temps de calcul des algorithmes. Cependant, l'apprentissage dans un groupe fournit des sources de connaissances qui, si communiquées, peuvent élargir l'échelle de l'apprentissage, temporellement et dans l'espace. Nous présentons deux techniques pour combiner le résultat ou la structure des arbres d'abstraction. Les arbres sont stockés dans différents robots s'ils font partie d'un système multi-robot, ou dans les arbres appris par le même robot mais en employant différentes méthodes. Les résultats de simulations pour un apprentissage non déterministe du jeu du football fournissent des preuves évidentes de l'amélioration du taux de convergence et des performances de la tactique, particulièrement pour de la coopération hétérogène.