برنامه‌ریزی مسیر پهپادها در فضای سه بعدی مبتنی بر الگوریتم بهینه‌سازی پروانه

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری / دانشکده مهندسی برق و کامپیوتر، دانشگاه کاشان

2 عضو هیات علمی / دانشکده مهندسی برق و کامپیوتر، دانشگاه کاشان

چکیده

تحقیقات بسیاری در زمینه برنامه‌ریزی مسیر به عنوان یکی از مهم‌ترین مسائل در پهپادها انجام شده است که باتوجه به شرایط و محدودیت‌های موجود، نتایج مختلفی به همراه داشته است. در این پژوهش از یک الگوریتم پیشنهادی موثر مبتنی بر الگوریتم بهینه‌سازی پروانه استفاده شده که دارای یک تابع مطلوبیت و قابلیت بهینه‌سازی همزمان چند پاسخ است. وجه تمایز BOA نسبت به سایر الگوریتم‌های فراابتکاری آن است که هر پروانه با ترکیب اطلاعات به دست آمده از گیرنده‌های مختلف حسی‌، برازش منحصر به خود را در مسیر تولید کرده و از این جهت توانایی خوبی در حل مسائل چندهدفه دارد. در این نوشتار از یک تابع هدف سه‌بعدی به منظور محاسبه طول کوتاه‌ترین مسیر، شدت برخورد با موانع، جلوگیری از تصادم و افزایش توان عملیاتی پهپاد که تابعی از میزان انرژی مصرف شده است، استفاده خواهد شد. همچنین مفهوم عامل پرتاب هوشمند استفاده شده در این الگوریتم همزمان باعث جلوگیری از گیر افتادن در بهینه‌های محلی و افزایش سطح پوشش شبکه در فرایند مسیریابی می‌شود. این عامل پرتاب با استفاده از تکنیک‌های هندسی و منحنی میزان، مانع از برخورد پهپاد با موانع می شود. عملکرد الگوریتم پیشنهادی با روش‌های کلونی مورچه و بهینه‌سازی ازدحام ذرات به عنوان کاربردی‌ترین الگوریتم‌های فراابتکاری مقایسه شده است. نتایج نشان می‌دهد، الگوریتم BOA در مقایسه با دو الگوریتم دیگر، در بهترین حالت، دارای کمترین هزینه و در بدترین حالت، دومین کمترین هزینه را داشته است. هم‌چنین BOA از نظر مدت زمان اجرا و مقدار بهینه تابع برازش، به نسبت دو الگوریتم دیگر عملکرد بهتری دارد.

کلیدواژه‌ها


عنوان مقاله [English]

UAV path planning based on butterfly optimization algorithm in three-dimensional space

نویسندگان [English]

  • Hakimeh Mazaheri 1
  • salman goli 2
1 Kashan University
2 Kashan University
چکیده [English]

Much studied have addressed Path planning as one of the main topics in unmanned aerial vehicles; which has yielded different results due to the existing conditions and limitations. To this end, the present study proposed an efficient algorithm underpinned by the propeller optimization algorithm, which had a utility function and could optimize multiple responses simultaneously. BOA is different from other meta-heuristic algorithms as each propeller produces its own unique fit in the path by combining information extracted from different sensory receptors. Accordingly, BOA can solve multi-objective problems. A 3D objective function was used in this study to estimate the length of the shortest path and the intensity of collisions with obstacles, avoid collisions and enhance UAVs’ operational capacity as a function of consumed energy. Furthermore, A smart launcher factor was also included in this algorithm to prevent trapping in local optimizations and promote network coverage in the routing process at the same time. The launcher prevents collision with obstacles in UAVs by adopting geometric techniques and the contour line. The performance of the proposed algorithm was compared with that of the most practical meta-heuristic algorithms (namely ACO and PSO methods). The findings revealed that the BOA algorithm compared to the other two algorithms had the lowest cost and the second lowest cost under the best and worst conditions, respectively. The findings also confirmed the better performance of BOA than the other two algorithms regarding execution time and the optimal value of the fit function.

کلیدواژه‌ها [English]

  • Unmanned Aerial Vehicles
  • Path Planning
  • Butterfly Optimization Algorithm
  • 3 Dimension.collision avoidance
[1] J. Sánchez-García, D. G. Reina, and S. L. Toral, ‘‘A distributed PSO-based exploration algorithm for a UAV network assisting a disaster scenario,’’Future Gener. Comput. Syst., vol. 90, pp. 129–148, Jan. 2019. doi:10.1016/j.future.2018.07.048.
[2] T. Kopfstedt, M. Mukai, M. Fujita, and C. Ament, ‘‘Control of formations of UAVs for surveillance and reconnaissance missions,’’IFAC Proc.Volumes, vol. 41, no. 2, pp. 5161–5166, 2008. doi:10.3182/20080706-5-kr-1001.00867.99716VOLUME 7, 2019.
[3] D. Bein, W. Bein, A. Karki, and B. B. Madan, ‘‘Optimizing border patrol operations using unmanned aerial vehicles,’’ in Proc. 12th Int.Conf. Inf. Technol.-Generations, Apr. 2015, pp. 479–484. doi:10.1109/itng.2015.83.
[4] R. R. Pitre, X. R. Li, and R. Delbalzo, ‘‘UAV route planning for joint search and track missions—An information-value approach,’’IEEE Trans. Aerosp. Electron. Syst., vol. 48, no. 3, pp. 2551–2565, Jul. 2012.doi: 10.1109/taes.2012.6237608.
[5] C. Barrado, R. Messeguer, J. Lopez, E. Pastor, E. Santamaria, and P. Royo, ‘‘Wildfire monitoring using a mixed air-ground mobile net-work,’’IEEE Pervasive Comput., vol. 9, no. 4, pp. 24–32, Oct./Dec. 2010.doi: 10.1109/mprv.2010.54.
[6] E. Semsch, M. Jakob, D. Pavlicek, and M. Pechoucek, ‘‘Autonomous UAV surveillance in complex urban environments,’’ inProc.IEEE/WIC/ACM Int. Joint Conf. Web Intell. Intell. Agent Technol.,Sep. 2009, pp. 82–85. doi:10.1109/wi-iat.2009.132.
[7] F. Jiang and A. Lee Swindle hurst, ‘‘Dynamic UAV relay positioning for the ground-to-air uplink,’’ in Proc. IEEE GLOBECOM Work shops,Dec. 2010, pp. 1766–1770. doi:10.1109/glocomw.2010.5700245.
[8] S. A. Vollgger and A. R. Cruden, ‘‘Mapping folds and fractures in basement and cover rocks using UAV photogrammetry, Cape Liptrap and Cape Paterson, Victoria, Australia,’’J. Struct. Geol., vol. 85, pp. 168–187,Apr. 2016. doi:10.1016/j.jsg.2016.02.012
[9] PwC, “Global market for commercial applications of drone technology valued at over 127bn,” (Accessed on February 2018). [Online]. Available:https://press.pwc.com.
[10] S. D. Intelligence, “The global UAV payload market 2017-2027,”(Accessed on February 2018). [Online]. Available: https://www.researchandmarkets.com/research/nfpsbm/the\_global\_uav.
[11] M. Ferry, Z. Tu, L. Stephens, G. Prickett, Towards true uav autonomy, in: 2007 Information, Decision and Control,IEEE, 2007, pp. 170–175.
[12] T.Omkar , G. Jugal, " A game theoretic approach to UAV routing and information collection" , M.S. Thesis, University of Illinois at Urbana-Champaign, 2017.
[13] H. Chen, X.-m. Wang, Y. Li, A survey of autonomous control for uav, in: 2009 International Conference on Artificial Intelligence and Computational Intelligence, Vol. 2, IEEE, 2009, pp. 267–271.
[14] S. Hrabar, 3d path planning and stereo-based obstacle avoidance for rotorcraft uavs, in: 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, 2008, pp. 807–814.
[15] Z. W. Geem, J. H. Kim, G. V. Logana than, A new heuristic optimization algorithm: harmony search, simulation 76 (2)(2001) 60–68.
[16] Arora, S., Singh, S. Butterfly optimization algorithm: a novel approach for global optimization. Soft Comput 23, 715–734 (2019). https://doi.org/10.1007/s00500-018-3102-4.
[17] S. Aggarwal and N. Kumar, Path planning techniques for unmannedaerial vehicles: A review, solutions, and challenges, Computer Communications (2019), doi:https://doi.org/10.1016/j.comcom.2019.10.014.
[18] K. Yang, S. Sukkarieh, 3d smooth path planning for a uav in cluttered natural environments, in: 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, 2008, pp. 794–800.
[19] Wang, Han et al. “On optimal path planning for UAV based patrolling in complex 3D topographies.” 2016 IEEE International Conference on Information and Automation (ICIA) (2016): 986-990.
[20] R. Geraerts, Planning short paths with clearance using explicit corridors, in: 2010 IEEE International Conference on Robotics and Automation, IEEE, 2010, pp. 1997–2004.
[21] R. DuToit, M. Holt, M. Lyle, S. Biaz, Uav collision avoidance using rrt* and los maximization technical report# csse12-03.
[22] S. Koenig, M. Likhachev, Improved fast replanning for robot navigation in unknown terrain, in: Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No. 02CH37292), Vol. 1, IEEE, 2002, pp. 968–975.
[23] A. Nash, S. Koenig, C. Tovey, Lazy theta*: Any-angle path planning and path length analysis in 3d, in: Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010.
[24] Hrabar, 3d path planning and stereo-based obstacle avoidance for rotorcraft uavs, in: 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, 2008, pp. 807–814.
[25] W. Geem, J. H. Kim, G. V. Logana than, A new heuristic optimization algorithm: harmony search, simulation 76 (2)(2001) 60–68.
[26] Arora, S., Singh, S. Butterfly optimization algorithm: a novel approach for global optimization. Soft Comput 23, 715–734 (2019). https://doi.org/10.1007/s00500-018-3102-4.
[27] Ji, Q. Hua, C. Li, J. Tang, A. Wang, X. Chen, D. Fang, 2-optaco: An improvement of ant colony optimization for uav path in disaster rescue, in: Networking and Network Applications (NaNA), 2017 International Conference on, IEEE, 2017, pp. 225–231.
[28] L.Yue and H.Chen, Unmanned vehicle path planning using anovel ant colony algorithm, EURASIP Journal on Wireless Communications and Networking (2019) 2019:136 https://doi.org/10.1186/s13638-019-1474-5.
[29] Ning, Q. Zhang, C. Zhang, et al., A best-path-updating information -guided ant colony optimization algorithm. Inf. Sci. s 433–434, 142–162 (2018)/
[30] Kirsal Ever, Yoney. (2017). Using simplified swarm optimization on path planning for intelligent mobile robot. Procedia Computer Science. 120. 83-90. 10.1016/j.procs.2017.11.213.
[31] Geng, Q. and Zhao, Z. 2013. A kind of route planning method for UAV based on improved PSO algorithm. 25th Chinese Control and Decision Conference (CCDC), 2328--2331.
[32] S. A. Gautam and N. Verma, "Path planning for unmanned aerial vehicle based on genetic algorithm & artificial neural network in 3D," 2014 International Conference on Data Mining and Intelligent Computing (ICDMIC), 2014, pp. 1-5, doi: 10.1109/ICDMIC.2014.6954257.
[33] Sonmez, E. Kocyigit and E. Kugu, "Optimal path planning for UAVs using Genetic Algorithm," 2015 International Conference on Unmanned Aircraft Systems (ICUAS), 2015, pp. 50-55, doi: 10.1109/ICUAS.2015.7152274.
[34] Cekmez, M. Ozsiginan, O.K. Sahingoz, "Adapting the GA approach to solve Traveling Salesman Problems on CUDA architecture", 14th IEEE International Symposium on Computational Intelligence and Informatics (CINTI 2013), pp. 423-428, 2013.
[35] Choueiry, M. Owayjan, H. Diab and R. Achkar, "Mobile Robot Path Planning Using Genetic Algorithm in a Static Environment," 2019 Fourth International Conference on Advances in Computational Tools for Engineering Applications (ACTEA), pp. 1-6.2019.
[36] D. M. Pierre, N. Zakaria, and A. J. Pal, “Master-slave parallel vector-evaluated genetic algorithm for unmanned aerial vehicle's path planning,” in Proceedings of the 11th International Conference on Hybrid Intelligent Systems (HIS '11), pp. 517–521, Malacca, Malaysia, December 2011.
[37] F. C. J. Allaire, M. Tarbouchi, G. Labonté, and G. Fusina, “FPGA implementation of genetic algorithm for UAV real-time path planning,” Journal of Intelligent and Robotic Systems, vol. 54, no. 1–3, pp. 495–510, 2009.
[38] A. P. Garcia, O. Montiel, O. Castillo, R. Sepúlveda, and P. Melin, “Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation,” Applied Soft Computing, vol. 9, no. 3, pp. 1102–1110, 2009.
[39] A. Jevtić, D. Andina, A. Jaimes, J. Gomez, and M. Jamshidi, “Unmanned aerial vehicle route optimization using ant system algorithm,” in Proceedings of the 5th International Conference on System of Systems Engineering (SoSE '10), pp. 1–6, Loughborough, UK, June 2010.
[40]  R. Samar and A. Rehman, “Autonomous terrain-following for unmanned air vehicles,” Mechatronics, vol. 21, no. 5, pp. 844–860, 2011.