Bsi

Resolución de
problemas
mediante búsqueda
“Búsqueda ciega, no informada”
“Búsqueda heurística, informada”
1

Introducción




Agentes de resolución de problemas:
es un tipo de agentes basados en el
objetivo.
Algoritmos no informados: no disponen
de ninguna información adicional a la
propia definición del problema
» Es necesario realizar
– formulación de objetivos basada en:
 la situaciónactual
 medida sobre el desempeño de la tarea
– Formulación del problema mediante
 estados posibles
 acciones a ejecutar

» Algoritmo: simple-problem-solving-agent
– Diseñado: Formulate, Search, Execute

» Ejemplos
– mapa de carreteras
– viajante de comercio

2

Agente simple de
resolución de problemas
“Formulate, Search, Execute”

Etapas de la resolución de
problemas con objetivos:
1. Formulaciónde 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
Obs:
RECOMMENDATION
devuelve la primera acción (first) de la secuencia.
REMAINDER
devuelve el resto (rest) de la secuencia
(Russell 2nd. Ed.)

3

Formulación de problemas, I
(ejemplo)


Problema de aspiradora:
» Se dispone de una aspiradora conacceso
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, noaccesible
– 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.
4

Formulación de problemas, II
(abstracción)
El mundo tiene dos posiciones: puede
haber o no suciedad
El agente está en una u otra posición
1

5

26

7

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

3

4

8

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

5

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

6

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
quepueden 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 losoperadores 7

Formulación de problemas, V
(Problema Bien Definido)
Estados?

Posiciones de la suciedad y del
robot

Estado inicial?

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

El que se designe

Operadores? Left (L), right (R), suck (S)
(1 R 2), (1 S 5) … 1

Función sucesor?

2

Objetivo? NoDirt(x)
Coste del
camino?

1 por
operador
5

6

3

7

4

8

8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...