基於優先權機制之多機器人路徑規劃

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：21

、訪客IP：18.216.174.32

姓名

黃聖凱(Sheng-Kai Huang) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

基於優先權機制之多機器人路徑規劃
(Multi-robot path planning based on priority mechanism)

相關論文

★ 直接甲醇燃料電池混合供電系統之控制研究	★ 利用折射率檢測法在水耕植物之水質檢測研究
★ DSP主控之模型車自動導控系統	★ 旋轉式倒單擺動作控制之再設計
★ 高速公路上下匝道燈號之模糊控制決策	★ 模糊集合之模糊度探討
★ 雙質量彈簧連結系統運動控制性能之再改良	★ 桌上曲棍球之影像視覺系統
★ 桌上曲棍球之機器人攻防控制	★ 模型直昇機姿態控制
★ 模糊控制系統的穩定性分析及設計	★ 門禁監控即時辨識系統
★ 桌上曲棍球：人與機械手對打	★ 麻將牌辨識系統
★ 相關誤差神經網路之應用於輻射量測植被和土壤含水量	★ 三節式機器人之站立控制

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本論文介紹了三種基於優先權機制之多機器人路徑規劃演算法，使多個機器人能夠在大型平面空間中從初始點移動到目標點，並有效地避免與任何靜態及動態障礙物碰撞。本論文所提出的演算法都是基於廣義沃羅諾伊圖（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.

關鍵字(中)

★ 沃羅諾伊圖
★ 戴克斯特拉演算法
★ Yen’s演算法
★ 多機器人路徑規劃
★ 無碰撞
★ 優先權

關鍵字(英)

★ Voronoi diagram
★ Dijkstra algorithm
★ Yen′s algorithm
★ multi-robot path planning
★ collision-free
★ priority order

論文目次

摘要 i
Abstract iii
Contents v
Acronyms vii
List of Figures viii
List of Tables xiii
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Organization of the Dissertation 5
Chapter 2 Preliminary Background 7
2.1 Generalized Voronoi Diagram Generation 7
2.1.1 Data Pre-processing 7
2.1.2 Generalized Voronoi Diagram 8
2.2 The Calculation for a Robot Direction 13
Chapter 3 Navigation Strategy with Path-priority (NSPP) 17
3.1 Path Planning 17
3.2 Collision Prevention 20
3.3 Simulation and Comparison 22
3.3.1 The Simulation Results 22
3.3.2 The Comparison Results 28
3.4 Conclusions 32
Chapter 4 Priority Order Navigation Algorithm (PONA) 34
4.1 Path Planning 34
4.1.1 Shorten the Feasible Paths 34
4.1.2 Switch Between Two Feasible Modified Paths 38
4.2 Collision Prevention 43
4.3 Simulation and Comparison 47
4.3.1 The Simulation Results 47
4.3.2 The Comparison Results 50
4.4 Conclusions 56
Chapter 5 Improved Priority Order Navigation Algorithm (PONA2.0) 57
5.1 Adjustable Multipath Switching Mechanism 57
5.2 Simulation and Comparison 62
5.2.1 The Simulation Results 62
5.2.2 The Comparison Results in Arrival Order 66
5.2.3 The Comparison Results in Average Length 70
5.2.4 The Comparison Results of Time Consumption 73
5.3 Conclusions 75
Chapter 6 Conclusions and Future Works 77
References 79
Publication List 83

參考文獻

[1] S. Wang, J. Wan, D. Li, and C. Zhang, "Implementing smart factory of industrie 4.0: an outlook," International Journal of Distributed Sensor Networks, vol. 12, no. 1, pp. 1–10, 2016.
[2] M. J. Matarić, G. S. Sukhatme, and E. H. Østergaard, "Multi-robot task allocation in uncertain environments," Autonomous Robots, vol. 14, no. 2, pp. 255–263, 2003.
[3] L. E. Kavraki, P. Svestka, J. Latombe, and M. H. Overmars, "Probabilistic roadmaps for path planning in high-dimensional configuration spaces," IEEE Transactions on Robotics and Automation, vol. 12, no. 4, pp. 566–580, 1996.
[4] F. Belkhouche, "Reactive path planning in a dynamic environment," IEEE Transactions on Robotics, vol. 25, no. 4, pp. 902–911, 2009.
[5] J. S. Bellingham, M. Tillerson, M. Alighanbari, and J. P. How, "Cooperative path planning for multiple UAVs in dynamic and uncertain environments," in 41st IEEE Conference on Decision and Control, 2002, vol. 3, pp. 2816–2822.
[6] Y. Guo and L. E. Parker, "A distributed and optimal motion planning approach for multiple mobile robots," in 2002 IEEE International Conference on Robotics and Automation, 2002, vol. 3, pp. 2612–2619.
[7] D. Keymeulen and J. Decuyper, "The fluid dynamics applied to mobile robot motion: the stream field method," in 1994 IEEE International Conference on Robotics and Automation, 1994, vol. 1, pp. 378–385.
[8] P. Das, S. Pradhan, S. Patro, and B. Balabantaray, "Artificial immune system based path planning of mobile robot," in Soft Computing Techniques in Vision Science, vol. 395: Springer, 2012, pp. 195–207.
[9] S. S. Ge and Y. J. Cui, "Dynamic motion planning for mobile robots using potential field method," Autonomous robots, vol. 13, no. 3, pp. 207–222, 2002.
[10] S. G. Cui, H. Wang, and L. Yang, "A simulation study of A-star algorithm for robot path planning," in 16th international conference on mechatronics technology, 2012, pp. 506–509.
[11] P. Bhattacharya and M. L. Gavrilova, "Roadmap-based path planning - using the Voronoi diagram for a clearance-based shortest path," IEEE Robotics & Automation Magazine, vol. 15, no. 2, pp. 58–66, 2008.
[12] H. Imai, M. Iri, and K. Murota, "Voronoi diagram in the laguerre geometry and its applications," SIAM Journal on Computing, vol. 14, no. 1, pp. 93–105, 1985.
[13] F. Duchoň et al., "Path planning with modified a star algorithm for a mobile robot," Procedia Engineering, vol. 96, pp. 59–69, 2014.
[14] M. Elhoseny, A. Tharwat, and A. E. Hassanien, "Bezier curve based path planning in a dynamic field using modified genetic algorithm," Journal of Computational Science, vol. 25, pp. 339–350, 2018.
[15] P. K. Das, H. S. Behera, P. K. Jena, and B. K. Panigrahi, "Multi-robot path planning in a dynamic environment using improved gravitational search algorithm," Journal of Electrical Systems and Information Technology, vol. 3, no. 2, pp. 295–313, 2016.
[16] G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, "Conflict-based search for optimal multi-agent pathfinding," Artificial Intelligence, vol. 219, pp. 40–66, 2015.
[17] P. K. Das, H. S. Behera, and B. K. Panigrahi, "A hybridization of an improved particle swarm optimization and gravitational search algorithm for multi-robot path planning," Swarm and Evolutionary Computation, vol. 28, pp. 14–28, 2016.
[18] C. Huang, X. Chen, Y. Zhang, S. Qin, Y. Zeng, and X. Li, "Hierarchical model predictive control for multi-robot navigation," in International Joint Conference on Artificial Intelligence, New York City, 2016, pp. 3140–3146.
[19] C. Huang, X. Chen, Y. Zhang, S. Qin, Y. Zeng, and X. Li, "Switched linear multi-robot navigation using hierarchical model predictive control," in Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017, pp. 4331–4337.
[20] J. Alonso-Mora, S. Baker, and D. Rus, "Multi-robot navigation in formation via sequential convex programming," in 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2015, pp. 4634–4641.
[21] A. A. Ali, A. T. Rashid, M. Frasca, and L. Fortuna, "An algorithm for multi-robot collision-free navigation based on shortest distance," Robotics and Autonomous Systems, vol. 75, pp. 119–128, 2016.
[22] D. C. Guastella, L. Cantelli, D. Longo, C. D. Melita, and G. Muscato, "Coverage path planning for a flock of aerial vehicles to support autonomous rovers through traversability analysis," ACTA IMEKO, vol. 8, no. 4, pp. 9–12, 2019.
[23] J. Zoto, M. A. Musci, A. Khaliq, M. Chiaberge, and I. Aicardi, "Automatic path planning for unmanned ground vehicle using uav imagery," in International Conference on Robotics in Alpe-Adria Danube Region, 2019: Springer, pp. 223–230.
[24] Z. Gabbassova, D. Sedighizadeh, A. Sheikhi Fini, and M. Seddighizadeh, "Multiple robot motion planning considering shortest and safest trajectory," Electromechanical Energy Conversion Systems, vol. 1, no. 3, pp. 1–6, 2019.
[25] J. Kim and H. I. Son, "A Voronoi diagram-based workspace partition for weak cooperation of multi-robot system in orchard," IEEE Access, vol. 8, pp. 20676–20686, 2020.
[26] N. Ben Slimane and M. Tagina, "Proposition of a distributed Voronoi partitioning approach enhanced with a dispersion phase for a multirobot system," International Journal of Social Robotics, vol. 13, no. 5, pp. 887–898, 2021.
[27] D. T. Lee and R. L. D. III, "Generalized Voronoi diagrams in the plain," SIAM J. Comput, vol. 10, 1, pp. 73–87, 1981.
[28] J. Wang and M. Q. H. Meng, "Optimal path planning using generalized Voronoi graph and multiple potential functions," IEEE Transactions on Industrial Electronics, vol. 67, no. 12, pp. 10621–10630, 2020.
[29] W. Chi, Z. Ding, J. Wang, G. Chen, and L. Sun, "A generalized Voronoi diagram based efficient heuristic path planning method for RRTs in mobile robots," IEEE Transactions on Industrial Electronics, pp. 1–1, 2021.
[30] D. Chandrasekhar Rao, M. R. Kabat, P. K. Das, and P. K. Jena, "Cooperative navigation planning of multiple mobile robots using improved krill herd," Arabian Journal for Science and Engineering, Article vol. 43, no. 12, pp. 7869–7891, 2018.
[31] M. Bennewitz, W. Burgard, and S. Thrun, "Optimizing schedules for prioritized path planning of multi-robot systems," in Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation, 2001, vol. 1, pp. 271–276.
[32] R. Regele and P. Levi, "Cooperative multi-robot path planning by heuristic priority adjustment," in 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2006, pp. 5954–5959.
[33] W. Wu, S. Bhattacharya, and A. Prorok, "Multi-Robot path deconfliction through prioritization by path prospects," in 2020 IEEE International Conference on Robotics and Automation, 2020, pp. 9809–9815.
[34] R. K. Dewangan, A. Shukla, and W. W. Godfrey, "A solution for priority-based multi-robot path planning problem with obstacles using ant lion optimization," Modern Physics Letters B, vol. 34, no. 13, p. 2050137, 2020.
[35] W. Yu, J. Peng, and X. Zhang, "A prioritized path planning algorithm for MMRS," in Proceedings of the 33rd Chinese Control Conference, China, 2014, pp. 966–971.
[36] M. Čáp, P. Novák, A. Kleiner, and M. Selecký, "Prioritized planning algorithms for trajectory coordination of multiple mobile robots," IEEE Transactions on Automation Science and Engineering, vol. 12, no. 3, pp. 835–849, 2015.
[37] C. Riman and P. E. Abi-Char, "A priority-based modified A∗ path planning algorithm for multi-mobile robot navigation," in 19th International Conference on Electrical Engineering, Computing Science and Automatic Control, Mexico, 2022, pp. 1–6.
[38] A. Andreychuk and K. Yakovlev, "Two techniques that enhance the performance of multi-robot prioritized path planning," in International Joint Conference on Autonomous Agents and Multi-agent Systems, Sweden, 2018, pp. 2177–2179.
[39] S. K. Huang and W. J. Wang, "An evolutionary navigation algorithm for multi-robot with priority order," IEEE Access, vol. 11, pp. 45222–45232, 2023.
[40] S. K. Huang, W. J. Wang, and C. H. Sun, "A new multirobot path planning with priority order based on the generalized Voronoi diagram," IEEE Access, vol. 10, pp. 56564–56577, 2022.
[41] S.-K. Huang, W.-J. Wang, and C.-H. Sun, "A path planning strategy for multi-robot moving with path-priority order based on a generalized Voronoi diagram," Applied Sciences, vol. 11, no. 20, p. 9650, 2021.
[42] R. Siegwart, I. R. Nourbakhsh, and D. Scaramuzza, Introduction to autonomous mobile robots, second edition. Cambridge, Massachusetts: MIT Press, 2011.
[43] C.-H. Sun, Y.-J. Chen, Y.-T. Wang, and S.-K. Huang, "Sequentially switched fuzzy-model-based control for wheeled mobile robot with visual odometry," Applied Mathematical Modelling, vol. 47, pp. 765–776, 2017.
[44] D. Coleman, "Lee’s O (n2 log n) visibility graph algorithm implementation and analysis," ed: Rapport. Department of Computer Science, University of Colorado at Boulder, 2012.
[45] S. Fortune, "A sweepline algorithm for Voronoi diagrams," Algorithmica, vol. 2, no. 1, pp. 153–174, 1987.
[46] J. Y. Yen, "An algorithm for finding shortest routes from all source nodes to a given destination in general networks," Quarterly of Applied Mathematics, vol. 27, no. 4, pp. 526–530, 1970.

指導教授

王文俊(Wen-June Wang)

審核日期

2023-7-25

推文