A Clustering Approach to Approximate the Timed Reachability Graph for a Class of Time Petri Nets

• 成果类型: Article
• 署名作者: Zhou, Jiazhong; Lefebvre, Dimitri; Li, Zhiwu
• 署名单位: Xidian University; Universite Le Havre Normandie; Macau University of Science & Technology
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3110010
• 发表日期: 2022
• 页码: 3693-3698
• 关键词: Approximation; clustering algorithm; discrete event system; reachability graph; time Petri net (TPN)

摘要

Timed extended reachability graphs (TERG) of time Petri nets abstract the temporal specifications and represent the feasible trajectories under the earliest firing policy. One drawback of such graphs is the rapid increase in the number of states with respect to time specifications. For this reason, approximations of TERG that remove some states have been studied in recent works. In this article, we improve the approximation of a TERG. New objects-called vertices-are defined to manipulate the time constraints and algorithms are proposed to cluster nearby vertices. A metric based on the time constraints is defined for this purpose and a cluster TERG of reduced size is obtained.