2025-11-12T02:22:29.481811

PSN Game: Game-theoretic Prediction and Planning via a Player Selection Network

Qiu, Ouano, Palafox et al.
While game-theoretic planning frameworks are effective at modeling multi-agent interactions, they require solving large optimization problems where the number of variables increases with the number of agents, resulting in long computation times that limit their use in large-scale, real-time systems. To address this issue, we propose 1) PSN Game: a learning-based, game-theoretic prediction and planning framework that reduces runtime by learning a Player Selection Network (PSN); and 2) a Goal Inference Network (GIN) that makes it possible to use the PSN in incomplete information games where agents' intentions are unknown. A PSN outputs a player selection mask that distinguishes influential players from less relevant ones, enabling the ego player to solve a smaller, masked game involving only selected players. By reducing the number of players in the game, and therefore reducing the number of variables in the corresponding optimization problem, PSN directly lowers computation time. The PSN Game framework is more flexible than existing player selection methods as it 1) relies solely on observations of players' past trajectories, without requiring full state, action, or other game-specific information; and 2) requires no online parameter tuning. Experiments in both simulated scenarios and human trajectory datasets demonstrate that PSNs outperform baseline selection methods in 1) prediction accuracy; and 2) planning safety. PSNs also generalize effectively to real-world scenarios in which agents' objectives are unknown without fine-tuning. By selecting only the most relevant players for decision-making, PSN Game offers a general mechanism for reducing planning complexity that can be seamlessly integrated into existing multi-agent planning frameworks.
academic

لعبة PSN: التنبؤ والتخطيط القائم على نظرية اللعبة عبر شبكة اختيار اللاعبين

المعلومات الأساسية

  • معرّف الورقة: 2505.00213
  • العنوان: PSN Game: Game-theoretic Prediction and Planning via a Player Selection Network
  • المؤلفون: Tianyu Qiu, Eric Ouano, Fernando Palafox, Christian Ellis, David Fridovich-Keil (جامعة تكساس في أوستن)
  • التصنيف: cs.RO (الروبوتات)، math.OC (التحسين والتحكم)
  • تاريخ النشر: 2025 (نسخة arXiv)
  • رابط الورقة: https://arxiv.org/abs/2505.00213

الملخص

إطار التخطيط القائم على نظرية اللعبة فعّال في نمذجة التفاعلات متعددة الوكلاء، لكنه يتطلب حل مشاكل تحسين كبيرة، حيث يزداد عدد المتغيرات مع زيادة عدد الوكلاء، مما يؤدي إلى أوقات حسابية طويلة وتحديد استخدامه في الأنظمة الفعلية الكبيرة. لحل هذه المشكلة، تقترح هذه الورقة: 1) لعبة PSN - إطار عمل للتنبؤ والتخطيط القائم على نظرية اللعبة والمبني على التعلم، من خلال تعلم شبكة اختيار اللاعبين (PSN) لتقليل وقت التشغيل؛ 2) شبكة الاستدلال على الأهداف (GIN)، التي تمكّن PSN من الاستخدام في ألعاب المعلومات غير الكاملة حيث تكون نوايا الوكلاء غير معروفة. تُخرج PSN قناع اختيار اللاعبين، الذي يميز بين اللاعبين المؤثرين واللاعبين الأقل صلة، مما يمكّن الوكيل الذاتي من حل لعبة قناع أصغر تتضمن فقط اللاعبين المختارين. بتقليل عدد اللاعبين في اللعبة، وبالتالي تقليل عدد المتغيرات في مشكلة التحسين المقابلة، تقلل PSN بشكل مباشر الوقت الحسابي.

الخلفية البحثية والدافع

تعريف المشكلة

المشكلة الأساسية التي تواجهها أطر التخطيط القائمة على نظرية اللعبة في الأنظمة متعددة الوكلاء هي أن التعقيد الحسابي ينمو بشكل مكعب مع عدد الوكلاء. كما هو موضح في الشكل 2، عند استخدام المحللات الحالية، يزداد وقت الحساب بـ O(N³)، حيث N هو عدد اللاعبين. هذا يجعل أساليب نظرية اللعبة غير عملية في الأنظمة الفعلية الكبيرة.

أهمية البحث

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

قيود الأساليب الموجودة

تعاني أساليب اختيار اللاعبين الموجودة من المشاكل التالية:

  1. اعتماد معلومات قوي: تتطلب معلومات خاصة بالمحاكاة مثل المدخلات المتحكم بها ودوال التكلفة
  2. تعقيد ضبط المعاملات: تتطلب تعديلات معاملات خاصة بالبيئة
  3. تجميد استراتيجية الاختيار: تفتقر طرق الترتيب البسيطة (مثل المسافة والتدرج) إلى التكيف

المساهمات الأساسية

  1. اقتراح شبكة اختيار اللاعبين غير الموجهة (PSN): التدريب باستخدام محلل ديناميكي للعبة قابل للتفاضل، يدعم الانتشار العكسي من خلال أقنعة الاختيار
  2. بناء شبكة الاستدلال على الأهداف الموجهة (GIN): استنتاج أهداف الوكلاء من المسارات التاريخية، مما يجعل PSN قابلة للتطبيق في سيناريوهات النوايا غير المعروفة
  3. تطوير إطار عمل الأفق الزمني المتناقص: استخدام PSN لتحديد استراتيجيات التوازن بكفاءة من خلال حل ألعاب مخفضة الحجم
  4. التحقق التجريبي: التحقق على محاكاة متعددة الوكلاء ومجموعات بيانات المسارات البشرية الحقيقية، حيث تقلل لعبة PSN حجم اللعبة بنسبة 50%-75%، مما يحقق تسريعاً ملحوظاً

شرح الطريقة

تعريف المهمة

ضع في الاعتبار لعبة ناش ذات الأفق الزمني المحدود والوقت المنفصل المفتوح الحلقة لـ N وكيل، حيث يمتلك كل وكيل i الحالة xki∈Rnx_k^i \in \mathbb{R}^n والمدخل التحكم uki∈Rmu_k^i \in \mathbb{R}^m. يتبع انتقال حالة الوكيل معادلة الديناميكا: xk+1i=fi(xki,uki)x_{k+1}^i = f^i(x_k^i, u_k^i)

الهدف من كل وكيل هو تقليل التكلفة المتراكمة: Ji(x,u;θi)=∑k=0Tcki(xk,uk;θi)J^i(x,u;\theta^i) = \sum_{k=0}^T c_k^i(x_k, u_k; \theta^i)

معمارية النموذج

1. شبكة اختيار اللاعبين (PSN)

PSN هي شبكة عصبية تهدف إلى استنتاج القناع MiM^i لتحقيق التوازن بين الأداء والندرة. توفر متغيرين:

  • PSN-Full: المدخل هو الحالة التاريخية الكاملة لجميع الوكلاء x0:Kx_{0:K}
  • PSN-Partial: المدخل هو الملاحظة الجزئية {h(xk)}k=0K\{h(x_k)\}_{k=0}^K (مثل معلومات الموقع فقط)

بنية الشبكة:

  • استخدام مشفر GRU (بُعد مخفي 64) لمعالجة تسلسل K خطوة لكل وكيل
  • طبقة MLP: 256→128→32 (تفعيل ReLU، dropout=0.3)
  • طبقة إخراج Sigmoid تنتج قناع مستمر mji∈[0,1]m_j^i \in [0,1]

2. لعبة ناش المقنعة

حدد قناع اختيار اللاعب Mi=(mji)∈{0,1}N−1M^i = (m_j^i) \in \{0,1\}^{N-1}، حيث:

1, & \text{الوكيل j مضمن في اللعبة} \\ 0, & \text{الوكيل j مستبعد} \end{cases}$$ لعبة القناع $\Gamma^i(\tilde{x}_0, \tilde{f}; \theta, M^i)$ تحتفظ فقط بمعاملات الوكلاء والحالات الأكثر صلة بالوكيل i. #### 3. شبكة الاستدلال على الأهداف (GIN) GIN هي شبكة مدفوعة بالبيانات تستنتج أهداف الوكيل $p_g^i$ من ملاحظات المسار الجزئي: - المدخل: المسار التاريخي $\{h(x_k)\}_{k=0}^K$ - المخرج: موقع الهدف ثنائي الأبعاد $p_g^i$ - دالة الخسارة: متوسط الخطأ التربيعي $L_{Goal} = \frac{1}{|D| \cdot N}\sum_{d \in D}\sum_{i \in [N]} \|p_{g,ref}^i - G_\phi(x_{0:K})\|$ ### تصميم دالة الخسارة يستخدم تدريب PSN دالة خسارة مركبة: **مهمة التنبؤ**: $$L_{Pred} = L_{Binary} + \sigma_1 L_{Sparsity} + \sigma_2 L_{Similarity}$$ **مهمة التخطيط**: $$L_{Plan} = L_{Binary} + \sigma_3 L_{Sparsity} + \sigma_4 L_{Cost}$$ حيث: - $L_{Binary} = \frac{1}{N}\sum_{j=1}^N m_j^i(1-m_j^i)$: يعزز القناع نحو القيم الثنائية - $L_{Sparsity} = \frac{\|M^i\|_1}{N}$: يشجع اختيار عدد أقل من الوكلاء - $L_{Similarity}$: يشجع اختيار مجموعة فرعية من الوكلاء يمكنها استعادة المسار المرصود - $L_{Cost}$: يشجع اختيار الوكلاء المناسبين لتقليل تكلفة اللعبة ### تنفيذ الأفق الزمني المتناقص تعمل الخوارزمية في كل خطوة زمنية $k$: 1. استنتاج أهداف الوكيل من خلال GIN 2. الحصول على قناع تكيفي $M_k^i$ باستخدام PSN 3. حل لعبة القناع للحصول على استراتيجية OLNE 4. تنفيذ مدخل التحكم للخطوة الأولى وتحديث الحالة ## إعداد التجارب ### مجموعات البيانات **السيناريوهات المحاكاة**: - سيناريو 4 وكلاء: بيئة 5m×5m - سيناريو 10 وكلاء: بيئة 7m×7m - سيناريو 20 وكيل: بيئة 7m×7m (اختبار قابلية التوسع) **البيانات الحقيقية**: - مجموعة بيانات المشاة CITR: بيئة 7.5m×25.5m، 10 مشاة **إعدادات اللعبة**: - فضاء الحالة: 4 أبعاد (الموقع + السرعة) - الديناميكا: نموذج المتكامل المزدوج - دالة التكلفة: تتضمن تتبع الهدف وعقوبة السرعة وتكلفة التحكم وتجنب الاصطدام ### مؤشرات التقييم **مهمة التنبؤ**: - ADE (متوسط خطأ الإزاحة): متوسط خطأ الإزاحة - FDE (خطأ الإزاحة النهائي): خطأ الإزاحة النهائي - Consistency: اتساق الاختيار **مهمة التخطيط**: - Navigation Cost: تكلفة الملاحة - Collision Cost: تكلفة الاصطدام - Control Cost: تكلفة التحكم - Minimum Distance: الحد الأدنى للمسافة - Trajectory Smoothness: سلاسة المسار - Trajectory Length: طول المسار ### طرق المقارنة 1. **متغيرات PSN**: PSN-Threshold, PSN-Rank 2. **طرق المسافة**: Distance, kNNs 3. **طرق التدرج**: Gradient, Hessian, Cost Evolution 4. **طرق القيود**: BF (Barrier Function), CBF (Control Barrier Function) ## نتائج التجارب ### النتائج الرئيسية #### أداء التنبؤ (الجدول 2) في سيناريو 4 وكلاء: - PSN-Full ADE: 0.1834m (الأمثل) - PSN-Partial ADE: 0.1876m - أفضل خط أساس (Cost Evolution) ADE: 0.1861m في سيناريو 10 وكلاء: - PSN-Partial ADE: 0.2213m (الأمثل) - PSN-Full ADE: 0.2314m - أفضل خط أساس (kNNs) ADE: 0.2343m #### أداء التخطيط (الجدول 3) تتفوق PSN في مؤشرات السلامة: - **تكلفة الاصطدام**: تحقق الأمثل في سيناريوهات 4 و10 وكلاء - **الحد الأدنى للمسافة**: تحتل المراكز الثلاثة الأولى في كلا السيناريوهين - مقارنة باللعبة الكاملة، تدهور الأداء الآمن طفيف ### تكيف لعبة المعلومات غير الكاملة في سيناريو الأهداف غير المعروفة (الجداول 4-5)، PSN مع GIN: - مؤشرات التنبؤ تبقى في المراكز الأولى - مؤشرات التخطيط تحتل المراكز الثلاثة الأولى - مؤشرات السلامة لا تزال الأمثل ### التحقق من قابلية التوسع استخدام PSN المدربة على 10 وكلاء في سيناريو 20 وكيل: - PSN-Full ADE: 0.3108m (الأمثل) - PSN-Partial ADE: 0.3152m (الثاني) - يمكن التكيف مع سيناريوهات أكبر دون إعادة تدريب ### التعميم على البيانات الحقيقية على مجموعة بيانات المشاة CITR: - PSN-Partial ADE: 0.4931m (الأمثل) - PSN-Full ADE: 0.4966m - يتفوق حتى على أداء حل اللعبة الكاملة ## الأعمال ذات الصلة ### التخطيط القائم على نظرية اللعبة تركز الأساليب الموجودة على بيئات صغيرة الحجم (≤5 وكلاء)، باستخدام محللات بأسلوب نيوتن للحل التكراري. يزداد التعقيد بشكل مكعب مع عدد اللاعبين، مما يصبح عائقاً أساسياً للأنظمة الفعلية الكبيرة. ### طرق اختيار اللاعبين **طرق الحد الأدنى**: اختيار الوكلاء بناءً على حد أدنى محدد مسبقاً للمسافة، يتطلب ضبط معاملات كبير. **طرق الترتيب**: اختيار أفضل k وكيل مؤثر، لكن الاختيار بعدد ثابت قد يكون متطرفاً جداً أو متحفظاً جداً. **مزايا هذه الورقة**: 1. تتطلب فقط ملاحظات المسار التاريخي، بدون معلومات امتيازية 2. لا تتطلب ضبط معاملات عبر الإنترنت 3. اختيار تكيفي لعدد الوكلاء ## الخلاصة والمناقشة ### الاستنتاجات الرئيسية 1. تنجح لعبة PSN في تقليل حجم اللعبة بنسبة 50%-75%، مما يحقق تسريعاً حسابياً ملحوظاً 2. تتفوق على طرق الخط الأساس الموجودة في دقة التنبؤ وسلامة التخطيط 3. تتمتع بقدرة تعميم جيدة، يمكنها التكيف مع سيناريوهات أكبر حجماً والبيانات الحقيقية ### القيود 1. **تقريب القناع المستمر**: استخدام أقنعة مستمرة لدعم الانتشار العكسي، يتطلب تحويل عتبة في وقت التشغيل 2. **اعتماد بيانات التدريب**: يتطلب بيانات تدريب تم إنشاؤها من خلال حل اللعبة الكاملة 3. **افتراضات نموذج الديناميكا**: تركز التجارب بشكل أساسي على نموذج المتكامل المزدوج ### الاتجاهات المستقبلية 1. التوسع إلى نماذج ديناميكية أكثر تعقيداً 2. البحث عن استدلالات معاملات لعبة أخرى 3. استكشاف استراتيجيات التدريب من النهاية إلى النهاية ## التقييم المتعمق ### المزايا 1. **أهمية المشكلة**: حل الاختناق الحسابي الأساسي في التخطيط القائم على نظرية اللعبة 2. **ابتكار الطريقة**: أول دمج للتعلم العميق مع نظرية اللعبة لاختيار اللاعبين 3. **كفاية التجارب**: تغطي المحاكاة والبيانات الحقيقية، التحقق من فرضيات متعددة 4. **القيمة العملية**: توفر آلية عامة يمكن دمجها مباشرة في الأطر الموجودة ### أوجه القصور 1. **نقص التحليل النظري**: عدم توفير ضمانات نظرية للتقارب أو خطأ التقريب 2. **النفقات الحسابية**: على الرغم من تقليل وقت حل اللعبة، إضافة نفقات استدلال الشبكة 3. **قيود السيناريو**: التحقق الرئيسي على مهام الملاحة، تطبيقية الألعاب الأخرى غير معروفة ### التأثير 1. **المساهمة الأكاديمية**: توفير منظور حل جديد للأنظمة متعددة الوكلاء الكبيرة 2. **التطبيق العملي**: قيمة تطبيق مباشرة في مجالات القيادة الذاتية وأسراب الروبوتات 3. **قابلية الاستنساخ**: توفير تفاصيل تنفيذ شاملة وإعدادات معاملات ### السيناريوهات المناسبة 1. **بيئات متعددة الوكلاء الكثيفة**: مثل المرور الحضري والملاحة بين الحشود 2. **الأنظمة ذات متطلبات الوقت الفعلي العالي**: تحتاج إلى إعادة تخطيط متكررة في بيئات ديناميكية 3. **سيناريوهات الملاحظة الجزئية**: ألعاب المعلومات غير الكاملة حيث تكون نوايا الوكلاء غير معروفة ## المراجع تستشهد الورقة بـ 35 مرجعاً ذا صلة، تغطي بشكل أساسي: - طرق التخطيط القائمة على نظرية اللعبة [8, 28, 9, 15] - نمذجة التفاعلات متعددة الوكلاء [17, 20, 21, 24] - طرق اختيار اللاعبين الاستكشافية [2, 27, 30] - آليات الانتباه واختيار الجيران [3, 6, 32] --- تقدم هذه الورقة مساهمة مهمة في حل التعقيد الحسابي للتخطيط القائم على نظرية اللعبة، حيث تحسن بشكل كبير الكفاءة الحسابية للأنظمة متعددة الوكلاء من خلال اختيار اللاعبين المدفوع بالتعلم، مما يمهد الطريق للتطبيقات الفعلية الكبيرة والفعلية في الوقت الحقيقي.