基於時間窗協合路徑規劃之多移動機器人調度與任務運行

摘要：本文提出一種基於時間窗路徑規劃之多自主移動機器人調度的方法，包含移載機器人選派、時間窗多機協合路徑規劃和多機協合路徑之任務運行等技術。首先，我們分析了現有的相關文獻，指出多移動機器人時間窗調度策略在提高運輸效率和避免阻塞方面的優勢。接著，我們討論了移載機器人選派的重要性，並介紹了如何利用時間窗技術來合理分配任務和調度機器人的運行時序。此外，我們還探討了時間窗多機協合路徑規劃的挑戰，並提出了一些解決方案，包括考慮機器人之間的會機衝突和最小化整體行程代價等。最後，我們討論了時間窗技術於多機實際協合運載中的應用，並以模擬結果佐證提出方法之有效性。

Abstract：This article presents a multi-mobile robot scheduling method, which includes techniques such as robot assignment, time window based on multi-mobile robot cooperative path planning, and multi-robot cooperative task execution. Firstly, we analyze existing relevant literature and point out the advantages of multi-robot time window scheduling strategies in improving transportation efficiency and avoiding congestion. Next, we discuss the importance of robot assignment and introduce how to use time window techniques to allocate tasks and schedule the operation time of robots effectively. Additionally, we explore the challenges of time window-based multi-robot cooperative path planning and propose some solutions, including considering robot collisions and minimizing the overall travel cost. Finally, we discuss the practical application of time window techniques in multi-robot cooperative operations and provide simulation results to demonstrate the effectiveness of the proposed method.

關鍵詞：多移動機器人調度、時間窗、協合路徑規劃
Keywords：Scheduling of multi-mobile robot, Time windows, Cooperative path planning

前言

近年來，隨著自主移動機器人技術的快速發展，多移動機器人系統在各個領域中的應用越來越廣泛，例如物流倉儲、半導體與製造業等。在這些應用中，為確保交通順暢並高效的作業，有效的分派並協調多台移動機器人運行任務至關重要。然而，當系統的移動機器人數量增加時，調度和協調的複雜性也隨之增加。關鍵在於如何合理地分配運載任務給每一台機器人，並作好多機協調以降低機器人彼此間的衝突，進而避免交通死鎖(Deadlock)的情況，在滿足平均週期運載量前提下最大化整體搬運效率。

多移動機器人管理系統架構

一般多移動機器人管理系統可分為中央式管理(Centralized)與分散式管理(Decentralized)[1][2]，中央式管理優點是架構單純，建置較為容易；缺點是移動機器人的資訊交握都需透過中央控制器橋接，且移動機器人的分派、路徑規劃等程序都需先透過中央控制器演算，再傳輸給移動機器人任務命令與對應之運行路徑。故當機器人數量提高時，中央控制器(Control system)易因演算量過大而導致系統延遲，甚而造成系統困境的情形。而分散式管理的優點即能有效解決前述中央式管理造成之系統延遲問題。因每台移動機器人與中央控制器都是獨立個體(Agent)，彼此間可自行互傳資訊[3][4]，且中央控制器除進行分派任務演算外，其運行之路徑規劃將由移動機器人收到中央控制器下達的分派任務後自行演算，這種透過每個Agents都分擔系統計畫量的分散式架構可大大降低中央控制器運算負載，但此架構的缺點即是相對複雜，建置與維護成本較高昂。
本研究採用分散式管理的架構，如圖1所示，包含路徑伺服器(Path server)、中央控制器與移動機器人。並於此三者間建立多機通訊系統(Multi-agent communication system)[5][6]。且所有Agents都將建置場域地圖、多移動機器人調度分派程序、多移動機器人協合路徑規劃與多移動機器人協合路徑之任務運行等演算法，其中調度分派與協合路徑之任務運行都是基於多移動機器人協合路徑規劃演算的延伸應用。其控制演算架構如圖2所示。主要是以執行任務的順序進行開發，當多移動機器人管理系統接收到現場執行系統(MES)下達的任務命令時，第一步是選擇合適的機器人去執行此任務，哪一台移動機器人是最為適切的選擇將於多移動機器人調度分派章節詳細說明，接著便是進行多移動機器人時間窗協合路徑規劃，該運算方法是於最短路徑Dijkstra演算法[7]中導入時間窗技術，藉此優化多移動機器人運行路徑，以降低會機衝突提升運載效率。設計細節將於多移動機器人時間窗協合路徑規劃章節說明。最後多移動機器人會依規劃之協合路徑執行任務運行，實際運行時發生的會機衝突(Conflict)或會機碰撞(Collision)問題[8]的因應方式將於多移動機器人協合路徑之任務運行章節詳盡說明。

                                                        圖1 多移動機器人管理系統分散式架構

                                                      圖2 多移動機器人管理系統控制演算架構

多移動機器人時間窗協合路徑規劃

1. 最短路徑演算法
由於本研究提出之多移動機器人時間窗協合路徑規劃演算法是由Dijkstra演算法優化而成，故本節中將先介紹Dijkstra演算法原理。Dijkstra演算法可以保證於場域地圖中求出某一節點到其他任一節點的最短路徑。目前最常用的A*演算法[9]也是由Dijkstra演算法衍生而來。Dijkstra 演算法的主要特點是以起始點為中心向外一層一層擴展，把每段路徑都納入比對表評比，直到擴展到目標點為止。故Dijkstra 演算法能夠保證求得最短路徑。Dijkstra 演算法一般對於行走節點代價(cost)的紀錄分析有兩種方式，一種用永久和臨時標號方式，一種是使用Open與Close之關聯節點表的方式，本研究將採用後者進行開發。