Parallel Branch Model Predictive Control on GPUs

ملخص تقني: التحكم التنبئي بالنماذج ذو الفروع المتوازية على وحدات معالجة الرسومات (GPUs)

بيان المشكلة
يُعد التحكم التنبئي بالنماذج ذو الفروع (Branch Model-Predictive Control - BMPC) إطار تخطيط قوي للتعامل مع عدم اليقين في البيئات الديناميكية، مثل القيادة الذاتية، من خلال توليد أشجار مسارات حيث تمثل الفروع حالات مختلفة من تحقق عدم اليقين. ومع ذلك، فإن النشر الواسع لـ BMPC تعوقه الأعباء الحسابية الكبيرة المطلوبة لحل هذه المشكلات، لا سيما عند التعامل مع آفاق تخطيط طويلة وعدد كبير من السيناريوهات المتوقعة. غالبًا ما تعاني الحلول الحالية من صعوبة في استغلال البنية الشجرية المتأصلة بكفاءة أو تفشل في تحقيق التوازي الزمني، مما يحد من ملاءمتها للتطبيقات في الوقت الفعلي. علاوة على ذلك، يظل التعامل مع القيود العامة لكل مرحلة ضمن إطار تحكم أمثل ذي بنية شجرية تحديًا عند العمل على أجهزة متوازية.

المنهجية
يقترح المؤلفون حلاً لـ BMPC يعتمد على وحدة معالجة الرسومات (GPU)، يدمج صياغة "الإطلاق المتعدد" (multiple-shooting) مع طريقة "لاغرانج المعززة" (Augmented Lagrangian - AL) للتعامل مع القيود. يعتمد جوهر هذا النهج على حلّين داخليين مخصصين لـ "منظم لينتر ليني تربيعي" (LQR) مصممين لاستغلال البنية الشجرية المتفرقة:

1. حلول LQR الشجرية المتوازية:

   • SLQR (التوازي على مستوى السيناريو): يقوم هذا الحل بعملية تكرار "ريكاتي" (Riccati recursion) معدلة من الأوراق إلى الجذر. يقوم بتجميع دالات القيمة من عقد الأبناء عند كل مرحلة، مما يسمح بحل مشكلات التصغير بشكل مستقل في كل عقدة بالتوازي. يتطلب هذا النهج موارد أقل من وحدة معالجة الرسومات وهو مناسب للسيناريوهات التي تكون فيها الموارد محدودة.
   • STLQR (التوازي على مستوى السيناريو والزمن): يستفيد هذا الحل من خوارزمية "المسح المتوازي" (parallel scan) لتحقيق التوازي على مستوى السيناريو والزمن في كل من عمليات المرور الخلفي (Riccati) والأمامي (rollout). يستخدم دالات القيمة الشرطية (CVFs) وقاعدة دمج ذات بنية شجرية لحساب دالات القيمة والقوانين التآلفية في زمن تعقيد قدره $O(\log N)$. يوفر هذا الأسلوب توازيًا أعلى ولكنه يتطلب موارد أكثر من وحدة معالجة الرسومات.

2. التعامل مع القيود عبر لاغرانج المعززة:
   لمعالجة القيود العامة لكل مرحلة، يستخدم المؤلفون طريقة "لاغرانج المعززة" (AL). تستخدم الحلقة الداخلية نهج "LQR التكراري" (iLQR) حيث يتم تقريب المشكلة المقيدة كمسألة LQR شجرية غير مقيدة باستخدام دالة جزاء "باول-هيستنيس-روكافار" (PHR). تُستخدم عملية "تدحرج خطي" (linear rollout) لحساب الاضطرابات المثلى، مما يتيح التوازي الفعال على وحدات معالجة الرسومات. تقوم الحلقة الخارجية بتحديث مضاعفات لاغرانج وأوزان الجزاء تكيفيًا بناءً على انتهاكات القيود، باتباع قاعدة BCL.

3. التنفيذ:
   تم تنفيذ الحل باستخدام مكتبة JAX، مع الاستفيد من "الاشتقاق التلقائي" ومترجم XLA لتسريع المعالجة على وحدة معالجة الرسومات. يدعم الإطار الحسابات بدقة الفاصلة العائمة المفردة (FP32) والدقة المزدوجة (FP64).

المساهمات الرئيسية
تحدد الورقة ثلاث مساهمات رئيسية:

1. الحلول المزدوجة المتوازية: تطوير حلّي LQR شجريين متوازيين (SLQR و STLQR) يقدمان مستويات مختلفة من التوازي، مما يسمح للمستخدمين باختيار الطريقة المناسبة بناءً على حجم المشكلة والموارد الحسابية المتاحة.
2. حل BMPC غير الخطي المقيد: دمج حلول LQR الشجرية هذه في حل تكراري يعتمد على "الإطلاق المتعدد" لمشكلات BMPC غير الخطية، مع دمج طريقة لاغرانج المعززة للتعامل القوي مع القيود وقدرات "البدء الدافئ" (warm-starting).
3. القياس المرجعي والمصدر المفتوح: إجراء قياس مرجعي شامل لحل المقترح مقابل حلول iLQR الحالية (مثل TRAJAX و MPX) وحل عالي الأداء يعتمد على وحدة المعالجة المركزية (HPIPM)، بالإضافة إلى إصدار التنفيذ كمصدر مفتوح.

النتائج العددية
قام المؤلفون بتقييم الحل في مهمتين مختلفتين: مشكلات LQR شجرية غير مقيدة، وتخطيط المسار المقيد لنموذج "unicycle" ونموذج "quad-pendulum".

• الأداء على Tree LQR: يعتمد أداء حلول وحدة معالقة الرسومات بشكل كبير على حجم المشكلة والعتاد. في أحجام المشكلات الصغيرة (مثل $Z = 2$ مسارات شجرية)، تكون الحلول أبطأ بكثير من حل HPIPM الذي يعتمد على وحدة المعالجة المركزية؛ حيث كان STLQR أبطأ بـ 5 أضعاف وSLQR أبطأ بـ 20 ضعفًا على بطاقة NVIDIA RTX 5060 Ti بسبب زمن وصول ذاكرة وحدة معالجة الرسومات والعبء الإضافي (overhead). ومع ذلك، في الحالات واسعة النطاق، تنعكس الآية: يمكن لـ SLQR أن يتفوق على HPIPM بما يصل إلى ضعفين في الحالات الكبيرة ($Z \ge 128$) على بطاقة RTX 5060 Ti. وبالمثل، في وحدات معالجة الرسومات عالية الأداء مثل RTX 4090، يحقق STLQR تسريعًا يصل إلى 1.9 ضعفًا مقارنة بـ HPIPM لأحجام الأشجار المتوسطة إلى الكبيرة ($Z \ge 16$).
• التعامل مع القيود: في مهام تخطيط المسار، أظهر الحل المقترح (ILQRJAX) سلوك تقارب مشابه لحل IPOPT المتقدم الذي يعتمد على وحدة المعالجة المركزية، ولكن مع تقليل كبير في وقت الحساب لكل دورة (على سبيل المثال، تقليل متوسط وقت الدورة من 3.80 مللي ثانية إلى 1.87 مللي ثانية لنموذج unicycle). نجح الحل في التعامل مع جميع حالات الاختبار، بينما واجهت الحلول الأخرى القائمة على وحدة معالجة الرسومات (TRAJAX, MPX) صعوبات في الحالات الأكثر تحديًا، حيث فشلت غالبًا في التقارب بسبب قيود الصياغة أو نقص مخططات التحديث التكيفية.

الأهمية والادعاءات
تزعم الورقة أن النهج المقترح يوفر مسارًا قابلًا للتطبيق نحو BMPC في الوقت الفعلي للمشكلات واسعة النطاق من خلال الاستغلال الكامل للبنية الشجرية عبر خوارزميات متوازية على وحدات معالجة الرسومات. يؤكد المؤلفون أن طريقتهم تحقق أداءً فائقًا مقارنة بالحلول عالية الأداء التي تعتمد على وحدة المعالجة المركزية، وتحديدًا في الحالات واسعة النطاق حيث يمكن موازاة البنية الشجرية بفعالية. ومع ذلك، يقرون بأن الحل القائم على المسح (parallel scan) يتطلب موارد عالية من وحدة معالجة الرسومات، مما قد يحد من القدرة على التوسع إذا تشبعت الموارد، وأن الحلول التي تعتمد على وحدة المعالجة المركزية قد تظل تتفوق في أحجام المشكلات الصغيرة. يضع هذا العمل نفسه كخطوة نحو جعل التخطيط المدرك لعدم اليقين أمرًا ممكنًا للتطبيقات المعقدة في العالم الحقيقي من خلال الموازنة بين الكفاءة الحسابية والتعامل الصارم مع القيود وعدم اليقين. وقد تم تحديد العمل المستقبلي في تنفيذ الطريقة باستخدام CUDA C++ لمزيد من تحسين استخدام الموارد واستكشاف الحسابات ذات الدقة المختلطة لتحسين الاستقرار العددي على الأجهزة المحسنة لدقة FP32.