臺灣博碩士論文加值系統

在本論文中，提出了一種新穎的自走車導航路徑規劃算法。其具有三大主要改進。第一項改進是減少搜尋方向，使演算法在搜尋過程中，避免探索冗餘節點。第二項改良是加入障礙物懲罰機制，確保演算法生成的路徑與障礙物保持安全距離，從而防止在自走車在導航過程中發生碰撞。最後一項改進是優化路徑，通過減少轉彎次數和縮短路徑長度進一步提升路徑品質。這些改進使得演算法生成的路徑更加適合自走車的實際應用。在模擬中，這些改進方法的可行性和性能提升得到了驗證。最終，這些方法被應用於一套自走車系統，並於現實環境中成功完成了導航任務，進一步展示與驗證了所提出方法的可行性。

In this work, a novel path planning algorithm for mobile robot navigation is proposed, featuring three key improvements. The first improvement is reducing the search direction, which helps the algorithm avoid redundant nodes exploration. The second improvement is the obstacle penalty, which ensures that the path generated by the algorithm maintains a safe distance from obstacles, thereby preventing collisions during mobile robot navigation. The final improvement is the optimization of the number of turns, which further refines the path by reducing both the number of turns and the path length. These enhancements make the algorithm's paths more suitable for practical applications in mobile robot navigation. In simulations using various maps, the proposed methods were validated for their feasibility and improved performance. Finally, the methods were applied to an actual mobile robot, successfully completing navigation tasks in a real-world environment, thereby further demonstrating and verifying the feasibility and effectiveness of the proposed methods.

摘要 i
Abstract ii
Contents iii
List of Figures v
List of Tables viii
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Literature Review 2
1.3 Contribution 5
1.4 Organization 6
Chapter 2 System Description 7
2.1 Hardware Platform 8
2.2 Software Architecture 12
Chapter 3 Methodology 13
3.1 Map Building 13
3.1.1 ORB-SLAM2 13
3.1.2 Mapping 16
3.2 Path Planning Algorithm 20
3.2.1 A* Algorithm 20
3.2.2 Weighted A* Algorithm 22
3.2.3 Anytime Weighted A* Algorithm 23
3.2.4 Anytime Repairing A* Algorithm 26
3.2.5 ARA*+ Algorithm 31
3.3 Adaptive Visual Servo Tracking Using Fuzzy Q-Learning 33
3.3.1 Target Searching Based on Object Features Matching 34
3.3.2 Fuzzy Q-Learning (FQL) Controller 36
3.3.3 Visual Servo Tracking 41
3.3.4 Adaptive Servo Gain with Fuzzy Q-Learning 45
Chapter 4 Proposed Method 47
4.1 Reduce Search Direction 47
4.2 Obstacle Penalty 50
4.3 Number of Turns Optimization 53
Chapter 5 Simulation 56
5.1 Simulation Environments 56
5.2 Performance of Reduce Search Direction 59
5.3 Performance of Obstacle Penalty 67
5.4 Performance of Number of Turns Optimization 70
Chapter 6 Experiment 77
6.1 Performance of Mobile Robot Navigation Using Different Path Planning Algorithm 77
6.1.1 Map Building 77
6.1.2 A* Algorithm 81
6.1.3 ARA* Algorithm 82
6.1.4 Proposed Method 84
Chapter 7 Conclusion and Future Work 86

[1]"World Robotics 2023 Report: Asia ahead of Europe and the Americas." International Federation of Robotics. https://ifr.org/ifr-press-releases/news/world-robotics-2023-report-asia-ahead-of-europe-and-the-americas (accessed 21 June 2024.
[2]"Robots Help to Solve “Japan’s 2024 Problem”." International Federation of Robotics. https://ifr.org/ifr-press-releases/news/robots-help-to-solve-japans-2024-problem (accessed 21 June 2024.
[3]"Staff Shortage Boosts Service Robots – Sales Up 48%." International Federation of Robotics. https://ifr.org/ifr-press-releases/news/staff-shortage-boosts-service-robots-sales-up-48 (accessed 21 June 2024.
[4]M. Aizat, A. Azmin, and W. Rahiman, "A survey on navigation approaches for automated guided vehicle robots in dynamic surrounding," IEEE Access, vol. 11, pp. 33934-33955, 2023.
[5]L. Liu, X. Wang, X. Yang, H. Liu, J. Li, and P. Wang, "Path planning techniques for mobile robots: Review and prospect," Expert Systems with Applications, p. 120254, 2023.
[6]E. W. Dijkstra, "A note on two problems in connexion with graphs," in Edsger Wybe Dijkstra: His Life, Work, and Legacy, 2022, pp. 287-290.
[7]P. E. Hart, N. J. Nilsson, and B. 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.
[8]I. Pohl, "First results on the effect of error in heuristic search," Machine Intelligence, vol. 5, pp. 219-236, 1970.
[9]I. Pohl, "Heuristic search viewed as path finding in a graph," Artificial intelligence, vol. 1, no. 3-4, pp. 193-204, 1970.
[10]J. Pearl, Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley Longman Publishing Co., Inc., 1984.
[11]B. Bonet and H. Geffner, "Planning as heuristic search," Artificial Intelligence, vol. 129, no. 1-2, pp. 5-33, 2001.
[12]H. Davis, A. Bramanti-Gregor, and J. Wang, "The advantages of using depth and breadth components in heuristic search. Methodologies for Intelligent Systems, vol. 3, Ras, ZW and Saitta, L," ed: New York, North-Holland, 1988.
[13]S. Chen, J. Ji, H. Su, and Y. Yang, "Improved A-star Method for Collision Avoidance and Path Smoothing," in 2023 IEEE International Conference on Control, Electronics and Computer Technology (ICCECT), 2023: IEEE, pp. 32-35.
[14]T. Long, "Improved A-star Algorithm in Efficiency Enhancing and Path Smoothing," in 2023 IEEE International Conference on Control, Electronics and Computer Technology (ICCECT), 2023: IEEE, pp. 28-31.
[15]B. Cao, Z. Yang, L. Yu, and Y. Zhang, "Research on the star algorithm for safe path planning," in 2023 IEEE International Conference on Control, Electronics and Computer Technology (ICCECT), 2023: IEEE, pp. 105-109.
[16]R. Yang and L. Cheng, "Path planning of restaurant service robot based on a-star algorithms with updated weights," in 2019 12th International Symposium on Computational Intelligence and Design (ISCID), 2019, vol. 1: IEEE, pp. 292-295.
[17]I. Pohl, "The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving," in Proceedings of the 3rd international joint conference on Artificial intelligence, 1973, pp. 12-17.
[18]C. Jiang, C. Wang, and M. Wang, "Research on path planning for mobile robots based on improved A-star algorithm," in 2023 IEEE 7th Information Technology and Mechatronics Engineering Conference (ITOEC), 2023, vol. 7: IEEE, pp. 723-727.
[19]W. Bao, J. Li, Z. Pan, and R. Yu, "Improved A-star Algorithm for Mobile Robot Path Planning Based on Sixteen-direction Search," in 2022 China Automation Congress (CAC), 2022: IEEE, pp. 1332-1336.
[20]P. Luo, B. Li, X. Xue, and Z. Liu, "Research on Path Planning of Substation Inspection Robot Based on Improved A* Algorithm," in 2022 China Automation Congress (CAC), 2022: IEEE, pp. 1119-1124.
[21]E. A. Hansen and R. Zhou, "Anytime heuristic search," Journal of Artificial Intelligence Research, vol. 28, pp. 267-297, 2007.
[22]R. Zhou and E. A. Hansen, "Multiple Sequence Alignment Using Anytime A*," in AAAI/IAAI, 2002, pp. 975-977.
[23]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.
[24]M. Likhachev, G. J. Gordon, and S. Thrun, "ARA*: Anytime A* with provable bounds on sub-optimality," Advances in neural information processing systems, vol. 16, 2003.
[25]M. Cao, B. Li, and M. Shi, "The Dynamic Path Planning of Indoor Robot Fusing B-Spline and Improved Anytime Repairing A* Algorithm," IEEE Access, 2023.
[26]J. Xin, X.-L. Jiao, Y. Yang, and D. Liu, "Visual navigation for mobile robot with Kinect camera in dynamic environment," in 2016 35th Chinese Control Conference (CCC), 2016: IEEE, pp. 4757-4764.
[27]Z. Zhang, T. Long, Z. Wang, G. Xu, and Y. Cao, "UAV Dynamic Path Planning using Anytime Repairing Sparse A* Algorithm and Targets Motion Estimation (IEEE/CSAA GNCC)," in 2018 IEEE CSAA Guidance, Navigation and Control Conference (CGNCC), 2018: IEEE, pp. 1-6.
[28]B. Li, J. Gong, Y. Jiang, H. Nasry, and G. Xiong, "ARA*+: Improved path planning algorithm based on ARA," in 2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, 2012, vol. 2: IEEE, pp. 361-365.
[29]R. Mur-Artal and J. D. Tardós, "Orb-slam2: An open-source slam system for monocular, stereo, and rgb-d cameras," IEEE transactions on robotics, vol. 33, no. 5, pp. 1255-1262, 2017.
[30]E. Rublee, V. Rabaud, K. Konolige, and G. Bradski, "ORB: An efficient alternative to SIFT or SURF," in 2011 International conference on computer vision, 2011: Ieee, pp. 2564-2571.
[31]D. G. Lowe, "Distinctive image features from scale-invariant keypoints," International journal of computer vision, vol. 60, pp. 91-110, 2004.
[32]H. Bay, T. Tuytelaars, and L. Van Gool, "Surf: Speeded up robust features," in Computer Vision–ECCV 2006: 9th European Conference on Computer Vision, Graz, Austria, May 7-13, 2006. Proceedings, Part I 9, 2006: Springer, pp. 404-417.
[33]A. Hornung, K. M. Wurm, M. Bennewitz, C. Stachniss, and W. Burgard, "OctoMap: An efficient probabilistic 3D mapping framework based on octrees," Autonomous robots, vol. 34, pp. 189-206, 2013.
[34]E. A. Hansen, S. Zilberstein, and V. A. Danilchenko, "Anytime heuristic search: First results," Univ. Massachusetts, Amherst, MA, Tech. Rep, vol. 50, 1997.
[35]Z. Zhang, S. Wang, and J. Zhou, "A-star algorithm for expanding the number of search directions in path planning," in 2021 2nd International Seminar on Artificial Intelligence, Networking and Information Technology (AINIT), 2021: IEEE, pp. 208-211.
[36]S. K. Debnath et al., "Different cell decomposition path planning methods for unmanned air vehicles-A review," in Proceedings of the 11th National Technical Seminar on Unmanned System Technology 2019: NUSYS'19, 2021: Springer, pp. 99-111.
[37]E. Andres, P. Nehlig, and J. Françon, "Supercover of straight lines, planes and triangles," in Discrete Geometry for Computer Imagery: 7th International Workshop, DGCI'97 Montpellier, France, December 3–5, 1997 Proceedings 7, 1997: Springer, pp. 243-254.