Conceptos Fundamentales de Agentes Inteligentes

Definición y Características

Un agente se define como una entidad que percibe su entorno a través de sensores y actúa sobre él mediante actuadores. La función del agente especifica la acción que este debe realizar en respuesta a cualquier secuencia de percepciones. El comportamiento del agente se evalúa mediante una medida de rendimiento. Un agente racional busca maximizar el valor esperado de esta medida, considerando las percepciones acumuladas.

Entorno de Trabajo

El entorno de trabajo incluye la medida de rendimiento, el entorno externo, los actuadores y los sensores. Es crucial especificar completamente el entorno de trabajo al diseñar un agente. Los entornos varían según varios parámetros:

• Visibilidad: Total o parcialmente observables.
• Determinismo: Deterministas o estocásticos.
• Episódicos: Episódicos o secuenciales.
• Estáticos: Estáticos o dinámicos.
• Discretos: Discretos o continuos.
• Número de agentes: Un único agente o múltiples agentes.

Tipos de Agentes

El programa del agente implementa la función del agente. Existen diversos diseños, que varían en eficiencia, solidez y flexibilidad. La elección del diseño depende de la naturaleza del entorno. Algunos tipos de agentes son:

• Agentes reactivos simples: Responden directamente a las percepciones.
• Agentes reactivos basados en modelos: Mantienen un estado interno para rastrear aspectos no evidentes en las percepciones actuales.
• Agentes basados en objetivos: Actúan para alcanzar sus metas.
• Agentes basados en utilidad: Intentan maximizar su «felicidad» esperada.

Todos los agentes pueden mejorar su rendimiento mediante mecanismos de aprendizaje.

Formulación y Resolución de Problemas

Formulación del Problema

Para buscar soluciones, un agente debe formular un objetivo y, a partir de él, un problema. Un problema consta de:

• Estado inicial.
• Conjunto de acciones.
• Función para el test objetivo.
• Función de costo del camino.

El entorno del problema se representa como un espacio de estados. Una solución es un camino a través del espacio de estados desde el estado inicial hasta un estado objetivo.

Algoritmos de Búsqueda

Se puede utilizar un algoritmo general de BÚSQUEDA-ÁRBOL para resolver cualquier problema. Las variantes del algoritmo incorporan diferentes estrategias. Los algoritmos de búsqueda se evalúan según:

• Completitud
• Optimización
• Complejidad en tiempo
• Complejidad en espacio

La complejidad depende de b (factor de ramificación) y d (profundidad de la solución más superficial).

Algoritmos Específicos

• Búsqueda primero en anchura: Expande el nodo no expandido más superficial. Es completo, óptimo para costos unitarios, pero su complejidad espacial (O(b^d)) lo hace poco práctico en muchos casos.
• Búsqueda de coste uniforme: Similar a la búsqueda primero en anchura, pero expande el nodo con el menor costo del camino (g(n)). Es completo y óptimo si el costo de cada paso supera un valor positivo.
• Búsqueda primero en profundidad: Expande el nodo no expandido más profundo. No es completo ni óptimo, pero su complejidad espacial (O(bm), donde m es la profundidad máxima) es menor que la búsqueda en anchura.
• Búsqueda de profundidad limitada: Impone un límite de profundidad a la búsqueda primero en profundidad.
• Búsqueda de profundidad iterativa: Llama a la búsqueda de profundidad limitada, aumentando el límite hasta encontrar un objetivo. Es completo, óptimo para costos unitarios y tiene una complejidad espacial de O(bd).
• Búsqueda bidireccional: Puede reducir la complejidad temporal, pero no siempre es aplicable y puede requerir mucho espacio.
• BÚSQUEDA-GRAFOS: Cuando el espacio de estados es un grafo, este algoritmo elimina estados duplicados.

En entornos parcialmente observables, el agente puede aplicar algoritmos de búsqueda en el espacio de estados de creencia. En algunos casos, se necesita un plan de contingencia para manejar circunstancias desconocidas.

Búsqueda Heurística y Métodos Avanzados

Búsqueda Primero el Mejor y A*

Búsqueda primero el mejor es una BÚSQUEDA-GRAFO que selecciona para expansión los nodos de menor costo según alguna medida. Se utiliza una función heurística h(n) que estima el costo de una solución desde n.

• Búsqueda primero el mejor avara: Expande nodos con h(n) mínima. No es óptima, pero suele ser eficiente.
• Búsqueda A*: Expande nodos con mínimo f(n) = g(n) + h(n). Es completa y óptima si h(n) es admisible (para BÚSQUEDA-ÁRBOL) o consistente (para BÚSQUEDA-GRAFO). Su complejidad espacial sigue siendo un problema.

Construcción de Heurísticas

El rendimiento de los algoritmos de búsqueda heurística depende de la calidad de la función heurística. Las heurísticas se pueden construir:

• Relajando la definición del problema.
• Usando costos precalculados para subproblemas.
• Mediante bases de datos de patrones.
• Aprendiendo de la experiencia.

Algoritmos con Memoria Limitada

BRPM (Búsqueda Recursiva Primero el Mejor) y A*MS (A* Simplificado con Memoria) son algoritmos robustos y óptimos que utilizan cantidades limitadas de memoria.

Búsqueda Local y Algoritmos Genéticos

Los métodos de búsqueda local, como la ascensión de colinas, operan en formulaciones completas de estados. El temple simulado es un algoritmo estocástico que puede encontrar soluciones óptimas. Muchos métodos de búsqueda local se aplican a espacios continuos.

Un algoritmo genético es una búsqueda de ascensión de colinas estocástica que mantiene una población de estados. Los nuevos estados se generan por mutación y cruce.

Problemas de Exploración

Los problemas de exploración surgen cuando el agente desconoce los estados y acciones de su entorno. Los agentes de búsqueda en línea pueden construir un mapa y encontrar un objetivo en entornos seguramente explorables. Las estimaciones heurísticas actualizadas por la experiencia ayudan a escapar de mínimos locales.

Lógica Proposicional y Agentes Basados en Conocimiento

Representación del Conocimiento

Los agentes inteligentes necesitan conocimiento para tomar decisiones. El conocimiento se representa mediante sentencias en un lenguaje de representación del conocimiento y se almacena en una base de conocimiento.

Un agente basado en conocimiento consta de una base de conocimiento y un mecanismo de inferencia. El agente almacena sentencias, infiere nuevas sentencias y las utiliza para decidir qué acciones tomar.

Lenguaje de Representación

Un lenguaje de representación se define por su sintaxis (estructura de las sentencias) y su semántica (valor de verdad en cada mundo posible o modelo).

Implicación e Inferencia

La implicación entre sentencias es crucial. Una sentencia a implica otra sentencia B si B es verdadera en todos los mundos donde a lo es. Conceptos relacionados son la validez (a => B) y la insatisfacibilidad (a A ¬B).

La inferencia es el proceso de derivar nuevas sentencias a partir de las existentes. Los algoritmos de inferencia sólidos solo derivan sentencias implicadas; los algoritmos completos derivan todas las sentencias implicadas.

Lógica Proposicional

La lógica proposicional es un lenguaje sencillo con símbolos proposicionales y conectivas lógicas. Permite manejar proposiciones verdaderas, falsas o desconocidas.

La implicación se puede comprobar enumerando los modelos (que son finitos). Existen algoritmos eficientes de comprobación de modelos, como backtracking y búsqueda local.

Reglas de Inferencia y Razonamiento

Las reglas de inferencia son patrones de inferencia sólidos. La resolución proporciona un algoritmo de inferencia completo para bases de conocimiento en forma normal conjuntiva. El encadenamiento hacia delante y el encadenamiento hacia atrás son algoritmos adecuados para bases de conocimiento en cláusulas de Horn.

Agentes Basados en Inferencia y en Circuitos

Se pueden diseñar dos tipos de agentes que utilizan la lógica proposicional:

• Agentes basados en inferencia: Utilizan algoritmos de inferencia para rastrear el mundo y deducir propiedades ocultas.
• Agentes basados en circuitos: Representan proposiciones mediante bits y las actualizan utilizando propagación de señal.

Limitaciones de la Lógica Proposicional

La lógica proposicional es útil para ciertas tareas, pero no es escalable a entornos ilimitados debido a su limitada capacidad para manejar el tiempo, el espacio o patrones genéricos de relaciones entre objetos.