Inteligencia Artificial: agentes, búsqueda y representación en espacios de estado

Introducción

IA: estudio del comportamiento inteligente en máquinas. (*) Percibir (Rvoz, VA), razonar (SEs), aprender (RNAs), buscar, comunicarse y actuar en entornos complejos. Sistemas que piensan y actúan racionalmente como humanos. Una parte muy importante de la inteligencia artificial está destinada a la resolución de problemas mediante algoritmos o estrategias de búsqueda.

Agente

Agente: entidad que toma decisiones dependiendo del estado de su entorno. Un agente inteligente es una entidad capaz de percibir su entorno, procesar tales percepciones y responder o actuar en su entorno de manera racional, es decir, de manera adecuada y tendiendo a maximizar un resultado esperado. Es capaz de percibir su medio ambiente con la ayuda de sensores y actuar en ese medio utilizando actuadores (elementos que reaccionan a un estímulo realizando una acción).

Un agente con distintas opciones inmediatas de valores desconocidos puede decidir qué hacer examinando las diferentes secuencias posibles de acciones que le conduzcan a estados de valores conocidos, y entonces escoger la mejor secuencia. Este proceso de hallar dicha secuencia se llama búsqueda.

Búsqueda

La búsqueda consiste en encontrar una secuencia de operadores (acciones) que lleve desde el estado inicial hasta un estado objetivo. Existen enfoques y estrategias distintas, entre las que destacan las siguientes:

• Búsqueda a ciegas: no aprovechan información del dominio. Son búsquedas sistemáticas y exhaustivas, poco eficientes. Aplicación a una gran diversidad de problemas. Ejemplos de estrategias: amplitud y profundidad.
• Búsqueda informada: usan información del dominio para ayudar en la búsqueda. Evitan la explosión combinatoria y resultan muy eficientes (dependen de la función heurística). Ejemplos de estrategias: A^* y voraz.

Nodos y terminología

• Nodo: elementos en el espacio de estados que representan situaciones válidas en el dominio.
• Nodo meta: un nodo terminal que satisface las condiciones del objetivo.
• Nodo raíz: el nodo del que se parte.
• Expansión: obtener todos los posibles sucesores de un nodo en el árbol de búsqueda mediante la aplicación de todos los operadores disponibles relacionados.
• Coste-arco: valor numérico que refleja el coste (tiempo, espacio, etc.) requerido para aplicar un operador a un estado en el proceso de búsqueda. Aunque no se indique explícitamente, siempre debe considerarse un coste implícito, que por defecto puede tomar el valor 1.
• Coste-nodo: medida del coste consumido en alcanzar el nodo en cuestión desde la raíz a lo largo del mejor camino encontrado hasta un momento dado.
• Factor de ramificación: número de descendientes de un nodo, o lo que es lo mismo, número de operadores que pueden aplicarse a un estado (ej.: en árboles binarios es 2).
• Profundidad: longitud del camino más corto desde el estado inicial a una meta. Dicho de otra forma, la longitud de la secuencia más corta de operadores que resuelven el problema. La profundidad del nodo raíz es 0 y la de cualquier otro nodo es la de su antecesor inmediato más 1.

Representación

Representación explícita: mostrar todos los nodos y aristas del árbol.

Representación implícita: estado inicial y efectos que las acciones producen sobre él. A partir de la representación implícita podemos obtener el grafo explícito generando los nodos sucesores del nodo inicial y los sucesores de estos. Existen tres elementos básicos en la representación implícita del grafo de estados: nodo inicial, operadores y condición de éxito.