الگوریتم جستجوی گرانشی با کدگذاری حرکت برای جستجوی هدف با استفاده از پهپادها

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

نویسندگان

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

2 استادیار، گروه کامپیوتر، دانشگاه لرستان، لرستان، ایران

چکیده

در این مقاله یک الگوریتم جدید به نام الگوریتم جستجوی گرانشی با کدگذاری حرکت برای یافتن هدف متحرک با استفاده از هواپیمای بدون سرنشین (پهپاد) ارائه می‌شود. با استفاده از قوانین فیزیک و ویژگی‌های زمین، هر بعد بر اساس نوع متغیر، معادله حرکت خود را دارد. بسیاری از روش‌های اکتشافی سنتی نمی‌توانند در فضاهای با ابعاد بالا برای جستجوی هدف متحرک به راه‌حل مطلوب برسند. فرایند بهینه‌سازی الگوریتم جستجوی گرانشی که بر اساس فعل‌وانفعال گرانشی بین ذره‌ها است، وابستگی به فاصله و ارتباط بین مقادیر جرم و محاسبه برازندگی، این الگوریتم را منحصربه‌فرد می‌کند. در این مقاله، الگوریتم پیشنهادی برای حل مشکل چالش پیچیدگی مسیر به‌منظور یافتن هدف متحرک از طریق کدگذاری حرکت با استفاده از پهپاد ارائه‌شده است. مجموعه‌ای از ذره‌ها در مسیر حرکت برای جستجوی هدف، از طریق ثابت گرانش، عامل وزن، نیرو و فاصله که با بسیاری از سناریوهای جستجو در یک الگوریتم جستجوی گرانشی تکامل‌یافته، به یک راه‌حل نزدیک به بهینه خواهد رسید. این روش کدگذاری شده برای حرکت، امکان حفظ ویژگی‌های مهم ذرات ازجمله حرکت به سمت بهینه سراسری را فراهم می-سازد. نتایج حاصل از شبیه‌سازی با روش موجود نشان می‌دهد که الگوریتم پیشنهادی، عملکرد تشخیص را 12% و عملکرد زمان را 71/1 برابر در مقایسه با APSO بهبود می‌بخشد. علاوه بر این، از دیگر الگوریتم‌های بهینه‌سازی فرا ابتکاری پیشرفته از جمله الگوریتم ژنتیک بهتر عمل می‌کند.

کلیدواژه‌ها


Smiley face

[1] F. Bourgault, T. Furukawa, & H. F. Durrant-Whyte, “Optimal Search for a Lost Target in a Bayesian World,” in Field and Service Robotics, vol. 24, S. Yuta, H. Asama, E. Prassler, T. Tsubouchi, and S. Thrun, Eds. Berlin/Heidelberg: Springer-Verlag, pp. 209-222, 2010.
[2] S. F. Ochoa & R. Santos, “Human-centric wireless sensor networks to improve information availability during urban search and rescue activities,” Inf. Fusion, vol. 22, pp. 71-84, 2015.
[3] M. D. Phung & Q. P. Ha, “Motion-encoded particle swarm optimization for moving target search using UAVs,” Appl. Soft Comput., vol. 97, pp. 106-705, 2020.
[4] Raap Manon, Meyer-Nieberg Silja, Pickl Stefan, & Zsifkovits Martin, “Aerial Vehicle Search-Path Optimization,” J. Optim. Theory Appl., 2017.
[5] F. Farivar & M. A. Shoorehdeli, “Stability analysis of particle dynamics in gravitational search optimization algorithm,” Inf. Sci., vol. 33, pp. 25-43, 2016.
[6] E. Rashedi, H. Nezamabadi-pour, & S. Saryazdi, “GSA: A Gravitational Search Algorithm,” Inf. Sci., vol. 179, no. 13, pp. 2232-2248, 2011.
[7] S. Tabatabaei, “A new gravitational search optimization algorithm to solve single and multiobjective optimization problems,” J. Intell. Fuzzy Syst., vol. 26, no. 2, pp. 993-1006, 2014.
[8] D. Pelusi, R. Mascella, & L. Tallini, “Revised Gravitational Search Algorithms Based on Evolutionary-Fuzzy Systems,” Algorithms, vol. 10, no. 2, p. 44, 2017.
[9] S. Perez-Carabaza, E. Besada-Portas, J. A. Lopez-Orozco, & J. M. de la Cruz, “Ant colony optimization for multi-UAV minimum time search in uncertain domains,” Appl. Soft Comput., vol. 62, pp. 789-806, 2018.
[10] R. Peng, “Joint routing and aborting optimization of cooperative unmanned aerial vehicles,” Reliab. Eng. Syst. Saf., vol. 177, pp. 131-137, 2018.
[11] M. Garraffa, M. Bekhti, L. Letocart, N. Achir, & K. Boussetta, “Drones path planning for WSN data gathering: A column generation heuristic approach,” pp. 1-6, 2018.
[12] B. J. Olivieri de Souza & M. Endler, “Evaluating flight coordination approaches of UAV squads for WSN data collection enhancing the internet range on WSN data collection,” J. Internet Serv. Appl., vol. 11, no. 1, 2020.
[13] K. E. Trummel & J. R. Weisinger, “Technical Note—The Complexity of the Optimal Searcher Path Problem,” Oper. Res., vol. 34, no. 2, pp. 324-327, 1986.
[14] D. S. Bernstein, R. Givan, N. Immerman, & S. Zilberstein, “The Complexity of Decentralized Control of Markov Decision Processes,” Math. Oper. Res., vol. 27, no. 4, pp. 819-840, 2010.
[15] R. M. C. Santiago, A. L. De Ocampo, A. T. Ubando, A. A. Bandala, & E. P. Dadios, “Path planning for mobile robots using genetic algorithm and probabilistic roadmap,” pp. 1-5, 2017.
[16] G. Flores-Caballero, A. Rodriguez-Molina, M. Aldape-Perez, & M. G. Villarreal-Cervantes, “Optimized Path-Planning in Continuous Spaces for Unmanned Aerial Vehicles Using Meta-Heuristics,” IEEE Access, vol. 8, pp. 176774-176788, 2020.
[17] M. Gendreau & J.-Y. Potvin, Eds., "Handbook of Metaheuristics," vol. 146. Boston, MA: Springer US, 2010.
[18] ‏I. H. Osman & G. Laporte, “Metaheuristics: A bibliography,” Ann. Oper. Res., vol. 63, no. 5, pp. 511-623, 1996.
[19] D.B Fogel, & Z Mich, "Handbook of Evolutionary Computation," Ann. Oper. Res., vol. 87, no. 9, pp. 251-320, 2021.
[20] A. Y. Zomaya, Ed., "Handbook of Nature-Inspired and Innovative Computing," Boston: Kluwer Academic Publishers, 2010.
[21] E. Rashedi, E. Rashedi, & H. Nezamabadi-pour, “A comprehensive survey on gravitational search algorithm,” Swarm Evol. Comput., vol. 41, pp. 141-158, 2018.
[22] C. Sean M., “Spacetime and Geometry: An Introduction to General Relativity,” ResearchGate. Appl. Soft Comput., vol. 97, pp. 207-877, 2021.
[23] M. Du, & Q. Ph, “Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization,” Inf. Sci., vol. 179, no. 13, pp. 2232-2248, 2020.
[24] M. Raap, S. Meyer-Nieberg, S. Pickl, & M. Zsifkovits, “Aerial Vehicle Search-Path Optimization: A Novel Method for Emergency Operations,” J. Optim. Theory Appl., vol. 172, no. 3, pp. 965-983, 2017.
[25] O. Avalos, “GSA for machine learning problems: A comprehensive overview,” Appl. Math. Model., vol. 92, pp. 261-280, 2021.
[26] S. K. Gan & S. Sukkarieh, “Multi-UAV target search using explicit decentralized gradient-based negotiation”, pp. 751-756, 2011.
[27] M. B. Dowlatshahi, H. Nezamabadi-pour, & M. Mashinchi, “A discrete gravitational search algorithm for solving combinatorial optimization problems,” Inf. Sci., vol. 258, pp. 94-107, 2014.
[28] F. Su, C. Duan, & R. Wang, “Analysis and improvement of GSA’s optimization process,” Appl. Soft Comput., vol. 107, pp. 107-367, 2021.
[29] D. Yulong et al., “Path Planning of Messenger UAV in Air-ground Coordination,” IFAC-Pap., vol. 50, no. 1, pp. 8045-8051, 2017.
[30] Y. Jiang, Q. Wu, G. Zhang, S. Zhu, & W. Xing, “A diversified group teaching optimization algorithm with segment-based fitness strategy for unmanned aerial vehicle route planning,” Expert Syst. Appl., vol. 185, pp. 115-690, 2021.
[31] V. T. Hoang, M. D. Phung, T. H. Dinh, & Q. P. Ha, “System Architecture for Real-Time Surface Inspection Using Multiple UAVs,” IEEE Syst. J., vol. 14, no. 2, pp. 2925-2936,  2020.
[32] S. Zhang & J. Ou, “BP-PSO-based intelligent case retrieval method for high-rise structural form selection,” Sci. China Technol. Sci., vol. 56, no. 4, pp. 940-944, 2013.
[33] H. Duan & C. Sun, “Pendulum-like oscillation controller for micro aerial vehicle with ducted fan based on LQR and PSO,” Sci. China Technol. Sci., vol. 56, no. 2, pp. 423-429, 2013.
[34] ‏Y. Chen & H. Duan, “Multiple UCAVs mission assignment based on modified Gravitational Search, pp. 540-545, 2014.
[35] J. Khalil Pour, M.Veisi & F. Rahimi, “Distributed control and control of the UAV network,” Scientific Journal of Electronic and Cyber., vol. 7, no. 4, pp. 117-129, 2020. (in persian)
دوره 10، شماره 4 - شماره پیاپی 40
شماره پیاپی 40، فصلنامه زمستان
بهمن 1401
صفحه 63-73
  • تاریخ دریافت: 20 بهمن 1400
  • تاریخ بازنگری: 27 فروردین 1401
  • تاریخ پذیرش: 18 مرداد 1401
  • تاریخ انتشار: 01 بهمن 1401