时间自动机上邮递员问题：理论、模型、算法及应用研究

项目名称： 时间自动机上邮递员问题：理论、模型、算法及应用研究

项目编号： No.61300194

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 孙景昊

作者单位： 东北大学

项目金额： 23万元

中文摘要： 研究表明计算模式的变革遵循"十五年周期定律"，信息物理系统(CPS)的兴起恰好符合这一定律。CPS的基本科学问题是连续量与离散量共存，需要建立动态系统计算理论。近年来，科学家们一直在逻辑与物理交叉前沿领域探索新的计算模型，其中混合自动机是代表性方法之一。时间自动机(TA)是一种线性混合自动机，TA的建模、分析、综合和最优化这四大基本问题开辟了TA的理论研究课题。本课题针对TA上最优化问题开展探索性、创新性研究，首次提出了TA上两类邮递员问题的理论、模型和算法研究，分析了新问题的强NP困难性质和PSPACE完全性质等若干计算复杂性理论，建立了新问题的线性松弛、偏序覆盖和弧依赖动态流等松弛模型及其相关的多面体理论，并基于此提出了近似算法、启发式算法等一整套求解方法。本课题不仅在理论上具有挑战性，而且对应用研究有重要影响，其研究成果为实时通信系统一致性协议测试序列生成与优化提供了新的理论和方法。

中文关键词： 计算复杂性；时间自动机；时变邮递员问题；多面体理论；近似算法

英文摘要： Cyber-Physical Systems (CPS) were recently named the first research priority in networking and information technology in China by the state council of advisors on science and technology. They offer new research challenges that stem from the integrations of computation with physical processes, and the traditional foundations of computing built over the last serveral decades are not adequate for CPS. Growing challenges span a large spectrum ranging from new models of compuation for systems that combine discrete and contineous variables, especailly, Hybrid Automata (HA), to the certain key problems incudling modeling, analysis, synthesize and optimization associated with the new models. This research focuses on the challenges in the compuation model and theory for CPS, more specifically, a special linear HA model, namely, Timed Automaton (TA), and the associated optimization theory are investigated. In this subject, two new kinds of Chinese Postman Problems (CPP) defined on TA are studied intensively for the first time. There are three main contributions in the subject: (1)The computational complexity theorems of the new problems, such as NP-hard and PSPACE perpoerties, are discussed; (2)Several mathematical models including linear relax model, partial order covering set model and arc dependent flow over time mod

英文关键词： Computation Complexity；Timed Automata；Timing varying Postman Problem；polyhedral theory；approximation algorithm