التخطيط الكلاسيكي: القوالب والإرخاءات وبيان التخطيط

سيحلّ البحث مسألة تخطيط متى أُعطي استدلالًا. والسؤال المثير هو من أين يأتي الاستدلال، والجواب يتبيّن أنه دعوى عن التمثيل لا عن الخوارزميات.

أ. ما الذي يشتريه التمثيل العاملي

يعامل عميلُ حلّ المسائل الحالةَ معاملةَ الذرّة. فلا يسعه منها إلا اختبار كونها هدفًا، ولا شيء غير ذلك، فيلزم أن يُمَدّ بكل استدلال من الخارج. أما العميل المنطقي فيستطيع النظر داخل الحالة، لكنه يستدلّ بجمل مؤرَّضة ويغرق فيها: ففي عالم الومبَس احتاج التقدّم إلى الأمام جملةً منفصلة لكل اتّجاه من أربعة اتّجاهات، و$T$ خطوة زمنية، و$n^2$ موضعًا.

ويسلك التخطيط الطريق الوسط. فالحالة مجموعة متغيّرات - عطفٌ بين قضايا متغيّرة (fluents) مؤرَّضة موجبة خالية من الدوالّ:

$$\mathrm{At}(\mathit{Flat}, \mathit{Axle}) \wedge \mathrm{At}(\mathit{Spare}, \mathit{Trunk}) .$$

وتحت افتراض العالم المغلق يكون كل ما لم يُذكَر كاذبًا، فلا يلزم كتابة النفي أبدًا. فتُقرأ الحالة عندئذ على وجهين معًا، جملةً منطقية أو مجموعةً، وتأخذ كل الخوارزميات تقريبًا بالثاني.

والأفعال قوالب لا تصف إلا ما يتغيّر:

$$\begin{array}{l} \mathrm{Action}(\mathrm{Fly}(p, \mathit{from}, \mathit{to}), \\ \quad \textsc{Precond}: \mathrm{At}(p, \mathit{from}) \wedge \mathrm{Plane}(p) \wedge \mathrm{Airport}(\mathit{from}) \wedge \mathrm{Airport}(\mathit{to}) \\ \quad \textsc{Effect}: \neg\mathrm{At}(p, \mathit{from}) \wedge \mathrm{At}(p, \mathit{to})) \end{array}$$

والحروف الموجبة هي قائمة الإضافة، والمنفيّة قائمة الحذف، وتطبيق الفعل تعبيرٌ مجموعيّ واحد: $\mathrm{Result}(s, a) = (s \setminus \mathrm{Del}(a)) \cup \mathrm{Add}(a)$. ومسألة الإطار ليست محلولة بقدر ما هي متروكة: إذ يُقصَر النظر على المجالات التي تترك فيها أكثرُ الأفعال أكثرَ الأشياء على حالها، فتصير الاستدامة هي الأصل.

ب. ثمن التأريض

القالب موجز؛ وأمثلته ليست كذلك. فبشحنتين وطائرتين ومطارين تتوسّع ثلاثة قوالب للشحن الجوّي إلى عشرين فعلًا مؤرَّضًا، وقالب الطيران وحده بعشر طائرات وخمسة مطارات يعطي $10 \times 5 \times 4 = 200$.

وليس الشرط في آخر الاستيعاب تأنّقًا. فبدونه يُنتج القالب $\mathrm{Fly}(P_1, JFK, JFK)$، وأثره $\neg\mathrm{At}(P_1, JFK) \wedge \mathrm{At}(P_1, JFK)$، وذلك تناقض؛ والإصلاح المبدئي شرطٌ مسبق بعدم المساواة.

ولهذا يتعثّر البحث الأمامي. فهو تامّ، وأمثل عند تساوي الكلف، لكنه سينظر في تطيير طائرة فارغة بين مطارين لا صلة لهما بالأمر بمثل ما ينظر في تحميل الشحنة الصحيحة. أما البحث الخلفي من الهدف فلا ينظر إلا في الأفعال ذات الصلة، إذ يرتدّ بالهدف إلى $(g \setminus \mathrm{Add}(a)) \cup \mathrm{Precond}(a)$، ويتفرّع أقلّ بكثير - لكن عقده مجموعات حالات لا حالات، وذلك يحتاج توحيدًا ويجعل الاستدلالات الجيدة أعسر تعريفًا.

ج. استدلالات بالحذف

هنا يؤتي التمثيل ثمرته. فالاستدلال كلفةُ مسألة أيسر، والقوالب يمكن ببساطة أن تُحرَّر.

إهمال الشروط المسبقة ينزع كل شرط مسبق، فيصير كل فعل قابلًا للتطبيق في كل موضع. والباقي تغطية حروف الهدف غير المحقّقة بأقلّ ما يمكن من قوائم الإضافة. ومن هنا جاءت استدلالات الأحاجي الكلاسيكية: ففي أحجية الثمانية يعطي إسقاط $\mathrm{Blank}(s_2) \wedge \mathrm{Adjacent}(s_1, s_2)$ عددَ البلاطات في غير مواضعها، ويعطي إسقاط $\mathrm{Blank}(s_2)$ وحده مسافة مانهاتن. وكلاهما يسقط سقوطًا آليًا.

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

وعلى مسألة الشحن الجوّي يبلّغ كلاهما 2 عند الحالة الابتدائية في مقابل كلفة حقيقية قدرها 6 (ورقم إهمال قوائم الحذف يعدّ طبقات المسألة المُرخاة كما يفعل بيان التخطيط، أما أقصر خطة مُرخاة فتضمّ 5 أفعال):

والفوارق ضئيلة لأن المسألة صغيرة. والمهمّ أن أحدًا لم يكتب استدلالًا للشحن الجوّي.

د. ما الذي يلحظه بيان التخطيط

بيان التخطيط يناوب بين مستويات الحالات ومستويات الأفعال، ويضيف فعل استدامة لكل حرف، ويُبنى في زمن كثير الحدود بلا بحث. وجوهره روابط التنافي (mutex) التي تسجّل الأزواج التي لا يمكن أن تجتمع: الأفعال ذات الآثار المتناقضة، والأفعال التي يتداخل بعضها مع بعض، والأفعال ذات الحاجات المتزاحمة، والحروف التي يتنافى كل زوج من منتجيها.

خذ أصغر مسألة توضّح المقصود. لديك في البداية كعكة؛ وتريد أن تملكها وأن تكون قد أكلتها. والأكل يحذف الملك، والخَبز يقتضي عدم الملك.

وتظهر حرفا الهدف كلاهما عند $S_1$، فيقول الاستدلال حرفًا حرفًا إن خطوة واحدة تكفي. وهي لا تكفي: فهما عند $S_1$ متنافيان، لأن السبيل الوحيد إلى ملك الكعكة هو استدامتها، والسبيل الوحيد إلى أكلها هو أكلها، والأكل يحذف الملك. وعند $S_2$ يزول التنافي ويكون البيان قد استوى.

وكلفة المستوى لحرف هي المستوى الذي يظهر فيه أول مرة، وهي تعطي ثلاثة استدلالات. فأقصى المستوى يأخذ الأكبر، ومجموع المستويات يجمعها، ومستوى المجموعة ينتظر أول مستوى تظهر فيه كل حروف الهدف دون تنافٍ بينها. وهنا تعطي $1$ و$1$ و$2$. والخطة المثلى - كُلِ الكعكة ثم اخبز أخرى - طولها $2$، فمستوى المجموعة وحده هو المصيب، وهو وحده الذي نظر هل تستطيع الأهداف أن تجتمع.

وأقصى المستوى ومستوى المجموعة مقبولان، ومستوى المجموعة يسيطر. أما مجموع المستويات فيعامل الأهداف الفرعية معاملة المستقلّة وقد يتجاوز، فهو غير مقبول في العموم، وذلك لا يمنعه من أن يكون أنفع الثلاثة في الممارسة.

يبني الشكل أدناه ذلك البيان بدل أن ينقله: فكل تعارض فيه محسوب من شروط الأفعال الثلاثة وشرطَي المقولات، ولهذا تخرج الأعداد من تلقاء نفسها 0 و4 و3 و3. وانظر إلى الخط الواصل بين مقولتَي الهدف: هو حاضر عند S1 وغائب عند S2، وهذا الخط المتلاشي وحده هو كل الفرق بين استدلال يجيب 1 والجواب الحقيقي 2.

أين يضعك هذا

التقريب يجري في اتّجاه واحد لا غير. فالحرف الغائب عند المستوى $i$ غير قابل للتحقيق حقًّا في $i$ خطوة، وذلك ما يجعل كلف المستويات حدودًا دنيا. أما الحرف الحاضر، ولو بلا تنافٍ، فلا يعد بشيء؛ إذ لا يُحسَب إلا التنافي بين الأزواج، فيمرّ تعارضٌ ثلاثيّ دون أن يُلحَظ. وذلك اللاتناظر هو الصورة الأمينة للموضوع كله: فالتخطيط الكلاسيكي لا يجعل المسائل الصعبة سهلة، وإنما يجعل وصف المسألة شيئًا يستطيع الحلّال قراءته. ومسار التدريب التخطيط الكلاسيكي يبني القوالب والإرخاءات والبيان يدويًا وبالشيفرة.