A Cutting-Edge Approach to Multi-UAV Mission Planning Using Enhanced Constraint Satisfaction

Creative Commons License

Ayvaz E., ATAY Y., Babaoğlu İ.

Journal of Intelligent and Robotic Systems: Theory and Applications, cilt.111, sa.3, 2025 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 111 Sayı: 3
  • Basım Tarihi: 2025
  • Doi Numarası: 10.1007/s10846-025-02279-4
  • Dergi Adı: Journal of Intelligent and Robotic Systems: Theory and Applications
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Aerospace Database, Applied Science & Technology Source, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, DIALNET, Civil Engineering Abstracts
  • Anahtar Kelimeler: Constraint Satisfaction, Dynamic Domain, Dynamic Programming, Mission Planning, Multi-Objective, Multi-task Planning, NP-hard, UAVs
  • Gazi Üniversitesi Adresli: Evet

Özet

Multi-task planning for diverse UAVs and missions can be approached as a Constraint Satisfaction Problem (CSP) where the Temporal CSP (TCSP) method adds time-based sequential task modeling. The Enhanced Temporal Constraint Satisfaction Problem (ETCSP) method innovatively merges dynamic domain features with a MIQP (Mixed Integer Quadratic Programming) based scoring system to optimally assign UAVs to tasks, moving beyond traditional greedy algorithms. This approach includes an enhanced forward checking method that evaluates task suitability and UAV compatibility in real-time using dynamic programming, thus refining search precision. The ETCSP model was tested in two phases, initially assigning various tasks and then employing CSP methods to monitor task changes over time. Results show that the generic TCSP method requires 61 UAVs to complete 70 tasks, while the Enhanced TCSP achieves the same with only 48 UAVs—which is roughly a 21% reduction in UAV usage. Similarly, the Enhanced method completes the task package in about 3800 min and with 1142 L of fuel, compared to 4855 min and 1615 L for the TCSP method, translating to approximately a 22% reduction in time and a 29% reduction in fuel consumption.