Bases de Conocimiento
Maestría en Ingeniería en Sistemas
Noviembre – Diciembre 2008
Guido Fidel Flores Pérez
Maestro en Sistemas de Información UDLAP 1990
Master en Redes y Sistemas de Datos UP Madrid 1996
Doctorando en TI y Análisis de Decisiones UPAEP ----
AGENTES PARA LA
SOLUCION DE
PROBLEMAS
Agentes para la Solución de Problemas
Agentes para la solución de problemas
Son Agentes basados en metas que determinan que
deberán hacer por medio de secuencias de acciones que
les permitan obtener estados deseables.
Agentes para la Solución de Problemas
Pasos para la solución de problemas:
Formulación de metas: se establece el objetivo
Formulación del problema: se decide que acciones y
estados habrán de considerarse.
Búsqueda: evaluación de las posibles secuencias de
acciones que le llevan a la meta y elección de la más
apta.
Ejecución: se llevan adelante la solución que presenta la
búsqueda.
Agentes para la Solución de Problemas
Tipos de problemas:
•
Problemas de un solo estado: el agente conoce con exactitud en que
estado se encuentra y el resultado de cada una de sus acciones.
•
Problemas de estados múltiples: el agente no conoce con exactitud en
que estado se encuentra, pero si el resultado de cada una de sus acciones.
•
Problemas de contingencias: el agente no conoce con exactitud en que
estado se encuentra, pero si el resultado de cada una de sus acciones, aunque se
le pueden presentar ciertas contingencias en las mismas.
•
Problemas de exploración: el agente no conoce con exactitud en que
estado se encuentra, ni el resultado exacto de cada una de sus acciones.
Agentes para la Solución de Problemas
Problemas
Definición: Es un conjunto de información que el Agente utiliza para
decidir lo que va a hacer.
Un problema esta compuesto por:
•
Un estado inicial que es donde se encuentra el Agente.
•
Un conjunto de acciones que el Agente puede emprender.
•
La prueba de meta para saber si alcanzo un estado meta.
•
La función costo de ruta que le asigna un valor a una ruta
determinada.
Agentes para la Solución de Problemas
Eficiencia para resolver problemas
Hay tres formas para medir la eficiencia de la
búsqueda:
•
Según permita o no alcanzar la solución,
•
Según su costo de ruta
•
Según el costo de tiempo y memoria para
alcanzar la solución
Agentes para la Solución de Problemas
Elección de estados y acciones
Los estados y acciones se eligen mediante un proceso de
abstracción (eliminación de detalles de una
representación).
Para escoger una buena abstracción hay que eliminar todos
los detalles que sea posible siempre y cuando se conserve
la validez y se garantice que es fácil emprender las
acciones abstractas.
Agentes para la Solución de Problemas
Búsqueda de soluciones
La búsqueda consiste en escoger una opción, haciendo a un
lado las demás para considerarlas posteriormente en caso de no
obtener respuesta alguna mediante la primera opción.
La búsqueda termina cuando se encuentra una solución o
cuando no hay mas estados que expandir.
Agentes para la Solución de Problemas
Árboles de búsqueda
Componentes en la estructura de datos para los árboles de búsqueda:
•
•
•
•
•
El estado al que corresponda el nodo,
El nodo padre,
El operador que se aplico para generar el nodo,
La profundidad del nodo (distancia hasta la raíz),
El costo de ruta desde el estado inicial hasta el nodo.
Agentes para la Solución de Problemas
Estrategia de búsqueda
Las estrategias de búsqueda se evalúan según los siguientes
criterios:
•
Completo: si garantiza o no encontrar la solución si
es que existe.
•
Complejidad temporal: cantidad de tiempo necesario
para encontrar la solución.
•
Complejidad espacial: cantidad de memoria
necesaria para encontrar la solución.
•
Optimización: si se encontrará o no la mejor solución
en caso de que existan varias.
Agentes para la Solución de Problemas
Tipos de estrategias de búsqueda
Las estrategias de búsqueda se pueden agrupar en dos grandes
grupos:
•
Búsquedas sin contar con información (o búsqueda
ciega): no existe información acerca de la cantidad de pasos
necesarios o sobre el costo de ruta para pasar del estado de un
momento dado a la meta.
•
Búsqueda respaldada con información (o búsqueda
heurística): se posee información muy valiosa para orientar la
búsqueda para que sea mas óptima.
Agentes para la Solución de Problemas
Búsquedas sin contar con información
Las seis estrategias de búsqueda sin contar con información son las
siguientes:
•
•
•
•
•
•
Búsqueda preferente por amplitud
Búsqueda de costo uniforme
Búsqueda preferente por profundidad
Búsqueda limitada por profundidad
Búsqueda por profundización iterativa
Búsqueda direccional
Agentes para la Solución de Problemas
Búsqueda preferente por amplitud:
En esta búsqueda todos los nodos que están en la profundidad d del
árbol de búsqueda se expanden antes de los nodos que estén en la
profundidad d+1.
•
Si son varias las soluciones, este tipo de búsqueda permitirá
siempre encontrar primero el estado meta más próximo a la raíz.
•
En esta búsqueda el tiempo y la cantidad de memoria
necesaria crece exponencialmente con respecto a la profundidad.
•
Es óptima y completa.
Agentes para la Solución de Problemas
Búsquedas de costo uniforme:
En esta búsqueda se modifica la estrategia preferente por amplitud en el
sentido de expandir siempre el nodo de menor costo en el margen (medido por
el costo de la ruta g(n)) en vez del nodo de menor profundidad.
Este tipo de búsqueda permitirá siempre encontrar la solución mas barata
siempre y cuando el costo de ruta nunca disminuya conforme avanzamos por
la ruta.
•
En esta búsqueda el tiempo y la cantidad de memoria necesaria crece
exponencialmente con respecto a la profundidad.
•
Es óptima y completa.
Agentes para la Solución de Problemas
Búsqueda preferente por profundidad:
En esta búsqueda siempre se expande uno de los nodos que se encuentren en los mas
profundo del árbol. Solo si la búsqueda conduce a un callejón sin salida, ser revierte la
búsqueda y se expanden los nodos de niveles menos profundos.
Esta búsqueda o se queda atorada en un bucle infinito y nunca es posible regresar al
encuentro de una solución, o a la larga encontrará una ruta de solución mas larga que la
solución óptima.
•
En esta búsqueda el tiempo necesario crece exponencialmente con respecto a la
profundidad, mientras que el espacio requerido en memoria lo hace en forma lineal
•
No es óptima ni completa.
Agentes para la Solución de Problemas
Búsqueda limitada por profundidad:
Esta búsqueda es similar a la búsqueda preferente por profundidad con la
diferencia que se impone un límite a la profundidad máxima de una ruta.
Se utilizan operadores que informan constantemente de la profundad del nodo.
•
En esta búsqueda el tiempo necesario crece exponencialmente con
respecto a la profundidad, mientras que el espacio requerido en memoria lo
hace en forma lineal
•
No es óptima, pero si completa cuando la profundidad del límite es
menor o igual a la profundidad de la solución.
Agentes para la Solución de Problemas
Búsqueda por profundización iterativa:
Esta búsqueda es similar a la búsqueda limitada por profundidad con la
diferencia que se repiten las búsquedas dando en cada iteración un valor
distinto de profundiad para la misma.
•
En esta búsqueda el tiempo necesario crece exponencialmente con
respecto a la profundidad, mientras que el espacio requerido en memoria lo
hace en forma lineal
•
Es óptima y completa.
Agentes para la Solución de Problemas
Búsqueda bidireccional:
Esta es una búsqueda que avanza a partir del estado inicial y que
retrocede a partir de la meta y que se detiene cuando ambas
búsquedas se encuentran en algún punto intermedio.
•
En esta búsqueda el tiempo y el espacio requerido en
memoria crecen exponencialmente con respecto a la mitad de la
profundidad (bd/2).
•
Es óptima y completa.
Agentes para la Solución de Problemas
Comparación entre las diferentes estrategias de búsqueda:
Agentes para la Solución de Problemas
Bibliografía
Janet Finlan & Alan Dix.,
An Introduction to Artificial Inteligence
Addison Wesley Reading,
United States, 1990
Google Books
Waterman, D. A.,
A Guide to Expert Systems,
Addison Wesley Reading,
United States, 1990
Descargar

Document