Algorithms for Real-Time Game-Tree Search for Hybrid System Control

Hybrid Systems and AI: Modeling Analysis and Control of Discrete Plus Continuous Systems

Volume

Papers from the 1999 AAAI Spring Symposium

Contents

This paper describes four algorithms for real-time game-tree search for hybrid system control. A hybrid system control game is a hybrid system with discretely and continuously evolving scores, and an enabled action set for each player. As computational speed increases, we can expect simulation to become more useful for informing control decisions in real-time. To this end, we seek to extend existing game-tree search techniques for real-time hybrid system control. We introduce the notion of an n-player augmented cellmap and apply both dynamic programming and an anytime minimax algorithm with caching. For games with zero-sum scores, we generalize alpha-beta for nplayers. Combining the best characteristics of these algorithms, we introduce a generalized caching alphabeta algorithm for graphs. We discuss the benefits and limitations of each algorithm.