Inteligenica Artificial I Alejandro Permingeat Inteligencia Artificial de Russell y Norving 1° edición 1996 Parte II Capítulo III

Inteligenica Inteligenica Artificial IArtificial IAlejandro Permingeat

Inteligencia Artificialde Russell y Norving

1° edición 1996

Parte II

Capítulo III

Agentes para la solucion 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.

Alejandro Permingeat 2

Agentes para la solucion de problemas

Pasos para la solución de problemas:

1. Formulación de metas: se etablece el objetivo

2. Formulación del problema: se decide que acciones y estados habran de conciderarse.

3. Busqueda: evaluacion de las posibles secuencias de acciones que le llevan a la meta y elección de la mas apta.

4. Ejecución: se llevan adelante la solución que presenta la búsqueda.



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.


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


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


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.


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


Árboles de búsqueda.

Componentes en la estructura de datos para los árboles de búsqueda:

1. El estado al que corresponda el nodo,2. El nodo padre,3. El operador que se aplico para generar el nodo,4. La profundidad del nodo (distancia hasta la raíz),5. El costo de ruta desde el estado inicial hasta el

nodo.


Estrategia de búsqueda.

Las estrategias de búsqueda se evalúan según los siguientes criterios:

• Completez: 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.

• Optimidad: si se encontrará o no la mejor solución en caso de que existan varias.


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.


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


Búsquedas 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 optima y completa.


Búsquedas de costouniforme.

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 optima y completa.


Búsquedas 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.


Búsquedas 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.


• No es óptima, pero si completa cuando la profundidad del límite es menor o igual a la profundidad de la solución.


Búsquedas 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.


• Es óptima y completa.


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.

Documents

Inteligenica Artificial I Alejandro Permingeat Inteligencia Artificial de Russell y Norving 1° edición 1996 Parte II Capítulo III