Collaborative Planning with Concurrent Synchronization for Operationally Constrained UAV-UGV Teams

إليك ملخص تقني مفصل لورقة البحث بعنوان "التخطيط التعاوني مع التزامن المتزامن لفرق الطائر بدون طيار والمركبات الأرضية غير المأهولة المقيدة تشغيلياً" (CoPCS).

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

تتناول الورقة تحدي التخطيط التعاوني لفرق الروبوتات غير المتجانسة المكونة من طائرات بدون طيار (UAVs) ومركبات أرضية غير مأهولة (UGVs) تعمل تحت قيود تشغيلية صارمة.

• الصراع: توفر الطائرات بدون طيار تغطية سريعة ولكنها محدودة بـ قيود الطاقة (وقت طيران قصير). بينما تمتلك المركبات الأرضية سعة طاقة عالية ويمكنها العمل كمحطات شحن متنقلة، لكنها محدودة بـ قيود القابلية للاجتياز (يجب أن تظل في التضاريس أو الطرق القابلة للقيادة).
• التحدي الجوهري: لا يمكن لأي من المنصتين إكمال مهام مراقبة بيئية واسعة النطاق بمفردها. يتطلب التعاون الفعال ما يلي:
  1. تخطيط مهام متعدد للطائرات بدون طيار مقيد بالطاقة: تحديد المهام التي يجب زيارتها وترتيبها.
  2. تخطيط مسار متعدد للمركبات الأرضية مقيد بالقابلية للاجتياز: تخطيط المسارات على شبكات الطرق لدعم الطائرات بدون طيار.
  3. التخطيط المشترك المتزامن والمتزامن (Synchronized Concurrent Co-Planning): وهو الجانب الأكثر أهمية. يجب على الطائرات بدون طيار والمركبات الأرضية التخطيط بشكل مشترك ومتزامن لضمان وصول المركبات الأرضية إلى نقاط الشحن في اللحظة التي تحتاج فيها الطائبات بدون طيار إلى إعادة الشحن تماماً. الطرق الحالية غالباً ما تخطط بشكل تسلسلي أو تستخدم استراتيجيات جشعة، مما يؤدي إلى وقت انتظار غير مستغل، أو فشل المهمة، أو أوقاء إنجاز غير مثالية.

2. المنهجية: إطار عمل CoPCS

يقترح المؤلفون CoPCS (التخطيط التعاوني مع التزامن المتزامن)، وهو نهج قائم على التعلم يتم تدريبه من البداية إلى النهاية باستخدام التعلم بالتقليد (Imitation Learning). يتكون الإطار من ثلاثة مكونات رئيسية:

أ. تمثيل الرسم البياني غير المتجانس (Heterogeneous Graph Representation)

يتم نمذجة البيئة كرسم بياني $G = \{T, E_{intra}, E_{uav}, E_{ugv}\}$:

• العقد ($T$): تمثل المهام ($m$)، ونقاط المسار ($p$)، والطائرات بدون طيار ($a$)، والمركبات الأرضية ($g$). تحتوي كل عقدة على سمات مثل الإحداثيات، ومستويات الطاقة، وحالة الزيارة.
• الحواف (Edges):
  • حواف النوع الواحد (Intra-type edges): تربط العقد من نفس النوع (مثل طائرة بدون طيار إلى طائرة أخرى).
  • حواف الأنواع المختلفة (Cross-type edges): تربط الكيانات غير المتجانسة (مثل طائرة بدون طيار إلى مركبة أرضية للشحن، وطائرة بدون طيار إلى مهمة للزيارة).
  • ترميز القيود: يتم تعريف الحواف بناءً على المسافة والقابلية للاجتياز (لا يمكن للمركبات الأرضية الاتصال بعقد المهام غير القابلة للاجتياز).

ب. محول الرسم البياني غير المتجانس (المُشفّر - Encoder)

تقوم شبكة محول (Transformer) $\psi$ بمعالجة الرسم البياني لتوليد تضمينات مدركة للقيود ($H$).

• الآلية: تستخدم مزيجاً من الانتباه الذاتي (Self-Attention) (داخل أنواع الروبوتات) والانتباه المتقاطع (Cross-Attention) (بين أنواع الروبوتات).
• التزامن: تسمح آلية الانتباه المتقاطع للطائرات بدون طيار والمركبات الأرضية بتبادل المعلومات المتعلقة بمستويات الطاقة وقيود المسار، مما يمكن النموذج من تعلم التبعيات الزمنية المطلوبة لإعادة الشحن المتزامن.

ج. مُفكك الشفرة المدرك للسياق (Context-Aware Transformer Decoder)

يقوم مُفكك الشفرة $\phi$ بتوليد تسلسل إجراءات مشترك بشكل تلقائي (Autoregressively).

• فضاء الإجراءات: يتنبأ المُفكك بثلاثة أنواع من الإجراءات في آن واحد:
  1. زيارة طائرة بدون طيار لمهمة ما.
  2. تحرك مركبة أرضية على طول مسار.
  3. إعادة شحن طائرة بدون طيار على مركبة أرضية محددة.
• الآلية: يستخدم الانتباه الذاتي السببي لنمذجة تاريخ الإجراءات، والانتباه المتقاطع لربط الإجراءات بالتضمينات العالمية للرسم البياني ($H$). يضمن ذلك أن خطة الطائرة بدون طيار تدرك موقع المركبة الأرضية والعكس صحيح.

د. نموذج التدريب

• التعلم بالتقليد (Imitation Learning): يتم تدريب النموذج لمحاكاة الحلول المثلى التي يتم إنتاجها بواسطة مُحلل البرمجة الخطية المختلطة (MIP).
• العملية: يوفر مُحلل MIP تسلسلات الإجراءات الصحيحة (Ground-truth) لمختلف السيناريوهات. يقوم نموذج CoPCS بتقليل خسارة الإنتروبيا المتقاطعة (Cross-entropy loss) بين الإجراءات المتوقعة وحقيقة MIP، ليتعلم تكرار السلوك المتزامن الأمثل دون الحاجة للتكلفة الحسابية لـ MIP أثناء التنفيذ.

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

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

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

قيم المؤلفون CoPCS عبر ثلاث بيئات: محاكاة الخرائط ثنائية الأبعاد (2D)، محاكاة ثلاثية الأبعاد عالية الدقة (Unity + ROS1)، وفرق روبوتات فيزيائية (طائرات Crazyflie ومركبات Limo مع ROS2).

• النماذج المرجعية (Baselines): تمت المقارنة مع الخوارزميات الحدسية (Guided Local Search, Tabu Search, Simulated Annealing) ونموذج MLP أساسي.
• مقاييس الأداء: زمن الإنجاز (Makespan - إجمالي وقت المهمة)، استهلاك طاقة الطائرات بدون طيار، واستهلاك طاقة المركبات الأرضية.
• النتائج الرئيسية:
  • كفاءة فائقة: حقق CoPCS باستمرار أقصر زمن إنجاز وأقل استهلاك للطاقة عبر جميع تكوينات الفريق (1-4 طائرات بدون طيار، 1-2 مركبات أرضية) وتعقيدات المهمة (من 15 إلى 45 مهمة).
  • القابلية للتوسع: مع زيادة تعقيد المهمة (45 مهمة)، اتسعت الفجوة في الأداء بين CoPCS والنماذج المرجعية بشكل كبير؛ حيث فشلت الخوارزميات الحدسية في التوسع بفعالية بسبب عدم قدرتها على التعامل مع التزامن العالمي.
  • التعميم: نجح النموذج في التعميم على بيئات غير مرئية (خرائط ضواحي وحضرية) ذات تخطيطات طرق ونقاط انطلاق مختلفة، محافظاً على أداء عالٍ.
  • التحقق الواقعي: في التجارب الفيزيائية، حقق CoPCS معدلات استدلال بلغت 9 هرتز (لـ 15 مهمة) و3 هرتز (لـ 45 مهمة)، مما يثبت الجدوى الزمنية الحقيقية للنشر الروبوتي الفيزيائي.

5. الأهمية

يمثل هذا العمل تقدماً كبيراً في أنظمة الروبوتات المتعددة من خلال حل "عنق زجاجة التزامن" في الفرق غير المتجانسة.

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