💻 computer science

Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem

यह शोध पत्र MWRP-CP3 प्रस्तुत करता है, जो एक कुशल इष्टतम प्लैनर (optimal planner) है जो 200 गुना से अधिक की गति वृद्धि के साथ मल्टीपल वॉचमैन रूट प्रॉब्लम को हल करने के लिए स्टेट-स्पेस प्रूनिंग और उन्नत ह्यूरिस्टिक्स का उपयोग करता है, साथ ही इसमें प्रमाणित इष्टतम सीमाओं वाले स्केलेबल उपइष्टतम (suboptimal) एल्गोरिदम भी हैं जो तीन गुना बड़े मानचित्रों को संभालने में सक्षम हैं।

मूल लेखक: Srikar Gouru, Ariel Felner, Jiaoyang Li

प्रकाशित 2026-04-20

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Srikar Gouru, Ariel Felner, Jiaoyang Li

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक सुरक्षा टीम के प्रबंधक हैं। आपके पास एक बड़ी, जटिल इमारत है (जैसे कोई भूलभुलैया या किला) जिसमें कई छिपे हुए कोने हैं, और आपको वहां गश्त लगाने के लिए चौकीदारों (watchmen) की एक टीम तैनात करने की आवश्यकता है।

आपका लक्ष्य सरल है: इमारत का एक-एक इंच किसी न किसी समय कम से कम एक चौकीदार को दिखाई देना चाहिए।

लेकिन इसमें एक पेंच है: आप केवल कोई भी समाधान नहीं चाहते; आप सबसे तेज़ संभव समाधान चाहते हैं। आप जानना चाहते हैं कि सबसे धीमे चौकीदार को अपना रास्ता पूरा करने में न्यूनतम कितना समय लगेगा। यदि एक चौकीदार को 100 कदम चलना पड़ता है और अन्य को केवल 10, तो आपकी टीम तब तक "पूरी" नहीं मानी जाएगी जब तक कि वह एक व्यक्ति अपना काम पूरा नहीं कर लेता। इसे मल्टीपल वॉचमैन रूट प्रॉब्लम (MWRP) कहा जाता है।

यह शोध पत्र इस पहेली को पहले की तुलना में बहुत तेज़ी से हल करने के लिए उपकरणों का एक नया सेट पेश करता है। उन्होंने इसे कैसे किया, इसका विवरण रोजमर्रा के उदाहरणों के साथ यहाँ दिया गया है।

1. समस्या: यह इतना कठिन क्यों है?

इमारत को टाइल्स के एक विशाल ग्रिड के रूप में सोचें। यदि आपके पास 5 चौकीदार हैं, तो कंप्यूटर को यह गणना करनी होगी कि वे पाँचों एक ही समय में कहाँ हैं, हर कदम पर।

पुराना तरीका: एक 5-आयामी (5-dimensional) रूबिक क्यूब को हल करने की कोशिश करने की कल्पना करें। कंप्यूटर लाखों संयोजनों को आज़माएगा, यह जाँचते हुए कि क्या हर कोना देखा जा रहा है। यह घास के ढेर में सुई खोजने जैसा है जहाँ घास का ढेर बढ़ता ही जा रहा है।
लक्ष्य: लेखकों चाहते थे कि यह खोज इतनी तेज़ हो सके कि इसे ढही हुई इमारतों में जीवित बचे लोगों को खोजने या जंगल की आग का पता लगाने जैसी वास्तविक आपात स्थितियों में इस्तेमाल किया जा सके।

2. समाधान: "MWRP-CP3" (स्मार्ट ऑप्टिमाइज़र)

लेखकों ने एक अत्यंत बुद्धिमान प्लानर बनाया जिसे MWRP-CP3 कहा जाता है। इसे एक जीनियस टूर गाइड की तरह समझें जिसे पता है कि चलने शुरू करने से पहले ही कौन से रास्ते बेकार हैं। उन्होंने इसे तेज़ बनाने के लिए तीन मुख्य तरकीबों का उपयोग किया:

अ. "परछाई" वाली तरकीब (स्टेट स्पेस रिडक्शन)

कल्पना कीजिए कि आप एक गलियारे में चल रहे हैं। यदि आप बाईं ओर देखते हैं और एक अंधेरा कोना देखते हैं, तो आप स्वचालित रूप से उसके ठीक बगल के फर्श को भी देख लेते हैं। आपको उस फर्श तक देखने के लिए चलने की ज़रूरत नहीं है; कोने को देखना ही उसे कवर कर देता है।

तरकीब: एल्गोरिदम यह पहचान लेता है कि इमारत के कुछ स्थान दूसरों द्वारा "डोमिनेटेड" (अधिग्रहित) हैं। यदि आप स्थान A को देखते हैं, तो आप स्थान B को अपने आप देख लेते हैं।
परिणाम: कंप्यूटर स्थान B को देखने के लिए समय बर्बाद करना बंद कर देता है। वह बस कहता है, "यदि हम A को देखते हैं, तो B कवर हो गया।" यह गणना की संभावनाओं को 95% तक कम कर देता है। यह ऐसा ही है जैसे यह मान लेना कि आपको समुद्र तट पर रेत के हर एक कण की जांच करने की आवश्यकता नहीं है क्योंकि यदि आप ऊपरी परत की जांच कर लेते हैं, तो आप जानते हैं कि नीचे की परत भी कवर है।

ब. "शॉर्टकट" वाली तरकीख (पिवट प्रूनिंग)

सर्वश्रेष्ठ मार्ग की गणना करते समय, कंप्यूटर कभी-कभी यह सुनिश्चित करने के लिए "चेकपॉइंट्स" (पिवोट्स) चुनता है कि कुछ भी छूटा न रहे। कभी-कभी, यह ऐसा चेकपॉइंट चुन लेता है जो वास्तव में रास्ता लंबा कर देता है क्योंकि यह एक चक्कर (detour) लगाने के लिए मजबूर करता है।

तरकीफ: एल्गोरिदम इन चेकपॉइंट्स को देखता है और पूछता है, "क्या यह चेकपॉइंट वास्तव में मदद कर रहा है, या यह केवल एक चक्कर है?" यदि कोई चेकपॉइंट केवल एक शॉर्टकट है जो गणित को उलझा देता है, तो एल्गोरिदम उसे हटा देता है।
परिणाम: कंप्यूटर अनावश्यक चक्करों को हल करने की कोशिश करना बंद कर देता है, जिससे गणना बहुत तेज़ हो जाती है।

स. "असेंबली लाइन" वाली तरकीफ (पैरलल ह्यूरिस्टिक्स)

आमतौर पर, एक कंप्यूटर एक समस्या हल करता है, फिर अगली, फिर अगली।

तरकीफ: लेखकों ने कंप्यूटर को एक फैक्ट्री असेंबली लाइन की तरह काम करने के लिए बनाया। जब यह वर्तमान सर्वोत्तम पथ की गणना पूरी कर रहा होता है, तो यह बैकग्राउंड में अगले 100 संभावित पथों की गणना पहले से ही शुरू कर देता है।
परिणाम: कंप्यूटर कभी खाली नहीं बैठता। यह हमेशा आगे की गणना करता रहता है, जिससे पूरी प्रक्रिया अविश्वसनीय रूप से तेज़ हो जाती है।

मुख्य बात: उनका नया प्लानर पुराने सबसे अच्छे तरीके से 200 गुना तेज़ है। यह उन मानचित्रों को भी हल कर सकता है जिन्हें पहले उचित समय में हल करना असंभव था।

3. "काफी अच्छे" समाधान (बाउंडेड सबऑप्टिमल एल्गोरिदम)

कभी-कभी, आपको बिल्कुल सटीक समाधान की आवश्यकता नहीं होती; आपको बस एक बहुत अच्छा समाधान चाहिए, और वह भी अभी।

उदाहरण: कल्पना कीजिए कि आपकी फ्लाइट छूटने वाली है। आपको गेट तक पहुँचने के लिए सबसे छोटे रास्ते की आवश्यकता नहीं है; आपको बस एक ऐसे रास्ते की आवश्यकता है जो आपको 20 मिनट के बजाय 15 मिनट में वहाँ पहुँचा दे।
उपकरण: उन्होंने "MxWA*" और "फोकल सर्च" बनाए हैं। ये एक GPS की तरह हैं जो कहते हैं, "मैं सबसे छोटा रास्ता सुनिश्चित नहीं कर सकता, लेकिन मैं वादा करता हूँ कि जो रास्ता मैं आपको दे रहा हूँ वह सबसे अच्छे रास्ते से 20% से अधिक लंबा नहीं होगा।"
लाभ: ये एल्गोरिदम उन मानचित्रों को संभाल सकते हैं जो मूल रूप से परफेक्ट प्लानर की तुलना में 3 गुना बड़े हैं। ये समूह के "स्पीड डेमन" (गति के महारथी) हैं।

4. "पॉलिश" (पोस्टप्रोसेसिंग)

कल्पना कीजिए कि आपके पास धावकों की एक टीम है। आपने उन्हें रूट सौंप दिए हैं, लेकिन एक व्यक्ति बहुत दूर दौड़ रहा है जबकि अन्य आराम कर रहे हैं।

तरकीफ: लेखकों ने एक "पॉलिशिंग" टूल बनाया है। यह तैयार योजना को देखता है, सबसे लंबे मार्ग वाले व्यक्ति को ढूंढता है, और पूछता है, "क्या मैं तुम्हें कोई भी अंधेरा कोना बिना छोड़े, एक छोटा रास्ता दे सकता हूँ?"
परिणाम: यह एक "काफी अच्छे" प्लान को लेता है और उसे लगभग पूर्ण बनाने के लिए उसमें सुधार करता है, जो अक्सर कुछ ही सेकंड में होता है।

सारांश

यह शोध पत्र कंप्यूटर को स्मार्ट सुरक्षा गार्ड बनने की शिक्षा देने के बारे में है।

सब कुछ न देखें: उन चीजों को अनदेखा करें जिन्हें आप किसी और चीज़ को देखकर देख सकते हैं (सेल डोमिनेंस)।
चक्कर न लगाएं: अनावश्यक चेकपॉइंट्स को हटा दें (पिवट प्रूनिंग)।
तेज़ी से काम करें: एक साथ कई गणनाएँ करें (पैरेललिज्म)।
लचीले बनें: यदि आप तुरंत सटीक उत्तर नहीं पा सकते, तो जल्दी से एक "बहुत अच्छा" उत्तर खोजें और बाद में उसे पॉलिश करें।

इन विधियों की बदौलत, अब हम सेकंडों में विशाल क्षेत्रों के लिए जटिल सुरक्षा मार्गों की योजना बना सकते हैं, जो आपातकालीन प्रतिक्रिया, रोबोटिक्स और अन्वेषण के लिए एक बड़ा कदम है।

यहाँ शोध पत्र "Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या की परिभाषा

यह शोध पत्र मल्टीपल वॉचमैन रूट प्रॉब्लम (MWRP) को संबोधित करता है, जो क्लासिक वॉचमैन रूट प्रॉब्लम (WRP) का एक सामान्य रूप है।

उद्देश्य: $M$ एजेंटों (वॉचमेन) के लिए पथों का एक सेट खोजना (जिसे 2D ग्रिड ग्राफ के रूप में मॉडल किया गया है) ताकि लक्ष्य सेट $U$ के प्रत्येक सेल को कम से कम एक एजेंट के कम से कम एक पथ के साथ देखा जा सके।
अनुकूलन लक्ष्य (Optimization Goal): प्राथमिक ध्यान मेकस्पैन (Makespan) उद्देश्य (min-max) पर है, जो सभी एजेंटों के बीच सबसे लंबे पथ की लंबाई को न्यूनतम करने का प्रयास करता है। यह आपदा राहत और अग्निशमन जैसे समय-संवेदनशील अनुप्रयोगों के लिए महत्वपूर्ण है।
बाधाएं (Constraints):
- दृश्यता (Visibility): इसे लाइन-ऑफ-साइट (LOS) फंक्शन (जैसे, ब्रेसेनहैम LOS) द्वारा परिभाषित किया गया है, जो यह निर्धारित करता है कि किसी दिए गए सेल से कौन से सेल दिखाई देते हैं।
- टकराव (Collisions): शोध पत्र यह मानता है कि एजेंट एक ही सेल में रह सकते हैं (कोई इंटर-एजेंट टकराव बाधा नहीं है) ताकि कवरेज/दृश्यता के पहलू की जटिलता पर ध्यान केंद्रित किया जा सके।
- जटिलता: यह सिद्ध किया गया है कि यह समस्या NP-hard है।

2. कार्यप्रणाली (Methodology)

लेखक सटीक अनुकूलतम समाधानों (exact optimal solvers) से लेकर सीमित उप-इष्टतम (bounded suboptimal) विधियों और पोस्ट-प्रोसेसिंग तकनीकों तक के एल्गोरिदम का एक समूह प्रस्तावित करते हैं।

A. इष्टतम खोज: MWRP-CP3

मुख्य योगदान MWRP-CP3 है, जो मौजूदा MWRP-A* (संयुक्त-स्थान A*) पर आधारित एक उन्नत इष्टतम खोज एल्गोरिदम है। यह खोज स्थान और गणना समय को नाटकीय रूप रूप से कम करने के लिए चार प्रमुख नवाचार पेश करता है:

स्टेट स्पेस रिडक्शन (सेल और पाथ डोमिनेंस):
- सेल डोमिनेंस (CD): उन सेल्स $s_1$ और $s_2$ की पहचान करता है जहाँ $s_1$ के लिए वॉचर्स का सेट $s_2$ के वॉचर्स का एक उपसमुच्चय (subset) है ( $W(s_1) \subseteq W(s_2)$ )। यदि $s_1$ देखा जाता है, तो $s_2$ भी देखे जाने की गारंटी है। अतः $s_2$ को लक्ष्य सेट $U$ से हटा दिया जाता है।
- पाथ डोमिनेंस (PD): उन सेल्स $s_1$ और $s_2$ की पहचान करता है जहाँ $s_1$ को देखने वाला कोई भी पथ अनिवार्य रूप से एक ऐसे स्थान से गुजरता है जो $s_2$ को देखता है। इस प्रकार $s_2$ को हटा दिया जाता है।
- प्रभाव: ये विधियाँ संरचित मानचित्रों पर अवशेष सेट $U$ (वे सेल जिन्हें कवरेज की आवश्यकता है) को 95% से अधिक कम कर देती हैं, जिससे स्टेट स्पेस $O(|C|^M 2^{|U|})$ काफी छोटा हो जाता है।
पिवट प्रूनिंग (Pivot Pruning):
- ह्यूरिस्टिक (Heuristic) "पिवोट्स" (देखे जाने वाले प्रमुख सेल) के ग्राफ पर मल्टीपल ट्रैवलिंग सेल्समैन प्रॉब्लम (mTSP) को हल करने पर निर्भर करता है।
- लेखक उन पिवोट्स को हटाने के लिए एक ग्रीडी रिमूवल रणनीति पेश करते हैं जो mTSP ग्राफ में "शॉर्टकट" के रूप में कार्य करते हैं। इन पिवोट्स को हटाने से अक्सर ह्यूरिस्टिक मान बढ़ जाता है (इसे अधिक सूचनात्मक बनाता है) बिना एडमिसिबिलिटी (admissibility) से समझौता किए, जिससे अभिसरण (convergence) तेज हो जाता है।
समानांतर ह्यूरिस्टिक गणना (Parallel Heuristic Calculation):
- mTSP ह्यूरिस्टिक गणना मुख्य बाधा है। लेखक बैच A* लागू करते हैं, जहाँ विस्तार किए जाने वाले अगले $N$ नोड्स के लिए ह्यूरिस्टिक की गणना समानांतर (parallel) में की जाती है। यह A* की एसिम्प्टोटिक कॉम्प्लेक्सिटी को बदले बिना आधुनिक मल्टी-कोर प्रोसेसरों का उपयोग करता है।

B. बाउंडेड सब-ऑप्टिमल सर्च (BSS)

बड़े मानचित्रों के लिए स्केल करने हेतु जहाँ इष्टतम खोज अव्यावहारिक है, यह शोध पत्र ऐसे एल्गोरिदम पेश करता है जो इष्टतम लागत ( $C \le w \cdot C^*$ ) के एक कारक $w$ के भीतर समाधान की गारंटी देते हैं।

मिनिमैक्स वेटेड A (MxWA):**
- मेकस्पैन उद्देश्य के लिए विशेष रूप से तैयार किया गया एक नया वेरिएंट।
- लागतों के योग को वेट करने के बजाय, यह $f_{MxW}(n) = \max_k \{ g_k(n) + w \cdot h_k(n) \}$ की गणना करता है, जहाँ $k$ प्रत्येक एजेंट का प्रतिनिधित्व करता है।
- यह उन एजेंटों को प्राथमिकता देता है जिनका शेष खोज प्रयास कम है, जबकि $w$ -सब-ऑप्टिमलिटी बाउंड को बनाए रखता है।
- इसमें एक Anytime संस्करण (AMxWA*) भी शामिल है जो समाधान में निरंतर सुधार करता है।
फोकल सर्च (FS) नए ह्यूरिस्टिक्स के साथ:
- यह एक "फोकल" सूची से नोड्स चुनने के लिए एक माध्यमिक ह्यूरिस्टिक ( $h_{FOCAL}$ ) का उपयोग करता है।
- mTSP पथ लंबाई के आधार पर दो नए ह्यूरिस्टिक्स प्रस्तावित करता है: सम ऑफ रिमेनिंग कॉस्ट (SORC) और मैक्स ऑफ रिमेनिंग कॉस्ट (MORC)।
- इसमें एक एनीटाइम वेरिएंट (AFS) भी शामिल है।

C. पोस्टप्रोसेसिंग फ्रेमवर्क

यह एक मौजूदा उप-इष्टतम समाधान को लेता है और समस्या को विभाजित करता है।
यह सबसे लंबे पथ वाले एजेंट ( $a_{max}$ ) की पहचान करता है और "न्यूनतम जिम्मेदारी" (वर्तमान समाधान में केवल $a_{max}$ द्वारा दृश्य सेल) की गणना करता है।
इन विशिष्ट सेल्स के लिए $a_{max}$ के लिए एकल-एजेंट इष्टतम पथ को फिर से हल करता है।
यह तब तक दोहराया जाता है जब तक कि कोई और सुधार न मिल जाए। यह न्यूनतम रनटाइम ओवरहेड के साथ समाधान की गुणवत्ता में काफी सुधार करता है।

3. प्रमुख योगदान

MWRP-CP3: पहला इष्टतम सॉल्वर जो हजारों सेल्स वाले मानचित्रों पर जटिल MWRP इंस्टेंस को संभालने में सक्षम है, जो पिछले बेसलाइन (MWRP-A*) की तुलना में 200× तेज़ चलता है।
MxWA:* संयुक्त-स्थान खोज (joint-space search) में मेकस्पैन उद्देश्य के लिए विशेष रूप से अनुकूलित पहला वेटेड A* अनुप्रयोग, जो प्रमाणित बाउंडेड सब-ऑप्टिमलिटी प्रदान करता है।
स्केलेबिलिटी: MWRP-CP3 द्वारा संभाले जाने वाले ~200 सेल्स की तुलना में, 1,500+ ग्रिड सेल्स और 5+ एजेंटों वाले मानचित्रों को हल करने की क्षमता प्रदर्शित की।
दक्षता तकनीकें: यह प्रमाणित किया गया कि सेल/पाथ डोमिनेंस और पिवट प्रूनिंग, खोज स्थान को कम करने के लिए महत्वपूर्ण हैं, जबकि समानांतर ह्यूरिस्टिक गणना कम्प्यूटेशनल बाधा को दूर करती है।

4. प्रयोगात्मक परिणाम

स्टेट स्पेस रिडक्शन: संरचित मानचित्रों (मेज़, माइनक्राफ्ट-प्रेरित) पर, सेल और पाथ डोमिनेंस ने क्रमशः लक्ष्य सेट $U$ को 95.3% और 89.0% तक कम कर दिया।
रनटाइम प्रदर्शन:
- MWRP-CP3 ने MWRP-A* की तुलना में 200× तेज़ समाधान निकाला।
- इसने उन जटिल मामलों को हल किया जिन्हें MWRP-A* 200 सेकंड की समय सीमा के भीतर हल करने में विफल रहा।
सब-ऑप्टिमल स्केलिंग:
- MxWA* और फोकल सर्च वेरिएंट उन मानचित्रों को हल करने में सक्षम थे जो MWRP-CP3 के लिए बहुत बड़े थे।
- उच्च-आयामी संयुक्त स्थानों में फोकल सूची को प्रबंधित करने के ओवरहेड के कारण, उच्च एजेंट गणनाओं पर MxWA* आमतौर पर फोकल सर्च से बेहतर प्रदर्शन करता है।
पोस्टप्रोसेसिंग: इसने कुल रनटाइम में केवल 8% की वृद्धि के साथ समाधान लागत में उल्लेखनीय सुधार किया (उदाहरण के लिए, एक टेस्ट केस पर MxWA* लागत को 124 से घटाकर 93 करना)।
Anytime व्यवहार: सभी एनीटाइम वेरिएंट (AMxWA*, AFS) ने तीव्र प्रारंभिक समाधान पीढ़ी के बाद निरंतर गुणवत्ता सुधार दिखाया।

5. महत्व

यह कार्य सैद्धांतिक इष्टतमता और व्यावहारिक स्केलेबिलिटी के बीच के अंतर को पाटता है।

वास्तविक दुनिया में प्रयोज्यता: सेकंडों में बड़े पैमाने के मानचित्रों (हजारों सेल) को हल करने की क्षमता प्रदान करके, ये एल्गोरिदम वास्तविक समय की आपातकालीन स्थितियों (जैसे खोज और बचाव, जंगल की आग की निगरानी) के लिए इष्टतम या निकट-इष्टतम योजना को संभव बनाते हैं।
सैद्धांतिक प्रगति: MxWA* का परिचय वेटेड सर्च ह्यूरिस्टिक्स को मिन-मैक्स उद्देश्यों (min-max objectives) के अनुप्रयोग तक विस्तारित करता है, जो एक ऐसा क्षेत्र है जहाँ मानक वेटेड A* सीधे लागू नहीं होता है।
ओपन सोर्स: लेखक एक सार्वजनिक कोडबेस और वीडियो प्रदर्शन प्रदान करते हैं, जिससे रोबोटिक्स और AI समुदायों में अनुसंधान और अपनाने की सुविधा मिलती है।

संक्षेप में, यह शोध पत्र एक व्यापक ढांचे को प्रस्तुत करता है जो गणितीय प्रूनिंग, एल्गोरिथम संवर्द्धन और समानांतर कंप्यूटिंग को जोड़ता है ताकि एक अत्यंत कठिन NP-hard समस्या को उस स्तर पर हल किया जा सके जो पहले अप्राप्य था।