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ón actual 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 
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
| Página siguiente |