Title
Information-Based Alpha-Beta Search and the Homicidal Chauffeur
Document Type
Article
Publication Date
2002
Department 1
Computer Science
Abstract
The standard means of applying a discrete search to a continuous or hybrid system is the uniform discretization of control actions and action timing. Such discretization is fixed a priori and does not allow search to benefit from information gained at run-time. This paper introduces Information-Based Alpha-Beta Search, a new algorithm that preserves and benefits from the continuous or hybrid nature of the search. In a novel merging of alpha-beta game-tree search and information-based optimization, Information-Based Alpha-Beta Search makes trajectory-sampling decisions dynamically based on the maximum-likelihood of search pruning. The result is a search algorithm which, while incurring higher computational overhead for the optimization, manages to so increase the quality of the sampling, that the net effect is a significant increase in performance. We present a new piecewise-parabolic variant of the algorithm and provide empirical evidence of its performance relative to random and uniform discretizations in the context of a variant of the homicidal chauffeur game.
DOI
10.1007/3-540-45873-5_26
Recommended Citation
Neller, Todd. "Information-Based Alpha-Beta Search and the Homicidal Chauffeur," in C.T. Tomlin and M.R. Greenstreet, eds., Lecture Notes in Computer Science 2289, Hybrid Systems: Computation and Control, Proceedings of the Fifth International Workshop (HSCC '02, Stanford University, Palo Alto, California, USA, 2002), pp. 323-336, Springer Verlag, 2002.
Comments
Original version is available from the publisher at: http://link.springer.com/chapter/10.1007/3-540-45873-5_26