Propagación acotada en búsqueda heurística en tiempo real en entornos inicialmente desconocidos

Author: Carlos Hernández
Advisor: Pedro Meseguer
Year: 2008

This thesis considers bounded propagation of heuristic updates in the context of real-time heuristic search. The basic idea is that a change in the heuristic of a state is propagated towards its sucessors, and the successors of its successors etc. Propagation is bounded, up to a maximum of k states can be reconsidered per planning step. We have developed two strategies of bounded propagation, based on value iteration and local space respectively. We have combined bounded propagation with lookahead greater than the inmediate successors, including the possibility of performing several moves per planning step. All these strategies have been implemented and tested on artificial benchmarks (grids and mazes randomly generated) and real-world benchmarks (maps from commercial computer games), showing the benefits of our approach.