Dynamic Adversarial Resource Allocation: the dDAB Game

إليك ملخص تقني مفصل لورقة البحث بعنوان "تخصيص الموارد الديناميكي المعادي: لعبة DDAB".

1. صياغة المشكلة

تقدم الورقة البحثية لعبة ديناميكية للمدافع والمهاجم في توزيع بلوتو (dDAB)، وهي امتداد جديد للعبة "كولونيل بلوتو" (Colonel Blotto) الاستاتيكية الكلاسيكية إلى بيئة ديناميكية مقيدة بالرسوم البيانية (Graphs).

• البيئة: تُلعب اللعبة على رسم بياني موجه ومتصل بقوة $G=(V, E)$، حيث تمثل العقد مواقع فيزيائية وتمثل الحواف إمكانية التنقل.
• اللاعبون: يتنافس لاعبان، المدافع (الأزرق) والمهاجم (الأحمر)، للسيطرة على مجموعة فرعية من العقد تسمى العقد الرئيسية ($V_{key}$).
• الموارد: يمتلك اللاعبون موارد مستمرة (أو منفصلة) (مثل الروبوتات) بإجمالي كميات $X$ و $Y$ على التوالي.
• الديناميكيات: تسير اللعبة في خطوات زمنية منفصلة. وخلافًا لألعاب بلوتو الاستاتيكية حيث يكون التوزيع لحظيًا، يجب أن تتحرك الموارد عبر الحواف. في كل خطوة:
  1. يقوم المدافع بتحريك الموارد بناءً على الحالة الحالية (مصفوفة الانتقال $K_t$).
  2. يراقب المهاجم حالة المدافع الجديدة ويقوم بتحريك الموارد (مصفوفة الانتقال $F_t$).
  3. شرط الفوز: يفوز المهاجم إذا تجاوز عدد موارد المهاجم عدد موارد المدافع عند أي عقدة رئيسية $i$ (أي $[y_t]_i > [x_t]_i$). ويفوز المدافع إذا استطاع منع حدوث هذا الشرط لفترة زمنية محددة $T$ (أو إلى ما لا نهاية).
• الهدف: تحديد نسبة الموارد الحرجة (CRR)، وهي $\alpha_T$، التي تمثل الحد الأدنى لنسبة $X/Y$ المطلوبة لضمان فوز المدافع ضد أي استراتيجية مهاجم عقلانية، وتوليف استراتيجيات التغذية الراجعة المقابلة.

2. المنهجية

يطور المؤلفون تحليلاً قائماً على الوصول (Reachability-based analysis) مدمجاً مع البرمجة الديناميكية القائمة على المجموعات لحل اللعبة.

أ. المجموعات القابلة للوصول والمتعدد الأوجه (Polytopes)

بدلاً من تحليل مساحات العمل مباشرة، يحلل المؤلفون المجموعات القابلة للوصول ($R(x_t)$)، والتي تمثل جميع الحالات التي يمكن للاعب الوصول إليها في خطوة واحدة من الحالة الحالية $x_t$.

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

ب. المجموعات المطلوبة ($P_{req}$)

لضمان الدفاع في الخطوة $t+1$، يجب على المدافع تخصيص الموارد بحيث يتفوق عددهم على أقصى تخصيص ممكن للمهاجم في كل عقدة رئيسية.

• يتم تعريف المجموعة المطلوبة $P_{req}(y_t)$ بأنها مجموعة حالات المدافع $x_{t+1}$ التي تحقق $[x_{t+1}]_i \geq \max_{y' \in R(y_t)} [y']_i$ لجميع العقد الرئيسية.
• إذا لم يستطع المدافع الوصول إلى $P_{req}(y_t)$ من حالته الحالية، فإنه يخسر.

ج. مجموعات Q (مجموعات الأمان لـ k-خطوة)

للتعامل مع الآفاق متعددة الخطوات، يعرّف المؤلفون مجموعات Q ($Q^{(i)}_k$)، والتي تمثل مجموعة حالات المدافع التي يمكنه من خلالها ضمان الدفاع لمدة $k$ من الخطوات ضد مهاجم متمركز حالياً في العقدة $i$.

• التعريف التكراري:
  $$Q^{(i)}_k = \{ x \mid x \in P_{req}(y^{(i)}) \land \forall j \in N_i, R(x) \cap Q^{(j)}_{k-1} \neq \emptyset \}$$
  وهذا يعني أن الحالة تكون آمنة لـ $k$ من الخطوات إذا كانت آمنة للخطوة الحالية، وَيمكن للمدافع الوصول إلى حالة آمنة لـ $k-1$ من الخطوات بغض النظر عن الجار الذي سينتقل إليه المهاجم في الخطوة التالية.
• الدفاع غير المحدود: يؤدي تقاطع جميع مجموعات $Q^{(i)}_k$ عندما $k \to \infty$ إلى مجموعات الأمان غير المحدودة ($Q^{(i)}_\infty$). إذا كانت هذه المجموعات غير فارغة، فإن الدفاع غير المحدود ممكن.

د. التعامل مع استراتيجيات التقسيم (Splitting Strategies)

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

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

هـ. الحل الخوارزمي

• خوارزمية Q-Prop: تقوم خوارزمية تكرارية بحساب مجموعات Q عبر نشر القيود عكسياً من الأفق الزمني. وهي تستخدم المجموعات القابلة للوصول العكسية (المحسوبة عبر رسم بياني معكوس) لتحديد تقاطع المجموعات القابلة للوصول والمجموعات المطلوبة بكفاءة.
• استخراج الإجراء: بمجرد تحديد حالة مستهدفة في مجموعة Q، تقوم الخوارزمية بحل برمجة خطية لإيجاد مصفوفة الانتقال المحددة (الإجراء) للوصول إلى تلك الحالة.

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

1. صياغة dDAB: أول صياغة للعبة بلوتو مع حركة موارد ديناميكية مقيدة بالرسم البياني وتغذية راجعة قائمة على الأدوار.
2. الشروط الضرورية والكافية: اشتقاق نسبة الموارد الحرجة (CRR) ومجموعات Q، مما يوفر شروطاً دقيقة لضمان الدفاع.
3. تكافؤ عدم التقسيم: إثبات أن تقسيم الموارد لا يوفر ميزة للمهاجم، مما يبسط عملية توليف الاستراتيجية بشكل كبير.
4. استراتيجيات التغذية الراجعة: توليف استراتيجيات تغذية راجعة مثلى لكل من اللاعبين تتفاعل مع الحالة الحالية بدلاً من الخطط المفتوحة (Open-loop) المعدة مسبقاً.
5. النسبة غير الصحيحة (Non-Integer CRR): إظهار أن CRR يمكن أن تكون غير صحيحة (مثلاً 3.5) في الألعاب ذات الأفق المحدود، مما يتحدى الحدس بأن نسب الموارد يجب أن تكون أعداداً صحيحة.

4. النتائج

• المحاكاة العددية:
  • تم عرضها على تضاريس رسوم بيانية متنوعة (حلقات، رسوم بيانية موجهة عامة).
  • أظهرت أن إضافة الحواف لا تؤدي دائماً إلى زيادة CRR؛ ففي بعض الحالات، تقللها (على سبيل المثال، إضافة حلقة ذاتية أو حواف ثنائية الاتجاه محددة يمكن أن يحسن كفاءة المدافع).
  • تم التحقق من أن مجموعات Q تتقارب نحو نقطة ثابتة في الرسوم البيانية المتصلة بقوة، مما يسمح بالدفاع غير المحدود.
• التجارب العتادية (Robotarium):
  • تم تنفيذ الخوارزمية على منصة اختبار روبوتية فيزيائية (Georgia Tech Robotarium).
  • السيناريو 1: 8 روبوتات مدافع مقابل 2 روبوت مهاجم على رسم بياني مكون من 7 عقد. نجح المدافع في الحفاظ على التفوق العددي عند العقد الرئيسية.
  • السيناريو 2: 4 روبوتات مدافع مقابل 1 روبوت مهاجم في بيئة مراقبة داخلية (9 غرف). حافظ النظام على المراقبة المستمرة رغم تحركات المهاجم العشوائية.
  • أكدت التجارب قدرة الخوارزمية على التعامل مع الموارد المنفصلة والمجسدة من خلال تغليف الحل المستمر باستراتيجية تخصيص منفصلة.

5. الأهمية

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

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