PROPAGACION ACOTADA EN BUSQUEDA HEURISTICA EN TIEMPO REAL EN ENTORNOS INICIALMENTE DESCONOCIDOS.
Autor	CARLOS HERNANDEZ ULLOA
Profesor guía	PEDRO MESEGUER
Para optar al grado de	DOCTOR EN CIENCIAS DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL.	Institución	INSTITUTO DE INVESTIGACION EN INTELIGENCIA ARTIFICIAL. CONSEJO SUPERIOR DE INVESTIGACIONES CIENTIFICAS BELLATERRA
Lugar	BARCELONA, ESPAÑA	Año	2007
Páginas	184p.
Disciplina	INGENIERIA EN COMPUTACION.	Colección
Ubicación	TESIS/647D
Resumen
LOS PROBLEMAS DE BUSQUEDA EN DONDE EL AGENTE TIENE UN TIEMPO LIMITADO PARA CALCULAR UNA SOLUCION EN UN ENTORNO INICIALMENTE DESCONOCIDO, NO PUEDEN SER ABORDADOS POR MECANISMOS TRADICIONALES DE BUSQUEDA HEURISTICA. ALGUNOS PROBLEMAS DE ESTE TIPO SON LA PLANIFICACION DE RUTAS EN: ROBOTS AUTONOMOS, PERSONAJES DE JUEGOS EN TIEMPO REAL PARAñoRDENADOR Y PAQUETES DE INFORMACION EN REDES DE SENSORES. ESTA TESIS ESTA DEDICADA A RESOLVER ESTE TIPO DE PROBLEMAS, MEDIANTE ALGORITMOS DE BUSQUEDA HEURISTICA EN TIEMPO REAL. PRESENTAMOS VARIOS MECANISMOS GENERICOS QUE APLICADOS A ALGORITMOS EXISTENTES, GENERAN NUEVOS ALGORITMOS. LOS NUEVOS ALGORITMOS QUE DESARROLLAMOS MEJORAN EL RENDIMIENTO DE LAS APROXIMACIONES EXISTENTES. ESTOS SE EVALUAN CONSIDERANDO VARIAS MEDIDAS DE DESEMPEÑO, LAS MAS IMPORTANTES SON: EL COSTE DE LA SOLUCION, EL TIEMPO TOTAL DE BUSQUEDA Y EL TIEMPO POR EPISODIO DE PLANIFICACION. LAS PRINCIPALES IDEAS QUE HEMOS DESARROLLADO EN LA TESIS SON: PROPAGACION ACOTADA DE CAMBIOS HEURISTICOS CON ITERACION DE VALORES: PRESENTAMOS UN MECANISMO DE APRENDIZAJE DE HEURISTICAS BASADO EN EL METODO DE ITERACION DE VALORES DE PROGRAMACION DINAMICA. PROPAGACION ACOTADA DE CAMBIOS HEURISTICOS SOBRE UN ESPACIO LOCAL: PRESENTAMOS UN MECANISMO DE APRENDIZAJE DE HEURISTICAS QUE MEJORA EL MECANISMO BASADO EN ITERACION DE VALORES. COMBINACION ENTRE ANTIPACION Y PROPAGACION ACOTADA: PRESENTAMOS UN MECANISMO QUE PERMITE COMBINAR ANTICIPACION CON PROPAGACION ACOTADA SOBRE UN ESPACIO LOCAL. ESTA COMBINACION MEJORA EL COSTE DE LA SOLUCION AUMENTANDO EL TIEMPO DE PLANIFICACION POR PASO. ANTICIPACION Y MOVIMIENTOS DEL AGENTE. ANALIZAMOS DISTINTAS ESTRATEGIAS DE MOVIMIENTO DEL AGENTE. CADA ESTRATEGIA TIENE UN RENDIMIENTO DISTINTO, EL USO DE UNA U OTRA DEPENDERA DE LA MEDIDA DE DESEMPEÑO QUE MAS IMPORTE AL USUARIO. APLICAICONES: IMPLEMENTAMOS NUESTROS ALGORITMOS EN MAPAS EXTRAIDOS DE JUEGOS EN TIEMPO REAL COMERCIALES PARAñoRDENADOR. EL DESEMPEÑO DE LOS ALGORITMOS ES MEJOR QUE EL DESEMPEÑO DE LAS PRINCIPALES APROXIMACIONES DE LA COMUNIDAD DE BUSQUEDA HEURISTICA EN TIEMPO REAL. TODOS LOS ALGORITMOS PROPUESTOS EN LA TESIS HAN SIDO IMPLEMENTADOS. SE PRESENTAN RESULTADOS FORMALES Y EXPERIMENTALES.