Posibles variables para el aprendizaje supervisado

De los datos obtenidos de los registros de los juegos podemos utilizar las siguientes variables para utilizarlas dentro del aprendizaje supervisado:

• Posición inicial y final del balón.
• Posición inicial y final de los jugadores propios/rivales.
• Cantidad de pases en la jugada.
• Número de jugadores involucrados en la jugada (jugadores que tuvieron contacto con el balón o que hicieron algún movimiento en la jugada).
• Duración de la jugada.
• Número de pases por jugada.
• Promedio de cercanía a los jugadores rivales respecto al balón.
• Promedio de distancia recorrida por los jugadores.

Promedio de distancia recorrida por el balón en cada pase.

Random Forests

Las características principales de este tipo de aprendizaje supervisado son:

• Se ejecutan de manera eficiente en grandes bases de datos.
• Puede manejar miles de variables sin eliminarlas.
• Brinda un estimado de cuáles son las variables más importantes en la clasificación.
• Genera un estimado del error de generalización mientras se construye el bosque.
• Tiene un método efectivo para estimar datos faltantes y logra mantener una buena precisión aunque falte una cantidad considerable de datos.
• Tiene métodos para balanceo del error de clases en conjuntos de datos desbalanceados.
• Los bosques generados pueden ser guardados para uso futuro en otros datos.
• Se computan prototipos que dan información sobre la relación de las variables y la clasificación.
• Computa proximidad entre pares de casos que pueden ser usados en clustering, encontrar valores atípicos o para proporcionar vistas de los datos.
• Se puede extender a datos sin clasificación y a aprendizaje no supervisado.
• Ofrece un método para la detección de la interacción entre variables.

Gracias al uso de este algoritmo se puede encontrar relaciones posibles entre las variables obtenidas de los logs de los juegos y la relevancia que estas tienen para el desarrollo de las jugadas. Además de que para un posible trabajo a futuro se pueden utilizar los bosques guardados para generar jugadas propias en base a los valores de relevancia de las variables y pasarlas por el mismo clasificador para predecir de cierta forma el posible éxito de la jugada.

Algoritmo de aprendizaje supervisado

Los algoritmos de aprendizaje supervisado son varios y según las pruebas realizadas por Caruana y Niculescu-Mizil (2006) sobre los algoritmos más populares que incluyen SVMs (máquinas de soporte vectorial), redes neuronales, regresión logística, naive bayes, árboles de decisión, etc. Logran concluir a partir de llevar a cabo varias pruebas y con respecto a métricas como lo son precisión, F-Score, ROC Area, punto de equilibrio, error cuadrático y cruce de entropía, el algoritmo que mejor desempeño general obtuvo.

Esta prueba había sido realizada previamente por el Statlog Project a inicios de la década de los 90’s sin embargo desde dicha prueba habían surgido nuevos algoritmos que parecían tener un mejor desempeño. Las pruebas se llevaron a cabo con un conjunto de cinco mil ejemplos y en los casos en los que aplicara, se realizaron pruebas con los algoritmos calibrados y sin calibrar.

Los resultados obtenidos postraron a los Calibrated Boosted Trees seguidos de cerca por los Random Forests. Debido a esta calificación y a las características de los Random Forest he determinado elegirlos como el algoritmo de aprendizaje que utilizaré.

Caruna, R., & Niculescu-Mizil, A. (2006). An empirical comparison of supervised learning algorithms. Proceedings of the 23rd international conference on Machine learning (págs. 161-168). Pittsburgh, Pennsylvania: ACM.

División del terreno de juego

La división del terreno de juego se ha determinado hacer de la siguiente forma a diferencia de la propuesta por el equipo Hanna en 2004 y por Myriam Arias en 2008 con el fin de que el cambio de zonas sea más sensible en las jugadas aunque podría cambiar si las divisiones no son suficientes.

Representación de las jugadas

Las jugadas consisten de dos archivos XML. Uno contiene las condiciones iniciales de las jugadas y el otro el desarrollo de las mismas. El primer archivo permite que la búsqueda de la jugada que se acomode mejor a las circunstancias del terreno de juego sea de manera eficiente al tener un tamaño de archivo reducido.

La estructura básica del primer archivo es la siguiente:

<PlayBook>
 <Play id=”1” duration=”5”>
  <Start>
   <Ball>
    <Zone>1</Zone>
   </Ball>
   <Player unum=”1” side=”l”>
    <Zone>1<Zone>
   </Player>
   <Player unum=”1” side=”l”>
    <Zone>1<Zone>
   </Player>
.
. (Todos los jugadores propios y del rival)
.
   <Player unum=”11” side=”r”>
    <Zone>1<Zone>
   </Player>
  </Start>
 </Play>
</PlayBook>

Mientras que la descripción de las jugadas se encuentra formado de la siguiente manera:

<PlayBook>
 <Play id =”1” duration=”5”>
  <Ball>
   <Time step=”1”>
   (Para cada tiempo en que cambie de zona el balón)
    <Zone>1</Zone>
   </Time>
  </Ball>
  <Player unum=”1” side=”l”>
   <Time step=”1”> 
   (Para cada tiempo en que cambie de zona el jugador
   o realice un kick)
    <Zone>1<Zone>
    <Kick>5</Kick>
    (Indica la zona a la que se debe
     enviar el balón)
   <Time>
  </Player>
.
. (Todos los jugadores propios)
.
  <Player unum=”11” side=”l”>
   <Time step=”1”> 
    <Zone>1<Zone>
    <Kick>5</Kick>
   <Time>
  </Player>
  <End>
  (Condiciones en las que término la jugada)
   <Ball>
    <Zone>5</Zone>
    (Zona en la que terminó el balón,
    dependiendo de esta se puede calificar
    la jugada)
   </Ball>
  </End>
 </Play>
</PlayBook>

Evaluación de las jugadas

La calificación de las jugadas será en base a la zona en que terminaron siendo así que mientras más cercanas al área rival tendrán una mejor calificación. Podría considerarse también la inclusión de la zona de inicio de la jugada como parámetro. Si la jugada termina con una anotación se deberá dar un peso o calificación especial.

Limpieza de jugadas

Duración de la jugada.- si hubo solo uno o dos pases posiblemente no sea una jugada sino una circunstancia.

Cambios en el estado de juego.- Difícil determinar el grado de éxito de la jugada ya que se pudo ver afectada por una falta cometida por otro jugador, por el final del partido o el final del primero de los dos tiempos.

Balón abandonó el terreno de juego (por los costados alejados de la portería contraria o en portería propia).- Posiblemente se dio mal un pase u ocurrió otra circunstancia que no permita determinar el valor de la jugada.

El balón es interceptado.- Si el balón es interceptado lejos del área rival aparte de cortar la jugada (por lo que lo registrado sería una jugada incompleta) podría también significar que no es una buena jugada.

Separación de las jugadas

• Inician con un kick de algún jugador del equipo al que se esté siguiendo.
• Posición del equipo.
• Posición del rival.
• Posición del balón.
• Jugador que inicia la jugada.
• Final de una jugada
• Kick o Catch de un oponente.
• El balón sale del terreno de juego.
• El árbitro marca una falta.
• Cambio en el estado de juego.

Acciones dentro de las jugadas

Kick – Existe un jugador en rango y realiza la acción kick (se incrementa el contador de dicha acción en el log).

Pass – Se determina como la existencia de dos kicks seguidos por parte de un mismo equipo (es decir no hubo otro kick intermedio de un rival, no se toma en cuenta las acciones como dash ya que no intervienen en el pase, sin embargo hay que considerar una posible marcación del árbitro que corte la jugada).

Intercepción – Se tiene cuando un equipo realiza un kick y el siguiente es dado por un rival por lo que se deduce que se perdió la posesión del balón.

Dash – Se determina con el movimiento de los jugadores en las zonas del campo.

Tackle – Determinar posteriormente como un medio para que el jugador la realice pero no como parte de la jugada.

RoboCup Logs

RoboCup Logs

La generación de logs por parte del servidor de RoboCup se realiza en forma automática al ejecutarse un juego y se forman tres archivos, RCG, RCL y LOG los cuales contienen la siguiente información según se ha visto:

• LOG: Contiene los mensajes arrojados por los equipos y por el mismo servidor, es prácticamente la salida a consola de ambos.
• RCL: Es un archivo en el que se indican las acciones de cada uno de los jugadores y el referee a lo largo de todos los ciclos del juego, se utilizan términos para describir cada acción como: init, turn, turn_neck, move, dash, kick entre otras.
• RCG: Es un archivo binario que contiene toda la información del juego, para poderse leer en un simple editor de texto se debe convertir a XML con el RCSSLOGPLAYER, este archivo indica las posiciones y velocidades de todos los elementos del terreno de juego, los parámetros de inicio de los jugadores, los parámetros del servidor, entre otras cosas.

Se ha encontrado un software que permite la recopilación de datos de los archivos XML generados por el RCSSLOGPLAYER de nombre VIENA, este funciona como un visor de los partidos pero permite un buen nivel de interacción y además genera una especie de análisis de los oponentes ya que se generan grupos de movimientos individuales con los cuales se generan jugadas comunes y surgen del análisis de los juegos.

VIENA
Documentación VIENA

Propuesta de Tesis

Subí el archivo a GoogleDocs:

propuesta.docx

gant

Secciones Propuesta

Secciones tentativas:

• Motivación
• Antecedentes
• Planteamiento del problema
• Justificación
• Trabajo propuesto
• Plan de Trabajo
• Identificación de Metas Parciales
• Calendarización de actividades
• Fuentes

Subsecciones del Estado del Arte

Estado del Arte

• Agentes Inteligentes y Sistemas Multiagentes
• Agente Inteligente
• Sistema Multiagente
• Comportamiento Social
• Simulación de Futbol Soccer
• Fira
• RoboCup
• Estrategias en Sistemas Multiagentes
• Definición de Estrategia
• Representación de Estrategias
• Modelado del Oponente
• Aprendizaje Automático
• Aprendizaje por Refuerzo
• Razonamiento Basado en Casos
• Selección de Planes

Continuación Estado del Arte

Agentes Inteligentes y Sistemas Multiagentes


Agente Inteligente

Se pueden definir a los agentes inteligentes como un sistema computacional que se encuentra en algún ambiente y que es capaz de llevar a cabo acciones autónomas dentro de dicho ambiente con el fin de lograr el objetivo por el que fue diseñado como indica Wooldridge (2002). Aunque como el mismo indica, no existe una definición que abarque todas las características que un agente pueda contener ya que estos pueden diferir en ciertas propiedades dependiendo del problema que atacan y de la implementación específica de su solución.

Los agentes deben cumplir con ciertas características para poder ser catalogados como inteligentes como definieron Wooldridge y Jennings (1995), dichas características son:

• Reactividad
• Pro actividad
• Habilidad social

La reactividad logra que los agentes puedan percibir su ambiente y los cambios del mismo para lograr reaccionar de forma acorde a ello. La pro actividad dentro de este concepto permite que cada agente tome cierta iniciativa para satisfacer su objetivo. Por último la habilidad social se emplea para que cada uno de los agentes pueda interactuar con sus semejantes para llevar a cabo su objetivo en común.

Además cada uno de los agentes debe cumplir con ciertas cualidades que son específicas de esta investigación como lo son la interacción con factores externos, la colaboración, el aprendizaje sobre cada una de las situaciones que se presenten dentro del ambiente y la colaboración con otros agentes reflejadas en estrategias adaptativas.

En el caso particular que se aborda en el cual existen agentes externos los cuales para este caso tienen un fin contrario al de nuestros agentes debemos asegurarnos que nuestros agentes sigan estos protocolos para su colaboración sin embargo habrá que definir una forma de lidiar con los agentes rivales.

Sistema Multiagente

El uso de sistemas multiagentes es un campo relativamente nuevo en cuanto al campo de la computación dado a que sus orígenes datan de la década de los 1990’s cuando se planteaba la posibilidad de resolver alguna situación utilizando pequeños componentes denominados agentes para lograrlo. El interés en desarrollar este tipo de sistemas empezó a crecer de una manera considerable haciendo que hoy en día sea objeto de atención de diversas publicaciones y conferencias.

Los agentes inteligentes son la base del desarrollo de los sistemas multiagentes, debido a que dependen completamente de estos ya que son los encargados de llevar a cabo tareas pequeñas e individualizadas para llegar a un objetivo de mayor complejidad que requiere de su colaboración para ser llevado a cabo con éxito.

Una propiedad fundamental en el desarrollo de los sistemas que incorporan agentes es la interacción de los mismos con el medio en el que se encuentran debido a que se espera que a cada acción realizada dentro del ambiente produzca una reacción en el mismo o una salida del sistema. Los agentes en la mayoría de los casos no tienen una vista global de su ambiente y tampoco ejercen un control total sobre el mismo, debido a esto no se puede asegurar que una acción realizada por un agente de forma idéntica dos veces tenga el mismo resultado o incluso que este sea correcto.

Un aspecto que se debe tomar en cuenta sobre el ambiente radica en que no en todos los casos se mantiene estático, es decir no cambia el estado de los elementos que lo conforman a menos que algún agente haga una acción directa sobre alguno de ellos. Tomando lo anterior a consideración debemos prever que el ambiente puede cambiar el entorno en el que se encuentran los agentes ya sea por la misma interacción de los agentes o por algún otro factor externo.

Retomando el contexto de sistemas multiagentes ahora que han sido definidos los agentes inteligentes que interactúan dentro del mismo, debemos tener otras consideraciones sobre el funcionamiento de este tipo de sistemas.

La principal característica y razón por la cual se optó por crear los sistemas multiagentes es la habilidad que tienen estos para resolver o simular problemas que necesitan de la intervención de distintos elementos con acciones autónomas y que sean capaces de tomar ciertas decisiones que los lleven a colaborar entre sí para llegar a un fin común. Debido a esto las áreas en donde los sistemas multiagentes pueden colaborar a la resolución de problemas es realmente extensa y entre las cuales encontramos ejemplos como lo son teoría de juegos, economía, biología, ambientes de aprendizaje, etc.

Las consideraciones sobre el ambiente en el cual se desenvuelven los agentes don prácticamente las mismas que se han expuesto en puntos anteriores agregando que al ser un ambiente compartido, este puede ser modificado por cualquiera de los agentes envueltos en él. Además en el enfoque dado en este documento se debe tomar en cuenta a los agentes externos y que ellos tienen la misma capacidad de modificar los elementos del ambiente que nuestros propios agentes.

Aunado a las consideraciones sobre el ambiente y mencionado el hecho de cómo pueden influir en el mismo los agentes externos, se debe recalcar otro aspecto el cual es la interacción entre agentes. Dado que se espera un resultado a cada acción llevada a cabo por los agentes, ahora dicho resultado depende de la combinación de acciones de cada uno de los agentes que intervengan. Esto puede alterar los resultados esperados y se debe tener un control o una forma de prever lo que pueda suceder así como posiblemente coordinarlo.

Comportamiento Social

Las acciones realizadas por los diversos agentes deben cumplir con los puntos anteriores y se logra de forma que cada agente tenga una noción sobre qué acciones conllevan el mejor resultado y son premiados con algún sistema de puntuación. Cada acción tiene cierto marcador y de esta forma pueden realizar la más adecuada para el momento en que se encuentran haciendo una evaluación de los pasos que deben seguir y el acumulado de puntos, también conocido como utilidad, que tendrán al finalizar cada posible camino que pueden tomar para llevar a cabo la labor.

Sin embargo la interacción de los agentes y los caminos que pueden tomar pueden interferir con las decisiones tomadas por el resto del conjunto. Esto se puede solucionar de diversas formas que comprenden las estrategias de interacción entre agentes, las cuales deben evaluar cada agente las opciones que tiene a seguir de forma que elija la que le sea más conveniente.

Normalmente en los sistemas multiagentes donde se busca llegar a una meta en común se emplean protocolos que se aseguran de ello y necesitan cumplir ciertos requisitos como lo son:

• Se garantiza el éxito del sistema si se asegura que eventualmente los agentes que están involucrados llegan a un acuerdo para realizar el trabajo.
• Se asegura que el resultado al que se llegue implique que se utilizaron los agentes de forma que todos lleguen a su máxima utilidad posible.
• El protocolo será pareto eficiente si se llega a una situación donde para cualquier agente no puede recibir una utilidad mayor sin disminuir la utilidad de algún otro agente.
• El protocolo debe ser individualmente razonable, esto es que siguiendo el protocolo cada agente tenga el conocimiento que siguiendo las reglas definidas en el sistema es la mejor forma de llegar a su utilidad.
• El protocolo debe asegurarse que exista estabilidad en el sistema, esto se logra dando incentivos a los agentes para que actúen de una manera que se busca y también se le conoce como el equilibrio de Nash.
• El protocolo debe ser simple asegurándose que cada agente al utilizarlo pueda determinar de una forma sencilla que estrategia debe seguir.
• Además el protocolo debe cerciorarse que no existe un punto de falla común, por ejemplo que no existe un solo árbitro o coordinador, así asegura esta propiedad también llamada como distribución.

Lo anterior es logrado por un sistema de comunicación que varía en cada implementación de sistemas multiagentes pero el cual tiene el fin de coordinar cada uno de los agentes. Esto resulta muy útil puesto que es lo más cercano que tienen los agentes a una visión global del ambiente con la cual pueden negociar y llevar a cabo la situación que mejor convenga a su desempeño.

Este sistema de comunicación se lleva comúnmente a cabo por el paso de mensajes en los cuales se indican datos relevantes para cada uno de los agentes. La estructura de dichos mensajes depende de cada implementación pero se conocen comúnmente dos representaciones:

• Knowledge Query and Manipulation Language (KQML)
• Knowledge Interchange Format (KIF)

Mientras que KQML se encuentra enfocado a la comunicación entre agentes como tal asegurándose de proveer una estructura que define destinatario, tipo de mensaje, etc., KIF se asegura de incluir la información sobre el entorno dentro de los mensajes, la parte relevante para la toma de decisiones.

La conjunción de estos elementos como se indica forman un sistema basado en la interacción de agentes lo cual ha sido objeto de estudio de numerosas investigaciones y presentado en competiciones en las que se demuestra el avance en este tipo de sistemas como los que se presentan a continuación.

Simulación de Fútbol Soccer

Existen diversos dominios en los que se pueden probar las teorías sobre nuevas técnicas de aprendizaje, negociación, colaboración y todo lo que interviene en el desarrollo de un sistema multiagente pero se ha tomado especial interés en escenarios que permitan y más específicamente obliguen a la interacción entre los miembros de un equipo que requieren llevar a cabo un objetivo, siendo así los deportes de conjunto los que proveen de esta característica además de incluir otra, muy relevante en cuanto a posibilidades de estudio, que resulta ser la interacción con un equipo rival.

Debido a las razones anteriores y a lo popular que se ha vuelto el fútbol alrededor del mundo, han surgido competiciones basadas en este dominio en las que se busca mantener de forma realista las características heredadas por el mismo dominio que incluye ser un ambiente de información incompleta, es un ambiente dinámico, se busca un objetivo, etc.

Además en general se busca desarrollar las áreas de estudio de los sistemas multiagentes como lo son el comportamiento reactivo, aprendizaje automático, coordinación entre agentes, percepción del ambiente, estrategias, etc.

Beneficios

A pesar de existir trabajos de investigación basados en el aprendizaje por refuerzo y otros en el modelado del oponente, no existe como tal un verdadero aprendizaje de conductas o estrategias de juego que engloben el comportamiento del equipo sino solo una serie de acciones individuales.

En esta propuesta de investigación se consideran los siguientes beneficios:

• Desarrollar un mecanismo de extracción de patrones de juego.
• Incorporar el manejo de un modelado del oponente como una estrategia global y no acciones individuales de cada agente.
• Continuidad a trabajos previos de estudiantes del Instituto Tecnológico y de Estudios Superiores de Monterrey, Campus Estado de México, relacionados al uso del razonamiento basado en casos.
• Mejorar el funcionamiento del equipo de simulación en 2D del mismo instituto.

Alcances y limitaciones

Los alcances de este proyecto se centran en la elaboración del mecanismo de extracción de patrones de juego que puedan ser representados en una base de conocimiento y que pueda ser aplicada al entorno de la competencia de simulación de RoboCup 2D.

El alcance de la investigación se encuentra limitado por lo siguiente:

• La base de conocimiento se formará a partir de registros de competiciones pasadas dentro del mismo entorno de simulación 2D de RoboCup.
• El agente líder o coordinador será determinado por el grado de participación en una jugada dependiendo de la posición del agente respecto al balón.
• La selección de las jugadas es inherente al estado actual del entorno y de ambos equipos al momento de ejecución y se clasificarán por eventos o condiciones.
• La selección de jugadas se llevará a cabo en base a la percepción actual que tengan los agentes dentro del campo de juego.
• Los agentes informarán sobre su posición con respecto a la cancha y de los adversarios adyacentes, esto con el fin de identificar de la base de estrategias la más adecuada de acuerdo a un margen o rango de posiciones.

Objetivos

El objetivo general de la presente investigación es diseñar, implementar y probar un mecanismo de extracción de patrones de juego que puedan ser representados en una base de conocimiento y que pueda ser aplicada a sistemas multiagentes (en el caso de las pruebas al ambiente de RoboCup) al considerar el comportamiento colectivo del equipo rival.

Los objetivos específicos se detallan a continuación:

• Investigar y seleccionar el método de aprendizaje por refuerzo por medio del cual se extraerán los patrones de juego y una manera comprensible en que puedan ser representados.
• Clasificación de las estrategias y patrones encontrados según su tipo, localización y disponibilidad de los agentes.
• Aplicar la metodología de razonamiento basado en casos para la selección de las jugadas.
• Comparar el comportamiento de un equipo con la aplicación de las estrategias aprendidas contra uno que no lo utiliza.

Inicio Estado del Arte

Agentes Inteligentes y Sistemas Multiagentes

Agente Inteligente

Se pueden definir a los agentes inteligentes como un sistema computacional que se encuentra en algún ambiente y que es capaz de llevar a cabo acciones autónomas dentro de dicho ambiente con el fin de lograr el objetivo por el que fue diseñado como indica Wooldridge (2002). Aunque como el mismo indica, no existe una definición que abarque todas las características que un agente pueda contener ya que estos pueden diferir en ciertas propiedades dependiendo del problema que atacan y de la implementación específica de su solución.

Los agentes deben cumplir con ciertas características para poder ser catalogados como inteligentes como definieron Wooldridge y Jennings (1995), dichas características son:

• Reactividad
• Pro actividad
• Habilidad social

La reactividad logra que los agentes puedan percibir su ambiente y los cambios del mismo para lograr reaccionar de forma acorde a ello. La pro actividad dentro de este concepto permite que cada agente tome cierta iniciativa para satisfacer su objetivo. Por último la habilidad social se emplea para que cada uno de los agentes pueda interactuar con sus semejantes para llevar a cabo su objetivo en común.

Además cada uno de los agentes debe cumplir con ciertas cualidades que son específicas de esta investigación como lo son la interacción con factores externos, la colaboración, el aprendizaje sobre cada una de las situaciones que se presenten dentro del ambiente y la colaboración con otros agentes reflejadas en estrategias adaptativas.

En el caso particular que se aborda en el cual existen agentes externos los cuales para este caso tienen un fin contrario al de nuestros agentes debemos asegurarnos que nuestros agentes sigan estos protocolos para su colaboración sin embargo habrá que definir una forma de lidiar con los agentes rivales.

Sistema Multiagente

El uso de sistemas multiagentes es un campo relativamente nuevo en cuanto al campo de la computación dado a que sus orígenes datan de la década de los 1990’s cuando se planteaba la posibilidad de resolver alguna situación utilizando pequeños componentes denominados agentes para lograrlo. El interés en desarrollar este tipo de sistemas empezó a crecer de una manera considerable haciendo que hoy en día sea objeto de atención de diversas publicaciones y conferencias.

Los agentes inteligentes son la base del desarrollo de los sistemas multiagentes, debido a que dependen completamente de estos ya que son los encargados de llevar a cabo tareas pequeñas e individualizadas para llegar a un objetivo de mayor complejidad que requiere de su colaboración para ser llevado a cabo con éxito.

Una propiedad fundamental en el desarrollo de los sistemas que incorporan agentes es la interacción de los mismos con el medio en el que se encuentran debido a que se espera que a cada acción realizada dentro del ambiente produzca una reacción en el mismo o una salida del sistema. Los agentes en la mayoría de los casos no tienen una vista global de su ambiente y tampoco ejercen un control total sobre el mismo, debido a esto no se puede asegurar que una acción realizada por un agente de forma idéntica dos veces tenga el mismo resultado o incluso que este sea correcto.

Un aspecto que se debe tomar en cuenta sobre el ambiente radica en que no en todos los casos se mantiene estático, es decir no cambia el estado de los elementos que lo conforman a menos que algún agente haga una acción directa sobre alguno de ellos. Tomando lo anterior a consideración debemos prever que el ambiente puede cambiar el entorno en el que se encuentran los agentes ya sea por la misma interacción de los agentes o por algún otro factor externo.

Retomando el contexto de sistemas multiagentes ahora que han sido definidos los agentes inteligentes que interactúan dentro del mismo, debemos tener otras consideraciones sobre el funcionamiento de este tipo de sistemas.

La principal característica y razón por la cual se optó por crear los sistemas multiagentes es la habilidad que tienen estos para resolver o simular problemas que necesitan de la intervención de distintos elementos con acciones autónomas y que sean capaces de tomar ciertas decisiones que los lleven a colaborar entre sí para llegar a un fin común. Debido a esto las áreas en donde los sistemas multiagentes pueden colaborar a la resolución de problemas es realmente extensa y entre las cuales encontramos ejemplos como lo son teoría de juegos, economía, biología, ambientes de aprendizaje, etc.

Las consideraciones sobre el ambiente en el cual se desenvuelven los agentes don prácticamente las mismas que se han expuesto en puntos anteriores agregando que al ser un ambiente compartido, este puede ser modificado por cualquiera de los agentes envueltos en él. Además en el enfoque dado en este documento se debe tomar en cuenta a los agentes externos y que ellos tienen la misma capacidad de modificar los elementos del ambiente que nuestros propios agentes.

Aunado a las consideraciones sobre el ambiente y mencionado el hecho de cómo pueden influir en el mismo los agentes externos, se debe recalcar otro aspecto el cual es la interacción entre agentes. Dado que se espera un resultado a cada acción llevada a cabo por los agentes, ahora dicho resultado depende de la combinación de acciones de cada uno de los agentes que intervengan. Esto puede alterar los resultados esperados y se debe tener un control o una forma de prever lo que pueda suceder así como posiblemente coordinarlo.

Comportamiento Social

Las acciones realizadas por los diversos agentes deben cumplir con los puntos anteriores y se logra de forma que cada agente tenga una noción sobre qué acciones conllevan el mejor resultado y son premiados con algún sistema de puntuación. Cada acción tiene cierto marcador y de esta forma pueden realizar la más adecuada para el momento en que se encuentran haciendo una evaluación de los pasos que deben seguir y el acumulado de puntos, también conocido como utilidad, que tendrán al finalizar cada posible camino que pueden tomar para llevar a cabo la labor.

Sin embargo la interacción de los agentes y los caminos que pueden tomar pueden interferir con las decisiones tomadas por el resto del conjunto. Esto se puede solucionar de diversas formas que comprenden las estrategias de interacción entre agentes, las cuales deben evaluar cada agente las opciones que tiene a seguir de forma que elija la que le sea más conveniente.

Normalmente en los sistemas multiagentes donde se busca llegar a una meta en común se emplean protocolos que se aseguran de ello y necesitan cumplir ciertos requisitos como lo son:

• Se garantiza el éxito del sistema si se asegura que eventualmente los agentes que están involucrados llegan a un acuerdo para realizar el trabajo.
• Se asegura que el resultado al que se llegue implique que se utilizaron los agentes de forma que todos lleguen a su máxima utilidad posible.
• El protocolo será pareto eficiente si se llega a una situación donde para cualquier agente no puede recibir una utilidad mayor sin disminuir la utilidad de algún otro agente.
• El protocolo debe ser individualmente razonable, esto es que siguiendo el protocolo cada agente tenga el conocimiento que siguiendo las reglas definidas en el sistema es la mejor forma de llegar a su utilidad.
• El protocolo debe asegurarse que exista estabilidad en el sistema, esto se logra dando incentivos a los agentes para que actúen de una manera que se busca y también se le conoce como el equilibrio de Nash.
• El protocolo debe ser simple asegurándose que cada agente al utilizarlo pueda determinar de una forma sencilla que estrategia debe seguir.
• Además el protocolo debe cerciorarse que no existe un punto de falla común, por ejemplo que no existe un solo árbitro o coordinador, así asegura esta propiedad también llamada como distribución.

Lo anterior es logrado por un sistema de comunicación que varía en cada implementación de sistemas multiagentes pero el cual tiene el fin de coordinar cada uno de los agentes. Esto resulta muy útil puesto que es lo más cercano que tienen los agentes a una visión global del ambiente con la cual pueden negociar y llevar a cabo la situación que mejor convenga a su desempeño.

Este sistema de comunicación se lleva comúnmente a cabo por el paso de mensajes en los cuales se indican datos relevantes para cada uno de los agentes. La estructura de dichos mensajes depende de cada implementación pero se conocen comúnmente dos representaciones:

• Knowledge Query and Manipulation Language (KQML)
• Knowledge Interchange Format (KIF)

Mientras que KQML se encuentra enfocado a la comunicación entre agentes como tal asegurándose de proveer una estructura que define destinatario, tipo de mensaje, etc., KIF se asegura de incluir la información sobre el entorno dentro de los mensajes, la parte relevante para la toma de decisiones.

Subsecciones del Estado del Arte

Estado del Arte

• Agentes Inteligentes y Sistemas Multiagentes
• Agente Inteligente
• Sistema Multiagente
• Comportamiento Social
• Simulación de Futbol Soccer
• RoboCup
• Estrategias
• Estrategia
• Representación de Estrategias
• Modelado del Oponente
• Aprendizaje Automático
• Aprendizaje por Refuerzo
• Razonamiento Basado en Casos
• Selección de Planes

Antecedentes (Tercera versión)

Los antecedentes directos a esta investigación están situados en los trabajos aplicados al evento RoboCup en el cual se organizan competiciones de partidos de futbol para probar avances en los sistemas multi-agentes. Al ser un evento a nivel mundial y con rondas clasificatorias (como si fuera un verdadero torneo de futbol) se logra poner a prueba cada nueva teoría o implementación que se realiza en las diversas instituciones de educación superior alrededor del mundo.

Independientemente del uso de robots físicos o simulaciones dentro de las pruebas de RoboCup, todas las competencias se encuentran basadas en sistemas multi-agentes donde cada agente representa a un jugador, aunque en este caso las pruebas e investigación se encuentran enfocadas a la competencia de simulación en 2D.

Debido a la complejidad e ineficiencia que implica indicar cada movimiento que los agentes pueden realizar dentro del campo de forma explícita, se emplean, en lo general, métodos de aprendizaje (como el basado en refuerzo) para que los jugadores conforme pase el tiempo de aprendizaje corrijan las acciones que llevan a cabo de forma incorrecta y perfeccionen hasta cierto grado los movimientos que pueden realizar.

Dentro de los avances encontrados, existe el uso del modelado del oponente como forma de evaluación en el modo de competencia de Coach debido a que se basa específicamente en los resultados que arroja dicho modelado. Sin embargo, en el caso particular de la competencia entre dos equipos sin el uso del agente Coach se ha hecho un modelado simplista y genérico en la mayoría de los casos.

El hecho de no lograr crear un modelado del oponente específico para un contrario en el tiempo de juego es debido a la poca interacción que existe dentro de cada partido ya que las interacciones entre ambos equipos son limitadas e insuficientes para lograr crear un modelo realista y confiable de la forma de jugar del rival (Stone, Riley, y Veloso, 2000). Debido a esto el modelado del oponente se ha basado en dos aproximaciones, la primera es contemplar un modelo predefinido de comportamientos individuales posibles de los rivales excluyendo así las estrategias de equipo y por otro lado se crean estrategias que incluyan posiciones posibles de los rivales y se procesan de distintas formas teniendo como ejemplo un CBR (Case Based Reasoning).

En el primer caso, se han logrado avances y algunas pruebas tanto en la competencia de RoboCup como en sistemas similares en entornos multi-agente empleando juegos de información incompleta como escenarios de pruebas (Parker, Nau, Subrahmanian 2006). En dichos escenarios se han probado distintas formas de asumir el comportamiento del rival de forma que siempre se tome en cuenta algún tipo de rival y no quede vació algún caso tomando como peor escenario el uso de un modelo genérico.

Del último caso, se han hecho avances en la definición de las estrategias dentro del equipo de robots cuadrúpedos del ITESM-CEM (Arias 2008) y su implementación dentro del terreno de juego sin lograr llevar a cabo pruebas contra equipos reales. Aunque las jugadas fueron definidas para una competición distinta, las bases de la misma son idénticas al tratarse de un mismo dominio (juego de soccer).

La base de la aplicación de las jugadas contenidas en el CBR en el caso del equipo del ITESM-CEM era conducida por uno de los mismos agentes que dentro del espacio y tiempo de juego es elegido como líder y lleva a cabo el reconocimiento del estado actual del campo y la comparación con los casos registrados en el libro de jugadas con tal de que elija la que se asemeje de forma apegada al estado actual del sistema.

El uso del libro de jugadas no es exclusivo del ITESM-CEM ya que otros equipos lo han llevado a cabo dentro de las competiciones de RoboCup (equipo AT Humboldt) y que han perfeccionado la elección de las jugadas de a cuerdo a cada situación en el campo. Sin embargo, no se especifica la manera de alimentar los casos considerados en el libro de jugadas.

Se puede observar que existen limitantes que conciernen a la misma forma en que se realiza el modelado del rival. Aunque existe y se busca el ideal de crear una representación de cada oponente a un nivel apegado a la realidad, aún no se ha logrado llevar a cabo en periodos cortos de interacción aun con dominios acotados de forma que las acciones conformen un conjunto mínimo y por ende sea de cierta forma sencilla su predicción (Del Giudice y Gmytrasiewicz, 2007).

Al considerar estos factores, se encuentra como deseable un modelo del oponente apegado a situaciones que asemejen con cierta precisión a la realidad del juego actual y que puedan ayudar a que se comprenda no solo las acciones individuales del contrario sino un nivel superior en cuanto a entendimiento siendo en el caso de RoboCup, la estrategia que emplea el equipo. Siendo esta una posible generalización de un conjunto de estrategias con características similares pero que logren englobar algunas de las formas en que se desempeña el equipo de forma que se tenga información sobre la reacción del mismo y deseablemente la manera en que puede ser contrarrestada o respondida.

Tercera Versión de Hipótesis

Existen modelos del oponente dentro de la competencia de simulación RoboCup 2D que abarcan acciones sencillas e independientes que no conforman una estrategia grupal. Se pretende crear una extracción de patrones de juego que logre englobar las jugadas más comunes en los equipos que existen actualmente y mediante aprendizaje por refuerzo generar una base de conocimiento (libro de jugadas) con las estrategias que se adapten al rival de forma que al momento del juego se puedan reconocer y emplear para mejorar los resultados en la competencia.

Antecedentes (Segunda versión)

Los antecedentes directos a esta investigación están situados en las investigaciones aplicadas al evento RoboCup en el cual se organizan simulaciones de partidos de futbol para probar avances en los sistemas multi-agentes. Al ser un evento a nivel mundial y con rondas clasificatorias (como si fuera un verdadero torneo de futbol) se logra poner a prueba cada nueva teoría o implementación que se realiza en las diversas instituciones de educación superior alrededor del mundo.

Independientemente del uso de robots físicos o simulaciones dentro de las pruebas de RoboCup, todas las competencias se encuentran basadas en sistemas multi-agentes donde cada agente representa a un jugador, aunque en este caso las pruebas e investigación se encuentran enfocadas a la competencia de simulación en 2D.

Dentro de los avances encontrados, existe el uso del modelado del oponente como forma de evaluación en el modo de competencia de Coach debido a que se basa específicamente en los resultados que arroja dicho modelado. Sin embargo, en el caso particular de la competencia entre dos equipos sin el uso del agente Coach se ha hecho un modelado simplista y genérico en la mayoría de los casos.

Es importante recalcar que lo anterior ha sucedido debido al poco tiempo de interacción existente dentro de cada partido ya que las interacciones entre ambos equipos son limitadas e insuficientes para lograr crear un modelo realista y confiable de la forma de jugar del rival (Stone, Riley, y Veloso, 2000). Debido a esto el modelado del oponente se ha basado en dos aproximaciones, la primera es contemplar un modelo predefinido de comportamientos individuales posibles de los rivales excluyendo así las estrategias de equipo y por otro lado se crean estrategias que incluyan posiciones posibles de los rivales y se procesan de distintas formas teniendo como ejemplo un CBR (Case Based Reasoning).

Del último caso, se han hecho avances en la definición de las estrategias dentro del equipo de robots cuadrúpedos del ITESM-CEM (Arias 2008) y su implementación dentro del terreno de juego sin lograr llevar a cabo pruebas contra equipos reales. Aunque las jugadas fueron definidas para una competición distinta, las bases de la misma son idénticas al tratarse de un mismo dominio (juego de soccer).

Se puede observar que existen limitantes que conciernen a la misma forma en que se realiza el modelado del rival. Aunque existe y se busca el ideal de crear una representación de cada oponente a un nivel apegado a la realidad, aún no se ha logrado llevar a cabo en periodos cortos de interacción aun con dominios acotados de forma que las acciones conformen un conjunto mínimo y por ende sea de cierta forma sencilla su predicción (Del Giudice y Gmytrasiewicz, 2007).

Al considerar estos factores, se encuentra como deseable un modelo del oponente apegado a situaciones que asemejen con cierta precisión a la realidad del juego actual y que puedan ayudar a que se comprenda no solo las acciones individuales del contrario sino un nivel superior en cuanto a entendimiento siendo en el caso de RoboCup, la estrategia que emplea el equipo. Siendo esta una posible generalización de un conjunto de estrategias con características similares pero que logren englobar algunas de las formas en que se desempeña el equipo de forma que se tenga información sobre la reacción del mismo y deseablemente la manera en que puede ser contrarrestada o respondida.

Overconfidence or Paranoia? Search in Imperfect-Information Games

En esta lectura se expone el uso de un algoritmo de búsqueda en conjuntos de información para juegos de información imperfecta (incompleta) en el que se espera lograr un mejor desempeño comparado al uso de investigaciones anteriores mencionadas dentro del mismo artículo.

Para mostrar el uso del algoritmo plantearon usar el juego de Kriegspiel en el cual, al igual en que la mayoría de juegos, se puede llevar a cabo un modelado del oponente y es un aspecto que toman en cuenta los autores para probar su algoritmo.

Para el modelado del oponente emplearon dos visiones distintas, el uso de una estrategia similar a la de mini-max pero adaptada para juegos de información imperfecta (modelo paranoico) en el cual asumen que el oponente siempre va a elegir la mejor opción y por otro lado emplearon un modelo en que las jugadas se deciden al azar (modelo de exceso de confianza).

Al momento de realizar las pruebas, el modelo de exceso de confianza obtuvo resultados más favorables y posiblemente es debido al mismo entorno del juego en el que ninguno de los dos jugadores conoce realmente los movimientos del contrario por lo que deducir la mejor estrategia del rival no siempre (visto por los resultados, casi nunca) se emplea la jugada determinada como mejor, en cambio al modelarlo como jugadas al azar, si bien es cierto que esto impide realmente deducir una estrategia del rival, se obtiene una mayor probabilidad de alguna manera obtener un resultado más parecido a la realidad.

Parker, A., Nau, D., & Subrahmanian, V. (2006). Overconfidence or Paranoia? Search in Imperfect-Information Games. The Twenty-First National Conference on Artificial Intelligence (págs. 1045-1050). Boston: AAAI.

Safe Strategies for Agent Modelling in Games

Esta lectura trata un problema encontrado al momento de realizar el modelado del oponente y el cual, aun siendo un posible factor crítico en el transcurso de la ejecución del sistema, es de alguna forma obviado por la mayoría de sistemas.

Este problema radica en la imposibilidad de realizar un buen modelado del oponente debido a las características que este posea, pudiendo ser este demasiado complejo para ser modelado, no se tiene suficiente información, el rival está empleando un modelo del oponente que se adapta a los cambios que nuestro mismo agente realiza, entre otras posibles circunstancias.

Teniendo esto a consideración es posible que los agentes tomen decisiones incorrectas o improductivas debido a que están basadas en el conocimiento que tienen sobre el oponente actualmente. En este caso y como es propuesto, se deben emplear una serie de acciones o estrategias seguras que permitan de cierta forma maximizar la recompensa obtenida.

Los autores desarrollaron un algoritmo (basados en el algoritmo No Regrets) que permiten llevar a cabo esta tarea y asegurar que el resultado obtenido cuando no se logró realizar el modelado del oponente de forma correcta sea mejor que cuando se toma en consideración un modelo erróneo.

El algoritmo no solo busca la maximización del resultado propio sino que propicia que la ganancia del rival sea más pequeña. Esto fue probado con la simulación de un torneo de piedra-papel-tijeras (competición RoShamBoo) empleando en todos los casos el algoritmo implementado en cada uno de los equipos.

Los resultados muestran que el desempeño de los agentes que logran hacer un buen modelado del oponente, no son alterados substancialmente y por otra parte los agentes que se benefician de dicho algoritmo son aquellos que habían conseguido originalmente los peores lugares. Sin embargo, se menciona que el algoritmo tiene dificultades al ser empleado en sistemas en los que la recompensa obtenida no es inmediata.

McCracken, P., & Bowling, M. (2004). Safe Strategies for Agent Modelling in Games. AAAI 2004 Fall Symposia. Virginia: AAAI.

Batch Reinforcement Learning in a Complex Domain

Este artículo habla del uso de un tipo de algoritmos de aprendizaje por refuerzo como alternativa a los algoritmos tradicionales para lograr una convergencia rápida en cuanto al aprendizaje. Se emplea un medio complejo que implique de forma tradicional un enorme número de iteraciones en los algoritmos para completar su aprendizaje.

Los algoritmos de lote (batch) a diferencia de los algoritmos tradicionales de aprendizaje por refuerzo, toman en cuenta todo el historial de pasos que se han llevado a cabo para el aprendizaje en lugar de modificar sus valores empleando solo la última iteración.

Para este caso decidieron utilizar RoboCup Keepaway (previamente expuesto por Peter Stone y otros autores previamente) para probar el uso de los algoritmos de lote. Para las pruebas realizadas decidieron utilizar los algoritmos de aprendizaje siguientes: Online Learning (OL), Experience Replay (ER) y Fitted Q-Iteration (FQI) implementados de dos maneras distintas, empleando CMAC tile coding y redes neuronales.

Los resultados obtenidos se basan en las pruebas prácticas del tiempo que logran retener el balón los jugadores respecto al número de iteraciones realizadas. Los autores resaltan que la convergencia de los algoritmos basados en las implementaciones con CMAC solo convergen en situaciones específicas y aunque se pueden obtener buenos resultados con ellos no siempre se puede asegurar dicha convergencia. Por otra parte también se menciona que el paso de aprendizaje para ER por lo que un análisis detallado sobre este es requerido al llevar a cabo la implementación.

Los resultados como eran esperados reflejan que el uso de los algoritmos de lote obtienen mejores resultados en un tiempo corto aunque existe el caso especial del FQI implementado con CMAC jamás obtiene resultados en los que el jugador pueda retener el balón por más de 8 segundos. Por otra parte, se reduce el tiempo considerablemente hasta en 14 veces (aproximadamente).

Kalyanakrishnan, S., & Stone, P. (2007). Batch Reinforcement Learning in a Complex Domain. Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems (págs. 662-669). New York: ACM.

Reinforcement learning in simulation RoboCup soccer

Este artículo habla de los beneficios que implica el uso del aprendizaje por refuerzo en un ambiente como lo es RoboCup debido a la dificultad que implica el considerar una programación de manera estática en la que se le indique al agente que debe realizar según ciertas circunstancias.

Un punto distinto en cuanto a la implementación del aprendizaje por refuerzo es que en este caso no solo se emplea para desarrollar habilidades básicas del jugador sino que la función de recompensa se basa en el bienestar (cumplimiento del objetivo) del grupo siendo así de alguna manera implica la colaboración del equipo.

Se divide el equipo en grupos pequeños en los que se encuentra un jefe y sus subordinados siendo el jefe el que es capaz de aprender las acciones que realiza y cuáles son las mejores opciones y los subordinados se encargan simplemente de apoyar o realizar las acciones de pide el agente jefe. Para el caso planteado en la lectura, el agente jefe es aquel agente que se encuentre con la posesión del balón.

Sin embargo, la recompensa que recibe el agente no la conoce por sí mismo y para conocer si sus acciones se desenlazaron en un beneficio al grupo debe existir comunicación entre sus integrantes para conocer el resultado de sus acciones.

Xian-Yi, C., Xiao-Hua, Y., Ling-Han, P., & De-Shen, X. (2004). Reinforcement learning in simulation RoboCup soccer. Conference on Machine Learning and Cybernetics, 2004. Proceedings of 2004 International (págs. 244 - 248). Shanghai, China: IEEE.

Scaling Reinforcement Learning toward RoboCup Soccer

Este es un artículo por Peter Stone sobre el rubro de RoboCup en el cual se reduce el enfoque del juego a uno más sencillo. En este caso se emplean dos equipos pero el objetivo del juego no se basa sobre un partido de fútbol real sino en que el equipo que inicia con el balón tratará de retenerlo la mayor cantidad de tiempo posible y el equipo contrario por su parte tratará de robarlo.

El final del juego se declara cuando el balón abandona el espacio indicado (campo de juego) o cuando un jugador del equipo contrario obtiene el balón. Para ambos equipos se emplea un sistema de recompensa de acuerdo al objetivo de cada equipo.

Para el aprendizaje emplearon el algoritmo SARSA (parte de tile coding) en el cual se van ajustando los pesos según las recompensas obtenidas en cada uno de los estados en que se encuentra el sistema de modo que por medio de un número dado de iteraciones cada agente aprende cual es la mejor opción a seguir.

Al final se muestra que existe mejoría respecto a políticas previamente establecidas (estáticas) y como mediante las iteraciones aumentan, disminuye la probabilidad de fallar en el objetivo del equipo.

Stone, P., & Sutton, R. (2001). Scaling Reinforcement Learning toward RoboCup Soccer. The Eighteenth International Conference on Machine Learning (págs. 537-544). Williamstown: ICML.

Segunda Versión de Hipótesis

Aunque existen modelos del oponente dentro de la competencia de simulación RoboCup 2D, estos abarcan acciones sencillas e independientes que no conforman una estrategia como tal. Se pretende crear una extracción de patrones de juego que logre englobar las jugadas más comunes en los equipos que existen actualmente y generar una base de conocimiento (libro de jugadas) con las estrategias que se adapten a la estrategia del rival de forma que al momento del juego se puedan emplear para mejorar los resultados en la competencia.

Antecedentes

Los antecedentes directos a esta investigación están situados en las investigaciones aplicadas al evento RoboCup en el cual se organizan simulaciones de partidos de futbol para probar avances en los sistemas multi-agentes. Al ser un evento a nivel mundial y con rondas clasificatorias (como si fuera un verdadero torneo de futbol) se logra poner a prueba cada nueva teoría o implementación que se realiza en las diversas instituciones de educación superior alrededor del mundo.

Independientemente del uso de robots físicos o simulaciones dentro de las pruebas de RoboCup, todas las competencias se encuentran basadas en sistemas multi-agentes donde cada agente representa a un jugador, aunque en este caso las pruebas e investigación se encuentran enfocadas a la competencia de simulación en 2D.

Dentro de los avances encontrados, existe el uso del modelado del oponente como forma de evaluación en el modo de competencia de Coach debido a que se basa específicamente en los resultados que arroja dicho modelado. Sin embargo, en el caso particular de la competencia entre dos equipos sin el uso del agente Coach se ha hecho un modelado simplista y genérico en la mayoría de los casos.

Es importante recalcar que lo anterior ha sucedido debido al poco tiempo de interacción existente dentro de cada partido ya que las interacciones entre ambos equipos son limitadas e insuficientes para lograr crear un modelo realista y confiable de la forma de jugar del rival (Stone, Riley, y Veloso, 2000). Debido a esto el modelado del oponente se ha basado en dos aproximaciones, la primera es contemplar un modelo predefinido de comportamientos individuales posibles de los rivales excluyendo así las estrategias de equipo y por otro lado se crean estrategias que incluyan posiciones posibles de los rivales y se procesan de distintas formas teniendo como ejemplo un CBR (Case Based Reasoning).

De lo anterior se puede observar que existen limitantes que conciernen a la misma forma en que se realiza el modelado del rival. Aunque existe y se busca el ideal de crear una representación de cada oponente a un nivel apegado a la realidad, aún no se ha logrado llevar a cabo en periodos cortos de interacción aun con dominios acotados de forma que las acciones conformen un conjunto mínimo y por ende sea de cierta forma sencilla su predicción (Del Giudice y Gmytrasiewicz, 2007).

Al considerar estos factores, se encuentra como deseable un modelo del oponente apegado a situaciones que asemejen con cierta precisión a la realidad del juego actual y que puedan ayudar a que se comprenda no solo las acciones individuales del contrario sino un nivel superior en cuanto a entendimiento siendo en el caso de RoboCup, la estrategia que emplea el equipo. Siendo esta una posible generalización de un conjunto de estrategias con características similares pero que logren englobar algunas de las formas en que se desempeña el equipo de forma que se tenga información sobre la reacción del mismo y deseablemente la manera en que puede ser contrarrestada o respondida.

Reinforcement Learning of Player Agents in RoboCup Soccer Simulation

En esta lectura se establece el uso del aprendizaje por refuerzo como una posible técnica para la mejora del comportamiento de los agentes dentro de los sistemas multi-agentes debido a su capacidad de, en un determinado lapso de tiempo, desarrollar de cierta manera habilidades que permiten a los actores de los sistemas desempeñarse.

De esta forma utilizan este tipo de aprendizaje en el ambiente de simulación 2D de RoboCup para que los jugadores aprendan y en dado caso mejoren su habilidad de interceptar pases del rival. Se emplea el uso de recompensas en el que el acierto (en este caso la intercepción del balón) otorga una recompensa (un valor de 1) y en otro caso se da el valor mínimo (0).

De lo anterior el agente construye una serie de estados con cierta probabilidad de intercepción dependiendo del movimiento que realice el jugador. Los resultados mostraron que se puede apreciar de forma clara que la habilidad de intercepción mejoró respecto a la que ellos habían codificado manualmente a partir de una hora de constante entrenamiento con el método expuesto.

Sarje, A., Chawre, A., & Nair, S. (2004). Reinforcement Learning of Player Agents in RoboCup Soccer Simulation. Fourth International Conference on Hybrid Intelligent Systems (págs. 480-481). Kitakyushu, Japan: IEEE.

Heuristic Reinforcement Learning applied to RoboCup Simulation Agents

Se menciona el creciente uso de técnicas de aprendizaje por refuerzo para diversas áreas y en particular el uso del Q-Learning debido al interés que genera por una característica intrínseca del mismo que consiste en que en algún momento se convergerá al estado óptimo de aprendizaje.

Sin embargo, como la mayoría de algoritmos, este requiere cierto número de interacciones para lograr llevar a cabo el aprendizaje las cuales sobrepasan el número natural de encuentros dentro de un juego de un ambiente como lo es el de RoboCup. Por ello, en este artículo se propone el uso de una evolución de Q-Learning llamado HAQL (Heuristic Accelerated Q-Learning).

Este algoritmo en principio comparte una cantidad significante de características con el Q-Learning original pero con una mejora al momento de llevar a cabo el aprendizaje ya que este es guiado por una heurística que influye en las decisiones que toma el agente durante el mismo periodo de aprendizaje de modo que se define una política de heurísticas que permite que el aprendizaje se lleve a cabo en un menor tiempo.

Para las pruebas realizadas en un ambiente que incluye a un equipo defendiendo su portería y otro atacándolo en el que se empleo el aprendizaje para la parte defensora, se logra ver que el uso de HAQL permite que los resultados positivos lleguen en una menor cantidad de interacciones que empleando Q-Learning. Sin embargo, mientras se aumenta el número de interacciones, los resultados se vuelven simulares debido a que el aprendizaje en Q-Learning converge.

Celiberto, L., Ribeiro, C., Reali Costa, A. H., & Bianchi, R. (2008). Heuristic Reinforcement Learning applied to RoboCup Simulation Agents. En RoboCup 2007: Robot Soccer World Cup XI (págs. 220-227). Berlin: Springer Berlin / Heidelberg.

Opponent Modeling in Scrabble

En este artículo se toma como base al juego del Scrabble para mostrar lo útil que puede llegar a ser tener un modelo del oponente para poder hacer una elección de jugadas. El juego en sí comprende un medio parcialmente observable debido a que lo único que cada jugador puede observar son sus fichas y las acomodadas en el tablero, teniendo como incógnita las que se encuentran del lado del oponente y las restantes halladas en un saco.

Como indica el autor lo natural parece ser emplear un POMDP (Partially Observable Markov Decision Process) pero este se convierte en un problema intratable al no contener cantidades reducidas de estados como lo es el juego del Scrabble. Debido a lo anterior, se asume el uso de otra técnica que si bien sacrifica precisión en la solución del problema, implica también una mayor simplicidad y más relevante, una manera de modelar en un tiempo razonable.

Para efectos del experimento se asume que el juego será llevado a cabo entre dos computadoras (por ende entre dos jugadores), no se utilizan estrategias como lo es el Bluff, se emplean solo palabras que son legales en este tipo de juego y el paso a un ambiente con información conocida no se toma en cuenta (esto ocurre al final del juego cuando no quedan fichas en la bolsa o saco de reserva).

Se utiliza el teorema de Bayes para llevar a cabo las funciones de probabilidad sobre las posibles fichas con las que cuenta el oponente basado en las tiradas que ha realizado. Es decir, si ha formado una palabra y al tener en cuenta que el oponente no es humano, se considera que su salida o tiro se basa únicamente en que se realizó intentando obtener el mayor puntaje en dicha jugada. Teniendo lo anterior en cuenta, se descartan las letras que pudieron haber formado una palabra con mayor puntaje armando así una posible combinación de las letras que se acaban de poner en juego y las que posiblemente aun tengan en su conjunto el rival.

Basado en las posibles combinaciones de fichas que puede tener en el momento actual el rival, se procede a hacer las jugadas que el propio jugador crea convenientes y en los resultados en la experimentación realizada, se encontró que el promedio tanto de puntos como de juegos ganados aumento respecto a emplear otras estrategias tradicionales.

Richards, M., & Amir, E. (2007). Opponent Modeling in Scrabble. Twentieth International Joint Conference on Artificial Intelligence (págs. 1482-1487). Hyderabad, India: IJCAI.

Sitio Reinforcement Learning

Encontré un sitio en el cual se encuentran varios papers sobre aprendizaje por refuerzo que pueden ser útiles:

http://www.fei.edu.br/~rbianchi/publications-full.html

Improving Offensive Performance Through Opponent Modeling

Este artículo habla sobre la utilidad de emplear el modelado del oponente no solo a un nivel individual en el que se intente predecir los movimientos básicos de los rivales sino de reconocer y contrarrestar la estrategia del equipo contrario. Esto es aplicado al ambiente de futbol americano.

Se toman como antecedentes varias competiciones y entre ellas a RoboCup pero se menciona que el modelado del oponente se realiza tradicionalmente en la modalidad de Coach en la cual se hace aprendizaje offline y su utilidad radica más entre partido y partido que dentro de un solo juego.

Se divide al modelado del oponente en tres clasificaciones:

• Seguimiento Online – Aquí se desglosan los movimientos de más bajo nivel intentando predecir acciones individuales como el avance de un jugador, pases, etc.
• Reconocimiento de Estrategia Online – Este es un nivel más elevado del anterior ya que se intenta identificar las acciones del equipo rival como una estrategia enfocada a un objetivo.
• Revisión Offline – Esta es la fase de entrenamiento y aprendizaje que se realiza fuera del tiempo de juego.

El objetivo fundamental del desarrollo expresado en el artículo es aprovechar la parte del reconocimiento de estrategias para lo cual emplean un clasificador que les permite discriminar entre las opciones contenidas en su libro de jugadas y que resulte ser la mejor opción para llevar a cabo el ataque.

Se emplea una SVM (Support Vector Machine) de tipo multi-clase que a su vez contiene una colección binaria de 26 SVM binarias. Se elige la SVM multi-clase dependiendo del estado actual de los jugadores y el tiempo de la jugada. Con estos datos se procede a adaptar el equipo y que este adopte la formación que mayor ganancia signifique en cuanto a yardas obtenidas.

Los resultados demostraron una mayor efectividad en cuanto al ataque obteniendo una mejoría del 29% respecto a las yardas obtenidas comparando este tipo de estrategia contra métodos tradicionales que intentan maximizar el mismo parámetro.

Laviers, K., Sukthankar, G., Molineaux, M., & W. Aha, D. (2009). Improving Offensive Performance Through Opponent Modeling. Proceedings of the Fifth Artificial Intelligence for Interactive Digital Entertainment Conference (págs. 58-63). Stanford, California: AAAI.

Towards Strategic Kriegspiel Play with Opponent Modeling

Este es un artículo en el que muestran el uso del modelado del oponente en una situación en que no se conoce el estado actual del oponente como sucede en algunos tipos de problemas. Para lo anterior emplearon Kriegspiel que es una versión modificada del ajedrez tradicional en la cual cada jugador no conoce la ubicación de las piezas del contrario y los movimientos son evaluados por un árbitro que indica si estos son legales o no y que consecuencias producen.

Debido al costo computacional de llevar a cabo el modelado se decidió reducir tanto el tamaño del tablero (a tan solo una dimensión de cuatro por cuatro casillas) y el número de piezas (se empleo solo el rey y la reina). Aun con esta reducción se obtiene alrededor de 74 mil posibles combinaciones de estados a lo largo del juego.

Para el desarrollo del juego se emplean I-POMDP (Interactive Partially Observable Markov Decision Processes) para cada agente, lo cual está formalmente definido por:

I-POMDP = {IS, A, T, Ω, O, R}

• IS – Es el estado interactivo el cual está definido por el cruce entre los estados físicos (configuraciones del tablero S) y los posibles modelos del oponente.
• A – Es el cruce entre las acciones posibles del agente propio y el oponente.
• T: S x A x S --> {0,1} – Es la función de transición que representa la influencia de los agentes con el ambiente.
• Ω - Es el conjunto que contiene las respuestas posibles del referee.
• O: S x A x Ω -->{0,1} – Es la función de observación del referee que dicta que respuesta debe brindar.
• R: S x A --> R – Es la función de recompensa asociada a uno de los estados finales del juego (victoria, empate o derrota).

Se emplea una red bayesiana para elegir la jugada que realizara el agente teniendo en cuenta las probabilidades y los pesos de elegir una opción respecto a que el oponente pueda elegir otra de forma que se cuantifica cada posibilidad.

Del Giudice, A., & Gmytrasiewicz, P. (2007). Towards Strategic Kriegspiel Play with Opponent Modeling. AAAI Spring Symposia. Stanford, California: AAAI.

Opponent Modeling by Analyzing Play

Este artículo presenta si bien una introducción al tema del modelado del oponente, también considera algunas ideas prácticas que se puede obviar en ciertos momentos pero que son fundamentales para saber si lo que se realiza se encuentra enfocado correctamente.

Las ideas básicas detrás del modelado del oponente se basan en lo que cualquier ser humano realiza cuando se enfrenta a algún contrincante en un juego por simple que este sea. Por ejemplo en el póquer, aunque no se conozca al rival conforme va avanzando el juego vas entendiendo su forma de apostar durante el juego y como contestar a ello.

También se menciona que se debe decidir qué características del oponente son las que se tomarán en cuenta para llevar a cabo el modelo ya que puede que existan algunas que no proporcionen información que permita llevar a cabo el entendimiento de su comportamiento y que sean simplemente insignificantes, por el contrario si se omite algún elemento relevante entonces posiblemente el modelo que se lleve a cabo sobre el contrario contenga información incompleta y menos útil que si se hubiese tomado la variable omitida.

Pasando estas bases se mencionan algunas formas de modelado entre las que se encuentran el uso del modelo de un oponente promedio, el modelado particular de cada oponente y otro que llamo en particular mi atención que consiste en después de haber realizado el modelado promedio de los rivales, complementarlo con acciones específicas que dependan de cada adversario con el que se encuentre compitiendo.

Para probar lo anterior hacen uso de un clasificador (C4.5) con el sistema TILDE basados en el juego Go. Realizaron pruebas básicas y midiendo los resultados dependiendo de cuantas jugadas fueron analizadas mostrando una mejoría cuando se alimento al sistema con más información.

Jan, R., Jacobs, N., & Blockeel, H. (2002). Opponent Modeling By Analysing Play. Proceedings of Workshop on agents in computer games. Edmonton, Canada: AAAI.

Aprendizaje por Refuerzo

En el aprendizaje por refuerzo se busca que una entidad aprenda cuál es la mejor decisión que puede tomar y llevarla a cabo mediante un sistema de recompensa. Debido a que no se indica inicialmente cuál es la mejor opción que se puede tomar, se deben llevar a cabo varias iteraciones de la tarea sobre la que se basa el aprendizaje para poder generar un conocimiento correcto.

Para el modelado de este tipo de aprendizaje se debe tomar en cuenta los estados y las acciones posibles. En los estados se determinan las posibles situaciones que se pueden presentar en el sistema, mientras que en las acciones se describen los actos que el sistema puede llevar a cabo en cada uno de los estados. El fin de lo anterior es encontrar la mejor acción posible para cada una de los estados del sistema y que este reaccione de la forma más conveniente a lo que se le puede presentar.

Una característica de este estilo de aprendizaje es que se considera al problema completo como dirigido a una meta y que se desenvuelve en un entorno incierto (posiblemente cambiante). Además se le considera como un aprendizaje basado en la interacción. Debido a esto también se le considera como aprendizaje no supervisado ya que es impráctico intentar obtener muestras representativas y útiles de las situaciones que se pueden presentar en los ambientes estudiados por este tipo de aprendizaje.

http://webdocs.cs.ualberta.ca/~sutton/book/ebook/the-book.html

Logs de Equipos

Encontré algunos logs de las competencias de RoboCup en línea por lo que es posible obtenerlos, falta analizarlos a detalle pero en general parecen incluir la comunicación con el servidor, entre los agentes y las acciones de los mismos.

Algunos sitios que encontré son:

http://202.141.161.27/results_09/
http://202.141.161.27/results/
http://www.ni.uos.de/index.php?id=990

Buscador Científico

Hoy durante la presentación de Sciende Direct y nos mencionaron su página accesible mediante las ligas en www.cem.itesm.mx/bibloteca y se nos mencionó otro buscador interesante de nombre Scirus que pueden ser útiles.

Emotion-based Norm Enforcement and Maintenance in Multi-Agent Systems: Foundations and Petri Net Modeling

Este artículo brinda una base para la modelación de los sistemas multi-agentes empleando emociones y la forma en que estas intervienen en el accionar social del sistema.

Se emplean redes Petri para mostrar los modelos de los agentes involucrados en el sistema en el que se incluye la representación de las normas sociales y la forma en que se reacciona si alguna acción relacionada con ellas es llevado a cabo, por ejemplo el violar alguna de las mismas.

El objetivo de emplear emociones en un sistema multi-agente es el poder hacer que los agentes reaccionen de modo distinto dependiendo de los eventos producidos a lo largo de la ejecución del sistema y que esto a su vez sea provechoso para el agente y el sistema a la vez, brindando otro mecanismo de adaptación para los SMA.

Fix, J., von Scheve, C., & Moldt, D. (2006). Emotion-based norm enforcement and maintenance in multi-agent systems: foundations and petri net modeling. Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems (págs. 105-107). Hakodate, Japón: ACM.

Effective Short-Term Opponent Exploitation in Simplified Poker

En esta lectura se aborda el tema parecido al anterior, el modelado del oponente con pocos datos de entrada para realizar el aprendizaje sobre sus estrategias. En este caso se emplea el póquer como base (una versión simplificada en la que solo se usan las figuras de las cartas J, Q y K).

El hecho de emplear una versión simplificada del póquer en el que solo se incluyen las tres figuras de la baraja inglesa y las opciones de apostar (en este caso las apuestas son de 1 ficha o unidad solamente, no se involucran variables para reducir aún más la complejidad del modelado) o pasar (que en ocasiones puede convertirse en retirarse de la mano como opción) se usa para demostrar que a pesar de ser condiciones simples se involucra un proceso complejo al momento de aprender una estrategia sobe el mismo.

El desarrollo del juego se basa en dos partes, una de aprendizaje y exploración y otra de solo exploración empleando las estrategias aprendidas. A pesar de haber empleado algoritmos para aprendizaje, la convergencia del mismo no llegaba sino hasta haber sido jugadas cincuenta manos con el oponente para poder predecir sus acciones.

Hoehn, B., Southey, F., Holte, R., & Bulitko, V. (2005). Effective Short-Term Opponent Exploitation in Simplified Poker. The Twentieth National Conference on Artificial Intelligence. Pittsburgh, Pennsylvania: AAAI.

Defining and Using Ideal Teammate and Oponent Agent Models

Este artículo resulta ser de gran utilidad a pesar de su antigüedad debido a la mención que hace sobre la forma en que se toma en cuenta al rival dentro de la competición de RoboCup y la forma en que ellos planearon modelarlo.

Se menciona que el modelado del oponente de forma dinámica durante un partido es una tarea difícil y de cierta forma inapropiada para este estilo de competencia debido al poco tiempo de interacción que se tiene con cada equipo rival (solo la duración del partido). Es posible que por esta razón se limite el uso de un modelado del oponente de forma exhaustiva solo en las competencias de Coach en las que se tienen los datos del rival con anterioridad para entrenar al equipo.

La forma en que los autores de este artículo decidieron llevar a cabo el modelado del oponente parte de una base estática pero posiblemente eficaz asumiendo que el rival tiene cierto comportamiento (previamente definido por ellos) en el cual se considera que es muy probable que tenga una habilidad semejante o superior a la de los agentes propios para llevar a cabo acciones dentro del terreno de juego.

Se prueban las anteriores suposiciones con dos acciones básicas en el ataque dentro del juego, la decisión de tiro y los pases que se realizan a los compañeros. En ambos se asume que el rival tiene cierta capacidad para bloquear el tiro o el pase y en el caso del portero se emplearon varios modelos en los que se observa que el agente reacciona de forma inmediata a la posición del balón y en algunas ocasiones cuando se acerca a cierto radio se aventura a por él o en otras espera hasta el último momento (justo después del disparo del delantero) para lanzarse por el balón.

Stone, P., Riley, P., & Veloso, M. (2000). Defining and Using Ideal Teammate and Opponent Agent Models. Proceedings of the Twelfth Annual Conference on Innovative Applications of Artificial Intelligence. Austin, Texas: AAAI.

Sitio de Peter Stone

Revisando su sitio web encontré que aunque aún se encuentra involucrado en los proyectos relacionados con sistemas multi-agentes y en específico con RoboCup, actualmente ha tomado mucha mayor atención en cuanto a robots físicos y no a la base de simulación aunque sus artículos genéricos sobre SMAs pueden ser útiles.

Helios Team

Encontré el sitio en el que se encuentra el código fuente del equipo, sin embargo el sitio está en japonés y es bastante complicado entender en que parte se encuentra el archivo para descargar y su descripción.

http://sourceforge.jp/projects/rctools/

Robocup 2009 Team Description

Esta es la competición más reciente en cuanto a RoboCup, la mayoría de los equipos son los mismos que en la competición del 2007 y continúan con la investigación llevada a cabo siguiendo su línea en cuanto a los sistemas multi-agentes.

• Helios – Con su código abierto al público y teniendo una sólida implementación de un conjunto significante de comportamientos básicos, se menciona su uso como base para diversos equipos dentro de la competición, siendo esta una posibilidad para la implementación del código de los TecRams2D.
• AT Humboldt 2009 – Por su parte este equipo sigue empleando decisiones basadas en CBR y sencillamente se mencionan mejoras en cuanto a su sistema.
• The DAInamite 2009 – Este equipo menciona la localización de sus jugadores en cuanto a diagramas de Voronoi para descomponer el plano del terreno de juego y posicionar cada línea de jugadores en su punto óptimo.

Robocup 2007 Team Description

En cada año revisado se ve una evolución en cuanto a los temas y problemas que intentan resolver cada uno de los equipos, siendo en los primeros problemas ligados con el uso del servidor, acomodo del equipo y comportamientos individuales y en otros más recientes como este se emplean técnicas involucradas en la inteligencia artificial como lo es el uso de redes neuronales o lógica difusa.

• AT Humboldt 2007 – En este año se continuo con el desarrollo del uso de CBR y se mencionan aspectos que son fundamentales para su óptimo uso como es el mecanismo de selección de jugadas y la optimización del conjunto de casos Posicionamiento en cuanto al espacio y eliminación de casos redundantes).
• Bahia 2D – Hace uso de lógica difusa para diversos motivos siendo de los más relevantes para los datos relacionados con su posición y poder emplearlos así en su aprendizaje.
• Helios 2007 – Este es uno de los equipos más sólidos en la competencia, hacen uso de un posicionamiento en base a triangulación de Delaunay además de tener claramente definidos los comportamientos básicos de los agentes como lo son el correr con el balón, pases, tiros, etc.
• OPU Hana 2D – Este equipo sigue mencionando el uso de algoritmos genéticos y aunque no profundiza en los mismos, como en sus descripciones anteriores, es interesante ver que cada uno de los equipos toma cierto rumbo en cuanto sus investigaciones. También se menciona el uso de una red neuronal para mejorar su técnica para llevar el balón.

Robocup 2005 Team Description

En este año se nota que se ha tomado mayor importancia a la coordinación entre agentes llevando a varios equipos a describir la forma en que se comunican entre ellos (empleo de gritos “Shouts” por ejemplo) además del uso de formas de aprendizaje y en su mayor parte siendo este por refuerzo.

• TsinghuAeolus2005 – Este equipo hace mención de un modelado del equipo rival llevado a cabo de forma individual, intentando anticipar los movimientos y posiciones de cada jugador contrario pero no entendiendo las estrategias de los rivales. No se menciona si esto se hace en la competencia del “Coach” o si es en la competencia de los simuladores y no es claro debido a que muchos equipos emplean la misma descripción para todas las competencias que han sido incluidos.
• Brainstormers 2D – Este equipo hace énfasis en la arquitectura que emplean para el comportamiento de los agentes, siendo esta híbrida ya que aunque se cuenta con una capa reactiva, otra lleva a cabo el aprendizaje del agente para que pueda llevar a cabo decisiones complejas. Este es un punto común en varios de los equipos que emplean una estructura similar para sus arquitecturas.
• YowAI2005 – Por su parte, este equipo hace referencia a la importancia de la comunicación dentro del entorno del simulador 2D y explica el uso de su modelo de gritos o “Shouts”. También es importante remarcar que en su trabajo futuro hace mención a un modelado del oponente.

Robocup 2004 Team Description

En este año se muestra como muchos de los equipos han logrado dejar atrás los problemas que consistían a los movimientos individuales de los agentes, y aunque no habían sido perfeccionados (y de hecho, muchas descripciones hablan de forma de mejorarlos y hasta se plantea como trabajo a futuro) se empieza a notar un mayor interés en la toma de decisiones del equipo como tal y no solo de cada agente, esto es, se trata de llevar a cabo un verdadero juego de equipo y no solo once agentes sin algún tipo de coordinación.

• AT Humboldt 2004 & AT Humboldt 3D – Este equipo menciona el uso de CBR (Case-Based Reasoning) para la selección de jugadas y aunque de una forma muy rudimentaria y poco eficaz, es algo que decidieron emplear y expandir en próximas competiciones.
• Tram Hana – Este equipo decidió utilizar computación evolutiva que le permitiera aprovechar el uso de algoritmos genéticos para llevar a cabo sus estrategias, se denota un mayor conocimiento en cuanto a su antecedente inmediato (Iranians 2003) posiblemente causado por una mayor investigación en cuanto al campo.
• UTUtd 2004 – Este equipo por su parte (y en realidad siendo el único que he encontrado que hace uso de esto) adapta el comportamiento guiado por emociones en los agentes y que pueden afectar las decisiones y acciones que llevan a cabo dentro del juego basados en su desempeño individual.

Robocup 2003 Team Description

En general, los equipos en este año se encontraban enfocados a la resolución de los comportamientos individuales de los agentes, partes que tienen que ver mucho más con la forma en que cada agente se posiciona en el entorno y como actúa que en avances en cuanto a coordinación y cooperación así como comportamientos complejos a pesar de que varios equipos mencionan que su participación en esta competición inicia algunos años atrás.

Aún así, dentro de los participantes existieron tres que llamaron mi atención los cuales son:

• Arian Robocup 2003 – Debido a que mencionan la posibilidad de introducir alguna forma en la que puedan predecir la forma en que el equipo contrario actuará, la explicación se basa más en lo que quieren lograr que en algo que hayan logrado implementar en el momento.
• Brainstormers 2003 - Este equipo emplea una localización dentro del terreno de juego de forma similar a la que empleamos actualmente para las pruebas de los TecRams2D, sin embargo mencionan que debieron de utilizar algoritmos para reducir el ruido captado por los agentes y que es enviado por el servidor.
• Iranians 2003 – Mientras que la mayoría de los otros equipos se enfocaban a las acciones básicas de los agentes, este por lo contrario plantea utilizar algoritmos genéticos como base para el desempeño de un nivel de cooperación de los agentes con un nivel con mayor grado de complejidad y ambición para lograr la interacción entre los agentes.

Fedora 12

Se optó por cambiar de sistema operativo a uno que se ha encontrado que resulta ser ampliamente soportado por el software de RoboCup y Python Robotics. Sin embargo aun asi se encontrarón problemas debido a que es la última versión del sistema operativo y no todo ha sido actualizado para el mismo por lo que se debieron cambiar algunas partes para que funcionara.

Detalles:

La instalación del cliente de RoboCup se realizó sin problemas excepto al intentar emplear un driver de la tarjeta de video distinto al de default del sistema debido a que deja de reconocer la versión de OpenGL soportada.

Se cambio el repositorio de Python Robotics para que se descargue el software como si fuese la versión 11 del sistema operativo debido a que la versión 12 todavía no se encuentra soportada o al menos en su sitio.

Primera Versión de Hipótesis

Aunque existen modelos que toman decisiones sobre las estrategias colaborativas en los sistemas multi agentes tomando en cuenta su entorno, se pretende crear un sistema que tenga un libro de jugadas (basado en CBR) que tenga ciertas jugadas predefinidas pero que a su vez asocie no solo las estrategias del equipo sino del rival al mismo y pueda de cierta forma predecir su comportamiento tal que el desempeño del equipo mejore y sea capaz de obtener mejores resultados reflejados en los datos del partido.

Intuitive Plan Construction and Adaptive Plan Selection

Hasta este momento y después de haber leído los artículos anteriores incluyendo las secciones de la tesis de Myriam que hablan sobre CBR (Case Based Reasoning) encuentro este artículo como el más apegado a las necesidades de implementación que han ido surgiendo conforme al desarrollo de estos documentos ya que de forma clara explican el método empleado para llevar a cabo algo como lo intentado por Myriam en el ambiente de simulación de RoboCup.

Este documento se enfoca a dos áreas cruciales dentro de las estrategias colaborativas, una es la estructura y definición de planes (estrategias) que se emplearán a lo largo del desarrollo del partido en este caso y la otra es la elección de dicha estrategia que resulta tener la misma importancia que la definición.

De manera muy similar al CBR de Myriam se plantea el uso de una especie de libro de jugadas parecido a lo que los entrenadores emplean en el fútbol humano y en el cual se incluyen diversas jugadas que son descritas por las posiciones de los jugadores y el balón. Este libro de jugadas es definido previo a los partidos para que se cuente con el mismo en el desarrollo del juego.

La definición de las jugadas la realizaron mediante el software de un equipo de RoboCup de robots llamado b-smart en el cual se define la estructura de cada jugada sin necesidad de comandos complejos lo cual muestran que facilitó el desarrollo de su implementación.

Cada jugada fue dividida en pasos que contenían condiciones y acciones que debían cumplir los jugadores para que sean llevadas a cabo, de lo contrario se encontrarían como jugadas no realizables y en la elección de las mismas se descartarían en el momento.

La selección del plan a realizar se debe llevar a cabo en un tiempo razonable (aproximado al tiempo real) por lo que considerar todos los casos definidos en el libro de jugadas es demasiado costoso, por lo tanto decidieron acotar las jugadas que pueden ser elegidas dividiéndolas en dos subconjuntos teniendo así jugadas posiblemente aplicables y con mayor relevancia las jugadas aplicables. Estos subconjuntos son creados en base a la posición del balón y por medio de la realización de un backtracking especial que dicta que jugadas son aplicables y cuáles no.

Al momento de elegir la jugada pueden o no participar expertos en la evaluación de la misma. Ellos determinan la probabilidad de éxito de cada jugada y se arma un árbol de decisión sobre el cual como normalmente se debe comportar se emplean las ramas que tienen una probabilidad más alta de éxito.

Stoye, K., & Elfers, C. (2008). Intuitive Plan Construction and Adaptive Plan Selection. En RoboCup 2007: Robot Soccer World Cup XI (págs. 278-285). Berlin: Springer.