Multi-Agent Planning with Spatio-Temporal and Topological Constraints using STL-GO

تخيل عالماً لا تطير فيه أسراب الدرونز بشكل عشوائي، بل تعمل كدماغ واحد فائق الذكاء. هذا هو مجال الأنظمة متعددة الوكلاء (Multi-Agent Systems)، وهو فرع من علوم الحاسوب حيث تعمل العديد من الروبوتات معاً لحل مشكلات كبيرة، مثل إخماد حرائق الغابات أو البحث عن المتنزهين المفقودين. ولضمان عدم اصطدام هذه الروبوتات ببعضها البعض أو نسيان مهامها، يستخدم المهندسون "الأساليب الرسمية" (Formal Methods) — وهي طريقة منمقة لقول إنهم يكتبون كتب قواعد رياضية صارمة لتتبعها الروبوتات. عادة ما تكون كتب القواعد هذه مثل قوانين المرور البسيطة: "توقف عند الإشارات الحمراء" أو "لا تتجاوز سرعة 20 ميلاً في الساعة". لكن الحياة الواقعية أكثر تعقيداً؛ فأحياناً يحتاج الروبوت لمعرفة: "هل صديقي قريب مني؟ هل يمكنني التحدث إليه؟ هل رأى الحريق؟". يتطلب هذا كتاب قواعد لا يفهم الزمان والمكان فحسب، بل يفهم أيضاً الطوبولوجيا (Topology) — أي شكل الروابط بين الروبوتات. فكر في الأمر كفرق بين قائمة قواعد لسيارة واحدة وبين كتاب قواعد لفريق رقص يغير شركاءه في الرقص كل ثانية.

تتناول هذه الورقة البحثية المشكلة الصعبة المتمثلة في تعليم سرب من الروبوتات كيفية تخطيط تحركاتها عندما تكون "خريطة صداقتها" متغيرة باستمرار. قدم المؤلفون لغة جديدة قوية للغاية تسمى STL-GO (المنطق الزماني المكاني مع معاملات الرسم البياني - Spatio-Temporal Logic with Graph Operators). وبينما كانت اللغات السابقة قادرة على التعامل مع الزمان والمكان، إلا أنها واجهت صعوبة في التعامل مع الشبكة المعقدة والمتغيرة لمن يتحدث مع من. قام الباحثون ببناء "مترجمين" مختلفين (أحدهما يعتمد على البرمجة الخطية المختلطة integer programming، والآخر على نظرية القابلية للتحقق من النماذج SMT) يمكنهما أخذ هذه القواعد المعقدة والمتغيرة وتحويلها إلى خطة طيران ملموسة للروبوتات. اختبر الباحثون هذين المترجمين في مهمة إنقاذ محاكية تتضمن درونات "محددة للمواقع" (Locators) ودرونات "منقذة" (Rescuers). وأظهرت نتائجهم أنه بينما الطريقة الجديدة قوية بما يكفي للتعامل مع العمل الجماعي المعقد، إلا أنها قد تكون ثقيلة حسابياً، حيث يحل أحد الأساليب المشكلات بشكل أسرع من الآخر اعتماداً على المهمة المحددة.

قصة السرب المتغير

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

1. الاستشعار: التأكد من أن الحريق حقيقي.
2. الاتصال: الصراخ إلى "المحددة للمواقع" الأخرى وإلى "المنقذة" لتقول: "حريق هنا!".
3. التكليف: اختيار "منقذة" محددة للذهال للمساعدة.
4. التنفيذ: تطير "المنقذة" إلى الحريق، وتلتقط ناجياً، ثم تطير به إلى خيمة آمنة.

لكن العقبة هي أن عملية "الصراخ" تعتمد على الرياح، ومستويات البطارية، ومكان طيران الدرونز. أحياناً تستطيع "المحددة للموقع" التحدث إلى "المنقذة"، وأحياناً لا تستطيع. وأحياناً تكون "المنقذة" بعيدة جداً بحيث لا تسمعها. إن خريطة من يمكنه التحدث مع من هي عبارة عن رسم بياني ديناميكي (Dynamic Graph) — وهو شبكة من الاتصالات تتغير كل ثانية.

المشكلة التي حلها المؤلفون هي: كيف نكتب برنامج حاسوبي يحدد مسارات الطيران المثالية لكل هذه الدرونز بحيث تتبع القواعد، حتى عندما تستمر اتصالاتها في التغير؟

كتاب القواعد السحري: STL-GO

استخدم المؤلفون لغة خاصة تسمى STL-GO. فكر في هذه اللغة كوسيلة لكتابة تعليمات يمكنها قول أشياء مثل:

• "يجب رؤية كل حريق بواسطة 'محددة مواقع' خلال 5 دقائق".
• "بمجرد رؤيته، يجب على 'المحددة للموقع' العثور على منقذة واحدة على الأقل يمكنها التحدث إليها خلال دقيقتين".
• "يجب على 'المنقذة' بعد ذلك الطيران إلى الحريق وإحضار الناجي إلى الخيمة".

"معاملات الرسم البياني" (Graph Operators) في STL-GO هي السر الكامن وراء قوتها. فهي تسمح لكتاب القواعد بقول أشياء مثل: "تحقق من خريطة الاتصالات الحالية. هل هناك مسار من 'المحددة للموقع' إلى 'المنقذة'؟". هذا أصعب بكثير من مجرد قول "اذهب إلى الإحداثيات X، Y". فهو يتطلب من الحاسوب إعادة تقييم شكل شبكة الفريق باستمرار.

المترجمان: MIP و SMT

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

1. مترجم MIP (البرمجة الخطية المختلطة): تخيله كمحاسب دقيق للغاية ومهتم بالتفاصيل. هو يحاول إيجاد الخطة الأفضل الممكنة، وليس مجرد أي خطة. يمكن إخباره: "جد مساراً يستخدم أقل قدر من البطارية". هذا رائع إذا كنت تريد توفير الطاقة، ولكنه قد يكون بطيئاً وثقيلاً، مثل محاولة حل لغز "سودوكو" ضخم أثناء التلاعب بالكرات.
2. مترجم SMT (نظرية القابلية للتحقق من النماذج): فكر في هذا كالمحقق السريع جداً. هو لا يهتم بإيجاد الخطة "الأفضل"؛ بل يريد فقط إيجاد أي خطة تعمل. هو يسأل: "هل من الممكن استيفاء كل هذه القواعد؟". إذا كان الجواب نعم، فإنه يعطيك حلاً. وعادة ما يكون أسرع بكثير من المحاسب، لكنه لا يستطيع التحسين من أجل أشياء مثل كفاءة الوقود.

محاكاة الإنقاذ

لاختبار أفكارهم، أنشأ المؤلفون محاكاة لعملية إنقاذ من حريق غابة. لقد أعدوا سيناريو يتضمن "محددات مواقع" و**"منقذات"** وطلبوا من الحاسوب تخطيط مهمة حيث:

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

قاموا بتشغيل المحاكاة مع أحجام فرق مختلفة (من 5 إلى 9 من "محددات المواقع") ومستويات مختلفة من التعقيد (مجرد الاستشعار، بالإضافة إلى التواصل، بالإضافة إلى تكليف المهام).

ما وجدوه:

• مترجم SMT كان هو السريع: في كل اختبار تقريباً، وجد خطة طيران صالحة بشكل أسرع بكثير من مترجم MIP. على سبيل المثال، مع فريق مكون من 9 "محددات مواقع" و3 "منقذات" يتعاملون مع جميع أنواع الاتصالات، حل مترجم SMT المشكلة في حوالي 16.5 ثانية، بينما استغرق مترجم MIP أكثر من 1,480 ثانية (ولم يكن قد وجد الخطة الأفضل المطلقة بعد، بل وجد خطة جيدة فقط).
• مترجم MIP كان هو المُحسِّن: عندما طلب المؤلفون من مترجم MIP إيجاد المسارات الأكثر مباشرة وكفاءة في استهلاك الوقود، قام بعمل رائع في تشكيل تحركات الدرونز، بينما أعطتهم "المنقذة" (SMT) أي مسار يعمل فحسب.
• التعقيد مهم: مع إضافة المزيد من القواعد (مثل اشتراط روابط اتصال محددة أو تكليفات مهام)، أصبح المشكل أكثر صعوبة لكليهما. ولكن مترجم MIP عانى أكثر، حيث انفجر عدد المتغيرات والقيود مع كبر حجم الفريق.

لماذا يهم هذا الأمر؟

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

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