التخطيط الكلاسيكي وSTRIPS

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

Definition

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

Scope

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

Core questions

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

Key concepts

• نموذج حتمي، قابل للملاحظة بالكامل
• الشروط المسبقة والتأثيرات في STRIPS
• قوائم الإضافة والحذف
• PDDL وADL
• بحث التقدم (الأمامي)
• بحث التراجع (الخلفي)
• التخطيط ذو الترتيب الجزئي
• تعقيد وجود الخطة

Key theories

تمثيل STRIPS

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

بحث التقدم والتراجع

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

تعقيد التخطيط

إن تحديد ما إذا كانت خطة STRIPS الافتراضية موجودة هو PSPACE-كامل بشكل عام، مما يفسر رسميًا سبب صعوبة التخطيط ويحفز الأساليب الاستدلالية والهيكلية لجعله عمليًا.

Clinical relevance

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

History

طُوِّر STRIPS في SRI حوالي عام 1971 للتحكم في الروبوت Shakey، وقدم نموذج عمل الشرط المسبق/التأثير الذي يحدد التخطيط الكلاسيكي. نضج التخطيط ذو الترتيب الجزئي في السبعينيات والثمانينيات، وأثبت بايلاندر اكتمال PSPACE للتخطيط الافتراضي في عام 1994، ووحد معيار PDDL لاحقًا معايير المجال.

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Tom Bylander
• Earl D. Sacerdoti

Seminal works

• fikes1971
• bylander1994

Frequently asked questions

ما هي افتراضات التخطيط الكلاسيكي؟

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

ماذا تعني قائمة الإضافة وقائمة الحذف في STRIPS؟

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