Smart robot

Informe proyecto Univalle Smart Robot

Presentado al profesor: Oscar Bedoya

Héctor Mario Arana Arias Pedro Briñez Rodríguez

código: 0931120 código: 0910325

Universidad del Valle Escuela de Ingeniería de Sistemas y Computación Inteligencia Artificial Santiago de Cali 2010

Univalle Smart Robot

El proyecto Univalle Smart Robot consistió en la implementación y aplicación de losalgoritmos de búsqueda no informada e informada que se han visto en el curso. La implementación de los algoritmos se realizo utilizando JAVA como lenguaje de programación y la parte grafica del proyecto se realizo con ayuda de NetBeans IDE. Al momento de la implementación de los algoritmos de búsqueda informada se utilizaron las heurísticas; teniendo claro que una heurística muy buena calcula el costopara llegar a la meta sin sobrepasar su valor real y aquí está el fuerte de la utilización de esta técnica al momento de diseñar los algoritmos de búsqueda informada.

Algoritmos de Búsqueda no Informada



Algoritmo de búsqueda Preferente por Amplitud

Para implementar este algoritmo se utilizo una lista con los nodos expandidos, los nodos se iban expandiendo según el orden de llegada,es decir el nodo que primero llega es el primero que se expande, de forma que tomamos el concepto de cola o “el primero en entrar es el primero en atender”, se expande el primero de la lista y después se borra de la lista.



Algoritmo de búsqueda Preferente por profundidad

Para la implementación del algoritmo de búsqueda preferente por profundidad utilizamos la clase stack (pila) queintroduce los nodos y expande el ultimo nodo que entro; asimilando asi el concepto de “ultimo en entrar primero en atender” donde el último elemento que se introduce se expande y luego se borra de la cola siguiendo así el orden de expansión de una pila. Para evitar los ciclos se utiliza una lista con los nodos que ya se visitaron, entonces si ya se visito no lo expande y expande el nodo de menorprofundidad es decir el siguiente en atender de la pila.



Algoritmo de búsqueda por Costo uniforme

Para la implementación de este algoritmo se utiliza un costo por cada movimiento, esto incluye cuando toma una nave; en el caso de la nave 1 puede moverse 10 casillas con el costo por casilla igual a 0,5 y con la nave 2 puede moverse 20 casillas con el costo por casilla igual a 0,5, cuando pasapor un campo electromagnético cuyo costo por pasar es igual a 6 y cuando pasa

por una casilla vacía con costo 1. Ahora el costo total se calcula analizando cuando encuentra los dos ítems y encuentra la salida, cuando encuentra un ítem sigue expandiendo los posibles nodos hasta el segundo ítem y hasta la salida calculando de esta forma cada costo y expandiendo el menor siempre; así se garantizaque la ruta elegida siempre será la menor de todas sea que escoja el ítem 1 o el ítem 2 de primero.

Algoritmos de búsqueda informada Se implementaron dos algoritmos de búsqueda informada Avara y A* cada uno con dos heurísticas: Distancia en línea recta a los objetivos / 2.5 y Distancia de Manhattan a los objetivos / 2.

Heurísticas: Distancia en línea recta a los objetivos / 2.5 La distanciaen línea recta a los objetivos se elije como heurística ya que la situación del problema del Univalle Smart Robot se puede tomar como el problema de viajar de un lugar a otro, entonces una buena medida de estimar el costo de llegada a una meta es la distancia en línea recta porque es la menor distancia que tiene entre un punto a otro y si esto fuera posible entonces el mejor camino debería ser enlínea recta hacia el objetivo. La Distancia en línea recta a los objetivos se divide entre 2.5 para que una de las dos heurísticas escogidas domine a la otra, en este caso Distancia de Manhattan dominara a Distancia en línea recta ya que el valor de la h(n) en todo n será mayor en la distancia de Manhattan que en línea recta debido a que se divide en un número menor (posteriormente veremos que...