Reference: Neller, T. W. Simulation-Based Search for Hybrid System Control and Analysis. 2000.
Abstract: This dissertation explores new algorithmic approaches to simulation-based optimization, game-tree search, and tree search for the control and analysis of hybrid systems. Hybrid systems are systems that evolve with both discrete and continuous behaviors. Examples of hybrid systems include diverse mode-switching systems such as those we have used as focus problems: stepper motors, magnetic levitation units, and submarine detection avoidance scenarios. For hybrid systems with complex dynamics, the designer may have little other than simulation as a tool to detect design flaws or inform offline or real-time control. In approaching control and analysis of such systems, we thus limit ourselves to a black-box simulation of the system. Among our algorithmic contributions are: - the first multi-dimensional information-based optimization approach, - a generalization of previous multi-level optimization methods, - information-based alpha-beta game-tree search, - syntheses of cell-mapping and game-tree search techniques, - iterative refinement approaches for dynamic action timing discretization, - a best-first search variant with dynamic time-step refinement, - iterative refinement with an epsilon variant of recursive best-first search, and - a dispersion technique for dynamic action parameter discretization. We also formally define several hybrid system game-tree and tree search problems.
Full paper available as doc, ps.