Crónica seminario sobre coevolución

Esta mañana hemos dado el paper seminar sobre coevolución, con un lleno absoluto. Vamos a tener que cambiar a la sala de Juntas como sigamos así.
He aprovechado para hacer mi primera presentación en Prezi que no puedo empotrar porque me salen cosas raras finalmente he podido empotrar usando esta solución.

El trabajo no decepciona: es de los tiempos cuando en siete páginas se creaba no ya un algoritmo, sino una familia completa: los algoritmos coevolutivos. Y siendo del creador de Thinking Machines y uno de los padres fundadores de la vida artificial, tampoco. Por eso es fácil de entender: se trata de crear un algoritmo que diseñe redes de clasificación que sean mejores (que necesiten menos cambios) que las existentes. Y hacerlo usando evolución; pero la evolución no funciona, porque las redes se quedan estancadas clasificando bien el (limitado) conjunto de test que se les da, y de ahí no hay quien las saque. Así que para aumentar la diversidad y crear redes capaces de clasificar más pruebas en menos cambios, creó dos poblaciones: una de redes y otra de tests. Las redes tratan de clasificar contrimás mejor, y los tests pues justamente al reves. Al final no gana ni una ni otra, sino el autor que consigue pasar a la historia y aumentar su número H. Y nosotros también, con un algoritmo muy interesante que finalmente podremos aplicar a nuestro competidor en el reto Google de inteligencia artificial (próximamente en su congreso de confianza)

Paper Seminar: Co-evolving parasites improve simulated evolution as an optimization procedure

Mañana, a las 12:30 de la mañana y en la sala de Juntas, discutiremos el trabajo Co-evolving parasites improve simulated evolution as an optimization procedure, de W. Daniel Hillis, todo un clásico de la vida artificial, y escrito por la persona que creó la Connexion Machine, fue contratada por Disney y lideró la Long Now Foundation. Yo haré la presentación porque nadie se ha presentado voluntario, ni Carlos siquiera, que fue quien sugirió el trabajo.

Reactive Planning for RTS games

The paper “Reactive Planning Idioms for Multi-Scale Game AI” (Weber et al.), published last year in the proceedings of the IEEE Conference on Computation Intelligence and Games (CIG 2010), proposes a technique called reactive planning for designing a bot for Real-time strategy games (RTS). The agent is implemented in ABL (a behavioral language), an environment that allows the programmer to embed the multi-level reasoning that is required for efficient and complex RTS bots. A bot for RTS games (such as the StarCraft) must deal simultaneously with several goals, making intelligent high-level decisions while micromanaging units in combat, and ABL provides features such as daemons, messaging (memory), managers and micromanagement behaviors that can be of great help for such task. The authors propose a specific framework, for the structure of the bot and interfaces, and demonstrate that the resulting agent is able to beat the built-in StarCraft bot. However, when tested against moderately skilled human players, the agent performs poorly. As far as we understood, this work deals mainly with traditional Artificial Intelligence. The open question now is: can we model some kind of adaptive behavior in this ABL environment?

Paper Seminar: Reactive Planning Idioms for Multi-Scale Game AI

El viernes que viene, a las 12:30 y en la sala de reuniones de la ETSIIT, Carlos Fernandes hará una presentación sobre el trabajo Reactive Planning Idioms for Multi-Scale Game AI. En este seminario veremos cuáles son las claves de este trabajo en un ambiente más o menos informal, con el objetivo principal de aplicarlo a nuestra investigación sobre juegos en tiempo real

Environment-driven evolution in robot swarms

In the last Friday paper seminar we were discussing the paper:

which was presented at PPSN XI where we were attending as we mentioned.

Authors present a nice work on  swarm robotics where they try to evolve robot controllers using a fixed size population of autonomous robots. Evolution will take place in a decentralized fashion where no information on a possibly changing environment is provided. In that context, evolution is challenged to react to changes on-line and self-adapt to the environment without the global knowledge  on the problem that the fitness function would provide. That way “fitness” is implicit within the environment and the success criterion of a given strategy is defined as follows: one specific strategy is successful if it manages to spread over the population.

To that aim, authors propose mEDEA (minimal Environment-driven Distributed Evolutionary Adaptation), an intuitive algorithm which tackle the problem and tries to evolve controllers following a simple but elegant rule: those robot controllers that maximize the number of matings while preventing running out of energy will succeed on spreading their genomes.

Las GPUs no son para jugar

O al menos no todo el tiempo, también podemos hacer cosas ‘de provecho’ con ellas… :D

Como expuse en la reunión del pasado Viernes 24, ultimamente se estan adaptando y desarrollando muchos de los algoritmos que todos conocemos (AGs, GPs,  RNs, PSOs, etc), para el aprovechamiento de estas unidades de procesamiento, optimizadas para la computación en paralelo (de forma masiva, ya que cuentan con decenas o cientos de procesadores dedicados al cálculo en coma flotante).

En la siguiente presentación, se exponen sus ventajas e inconvenientes, así como se muestran algunas de las herramientas y APIs utilizadas para realizar dichas implementaciones, como por ejemplo CUDA.

Que la disfruteis! ;) :D

De nuevo, reunión con Mario Bros.

Antes de nada me presento, me llamo Vicente Ruiz y este es mi primer post para Geneura. La verdad es que soy un acopladillo, pero es placer :)

Este Viernes hemos hablado nuevamente de Mario Bros, entrando en detalles más internos a cerca de las distintas pruebas que hay en las competiciones:

  • Game Play
  • Learning (ya nos hubiera gustado…)
  • Level Generation

Aquí dejo la presentación para descargar (yo no sé poner las presentaciones tan chulas):

Mario IA Competition

Los temas principales que se han tratado han sido las reglas de cada una de las competiciones y por dónde se puede empezar a implementar. Aunque no hemos podido hablar de Learning Track debido a que no hay ningún tipo de información disponible en la página principal ni contestan los organizadores.

Las conclusiones a las que hemos llegado es que para Game Play, el algoritmo A* funciona muy bien, pero queda mucho trabajo por hacer (mucho más de lo que yo creía) y para Level Generation puede ser una posibilidad interesante (aunque el sistema de evaluación es muy subjetivo).

Y para terminar, os dejo aquí un enlace al Agente ganador del año pasado:

Reunión con Super Mario Bros.

El pasado Viernes dedicamos la reunión al increible mundo de Super Mario Bros. :O

No, aunque lo parezca no quedamos para echar unas partidillas con el reciente (y superviciante en multijugador) New Super Mario Bros. Wii. ;) :D

En lugar de eso hicimos una charla seria, con una presentación llena de rigor acerca de dicho personaje y centrándonos únicamente en la relevancia científica de las llamadas Mario AI Competitions.

La presentación es:

En ella se comentan varios aspectos a destacar de la ‘mascota’ de Nintendo, desde sus inciertos orígenes (hay varias teorías, una de las más sólidas se puede ver en ), pasando por su relevancia dentro del mundo de los videojuegos, hasta concluir con una descripción de sus posibilidades de estudio dentro del ámbito de la ciencia (en serio). ;)  :)

De ese modo, se presentan algunas de las competiciones relacionadas con la creación de agentes autónomos que ‘jueguen’ a Super Mario y/o ‘aprendan’ a jugar, así como la generación automática de niveles en base a los gustos/criterios de un jugador específico.

Para ello se trabaja con un Framework hecho en Java (aunque se puede programar también en Phyton) que contiene el código fuente de un clon de Super Mario Bros., y que es completamente editable.

En la reunión discutimos la línea de competición por la que nos íbamos a decantar, así como posibles ideas a implementar. ;)

Desde la reunión dedicada al porno (filtrado de contenidos en navegadores :D), no se había visto otra con tanta asistencia y participación (supongo que esperarían echar una partidilla al menos). ;) :D

Taluego!

FrikiMario

Porn recognition

Last friday I presented the work “Simple but Effective Porn Query Recognition” by Fu et al. to the rest of the group. I chose this paper because it adress an interesting investigation line. The porn. Yeah, it is a paper with “porn” in its title, so it is necessary to print, read and explain to others.

The authors claims that it is important for a search engine to filter porn to users, to avoid bad influence in children (nevertheless, queries with war and violence, and press control it is good to grow as a good human being, it seems). In China every query is
associated to a formal ID of the user, but this is another history, and must be told in another occasion.

This paper shows a way to measure similarity between queries. For example “gay movie” is porn and “bambi movie” is not porn, although they have a term in common. Another example is “Army comrade” and “gay image”, because in Chinese the term “comrade” has different meanings. Which you can imagine.

So, the autors propose to use all documents retrieved by the query to build a term vector of each document and obtain a compose vector for the query (the paper includes nice formulae). And this is how the semantical similarity measure works.

Once the semantical comparison is stablished, the authors use a k-NN algorith to classify the queries into two classes: Porn or Not-Porn (uhm… interesting…). So,  after a conducted training the algorithm sets the class of a new query comparing with the k more simillar, using the Euclidean distance of the feature vector.

Respecting the empirical studies, the authors uses their query repository (they work in a search engine company, Roboo Inc), so they have a real data to analyze. It is interesting to note that they chose 2000 random querys to test and the ratio of porn queries is higher than non-porn ones. So, as can be seen, I think it is not a good idea to filter to their potential clients that enormous and important information.

The authors also include some charts with data and numbers and stuff, and they adress the problem that sometimes (just a little) the algorithm category a non-porn query as porn (so P=NP!!!).

To finalize this post, I have to say that is a easy to read paper and, for a profane in text recognition like me, you can learn some basis of this research line. And also, it includes funny examples. Like “pretty nurse”. Yes. In China it is a porn query.

Tía en pelotas (alemana)! (o en tetas)
This photo was taken in Dortmund, when I was in the PPSN conference. I found it quite related with the content of this post.

You can read the paper in Google Docs. Thanks to my colleague José Urquiza, that was the discoverer of the paper ;)

Pablo G.

Evolution of Still Lifes

In the context of cellular automata, a still life is a stable pattern that does not change from one iteration to the next. Such patterns have mostly received attention with regard to Conway’s Game of Life. This conspicuous cellular automaton is characterized by the so-called 2333 rule: a cell remains alive only if it is surrounded by 2 or 3 live cells, and a new cell is born in any empty slot with exactly 3 alive neighbors. Therefore, any pattern intended to be a still life has to fulfill these contraints for each of its cells (alive or not). Although it is relatively easy to desing by hand some  small configurations verifying this stability property, coming up with a large still life is a very complex excercise.

Precisely due to the difficulty of designing large still lifes, this problem has become a very good benchmark to assess the effectiveness of constraint satisfaction algorithms. Actually, the problem is more than a mere CSP, since it also incorporates an optimality criterion: maximizing the number of live cells. This leads to the Maximum Density Still Life Problem (MDSLP).

The MDSLP has been traditionally tackled in the literature by different exact methods, in particular with a technique termed Bucket Elimination (BE). BE is a technique related to dynamic programming, based on the successive elimination of variables from the problem (this involves maintaining auxiliary memory structures to keep track of the optimal value of this variable for each combination of values of other variables the former is related -via constraints- to). In the case of the MDSLP, this technique benefits from the relatively simple structure of the constraint graph, but still has exponential complexity in time and space. It has nevertheless provided the best results in exactly solving the MDSLP [1], providing optimal solutions up to 20×20 patterns.

A completely different approach for finding MDSLs is using metaheuristic techniques. The first such approach was done by Gallardo et al. [2], using memetic algorithms (MA). This MA featured a dynastically optimal recombination operator based on BE, and a local-searcher based on tabu search (TS). The former is a restricted version of BE that considers the set of rows contained in the parents to be recombined,  and returns the best possible children that can be constructed using these. As to TS, it was used to improve every generated solution in short stints of n2 iterations. It was shown that an evolutionary algorithm  that did no use neither TS nor BE was incapable of providing a single feasible solution in most runs up from size 12. On the contrary a MA just featuring TS did consistently provide feasible solutions in all cases, and optimal ones for n < 15. Adding BE resulted in optimal solutions for n < 17.

A further step was taken in [3], considering a multilevel hybrid algorithm that incorporated beam search and the aforementioned MA. The use of superbuckets (a variable clustering technique) to reduce the cost of BE-based recombination was considered. It did not ultimately lead to better results, but helped in showing the usefulness of multiparent recombination.

A full-flegged approach incorporating multiparent BE-based recombination, and mini-buckets to compute lower bounds of incomplete solutions in the node-selection phase of beam search was finally reported in [4] (see also [5] for additional details). This algorithm was capable of obtaining optimal solutions up to size 20 (the largest known). For larger size only optimal symmetrical solutions are known up to size 28. Compared to these, the hybrid MA was capable of finding equal or better solutions; actually it provided new best-known solutions for for size 24 and 26. If symmetry constraints were enforced, the algorithm was capable of finding optimal solutions up to size 28.

References

[1] J. Larrosa, E. Morancho, D. Niso, On the practical use of variable elimination in constraint optimization problems: ‘still life’ as a case study. Journal of Artificial Intelligence Research 23:421–440, 2005

[2] J.E. Gallardo, C. Cotta, A.J. Fernández, A Memetic Algorithm with Bucket Elimination for the Still Life Problem, Evolutionary Computation in Combinatorial Optimization, J. Gottlieb, G. Raidl (eds.), pp. 73-85, Lecture Notes in Computer Science 3906, Springer-Verlag, Berlin Heidelberg, 2006

[3] J.E. Gallardo, C. Cotta, A. Fernández, A Multi-Level Memetic/Exact Hybrid Algorithm for the Still Life Problem, Parallel Problem Solving from Nature IX, T. Runarsson et al., pp. 212-221, Lecture Notes in Computer Science 4193, Springer-Verlag, Berlin Heidelberg, 2006

[4] J.E. Gallardo, C. Cotta, A.J. Fernández, Solving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms, Journal of Artificial Intelligence Research 35:533-555, 2009

[5] J.E. Gallardo, C. Cotta, A.J. Fernández, Finding Still Lifes with Memetic/Exact Hybrid Algorithms, arXiv:0812.4170, 2008