latex
المعالم هي حقائق أو أفعال تظهر في جميع الحلول الصالحة لأي مشكلة تخطيط، وقد استُخدمت بنجاح لاشتقاق دوال إرشادية توجه البحث عن خطة. في هذا العمل نستكشف توسيع هذا المفهوم بتعريف جديد لمسماة "درجة الصلة"، التي تقيس مدى تكرار ظهور حقائق أو أفعال معينة في معظم الخطط ولكن ليس في جميعها لتحقيق هدف معيّن. نصف هنا طريقة لحساب هذه الدرجة واستعمالها كأساس لدالة إرشادية أثناء البحث. نقارن بين أداء منهجنا ومنهج تخطيط قائم على المعالم يُعدّ من أحدث الأساليب، باستخدام مجموعة من المشكلات القياسية. ونجد أنه بينما يتفوّق الإرشاد المعتمد على المعالم الأصلية في المجالات التي تحتوي معالم محددة بوضوح، تحقّق درجة الصلة تحسينات كبيرة في المجالات التي تفتقر إلى معالم غير تافهة.
يُعَدُّ استخدام الدوال الإرشادية لتوجيه البحث وتقليص مساحة البحث مكوناً أساسياً في أنظمة التخطيط الحديثة. وتوجد أدبيات متينة حول الأساليب التي تُوظّف فيها هذه الدوال لتحسين الكفاءة الحسابية في إيجاد الخطط. فالدالة الإرشادية الملائمة التي تُحتسب بسرعة تجعل البحث الإرشادي في فضاء الحالات أكثر كفاءة بكثير من طرق البحث غير الموجهة. إحدى الدوال الإرشادية الناجحة في تخطيط المهام هي عد "المعالم البارزة" غير المنفذة من الحالة الحالية (Zhu2003, Hoffmann2004, Richter2010, Keyder2010)، حيث يُعرَّف المعلم البارز كحقيقة أو فعل أو عبارة منطقية على الحقائق والأفعال توجد في جميع الحلول الصالحة (أي تسلسلات الأفعال) لمشكلة التخطيط. يؤدي ذلك إلى تفضيل الأفعال التي هي معالم بارزة أو تحقق واحداً منها. ومع ذلك، فإن حساب جميع المعالم البارزة لمشكلة تخطيط ما عملية مكلفة؛ وهو أمر معروف بأنه كاملة الفضاء الكلي (Porteous2001a). لذا تحدد الأنظمة التي تحسب المعالم البارزة مجموعة فرعية من المعالم الرئيسية غالباً عبر تبسيط مشكلة التخطيط (Keyder2010)، لكن تكلفة الحساب تظل مرتفعة.
أحد القيود الشائعة في الغالب على المنهجيات التي تحسب وتستعين بالمعالم كدالة إرشادية هو وجوب وجود معالم غير تافهة في مجالات التخطيط قيد الدراسة. ففي كثير من المجالات المعقدة التي توفر مسارات متعددة لتحقيق الهدف، قد تكون المعالم البسيطة (حقائق منفردة) الموجودة تافهة—أي موجودة في مواصفات الهدف أو صحيحة بالفعل في الحالة الابتدائية. ورغم أن الصيغ المنطقية المعقدة قد تؤدي دور معالم بارزة، يصعُب احتسابها واستخدامها كدالة إرشادية. يتجنب المنهج الموصوف هنا هذا القيد بحساب "درجة الصلة"، التي تقيّم أيضاً القيمة الإرشادية للحقائق (أو الأفعال) التي تظهر في كثير من الخطط الصالحة لكنها ليست ضرورية في جميعها. الفرضية الأساسية أننا بحوزة هذه المعلومات الإضافية ننطلق في بحث أكثر كفاءة عن حل صالح لمشكلة التخطيط المعطاة. كنموذج أساسي، نعتمد مخطط لاما (Richter2010)، الذي يجمع عد المعالم البارزة مع المصطلح الأمامي للتكلفة (Hoffmann2001)، ويستخرج أقصر خطة بواسطة بحث \(A^*\) الموزون في إطار استرخاء الحذف. وقد ظل هذا المنهج متصدراً مسابقات التخطيط لأكثر من عقد.
المساهمة الرئيسية لهذه الورقة هي تعريف ووصف دالة إرشادية جديدة، "درجة الصلة" (\(h_{\Xi}\)). تقوم هذه الدالة بتعميم مفهوم المعلم البارز—الذي يجب أن يتحقق في كل خطة صالحة (تحت استرخاء الحذف)—إلى مقياس للصلة يقيس مدى ظهور الحقائق أو الأفعال ضمن الخطط (تحت نفس شروط الاسترخاء). يوضح الشكل [fig:illustration] المعلومات التي نهدف إلى التقاطها عبر درجة الصلة، وعلاقتها بالمعالم البارزة. وللمقارنة مع مخطط لاما الأصلي، نركز هنا على الحقائق باعتبارها كيانات شبيهة بالمعالم. ثم نورّح، عبر تقييم تجريبي على مجموعة من مشكلات التخطيط القياسية، أنه بينما يتفوّق الإرشاد المعتمد على المعالم البارزة في المشكلات المزودة بمعالم بارزة واضحة، يحقق نهجنا المعتمد على درجات الصلة تحسناً ملموساً في المشكلات التي تفتقد معالم بارزة غير تافهة.
يُنظَّم باقي البحث على النحو التالي. يستعرض القسم [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 نحو حلٍّ لمشكلات يضعف فيها عد المعالم. لكن ذلك على حساب تكلفة حسابية أعلى وأداء أضعف في المشكلات القياسية. لذا يُوصى باستخدامه فقط في المشكلات التي يتفوق فيها—أي التي تحتوي على عدد قليل أو لا تحتوي على معالم غير تافهة. ولحسن الحظ، تُحدَّد المعالم قبل بدء البحث، مما يتيح دمج كلا الإرشادين بسهولة: استخدم عد المعالم في المجالات التي تمتلك معالم واضحة، ودرجة الصلة في المجالات التي لا تمتلك سوى معالم تافهة. في العمل المستقبلي، سنسعى لاستقصاء هذه الأفكار مع مجالات تخطيط أكثر تنوعاً وتعقيداً.