Revolución IA

La Inteligencia Artificial está llamada a protagonizar la próxima Revolución tecnológica

Inicio Sobre Revolucionia Temas Para saber más Contacto

Introducción a la búsqueda de soluciones

Fernando P.    09/10/2017

Temas:  Fundamentos

Hemos tratado en artículos anteriores sobre el concepto de agente inteligente y sobre cómo se pueden diseñar agentes que puedan funcionar en distintos tipos de entornos.

Existen muchos problemas relativamente comunes que pueden describirse en términos de entornos bastante sencillos y para los que no es difícil diseñar agentes inteligentes que puedan resolverlos.

En este artículo vamos a introducir este tipo de problemas y vamos a hacer una primera aproximación al diseño de agentes inteligentes para resolver estos problemas.

Problemas que se pueden solucionar mediante búsqueda
Para facilitar la comprensión del tipo de problemas que pueden ser resueltos mediante búsqueda, vamos a ver un ejemplo sencillo de uno de estos problemas y vamos a usarlo para describir las propiedades clave de este tipo de problemas.

Supongamos que somos turistas en Madrid, estamos alojados en un hotel en la Avenida de América y deseamos ir en Metro a la Puerta del Sol lo más rápido posible, no conocemos la red de Metro pero tenemos un plano. Nuestro problema se caracteriza por lo siguiente:

Búsqueda itinerario Metro Este problema no es difícil de resolver, es tan sencillo como buscar todos los posibles itinerarios en el plano, sumar cuantas estaciones componen cada uno y quedarnos con el que menos estaciones tenga.

Si hacemos unos números, veremos que el camino más corto es ir por Príncipe de vergara, como se muestra en la ilustración adjunta que resume algunos posibles itinerarios en forma de grafo.

Si en vez de Madrid, consideramos una ciudad más grande como Londres, igual ya no es tan fácil. Y si en vez de una red de Metro consideramos la red de carreteras de la Unión Europea y deseamos ir de Madrid a Helsinki en el mínimo tiempo posible, la cosa se complica peligrosamente. Pero la estructura de todos estos problemas es muy similar.

Entorno de agentes inteligentes que resuelven problemas de búsqueda
Para diseñar un agente inteligente, lo primero que tenemos que hacer es establecer el tipo de entorno para el agente, porque esto va a condicionar todas las decisiones de diseño del agente.

Los problemas que se pueden solucionar mediante búsqueda usando agentes inteligentes son muy homogéneos y se caracterizan porque definen un entorno para el agente con las siguientes propiedades, que se van a ilustrar con el ejemplo descrito:

Si tenemos un problema que se puede modelizar mediante un entorno observable, determinístico, discreto, estático y conocido podemos resolverlo con un agente inteligente mediante búsqueda.

Representación del entorno en problemas a resolver usando búsqueda
La representación del entorno para un agente inteligente es de gran importancia. Ya vimos que esta podía ser atómica, factorizada o estructurada.

Para el caso que nos ocupa, relativo a los problemas a resolver por búsqueda, la representación del entorno debe ser atómica. Si precisamos de una representación más elaborada del entorno, tenemos un problema que no va a ser fácil de resolver usando las técnicas de búsqueda habituales.

Programación de agentes inteligentes que resuelven problemas de búsqueda
Una vez que tenemos claras las propiedades del entorno sobre el que se va a desenvolver nuestro agente, necesitamos escoger un modelo de programación para el agente.

Generalmente, los problemas que deben resolverse usando búsqueda tienen una cantidad muy elevada de posibles estados del entorno. En el ejemplo visto tan simple, cada estación de Metro es un posible estado en el que nos podemos encontrar y son varias docenas (si consideramos todas las que hay en Madrid).

Los modelos de programación reactiva exigen tener una base de datos que codifica las acciones a tomar por el agente con cada posible estado del entorno. Estos modelos no son viables para problemas de búsqueda porque el elevado número de posibles estados implicaría una base de datos inmensa.

El modelo de programación preferido en este tipo de problemas es la programación basada en objetivos. No tenemos una acción definida de antemano a ejecutar en cada estado del entorno pero sí tenemos un objetivo que alcanzar, que va guiando la búsqueda de la solución al problema. En el caso de nuestro ejemplo se trata de llegar a la Puerta del Sol lo más rápido posible.

Para problemas muy sencillos, como el ejemplo propuesto, es factible localizar todas las secuencias de estados del entorno que nos permiten conseguir nuestro objetivo (itinerarios en el ejemplo) para quedarnos con la más eficaz (la más rápida en el ejemplo). Pero esto es inviable en problemas realistas de cierto tamaño.

En general, la misión de un agente inteligente es localizar una solución aceptable sin tener que evaluar todas las posibles combinaciones de estados del entorno. Cuantas menos evaluaciones tenga que hacer el agente, mejor será.



Una vez delimitada la clase de problemas que pueden ser resueltos mediante búsqueda, podemos diseñar una arquitectura general de agente que pueda resolver estos problemas, así como algoritmos específicas de búsqueda. Esto se verá en sucesivos artículos.



Para saber más:

Este libro tiene varios capítulos dedicados a agentes inteligentes así como resolución de problemas mediante búsqueda y seguramente sea el mejor recurso que se puede encontrar para profundizar en este tema.



 

Inicio Powered by NetBSD
 
HTML5
 
En general, todo el contenido de este sitio web es original, salvo referencias o enlaces a otros sitios web y citas o reproducciones expresamente presentadas como tales.

No está permitida la reproducción ni la copia del contenido de este sitio web sin el permiso expreso de la propiedad del mismo.

Este sitio web no utiliza cookies ni ningún otro mecanismo para almacenar información en los navegadores de los visitantes ni para realizar seguimiento de los mismos.

2017,2018 Revolucionia.net
Sobre Revolucionia
Temas
Para saber más
Contacto