Generating Local Shields for Decentralised Partially Observable Markov Decision Processes

إليك ملخص تقني مفصل لورقة البحث "توليد دروع محلية لعمليات ماركوف لاتخاذ القرار تحت الملاحظة الجزئية اللامركزية" (Generating Local Shields for Decentralised Partially Observable Markov Decision Processes) للباحثين هاوران يانغ ونوبوكو يوشيدا.

1. بيان المشكلة

تتناول الورقة التحدي الحرج المتعلق بالسلامة في الأنظمة متعددة الوكلاء (MAS) التي تعمل تحت ظروف عمليات ماركوف لاتخاذ القرار تحت الملاحظة الجزئية اللامركزية (Dec-POMDPs).

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

2. المنهجية

يقترح المؤلفون مسار عمل (Pipeline) مبتكر يسد الفجوة بين مواصفات السلامة العالمية عالية المستوى وبين مرشحات السلامة المحلية القابلة للتنفيذ (الدروع) دون الحاجة إلى التواصل.

أ. جبر العمليات للدرع (Shield Process Algebra)

يقدم المؤلفون جبر عمليات لتحديد السلوك الآمن عالمياً. تتضمن الصيغة ما يلي:

• الاختيار المحروس (Guarded Choice - $P_1 \parallel_g P_2$): يتصرف المسار كـ $P_1$ إذا كانت الحالة الحالية في مجموعة الحراسة $g$، وإلا يتصرف كـ $P_2$.
• التكرار (Recursion - $\mu X.P$): يسمح بالسلوكيات والدوائر اللانهائية.
• تأكيدات الحالة (State Assertions - $Sh.P$): تؤكد أن الحالة التالية يجب أن تقع ضمن مجموعة آمنة $Sh$ قبل الاستمرار كـ $P$.
• الإنهاء: idle (نجاح) و fail (فشل).

ب. مسار التجميع (The Compilation Pipeline)

المساهمة الأساسية هي مسار تجميع مكون من ثلاث خطوات يحول مواصفات العملية عالية المستوى إلى آلات "ميلي" (Mealy machines) محلية:

1. بناء آلة العمليات (Process Automaton Construction):
   يتم ترجمة عملية الدرع إلى آلة عمليات حتمية ($A_P$). تتبع هذه الآلة التقدم في مواصفات السلامة (على سبيل المثال، تسلسل الحالات الآمنة الذي يتم تنفيذه حالياً).

2. توليد آلة ميلي العالمية (Global Shield Mealy Machine Synthesis):
   يتم إنشاء آلة ميلي عالمية ($G$).

   • المدخلات: حالات Dec-POMDP العالمية ($S$).
   • المخرجات: مجموعة من الإجراءات المشتركة الآمنة ($\prod 2^{A_i}$).
   • المنطق: تجمع الآلة بين الحالة العالمية الحالية وحالة آلة العمليات الحالية. تقوم بحساب الإجراءات المشتركة الآمنة عبر تقاطع الانتقالات المحتملة مع قيود العملية. تقوم دالة تفكيك حتمية ($Dec$) برسم خرائط مجموعات الإجراءات المشتركة إلى مجموعات إجراءات الوكيل الفردي.

3. إسقاط الدرع المحلي (بناء حالة الاعتقاد - Belief-State Construction):
   بما أن الوكلاء لا يمكنهم رؤية الحالة العالمية، يتم إسقاط آلة ميلي العالمية إلى آلات ميلي محلية ($L_i$) لكل وكيل.

   • تمثيل الحالة: حالة الآلة المحلية هي مجموعة اعتقاد (مجموعة جزئية من حالات ميلي العالمية) تتوافق مع ملاحظة الوكيل المحلية الحالية.
   • الانتقال: عندما يلاحظ الوكيل $o_i$، يتم تحديث مجموعة الاعتقاد عن طريق تصفية الحالات العالمية المتوافقة مع $o_i$ ومحاكاة الانتقالات.
   • المخرجات: مخرج الآلة المحلية هو تقاطع مجموعات الإجراءات الآمنة لجميع الحالات العالمية الموجودة في مجموعة الاعتقاد الحالية. إذا كان التقاطع فارغاً (أو يؤدي إلى fail)، يكون المخرج هو $\perp$ (فشل الدرع).

ج. التنفيذ

• اللغة: تم تنفيذ مسار العمل باستخدام لغة Rust.
• التحقق: متكامل مع PRISM (أداة فحص النماذج الاحتمالية الرمزية) لحساب احتمالات السلامة في أفضل وأسوأ الحالات دون تحديد سياسة وكيل معين.

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

1. جبر عمليات الدرع: صياغة رسمية تتضمن الاختيار المحروس والتكرار مصممة خصيصاً لبيئات تعدد الوكلاء ذات الملاحظة الجزئية والخالية من التواصل.
2. مسار التجميع: طريقة مبتكرة لتوليد دروع ميلي محلية من مواصفات العمليات العالمية. وهي تعالج مشكلة الملاحظة الجزئية باستخدام مجموعات حالات الاعتقاد، مما يسمح للوكلاء باتخاذ قرارات آمنة بناءً على معلومات محدودة.
3. تنفيذ Rust والتكامل مع PRISM: سلسلة أدوات عاملة تسمح بتحليل احتمالات السلامة (الحدود الدنيا والعليا) بشكل مستقل عن سياسات تعلم الوكلاء.

4. دراسة الحالة والنتائج

قيم المؤلفون مسار العمل باستخدام مشكلة إيجاد المسار متعدد الوكلاء (MAPF) على شبكات ذات أحجام متفاوتة ($3\times3$ إلى $5\times5$) وأعداد وكلاء ($n=2, 3$).

الإعداد التجريبي

• النماذج المرجعية (Baselines): سياسات عشوائية غير محمية وسياسات تعلم $Q$ (Q-learning).
• متغيرات الدرع:
  • $P_1$ (المتحفظ): يبقي الوكلاء في حالات آمنة ولكنه غالباً ما يجبرهم على البقاء ثابتين، مما يؤدي إلى انخفاض معدل إتمام المهام.
  • $P_2$ (المُحسَّن): يقلل من فقدان الإجراءات عبر تجنب التقاطعات غير الضرورية في هيكل التفرع، مما يسمح بمزيد من الحركة مع الحفاظ على السلامة.

النتائج الرئيسية

• السلامة: حقق كلا النوعين من الدروع ($P_1$ و $P_2$) نسبة تصادم 0% في جميع التكوينات، بينما سجل النموذج المرجعي غير المحمي معدلات تصادم عالية (وصلت إلى 98.6%).
• الأداء (الوصول إلى الهدف):
  • تفوق $P_2$ بشكل كبير على $P_1$. بينما كان $P_1$ متحفظاً للغاية (غالباً ما يؤدي إلى معدل نجاح أقل من 10%)، سمح $P_2$ للوكلاء بالوصول إلى الأهداف في أكثر من 90% من التجارب (مثلاً 0.929 لشبكة $4\times4$ و $n=2$).
  • نطاق الملاحظة ($R$): أدى زيادة نطاق الملاحظة إلى تحسين أداء $P_2$ من خلال تمكين تحديثات أكثر دقة لحالة الاعتقاد.
• السياسات المتعلمة: عند التطبيق على وكلاء تعلم $Q$:
  • فرضت الدروع تصادماً صفرياً بغض النظر عن السياسة الأساسية.
  • حقق الوكلاء المدربون باستخدام $P_2$ أعلى معدلات النجاح، مما يثبت أن الدرع لا يعيق التعلم بل يوجهه بأمان.
  • أدى الوكلاء المدربون باستخدام $P_1$ إلى أداء ضعيف، مما يؤكد أن الدرع المفرط في التحفظ يقيد قدرة الوكيل على تعلم مسارات فعالة.

5. الأهمية

يوفر هذا العمل إطاراً نظرياً وعملياً صارماً لضمان السلامة في الأنظمة متعددة الوكلاء اللامركزية والخالية من التواصل.

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

في الختام، نجحت الورقة في سد الفجوة بين مواصفات السلامة العالمية الرسمية والتنفيذ اللامركزي، مقدمة حلاً قابلاً للتوسع لمنع التصادمات وحالات الجمود في البيئات المعقدة متعددة الوكلاء.