簡易檢索 / 詳目顯示

回結果列表
研究生： 劉展安
Liu, Chang-An
論文名稱： 自動割草機多機覆蓋式路徑規劃之地圖切割與任務分配最佳化研究
Map Partition and Task Allocation Optimization for Multi-Robot Coverage Path Planning of Autonomous Mowers
指導教授： 莊智清
Juang, Jyh-Ching
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2026
畢業學年度： 114
語文別： 英文
論文頁數： 103
中文關鍵詞： 自動割草機 、覆蓋式路徑規劃 、地圖切割 、任務分配最佳化
外文關鍵詞： Autonomous Mower, Coverage Path Planning, Map Partition, Task Allocation Optimization
相關次數： 點閱：11  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 隨著科技的日新月異，自動割草機已經逐漸取代傳統割草機並成為一種發展趨勢。在自動割草機系統中，路徑規劃和路徑完整覆蓋性是極為關鍵的技術。為了提升整體割草效率並且減少時間的浪費，使用多台割草機同時執行割草任務就可以達到這個目的。然而如何讓多台割草機去完美的分配任務達到任務量相同並且將分配之區域完整的覆蓋就會是一個非常重要的議題。
    有鑑於此，本研究提出了一種地圖切割及任務分配方法，這一方法融合了全球衛星導航系統（GNSS）、慣性量測單元（IMU）來得到割草機的位置及進行地圖製作，並對傳統的K-means分群演算法進行了改進。本研究使用GNSS和IMU收集的數據來建立一個二維點地圖，透過改進的K-means演算法將收集到的地圖依據割草機的數量進行切割，考量割草機的移動距離、轉彎次數、工作量平衡及覆蓋路徑距離作為成本函數，透過降低成本函數來得到最優的路徑切割及任務分配的方式。本方法特別使用類似3D列印(slic3r)來回移動的路徑規劃來進行路徑切割的最佳化評估，slic3r路徑規劃主要是扣除掉外圍區域讓中間要割草的區域使用同方向來回行走的方式進行規劃，透過加入slic3r中實際規劃出來的路徑以及轉彎次數來估算實際完成割草任務的時間是多少，從而最佳化地圖切割使工作效率提升。
    本方法特別適用於實際運作的割草機並且應用在相對比較平緩的割草區域，為了提升整體的割草效率因此把整個割草機的動態納入考量並且評估他們動態的資訊，透過多次重複的評估及修正，提供割草機的使用者即使在一個未知的區域之下只需要進行一次地圖的錄製就可以進行割草任務的分配並且能達到幾乎相同的完成時間。
    綜合以上所述，本研究創新之處在於將實際的路徑規劃納入地圖切割以及任務分 配的過程中而非單純以距離遠近或是面積大小相同作為地圖切割及任務分配的依據。透過模擬的方式得到任務分配後透過實際割草機運行模擬出來的任務分配，將模擬及實際運行的狀況做一個詳細的比較並在後續作更精細的修正及調整。未來如果要應用到更複雜的環境也可以以此方法為基礎，擴展自動割草機可以應用的環境。

    With the continuing advancement of autonomous mobile technologies, autonomous mowers have emerged as a practical alternative to conventional mowing equipments. In autonomous mowing systems, path planning and coverage path planning are essential functions for ensuring complete, efficient, and reliable operations. For large or geometrically complex mowing areas, deploying multiple mowers can reduce the total operation time. However, effective multi-mower operation requires the workload to be distributed evenly so that all mowers can complete their assigned tasks within similar time periods.
    To address this issue, this thesis proposes a map partitioning and task allocation method for multi-mower coverage path planning. The proposed system uses Global Navigation Satellite System (GNSS) and Inertial Measurement Unit (IMU) data to estimate mower position and record the working environment. The recorded position data are converted into a two-dimensional point map, and an improved K-means-based partitioning method is used for map partitioning and task allocation. To this end, the cost function incorporates movement distance, turning count, workload balance, and coverage path distance, allowing the final partition and task allocation to be determined through cost minimization. A key feature of the proposed method is the application of Slic3r-based coverage path planning as an evaluation mechanism for partition optimization. The Slic3r planner generates back-and-forth mowing paths with a 0.13 m spacing between adjacent paths. By evaluating the actual generated paths and turning motions, the proposed method estimates the real workload of each mower and refines the task allocation accordingly.
    The proposed method is designed for autonomous mower operation in relatively flat mowing environments. For each partition, the centroid is first identified and the corresponding coverage path is generated using Slic3r. The generated path is then used to evaluate the mowing workload, after which the centroid is adjusted to produce an updated partition. Through repeated centroid adjustment, the method gradually converges toward a workload-balanced map partition and task allocation. As a result, the mowing area can be recorded once and then divided into regions that allow multiple mowers to complete their missions at approximately the same time.
    Overall, this thesis presents a planner-aware approach to map partitioning and task allocation for multiple autonomous mowers. Unlike methods that rely only on geometric distance, partition area, or region shape, the proposed method evaluates workload using actual Slic3r-generated coverage paths. The simulation results are compared with real mowing experiments, enabling the gap between simulated workload estimation and real-world execution to be analyzed. This analysis provides a basis for refining the workload model and extending the method to more complex operating conditions.

    摘要 I Abstract III Acknowledgments VI Contents VII List of Figures X List of Tables XII List of Abbreviations XIII Chapter 1 Introduction 1 1.1 Motivation and Objectives 1 1.2 Literature Review 3 1.3 Contributions 6 1.4 Thesis Overview 7 Chapter 2 System Overview and Data Analysis 9 2.1 System Overview 9 2.2 System Data Flow 12 2.3 Data Analysis 13 2.3.1 Total Workload Evaluation 13 2.3.2 Total Objective Evaluation 14 Chapter 3 Mapping and Coverage Path Planning 16 3.1 Architecture of Mapping 16 3.2 Coordinate system 18 3.3 Coverage Path Planning 19 3.3.1 Objective of Coverage Path Planning 19 3.3.2 Boundary Path Generation 20 3.3.3 Fill Path Generation 21 3.3.4 Obstacle Handling in Coverage Planning 24 3.3.5 Connector Path Planning 25 3.3.6 Path Segmentation 27 3.4 Summary 29 Chapter 4 Map Partition and Task Allocation 31 4.1 Initial Partition Using Coverage-Weighted K-means 32 4.1.1 Coverage Weight Definition and Estimation 34 4.1.2 Weighted K-means Initialization and Objective 35 4.1.3 Cost-aware Tile Assignment and Initial Region Generation 37 4.2 Centroid Feedback for Coarse Adjustment 38 4.2.1 Slic3r-in-the-loop Workload Evaluation 40 4.2.2 Workload Imbalance and Pairwise Geometric Feedback 41 4.2.3 Effect on Overloaded and Underloaded Robots 42 4.2.4 Centroid Update Strategy and Stopping Criteria 43 4.3 Cut-line Refinement for Fine Adjustment 44 4.3.1 Workload Evaluation Using Slic3r-in-the-Loop 46 4.3.2 Straight Cut-Line Approximation of the Shared Boundary 47 4.3.3 Cut-Line Shifting and Region Reassignment 50 4.3.4 Binary Search for Best Cut-Line Refinement Candidate 51 4.3.5 Relay Refinement for Non-Adjacent Workload Balancing 53 4.4 Summary 54 Chapter 5 System Implementation and Experiments 56 5.1 Real Mower 56 5.1.1 Hardware Architecture 57 5.1.2 Software Architecture 60 5.1.3 ROS and Rviz 61 5.2 Experiment Scenario 64 5.2.1 Scenario 1: Only Mowing Area 65 5.2.2 Scenario 2: Mowing Area with an Internal Obstacle 65 5.2.3 Scenario 3: Mowing Area with a Complicated Internal Obstacle 66 5.3 Evaluation 67 5.3.1 Simulation Result 67 5.3.2 Comparison of Proposed Method and Existing Map Partitioning Methods 77 5.3.3 Real Mower Field Experiment Result 79 5.4 Discussion 81 Chapter 6 Conclusions and Future Work 83 6.1 Conclusions 83 6.2 Future Work 84 Reference 86

    [1] C. S. Tan, R. Mohd-Mokhtar, and M. R. Arshad, “A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms,” IEEE Access, vol. 9, pp. 119310–119342, 2021.
    [2] E. Galceran and M. Carreras, “A survey on coverage path planning for robotics,” Robot. Auton. Syst., vol. 61, no. 12, pp. 1258–1276, 2013.
    [3] H. Choset, “Coverage for robotics: A survey of recent results,” Ann. Math. Artif. Intell., vol. 31, pp. 113–126, 2001.
    [4] H. Choset and P. Pignon, “Coverage path planning: The boustrophedon cellular decomposition,” in Field and Service Robotics, A. Zelinsky, Ed. London, U.K.: Springer, 1998, pp. 203–209, doi: 10.1007/978-1-4471-1273-0_32.
    [5] H. Choset, “Coverage of known spaces: The boustrophedon cellular decomposition,” Auton. Robots, vol. 9, no. 3, pp. 247–253, 2000, doi: 10.1023/A:1008958800904.
    [6] E. U. Acar, H. Choset, A. A. Rizzi, P. N. Atkar, and D. Hull, “Morse decompositions for coverage tasks,” Int. J. Robot. Res., vol. 21, no. 4, pp. 331–344, 2002.
    [7] J. Ni, Y. Gu, G. Tang, C. Ke, and Y. Gu, “Cooperative coverage path planning for multi-mobile robots based on improved K-means clustering and deep reinforcement learning,” Electronics, vol. 13, no. 5, Art. no. 944, 2024.
    [8] F. Zhang, J. Chen, and H. Ren, “Path planning and task allocation based on community detection in Voronoi diagrams,” Inf. Sci., vol. 733, Art. no. 122991, 2026.
    [9] A. C. Kapoutsis, S. A. Chatzichristofis, and E. B. Kosmatopoulos, “DARP: Divide areas algorithm for optimal multi-robot coverage path planning,” J. Intell. Robot. Syst., vol. 86, pp. 663–680, 2017.
    [10] J. P. Carvalho and A. P. Aguiar, “Multi-agent reinforcement learning for zero-shot coverage path planning with dynamic UAV networks,” Robot. Auton. Syst., vol. 195, Art. no. 105163, 2026, doi: 10.1016/j.robot.2025.105163.
    [11] J. Gong, H. Kim, and S. Lee, “Resilient multi-robot coverage path redistribution using boustrophedon decomposition for environmental monitoring,” Sensors, vol. 24, no. 23, Art. no. 7482, 2024.
    [12] I. M. Rekleitis, A. P. New, E. S. Rankin, and H. Choset, “Efficient boustrophedon multi-robot coverage: An algorithmic approach,” Ann. Math. Artif. Intell., vol. 52, pp. 109–142, 2008.
    [13] J. Tang, C. Sun, and X. Zhang, “MSTC*: Multi-robot coverage path planning under physical constraints,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), 2021, pp. 2518–2524, doi: 10.1109/ICRA48506.2021.9561371.
    [14] I. Vandermeulen, R. Groß, and A. Kolling, “Turn-minimizing multirobot coverage,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), 2019, pp. 1014–1020.
    [15] S. Agarwal and S. Akella, “Area coverage with multiple capacity-constrained robots,” IEEE Robot. Autom. Lett., vol. 7, no. 2, pp. 3734–3741, 2022.
    [16] T. Oksanen and A. Visala, “Coverage path planning algorithms for agricultural field machines,” J. Field Robot., vol. 26, no. 8, pp. 651–668, 2009.
    [17] G. Mier, J. Valente, and S. de Bruin, “Fields2Cover: An open-source coverage path planning library for unmanned agricultural vehicles,” IEEE Robot. Autom. Lett., vol. 8, no. 4, pp. 2166–2172, 2023.
    [18] I. A. Hameed, D. Bochtis, and C. A. Sørensen, “An optimized field coverage planning approach for navigation of agricultural robots in fields involving obstacle areas,” Int. J. Adv. Robot. Syst., vol. 10, no. 5, 2013
    [19] K.-C. Huang, F.-L. Lian, C.-T. Chen, C.-H. Wu, and C.-C. Chen, “A novel solution with rapid Voronoi-based coverage path planning in irregular environment for robotic mowing systems,” Int. J. Intell. Robot. Appl., vol. 5, pp. 558–575, 2021.
    [20] M. Höffmann, J. Clemens, and D. Stronzek-Pfeifer, “Coverage path planning and precise localization for autonomous lawn mowers,” in Proc. 6th IEEE Int. Conf. Robot. Comput. (IRC), 2022, pp. 238–242.
    [21] A. Šelek, M. Seder, M. Brezak, and I. Petrović, “Smooth complete coverage trajectory planning algorithm for nonholonomic mobile robots,” Sensors, vol. 22, no. 23, Art. no. 9269, 2022.
    [22] R. Bähnemann, N. Lawrance, J. J. Chung, M. Pantic, R. Siegwart, and J. Nieto, “Revisiting boustrophedon coverage path planning as a generalized traveling salesman problem,” in Field and Service Robotics, G. Ishigami and K. Yoshida, Eds., ser. Springer Proc. Adv. Robot., vol. 16. Cham, Switzerland: Springer, 2021, pp. 277–290.
    [23] I. A. Hameed, “Coverage path planning software for autonomous robotic lawn mower using Dubins’ curve,” in Proc. IEEE Int. Conf. Real-Time Comput. Robot. (RCAR), 2017, pp. 517–522.
    [24] OpenMower, “OpenMower documentation.” [Online]. Available: https://openmower.de/latest/docs/. [Accessed: Jul. 3, 2026].

    下載圖示
    校外：立即公開
    QR CODE