المعالِم هي حقائق أو أفعال تظهر في جميع الحلول الصالحة لأيّ مشكلة تخطيط، وقد استُخدمت بنجاح لاشتقاق دوالّ إرشاديّة تُوجِّه البحث عن خطة. في هذا العمل نستكشف توسيع هذا المفهوم بتعريف جديد نُسمّيه «درجة الصِّلة»، يقيس مدى تكرار ظهور حقائق أو أفعال معيّنة في معظم الخطط لا في جميعها لتحقيق هدفٍ معيّن. نصفُ طريقةً لحساب هذه الدرجة واستعمالها أساساً لدالّة إرشاديّة أثناء البحث. نقارن بين أداء منهجنا ومنهج تخطيط قائم على المعالِم يُعدّ من أحدث الأساليب، باستخدام مجموعة من المشكلات القياسيّة. ونجد أنّه، بينما يتفوّق الإرشاد المعتمد على المعالِم في المجالات التي تتضمّن معالِم محدّدة بوضوح، تُحقِّق درجة الصِّلة تحسينات كبيرة في المجالات التي تفتقر إلى معالِم غير تافهة.
يُعَدّ استخدام الدوالّ الإرشاديّة لتوجيه البحث وتقليص مساحة البحث مُكوِّناً أساسياً في أنظمة التخطيط الحديثة. وتوجد أدبيات متينة حول الأساليب التي تُوظَّف فيها هذه الدوال لتحسين الكفاءة الحسابيّة في إيجاد الخطط. فالدالة الإرشادية الملائمة التي تُحتسَب سريعاً تجعل البحث الإرشادي في فضاء الحالات أكثر كفاءة بكثير من طرق البحث غير المُوجَّهة. إحدى الدوالّ الإرشاديّة الناجحة في تخطيط المهام هي عدّ المعالِم غير المُنجزة انطلاقاً من الحالة الحالية (Zhu2003, Hoffmann2004, Richter2010, Keyder2010)، حيث يُعرَّف «المعلَم» كحقيقة أو فعل أو صيغة قضاياية على الحقائق والأفعال لا بدّ من تحقّقها في جميع الحلول الصالحة (أي تسلسلات الأفعال) لمشكلة التخطيط. يؤدي ذلك إلى تفضيل الأفعال التي تُعدّ معالِم أو تُحقّق أحدها. ومع ذلك، فإن حساب جميع المعالِم لمشكلة تخطيطٍ ما عمليةٌ مُكلفة؛ وهي معروفة بأنها من مسائل PSPACE-كاملة (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).
يعرّف هذا القسم مبدأ «درجة الصِّلة» \(h_{\Xi}\) للحقائق/الأفعال ضمن إطار استرخاء الحذف، ويعرض على نحوٍ مُوجز كيفية تقديرها اعتماداً على تردّد الظهور في الخطط الممكنة، ثم يوظّفها دالّةً إرشاديّة أثناء البحث. تُركت التفاصيل والصيغ الرياضيّة كما هي في النص الأصلي.
لقد أجرينا التقييمات التالية:
يُعَدّ مُقَيَّس درجة الصِّلة 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 نحو حلٍ لمشكلاتٍ يضعف فيها عدّ المعالِم. لكن ذلك على حساب كلفةٍ حاسوبيّة أعلى وأداءٍ أضعف في المشكلات القياسية. لذا يُوصى باستخدامه فقط في المشكلات التي يتفوّق فيها—أي التي تحتوي على عددٍ قليل أو لا تحتوي على معالِم غير تافهة. ولحسن الحظ، تُحدَّد المعالِم قبل بدء البحث، ما يُتيح دمج كلا الإرشادين بسهولة: استعمل عدّ المعالِم في المجالات التي تمتلك معالِم واضحة، ودرجة الصِّلة في المجالات التي لا تمتلك سوى معالِم تافهة. في العمل المستقبلي، سنسعى لاستقصاء هذه الأفكار مع مجالات تخطيط أكثر تنوّعاً وتعقيداً.
مستودع الشيفرة والمواد التجريبية: https://github.com/relevancescoreplanning/relevance_score.git ↩