Sistemas de informacion

ALUMNO: ZATARAIN GALVEZ DANIEL

MATRICULA: 0640642

MATERIA: INTELIGENCIA ARTIFICIAL (IA)

MAESTRO: VICENTE OCHOA

CULIACAN SINALOA, 18 DE NOVIEMBRE DEL 2009

“Algoritmos de búsqueda heurística en tiempo real.
Aplicación a la navegación en los juegos de vídeo”
Introducción

La constante evolución de los juegos de vídeo ha llevado a que la inteligencia artificial
Constituya uno de los aspectosmás importantes; es fundamento al que los agentes
(entidades autónomas) controlados por la computadora se comporten en forma
inteligente. Un problema característico es la navegación, que consiste en determinar el
camino más conveniente entre una posición inicial y una posición de destino. Si bien el
planteo del problema es sencillo, el mismo está lejos de ser trivial debido a la crecientecomplejidad de los entornos simulados y los requerimientos de tiempo real de los juegos
modernos.

La búsqueda es una de las técnicas más utilizadas para resolver los problemas de
pathfindin1 o planificación que se presentan en la inteligencia artificial en los juegos de
vídeo. En particular, la búsqueda es utilizada para resolver el problema de la navegación.
De los distintos tipos de algoritmos debúsqueda, los algoritmos búsqueda
heurística completa se encuentran ampliamente difundidos. Sin dudas, el algoritmo A* es
el algoritmo de búsqueda heurística más popular.

Los algoritmos heurísticos tradicionales muestran limitaciones importantes cuando el
espacio de búsqueda es demasiado grande o existen factores dinámicos. En la
navegación, de los juegos de vídeo en tiempo real, este problema aparececuando las
rutas a determinar son muy largas, el terreno es modificable o existen muchos objetos
móviles. Bajo esas condiciones, los algoritmos de búsqueda básicos no pueden responder
en el tiempo requerido y resultan inadecuados. De esta forma, surge la necesidad de
desarrollar nuevas estrategias de búsqueda, que se adapten a los requerimientos de
tiempo real de los juegos de vídeo y resuelvanadecuadamente caminos en condiciones
de incertidumbre sobre terrenos de gran extensión.

Actualmente existen dos clases de algoritmos de búsqueda que se adecuan a la
resolución de problemas con las características mencionadas: los algoritmos de
búsqueda heurística incrementales y los algoritmos de búsqueda heurística en tiempo
real . Los algoritmos incrementales utilizan información de búsquedasprevias para
encontrar soluciones a problemas similares posiblemente más rápido que realizando
cada búsqueda partiendo de cero. Por otra parte, los algoritmos de búsqueda
en tiempo real alternan planificación y ejecución del plan y restringen la planificación a
la parte del dominio inmediata al estado actual del agente.

Aunque ambas técnicas se adaptan a los requerimientos de los juegos en tiemporeal,
la idea de dividir la planificación en etapas de duración limitada parece ser la más
difundida. Esto se debe a que los algoritmos de tiempo real se basan en las estrategias de
búsqueda de profundidad limitada utilizadas en los problemas de juegos de dos
jugadores como el ajedrez, las damas y el Othello.
Fundamentos de la búsqueda en tiempo real

La búsqueda es una técnica para resolver problemascuya solución consiste en una serie
de pasos que frecuentemente deben determinar se mediante la prueba sistemática de las
alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en
diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción
de restricciones y problemas de pathfinding de un único agente.

Los algoritmos de búsquedacompleta 2 tradicionales se caracterizan por su modo de
operación off - line , que determina que debe encontrar se la solución entera en una única
etapa de planificación, antes de comenzar la ejecución de los pasos o acciones que la
componen . Es posible utilizar este esquema de búsqueda si se cuenta con la
información suficiente sobre el problema y el tamaño del espacio de búsqueda permite el...