Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Reachability analysis method of hybrid system

An analysis method and technology for hybrid systems, applied in the field of accessibility analysis of hybrid systems, can solve problems such as error-prone, difficult, and increased memory requirements, so as to reduce the time of bounded reachability analysis, solve fast, and save memory. low-occupancy effect

Active Publication Date: 2013-11-20
NANJING UNIV
View PDF2 Cites 6 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, since this method needs to encode all the behaviors of the system in k steps into a constraint set before testing, when the scale of the problem, such as the size of the given step size, the number of system variables, the number of members in the automaton combination, etc., increases, the size of the constraint set will grow rapidly, leading to a corresponding sharp increase in memory requirements, which in turn limits the size of the problem that can be solved
In addition, although the accessibility problem of linear hybrid systems can be solved by using SMT, the general satisfiability method, in a certain coding method, the coding itself is a very complicated task, and there is currently no corresponding supporting tool to solve it. finish this job
For design and modeling engineers of hybrid systems, converting the corresponding linear hybrid automaton model into an SMT problem would be a very difficult and error-prone task without relevant long-term training

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Reachability analysis method of hybrid system
  • Reachability analysis method of hybrid system
  • Reachability analysis method of hybrid system

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0024] In order to better understand the technical content of the present invention, specific embodiments are given and described below in conjunction with the accompanying drawings.

[0025] A hybrid system is a system that can express both continuous and discrete dynamic behaviors. Linear hybrid automata is the simplest subclass of hybrid systems. For a linear hybrid automaton, its expression is as follows: H=(X,∑,V,V 0 ,E,α,β,γ), where X is a finite set of real-valued system variables, and the number of variables in X is also called the dimension of the automaton; Σ is a finite set of event names; V is a finite set of location nodes Set; E is the set of jump relationships between location nodes, and the element e in E represents a jump relationship, which looks like , where v,v′∈V,σ∈Σ, is behavior The transformation guard set of , ψ is the reset action set of behavior x:= c, above x, x i (0≤i≤l)∈X,a,b,c i (0≤i≤l)∈R, a can take the value -∞, b can take the value ∞; V...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention provides a reachability analysis method of a hybrid system. The reachability analysis method comprises the following steps that input files of a hybrid automaton are analyzed, and the bounded figure structure of the automaton is encoded into a propositional logic formula set; an SAT solver is used for solving the formula set, if the formula set can not be solved, an output result is insoluble, and if the output result is soluble, an assignment capable of being met is decoded to be a path on the figure structure of the automaton; a target path is encoded to form linear constraint according to the meaning of the hybrid automaton; the linear constraint is solved, if the linear constraint is soluble, the path is output as a result, and if the linear constraint is insoluble, a next step is turned; an irreducible and insoluble set of the linear constraint is given; an unreachable path is encoded into the propositional logic formula set and then is added into the formula set of the figure structure of the automaton. The reachability analysis method is used so that the candidate path for reaching a target node can be quickly found out, and the time for searching the figure structure of the hybrid automaton can be shortened.

Description

technical field [0001] The invention relates to the field of accessibility analysis of hybrid systems, in particular to a method for accessibility analysis of hybrid systems of SAT, LP, IIS (Irreducible and Irresolvable Set) dynamic feedback guidance. [0002] Propositional logic satisfiability SAT (boolean satisfiability) is the problem of determining whether there is an assignment that makes a given set of propositional logic formulas true. Linear programming (LP) is the problem of determining whether there is a solution that satisfies a given set of linear inequalities. Irreducible infeasible set IIS (irreducible infeasible set) refers to a subset of a set of unsatisfiable linear constraints, which is characterized in that the set is insoluble, but the set can be solved by removing any constraint. Background technique [0003] A hybrid system is a kind of complex system with both discrete and continuous behavior characteristics. In real life, especially in embedded rela...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06F19/00
Inventor 解定宝卜磊李宣东
Owner NANJING UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com