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

Búsqueda de soluciones: estructura de los problemas

Fernando P.    18/10/2017

Temas:  Fundamentos

Las técnicas de búsqueda de soluciones son muy efectivas en la clase de problemas en los que puede aplicarse. Pero es importante delimitar esa clase de problemas.

Desde el punto de vista de un agente inteligente que deba resolver uno de estos problemas, existen unas cuantas restricciones sobre el entorno, la representación del entorno y el modelo de programación que se deben cumplir para que podamos atacar al problema con técnicas de búsqueda. Estas restricciones ya se vieron en la introducción a la búsqueda de soluciones.

Estructura general de los problemas resolubles mediante búsqueda
La clase de problemas que pueden resolverse usando búsqueda de soluciones tienen una estructura muy bien definida que consta de cinco elementos: estado inicial, acciones, modelo de transición, prueba de factibilidad y función de coste.

Básicamente, esta estructura permite que un agente inteligente pueda construir un conjunto de soluciones factibles para el problema, que son posibles soluciones que verifican todas las condiciones que impone el problema.
Esquema para búsqueda de soluciones
La solución factible que tenga el menor coste será la verdadera solución, o solución óptima, al problema.

En la introducción a la búsqueda de soluciones se propuso un ejemplo muy sencillo de problema que consistía en buscar el itinerario más rápido entre dos estaciones de Metro.

Siguiendo con este ejemplo, soluciones factibles serían aquellos itinerarios que, efectivamente, nos permiten ir desde la estación de origen (Avda. América) hasta la estación de destino. La solución óptima es aquella que lo hace de forma más rápida (menos estaciones en el itinerario).

Estado inicial
El estado inicial se corresponde con el estado del entorno en el momento en el cual al agente comienza a trabajar para resolver el problema.

En el caso del ejemplo del itinerario en Metro, el estado inicial se corresponde con estar en la estación de Avda. de América.

Acciones
Para cada estado del entorno, el agente dispone de una serie de acciones que puede ejecutar. Estas acciones, en egeneral, serán distintas en cada estado del entorno.

Siguiendo con el ejemplo del Metro, estando en una estación determinada, el conjunto de posibles acciones que podemos tomar en esa estación consiste en elegir una línea que pase por esa estación y un sentido de circulación para llegar a otra estación que nos permita cambiar de línea o que constituya el destino.

Por ejemplo, estando en la Avda. de América, nuestras posibles acciones son:

Modelo de transición Búsqueda itinerario Metro
El modelo de transición es una aplicación que, dado un estado actual y una acción escogida por el agente (aplicable al estado actual) nos proporciona un nuevo estado del entorno.

El estado inicial, conjuntos de acciones y modelo de transición definen conjuntamente lo que llamamos espacio de estados, que es el conjunto de todos los estados de el entorno que pueden darse a partir del estado inicial mediante acciones tomadas por el agente.

Para el ejemplo del Metro, el modelo de transición es simple. Elegida una línea y sentido de circulación llegamos a la siguiente estación que conecte con otra línea distinta. Desde el estado inicial, estas serán las transiciones posibles para el ejemplo:

Prueba de factibilidad
Antes y después de cada acción, el agente tiene que comprobar si se han alcanzado los objetivos propuestos para el problema, de forma que se pueda dar por localizada una solución factible para el problema.

En el ejemplo del Metro, tenemos una solución factible una vez que hemos ejecutado una acción que consiste en tomar una línea de Metro con la que podemos alcanzar la estación de Sol directamente. Es una comprobación inmediata, pero en otros problemas más complejos puede no ser tan fácil comprobarlo.

Función de coste
Cada vez que el agente ejectua una acción y el entorno cambia como consecuencia de esa acción (según el modelo de transición), se produce un coste individual de esa acción que se suma al coste general de la solución factible que el agente está construyendo.

El coste total de cada solución factible es la suma de los costes individuales de cada acción tomada por el agente. La solución óptima es aquella que tiene menos coste total.

Para el ejemplo del Metro, las acciones tomadas tienen coste equivalente al número de estaciones por las que pasamos hasta llegar al siguiente destino elegido:

En el ejemplo, la solución óptima consiste en tomar la línea 9 desde Avda. de América hasta Príncipe de Vergara (+2 estaciones) y en Príncipe de Vergara tomar la línea 4 hasta Sol (+4 estaciones) obteniendo un coste total de 6 estaciones, que se puede verificar que es el menor de todas las soluciones factibles.

Elección de soluciones
La característica más interesante de los problemas que se pueden resolver mediante búsqueda de soluciones es que el espacio de estados está muy bien definido y solucionar el problema puede ser tan sencillo como construir un agente que evalúe todas las soluciones factibles y se quede con la de menor coste.

Esta forma de proceder tan sencilla nos asegura una forma de atacar el problema. Pero en problemas de cierto tamaño el espacio de estados puede ser tan grande que resulta inabordable.

Las técnicas de búsqueda de soluciones, que se irán viendo en sucesivos artículos, abordan el espacio de estados de forma que podamos ir descartando zonas inmensas del mismo para ir quedándonos con regiones muy pequeñas que podamos evaluar para encontrar la solución óptima o, al menos, una que sea mucho mejor que la inmensa mayoría de soluciones factibles.



La beneficiosa estructura de este tipo de problemas permite localizar buenas soluciones con facilidad, pero en problemas complejos no es suficiente y son necesarias técnicas muy refinadas que nos permitan centrarnos en zonas prometedoras del espacio de estados.



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