Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints

إليك ملخص تقني مفصل للورقة البحثية بعنوان "إعادة صياغة محدبة دقيقة وتقريبية للتحكم الأمثل الخطي العشوائي مع قيود الاحتمالية" من إعداد تانماي دوكانيا ويشوانث كومار ناكا.

1. بيان المشكلة

تتناول الورقة البحثية تخطيط الحركة العشوائي (Stochastic Motion Planning) للأنظمة الخطية ذات الزمن المنفصل المعرضة لعدم اليقين (ضوضاء العملية وتوزيع الحالة الأولية). الهدف هو إيجىاد سياسة تحكم مثلى تقلل دالة التكلفة التربيعية مع استيفاء قيود الاحتمالية (Chance Constraints - CCs) بمستوى احتمالية محدد ($1-\epsilon$).

تشمل التحديات الرئيسية في النهج الحالية ما يلي:

• عدم التحدب (Non-convexity): غالبًا ما تؤدي صياغة قيود الاحتمالية على الحالات والتحكم إلى مشكلات تحسين غير محدبة، مما يتطلب خطية (linearization) أو تسلسلاً لتصحيح التحدب (successive convexification)، وهو ما قد يكون محافظاً للغاية أو مكلفاً حاسوبياً.
• محدودية الفصل (Decoupling limitations): تفشل العديد من الطرق التي تفصل بين تحسين المتوسط والتباين في التقاط المقايضة بين المخاطرة والأداء (على سبيل المثال، الملاحة في الممرات الضيقة تتطلب قوانين تغذية راجعة أكثر إحكاماً).
• التحفظ (Conservatism): غالباً ما تكون التقريبات الموجودة لقيود الاحتمالية التربيعية (مثل استخدام متباينة ماركوف) محافظة بشكل مفرط، مما يؤدي إلى عدم الجدوى تحت مستويات الضوضاء المتوسطة.

تتضمن المشكلة المحددة (المشكلة 1) نظاماً خطياً متغيراً مع الزمن:
$$x_{k+1} = A_k x_k + B_k u_k + D_k w_k$$
خاضع لـ:

• قيود الاحتمالية الخطية (LCC): حدود احتمالية على تركيبات خطية من الحالات والتحكم عبر خطوات زمنية مفردة أو متعددة.
• قيود الاحتمالية التربيعية (QCC): حدود احتمالية على انحراف الحالة عن متوسطها (القيود الإهليلجية).
• قيود التباين النهائي (Terminal Covariance Constraints): حدود على تباين الحالة النهائية.

2. المنهجية: التمثيل المرفوع (Lifted Representation)

تتمثل المساهمة الجوهرية في طريقة التمثيل المرفوع التي تدمج معلومات اللحظة (المتوسط والتباين) صراحةً في متغيرات القرار، مما يحول المشكلة العشوائية إلى مشكلة حتمية محدبة.

أ. الأساس العشوائي وتمثيل الحالة/التحكم

بدلاً من نشر التباينات بشكل منفصل، يمثل المؤلفون المتغيرات العشوائية (الحالات $x_k$ والتحكم $u_k$) كدوال تآلفية لـ أساس عشوائي $e(k)$.

• بناء الأساس: يتم بناء الأساس $e(k)$ كمتجه من المتغيرات الغاوسية القياسية المستقلة التي تُبنى تكرارياً من ضوضاء الحالة الأولية وضوضاء العملية حتى الزمن $k$.
• المتغيرات المرفوعة:
  • الحالة: $x_k = \mu_k + \Psi_k e(k)$، حيث $\mu_k$ هو المتوسط و $\Psi_k$ يمثل هيكل التباين ($\text{var}(x_k) = \Psi_k \Psi_k^\top$).
  • التحكم: $u_k = \nu_k + V_k e(k)$، حيث $\nu_k$ هو متوسط التحكم و $V_k$ يمثل هيكل التغذية الراجعة بالنسبة لأساس الضوضاء.
• يفترض هذا الصياغة السياسات التآلفية السببية (causal affine policies)، حيث يعتمد التحكم عند الزمن $k$ خطياً على سجل تحققات الضوضاء حتى $k$.

ب. إعادة صياغة القيود

باستخدام المتغيرات المرفوعة ($\mu, \nu, \psi, v$)، يستنتج المؤلفون إعادة صياغة محدبة دقيقة أو محافظة:

1. قيود الاحتمالية الخطية (إعادة صياغة دقيقة):

   • بالنسبة للقيد الخطي $P(a^\top x + \alpha^\top u \le b) \ge 1-\epsilon$، فإن المتغير العشوائي هو تركيبة خطية من التوزيعات الغاوسية، وبالتالي فهو غاوسي.
   • تتم إعادة صياغة القيد بدقة كقيد مخروط من الدرجة الثانية (SOC):
     $$\text{Mean} + \Phi^{-1}_N(1-\epsilon) \cdot \|\text{StdDev}\|_2 \le b$$
   • وهذا ينطبق دون تحفظ لـ $0 \le \epsilon < 0.5$.

2. قيد التباين النهائي (إعادة صياغة دقيقة):

   • يتم إعادة صياغة القيد $\text{var}(x_N) \preceq \Sigma_f$ باستخدام متممة شير (Schur complement) كـ متباينة مصفوفة خطية (LMI) تتضمن $\Psi_N$.

3. قيود الاحتمالية التربيعية (إعادة صياغة تقريبية):

   • تقترح الورقة نوعين من التقريبات المحافظة لـ $P((x-\mu)^\top Q^{-1}_{CC} (x-\mu) \le 1) \ge 1-\epsilon$:
     • تقريب LMI: يستخدم خصائص احتواء المجموعات للإهليلجات لاستنتاج قيد LMI. يكون هذا التقريب أكثر إحكاماً عندما تكون القيم الذاتية لمصفوفة التباين متشابهة.
     • التقريب التربيعي: يستخدم حداً على أثر (trace) مصفوفة التباين المستمد من متباينات التركيز. يكون هذا التقريب أكثر إحكاماً عندما تكون القيم الذاتية متباعدة للغاية (تباين خواص الضوضاء).
   • كلا التقريبين أقل تحفظاً بشكل مثبت من الطرق الموجودة (مثل متباينة ماركوف).

ج. مشكلة التحسين الناتجة

تتحول المشكلة العشوائية الأصلية إلى المشكلة 2، وهي مشكلة تحسين محدبة حتمية بمتغيرات القرار $\{\mu_k, \nu_k, \psi_k, v_k\}$.

• الدالة الهدف: دالة تكلفة تربيعية تتضمن حدوداً لكل من مسار المتوسط و"الانتشار" (التباين) للمسار.
• القيود: ديناميكيات تآلفية (في الفضاء المرفوع)، قيود SOC (لـ LCCs)، وLMIs/قيود تربيعية (لـ QCCs).

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

1. إعادة صياغة محدبة دقيقة: تم إثبات أن قيود الاحتمالية الخطية على الحالات والتحكم (بما في ذلك القيود متعددة الخطوات والمختلطة) يمكن تمثيلها بدقة كقيود SOC تحت الافتراضات الغاوسية، مما يلغي الحاجة إلى الخطية أو تصحيح التدرج المتتالي.
2. تحسين التقريبات التربيعية: اشتق تقريبات محدبة جديدة للقيود الاحتمالية التربيعية (LMI والاشكال التربيعية) والتي ثبت أنها أقل تحفظاً من طرق مثل متباينة ماركوف.
3. إطار عمل موحد: وفر إطار عمل موحداً يتعامل مع تحسين المتوسط، وتشكيل التباين، وقيود الاحتمالية في آن واحد، متجنباً فصل المخاطرة عن الأداء.
4. الضمانات النظرية: أثبتت الورقة أن مجموعة الحلول الممكنة للمشكلة المرفوعة تعادل مجموعة السياسات التآلفية السببية الممكنة في المشكلة العشوائية الأصلية.

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

قام المؤلفون بالتحقق من صحة إطار العمل باستخدام توليد مسار الحد الأدنى من الـ (snap) لطائرة بدون طيار (quadrotor) في مستوى ثنائي الأبعاد تحت تأثير اضطرابات عشوائية. قارنوا طريقتهم بنموذجين مرجعيين:

• [7]: طريقة تستخدم معاملات التغذية الراجعة (معادلة ريكاتي) والقيود الخطية الدقيقة.
• [11]: طريقة تستخدم تقدير التباين التكراري والقيود الخطية التقريبية.

النتائج الرئيسية:

• الجدوى: ظلت الطريقة المقترحة قابلة للتنفيذ عند مستويات ضوضاء أعلى برتبة مقدار (order of magnitude) من النماذج المرجعية.
  • ساحة الدائرة (Circle Arena): كانت قابلة للتنفيذ حتى $\sigma = 0.85$، بينما فشلت النماذج المرجعية عند $\sigma \approx 0.06$.
  • ممر القمع (Funnel Corridor): كانت قابلة للتنفيذ حتى $\sigma = 0.60$، بينما فشلت النماذج المرجعية عند $\sigma \approx 0.06$.
• الأمثلية (تقليل التكلفة):
  • في ساحة الدائرة، حققت الطريقة المقترحة تقليلاً في التكلفة يصل إلى 35% مقارنة بـ [7].
  • في ممر القمع، حققت تقليلاً في التكلفة يصل إلى 43% تحت الضوضاء المتوسطة.
• القيود التربيعية: أدى تقريب LMI (22) إلى أفضل أداء للضوضاء متماثلة الخواص (isotropic)، بينما كان التقريب التربيعي (24) متفوقاً للضوضاء عالية تباين الخواص (anisotropic). كلاهما تفوق بشكل كبير على حد ماركوف.

5. الأهمية

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