PDF de programación - Resolución de problemas mediante búsqueda

Resolución de

problemas

mediante búsqueda

Búsqueda ciega, no informada

Bú
d
Búsqueda heurística, informada

d h

i f

í

i

1

1

Agente simple de resolución de
problemas: Tipos de problemas

(cid:122) Agentes de resolución de problemas son un tipo de agentes

basados en el objetivo

(cid:122) Determinista, completamente observable (cid:198) problema de

estado simples:
» El agente sabe exactamente en qué estado se encuentra La
» El agente sabe exactamente en qué estado se encuentra. La

solución es una secuencia

(cid:122) No-observable (cid:198) problema sin sensores

» El agente no sabe dónde se encuentra. La solución es una

secuencia.

estado actual.

(cid:122) No determinista y/o parcialmente observable (cid:198) problema con

contingencias.
» Las percepciones proporcionan información actualizada sobre el

y p

p

(cid:122) Espacio de estados desconocido (cid:198) problema exploratorio

2

2

Formulación de problemas, I
Problema de la aspiradora
(cid:122) Se dispone de una aspiradora con
acceso a dos habitaciones y con la
capacidad de aspirar basura
capacidad de aspirar basura
» Entorno accesible y determinista: Problema

de estados simples

El agente está en alguna posición

El mundo tiene dos alternativas
{LIMPIO, SUCIO}

5

1

6

7

2

8

3

4

Las acciones que puede
realizar el agente:
L: left (izquierda)
R: right (derecha)
S: suck (aspirar)

Objetivo: limpiar toda la
suciedad.
Equivale al conjunto de
3
estados {7,8}

3

Formulación de problemas, II

Problema de la aspiradora

» Entorno no accesible (parcialmente observable) y/o

no determinista: Problema de estados múltiples

– DEF: Un problema de estados múltiples es un caso
particular del caso de un problema de estado simple
particular del caso de un problema de estado simple,
en donde cada estado es un multiestado.

4

4

Formulación de problemas, III

(definición)
(cid:122) Abstracción de un problema

» DEF: Proceso de eliminar los detalles de la

representación formal de un problema

(cid:122) Problemas bien definidos

» La formulación de un problema requiere

– Especificación de estados iniciales: uno o más
estados que describen las situaciones de partida
estados que describen las situaciones de partida
– Especificación de estados objetivos: uno o más
estados que podrían ser soluciones admisibles del
problema

(cid:122) Función/test objetivo: determina si un estado es

un estado objetivo.

– Especificación del conjunto de acciones/operadores

que pueden realizarse sobre cada estado.

(cid:122) Función sucesor: estando en un estado,

aplicando un operador indica a qué estado se
aplicando un operador indica a qué estado se
accede. S: x (cid:198) S(x)

– Definición de un espacio de estados del problema
(cid:122) Conjunto de todos los estados alcanzables a

partir del estado inicial aplicando cualquier
partir del estado inicial aplicando cualquier
secuencia de operadores

(cid:122) Determina un grafo: estados - arcos - caminos
– Función de coste de aplicación de los operadores

5

5

Estados?

Posiciones de la suciedad y del
robot

E t d i i i l? El
Estado inicial? El que se designe

d i

Operadores? Left (L), right (R), suck (S)

Función sucesor?

(1 R 2), (1 S 5) …

1

Objetivo?

NoDirt(x)

Coste del
camino?

1 por
operador

5

6

2

3

7

8

Formulación de problemas, V

(Problema Bien Definido)

(1, AS, S), (2, S, AS), (3, AS, )
(4, S, A), (5, A, S), (6, , AS)
(7, A, ), (8, , A)

4
4

6

6

Resolución mediante

búsqueda, I

(cid:122) La resolución de un problema de IA

mediante búsqueda consiste en:
» Aplicar una determinada estrategia de
» Aplicar una determinada estrategia de
control que conduzca a encontrar un
camino desde el estado inicial hasta algún
estado objetivo del espacio de estados
Exige examinar las posibles secuencias de
– Exige examinar las posibles secuencias de
acciones

– Se debe seleccionar aquella secuencia que sea

la mejor según un determinado criterio

(cid:122) Los objetivos fundamentales de la
(cid:122) Los objetivos fundamentales de la

resolución de un problema mediante
búsqueda son:
» Encontrar una solución
» Que la solución tenga coste total mínimo:

» Coste de búsqueda (coste offline):
» Tiempo y memoria necesarios.
» Coste del camino solución (coste

online).

7

7

Resolución mediante

búsqueda, II

(cid:122) El entorno del problema influye sobre la

secuencia de acciones solución
» Ejemplos

Ej
– Entorno determinista

l

(cid:122) Para cada estado inicial, hay una secuencia

fija de operadores que llevan al objetivo

» Comenzar en #5
» Secuencia: [R, S]

– Entorno determinista no accesible

(cid:122) Para cada estado inicial hay una secuencia
(cid:122) Para cada estado inicial, hay una secuencia

fija de operadores que llevan al objetivo
» Comenzar en algún estado: {1 .. 8}
» Secuencia: [R, S, L, S]
i

– Entorno no determinista, semiaccesible
ibl

E t

d t

i

i t

(cid:122) La absorción deposita algunas veces suciedad, pero

sólo cuando no hay suciedad

» sensor de posición y sensor local de

suciedad (cid:198) Se percibe [L, Limpio].

» Comenzar en #5 ó #7 [L, Limpio]
» Secuencia: [R, If Sucio Then S]

8

8

Ejercicios propuestos

En ambos casos determinar:
(a) estados, (b) estado inicial, (c) operadores, (d) objetivo,
(e) coste del camino
1 - Dado un puzzle de 8 piezas alcanzar el estado
1. Dado un puzzle de 8 piezas, alcanzar el estado
objetivo mediante sucesivos movimientos del hueco.

2.- Dado un tablero con N
reinas, encontrar una
configuración en la que no
estén enfrentadas entre si

Solución no válida (cid:198)

9

9

Soluciones a ejercicios

propuestos

(cid:122) Problema de las 8 reinas (en general de las N

/d

i
reinas/damas):
)
» Coste operadores: 1 (el camino solución siempre

tiene coste 8).

» Posible representación (1):
l t bl

t d N i

– estado: N reinas en el tablero
– operadores: añadir una reina a una posición vacía.

» Posible representación (2):

– estado: N reinas en el tablero (no atacándose).
Operadores: añadir una reina en la columna vacía
– Operadores: añadir una reina en la columna vacía
más a la izquierda tal que no sea atacada por ninguna
de las ya existentes.

– Menos operadores que en la representación (1)

(cid:122) Problema del 8-puzzle

» Estados: posiciones de las piezas y hueco

(setf *estado0*

‘((0 5)(1 4)(2 nil)

(3 6)(4 1)(5 8)
(6 7) (7 3) (8 2))

» Operadores:

– HuecoA: Dcha – Izda – Arriba – Abajo
Izda Arriba Abajo

HuecoA: Dcha

» Objetivo: (ver gráfico anterior)
» Coste operadores: 1

10

10

Otros ejemplos, I
(cid:122) Problemas de Criptoaritmética

FORTY
+ TEN
TEN
+
TEN
------
SIXTY

29786
+ 850
850
850
------
31486

» Estados: algunas letras sustituidas por

tit id

t

E t d
dígitos.

l

l

» Operadores: sustituir una letra por un dígito

que no aparece ya dentro del estado
que no aparece ya dentro del estado.

» La solución se encuentra a profundidad

conocida.
– Todas las soluciones son igualmente válidas

luego el coste del camino es 0

11

11

Otros ejemplos, II

(cid:122) Misioneros y caníbales

» Hay 3 misioneros y 3 caníbales en la orilla

izquierda de un río. Un bote puede
izquierda de un río. Un bote puede
transportar a 1 ó 2 personas de una orilla a
otra.
– Objetivo: pasar a todos a la otra orilla.
Condición: No puede ocurrir nunca que si en una
– Condición: No puede ocurrir nunca que si en una
orilla hay algún misionero haya a la vez un
número mayor de caníbales (se los comerían).

» Estados:

– Parámetros: número misioneros lado izquierdo,
Parámetros: número misioneros lado izquierdo,
número caníbales lado izquierdo, posición bote
(izquierda o derecha).

» Operadores:

– Se debe verificar la condición.
p
– Transportar 1 misionero.
– Transportar 1 caníbal.
– Transportar 2 misioneros.
– Transportar 2 caníbales
Transportar 2 caníbales.
– Transportar 1 misionero y 1 caníbal.

» Coste operador: 1

12

12

Otros ejemplos, III

(cid:122) Problema de mapa de carreteras

» Viajar de una ciudad a otra recorriendo la menor

distancia posible

(cid:122) Problema del viajante de comercio

» Un viajante debe viajar recorriendo un conjunto de
ciudades. Debe partir de una ciudad inicial y, tras
recorrer todas las ciudades volver a la ciudad de
recorrer todas las ciudades, volver a la ciudad de
inicio. Debe visitar exactamente 1 vez todas las
ciudades (excepto la de inicio que la visita 2 veces).

7

B

A
A

10

5

6

C

10

13

8

D

Estado inicial: (A)
Estado final: (A ... A)

Estados:
(A C) (A D) (A B) (A E)
(A C D) (A C D E)
(A C D E B) ...
Operadores:
Operadores:
VisitarCiudadA = VA,
VisitarCiudadB = VB, ...
VisitarCiudadE = VE

E

6

13

13

Búsqueda en árboles, I

(cid:122) Representación de un nodo:

» Estado: elemento del espacio de estados

que corresponde con el nodo
que corresponde con el nodo.

» Nodo padre: el nodo en el árbol de

búsqueda que ha generado este nodo.

» Acción/Operador: operador que se aplicó al
» Acción/Operador: operador que se aplicó al

padre para generar este nodo.

» Coste del camino: el coste desde el nodo

inicial. Denotado por g(n).

» Profundidad en el árbol de búsqueda:
número de pasos a lo largo del camino
desde el nodo inicial.

(cid:122) Distinguir los conceptos:

» Espacio de estados:

» Árbol de nodos: se genera

– Finito
Á
– Finito o infinito

14

14

Búsqueda en árboles, II

(cid:122) Algoritmo de búsqueda en árboles
(cid:122) Algoritmo de expansión de nodos

15

15

Búsqueda en árboles, III
(cid:122) Algoritmo de búsqueda en árboles

(descripción informal):

funcion búsqueda-árboles (problema, frontera)
devuelve una solución o fallo

inicializa árbol de búsqueda con estado inicial
inicializa árbol de búsqueda con estado inicial
bucle hacer

si no hay candidatos para expandir en frontera,

entonces devolver fallo

en otro caso

escoger de frontera, según estrategia,

nodo para expandir y eliminar de ella
si el nodo es objetivo (contiene estado objetivo)
si el nodo es objetivo (con