مسیریابی ربات با استفاده از الگوریتم انتخاب کلونال
محورهای موضوعی : مهندسی برق و کامپیوتر
سید علی دانش نیا
1
,
شهرام گلزاري
2
*
,
عباس حریفی
3
,
عباسعلی رضائی
4
1 - دانشگاه پیام نور مرکز قشم
2 - دانشگاه هرمزگان
3 - دانشگاه هرمزگان
4 - دانشگاه پیام نور تهران
کلید واژه: ربات سیارالگوریتم انتخاب کلونالطرح‌ریزی مسیرمسیریابی,
چکیده مقاله :
مسیریابی ربات یکی از موضوعات مهم در مبحث رباتیک سیار است. هدف، پیداکردن یک مسیر پیوسته از یک موقعیت اولیه به یک مقصد نهایی است به طوری که عاری از برخورد بوده و بهینه یا نزدیک به بهینه نیز باشد. از آنجایی که مسئله مسیریابی ربات از نوع مسایل بهینه‌سازی است، می‌توان از الگوریتم‌های تکاملی برای حل این مسئله استفاده نمود. امروزه الگوریتم انتخاب کلونال به علت داشتن ویژگی‌های محاسباتی ارزنده به دفعات برای حل مسایل مورد استفاده قرار گرفته است، اما در زمینه استفاده از این روش برای حل مسئله مسیریابی ربات تلاش‌های بسیار کمی انجام شده است. اندک تلاش‌های انجام‌گرفته نیز در واقع نوعی الگوریتم ژنتیک بهبودیافته می‌باشند. در این پژوهش با بهره‌گیری از تمام ویژگی‌های الگوریتم کلونال روشی کارا برای مسیریابی ربات در حضور موانع طراحی شده است. روش ارائه‌شده در محیط‌های متنوع و با اجراهای مختلف از نظر معیارهای طول مسیر پیشنهادی و تعداد نسل‌های لازم برای تولید مسیر مورد ارزیابی قرار می‌گیرد. بر اساس نتایج حاصل از آزمایش‌های متعدد، روش ارائه‌شده عملکرد بهتری نسبت به الگوریتم ژنتیک در تمامی محیط‌ها و همه پارامترهای ارزیابی از خود نشان می‌دهد. به‌خصوص با افزایش تعداد رئوس موانع و نیز موانع مقعر، روش پیشنهادی عملکرد بسیار بهینه‌تری در مقایسه با الگوریتم ژنتیک از خود نشان می‌دهد. همچنین مقایسه عملکرد روش پیشنهادی با الگوریتم ترکیبی جغرافیای زیستی-ازدحام ذرات بیانگر برتری الگوریتم مسیریابی مبتنی بر انتخاب کلونال هست.
Path planning of mobile robot is one of the most important topics in mobile robotic discussion. The aim of this study is to find a continuous path from an initial position to the final target; So that, it should be free of collision and optimal or near to optimal. Since path planning problem of robot is one type of optimization problems, the evolutionary algorithms can be used to solve this problem. Nowadays, clonal selection algorithm is frequently used to solve the problems because of having valuable computational characteristics. But very little attempts have been done in the field of using this method to solve robot path planning problem. Few accomplished attempts are actually a kind of improved genetic algorithm. In this research, an efficient method for robot path planning in the presence of obstacles is designed using all the features of the clonal selection algorithm. The proposed method is evaluated in various environments with different runs in terms of the proposed path length criteria and the number of generations needed to generate the path. Based on the results of experiments, the proposed method shows better performance than the genetic algorithm in all environments and all the evaluation parameters. Especially, by increasing the number of obstacles vertices and also concave obstacles, the proposed method shows much more efficient performance than the genetic algorithm. Also, comparing the performance of the proposed method with the BPSO algorithm (presented in another study) indicates the superiority of path planning algorithm based on the clonal selection.
[1] J. C. Latombe, Robot Motion Planning, Springer, pp. 100-107, 1991.
[2] D. J. Cook, "Adding intelligence to robot arm path planning using a graph-match analogical reasoning system," in Proc. of the lEEE/RSJ Int.l Conf. on Intelligent Robots and Systems, pp. 657-662, Raleigh, NC, USA, 7-10 Jul. 1992.
[3] H. Miao and Y. C. Tian, "Robot path planning in dynamic environments using a simulated annealing based approach," in Proc. 10th Int. Conf. on Control, Automation, Robotics and Vision, ICARCV'08, pp. 1253-1258, Hanoi, Vietnam, 17-20 Dec. 2008.
[4] H. M. Choset, Principles of Robot Motion: Theory, Algorithms, and Implementation, MIT Press, 2005.
[5] E. Masehian and D. Sedighizadeh, "Classic and heuristic approaches in robot motion planning-a chronological review," World Academy of Science, Engineering and Technology, vol. 23, no. 5, pp. 255-260, 2007.
[6] T. Back, Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press, 1996.
[7] H. C. Huang, "Intelligent motion control for omnidirectional mobile robots using ant colony optimization," Applied Artificial Intelligence, vol. 27, no. 3, pp. 151-169, 2013.
[8] M. A. Contreras-Cruz, V. Ayala-Ramirez, and U. H. Hernandez-Belmonte, "Mobile robot path planning using artificial bee colony and evolutionary programming," Applied Soft Computing, vol. 30, pp. 319-328, May 2015.
[9] N. Zeng, H. Zhang, Y. Chen, B. Chen, Y. Liu, and B. Shen, "Path planning for intelligent robot based on switching local evolutionary PSO algorithm," Assembly Automation, vol. 36, no. 2, pp. 120-126, 2016.
[10] M. Reza, S. K. Satapathy, S. Pattnaik, and D. R. Panda, "Optimized point robot path planning in cluttered environment using GA," in Proc. of Fifth Int. Conf. on Soft Computing for Problem Solving, vol.436, pp. 475-485, 2016.
[11] W. Qu, S. Jia, and X. Zhao, "Environment exploration and recognition for mobile robot using immune algorithm and objectness measure," in Proc. IEEE Int. Conf. on Mechatronics and Automation, ICMA'15, pp. 2226-2231, Beijing, China, 2-5 Aug. 2015.
[12] J. H. Walker and S. M. Garrett, "Dynamic function optimisation: comparing the performance of clonal selection and evolution strategies," in Proc. Int. Conf. Artificial Immune Systems, ICARIS'03, pp. 273-284, 2003.
[13] G. C. Silva and D. Dasgupta, A Survey of Recent Works in Artificial Immune Systems, in Handbook on Computational Intelligence: vol. 2, Evolutionary Computation, Hybrid Systems, and Applications, Ed: World Scientific, pp. 547-586, 2016.
[14] A. Raza and B. R. Fernandez, "Immuno-inspired robotic applications: a review," Applied Soft Computing, vol. 37, pp. 490-505, 2015.
[15] X. Hu, "Clonal selection based mobile robot path planning," in Proc. IEEE Int. Conf. on Automation and Logistics, ICAL'08, pp. 437-442, Qingdao, China, 1-3 Sept. 2008.
[16] L. Wang and B. Hirsbrunner, "An evolutionary algorithm with population immunity and its application on autonomous robot control," in Proc. Congress on Evolutionary Computation, CEC'03, the vol. 1, pp. 397-404, Canberra, Australia, 2003.
[17] N. K. Jerne, "The immune system," Scientific American, vol. 229, no. 1, pp. 52-63, Jul. 1973.
[18] C. A. Janeway, "The immune system evolved to discriminate infectious nonself from noninfectious self," Immunology Today, vol. 13, no. 1, pp. 11-16, 1992.
[19] M. D. Mannie, "Immunological self/nonself discrimination," Immunologic Research, vol. 19, no. 1, pp. 65-87, Feb. 1999.
[20] P. Marrack and J. W. Kappler, "How the immune system recognizes the body," Scientific American, vol. 269, no. 3, pp. 80-89, Sept. 1993.
[21] J. D. Farmer, N. H. Packard, and A. S. Perelson, "The immune system, adaptation, and machine learning," Physica D: Nonlinear Phenomena, vol. 22, no. 1-3, pp. 187-204, Oct./Nov. 1986.
[22] A. A. Freitas and J. Timmis, "Revisiting the foundations of artificial immune systems for data mining," IEEE Trans. on Evolutionary Computation, vol. 11, no. 4, pp. 521-540, Aug. 2007.
[23] Y. Tenne and S. W. Armfield, "A novel evolutionary algorithm for efficient minimization of expensive black-box functions with assisted-modelling," in Proc. IEEE Congress on Evolutionary Computation, CEC'06, pp. 3219-3226, Vancouver, BC, Canada, 16-21 Jul. 2006.
[24] L. Xu, M. Y. Chow, J. Timmis, and L. S. Taylor, "Power distribution outage cause identification with imbalanced data using artificial immune recognition system (AIRS) algorithm," IEEE Trans. on Power Systems, vol. 22, no. 1, pp. 198-204, Feb. 2007.
[25] J. Greensmith, U. Aickelin, and S. Cayzer, "Introducing dendritic cells as a novel immune-inspired algorithm for anomaly detection," Artificial Immune Systems, vol. 3267, pp. 153-167, 2005.
[26] E. Hart and J. Timmis, "Application areas of AIS: the past, the present and the future," Applied Soft Computing, vol. 8, no. 1, pp. 191-201, Jan. 2008.
[27] Y. Zhong, L. Zhang, J. Gong, and P. Li, "A supervised artificial immune classifier for remote-sensing imagery," IEEE Trans. on Geoscience and Remote Sensing, vol. 45, no. 12, pp. 3957-3966, Dec. 2007.
[28] U. Aickelin and S. Cayzer, "The danger theory and its application to artificial immune systems," arXiv preprint arXiv: 0801.3549, 2008.
[29] M. Ayara, J. Timmis, R. de Lemos, L. N. de Castro, and R. Duncan, "Negative selection: how to generate detectors," in Proc. of the 1st Int. Conf. on Artificial Immune Systems, ICARIS'02, pp. 89-98, Canterbury, UK, Sept. 2002.
[30] L. N. De Castro and F. J. Von Zuben, "Learning and optimization using the clonal selection principle," IEEE Trans. on Evolutionary Computation, vol. 6, no. 3, pp. 239-251, Jun. 2002.
[31] A. Coutinho, "The network theory: 21 years later," Scandinavian J. of Immunology, vol. 42, no. 1, pp. 3-8, Jul. 1995.
[32] J. Kim and P. J. Bentley, "Immune memory in the dynamic clonal selection algorithm," in Proc. of the 1st Int.l Conf. on Artificial Immune Systems, ICARIS'02, vol. 1, pp. 59-67, Canterbury, UK, Sept. 2002.
[33] J. Kim and P. J. Bentley, "A model of gene library evolution in the dynamic clonal selection algorithm," in Proc. of the 1st Int. Conf. on Artificial Immune Systems, ICARIS'02, pp. 175-182, Canterbury, UK, Sept. 2002.
[34] A. Secker, A. A. Freitas, and J. Timmis, "AISEC: an artificial immune system for e-mail classification," in Proc. The Congress on Evolutionary Computation, CEC'03, vol. 1, pp. 131-138, Dec. 2003.
[35] J. Timmis, T. Knight, L. N. de Castro, and E. Hart, Computation in Cells and Tissues, Berlin: Springer, pp.51-91, 2004.
[36] R. Larson and R. P. Hostetler, Precalculus: A Concise Course: Cengage Learning, 2006.
[37] L. Deng, X. Ma, J. Gu, and Y. Li, "Mobile robot path planning using polyclonal-based artificial immune network," J. of Control Science and Engineering, vol. 2013, Article ID 416715, 13 pp., 2013.
[38] C. Huizar, O. Montiel-Ross, R. Sepulveda, and F. J. D. Delgadillo, "Path planning using clonal selection algorithm," Recent Advances on Hybrid Intelligent Systems, vol. 451, pp. 303-312, 2013.
[39] H. Miao and Y. C. Tian, "Dynamic robot path planning using an enhanced simulated annealing approach," Applied Mathematics and Computation, vol. 222, pp. 420-437, Oct. 2013.
[40] H. Mo and L. Xu, "Research of biogeography particle swarm optimization for robot path planning," Neurocomputing, vol. 148, pp. 91-99, Jan. 2015.