1 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 tontos inteligentes Entornos virtuales tontos e inteligentes, viejos algoritmos de IA para los nuevos dominios gráficos Miguel Lozano Ibáñez Grupo Artec, Instituto de Robótica Departament d’Informàtica Facultat de Físiques Facultat de Físiques Universitat de València

2 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Índice “tontos” Entornos virtuales “tontos” Inteligencia Artificial para Humanos Virtuales Personajes, avatares Agentes autónomos Animación comportamental: actores capaces de comportarse y reaccionar en su entorno. Path-Planning: navegación de actores en entornos virtuales. Simulación multi-agente: MAS y coordinación. Problemas pendientes: Futuro

3 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Entornos virtuales “tontos” Basados en alguna API gráfica (OpenGL), los entornos se crean a partir de: –Modelado y Representación de la Geometría. – –Modelos Polígonales. – –Modelos de Superficies. – –Modelado Sólido. – –Modelos de partición Espacial Normalmente se trabaja a partir de primitivas poligonales optimizadas.Normalmente se trabaja a partir de primitivas poligonales optimizadas. –Tira de cuadrados. –Tira de Triangulos. –Abanico de Triangulos...

4 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Entornos virtuales “tontos” Propiedades de color y textura: la luz.Propiedades de color y textura: la luz.... propiedades de los objetos.... comportamiento de la Luz. Soluciones computables: – –Modelos de Iluminación (pto, normal, nvértices, no interacción entre objetos,...)Iluminación Local (pto, normal, nvértices, no interacción entre objetos,...) – –... sombreado. Phong Goraud... (interacción entre objetos, sombras,...)Iluminación global (interacción entre objetos, sombras,...) T.Rayos Radiosidad Mejora de las Soluciones: Mapeado de Texturas.

5 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Entornos virtuales “tontos” El procesamiento de los Gráficos 3D. La pipeline Gráfica. Procesamiento de Objetos. Procesamiento de Vértices – –Transformaciones del Modelo. – –Transformaciones de la Vista. – –Iluminación – –Proyección. Procesamiento de Pixels: – –Zbuffer. – –Rellenado de color. – –Texturación.

6 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Entornos virtuales “tontos” orientados a la visualización... Interacción mínima/nula con el entorno, orientados a la visualización... Entornos estáticos no demasiado amigables (frios) calidad gráfica != calidad comportamental Ausencia de actores/personajes autónomos

7 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Entornos virtuales “tontos” (Man In the Loop) Simulación (Man In the Loop) Interacción usuari@ - entorno a través del modelo simulado

8 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Entornos virtuales “tontos” – –Grafos acíclicos dirigidos. – –Recorrido o traversal del grafo se obtiene como resultado un conjunto de primitivas con las transformaciones del modelo acumuladas. – –Los nodos sirven para organizar la escena, aplicar transformaciones, toma de decisiones, indicar geometría, propiedades visuales de los objetos, etc. Estructuras de datos para la simulación 3D TR: – –Nodos Visuales (geom & propiedades). – –Nodos de Operación (traversal: agrupación, recorte, LODs, Switch...). – –Nodos de Transformación. – –Nodos de Retroalimentación (navegación..).

9 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Entornos virtuales “tontos” – –El aumento de calidad gráfica de los entornos virtuales 3D ha generado la correspondiente expectación a nivel comportamental. – –Grafo de escena claramente orientado a la visualización tiempo real (militar), pero no al mantenimiento de la información de un entorno dinámico (IA). – –Difícil integración de actores/personajes/criaturas articuladas autónomas en estos entornos... sensores?, comunicación?, mantenimiento del mundo?.... –Aylett(00) –Aylett(00): La combinación de técnicas inteligentes de IA + VA integradas en criaturas autónomas con capacidad de actuación/interacción... E ntornos V irtuales I nteligentes. Conclusiones:

10 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Inteligencia Artificial para humanos virtuales Categorías … – –Personajes virtuales – –Avatares – –Agentes autónomos LIG-EPFL Agentes Físicos Comportamiento físico realista (gestos, expr. Faciales) Agentes Cognitivos Comportamiento cognitivo:, repr. simbólica, leng. natural, procesos cognitivos (planning)

11 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Inteligencia Artificial para humanos virtuales Personajes virtuales Ananova  Kyoko Date  Webbie Tookay 

12 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Inteligencia Artificial para humanos virtuales Avatares virtuales Ciertas capacidades físicas y efectoras sobre el entorno (correr, saltar, volar, bailar,... ). Expresan un conjunto de emociones. representación del usuari@ Active Worlds

13 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Inteligencia Artificial para humanos virtuales Agentes autónomos Comportamiento autónomo individual y/o colectivo LIG-EPFL

14 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Inteligencia Artificial para humanos virtuales Agentes autónomos … inteligentes? objetivos Sistema capaz de cumplir sus objetivos en un entorno complejo y dinámico, sensorizando su entorno y actuando sobre el mismo.(Maes95) No hay intervención humana Flexibilidad en la toma de decisiones ( AI-based, Wooldridge ) Autonomía, sociabilidad, reactividad, proactividad Autonomía, sociabilidad, reactividad, proactividad... + fuerte: en base a conceptos humanos, creencias, intenciones,...

15 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 (AI Techniques for NPC Behaviours) Animación comportamental Non-Player Characters (NPCs) Comportamiento : Las posibles acciones que los personajes autónomos ( Non-Player Characters (NPCs) ) llevarán a cabo en función de: – –el estado de su entorno (e.j. Lemmings) – –Localización espacial del usuari@ o estado del mismo (e.j. Doom, Tekken, Air Combat …) – –estado/reglas del juego (e.j. RISK) –objetivos –propia iniciativa (objetivos) AI-based, Wooldridge Flexibilidad en la toma de decisiones ( AI-based, Wooldridge ) – –Ej: El cálculo de las trayectorias necesarias en juegos de simulación, basado unicamente en módulos de simulación matemática/cinemática no debería ser considerado, estrictamente hablando, como comportamiento inteligente. atacar/adelantar… pero las decisiones a llevar a cabo (ej: atacar/adelantar a otros coches... sí. Comportamientos... Reactivos?... Inteligentes?...

16 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Animación comportamental (AI Techniques for NPC Behaviours) Comportamientos reactivos Descritos en base a la inmediata reacción ante determinadas situaciones Generalmente son comportamientos de bajo nivel – –pueden ser parte de un plan más complejo – –algunos NPC pueden ser programados únicamente en base a comportamientos reactivos... Comportamientos deliberativos Razonamiento Lógico/Planificación: búsqueda de la secuencia de acciones que permite al agente alcanzar su objetivo. En nuestro contexto puede ser considerada como la forma más genérica de animación comportamental para agentes virtuales inteligentes.

17 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Formalismos (AI Techniques for NPC Behaviours) Geometría Precálculos cinemáticos (motion capture) Cinemática Simulación dinámica Comportamiento reactivo Comportamiento reactivo Modelado cognitivo (dirigido por objetivo) Integración Comportamiento - Sistema motor/actuador Introduciremos tres formalismos:Introduciremos tres formalismos: –Máquinas de estados finitos (Case-based reasoning) –Razonamiento basado en reglas (Rule-based reasoning) Sistemas de producciónSistemas de producción –Planificación jerárquica Árboles Y/O ( AND/OR Graphs )Árboles Y/O ( AND/OR Graphs ) Reactivos Deliberativos

18 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Máquinas de estados finitos Técnica dominante en juegos – –Formalmente son tuplas (V, Q, I, F, m)... – –Técnica eficiente... adecuada para actores virtuales – –Alto grado de descripción y fácilidad de mantenimiento: normalmente máquinas con un número de estados reducido (AI Techniques for NPC Behaviours) Puerta Cerrada Abrir Puerta Puerta Abierta Nodos representan estados, mientras que los arcos representan transiciones entre estados “planes compilados”Pueden ser vistos como “planes compilados”

19 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Distintos autómatas basados en la Teoría de autómatas finitos (ATN, FSTN,...) (adaptación de A. Whittaker) Máquinas de estados finitos ( F inite S tate T ransition N etworks)

20 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Ejemplo: Quake idle, attacking, reacting to attack, …El comportamiento está basado en la definición del autómata, estados (idle, attacking, reacting to attack, … etc.) y transiciones. The QUAKE™ FSA (AI Techniques for NPC Behaviours)

21 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 idleattackdead search hurt Sees enemy Kills enemy Loses interest loses sight of enemy Gets killed gets hurt Compute LOS Compute damage Compute, e.g. time limit retaliate Search procedure Changeappearance Data-driven perceptsactionsData-driven system... división entre tareas de programación de percepts/actions y las tareas de diseño comportamental (creación del autómata). Un buen formalismo debería proporcionar mecanismos necesarios para realizar cambios consistentes o mejoras. Ajustes mediante parametrización – –Variar el tiempo límite de pérdida de interés para hacer a los personajes más persistentes – –Alterar la línea de visión Ejemplo: Quake (comentarios) (AI Techniques for NPC Behaviours)

22 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 (AI Techniques for NPC Behaviours) Razonamiento basado en reglas (rule-based systems) Técnica muy utilizada en IA – –Tradicionalmente asociada con los sistemas expertos – –Paradigma de programación (alta aplicabilidad) –Declaratividad, Modularidad –Declaratividad, Modularidad... Separación control/datos + robusto Elementos – –Hechos (memoria dinámica) – –Reglas (memoria estática/dinámica?) – –Motor de inferencia –(eficiencia?) –Mecanismo de unificación (eficiencia?) En Entornos Virtuales ha sido utilizada – (forward/backward chaining) –Toma de decisiones (forward/backward chaining) – (forward chaining) –Simulación comportamental [1..n] actores (Ej: Flock of birds (Reynolds)) (forward chaining) equilibrio

23 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 (AI Techniques for NPC Behaviours) Sistemas de producción (rule-based systems) Las reglas/producciones son de la forma hechoshechos | acciones IF (hechos) THEN (hechos | acciones) … añadir nuevos hechos a la M.T. hará que se disparen nuevas reglas.. … proponer acción … IF (health < 10%) and (Medikit nearby) THEN (pick up the Medikit at once) IF (health < 40%) THEN (health_is_bad) IF (health_is_bad) and (no plasma_gun) and (no plasma_gun) THEN (situation_is_bad) forward chaining facts_0 rules facts_1 facts_2... rules

24 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Elaboration Propose Operators Evaluate Proposed Operators Select One Operator Perform Operator Actions Soar (AI Techniques for NPC Behaviours) Sistemas de producción (rule-based systems) QuakeII, Unreal, … Ejemplo: Soar Quakebots (Laird): QuakeII, Unreal, … Sistema experto en tiempo real, el conocimiento del juego está codificado en aproximadamente 800 reglas IF enemy visible AND my health is < very-low-health-value (20%) OR his weapon is much better than mine THEN propose retreat (Toma de decisiones: Inteligencia táctica aplicada a las ppales fases del juego, coger armas, atacar, retirarse,…)

25 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 (AI Techniques for NPC Behaviours) Sistemas de producción (rule-based systems) Encadenamiento hacia atrás (Backward chaining) “hacia atrás …” … demostrar que una conclusión/hecho es cierto buscando “hacia atrás …” IF A and B THEN C IF C or D THEN E IF E and F THEN G demostrar A y B Demostrar G … F Laird, GDC99

26 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 (AI Techniques for NPC Behaviours) Computer-Aided Instruction: Steve Steve es un humano virtual autónomo para el entrenamiento de tareas de mantenimiento Steve se comunica con el usuari@ por medio de voz sintética …  University of Southern California Sistemas de producción (rule-based systems)

27 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Control es complicado... número de reglas..... a menudo muchas reglas se disparan... conflictos... consecuencias contradictorias?... acciones incompatibles... conflictos..en algunos casos todas las reglas son plausibles... En otros no... Agrupaciones de reglas... (AI Techniques for NPC Behaviours) Sistemas de producción (rule-based systems) Problemas … IF (you are unarmed) and (guard has not noticed you) and (guard has not noticed you)THEN (attack with bare fists) (attack with bare fists) IF (you are unarmed) and (guard has not noticed you) THEN (wait) (wait) Meta-reglas que operan sobre reglas.. Son usadas para la resolución de conflictos, donde varias reglas se han disparado (several rules can be applied) IF (several rules can be applied) (apply first rules dealing with health) THEN (apply first rules dealing with health) Asociar valores numéricos a las reglas (v. certeza/ prob...) Usar estos “marcadores” para resolver el conflicto

28 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Juegos Interactivos …Cine interactivo... Planes de “nivel alto” Ejemplo II: Virtual Storytelling (AI Techniques for NPC Behaviours) Planificación jerárquica Cavazza, VR00

29 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 (AI Techniques for NPC Behaviours) Generación de la historia … Los personajes compiten por los “recursos/objetos” que percibe en su escenario (… The Sims) Virtual Storytelling Planificación jerárquica

30 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Recordemos... “tontos” Entornos virtuales “tontos” Inteligencia Artificial para Humanos Virtuales Problemas principales Animación comportamental: actores capaces de comportarse y reaccionar en su entorno. Path-Planning: navegación de actores en entornos virtuales. Sistemas multi-agente e IAD Problemas pendientes: Futuro

31 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Navegación de actores virtuales(Path-planning) … entornos robóticos y virtuales … 2 enfoques: Global NPC: acceso a toda la BD … no tienen limitación sensorial (omniscientes?, entornos estáticos?) … Familia de algortimos de Búsqueda Heuristica (A*, RTA*, D*…) Local Robots & Agentes/Humanos Virtuales Navegación reactiva … orientados a entornos dinámicos Reglas, Redes Neuronales, …

32 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Navegación de actores virtuales(Path-planning) Navegando con información global... Problema de búsqueda aplicado al problema de la navegación... Laberinto (real?) Ir de A a B evitando obstáculos Moviemintos válidos 4/8 vecinos Camino más corto … Discretización del entorno

33 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Navegación de actores virtuales(Path-planning) Camino A-B A B A* es un algoritmo de búsqueda que garantiza una solución/camino óptimo. A* reduce el numero de nodos expandidos por medio de una función heuristica,... de esta manera explora el árbol más rápido. A B

34 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Navegación de actores virtuales(Path-planning) Cada nodo tendrá asociado una función de evaluación o coste f’(n) = h’(n) + g(n) g(n)Coste estático (g(n)) : derivado a partir de su padre g(n) g(n) = g( padre ) + c(padre,n) h’(n)La función heuristica corresponderá a algún tipo de distancia al nodo/celda objetivo (h’(n) estimará a la distancia real h(n) ) A B x z Distancia Euclidea Distancia de Manhattan

35 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Navegación de actores virtuales(Path-planning) f’(n) = g(n) + h’(n) “Depth-first” component “Breadth-first” component f’ w (n) = (1-w) g(n) + w h’(n)... con pesos (Pohl) w = 0 (breadth-first) w = 1/2 (A*) w = 1 (BF*, with f = h) … equilibrio entre eficiencia y seguridad...

36 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Navegación de actores virtuales(Path-planning) Complejidad … La complejidad temporal de A* es exponencial, a menos que la función heurística sea excelente (.. el error por debajo de la función logarítmica) Una restricción más fuerte es la complejidad espacial de A*’, … también exponencial, limitando su uso práctico (n-puzzles) IDA* (Korf) soluciona este problema de A*, sin sacrificar su optimalidad. Es aconsejable?... Humanos tenemos un campo de visión limitado, lo que nos hace “buscar” los objetos que caen fuera de él. Caminos poco realistas (suavizados posteriormente) Entornos dinámicos !!

37 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Navegación de actores virtuales(Path-planning) La familia de A* RTA *:RTA *: Real-Time A*... Calcula un mvto. por ciclo … no todo el camino off-line LRTA*:LRTA*: Learning RTA* (pesos dinámicos, objetivo móvil) IDA*:IDA*: Iterative-Deepening A* D*:replanningD*: Dynamic A*, permite “replanning” Rd*:Rd*: Variante que utiliza información a cerca de la bondad de la función heurística

38 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02... más de 1 agente (MAS)(distributed problem solving) … sistemas multiagente (MAS) e IAD (distributed problem solving) ¿trabajan en común resolviendo un problema? las tareas “inteligentes” (planning, etc) son llevadas a cabo por agentes con capacidad de comunicarse para cooperar Rama de la IA que estudia la resolución de problemas mediante procesamiento descentralizado contiene a... Algunos juegos/simulaciones, etc. están basados en la interacción de agentes/actores...... es posible obtener comportamientos globales complejos como resultado de los comportamientos individuales (MAS) (general problem-solving technique) (multi-agent co-ordination)Las técincas Multi-agente son también una forma de resolver problemas (general problem-solving technique)... No confundir con coordinación multi-agente (multi-agent co-ordination)

39 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Multi-agent (High-Level) Co-ordination (simulation agents) NPC co-ordination En juegos … NPC co-ordination – –… con el usuari@ (Team Buddies, X-Squad, etc.) – –… con otros agentes – –... comportaminto colectivo agentes: coches, hormigas, aviones, gente … Basados en algún lenguaje de comunicación entre agentes KQML KQML, ACL (FIPA), COOL, (CFOR) Tratamiento de mensajes …

40 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 IAD (resolución de problemas) y Sistemas Multiagente 123 4 567 8 La solución de la IAD sería asociar un agente a cada celda Cada agente tendría comportamientos elementales como “atacar otra celda para ocupar su posicón” o “escapar en caso de ataque” Además cada agente tendría su objetivo “ocupar su posición final” Este metodo proporciona resultados similares a RTA* y LRTA*, es decir, similar a los mejores métodos de búsqueda heuristica Lemmings’

41 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 Futuro … Problemas pendientes …

42 II Jornada de Informática Gráfica, Universitat Jaume I, Castelló. Julio 02 tontos inteligentes Entornos virtuales tontos e inteligentes, viejos algoritmos de IA para los nuevos dominios gráficos Miguel Lozano Ibáñez Grupo Artec, Instituto de Robótica Departament d’Informàtica Facultat de Físiques Universitat de València