Resolución de problemas mediante búsqueda (Presentación PowerPoint)

Agente simple de resolución de problemas
Etapas de la resolución de problemas con objetivos:
1. Formulación de objetivos
2. Formulación del problema
3. Búsqueda de la secuencia de acciones que deberían resolver el problema
4. Ejecuta las acciones una cada vez
“Formulate, Search, Execute”
Obs:
RECOMMENDATION
devuelve la primera acción (first) de la secuencia.
REMAINDER
devuelve el resto (rest) de la secuencia
(Russell 2nd. Ed.)

Formulación de problemas, I (ejemplo)
Problema de aspiradora:
Se dispone de una aspiradora con acceso a dos habitaciones y con la capacidad de aspirar basura
8 posibles estados
2 estados objetivo
3 posibles acciones
Mundo: 2 posibles posiciones
Sucio – limpio
Dos tipos de problemas:
Problema de estados únicos:
entornos accesible y determinista
Problema de estados múltiples:
entornos no accesible o no determinista
Ejemplo aspiradora sin sensores: determinista, no accesible
DEF: Un problema de estados múltiples es un caso particular del caso de un problema de estado único, en donde cada estado es un multiestado:
Estado inicial: multiestado
Cada operador obtiene un multiestado a partir de otro multiestado.

Formulación de problemas, II (abstracción)
Las acciones que puede
realizar el agente:
L: left (izquierda)
R: right (derecha)
S: suck (aspirar)
El mundo tiene dos posiciones: puede haber o no suciedad
El agente está en una u otra posición
Objetivo: limpiar toda la
suciedad.
Equivale al conjunto de
estados {7,8}
1
2
5
6
3
4
7
8

Formulación de problemas, III (abstracción)

Formulación de problemas, IV (definición)
Abstracción de un problema
DEF: Proceso de eliminar los detalles de la representación formal de un problema
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
Especificación de estados objetivos: uno o más estados que podrían ser soluciones admisibles del problema
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.
Función sucesor: estando en un estado, aplicando un operador indica a qué estado se accede. S: x ? S(x)
Definición de un espacio de estados del problema
Conjunto de todos los estados alcanzables a partir del estado inicial aplicando cualquier secuencia de operadores
Determina un grafo: estados – arcos – caminos
Función de coste de aplicación de los operadores

Estados?
Posiciones de la suciedad y del robot
1
2
5
6
3
4
7
8
Operadores?
Left (L), right (R), suck (S)
1 por operador
NoDirt(x)
Coste del camino?
Objetivo?
(Gp:) (1, AS, S), (2, S, AS), (3, AS, ) (4, S, A), (5, A, S), (6, , AS)
(7, A, ), (8, , A)

Formulación de problemas, V (Problema Bien Definido)
Estado inicial?
El que se designe
Función sucesor?
(1 R 2), (1 S 5) …

Resolución de problemas, I
La resolución de un problema consiste en definir un conjunto de acciones que nos permita llegar al objetivo.
Para la resolución de un determinado problema se necesita su formulación.
El entorno del problema influye sobre el curso de acciones hacia la solución.
Ejemplo (En un entorno no determinista)
La absorción deposita algunas veces suciedad, pero sólo cuando previamente no hay suciedad
Si el entorno es accesible, para cada estado inicial, hay una secuencia fija de operadores que llevan al objetivo.
Si el entorno es semiaccesible (sensor de posición y sensor local suciedad) no hay una secuencia fija que garantice una solución a partir de cualquier estado:
Estados (A=aspiradora, S=suciedad):
(1, AS, S), (2, S, AS), (3, AS, )
(4, S, A), (5, A, S), (6, , AS)
(7, A, ), (8, , A)

Resolución de problemas, II

{1,3} –(absorción)–>{5,7}–(derecha)–> {6,8}–(absorción)–>{6,8}
La solución sería: absorción, derecha, absorción, “absorción si sucio”. Es un árbol de posibles acciones (problema con contingencias)

{1,3}
{5,7}
{2,4}
{6,8}
{5,1,7,3}
S
L
S
R
L
R
S
L
R
L
R
S
{………}

1
2
5
6
3
4
7
8
Secuencia solución: Absorción – derecha – absorción
{1,3} –> {5,7} –> {6,8} –> {6,8}
Resolución de problemas, III