[PhD Proposal] Analysis of evolutionary learning algorithms for swarm robotics

Abstract

Imagine a set of miniature robots capable of evolving in an environment to achieve a given goal (exploration, detection of failures etc.). Furthermore, suppose that the environment is unknown and that the robots have a restricted field of communication. Designing such devices is, for the moment, an open problem where conventional algorithms struggle to work and where other approaches based on the distribution of computation, randomness and sparse exchange of data, manage to find solutions. However, we remain unable to explain why and how they get there.

Keywords: machine learning, swarm robotics, stochastic algorithms analysis.

Context

The LARSEN team is interested in artificial intelligence and more specifically in the design of robotic agents with intelligent autonomous behaviors. An agent is a computer or robotic entity endowed with sensori-motor capacities, capable of evolving autonomously in a given environment. The goal of this thesis is to contribute to this subject by studying how to learn the behaviors of a set of agents by evolutionary robotics [5].
Robot swarms are systems made up of a large number of relatively simple and cheap robots. Due to the large number of units, these systems have good robustness and scalability properties. However, designing systems of this nature to carry out interesting tasks remains a challenge and classical approaches like machine learning or deep learning cannot be applied. On the other hand, automated and decentralized approaches such as Embodied Evolutionary Robotics (EER) [2] are an attractive alternative. They open up many opportunities, where learning is carried out on line and in parallel by each robot in the swarm and during the execution of a task.

Goals

From an experimental point of view, EER algorithms have been used successfully on a large number of problems [2], however their analysis remain relatively underdeveloped. For example, there are no results guaranteeing or quantifying their convergence even on the simplest problem instances. Among the goals of this thesis, the most central will be to better understand these algorithms from a theoretical point of view by proposing the mathematical tools and models and by setting the frameworks that allow the study of these algorithms. One potentially promising path we propose to follow to reach this goal is to use known results in the field of distributed systems as well as the stochastic models in computational biology [3, 4] whose links with EER algorithms begin to be woven [1]. These results seem very promising for analyzing the internal dynamics of these algorithms as well as identifying the conditions necessary for their convergence. An other goal of the thesis would be to define a classification of the problems (complexity, nature, etc.) on which these algorithms are generally applied. In view of some experimental results [2], it seems that the application of these algorithms on different problems produces similar dynamics, it would be important to better understand how these problem instances could be linked. Furthermore, such a classification of problems would allow to generalize the analysis of the algorithms.

Additional information

The research proposed here will combine algorithmic analysis and experimentation in simulation and on robotic platforms. We seek a candidate with a strong background in AI, probability and stochastic processes, and with interest for machine learning and robotics, as well as good programming skills.

Contacts:

  • François Charpillet (DR INRIA, HDR) francois.charpillet@loria.fr
  • Amine Boumaza (MCF, Université de Lorraine) amine.boumaza@loria.fr

Duration: 3 years

Starting date: October 1st 2020

References

  1. Amine Boumaza. Phylogeny of embodied evolutionary robotics. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’17, pages 1681–1682, New York, NY, USA, 2017. ACM.
  2. Nicolas Bredeche, Evert Haasdijk, and Abraham Prieto. Embodied evolution in collective robotics: A review. Front, in Robo. and AI, 5:12, 2018.
  3. Benjamin Doerr, Philipp Fischbeck, Clemens Frahnow, Tobias Friedrich, Timo Kötzing, and Martin Schirneck. Island models meet rumor spreading. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’17, pages 1359–1366, New York, NY, USA, 2017. ACM.
  4. Jotun Hein, Mikkel H. Schierup, and Carsten Wiuf. Gene Genealogies, Variation and Evolution A Primer in Coalescent Theory. Oxford University Pres, 2005.
  5. Stefano Nolfi and Dario Floreano. Evolutionary Robotics: The Biology, Intelligence, and Technology. MIT Press, Cambridge, MA, USA, 2000.

Logo d'Inria