Abstract:
To solve the problem that the existing consistency checking algorithm of STN can only detect temporal conflicts but can’t resolve them, this paper proposes an iterative algorithm of conflict detection and resolution based on negative cycle detection algorithm. A conflict resolution method based on the cost of modifying constraints is designed, and the negative cycle detection algorithm work is made incrementally. It improves reasonability and speed of conflict resolution, reduces the burdens of planners. Experimental results prove the efficiency of this algorithm.
Key words:
Simple Temporal Network(STN),
temporal conflict,
conflict detection and resolution
摘要: 针对已有的STN一致性检验算法只能检测时间冲突而不能消解冲突的问题,以负环检测算法为基础,提出一种结合冲突检测和冲突消解的迭代算法。设计基于调整代价的冲突消解方法,对负环检测进行增量处理,可提高冲突消解的合理性和速度,减轻计划者处理冲突的负担。实验结果证明该算法具有较高的效率。
关键词:
简单时间网络,
时间冲突,
冲突检测与消解
CLC Number:
SHANG Luo-Gao, SHU Cheng, LUO Jiang-Feng, ZHANG Wei-Meng, HUANG Jin-Cai. Temporal Conflict Detection and Resolution Based on STN[J]. Computer Engineering, 2011, 37(3): 251-253,256.
汤罗浩, 朱承, 罗江锋, 张维明, 黄金才. 基于STN的时间冲突检测与消解[J]. 计算机工程, 2011, 37(3): 251-253,256.