Adaptive Randomized Algorithms for Validation and Analysis of Complex Systems.

Mr. Jongwoo Kim
Ph.D. Candidate
Advisor: Professor Vijay Kumar
Department of Mechanical Engineering
University of Pennsylvania

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 system that analyzes a control system design for complex systems by finding trajectories that violate safety specifications using sampling based techniques.

Thursday, March 23, 2006
2 PM, 337 Towne Bldg.