فريق بحثي صيني يطرح نموذجًا جديدًا لتخطيط المسارات متعددة الوكلاء تحت اسم DPCN

أخبار ar.wedoany.com، طرح فريق بحثي صيني نموذجًا جديدًا يُعرف باسم DPCN (اختصارًا لـ Decentralized-Planning-Centralized-Negotiation) لحل مشكلة تخطيط المسارات متعددة الوكلاء (MAPF). يحافظ هذا النموذج على قابلية التوسع التي تتميز بها الأساليب اللامركزية، بينما يعالج بشكل فعال النزاعات الديناميكية من خلال آلية تفاوض مركزية، محققًا أداءً متفوقًا على أساليب التعلم المعزز الحالية في الاختبارات المعيارية.

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

يقسم نموذج DPCN كل خطوة زمنية إلى مرحلتين: في مرحلة التخطيط، يولد كل وكيل بشكل مستقل نية حركة بناءً على معلومات الرصد المحلية o_i^t (بمجال رؤية يبلغ 3×3). وفي مرحلة التفاوض، يكتشف النظام جميع النزاعات المحتملة (بما في ذلك نزاعات الرؤوس ونزاعات التبادل)، ويجمع ديناميكيًا الوكلاء المتورطين في النزاع لتشكيل "وكيل فائق". من خلال شبكة PNSE القابلة للتعلم (Pointer Network Special Edition)، يتم اختيار "فائز" واحد من مجموعة النزاع بناءً على حالة البيئة لتنفيذ نيته الأصلية، بينما يظل باقي الوكلاء ثابتين أو يعيدون اختيار حركة جديدة.

لمواجهة مشكلة عدم اتساق مجموعة حركات الوكيل الفائق وصعوبة التدريب الديناميكي، تستلهم شبكة PNSE فكرتها من شبكات المؤشرات (Pointer Networks)، مما يمكنها من معالجة المدخلات متغيرة الطول ومساحات الحركة غير المتسقة. وقد طور فريق البحث آلية تدريب مخصصة للتعلم المعزز القائم على تدرج السياسات، باستخدام تقريب متوسط المجال لتوزيع المكافآت العالمية بشكل عادل، مما يتيح تدريبًا فعالًا للوكلاء الفائقين الديناميكيين.

أُجريت التجارب على معايير MAPF القياسية وخرائط عشوائية، وشملت المقارنة نوعين من المخططات المركزية (ODrM*، BALANCE) وثلاث طرق رائدة في التعلم المعزز (SCRIMP، DCC، PICO). تضمنت إعدادات الخريطة العشوائية أحجامًا تتراوح بين 30×30 و100×100، وكثافة عوائق تتراوح بين 0% و30%، وعدد وكلاء يتراوح بين 32 و256، مع تكرار كل إعداد 200 مرة، مع الإبلاغ عن معدل النجاح وعدد خطوات إنجاز المهمة. أظهرت النتائج أن DPCN يحافظ باستمرار على معدل نجاح مرتفع ووقت مهمة منخفض في السيناريوهات ذات كثافة العوائق العالية (30%) والسيناريوهات واسعة النطاق، متجاوزًا بشكل كبير طرق التعلم المعزز الأخرى، بل ومتفوقًا على المخططات المركزية.

عند تقييم قدرة التعميم على الخرائط الهيكلية، استُخدمت ثلاثة أنواع نموذجية من الخرائط: بيئة متعددة الغرف بأبعاد 32×32 (حجم الغرفة 3×3)، وبيئة قاعة بأبعاد 162×141، وبيئة مستودع بأبعاد 170×84 (بعرض ممر رفوف يبلغ خليتين فقط)، مع احتواء كل خريطة على 25 نموذج مشكلة. أظهر DPCN قدرة على التنسيق الفعال للفرق الكبيرة في هذه الهياكل المعقدة.

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