ملخص تقني: تخطيط حركة متعدد الوكلاء مُحسَّن وممكن حركياً

صياغة المشكلة

تتناول الورقة البحثية مشكلة تخطيط الحركة متعددة الوكلاء (MAMP) للأنظمة ذاتية القيادة ذات الكينماتيكا المعقدة، مع التركيز بشكل خاص على أنظمة الجرار والمقطورة (tractor-trailer). وخلافاً لتخطيط المسارات متعدد الوكلاء (MAPF) القياسي الذي غالباً ما يفترض وكلاءً نقطيين في شبكات منفصلة مع ديناميكيات مبسطة، تعتبر هذه الدراسة الوكلاء أنظمة ديناميكية غير خطية توصف بـ $\dot{x}_i(t) = f_i(x_i(t), u_i(t))$. والهدف هو إيجاد مجموعة من المسارات الممكنة، والخالية من الاصطدامات، والمُحسَّنة لـ $k$ من الوكلاء الذين ينتقلون من حالات ابتدائية $x_{i,0}$ إلى حالات نهائية $x_{i,f}$ ضمن مساحة عمل $W$ تحتوي على عوائق $O$.

تسعى عملية التحسين إلى تقليل مجموع دوال التكلفة الفردية $J_i = \int_{t_0}^{t_f} l(x_i(t), u_i(t)) dt$، مع مراعاة القيود التالية:

1. قيود ديناميكيات النظام.
2. قيود الحالة (تجنب العوائق وحدود مساحة العمل).
3. قيود التحكم.
4. تجنب الاصطدام بين الوكلاء ($R_i(x_i) \cap R_j(x_j) = \emptyset$).

ويشير المؤلفون إلى أن إيجاد حل أمثل عالمياً هو مسألة معقدة من فئة NP-complete بسبب الطبيعة التوافقية لاختيار المسارات وغير خطية النظام، والتي تتفاقم بسبب صراعات الأولويات بين الوكلاء.

المنهجية

الإطار المقترح هو نهج مكون من خطوتين مصمم للموازنة بين القدرة الحسابية وجودة الحل والإمكانية الحركية (kinematic feasibility).

الخطوة 1: الحل الممكن الأولي

تولد الخطوة الأولى حلاً أولياً ممكناً وخالياً من الاصطدامات باستخدام طرق البحث المنفصلة.

• البحث متعدد الوكلاء: يستخدم الإطار إما البحث القائم على الصراع (CBS) أو البحث القائم على الأولويات (PBS). تقوم هذه الطرق بتفكيك مشكلة MAMP إلى مشكلات تخطيط أحادية الوكيل، حيث يتم حل الصراعات عن طريق إضافة قيود (في حالة CBS) أو استكشاف ترتيب الأولويات (في حالة PBS).
• المخطط أحادي الوكيل: يقيم المؤلفون نوعين من المخططات أحادية الوكيل:
  1. SIPP-IP الموسع (تخطيط المسار عبر الفترات الآمنة مع إسقاط الفترة): تم تعديله للتعامل مع دوال التكلفة العامة والوكلاء الأكبر حجماً (خلايا شبكية متعددة). وهو يستخدم الفترات الزمنية لتمثيل الحالات الآمنة.
  2. المخطط القائم على الشبكة (Lattice-Based Planner): يستخدم بحث الرسم البياني (A*) على مساحة حالة منفصلة معززة بالزمن.
• النماذج الحركية الأولية (Motion Primitives): مكون حاسم هو توليد نماذج حركية أولية متزامنة زمنياً. يقترح المؤلفون طريقة لتوليد نماذج أولية مثالية وممكنة حركياً حيث تكون مدة كل نموذج من مضاعفات زمن عينة ثابت $t_s$. هذا التزامن مطلوب للتحقق الفعال من الاصطدام في مخططات SIPP-IP والمخططات القائمة على الشبكة.

الخطوة 2: التحسين المستمر

تقوم الخطوة الثانية بتحسين الحل المنفصل باستخدام التحكم الأمثل العددي.

• مسألة التحكم الأمثل متعددة المراحل (Multi-Phase OCP): يُستخدم الحل المنفصل الأولي كـ "بداية دافئة" (warm-start) لمحلل عددي لمسألة التحكم الأمثل متعددة المراحل.
• هيكل المراحل: للتعامل مع الوكلاء الذين لديهم أوقات وصول مختلفة ($t_{i,f}$)، يتم تقسيم المشكلة إلى $M=k$ من المراحل. تغطي المرحلة $m$ الفترة الزمنية بين تحقيق الهدف للوكيل $m-1$ والوكيل $m$. يسمح هذا الهيكل بتجزئة زمنية متسقة داخل كل مرحلة للتحقق من الاصطدام مع السماح بمدد إجمالية مختلفة للوكلاء المختلفين.
• التحسين: يقوم الحل بتحسين المسارات المستمرة ومدخلات التحكم، مما يزيل آثار التجزئة ويضمن الإمكانية الحركية الصارمة.

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

1. إطار عمل MAMP ثنائي الخطوات: نهج هجين يجمع بين البحث المنفصل (CBS/PBS) لتحقيق الجدوى العالمية، والتحكم الأمثل المستمر (OCP) للتحسين المحلي والتنعيم الحركي.
2. توليد النماذج الأولية المتزامنة زمنياً: خوارزمية مبتكرة (الخوارزمية 1) لتوليد نماذج حركية أولية مثالية بمدد مقيدة لتكون مضاعفات صحيحة لزمن عينة مشترك، مما يسهل التحقق المتزامن من الاصطدام.
3. توسيعات لـ SIPP-IP: تعديلات على خوارزمية SIPP-IP لدعم دوال التكلفة العامة والوكلاء ذوي الهندسات المعقدة (الذين يشغلون خلايا شبكية متعددة)، بدلاً من مجرد نقاط مفردة.
4. صياغة Multi-Phase OCP: صياغة محددة لخطوة تحسين MAMP تتعامل مع أوقات وصول الوكلاء غير المتجانسة عن طريق تقسيم المشكلة إلى مراحل زمنية متتالية.

النتائج التجريبية

تم تقييم إطار العمل على أنظمة الجرار والمقطورة (تكوينات بـ 2 مقطورة) في بيئات خالية من العوائق وبيئات غنية بالعوائق.

• أداء الوكيل الواحد:
  • في البيئات الخالية من العوائق، كان المخطط القائم على الشبكة أسرع بكثير (0.008 ثانية مقابل 0.12 ثانية) وأنتج تكاليف أقل قليلاً من SIPP-IP الموسع.
  • في البيئات التي تحتوي على عوائق، ظل المخطط القائم على الشبكة أسرع وأنتج حلولاً بتكلفة أقل بنسبة 14% تقريباً. ويعزو المؤلفون ارتفاع تكلفة SIPP-IP وانخفاض معدل نجاحه إلى التحقق "المتحفظ" من الاصطدام (القائم على الخلايا الشبكية)، والذي يستبعد المسارات الممكنة التي يقبلها المخطط القائم على الشبكة (باستخدام فحص الدائرة إلى الدائرة).
• أداء الوكلاء المتعددين (CBS مقابل PBS):
  • معدل النجاح: في البيئات الخالية من العوائق، حل PBS عدداً أكبر من المشكلات من CBS. ومع ذلك، في البيئات التي تحتوي على عوائق، حقق CBS معدل نجاح أعلى ووقت تشغيل متوسط أقل.
  • جودة الحل: أنتج كلا المخططين حلولاً بجودة مماثلة بعد خطوة التحسين. وبينما وجد CBS في البداية حلولاً بتكاليف أقل قليلاً (بسبب ضماناته للأمثلية)، فإن خطوة التحسين المستمر غالباً ما ساوت أو قلبت هذا التفوق لصالح المخطط الآخر.
  • القابلية للتوسع: مع زيادة عدد الوكلاء، انخفض عدد المشكلات التي تم حلها بنجاح لكليهما، لكن CBS حافظ على تفوق في الأداء في السيناريوهات المعقدة المليئة بالعوائق.

الأهمية والادعاءات

تدعي الورقة أنه بالنسبة للأنظمة الحركية المعقدة مثل الجرار والمقطورة، فإن المخطط القائم على الشبكة مع CBS أو PBS يتفوق على نهج SIPP-IP الأكثر قوة من الناحية النظرية، ويرجع ذلك أساساً إلى التحقق الأقل تحفظاً من الاصطدام. ينجح إطار العمل المقترح المكون من خطوتين في سد الفجوة بين إيجاد حل ممكن في وقت معقول وتحقيق مسار مُحسَّن وممكن حركياً.

يشير المؤلفون بتواضع إلى أنه بينما يمكن لـ PBS حل المزيد من المشكلات في المساحات المفتوحة، فإن CBS يتفوق في البيئات المزدحمة. ويخلصون إلى أن جودة الحل المنفصل الأولي لا تملي بدقة التكلفة النهائية المُحسَّنة، حيث يمكن لخطوة التحسين المستمر أن تغير النتيجة بشكل كبير. ويُقترح أن يركز العمل المستقبلي على تحسين الكفاءة الحسابية لخطوة التحسين عبر التحسين الموزع ودمج قواعد المرور.