Temario IA MIGJRV Tema1.Ppt

1Inteligencia Artificial

HB/AFG: 2007/2008 1

Inteligencia Artificial

Mster oficial en informtica grfica,

juegos y realidad virtual

Curso acadmico: 2007/2008

Profesores: Holger Billhardt,

Alberto Fernndez Gil


HB/AFG: 2007/2008 2

Tema 1: Introduccin

1. Introduccin

1.1 Qu es la IA?

1.2 Agentes de resolucin de problemas

1.3 Juegos y sus caractersticas

1.4 Representacin de juegos como problemas

1.5 Principio de resolucin de problemas

Resumen:


HB/AFG: 2007/2008 3

Real academia de la lengua:

inteligencia.inteligencia.inteligencia.inteligencia.(Del lat. intelligenta). 1.1.1.1. Capacidad de entender o comprender. 2.2.2.2. Capacidad de resolver problemas. 3.3.3.3. Conocimiento, comprensin, acto de entender. 4.4.4.4. Sentido en que se puede tomar una sentencia, un

dicho o una expresin. 5.5.5.5. Habilidad, destreza y experiencia. 6.6.6.6. Trato y correspondencia secreta de dos o ms

personas o naciones entre s. 7.7.7.7. Sustancia puramente espiritual.

~ artificial.artificial.artificial.artificial. 1.1.1.1. Desarrollo y utilizacin de ordenadores con los que se

intenta reproducir los procesos de la inteligenciainteligenciainteligenciainteligenciahumana.

Que es Inteligencia (Artificial)?


HB/AFG: 2007/2008 4

Pregunta a varias personas Que es inteligencia?

Inteligencia parece estar vinculado al entorno cultural

Segn el test de inteligencia que se haca en 1912 a los inmigrantes que

entraban en EEUU, el 80 % de los hngaros, el 79% de los italianos y el

67% de los rusos eran (segn el test) dbiles mentales

Dnde estn los lmites de la inteligencia?

Aristteles: el hombre es un ser racional porqu algunas personas saben

sumar

Minsky: inteligencia es la forma de resolver problemas que an no se

entienden

Una vez que un ordenador es capaz de realizar algo inteligente, la

gente deja de considerarlo inteligencia.

La IA es todo lo que no se ha hecho hasta ahora.

Cual es la diferencia entre el comportamiento instintivo y el

comportamiento inteligente?



HB/AFG: 2007/2008 5

Objetivo: estudiar los entes inteligentes

cientfico: entender (modelar, describir) los entes inteligentes

ingenieril: construir entes inteligentes

Disciplinas relacionadas:

Filosofa

Matemticas

Psicologa:

Lingstica:

Sociologa:

Ingeniera:

modelar y proporcionar el comportamiento inteligente

(informtica)

crear los cuerpos de los artefactos inteligentes (ingeniera)



HB/AFG: 2007/2008 6

Entender los entes inteligentes:

Facultades de los seres inteligentes

Comunicacin

Conocimiento de si mismos

Conocimiento y percepcin del entorno

Interaccin con el entorno

Intencionalidad

comportamiento dirigido por metas

Creatividad

Capacidad de usar y aplicar su conocimiento

Razonamiento e inferencia

Inteligencia Artificial: Objetivos


HB/AFG: 2007/2008 7

Inferencia:

- hacer suposiciones de lo que significan hechos (observados y/o

conocidos)

- sacar consecuencias de algo o deducir algo de otra cosa

Razonamiento:

Capacidad de derivar inferencias a partir de conocimiento y de

observaciones con el proposito de alcanzar una meta o resolver

un problema.

Tipos de razonamiento:

Deductivo

Abductivo

Inductivo

Razonamiento e inferencia


HB/AFG: 2007/2008 8

Razonamiento deductivo:

- Inferir hechos concretos a partir de otros hechos y de aserciones

generales

- Ejemplo:

Hecho concreto: Pepe es un pjaro.

Asercin general: Todos los pjaros pueden volar.

Conclusin: Pepe puede volar.

Razonamiento abductivo:

- Establecer hiptesis a partir de hechos concretos y de suposiciones

generales

- Eada justifica la inferencia abductivo, excepto que proporcione una

explicacin de los hechos

- Ejemplo:

Asercin general: Cualquier asesino estaba en el lugar del crimen.

Hecho concreto: Pepe estaba en el lugar del crimen.

Conclusin: Pepe es el asesino.

Tipos de Razonamiento


HB/AFG: 2007/2008 9

Razonamiento inductivo:

Inferir suposiciones generales a partir de (muchos) hechos concretos

(aprendizaje)

Ejemplo:

Conclusin: Animales que son pjaros y pequeos pueden volar.

Tipos de Razonamiento

sipequeopjarourraca

nograndepeztiburn

sipequeopjaropaloma

sipequeopjarogaviota

nograndepjaroavestruz

nograndemamferoselefante

Puede volarTamaoEspecieAnimal


HB/AFG: 2007/2008 10

Inteligencia Artificial: Objetivos

Construir entes inteligentes:

Diferentes enfoques:

Sistemas que piensan como humanos

La interesante tarea de lograr que las computadoras piensen...

Mquinas con mente, en su amplio sentido literal (Haugeland 1985)

Sistemas que actan como humanos

El arte de crear mquinas con capacidad de realizar funciones que

realizadas por personas requieren inteligencia (Kurzweil 1990)

Sistemas que actan de forma racional

La rama de la Informtica que se ocupa de la automatizacin del

comportamiento inteligente (Luger & Stubblefield, 1993)

IA fuerte

IA dbil


HB/AFG: 2007/2008 11

Pensar como humanos

General Problem Solver (GPS) [Newell & Simon 1961]:

resuelve problemas mediante la descomposicin en subproblemas ms

simples

se centra en la comparacin de los pasos de razonamiento del GPS con

los pasos seguidos por una persona al resolver el mismo problema

Ciencia Cognitiva:

modelos computacionales (IA) + tcnicas experimentales (psicologa)

construir teoras rigurosas y verificables acerca de los procesos mentales

Modelado cognitivo:

abrir la caja negra de la mente humana

analizar los procesos mentales (introspeccin, experimentos)

desarrollar una teora acerca de los procesos mentales

aplicar esta teora en la simulacin de dichos procesos en un ordenador


HB/AFG: 2007/2008 12

Actuar como humanos

Prueba de Turing : [Alan Turing, 1950]

Un evaluador humano y dos interlocutores estn separados por mamparas

Un interlocutor es una persona y el otro un ordenador

El evaluador formula preguntas a travs de un teletipo, y los interlocutores dan sus respuestas del mismo modo

El ordenador supera la prueba, si el evaluador no es capaz de distinguir entre l y el humano

Capacidades requeridas :

procesamiento del lenguaje natural

representacin del conocimiento y razonamiento

aprendizaje

Prueba total de Turing:

incluye seales de vdeo y objetos fsicos

requiere capacidad de visin computacional y robtica


HB/AFG: 2007/2008 13

Actuar de forma racional

Racionalidad:

prescriptivo: como las personas deberan actuar

sentido estricto: cmo sacar conclusiones verdaderas?

sentido amplio: cmo actuar y sobrevivir en un entorno?

Pensar de forma racional:

leyes de pensamiento de Aristteles: razonamiento irrefutable

lgica formal :

lenguaje formal para representar todo tipo de entes en el mundo

modelo riguroso para razonar sobre dichos entes

en su estado puro, ms estrechamente relacionado con la

filosofa y las matemticas

Objetivo de IA:

modelar/construir sistemas que actan de forma racional


HB/AFG: 2007/2008 14

Actuar de forma racional:

enfoque relativo al contexto: actuar de forma correcta en un entorno

no se limita a la inferencia racional (lgica)

a veces es imposible determinar formalmente cul es la mejor accin

en algunas situaciones es racional emprender una accin buena

inmediatamente en vez de esperar hasta determinar la alternativa ptima

se pueden determinar acciones racionales por inferencias no lgicas

Ventajas:

pone nfasis en una perspectiva ingenieril

destaca la relacin entre comportamientos inteligentes y el entorno en el

que se desarrollan

proporciona criterios transparentes para evaluar conducta inteligente

permite una concepcin integrada de las distintas tcnicas y subreas de la


Actuar de forma racional


HB/AFG: 2007/2008 15

Inteligencia Artificial: Historia

1940/50:

Programas que resuelven tareas bsicas de razonamiento (jugar al ajedrez /

jugar a las damas / probar teoremas geomtricos)

primeros modelos de neuronas artificiales (McCulloch/Pitts)

1960/70:

representaciones especializadas del conocimiento (reglas, marcos, guiones)

primeros sistemas expertos (Dendral, Prospector, Mycin)

declive de la computacin neuronal (anlisis de los Perceptrones de Minsky)

1980:

aplicaciones comerciales de los sistemas expertos

proyecto de software de quinta generacin en Japn

1990 hasta hoy:

regreso de las redes de neuronas

modelos de incertidumbre (cadenas de Markov, redes Bayesianas)

agentes inteligentes (robots autnomos, sistemas multiagente)

. . .


HB/AFG: 2007/2008 16

Inteligencia Artificial: Subreas

Resolucin de problemas mediante bsqueda:

actuar de forma racional en entornos bien definidos: espacios de estado

(entornos accesibles, deterministas, estticos y discretos)

Representacin del conocimiento y razonamiento

combatir la complejidad : estructurar la representacin del entorno

entornos inaccesibles / no deterministas: razonamiento no-montono

. . .

Planificacin:

combatir la complejidad : representacin estructurada + inferencia especializada

entornos no-deterministas: planificacin condicional

entornos dinmicos: replanificacin

Aprendizaje:

combatir la complejidad: aprender a actuar ms rpido

mejorar el rendimiento: aprender a actuar mejor

mejorar la autonoma: reducir dependencia de conocimientos a priori


HB/AFG: 2007/2008 17

Incertidumbre:

entornos inaccesibles/ no deterministas/ continuos: creencias

(lgica borrosa, redes Bayesianas...)

medidas de rendimiento basados en la utilidad esperada

(Teora de la Utilidad, inferencia basada en la Teora de la Decisin)

Comunicacin:

entornos en el que el agente interacta de forma flexible con humanos

(procesamiento del lenguaje natural, actos de habla, ...)

entornos multiagente (razonar sobre otros agentes, coordinacin,

lenguajes de comunicacin entre agentes, ...)

Percepcin y actuacin:

robtica: entornos fsicos y agentes hardware

visin computacional

Inteligencia Artificial: Subreas


HB/AFG: 2007/2008 18

Tema 1: Introduccin a la IA

1. Introduccin

1.1 Qu es la IA?





Resumen:

10


HB/AFG: 2007/2008 19

Agentes

Agente:

ente activo embebido en un entorno

cuerpo:

percibe el entorno por medio

de sensores

acta sobre el entorno por

medio de efectores

mente:

determina las acciones a partir

de las percepciones

medida de rendimiento que gua

dicho proceso

entorno

percepciones

acciones


HB/AFG: 2007/2008 20

Tipos de Agentes

Agentes naturales:

cuerpo biolgico y entorno natural

sensores: ojos, odos, lengua, etc.

efectores: piernas, brazos, manos, etc.

medida de rendimiento: sobrevivir, reproducirse, ...

Agentes artificiales:

agentes hardware (robots):

interactan directamente con un entorno fsico

disponen de un cuerpo fsico

sensores: cmaras, telmetros infrarojos, etc.

efectores: ruedas/piernas, manipuladores, etc.

agentes software (softbots):

actan en entornos virtuales (p.e. Internet)

todo software: no necesitan manipular fsicamente el entorno

sensores y efectores: dependientes del entorno

11


HB/AFG: 2007/2008 21

Agente inteligente

Agentes inteligentes:

actan de forma racional en su entorno

determinantes de un comportamiento racional :

medida de rendimiento: define el grado de xito del agente

secuencia de percepciones: la experiencia del agente

conocimientos a priori sobre su entorno

capacidades: las acciones que el agente pueda emprender

Comportamiento racional:

a partir de la secuencia de percepciones hasta el momento, y el

conocimiento a priori sobre el entorno

elegir entre las capacidades la accin que maximice la medida de

rendimiento

Racionalidad Omnisciencia

la seleccin racional de acciones slo se basa en la informacin disponible


HB/AFG: 2007/2008 22

Autonoma

Autonoma:

no bajo el control inmediato de una persona

un agente es ms autnomo...

... cuanto ms se rige su comportamiento por su propia experiencia

... cuanto menos depende de sus conocimientos a priori

Problema:

los conocimientos a priori compilan la inteligencia del diseador

un agente que no presta atencin a sus percepciones

no sera inteligente

slo podra actuar en entornos extremadamente simples

no puede actuar con xito en situaciones no anticipadas

(escarabajo de estircol)

Agente inteligente = comportamiento racional + autonoma

12


HB/AFG: 2007/2008 23

Problema:

Se tiene un problema si se quiere conseguir un objetivo y no se conoce qu

accin o qu serie de acciones llevan a conseguir este objetivo.

Componentes de un problema:

Individuo (agente, humano, ...)

Estado actual (percepcin del mundo real)

Estado meta (objetivo)

Acciones (que el individuo puede realizar)

influyen en el mundo (cambian el estado del mundo)

deben existir varias acciones

el individuo debe ser capaz de seleccionar una accin

las acciones deben repercutir de forma diferente en la consecucin del objetivo

Voluntad de conseguir el objetivo por parte del individuo

el individuo ignora cual es la mejor secuencia de acciones para conseguir el

objetivo

Resolucin de problemas


HB/AFG: 2007/2008 24

Agentes de resolucin de problemas

Son entes que desean resolver problemas

Realizan acciones para modifican el estado del mundo de acuerdo con

sus objetivos

2

8

3

1

6

4

7

5

1 2 3

4

567

8

13


HB/AFG: 2007/2008 25

Agentes de resolucin de problemas

Ciclo de actuacin del agente:

1. Percibir y clasificar la situacin presente

2. Buscar una accin (o un plan de actuacin)

3. Ejecutar la accin (o el plan de actuacin)

Los agentes son especializados:

el diseador dota al agente a priori con conocimientos especficos

que definen el entorno del problema

que definen los objetivos

se supone una percepcin y una ejecucin ideal


HB/AFG: 2007/2008 26

Tipos de Agentes

Funcin percepcin-accin:

Agentes estimulo-reaccin (reactivos) :

calculan las acciones directamente a partir de las percepciones

frecuentemente siguen un enfoque conexionista

en muchos dominios permite generar rpidamente acciones buenas

Agentes deliberativos:

mantienen un modelo simblico de su entorno

anticipan los efectos potenciales de sus acciones a travs del modelo

permite evitar emprender acciones equivocadas y irrevocables

Agentes hbridos: combinan ambos enfoques

enfoque reactivo para acciones inmediatas

enfoque deliberativo para acciones estratgicos

14


HB/AFG: 2007/2008 27


1. Introduccin

1.1 Qu es la IA?





Resumen:


HB/AFG: 2007/2008 28

Juegos y sus caractersticas

Juegos:

Presentan una gran similitud con problemas reales

Estn bien formuladas

Unen riqueza (complejidad) y simplicidad

Jugar bien requiere inteligencia:

en muchos juegos no se conoce un algoritmo que garantice una

solucin

Son ejemplos claros de problemas de toma de decisiones

Se han utilizado tradicionalmente como campo de estudio y de

aplicacin de IA

Agentes que juegan a juegos complejos y son capaces de mejorar su

juego pueden ser los precursores de artefactos inteligentes del futuro

15


HB/AFG: 2007/2008 29

Caractersticas generales

Caractersticas generales para el empleo de IA en los juegos:

Secuenciales: las jugadas se efectan de forma secuencial y los efectos son

inmediatos

Discretos: un nmero finito de jugadas posibles en cada estado del juego

Implcitos: no se sabe a priori la ganancia obtenida con una jugada

Voluntad de ganar: Existe un conjunto de estados objetivos y la voluntad

de conseguirlos

Deterministas o semideterministas: los resultados de acciones son

previsibles

Accesible: se puede percibir el estado actual y se puede determinar si es un

estado objetivo

Para muchos juegos, jugar bien es un problema bien definido.


HB/AFG: 2007/2008 30

Caractersticas de Juegos

Nmero de jugadores:

unipersonales: 8-puzzle, laberinto, comococos, ...

varios jugadores: ajedrez, damas, parchis

Determinista frente a no determinista:

Los acciones del agente en un estado actual determinan

completamente el estado resultante?

con elementos de azar: backgammon, juegos con dados

sin elementos de azar: damas, ajedrez

16


HB/AFG: 2007/2008 31

Caractersticas de Juegos

Totalmente observable frente a parcialmente observable:

El agente puede determinar inequvocamente el estado del juego?

informacin completa: damas, ajedrez

informacin incompleta: laberinto, pker

Esttico frente a dinmico:

El estado del entorno pueda cambiar mientras que el agente delibera?

Puede cambiar sin que el agente acte?

esttico: laberinto, 8-puzzle

semidinmico (cambios previsibles): ajedrez, damas

dinmico: videojuegos


HB/AFG: 2007/2008 32

Juegos y sus caractersticas

Para qu sirve la inteligencia

artificial en juegos de ordenadores?

17


HB/AFG: 2007/2008 33


1. Introduccin

1.1 Qu es la IA?





Resumen:


HB/AFG: 2007/2008 34

Problema:

Descripcin de los estados (posibles situaciones)

Descripcin de los operadores (acciones)

determina en que condiciones (estados) se puede aplicar una accin

determina el resultado de realizar una accin (el estado resultante)

Funcin de coste que asigna un coste a cada accin ( o secuencia de

acciones)

Descripcin de la solucin

un estado objetivo (4 reinas)

una accin (laberinto)

una secuencia de acciones (8-puzzle)

Instanciacin del problema:

Estado meta

Estado inicial (situacin actual)

Componentes que definen un problema

18


HB/AFG: 2007/2008 35

Ejemplo: 8-Puzzle

Estados:

posicin de cada una de las piezas 2

8

31

6

47

5

Estado inicial

1 2 3

4

567

8

Estado meta

Acciones:

mover pieza adyacente a la posicin

del hueco

de 2 a 4 operadores aplicables,

segn el estado

Coste:

La aplicacin de cada operador vale

una unidad

Problema: Instanciacin:

Solucin:

secuencia de acciones que lleva de

un estado inicial al estado meta


HB/AFG: 2007/2008 36

Representacin de problemas /

bsqueda en el espacio de estados

Ejemplo con 3-Puzzle

2 1

3

21

3

21

3 2

1

3

2

1 3 23

1

2

3 12

1 3

2

1

3

2

3 12

1

3

2 1

3

Instanciacin

estado inicial

estado meta

Solucin ptima

19


HB/AFG: 2007/2008 37

Bsqueda en espacios de estados

mundo modelo representacin

situacion estado nodo

accin y sus efectos operador arco

solucin plan (secuencia de

acciones); accin;

estado

camino; arco; nodo

Espacio de estados: modelo del mundo representado por un grafo

actitud representacin

estados meta conjunto de nodos

eficiencia de un plan coste de un camino

estado inicial nodo inicial

Problema de bsqueda: espacio de estados + actitud del agente

Objetivo: encontrar el plan ms eficiente que lleve del estado inicial a un

estado meta


HB/AFG: 2007/2008 38

Formalizacin del problema

Ejemplo 3-Puzzle:

Representacin (eficiente) de estados

Estado inicial

Estado meta

Coste de un operador: 1 para todos los operadores

Coste de un plan: suma de los costes de los operadores

Tipo de solucin: plan

2221

1211

,

,

xx

xx

3,0

2,1

0,2

1,3

20


HB/AFG: 2007/2008 39

Formalizacin del problema

Ejemplo 3-Puzzle:

Operadores:

zy

x

,

,0

zy

x

,

0,OP1:

z

xy

,0

,OP2:

zy

x

,

0,

zy

x

,

,0OP3:

0,

,

y

zxOP4:

zy

x

,

,0

zy

x

,

0,

z

xy

,0

,

0,

,

z

xyOP4:

zy

x

,

,0OP5:

0,

,

y

zx

y

zx

,0

,OP6:

OP7:

z

xy

,0

,

0,

,

y

zx

zy

x

,

0,


HB/AFG: 2007/2008 40

Mtodo general de resolucin de problemas

Decidir la accin en base de la bsqueda de un camino a la

situacin objetiva (el mejor camino)

Situacin actual

Acciones posibles

Situacin objetiva

Problema: Qu accin hago?

21


HB/AFG: 2007/2008 41

Mtodo general de bsqueda

Mtodo de bsqueda:

estrategia para explorar el espacio de estados

en cada paso se expande un estado

se desarrolla sucesivamente un rbol de bsqueda

Arbol de bsqueda:

Mtodo general de bsqueda:

2. comprobar si es nodo meta

21

3

21

3

2

1

3

2

1 3

23

1

2

1 3

21

3

21

3

21

3

3. expandir este nodo hoja2

3 1

2

1

3

1. seleccionar nodo hoja


HB/AFG: 2007/2008 42

Clasificacin de mtodos de bsqueda

Caractersticas:

Completitud: se encuentra una solucin si existe

Optimalidad: se encuentra la mejor solucin si hay varias

Complejidad en tiempo: cunto se tarda en encontrar la solucin?

Complejidad en espacio: cunta memoria se utiliza en la bsqueda?

Tipos de mtodos de bsqueda:

no informados: utilizan slo conocimientos a priori (estados y acciones)

bsqueda en profundidad

bsqueda en amplitud

bsqueda por profundizacin iterativa

heursticos: adems utilizan informacin aproximada, y especfica

del problema, para guiar la bsqueda

22


HB/AFG: 2007/2008 43

Ejercicio 2.1

Problema de bsqueda / formalizacin:

En una mesa se encuentran dos jarras, una con una capacidad de 3 litros (llamada

Tres), y la otra con una capacidad de 4 litros (llamada Cuatro). Inicialmente, Tres

y Cuatro estn vacas. Cualquiera de ellas puede llenarse con el agua de un grifo

G. Asimismo, el contenido tanto de Tres como de Cuatro puede vaciarse en una

pila P. Es posible echar todo el agua de una jarra a la otra. No se dispone de

dispositivos de medicin adicionales. Se trata de encontrar una secuencia de

operadores que deje exactamente dos litros de agua en Cuatro.

a) Modele este problema como un problema de bsqueda. Con tal fin, defina

una representacin eficiente de los estados, el estado inicial, el conjunto de

estados meta, los operadores con precondiciones y postcondiciones, tipo de

solucin, as como el coste de cada operador.

b) Encuentre una solucin al problema.


HB/AFG: 2007/2008 44

Ejercicio 2.2

Problema de bsqueda / formalizacin:

Modela el problema de las Torres de Hanoi

A B C

A B CObjetivo:

Trasladar los discos de

la aguja A a B en el

mismo orden

Restriccin:

un disco mayor nunca

debe reposar sobre uno

de menor tamao

Documents

Temario IA MIGJRV Tema1.Ppt