Diseño basado en comportamientos y planificación Luis Peña 2009

Diseño basado Diseño basado en comportamientos en comportamientos y planificacióny planificación

Luis PeñaLuis Peña20092009

CETINIA 2009 Diseño basado en comportamiento 2

Tomar decisiones

¿Por qué es importante la IA en el modelado de personajes automáticos?

Realismo Interacción Diversión Presentar comportamientos “humanos” No repetitivos Planificados

Entorno dinámico Posible actuación por parte del usuario humano Relaciones consistentes

Sorpresa Emoción DIVERSIÓN

BU

SC

AM

OS

BU

SC

AM

OS

EN

CO

NT

RA

MO

SE

NC

ON

TR

AM

OS

Realismo

Interacción

Diversión

Poca Inteligencia

Poca reactividad

Aburrimiento


Tomar decisiones

Hay BUENAS...... ...y MALAS decisiones


Tomar decisiones

¿Cómo tomar “buenas” decisiones?

Percibir

Actuar

Pensar

Máquinas de EstadosAlgoritmos Genéticos

PlanificadoresRedes Nueronales

....

Máquinas de EstadosAlgoritmos Genéticos

PlanificadoresRedes Nueronales

....


Tomar decisiones


Técnicas Básicas

Sistemas de reglas

Máquinas de estados finitos

Definición de comportamientos

Scripting

Árboles de decisión


T.B.: Sistemas de Reglas

Planteamiento más básico

Computación basada en las estructuras condicionales de los lenguajes de programación.

Si Enemigo a vista entonces atacarSi no

Si Amigo a vista y herido entonces curar compañeroSi no

Si Amigo a vista, no herido entonces mover a x,y........

Si Enemigo a vista entonces atacarSi no

Si Amigo a vista y herido entonces curar compañeroSi no

Si Amigo a vista, no herido entonces mover a x,y........


T.B.: Sistemas de Reglas

Ventajas Muy simple

Problemas Muy limitado

Difícil de depurar / modificar

No adaptativo

Nula escalabilidad


Técnicas Básicas

Sistemas de reglas



Scripting

Árboles de Decisión


T.B.: Máquinas de Estados Finitos

Máquina (hypotetical device) de Turing:

“Una máquina de estados finitos es un modelo que tiene un número de

estados finito en los cuales nos podemos encontrar en un instante y

que dadas unas entradas puede hacernos transitar de un estado a

otro o permite activar acciones o salidas relacionadas con dicho

estado”

Una FSM (Máquina de Estados Finitos) sólo puede estar en un estado en cada instante.

Los agentes se dirigen en base al estado en el que se encuentran.



Las FSMs están compuestas por 4 elementos principales:

estados que definen el comportamiento y pueden producir acciones

transiciones de estado que son movimientos de un estado a otro

reglas o condiciones que deben cumplirse para permitir un cambio de estado

eventos de entrada que son externos o generados internamente, que permiten el lanzamiento de las reglas y permiten las transiciones



Esquema general

AI Depot



Ejemplos:

Fantasmas del PacManFantasmas del PacMan

Cazar Evadir

PacMan comePower Pill

Fin de tiempoPower Pill



Ejemplos:

Bots del QuakeBots del Quake



Ventajas de una FSM Su simplicidad hace fácil para los desarrolladores sin experiencia

Predictibilidad (en FSM deterministas)

las FSM son rápidos de diseñar e implementar

FSM en una técnica antigua de representación de conocimiento verificada como una técnica de inteligencia artificial, con muchos ejemplos de los que aprender

Las FSM son relativamente flexibles en su implementación.

Bajo uso del procesador

Es fácil determinar si se puede llegar o no a un estado.



Desventajas de una FSM La naturaleza predecible de las FSM deterministas puede no resultar

conveniente en algunos dominios

Si se implementa un sistema grande usando FSMs puede ser difícil de administrar y mantener sin un buen diseño.

No es apropiado para todos los dominios de problema, solo debe ser usado cuando el comportamiento de un sistema puede ser descompuesto en estados separados con condiciones bien definidas para las transiciones.

Las condiciones para las transiciones entre estados son rígidas, significando que están fijadas


Técnicas Básicas

Sistemas de reglas



Scripting



T.B.: Definición de Comportamientos(Behaviors)

Abstracción de las FSM

Encapsulan transiciones de estados que se agrupan para definir un comportamiento

Se pueden definir como una cadena de acciones que describen un comportamiento determinado.



Comportamiento de Patrulla



Permiten aplicar varias técnicas en diferentes niveles:

Planificación para la selección de la secuencia de acciones

Combinación dinámica de acciones para comportamientos más realistas

Combinación de distintas FSM para distintos comportamientos.


Técnicas Básicas

Sistemas de reglas



Scripting



T.B.: Scripting

Aumenta la modularidad de una solución.

Fomenta la creación de contenido durante más tiempo. Aportaciones de usuarios.

Mejora (algo) la depuración de los comportamientos.

Permite separa la programación del motor del juego de la IA de los NPC.


T.B.: Scripting

Varios tecnologías:

Funciones C/C++ Lenguajes de Scripting (incluso javascript) Descripciones en Texto


T.B.: Scripting

Las tareas más comunes que un diseñador quiere realizar vía un script han de ser sencillas

Sencillez para activar/desactivar propiedades o marcadores de objetos

Encontrar objetos y su pertenencia a determinados grupos (e.g. El enemigo más cercano...)

Control simple del tiempo y las esperas

Fácil selección de estados / comportamientos para un agente.

IDE

A B

AS

EID

EA

BA

SE


T.B.: Scripting

Los programadores de la IA proporcionan a los diseñadores de los scripts las funciones e incluso comportamientos de tal modo que la gestión interna del comportamiento recaiga en el motor y no en el script

Es posible combinar scripts manualmente (el diseñador indica que comportamiento desea en cada instante aunque el control lo lleve el motor de la IA)

También es posible que se especifiquen varios comportamientos y se combinen DINAMICAMENTE.

IDE

A B

AS

EID

EA

BA

SE


T.B.: Scripting

Es necesario tener un intérprete del lenguaje de scripting, habitualmente vale con unas líbrerías.

Se cargan los scripts generados, almacenados en ficheros externos y se incluyen como parte de la lógica.

Eje

mp

lo L

UA

Eje

mp

lo L

UA


T.B.: Scripting

Eje

mp

lo L

UA

Eje

mp

lo L

UA

int main(int argc, char* argv[]){ lua_State* luaVM = lua_open(0); if (NULL == luaVM) { printf("Error Initializing lua\n"); return -1; } // initialize lua standard library // functions lua_baselibopen(luaVM); lua_iolibopen(luaVM); lua_strlibopen(luaVM); lua_mathlibopen(luaVM); printf("Simple Functional lua interpreter\n"); printf("Based on lua version 4.0.1\n"); printf("Registering Custom C++ Functions.\n"); lua_register( luaVM, "addNPC", l_addNPC ); lua_register( luaVM, "deleteNPC", l_deleteNPC );

printf("Enter lua commands. type 'exit' to exit\n"); printf("\n>"); lua_dofile(luaVM, "./startup.lua"); // Print out the NPC's that //have been added. theNPCManager->Dump(); lua_close(luaVM); return 0;}

Parte en el motor deljuego

Parte en el motor deljuego


T.B.: Scripting

Eje

mp

lo L

UA

Eje

mp

lo L

UA

-- Simple lua script-- comments indicated with a '--'-- New C functions exposed to lua-- addNPC("NPC Name")-- deleteNPC("NPC Name") addNPC("Joe");addNPC("Sue");addNPC("KillBot2000"); addNPC("BotToDelete");addNPC("Krista");addNPC("Brandon");deleteNPC("BotToDelete");

El script se almacenaEn un fichero por separado

El script se almacenaEn un fichero por separado


Técnicas Básicas

Sistemas de reglas



Scripting



T.B.: Árboles de Decisión

Técnica que permite analizar decisiones secuenciales basada en el uso de resultados y probabilidades asociadas.

Resume los ejemplos de partida, permitiendo la clasificación de nuevos casos.

Facilita la interpretación de la decisión adoptada.

Proporciona un alto grado de comprensión del conocimiento utilizado en la toma de decisiones.

Explica el comportamiento respecto a una determinada tarea de decisión.

Reduce el número de variables independientes.



Requiere de un conjunto de entrenamiento para ajustar los caminos del árbol y la clasificación de resultados.

Los resultados del árbol deben ser un conjunto finito de resultados discretos..

Observaciones importantesObservaciones importantes



Existen varios algoritmos para, dado un conjunto de parámetros a evaluar, crear un árbol de decisión que clasifique los resultados

ID3 C4.5 o C5.0 CART (Árboles de Decisión y Regresión)

Algoritmos de CreaciónAlgoritmos de Creación



El algoritmo de ID3 es el siguiente:

(1) Seleccionar el atributo Ai que maximice la ganacia, e.d, el que tenga menor entropia.

(2) Crear un nodo para ese atributo, con tanto sucesores como valores tenga.

(3) Introducir los ejemplos en los sucesores según el valor que tenga el atributo Ai.

(4) Por cada sucesor,

(1) SI sólo hay ejemplos de una clase ck

Entonces etiquetarlo con ck

SINO, llamar al id3 con una tabla formada por los ejemplos de ese nodo, eliminando la columna del atributo Ai

Ejem

plo

ID3

Ejem

plo

ID3

ID3 intenta encontrar el árbol más sencillo que separa mejor los ejemplos. Para ello utiliza la entropía para elegir o tomar decisiones.

Documents

Diseño basado en comportamientos y planificación Luis Peña 2009