学位论文 > 优秀研究生学位论文题录展示

基于STN的行动计划时间表示和冲突处理研究

作　者: 汤罗浩
导　师: 张维明
学　校: 国防科学技术大学
专　业: 管理科学与工程
关键词: 简单时间网络行动计划时间一致性冲突检测与消解
分类号: E07
类　型: 硕士论文
年　份: 2010年
下　载: 7次
引　用: 1次
阅　读: 论文下载

内容摘要

时间是军事行动最关键的要素之一,行动的成败与时间的规划息息相关。尤其在信息化条件下,战争节奏越来越快,行动计划对时间精度要求越来越高,计划中往往包含大量的、复杂的时间约束关系,例如,行动的先后次序、同步关系、期限约束等等。这些约束可否满足决定了任务能否顺利完成,需要对它们进行有效表示和处理。STN是一种基于约束的时间表示和推理方法,具有表达能力强、计算简单等优点,被广泛应用于规划和调度领域。行动计划时间约束的可满足性可通过STN的一致性来判断,但现有的STN一致性检验算法存在一个共同的不足:只能检测冲突而不能处理冲突,冲突处理工作全部由计划者承担。在计划制定阶段,由于约束设置不合理导致的时间冲突常有发生,在计划执行阶段,事件的执行异常也常常会导致时间约束的违背。所以,仅由人处理所有冲突是不科学甚至不可行的。论文主要研究行动计划时间冲突的处理问题,利用STN表达时间约束关系,提出了静态和动态的时间冲突检测和消解方法,确保计划的时间一致性。做了以下几个方面的工作:1.从行动计划中提取时间关系建立STN为了利用STN表示行动计划的时间关系,首先根据行动计划的四种基本执行关系得到定性时间网络,进而根据三类转化规则将定性关系转化为定量关系,最后通过添加定量约束建立STN,为后续的时间冲突处理提供前提。2.提出了基于STN的静态时间冲突检测与消解算法为处理计划制定阶段的时间冲突,提出了CDR算法,它采用迭代方式不断检测和消解冲突,直到计划中的所有时间约束都可满足。提出了基于松弛代价的冲突消解方法,提高了冲突消解的合理性,并对负环检测算法做了增量处理,减少迭代过程中的重复计算,提高算法效率。CDR算法能在多项式时间里消解所有冲突,且通过仿真试验论证其效率优于其他两种对比算法。3.提出了计划执行过程中时间冲突的检测与消解方法分析了计划执行过程中由事件延迟和提前执行导致的两种时间冲突,给出了冲突判定定理和消解定理,设计了结合深度优先搜索(DFS)和回溯的冲突路径搜索算法。提出了两种消解冲突方法,一种建立了代价模型以计算每条约束精确的的调整量,一种采用启发式为计划者建议约束调整的次序。通过动态检测和处理事件执行异常导致的时间冲突,可确保计划执行过程的时间一致性。

基于STN的行动计划时间表示和冲突处理研究

内容摘要

全文目录

相似论文