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.
academicPSN Game: एक प्लेयर सिलेक्शन नेटवर्क के माध्यम से गेम-सैद्धांतिक भविष्यवाणी और योजना
मूल जानकारी
- पेपर ID: 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 (University of Texas at Austin)
- वर्गीकरण: cs.RO (रोबोटिक्स), math.OC (अनुकूलन और नियंत्रण)
- प्रकाशन समय: 2025 (arXiv प्रीप्रिंट)
- पेपर लिंक: https://arxiv.org/abs/2505.00213
सारांश
गेम सिद्धांत योजना ढांचा बहु-एजेंट इंटरैक्शन को मॉडल करने में प्रभावी है, लेकिन इसे बड़ी अनुकूलन समस्याओं को हल करने की आवश्यकता है, जिसमें चर की संख्या एजेंटों की संख्या के साथ बढ़ती है, जिससे कम्प्यूटेशनल समय लंबा हो जाता है और बड़े पैमाने पर रीयल-टाइम सिस्टम में अनुप्रयोग सीमित हो जाता है। इस समस्या को हल करने के लिए, यह पेपर प्रस्तावित करता है: 1) PSN Game - एक सीखने-आधारित गेम-सैद्धांतिक भविष्यवाणी और योजना ढांचा जो प्लेयर सिलेक्शन नेटवर्क (PSN) सीखकर रनटाइम को कम करता है; 2) लक्ष्य अनुमान नेटवर्क (GIN), जो PSN को अधूरी जानकारी वाले खेलों में उपयोग करने में सक्षम बनाता है जहां एजेंट के इरादे अज्ञात हैं। PSN प्लेयर सिलेक्शन मास्क आउटपुट करता है जो प्रभावशाली खिलाड़ियों और कम प्रासंगिक खिलाड़ियों को अलग करता है, जिससे स्व-एजेंट केवल चयनित खिलाड़ियों से जुड़ी छोटी मास्क गेम को हल कर सकता है। गेम में खिलाड़ियों की संख्या को कम करके, और इसके परिणामस्वरूप संबंधित अनुकूलन समस्या में चर की संख्या को कम करके, PSN सीधे कम्प्यूटेशनल समय को कम करता है।
अनुसंधान पृष्ठभूमि और प्रेरणा
समस्या परिभाषा
बहु-एजेंट सिस्टम में गेम सिद्धांत योजना ढांचे का सामना करने वाली मूल समस्या यह है कि कम्प्यूटेशनल जटिलता एजेंटों की संख्या के साथ घन रूप से बढ़ती है। जैसा कि चित्र 2 में दिखाया गया है, मौजूदा सॉल्वर का उपयोग करते समय, कम्प्यूटेशनल समय O(N³) के अनुसार बढ़ता है, जहां N खिलाड़ियों की संख्या है। यह गेम सिद्धांत विधियों को बड़े पैमाने पर रीयल-टाइम सिस्टम में अव्यावहारिक बनाता है।
अनुसंधान का महत्व
- रीयल-टाइम आवश्यकता: स्वायत्त वाहन, रोबोट नेविगेशन आदि अनुप्रयोगों को बार-बार पुनः योजना की आवश्यकता होती है, कम्प्यूटेशनल दक्षता महत्वपूर्ण है
- स्केलेबिलिटी चुनौती: वास्तविक परिदृश्यों में एजेंटों की संख्या अक्सर बहुत बड़ी होती है (जैसे घनी ट्रैफिक वातावरण)
- मानव व्यवहार से प्रेरणा: अनुसंधान से पता चलता है कि मानव ड्राइवर घनी ट्रैफिक में सहज रूप से पास के खतरनाक वाहनों को प्राथमिकता देते हैं, न कि सभी वाहनों की निगरानी करते हैं
मौजूदा विधियों की सीमाएं
मौजूदा प्लेयर सिलेक्शन विधियों में निम्नलिखित समस्याएं हैं:
- मजबूत सूचना निर्भरता: नियंत्रण इनपुट, लागत कार्य आदि गेम-विशिष्ट जानकारी की आवश्यकता है
- जटिल पैरामीटर ट्यूनिंग: पर्यावरण-विशिष्ट पैरामीटर समायोजन की आवश्यकता है
- निर्धारित चयन रणनीति: सरल अनुमानी (जैसे दूरी, ढाल) पर आधारित रैंकिंग विधियों में अनुकूलन क्षमता की कमी है
मुख्य योगदान
- अनुपर्यवेक्षित प्लेयर सिलेक्शन नेटवर्क (PSN) का प्रस्ताव: सूक्ष्म-भेद गतिशील गेम सॉल्वर का उपयोग करके प्रशिक्षण, सिलेक्शन मास्क के माध्यम से बैकप्रोपेगेशन का समर्थन करता है
- पर्यवेक्षित लक्ष्य अनुमान नेटवर्क (GIN) का निर्माण: ऐतिहासिक प्रक्षेपवक्र से एजेंट लक्ष्यों का अनुमान लगाता है, PSN को अज्ञात इरादों वाले परिदृश्यों में लागू करने में सक्षम बनाता है
- घटती समय-क्षितिज ढांचा विकसित करना: PSN का उपयोग करके घटाई गई गेम को हल करके कुशलतापूर्वक संतुलन रणनीति की पहचान करता है
- प्रायोगिक सत्यापन: बहु-एजेंट सिमुलेशन और वास्तविक मानव प्रक्षेपवक्र डेटासेट पर सत्यापन, PSN Game प्रभावी रूप से गेम स्केल को 50%-75% तक कम करता है, महत्वपूर्ण त्वरण प्राप्त करता है
विधि विवरण
कार्य परिभाषा
N एजेंटों के साथ सीमित समय-क्षितिज असतत-समय ओपन-लूप नैश गेम पर विचार करें, जहां प्रत्येक एजेंट i के पास स्थिति और नियंत्रण इनपुट है। एजेंट की स्थिति संक्रमण गतिविज्ञान समीकरण का पालन करता है:
प्रत्येक एजेंट का उद्देश्य संचयी लागत को कम करना है:
मॉडल आर्किटेक्चर
1. प्लेयर सिलेक्शन नेटवर्क (PSN)
PSN एक तंत्रिका नेटवर्क है जिसका कार्य प्रदर्शन और विरलता को संतुलित करने के लिए मास्क का अनुमान लगाना है। दो वेरिएंट प्रदान किए गए हैं:
- PSN-Full: सभी एजेंटों के पूर्ण ऐतिहासिक स्थिति को इनपुट के रूप में लेता है
- PSN-Partial: आंशिक अवलोकन को इनपुट के रूप में लेता है (जैसे केवल स्थिति जानकारी)
नेटवर्क संरचना:
- GRU एनकोडर (छिपा हुआ आयाम 64) का उपयोग करके प्रत्येक एजेंट के K-स्टेप अनुक्रम को प्रोसेस करता है
- MLP परतें: 256→128→32 (ReLU सक्रियण, dropout=0.3)
- Sigmoid आउटपुट परत निरंतर मास्क उत्पन्न करता है
2. मास्क नैश गेम
प्लेयर सिलेक्शन मास्क को परिभाषित करें, जहां:
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$ - आउटपुट: 2D लक्ष्य स्थिति $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. PSN से अनुकूली मास्क $M_k^i$ प्राप्त करता है 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), GIN के साथ PSN: - भविष्यवाणी मेट्रिक्स शीर्ष दो में रहते हैं - योजना मेट्रिक्स सभी शीर्ष तीन में हैं - सुरक्षा मेट्रिक्स अभी भी सर्वोत्तम हैं ### स्केलेबिलिटी सत्यापन 10-एजेंट प्रशिक्षण के साथ PSN को 20-एजेंट परिदृश्य में उपयोग करते हुए: - PSN-Full ADE: 0.3108m (सर्वोत्तम) - PSN-Partial ADE: 0.3152m (दूसरा) - पुनः प्रशिक्षण के बिना बड़े पैमाने के परिदृश्यों के अनुकूल ### वास्तविक डेटा सामान्यीकरण CITR पैदल यात्री डेटासेट पर: - PSN-Partial ADE: 0.4931m (सर्वोत्तम) - PSN-Full ADE: 0.4966m - पूर्ण गेम को हल करने के प्रदर्शन से भी बेहतर ## संबंधित कार्य ### गेम सिद्धांत योजना मौजूदा विधियां मुख्य रूप से छोटे पैमाने के वातावरण (≤5 एजेंट) पर ध्यान केंद्रित करती हैं, Newton-शैली सॉल्वर का उपयोग करके पुनरावृत्ति से हल करती हैं। जटिलता खिलाड़ियों की संख्या के साथ घन रूप से बढ़ती है, जो बड़े पैमाने पर रीयल-टाइम सिस्टम के लिए एक मौलिक बाधा है। ### प्लेयर सिलेक्शन विधियां **थ्रेसहोल्ड विधि**: पूर्वनिर्धारित दूरी थ्रेसहोल्ड के आधार पर एजेंटों का चयन करता है, बड़े पैमाने पर पैरामीटर ट्यूनिंग की आवश्यकता है। **रैंकिंग विधि**: शीर्ष-k सबसे प्रभावशाली एजेंटों का चयन करता है, लेकिन निश्चित संख्या चयन बहुत आक्रामक या रूढ़िवादी हो सकता है। **इस पेपर के लाभ**: 1. केवल ऐतिहासिक प्रक्षेपवक्र अवलोकन की आवश्यकता, विशेषाधिकार प्राप्त जानकारी की नहीं 2. ऑनलाइन पैरामीटर ट्यूनिंग की आवश्यकता नहीं 3. एजेंटों की संख्या को अनुकूली रूप से चुनता है ## निष्कर्ष और चर्चा ### मुख्य निष्कर्ष 1. PSN Game सफलतापूर्वक गेम स्केल को 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] --- यह पेपर गेम सिद्धांत योजना में कम्प्यूटेशनल जटिलता को हल करने में महत्वपूर्ण योगदान देता है, सीखने-संचालित प्लेयर सिलेक्शन के माध्यम से बहु-एजेंट सिस्टम की कम्प्यूटेशनल दक्षता में महत्वपूर्ण वृद्धि करता है, और बड़े पैमाने पर रीयल-टाइम अनुप्रयोगों के लिए मार्ग प्रशस्त करता है।