馬柯  賈為征  

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

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

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

0  前言

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

1  避讓策略

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

B 天車(chē)比A 天車(chē)任務(wù)開(kāi)始時(shí)間早的任務(wù)，都排除掉，不做沖突計(jì)算

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

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

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

圖1 避讓策略圖示

Fig.1 Collision Avoidance Strategy Diagram

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

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

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

表1  天車(chē)任務(wù)表

Table 1  Crane Task Schedule

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

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

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

Fig.2 Task Unified Coordinate Process

3 計(jì)算沖突時(shí)間點(diǎn)

3.1問(wèn)題描述

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

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

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

Table 2  Line Segment Coordinate Diagram

直觀判斷，A1是斜線，穿過(guò)了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 向量外積法的原理

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

1、計(jì)算向量叉積

2、判斷叉積的符號(hào)：

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

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

3、綜合判斷：

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

3.3 計(jì)算過(guò)程 

判斷叉積的符號(hào)，對(duì)于線段 AB：

AB×AC=4680675（正）

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

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

對(duì)于線段 CD：

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

CD×CB=5401325（正）

符號(hào)相反，說(shuō)明點(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時(shí)A1位置,p1.x=0,p1.y=255915;p2是71s時(shí)A1的位置,則p2.x=71,p2.y=397915;p3是0s時(shí)B2位置,則p3.x=0,p3.y=321840,p4是71s時(shí)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é)果

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

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

Fig.3 Overhead Crane Trajectory Diagram

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

5 結(jié)語(yǔ)

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

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

參考文獻(xiàn)

[1] 王磊, 孫立. 基于時(shí)間窗和向量叉積法的天車(chē)任務(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] 張偉, 李明. 天車(chē)調(diào)度系統(tǒng)中的任務(wù)沖突檢測(cè)與避讓策略研究[J]. 自動(dòng)化技術(shù)與應(yīng)用, 2022, 41(3): 45-52. DOI:10.3969/j.issn.1003-7241.2022.03.008.

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

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

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

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

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

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

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

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