馬柯  賈為征  

（北京首鋼自動化信息技術有限公司京唐運行事業部，河北 唐山 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.