معهد ستانفورد للأبحاث لحل المشكلات

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

يتكون نموذج STRIPS من:

• حالة ابتدائية؛
• تحديد حالات الهدف - المواقف التي يحاول المخطط الوصول إليها؛
• مجموعة من الإجراءات. لكل إجراء، يتم تضمين ما يلي:
  • الشروط المسبقة (ما يجب تحديده قبل تنفيذ الإجراء)؛
  • الشروط اللاحقة (ما يتم تحديده بعد تنفيذ الإجراء).

رياضياً، تُعتبر حالة STRIPS رباعية.${\displaystyle \langle P,O,I,G\rangle }$، حيث يكون لكل مكون المعنى التالي:

1. ${\displaystyle P}$هي مجموعة من الشروط (أي المتغيرات الافتراضية )؛
2. ${\displaystyle O}$هي مجموعة من العوامل (أي الإجراءات)؛ كل عامل هو في حد ذاته رباعي${\displaystyle \langle \alpha ,\beta ,\gamma ,\delta \rangle }$، كل عنصر عبارة عن مجموعة من الشروط. تحدد هذه المجموعات الأربع، بالترتيب، الشروط التي يجب أن تكون صحيحة حتى يكون الإجراء قابلاً للتنفيذ، والشروط التي يجب أن تكون خاطئة، والشروط التي يتم جعلها صحيحة بواسطة الإجراء، والشروط التي يتم جعلها خاطئة؛
3. ${\displaystyle I}$هي الحالة الأولية، المعطاة كمجموعة من الشروط التي تكون صحيحة في البداية (يفترض أن جميع الشروط الأخرى خاطئة)؛
4. ${\displaystyle G}$يمثل هذا تحديد حالة الهدف؛ ويتم تقديمه كزوج${\displaystyle \langle N,M\rangle }$والتي تحدد الشروط الصحيحة والخاطئة، على التوالي، حتى يتم اعتبار حالة ما حالة هدف.

إن خطة مثل هذه الحالة التخطيطية هي عبارة عن سلسلة من العمليات التي يمكن تنفيذها من الحالة الأولية والتي تؤدي إلى حالة الهدف.

بصورة رسمية، الحالة هي مجموعة من الشروط: تُمثَّل الحالة بمجموعة الشروط التي تتحقق فيها. تُنمذج الانتقالات بين الحالات بواسطة دالة انتقال، وهي دالة تربط الحالات بحالات جديدة ناتجة عن تنفيذ الإجراءات. وبما أن الحالات تُمثَّل بمجموعات من الشروط، فإن دالة الانتقال بالنسبة لمثيل STRIPS${\displaystyle \langle P,O,I,G\rangle }$هي دالة

${\displaystyle \operatorname {succ} :2^{P}\times O\rightarrow 2^{P},}$

أين${\displaystyle 2^{P}}$هي مجموعة جميع المجموعات الجزئية من${\displaystyle P}$وبالتالي فهي مجموعة جميع الحالات الممكنة.

دالة الانتقال${\displaystyle \operatorname {succ} }$بالنسبة لإحدى الولايات${\displaystyle C\subseteq P}$يمكن تعريفها على النحو التالي، باستخدام الافتراض المبسط بأن الإجراءات يمكن تنفيذها دائمًا ولكن ليس لها أي تأثير إذا لم يتم استيفاء شروطها المسبقة:

${\displaystyle \operatorname {succ} (C,\langle \alpha ,\beta ,\gamma ,\delta \rangle )}$	=${\displaystyle (C\backslash \delta )\cup \gamma }$	لو${\displaystyle \alpha \subseteq C}$و${\displaystyle \beta \cap C=\varnothing }$
	=${\displaystyle C}$	خلاف ذلك

الوظيفة${\displaystyle \operatorname {succ} }$يمكن توسيع نطاقها ليشمل تسلسلات من الإجراءات من خلال المعادلات التكرارية التالية:

${\displaystyle \operatorname {succ} (C,[\ ])=C}$

${\displaystyle \operatorname {succ} (C,[a_{1},a_{2},\ldots ,a_{n}])=\operatorname {succ} (\operatorname {succ} (C,a_{1}),[a_{2},\ldots ,a_{n}])}$

خطة لحالة STRIPS هي سلسلة من الإجراءات بحيث تحقق الحالة الناتجة عن تنفيذ هذه الإجراءات بالترتيب بدءًا من الحالة الأولية شروط الهدف. رسميًا،${\displaystyle [a_{1},a_{2},\ldots ,a_{n}]}$هي خطة لـ${\displaystyle G=\langle N,M\rangle }$لو${\displaystyle F=\operatorname {succ} (I,[a_{1},a_{2},\ldots ,a_{n}])}$يستوفي الشرطين التاليين:

${\displaystyle N\subseteq F}$

${\displaystyle M\cap F=\varnothing }$

اللغة المذكورة أعلاه هي في الواقع النسخة الافتراضية من STRIPS؛ عمليًا، غالبًا ما تتعلق الشروط بالكائنات: على سبيل المثال، يمكن نمذجة موضع الروبوت بواسطة مسند.${\displaystyle At}$، و${\displaystyle At(room1)}$هذا يعني أن الروبوت موجود في الغرفة 1. في هذه الحالة، يمكن أن تحتوي الأفعال على متغيرات حرة ، يتم تحديدها كميًا ضمنيًا. بعبارة أخرى، يمثل الفعل جميع الأفعال المنطقية الممكنة التي يمكن الحصول عليها باستبدال كل متغير حر بقيمة.

تُعتبر الحالة الأولية معروفة تمامًا في اللغة الموصوفة أعلاه: الشروط التي ليست في${\displaystyle I}$يُفترض خطأ جميع هذه الحالات. غالبًا ما يكون هذا افتراضًا مُقيِّدًا، إذ توجد أمثلة طبيعية لمشاكل التخطيط التي لا تكون فيها الحالة الأولية معروفة تمامًا. وقد طُوِّرت امتدادات لخوارزمية STRIPS للتعامل مع الحالات الأولية المعروفة جزئيًا.

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

الحالة الابتدائية: عند (أ)، مستوى (منخفض)، صندوق عند (ج)، موز عند (ب) الحالة المستهدفة: امتلاك (موز)

الإجراءات: // الانتقال من X إلى Y _Move(X, Y)_ الشروط المسبقة: عند (س)، المستوى (منخفض) الشروط اللاحقة: ليس عند (X)، عند (Y) // اصعد على الصندوق _ClimbUp(Location)_ الشروط المسبقة: في (الموقع)، صندوق في (الموقع)، مستوى (منخفض) الشروط اللاحقة: المستوى (عالي)، وليس المستوى (منخفض) // انزل من الصندوق _ClimbDown(Location)_ الشروط المسبقة: في (الموقع)، صندوق في (الموقع)، مستوى (عالي) الشروط اللاحقة: المستوى (منخفض)، وليس المستوى (مرتفع) // انقل القرد والصندوق من X إلى Y _MoveBox(X, Y)_ الشروط المسبقة: عند (X)، صندوق عند (X)، مستوى (منخفض) الشروط اللاحقة: BoxAt(Y)، ليس BoxAt(X)، At(Y)، ليس At(X) // خذ الموز _TakeBananas(Location)_ الشروط المسبقة: في (الموقع)، موز في (الموقع)، مستوى (عالي) الشروط اللاحقة: وجود (موز)

يُعدّ تحديد ما إذا كانت هناك خطة موجودة لحالة STRIPS افتراضية مسألةً كاملةً من فئة PSPACE . ويمكن فرض قيود مختلفة لتحديد ما إذا كانت الخطة موجودة في وقت متعدد الحدود ، أو على الأقل لجعلها مسألةً كاملةً من فئة NP . ^{[ 2 ]}

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

يمكن تحديد عوامل تشغيل كلية جديدة لمجال معين باستخدام البرمجة الجينية . ^{[ 4 ]} الفكرة ليست تخطيط المجال نفسه، بل إنشاء طريقة استدلالية في الخطوة التمهيدية تُمكّن من حل المجال بسرعة أكبر. في سياق التعلم المعزز ، يُطلق على عامل التشغيل الكلي اسم "خيار". على غرار التعريف في تخطيط الذكاء الاصطناعي، تكمن الفكرة في توفير تجريد زمني (يمتد على فترة أطول) وتعديل حالة اللعبة مباشرةً على مستوى أعلى. ^{[ 5 ]}

• لغة وصف الأفعال (ADL)
• التخطيط الآلي
• شبكة المهام الهرمية
• لغة تعريف مجال التخطيط (PDDL)
• شذوذ سوسمان

• سي. باكستروم وبي. نيبيل (1995). نتائج التعقيد لتخطيط SAS+. الذكاء الحسابي ، 11: 625-656.
• تي. بايلاندر (1991). نتائج التعقيد للتخطيط. في وقائع المؤتمر الدولي المشترك الثاني عشر حول الذكاء الاصطناعي (IJCAI'91) ، الصفحات 274-279.
• راسل، ستيوارت جيه .؛ نورفيج، بيتر (2003)، الذكاء الاصطناعي: منهج حديث (  الطبعة الثانية)، أبر سادل ريفر، نيو جيرسي: برنتيس هول، ISBN 0-13-790395-2