6.5 Agentes basados en algoritmos de búsqueda

Agentes basados en algoritmos de búsqueda

Tras el estudio en profundidad del problema que plantea la naturaleza del entorno  en el cálculo de recorridos mínimos, y una definición formal de la apariencia que tendrán los agentes inteligentes que se integrarán en él con el fin de aportar soluciones, debemos consensuar más explícitamente el cuerpo que tendrán estos, planteando como razonarán en el camino a la toma de decisiones, y en base a qué criterios, según la propuesta planteada en el apartado de objetos de la presente memoria.

Para el cálculo de recorridos mínimos, nuestros agentes inteligentes se encontrarán basados en algoritmos de búsqueda, modelo que, bajo definición, hace que los agentes mantengan un modelo simbólico del mundo a tratar, deseando modificar el estado del mundo de acuerdo a sus objetivos, para ello anticipando los efectos esperados de sus acciones sobre el modelo.

Técnicas basados en búsqueda

La funcionalidad más compleja del proyecto reside en el cálculo del recorrido mínimo entre dos estaciones x e y sobre la red de estaciones de línea del metro de Madrid, que como ya hemos analizado, podría equipararse a una representación compuesta por listas de líneas, cada una de las cuales contuviera, siguiendo fielmente la infraestructura de la Red de Metro, el listado de nodos estación con la información necesaria para su descripción. La dificultad reside en la descomposición del problema en tres partes fuertemente caracterizadas, y que tienen por objetivo fundamental proveer al proyecto de una mayor funcionalidad, y al usuario de un mayor número de recursos operativos con los que contar, y de un rango de criterios diverso y de importancia mayor o menor según los gustos y/o las circunstancias del viajero: Recorrido mínimo por menor distancia recorrida, recorrido mínimo por menor número de estaciones y transbordos, y recorrido mínimo más rápido (menor tiempo en minutos aproximado), para cada uno de los cuales deberemos construir agentes inteligentes basados en algoritmos de búsqueda diferentes.

Para el primer caso utilizaremos un algoritmo de búsqueda A*, algoritmo de exploración informado que se rige por un coste real asociado (costes unitarios entre estación y estación más la adición unitaria en caso de transbordo) y un coste estimado heurístico (la distancia en línea recta entre la estación origen y la destino) para alcanzar la solución; para los dos casos siguientes, utilizamos el algoritmo de Coste Uniforme, algoritmo no informado conocido también como Uniform Cost Search, el cual guía la búsqueda de los operadores para la determinación del camino más corto dado un vértice o estación origen al resto de estaciones hasta topar con la destino en nuestra estructura por el coste real, definido éste cómo g(n), un coste mínimo para llegar del nodo inicial al nodo n, expandiendo siempre el nodo de menor coste g primero; sobre nuestros dos agentes basados en algoritmos de búsqueda de coste uniforme, precisar que el coste real g para el recorrido mínimo por menor número de estaciones y transbordos será el número de estaciones recorridas y transbordos realizados hasta el momento, y para el recorrido mínimo más rápido el números de minutos transcurridos entre estación y estación en las estaciones recorridas hasta ese momento.

Creative Commons License
Poiritem by Ismael Rihawi Aragón is licensed under a Creative Commons Reconocimiento-No comercial-Sin obras derivadas 3.0 España License.
Anuncios

Los comentarios están cerrados.