Luis Feijoo

Santiago Medina

AGENTE INTELIGENTE:

VIAJERO PERDIDO

ABSTRACT

El presente trabajo describe como resolver un

juego con algoritmos de inteligencia artificial.

El viajero perdido el cual consiste en un carro en el

que un viajero trata de conducir para encontrar el

destino al cual desea llegar, para ello debe ir

pasando por unas calles las cuales tienen

obstáculos y este deberá ir sorteándolos, y

además deberá ir desde el inicio hasta el final

siguiendo la ruta más corta.

INTRODUCCIÓN

En los últimos años la inteligencia artificial a

evolucionado en gran medida hasta el punto que

se han construido maquinas inteligentes que

inclusive tienen la capacidad de aprender.

Abarca un sinnúmero de campos y conceptos

entre los cuales se encuentra el concepto de

agente, se dice que estos constituyen el próximo

avance más significativo en el desarrollo de

sistemas y pueden ser considerados como la

nueva revolución en el software.

DESCRIPCIÓN DEL

PROBLEMA

Meta: El viajero deberá llegar a su destino final

en un corto tiempo, de la manera más

rápida, escogiendo las calles más cortas o ruta

más corta y además deberá evitar chocar con los

obstáculos que se encuentre en su camino.

Inicio: El viajero tendrá un punto de partida

cualquiera, tendrá varias rutas para llegar a su

destino, y este deberá tener la capacidad para

llegar al destino sorteando los obstáculos

colocados en su trayecto.

Obstáculos: Los obstáculos serán casas que

las cuales estarán a lo largo de todo el trayecto.

INGENIERIA DEL AGENTE

Tipo de agente

Basado en Objetivos

Sensores

Sensor para detectar obstáculos.

Sensor de posición final o meta.

Sensor de posición inicial.

Entorno

Calles.- Por donde se va a desplazar el agente

Obstáculos.- Con lo que debe evitar chocar el

agente.

Características entorno

Episódico

Ambiente dinámico

Es accesible

Ambiente continuo

Es no determinista

Actuadores-Acciones

Metas

Es el objetivo final del agente, al llegar a la meta

el agente se detendrá y dará por concluida su

misión.

Algoritmo y tipo de Agente para

este

problema

Hemos determinado que la mejor opción para

resolver este problema es implementar un

agente de búsqueda online.

La búsqueda online intercambia computación con

acción, y difiere en esto con las búsquedas

offline, las cuales determinan una solución antes

de ejecutarla.

Una búsqueda online es necesaria para entornos

dinámicos y semi-dinámicos, es por eso que son

utilizados comúnmente en problemas de

exploración.

Pasos para resolver nuestro

problema:

Primeramente ubicamos la posición de inicio opartida para ello usamos la clase que la hemosdenominado Nodo y enviamos como parámetros:la partida y la casilla en cual se encuentra dichapartida.

Nodo("partida.", this.casilla_partida.Name)

En esta clase utilizamos un procedimientollamado ‘calcular ubicación’ en el cual obtenemosla ubicación de la partida. Para ello hemosdividido a nuestro cuadro en niveles ypasillos, los niveles son tomados en formahorizontal empezando desde cero por la partesuperior, y los pasillos son tomados en formavertical empezando desde cero por la izquierda

Ahora que ya sabemos la ubicación de la partida ubicamos los vecinos de esta partida. Con vecinos nos referimos a los nodos que lo rodean. Para hacer esta ubicación enviamos como parámetro el nivel y pasillo de la partida al procediendo que lo hemos denominado ‘Definir Vecinos’. En este procedimiento, hacemos una comparación:

si nivel = 0

no vecino hacia arriba,

si nivel = 9

no vecino hacia abajo,

si pasillo = 0

no vecino izquierda

si el pasillo = 9

no vecino derecha

Siguiendo los mismos pasos del 1 al 3

calculamos la ubicación de la llegada, así mismo

calculamos los vecinos de la casilla llegada.

A continuación calculamos la heurística y

enviamos como parámetro el nodo partida ya

definido su ubicación y vecinos.

CalcularHeuristica(this.miPartida)

En esta heurística calculamos la distancia queexiste desde la partida, y desde cada vecinodonde no existe un obstáculo, para calcular laheurística utilizamos el nivel y el pasillo en el quese encuentra cada nodo. Con la siguiente formulacalculamos la heurística:

a= nivel_nodo - nivel_llegada

b= pasillo_nodo - pasillo_llegada

h(n): a2 + b2

Math.Sqrt(Math.Pow(a, 2) + Math.Pow(b, 2))

Este algoritmo nos dice que antes de un agentepoder realizar una acción debe calcular laheurística de los nodos sucesores y así luegohacer una comparación de que heurística es lamejor y tomar esa para su próxima acción.

Creamos dos variables de tipo array una para almacenar los nodos que expandiremos del árbol, y otro para almacenar la ruta que nos llevara a la llegada.

Luego Hemos creado un procedimiento llamado BLO(Búsqueda Local Online), el cual a su vez hace un llamado a la función Búsqueda Local Online 1(BLO1), esta función BLO1 lo que nos hace es:

a) Verificar si la casilla en donde nos encontramos es la llegada

b) Llamar a la función expandir nodos enviando como parámetro el nodo en el cual nos encontramos actualmente.

c) En la función expandir nodo verificamos cuantos nodos hojas puede tener un nodo, haciendo una comparación determinamos si un sucesor es un camino o es un obstáculo. En caso de ser un obstáculo pasamos, en caso de ser un camino hacemos el procedimiento del 1 al 3 que es de calcular su ubicación, definir sus vecinos y calcular la heurística.

d) Una vez que definimos cada sucesor de un

nodo lo ubicamos dentro en un array llamado

árbol, calculando el costo desde el padre al

nodo hijo en este caso desde n1 hasta s1 o

desde n1 hasta s2, además calculamos la

heurística de cada nodo hijo o sucesor.

e) Ya tenemos en nuestro árbol el nodo padre y

sus sucesores, con sus respectivas

heurísticas, a continuación creamos un array

auxiliar para poder ordenar nuestro

árbol, ordenamos los sucesores de un nodo

tomando en cuenta la función heurística en

nodo con menor función heurística estará

primero, esto con la finalidad de escoger como

primera opción el nodo con función heurística

más corta.

f) Además debemos tomar en cuenta que nosiempre un nodo con mejor función heurísticaserá el elegido, se debe hacer todo el procesonuevamente con ese nodo con mejor funciónheurística para determinar si los sucesores deeste son obstáculos o caminos y determinar susfunciones heurísticas respectivas. Así es elproceso que se hace nodo a nodo hasta llegaral objetivo final.

g) Una vez que hemos llegado a la meta el nodollegada tendrá una bandera llamada ‘llegada’, elcual nos indicara que hemos llegado al final.

h) Además para poder almacenar las rutas quesigue el agente las almacenamos en un arrayllamado ruta, para luego pasar esta ruta a otroarray llamado mi ruta y poder presentarla enpantalla.

Ontología que permitirá Aprender al

Agente Aprenderagente

Algunas tripletas que obtuvimos

Validando la ontología en la página

http://www.w3.org/RDF/Validator/ARPServlet obtuvimos la

siguiente tabla de tripletas