Tarea

Simulación de un Agente Carro Repartidor aplicando el algoritmo A* en la búsqueda de la mejor ruta

María Esther Ruilova Rojas [*]

Escuela de Ciencias de la Computación Universidad Técnica Particular de Loja meruilova@utpl.edu.ec Resumen. En este trabajo se presenta una solución al problema de encontrar la mejor ruta en el desplazamiento de un punto a otro dentro de una ciudad. Para esto seutilizó el algoritmo A* que pertenece a la familia de algoritmos de la búsqueda informada, cuya principal característica es encontrar, si la hay, la mejor ruta hacia su destino. Para tal efecto, se realizó el planteamiento del problema aplicando conceptos de Inteligencia Artificial, se efectuó el desarrollo teórico de la solución planteada. Además encontrarán la base de conocimientos del agente dela cual aprenderá, la misma que fue realizada en RDF. Finalmente las conclusiones que son el resultado de la ejecución del presente proyecto.

Palabras Claves: Inteligencia Artificial, Algoritmos de Búsqueda, A*.

1. INTRODUCCIÓN
Desde hace muchos años la Inteligencia Artificial se ha enfrentado al reto de crear agentes inteligentes, capaces de no sólo hacer lo que les diga su creador sinotambién capaces de aprender de sus percepciones para tomar decisiones adecuadas e inteligentes. Pero ¿cómo poder hacer esto? Dentro del estudio de la Inteligencia Artificial existen familias de algoritmos que permiten que los agentes encuentren su objetivo de forma más eficaz y eficiente, logrando de esta forma ahorrar recursos de tiempo y espacio; los algoritmos de búsqueda informada manejanheurísticas que nos permiten establecer lineamientos para llevar a cabo dicha búsqueda. Básicamente, el presente proyecto se basó en la simulación de un Carro Repartidor el cuál se mueve a través de las principales calles de la ciudad de Loja, desde cualquier punto hacia otro, estableciendo las distancias entre puntos y las distancias en línea recta hacia cada uno de los puntos Se ha aplicado elalgoritmo A*, que es un algoritmo que se caracteriza por encontrar siempre una solución en caso que exista.

1.1 Problemática
El presente agente, se basa en encontrar la ruta más corta desde un punto origen a un punto objetivo, tomado en cuenta las distancias en línea recta desde San Sebastián (punto origen) hacia cualesquier punto y las distancias entre los diferentes puntos conectados. Como semencionó antes, el entorno son las principales calles de la ciudad de Loja establecidas previamente. El agente carro podrá desplazarse desde cualquier punto origen hacia otro, sin excepción alguna.

1.2 Objetivos
El objetivo del presente trabajo es simular un agente inteligente aplicando técnicas de inteligencia artificial, especialmente algoritmos de búsqueda informada, A*, y que dicho agentellegue a su objetivo con el menor costo basándose en la heurística establecida. Determinar por qué los algoritmos de búsqueda informada son más efectivos que los de búsqueda no informada.

2. FUNDAMENTOS TEÓRICOS
2.1 Agente
“Un agente no es más que cualquier cosa capaz de percibir su medio ambiente con la ayuda de sensores y actuar en ese medio utilizando actuadores ”. [1]

2.2 Agente RacionalEs aquel que hace lo correcto, para de esta manera obtener un mejor resultado.

2.3 Tipos de agentes
A los agentes se los puede clasificar en 4 categorías principales [1]: • • • • Agentes reactivos Agentes reactivos basados en modelo Agentes basados en objetivos Agentes basados en utilidad

Se hace referencia a los agentes reactivos basados en objetivos ya que es el tipo de agenteimplementado en el presente trabajo. Es un agente basado en objetivos ya que se basa en alcanzar un objetivo (nodo objetivo), haciendo una búsqueda en función a la heurística y el algoritmo aplicado, en este caso el Algoritmo A*, que pertenece a la familia de algoritmos de búsqueda informada.

2.4 Estrategias de Búsqueda informada
Las técnicas de solución de problemas de IA, llevan incorporado un...