Adaptive randomized algorithms for validation and analysis of complex systems

2006 2006

Other formats: Order a copy

Abstract (summary)

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.

Indexing (details)

Mechanical engineering;
0548: Mechanical engineering
0346: Mechanics
0771: Robots
Identifier / keyword
Applied sciences, Adaptive algorithms, Complex systems, Motion planning, Robotics
Adaptive randomized algorithms for validation and analysis of complex systems
Kim, Jongwoo
Number of pages
Publication year
Degree date
School code
DAI-B 67/07, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Kumar, Vijay; Esposito, Joel M.
University of Pennsylvania
University location
United States -- Pennsylvania
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.