latex
المعالم حقائق أو أفعال تظهر في جميع الحلول الصالحة لأي مشكلة تخطيط، واستُخدمت بنجاح لاشتقاق دوال إرشادية توجه البحث عن خطة. في هذا العمل نستكشف توسيع هذا المفهوم عبر تعريف جديد يُسمّى «درجة الصلة»، التي تقيس مدى تكرار ظهور حقائق أو أفعال معينة في معظم الخطط ولكن ليس في جميعها لتحقيق هدف معيّن. نصف هنا طريقة حساب هذه الدرجة واستخدامها كأساس لدالة إرشادية أثناء البحث. نقارن أداء منهجنا بمنهج تخطيط قائم على المعالم يُعدّ من أحدث الأساليب، باستخدام مجموعة من المشكلات القياسية. ونجد أنه في حين يتفوّق الإرشاد المعتمد على المعالم الأصلية في المجالات ذات المعالم المحددة بوضوح، تحقق درجة الصلة تحسينات كبيرة في المجالات التي تفتقر إلى معالم غير تافهة.
يُعَدُّ استخدام الدوال الإرشادية لتوجيه البحث وتقليص مساحة البحث مكوناً أساسياً في أنظمة التخطيط الحديثة. وتوجد أدبيات واسعة حول الأساليب التي تُوظّف هذه الدوال لتحسين الكفاءة الحسابية في إيجاد الخطط. فالدالة الإرشادية الملائمة التي تُحتسب بسرعة تجعل البحث الإرشادي في فضاء الحالات أكثر كفاءة بكثير من طرق البحث غير الموجهة. إحدى هذه الدوال الناجحة في تخطيط المهام هي عدّ «المعالم البارزة» غير المنفذة من الحالة الحالية (Zhu2003, Hoffmann2004, Richter2010, Keyder2010)، حيث يُعرَّف المعلم البارز كحقيقة أو فعل أو عبارة منطقية توجد في جميع الحلول الصالحة (أي تسلسلات الأفعال) لمشكلة التخطيط. يؤدي ذلك إلى تفضيل الأفعال التي هي معالم بارزة أو تحقق واحداً منها. ومع ذلك، فإن حساب جميع المعالم البارزة لمشكلة تخطيط ما عملية مكلفة؛ وهو أمر معروف بأنه كاملة الفضاء الكلي (Porteous2001a). لذا غالباً ما تستخرج الأنظمة التي تحسب المعالم البارزة مجموعةً فرعيةً منها عبر تبسيط مشكلة التخطيط (Keyder2010)، غير أن تكلفة الحساب تظل مرتفعة.
أحد القيود الشائعة على المنهجيات التي تحسب المعالم وتستخدمها كدالة إرشادية هو وجوب وجود معالم غير تافهة في مجالات التخطيط قيد الدراسة. ففي كثير من المجالات المعقدة التي توفر مسارات متعددة لتحقيق الهدف، قد تكون المعالم البسيطة (حقائق منفردة) الموجودة تافهة—أي مدرجة في مواصفات الهدف أو صحيحة بالفعل في الحالة الابتدائية. ورغم أن الصيغ المنطقية المعقدة قد تلعب دور معالم بارزة، يصعُب احتسابها واستخدامها كدالة إرشادية. يتجنب المنهج الموصوف هنا هذا القيد بحساب «درجة الصلة»، التي تقيّم أيضاً القيمة الإرشادية للحقائق (أو الأفعال) التي تظهر في كثير من الخطط الصالحة لكنها ليست ضرورية في جميعها. الفرضية الأساسية أننا بحوزة هذه المعلومات الإضافية ننطلق في بحث أكثر كفاءة عن حل صالح لمشكلة التخطيط المعطاة. كنموذج أساسي، نعتمد مخطط LAMA (Richter2010)، الذي يجمع عدّ المعالم البارزة مع المصطلح الأمامي للتكلفة (Hoffmann2001)، ويستخرج أقصر خطة بواسطة بحث \(A^*\) الموزون في إطار استرخاء الحذف. وقد ظل هذا المنهج متصدراً مسابقات التخطيط لأكثر من عقد.
المساهمة الرئيسية لهذه الورقة هي تعريف ووصف دالة إرشادية جديدة، «درجة الصلة» (\(h_{\Xi}\)). تقوم هذه الدالة بتعميم مفهوم المعلم البارز—الذي يجب أن يتحقق في كل خطة صالحة تحت استرخاء الحذف—إلى مقياس يقيس مدى ظهور الحقائق أو الأفعال ضمن الخطط تحت نفس شروط الاسترخاء. يوضح الشكل [fig:illustration] المعلومات التي نهدف إلى التقاطها عبر درجة الصلة وعلاقتها بالمعالم البارزة. وللمقارنة مع مخطط LAMA الأصلي، نركز هنا على الحقائق باعتبارها كيانات شبيهة بالمعالم. ثم نوضح، عبر تقييم تجريبي على مجموعة من مشكلات التخطيط القياسية، أنه بينما يتفوّق الإرشاد المعتمد على المعالم البارزة في المشكلات المزودة بمعالم بارزة واضحة، يحقق نهجنا المعتمد على درجات الصلة تحسناً ملموساً في المشكلات التي تفتقد معالم بارزة غير تافهة.
يُنظَّم باقي البحث على النحو التالي. يستعرض القسم [sec:rel-work] الأعمال ذات الصلة التي تلهم منهجنا المقترح. يصف القسم [sec:definitions] صياغة المشكلة والاستدلال الجديد، في حين يوضح القسم [sec:methods] كيفية حساب هذا الاستدلال واستخدامه في تركيب الخطط. تستند النتائج التجريبية في القسم [sec:results] إلى تحليل أداء المنهج، وتفتح الباب لمناقشة الخطوات المستقبلية في القسم [sec:discuss].
قدّم Porteous (Porteous2001a) أول تعريف للمعالم كوسيلة للتوجيه الأساسي، ثم طوّرها Hoffmann (Hoffmann2004) بامتداد يرتكز على ترتيب الأهداف. هدفوا إلى استخراج وترتيب الحقائق التي يجب تحقيقها في أي خطة صالحة، والتعامل مع هذا الترتيب الجزئي للمعالم كسلسلة من الأهداف الفرعية لتقسيم مشكلة التخطيط إلى مهام أبسط. عادةً ما تُستخرج المعالم عبر استخدام رسم بياني للتخطيط المرن (RPG) (Hoffmann2001)، الذي يحلل إمكانيات الوصول ضمن استرخاء الحذف ويتضمن خطوات متعددة للتحقق من صحة المعالم وترتيبها.
استخدم عدد من الباحثين المعالم لتوجيه المخططين المعتمدين على البيانات الإرشادية (Zhu2003, Helmert2006, Richter2008). وقد توسّع آخرون في هذا الإطار لاستهداف إيجاد خطط أمثل من حيث التكلفة، وبدأوا باستخدام الأفعال والصيغ القابلة للاقتراح كمعالم محتملة (Keyder2008, Karpas2009, Richter2010). في الغالب، يُقدَّر عدد المعالم في الرسم البياني بناءً على افتراض أن لكل معلم غير منفّذ تكلفة فعل واحدة، ومن ثم تُقدَّر المسافة إلى الهدف بعدد المعالم المتبقية. وحاول بعض الباحثين الاحتفاظ بالتكاليف الحقيقية للأفعال في التقييم، مع الأخذ في الاعتبار الأفعال القادرة على تحقيق أكثر من معلم دفعة واحدة (Helmert2009, Karpas2009). كذلك استكشفت دراسات أخرى طرقاً أكثر كفاءة لاستخراج المعالم (Keyder2010).
لقد قمنا بتقييم التجارب التالية:
يُعدُّ مقياس درجة الصلة S1 أبطأ من مقياس عد المعالم البارزة S2 عند حل المشكلات القياسية، لكنه يظل قادراً على إيجاد حلول في معظم الحالات.
يحسن مقياس درجة الصلة S1 بشكل كبير القدرة على إيجاد الخطط مقارنة بمقياس عد المعالم البارزة S2 في المجالات التي لا تحتوي على معالم غير تافهة.
لا يتأثر المخطط بتغييرات بسيطة في \(\rho\). نلاحظ أن استكشاف المزيد من الشجرة (أي التوقف عند نسبة أقل من المعلومات مقابل \( \overline{T_{\Pi}} \)) لا يحسّن قدرة \( h_{\Xi} \) على حل المشكلات، بينما يستهلك المزيد من الذاكرة ويقلل قدرة المخطط على العمل ضمن حدود الذاكرة.
توفر النتائج التجريبية رؤى هامة. فعند احتساب درجة الصلة على الشجرة المكتشفة بالكامل (\( \overline{T_{\Pi}} = T_{\Pi} \)), حيث تحصل الحقائق المعتبرة معالم على قيمة \(\Xi_\sigma(l)=1\) وتُضاف إليها صلة بقية الحقائق، يتبيّن أنه في المشكلات القياسية تزيد هذه المعلومات من زمن التخطيط، ويبدو أن الإرشاد المقترح يعيق إيجاد حل ضمن حدود الموارد. نفترض أن الحقائق ذات الصلة العالية (أقل من 1) توجه المخطط نحو مسارات بديلة متنافسة، فتنتج خططاً أطول تشتمل على عناصر من مسارات جزئية عدة. وعندما يكون التداخل بين المسارات ضعيفاً، يزداد فرق طول الخطط بين S1 وS2. كما تزيد هذه الظاهرة من تكلفة الاستكشاف (M2 وM3)، فتدرج مشاكل لا تُحل ضمن قيود الذاكرة.
في المشكلات الخالية من معالم غير تافهة، يكتفي S2 بإبلاغ المخطط بأن بعض حقائق الهدف قد تُشكّل بداية جيدة، ويبقى البحث دون توجيه فعّال حتى تتحقق إحدى هذه الحقائق. أما S1 فيمكنه استكشاف سطح معلومات مائل نحو الخطط المحتملة بسبب مكافأته للحقائق ذات الصلة بالمسارات البديلة—وإن لم تسهم مباشرة في الهدف. لذلك يميل إلى تضمين أفعال لا تحقق الهدف فعلياً، ما يؤدي إلى خطط أطول. نرى أن هذا ناتج عن طريقة توليد المجالات المدروسة ولا يلزم أن يتكرر في مجالات أخرى.
بشكل عام، أهم ما نلاحظه هو قدرة إرشاد درجة الصلة على توجيه مخطط LAMA نحو حلّ مشكلات يضعف فيها عد المعالم، لكن ذلك على حساب تكلفة حسابية أعلى وأداء أضعف في المشكلات القياسية. لذا يُوصى باستخدامه فقط في المشكلات التي يتفوق فيها—أي التي تحتوي على عدد قليل أو لا تحتوي على معالم غير تافهة. ولحسن الحظ، تُحدَّد المعالم قبل بدء البحث، مما يتيح دمج كلا الإرشادين بسهولة: استخدم عد المعالم في المجالات التي تمتلك معالم واضحة، ودرجة الصلة في المجالات التي لا تمتلك سوى معالم تافهة. في العمل المستقبلي، سنسعى لاستقصاء هذه الأفكار مع مجالات تخطيط أكثر تنوعاً وتعقيداً.