PDF de programación - Inteligencia Artificial - Unidad 1 - Introducción y resolución de problemas

Unidad 1

Introducción y

resolución de problemas

11/01/2014

Unidad 1
Lección 1

Introducción a la

Inteligencia Artificial

3

Contenidos

1. ¿Qué es inteligencia artificial?

2. Perspectiva histórica

3. Tipos de sistemas IA

4. Marco I+D+I (Nacional y Europeo)

4

Objetivos

 Obtener una vision amplia del concepto

Inteligencia Artifcial

 Conocer el marco histórico de la Inteligencia

Artificial

 Taxonomia y tipos de sistemas dentro de la

Inteligencia Artificial

¿Qué es Inteligencia Artificial?

5

“El estudio de las facultades mentales mediante el uso de
modelos computacionales” (Charniaky McDermott, 1985).

“IA (…) está relacionada con conductas inteligentes en artefactos”
(Winston, 1992).

“El estudio de cómo lograr que los computadores realicen tareas
que, por el momento, los humanos hacen mejor” (Rich y Knight,
1991).

“Capacida de entender, asimilar, elaborar información y utilizarla
adecuadamente.”

¿Qué es Inteligencia Artificial?

6

Lingüistica

IA

Psicología

Informatica

7

¿Qué es Inteligencia Artificial?

• Tipos de sistemas en IA:

• Sistemas basados en conocimiento

• Definicion de dicho conocimiento a través de un experto

• Sistemas basados en el aprendizaje

• El conocimiento puede ser aprendido a partir de casos concretos y

ejemplos

• Son tratados de manera diferente y las técncias utilizadas
también difieren pero se pueden complementar el uno al
otro

8

¿Qué es Inteligencia Artificial?

• Dimensiones de la investigación de IA:

• Desarrollo de nuevas funcionalidades: se centra en resolver
problemas a través del uso de la computación que hasta ahora o
de otro modo no pueden ser resueltos (p.e. OCR, reconocimiento
de objetos, etc.).

• Métodos y herramientas utilizadas en los sistemas: entornos de

desarrollo de sistemas expertos (p.e. CLISP, Prolog).

• Desarrollo y utilización en aplicaciones comerciales: ciclos de 5-5-5

(investigación-desarrollo-diseminación).

9

Perspectiva histórica

• Fundamentos (400 a.c.)

• Aristóteles (384‐322 a.c.) Entendimiento a través de la razón.
• Formalización de los algoritmos de al‐Khowarazmi (s. IX)
• primeras máquinas de cálculo de Pascal

(s. XVII) y Charles

Babagge (s.XIX)

• Primeros computadores (sobre 1940)

• Z‐3 fue inventado por Konrad Zuse en 1941. En el Reino Unido, el
primer sistema de Alan Turing en 1940, y el Colossus en 1943. En
estados Unidos, el ABC entre 1940 y 1942 por John Atanasoff

• ENIAC 1946(Electronic Numerical

Integrator

and

Computer).

10

Perspectiva histórica

• Génesis (1943‐1956)

• McCulloch y Pitts han sido reconocidos como los autores del
primer trabajo de IA,en 1943, proponiendo un modelo constituido
por neuronas artificiales

• Primeros programas de juego del ajedrez desarrollados por

Shannon y Turing entre 1950

• primeros sistemas de traducción automática, como el experimento

Georgetown‐IBM

Seminario de Darmouth 1956 origen del
término inteligencia artificial

Biblioteca Bake, Universidad de Darmouth.

11

Perspectiva histórica

• Entusiasmo inicial, grandes esperanzas (1952‐1969)

• Gran éxito tanto a nivel de universidad como de empresas y

centros de investigación

• Desarrollo de herramientas como LISP

• Crisis / redimensionamiento de problemas (1966‐1973)

• Limitaciones computaciones y de hardware no son el único

problema

• Decremento de la financiación y se interrumpen un gran número de

proyectos

Perspectiva histórica

12

• Resurgimiento

en

centrado
conocimiento (1969‐1979)
• Surge un renovado interés por sistemas expertos y basados en el
conocimiento aplicado a dominios como diagnóstico médico o control
de plantas

sistemas

basados

en

el

• La industria de la IA (1980 hasta el presente)

• Sistemas expertos comienzan a reportar beneficios en sus diversas

aplicaciones (p.e. DEC sistemas de pedidos)

• Comienzan a desarrollarse nuevos aspectos de IA como la minería de

datos o tecnología semántica

• 2013-….

• Sistemas de análisis y aprendizaje en tiempo real y ubicuos para

adaptarse a las variabilidaes y necesidades del entorno (Big Data).

13

Taxonomia de la IA

• Sistemas basados en conocimiento

• Dispone de una base de conocimiento

• Necesidad de adquisición, formalización, y codificación

• Los sistemas expertos pertenecen a esta categoría

sistema

experto

es

conocimiento

computerizado

un
Un
que
sistema
un
utiliza
un
dominio
ese
problema
dominio,
la
solución debe ser esencialmente
la misma que la proporcionada
por un experto humano en ese
dominio.

de
resolver
de
que

para
específico
forma
de

14

Taxonomia de la IA

• Sistemas basados en en aprendizaje

• Se compone de una fase de entrenamiento y una fase operativa

• La fase de entrenamiento utilia ejemplos para crear un modelo.

• La fase operativa ejecuta el modelo aprendido para tomar

decisiones.

• OCR o sistemas de reconocimiento de objetos en imagen son dos

ejemplos de este tipo de sistemas.

15

Taxonomia de la IA

• Redes neuronales, las Redes bayesianas, Algoritmos genéticos y

Razonamiento basado en casos

Aplicaciones comerciales y sistemas
experimentales

16

• Sistemas de control en transporte ferroviario

• Sistemas de diagnóstico y reparación (medicina y

automoción)

• Agentes

inteligentes

en

videojuegos

y

comercio

electrónico

• Minería de datos es común en astronomía, biología,

teledetección, análisis contenidos Web

• Detección de fraude a través del análisis de patrones

Aplicaciones comerciales y sistemas
experimentales

17

• Previo a la comercialización se produce un ciclo de 5-5-5

(investigación-desarrollo-comercialización)

• Algunos centros de referencia son:

• MIT(Instituto de Tecnología de Massachusetts)
• KSL de Standford
• PARC de Xerox
• ATT Labs
• IBM Watson Laboratory
• Instituto de Investigación en Inteligencia Artificial del Consejo Superior

de Investigaciones Científicas

• Muchas universidades también disponen de un grupo de IA (en
la Universidad Europea se creo en 1999 el grupo de
investigación en Sistemas Inteligentes)

18

Resumen

• Enfocado en esta asignatura como Informática

Aplicada Avanzada y disciplina multidisciplinar

• Perspectiva histórica

• Fundamentos (400 a.c.!).
• Primeros computadores (sobre 1940).
• Génesis (1943‐1956).
• Entusiasmo inicial, grandes esperanzas (1952‐1969).
• Crisis / redimensionamiento de problemas (1966‐1973).
• La industria de la IA (1980 hasta el presente).

• Seminario de Darmouth en 1956 como origen del

término

• Sistemas basados en el conocimiento y sistemas

basados en el aprendizaje

Unidad 1
Lección 2

Resolución de

problemas mediante

búsqueda

20

Contenidos

1. Resolución de problemas mediante la

abstracción

2. Formulación de problemas como espacios de

estados

3. Árboles de búsqueda y búsqueda de

soluciones

21

Objetivos

 Definir un problema desde el punto de vista

computacional

 Buscar las acciones que lleven a la solución

22

Problemas y abstracción

• La abstracción es una pieza fundamental en diversas

técnicas y métodos de la informática en general

Por abstraer solemos entender el centrarnos sólo en los
aspectos de un problema que identificamos como principales,
sabiendo dejar aparte multitud de detalles que decidimos que no
son relevantes.

• Caso de ejemplo: queremos ir de una ciudad a otra en

Rumania (de Arad a Bucarest)

Problemas y abstracción

23

24

Formulación del problema como un
espacio de estados
• Existen diversad formas de formalización, como puede

ser una quíntupla: P= [E, Ei, O,M, C].

Formulación del problema como un
espacio de estados

25

26

Ejemplo: robot aspirador (I)

• Construir un sistema de control de un aspirador, que tiene
un motor para aspirar y otro para irse desplazando de un
lugar a otro.

un

de

¿Cuantos posibles estados
en
dos
unidades donde cada una
puede estar sucia o limpia?

espacio

2 posiciones robot * 2 posibles
estados para celda1 * 2
posibles estados para celda2
= 8

27

Ejemplo: robot aspirador (II)

P= [E, Ei, O,M, C]

E =

Ei = {E1}

O = {O-I, O-D, O-S }

M = {E7, E8}

C = {1, 1, 1}

Ejemplo: robot aspirador (III)

28

¿Cúal es el coste mínimo?

¿Cúal es el coste máximo?

Ejemplo II: el puzzle (I)

29

Formalización en quíntuplas: [E, Ei, O,M, C]

¿Cuantos posibles estados?

181.440 posibles estados

30

Ejemplo II: el puzzle (II)

• E = {E1,.....En} : n = 9!/2 (la mitad de los estados son espejo)

• Ei = {E1}

Diferentes modos de definir un operador

• O = {OA(1), OA(2),...OD(1)....OI(1),....OAb(1)...OAb(8)}

• O = {OA(h), OD(h), OI(h), Oab(h)}

Mover las piezas

Mover el hueco

• M = {E2}

• C = {1, 1, ...1}

31

Árboles de búsqueda y búsqueda de
soluciones (I)
• Para resolver el problema es necesario disponer de un

algoritmo que permita transitar por los diferentes estados
para llegar del estado inicial al estado final deseado

• Este algoritmo se basa en una estructura de árbol para

realizar la búsqueda y por eso denomina árbol de
búsqueda

• Se ejecutan los operadores en el estado inicial y se

obtienen los sucesores. Posteriormente se aplican otra
vez los operadores con éstos y así sucesivamente hasta
encontrar la meta

Árboles de búsqueda y búsqueda de
soluciones (II)

32

33

Árboles de búsqueda y búsqueda de
soluciones (III)
• El viajero quería ir de Arad a Bucarest

• Una solución es [Arad, Zerind, Oradea, Sibiu, Fagaras,

Bucarest]

Árboles de búsqueda y búsqueda de
soluciones (IV)

34

35

Árboles de búsqueda y búsqueda de
soluciones (V)

Función búsqueda-árbol devuelve una solución o fallo

bucle hacer

si no hay candidatos para expandir entonces devolver fallo
escoger, de acuerdo a la estrategia, un nodo hoja para expandir
si el nodo contiene un estado objetivo entonces devolver la

correspondiente solución

en otro caso expandir el nodo y añadir los nodos resultado al
árbol de búsqueda

final bucle

Final función

¿Cual es el orden de expansión del árbol? ¿Qué tipo de árbol se genera?

36

Resumen

• Tecnicas de modelado de problemas a través de la