本研究基於粒子群演算法(PSO)與自我學習粒子群演算法(SLPSO)探討具有不同速度限制的機器人最佳路徑規劃。
粒子群演算法已被示為一個解決最佳化問題的有效演算法，文獻回顧顯示大多數的粒子群演算法其全部的粒子會使用相同的策略，換言之，僅使用唯一的學習模式，而這種單調的學習模式將會造成陷入局部最佳解的結果，而無法處理不同的複雜的問題。對於全局最佳的問題，本文研究應用了一個新穎的粒子群演算法，稱之為自我學習粒子群演算法，在此演算法中，每一個粒子皆有四種策略，用以解決搜尋空間中不同的狀況。此外，搭配這四種策略進而被實現在個別的適應學習架構上，使每一個粒子都依據自身的局部適應值來選擇其適當對應的策略。
一般而言， 在機械人最佳路徑規劃中，最佳解意指為最短路徑，換言之即是具有最短時間的路徑。然而在實際的情況裡，由於不同的地形狀況機械人的移動速度亦會有所不同。在本文研究中，我們基於這個觀點來考慮機械人路徑規劃，在不同的地形狀態底下，假設機械人以不同的速度限制來做移動，所以最短路徑並非代表著最短時間。因此，應用自我學習粒子群演算法於不同的速度限制下來解決機械人最佳路徑規劃的問題，由本研究的模擬結果顯示出，自我學習粒子群演算法相較粒子群演算法能更有效且更有效率地找到最佳解。

Based on the particle swarm optimization (PSO) and self-learning particle swarm optimization (SLPSO), this study discusses the optimal path planning for a mobile robot with different velocity constraints.
PSO has been shown as an effective algorithm for solving global optimization problems. Literature survey indicates that in most PSO algorithms all particles in a swarm use the same strategy, i.e., a single learning pattern. This monotonic learning pattern may result in the local optimization solution which makes it unable to deal with different complex situations. This study applies a novel PSO algorithm, SLPSO, for global optimization problems. In SLPSO, each particle has a set of four strategies to cope with different situations in the search space. Moreover, the cooperation of the four strategies is implemented by an adaptive learning framework at the individual level, which can enable a particle to choose the optimal strategy according to its own local fitness landscape.
In general, for the optimal robotic path planning the optimal solution means the shortest path, i.e., the shortest time. However, in the real case, a robot may move in different velocities due to the different terrain conditions. In this study, we consider the robotic path planning issue based on this viewpoint. Under different terrain conditions, a robot will be assumed to move with different velocity constraints, and the shortest path will not necessarily represent the shortest time. Therefore, SLPSO is applied to solving the optimal robotic path planning issue under velocity constraints. Simulation results show that SLPSO will work effectively and efficiently than PSO to get the optimal solution of the studied issue.

[1]Z.-L. Gaing, C.-H. Lin, M.-H. Tsai, M.-F. Hsieh, and M.-C. Tsai, “Rigorous design and optimization of brushless PM motor using response surface methodology with quantum-behaved PSO operator,” IEEE Transactions on Magnetics, vol. 50, pp. 1-4, 2014.
[2]M. K. Alam, F. Khan, and A. M. Imtiaz, “Optimization of subcell interconnection for multijunction solar cells using switching power converters,” IEEE Transactions on Sustainable Energy vol. 4, pp. 340-349, 2013.
[3]S.-H. Sandra and G.-P. Emiliano, “Channel time allocation PSO for gigabit multimedia wireless Networks,” IEEE Transactions on Multimedia, vol. 16, pp. 828-836, 2014.
[4]Y. Wang, H. Xie, X. Jiang, and B. Liu, “Intelligent closed-loop insulin delivery systems for ICU patients,” IEEE Journal of Biomedical and Health Informatics, vol. 18, pp. 290-299, 2014.
[5]W. Xian, B. Long, M. Li, and H. Wang, “Prognostics of lithium-ion batteries based on the verhulst model, particle swarm optimization and particle filter,” IEEE Transactions on Instrumentation and Measurement, vol. 63, pp. 2-17, 2014.
[6]T. H. Nguyen, H. Morishita, Y. Koyanagi, K. Izui, and S. Nishiwaki, “A multi-level optimization method using PSO for the optimal design of an l-shaped folded monopole antenna array,” IEEE Transactions on Antennas and Propagation, vol. 62, pp. 206-215, 2014.
[7]Y. V. Pehlivanoglu, “A new particle swarm optimization method enhanced with a periodic mutation strategy and neural networks,” IEEE Transactions on Evolutionary Computation, vol. 17, pp. 436-452, 2013.
[8]M. Hu, T. Wu, and J. D. Weir, “An adaptive particle swarm optimization with multiple adaptive methods,” IEEE Transactions on Evolutionary Computation, vol. 17, pp. 705-720, 2013.
[9]H. Duan, Q. Luo, G. Ma, and Y. Shi, “Hybrid particle swarm optimization and genetic algorithm for multi-UAV formation reconfiguration,” IEEE Computational Intelligence Magazine, vol. 8, pp. 16-27, 2013.
[10]K.-B. Lee and J.-H. Kim, “Multiobjective particle swarm optimization with preference-based sort and its application to path following footstep optimization for humanoid robots,” IEEE Transactions on Evolutionary Computation, vol. 17, pp. 755-766, 2013.
[11]Y. Fu, M. Ding, C. Zhou, and H. Hu, “Route planning for unmanned aerial vehicle (UAV) on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 43, pp. 1451-1465, 2013.
[12]C. Liu, Y.-l. Hao, and F. Gao, “A path planning method for underwater vehicle based on ocean current information,” in 2011 Fourth International Joint Conference on Computational Sciences and Optimization (CSO), 2011, pp. 987-991.
[13]G. Yang and R. Zhang, “Path Planning of AUV in Turbulent Ocean Environments Used Adapted Inertia-Weight PSO,” in 2009 Fifth International Conference on Natural Computation, 2009, pp. 299-302.
[14]K. Zhao, S.-J. Li, G. Lu, G.-W. Zhou, and S.-S. Zhang, “Information merging technology and its application in robot path planning,” in 2011 International Conference on Electrical and Control Engineering (ICECE), 2011, pp. 688-691.
[15]P. Raja and S.Pugazhenthi, “Path planning for mobile robots in dynamic environments using particle swarm optimization,” in 2009 International Conference on Advances in Recent Technologies in Communication and Computing, 2009, pp. 401-405.
[16]L.-G. Weng, Z. Ji, M. Xia, and A. Wang, “A multi-objective optimization based on adaptive environmental selection,” in 2013 2nd International Symposium on Instrumentation and Measurement, Sensor Network and Automation (IMSNA), 2013, pp. 999-1003.
[17]C.-C. Tsai, C.-Z. Kuo, C.-C. Chan, and X.-C. Wang, "Global path planning and navigation of an omnidirectional Mecanum mobile robot," in 2013 CACS International Automatic Control Conference (CACS), 2013, pp. 85-90.
[18]K. D. Sharma, A. Chatterjee, and A. Rakshi, "A PSO-lyapunov hybrid stable adaptive fuzzy tracking control approach for vision-based robot navigation," IEEE Transactions on Instrumentation and Measurement, vol. 61, pp. 1908-1914, 2012.
[19]S. V. Ragavan, S. G. Ponnambalam, and C. Sumero, "Waypoint-based path planner for mobile robot navigation using PSO and GA-AIS," in 2011 IEEE Recent Advances in Intelligent Computational Systems (RAICS), 2011, pp. 756-760.
[20]H.-C. Huang and C.-C. Tsai, “Global path planning for autonomous robot navigation using hybrid metaheuristic GA-PSO algorithm,” in 2011 SICE Annual Conference, Waseda University, Tokyo, Japan, 2011, pp. 1338-1343.
[21]Y. Shen and M. Yuan, “A novel poly-clone particle swarm optimization algorithm and its application in mobile robot path planning,” in 2010 Chinese Control and Decision Conference (CCDC), 2010, pp. 2271-2276.
[22]E. Masehian and D. Sedighizadeh, “A multi-objective PSO-based algorithm for robot path planning,” in 2010 IEEE International Conference on Industrial Technology (ICIT), 2010, pp. 465-470.
[23]M. Qian-Zhi and L. Xiu-Juan, “The application of hybrid orthogonal particle swarm optimization in robotic path planning,” in 2010 Sixth International Conference on Natural Computation (ICNC), 2010, pp. 3536-3540.
[24]A.-L. Duan, Q.-B. Duan, and G.-F. Deng, “The new fusion algorithm in robot path planning application,” in 2010 2nd International Conference on Advanced Computer Control (ICACC), 2010, pp. 430-434.
[25]C. Li, S. Yang, and T. T. Nguyen, “A self-learning particle swarm optimizer for global optimization problems,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 42, pp. 627-646, 2012.
[26]“iRobot RoombaR 770, ” 參考網頁http://store.irobot.com/product/index.jsp?productId=11305110
[27]“Google Maps navigation, ” 參考網頁http://www.techbang.com/posts/14008-google-maps-version-of-the-official-voice-navigation-capabilities-into
[28]“上海世博 機械人導覽, ” 參考網頁http://orientaldaily.on.cc/cnt/lifestyle/20100501/00294_001.html?pubdate=20100501
[29]“Intel玩手機遊戲的機械人, ” 參考網頁http://www.dgtrend.com/2013/12/23/
[30]Y.-J. Zheng, H.-F. Ling, J.-Y. Xue, and S.-Y. Chen, “Population classification in fire evacuation: a multiobjective particle swarm optimization approach,” IEEE Transactions on Evolutionary Computation, vol. 18, pp. 70-81, 2014.
[31]Z. Zhang, Q. Zhou, and A. Kusiak, “Optimization of wind power and its variability with a computational intelligence approach,” IEEE Transactions on Sustainable Energy, vol. 5, pp. 228-236, 2014.
[32]Z. Zhang, K. Long, J. Wang, and F. Dressler, “On swarm intelligence inspired self-organized networking: its bionic mechanisms, designing principles and optimization approaches,” Communications Surveys & Tutorials, IEEE, vol. 16, pp. 513-537, 2014.
[33]J. Sun, V. Palade, X.-J. Wu, W. Fang, and Z. Wang, “Solving the power economic dispatch problem with generator constraints by random drift particle swarm optimization,” IEEE Transactions on Industrial Informatics, vol. 10, pp. 222-232, 2014.
[34]S. Saxena, K. Sharma, S. Shiwani, and H. Sharma, “Lbest artificial bee colony using structured swarm,” in 2014 IEEE International Advance Computing Conference (IACC), 2014, pp. 1354-1360.
[35]P. Regulski, D. S. Vilchis-Rodriguez, S. Djurović, and V. Terzija, “Estimation of composite load model parameters using an improved particle swarm optimization method,” IEEE Transactions on Power Delivery, vol. PP, pp. 1-1, 2014.
[36]M. Mishra and S. K. Pal, “A multithreaded bound varying chaotic firefly algorithm for prime factorization,” in 2014 IEEE International Advance Computing Conference (IACC), 2014, pp. 1322-1325.
[37]T.-H. S. Li, Y.-H. Wang, C.-C. Chen, and C.-J. Lin, “A fast color information setup using EP-like PSO for manipulator grasping color objects,” IEEE Transactions on Industrial Informatics, vol. 10, pp. 645-654, 2014.
[38]A. Laudani, F. R. Fulginei, and A. Salvini, “Bouc–wen hysteresis model identification by the metric-topological evolutionary optimization,” IEEE Transactions on Magnetics, vol. 50, pp. 621-624, 2014.
[39]K. Kiran, S. T, A. A. Singh, N. Begum, R. R, P. D. Shenoy, et al., “Performance analysis of bee-hive routing in multi-radio networks,” in 2014 IEEE International Advance Computing Conference (IACC), 2014, pp. 360-364.
[40]W. Hu, J. Gao, Y. Wang, O. Wu, and S. Maybank, “Online adaboost-based parameterized methods for dynamic distributed network intrusion detection,” IEEE Transactions on Cybernetics, vol. 44, pp. 66-82, 2014.
[41]S. K. Goudos, K. Siakavara, and J. N. Sahalos, “Novel spiral antenna design using artificial bee colony Optimization for UHF RFID applications,” IEEE Antennas and Wireless Propagation Letters, vol. 13, pp. 528-531, 2014.
[42]S. Chetty and A. O. Adewumi, “Comparison study of swarm intelligence techniques for the annual crop planning problem,” IEEE Transactions on Evolutionary Computation, vol. 18, pp. 258-268, 2014.
[43]M. Castillo-Cagigal, E. Matallanas, I. n. Navarro, E. ı. Caama˜no-Mart’ın, F. l. Monasterio-Huelin, and A. l. Gutie’rrez, “Variable threshold algorithm for division of labor analyzed as a dynamical system,” IEEE Transactions on Cybernetics, vol. PP, pp. 1-1, 2014.
[44]H. Bevrani, P. R. Daneshmand, P. Babahajyani, Y. Mitani, and T. Hiyama, “Intelligent LFC concerning high penetration of wind power: synthesis and real-time application,” IEEE Transactions on Sustainable Energy, vol. 5, pp. 655-662, 2014.
[45]B. Anand, I. Aakash, Akshay, V. Varrun, M. K. Reddy, T. Sathyasai, et al., “Improvisation of particle swarm optimization algorithm,” in 2014 International Conference on Signal Processing and Integrated Networks (SPIN), 2014, pp. 20-24.
[46]Y. Okamoto, Y. Tominaga, S. Wakao, and S. Sato, “Topology optimization of rotor core combined with identification of current phase angle in IPM motor using multistep genetic algorithm,” IEEE Transactions on Magnetics, vol. 50, pp. 725-728, 2014.
[47]M. J. Neath, A. K. Swain, U. K. Madawala, and D. J. Thrimawithana, “An optimal PID controller for a bidirectional inductive power transfer system using multiobjective genetic algorithm,” IEEE Transactions on Power Electronics, vol. 29, pp. 1523-1531, 2014.
[48]T. Ishikawa, K. Nakayama, N. Kurita, and F. P. Dawson, “Optimization of rotor topology in PM synchronous motors by genetic algorithm considering cluster of materials and cleaning procedure,” IEEE Transactions on Magnetics, vol. 50, pp. 637-640, 2014.
[49]K. Chandrasekaran and G. S. Punekar, “Use of genetic algorithm to determine lightning channel-base current-function parameters,” IEEE Transactions on Electromagnetic Compatibility, vol. 56, pp. 235-238, 2014.
[50]S. M. R. Islam, M. A. Ahsan, and B. C. Ghosh, “Optimization of power system operation with static var compensator applying ACO algorithm,” in 2013 International Conference on Electrical Information and Communication Technology (EICT), 2014, pp. 1-6.
[51]P. GaneshKumar, C. Rani, D. Devaraj, and T. A. A. Victoire, “Hybrid ant bee algorithm for fuzzy expert system based sample classification,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. PP, pp. 1-1, 2014.
[52]F. Xhafa, X. Herrero, A. Barolli, and M. Takizawa, “A simulated annealing algorithm for ground station scheduling problem,” in 2013 16th International Conference on Network-Based Information Systems (NBiS), 2013, pp. 24-30.
[53]W. Zhongjie, Z. Mingming, and H. Miao, “Study of the immune simulated annealing algorithm and dual-resource job shop order scheduling,” in 2013 25th Chinese Control and Decision Conference (CCDC), 2013, pp. 2375-2379.
[54]X. Wang, M. Zhang, and Y. Yang, “3D face registration on simulated annealing algorithm,” in 2013 International Conference on Information Science and Technology (ICIST), 2013, pp. 647-651.
[55]W. Tao and Y. Huang, “Research on disposal station location problem based on genetic and simulated annealing algorithm,” in 2013 Fifth International Conference on Computational and Information Sciences (ICCIS), 2013, pp. 1897-1900.
[56]S. Sakamoto, T. Oda, E. Kulla, M. Ikeda, L. Barolli, and F. Xhafa, “Performance analysis of WMNs using simulated annealing algorithm for different temperature values,” in 2013 Seventh International Conference on Complex, Intelligent, and Software Intensive Systems (CISIS), 2013, pp. 164-168.
[57]L. Rong and C. Mou, “Flight control law evaluation for UAV based on simulated annealing algorithm,” in 2013 32nd Chinese Control Conference (CCC), 2013, pp. 8697-8702.
[58]L. Xu, L. Yanpeng, and J. Xuan, “Based on Tabu Search and Particle Swarm Optimization Algorithms Solving Job Shop Scheduling Optimization Problems,” in 2013 Fourth International Conference on Digital Manufacturing and Automation (ICDMA), 2013, pp. 322-324.
[59]J. Tongpang and P. Tantatsanawong, “An Application of Tabu Search Algorithms and Genetic Algorithms in Collaborative Logistics Optimization,” in 2011 Annual SRII Global Conference (SRII), 2011, pp. 699-706.
[60]C.-h. Guan, Y. Cao, and J. Shi, “Tabu search algorithm for solving the vehicle routing problem,” in 2010 Third International Symposium on Information Processing (ISIP), 2010, pp. 74-77.
[61]J. Yang, H. Zhang, Y. Ling, C. Pan, and W. Sun, “Task allocation for wireless sensor network using modified binary particle swarm optimization,” IEEE Sensors Journal, vol. 14, pp. 882-892, 2014.
[62]W. Xian, B. Long, M. Li, and H. Wang, “Prognostics of Lithium-Ion Batteries Based on the Verhulst Model, Particle Swarm Optimization and Particle Filter,” IEEE Transactions on Instrumentation and Measurement, vol. 63, pp. 2-17, 2014.
[63]J. Qi, B. Guo, H. Lei, and T. Zhang, “Solving resource availability cost problem in project scheduling by pseudo particle swarm optimization,” Journal of Systems Engineering and Electronics, vol. 25, pp. 69-76, 2014.
[64]J. J. Lake, A. E. Duwel, and R. N. Candler, “Particle swarm optimization for design of slotted MEMS resonators with low thermoelastic dissipation,” Journal of Microelectromechanical Systems, vol. 23, pp. 364-371, 2014.
[65]P. Kitak, A. Glotic, and I. Ticar, “Heat transfer coefficients determination of numerical model by using particle swarm optimization,” IEEE Transactions on Magnetics, vol. 50, pp. 933-936, 2014.
[66]M. Gong, Q. Cai, X. Chen, and L. Ma, “Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 18, pp. 82-97, 2014.
[67]P. Ghamisi, M. S. Couceiro, F. M. L. Martins, and J. A. Benediktsson, “Multilevel image segmentation based on fractional-order darwinian particle swarm optimization,” IEEE Transactions on Geoscience and Remote Sensing, vol. 52, pp. 2382-2394, 2014.
[68]“最佳化方法, ” 參考網頁http://ntou-sdol.weebly.com/2636820339212702604127861.html
[69]“PSO 粒子群演算法, ” 參考網頁http://www.dotblogs.com.tw/dragon229/archive/2013/01/10/87127.aspx