Performance Comparison of Classical and Neural Sampling Algorithms for Robotic Navigation

ملخص تقني: مقارنة الأداء بين خوارزميات أخذ العينات الكلاسيكية والعصبية للملاحة الروبوتية

بيان المشكلة
تُعد التخطيط القائم على أخذ العينات (Sampling-based motion planning) أمراً جوهرياً للأنظمة ذاتية القيادة، بما في ذلك الروبوتات الأرضية، والطائرات بدون طيار (UAVs)، والمركبات ذاتية القيادة. وبينما تُستخدم خوارزمية الشجرة عشوائية الاستكشاف السريعة (RRT) ومتغيرها الأمثل (RRT*) على نطاق واسع لكفاءتها في المساحات عالية الأبعاد، إلا أنها تعاني من عدم كفاءة أخذ العينات العشوائي. يؤدي هذا إلى تكاليف حوسبة عالية، وبطء في التقارب، ومسارات غير مثالية ومتعرجة، لا سيما في البيئات المزدحمة ذات كثافة العوائق المتغيرة. وعلى الرغم من أن متغيرات مثل (Informed RRT*) تستخدم استدلالات مصممة يدوياً (مثل أخذ العينات الإهليلجي) لتسريع التقارب، إلا أنها تفتقر إلى القدرة على التكيف مع هياكل البيئات المتنوعة. وتشير التطورات الأخيرة في تعلم الآلة إلى أن الشبكات العصبية يمكن أن توجه عملية أخذ العينات نحو المناطق الواعدة، ومع ذلك، لا يزال هناك نقص في التقييم الموحد والمحكوم الذي يقارن بين هذه النهج الموجهة عصبياً والأسس الكلاسيكية تحت ظروف متسقة.

المنهجية
تقوم هذه الدراسة بتنفيذ ومقارنة ثلاث خوارزميات ضمن إطار عمل موحد عبر بيئات ذات توزيع عوائق (متفرقة، متوسطة، وكثيفة):

1. RRT:* وهو الخط المرجعي الكلاسيكي الذي يستخدم أخذ العينات العشوائي المنتظم والتحسين الأمثل عبر إعادة ربط العقد (node rewiring).
2. Neural RRT:* وهو تحسين حيث يتم توجيه خطوة أخذ العينات بواسطة خريطة احتمالية $P(x, y)$ يتنبأ بها نموذج عصبي مدرب. يكون أخذ العينات عبارة عن مزيج مرجح من التوزيع المتعلم وأخذ العينات المنتظم ($x_{rand} \sim \alpha P(x, y) + (1-\alpha)U(X_{free})$).
3. Neural Informed RRT:* وهو نهج هجين يجمع بين توزيع أخذ العينات المتعلم والقيود الهندسية لـ (Informed RRT*). بعد إيجاد مسار أولي قابل للتنفيذ بتكلفة $c_{best}$، يتم تقييد أخذ العينات في تقاطع خريطة الاحتمالية المتعلمة مع المنطقة الإهليلجية المحددة بواسطة نقطة البداية، والهدف، و $c_{best}$.

بنية الشبكة العصبية والتدريب
يستخدم كلا المخططين العصبيين نموذجاً يعتمد على بنية (U-Net) مع مشفر وفك تشفير من نوع (ResNet-50). المدخل هو صورة ثلاثية القنوات بحجم 224×224 تمثل خريطة العوائق، وموقع البداية، وموقع الهدف. وتنتج الشبكة خريطة احتمالية كثيفة لتوجيه عملية أخذ العينات. تم تدريب النموذج بطريقة تحت الإشراف باستخدام مجموعة بيانات تم إنشاؤها بواسطة خوارزمية (A*) على خرائط شبكية عشوائية. كما تم استخدام تقنيات تعزيز البيانات (Data augmentation)، بما في ذلك تغييرات العوائق العشوائية وإعادة تموضع البداية والهدف، لضمان القدرة على التعميم.

المساهمات الرئيسية

• مقارنة موحدة: تقدم الورقة تقييماً محكوماً جنباً إلى جنب لكل من (RRT*) الكلاسيكي، و(Neural RRT*)، و(Neural Informed RRT*) عبر خرائط ذات تعقيدات متفاوتة، مما يعالج نقص المعايير المتسقة في الأدبيات الموجودة.
• التقييم الكمي: يتم تقييم الأداء بصرامة باستخدام أربعة مقاييس: طول المسار، وقت التخطيط، سلاسة المسار، ومعدل النجاح.
• تحليل المقايضة: تدرس الدراسة صراحةً المقايضات بين العبء الحوسبي للاستدلال العصبي والمكاسب في جودة المسار وكفاءة التقارب.

النتائج
أسفرت التجارب التي أجريت على 50 دورة لكل نوع من الخرائط (متفرقة، متوسطة، كثيفة) عن النتائج التالية:

• جودة المسار: حققت خوارزمية (Neural Informed RRT*) باستمرار أقصر أطوال مسارات وأكثر المسارات سلاسة. وفي البيئات الكثيفة، أظهرت انخفاضاً يصل إلى 14% في طول المسار وتحسناً بنسبة 55-75% في السلاسة مقارنة بـ (RRT*) الكلاسيكي. كما حسنت (Neural RRT*) جودة المسار مقارنة بالخط المرجعي، ولكن بدرجة أقل.
• وقت التخطيط: أظهرت خوارزمية (RRT*) الكلاسيكية عموماً أسرع أوقات التخطيط، لا سيالما في الخرائط المتفرقة. وقد واجهت المخططات الموجهة عصبياً زيادة طفيفة في وقت الحوسبة بسبب الاستدلال العصبي. ومع ذلك، تشير الدراسة إلى أن تكلفة الوقت هذه تتلاشى أمام التحسينات الكبيرة في مثالية المسار وسلاسته في البيئات المعقدة.
• معدل النجاح: حافظت جميع الخوارزميات على معدل نجاح بنسبة 100% في الخرائط ذات الكثافة المتفرقة والمتوسطة. وفي الخرائط الكثيفة، انخفضت نسبة نجاح (Neural Informed RRT*) أحياناً إلى 90% (ويعزى ذلك إلى التقليص الشديد لمساحة البحث)، لكنها لا تزال تتفوق على غيرها في مقاييس الكفاءة.

الأهمية والادعاءات
تدعي الورقة أن دمج التوجيه القائم على الذكاء الاصطناعي في المخططات القائمة على أخذ العينات يعزز بشكل كبير من موثوقية وكفاءة المسار للملاحة الروبوتية. وتظهر النتائج أن (Neural Informed RRT*) تقدم أفضل توازن بين جودة المسار ووقت الحوسبة، مما يجعلها الخيار الأكثر ملاءمة للملاحة في البيئات المعقدة والمزدحمة. وبينما يفرض هذا النهج عبئاً حوسبياً طفيفاً، تخلص الدراسة إلى أن التحسينات الناتلة في مثالية المسار وسلاسته تبرر هذه التكلفة للتطبيقات في الوقت الفعلي. ويضع المؤلفون هذا العمل كخطوة نحو تطوير التخطيط للمسارات الروبوتية في الوقت الفعلي من خلال التكامل الفعال بين الاستدلالات المتعلمة وضمانات المثالية الكلاسيكية. ويُقترح كعمل مستقبلي توسيع هذه الأساليب لتشمل البيئات الديناميكية ثلاثية الأبعاد والتطبيقات الروبوتية في العالم الحقيقي.