          |
GRASP Student Seminar Series: Spring 2006
April 19, 5:00 PM, 307 Levine Hall
Jongwoo Kim
“Adaptive Randomized Algorithms for Validation and Analysis of
Complex Systems"
Abstract: This work addresses the
problem of validating software-enabled controllers for complex dynamic
systems with dynamic constraints. In such complex systems, the controllers
cannot be designed with performance guarantees. Analytical methods for
analysis fail because the computation of the reachable set for a given
set of initial conditions is intractable. Thus, it is necessary to establish
and verify performance using simulation techniques. This is particularly
true in hybrid systems where the control algorithms often involve a
switching between different controllers. While it is possible to analyze
simple systems and each controller in isolation, there is no systematic
approach to testing and validating the complex continuous and hybrid
systems.
In this work we address the problem of generating sets of conditions
(inputs, disturbances, initial conditions, and parameters) that might
be used to "test" a given complex system. This problem of
testing is related to motion planning. Motion planning addresses the
problem of finding a plan from a starting point or a set of starting
points to a goal point or a goal set. Testing involves finding a trajectory
from a set of initial conditions to a specification set. Typically,
this specification set is the unsafe set. Thus finding a trajectory
to the unsafe set would invalidate the controller. We propose the use
of sampling-based algorithms to the testing and validation problem.
Our work is based on previous work on the Rapidly-exploring Random Trees
(RRT) algorithm. Unlike motion planning problems, the problem of testing
generally involves systems that are not controllable with respect to
disturbances or adversarial inputs and therefore, the reachable set
of states is a small subset of the entire state space. Because of the
differences between testing and motion planning, we propose a new algorithm,
called the Rapidly-exploring Random Forest of Trees (RRFT) algorithm
which allows a search over not only continuous inputs but also time
invariant sets. We also propose three modifications to the original
RRT algorithm, suited for use on uncontrollable systems. We demonstrate
the application of the new algorithms to testing and validation of complex
dynamic systems. The main contribution of this work is an automated
algorithm that analyzes a control system design for complex systems
by finding trajectories that violate safety specifications using sampling
based techniques.
Biography: Jongwoo Kim is a PhD candidate
in the Department of Mechanical Engineering and Applied Mechanics at
the University of Pennsylvania. His research interests include testing
and validation of complex dynamic systems, motion planning methods applied
to robotic and biological systems, and feedback control of mechanical
systems.
GRASP Laboratory
Site maintained by graspadm@grasp.cis.upenn.edu
Last update:18 April, 2006