New research line on µRTS

This new research line was started one year ago together with PhD student Abdessamed Ouessai and professor Mohammed Salem both from the University of Mascara (Algeria).

The objective is focused on the improvemet of the decision process of an autonomous agent for playing a simple Real-Time Strategy Game, named µRTS (microRTS). See an illustrative image below of this game/simulator created by Proffessor Santiago Ontañón mainly for research purposes.

For the moment three papers have been published:

1. Online Adversarial Planning in μRTS: A Survey. Presented at 2019 International Conference on Theoretical and Applicative Aspects of Computer Science (ICTAACS) on December 2019, and selected as Best paper of the conference.
2. Improving the Performance of MCTS-Based µRTS Agents Through Move Pruning. Published and presented at IEEE Conference on Games 2020 last August 2020.
3. Parametric Action Pre-Selection for MCTS in Real-Time Strategy Games. Presented at CoSECiVi 2020 yesterday.

Here you can see the slides and the video presentation of the paper at CoG:

Moreover an agent named USMBot was created and participed in the last µRTS AI Competition, reaching rank 4!!!

The bot can be found in Github

We hope you like it, as usual. :D

EAs + Monte Carlo Tree Search for the win (*BEST PAPER of EvoAPPS 2020 conference*)

Yes! We did it! :D

Yesterday we presented our last paper on the scope of AI in Videogames entitled «Testing hybrid computational intelligence algorithms for general game playing«, by two colleagues of the University of Málaga (A. E. Vázquez-Núñez and A. J. Fernández-Leiva), together with P. García-Sánchez (@fergunet) and I (A. M. Mora).

It was focused on the domain of General Game Playing, where the aim is to create an autonomous agent able to adapt itself to play to several different videogames (not previously known for it). We used the framework and followed the rules of the General Video Game AI Competition.

Thus, it’s an approach to implement a kind of human-like behaviour the first time we face a new game.

The manuscript was selected as the Best Paper of EvoAPPS 2020 conference (inside EVO* 2020), held online for the first time, due to COVID-19 situation.

The abstract of the work is:

General Videogame Playing is one of the hottest topics in the research field of AI in videogames. It aims at the implementation of algorithms or autonomous agents able to play a set of unknown games efficiently, just receiving the set of rules to play in real time. Thus, this work presents the implementation of eight approaches based on the main techniques applied in the literature to face this problem, including two different hybrid implementations combining Monte Carlo Tree Search and Genetic Algorithms. They have been created within the General Video Game Artificial Intelligence (GVGAI) Competition platform. Then, the algorithms have been tested in a set of 20 games from that competition, analyzing its performance. According to the obtained results, we can conclude that the proposed hybrid approaches are the best approaches, and they would be a very competitive entry for the competition.

And here is the presentation:

Enjoy it!

And, as usual, cite us. ;D

Ants are already in 5G

Today we have presented our first international paper on the scope of 5G. I have used for that my favourite metaheuristic: Ant Colony Optimization, which has been adapted to solve a problem of network service composition, i.e., the so-called Service Function Chaining.

The paper is titled «Applying Ant Colony Optimization for Service Function Chaining in a 5G Network» paper with the same title presented today (22 October 2019) in Granada, on the «6th IEEE International Conference on Internet of Things: Systems, Management and Security (IOTSMS 2019)«, and in this, inside the «International Workshop on Efficient and Smart 5G Technologies for IoT (ES5TI)«.

The abstract of the paper is:

The growth of data traffic and the demand for new services are two of the main challenges to take into account in the design of next-generation networks. Service Function Chaining (SFC) is a technique that allows the execution of advanced services, routing network traffic through an ordered list of virtual functions. This mechanism is getting great relevance due to the rise of Software-defined Networks (SDNs) and the use of Network Function Virtualization (NFV), as well as the offered possibilities in terms of flexibility and automation. Given the existing need for operators to offer low latency services in 5G networks, the composition of this chain is a critical process that affects the performance of these services. Inside this context, this paper presents the design and implementation of an Ant Colony Optimization algorithm (ACO) for the minimization of the routing cost of service chain composition. ACO is a specially designed metaheuristic to work with weighted graphs, also considering restrictions, as is the case of the addressed problem. To test the value of the implemented algorithm, two different instances have been solved. The first one (with only 6 nodes) is a proof of concept, which easily allows to analyze the obtained solutions. The second one (19 nodes) models a medium-size 5G network, and tries to show the performance of this method in a wider graph. The results show that the proposed algorithm can lead to optimal solutions in many cases, even in a short time (less than 0.5 seconds) in the largest instance, so we consider this method as a very promising solution in this field.

The presentation can be see from Slidehare:

Enjoy it!

(and cite us :D)

 

A new lap in the race to improve our evolutionary fuzzy-controllers for TORCS

Last week we presented at the IEEE Conference on Game 2019, held in London (UK), our new paper titled «Beating uncertainty in racing bot evolution through enhanced exploration and pole position selection«.

The abstract of the work is:

One of the main problems in the design through optimization of car racing bots is the inherent noise in the optimization process: besides the fact that the fitness is a heuristic
based on what we think are the keys to success and as such just a surrogate for the ultimate objective, winning races, fitness itself is uncertain due to the stochastic behavior of racing conditions and the rest of the (simulated) racers. The fuzzy-based genetic controller for the car racing simulator TORCS that we have defined in previous works is based on two fuzzy subcontrollers, one for deciding on the wheel steering angle and another to set the car target speed at the next simulation tick. They are both optimized by means of an Evolutionary Algorithm, which considers an already tested fitness function focused on the maximization of the average speed during the race and the minimization of the car damage. The noisy environment asks for keeping diversity high during evolution, that is why we have added a Blend Crossover (BLX-alpha) operator, which is, besides, able to exploit current results at the same time it explores. Additionally, we try to address uncertainty in selection by introducing a novel selection policy of parents based in races, where the individuals are grouped and compete against others in several races, so just the firsts ranked will remain in the population as parents. Several experiments have been conducted, testing the value of the different controllers. The results show that the combination of a dynamic BLX-alpha crossover operator plus the pole position selection policy clearly beats the rest of approaches. Moreover, in the comparison of this controller with one of the participants of the prestigious international Simulated Car Racing Championship, our autonomous driver obtains much better results than the opponent.

The presentation can be seen below:

As usual, enjoy it and…cite us! :D

Angry Birds meet EAs at EVO* 2019

Last 24 of April we presented the work «Free Form Evolution for Angry Birds Level Generation» at EVOApplications 2019 (EvoGAMES) a conference part of EVO* 2019, held in Leipzig (Germany).

The abstract of the work is:

This paper presents an original approach for building structures that are stable under gravity for the physics-based puzzle game Angry Birds, with the ultimate objective of creating fun and aesthetically pleasing Angry Birds levels with the minimum number of constraints. This approach consists of a search-based procedural level generation method that uses evolutionary algorithms. In order to evaluate the stability of the levels, they are executed in an adaptation of an open source version of the game called Science Birds. In the same way, an open source evolutionary computation framework has been implemented to fit the requirements of the problem. The main challenge has been to design a fitness function that, first, avoids if possible the actual execution of the simulator, which is time consuming, and, then, to take into account the different ways in which a structure is not structurally sound and consider them in different ways to provide a smooth landscape that eventually achieves that soundness. Different representations and operators have been considered and studied. In order to test the method four experiments have been carried out, obtaining a variety of stable structures, which is the first path for the generation of levels that are aesthetically pleasing as well as playable.

@amorag did a short presentation and later ‘defended’ a poster during the reception act. The presentation is a description of the poster:

Actually the poster was selected as the second best of the conference by the attendants. :D

Those interested can found the paper at Springer web: https://link.springer.com/chapter/10.1007/978-3-030-16692-2_9

Enjoy it… and cite us! ;D

Algoritmos evolutivos aplicados a HearthStone en las noticias

Este fin de semana algunas webs se han hecho eco de una noticia originada por la Agencia SINC.

En concreto la noticia se ha titulado «La inteligencia artificial imita la evolución biológica para ganar en los videojuegos« y resumida como:

Informáticos españoles han aplicado técnicas avanzadas de inteligencia artificial para generar automáticamente los mejores mazos de cartas en Hearthstone, un videojuego en línea con más de 30 millones de jugadores en todo el mundo. Los algoritmos se inspiran en el proceso biológico de la selección natural.

Entre las webs que la han recogido, destacan, por ejemplo la de La Sexta.

Dichas noticias se refieren a nuestro trabajo publicado hace algunos meses en la revista Knowledge-Based Systems y comentado en esta entrada del blog.

 

 

Stateless evolutionary algorithms

Most algorithms keep some kind of state: global variable that holds the optimum, a counter of the number of evaluations, some context every piece algorithm must be aware of. However, this might not be the best when we want to create cloud-native algorithms, and it’s not in the case of cloudy evolutionary algorithms. There was a bit of that in GECCO, but as long as I was attending the Perl Conference in Glasgow, and I was using Perl, I kind of switched focus from the evolutionary part (but there was a bit of that too) to the language-design part and talked about evolutionary algorithms in Perl 6. The presentation is linked from the talk description.
Main problem is that you have to create dataflows that allow the algorithm to progress, as well as work efficiently in that kind of concurrent architecture, which is similar to the serverless architecture that is our eventual target.
We’ll be continuing this research in the workshop on engineering applications in Medellín, where my keynote will deal with this same topic.

//embedr.flickr.com/assets/client-code.js

Improved Genetic Fuzzy Drivers presented at CIG 2018

Last week I presented at IEEE CIG 2018 (held in Maastricht, The Netherlands) our following step in our research about autonomous drivers for Car Racing Simulators, such as TORCS, titled «The Evolutionary Race: Improving the Process of Evaluating Car Controllers in Racing Simulators«.

As commented before by @jjmerelo and later by @fergunet, we designed with Mohammed Salem (University of Mascara) a driver’s AI in which two Fuzzy Subcontrollers were hybridized with a Genetic Algorithm.

In this work we present a better evaluation approach for the GA, combining three methods: heuristic track choosing, improved fitness functions, and race-based selection of the best.

The abstract of the work is:

Simulated car races have been used for a long time as an environment where car controlling algorithms can be tested; they are an interesting testbed for all kinds of algorithms, including metaheuristics such as evolutionary algorithms. However, the challenge in the evolutionary algorithms is to design a reliable and effective evaluation process for the individuals that eventually translates into good solutions to the car racing problem: finding a controller that is able to win in a wide range of tracks and with a good quantity of opponents. Evaluating individual car controllers involves not only the design of a proper fitness function representing how good the car controller would be in a competitive race, but also the selection of the best solution for the optimization problem being solved; this decision might not be easy when uncertainty is present in the problem environment; in this case, weather and track conditions as well as unpredictable behavior of other drivers. Creating a methodology for the automatic design of the controller of an autonomous driver for a car racing simulator such as TORCS is an optimization problem which offers all these challenges. Thus, in this paper we describe an analysis and some proposals to improve the evaluation of optimized fuzzy drivers for TORCS over previous attempts to do so. It builds on preliminary results obtained in previous papers as a baseline and aims to obtain a more competitive autonomous driver via redesign of the fitness evaluation procedure; to this end, two different fitness functions are studied in several experiments, along with a novel race-based approach for the selection of the best individual in the evolution.

And the presentation is:

You can check our paper in the proceedings of the conference.

Enjoy it!

(And cite us as usual :D)

On Volunteer-Computing and Self-driving car fuzzy controllers in the sunny Cádiz

Every two years, the International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU) brings together the most important researchers in the area of uncertainty and fuzzy systems. As I am working in Cadiz, it was a great opportunity to present some of the latest work that the Geneura group has recently developed.

The first of these has been developed together with the Technical Institute of Tijuana and describes the social behaviour of users of a voluntary computer system. It is very interesting to discover how the use of a leaderboard makes users spend more time collaborating. Take  a look to the presentation:

Mario García Valdez, Juan Julián Merelo Guervós, Lucero Lara, Pablo García-Sánchez:
Increasing Performance via Gamification in a Volunteer-Based Evolutionary Computation System. IPMU (3) 2018: 342-353

Here is the abstract:

Distributed computing systems can be created using volunteers, users who spontaneously, after receiving an invitation, decide to provide their own resources or storage to contribute to a common effort. They can, for instance, run a script embedded in a web page; thus, collaboration is straightforward, but also ephemeral, with resources depending on the amount of time the user decides to lend. This implies that the user has to be kept engaged so as to obtain as many computing cycles as possible. In this paper, we analyze a volunteer-based evolutionary computing system called NodIO with the objective of discovering design decisions that encourage volunteer participation, thus increasing the overall computing power. We present the results of an experiment in which a gamification technique is applied by adding a leader-board showing the top scores achieved by registered contributors. In NodIO, volunteers can participate without creating an account, so one of the questions we wanted to address was if the need to register would have a negative impact on user participation. The experiment results show that even if only a small percentage of users created an account, those participating in the competition provided around 90% of the work, thus effectively increasing the performance of the overall system.

 

The second work uses an evolutionary algorithm to optimize the parameters of a fuzzy controller that drives a car in the TORCS video game and continues our previous work. We have been collaborating with Mohammed Salem of University of Mascara along this line for a while.

Mohammed Salem, Antonio Miguel Mora, Juan Julián Merelo Guervós, Pablo García-Sánchez: Applying Genetic Algorithms for the Improvement of an Autonomous Fuzzy Driver for Simulated Car Racing. IPMU (3) 2018: 236-247

Games offer a suitable testbed where new methodologies and algorithms can be tested in a near-real life environment. For example, in a car driving game, using transfer learning or other techniques results can be generalized to autonomous driving environments. In this work, we use evolutionary algorithms to optimize a fuzzy autonomous driver for the open simulated car racing game TORCS. The Genetic Algorithm applied improves the fuzzy systems to set an optimal target speed as well as the instantaneous steering angle during the race. Thus, the approach offer an automatic way to define the membership functions, instead of a manual or hill-climbing descent method. However, the main issue with this kind of algorithms is to define a proper fitness function that best delivers the obtained result, which is eventually to win as many races as possible. In this paper we define two different evaluation functions, and prove that fine-tuning the controller via evolutionary algorithms robustly finds good results and that, in many cases, they are able to play very competitively against other published results, with a more relying approach that needs very few parameters to tune. The optimized fuzzy-controllers (one per fitness) yield a very good performance, mainly in tracks that have many turning points, which are, in turn, the most difficult for any autonomous agent. Experimental results show that the enhanced controllers are very competitive with respect to the embedded TORCS drivers, and much more efficient in driving than the original fuzzy-controller.

 

A better TORCS driving controller presented in EvoStar 2018

Last year, we presented along with Mohammed Salem, from the university of Mascara, in Algeria, our TORCS driving controller. This controller effectively drives a simulated vehicle, considering input from its sensors, and deciding on a target speed and how to turn the steering wheel.

This year, in Evostar 2018 in Parma, we had again our paper accepted for the poster session, which took place in the incredible corridor to the right of these words. The poster included interactive elements, such as a small car used for demonstration on how the driver worked.

And it works really well, or at least better than the previous versions. The key element was the design of a new fitness function that includes damages, and also terms related to speed. Still some way to go; in the near future we will be posting our new results in this area.

The book of proceedings can be downloaded from Springer. Our paper is in page 342 and you can also download just the paper from here, but we do open science, so you can follow our writing process and download the paper from this GitHub repository too