تاكافومي هوريوتشي

أطروحة بكالوريوس في البرمجة بالقيود

نظرة عامة

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

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

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


المشكلة: ازدياد الاحتمالات يطيل زمن التنفيذ

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

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

النموذج: الجمع بين التغيّر المستمر والمتقطّع

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

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

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

عنق الزجاجة: زيادة الشروط ترفع زمن التنفيذ

تُسمّى القاعدة التي لا تنشط إلا عند تحقق شرط معيّن «قيدًا مشروطًا» (guarded constraint). في نموذج التقييم، لا تنشط قاعدة الارتداد الخاصة بجزء من السطح إلا حين تصل الكرة إلى الأرض ويقع موضعها الأفقي ضمن ذلك الجزء.

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

التحليل: أين استُهلكت 96% من مدة التنفيذ؟

أظهر تحليل الأداء لنموذج ذي 100 جزء أن الإجراء FindMinTime استهلك 96% من زمن التنفيذ الكلي. ويحدّد هذا الإجراء أقرب حدث تالٍ ممكن، عبر التقييم المتكرر لجميع الشروط المرشّحة لتفعيل القيود.

حدّد ذلك فرصة واضحة للتحسين: تقليص الشروط المرشّحة التي تُمرّر إلى FindMinTime بأمان. كان الهدف تجاوز الاحتمالات التي لم تعد بحاجة إلى التقييم فقط، مع الحفاظ على نتائج المحاكاة.

النهج: استبعاد الشروط التي لن تتحقق مرة أخرى

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

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

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

عندما يبقى اتجاه التغيّر ثابتًا

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

الخط الأحمر الذي يرتفع من α عند الزمن 0 إلى β عند الزمن الأقصى يمثل متغيرًا يستمر في الزيادة طوال المحاكاة.
تعني الرتابة المنتظمة بقاء اتجاه التغيّر ثابتًا طوال الفترة التي تجري محاكاتها.

عندما ينعكس اتجاه التغيّر

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

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

النتيجة: نحو نصف زمن التنفيذ في نموذج التقييم

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

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

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

ما تعلّمته

استخدم هذا البحث خصائص معروفة لسلوك النظام لتقليص مجموعة الاحتمالات التي يجب على المحاكي النظر فيها. ويُعد تضييق فضاء البحث مع الحفاظ على النتائج من نقاط قوة البرمجة بالقيود.

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

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

Takafumi Horiuchi and Kazunori Ueda. “Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa.” Proceedings of the 33rd Annual Conference of the Japanese Society for Artificial Intelligence, 2019. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02