مخطط بياني

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
الموسوعة الحرة

Graphplan هي خوارزمية للتخطيط الآلي تم تطويرها بواسطة Avrim Blum و Merrick Furst في عام 1995. تأخذ Graphplan كمدخل مشكلة تخطيط معبر عنها في STRIPS وتنتج، إن أمكن، سلسلة من العمليات للوصول إلى حالة الهدف.

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

في مخطط فضاء الحالة :

  • تمثل العقد الحالات الممكنة،
  • وتشير الحواف إلى إمكانية الوصول من خلال إجراء معين.

على العكس من ذلك، في مخطط التخطيط الخاص بـ Graphplan :

  • تمثل العقد الإجراءات والحقائق الأساسية، مرتبة في مستويات بديلة.
  • والحواف نوعان:
    1. من حقيقة ذرية إلى الأفعال التي تُعد شرطاً لها،
    2. من الفعل إلى الحقائق الذرية التي يجعلها صحيحة أو خاطئة.

يحتوي المستوى الأول على حقائق ذرية حقيقية تحدد الحالة الأولية.

كما يتم الاحتفاظ بقوائم للحقائق غير المتوافقة التي لا يمكن أن تكون صحيحة في نفس الوقت، والإجراءات غير المتوافقة التي لا يمكن تنفيذها معًا.

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

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

مراجع