馬柯  賈為征  

（北京首鋼自動化信息技術(shù)有限公司京唐運(yùn)行事業(yè)部，河北 唐山 063200）

摘要：天車調(diào)度問題，為每一臺天車安排一系列的任務(wù)，并包含任務(wù)開始、結(jié)束時間，任務(wù)的源垛位和目標(biāo)垛位，在進(jìn)行天車任務(wù)分配、排序求解的過程中，如果針對的只是單獨(dú)一個天車，同跨的天車輪詢計算并排好任務(wù)之后，必然會出現(xiàn)同一時間相鄰天車任務(wù)空間沖突的現(xiàn)象，此時需要增加避讓策略，以及避讓時長的計算。避讓采用向量叉積法進(jìn)行判斷和計算時長，算法復(fù)雜度低于方程求解法，適用于天車調(diào)度系統(tǒng)。

關(guān)鍵詞： 天車避讓； 坐標(biāo)系；向量叉積法；

0  前言

天車調(diào)度問題，為每一臺天車安排一系列的任務(wù)以及任務(wù)開始、結(jié)束時間，任務(wù)的源垛位和目標(biāo)垛位^[1]，在進(jìn)行天車任務(wù)分配、排序求解的過程中，如果針對的只是單獨(dú)一個天車，同跨的天車輪詢計算并排好任務(wù)之后^[2]，必然會出現(xiàn)同一時間相鄰天車任務(wù)空間沖突的現(xiàn)象^[3]，此時需要增加避讓策略，以及避讓時長的計算^[4]。天車調(diào)度問題是典型的NP難問題^[5]，程序的計算需要很大的算力，而避讓時長的計算有多種計算方法，采用向量叉積法能夠快速判斷出線段是否相交，代碼實(shí)現(xiàn)簡單，計算量較小^[6]。

1  避讓策略

假定有A，B兩個相鄰的天車，此時對A天車每一個任務(wù)進(jìn)行遍歷，檢查A 天車第1個任務(wù)A1。

B 天車比A 天車任務(wù)開始時間早的任務(wù)，都排除掉，不做沖突計算

先級低的任務(wù)，A不進(jìn)行避讓

排除B任務(wù)結(jié)束時間，小于A的開始時間的任務(wù)，A不進(jìn)行避讓，排除下圖B1任務(wù)

排除B任務(wù)開始時間大于A任務(wù)的開始時間，A不進(jìn)行避讓。排除下圖B3，B4，B5任務(wù)。

圖1 避讓策略圖示

Fig.1 Collision Avoidance Strategy Diagram

篩選結(jié)果，A1，和B2進(jìn)行避讓計算，A1和B2如果有空間沖突，那么，A1需要增加避讓時長，B2不會增加時長。

2  坐標(biāo)系的建立

如果想計算避讓，需要繪制A1任務(wù)，B2任務(wù)的時間空間坐標(biāo)系，檢查是否有相交曲線。篩選結(jié)果，A1，和B2進(jìn)行避讓計算，A1和B2如果有空間沖突，那么，A1需要增加避讓時長，B2不會增加時長。

表1  天車任務(wù)表

Table 1  Crane Task Schedule

每臺天車完成一個任務(wù)，需要經(jīng)歷一下路徑：由當(dāng)前位置去源垛位、吊起、由源垛位去目標(biāo)垛位、放下。天車速度設(shè)定2000mm/s，吊起的時間是70S，放下的時間是70S。

根據(jù)以上信息，依次計算出A1任務(wù)坐標(biāo)，B2任務(wù)坐標(biāo)， 將兩個任務(wù)統(tǒng)一時間坐標(biāo)，并根據(jù)運(yùn)行軌跡補(bǔ)全坐標(biāo)位置，過程如下圖所示。

圖2 任務(wù)統(tǒng)一坐標(biāo)過程

Fig.2 Task Unified Coordinate Process

3 計算沖突時間點(diǎn)

3.1問題描述

計算沖突時間點(diǎn)，對上面坐標(biāo)點(diǎn)循環(huán)取出相鄰的兩個進(jìn)行判斷，

首先對下面四個點(diǎn)進(jìn)行判斷其是否相交。

表2 線段坐標(biāo)圖

Table 2  Line Segment Coordinate Diagram

直觀判斷，A1是斜線，穿過了B2。

給定兩條線段：

線段 A1：起點(diǎn)  (x1?,y1?)=(0,255915)，終點(diǎn)  (x2?,y2?)=(71.00,397915)。

線段 B2：起點(diǎn)  (x3?,y3?)=(0,321840)，終點(diǎn)  (x4?,y4?)=(71.00,321840)。

定義點(diǎn)坐標(biāo)如下：

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

首先，采用向量外積法判斷線段A1，B2是否相交。

3.2 向量外積法的原理

向量外積法的核心思想是通過計算向量的叉積來判斷兩條線段是否相交^[7]。具體步驟如下：

1、計算向量叉積

2、判斷叉積的符號：

如果兩個叉積的符號相反，則說明兩個點(diǎn)在線段的兩側(cè)。

如果兩個叉積的符號相同，則說明兩個點(diǎn)在線段的同一側(cè)。

3、綜合判斷：

如果兩條線段互相跨越（即每條線段的兩端點(diǎn)都在另一條線段的兩側(cè)），則兩條線段相交。

3.3 計算過程 

判斷叉積的符號，對于線段 AB：

AB×AC=4680675（正）

AB×AD=−5401325（負(fù)）

符號相反，說明點(diǎn) C 和點(diǎn) D 在線段 AB 的兩側(cè)。

對于線段 CD：

CD×CA=−4680675（負(fù)）

CD×CB=5401325（正）

符號相反，說明點(diǎn) A 和點(diǎn) B 在線段 CD 的兩側(cè)。

3.4. 求相交點(diǎn)的橫坐標(biāo)

P1,p2,p3,p4是數(shù)據(jù)類型是結(jié)構(gòu) 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.

求兩段線構(gòu)成的向量

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

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

4避讓結(jié)果

通過以上計算，發(fā)現(xiàn)相鄰的兩個天車在執(zhí)行任務(wù)大約33S時，后續(xù)幾個相交的都能計算出。下圖展示的時天車運(yùn)行軌跡圖。

圖3 天車運(yùn)行軌跡圖

Fig.3 Overhead Crane Trajectory Diagram

通過上圖直觀看出天車軌跡，而圖中的相交時間已經(jīng)計算完成，可根據(jù)現(xiàn)場實(shí)際情況，安排避讓時長。

5 結(jié)語

用向量外積法通過幾個叉積的計算，通過判斷點(diǎn)在線段的哪一側(cè)，用較小的計算量完成了是否相交的判斷，如果判斷相交，則再計算相交點(diǎn)，適合大量線段相交判斷的場景^[8]。如果用參數(shù)方程法進(jìn)行判斷，則直接求出相交的坐標(biāo)，雖然邏輯清除，但是涉及的計算步驟比較多，需要解線性方程組，并且涉及觸發(fā)和浮點(diǎn)數(shù)運(yùn)算，存在精度問題^[9]。

天車避讓問題是天車系統(tǒng)實(shí)現(xiàn)無人駕駛的必須解決問題，采用高效的方法計算出避讓時間，可及時安排天車任務(wù)，為天車給定確定的運(yùn)行時間和位置^[10]。

參考文獻(xiàn)

[1] 王磊, 孫立. 基于時間窗和向量叉積法的天車任務(wù)調(diào)度優(yōu)化[J]. 系統(tǒng)工程與電子技術(shù), 2014, 36(12): 2456-2463. DOI:10.3969/j.issn.1001-506X.2014.12.20.

[2] 張偉, 李明. 天車調(diào)度系統(tǒng)中的任務(wù)沖突檢測與避讓策略研究[J]. 自動化技術(shù)與應(yīng)用, 2022, 41(3): 45-52. DOI:10.3969/j.issn.1003-7241.2022.03.008.

[3] 王強(qiáng), 陳曉東. 基于向量叉積法的天車任務(wù)沖突檢測算法[J]. 計算機(jī)工程與應(yīng)用, 2021, 57(15): 123-130. DOI:10.3778/j.issn.1002-8331.2105-0123.

[4] 李華, 趙磊. 天車調(diào)度系統(tǒng)中的任務(wù)分配與優(yōu)化方法研究[J]. 機(jī)械工程學(xué)報, 2020, 56(10): 89-96. DOI:10.3901/JME.2020.10.089.

[5] 陳剛, 劉洋. 天車任務(wù)沖突避讓策略及其在鋼鐵廠的應(yīng)用[C]//中國自動化學(xué)會. 2021年中國自動化大會論文集. 北京: 中國自動化學(xué)會, 2021: 567-572.

[6] 周杰, 黃偉. 基于時間窗的天車任務(wù)調(diào)度優(yōu)化研究[J]. 工業(yè)工程, 2019, 22(4): 67-74. DOI:10.3969/j.issn.1007-7375.2019.04.010.

[7] 吳鵬, 鄭小龍. 天車調(diào)度系統(tǒng)中的任務(wù)沖突檢測與避讓算法[J]. 計算機(jī)集成制造系統(tǒng), 2018, 24(6): 1456-1464. DOI:10.13196/j.cims.2018.06.015.

[8] 孫立, 王磊. 天車任務(wù)調(diào)度中的沖突檢測與避讓策略研究[J]. 控制與決策, 2017, 32(5): 823-830. DOI:10.13195/j.kzyjc.2016.1234.

[9] 劉洋, 陳剛. 天車調(diào)度系統(tǒng)中的任務(wù)分配與沖突避讓研究[J]. 系統(tǒng)工程理論與實(shí)踐, 2016, 36(8): 2135-2142. DOI:10.12011/1000-6788(2016)08-2135-08.

[10] 趙磊, 李華. 天車任務(wù)調(diào)度中的沖突檢測與避讓算法研究[J]. 計算機(jī)科學(xué), 2015, 42(11): 234-240. DOI:10.11896/j.issn.1002-137X.2015.11.042.