For symbolic reachability analysis of rectangular hybrid systems, the basic issue is finding a formal structure to represent and manipulate its infinite state spaces. Firstly, this structure must be closed to the reac...For symbolic reachability analysis of rectangular hybrid systems, the basic issue is finding a formal structure to represent and manipulate its infinite state spaces. Firstly, this structure must be closed to the reachability operation which means that reachable states from states expressed by this structure can be presented by it too. Secondly, the operation of finding reachable states with this structure should take as less computation as possible. To this end, a constraint system called rectangular zone is formalized, which is a conjunction of fixed amount of inequalities that compare fixed types of linear expressions with two variables to rational numbers. It is proved that the rectangular zone is closed to those reachability operations-intersection, elapsing of time and edge transition. Since the number of inequalities and the linear expression of each inequality is fixed in rectangular zones, so to obtain reachable rectangular zones, it just needs to change the rational numbers to which these linear expressions need to compare. To represent rectangular zones and unions of rectangular zones, a data structure called three dimensional constraint matrix(TDCM) and a BDD-like structure rectangular hybrid diagram(RHD) are introduced.展开更多
基金supported by the National Natural Science Foundation of China(Grant Nos.61373043&61003079)the Fundamental Research Funds for the Central Universities(Grant No.JB140316)
文摘For symbolic reachability analysis of rectangular hybrid systems, the basic issue is finding a formal structure to represent and manipulate its infinite state spaces. Firstly, this structure must be closed to the reachability operation which means that reachable states from states expressed by this structure can be presented by it too. Secondly, the operation of finding reachable states with this structure should take as less computation as possible. To this end, a constraint system called rectangular zone is formalized, which is a conjunction of fixed amount of inequalities that compare fixed types of linear expressions with two variables to rational numbers. It is proved that the rectangular zone is closed to those reachability operations-intersection, elapsing of time and edge transition. Since the number of inequalities and the linear expression of each inequality is fixed in rectangular zones, so to obtain reachable rectangular zones, it just needs to change the rational numbers to which these linear expressions need to compare. To represent rectangular zones and unions of rectangular zones, a data structure called three dimensional constraint matrix(TDCM) and a BDD-like structure rectangular hybrid diagram(RHD) are introduced.
