लेज़ी थीटा*: 3D में किसी भी कोण का पथ योजना और पथ लंबाई विश्लेषण

रोबोटिक्स और वीडियो गेम्स में निरंतर 2D और 3D पर्यावरणों को दर्शाने के लिए अवरुद्ध और अवरुद्ध सेल वाले ग्रिड्स का उपयोग अक्सर किया जाता है। 8-पड़ोसी 2D ग्रिड्स के किनारों द्वारा बनाए गए सबसे छोटे पथ निरंतर पर्यावरण में सबसे छोटे पथों की तुलना में 8% तक लंबे हो सकते हैं। थीटा* आमतौर पर ग्राफ के किनारों के साथ जानकारी को प्रसारित करके इससे कहीं छोटे पथ खोजता है (छोटी कार्यकाल प्राप्त करने के लिए) बिना यह बाधित किए कि पथ ग्राफ के किनारों द्वारा बनाए जाएं ("किसी भी कोण" के छोटे पथ खोजने के लिए)। हम इस पेपर में दिखाते हैं कि 26-पड़ोसी 3D ग्रिड्स के किनारों द्वारा बनाए गए सबसे छोटे पथ निरंतर पर्यावरण में सबसे छोटे पथों की तुलना में 13% लंबे हो सकते हैं, जो 3D में स्मार्ट पथ योजना एल्गोरिदम की आवश्यकता को उजागर करता है। थीटा* को 3D ग्रिड्स पर सीधे तरीके से लागू किया जा सकता है, लेकिन यह प्रत्येक विस्तारित вершिन के प्रत्येक अविकसित दृश्यमान पड़ोसी के लिए एक दृष्टि की जांच करता है और इस प्रकार 26-पड़ोसी 3D ग्रिड पर प्रत्येक विस्तारित вершिन के लिए 8-पड़ोसी 2D ग्रिड की तुलना में बहुत अधिक दृष्टि की जांचें करता है। इसलिए, हम लेज़ी थीटा* पेश करते हैं, जो थीटा* का एक रूपांतर है जो केवल एक विस्तारित вершिन के लिए एक दृष्टि की जांच करने के लिए आलस्य मूल्यांकन का उपयोग करता है (लेकिन थोड़ा अधिक विस्तारित вершिन के साथ)। हम प्रायोगिक रूप से दिखाते हैं कि लेज़ी थीटा* 26-पड़ोसी 3D ग्रिड पर थीटा* की तुलना में तेजी से पथ ढूंढता है, एक ऑर्डर के एक आकार कम दृष्टि की जांचों के साथ और पथ की लंबाई में वृद्धि के बिना।