Introducción Agentes basados en el objetivo de resolución de problemas. Necesaria una formulación de objetivos. Estados y posibles acciones. Ejemplo de mapa de carreteras. Un agente simple de resolución de problemas:
La función RECOMMENDATION devuelve la primera acción en la secuencia. La función REMAINDER devuelve el resto.
Formulación de problemas, I Problema de aspiradora: 8 posibles estados Los estados están contenidos en esta figura:
Dos tipos de problemas: Problemas de estados únicos. Aparecen en entornos accesibles (la percepción determina completamente el estado) y deterministas. Problemas de estados múltiples. Aparecen por ejemplo en entornos no accesibles o no deterministas. Ejemplo (sin sensores; determinista, pero no accesible):
Formulación de problemas, II Si el entorno es no determinista (por ejemplo, “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 (por ejemplo, si tenemos un sensor de posición y un sensor local del estado de suciedad): entonces, 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)
Formulación de problemas, III
{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). Posibles operadores para el estado inicial {1,3}:
{1,3} {5,7} {2,4} {6,8} {5,1,7,3} S L S R L R S L R L R S {………}
Problemas bien definidos Consideramos los problemas más sencillos (problema de estado único): Estado inicial Espacio de estados. Posibles acciones (operadores) sobre cada estado. Cada operador obtiene un estado a partir de otro estado. Función objetivo (estados objetivo). Función de coste de aplicación de los operadores. 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.
Ejemplos, I Los objetivos de la resolución de un problema mediante búsqueda son: Encontrar una solución La solución debe tener coste total mínimo: Coste de búsqueda: Tiempo y memoria necesarios. Coste del camino solución. Ejemplos: Problema del 8-puzle. Coste operadores: 1 Problema de las 8 reinas (en general de las N reinas/damas): Coste operadores: 1 (el camino solución siempre tiene coste 8). Posible representación (1): estado: n reinas en el tablero operadores: añadir una reina a una posición vacía.
Ejemplos, II Posible representación (2): estado: n reinas en el tablero (no atacándose). 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. Criptoaritmética.
Estados: algunas letras sustituidas por dígitos. Operadores: sustituir una letra por un dígito que no aparece ya dentro del estado. La solución se encuentra a profundidad conocida.
FORTY + TEN TEN —— SIXTY
29786 + 850 850 —— 31486
Ejemplos, III Ejemplo de aspiradora. Entorno accesible y determinista. Estados: 8. Operadores: L, R, S Estados objetivo: 7, 8 Coste: 1
Agente sin sensores (entorno no accesible, pero determinista) Estados: subconjuntos de los 8 Coste: 1 Estados objetivo: estados formados por una combinación de 7,8.
Ejemplos, IV Misioneros y caníbales. Hay 3 misioneros y 3 caníbales en la orilla izquierda de un río. Un bote puede transportar a 1 o 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 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, número caníbales lado izquierdo, posición bote (izquierda o derecha). Se debe verificar la Condición. Operadores: Transportar 1 misionero. Transportar 1 canibal. Transportar 2 misioneros. Transportar 2 caníbales. Transportar 1 misionero y 1 caníbal. Coste operador: 1.
Ejemplos, V Otros ejemplos (más reales): Problema de mapa de carreteras. Viajar de una ciudad a otra recorriendo la menor distancia posible. 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 inicio. Problema clásico: debe visitar exactamente 1 vez todas las ciudades (excepto la de inicio que la visita 2 veces). Diseño de circuitos. Navegación de robots. Montaje mecánico de robots. Planificación de toma de imágenes (telescopio Hubble).
Algoritmo general de búsqueda, I Problema del mapa de carreteras: Espacio de estados (finito). Árbol de nodos (infinito), generable.
Un nodo: Un estado (del espacio de estados). Su nodo padre. Operador que lo generó. Profundidad en el árbol de búsqueda. Coste desde nodo inicial.
Algoritmo general de búsqueda, II Algoritmo general de búsqueda (pseudo-C): funcion búsqueda-general (problema, estrategia) returns una solución o fallo { “inicializa árbol de búsqueda con estado inicial” loop { if “no es posible expandir ninguna hoja”, return fallo “elige un nodo hoja a expandir, según la estrategia” if “el nodo es objetivo”, return “la solución” else “expande nodo y añade los nodos resultantes al árbol de búsqueda” } } Con más detalle:
| Página siguiente |