⚡ electrical engineering

A Luenberger Observer for P-Time Event Graphs

تقترح هذه الورقة خوارزمية مراقب "لونبرجر" لرسوم الأحداث ذات الزمن المحدود (P-Time Event Graphs)، والتي تقوم بتقدير أوقات إطلاق الانتقالات غير المرصودة من خلال دمج قيود الحد الأعلى لوقت المكوث لتحقيق نتائج أكثر دقة من مراقبي رسوم الأحداث الموقوتة التقليدية.

المؤلفون الأصليون: Dominik Tirpák, Davide Zorzenon, Jörg Raisch

نُشر 2026-08-04

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Dominik Tirpák, Davide Zorzenon, Jörg Raisch

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تراقب أرضية مصنع مزدحمة، لكنك لا ترى سوى الباب الأمامي حيث تصل المواد الخام والباب الخلفي حيث تخرج المنتجات النهائية. في الداخل، تدور رقصة معقدة من الآلات، وسيور النقل، والعمال، لكن المنتصف عبارة عن صندوق أسود. أنت تعرف القواعد: لا يمكن للقطعة (widget) أن تغادر محطة قبل أوانها (فهي تحتاج وقتاً لتبرد)، ولا يمكنها البقاء لفترة طويلة جداً (وإلا فقد تذوب أو تنتهي صلاحيتها). هذا هو عالم أنظمة الأحداث المنفصلة (Discrete Event Systems)، وهو فرع من العلوم يدرس كيفية تحرك الأشياء وتغيرها في خطوات بدلاً من التدفق مثل الماء. ولجعل هذه الأنظمة مفهومة، يستخدم العلماء أداة تسمى شبكة بيتري (Petri Net)، وهي تشبه خريطة لرموز (نقاط صغيرة) تتحرك عبر شبكة من الأماكن والانتقالات. وعندما يُضاف عنصر الزمن إلى المزيج، تصبح رسم بياني للأحداث الموقوتة (Timed Event Graph)، حيث لكل حركة جدول زمني. ولكن الحياة الواقعية صعبة؛ فأحياناً يكون للمهمة موعد نهائي. تتناول هذه الورقة البحثية الرسوم البيانية للأحداث ذات الزمن المحدود (P-Time Event Graphs)، وهي نسخة متطورة من الخريطة تتضمن حدوداً زمنية لكل خطوة، سواء كانت "أبكر وقت ممكن" أو "أخر وقت ممكن". لماذا يهم هذا؟ لأنه في صناعات مثل التصنيع أو معالجة الأغذية، قد يؤدي تفويت الموعد النهائي إلى إفساد المنتج، ومعرفة ما يحدث بالضبط داخل الصندوق الأسود دون فتحه هو الهدف الأسمى للكفاءة.

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

لفهم كيفية عمل ذلك، تخيل سباق تتابع حيث يمر العداؤون (الرموز/tokens) بعصا التتابع (المهمة) بين المحطات. في السباق البسيط، تعلم فقط أن العداء يجب أن ينتظر 5 ثرائق على الأقل قبل تمرير العصا. ولكن في نسخة هذه الورقة، هناك أيضاً قاعدة: يجب على العداء تمرير العصا في غضون 10 ثوانٍ، وإلا سيتم استبعاده (تموت الرمز/token). المراقب هو بمثابة مدرب يقف خارج المضمار، لا يمكنه رؤية سوى طلقة البداية وخط النهاية. ويمتلك المدرب نموذجاً ذهنياً للسباق. إذا كان المدرب يعرف فقط أقصر أوقات الانتظار، فقد يخمن أن العدائين يتحركون ببطء. ولكن بما أن المدرب يعرف أيضاً الموعد النهائي المتمثل في 10 ثوانٍ، فيمكنه أن يدرك: "مهلاً، إذا عبر العداء عند خط النهاية للتو في الثانية العاشرة، فلا بد أن العداء المخفي قد مرر العصا بالفعل بحلول الآن، وإلا لكان قد استُبعد". هذه القطعة الإضافية من المعلومات تجبر المدرب على تحديث تخمينه، مما يجعله أكثر دقة.

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

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

ملخص تقني: مراقب لونبرجر لرسوم الأحداث من النوع P-Time (P-TEGs)

بيان المشكلة
تتناول الورقة مشكلة تقدير الحالة لرسوم الأحداث من نوع P-Time (P-TEGs)، وهي فئة من أنظمة الأحداث المنفصلة المستخدمة لنمذجة التزامن وقيود النوافذ الزمنية في العمليات التصنيعية والصناعية. بخلاف رسوم الأحداث الموقوتة (TEGs) القياسية، تتضمن P-TEGs كلاً من قيود الحد الأدنى والحد الأعلى لأوقات المكوث (sojourn times) للرموز (tokens) في الأماكن. التحدي الجوهري يكمثل في تقدير أوقات إطلاق الانتقالات الداخلية وغير المرصودة في الوقت الفعلي (online)، نظراً لأن مجموعة فرعية فقط من الانتقالات (انتقالات المخرجات وانتقالات المدخلات المرصودة) هي التي يمكن قياسها مباشرة. يجب أن يوفر المراقب أدق تقدير ممكن (أكبر تقريب سفلي لأوقات الإطلاق الحقيقية) مع احترام القيود الهيكلية للنظام وتجنب "موت الرمز" (انتهاك قيود النافذة الزمنية).

المنهجية
يقوم المؤلفون بتوسيع إطار عمل مراقب لونبرجر الكلاسيكي، الذي تم تأسيسه سابقاً لرسوم TEGs باستخدام جبر max-plus، إلى المجال الأكثر تعقيداً لرسوم P-TEGs. تعتمد المنهجية على الركائز التقنية التالية:

تمثيل المتجه اللانهائي: للتعامل مع المتباينات الناتجة عن قيود الحد الأعلى ومختلف الشروط الأولية، تتبنى الورقة "تمثيل المتجه اللانهائي" لدوال التاريخ (التي تربط الإطلاق رقم $k$ لانتقال ما بزمن حدوثه). يعمل هذا النهج كبديل مرن لتحويل $\gamma$ ، الذي يعد أقل ملاءمة لهياكل المتباينات المحددة الموجودة في P-TEGs.
الصياغة الجبرية: يتم نمذجة ديناميكيات P-TEG باستخدام نظام من معادلات ومتباينات max-plus الفرقية الخطية. يتم تمثيل النظام في فضاء متجهي لانهائي الأبعاد، مما يحول السلوك الديناميكي إلى معادلات جبرية تتضمن المصفوفات $A$ و $B$ و $R$ و $C$ ، جنباً إلى جنب مع مصفوفات المتباينات $U$ التي تشفر قيود الحد الأعلى.
تصميم المراقب: صُمم المراقب لإيجاد أكبر تقريب سفلي لمتجه الحالة $x$ $x$ . تتضمن عملية التصميم ما يلي:
- اشتقاق "أكبر مصفوفة حالة" $M^*$ التي تلخص ديناميكيات النظام وقيود الحد الأعلى.
- صياغة معادلة المراقب $\hat{x} = x_0 \oplus M \hat{x} \oplus Bu \oplus L(y \oplus \hat{y})$ ، حيث $L$ هي مصفوفة كسب المراقب.
- حل نظام من المتباينات لتحديد مصفوفة المراقب المثلى $L_{opt}$ . يثبت المؤلفون أنه يمكن حساب $L_{opt}$ كـ $J_{opt} \otimes C^T$ ، حيث يتم اشتقاق $J_{opt}$ من نجم كليني (Kleene star) لمصفوفة النظام ومصفوفات المدخلات والمخرجات.
خوارزمية التقدير عبر الإنترنت (Online): تعمل الخوارزمية المقترحة في خطوتين. أولاً، يتم حساب الكسب الأمثل $L_{opt}$ خارج الخط (offline). ثانًا، أثناء التشغيل عبر الإنترنت، يتم تحديث تقدير الحالة $\hat{x}_t$ عند أي وقت $t$ باستخدام تاريخ الأحداث المرصودة فقط (أوقات إطلاق $u$ و $y$ حتى الوقت $t$ ). يثبت المؤلفون أنه رغم الأبعاد اللانهائية للمصفوفات، يمكن إجراء التقدير في وقت متعدد الحدود بالنسبة لعدد انتقالات النظام والأحداث المرصودة.

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

توسيع مراقبات لونبرجر: نجحت الورقة في تعميم مراقب لونبرجر من TEGs إلى P-TEGs، مما يسمح باستغلال قيود الحد الأعلى لتحسين تقدير الحالة.
التعامل مع قيود الحد الأعلى: من خلال استخدام تمثيل المتجه اللانهائي، قدم المؤلفون إطاراً جبرياً صارماً لدمج قيود النافذة الزمنية مباشرة في تصميم المراقب، مما يسمح بـ "تقديرات دقيقة" تمنع التنبؤ بمسارات مستحيلة (تؤدي إلى موت الرمز).
اشتقاق الكسب الأمثل: توفر الورقة حلاً مغلق الصيغة لمصفوفة المراقب المثلى $L_{opt}$ ، وتثبت أنها تعطي أكبر تقدير ممكن للحالة الداخلية بما يتوافق مع جميع القياسات وقيود النظام المتاحة.
الكفاءة الحسابية: يثبت العمل أن خطوة التقدير عبر الإنترنت مجدية حسابياً (وقت متعدد الحدود)، مما يجعل النهج قابلاً للتطبيق العملي.

النتائج
تتحقق الورقة من الطريقة المقترحة باستخدام مثال عددي (P-TEG بثلاثة انتقالات داخلية وقيود نافذة زمنية).

التقارب: يتقارب المراقب مع أوقات الإطلاق الفعلية للانتقالات الداخلية مع توفر المزيد من بيانات المخرجات، باستثناء وقت إطلاق واحد محدد (الإطلاق الثاني للانتقال $x_1$ ) والذي يظل مقدراً بأقل من قيمته الحقيقية بمقدار وحدة زمنية واحدة بشكل دائم.
تحسين الدقة: يظهر تحليل مقارن أن المراقب المقترح، الذي يستخدم قيود الحد الأعلى، يقدم تقديرات أكبر من أو تساوي تلك التي يحصل عليها مراقب TEG القياسي (الذي يتجاهل الحدود العليا). بالنسبة لانتقال المخرجات المقاس، يعطي كلا المراقبين تقديرات متطابقة. أما بالنسبة للانتقالات الداخلية غير المرصودة، فإن المراقب المقترح يوفر تقديرات أفضل (أكبر) بشكل صارم في معظم الحالات؛ فعلى سبيل المثال، عند خطوة زمنية محددة، قام المراقب المقترح بتصحيح التقدير من 5 إلى 6 لتجنب موت الرمز المتوقع، بينما فشل المراقب القياسي في إجراء هذا التصحيح، مما أدى إلى تقدير أقل دقة (أصغر).
الاتساق: تضمن الخوارزمية بقاء المسار المقدر متسقاً مع القيود الهيكلية لـ P-TEG، متجنبة التنبؤ بمسارات غير متسقة.

الأهمية والادعاءات
يزعم المؤلفون أن هذا العمل يوفر طريقة منهجية لتقدير الحالة في P-TEGs تستفيد من كامل القدرة النمذجة لهذه الرسوم، وتحديداً قيود الحد الأعلى الموجودة غالباً في الأنظمة الواقعية (مثل المواعيد النهائية أو نوافذ وقت المعالجة). تؤكد الورقة أنه على عكس النهج السابقة لشبكات P-time Petri التي تحسب جميع المتواليات المتسقة الممكنة (والتي قد تكون مكلفة حاسوبياً ولا تتطلب مجموعات وصول نهائية)، فإن هذا المراقب يوفر أفضل تقديرات لأوقات الحدوث مباشرة. تكمن الأهمية في القدرة على إجراء مراقبة دقيقة عبر الإنترنت لأنظمة الأحداث المنفصلة المعقدة حيث تكون قيود التوقيت حاسمة، دون الحاجة إلى مجموعة الوصول (reachability set) للشبكة الأساسية أن تكون منتهية. يُقدم العمل كإمتداد مباشر لنظرية مراقب TEG الحالية، مهيأة للتعامل مع التحديات الجبرية المحددة التي تفرضها P-TEGs.

أبحاث مشابهة