Todd W. Neller
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.