臺灣博碩士論文加值系統

所謂的路徑規劃問題是在計算最佳路徑從來源端到目的端且不和任何障礙物進行碰撞。這篇文章主要使用三個步驟來解決路徑規劃的問題。第一步假設在沒有障礙物的環境中計算最小距離路徑從來源端到目的地。然後考慮這條道路會不會碰撞到障礙物。當路徑碰撞到障礙，設置轉折點在碰撞點附近的無障礙物區域且設置新的路徑經過這個轉折點。使用這三個步驟形成一個迴圈並且在該路徑不跨越任何障礙物時停止。
我們進行模擬在6種不同型態的障礙物下，這個演算法都使用極少的時間以及回合數，尤其是在簡單的環境中執行效率更佳。我們也與分層進化算法做比較，其執行的回合數少了將近一半且儲存的路徑數量也只有1/20。相對與進化演算法節省了較多的系統資源並減少運算時間。

The so-called problem of path planning refers to the computation of an optimal path for a robot to move from the origin to the destination without colliding with any obstacles. In this study, we mainly use three steps to solve the problem of path planning. First, we calculate the minimum distance path from the origin to the destination when there are no obstacles in the environment. Then, we consider the case in which the robot comes across an obstacle in the abovementioned path. In this case, we set a turning point that is close to the collision point and is within an obstacle-free area. In the third step, we set a new path that crosses this turning point. We use these three steps in a loop until an obstacle-free path is found.
Further, we select six types of obstacles to simulate the proposed algorithm. This algorithm requires only a little time and a relatively fewer number of rounds to calculate the path. In particular, in a simple environment, this algorithm is quite efficient. We also compare the proposed algorithm with hierarchical evolutionary algorithms. The comparison results reveal that the proposed algorithm requires close to just half the number of rounds required by hierarchical evolutionary algorithms. Further, the amount of memory required to store the path tree in the case of the proposed algorithm is just one-twentieth of that required in the case of hierarchical evolutionary algorithms. Hence, the proposed algorithm requires fewer system resources and has a lower computation time than the hierarchical evolutionary algorithms.

中文摘要 i
Abstract ii
Acknowledgements iii
Contents iv
List of figures v
Chapter 1 Introduction 1
Chapter 2 Maps and path planning 3
2.1 Maps 3
2.2 Evolutionary algorithm for path planning 4
Chapter 3 Path planning method 5
3.1 Set the minimum distance path between two points 5
3.2 Does the path have any obstacles? 6
3.3 Set a turning point for a new path 7
3.4 Total flow path 8
Chapter 4 Greedy algorithm for path planning 13
4.1 Modified algorithm 13
4.2 Simulation 13
4.3 Comparison with hierarchical evolutionary algorithms 21
Chapter 5 Conclusions 22
References 23

[1]Kala,R., Shukla,A., and Tiwari,R., 2010, “Dynamic [1]Environment Robot Path Planning Using Hierarchical Evolutionary Algorithms,” Cybernetics and Systems: An International Journal 41, 435–454.
[2]Tungadi, F. and Kleeman, L., 2011, “Discovering and restoring changes in object positions using an autonomous robot with laser rangefinders,” Robotics and Autonomous Systems 59, 428–443.
[3]Xia, Zeyang., Xiong, J., and Chen, K., 2011, “Global Navigation for Humanoid Robots Using Sampling-Based Footstep Planners,” IEEE/ASME TRANSACTIONS ON MECHATRONICS 16(4), 716-723.
[4]Alvarez, A., Caiti, A., and Onken, R., 2004, “Evolutionary path planning for autonomous underwater vehicles in a variable ocean,” IEEE Journal of Oceanic Engineering 29(2), 418–429.
[5]Carpin, S. and Pagello, E., 2009, “An experimental study of distributed robot coordination,” Robotics and Autonomous Systems 57(2), 129–133.
[6]Chen, L.-H. and Chiang, C.-H., 2003, “New approach to intelligent control systems
[7]with self-exploring process,” IEEE Transactions on Systems, Man and Cybernetics – Part B: Cybernetics 33(1), 56–66.
[8]Ge, S. S. and Lewis, F. L., 2006, “Autonomous mobile robot. Boca Raton, FL: Taylor & Francis.”
[9]Hui, N. B. and Pratihar, D. K., 2009, “A comparative study on some navigation schemes of a real robot tackling moving obstacles,” Robotics and Computer-Integrated Manufacturing 25(4–5), 810–828.
[10]Hwang, J. Y., Kim, J. S., Lim, S. S., and Park, K. H., 2003, “A fast path planning by path graph optimization,” IEEE Transaction on Systems, Man, and Cybernetics – Part A: Systems and Humans 33(1), 121–128.
[11]Jolly, K. G., Kumar, R. S., and Vijayakumar, R., 2009, “A Bezier curve based path planning in a multi-agent robot soccer system without violating the acceleration limits,” Robotics and Autonomous Systems 57(1), 23–33.
[12]Juidette, H. and Youlal, H., 2000, “Fuzzy dynamic path planning using genetic algorithms,” IEEE Electronics Letters 36(4), 374–376.
[13]Kala, R., Shukla, A., and Tiwari, R., 2009a, “Fusion of evolutionary algorithms and multi-neuron heuristic search for robotic path planning,” In Proceedings of the IEEE 2009 world congress on nature & biologically inspired computing (NABIC’09). Coimbatore, India, IEEE, pp. 684–689.
[14]Kala, R., Shukla, A., and Tiwari, R., 2009b, “Robotic path planning using multi neuron heuristic search,” Proceedings of the ACM 2009 International Conference on Computer Sciences and Convergence Information Technology (ICCIT 2009). Seoul, Korea, ACM, pp. 1318–1323.
[15]Kala, R., Shukla, A., Tiwari, A., Rungta, S., and Janghel, R. R., 2009c, “Mobile robot navigation control in moving obstacle environment using genetic algorithm, artificial neural networks and A algorithm,” In Proceedings of the IEEE World Congress on Computer Science and Information Engineering (CSIE 2009), Los Angeles=Anaheim, USA, IEEE, pp. 705–713.
[16]Kala, R., Shukla, A., and Tiwari, R., 2010, “Fusion of probabilistic A algorithm and fuzzy inference system for robotic path planning,” Artificial Intelligence Review 33(4), 275–306.
[17]Kambhampati, S. and Davis, L. S., 1986, “Multiresolution path planning for mobile Robots,” IEEE Journal of Robotics and Automation 2(3), 135–145.
[18]Lai, X.-C., Ge, S. S., and Mamun, A. A., 2007, “Hierarchical incremental path planning and situation-dependent optimized dynamic motion planning considering accelerations,” IEEE Transactions on Systems, Man, and Cybernetics – Part B: Cybernetics 37(6), 1541–1554.
[19]Lin, H.-S., Xiao, Ji., and Michalewicz, Z., 1994, “Evolutionary algorithm for path planning in mobile robot environment,” In Proceedings of the First IEEE Conference on Evolutionary Computation (ICEC ’94), Piscataway, NJ, IEEE, pp. 211–216.
[20]O’Hara, K. J., Walker, D. B., and Balch, T. R., 2008, “Physical path planning using a pervasive embedded network,” IEEE Transactions on Robotics 24(3), 741–746.
[21]Peasgood, M., Clark, C. M., and McPhee, J., 2008, “A complete and scalable strategy for coordinating multiple robots within roadmaps,” IEEE Transactions on Robotics 24(2), 283–292.
[22]Pozna, C., Troesterb, F., Precupc, R. E., Tard, J. K., and Preitlc, S., 2009, “On the design of an obstacle avoiding trajectory: Method and simulation,” Mathematics and Computers in Simulation, 79(7), 2211–2226.
[23]Shibata, T., Fukuda, T., and Tanie, K., 1993, “Fuzzy critic for robotic motion planning
[24]by genetic algorithm in hierarchical intelligent control,” In Proceedings of 1993 ,International Joint Conference on Neural Networks. Nagoya, Japan, IEEE, pp. 770–773.
[25]Shukla, A. and Kala, R. 2008., “Multi neuron heuristic search.” International Journal of Computer Science and Network Security 8(6), 344–350.
[26]Shukla, A., Tiwari, R., and Kala, R., 2008, “Mobile robot navigation control in moving obstacle environment using A algorithm,” Intelligent Systems Engineering Systems through Artificial Neural Networks 18, 113–120.
[27]Shukla, A., Tiwari, R., and Kala, R., 2009, “Mobile robot navigation control in moving obstacle environment using genetic algorithms and artificial neural networks,” International Journal of Artificial Intelligence and Computational Research 1(1), 1–12.
[28]Shukla, A., Tiwari, R., and Kala, R., 2010, “Real life applications of soft computing.” Boca Raton, FL, USA, CRC Press.
[29]Tsai, C.-H., Lee, J.-S., and Chuang, J.-H., 2001, “Path planning of 3-D objects using a new workspace model.” IEEE Transactions on Systems, Man, and Cybernetics – Part C: Applications and Reviews 31(3), 405–410.
[30]Urdiales, C., Bantlera, A., Arrebola, F., and Sandova1, F., 1998, “Multi-level path planning algorithm for autonomous robots,” IEEE Electronics Letters 34(2), 223–224.
[31]Xiao, J., Michalewicz, Z., Zhang, L., and Trojanowski, K., 1997, “Adaptive evolutionary planner=navigator for mobile robots.” IEEE Transactions on Evolutionary Computation 1(1), 18–28.
[32]Zhu, D. and Latombe, J.-C., 1991, “New heuristic algorithms for efficient hierarchical path planning,” IEEE Transactions on Robotics and Automation 7(1), 9–20.