Stanford تنشر محاضرة بافوني عن تخطيط الحركة: RRT وPRM وFMT*

نشرت Stanford Online على YouTube المحاضرة السابعة من مقرر AA274A Principles of Robotic Autonomy بعنوان «Motion Planning II: Sampling-Based Methods». سُجّلت المحاضرة في خريف 2019. يلقيها ماركو بافوني، الأستاذ المساعد في قسم الملاحة الجوية والفضائية في Stanford والمدير الأول (Senior Director) لأبحاث المركبات ذاتية القيادة في NVIDIA. وقبل انتقاله إلى الجامعة عمل في مختبر الدفع النفاث (Jet Propulsion Laboratory) التابع لـNASA. هذه المحاضرة ليست إصدار منتج بل مادة تعليمية، لكن موضوعها يحدد مباشرة كيف ترسم الروبوتات والمركبات ذاتية القيادة مساراتها. وتشير Stanford نفسها إلى أن بنية المقرر وواجباته ومواده تغيّرت منذ 2019، وأن الروابط في الوصف تقود إلى النسخة الحالية.

لماذا يحتاج المخطِّط إلى نقاط عشوائية

يتطلب البحث الكلاسيكي في الرسوم البيانية (Dijkstra وA*) تقسيم فضاء الإعدادات إلى وحدات منفصلة. وهذا مقبول للروبوت المستوي. أما بالنسبة إلى ذراع روبوتية بسبعة مفاصل وشبكة من 100 قيمة لكل محور، فيبلغ العدد 100 مرفوعًا إلى القوة السابعة، أي نحو 10^14 خلية. ولا يمكن تخزين شبكة بهذا الحجم ولا اجتيازها.

تتجاوز طرق أخذ العينات هذه المشكلة بأسلوب مختلف. يرمي المخطِّط إعدادات عشوائية، ويستبعد ما يسبب منها تصادمًا، ثم يصل الإعدادات المتبقية بقطع قصيرة مسموح بها. ولا حاجة إلى خريطة صريحة للعوائق في فضاء الإعدادات، فيكفي وجود دالة تجيب عما إذا كانت نقطة أو قطعة معينة خالية.

ما الخوارزميات التي تدخل في هذا المحور

يرد موضوع المحاضرة في الوصف بعنوان عام، لكن المجموعة المعتادة في التخطيط القائم على أخذ العينات هي التالية:

• PRM (Kavraki, Švestka, Latombe, Overmars, 1996): يبني رسمًا بيانيًا من نقاط عشوائية مرة واحدة، ويجيب عن عدد كبير من الاستعلامات. ويناسب البيئة الثابتة.
• RRT (LaValle, 1998): ينمّي شجرة من نقطة البداية باتجاه نقاط عشوائية. يجد مسارًا بسرعة في الفضاءات متعددة الأبعاد، وهو أنسب من PRM للاستعلام الواحد.
• RRT* (Karaman, Frazzoli, 2011): يضيف إعادة بناء الشجرة ويحقق الأمثلية التقاربية. تتقارب كلفة المسار نحو القيمة المثلى مع زيادة عدد العينات.
• FMT* (Janson, Schmerling, Clark, Pavone, 2015): من تطوير مجموعة بافوني. يجتاز العينات بترتيب يقارب طريقة الزحف السريع (fast marching)، وغالبًا ما يصل إلى مسار جيد بعدد أقل من فحوص التصادم.
• نصف قطر الاتصال في PRM*: يتناسب مع (log n / n)^(1/d)، حيث تمثّل d بُعد الفضاء. ويستند إلى هذا التقدير إثبات الأمثلية.

المفهوم النظري الأهم هنا هو الاكتمال الاحتمالي. فإذا كان المسار موجودًا، فإن احتمال العثور عليه يتجه إلى الواحد مع زيادة عدد النقاط. ولا توجد ضمانات بشأن الزمن، وهذا تحفظ مهم.

لماذا لم تفقد محاضرات 2019 قيمتها

لم تختفِ مخططات أخذ العينات. ففي مكتبة OMPL، التي يستخدمها MoveIt للتخطيط افتراضيًا، توجد تطبيقات لـPRM وRRT وRRT* وFMT. وتُبنى الاتجاهات الحديثة فوق هذا الأساس: توزيعات قابلة للتعلم لاختيار النقاط، وفحص التصادم المتوازي على GPU كما في cuRobo من NVIDIA، وأساليب هجينة مع تحسين المسارات. ونقطة الاختناق عند الجميع واحدة: فحص التصادم يستهلك عادةً الجزء الأكبر من زمن التخطيط.

يتوفر للمقرر كتاب مجاني Principles of Robot Autonomy على porabook.com ومنهج مفتوح على stanfordasl.github.io/PoRA-I. وللتعلم الذاتي، من النادر أن تجتمع المحاضرات والنص والواجبات في مكان واحد.

كيف تستخدم المادة عمليًا

ابدأ بالكتاب، ثم شاهد المحاضرة. نفّذ RRT على المستوى في نحو مئة سطر من الشيفرة، واحسب عدد استدعاءات فحص التصادم اللازمة لمسار واحد. بعد ذلك اربط OMPL وقارن بين RRT وRRT وFMT في مشهد واحد فيه ممر ضيق. هناك يظهر أبرز ضعف في هذه الطرق: احتمال الوقوع في الممر الضيق صغير، ويرتفع زمن البحث بشكل حاد.

ويجب أيضًا مراعاة قيدين. فمسارات RRT تأتي متعرجة، وتحتاج في الغالب إلى تنعيم. أما بالنسبة إلى المركبات ذات الديناميكا، مثل السيارات، فلا تكفي الهندسة وحدها: تلزم نسخ كينوديناميكية (kinodynamic) وتنسيق مع المتحكم. تقدم محاضرة 2019 الأساس، أما التفاصيل فينبغي استكمالها من النسخة الحديثة للمقرر.