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

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.