فهم التخطيط الآلي
يعالج التخطيط الكلاسيكي البيئات التامّة الرصد، الحتمية، الساكنة، ذات العميل الواحد، وإسهامه تمثيليّ لا خوارزميّ. فالحالة عطف من قضايا متغيّرة مؤرَّضة موجبة خالية من الدوالّ. وبافتراض العالم المغلق تكون كل قضية متغيّرة لم تُذكر كاذبةً، فلا يحتاج النفي إلى كتابة أصلاً، وبافتراض الأسماء الوحيدة تدلّ الثوابت المختلفة على أشياء مختلفة. ونتيجة ذلك أن الحالة يمكن أن تُقرأ على السواء جملةً منطقية يُستدلّ بها أو مجموعةً تُعالَج، وأكثر خوارزميات التخطيط تأخذ بالقراءة الثانية.
وتُعطى الأفعال قوالبَ بلغة PDDL، أي لغة تعريف مجال التخطيط، وهي سليلة STRIPS. فالقالب يسمّي الفعل، ويعدّد متغيّراته، ويعطي شرطاً مسبقاً وأثراً. والحروف الموجبة في الأثر تؤلّف قائمة الإضافة، والمنفيّة منها تؤلّف قائمة الحذف، فيصير تطبيق فعل مؤرَّض على حالة تعبيراً مجموعياً واحداً: احذف قائمة الحذف ثم أضف قائمة الإضافة. وكل ما عدا ذلك يبقى على حاله افتراضاً. وهكذا يتعامل التخطيط الكلاسيكي مع مسألة الإطار - لا بإثبات ما يبقى على حاله، بل بقصر النظر على مجالات تترك فيها أكثرُ الأفعال أكثرَ الأشياء دون مساس، ثم بوصف التغيير وحده.
والقالب تمثيل مرفوع، يرقى بالاستدلال من منطق القضايا إلى شذرة مقيَّدة من منطق الرتبة الأولى. فحيث كان العميل القضويّ يحتاج جملةً لكل اتجاه وكل خطوة زمنية وكل موضع، يغطّيها قالب واحد جميعاً. والاقتصاد حقيقي، لكن تأريضه باهظ: إذ ينتشر القالب على مجال كل وسيط من وسائطه، حتى إن فعل طيران بعشر طائرات وخمسة مطارات يسهم وحده بمئتَي فعل مؤرَّض. ويلزم شيء من الحذر كذلك إزاء النسخ الزائفة، كالطيران من مطار إلى نفسه، وهي تُستبعد بشرط مسبق من عدم المساواة.
ويُكتب الهدف كما يُكتب الشرط المسبق، عطفاً من حروف تُقرأ متغيّراتها قراءةً وجودية، وتبلغه الحالة متى استلزمته. وبهذا تكتمل مسألة بحث: حالة ابتدائية، وأفعال قابلة للتطبيق، ودالّة نتيجة، واختبار هدف. والبحث الأمامي في هذا الفضاء تامّ لكنه سيّئ التوجيه، لأن التأريض يولّد أفعالاً كثيرة لا صلة لها بأي هدف بعينه. أما البحث الخلفي من الهدف فلا ينظر إلا في الأفعال ذات الصلة، فيتفرّع أقلّ، غير أن عُقده مجموعات حالات لا حالات مفردة. والميزة الحاسمة لهذا التمثيل أن الدالّة الاستدلالية يمكن استخراجها بتحرير القوالب نفسها.
كيفية الحساب
Result(s, a) = (s \ Del(a)) ∪ Add(a), applicable when Precond(a) ⊆ s
حيث
- s
- الحالة: مجموعة القضايا المتغيّرة المؤرَّضة الموجبة الصادقة فيها، وما عداها كاذب
- Add(a)
- الحروف الموجبة في أثر الفعل
- Del(a)
- الحروف التي ينفيها أثر الفعل
- Precond(a)
- الحروف التي يجب أن تصدُق ليكون الفعل قابلاً للتطبيق
مثال على التخطيط الآلي
تبدأ مسألة العجلة الاحتياطية من At(Flat, Axle) ∧ At(Spare, Trunk) بالهدف At(Spare, Axle). والبحث الأمامي بالعرض أولاً يعيد خطّة من ثلاث خطوات: انزع العجلة المثقوبة عن المحور، وأخرج الاحتياطية من الصندوق، وركّب الاحتياطية على المحور.
ولا بدّ من نزع المثقوبة أولاً لأن PutOn يحمل الشرط المسبق المنفيّ ¬At(Flat, Axle). ولولاه لكان الاختصار في خطوتين مشروعاً، وهذا يبيّن أن الشروط المسبقة المنفيّة تؤدّي عملاً تعجز عنه قائمتا الإضافة والحذف وحدهما.
ومجال الشحن الجوّي بشحنتين وطائرتين ومطارين ينشر ثلاثة قوالب في عشرين فعلاً مؤرَّضاً، وخطّته المثلى ستّ خطوات: حمّل الشحنتين، وطيِّر كل طائرة إلى المطار الآخر، ثم أنزل الشحنتين.
المزايا والعيوب
المزايا
- الحلّال المستقلّ عن المجال نفسه يتناول أي مسألة يمكن التعبير عنها باللغة، دون بحثٍ مكتوب باليد.
- بنية القوالب تدعم دوالّ استدلالية تُشتقّ آلياً بالإرخاء، بدل أن تُبتكر لكل مجال على حدة.
- تحديث الحالة حساب مجموعات، وهذا يبقي التنفيذ قصيراً ويجعل الاستدلال عليه مباشراً.
العيوب
- تأريض القالب ينشره على مجال كل وسيط من وسائطه، وقد ينفجر قبل أن يبدأ البحث أصلاً.
- الافتراضات الكلاسيكية - الحتمية والرصد التامّ والسكون والعميل الواحد - تستبعد أكثر البيئات الواقعية.
- قصر الحالات على قضايا متغيّرة مؤرَّضة موجبة بلا دوالّ يستبعد أوصافاً تعبيرية تحتاجها بعض المجالات حقاً.
الأسئلة الشائعة
بمَ يختلف هذا عن البحث المعتاد؟
البحث المعتاد يعامل الحالة ذرّةً لا يمكن إلا اختبار كونها هدفاً، فتلزم دالّة استدلالية تُقدَّم باليد. أما التخطيط فيستعمل حالة عاملية وأوصاف أفعال قابلة للفحص، ومعنى ذلك أن الحلّال يبني دالّته الاستدلالية بنفسه بإرخاء القوالب. وخوارزميات البحث ذاتها لا تتغيّر.
لماذا تُمنع الحروف المنفيّة من الحالات وتُجاز في الشروط المسبقة؟
الحالة يجب أن تكون منتهية، وسرد كل ما هو كاذب ليس كذلك. وافتراض العالم المغلق يجعل الغياب كذباً، فلا تحتاج الحالة إلا إلى القضايا المتغيّرة الموجبة. أما الشرط المسبق فاستعلام لا وصف، فالسؤال عن غياب شيء فيه ذو معنى وزهيد الكلفة معاً.
هل البحث الخلفي أفضل لأنه أقلّ تفرّعاً؟
هو أقلّ تفرّعاً بالفعل، إذ لا يكون ذا صلة إلا الفعل الذي تمدّ قائمةُ إضافته حرفاً مطلوباً. لكن كل عقدة وصفُ هدف ينوب عن حالات كثيرة وقد يحتوي متغيّرات، فتحتاج المطابقة إلى التوحيد، ويصعب تعريف دوالّ استدلالية جيّدة. وقد غلب في العموم البحث الأمامي المزوَّد بدالّة استدلالية مشتقّة قوية.
الخلاصة
التخطيط الآلي رهان على أن التمثيل الصائب يغلب البحث الأمهر: صِف الأفعال بما تغيّره، وأبقِ الحالات عاملية، عندئذ يستطيع حلّال مستقلّ عن المجال أن يقرأ وصف المسألة قراءةً تكفي لبناء دوالّه الاستدلالية بنفسه. وكل ما يجعل هذه اللغة مقيَّدة هو عينه ما يجعل ذلك ممكناً.