Distance-Constrained Unlabeled Multi-Agent Pathfinding

एक हलचल भरे शहर की कल्पना करें जहाँ हजारों छोटे, एक जैसे डिलीवरी बॉट्स को अपने चार्जिंग स्टेशनों से पैकेजों के ढेर तक तेजी से पहुंचना है। रोबोटिक्स की दुनिया में, इसे मल्टी-एजेंट पाथफाइंडिंग (MAPF) कहा जाता है। आमतौर पर, हम इन बॉट्स को बस इतना कहते हैं, "एक दूसरे से टकराना मत।" लेकिन वास्तविक दुनिया में, चीजें अधिक जटिल होती हैं। एक ड्रोन के पंखे पड़ोसी पर धूल उड़ा सकते हैं, या एक बड़े वेयरहाउस रोबोट को सुरक्षा बफर की आवश्यकता हो सकती है ताकि वह किसी शेल्फ से न टकरा जाए। इसका मतलब है कि रोबोट केवल एक-दूसरे के "करीब" नहीं हो सकते; उन्हें हर समय एक निश्चित दूरी बनाए रखनी होगी।

यह शोध पत्र इस समस्या को सुलझाने का प्रयास करता है जो एक कोरियोग्राफ किए गए नृत्य की तरह है, जहाँ सैकड़ों एक जैसे नर्तकों को कभी भी एक-दूसरे से कुछ निश्चित कदमों से अधिक करीब नहीं आना है। यदि वे बहुत करीब आते हैं, तो यह एक "टकराव" (collision) है। ट्विस्ट यह है कि नर्तक गुमनाम (anonymous) हैं; आपको इस बात से कोई फर्क नहीं पड़ता कि कौन सा विशिष्ट नर्तक किस विशिष्ट स्थान पर पहुँचता है, जब तक कि हर कोई सुरक्षित रूप से वहाँ पहुँच जाए। यह सरल लगता है, लेकिन जब आप इसमें "दूर रहने" का नियम जोड़ देते हैं, तो गणित अविश्वसनीय रूप से कठिन हो जाता है। यह एक ऐसी पहेली को हल करने जैसा है जहाँ टुकड़े अपना आकार बदलते रहते हैं, और कभी-कभी, इसे हल करने का एकमात्र तरीका ब्रह्मांड की आयु से भी लंबा हो सकता है।

यह शोध पत्र इस समस्या के बारे में सोचने का एक नया तरीका पेश करता है, जिसे लेखक डिस्टेंस-r इंडिपेंडेंट अनलेबल मल्टी-एजेंट पाथफाइंडिंग (या संक्षेप में rIUMAPF) कहते हैं। उन्होंने पाया कि जबकि इस समस्या का मानक संस्करण हल करना आसान है, "दूर रहने" का नियम जोड़ने से कंप्यूटर के लिए यह पता लगाना भी एक दुस्वप्न बन जाता है कि क्या कोई समाधान मौजूद है। हालाँकि, लेखकों ने हाथ पर हाथ रखकर नहीं बैठे। उन्होंने इस चुनौती से निपटने के लिए दो अलग-अलग उपकरण बनाए।

पहला उपकरण एक अति-सटीक वास्तुकार (super-precise architect) की तरह है। यह सबसे अच्छा, सबसे कुशल मार्ग खोजने के लिए 'इंटिजर लीनियर प्रोग्रामिंग' (ILP) नामक विधि का उपयोग करता है। इसे कंप्यूटर पर काम करने योग्य बनाने के लिए, उन्होंने एक चतुर "कंप्रेशन" ट्रिक का आविष्कार किया। कल्पना कीजिए कि आपके पास एक विशाल भूलभुलैया है जिसमें बहुत सारे खाली, बेकार गलियारे हैं। वास्तुकार उन खाली हिस्सों को छोटे, जादुय ब्लैक होल में सिकोड़ सकता है जो गुजरने वाले किसी भी रोबोट को सोख लेते हैं, जिससे भूलभुलैया बहुत छोटी और हल करने में तेज़ हो जाती है। यह रोबोटों के छोटे समूहों के लिए बहुत अच्छा काम करता है, लेकिन यदि आपके पास सैकड़ों रोबोट हैं, तो गणित बहुत भारी हो जाता है और वास्तुकार फंस जाता है।

दूसिमा उपकरण एक तेज़, सहज सुधारक (fast, intuitive improviser) है। पूरी प्रक्रिया से शुरू से अंत तक सटीक पथ की गणना करने के बजाय, यह एक "कॉन्फ़िगरेशन जनरेटर" का उपयोग करता है जिसे IU-PIBT कहा जाता है। इसे एक ट्रैफिक पुलिसकर्मी की तरह समझें जो वर्तमान दृश्य को देखता है और प्रत्येक रोबोट को बताता है, "ठीक है, तुम वहाँ जाओ, तुम यहाँ जाओ," चरण-दर-चरण। यह अविश्वसनीय रूप से तेज़ है और रोबोटों के विशाल झुंड को संभाल सकता है। हालाँकि, कभी-कभी ट्रैफिक पुलिसकर्मी भ्रमित हो जाता है और रोबोट गोल-गोल घूमने लगते हैं (एक "लाइवलॉक"), जिससे वे कभी भी अपने गंतव्य तक नहीं पहुँच पाते। इसे ठीक करने के लिए, लेखकों ने एक "सर्च" लेयर जोड़ी है जिसे IU-LaCAM कहा जाता है। यह एक स्मार्ट सुपरवाइजर की तरह काम करता है जो ट्रैफिक पुलिसकर्मी पर नज़र रखता है। यदि रोबोट गोल-गोल घूमने लगते हैं, तो सुपरवाइजर हस्तक्षेप करता है, लक्ष्यों को फिर से निर्धारित करता है, और गतिरोध को तोड़ देता है।

परिणाम प्रभावशाली हैं। जबकि यह समस्या सैद्धांतिक रूप से इतनी कठिन है कि खराब स्थितियों में इसे हल करने में अनंत समय लग सकता है, लेखकों के तरीके व्यवहार में आश्चर्यजनक रूप से अच्छा काम करते हैं। उनका "सुधारक" (IU-LaCAM) सेकंडों में बड़े मानचित्रों पर सैकड़ों एजेंटों को संभाल सकता है, और उन समस्याओं को हल कर सकता है जो अन्य तरीकों को उलझा देती हैं। उन्होंने पाया कि जबकि "वास्तुकार" (ILP) छोटे, उच्च-गुणवत्ता वाले प्लान के लिए बेहतरीन है, "सुधारक" बड़े पैमाने पर होने वाली अराजकता के लिए नायक है। दिलचस्प बात यह है कि उन्होंने यह भी खोजा कि एक बड़ी सुरक्षा दूरी (एक बड़ा "r") वास्तव में समस्या को हल करना आसान बना सकती है क्योंकि यह रोबर्स को संकीर्ण, भीड़भाड़ वाले गलियारों में फंसने से रोकता है।

संक्षेप में, यह शोध पत्र सिद्ध करता है कि सख्त सुरक्षा नियमों और एक जैसे रोबोटों के बावजूद, हम उनके विशाल समूहों के लिए पथ खोज सकते हैं। उन्होंने समस्या के हर संभव संस्करण को हल नहीं किया है (कुछ अभी भी इतने कठिन हैं कि किसी भी कंप्यूटर के लिए असंभव हैं), लेकिन उन्होंने एक ऐसा टूलकिट बनाया है जो हमें "सैद्धांतिक रूप से असंभव" से "व्यावहारिक रूप से संभव" की ओर ले जाता है।