Conceptos Esenciales en Inteligencia Artificial: Resolución de Problemas y Planificación

Conceptos Fundamentales en la Resolución de Problemas y Planificación

Espacio de Estados y Rutas

Espacio de Estados del Problema

Es el conjunto de todos los estados que se pueden alcanzar a partir del estado inicial mediante una secuencia de acciones.

Ruta

Es cualquier secuencia de acciones que permite pasar de un estado a otro.

Búsqueda y Estrategias

Búsqueda

Es el proceso de evaluar las distintas secuencias de acciones para encontrar aquellas que lleven del estado inicial al estado meta.

Estrategias de Búsqueda

Deben ocasionar cambios, ser sistemáticas y ser eficientes.

Características de los Problemas (en relación con errores o estados)

• Ignorables
• Recuperables
• No recuperables

Árbol de Búsqueda

Su raíz corresponde al estado inicial, y sus hojas son nodos sin sucesores. El algoritmo de búsqueda elige el nodo a expandir.

Diseño y Planificación de Agentes

Diseño del Agente

Implica los pasos de: Formular, buscar y ejecutar.

Estrategias de Búsqueda sin Información

Se impone un límite máximo a la profundidad de la ruta, lo que elimina la posibilidad de atascamientos (ej. Búsqueda en Profundidad Limitada).

Ideas Básicas para Dotar a un Agente Planificador

• Representación del objetivo a alcanzar
• Acciones que puede realizar
• Representación del entorno
• Generación de un plan

Plan

Es una secuencia de acciones (listadas) que llevan de un estado inicial a un estado final. Esto puede verse como un problema de búsqueda en un espacio de estados.

Algoritmos de Búsqueda y Planificación

Algoritmos de Búsqueda

Se interesan solo en devolver el estado final o estado-solución.

Algoritmos de Planificación

No solo se interesan por el estado solución, sino también por mantener los estados intermedios que llevan del inicial al final.

Tipos de Planificadores

• Específicos del dominio: Difícilmente pueden utilizarse en otros dominios.
• Independientes del dominio: No eficientes y con pocas aplicaciones prácticas.
• Configurables al dominio: Incluyen conocimiento del dominio para restringir la búsqueda del planificador.

Planificación Clásica y STRIPS

Planificación Clásica (Dominio 1)

Características: Finito, totalmente observable, determinista, estático, discreto.

Planificación Clásica (Dominio 2)

Características: Tiempo implícito, planes secuenciales, planificación offline, objetivo alcanzable.

STRIPS

Fue el primero de los grandes sistemas de planificación. El lenguaje ADL amplía las ideas de STRIPS; ambos son adecuados para dominios reales.

Conceptos Clave en la Definición de Acciones

Precondición

Es una conjunción de literales positivos que especifica lo que debe ser verdadero en un estado antes de que la acción se ejecute.

Efecto

Es una conjunción de literales que describen cómo cambia el estado cuando la acción se ejecuta.

Una acción es aplicable en cualquier estado que satisfaga su precondición.

Heurística

Heurística

En las ciencias de la computación, el método heurístico se utiliza en determinadas circunstancias, especialmente cuando no existe una solución óptima bajo las restricciones dadas. En general, la manera de actuar de los programas heurísticos consiste en encontrar algoritmos con buenos tiempos de ejecución y soluciones eficientes.