اختصاص وظایف و طراحی مسیر یکپارچه با وجود اهداف متحرک به روش برنامه‌ریزی خطی ابتکاری و منحنی‌های دابینز

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

نویسندگان

1 دانشگاه هوایی شهید ستاری- دانشکده هوافضا

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

چکیده

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

کلیدواژه‌ها


[1]        R. G. Grant, Flight: The Complete History of Aviation: DK; Updated, Revised edition (May 2, 2017), 2017.
[2]        T. Shima and C. Schumacher, Assigning cooperating UAVs to simultaneous tasks on consecutive targets using genetic algorithms, Journal of the Operational Research Society, vol. 60, pp. 973-982, 2009.
[3]        D. W. Casbeer and R. W. Holsapple, Column generation for a UAV assignment problem with precedence constraints, International Journal of Robust and Nonlinear Control, vol. 21, pp. 1421-1433, 2011.
[4]        C. Schumacher, P. R. Chandler, M. Pachter, and L. S. Pachter, Optimization of air vehicles operations using mixed-integer linear programming, Journal of the Operational Research Society, vol. 58, pp. 516-527, 2007.
[5]        Y. NI, D.-Y. ZHOU, Y.-h. MA, and B.-c. HE, The Air-to-Ground Tasks Assignment for Multi-UAV based Mixed Integer Linear Programming [J], Fire Control and Command Control, vol. 11, 2008.
[6]        J. Bellingham, Y. Kuwata, and J. How, "Stable receding horizon trajectory control for complex environments," in AIAA Guidance, Navigation, and Control Conference and Exhibit, p. 5635, 2003.
[7]        M. Gendreau, G. Laporte, and J.-Y. Potvin, "Metaheuristics for the capacitated VRP," in The vehicle routing problem, ed: SIAM, 2002, pp. 129-154.
[8]        M. Alighanbari, Task assignment algorithms for teams of UAVs in dynamic environments, Massachusetts Institute of Technology, 2004.
[9]        M. A. Darrah, W. Niland, and B. Stolarik, "Multiple UAV Task Allocation for an Electronic Warfare Mission Comparing Genetic Algorithms and Simulated Annealing (Preprint)," INSTITUTE FOR SCIENTIFIC RESEARCH FARIMONT WV2006.
[10]      E. Edison and T. Shima, Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms, Computers & Operations Research, vol. 38, pp. 340-356, 2011.
[11]      V. Shaferman and T. Shima, Unmanned aerial vehicles cooperative tracking of moving ground target in urban environments, Journal of guidance, control, and dynamics, vol. 31, pp. 1360-1371, 2008.
[12]      X. Fu, P. Feng, and X. Gao, Swarm UAVs Task and Resource Dynamic Assignment Algorithm Based on Task Sequence Mechanism, IEEE Access, vol. 7, pp. 41090-41100, 2019.
[13]      K. A. Ghamry, M. A. Kamel, and Y. Zhang, "Multiple UAVs in forest fire fighting mission using particle swarm optimization," in 2017 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 1404-1409, 2017.
[14]      J. Gu, T. Su, Q. Wang, X. Du, and M. Guizani, Multiple moving targets surveillance based on a cooperative network for multi-UAV, IEEE Communications Magazine, vol. 56, pp. 82-89, 2018.
[15]      A. T. Hafez and M. A. Kamel, Cooperative task assignment and trajectory planning of unmanned systems via hflc and pso, Unmanned Systems, vol. 7, pp. 65-81, 2019.
[16]      Z. Jia, J. Yu, X. Ai, X. Xu, and D. Yang, Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm, Aerospace Science and Technology, vol. 76, pp. 112-125, 2018.
[17]      X. Jiang, Q. Zhou, and Y. Ye, "Method of task assignment for UAV based on particle swarm optimization in logistics," in Proceedings of the 2017 International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence, pp. 113-117, 2017.
[18]      M. Zhu, X. Du, X. Zhang, H. Luo, and G. Wang, Multi-UAV Rapid-Assessment Task-Assignment Problem in a Post-Earthquake Scenario, IEEE Access, vol. 7, pp. 74542-74557, 2019.
[19]      X. Hu, H. Ma, Q. Ye, and H. Luo, Hierarchical method of task assignment for multiple cooperating UAV teams, Journal of Systems Engineering and Electronics, vol. 26, pp. 1000-1009, 2015.
[20]      Z. Zhao, J. Yang, Y. Niu, Y. Zhang, and L. Shen, A Hierarchical Cooperative Mission Planning Mechanism for Multiple Unmanned Aerial Vehicles, Electronics, vol. 8, p. 443, 2019.
[21]      Liu, Wei, Z. Zheng, and K.-Y. Cai, Bi-level programming based real-time path planning for unmanned aerial vehicles, Knowledge-Based Systems, vol. 44, pp. 34-47, 2013.
[22]      B. D. Song, K. Park, and J. Kim, Persistent UAV delivery logistics: MILP formulation and efficient heuristic, Computers & Industrial Engineering, vol. 120, pp. 418-428, 2018.
[23]      S. Perez-Carabaza, E. Besada-Portas, J. A. Lopez-Orozco, and M. Jesus, Ant colony optimization for multi-UAV minimum time search in uncertain domains, Applied Soft Computing, vol. 62, pp. 789-806, 2018.
[24]      Y. Chen, D. Yang, and J. Yu, Multi-UAV Task Assignment With Parameter and Time-Sensitive Uncertainties Using Modified Two-Part Wolf Pack Search Algorithm, IEEE Transactions on Aerospace and Electronic Systems, vol. 54, pp. 2853-2872, 2018.
[25]      E. Adamey, A. E. Oğuz, and Ü. Özgüner, Collaborative multi-msa multi-target tracking and surveillance: a divide & conquer method using region allocation trees, Journal of Intelligent & Robotic Systems, vol. 87, pp. 471-485, 2017.
[26]      W. Meng, Z. He, R. Su, P. K. Yadav, R. Teo, and L. Xie, Decentralized multi-UAV flight autonomy for moving convoys search and track, IEEE Transactions on Control Systems Technology, vol. 25, pp. 1480-1487, 2016.
[27]      H. Ergezer and M. Leblebicioğlu, "3D path planning for UAVs for maximum information collection. Unmanned Aircraft Systems (ICUAS)," in 2013 International Conference on, 2013.
[28]      O. Souissi, R. Benatitallah, D. Duvivier, A. Artiba, N. Belanger, and P. Feyzeau, "Path planning: A 2013 survey," in Proceedings of 2013 International Conference on Industrial Engineering and Systems Management (IESM), pp. 1-8, 2013.
[29]      D. González, J. Pérez, V. Milanés, and F. Nashashibi, A review of motion planning techniques for automated vehicles, IEEE Transactions on Intelligent Transportation Systems, vol. 17, pp. 1135-1145, 2015.
[30]      K. Ok, S. Ansari, B. Gallagher, W. Sica, F. Dellaert, and M. Stilman, "Path planning with uncertainty: Voronoi uncertainty fields," in 2013 IEEE International Conference on Robotics and Automation, pp. 4596-4601, 2013.
[31]      L. E. Dubins, On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents, American Journal of Mathematics, vol. 79, p. 497, Jul 1957.
[32]      J. Reeds and L. Shepp, Optimal paths for a car that goes both forwards and backwards, Pacific journal of mathematics, vol. 145, pp. 367-393, 1990.
[33]      L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE transactions on Robotics and Automation, vol. 12, pp. 566-580, 1996.
[34]      Y. Kuwata, A. Richards, T. Schouwenaars, and J. P. How, "Decentralized robust receding horizon control for multi-vehicle guidance," in 2006 American Control Conference, p. 6 pp., 2006.
[35]      T. R. Mehta and M. Egerstedt, An optimal control approach to mode generation in hybrid systems, Nonlinear Analysis: Theory, Methods & Applications, vol. 65, pp. 963-983, 2006.
[36]      G. Flores, I. Lugo-Cárdenas, and R. Lozano, "A nonlinear path-following strategy for a fixed-wing MAV," in 2013 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 1014-1021, 2013.
[37]      I. Lugo-Cárdenas, G. Flores, S. Salazar, and R. Lozano, "Dubins path generation for a fixed wing UAV," in 2014 International conference on unmanned aircraft systems (ICUAS), pp. 339-346, 2014.
[38]      ع. رودباری م. دهقانی محمدآبادی. ر. اسدی, اختصاص وظایف به تیم پهپادهای همکار با رویکرد ابتکاری برنامه­ریزی فازی خطی صحیح در محیط دینامیک با اهداف متحرک، مجله مهندسی مکانیک ایران، 1398
[39]      .Yan, Peng, et al. "A Fixed Wing UAV Path Planning Algorithm Based On Genetic Algorithm and Dubins Curve Theory." MATEC Web of Conferences. Vol. 179. EDP Sciences, 2018.