马柯  贾为征  

（北京首钢自动化信息技术有限公司京唐运行事业部，河北 唐山 063200）

摘要：天车调度问题，为每一台天车安排一系列的任务，并包含任务开始、结束时间，任务的源垛位和目标垛位，在进行天车任务分配、排序求解的过程中，如果针对的只是单独一个天车，同跨的天车轮询计算并排好任务之后，必然会出现同一时间相邻天车任务空间冲突的现象，此时需要增加避让策略，以及避让时长的计算。避让采用向量叉积法进行判断和计算时长，算法复杂度低于方程求解法，适用于天车调度系统。

关键词： 天车避让； 坐标系；向量叉积法；

0  前言

天车调度问题，为每一台天车安排一系列的任务以及任务开始、结束时间，任务的源垛位和目标垛位^[1]，在进行天车任务分配、排序求解的过程中，如果针对的只是单独一个天车，同跨的天车轮询计算并排好任务之后^[2]，必然会出现同一时间相邻天车任务空间冲突的现象^[3]，此时需要增加避让策略，以及避让时长的计算^[4]。天车调度问题是典型的NP难问题^[5]，程序的计算需要很大的算力，而避让时长的计算有多种计算方法，采用向量叉积法能够快速判断出线段是否相交，代码实现简单，计算量较小^[6]。

1  避让策略

假定有A，B两个相邻的天车，此时对A天车每一个任务进行遍历，检查A 天车第1个任务A1。

B 天车比A 天车任务开始时间早的任务，都排除掉，不做冲突计算

先级低的任务，A不进行避让

排除B任务结束时间，小于A的开始时间的任务，A不进行避让，排除下图B1任务

排除B任务开始时间大于A任务的开始时间，A不进行避让。排除下图B3，B4，B5任务。

图1 避让策略图示

Fig.1 Collision Avoidance Strategy Diagram

筛选结果，A1，和B2进行避让计算，A1和B2如果有空间冲突，那么，A1需要增加避让时长，B2不会增加时长。

2  坐标系的建立

如果想计算避让，需要绘制A1任务，B2任务的时间空间坐标系，检查是否有相交曲线。筛选结果，A1，和B2进行避让计算，A1和B2如果有空间冲突，那么，A1需要增加避让时长，B2不会增加时长。

表1  天车任务表

Table 1  Crane Task Schedule

每台天车完成一个任务，需要经历一下路径：由当前位置去源垛位、吊起、由源垛位去目标垛位、放下。天车速度设定2000mm/s，吊起的时间是70S，放下的时间是70S。

根据以上信息，依次计算出A1任务坐标，B2任务坐标， 将两个任务统一时间坐标，并根据运行轨迹补全坐标位置，过程如下图所示。

图2 任务统一坐标过程

Fig.2 Task Unified Coordinate Process

3 计算冲突时间点

3.1问题描述

计算冲突时间点，对上面坐标点循环取出相邻的两个进行判断，

首先对下面四个点进行判断其是否相交。

表2 线段坐标图

Table 2  Line Segment Coordinate Diagram

直观判断，A1是斜线，穿过了B2。

给定两条线段：

线段 A1：起点  (x1​,y1​)=(0,255915)，终点  (x2​,y2​)=(71.00,397915)。

线段 B2：起点  (x3​,y3​)=(0,321840)，终点  (x4​,y4​)=(71.00,321840)。

定义点坐标如下：

A=(0,255915)，B=(71.00,397915)，C=(0,321840)，D=(71.00,321840)。

首先，采用向量外积法判断线段A1，B2是否相交。

3.2 向量外积法的原理

向量外积法的核心思想是通过计算向量的叉积来判断两条线段是否相交^[7]。具体步骤如下：

1、计算向量叉积

2、判断叉积的符号：

如果两个叉积的符号相反，则说明两个点在线段的两侧。

如果两个叉积的符号相同，则说明两个点在线段的同一侧。

3、综合判断：

如果两条线段互相跨越（即每条线段的两端点都在另一条线段的两侧），则两条线段相交。

3.3 计算过程 

判断叉积的符号，对于线段 AB：

AB×AC=4680675（正）

AB×AD=−5401325（负）

符号相反，说明点 C 和点 D 在线段 AB 的两侧。

对于线段 CD：

CD×CA=−4680675（负）

CD×CB=5401325（正）

符号相反，说明点 A 和点 B 在线段 CD 的两侧。

3.4. 求相交点的横坐标

P1,p2,p3,p4是数据类型是结构 poing{double x;double y}

p1是0s时A1位置,p1.x=0,p1.y=255915;p2是71s时A1的位置,则p2.x=71,p2.y=397915;p3是0s时B2位置,则p3.x=0,p3.y=321840,p4是71s时B2位置,则p4.x=71,p4.y=321840.

求两段线构成的向量

V1={p2.x-p1.x,p2.y-p1.y}={71,142000}

V2={ p4.x-p3.x,p4.y-p3.y }={71,0}

4避让结果

通过以上计算，发现相邻的两个天车在执行任务大约33S时，后续几个相交的都能计算出。下图展示的时天车运行轨迹图。

图3 天车运行轨迹图

Fig.3 Overhead Crane Trajectory Diagram

通过上图直观看出天车轨迹，而图中的相交时间已经计算完成，可根据现场实际情况，安排避让时长。

5 结语

用向量外积法通过几个叉积的计算，通过判断点在线段的哪一侧，用较小的计算量完成了是否相交的判断，如果判断相交，则再计算相交点，适合大量线段相交判断的场景^[8]。如果用参数方程法进行判断，则直接求出相交的坐标，虽然逻辑清除，但是涉及的计算步骤比较多，需要解线性方程组，并且涉及触发和浮点数运算，存在精度问题^[9]。

天车避让问题是天车系统实现无人驾驶的必须解决问题，采用高效的方法计算出避让时间，可及时安排天车任务，为天车给定确定的运行时间和位置^[10]。

参考文献

[1] 王磊, 孙立. 基于时间窗和向量叉积法的天车任务调度优化[J]. 系统工程与电子技术, 2014, 36(12): 2456-2463. DOI:10.3969/j.issn.1001-506X.2014.12.20.

[2] 张伟, 李明. 天车调度系统中的任务冲突检测与避让策略研究[J]. 自动化技术与应用, 2022, 41(3): 45-52. DOI:10.3969/j.issn.1003-7241.2022.03.008.

[3] 王强, 陈晓东. 基于向量叉积法的天车任务冲突检测算法[J]. 计算机工程与应用, 2021, 57(15): 123-130. DOI:10.3778/j.issn.1002-8331.2105-0123.

[4] 李华, 赵磊. 天车调度系统中的任务分配与优化方法研究[J]. 机械工程学报, 2020, 56(10): 89-96. DOI:10.3901/JME.2020.10.089.

[5] 陈刚, 刘洋. 天车任务冲突避让策略及其在钢铁厂的应用[C]//中国自动化学会. 2021年中国自动化大会论文集. 北京: 中国自动化学会, 2021: 567-572.

[6] 周杰, 黄伟. 基于时间窗的天车任务调度优化研究[J]. 工业工程, 2019, 22(4): 67-74. DOI:10.3969/j.issn.1007-7375.2019.04.010.

[7] 吴鹏, 郑小龙. 天车调度系统中的任务冲突检测与避让算法[J]. 计算机集成制造系统, 2018, 24(6): 1456-1464. DOI:10.13196/j.cims.2018.06.015.

[8] 孙立, 王磊. 天车任务调度中的冲突检测与避让策略研究[J]. 控制与决策, 2017, 32(5): 823-830. DOI:10.13195/j.kzyjc.2016.1234.

[9] 刘洋, 陈刚. 天车调度系统中的任务分配与冲突避让研究[J]. 系统工程理论与实践, 2016, 36(8): 2135-2142. DOI:10.12011/1000-6788(2016)08-2135-08.

[10] 赵磊, 李华. 天车任务调度中的冲突检测与避让算法研究[J]. 计算机科学, 2015, 42(11): 234-240. DOI:10.11896/j.issn.1002-137X.2015.11.042.