لغة وصف الإجراءات

في مجال الذكاء الاصطناعي ، تُعد لغة وصف الإجراءات ( ADL ) نظامًا آليًا للتخطيط والجدولة، خاصةً للروبوتات. وهي تُعتبر تطورًا للغة STRIPS . اقترح إدوين بيدنولت (المتخصص في مجال تجريد البيانات ونمذجتها، والذي كان عضوًا في فريق أبحاث تجريد البيانات في شركة IBM منذ عام 1996 ^{[ 1 ]} ) هذه اللغة في عام 1987. وهي مثال على لغة الإجراءات .

لاحظ بيدنولت أن القدرة التعبيرية لـ STRIPS قابلة للتحسين من خلال السماح بأن تكون تأثيرات المُعامل مشروطة. هذه هي الفكرة الرئيسية لـ ADL-A، وهي تقريبًا الجزء الافتراضي من ADL الذي اقترحه بيدنولت، ^{[ 2 ]} مع ADL-B كامتداد لـ ADL-A. في الامتداد B، يمكن وصف الأفعال بتأثيرات غير مباشرة من خلال إدخال نوع جديد من القضايا: "القوانين الثابتة". هناك نوع ثالث من ADL وهو ADL-C، وهو مشابه لـ B، بمعنى أنه يمكن تصنيف قضاياه إلى قوانين ثابتة وديناميكية، ولكن مع بعض الخصائص الإضافية. ^{[ 3 ]}

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

على عكس STRIPS، ينطبق مبدأ العالم المفتوح على ADL: فكل ما لا يقع ضمن الشروط يُعتبر مجهولاً (بدلاً من افتراض خطئه). إضافةً إلى ذلك، بينما لا تسمح STRIPS إلا بالعبارات الموجبة والروابط ، تسمح ADL بالعبارات السالبة والفصل أيضاً .

يتكون مخطط ADL من اسم إجراء، وقائمة معلمات اختيارية، وأربع مجموعات اختيارية من البنود تحمل أسماء Precond و Add و Delete و Update.

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

يتم تحديد شروط الإضافة والحذف بواسطة مجموعتي الإضافة والحذف، على التوالي. تتكون كل مجموعة من مجموعة من البنود بالصيغ الموضحة في العمود الأيسر من الشكل 1:

1. يمثل الحرف R رمز العلاقة
2. تمثل τ ₁ ، ...، τ _{n الحدود}
3. ψ تمثل صيغة
4. التسلسل z ₁ ، ... ، z _k عبارة عن رموز متغيرة تظهر في المصطلحات τ ₁ ، ... ، τ _n ، ولكن ليس في قائمة معلمات مخطط الفعل
5. x1 _، ...، xn هي رموز متغيرة تختلف عن المتغيرات z1 _، ...، zn ولا تظهر في τ1 _، ...، τn _{، أو} ψ ، أو قائمة معلمات مخطط الفعل _.

تُستخدم مجموعات التحديث لتحديد شروط التحديث لتغيير قيم رموز الدوال. تتكون مجموعة التحديث من مجموعة من البنود بالصيغ الموضحة في العمود الأيسر من الشكل 2:

يتم تعريف الدلالة الرسمية لـ ADL من خلال أربعة قيود.

⇒ قد لا تغير الإجراءات مجموعة الأشياء الموجودة في العالم؛ وهذا يعني أنه بالنسبة لكل إجراء α وكل زوج من الحالة الحالية/الحالة التالية ( s ، t ) ∈ a ، يجب أن يكون مجال t مساويًا لمجال s .

⇒ يجب أن تكون الإجراءات في أنشطة الحياة اليومية حتمية. إذا كان ₍ s , t1 ) و ( s , t2 ) _{أزواجًا من} الحالة الحالية/الحالة التالية للإجراء ∃ ، فيجب أن يكون t1 = t2 _.

⇒ يجب أن تكون الدوال المذكورة أعلاه قابلة للتمثيل بصيغ من الدرجة الأولى. لكل رمز علاقة من الرتبة n ، R ، يجب أن توجد صيغة Φ ^a _R ( x ₁ , ... , x _n ) بمتغيرات حرة x ₂ , ..., x _n بحيث تُعطى f ^a _R ( s ) بالصيغة التالية:

${\displaystyle t(R)=f_{R}^{a}(s)=(d_{1},\ldots ,d_{n})\in \operatorname {Dom} (s)^{n}\mid s[d_{1}/x_{1},\ldots ,d_{n}/x_{n}\models \Phi _{R}^{a}(x_{1},\ldots ,x_{n})]}$

وبالتالي، ستكون F(n1, ..., xn) = y صحيحة بعد تنفيذ الإجراء |= إذا وفقط إذا كانت ΦaR ( _x1 , ... , xn, y) صحيحة مسبقًا _. ^لاحظ أن شرط التمثيل _{هذا يعتمد على} القيد الأول (يجب أن يكون مجال f مساويًا لمجال s ) .

⇒ يجب أن تكون مجموعة الحالات التي يمكن فيها تنفيذ إجراء ما قابلة للتمثيل بصيغة رياضية. لكل إجراء α يمكن تمثيله بلغة ADL، يجب أن توجد صيغة رياضية Πa بحيث يكون s ≤ Πa _إذا وفقط إذا كانت هناك حالة t بحيث يكون ( s , t ) ∈ α (أي أن الإجراء α قابل للتنفيذ في الحالة s ) ^.

من حيث الكفاءة الحسابية، يمكن تصنيف ADL بين STRIPS وحساب المواقف . ^{[ 4 ]} يمكن ترجمة أي مسألة ADL إلى مسألة STRIPS، إلا أن تقنيات الترجمة الحالية تعتمد على أسي في أسوأ الحالات. ^{[ 5 ]} لا يمكن تحسين أسوأ الحالات إذا أردنا الحفاظ على طول الخطط بشكل متعدد الحدود، ^{[ 6 ]} وبالتالي فإن ADL أقصر من STRIPS.

لا تزال مسألة تخطيط أنشطة الحياة اليومية مسألةً كاملةً من حيث المساحة متعددة الحدود. معظم الخوارزميات تعمل في فضاء متعدد الحدود حتى لو كانت الشروط المسبقة والنتائج عبارة عن صيغ معقدة. ^{[ 7 ]}

تستخدم معظم أساليب التخطيط الكلاسيكية عالية الأداء تمثيلاً داخلياً مشابهاً لنموذج STRIPS. في الواقع، تقوم معظم برامج التخطيط (FF، LPG، Fast-Downward، SGPLAN5، وLAMA) أولاً بتحويل نموذج ADL إلى نموذج STRIPS (بدون تأثيرات أو أهداف مشروطة أو كمية).

1. تسمح لغة STRIPS فقط بالقيم الإيجابية في الولايات، بينما تدعم لغة ADL القيم الإيجابية والسلبية على حد سواء. على سبيل المثال، يمكن أن تكون الجملة الصحيحة في STRIPS هي "غني  ∧  جميل". ويمكن التعبير عن الجملة نفسها في ADL على النحو التالي: "¬فقير  ∧  ¬قبيح"
2. في لغة STRIPS، تكون القيم الحرفية غير المذكورة خاطئة. يُعرف هذا بافتراض العالم المغلق . أما في لغة ADL، فتكون القيم الحرفية غير المذكورة غير معروفة. يُعرف هذا بافتراض العالم المفتوح.
3. في لغة STRIPS، لا يمكننا إيجاد سوى القيم الحرفية الأساسية في الأهداف. على سبيل المثال، Rich ∧ Beautiful. أما في لغة ADL، فيمكننا إيجاد المتغيرات الكمية في الأهداف. على سبيل المثال، ∃ x At (P1, x ) ∧ At(P2, x ) هو الهدف المتمثل في وضع P1 وP2 في نفس المكان في مثال المكعبات.
4. في نموذج STRIPS، تكون الأهداف عبارة عن روابط، مثل (غني ∧ جميل). أما في نموذج ADL، فقد تتضمن الأهداف روابط وفصلات (غني ∧ (جميل ∨ ذكي)).
5. في نظام STRIPS، تكون التأثيرات عبارة عن روابط، أما في نظام ADL، فيُسمح بالتأثيرات الشرطية: عندما P : E تعني أن E تأثير فقط إذا تحقق الشرط P
6. لا تدعم لغة STRIPS المساواة. أما في لغة ADL، فإنّ شرط المساواة ( x = y ) مُدمجٌ فيها.
7. لا يدعم STRIPS الأنواع، بينما يدعمها ADL (على سبيل المثال، المتغير p  : Person).

تُقيَّد قدرة لغة STRIPS التعبيرية بأنواع التحويلات التي يمكن وصفها في اللغة على مجموعات الصيغ. وتُجرى هذه التحويلات باستخدام عوامل STRIPS عن طريق إزالة بعض الصيغ من المجموعة المراد تحويلها وإضافة صيغ جديدة. بالنسبة لعامل STRIPS مُحدد، تكون الصيغ التي تُضاف وتُحذف ثابتة لجميع مجموعات الصيغ المراد تحويلها. ونتيجةً لذلك، لا تستطيع عوامل STRIPS نمذجة الإجراءات التي تعتمد آثارها على الظروف التي تُنفَّذ فيها بشكل كافٍ. لنفترض صاروخًا سيُطلق لفترة زمنية مُحددة. قد يختلف مساره ليس فقط بسبب مدة الاحتراق، بل أيضًا بسبب سرعة الصاروخ وكتلته واتجاهه. لا يمكن نمذجة ذلك باستخدام عامل STRIPS لأن الصيغ التي يجب إضافتها وحذفها ستعتمد على مجموعة الصيغ المراد تحويلها. ^{[ 8 ]}

على الرغم من إمكانية الاستدلال الفعال عند استخدام لغة STRIPS، إلا أنه من المتعارف عليه عمومًا أن قدرة STRIPS التعبيرية لا تفي بالغرض في نمذجة الإجراءات في العديد من التطبيقات العملية. وقد حفز هذا القصور تطوير لغة ADL. ^{[ 9 ] [ 10 ]} تقع قدرة ADL التعبيرية وتعقيدها بين لغة STRIPS وحساب المواقف. فقدرتها التعبيرية كافية لتمثيل مثال الصاروخ المذكور أعلاه، وفي الوقت نفسه، فهي محدودة بما يكفي للسماح بتطوير خوارزميات استدلال فعالة.

كمثال في نسخة أكثر تعقيدًا من عالم المكعبات : قد يكون حجم المكعب A ضعف حجم المكعبين B وC، لذا فإنّ الإجراء xMoveOnto(B,A) قد لا يُفعّل Clear(A) إلا إذا كان On(A,C) مُفعّلاً بالفعل، أو قد يُنشئ تأثيرًا مشروطًا يعتمد على حجم المكعبات. يصعب التعبير عن هذا النوع من التأثيرات المشروطة في ترميز STRIPS بدون استخدام التأثيرات المشروطة.

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

الإجراءات الضرورية هي التحميل والتفريغ والنقل الجوي ؛ ويمكن التعبير عن ذلك من خلال الواصفات ،In(c, p) وما At(x, A)إذا كانت الشحنة c موجودة في الطائرة p وما إذا كان الجسم x موجودًا في المطار A.

ويمكن تعريف الإجراءات على النحو التالي:

الإجراء (  التحميل ( ج : شحن، ع: طائرة، م: مطار)  الشرط المسبق: عند ( ج ، م) ^ عند ( ع ، م)  التأثير: ¬عند ( ج ، م) ^ في ( ج ، ع) )الإجراء (  تفريغ ( ج : شحنة، ع: طائرة، م: مطار)  الشرط المسبق: في ( ج ، ع) ^ عند ( ع ، م)  التأثير: عند ( ج ، م) ^ ¬ في ( ج ، ع) )الإجراء (  الطيران ( ع : طائرة، من: المطار، إلى: المطار)  الشرط المسبق: عند ( ع ، من)  التأثير: ¬عند ( ع ، من) ^ عند ( ع ، إلى) )

• لغة الحركة
• اختيار الإجراء
• شبكة المهام الهرمية
• لغة تعريف مجال التخطيط (PDDL)