Simulation-guided incremental stability analysis

Patent metadata

Field	Value
Publication number	US-9606773-B2
Application number	US-201414462218-A
Country	US
Kind code	B2
Filing date	Aug 18, 2014
Priority date	Jun 10, 2014
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

Abstract

A computer system may seek to identify at least one contraction metric that satisfies contraction conditions for a design of a dynamical system. The computer system may do so by formulating a search for a candidate contraction metric that is suspected of satisfying the contraction conditions for the design of the dynamical system from a set of simulation traces that describe the behavior of the dynamical system for a specific set of operating conditions. The search for the candidate contraction metric may then be performed.
The computer system may seek to verify that a candidate contraction metric for a design of a dynamical system satisfies contraction conditions by performing a process that uses solvers based on decision procedures.

First claim

The invention claimed is:

1. A non-transitory, tangible, computer-readable storage medium containing a program of instructions that cause a computer system running the program of instructions to perform a process that includes:
obtaining a set of simulation traces or test data that describe the behavior of a dynamical system for a specific set of operating conditions;
identifying at least one contraction metric that satisfies contraction conditions, including:
formulating a search for a candidate contraction metric that is suspected of satisfying the contraction conditions for the design of a dynamical system from the set of simulation traces or test data that describe the behavior of the dynamical system for a specific set of operating conditions;
performing the search for the candidate contraction metric, wherein the search results in a candidate contraction metric;
verifying that the candidate contraction metric satisfies the contraction conditions by performing a process that uses solvers based on decision procedures; and
designing the dynamical system taking into consideration the candidate contraction metric.

2. The storage medium of claim 1 wherein the process includes searching for a counterexample that constitutes a simulation trace that describes the behavior of the dynamical system for a specific set of operating conditions and that violates contraction conditions for the candidate contraction metric.

3. The storage medium of claim 2 wherein the process includes searching again for a candidate contraction metric from a set of simulation traces that describe the behavior of the dynamical system for a specific set of operating conditions while the search is constrained by information from the counterexample.

4. The storage medium of claim 3 wherein the process includes repeating the search for a candidate contraction metric and the two searches for counterexamples until a condition is met.

5. The storage medium of claim 4 wherein the condition is that the second search for a counterexample is unable to find a counterexample that constitutes a simulation trace that describes the behavior of the dynamical system for a specific set of operating conditions and that violates contraction conditions for the candidate contraction metric.

6. The storage medium of claim 4 wherein the condition is that a specified amount of time has expired.

7. The storage medium of claim 4 wherein the condition is that a specified number of searches have been made.

8. The storage medium of claim 4 :
wherein the second search for a counterexample results in a candidate contraction metric; and
the condition is that the last identified candidate contraction metric satisfies the contraction conditions as determined by performing a process that includes using solvers based on decision procedures.

9. The storage medium of claim 2 wherein the process includes using solvers based on decision procedures to generate the counterexample.

10. The storage medium of claim 9 wherein the process includes using global optimizers to generate the counterexample.

11. The storage medium of claim 2 wherein the process includes using global optimizers to generate the counterexample.

12. The storage medium of claim 1 wherein:
the set of simulation traces comes from a first source; and
the process includes searching again for a candidate contraction metric from a set of simulation traces that come from a second source that is different from the first source and that describe the behavior of the dynamical system for a specific set of operating conditions.

13. The storage medium of claim 1 wherein the search is performed by formulating a semidefinite programming problem and producing the search result using software.

14. A method of building a dynamical system comprising:
obtaining a set of simulation traces that describe the behavior of the dynamical system for a specific set of operating conditions;
using a computer system running a program of instructions that seeks to identify at least one contraction metric that satisfies contraction conditions to:
formulate a search for a candidate contraction metric that is suspected of satisfying the contraction conditions for the design of the dynamical system from the set of simulation traces that describe the behavior of the dynamical system for a specific set of operating conditions; and
perform the search for the candidate contraction metric, wherein the search results in a candidate contraction metric; and
verify that the candidate contraction metric satisfies the contraction conditions by performing a process that uses solvers based on decision procedures;

designing the dynamical system taking into consideration the candidate contraction metric; and
building the designed dynamical system.

15. A method of building an improved dynamical system comprising:
obtaining test data from a dynamical system that describe the behavior of the dynamical system for a specific set of operating conditions;
using a computer system running a program of instructions that seeks to identify at least one contraction metric that satisfies contraction conditions to:
formulate a search for a candidate contraction metric that is suspected of satisfying the contraction conditions for the design of the dynamical system from the test data that describe the behavior of the dynamical system for a specific set of operating conditions;
perform the search for the candidate contraction metric, wherein the search results in a candidate contraction metric; and
verify that the candidate contraction metric satisfies the contraction conditions by performing a process that uses solvers based on decision procedures;

designing the dynamical system taking into consideration the candidate contraction metric; and
building the designed dynamical system.

Assignees

• Toyota Motor Eng & Mfg North America Inc

Inventors

• Balkan Ayca
• Deshmukh Jyotirmoy Vinay
• Kapinski James

Classifications

• G06F30/20

  Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) · CPC title

• G06F8/20 Primary

  Software design · CPC title

• G06F16/245

  Query processing · CPC title

• G06F17/10

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F17/30424

  Physics · mapped topic