冲突检测

2024-09-20

冲突检测（共6篇）

冲突检测篇1

0引言

电大系统生源的种类较多, 有高职生、脱产成教学生、在职开放生、在职研究生等, 各类学生对上课时间有不同的要求, 加上各门课程不同的教学需求, 因此电大与普通高校的排课有所不同, 以宁波电大为例, 排课有下列特点:

(1) 上课时段有重叠, 现有的上课时段有8个:上午1-2节、上午3-4节、上午1-4节、下午5-6节、下午5-7 (13:00开始) 节、下午5-7节 (13:40开始) 、晚上, 另外还有非以上情况的自由设置时段。在上述时段中, 上午1-4节与上午另外两个时段有重叠, 下午的3个时段也有重叠。

(2) 上课周次设置灵活, 周次设置不是普通高校课表中的单周、双周和全周3种情形, 而是形如“1, 3-8”的周次序列, 一个课程安排 (以下简称课元) 的上课周次可以自由设置。

(3) 同一班级同一课程可能由多名教师在不同的时间和不同的教室授课, 因此一个教学班的一门课程安排可能包括多个课元。

由于上述原因, 为普通高校排课系统设计的冲突检测方法根本不适用, 采用全自动排课很难表述这种特殊性要求, 实现起来比较困难, 因此, 宁波电大排课系统采取半自动排课方式, 课表编排手工输入, 而每当更改排课元素时, 系统自动进行排课冲突检测, 当所有课表编排都没有冲突时, 所得课表就是一份没有冲突的有效课表。

1排课冲突检测算法设计

1.1排课冲突介绍

排课问题是满足教学计划和各种约束条件的组合规划问题, 约束条件就是要避免课元的各排课元素之间存在冲突, 排课元素包括课程、时间、教师、教室和班级, 在冲突检测中, 必须要满足的基本约束条件有:①教师不冲突, 同一时间, 一个教师只能给一个班级上课;②教室不冲突, 同一时间, 一个教室不能安排两门不同的课程;③班级不冲突, 同一时间不能给同一班级安排两门不同的课程。

在排课冲突检测中还有一些其它的约束条件也要满足, 例如上课的班级人数必须小于教室座位数等, 本文不做考虑。

1.2冲突检测算法的概念设计

考虑到上课时间可以细分为周次、星期和上课时段, 一个教学班一门课程安排的课表问题空间T可表示为:T=P×C×Z×W×S, 其中P为教师集合, 表示全校所有任课的教师;C为教室集合, 表示学校所有的教室;Z为周次序列集合, 可为任何有效的周次序列;W为星期集合, 具体为“周一”、“周二”…“周日”;S为上课时段集合, 具体为上述的8个上课时段。

课元a对应T中的一个向量, 记做a= (pα, cβ, zγ, wδ, sκ) , 其中pα∈P, cβ∈C, zγ∈Z, wδ∈W, sκ∈S。假设课表P有n条记录, 为了检测课元a与课表P是否有冲突, 那么系统要进行n次检测, 每次检测要考虑排课的5个元素, 而每当排课元素修改后, 系统都要进行冲突检测, 那么系统运行效率会很低。考虑到教师冲突、教室冲突、班级课程冲突都是因为课元所选的教师、教室、班级没有空闲时间, 它们都与时间关系密切, 排课冲突检测的关键就是时间的冲突检测。因此可以采取固定几个排课元素, 缩小问题空间维度的方法进行检测, 具体就是, 固定课元中除周次外的4个排课元素, 从课表中筛选有可能存在冲突的待检测数据集, 然后将课元中的周次和待检测数据集中的周次进行冲突检测, 如果周次有冲突, 则该课元与课表有冲突, 否则, 该课元与课表没有冲突。

在课表P中筛选出与课元a有可能冲突的待检测数据集Y可表示为:

设a= (p, c, z, w, s) , 则Y={t|t∈P, (t.p=a.p 或 t.c=a.c) 且 t.w=a.w 且t.s与a.s时间冲突}, 其中“.”表示向量的分量, t.p表示课元t的教师 (p) 分量, 其余符号意义类似。

有效课表P不冲突可表示为: P⊆T且∀a∈P, ∀b∈P, a≠ b有a与b不冲突。

1.3上课时段冲突检测

在上述上课时段中, 上午1-4节与上午1-2节、上午3-4节冲突, 下午5-6节、下午5-7 (13:40开始) 节和下午5-7节 (13:00开始) 冲突。为了判断上课时段是否有冲突, 对上课时段的编码设计如表1所示:

那么, 对于两个固定时段, 设其编码为s1、s2, 则:

undefined

非固定时段的冲突判断仍需人工判断。

1.4周次冲突检测

设一个学期有20周, 课元的周次设置可以用一个20位的二进制数z表示, z的位数对应周次, z数位上的值表示有无课程安排, “1”表示有课程安排, “0”表示无课程安排, 例如, 周次设置“1-2, 15, 20”的二进制编码为:

表示在第1、2、15、20周有课程安排, 其余周次没有安排课程。

那么, 对于两个周次设置, 设其二进制编码为z1、z2, 则

undefined

判断一个课元a与待检测数据集Y的周次设置是否存在冲突, 可采取下列方法:

a.z∧ (y1.z V y2.z V y3.z V … V yn.z )

undefined

其中a.z表示课元a周次设置的二进制编码, 其余符号类似地表示数据集Y中课元周次设置的二进制编码。

1.5算法流程图

在上述基本概念的基础上, 排课冲突检测算法的流程如图1所示。

2实现

宁波电大排课系统采用B/S结构, 选用Visual Studio.Net 2008开发平台, VB.NET开发语言开发, 系统开发采用面向对象的技术, 数据访问技术选用ADO.NET。

2.1排课页面

排课页面如图2所示, 该图显示经管系对课程“会计”进行课表编排, 该门课程有两个教学班, 教学班各有1、2个课元, 其中教学班1有排课冲突。在该页面中用户可以增删教学班, 教学班中的课元也可增删, 课元的排课元素除了周次和非固定时段是直接输入外, 其余排课元素都为下拉列表, 下拉列表数据来自对应的数据表。如果排课没有冲突, 在总课时栏会显示总的课时, 否则显示冲突的详细信息。

页面中教学班和教学班内的课元由具有主细关系的Repeate和GridView两个控件表示, Repeate控件负责显示教学班、Gridview控件负责显示教学班内的课元, 表格的内容和样式在控件单元格数据绑定的事件中编程控制。每当排课元素修改后, 页面将自动刷新, 重新进行冲突检测, 返回冲突的结果。

2.2数据库的逻辑设计

数据表中存储了排课信息和各类排课基础信息, 为了保证冲突检测时排课元素的唯一性, 对排课元素记录进行自动编码, 在课元表中保存的是排课元素的ID号, 冲突检测以ID为准, 教学班与课元是一对多的关系, 通过关键字“教学班ID”关联。数据表关系如图3所示。

2.3冲突检测类

冲突检测由自定义类GetDayFromStr实现, 类中包含用来设置课元排课元素的方法, 在设置了待检测教学班的排课元素后, 调用方法GetCount () 实现冲突检测。GetCount () 方法在不存在排课冲突的情况下, 返回周次序列所表示的课时数, 否则, 将冲突的详细信息保存到类的错误属性 (ErrorMsg) 中, 并返回一个负数, 不同的返回值代表不同的冲突类型, 具体情况见表2。

筛选待检测数据集的 SQL语句如下, 其中以”m_”开头的变量表示待检测课元排课元素的取值:

3结束语

本文提出了解决上课时段重叠、周次自由设置的排课冲突检测算法, 并在宁波电大排课系统中加以实现, 在2011年春季排课的试用中, 排课系统能准确地检测出上课冲突, 验证了该算法的正确性和可行性。通过采取缩小问题空间纬度的方法, 将排课冲突检测问题空间的纬度从5降低为1, 能提高排课冲突检测的效率, 并且算法简单, 有一定的通用性, 稍做修改可以应用到多种排课情况。

参考文献

[1]陶滔, 毛宁, 夏石莹, 等.有限维冲突算法及应用研究[J].南华大学学报 (自然科学版) , 2005 (9) .

[2]彭秀萍.排课系统的研究与实现[D].成都:电子科技大学, 2009.

高校排课流程及冲突检测分析篇2

关键词：高校,排课流程,冲突检测

0 引言

由于高校教学管理的差异性大, 个性化需求多, 所谓通用的高校排课软件并不通用, 从市面上购回来的排课软件往往需要开发者二次定制开发。我校既有本科教学, 也有研究生教学, 两者排课问题的差异性很大。因此很多高校也选择了贴近实际需求, 自主开发。

本文所述的排课问题及解决方法, 完全贴近我校本科教学中排课问题的实际需求, 是由学校自己的开发队伍, 设计、开发的排课系统。在此抛砖引玉, 或许对其他高校排课问题的解决, 有借鉴作用。

1 排课流程

在排课问题上, 最重要的是根据实际需求, 分析清楚排课的整个流程, 了解影响排课了解的诸多因素。实现了各种各样的自动排课、半自动辅助排课、全手工排课等系统。

我校本科教学是以学分制选课机制为主导的, 大学2年级到大学4年级的大部分课程, 学生都是通过网上选课来完成教学计划, 但新生的课程必须由教务部门在新生正式上课前预先排好。所以排课系统主要用于新生的排课以及高年级的部分特殊课程。

根据实际需求, 分析出我校本科教学的自动排课流程如下:

设:构建5个集合:课程=A, 班级=B, 教师=C, 教室=D, 时间片=E。

正式排课之前, 我们需要对时间片E进行设置。一周内可排课的天数, 我们按5天编排, 分别用“1”～“5”5个字符表示;1天内可排课的节数, 我们按“1”～“9”和“A”十个字符表示, 分别代表10节课, 其中上午“1”～“4”4节课, 下午“5”～“7”3节, 晚上“8”、“9”、“A”3节课;关于单双周的问题, 我们用“0”、“1”、“2”3个字符分别代表“全周”、“单周”、“双周”3种不同的周次安排。有了以上字符定义, 我们在时间片E的设置上, 就实现了对每节课时间片的字符串表示, 如:

全周的周1第2节用“012”表示, 单周的周3第6节用“136”表示, 双周的周4第10节用“24A”表示, ……

在排课过程中, 我们根据以人为本、科学编排的原则, 制定了时间片的取用规则:节数为偶数的课程 (如:2节、4节) , 尽可能按“先周1～5上午, 再周1～5下午, 再周1～5晚上”的顺序编排;节数为奇数的课程 (如:1节、3节) , 尽可能按“先周1～5下午, 再周1～5上午, 再周1～5晚上”的顺序编排。

正式排课, 首先, 我们需要跟踪实际情况, 如:任课教师的特殊需求, 以及人数多的大班课程等, 对需要参加排课的课程集合A进行优先级设置, 并按优先级从高到低进行排序, 然后以排好序的课程A, 从上到下, 逐门课程开始排课试探。

排课流程为:从课程A中取出一门需要排的课, 按时间片取用规则从时间片E中提取一个时间片, 在这个时间片中进行各种冲突检测 (主要对班级B、教师C和教室D在时间片上的检测) , 如果发现冲突, 则排课不成功, 提取下一个时间片, 继续进行冲突检测……;如果在一个时间片上没有冲突, 则标记排课成功, 记录下这门课在这个时间片上可用。从课程A中取下一门要排的课程, 继续上述过程, 直至课程A中所有课程全部排完, 结束自动排课。整个流程如图1所示:

2 冲突检测

当一门课准备在一个时间段上进行排课时, 主要进行的冲突检测有6个方面:

2.1 在这个时间段, 班级B可用

在班级B的冲突检测上, 我们主要从课表中提取课程所涉及的班级在指定时间段上, 是否已经安排了其他课程, 或指定了班会, 或有学校规定的特殊活动。如果没有, 则没有冲突, 返回值False;否则发现冲突, 返回值True。

2.2 在这个时间段上, 教师C可用

在教师C的冲突检测上, 我们主要从课表中提取该任课教师, 是否在指定时间段上, 已经安排了其他课程授课, 或这个时间片是该教师指定的不授课时间。如果没有冲突, 则返回值False, 否则返回值True。

2.3 在这个时间片上, 教室D可用

在教室D的冲突检测上, 我们主要从课程需求的教室容量上, 依次提取符合容量大小的教室, 判断各教室是否在指定的时间片上可用, 如果没有发现有合适的空教室可用, 则返回值False, 否则返回值True。

2.4 在这个时间片上, 单双周可用

在单双周的冲突检测上, 我们是结合进班级B、教师C和教室D的冲突检测中进行的。在同一个时间片上, 允许同时安排一个单周和一个双周的班级B、教师C和教室D, 也就是允许一个时间片上的共存。但不允许同一个时间片上, 一个全周的安排与任何一个单周或双周的共存安排。

2.5 合班冲突问题

对于多班合班上课的问题, 需要分别考虑参于合班的原班级, 在合班共同的时间片上, 是否均不发生冲突 (单班级的时间片冲突检测, 参考冲突检测1) 。只有参于合班的所有班级均无冲突, 则返回值False, 否则返回值True。

2.6 跨校区问题

由于各学院各专业的学生存在多校区之中, 在排课上需要考虑到学生尽可能不进行跨校区上课, 也就是要测定指定时间片上, 课程所指专业和班级的学生所在校区没有冲突;同时, 也要考虑授课教师在上午 (1-4节) 、下午 (5-7节) 、晚上 (89A节) 中途不跨多校区授课, 即要测定教师在指定时间片的半天中 (上午、下午、晚上) 不允许已有其他课程安排, 否则发生冲突, 返回值True;没有冲突, 返回值False。

3 实现

考虑到排课这项工作, 主要集中在教务部门的个别管理员手中操作, 我们没有采用流行的B/S开发模式, 而使用了可视化快速开发工具Delphi7.0开发了专用的C/S排课程序。采用专用程序的最大好处就是可以使排课和调课的权限, 尽可能掌握在个别人手中, 方便程序加壳加密处理, 而且C/S程序适合进行密集运算和快速开发。而对于已经排好的课表进行查询和显示, 则考虑到要面向广大的教师和学生, 则采用Java开发了B/S网站, 在网上进行发布, 师生可以随时方便地上网查询自己的课表。

4 结束语

本文以作者所在学校本科教学排课的实际需求为基础, 着重对自动排课流程和排课过程中重点需要考虑的冲突检测的几个方面进行了分析。

开发一套排课系统, 还有很多开发细节需要考虑, 不仅是开发技术在实现上的问题, 还有很多管理流程的细节问题。希望通过对本文的阅读, 能对排课流程和冲突检测的相关信息有所了解, 对自动排课有一个总体的认识。对于希望了解和开发新的排课系统的读者, 能多少起到一点借鉴作用。

参考文献

[1]王凤, 林杰.高校排课问题的图论模型及算法[J].计算机工程与应用, 2009 (27) .

[2]高武奇, 康凤举, 钟联炯.基于冲突检测算法的二级排课系统[J].西安工业大学学报, 2008 (10) .

冲突检测篇3

计算机支持协同工作(computer supported cooperative work, CSCW)是指地域分散的一个群体借助计算机多媒体技术、网络技术及通信技术，在共享环境下进行协调与协作来共同完成一项任务。它支持多个用户在时间上分离、空间上分布但工作又相互依赖的协同工作。

在协同CAD系统中，由于协同设计环境的复杂性，冲突是不可避免的问题。事实上，协同设计的过程就是冲突不断产生和消解的过程。协同设计过程中的冲突具有必发性、多样性、关系性等特点。并发冲突检测和领域语义密切相关，不同的领域语义要求并发冲突检测在操作执行的不同时期进行判别。

协同CAD系统中的一个文档可以表示为一组具有不同属性的图形对象。若各对象都是独立的，则冲突操作只存在于对同一对象的同一属性修改成不同的值时，这时需要进行冲突处理。典型的冲突检测算法有多版本、串型序列化机制、floor控制法和锁机制等，还有许多研究学者们对传统方法进行改进，提出了各种协同并发算法。若对象之间存在关联关系，则当某个用户修改某个图像对象的某一属性值时，另一用户也在修改该关联对象的属性，那么这就有可能产生冲突。因此，多对象之间的冲突处理是协同CAD系统中的核心和难点问题。目前，在国内外对单对象的冲突研究相对比较多，文献[4]提出一种对等式协同设计系统冲突管理中的基于几何级并发操作冲突检测算法，该算法只涉及到单个实体之间的并发冲突。目前，对涉及多对象之间的冲突的研究还比较少。

本文主要以建筑图纸中的图形实体为研究对象，研究协同设计中多个关联对象之间的冲突检测和消解问题。

（二）协同CAD系统冲突检测和并发控制模型

1. 相关定义

在实时协同建筑图形CAD系统中，操作的对象主要是二维图形对象。下面给出涉及到图形对象中的相关定义。

定义1：操作(OP)。操作是指对图形对象的发出的指令或命令，可以把它定义为一个九元组O={Oid, Uid, Gid, Ts, Te, Cat, Attr, Pri, V}。其中，Oid是操作标识符，Uid是产生该操作的用户标识符，Gid是对象标识符，Ts是操作的开始时间，Te是操作的结束时刻。Cat是操作所属类别，Attr是该操作O涉及的属性。Pri为操作优先权，V是操作对象的版本号。

定义2：操作对象。假定协同CAD协同中的操作命令都是以图形对象为核心，则操作对象(operate object简称OPO)是操作命令所选择或指定要进行操作的对象。

对于二维协同图形系统来说，操作对象可以是圆、直线、线段、矩形和圆弧等。

定义3：关联对象(RO)。关联对象是指某个对象与其它对象以某种方式建立的依赖规则，当与之参考的对象发生位置、大小等属性变化时，则该关联对象也要随之改变。

在二维协同图形编辑系统中，关联对象的种类繁多。凡具有下列之一的关系都可以看作是关联关系：

(1)借助于已存在的对象辅助创建的新对象，它们的关系称为辅助绘图关系，记为AR。

(2)相对参考关系：已存在的两对象之间具有平行、垂直、相交、相切、同圆心等关系，统称为参考关系。记为RR。

定义4：对象关联度及关联对象集。对象关联度是指对象与其它对象的具有关联关系的对象的数目，记为RD。关联对象集是指对象与其具有关联关系的对象的集合。记为RS。

定义5：属性关联。属性关联是指对象属性与关联对象的某一属性具有依赖或关联关系，记为RA。

在协同设计中，并发控制一致性因素包括因果一致性、结果一致性、意愿保证三方面要求。下面给出相关的定义。

定义6：因果关系。假设在节点i和j上生成两个操作O1和O2，如果符合下面条件之一，则说明O1和O2存在因果依赖关系：记为O1→O2。

(a) i=j且操作O1是在操作O2之前生成;

(b) i≠j，且O1在节点j执行过程发生在操作O2生成之前;

定义7：并发关系。设两个任意的操作O1和O2，若O1和O2存在因果顺序关系O1→O2，则说明O2依赖O1;若既不存在O1→O2，也不存在O1→O2，则O1和O2存在并发关系, 即O1‖O2。

显然，操作执行的因果关系或并发关系，都只与操作执行的时间顺序有关，因此通过历史操作信息表判断操作是并发关系还是因果关系。

定义8：操作意愿保留 (Intention-preservation) 。操作O的操作意愿是指O的执行效果与在产生O的文档状态下应用O的效果一致。对于任何操作O，在所有节点执行O的结果都应与O的意愿一致，而且O的应用不能改变其它并发操作的执行效果。

2. 并发控制模型

本文采用如图所示的并发冲突检测模型。该模型主要包括操作日志、冲突检测、并发控制模块，其中并发控制模块和冲突检测模块根据不同的应用需要选择不同的控制策略。

冲突检测模块主要是负责并发操作的冲突推理，并将相应的冲突信息送入并发控制模块进行相应的控制执行，是并发控制的基础。其工作原理大致描述如下：本地用户操作或从协同站点接受的操作首先通过网络服务器传送到操作事实日志并保存操作信息，同时发送给其他协同用户，然后送入冲突检测模块进行冲突判别。若有冲突，则根据冲突类型进行冲突处理，最后送入并发控制模块执行并更新操作日志信息;否则直接送入并发控制模块执行操作。

上图所示的并发控制模型可以保证操作一致性维护，即保证因果一致性、操作结果一致性、意愿保证。因为操作信息保存在操作日志中，可以根据操作信息时间表判断操作之间的因果关系和并发关系。如果是因果关系，则直接根据操作信息立即执行操作，并广播到其它协同用户。若是并发关系，则先送入冲突检测模块进行冲突检测，然后再送入并发控制模块做冲突处理并执行操作。并发控制模块采用多版本策略，能保证操作意愿，最后版本管理模块采用服务器仲裁决定采用某一版本做为最后版本，并将结果以消息形式发送给各协同站点。这样，就可以保证结果的一致性。

（三）冲突检测策略

1. 冲突检测

在实时协同CAD系统中，由于不同用户在不同地域进行协同工作，因此，存在多个用户同时访问同一对象的可能性，因而可能产生冲突。这种冲突来自于多用户对同一对象同时修改操作，但若多用户访问不同对象，但这些不同对象之间有着某种关联关系，则它们之间也有可能产生冲突。如在建筑结构图纸中，改变某一个门的大小，则对应门上的窗户大小也随之更改。若某一用户正在修改该门的大小，而另一用户也在修改窗的大小，则它们之间就会产生冲突。

若多用户同时对多个对象进行修改时，先看两对象之间是否存在关联对象关系。若存在关联关系，则先建立各对象之间的属性关联表。如果多用户同时修改关联对象之间的关联属性，则表示当前操作有冲突。如果修改属性之间不存在冲突，则可以认为这些修改没有产生冲突。

如果多用户对同一对象同时进行修改，则用目前使用的单对象冲突定义进行判别。即修改同一对象且是同一属性，则认为冲突。而对于多对象之间的冲突，则需要根据操作修改的属性是否有关联关系来进行判断。

设O是一个操作，G (O)为O的目标对象，Attr (O)代表对象G的某个属性，Attr (O) .type代表对象的属性类型。Attr (O) .value代表对象的属性值。操作O1和O2由两个节点i和j产生的两个操作，且O1和O2都是对图形对象进行操作。若满足下列两种情况之一：

(1)若操作对象之间相互独立，即不存在关联关系，则冲突只产生于对同一对象的同一属性进行修改时。用数学描述如下：

(2)若操作对象之间有关联，两用户分别对具有关联关系对象操作，即满足：

则可以认为O1和O2之间存在冲突。

在协同CAD系统中，我们将可能引起的冲突操作分三种：Modify(修改)、Insert(插入)和Delete(删除)，分别简称为M、I、D操作。它们具有以下特性：I、M、D操作每次仅作用于一个对象，且操作执行的效果也仅限于该对象;M操作每次只改变对象的一个属性。那么在进行冲突判别时，可以按以下情况来判断：

(1) I与I操作：不产生冲突。

(2) I与M操作：如果对象独立，则不产生冲突;若对象关联，且新建对象的某属性值与M操作对象属性值具有关联属性，则认为产生冲突。

(3) M操作与M操作：若对象独立，则修改同一对象同一属性设置成不同值时，产生冲突;若对象关联，修改关联对象的关联属性值也产生冲突。

(4) D操作与D操作：若删除同一对象，则两操作相同，产生冲突，做操作合并处理。

(5) I操作与D操作：若对象独立，不产生冲突;若I操作的辅助对象是D操作对象，则产生冲突。

(6) M操作与D操作：若M和D的操作对象相同，则产生冲突;若操作对象不同，则没有冲突。

2. 冲突检测算法设计

冲突检测算法描述如下：

假设操作日志保存所有历史操作信息{HB}，每个站点维护一张信息历史信息表，当新操作On通过网络发送到站点i作远程操作，首先与站点i的{HB}中所有操作相比较，若是依赖关系，则不存在冲突，按顺序执行，若存在并发，则进行冲突检测。

3. 算法正确性分析

本文提出的算法能检测到多对象之间冲突，其正确性验证如下：

假设O1与O2是并发操作，若都是修改操作(即O1.Cat==O2.Cat==M)，则O1.attr与O2.attr修改这些属性即产生冲突;或修改属性类型相同而值不等，则违背操作意愿，产生冲突;若新建操作是删除操作或修改操作，因为删除操作是修改操作的特例，即把属性值全部设置为空，则新建操作是根据辅助对象而创建，删除辅助对象，则它们之间的约束关系破坏，因此会产生冲突;若新建操作同时都是删除对象，且删除对象相同，则操作是相同操作，将发生冲突;如新建操作针对不同的对象，则没有冲突。

（四）结束语

协同CAD系统中各成员共享工作空间进行图纸编辑图纸时涉及到各种对象，不同用户可能会同时修改某个对象而产生关联，因而破坏关联关系，这时有可能产生冲突。本文提出的冲突检测算法是基于几何级的多对象之间的冲突检测算法，能检测到关联对象之间的冲突。但是如果涉及到很多对象之间有关联，则情况就比较复杂，需进一步研究。下一步工作将集中在对冲突消解及实验仿真。

摘要：实时协同设计是CSCW应用的重要领域。实时协同设计过程实际上就是并发冲突产生和消解的过程。提出协同CAD系统中多对象之间的冲突相关定义, 给出了协同CAD系统的框架和并发控制模型, 描述了冲突检测策略和相应的检测算法, 对算法的正确性进行了分析验证。

关键词：协同CAD,冲突检测,一致性,并发控制

参考文献

[1]史美林, 向勇, 杨光信, 等.计算机支持的协同工作理论与应用[M].电子工业出版社, 2002, 12.

[2]杨友东, 周勋, 方志民.复制式协同设计系统的并发控制研究[J].中国制造业信息化, 2005, 34 (6) :95-97.

[3]陈明.协同设计环境下的冲突检测模型设计[J].计算机时代, 2005, (7) :3-5.

冲突检测篇4

交通冲突判别主要有2种判别指标。1种是以时间参数作为判别指标,以交通行为者开始采取避险行为作为冲突的起始点。国外倾向于采用此类指标,主要的判别指标有距离碰撞的时间(time to collision)、后侵占时间(post encroach- ment time),以及在后侵占时间概念的基础上演变出来的间隙时间(gap time)、侵占时间(encroachment time)等[1]。另1种是以空间参数作为判别指标,国内较常采用这类指标,主要以非完全制动时间为基础得出的冲突距离进行判别。以这类指标进行判别简单且易于操作,但是不能判别冲突双方速度较低且距碰撞点较近的情况。单一的指标不能完全判别冲突的发生,因此,近年来出现了许多交通冲突综合判别方法。郭伟伟等在引入临界冲突区域的基础上,建立了以速度、距离和角度为核心的交通冲突判别理论模型[2];潘仕印结合速度和面积建立基于冲突场的交通冲突判别模型,并利用仿真方法进行分析[3]。上述文献仅从理论和仿真的角度进行研究而缺少现实场景的验证。在利用视频检测方式进行交通冲突判别研究方面,张方方运用减速度、转向角速度、速度和距离等指标给出交通冲突的判别方法[4];Ismail等以距离碰撞的时间、后侵占时间、间隙时间和减速到安全时间作为视频检测交通冲突的判别指标[5];曲昭伟等以交通冲突的理论定义为基础,利用视频处理技术进行无信号交叉口的交通冲突判别[6]。但是由于观测手段的更新,用于人工观测的冲突判别指标在视频检测的实用性方面存在一定缺陷。

因此,研究适用于视频检测的交通冲突判别方法是十分必要的。为此本文根据现有交通参数视频检测的研究基础,建立交通冲突综合判别模型,通过现实交通场景进行验证并评价冲突判别的效果。

1 基本思路

基于视频检测的交通冲突判别可以划分为3个阶段:交通参数的视频检测、坐标变换和交通冲突判别。①通过视频检测技术,经前景检测、目标检测、目标跟踪以及轨迹平滑等处理,从交通视频序列获得交通实体的ID和图像坐标;②根据摄像机标定过程得出的内参数和外参数,将交通实体的图像坐标转换成地面坐标;③根据冲突的临界区域和交通实体的运动状态进行冲突判别。其中前2个阶段为交通冲突判别提供数据支撑,已经有大量的研究成果。最后一个阶段则是本文提出的冲突判别方法,是本文研究的重点。基于视频检测的交通冲突判别流程见图1。

2 交通冲突判别模型

2.1 交通参数的视频检测

为了从道路交通视频序列中自动获取交通实体的交通参数,本文以VC++6.0作为基础开发平台,结合OpenCV[7]对交通实体进行检测跟踪。OpenCV(open source computer vision library)是1种开源计算机视觉库。它是由一系列C函数和C++类构成,是实现图像处理和计算机视觉方面的通用算法,可以进行目标分割与匹配、运动分析以及目标的检测与跟踪等。

将交通视频输入视频检测程序,首先采用背景差分法进行前景检测,将当前帧的像素分为前景像素和背景像素,得到前景掩码;在前景掩模的基础上检测新进入检测区域的交通实体;目标跟踪模块结合连通区域跟踪和MeanShift 粒子滤波的碰撞分析,通过当前帧的图像、当前帧的前景掩码和新检测的目标,对交通实体进行跟踪,得到当前帧图像中的交通实体信息,包括交通实体每一帧的ID和图像坐标,图2为基于OpenCV的视频检测实例。在检测过程中,由于交通实体被遮挡或者噪声的影响,导致同1个交通实体的多次检测或者个别交通实体的检测遗漏,甚至出现轨迹的检测偏差。但是关于视频检测算法的研究超出本文研究的范围,因此本文仅利用有效的视频检测数据进行研究。

由于受到检测方法的限制,逐帧提取交通实体的质心坐标不可避免会受到随机误差的影响,导致提取的运动轨迹会在真实轨迹附近随机摆动。因此,本文采用均值滤波法对交通实体运动轨迹进行平滑处理,用某点前后的若干点坐标分量的平均值代替其原有坐标的对应分量,生成1条更加接近真实情况的运动轨迹。假设某段连续时间序列的某个交通实体质心坐标为{(x1,y1),(x2,y2),…,(xk,yk),…,(xn,yn)}。

设取平均值的点个数为3,经过平滑处理后,点(xk,yk)和点(xk+m,yk+m)的坐标可表示为(Xk,Yk)和(Xk+m,Yk+m)

$\begin{array}{l} X_{k} = \frac{x_{k - 1} + x_{k} + x_{k + 1}}{3} \\ Y_{k} = \frac{y_{k - 1} + y_{k} + y_{k + 1}}{3} (1) \end{array}$

$\begin{array}{l} X_{k + m} = \frac{x_{k + m - 1} + x_{k + m} + x_{k + m + 1}}{3} \\ Y_{k + m} = \frac{y_{k + m - 1} + y_{k} + y_{k + m + 1}}{3} (2) \end{array}$

这2点间的距离可表示为

$D_{k} = \sqrt{(X_{k + m} - X_{k})^{2} + (Y_{k + m} - Y_{k})^{2}} (3)$

交通实体经过这2点的平均速度可表示为

$v_{k} = \frac{D_{k}}{Δ t} (4)$

式中:Δt为经过这2点的时间间隔,运动向量可表示为

(X,Y)=(Xk+m-Xk,Yk+m-Yk) (5)

2.2 坐标变换

通过视频检测得到的是交通实体的图像坐标,但是该坐标不能直接进行相关参数的计算,需要通过坐标变换将图像坐标转换成地面坐标。求取坐标变换参数的过程称为摄像机标定,标定的基本原理为

$s [\begin{array}{l} u \\ v \\ 1 \end{array}] = [\begin{matrix} f_{x} & 0 & c_{x} \\ 0 & f_{y} & c_{y} \\ 0 & 0 & 1 \end{matrix}] \cdot [\begin{matrix} r_{11} & r_{12} & r_{13} & t_{1} \\ r_{21} & r_{22} & r_{23} & t_{2} \\ r_{31} & r_{32} & r_{33} & t_{3} \end{matrix}] \cdot [\begin{array}{l} x \\ y \\ z \\ 1 \end{array}] =$

M1M2X (6)

式中:(x,y,z)为是一个点的世界坐标;(u,v)是该点投影在图像平面的坐标;M1为内参数矩阵,其中:(cx,cy)为基准点,fx和fy为摄像机焦距,内参数矩阵是摄像机的固有属性,不随场景的变化而变化;M2是外参数矩阵,包括旋转矩阵和平移向量,用来描述摄像机相对于一个固定场景的运动。

Matlab标定工具箱[8]可以方便地进行坐标变换。首先从视频序列中截取20张图像作为定标图像,将图像导入,提取每张图像的网格脚点,进行定标,得到内参数矩阵。然后进行外参数矩阵的计算,从视频序列中截取另一张图像,并提取该图像的网格脚点,得到外参数矩阵和标定标准误差。

将内参数矩阵和外参数矩阵代入式(6),根据视频检测得到的图像坐标,即可获得交通实体的地面坐标,进而获得交通实体的微观交通参数。

2.3 交通冲突判别

根据交通冲突的定义可以看出交通冲突应满足2个基本条件:假设运动双方维持现有运动状态继续运动将会发生碰撞;至少有一方为躲避事故的发生,有改变运动状态的行为。下面以2个交通实体(车辆1和车辆2)为例说明本文提出交通冲突的判别方法,为了便于描述,忽略交通实体自身的大小和形状,用质点来表示。

以速度相对较大的交通实体的速度方向作为y轴正向,建立x-y坐标系,见图3(a)。在t0时刻,车辆1与车辆2分别位于A点和B点,坐标为(x1,y1)和(x2,y2),2车之间的距离为d,瞬时速度分别为v1和v2。为了便于后文描述,引入冲突的临界区域和冲突角度的概念。冲突临界区域是指难以避免发生交通冲突的区域,冲突角度是用来衡量冲突临界区域的相关夹角,包括速度角度和位置角度。速度角度θ是指车辆2的速度方向与x轴正向的夹角;位置角度α是指2车位置连线与x轴正向的夹角。只有冲突角度满足一定条件,2车才有可能处于冲突的临界区域。那么冲突角度、速度大小以及两车间的距离是关于冲突临界区域的函数,即

conflict=f(θ,α,|v1|,|v2|,d) (7)

当2车的速度不相等时,假设车辆2的速度小于车辆1的速度时,即|v2|<|v1|。当车辆2的相对速度方向沿AB连线并指向车辆1时,车辆1所需要的安全距离最大。当v2的方向垂直于AB连线时,|v2|的值最小。因此对于每个给定的v2,都存在一个相应的α,限定冲突的临界区域,见图3。

$(a) α \in [\arccos \frac{| v_{2} |}{| v_{1} |}, π / 2) 冲突角度分析 (b) α \in (π / 2, π - \arccos \frac{| v_{2} |}{| v_{1} |}], (c) α \in (π / 2, π - \arccos \frac{| v_{2} |}{| v_{1} |}],$ θ∈(0,π/2)冲突角度分析 θ∈(π+α,2π)冲突角度分析

|v2|≥|v1|cosα (8)

因此,位置角度α的取值范围为

$α \in [\arccos \frac{| v_{2} |}{| v_{1} |}, π - \arccos \frac{| v_{2} |}{| v_{1} |}] (9)$

式中: $\arccos \frac{| v_{2} |}{| v_{1} |} \in (0, π / 2)$ 。

同样速度角度也必须满足一定条件。当 $α \in [\arccos \frac{| v_{2} |}{| v_{1} |}, π / 2)$ 时,如图3(a)所示,速度角度θ应满足

θ∈(π/2,π+α) (10)

当 $α \in (π / 2, π - \arccos \frac{| v_{2} |}{| v_{1} |}]$ 时,见图3(b)和图3(c),速度角度应满足

θ∈(0,π/2)U(π+α,2π) (11)

当2车的速度相等时,即|v2|=|v1|,位置角度α应满足α∈(0,π),使交通实体处于冲突的临界区域。

假设车辆1和车辆2维持现有的运动状态将会在C点发生碰撞,以图3(a)为例,由正弦定理可以看出

$\frac{d}{\sin φ} = \frac{s_{1}}{\sin (π / 2 - φ + α)} = \frac{s_{2}}{\cos α} (12)$

式中:s1和s2为在2车相距d的前提下,2车从当前位置到碰撞点的距离;φ为2车的速度夹角。

同理,在图3(b)和图3(c)中

$\frac{d}{\sin φ} = \frac{s_{1}}{\sin (3 π / 2 - φ - α)} = \frac{s_{2}}{\sin (α - π / 2)} (13)$

假设在t时刻,2车保持原有的运动状态不变继续运动,车辆2行驶的距离为s2

s2=f2(Δt) (14)

式中:Δt为车辆2从t时刻到碰撞点所用的时间。经过Δt时间,车辆1行驶的距离为s′1

s′1=f1(Δt) (15)

此时,如果

s′1∈(s1-l0,s1+l0) (16)

式中:l0为车辆长度。说明2车处于冲突的临界区域,这时候至少有一方有改变其运动状态的行为,根据交通冲突的基本条件可以判别冲突的发生,反之未发生冲突。

当α=π/2时,2车只有满足|v2|<|v1|且s1≥s2+d,2车才会发生冲突。

为了便于评价判别效果,定义判别的准确率和冲突检出率。其中,判别的准确率是指判别模型检测出的交通冲突属于实际发生的冲突个数与判别模型检测出总的交通冲突个数的比值;冲突检出率是指判别模型检测出的交通冲突属于实际发生的冲突个数与实际发生的交通冲突个数的比值。

3 实例分析

选取天津市某2相位信号交叉口对交通冲突判别模型进行验证,选择2个时段共20 min的交通视频,分析其中69个交通实体。经过视频检测得到交通实体的图像坐标,借助Matlab标定工具箱进行坐标变换,得到交通实体的地面坐标和标定标准误差,在x和y方向的误差分别为1.40像素和0.62像素。根据判别模型,在Matlab环境下编写程序实现交通冲突的判别。下面以ID为9的小汽车和ID为14的自行车为例进行说明计算,小汽车和自行车的初始位置相距35 m,见图4。

经过10帧后,小汽车和自行车分别位于A点和B点,相距10.50 m。经过计算,得出交通实体的速度大小、速度角度和位置角度分别为

|v1|=0.12 m/帧;|v2|=0.07 m/帧;

α=1.16 rad;θ=3.53 rad

根据式(9)和(10),可得冲突角度的范围分别为

α∈(0.95,2.19);θ∈(1.57,4.09)

冲突角度满足冲突的临界区域范围。

假设该小汽车和自行车在该帧之后保持原有的运动状态不变,做匀速直线运动,可以求得

s1=5.86 m;s2=3.36 m;Δt=45帧

进而得出s′1,l0取5 m,根据式(16)得

s′1=5.86 m∈(s1-l0,s1+l0)=

(0.86 m,10.86 m)

说明小汽车和自行车处于冲突的临界区域,由此判别1个机动车-自行车冲突的发生。

从总体上来看,根据视频的人工检测,2段视频一共发生了53次冲突。交通冲突判别模型总共判别出52个冲突,其中经过证实的冲突有42个,由此可以得出,冲突判别的准确率为80.77%,冲突检出率为79.25%。由于受到视频检测精度的制约,在获取交通实体坐标等参数时存在误差,导致交通冲突判别时出现误判。

4 结束语

交通冲突判别模型有着广阔的应用前景,可以运用于交通冲突的自动识别,在一定程度上对交通事故的发生提前预警,也可用于事后交通冲突的自动记录及交通安全评价,更能指导交通流控制方式及交通安全设施设计。本文建立了以冲突角度、速度和距离等指标为核心的综合交通冲突判别模型,克服单一判别指标存在的不足。将交通冲突判别和视频检测结合,借助OpenCV获得交通实体的图像坐标,通过Matlab标定工具箱将图像坐标转换为地面坐标,进而运用冲突判别模型进行判别。通过对现实交通场景的实验,验证了冲突判别模型的可靠性。由于检测精度受到视频检测技术的制约,因此该领域的下一步研究工作是在提高视频检测精度的基础上将交通冲突判别模型运用于实时的交通场景。

摘要：为了克服交通冲突传统人工判别方法的缺陷,提出了基于视频检测的交通冲突发生判别的基本流程,将交通冲突发生的判别划分为交通参数的视频检测、坐标变换和交通冲突判别3个阶段。在借助OpenCV和Matlab标定工具箱进行交通实体检测和坐标变换的基础上,建立了以冲突角度、速度和距离等指标为核心的交通冲突综合判别模型,并通过现实场景验证该模型的有效性。

关键词：交通冲突判别,视频检测,冲突角度,OpenCV,Matlab标定工具箱

参考文献

[1]Archer J.Methods for the assessment and predic-tion of traffic safety at urban intersections and theirapplication in micro-simulation Modelling[R].Stockholm:Royal Institute of Technology,2004.

[2]郭伟伟,曲昭伟,王殿海.交通冲突判别模型[J].吉林大学学报:工学版,2011,41(1):35-40.

[3]潘仕印.基于视频图像处理的平面交叉口交通冲突自动检测技术研究[D].北京:北方工业大学,2011.

[4]张方方.基于视频的平面交叉口机动车交通冲突检测技术研究[D].上海:同济大学,2008.

[5]Ismail K,Sayed T,Saunier N,et al.Automated a-nalysis of pedestrian-vehicle conflicts using video da-ta[J].Transportation Research Record,2009(2140):44-54.

[6]曲昭伟,李志慧,胡宏宇,等.基于视频处理的无信号交叉口交通冲突自动判别方法[J],吉林大学学报:工学版,2009,39(2):163-167.

[7]刘瑞帧,于仕琪.OpenCV教程[M].北京:北京航空航天大学出版社,2007.

冲突检测篇5

基于策略的网络管理技术不同于传统的网络管理, 它将网络管理中的管理和执行分开, 使得网络管理更为智能化。但是, 由于不可避免的策略冲突阻碍着基于策略的网络管理技术的发展, 如伺在基于策略的网络管理中解决策略冲突间题, 有效的检测策略冲突的方法成为解决问题的关键。

1 冲突的发生

如果两个策略的策略本身重叠, 即两个策略的主体, 客体都重叠, 并且赋予两个策略相互矛盾的动作, 这样当两个策略同时满足条件时触发执行, 就会发生意想不到的情况。由于策略最终会被解释为网络操作命令, 而两个矛盾的策略必然会被解释为两个矛盾的命令, 这样设备就会不知所措, 冲突由此产生。

因此, 策略冲突的发生需要满足几个条件, 一是策略间的策略本身即策略主体和客体重叠, 二是策略间有矛盾的策略动作, 三是策略间的执行时间彼此覆盖或交叉, 即两个策略之间的开始时间和结束时间区域有重叠。

2 冲突的分类

2.1 按照冲突发生时策略的状态

按照冲突发生时策略的状态冲突分为以下2种:

(l) 静态冲突

静态冲突是在策略制定以后, 向策略库存储时候, 就已经与库中存在的策略发生冲突。静态冲突是一种实际冲突, 在静态的时候就应该予以解决。

(2) 动态冲突

动态冲突相对于静态冲突, 属于一种潜在冲突, 是指策略在制定完之后尚不能确定是否与库中策略存在冲突, 但可以确定与库中的一些策略存在冲突的可能性。

2.2 按照策略作用对象间的关系

(1) 内部策略冲突

内部策略冲突是当多个策略赋予同一个角色, 这些策略间规定了一些相互矛盾的角色动作。比如如下两个策略:

策略Pl:规定管理员每天在8:30AM一11:30AM, 1:00PM一5:00PM时间内可以开启用户在线查看服务器。

策略P2:规定管理员在休息日不可开启用户在线查看服务器。

由于两个策略Pl与PZ的主!客体相重叠, 执行时间也相互交叉, 因此两个策略必定会发生冲突, 这种冲突称为内部策略冲突。

(2) 外部策略冲突

外部策略冲突发生在一个用户具有多重角色的时候。由于多重角色的存在可能引发角色间策略的冲突。为了说明外部策略冲突问题, 考虑下面两种策略:

Pl:只要审计文件没有达到一定大小之前, 审计员可以在任何时间查看审计记录。

P2:管理员在任何时间都不允许查看审计记录。

这样对于一个具有审计员和管理员双重角色的管理人员来说就可能产生外部策略冲突。

(3) 角色冲突

角色冲突在某中意义上来说不属于策略冲突, 但是基于角色策略的软件都隐含的存在角色冲突"角色冲突是指某个员工在一个团体中具有多个角色, 而这些角色之间违反了网络安全管理中事先定义好的权限分配, 从而造成角色冲突。比如对于一个银行网络安全来说, 不能对其内部一个员工赋予银行的出纳角色又赋予银行的审计员角色, 因为一个银行员工同时具有出纳和审计员两个角色可能导致该员工修改审计服务器上的记录, 造成银行数据不安全"这就是角色冲突。

3 冲突检测

3.1 冲突检测的目的

冲突检测有两个目的, 一是发现策略间的实际冲突;二是策略间的潜在冲突, 并记录下来, 以便跟踪冲突潜在中的事件因素, 一旦事件发生, 扫描记录体查找冲突是否存在。

3.2 冲突数据库的建立

在不包括冲突检测与解决模块的基于策略的网络管理软件中, 策略的一般定义是

为了有效的实现数据库的功能, 向策略类中添加如下属性

其中Temporalor Classifier是指策略执行时间的一些特性, 它包括10种类型。并且把这10种类型的集合称为完备集。Policycomment指策略的触发时间或者触发事件发生后策略开始执行的时刻, Policy Finish指策略的触发时间或者触发事件发生后策略执行结束的时刻, Policy Recur指策略满足某个条件时就反复执行。

通过策略间的Telllporal Classifier属性组合, 结合策略的Polieyeornment、Policy Finish和Policy Recur属性列举出所有的冲突形成冲突表, 从而组成冲突数据库。

4 解决冲突方法

4.1 特定策略优先级高于普通策略优先级规则

这个建立优先级的办法可以很好的解决管理员与职员角色之间的策略冲突。由于为管理员角色制定策略的特殊性, 可以认为当两者发生冲突时, 首先以管理员角色相关策略优先执行。

4.2 新策略优先级高于旧策略优先级

新策略优先级高于旧策略优先级规则也可以作为解决冲突的一种方法。这个解决办法一般是通过策略的创建时间来决定他们的执行顺序"创建时间最迟的策略一般比创建时间早的策略拥有更高的优先级。新策略优先级高于旧策略优先级规则在处理有些冲突时合适, 但是在处理别的冲突时则可能不合适。例如前面所述管理员角色和一般职员角色例子, 从前面的例子当中知道, 对赋予管理员角色的职员会发生外部策略冲突, 如果采用新策略优先级高于旧策略优先级来解决这个冲突时, 两个策略的创建时间都需要去检查, 当一个跟管理员角色有关的策略创建时间比与职员角色有关的策略创建时间早, 那么, 按照这个规则, 职员角色相关的策略具有高优先级, 而这明显是违背这种策略冲突的解决。因为在任何情况下, 管理员角色相关策略应该具有高优先级。

参考文献

[1]刘晖, 沈钧毅, 林欣.用CORBA创建电子商务系统[M].北京:希望电子出版社, 2011.

[2]宋丽华, 陈鸣.策略管理研究中的若干问题[J].解放军理工大学学报, 2012 (3) :6.

冲突检测篇6

1 卡片设置内部事件与自发事件

与HTML不同,一个WML页面由一个或多个卡片组成,在WML中使用标记定义一个卡片。卡片()不但能包含文本、图像、链接,还可在其中设置三种类型内部事件:自动向前跳转内部事件(onenterforward)、自动向后跳转内部事件(onenterforward)和定时跳转内部事件(ontimer),用来实现卡片自动向前跳转、自动向后跳转、定时跳转功能。

另外,在卡片中也可以设置自发事件,即在卡片标记属性中也可以设置上述三类内部事件来实现卡片间的自动跳转。

本文以onenterbackward(向前跳转)类型事件为例来检测和处理自发事件与内部事件发生冲突。

1.1 卡片中设置内部事件

1.2 卡片中设置自发事件

1.3 卡片内部事件与自发事件产生冲突及冲突解决方案

经过M3Gate手机模拟器测试后:如代码和图1所示,卡片设置自发事件与卡片设置内部事件时,会发生定义重复冲突。

测试代码如下:

发生事件冲突截图如图1所示。

解决方案:在卡片中只设置内部事件或只设置自发事件(即或在卡片()属性中设置自发事件,或在卡片标记内部设置内部事件)可避免事件定义冲突。

2 模板设置内部事件与自发事件

WML页面使用