本論文介紹了三種基於優先權機制之多機器人路徑規劃演算法，使多個機器人能夠在大型平面空間中從初始點移動到目標點，並有效地避免與任何靜態及動態障礙物碰撞。本論文所提出的演算法都是基於廣義沃羅諾伊圖（GVD, generalized Voronoi diagram）來初步劃分不同優先權機器人的各自地圖。機器人的優先權順序是由用戶根據機器人任務的重要程度分配，目標是期望機器人均同樣的移動速度的條件下，使高優先級機器人能以比低優先級機器人有更短的移動距離和更早的目標點抵達順序。 在第三章中，我們提出了路徑優先導航策略（NSPP, navigation strategy with path-priority）的新方法。該方法確保了從起點到目標點中高路徑優先級機器人的移動距離比低路徑優先級機器人移動的距離更短。然而，並不能保證在任何場景中機器人的抵達順序與路徑優先順序一致。第四章則根據機器人任務的重要性給每個機器人分配優先級編號。在第四章中我們提出了從NSPP衍生出來的增強方法名為優先順序導航演算法（PONA, priority order navigation algorithm）。在PONA中不僅保留了NSPP的優點，即高優先權機器人具有較短的移動距離之外，還新增了一個路徑切換機制來允許低優先級機器人在兩條路徑之間切換，從而防止阻擋到高優先級機器人的移動路徑。在我們的實驗場景為環形場景時，總機器人數量少於五個的時候，高優先權機器人比低優先權機器人更快到達目標點的可能性大幅提升。第五章提出了進化型優先順序導航演算法（PONA2.0, improved priority order navigation algorithm）的方法，該方法是從PONA衍生而來。PONA 2.0增強了PONA的路徑切換機制，並採用根據機器人同時出現在地圖中的數量來決定低優先權機器人可用的路徑數量的方法。這樣修改使得實驗場景為環形場景時，即使機器人數量超過四個，PONA 2.0也能夠使高優先級機器人比低優先級機器人更早的到達目標。 在模擬結果中，所提出的演算法在平均軌跡長度優於所比較的其他方法，如互相定位演算法（ROA, reciprocal orientation algorithm）和最短距離演算法（SDA, shortest distance algorithm）。此外，PONA和PONA 2.0相比於NSPP，在抵達目標點的順序幾乎與機器人的優先順序一致。 ;This dissertation introduces three efficient algorithms for the navigation of multi-robot with priority by which the multiple robots can move from their initial points to the target points in a large flat space without colliding with any static and/or dynamic obstacles efficiently. The proposed algorithms are based on the generalized Voronoi diagram (GVD) which is used to divide the map for different priority order of robots. The priority order of robots is assigned by the user based on the importance degree of the robots’ tasks, and all robots have the same speed. The objective is to make the higher-priority robot reach its target with a shorter moving distance and faster than the lower priority robot. In Chapter 3, we propose a new methodology called the navigation strategy with path-priority (NSPP). This methodology ensures that high path-priority robots have a shorter moving distance from the starting point to the target point compared to low path-priority robots. However, it does not guarantee that the robot’s arrival order is in line with the path-priority order in any scenario. Chapter 4 gives each robot priority number depending on its task importance. Then we introduce an enhanced methodology derived from NSPP called the priority order navigation algorithm (PONA). When the test is in the circle scenario, PONA not only keeps the advantages of NSPP that high-priority robots have shorter moving distances, but also offers significant improvements over NSPP by incorporating a feature that allows low-priority robots to switch between two paths to prevent blocking high-priority robots, so that the possibility of high-priority robots reaching the target faster than low-priority robots is increased when the number of robots is fewer than five. Chapter 5 introduces an advanced methodology (PONA 2.0) derived from PONA called the improved priority order navigation algorithm. PONA2.0 enhances the original path switching mechanism of PONA and introduces the capability to select a variable number of paths based on the number of robots involved. This modification empowers PONA2.0 to enable high-priority robots to reach their targets faster than low-priority robots, even if there are more than four robots when the test is in the circle scenario. In the simulation results, the proposed algorithms outperform benchmark methods such as the reciprocal orientation algorithm (ROA) and shortest distance algorithm (SDA) regarding the average trajectories length. Further, PONA and PONA2.0 present the improvement of that the arrival order is almost in line with the priority order of all robots.
