Distance-Constrained Unlabeled Multi-Agent Pathfinding

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

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

تقدم هذه الورقة طريقة جديدة للتفكير في هذه المشكلة، والتي يسميها المؤلفون "تخطيط مسار الوكلاء المتعددين غير المعنون والمستقل للمسافة r" (أو rIUMAPF اختصاراً). لقد اكتشفوا أنه بينما النسخة القياسية من هذه المشكلة سهلة الحل، فإن إضافة قاعدة "البقاء بعيداً" تجعل من الصعب جداً على الحواسيب حتى معرفة ما إذا كان الحل موجوداً. ومع ذلك، لم يستسلم المؤلفون؛ بل بنوا أداتين مختلفتين لمواجهة هذا الوحش.

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

الأداة الثانية هي المُرتجل السريع والبديهي. فبدلاً من حساب المسار المثالي من البداية إلى النها، تستخدم "مولد تكوينات" يسمى IU-PIBT. فكر في هذا كشرطي مرور ينظر إلى المشهد الحالي ويخبر كل روبوت: "حسناً، أنت تحرك إلى هناك، وأنت تحرك إلى هنا"، خطوة بخطوة. إنه سريع للغاية ويمكنه التعامل مع أسراب ضخمة من الروبوتات. ومع ذلك، في بعض الأحيان يرتبك شرطي المرور وتبدأ الروبوتات في الدوران في دوائر ("جمود حيوي" أو livelock) دون الوصول أبداً إلى وجهتها. ولحل هذه المشكلة، أضاف المؤلفون طبقة "بحث" تسمى IU-LaCAM. وهي تعمل بمثابة مشرف ذكي يراقب شرطي المرور؛ فإذا بدأت الروبوتات في الدوران في دوائر، يتدخل المشرف، ويعيد تعيين الأهداف، ويكسر حالة الجمود.

النتائج مبهرة. فبينما المشكلة نظرياً صعبة جداً لدرجة أنها قد تستغرق وقتاً طويلاً جداً في أسوأ الحالات، إلا أن طرق المؤلفين تعمل بشكل جيد بشكل مفاجئ في الممارسة العملية. يمكن لـ "المُرتجل" الخاص بهم (IU-LaCAM) التعامل مع مئات الوكلاء في خرائط كبيرة خلال ثوانٍ، وحل مشكلات قد تُحبط الطرق الأخرى. وقد وجدوا أنه بينما "المهندس المعماري" (ILP) ممتاز للخطط الصغيرة عالية الجودة، فإن "المُرتجل" هو البطل في حالات الفوضى واسعة النطاق. ومن المثير للاهتمام أيضاً أنهم اكتشفوا أن وجود مسافة أمان أكبر (مسافة "r" أكبر) يمكن أن يجعل المشكلة أسهل في الحل أحياناً، لأن ذلك يمنع الروبوتات من العلوق في الممرات الضيقة والمزدحمة في المقام الأول.

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