Comparison of Metaheuristic Algorithms for Evolving a Neural Controller for an Autonomous Robot

Robots are a good way to test things. Hope our robot overlords of the future will not take this to personal…

The task

We used a simulation of a robot that is searching for a light source as a testbed to compare how well a solution can be created by evolving an artificial neural network (ANN). While ANNs are often programmed using example input-output pairs which are learned by a backpropagation algorithm (supervised learning), in our case we left the how up to the system and only required the what – the robot should be able to find the light source by operating its wheels and using its sensors – that is called learning with belated rewards or reinforcement learning. We compared different evolutionary algorithms (EA), namely simple EA, two dimensional cellular EA, and random search, according to their performance in evolving a successful algorithm for the light-searching robot. In our experiments we studied the effects of EA parameters on performance, such as population size and number of generation. The simulations have been done using the open-source tool Framework for Evolutionary Design (FREVO).

The results explain how the choice of the neural network (three-layered or fully-connected) may inf

Possible implementation in hardware

luence the quality of a final solution. The results indicate that cEA and simple EA are the most applicable for evolving a neural controller. A fully-connected ANN outperforms three-layered ANN in all conducted experiments. Based on our findings, we recommend to use cEA and fully-connected ANN for problems that require short evaluation phase. For a large number of generations and population size the efficiency of both algorithms are approximately the same. In the experiments we measured an influence of population size and number of generations on performance of metaheuristic algorithms. The dependencies on these parameters are negligible. This information is important for the conduction of experiments. To accelerate a simulation, the population size should be the same as the number of cores on the server, where these experiments will be performed.

• Sergii Zhevzhyk, Wilfried Elmenreich, Comparison of Metaheuristic Algorithms for Evolving a Neural Controller for an Autonomous Robot, Transactions on Machine Learning and Artificial Intelligence, pp. 62-76, 15, 2014.
• A. Sobe, I. Fehérvári, and W. Elmenreich. FREVO: A tool for evolving and evaluating self-organizing systems. In Proceedings of the 1st International Workshop on Evaluation for Self-Adaptive and Self-Organizing Systems, Lyon, France, September 2012.

Scalability in Self-Organizing Systems

One of the properties of self-organizing systems is scalability. It means that system keeps its working capabilities even if we remove some of its components or add more of them. In our reseach, we employ different evolutionary algorithms (EAs) to create a self-organizing system. In particular, algorithms like a simple evolutionary algorithm or a two dimensional cellular EA are used  for adjusting the synaptic weights of an neural controller. The best solutions are identified based on simulations of the target application. Typically, the simulation parameters limit the applicability of the solution - there is no guarantee that an evolved solution is adaptable or scalable to situations not specified in the simulation parameters. On the other hand, there are many examples in nature where solutions could be successfully employed in other contexts. We decided to check how our soccer teams, which consist of evolved neural controllers, can scale.

For the FIFA World Cup in Brazil we organized our own tournament between evolved self-organized soccer teams. This is an exciting show - to see how simple agents having only partial information about the environment around them are reaching its goal (score a goal) as a team. Will they be able to play in the same manner if we take the contoller, trained in the simulation with 10 players per team, and increase or decrease the number of players? This question has remained open until today.

In our first scenario, we assume that we invited two soccer teams to show us a fantastic game, but due to some circumstances, only 4 players per teamshow up.
Thus our first experiment can be seen in the video below.
Despite the players being evolved in a context of 11 players on each side, reducing the number of players did not affect the ability of players to show good game.

To check the other extreme, we settled a very dangerous experiment - each team consisting of 40 players! The results were stunning (see video below). These soccer heroes could play as a team even with significantly increased number of players. Unfortunately, they could not play for a long time in this mode: Marco Materazzi headbutted Zinadine Zidane in the chest and shouted "Revenge!"; Luis Suarez bit two players in order to show his perfect teeth; Diego Maradona scored the goal by striking the ball with his hand and this time he was disqualified for this trick. We didn't care about these incidents since we got the results of our experiment:

Links:

• I. Fehervari and W. Elmenreich. Evolving neural network controllers for a team of self-organizing robots. Journal of Robotics, 2010.
• I. Fehervari and W. Elmenreich. Evolution as a tool to design self-organizing systems. In Self-Organizing Systems, volume LNCS 8221, pages 139–144. Springer Verlag, 2014.
• A. Sobe, I. Fehérvári, and W. Elmenreich. FREVO: A tool for evolving and evaluating self-organizing systems. In Proceedings of the 1st International Workshop on Evaluation for Self-Adaptive and Self-Organizing Systems, Lyon, France, September 2012.
• More simulated matches at Lakeside Labs WM Orakel http://www.robotoracle.at/

Simulating the Soccer World Cup 2014

You cannot wait for the soccer World Cup to start? We proudly present a peek preview of the World Cup 2014 - played by teams created with evolutionary algorithms. Using our evolutionary tool FREVO for designing self-organizing systems we have evolved neural networks that make robots playing soccer. During the evolution phase, a fitness function combines different aspects of gameplay like zone defense, man-marking, passing, shots, and goals. By tweaking the weights for these parameters we can influence the playing style of a team while the overall gameplay is still generated automatically by the evolutionary process. Thus we can simulate playing styles of different national teams and then match them against each other.

The following video shows a simulation of Brazil versus Croatia, the opening game of the world cup. The commentary is from Toni Polster, a legendary Austrian soccer player.

While the result is credible, we have not done this to exactly predict the outcome of the games - this would spoil the whole tournament! Furthermore, our approach is not meant for prediction but a system to train a distributed agent-based system to achieve an emergent cooperative behavior in a self-organized way. Setting up this work helped us in improving our understanding how we can create and guide self-organizing systems. We have chosen the soccer simulation as a demonstration because in soccer the global goal (no pun intended) can be achieved in so many different ways , for example with a defensive, offensive, kick-and-rush, pass-intensive, etc. style. And it is nice to watch - who said good science can't be fun!

Further readings:

• I. Fehervari and W. Elmenreich. Evolving neural network controllers for a team of self-organizing robots. Journal of Robotics, 2010.
• I. Fehervari and W. Elmenreich. Evolution as a tool to design self-organizing systems. In Self-Organizing Systems, volume LNCS 8221, pages 139–144. Springer Verlag, 2014.
• A. Sobe, I. Fehérvári, and W. Elmenreich. FREVO: A tool for evolving and evaluating self-organizing systems. In Proceedings of the 1st International Workshop on Evaluation for Self-Adaptive and Self-Organizing Systems, Lyon, France, September 2012.
• More simulated matches at Lakeside Labs WM Orakel http://www.robotoracle.at/

The Next Big Thing in Artificial Evolution

As announced in a previous blogpost, Prof. A. E. Eiben gave a very interesting talk on the next big in thing in artificial evolution during his visit at the Alpen-Adria-Universität Klagenfurt. Eiben presented a vision about having animate artefacts that are able to evolve and self-reproduce in physical spaces. To make this happen, he gives a notion of the integration of "hard" vs. "soft" evolutionary computation, the former meaning evolutionary optimiziation and design while the latter refering to artificial life, swarm robotics, and artificial societies.

Gusz Eiben's talk was attracting many people and lead to a vivid discussion afterwards about technology, possibilities, societal implications and parallels to existing sci-fi stories from Philip K. Dick or movies such as Terminator. So I think it is appropriate to say this talk was truly presenting science beyond fiction.

• A.E. Eiben, S. Kernbach, and Evert Haasdijk, Embodied artificial evolution: Artificial evolutionary systems in the 21st Century, Evolutionary Intelligence, 5(4):261-272, 2012
• A.E. Eiben. Introduction on Evolutionary Computing, Book, Springer, Natural Computing Series, 2003, ISBN: 3-540-40184-9
• More information on Eiben's work

6th International Conference on Agents and Artificial Intelligence

CALL FOR PAPERS

http://www.icaart.org/

March 6 - 8, 2014

Angers, France

In Cooperation with: AAAI and ACM SIGART
Co-organized by: ESEO
Sponsored by: INSTICC
INSTICC is Member of: FIPA, WfMC and OMG
Logistics Partner: SCITEVENTS


IMPORTANT DATES:
  Regular Paper Submission: September 24, 2013
  Authors Notification (regular papers): December 13, 2013
  Final Regular Paper Submission and Registration: January 7, 2014

The purpose of the 6th International Conference on Agents and Artificial Intelligence (ICAART) is to bring together researchers, engineers and practitioners interested in the theory and applications in the areas of Agents and Artificial Intelligence. Two simultaneous related tracks will be held, covering both applications and current research work.

We would like to highlight the presence of the following keynote speakers:
 - Philippe Leray, Université de Nantes, France
 - Henry Lieberman, MIT Media Laboratory, United States
(http://www.icaart.org/KeynoteSpeakers.aspx)

ICAART is interested in promoting high quality research as it can be confirmed by last year acceptance rates, where from 269 submissions, 14% were accepted as full papers. Additionally, 22% were presented as short papers and 22% as posters.
Submitted papers will be subject to a double-blind review process. All accepted papers will be published in the conference proceedings, under an ISBN reference, on paper and on CD-ROM support. A short list of papers presented at the conference will be selected for publication of extended and revised versions in a special issue of Springer's LNCS TCCI Journal. The proceedings will be submitted for indexation by Thomson Reuters Conference Proceedings Citation Index (ISI), INSPEC, DBLP, EI (Elsevier Index) and Scopus. All papers presented at the conference venue will be available at the SCITEPRESS Digital Library (http://www.scitepress.org/DigitalLibrary/). SCITEPRESS is member of CrossRef (http://www.crossref.org/).
Best paper awards will be distributed during the conference closing session. Please check the website for further information (http://www.icaart.org/BestPaperAward.aspx).
We would like to highlight the Doctoral Consortium on Agents and Artificial Intelligence that will take place in conjunction with ICAART and aims to provide an opportunity for graduate students to explore their research interests in an interdisciplinary workshop, under the guidance of a panel of distinguished experts in the field (http://www.icaart.org/DoctoralConsortium.aspx).

The conference will be sponsored by the Institute for Systems and Technologies of Information, Control and Communication (INSTICC), co-organized by the ESEO Group (ESEO) and held in cooperation with AAAI - Association for the Advancement of Artificial Intelligence and ACM SIGART - ACM Special Interest Group on Artificial Intelligence. INSTICC is Member of the Foundation for Intelligent Physical Agents (FIPA), Workflow Management Coalition (WfMC) and Object Management Group (OMG).