Swarm robotics designates large groups of robots with limited communication and capability, that coordinates on a local basis to achieve tasks that can be evaluated on a larger scale. Typical examples are: collective construction (Werfel et al. 2014), self-assembly into specific patterns (Rubenstein et al., 2014), collective transport and exploration (Bayindir, Sahin, 2007). However, the complex collective dynamics between individuals and the unpredictable nature of real-world environments makes it very difficult to hand-code or optimise swarm behaviours prior to deployment.
A promising class of algorithm to program on-the-fly swarm of robotics is that of embodied evolutionary algorithm (EEA). EEA are on-line distributed learning algorithms that makes it possible to learn collective behaviours on-the-fly while the robots are already deployed in the real world. The benefits of such algorithms is that collective dynamics arises from interaction between robots and with the environments.
One of the major issue is that the global objective, defined at the population level, is difficult to grasp at the individual-level. For example, a group of robots may be asked to gather as many items as possible, which may require some robots to explore part of the environment where there are fewer items that elsewhere. In this case, some robots will under-performed when compared to others, but the global score will be better than that of all robots going only to the area with the highest density of items.
During this internship, we will explore how to estimate synergies and marginal contributions of individuals within a group in an on-line distributed manner. As well known method such as the Shapley value or the Banzhaf power index are computationally and informationally demanding, we will explore how to automatically build individual-based objective function that approximate the local utility from a global utility function and past interactions. In particular, we will explore how a surrogate model of a local utility function can be constructed on-the-fly, to act as a local proxy for the global utility function.
__Administrative information__
The internship will be done at UPMC, between the ISIR and LIP6 labs, starting Feb. 15th for 6 months (internship gratification is approx. 500 euros per month).
__Short bibliography__
Embodied evolution: Distributing an evolutionary algorithm in a population of robots
RA Watson, SG Ficici, JB Pollack
Robotics and Autonomous Systems 39 (1), 1-18
Continuous Foraging and Information Gathering in a Multi-Agent Team
Somchaya Liemhetcharat, Rui Yan and Keng Peng Tee
Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), pages 1325-1333, May 2015
Weighted Synergy Graphs for Effective Team Formation with Heterogeneous Ad Hoc Agents
Somchaya Liemhetcharat and Manuela Veloso. Artificial Intelligence. Volume 208 (2014), pages 41-65, March 2014. DOI: 10.1016/j.artint.2013.12.002
A Review of Studies in Swarm Robotics
Bayindir, L., & Sahin, E. (2007) Turk J Elec Engin, 15(2), 115–147. http://doi.org/10.1.1.98.7821
Programmable self-assembly in a thousand-robot swarm
Rubenstein, M., Cornejo, A., & Nagpal, R. (2014) Science, 345(6198), 795–799. http://doi.org/10.1126/science.1254295
Designing collective behavior in a termite-inspired robot construction team
Werfel, J., Petersen, K., & Nagpal, R. (2014) Science (New York, N.Y.), 343(6172), 754–8. http://doi.org/10.1126/science.1245842
Hervé Moulin, Fair Division and Collective Welfare, The MIT Press, 2004
Peter Stone, Gal A. Kaminka, Sarit Kraus, and Jeffrey S. Rosenschein. Ad Hoc Autonomous Agent Teams: Collaboration without Pre-Coordination. In Proceedings of the Twenty-Fourth Conference on Artificial Intelligence, July 2010.