PDF de programación - Resolución de problemas

RESOLUCIÓN DE PROBLEMAS

GENERALIDADES

ESPACIO DE ESTADOS

CARACTERÍSTICAS GENERALES DE LOS
PROCESOS DE BÚSQUEDA

ESTRATEGIAS DE EXPLORACIÓN DEL ESPACIO DE
ESTADOS

CONCLUSIONES

Inteligencia Artificial. Ingeniería

Informática

1

RESOLUCIÓN DE PROBLEMAS

Moret et al., Fundamentos de Inteligencia Artificial,
Servicio de Publicaciones UDC, 2004

Nilsson, Problem-Solving Methods in Artificial
Intelligence, McGraw-Hill,eds., 1971

Rich & Knight, Inteligencia Artificial, McGraw-Hill, eds.,
1994

Russell & Norvig, Inteligencia Artificial: Un Enfoque
Moderno, Pearson Prentice Hall, eds., 2004

Inteligencia Artificial. Ingeniería

Informática

2

RESOLUCIÓN DE PROBLEMAS

El comportamiento inteligente obliga a utilizar de forma eficaz y
eficiente un conjunto mínimo de conocimientos… ¿por qué?

Distintos problemas requieren distintas técnicas:

– ¿Se requiere inteligencia para resolver: Ax2 + Bx + C = 0 ?

La IA debe producir programas que:

– Capten generalizaciones
– Incluyan conocimiento explícito
– Sean fácilmente actualizables
– Puedan ser aplicados en muchas situaciones diferentes

Inteligencia Artificial. Ingeniería

Informática

3

RESOLUCIÓN DE PROBLEMAS

En IA el tipo de
técnica está
condicionado por el
dominio de aplicación

Normalmente, para
resolver un problema
real, no hay
planteamientos
exclusivos

Programa de

IA

Programa
Convencional

Dominios
Simbólicos

Procesos
Heurísticos

Pasos
Implícitos

Dominios
Numéricos

Procesos
Algorítmicos

Pasos
Explícitos

Información y

Control
Separados

Información y

Control
Integrados

Inteligencia Artificial. Ingeniería

Informática

4

RESOLUCIÓN DE PROBLEMAS

El problema de los dos cubos:

– Disponemos de dos cubos inicialmente vacíos, uno
de 8 litros, y el otro de 6 litros. Ninguno de los cubos
tiene marcas ni divisiones. Disponemos también de
un grifo que puede emplearse para llenar los cubos.
¿Qué tenemos que hacer para llenar el cubo de 8
litros justamente hasta la mitad?

– NOTA: Llamaremos A al cubo de 8 litros, y B al cubo

de 6 litros

Inteligencia Artificial. Ingeniería

Informática

5

RESOLUCIÓN DE PROBLEMAS

Número de orden
Acción

Resultado

1

2

3

4

5

6

Llenar B

A vacío, 6 l en B

Vaciar B en A

6 l en A, B vacío

Llenar B

6 l en A, 6 l en B

Llenar A con B

8 l en A, 4 l en B

Vaciar A

A vacío, 4 l en B

Vaciar B en A

4 l en A, B vacío

Inteligencia Artificial. Ingeniería

Informática

6

RESOLUCIÓN DE PROBLEMAS

¿Es la única solución?

– Si
– No

→
→

Fin
Encontrar otra solución

¿La nueva solución encontrada es equivalente a la anterior?

¿Cuál es la mejor solución?

¿De qué depende que una solución sea mejor que otra?

¿Cuáles son los requisitos mínimos que debe cumplir una solución
para ser aceptable?

Inteligencia Artificial. Ingeniería

Informática

7

RESOLUCIÓN DE PROBLEMAS

Una representación del problema

– A
=
– B
=
– [A]
=
– [B]
=
– ([A],[B])
=
– Número “n” =

Cubo de 8 litros
Cubo de 6 litros
Contenido de A
Contenido de B
Estado actual del problema
Acción ejecutada

Inteligencia Artificial. Ingeniería

Informática

8

Número de orden

1
2
3
4
5

6

7

8

Precondiciones

RESOLUCIÓN DE PROBLEMAS
Acción
Llenar A
Llenar B
Vaciar A
Vaciar B

A no lleno
B no lleno
A no vacío
B no vacío

A no vacío, y B no
lleno, y [A] + [B] ≤ 6
B no vacío, y A no
lleno, y [A] + [B] ≤ 8
B no vacío, y A no
lleno, y [8] + [6] ≥ 8
A no vacío, y B no
lleno, y [8] + [6] ≥ 6
Inteligencia Artificial. Ingeniería

Informática

Vaciar A en B

Vaciar B en A

Llenar A con B

Llenar B con A

9

RESOLUCIÓN DE PROBLEMAS

Secuencia de acciones que nos lleva a una solución del
problema:

(0,0) 2 (0,6) 6 (6,0) 2 (6,6) 7 (8,4) 3 (0,4) 6 (4,0)

Espacio de Estados (EE) = Descripción formal del
universo de discurso

– Conjunto de estados iniciales
– Conjunto de operadores que definen operaciones permitidas

entre estados

– Conjunto de estados meta u objetivos: soluciones aceptables,

aunque no necesariamente la mejor

Inteligencia Artificial. Ingeniería

Informática

10

RESOLUCIÓN DE PROBLEMAS

La resolución de un problema en IA consiste en:

1.

La aplicación de un conjunto de técnicas conocidas, cada una
de ellas definida como un paso simple en el espacio de
estados

2. Un proceso de búsqueda, o estrategia general de exploración

del espacio de estados

Para abordar un problema desde la óptica de la
inteligencia artificial tenemos que ser capaces de
construir un modelo computacional del universo de
discurso, o dominio del problema

Inteligencia Artificial. Ingeniería

Informática

11

RESOLUCIÓN DE PROBLEMAS

FORMALMENTE…

I es el conjunto de estados iniciales…
I = {i1, i2,…, in}

O es el conjunto de operaciones permitidas…
O = {o1, o2,…, om}

M es el conjunto de metas o soluciones aceptables…
M = {m1, m2,…, mt}

Búsqueda = proceso de exploración en el espacio de estados tal que…
O : ( I → M )

Paso Simple… ox : ( iz → iw ) con iz, iw ∈ I, ox ∈ O

Si iw ∈ M, entonces iw verifica la prueba de meta, o test de realización, y
es una solución del problema

Inteligencia Artificial. Ingeniería

Informática

12

–

–

–

–

–

–

RESOLUCIÓN DE PROBLEMAS

El espacio de estados es el soporte físico del dominio
de discurso

Necesitamos también procesos de búsqueda o
mecanismos generales de exploración del espacio de
estados

–
–
–
–

Criterios de selección y aplicación de operadores relevantes
Capacidad de decisión sobre cuál será el próximo movimiento
Búsqueda sistemática
Tratar de generar siempre estados nuevos, no generados
previamente

Inteligencia Artificial. Ingeniería

Informática

13

–
–
–

1.
2.

3.
4.

RESOLUCIÓN DE PROBLEMAS

Volviendo al problema de los dos cubos…

(0,0)
(4,x) / x ∈ [0,6]
{op1, op2, op3, op4, op5, op6, op7, op8}

I
M
O

=
=
=

Estrategia 1

Identificar estado inicial
Prueba de meta

Si meta
Si no meta

Si meta
Si no meta

→
→

→
→

Fin
Seguir (ir a 3)

Fin
Seguir (ir a 3)

Aplicar 1er operador que cumpla requisitos de estado actual, según su número de orden
Prueba de meta

Secuencia de estados generada: (0,0)1(8,0)2(8,6)3(0,6)1(8,6)…
La estrategia es sistemática, pero no siempre genera estados
nuevos, y hay operadores que se repiten

Inteligencia Artificial. Ingeniería

Informática

14

RESOLUCIÓN DE PROBLEMAS

-Estrategia 2

Identificar estado inicial

1.
2. Prueba de meta

Si meta
→
Si no meta →

Fin
Ir a 3

3. Seleccionar operadores que verifiquen precondiciones
4. Descartar los ya aplicados
5. Aplicar el primero de los supervivientes
6. Prueba de meta

Si meta
→
Si no meta →

Fin
Ir a 3

–
–

–
–

-Secuencia de estados: (0,0)1(8,0)2(8,6)3(0,6)4(0,0)
-Búsqueda detenida sin solución
-Necesidad de utilizar estructuras adicionales (autoconocimiento)

Inteligencia Artificial. Ingeniería

Informática

15

RESOLUCIÓN DE PROBLEMAS

-Estrategia 3

Identificar estado inicial

1.
2. Prueba de meta

Si meta
→
Si no meta →

Fin
Ir a 3

–
–

–
–

3. Seleccionar operadores que verifiquen precondiciones
4. Descartar los ya aplicados
5. Descartar operadores que no generen estados nuevos
6. Aplicar el primero de los supervivientes
7. Prueba de meta

Si meta
→
Si no meta →

Fin
Ir a 3

-Secuencia de estados: (0,0)1(8,0)2(8,6)3(0,6)6(6,0)
-Búsqueda detenida sin solución
-Más estructuras adicionales (incrementar el autoconocimiento)

Inteligencia Artificial. Ingeniería

Informática

16

RESOLUCIÓN DE PROBLEMAS

-Estrategia 4

Identificar estado inicial

1.
2. Prueba de meta

Si meta
→
Si no meta →

Fin
Ir a 3

3. Seleccionar operadores que verifiquen precondiciones
4. Descartar operadores que no generen estados nuevos
5. Aplicar el primero de los supervivientes
6. Prueba de meta

–
–

–
–

Si meta
→
Si no meta →

Fin
Ir a 3

-Secuencia de estados…

(0,0)1(8,0)2(8,6)3(0,6)6(6,0)2(6,6)7(8,4)3(0,4)6(4,0)

-Solución aceptable, aunque no óptima
-Más estructuras adicionales (incrementar el autoconocimiento)

Inteligencia Artificial. Ingeniería

Informática

17

RESOLUCIÓN DE PROBLEMAS

Cuestiones importantes:

–

–

–

–

Hemos definido de forma independiente el conocimiento de la forma
en que dicho conocimiento es empleado

Hay una separación clara entre el conocimiento del sistema y las
estrategias de control del conocimiento

Son soluciones aceptables aquéllas que cumplen las restricciones de
la prueba de meta (¿qué pasaría si del grifo manara Hg?)

El sistema necesita AUTOCONOCIMIENTO (en forma de estructuras
adicionales auxiliares), para funcionar correctamente

Inteligencia Artificial. Ingeniería

Informática

18

RESOLUCIÓN DE PROBLEMAS

–

CARACTERÍSTICAS GENERALES DE LOS PROCESOS DE
BÚSQUEDA

1.

2.

3.

4.

DIRECCIÓN DE LA BÚSQUEDA

TOPOLOGÍA DEL PROCESO

REPRESENTACIÓN DE LOS ESTADOS POR LOS QUE DISCURRE LA
SOLUCIÓN DEL PROBLEMA

CRITERIOS DE SELECCIÓN Y APLICACIÓN DE OPERADORES
RELEVANTES

5. OPTIMIZACIÓN DE LA BÚSQUEDA MEDIANTE EL USO DE

FUNCIONES HEURÍSTICAS

Inteligencia Artificial. Ingeniería

Informática

19

RESOLUCIÓN DE PROBLEMAS

DIRECCIÓN DEL PROCESO DE BÚSQUEDA

– Desde los estados iniciales hacia los estados meta

Proceso progresivo o dirigido por los datos

– Desde los estados meta hacia los estados iniciales

Proceso regresivo, evocativo, o dirigido por objetivos

Inteligencia Artificial. Ingeniería

Informática

20

RESOLUCIÓN DE PROBLEMAS

¿Cuándo, y en función de qué, es mejor una dirección
que otra?

1.
2.

3.

Tamaño relativo de los conjuntos I y M del espacio de estados
Factor de ramificación, o número promedio de estados que
podemos alcanzar directamente desde un estado dado
Inclusión de estructuras explicativas como requisito inicial en
el diseño de nuestro sistema inteligente

1. De menor a mayor número de estados
2. En el sentido del menor factor de ramificación
3. De la forma que mejor se ajuste al modo de razonar de expertos

y usuarios

Inteligencia Artificial. Ingeniería

Informática

21

RESOLUCIÓN DE PROBLEMAS
TOPOLOGÍA DEL PROCESO DE BÚSQUEDA

–
ÁRBOL
– GRAFO
Transformación de árbol