用神經(jīng)網(wǎng)絡(luò)方法處理FMS

引言 
            在柔性制造系統(tǒng)(Flexible Manufacturing System,FMS)中最具柔性和發(fā)展最快的物料輸送系統(tǒng) 之一是自動導向小車系統(tǒng)(Automated Guided Ve— hicleSystem，以下簡稱AGV系統(tǒng))。物料輸送是制 造過程中的關(guān)鍵活動。物料輸送包括物料在生產(chǎn)的 各個階段的拾取、運送、存儲和包裝。物料輸送的準確及時對于提高FMS的生產(chǎn)效率和降低成本意義重大。 
            一個AGV系統(tǒng)由若干臺計算機控制的無人駕 駛小車組成。大部分現(xiàn)有AGV是在計算機調(diào)度下 沿導向軌道行駛，雖然其導向方法具有高可靠性，但卻降低了AGV系統(tǒng)的柔性。自由分布AGV系統(tǒng)使 用超聲波或激光視覺等裝置引導小車，使小車可在 車間內(nèi)自由行駛，從而增加了系統(tǒng)的通用性。
            自由分布AGV系統(tǒng)所碰到的一個主要問題是 小車的調(diào)度和控制，需要有效的AGV控制器監(jiān)測 設(shè)備的狀態(tài)和調(diào)節(jié)物料的運送，以使得能在適當?shù)?時間將適當?shù)奈锪纤偷竭m當?shù)牡攸c。
             本文論述在FMS中，如何以最有效的方式在 調(diào)節(jié)時間間隔內(nèi)處理同時發(fā)生的多個請求AGV運 送的情況。探討了AGV路徑規(guī)劃和分配問題，提出 了相應(yīng)數(shù)學模型，提供了自組織神經(jīng)網(wǎng)絡(luò)解決方案 的算法。
1、一般FMS的物流情況 
             對于一般FMS而言，每臺機床都是通用的，可實施多種操作�，F(xiàn)場備有一個儲備庫，在線工件(Work—In—Process WIP)需由 AGV從儲備庫運送到機床。與每臺機床相連的是輸入緩沖站(1nput Buffer IB)和輸出緩沖站(OutputBuffer OB)。當一項操作完成之后，機床會自動地將WIP卸載到OB 并發(fā)出運走請求。WIP一直等在OB上直到AGV 來拾取為止。由于緩沖站容量有限，一臺機床可能出現(xiàn)“撐死”或“饑餓”現(xiàn)象。“撐死”發(fā)生在一臺機床要 卸載剛完成的WIP到已經(jīng)飽和的OB上時，此時，該機床發(fā)出緊急運走請求。相應(yīng)地，“饑餓”則發(fā)生在一臺機床從已經(jīng)空了的IB上取下一個加工工件時，此時，該機床發(fā)出緊急運來請求。緊急運走請求也會 發(fā)生在當儲備庫中的WIP已到了該對其實施操作時。
              除了緊急運走、緊急運來請求外，WIP運送請 求還包括一般運走與運來請求。當任何一臺機床其 IB空了時，則發(fā)出運來請求，當一工件從儲備庫或上位機床運來并傳送到IB上后，該運來請求就被滿 足了。而運走請求的滿足是在從OB運走了WIP之后。
2、AGV路徑規(guī)劃和分配問題
2.1、問題的特征及解決方法 
                每一個AGV運送請求都涉及到兩個任務(wù)，即從一起始點拾取WIP，將其運送至一預(yù)先確定的送達點卸下。任務(wù)優(yōu)先關(guān)系要求先拾取后運送WIP，而拾取運送任務(wù)必須由同一臺AGV完成。在本研究背景下，一臺AGV一次只承載一個單位負荷，所謂一個單位負荷是指作為一個整體被夾持和傳輸?shù)墓ぜ�的集合。例如，一個裝有幾個工件的托盤[1]。因此，AGV在載有一個單位負荷去送達點途中再拾取另一個WIP是不允許的。
                與傳統(tǒng)的執(zhí)行單一運送請求而尋找最短路線的AGV規(guī)劃問題不同[2]，本研究尋找最短路徑涉及到的是執(zhí)行多項運送請求而不是一項。由于在自由分布AGV環(huán)境下，起始點到送達點間的最短路線變?yōu)闅W氏距離。因此傳統(tǒng)的方法不再適用，本研究致力于用神經(jīng)網(wǎng)絡(luò)方法來解決問題。
以下先闡述所開發(fā)系統(tǒng)的特點：
(1)系統(tǒng)每接受到一個運送請求時，都會進行規(guī)劃演算，立即分配一項AGV任務(wù)，以達到實時性要求；
(2)進行規(guī)劃演算時，將所有新的運送請求和所有系統(tǒng)內(nèi)還未被AGV拾取的WIP一起考慮，重新進行規(guī)劃。一般情況下，按先申請先享受服務(wù)的規(guī)劃 處理優(yōu)先次序。但也考慮根據(jù)當前系統(tǒng)狀態(tài)，原先的一般請求可能變成緊急請求，而緊急請求具有高優(yōu)先權(quán)；
(3)由于存在機床輸入和輸出緩沖站，并無必要在發(fā)出一般運送請求后立即將WIP運走。當一般運送請求發(fā)出時機床正在忙于下一工件的加工，因此，即使規(guī)劃演算開始于運送請求產(chǎn)生之后，機床的利用率并沒有受影響。
除以上所述之外，還有其他一些AGV系統(tǒng)問題需要解決。其中最重要的是車間內(nèi)的交通管理問 題。當無人駕駛小車遇到障礙物時需要避讓，當小車之間發(fā)生路線沖突時，需要沖突解決方法。通常設(shè)計一些控制區(qū)或緩沖區(qū)用于發(fā)生沖突時讓小車暫時避讓。為避免交通堵塞和小車干涉，文獻[2]提出了一些沖突解決方法，有幾何方法，if—then—else產(chǎn)生式 規(guī)則方法以及先到先服務(wù)規(guī)則(thefirst—comefirst— serve rule)方法。在本研究的自由分布AGV系統(tǒng)中，目標之一是確定每臺AGV的最短路徑。當運行 在該路徑上的AGV發(fā)生交通沖突時，應(yīng)用先到先服務(wù)規(guī)則。
2.2 數(shù)學模型
                首先將AGV從起始點拾取工件運送到送達點卸下工件定義為一項任務(wù)(Job)，則產(chǎn)生如下數(shù)學符號含義：
N——所涉及到的任務(wù)數(shù)目
di——任務(wù)i的起始點至送達點間的距離
dij——任務(wù)i的送達點至任務(wù)j的起始點間的距離
xij——當任務(wù)j在任務(wù)i完成后被立即執(zhí)行時為1，否則為0
U——不包括任務(wù)全集和單一任務(wù)子集的任務(wù)子集 
             約束條件(1)意味著在任務(wù)i之后立即執(zhí)行的只有一項任務(wù)。約束條件(2)表明緊接任務(wù)J．之前僅有一項任務(wù)。約束條件(3)限制一些子路徑：若任務(wù)j出現(xiàn)在任務(wù)i之后，那么禁止任務(wù)i在任務(wù)j之后。
                本研究采用被廣泛引用的自組織神經(jīng)網(wǎng)絡(luò)Ko honen網(wǎng)絡(luò)[3]。Kohonen網(wǎng)絡(luò)方法計算效率高并具有適應(yīng)不同情況的柔性，比如，上述數(shù)學模型僅適用于單一小車情況。當涉及多個小車時，Kohonen網(wǎng)絡(luò)方法也能夠提供綜合分配和路徑規(guī)劃的復雜模型。
3 AGV路徑規(guī)劃問題的Kohonen自組織神經(jīng)網(wǎng)絡(luò)
                在AGV規(guī)劃問題中，將要執(zhí)行的任務(wù)數(shù)目從1 計到N，即J1，J2，…，JN。每一個任務(wù)J由一對坐標 表示，對應(yīng)于任務(wù)J的起始點 和送達點的坐標。任務(wù)集中的一個排列可被看成為一組具體的拾取與送達任務(wù)指令。排列的目標是找 到最短的行駛距離。
                假設(shè)σ＝{1，2，…，N}為任務(wù)所涉及機床固定 位置的固定編號集，則路徑規(guī)劃任務(wù)就是給σ集中的每一位置分配唯一的一項任務(wù)i，并使得總的行駛距離最小。換句話說，在滿足最優(yōu)路徑?jīng)Q策的條件下，需要建立任務(wù)集(J1，J2，…，JN}與位置集σ＝ {1，2，…，N}間的一對一映射。運送任務(wù)所對應(yīng)的起始點和送達點的坐標是引導網(wǎng)絡(luò)學習的輸入樣本。當一輸入樣本存在時，與該 輸入樣本對應(yīng)的最小距離輸出節(jié)點(獲勝節(jié)點)，既全部輸出元素中對應(yīng)距離最短之元素被允許建立該輸入樣本的權(quán)重，同時在輸出層中的相鄰節(jié)點也建立該輸入樣本的較低權(quán)重。這樣做的目的是使得獲 節(jié)點處的相鄰節(jié)點在相同輸入樣本再次出現(xiàn)時也具有相類似反映。由于相鄰節(jié)點間的相互位置關(guān)系導致兩相鄰節(jié)點間距離最小，因而產(chǎn)生最短路徑。通過權(quán)重調(diào)節(jié)減低鄰域的長度，輸出節(jié)點相互間將變得越來越獨立，最終使得每一輸出節(jié)點被分配一個運送請求。
                在實際網(wǎng)絡(luò)訓練開始時，在輸出層并不存在輸 出節(jié)點，節(jié)點的數(shù)目按節(jié)點插入不斷增加，節(jié)點插入 過程對于改善網(wǎng)絡(luò)訓練速度和處理緊急請求以及多臺小車情況是很有用的。
3.1 單一AGV路徑規(guī)劃算法
                在以上所描述的算法中，在給定一個完整的任務(wù)集J1，J1，…JN的基礎(chǔ)上，如果在同一次迭代中，有兩個不同的任務(wù)都選擇同一節(jié)點作為獲勝點，則該節(jié)點被復制，新建立起的節(jié)點以相同的權(quán)重被插在輸出層獲勝點相鄰的左或右邊。如果在3次迭代中一個節(jié)點都沒有被選中為任何運送任務(wù)的獲勝點，則該節(jié)點被刪除。
3.2 多臺AGV路徑規(guī)劃和分配問題
             當涉及到多臺AGV時，系統(tǒng)需要保證每臺 AGV都以最短運行距離分配到任務(wù)，以使得每個物 料輸送系統(tǒng)的性能最優(yōu)化。算法的基本原理一是平 衡多臺 AGV的工作負荷，二是使所有被分配的 AGV的總運行距離最短。以下描述建立在Koho— nen自組織特征映射[3]基礎(chǔ)上的適用于多臺 AGV 情況的算法。
算法2
第1步：應(yīng)用算法1，在已給任務(wù)集基礎(chǔ)上獲得 單一路徑規(guī)劃結(jié)果。
第2步：令為當前AGV位置坐標(s＝l，2，…，M)，d1為所有送運任務(wù)應(yīng)當完成的時間界 限，分組匯集運送任務(wù)(保留路徑規(guī)劃次序)，使得每 組任務(wù)都能在時間界限d1之前完成，轉(zhuǎn)到第3步。
第3步：若在第2步中的任務(wù)組數(shù)小于等于M， 則對于每一任務(wù)組分配一臺距離組中第一節(jié)點位置 最近的AGV，讓其完成該組的所有運送任務(wù)；若任 務(wù)組數(shù)大于M(意味著AGV臺數(shù)不足夠)，則對每 一前M個組分配距離最近的的AGV前往。 在算法2 中還可以使用不同的策略。如不以時 間界限d1作為分組指標，可采用其他指標來分 組。再如當任務(wù)組數(shù)大于從時，可讓 AGV在超過 時間界限眾1之后繼續(xù)任務(wù)直到完成。策略的選擇應(yīng) 基于系統(tǒng)的條件以及其操作成本的大小。
4 結(jié)束語
                由于AGV路徑規(guī)劃和分配問題在整個FMS 運行中需反復被解決，所以有效的解決方法是很重要的。本文分析了一般FMS物流情況，研討了自由分布式AGV規(guī)劃問題的特征及相應(yīng)對策，并提出相應(yīng)的數(shù)學模型，闡述了在FMS環(huán)境下AGV的分配與路徑規(guī)劃問題的Kohonen自組織神經(jīng)網(wǎng)絡(luò)解 決方案的算法。這一算法和相應(yīng)的數(shù)學模型已應(yīng)用于一有兩臺AGV的FMS的實際運行中，目前運行情況良好。