💻 computer science

Landscape-Aware Bandit Hyper-Heuristics for Online Operator Selection in UAV Inspection Routing

تقدم هذه الورقة LA-BHH، وهو خوارزمية "بانديت" (bandit) فوق-استدلالية مدركة للمشهد، تتعلم ديناميكيًا سياسة اختيار مشغل عبر الإنترنت باستخدام ميزات سياقية وخوارزمية LinUCB لتحسين أداء توجيه تفتيش المواقع المتعددة للطائرات بدون طيار بشكل كبير مقارنة بالنماذج المرجعية الحالية.

المؤلفون الأصليون: Junhao Wei, Yanxiao Li, Yifu Zhao, Qibin He, Haochen Li, Dexing Yao, Baili Lu, Zhenhong Peng, Yapeng Wang, Sio-Kei Im, Xu Yang

نُشر 2026-05-15

📖 3 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Junhao Wei, Yanxiao Li, Yifu Zhao, Qibin He, Haochen Li, Dexing Yao, Baili Lu, Zhenhong Peng, Yapeng Wang, Sio-Kei Im, Xu Yang

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك طيار طائرة بدون طيار (درون) مكلف بفحص قائمة من المواقع—ربما أسطح مباني في حرم جامعي، أو خطوط طاقة في منتزه، أو مستشعرات في مزرعة. لديك خريطة بها جميع النقاط محددة، ولكن الترتيب الذي ستزور به هذه النقاط يهم للغاية. إذا زرتها بنمط متعرج وفوضوي، فستستهلك الكثير من البطارية والوقت. أما إذا زرتها في حلقة سلسة وذكية، فستنتهي بسرعة وكفاءة.

تقدم هذه الورقة البحثية نظام "طيار ذكي" جديد يُدعى LA-BHH يساعد الطائرات بدون طيار على معرفة أفضل ترتيب لزيارة هذه المواقع.

المشكلة: الكثير من الطرق لإعادة الترتيب

فكر في مسار الطائرة بدون طيار مثل خيط من الخرز. لجعل الخيط أقصر (أكثر كفاءة)، يمكنك تجربة حيل مختلفة:

2-opt: قطع حلقة في الخيط وقلبها لتفك عقدة ما.
التبديل (Swap): تبديل أماكن خرزتين.
إعادة التمركز (Relocate): أخذ خرزة واحدة ونقلها إلى مكان مختلف في الخط.
Or-opt: نقل مجموعة صغيرة من الخرز معاً إلى مكان جديد.

في الماضي، كان على مخططي الطائرات بدون طيار اختيار واحدة من هذه الحيل والالتزام بها، أو اختيارها عشوائياً. ولكن في بعض الأحيان، قد يكون "قلب الحلقة" رائعاً في حقل مفتوح، بينما يكون "تبديل الخرز" أفضل في مدينة مزدحمة. القاعدة الثابتة لا تعرف الفرق.

الحل: "مدرب ذكي" (LA-BHH)

ابتكر المؤلفون نظاماً يسمى LA-BHH (المدرب الفائق المعتمد على التعلم من تضاريس المشهد - Landscape-Aware Bandit Hyper-Heuristic). يمكنك التفكير في هذا كـ مدرب ذكي يقف بجانب الطائرة بدون طيار، يراقب الخريطة وتقدم الطائرة في الوقت الفعلي.

قراءة الأجواء (الوعي بالتضاريس): قبل أن تبدأ الطائرة حتى، ينظر المدرب إلى الخريطة. هل هو حقل واسع ومفتوح؟ أم مجموعة ضيقة من المباني؟ أم طريق طويل مستقيم؟ يسجل المدرب هذه "الميزات التضاريسية".
مراقبة اللعبة (التعلم عبر الإنترنت): بينما تحاول الطائرة بدون طيار إعادة ترتيب مسارها، يراقبها المدرب وما يحدث.
- إذا جربت الطائرة عملية "تبديل" وأصبح المسار أقصر، يمنح المدرب تلك الحركة درجة عالية.
- إذا جربت الطائرة "تبديلاً" وأصبح المسار أسوأ، يقوم المدتر بخفض درجتها.
اتخاذ القرار (استراتيجية الـ Bandit): يستخدم المدرب خدعة رياضية (تسمى "Bandit") لتقرير الحركة التالية التي يجب تجربتها. إنه يوازن بين الاستكشاف (تجربة أشياء جديدة لمعرفة ما إذا كانت ستنجح) والاستغلال (استخدام الحركات التي حققت أفضل النتائج حتى الآن).
حساس "التعثر": إذا استمرت الطائرة في تجربة الحركات ولكن المسار لم يتحسن (أي أنها عالقة)، فلدى المدرب قاعدة خاصة: "حسناً، نحن عالقون. لنقم بتجربة حركة '2-opt'، فهي ممتازة في فك العقد". هذا يساعد الطائرة على الخروج من المآزق.

ماذا حدث في التجارب؟

اختبر الباحثون هذا المدرب الذكي مقابل طرق أخرى باستخدام 45 سيناريو مختلفاً للخريطة (بعضها مفتوح، وبعضها مزدحم، وبعضها شبكي).

النتائج: كان المدرب LA-BHH هو الفائز الواضح. فقد وجد مسارات أقصر بشكل ملحوظ من تلك التي وجدتها الطرق التالية:
- مجرد اختيار "الجار الأقرب" (النهج "الكسول").
- التخمين العشوائي لنوع الحركة.
- استخدام كتاب قواعد قياسي غير ذكي.
التحسن: مقارنة بأفضل طريقة ذكية تالية، حسن LA-BHH جودة المسار النهائي بنسبة تقارب 17.6%. ومقارنة بالنهج "الكسول"، فقد تحسن بنسبة هائلة بلغت 68.2%.
السرعة: حقق ذلك دون الحاجة إلى كمبيوتر خارق أو فترة تدريب ضخمة. لقد تعلم كل شيء أثناء الرحلة الواحدة، مما جعله سريعاً وعملياً.

الخلاصة

تظهر الورقة البحثية أنك لست بحاجة إلى ذكاء اصطناعي ضخم ومعقد لحل مسألة توجيه الطائرات بدون طيار. بدلاً من ذلك، أنت بحاجة إلى مدرب خفيف الوزن وقابل للتكيف يمكنه:

النظر إلى شكل الخريطة.
مراقبة ما ينجح في الوقت الفعلي.
معرفة متى يغير التكتيكات إذا تعثرت الطائرة.

هذا يجعل الطائرة بدون طيار أكثر ذكاءً، وسرعة، وكفاءة في فحص المواقع، سواء كانت تفحص خط طاقة أو تراقب مصنعاً. وتخلص الورقة إلى أن نهج "التعلم أثناء العمل" هذا هو طريقة عملية وقوية للتعامل مع مهام التوجيه المعقدة.

ملخص تقني: خوارزميات "بانديت" فائقة للبحث عن الحلول المعتمدة على تضاريس المشهد لإدارة اختيار العمليات عبر الإنترنت في توجيه تفتيش الطائرات بدون طيار (UAV)

1. تعريف المشكلة

تتناول الورقة مشكلة توجيه التفتيش متعدد المواقع للطائرات بدون طيار، والتي تم تجريدها كمسأية البائع المتجول (TSP) في الفضاء الإقليدي. في هذا السياق، يجب على الطائرة بدون طيار زيارة مجموعة من المواقع المحددة والعودة إلى نقطة الانطلاق ضمن نافذة طيران محدودة. متغير القرار الأساسي هو ترتيب زيارة هذه المواقع، بافتراض أن المخاوف ذات المستوى الأدنى (مثل التحكم في الارتفاع، وتجنب الاصطدام، وأوقات الخدمة) يتم التعامل معها بشكل منفصل بواسطة مخططات أخرى.

يكمن التحدي في حقيقة أن تضاريس التوجيه المختلفة (مثل: الموحدة، المتكتلة، الممر، الشبكية، وكثافة المزيج) ومراحل البحث المختلفة تتطلب استراتيجيات تحسين مختلفة. غالبًا ما تعتمد الخوارزميات الاستدلالية الكلاسيكية على جداول زمنية ثابتة أو اختيار عشوائي للعمليات، مما قد يؤدي إلى عدم كفاءة مثل الإفراط في استخدام عملية لم تعد تقدم تحسينات أو إهدار عمليات التقييم في حركات غير مناسبة لحالة البحث الحالية.

2. المنهجية: LA-BHH

يقترح المؤلفون LA-BHH (خوارزمية "بانديت" فائقة لتضاريس المشهد)، وهي متحكم عبر الإنترنت مدمج مصمم لتعلم سياسة اختيار العمليات خلال دورة تحسين واحدة دون الحاجة لتدريب مسبق (offline).

إطار العمل فائق الاستدلال (Hyper-Heuristic Framework): يعمل LA-BHH على مستوى عالٍ، حيث يختار من بين مجموعة من أربع عمليات منخفضة المستوى (أذرع):
1. 2-opt: يعكس جزءًا من الجولة لإزالة تقاطعات الحواف.
2. Swap (التبديل): يتبادل موقعين للتفتيش.
3. Relocate (النقل): ينقل موقعًا واحدًا إلى موضع مختلف.
4. Or-opt-2: ينقل كتلة مكونة من موقعين.
متحكم "بانديت" سياقي (Contextual Bandit Controller): تستخدم آلية الاختيار خوارزمية LinUCB (الحد العلوي للثقة الخطي):
- متجه السياق ( $z_t$ ): يشترط المتحكم قراراته بناءً على متجه سمات يتكون من:
  - واصفات تضاريس المشهد الثابتة: حجم المشكلة المعياري، متوسط مسافة أقرب جار، التشتت، تباين الإحداثيات، التشتت الشعاعي، ووزن شجرة الامتداد الدنيا (MST) لكل عقدة.
  - سمات حالة البحث الديناميكية: تقدم الميزانية، طول الجولة الحالي/الأفضل بالنسبة للأولي، التحسن الأخير، معدل القبول، ومؤشرات الركود.
- إشارة التعلم: المكافأة ( $r_t$ ) هي التحسن النسبي المقطوع في طول الجولة الذي أنتجته العملية المختارة. تقوم هذه المكافأة بتحديث إحصائيات الانحدار الخطي ( $A_a, b_a$ ) للذراع المختار، مما يسمح للمتحكم بتكييف تخصيص الائتمان في الوقت الفعلي.
إصلاح مراعي للركود (Stagnation-Aware Repair): ميزة تصميم محددة توجه الاختيار نحو عمليات 2-opt عندما يكتشف البحث ركودًا (نقص في التحسن خلال نافذة قصيرة). هذا يستفيد من الفعالية المعروفة لـ 2-opt في الإصلاح الإقليدي دون تقديم أنواع حركات جديدة.
استراتيجية القبول: يستخدم الأسلوب قاعدة أفضل تحسين جشع (greedy best-improvement). وبينما تم اختبار قبول بأسلوب التلدين (annealing-style) كدراسة استئصال، وُجد أنه يقلل الأداء في هذه الحالات الإقليدية من خلال تعطيل هياكل "أقرب جار" القوية.

3. المساهمات الرئيسية

التعلم عبر الإنترنت للتوجيه: تثبت الورقة أن متحكمًا مدمجًا عبر الإنترنت يمكنه تعلم اختيار العمليات بناءً على كل من خصائص الحالة الثابتة وتقدم البحث الديناميكي، مما يلغي الحاجة إلى مجموعات بيانات ضخمة أو بنى عصبية معقدة.
تخصيص الائتمان السياقي: يجمع صراحةً بين واصفات تضاريس المشهد الثابتة وسمات حالة البحث عبر الإنترنت لتوجيه اختيار العمليات، مما يظهر أن هذا السياق يتفوق على اختيار البانديت غير السياقي (UCB-HH) أو الاختيار العشوائي.
التعامل مع الركود: يُعد دمج بوابة مراعية للركود، والتي توجه المتحكم ديناميكيًا نحو حركات إصلاح 2-opt، مكونًا حاسمًا للحفاظ على تقدم البحث.
تحليل الاستئصال (Ablation Analysis): قامت الدراسة بعزل مساهمات مكونات محددة (السياق، السمات الثابتة، السمات الديناميكية، العمليات المحددة) بشكل منهجي، موضحة أن مكاسب الأداء تنبع من التفاعل بين إصلاح 2-opt، وتخصيص الائتمان السياقي، واستخدام حالة الركود.

4. النتائج التجريبية

تم تقييم الطريقة على 45 حالة من مسائل TSP الإقليدية المولدة عبر خمس عائلات من التضاريس (موحدة، متكتلة، ممر، شبكية مع اضطراب، كثافة مختلطة) وثلاثة أحجام للحالات (50، 100، 200 موقع).

مقاييس الأداء: حقق LA-BHH أفضل متوسط فجوة نهائية (0.0223) وأفضل مساحة تحت المنحنى للتقارب (AUC) (0.0389) مقارنة بجميع الطرق المقارنة.
المكاسب المقارنة:
- قلل الفجوة النهائية بنسبة 17.6% مقارنة بـ UCB-HH غير السياخي.
- قلل الفجوة النهائية بنسبة 22.6% مقارنة بـ Random-HH.
- قلل الفجوة النهائية بنسبة 68.2% مقارنة ببناء "أقرب جار" (NN).
المتانة: تفوق LA-BHH باستمرار على النماذج الكلاسيكية (بما في ذلك التلدين المحاكي، الخوارزميات الجينية، والبحث المحلي المتكرر) عبر جميع عائلات التضاريس، مما أظهر استقرارًا في سيناريوهات النشر المتنوعة.
استخدام العمليات: أظهر التحليل أنه بينما كانت 2-opt هي العملية المهيمنة (خاصة أثناء الركود)، فقد استخدم المتحكم المتعلم بفعالية عمليات Swap و Relocate و Or-opt-2 لتصحيح أخطاء الترتيب المحلي التي لم تستطع 2-opt وحدها معالجتها.

5. الأهمية والادعاءات

تضع الورقة LA-BHH كـ حالة دراسية عملية لتصميم الخوارزميات المدعوم بالتعلم (LEAD) في مجال التوجيه. وتتم صياغة أهميتها حول عدة ادعاءات متواضعة ولكنها عملية:

القابلية للتفسير والكفاءة: على عكس النماذج الضخمة التي تعمل مسبقًا، فإن LA-BHH هو متحكم خفيف الوزن وقابل للفحص يتعلم خلال تشغيل واحد، مما يجعله مناسبًا للسيناريوهات التي تتوفر فيها فقط عدد قليل من الحالات ذات الصلة.
الدور التكميلي: يصرح المؤلفون صراحةً أن LA-BHH ليس مقصودًا به استبدال برامج حل TSP المتطورة (مثل LKH). بدلاً من ذلك، يعمل كطبقة توجيه تقرر أي عملية بحث قابلة لإعادة الاستخدام يجب تطبيقها تحت ميزانية ثابتة.
القابلية للتوسع: الطريقة فعالة حاسوبيًا (تعتمد على المعالج فقط، وتعقيد $O(Tn)$ ) وتتوسع جيدًا من 50 إلى 200 موقع، مع الحفاظ على التنافسية حيث تصبح نماذج البحث المحلي الكلاسيكية أقل موثوقية.
القابلية للتطبيق المستقبلي: يقترح المؤلفون إمكانية توسيع الإطار ليشمل التفتيش الحقيقي للطائرات بدون طيار عن طريق استبدال المسافات الإقليدية بمسافات المسار الأقصر على رسوم بيانية للقابلية للعبور، ومعالجة العوائق عبر مخططات ذات مستوى أدنى، رغم ملاحظتهم أن التجارب الحالية تعتمد على حالات مولدة محكومة بدلاً من بيانات تم جمعها ميدانيًا.