請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/92617
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 詹魁元 | zh_TW |
dc.contributor.advisor | Kuei-Yuan Chan | en |
dc.contributor.author | 李冠賢 | zh_TW |
dc.contributor.author | Kuan-Hsien Lee | en |
dc.date.accessioned | 2024-05-14T16:05:12Z | - |
dc.date.available | 2024-05-15 | - |
dc.date.copyright | 2024-05-14 | - |
dc.date.issued | 2024 | - |
dc.date.submitted | 2024-03-06 | - |
dc.identifier.citation | [1] R. N. Darmanin and M. K. Bugeja, “A review on multi-robot systems categorised by application domain,” in 2017 25th mediterranean conference on control and automation (MED), pp. 701–706, IEEE, 2017.
[2] C. Kunz, C. Murphy, R. Camilli, H. Singh, J. Bailey, R. Eustice, M. Jakuba, K.-i. Nakamura, C. Roman, T. Sato, et al., “Deep sea underwater robotic exploration in the ice-covered arctic ocean with auvs,” in 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3654–3660, IEEE, 2008. [3] P.Petráček,V.Krátkỳ,M.Petrlík,T.Báča,R.Kratochvíl,andM.Saska,“Large-scale exploration of cave environments by unmanned aerial vehicles,” IEEE Robotics and Automation Letters, vol. 6, no. 4, pp. 7596–7603, 2021. [4] C.Fu,G.Chen,B.Cheng,andY.Chung,“Tsmc develops the world’s first automated handling system for wafer warehouses effectively reducing 95% manual handling weight.” [5] D.B.Poudel,“Coordinating hundreds of cooperative, autonomous robots in a warehouse,” Jan, vol. 27, no. 1-13, p. 26, 2013. [6] E. Tuci, M. H. Alkilabi, and O. Akanyeti, “Cooperative object transport in multi-robot systems: A review of the state-of-the-art,” Frontiers in Robotics and AI, vol. 5, p. 59, 2018. [7] H.-y. Zhang, W.-m. Lin, and A.-x. Chen, “Path planning for the mobile robot: A review,” Symmetry, vol. 10, no. 10, p. 450, 2018. [8] J. R. Sanchez-Ibanez, C. J. Perez-del Pulgar, and A. García-Cerezo, “Path planning for autonomous mobile robots: A review,” Sensors, vol. 21, no. 23, p. 7898, 2021. [9] O. Souissi, R. Benatitallah, D. Duvivier, A. Artiba, N. Belanger, and P. Feyzeau, “Path planning: A 2013 survey,” in Proceedings of 2013 International Conference on Industrial Engineering and Systems Management (IESM), pp. 1–8, IEEE, 2013. [10] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische mathematik, vol. 1, no. 1, pp. 269–271, 1959. [11] P.E.Hart,N.J.Nilsson,andB.Raphael,“A formal basis for the heuristic determination of minimum cost paths,” IEEE transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968. [12] A. Stentz, “Optimal and efficient path planning for partially-known environments,” in Proceedings of the 1994 IEEE international conference on robotics and automation, pp. 3310–3317, IEEE, 1994. [13] S.Koenig and M.Likhachev,“Incrementala*,”Advances in neural information processing systems, vol. 14, 2001. [14] M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, and S. Thrun, “Anytime search in dynamic graphs,” Artificial Intelligence, vol. 172, no. 14, pp. 1613–1643, 2008. [15] D. Ferguson and A. Stentz, “The field d* algorithm for improved path planning and replanning in uniform and non-uniform cost environments,” Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-05-19, 2005. [16] J. Carsten, A. Rankin, D. Ferguson, and A. Stentz, “Global planning on the mars exploration rovers: Software integration and surface testing,” Journal of Field Robotics, vol. 26, no. 4, pp. 337–357, 2009. [17] Y. Zhang, L.-l. Li, H.-C. Lin, Z. Ma, and J. Zhao, “Development of path planning approach using improved a-star algorithm in agv system,” Journal of Internet Technology, vol. 20, no. 3, pp. 915–924, 2019. [18] D. Xiang, H. Lin, J. Ouyang, and D. Huang, “Combined improved a* and greedy algorithm for path planning of multi-objective mobile robot,” Scientific Reports, vol. 12, no. 1, p. 13273, 2022. [19] L. E. Kavraki, P. Svestka, J.-C. 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. [20] S. M. LaValle, J. J. Kuffner, B. Donald, et al., “Rapidly-exploring random trees: Progress and prospects,” Algorithmic and computational robotics: new directions, vol. 5, pp. 293–308, 2001. [21] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” The international journal of robotics research, vol. 30, no. 7, pp. 846–894, 2011. [22] J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, “Batch informed trees (bit*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs,” in 2015 IEEE international conference on robotics and automation (ICRA), pp. 3067–3074, IEEE, 2015. [23] W. Reid, R. Fitch, A. H. Göktoğan, and S. Sukkarieh, “Sampling-based hierarchical motion planning for a reconfigurable wheel-on-leg planetary analogue exploration rover,” Journal of Field Robotics, vol. 37, no. 5, pp. 786–811, 2020. [24] D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” IEEE Robotics & Automation Magazine, vol. 4, no. 1, pp. 23–33, 1997. [25] C. Rösmann, W. Feiten, T. Wösch, F. Hoffmann, and T. Bertram, “Trajectory modification considering dynamic constraints of autonomous robots,” in ROBOTIK 2012; 7th German Conference on Robotics, pp. 1–6, VDE, 2012. [26] D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel, “Practical search techniques in path planning for autonomous driving,” Ann Arbor, vol. 1001, no. 48105, pp. 18–80, 2008. [27] D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel,“Path planning for autonomous vehicles in unknown semi-structured environments,” The International Journal of Robotics Research, vol. 29, no. 5, pp. 485–501, 2010. [28] M. Tounsi and J. Le Corre, “Trajectory generation for mobile robots,” Mathematics and Computers in Simulation, vol. 41, no. 3-4, pp. 367–376, 1996. [29] J. Yuan, F. Sun, and Y. Huang, “Trajectory generation and tracking control for double-steering tractor–trailer mobile robots with on-axle hitching,” IEEE Transactions on Industrial Electronics, vol. 62, no. 12, pp. 7665–7677, 2015. [30] M. Hehn and R. D’Andrea, “Quadrocopter trajectory generation and control,” IFAC proceedings Volumes, vol. 44, no. 1, pp. 1485–1491, 2011. [31] T. Inanc, S. C. Shadden, and J. E. Marsden, “Optimal trajectory generation in ocean flows,” in Proceedings of the 2005, American Control Conference, 2005., pp. 674– 679, IEEE, 2005. [32] T. Kröger and T. Kröger, Literature survey: Trajectory generation in and control of robotic systems. Springer, 2010. [33] W. L. Nelson, “Continuous steering-function control of robot carts,” IEEE Transactions on Industrial Electronics, vol. 36, no. 3, pp. 330–337, 1989. [34] A. Piazzi, C. G. L. Bianco, and M. Romano, “eta3-splines for the smooth path generation of wheeled mobile robots,” IEEE Transactions on Robotics, vol. 23, no. 5, pp. 1089–1095, 2007. [35] M. Candeloro, A. M. Lekkas, A. J. Sørensen, and T. I. Fossen, “Continuous curvature path planning using voronoi diagrams and fermat’s spirals,” IFAC Proceedings Volumes, vol. 46, no. 33, pp. 132–137, 2013. [36] B. Song, Z. Wang, and L. Zou, “An improved pso algorithm for smooth path planning of mobile robots using continuous high-degree bezier curve,” Applied Soft Computing, vol. 100, p. 106960, 2021. [37] M. Kokot, D. Miklić, and T. Petrović, “Path continuity for multi-wheeled agvs,” IEEE Robotics and Automation Letters, vol. 6, no. 4, pp. 7437–7444, 2021. [38] R. H. Bartels, J. C. Beatty, and B. A. Barsky, An introduction to splines for use in computer graphics and geometric modeling. Morgan Kaufmann, 1995. [39] G. A. Watson, Approximation theory and numerical methods. John Wiley & Sons, 1980. [40] S.-R. Chang and U.-Y. Huh, “g2 continuity smooth path planning using cubic polynomial interpolation with membership function,” Journal of Electrical Engineering and Technology, vol. 10, no. 2, pp. 676–687, 2015. [41] T. Maekawa, T. Noda, S. Tamura, T. Ozaki, and K.-i. Machida, “Curvature continuous path generation for autonomous vehicle using b-spline curves,” Computer-Aided Design, vol. 42, no. 4, pp. 350–359, 2010. [42] J. Song and I. Sharf, “Collision and rollover-free g 2 path planning for mobile manipulation,” in 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 10275–10282, IEEE, 2022. [43] S. Zhang, Y. Chen, S. Chen, and N. Zheng, “Hybrid a-based curvature continuous path planning in complex dynamic environments,” in 2019 IEEE Intelligent Transportation Systems Conference (ITSC), pp. 1468–1474, IEEE, 2019. [44] F. H. Ajeil, I. K. Ibraheem, M. A. Sahib, and A. J. Humaidi, “Multi-objective path planning of an autonomous mobile robot using hybrid pso-mfb optimization algorithm,” Applied Soft Computing, vol. 89, p. 106076, 2020. [45] K.-C. Kuo, “Solving box-pushing problem in narrow passages environment with differential-drive robot based on hybrid a* algorithm,” Master’s thesis, National Taiwan University, Jan 2022. [46] A. Yufka and M. Ozkan, “Formation-based control scheme for cooperative transportation by multiple mobile robots,” International Journal of Advanced Robotic Systems, vol. 12, no. 9, p. 120, 2015. [47] Z. Wang and M. Schwager, “Multi-robot manipulation without communication,” in Distributed Autonomous Robotic Systems: The 12th International Symposium, pp. 135–149, Springer, 2016. [48] D. Trivun, E. Šalaka, D. Osmanković, J. Velagić, and N. Osmić, “Active slam-based algorithm for autonomous exploration with mobile robot,” in 2015 IEEE International Conference on Industrial Technology (ICIT), pp. 74–79, IEEE, 2015. [49] B. A. Barsky and T. D. DeRose, “Geometric continuity of parametric curves: three equivalent characterizations,” IEEE Computer Graphics and Applications, vol. 9, no. 6, pp. 60–69, 1989. [50] V. Galishnikova and P. Pahl, “Constrained construction of planar delaunay triangulations without flipping,” Structural Mechanics of Engineering Constructions and Buildings, vol. 14, pp. 154–174, 12 2018. [51] W. L. Roque and D. Doering, “Constructing approximate voronoi diagrams from digital images of generalized polygons and circular objects,” in International Conference in Central Europe on Computer Graphics and Visualization, 2003. [52] A. Okabe, B. Boots, and K. Sugihara, “Nearest neighbourhood operations with generalized voronoi diagrams: a review,” International Journal of Geographical Information Systems, vol. 8, no. 1, pp. 43–71, 1994. [53] R. Samaniego, J. Lopez, and F. Vazquez, “Path planning for non-circular, non-holonomic robots in highly cluttered environments,” Sensors, vol. 17, no. 8, p. 1876, 2017. [54] M. Likhachev and D. Ferguson, “Planning long dynamically feasible maneuvers for autonomous vehicles,” The International Journal of Robotics Research, vol. 28, no. 8, pp. 933–945, 2009. | - |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/92617 | - |
dc.description.abstract | 隨著工業技術的進步,移動式機器人在各個領域中的應用日益廣泛。其中由於搬運為移動式機器人的基本能力之一,在現今許多情境中搬運任務已經實現高度自動化。然而,當搬運物體的尺寸增加時,單一機器人面臨載重等方面的能力限制,這促使多機器人系統成為能 夠靈活適應需求的理想替代方案。然而,目前對多機器人搬運系統的運動規劃通常採用特定的運動模式來簡化問題,這往往限制了系統的運動彈性,特別是在處理瘦長物體時,這可能導致更複雜的避障問題。
為了克服這些限制,本研究分析了多差速式機器人參與搬運系統後耦合的運動限制。我們確定了使用差速式機器人進行搬運時,被搬運物必須滿足路徑為 G2 連續以及朝向對路徑長參數為 C2 連續的條件。基於這些限制,本研究提出了一種新的運動規劃方法,將路徑和朝向 的規劃分為兩個階段,以最大程度發揮系統的運動能力。具體而言,我們引入了自行建立的「朝向佔據地圖」和「沿著路徑的朝向網格地圖」來連接這兩個階段。接著,通過修改過的 A* 演算法在各階段中進行路徑規劃,獲得最佳結果。這種方法生成的路徑在滿足各機器人各輪速度連續的條件下,實現了等速率搬運物體,從而節省了以往切換運動模式所需的時間。同時,通過減少不必要的朝向變化,我們獲得了相對較短的總路徑長,進一步節省了搬運所需的能源。這項研究的方法不僅提高了搬運系統的靈活性和效能,同時也為解決目前搬運系統中存在的運動模式限制問題提供了新的洞察。 | zh_TW |
dc.description.abstract | Mobile robots are now widely used in various applications, especially in automation of objects transportation. As the size of the object increases, transporting with a single robot may become infeasible due to the limitations such as their weight-bearing capacity. In such cases, employing multi-robot systems that can be flexibly configured becomes a suitable alternative. However, existing planning methods for multi-robot systems often rely on predefined motion modes to simplify planning, thereby limiting the overall motion flexibility of the system. Additionally, when dealing with slender objects, the use of motion modes can lead to more complex challenges related to obstacle avoidance.
To address these issues, this research examines the coupled motion constraints arising from multiple differential-drived robots in transportation systems. It is established that the transported object must follow paths which satisfy G2 continuity and the orientation change must be C2 continuous with respect to the arc-length parameter of the path. A two-stage motion planning method is proposed, comprising path planning and orientation planning, with the goal of maximizing the utilization of system''s motion capabilities. In particular, A* algorithm is modified and utilized in each stage to achieve optimal results. The two stages are integrated using the Orientation Occupancy Map (OOM) and Orientation Grid Map along path (OGMap), constructed from static information. With continuous wheel velocities guaranteed for each robot, the generated paths using this approach enable the constant-speed transportation of objects, eliminating unnecessary time associated with motion mode switching. Furthermore, the method minimizes unnecessary changes in orientation, resulting in a relatively shorter total path length that conserves energy and enhances the overall efficiency of the transportation process. This research not only improves the flexibility and efficiency of transportation systems but also introduces a novel perspective on addressing challenges associated with motion modes. | en |
dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-05-14T16:05:12Z No. of bitstreams: 0 | en |
dc.description.provenance | Made available in DSpace on 2024-05-14T16:05:12Z (GMT). No. of bitstreams: 0 | en |
dc.description.tableofcontents | 口試委員會審定書 ........................................... i
誌謝 ....................................................... ii Abstract ................................................... iv 摘要 ....................................................... vi Contents ................................................... vii List of Figures ............................................ xi List of Tables ............................................. xiv List of Abbreviations ...................................... xv 1 Introduction ............................................. 1 1.1 Precface ............................................. 1 1.2 Multi-Robot Transportation System .................... 3 1.3 Research Motivation and Purpose ...................... 5 1.4 Thesis Organization .................................. 8 2 Literature Review ........................................ 9 2.1 Motion Planning ...................................... 10 2.1.1 C-Space-Based Approach ........................... 10 2.1.2 Control-Based Approach ........................... 15 2.1.3 Motion Planning Summary .......................... 17 2.2 Path Refinement ...................................... 18 2.2.1 Trajectory Generation ............................ 19 2.2.2 Smoothing ........................................ 22 2.2.3 Path Refinement Summary .......................... 24 2.3 Collision Detectionin Motion Planning ................ 25 2.4 Summary .............................................. 26 3 Proposed Algorithm Overview .............................. 28 3.1 Research Problem ..................................... 28 3.1.1 Target System Definition.......................... 28 3.1.2 Problem Definition................................ 31 3.1.3 Kinematic Constraints ............................ 32 3.2 Proposed Algorithm Framework ......................... 34 4 Proposed Algorithm Part 1: Path Planning ................. 37 4.1 Path Generation ...................................... 38 4.1.1 Modified A* ...................................... 38 4.1.2 Path Simplification .............................. 48 4.2 Path Smoothing ....................................... 51 4.2.1 Bezier Curve ..................................... 51 4.2.2 Modified Bezier Curve Connecting Path Segments ... 52 4.2.3 Obstacle Avoidance ............................... 53 4.3 Path Planning Summary ................................ 57 5 Proposed Algorithm Part 2: Orientation Planning .......... 58 5.1 Orientation Path Generation .......................... 58 5.1.1 Orientation Grid Map along Path .................. 59 5.1.2 Orientation A* ................................... 60 5.1.3 Orientation Path Simplification .................. 62 5.2 Orientation Smoothing ................................ 62 5.2.1 Polynomial Interpolation ......................... 63 5.2.2 Smoothing Adjustment for Obstacle Avoidance ...... 66 5.3 Orientation Planning Summary ......................... 69 6 Simulation Result and Analysis ........................... 70 6.1 Smooth Motion Validation ............................. 70 6.2 Global Planning Results .............................. 71 6.2.1 Obstacle Avoidance and Narrow Passage ............ 71 6.2.2 Planning Result with respect to Aspect Ratio ..... 75 6.2.3 Planning Capability .............................. 77 6.3 Integration Result and Summary ....................... 80 7 Conclusion and Future Works .............................. 83 7.1 Conclusion ........................................... 83 7.2 Future Works ......................................... 85 Reference .................................................. 87 | - |
dc.language.iso | en | - |
dc.title | 應用於多機器人平滑搬運瘦長物體之規劃方法 | zh_TW |
dc.title | A Smooth Planning Algorithm for Transporting Slender Objects using Multi-Robot Systems | en |
dc.type | Thesis | - |
dc.date.schoolyear | 112-2 | - |
dc.description.degree | 碩士 | - |
dc.contributor.oralexamcommittee | 蘇偉儁;林柏廷 | zh_TW |
dc.contributor.oralexamcommittee | Wei-Jiun Su;Po-Ting Lin | en |
dc.subject.keyword | 路徑規劃,路徑連續性,瘦長物體搬運,多機器人系統, | zh_TW |
dc.subject.keyword | Path Planning,Path Continuity,Slender Object Transportation,Multi-Robot System, | en |
dc.relation.page | 94 | - |
dc.identifier.doi | 10.6342/NTU202400757 | - |
dc.rights.note | 同意授權(全球公開) | - |
dc.date.accepted | 2024-03-06 | - |
dc.contributor.author-college | 工學院 | - |
dc.contributor.author-dept | 機械工程學系 | - |
顯示於系所單位: | 機械工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-112-2.pdf | 6.29 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。