Obstacle-aware multi-UAV scheduling for plant-protection operations using an enhanced walrus optimizer
تقترح هذه الورقة خوارزمية محسنة لتحسين مستويات أداء حيوان الفظ (CRWO) تدمج بين الطفرة التفاضلية العشوائية، والتعلم القائم على التضاد لتصوير العدسة، والبحث في الجوار المنفصل، وذلك لتحسين تعيين المهام وترتيب الزيارة لعمليات حماية النباتات متعددة الطائرات بدون طيار بشكل مشترك، مما يوازن بفعالية بين عبء عمل الأسطول ويضمن جدوى المسار مع مراعاة العوائق في ظل قيود القدرة على التحمل.
المؤلفون الأصليون:zhe sun, anchan liao, yunrui bi, zhixin sun
في الصفوف الهادئة للبساتين الحديثة، استوطن نوع جديد من العمال الأجواء: المركبة الجوية غير المأهولة، أو ما يعرف بالطائرة بدون طيار (الدرون). وخلافاً للجرارات الضخمة والمزعجة التي كانت سائدة في الماضي، تتميز هذه الآلات بالرشاقة التي تمكنها من التنقل بين الأشجار، والدقة الكافية لاستهداف الأوراق المريضة أو الأغصان التي تعاني من نقص المغذيات فقط. إن هذا التحول من التغطية الشاملة إلى الرعاية المستهدفة يعد بتوفير المواد الكيميائية وحماية البيئة. ومع ذلك، لا يمكن لطائرة واحدة تعمل بمفردها القيام بالمهمة بأكملها؛ فبطاريتها تنفد، وخزانها لحمل المبيدات السائلة يمتلئ بسرعة. ولحماية حقل كبير، يجب أن تعمل أسراب من هذه الطائرات معاً، حيث تتبادل الأدوار في الطيران للخارج، ورش بقعة محددة، ثم العودة إلى قاعدة مركزية لإعادة التعبئة، ثم الطيران مجدداً. ويكمن التحدي في تحديد أي طائرة تذهب إلى أي شجرة، وبأي ترتيب، وكم عدد الرحلات التي ستقوم بها كل واحدة منها. فإذا كان المخطط سيئاً، فستُنهك بعض الطائرات بينما تظل أخرى خاملة، أو والأسوأ من ذلك، قد تُرسل طائرة في مسار يبدو قصيراً على الخريطة ولكنه في الواقع محجوب بشجرة أو منطقة محظورة، مما يؤدي إلى تحطمها أو إهدار طاقة ثمينة.
لقد تصدى الباحثون في جامعة نانجينغ للاتصالات وعلوم التكنولوجيا ومعهد نانجينغ للتكنولوجيا لهذه المعضلة المعقدة في الجدولة عبر تطوير طريقة جديدة لتنسيق هذه الأسراب. فقد ابتكروا نظاماً لا ينظر فقط إلى المسافة المستقيمة بين الأشجار، بل يحسب بدلاً من ذلك المسار الآمن الفعلي الذي يجب أن تسلكه الطائرة لتجنب العوائق مثل الأغصح، والمباني، والمناطق المحظورة. ولإيجاد أفضل جدول زمني ممكن لأسراب الطائرات، صمموا خوارزمية حاسوبية جديدة مستوحاة من سلوك حيوان "الوالروس" (فقمة البحر). ففي البرية، تتحرك حيوانات الوالروس في مجموعات، موازنةً بين الحاجة إلى استكشاف مناطق تغذية جديدة وبين ضرورة البقاء بالقرب من القطيع من أجل السلامة. وقد ترجم الباحثون هذه السلوكيات الاجتماعية إلى قواعد رياضية تساعد الحاسوب على البحث عبر الملايين من خطط الطيران الممكنة لإيجاد خطة تجعل كل طائرة تعمل بشكل متساوٍ وآمن.
اختبر الفريق خوارزميتهم الجديدة، التي أطلقوا عليها اسم "محسن الوالروس المطور"، مقابل عدة طرق موجودة حالياً تُستخدم لمشكلات مماثلة. لقد قاموا بمحاكاة بيئة بستان واقعية، تشتمل على تضاريس متموجة، وأشجار ذات ارتفاعات متفاوتة، ومناطق حظر طيران لا يُسمح للطائرات بدخولها. وفي هذه عمليات المحاكاة، تفوقت الخوارزمية الجديدة باستمرار على الطرق الأخرى؛ فقد نجحت في تقليل إجمالي المسافة التي يتعين على السرب قطعها بهامش صغير ولكنه مؤثر، غير أن إنجازها الأكثر أهمية كان في موازنة عبء العمل. ففي أفضل النتائج، انخفض الفرق في المسافة المقطوعة بين أكثر الطائرات انشغالاً وأقلها انشغالاً بنسبة تقارب النصف مقارنة بالطريقة التالية لها في الكفاءة. وهذا يعني أنه في سيناريو واقعي، ستتآكل الطائرات في وقت متقارب تقريباً، ويمكن للسرب أن يعمل لفترة أطول دون الحاجة إلى استبدال الآلات المنهكة.
وكان جزء حاسم من هذا النجاح هو كيفية تعامل الباحثين مع واقع البستان. فالعديد من أنظمة التخطيط تفترض أن الطائرة يمكنها الطيران في خط مستقيم من شجرة إلى أخرى، وقد أظهر الباحثون أن هذا الافتراض خطير. فمن خلال استخدام تقنية مثبتة لتحديد المسارات (pathfinding) لرسم المسارات الالتفافية الفعلية المطلوبة للالتفاف حول العوائق، ضمنوا أن الجدول الزمني الذي تولده الخوارما هو مسار ممكن من الناحية الفيزيائية للطيران. كما أضافوا بُعداً ثالثاً إلى التخطيط، لضمان حفاظ الطائرات على ارتفاع آمن فوق الأرض وغطاء الأشجار، وضمان عدم صعودها أو هبوطها بشكل حاد، مما قد يشكل خطراً على الطائرة. وقد تم فحص كل مسار طيران تولده منظومتهم للتأكد من بقائه ضمن حدود بطارية الطائرة وقواعد السلامة.
تؤكد هذه الدراسة أن هذا النهج الجديد يعمل بشكل جيد في البيئات الثابتة حيث لا تتحرك الأشجار والعوائق. وقد وجد الباحثون أن طريقتهم كانت جيدة بشكل خاص في منع الإفراط في تشغيل طائرة واحدة بينما ترتاح الطائرات الأخرى، وهي مشكلة شائعة يمكن أن تبطئ العملية برمتها. وبينما لا تتعامل المنظومة بعد مع العوائق المتحركة أو تغيرات الطقس، وتفترض أن جميع الطائرات متطابقة، إلا أنها توفر أساساً متيناً لمستقبل الزراعة المؤتمتة. فمن خلال التعامل مع البستان كفضاء معقد ثلاثي الأبعاد بدلاً من مجرد خريطة مسطحة، وباستخدام خوارزمية ذكية مستوحاة من الطبيعة لإدارة السرب، قدم الباحثون وسيلة عملية للحفاظ على سلامة هذه العمال الآليين وكفاءتهم وتوازنهم. والنتيوتج هو منهج جدولة يحول مزيجاً فوضوياً من الرحلات إلى عملية منسقة وموثوقة، مما يضمن حماية البستان دون إرهاق الآلات التي تقوم بالعمل.
ملخص تقني: جدولة متعددة الطائرات بدون طيار (UAVs) مدركة للعوائق لعمليات حماية النباتات باستخدام مُحسِّن والروس المطور
بيان المشكلة تتناول الورقة البحثية تحدي جدولة الطائرات بدون طيار التعاونية المستخدمة في حماية النباتات في بيئات البساتين التي تتميز بتضاريس معقدة وعوائق. وخلافاً لتخطيط مسار التغطية التقليدي، يركز هذا البحث على المعالجة المستهدفة لبقع الأمراض أو مواقع نقص العناصر الغذائية المنفصلة. وتتمثل المشكلة الجوهرية في مهمة جدولة متعددة المهام، متعددة الطائرات، ومن مستودد واحد، مقيدة بما يلي:
القدرة على التحمل والحمولة: مدى بطارية محدود وسعة مبيدات تتطلب العودة المتكررة إلى مستودد مركزي.
تجنب العوائق: وجود أشجار، مبانٍ، ومناطق حظر طيران تجعل المسافات الإقليدية (الخطوط المستقيمة) غير دقيقة لتخطيط المسارات.
توازن عبء العمل: الحاجة إلى توزيع المهام بالتساوي بين أسطول متجانس لمنع تحميل طائرات معينة فوق طاقتها.
قابلية التنفيذ ثلاثية الأبعاد: المتطلب لتوليد مسارات قابلة للتنفيذ تحترم الخلوص التضاريسي، حدود زاوية الصعود، وارتفاعات العمل المحددة فوق الغطاء النباتي.
غالباً ما تقيم الطرق الحالية الجداول الزمنية باستخدام مسافات الخط المستقيم، مما قد يؤدي إلى مسارات غير قابلة للتنفيذ أو غير فعالة عند إدخال العوائق. علاوة على ذلك، فإن الدراسات القليلة التي تحسن تخصيص المهام، وترتيب الزيارات، وتحقيق المسار في آن واحد تحت هذه القيود ثنائية الأبعاد (2.5D) تظل نادرة.
المنهجية يقترح المؤلفون إطار عمل يتكون من مرحلتين: طبقة تحقيق مسار حتمية ومُحسِّن جدولة يعتمد على الاستدلال الميتاهيوريستي (Metaheuristic).
نموذج الجدولة:
الهدف: دالة متعددة الأهداف تهدف إلى تقليل إجمالي مسافة السفر، وأقصى مسافة تراكمية لكل طائرة (مدة المهمة)، والانحراف المعياري لأطوال مسارات الطائرات (توازن عبء العمل).
تكاليف الحواف: بدلاً من المسافة الإقليدية، يتم اشتقاق تكاليف الحواف (cij) من بحث A* على رسم بياني إشغالي ثابت. يضمن ذلك أن خوارزمية الجدولة تأخذ في الاعتبار الالتفافات الأفقية حول العوائق ومناطق حظر الطيران.
القيود: يفرض النموذج قيود الحمولة، وأقصى طول للمهمة الواحدة، وقيود العودة إلى المستودد الواحد. يقوم "المفكك" (Decoder) ببناء المهام عبر تعبئة المهام حتى الوصول إلى حدود السعة أو المدى.
تحقيق المسار (2.5-أبعاد):
أفقياً: يقوم خوارزم A* بإعادة بناء مسارات خالية من الاصطدام بين المهام بناءً على الجدول الزمني.
رأسياً: يقوم نموذج ارتفاع 2.5D بتعيين ملفات تعريف الارتفاع. تحافظ الطائرة بدون طيار على ارتفاع التحليق (Hc) فوق التضاريس، وتنخفض بسلاسة إلى ارتفاع العمل (Hmin) فوق الغطاء النباتي في مواقع المهام، وتلتزم بأقصى زاوية صعود (20∘).
التحقق من القابلية للتنفيذ: يتم حساب المسافة المكانية ثلاثية الأبعاد المحققة بعد الجدولة والتحقق منها مقابل قدرة الطائرة على التحمل.
مُحسِّن والروس المطور (CRWO): لحل مشكلة الجدولة التوافقية ذات التعقيد العالي (NP-hard)، قام المؤلفون بتطوير مُحسِّن والروس (WO) القياسي عبر ثلاث استراتيجيات محددة:
الطفرة التفاضلية العشوائية: تستخدم الفرق بين أفضل حل تاريخي والأفراد العشوائيين لتوجيه الاضطراب، مما يوازن بين الاستكشاف والاستغلال.
تعلم التضاد القائم على تصوير العدسة: يولد حلولاً مرشحة متماثلة عبر مساحة البحث للهروب من الحلول المحلية المثلى.
البحث في الجوار المنفصل: يُطبق على الحلول النخبوية لتحسين إعادة تخصيص المهام وأولويات الزيارة.
الترميز: يستخدم تمثيلاً بمفتاح عشوائي مزدوج لترميز كل من تخصيص المهام للطائرات وأولوية الزيارة، مما يسمح لمشغلات التحسين المستمرة بحل المشكلات المنفصلة.
المساهمات الرئيسية
صياغة مدركة للعوائق: صاغت الورقة نموذج جدولة حيث يتم حساب تكاليف الحواف مسبقاً عبر A* بدلاً من المسافة الإقليدية، مما يضمن توافق هدف التحسين مع تكاليف المسارات القابلة للتنفيذ.
خوارزمية CRWO: تطوير خوارزمية ميتاهيوريستية محسنة (CRWO) مصممة خصيصاً لجدولة الطائرات المتعددة عالية الأبعاد والمقيدة، والتي أظهرت أداءً فائقاً على WO وPSO وGWO وغيرها.
إطار عمل تحقيق 2.5D: نهج تسلسلي يفصل البحث في الجدولة ثنائي الأبعاد عن تحقيق المسار ثلاثي الأبعاد، مما يضمن أن الجداول المولدة تستوفي قيود الخلوص التضاريسي وزاوية الصعود دون تعقيد مساحة البحث بديناميكيات ثلاثية الأبعاد كاملة.
تقييم شامل: إجراء اختبار مرجعي صارم مقابل ثماني خوارزميات عبر كثافات عوائق منخفضة ومتوسطة وعالية، بما في ذلك دراسات الاستئصال (Ablation studies) لعزل مساهمة مكونات CRWO المحددة.
النتائج التجريبية أجريت التجارب على خريطة بستان بمساحة 800م × 800م مع 50 مهمة و6 طائرات بدون طيار.
الأداء مقابل النماذج المرجعية: في سيناريو العوائق المتوسطة، تفوق CRWO على أقوى نموذج مرجعي (PSO) من خلال تقليل متوسط قيمة الهدف بنسبة 3.71%، وتقليل أقصى مسافة مكانية تراكمية لكل طائرة بنسبة 3.70%، وتقليل الانحراف المعياري لأطوال مسارات الطائرات بنسبة 47.62%.
توازن عبء العمل: حقق CRWO باستمرار أدنى تباين في عبء العمل (الانحراف المعياري) عبر جميع كثافات العوائق، مما يشير إلى كفاءة فائقة في استخدام الأسطول.
A* مقابل الإقليدي: لم يؤدِ استخدام تكاليف حواف A* إلى تقليل إجمالي المسافة التراكمية بشكل كبير مقارنة بالجدولة الإقليدية، ولكنه حسن بشكل كبير توازن عبء العمل (تقليل الانحراف المعياري لطول المسار من 50.43م إلى 23.11م في الجولات المقترنة).
دراسة الاستئصال: أكدت الدراسة أن الجمع بين الطفرة التفاضلية، وتعلم التضاد، والبحث في الجوار المنفصل كان ضرورياً لتحقيق الأداء النهائي؛ حيث أدى إزالة أي مكون إلى تدهور النتائج.
الأهمية والادعاءات تزعم الورقة أن CRWO يوفر طريقة جدولة عملية لعمليات حماية النباتات ذات المستودد الواحد والثابتة، حيث يكون تجنب العوائق وتوازن الأسطول أمراً بالغ الأهمية. ويؤكد المؤلفون أن الطريقة هي "مجدول متوازن" وليست مجرد خوارزمية مسار قصير بحت؛ تكمن قيمتها الأساسية في توزيع عبء العمل بالتساوي وضمان تلبية قيود السلامة دون الحاجة إلى اقتران ثلاثي الأبعاد معقد أثناء مرحلة التحسين.
يحدد المؤلفون نطاق العمل بوضوح، مع الإقرار بأن الإطار الحالي محدود بالخرائط الثابتة، والطلبات الحتمية، والأساليب المتجانسة. كما ذكروا صراحة أن الطريقة لا تضمن الوصول إلى الحل الأمثل العالمي، وأن هناك حاجة لعمل مستقبلي لمعالجة إعادة التعيين الديناميكي، والأساليب غير المتجانسة، وعدم اليقين في ظروف الطيران. وتخلص الدراسة إلى أنه بينما تكون مكاسب المسافة الإجمالية هامشية، فإن التحسينات الكبيرة في توازن عبء العمل والامتثال لمعايير السلامة تجعل من CRWO حلاً قابلاً للتطبيق لحماية النباتات المستهدفة.