Translate

martes, 8 de diciembre de 2009

Steering Behaviors: Part I / Comportamientos de dirección: Parte I

(Does anybody has a better Spanish translation for the title? / ¿Mejor traducción al Español para el título?)

Usign Google Wave push a friend of mine (Ezequiel) and me to re-start with some old projects. The idea is to explore Artificial Intelligence for games. He has his programmer/gamer approach and interest and I am more into the scientific/gamer side, anyway we both share a lot of interest in common and, despite eventual arguments (:D), the project is flowing smoothly. You can check the webpage of the current project at Google Code, fell free to check out the SVN and send us your comments. / Luego de experimentar con Google Wave por un tiempo, mi amigo Ezequiel y yo, nos motivamos a re-iniciar proyectos antiguos inconclusos. La idea es explorar inteligencia artifical para juegos. Eze encara los problemas desde el punto de vista del programador/jugador mientras que yo me soy del estio científico/jugador; por suerte ambos tenemos un ben solapamiento de intereses y, dejando d elado alguna que otra discusión (jeje), el projecto está sobre ruedas. Si estás interesado podes mirar la pagina en Google Code y hacer un checkout del repositorio SVN. tus comentarios son bienvenidos.

Currently I am doing my PhD at the Artificial Intelligence Laboratory one of my research interest is to understand the difference in the behavior of an agent (and the algorithms used to program it) when we allow the use of information acquired only through sensors of the agent, without external references. In short, What is the effect of using a frame of reference fixed to the agent? Where the meaning of "fixed" is a used in a wider sense than in rigid body mechanics. At the moment I am happy if I can re-write an algorithm that was defined using variables respect to an external fixed frame of reference, to one using only local variables, and variables that can be acquired by the use of sensors, without knowing the existence of an external reference. Confusing? Well, today's post brings an example. / Actualmente estoy haciendo mi doctorado en un laboratorio de inteligencia artificial y uno de mis intereses es entender como cambia el comportamiento de un agente (y los algoritmos que usamos para programarlo) cuando la información sobre el "mundo exterior" se la obtiene solo a travéz de sensores situados en el agente mismo. En pocas palabras: ¿Cuál es el efecto de utilizar un sistema de referencia solidario al agente? Donde "solidario" lo utilizo en un sentido un poco más amplio que en la mecánica de cuerpos rígidos. Por ahora me contento con traducir algoritmos que fueron definidos utilizando variables en referencia a un sistema de coordenadas fijo, a otros donde solo se utilizan variables en el sistema de referencia local, y ademas que son adquiribles, sin necesidad de conocer el sistema de referencia fijo. Ok, un poco confuso ¿verdad? El post de hoy trae un ejemplo.

You may have heard of Craig Reynolds and his implementation of steering behaviors using agent to agent interaction (sort of molecular dynamics for agents). If you didn't check out the myriads of applets out there in the web, like this one. I won't explain here all the details (check Reynolds webpage or his paper for full details), but is enough to say that for the sake of optimization and the objectives he had in mind (games, games! bwahaha!) all the behaviors are written using the positions and velocities of the agents respect to a global fixed frame of reference; even more an agent can know its own velocity respect to that frame, something not wrong in mathematical terms but impossible if the agent doesn't know the transformation (in this case a Galilean one) from the local frame to the global one, at all times...something difficult in a real agent (without external help, like GPS)./ Quizás hayas escuchado hablar de Craig Reynolds y su implemntación de comportamientos de dirección usando interacciones entre agentes (algo como una dinámica molecular para agentes). Si no escuchaste de el, podés mirar alguno de los applets del montón, como este. No voy a entrar en detalles de todos los comprtamientos (los detalles están en la pagina de Reynolds o en su artículo (todo en inglés)) pero basta decir que, por razones de optimización y porque el tenía en mente juegos, todos los comprtameintos utilizan posiciones y velocidades definidas en un sistema fijo global, incluso un agente puede conocer su velocidad respecto a ese sistema de referencia. Si bien esto no es matemáticamente incorrecto, es imposible hacerlo si el agente no conoce la trasnformación (de Galileo en este caso) entre su sistema local y el global, en todo momento... algo que es muy dificil de tener en un agente real (si ayuda externa, como un GPS).

There is one behavior that I want to look at, the one that aligns the agent to produce flocking. Reynolds paper states: "The Alignment steering behavior gives a character the ability to align itself with other nearby characters...can be computed by finding all characters in the local neighborhood, averaging together the velocity (or alternately, the unit forward vector) of the nearby characters. This average is the desired velocity, and so the steering vector is the difference between the average and our character's current velocity (or alternately, its unit forward vector)." . Can this behavior be written in terms of local (to the agent) variables? Can we achieve an easier (in terms of time complexity) algorithm by doing that? I will try to answer the first question, and to do that lets interpret Reynolds explanation: / En particular me voy a referir a uno de los comportamientos propuestos por Reynolds, el que alinea los agentes para producir flocking. En su artículo, Reynolds nos indica que para cada agente hay que hacer lo siguiente (lo indica en palabras, por lo tanto esto es una interpretación):
  1. Get average velocity of agents nearby (or unit forward vector). / Calcule la velocidad promedio de los agentes cercanos (o el vector unitario que indica su orientación).
  2. Get the difference between that average and the agents velocity. / Tome la diferencia entre ese promedio y la velocidad del agente en cuestión.
  3. Apply a force proportional to that difference. / Aplique una fuerza al agente en cuestion proporcional al resultado de la diferencia.

I am looking to have something more like: / Yo estoy buscando algo como:

  1. Get average relative velocity of agents nearby (or relative heading); This can be achieved with distance sensors and some assumptions about the way another agents looks like or behaves (more on this to come). / Calcule la velocidad relativa promedio de los agentes cercanos (o la orientación relativa); que se puede obtener por medio de sensores de distancias y algunas hipótesis sobre el aspecto y la forma de moverse de los otros agentes.
  2. Apply a force to minimize the norm of that result. / Aplique una fuerza para reducir la norma de ese resultado.


To be continued.../ Continuará...

2 comentarios:

  1. Comportamientos de navegación? Comportamientos de dirección? Comportamientos de direccionamiento?

    ResponderEliminar
  2. El segundo es el que está, jaja
    Me gusta el primero...

    ResponderEliminar

Share it / Compartelo