Adaptive randomized algorithms for validation and analysis of complex systems

This thesis addresses the problem of validating software-enabled controllers for complex 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 trajectory 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 for the testing and validation problem. Our work is based on previous work on the Rapidly-exploring Random Trees (RRT) algorithm, originally proposed by LaValle and Kuffner, to obtain test inputs. 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 improve upon the algorithm in the following ways.; We propose a new algorithm, called the Rapidly-exploring Random Forest of Trees (RRFT) algorithm. While the traditional RRT algorithm only searches over continuous inputs based on a Voronoi biasing, RRFT algorithm can also search over time invariant sets by growing a set of trees for each time-invariant value choice. We also propose three modifications to the original RRT algorithm, suited for use on uncontrollable systems. First, we introduce a weighting to penalize nodes which are repeatedly selected but fail to extend. Second, we introduce a new distance function which incorporates information about the system's dynamics to select nodes for extension. Third, we propose a scheme for adaptively modifying the sampling probability distribution based on tree growth. We demonstrate the application of the new algorithms to testing and validation of complex robotic and biological systems. The main contribution of this thesis is an automated algorithm that analyzes a control system design for complex systems by finding trajectories that satisfy specifications using sampling-based techniques. Our algorithms are also applicable to motion planning for systems that are not small time locally controllable.