智能路徑規(guī)劃算法在鞋底點膠領域的應用研究

郭超 王勇 王瑛

（廣東工業(yè)大學 廣東省廣州市 510006）

1 引言

鞋底點膠一直是制鞋業(yè)生產(chǎn)的重要工序，點膠的質(zhì)量好壞直接影響鞋子的質(zhì)量，傳統(tǒng)的制鞋業(yè)生產(chǎn)需要進行大量的人工點膠工序，不僅費時費力，成本也居高不下，而且鞋底點膠所用的膠散發(fā)出的氣味嚴重影響點膠工人的身體健康。近年來，隨著機器人領域的發(fā)展，為制鞋業(yè)帶來了自動化大量生產(chǎn)的機會，目前機器人技術正越來越多地被應用于制鞋行業(yè)中，鞋底點膠作為制鞋工藝中的關鍵工序，工廠實現(xiàn)大規(guī)模自動化操作能夠大大地提高生產(chǎn)效率及其產(chǎn)品質(zhì)量，并能改善員工的工作環(huán)境。越來越多的路徑規(guī)劃算法被應用在鞋底點膠工業(yè)生產(chǎn)中，為制鞋業(yè)自動化生產(chǎn)提供了發(fā)展的契機，但是隨著人們對于鞋的需求量與鞋品種類的日益增多，傳統(tǒng)的路徑規(guī)劃算法以及越來越暴露出其弊端，如容易陷入局部最優(yōu)，規(guī)劃時間過長等缺陷。

隨著時代的進步，人工智能技術發(fā)展越來越成熟，被應用在了各個領域，均取得了較好的成果，而在路徑規(guī)劃整體優(yōu)化的領域，也涌現(xiàn)了許多優(yōu)秀的處理模型，均表現(xiàn)出了許多優(yōu)秀的性能，例如MIP 利用混合整數(shù)規(guī)劃的方法建模，再利用求解器求解，得到最優(yōu)解。SOM 自組織映射神經(jīng)網(wǎng)絡模型競爭學習調(diào)整鄰域函數(shù)的形式獲得最優(yōu)解。基于強化學習的求解組合優(yōu)化模型RL，應用了強化學習和一個叫structure2vec 的圖嵌入（graph embedding）方法，提出了解決這一類問題的一種“元算法”。在本文中，我們將從傳統(tǒng)的點膠機控制點膠、傳統(tǒng)路徑規(guī)劃算法與建模求解的方向進行比較概述，并在結(jié)尾處討論應用建模方法解決點膠效率問題的未來可能的發(fā)展方向。

2 鞋底點膠控制概述

2.1 鞋底點膠封裝定義

鞋底點膠封裝是一個典型的二維點滴噴射系統(tǒng)，點膠頭相對于待加工元件或基板需要做大量的往返運動，通過完成點膠過程固定電子元件，材料等操作的過程。點膠頭運動的控制屬于組合優(yōu)化問題的一個典型代表，如何合理的規(guī)劃點膠頭的運動路徑直接影響生產(chǎn)的效率。

2.2 鞋底點膠控制系統(tǒng)的工作流程

鞋底點膠機所使用的點膠控制系統(tǒng)基本流程如圖1 所示，點膠過程通常是先由單目或雙目攝像頭識別待點膠產(chǎn)品并進行點云掃描建模，控制系統(tǒng)接收點云數(shù)據(jù)建立二維點膠地圖，算法規(guī)劃點膠路徑，輸出機械手點膠頭移動控制地圖并進行點膠作業(yè)。

2.3 鞋底點膠效率評價標準

點膠路徑規(guī)劃問題是組合優(yōu)化問題的一個典型代表，可能出現(xiàn)的點膠路徑數(shù)目與待加工點數(shù)目呈指數(shù)型增長關系，因此，衡量一個點膠路徑規(guī)劃算法效率的評價標準就是判斷點膠規(guī)劃所需的時間T 與點膠規(guī)劃的路徑L，一個優(yōu)秀的點膠路徑規(guī)劃算法求解應能在較短的時間T 內(nèi)規(guī)劃出能遍歷點膠地圖上所有的點且每個點只訪問一次的較短的路徑L 長度。

3 傳統(tǒng)鞋底點膠手段

3.1 手動或半自動點膠控制

傳統(tǒng)的點膠方法有人工手動點膠，不僅效率低，而且還會導致產(chǎn)品質(zhì)量問題以及工作環(huán)境惡劣導致的工人身體健康問題。直到左力等發(fā)明了一種鞋大底自動點膠機，推動了半自動化鞋底點膠的進展，但是依然缺乏自動化點膠的點膠路徑指引，無法真正實現(xiàn)自動化，KWON 等提出了一種基于鞋底輪廓生成噴膠軌跡的辦法，解決了鞋底邊緣點膠的問題，但是隨著鞋品種類的發(fā)展，鞋底功能性的發(fā)展，點膠不再局限于鞋底邊緣，因此該方法無法針對個性化制鞋的復雜點膠產(chǎn)生效果，KIM 提出了一種基于鞋底三視圖和鞋幫的三維掃描數(shù)據(jù)自動提取噴膠軌跡的方法，然而該三維掃描技術成本較高，且操作復雜，規(guī)劃效率低，無法控制精度。

4 傳統(tǒng)路徑規(guī)劃算法控制點膠

4.1 蟻群算法控制系統(tǒng)

蟻群算法是一種模擬螞蟻覓食行為的模擬優(yōu)化算法，其基本原理是每一個螞蟻在走過的路徑上釋放信息素，遇見未知路口則隨機選擇并釋放與路徑長度有關的信息素，信息素濃度與路徑長度成反比，后面的螞蟻再次碰到該路口則會優(yōu)先選擇信息素濃度較高的路徑，如此迭代會存在最優(yōu)路徑上的信息素濃度越來越大，從而形成最優(yōu)路徑。其中，每一只螞蟻選擇目標點的概率取決于目標點之間的距離和當前連接支路所含的信息素余量有關，設置禁忌表控制螞蟻遍歷所有目標點以實現(xiàn)非重復遍歷。

如果把鞋底點膠任務抽象為二維旅行商問題，則有如下的問題模型： 給出待點膠點組合V=v1,v2,v3,…,vn。代表點vi 與vj 的歐式距離，M 代表該組合問題的解集，則必然存在一個最優(yōu)解M*，使得：

蟻群算法模型經(jīng)過多次的文獻優(yōu)化改進，國內(nèi)外對離散問題的蟻群改進算法成果很多，其中在點膠領域以該領域點膠規(guī)模不確定等情況多使用自適應蟻群優(yōu)化算法，自適應蟻群優(yōu)化算法其最基本的改進方法是對蟻群模型的關鍵因素進行自適應調(diào)整，主要包括對：對蟻群算法狀態(tài)轉(zhuǎn)移概率，信息素揮發(fā)因子，信息量等自適應調(diào)整。

智能點膠領域相關文獻采用蟻群優(yōu)化系統(tǒng)解決的點膠效率優(yōu)化問題采用協(xié)調(diào)的α 與β 做控制信息素與可見度的參數(shù)應用，降低算法因參數(shù)不當而導致的過度隨機性從而復雜度過高與較快收斂導致的陷入局部最優(yōu)的情況，并且為提高點膠規(guī)劃路徑的效率，避免因點膠問題規(guī)模過大導致的算法復雜度過大，使得算法規(guī)劃效率過低，采用根據(jù)問題規(guī)模設定最大迭代次數(shù)，路徑解長度質(zhì)量滿足條件范圍，或者設定的最大規(guī)劃時間。

圖1：點膠控制系統(tǒng)基本流程

4.2 蟻群，粒子群算法控制系統(tǒng)

蟻群算法在解決大規(guī)模的點膠問題也暴露出了許多缺點，并且要解決這些問題需要不斷的對參數(shù)進行改進，而蟻群算法參數(shù)過多，優(yōu)化比較困難，基于該問題，有學者提出使用蟻群與粒子群融合的解決方法。使用粒子群算法的全局搜索能力強，收斂速度快的特點，擬合蟻群算法的搜索能力差，難收斂，易陷入局部最優(yōu)的缺陷，同時，以蟻群算法的較強的局部搜索能力以及信息反饋能力彌補粒子群算法的局部搜索能力的缺陷，互相采取優(yōu)勢，構建出了ACO-PSO 算法模型，即首先以蟻群算法的一次遍歷探索的候選解做初始最優(yōu)解，再通過粒子群算法進行局部搜索更新，提高收斂速度，后期利用蟻群算法的信息素對搜索方向的影響避免粒子群算法搜索收斂速度慢的缺陷，既提高了算法高效性，又增加了尋找全局最優(yōu)解的能力。

在研究的最后該方法也對比了TSP 標準數(shù)據(jù)庫TSPLIB 中的Hopfield10、Eil51、Berlin52、rat99 四種實例進行測試。對于同一個TSP 問題分別對粒子群，蟻群，ACO-PSO 算法單獨運行，最后無論是平均路徑、最優(yōu)路徑長度，誤差率等均有長足的改進。

5 神經(jīng)網(wǎng)絡模型算法控制點膠

5.1 人工神經(jīng)網(wǎng)絡模型

人工神經(jīng)網(wǎng)絡(Artificial Neural Network, 簡稱ANN)，又稱神經(jīng)網(wǎng)絡（Neural Network，簡稱NN），是啟發(fā)于應用類似于大腦神經(jīng)突觸聯(lián)接的結(jié)構進行信息處理的數(shù)學模型，它的構筑理念是受到生物神經(jīng)網(wǎng)絡功能的運作啟發(fā)而產(chǎn)生的，試圖模擬大腦神經(jīng)網(wǎng)絡處理、記憶信息的方式進行信息處理，與其余基礎優(yōu)化算法相比，主要有三大優(yōu)勢：具有自學習能力，反饋網(wǎng)絡具有聯(lián)想存儲功能，高速尋優(yōu)化解的能力。神經(jīng)網(wǎng)絡最早應用于TSP 組合優(yōu)化的模型是1985年Hopfield 和Tank 的Hopfield 神經(jīng)網(wǎng)絡模型，其主要改進就是使用能量函數(shù)替代TSP 問題中的目標函數(shù), 通過能量函數(shù)確定神經(jīng)元之間的相互連接權限, 隨著網(wǎng)絡狀態(tài)的逐漸變化, 當能量達到平衡時, 就可以得到局部最優(yōu)解。

5.2 Hopfiled神經(jīng)網(wǎng)絡的點膠路徑軌跡優(yōu)化

Hopfiled 神經(jīng)網(wǎng)絡是一種遞歸神經(jīng)網(wǎng)絡，結(jié)合存儲系統(tǒng)和二元系統(tǒng)的神經(jīng)網(wǎng)絡。它保證了向局部極小的收斂，但收斂到錯誤的局部極小值(local minimum)，而非全局極小(global minimum)的情況也可能發(fā)生。

用Hopfiled 求解TSP 問題的基本思路是：設待點膠任務地圖存在N 個點膠點，建立一個擁有N2 個神經(jīng)元、帶反饋的神經(jīng)網(wǎng)絡，首先給網(wǎng)絡設置一組初始權值，然后經(jīng)過多次迭代計算，改變網(wǎng)絡能量和神經(jīng)元狀態(tài)。當網(wǎng)絡能量不再降低時, 神經(jīng)元的輸出矩陣即為問題的解。求解點膠問題的Hopfiled 神經(jīng)網(wǎng)絡為了精確性一般采用連續(xù)型而不是離散型，則其神經(jīng)元閾值函數(shù)可以設置為雙曲正切函數(shù)，一般形式為：

其中xi 代表第i 個點膠點，且x 與i 均滿足區(qū)間[1,N]，解矩陣約束條件為：每行有且僅有一個點膠點被訪問即標記為1，每列有且僅有一個點膠點被訪問標記為1，分別保證每個點都被訪問，且僅被訪問一次。

判斷解的合法性除了滿足上述的約束，還要滿足在一定的迭代次數(shù)的范圍內(nèi)完成路徑的尋找，但是實驗發(fā)現(xiàn)如果沒有選用合適的模型參數(shù)組合很容易導致Hopfiled 容易出現(xiàn)局部最優(yōu)的情況，而且求解較為不穩(wěn)定，在最大迭代次數(shù)內(nèi)無法完成。因此，對Hopfiled神經(jīng)網(wǎng)絡模型的應用應針對求解問題的特點進行參數(shù)的嘗試，才能更好的發(fā)揮模型的規(guī)劃能力得到較為滿意的結(jié)果。

5.3 SOM神經(jīng)網(wǎng)絡的點膠路徑軌跡優(yōu)化

SOM（Self-Organizing Maps，SOM）神經(jīng)網(wǎng)絡模型是由Teuvo Kohonen 教授于1998年提出，是一種無監(jiān)督學習的聚類方法，受人類大腦神經(jīng)元的自組織和側(cè)抑制現(xiàn)象啟發(fā)。不同外部刺激引起大腦皮層各個區(qū)域的反應是不同的，因此該模型以一種低維的方式來反應高維問題，生物神經(jīng)元之間存在側(cè)抑制現(xiàn)象，臨近的神經(jīng)元相互激勵，較遠的神經(jīng)元相互抑制。響應最強的神經(jīng)元即獲勝神經(jīng)元，以它為中心，會形成一個區(qū)域，距離中心越遠激勵越弱，這個區(qū)域就是“優(yōu)勝鄰域”，而SOM 神經(jīng)網(wǎng)絡針對組合優(yōu)化的TSP 問題的求解重點就是對鄰域函數(shù)的修改，通常求解此類二維點膠問題是通過以鞋底邊緣為邊界把神經(jīng)元排列成類圓形，通過競爭學習策略使得每個點只與其前后神經(jīng)元進行進行調(diào)整，同時通過學習率α 控制收斂，學習率曲線應該是一個遞減的曲線，其基本形式應該是：

這里α 是隨學習時間變化的特定時間的學習速率，g 是以獲勝神經(jīng)元為中心、具有領域分散h 的高斯函數(shù)。衰減函數(shù)中分別乘以兩個給定的值γ，分別代表學習速率和鄰近距離。

以上述方法，通過把鞋底點膠任務掃描轉(zhuǎn)化成二維點膠地圖任務，即2D的TSP問題，利用SOM神經(jīng)網(wǎng)絡模型，通過競爭學習策略，從任意一點開始按照獲勝神經(jīng)元出現(xiàn)的順序把獲勝神經(jīng)元與點膠點相連，以此就構建出一個全局最優(yōu)路徑。

6 神經(jīng)網(wǎng)絡模型的挑戰(zhàn)與點膠應用的展望

在神經(jīng)網(wǎng)絡模型日益發(fā)展多樣化的今天，誕生了許許多多優(yōu)秀的模型，也推動了不同領域?qū)ι窠?jīng)網(wǎng)絡方法的探索與應用，特別是在模式識別，智能控制領域都有非常吸引人的應用前景。以其具有獨特的高度復雜的非線性動力學習系統(tǒng)而被廣泛應用，但是其最大的特點在于具有大規(guī)模并行、分布式存儲和處理、自組織、自適應和自學能力，特別適合處理需要同時考慮許多因素和條件的、不精確和模糊的信息處理問題。盡管當今神經(jīng)網(wǎng)絡技術獲得了飛速的發(fā)展，在組合優(yōu)化問題領域有著比較卓越的效果，但是仍然面臨一系列的挑戰(zhàn)，如黑盒性，開發(fā)難度，訓練數(shù)據(jù)量需求大，計算代價高昂等缺陷。接下來，針對工業(yè)鞋底點膠生產(chǎn)的應用背景，我們討論一些可能的發(fā)展方向。

6.1 無監(jiān)督學習或半監(jiān)督學習

無監(jiān)督學習是當一個應用缺乏足夠的先驗知識，難以人工標注類別或進行人工類別標注的成本太高，而讓模型能根據(jù)類別未知(沒有被標記)的訓練樣本解決模式識別中的各種問題，半監(jiān)督學習則是使用大量的未標記數(shù)據(jù)，以及同時使用標記數(shù)據(jù)，來進行模式識別工作。鞋底點膠領域以其大量存在各式各樣的鞋底型號的無標簽數(shù)據(jù)，而導致人工標注類別訓練模型變得極為困難，而且由于不同品種，不同生產(chǎn)線的生產(chǎn)任務不同，鞋底模型也大相徑庭，逐一標注訓練非常耗費人工成本，不具有普適性。因此，無監(jiān)督或半監(jiān)督學習將會是日后點膠應用領域的重點研究方向。

6.2 通用性

構建通用型神經(jīng)網(wǎng)絡模型解決鞋底點膠組合優(yōu)化問題能大大節(jié)約運行成本，由于不同生產(chǎn)線，不同型號的鞋點膠需求也各不相同，算法運行的性能也變得不可控，因此，處理各種不同程度組合優(yōu)化問題的高性能模型仍是一個研究熱點，遷移學習是解決此問題的一種趨勢。

6.3 特征結(jié)合規(guī)劃點膠

針對鞋底特征提取進行重點點膠能有效提高點膠效率，以多任務規(guī)劃合并的點膠形式是高性能規(guī)劃點膠的一大趨勢，針對鞋底通用特征進行固定化點膠路徑，僅對具有不同特征的點膠任務進行規(guī)劃能有效提高規(guī)劃效率，以多規(guī)劃任務并行的方法換取時間效率是目前最主流的高效點膠模式。