AGV路徑規(guī)劃研究的國內外文獻綜述目錄TOC\o"1-3"\h\u7448AGV路徑規(guī)劃研究的國內外文獻綜述 114101.1AGV的發(fā)展歷史 121151.2AGV的國內外發(fā)展現(xiàn)狀 2301311.2.3路徑規(guī)劃問題的研究現(xiàn)狀 338971.4多AGV系統(tǒng)調度的研究現(xiàn)狀 41.1AGV的發(fā)展歷史AGV從最初出現(xiàn)到如今已經經歷了60年左右的發(fā)展歷史，據文獻記載第一臺AGV在1953年出現(xiàn)在歐洲，它由拖拉機經過改造而制成。結構簡單，僅用于運輸貨物，并且行駛路線十分死板，只能沿著固定路線行駛，缺乏靈活性和變通性。上個世紀70年代初，電磁技術的出現(xiàn)使人們可以通過電磁原理對AGV進行控制，美國巴雷特電器公司研制出了基于電磁導航的AGV[8]，根據規(guī)劃好的線路，事先將導線埋入地下，通過不同的電磁頻率控制AGV的速度，可以讓AGV能夠沿著導線前進，利用電磁技術進行導航比較簡單，但是要改變行走路徑則比較麻煩，因此，AGV只能按照提前鋪設好的磁條導線來行走，改變行走線路的成本較常高且后期維護也相當困難。在此之后經過了大約十幾年的發(fā)展，運用激光導引進行定位的AGV悄然問世了，瑞典丹納赫公司在1991成功制造研制出第一臺激光導航AGV[9]。激光導航是通過運用激光反射板來進行定位，此時AGV靈活性和定位準確度都有所提高，不再是只能沿著固定的路徑行駛，能夠比較方便的對路徑進行變更，從此AGV從有軌道發(fā)展了到無軌道階段。80年代后期出現(xiàn)了慣性導航技術[10]，通過車體上的陀螺儀計算出AGV的角速度和加速度，以此來獲得AGV當前所處的位置，這種定位方式十分準確且成本較為低廉。90年代以后，計算機控制技術與AGV的應用相結合大大提高了AGV的智能化，通過處理器可以對多個AGV同時進行控制，并能保持實時監(jiān)控和任務的及時分配。這些新興技術已經開始大量應用于AGV控制系統(tǒng)中。今后，隨著視覺SLAM技術的逐漸成熟[11]，以及目前人工智能的推廣與應用，自動掃描環(huán)境障礙物構建可通行路徑將成為未來AGV機器人導航的發(fā)展趨勢。圖1.4AGV在智能停車庫中的應用Fig.1.4ApplicationofAGVinintelligentparkinggarage1.2AGV的國內外發(fā)展現(xiàn)狀現(xiàn)目前，國外的AGV廠商大部分都集中在歐洲和美國，例如美國的NDC公司和德國的Sick公司，NDC開發(fā)的AGV軟件系統(tǒng)在實際運用中已經日趨成熟和完善，而Sick研發(fā)的NAV激光導航系統(tǒng)對AGV行業(yè)的發(fā)展做出了重要的貢獻。在亞洲，日本的發(fā)展較為迅速，比較出名的企業(yè)有川崎重工和住友重機等，這些企業(yè)生產的自動導引車主要以簡易技術型為主[12]，因為其低廉的價格和成本，可以讓其客戶在短時間內就能收回成本，所以這一類AGV公司在臺灣和日本當?shù)胤浅Ｊ軞g迎。與國外歐美等發(fā)達國家有所不同，因為受到了歷史條件的限制，我國對AGV技術的研究起步相對較晚。直到最近20年，隨著國家和社會重視程度的不斷提高，相應關鍵技術才得到快速的發(fā)展。20世紀70年代初，我國第一臺通過電磁技術進行通信的AGV在北京機械研究所被研制了出來[13]。80年代初，北京工業(yè)自動化研究院研制出由汽車發(fā)動機提供動力的AGV，并運用在了倉儲業(yè)中。在90年代末期，清華大學結合EIMS的相關研究，實現(xiàn)了AGV在控制技術方面的突破，20世紀90年代中期，中科院沈陽自動化研究所自主創(chuàng)新研發(fā)的AGV成功的應用在了汽車裝配車間中，從此開啟了AGV產品化的進程[14]。在進入新世紀后，AGV的應用場景已經越來越廣泛，在這個時期得到了突飛猛進的發(fā)展，政府也開始推廣這項技術，不過更多的還是應用在了大型工廠和車間中。隨著技術的進步和發(fā)展，相關領域的公司數(shù)量也在逐年遞增。目前國內比較出名的AGV企業(yè)有佳順智能、沈陽新松等，2013年國內AGV相關企業(yè)達到80～100家，到2016年12月，經過了三年的發(fā)展增加到了250家左[15]。這些企業(yè)主要集中在工業(yè)較為發(fā)達地區(qū)，但是在應用的領域上已經不再僅僅局限于工業(yè)領域了，目前，AGV在服務行業(yè)中也已經占有了一席之地，如醫(yī)療服務、倉儲物流等行業(yè)。圖1.52017年中國移動機器人(AGV)市場份額Fig.1.5ChinaMobileRobot(AGV)MarketSharein2017路徑規(guī)劃問題的研究現(xiàn)狀路徑規(guī)劃在移動機器人領域一直都是備受關注的研究課題，AGV路徑規(guī)劃的概念是指確定了任務的起點與終點后，在未知、已知或動態(tài)變化的環(huán)境中設計出一套合理的行進線路。在將任務分配給AGV小車后，控制系統(tǒng)會根據設定的程序自主為其規(guī)劃出一條路徑最優(yōu)且沒有碰撞的路徑。關于路徑規(guī)劃相關問題，許多專家學者都對其進行了深入的研究。BesantAJ，BesantCB和PREMIK率先提出了無碰撞的AGV路徑規(guī)劃問題[16]。Smolic-Rocak，Nenad和Zdenko提出了基于時間窗的多AGV路徑規(guī)劃[17]，該算法使用時間窗的矢量形式，建立了AGV僅可占據一條邊的規(guī)則，但該算法對路徑的利用率較低，并且不能保證找到的路徑是最優(yōu)的。Oboth通過計算所有的路徑所需要的完成時間提出了一種多AGV的路徑規(guī)劃算法，將所有路徑從大到小進行排列，先規(guī)劃其中一條路徑使其距離最短，然后在此基礎上規(guī)劃第二條路徑，使其與第一條路徑上的AGV不會發(fā)生沖突。Saidi-Mehrabad提出了一種數(shù)學模型，針對多個AGV的車間調度問題和無沖突路徑問題進行研究，該模型通過模擬螞蟻種群信息素的變化過程，提出了一種尋找AGV最優(yōu)路徑的優(yōu)化算法[18]。KimCW基于Dijkstra算法提出了一種可以在雙向流路網中搜索AGV的最優(yōu)路徑的方法，并且該方法會根據AGV的空閑時間窗口列表來規(guī)劃AGV的任務派遣[19]。Dijkstra算法是狄克斯特拉于1959年提出一種最短路徑搜索算法[46]，用于解決圖論中有向加權圖的最短路徑問題，該算法以任務的起點作為中心開始向外進行搜索，找到與起始節(jié)點相鄰且距離最短的節(jié)點，再以此節(jié)點為中心向外擴展，直到找到任務終點位置為止。賀麗娜等將迪科斯徹算法與時間窗方法相結合，并通過對AGV進行排序以確保每輛AGV都在計劃的路徑上行駛[20]。徐曉晴通過人工魚群算法來規(guī)劃出移動機器人的行駛路徑，并使用避碰規(guī)則庫來實現(xiàn)動態(tài)障礙規(guī)避，可以在復雜的動態(tài)環(huán)境中為機器人快速規(guī)劃出安全無沖突的路徑[21]；沈博聞等針對小批量，多品種，多批次，短運輸周期的特點，在A*算法中增加了時間序列，建立了時空圖的三維路徑規(guī)劃[23]。劉國棟提出的兩階段路徑規(guī)劃策略解決了多AGV路徑規(guī)劃問題，將預先生成的一系列可選路徑放入到集合中，然后再對該集合中的路徑進行動態(tài)選擇[24]。馮海雙利用A*算法找到最短路徑的規(guī)劃算法，滿足了環(huán)境對AGV系統(tǒng)性能的一些要求，并通過合理的調度提高了AGV的利用率[24]；羅繼亮提出了一種基于圖論法的AGV路徑規(guī)劃，并預估沖突風險較高區(qū)域內AGV的數(shù)量，通過預先判斷來避免碰撞和死鎖[25]。廖凱文[47]設計了基于A*算法的AGV路徑規(guī)劃方法，并通過綜合AGV在運行、等待、轉彎時所花的時間，以此來對AGV進行時間代價最小的路徑規(guī)劃。張原藝使用改進后的多步長蟻群算法作為全局最優(yōu)路徑的優(yōu)化算法，然后結合滾動窗口方法對路徑進行局部調整以避開障礙物[26]。1.4多AGV系統(tǒng)調度的研究現(xiàn)狀多AGV系統(tǒng)調度是根據實際運行環(huán)境和任務要求制定相應的調度策略。基于調度策略合理分配任務，多AGV系統(tǒng)可以提高整體工作效率并更好地利用資源。隨著自動化的相關關鍵技術不斷完善以及企業(yè)對效率的要求越來越高，智能自動化在運輸方面的應用程度也在隨之提高。對于一個單AGV系統(tǒng)來說，其工作效率是非常有限的，復雜的任務往往需要多個AGV一起完成，這樣才能滿足企業(yè)實際的需求。多個AGV系統(tǒng)具有單個AGV無與倫比的前景和優(yōu)勢。多任務高效率多個AGV能夠按照多個任務的要求分布在工作環(huán)境中，根據任務優(yōu)先級同時完成多個任務，且在同時參與搬運工作的過程中不發(fā)生沖突，這是多AGV系統(tǒng)相比于單AGV的優(yōu)勢，更能體現(xiàn)工作效率。協(xié)同作業(yè)在多AGV系統(tǒng)中，多個AGV小車彼此之間既相互關聯(lián)又相互獨立，可以根據其相互之間的獨立性將復雜的任務分解成若干個子任務讓多個AGV協(xié)同作業(yè)。高容錯率長時間的運行難免導致個別設備發(fā)生故障，當系統(tǒng)中某個AGV在運行過程中發(fā)生故障時，控制系統(tǒng)可以及時地根據各個AGV當前位置重新分配任務，使整個系統(tǒng)可以不停機繼續(xù)運行，提高了系統(tǒng)的魯棒性和容錯率，這樣可以使整個控制系統(tǒng)變得更加可靠。雖然多AGV系統(tǒng)優(yōu)勢明顯，但是隨著同時運行的AGV數(shù)量的增加，也面臨著許多急需要解決的難題：1)多個AGV同時運行時，相互之間應該通過怎樣的方式來傳遞和處理信息。2)通過何種方式使多AGV在運行過程中避免沖突和死鎖的發(fā)生3)如何制定交通規(guī)則讓AGV在十字路口等交匯路段安全高效的通行。多AGV調度規(guī)劃是一個相對比較新的研究領域，國內外的很多專家和學者都對此進行了不同程度的實驗和研究。在多AGV系統(tǒng)中，每個AGV不再是單獨的個體，需要通過調度來規(guī)劃各個AGV完成任務時的運動軌跡，否則實際運行過程中會導致沖突和死鎖的頻繁發(fā)生，并造成系統(tǒng)崩潰，而且通過調度規(guī)劃也能使整個AGV系統(tǒng)的工作效率提高。在多AGV系統(tǒng)調度研究領域中，國外的相關專家和學者在這方面取得了許多的研究成果。NegenbornRudy基于自動集裝箱碼頭的分層控制架構作為研究背景，使用調度模型對AGV的路徑進行規(guī)劃和調度，并通過混合整數(shù)線性規(guī)劃集來規(guī)劃最優(yōu)的無碰撞路徑[27]。Joon-MookL采用了遺傳算法對多AGV任務調度進行規(guī)劃，并對自動化倉儲中的位置進行優(yōu)化和布局設計[28]，遺傳算法通過模擬物種的進化規(guī)律，即優(yōu)勝劣汰原則，逐漸發(fā)展成為隨機搜索算法[48]，其缺點主要在于局部搜索能力較弱、實時性較差。FazlollahtabarH設計了兩階段優(yōu)化過程，提出了轉折點的概念，即基于智能搜索算法獲得初始解，然后通過動態(tài)運動程序跟蹤轉折點處的AGV，并對其實時狀態(tài)進行監(jiān)控，以保證在動態(tài)運行的過程中不會出現(xiàn)碰撞和死鎖[29]。Chow等通過仿真模型和排隊論對任務的關鍵性指標進行賦權，提出了動態(tài)調度過程的綜合評價指標[30]。SpensieriD提出了一種耦合迭代的方法來解決多AGV之間的調度問題，采用一種分支定界的方法來解決廣義最大和最小旅行商問題，并完成了調度的任務排序問題[31]。國內專家學者在多AGV調度領域也取得了很多相關的研究成果，提出了很多成熟有效的方法來提高多AGV任務執(zhí)行過程的效率和調度系統(tǒng)在任務分配過程中的效率。白帥福建立了一種混合區(qū)域控制模型，運用分布式協(xié)調策略解決了多AGV的沖突和死鎖問題[32]。剡昌鋒將改進后的遺傳算法運用在了倉儲物流中，通過在線調度策略有效地改善了AGV的調度效率[33]。張亞琦建立了一種同時考慮計費和運營的集成調度模型，設計出了一種可靠性較高的AGV調度方案[34]。夏田提出一種能夠動態(tài)調整信息素揮發(fā)系數(shù)的改進蟻群算法，通過此算法能夠計算出AGV的最短路徑[35]，基于此算法設計出了比較可靠的AGV調度方案。唐敦兵把AGV的調度任務和激素分泌模型結合在一起，設計出了一種基于神經-內分泌協(xié)調機制，創(chuàng)造性的應用在了多AGV的任務分配與調度中[36]。邊培瑩等人采用粒子群算法來編碼三維向量，提出了一種基于粒子群算法的柔性動態(tài)調度策略[37]，使系統(tǒng)中的