Online Bridged Pruning for Real-Time Search with Arbitrary Lookaheads

Online Bridged Pruning for Real-Time Search with Arbitrary Lookaheads

Carlos Hernandez, Adi Botea, Jorge A. Baier, Vadim Bulitko

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 510-516. https://doi.org/10.24963/ijcai.2017/72

Real-time search algorithms are relevant to time-sensitive decision-making domains such as video games and robotics. In such settings, the agent is required to decide on each action under a constant time bound, regardless of the search space size. Despite recent progress, poor-quality solutions can be produced mainly due to state re-visitation. Different techniques have been developed to reduce such a re-visitation with state pruning showing promise. In this paper, we propose a novel pruning approach applicable to the wide class of real-time search algorithms. Given a local search space of arbitrary size, our technique aggressively prunes away all states in its interior, possibly adding new edges to maintain the connectivity of the search space frontier. An experimental evaluation shows that our pruning often improves the performance of a base real-time search algorithm by over an order of magnitude. This allows our implemented system to outperform state-of-the-art real-time search algorithms used in the evaluation.
Keywords:
Combinatorial & Heuristic Search: Heuristic Search
Planning and Scheduling: Real-time Planning
Robotics and Vision: Motion and Path Planning