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].
تم وصف المعالم كوسيلة للتوجيه البدائي في (Porteous2001a) وتم تطويرها أكثر في (Hoffmann2004)، كامتداد لترتيب الأهداف. سعوا لإيجاد وترتيب الحقائق التي يجب تحقيقها في أي خطة صالحة. تم التعامل مع هذا الترتيب الجزئي للمعالم كسلسلة من الأهداف الفرعية لتقسيم مشكلة التخطيط إلى مشكلات فرعية. عادة ما يتم العثور على المعالم باستخدام رسم بياني للتخطيط المرن (RPG) (Hoffmann2001)، الذي يؤدي تحليل الوصول تحت شروط الاسترخاء الحذفي ويتطلب خطوات متعددة للتحقق من أن المعالم وترتيبها سليم.
استخدم العديد من الباحثين المعالم لتوجيه المخططين البحثيين القائمين على البيانات الإرشادية (Zhu2003,Helmert2006,Richter2008). وقد قام آخرون بتوسيع هذه الفكرة لإيجاد خطط مثلى من حيث التكلفة وبدأوا باستخدام الأفعال والصيغ الاقتراحية للحقائق كمعالم محتملة (Keyder2008,Karpas2009,Richter2010). يستخدم معظمهم عداد المعالم البياني، الذي يُفترض أن كل معلم لم يتم الوصول إليه بعد سيكلف فعلاً واحداً. ثم يُعطى تقدير المسافة إلى الهدف بعدد المعالم المتبقية للعثور عليها. كان هناك بعض العمل على البيانات الإرشادية التي تحافظ على تكاليف الأفعال، وتأخذ في الاعتبار الأفعال التي يمكن أن تحقق عدة معالم في آن واحد (Helmert2009,Karpas2009). وقد استكشفت هذه الأوراق وغيرها طرقاً أكثر كفاءة لتحديد العديد من المعالم (Keyder2010).
استكشف الباحثون طرقاً مختلفة لحساب واستخدام المعالم. مثال على ذلك هو ترجمة الرسوم البيانية للتخطيط المرن إلى رسوم بيانية AND/OR حيث تعتبر المعالم حلولاً فريدة وقصوى يتم حسابها باستخدام طرق بيلمان-فورد (Keyder2010). ينطوي تطبيق الاسترخاء الحذفي على مشكلة تخطيط على فقدان المعلومات، ويمكن أن يؤدي إلى أفعال أو تسلسلات أفعال مستحيلة في المشكلة الأصلية. إحدى الطرق تتمثل في التخلص من الشروط السلبية والآثار مع الحفاظ على المعلومات التي احتوتها (Haslum2009). من خلال النظر في أزواج (\(m=2\))، أو ثلاثيات (\(m=3\)) أو تراكيب أكبر من الحقائق، يتم الحفاظ على متطلب تحقيقها في وقت واحد، مما يؤدي إلى مشكلة أكبر \( \Pi^m \) خالية من الشروط السلبية أو الآثار. قام آخرون بالبناء على هذه الفكرة (Keyder2010). نظراً لأن حجم المشكلة ينمو بشكل أسي مع \(m\)، وإدخال حقائق مركبة جديدة في المجال يطرح تحديات أخرى، فإن الطرق التي تستخدم المعالم غالباً ما تفضل قبول القيود المفروضة بواسطة الاسترخاء الحذفي.
لا يزال هناك عمل جارٍ على حساب واستخدام المعالم. يشمل ذلك حساب المعالم باستخدام تعريفات مجال التخطيط غير المؤسسة أو "المرفوعة"، مما يسمح بتمثيل بعض تعقيدات المعالم المنفصلة في نطاق التأسيسات الممكنة (Wichlacz2022). كما يشمل استخدام المعلومات الترتيبية لحساب بيانات إرشادية جديدة، مما يحسن دقتها (Buchner2021). كما يتم استخدام البيانات الإرشادية المستندة إلى المعالم في العديد من المجالات ذات الصلة مثل التعرف على الأهداف (Pereira2017,Vered2018) والتخطيط المشروط (Maliah2018,Segovia-Aguas2022).
نبدأ بتعريف الرموز وبعض المفاهيم المستخدمة في هذه الورقة، يليه تعريف لمقياس الاستدلال للأهمية الذي اقترحناه.
تُعرّف مشكلة التخطيط الكلاسيكية بالثنائي (GNT2): \[\Pi = \langle F, A, I, G\rangle\] حيث \(F\) هي مجموعة محدودة من المقولات الأرضية التي تمثل الحقائق؛ \(A\) هي مجموعة محدودة من الأفعال؛ \(I\subseteq F\) هي مجموعة الحقائق الصحيحة في الحالة الابتدائية؛ و\(G \subseteq F\) هي مجموعة الحقائق التي تمثل الأهداف. الحالة \(\sigma\) هي مجموعة من الحقائق التي تكون صحيحة في وقت معين. لكل فعل \(a \in A\) هناك شروط مسبقة \(pre(a)\) وتأثيرات \(ef\!f(a)\)، وكل منهما مقسم إلى مجموعات من الحقائق الإيجابية والسلبية: \( pre^+(a), pre^-(a), ef\!f^+(a), ef\!f^-(a) \). إذا كانت الشروط المسبقة الإيجابية (السلبية) لفعل ما صحيحة (خاطئة) في حالة معينة، فإنه يمكن تطبيقه في تلك الحالة: \[Applicable(a, \sigma) \iff \sigma \models pre^+(a)\cap\neg pre^-(a)\] عند تطبيق فعل على حالة يمكن تطبيقه فيها، فإن الحالة الناتجة تُعطى بواسطة: \[Result(a, \sigma) \models \sigma \cup ef\!f^+(a) \setminus ef\!f^-(a)\] تكون سلسلة الأفعال \([a_1 ... a_n]\) قابلة للتطبيق في حالة إذا كان كل فعل قابل للتطبيق في الحالة الناتجة عن السلسلة السابقة من الأفعال، أي \( Applicable(a_1, \sigma), Applicable(a_2, Result(a_1, \sigma))\) وهكذا. نتيجة تطبيق سلسلة الأفعال على حالة يمكن تطبيقها هي نتيجة تطبيق كل فعل في تلك السلسلة، أي \( Result([a_1 ... a_n], \sigma) = Result(a_n, Result(a_{n-1}, ...Result(a_1, \sigma))\).
خطة \( \pi^\Pi\) لمشكلة \( \Pi = \langle F, A, I, G\rangle\) هي سلسلة من الأفعال \([a_1 ... a_n]\) التي تكون قابلة للتطبيق في \(I\) وتؤدي إلى حالة تكون فيها جميع الحقائق في \(G\) صحيحة، أي \(Result(\pi^\Pi, I) \models G\).
المعلم هو تعريف لصيغة اقتراحية من الحقائق التي تكون صحيحة في نقطة ما خلال تنفيذ جميع الخطط الصالحة. بسبب صعوبة تحديد المعالم الاختيارية، تستخدم العديد من أنظمة التخطيط، بما في ذلك LAMA (Richter2010)، المعالم الحقيقية فقط. هذه هي الحقائق الفردية التي يجب أن تكون صحيحة في نقطة ما خلال تنفيذ جميع الخطط الصالحة. كل حقيقة في الهدف والحالة الأولية هي معلم، لكنها ذات فائدة قليلة للمخطط؛ وتعرف هذه بالمعالم السطحية. الحقائق التي يجب أن تكون صحيحة في نقطة ما غير البداية أو نهاية تنفيذ الخطة تعتبر غير سطحية.
نقترح في هذه الورقة درجة أهمية تنطبق على كل من البناء على الحقائق والإجراءات المشابهة للمعالم. ومع ذلك، لتسهيل الاستخدام والمقارنة مع LAMA، نحد من مناقشتنا في هذه الورقة على الحقائق.
يمكن تبسيط مشكلة التخطيط الكلاسيكية لحساب الإرشادات التي ستساعد في حل المشكلة الأصلية (Bonet2001, Hoffmann2001). إحدى هذه التبسيطات هي استرخاء الحذف، الذي يزيل جميع الشروط السلبية والآثار السلبية من جميع الأفعال. تُستخدم تبسيطة أخرى غالباً لمجالات التخطيط التي تحتوي على أهداف متعددة. على وجه التحديد، يتم تعديل المجال بإضافة فعل \(achieveGoal\) الذي له تأثير إيجابي واحد \(ef\!f^+(achieveGoal) = \{success\}\)، وأهداف المشكلة كشروط مسبقة \(pre^+(achieveGoal) = G\). ثم يُستخدم \(success\) كهدف لحساب الإرشادات، مما يسمح بالنظر في جميع الأهداف معاً.
الشجرة هي تمثيل قياسي لمجال (وتغيرات في المجال) لمشكلة تخطيط. تتكون الشجرة من عقد \(\underline{n}\) وحواف \(e\). عقدة \(\underline{n} = \langle l, E \rangle\) تتكون من تسمية \( label(\underline{n}) = l \in F\cup A\)، والتي تشير إلى حقيقة \(f\) أو فعل \(a\)، ومجموعة من الحواف \(E\). حافة \( e = (\underline{n} \rightarrow \underline{c})\) تربط عقدة أصل \(\underline{n}\) بعقدة فرع \(\underline{c}\).
بالنظر إلى حافة \(e = (\underline{n} \rightarrow \underline{c})\)، فإن الدالة \(parent(\underline{c})\) تعطي \(\underline{n}\). الدالة \(children(\underline{n})\) تعطي مجموعة من العقد بحيث لكل عقدة \(c\)، \( parent(\underline{c}) = \underline{n}\). جذر الشجرة هو العقدة الوحيدة بدون أصل، أي \(parent(\underline{r}) = None\).
مشكلة التخطيط المرتخية للحذف \(\Pi = \langle F, A, I, G\rangle\) تحدد شجرة \(T_\Pi\). عقدة \(\underline{r}\) هي جذر \(T_\Pi\) ولها \(label (\underline{r}) = achieveGoal\). عقدة فعل \(\underline{a}\)، أي عقدة تسميتها فعل، لها أطفال تسمياتهم هي شروطها المسبقة \(f \in pre(label(\underline{a}))\). عقدة حقيقة \(\underline{f}\) لها أطفال تسمياتهم هي أفعال \(a\) بحيث \(label(\underline{f}) \in ef\!f(a)\).
الدالة \(L(l)\) تربط تسمية \(l\) بعقد الشجرة التي لها هذه التسمية: \[\begin{aligned} \nonumber L(l) &= \{ \forall \underline{n} : label(\underline{n}) = l\} \\ \intertext{% مسار عقدة هو تسلسل بديل من عقد الحقائق والأفعال الذي يتم إنشاؤه بإضافة أصل العقدة الحالية حتى يتم الوصول إلى الجذر: } \nonumber T_{\Pi}^{path}(\underline{n}) &= [\underline{n}, parent(\underline{n}), ..., \underline{r}] \\ \intertext{% النسل لعقدة $ \underline{n} $ هم جميع العقد التي لها $ \underline{n} $ في مسارها: } \nonumber T_{\Pi}^{desc}(\underline{n}) &= \{\forall \underline{d}: \underline{n} \in T_{\Pi}^{path}(\underline{d}) \}\end{aligned}\] يتم استثناء الأفعال من أطفال عقدة حقيقة \( \underline{f} \) إذا ظهرت أي شروط مسبقة لذلك الفعل كتسميات على أي عقدة في \( path(\underline{f}) \). هذا يمنع الدورات، التي من شأنها أن تمثل متطلبات غير قابلة للتحقيق.
الهدف من المقياس الاستدلالي درجة الأهمية هو تقدير مدى تكرار حقيقة ما يجب أن تصبح صحيحة في توزيع معين للخطط الجزئية. نستخدم سلوك وكيل غير حتمي (NDA) لتعريف هذا التوزيع. شجرة فرعية \( S_{\Pi} \) من \( T_{\Pi} \)، تتكون من مجموعة فرعية من العقد في \( T_{\Pi} \) ومساراتها، مختارة وفقاً للخوارزمية [alg:subtree]. تطبيق تسلسل الإجراءات الممثلة بمسار كل عقدة ورقية داخل \( S_{\Pi} \) سيؤدي إلى تحقيق الهدف. وبالتالي، قد يُعتبر \( S_{\Pi} \) خطة جزئية تحت شروط الاسترخاء الحذفي.
تفسيرنا، الذي نتابعه في هذه الورقة، هو أن احتمالية عالية لالتقاطها من قبل مثل هذا الوكيل غير الحتمي تشير إلى أن حقيقة ما لها أهمية كبيرة لتحقيق الهدف. الحقائق التي تظهر في جميع الخطط الجزئية التي يمكن أن يلتقطها يجب أن تكون في جميع الخطط، وبالتالي هي معالم بارزة.
لتمثيل درجة الصلة \( \Xi(l) \) احتمال أن يتم أخذ عينة من عقدة بتسمية \( l \) بواسطة NDA: \[\begin{aligned} \nonumber \Xi(l) &= P \left( \exists \underline{l} \in S_{\Pi} | label(\underline{l}) = l \right)\end{aligned}\] لتمثيل درجة الصلة المحلية \( \Xi(l, \underline{n}) \) احتمال أن يتم أخذ عينة من عقدة بتسمية \( l \) بواسطة NDA، بناءً على أن العقدة \( \underline{n} \) (وبالتالي \( S_{\Pi}^{path}(\underline{n}) \)) قد تم أخذ عينة منها. \[\begin{aligned} \label{eqn:localrel} \Xi(l, \underline{n}) &= P \left( \exists \underline{l} \in S_{\Pi}^{desc}(\underline{n}) | label(\underline{l}) = l \right) \end{aligned}\] إذا كانت \( label(\underline{n}) \) حقيقة، فإن أي من أطفالها قد يتم أخذ عينة منه، وقد يكون لديهم عقدة بتسمية \( l \) بين نسلهم: \[\begin{aligned} \nonumber \shortintertext{$ \texttt{if } label(n) \in F: $ } \nonumber \Xi(l, \underline{n}) &= \sum_{\underline{c} \in children(\underline{n})} P \left( \underline{c} \in S_{\Pi}^{desc}(\underline{n}) \right) \times \Xi(l, \underline{c}) \end{aligned}\] يختار NDA طفلاً واحداً من عقدة حقيقة بالتساوي، وهذا يعني: \[\begin{aligned} \label{eqn:XiFactBasic} \Xi(l, \underline{n}) &= \sum_{\underline{c} \in children(\underline{n})} \frac { \Xi(l, \underline{c}) } { \left| children(\underline{n}) \right| }\end{aligned}\] إذا كانت \( label(\underline{n}) \) فعلاً، فسيتم أخذ عينة من جميع أطفالها. وبالتالي فإن \(\Xi(l, \underline{n})\) هي 1 ناقص احتمال ألا يكون لأي من نسلهم المأخوذ عينة منه تسمية \(l\): \[\begin{aligned} \nonumber \shortintertext{$ \texttt{if } label(n) \in A: $ } \label{eqn:XiActBasic} \Xi(l, \underline{n}) &= 1 - \prod_{\underline{c} \in children(\underline{n})} \left( 1 - \Xi(l, \underline{c}) \right)\end{aligned}\]
احتمال أن يتم اختيار العقدة \(\underline{n}\) بواسطة NDA، \(\xi(\underline{n}) = P(\underline{n} \in S_{\Pi})\) يعتمد على عدد الخيارات البديلة التي كان يمكن اتخاذها بدلاً من تلك التي تصل إلى تلك العقدة. سيتم دائماً اختيار جذر الشجرة: \[\begin{aligned} \nonumber \xi(\underline{r}) &= \textnormal{1}\end{aligned}\] بين الفعل وشروطه المسبقة، لا يوجد لدى NDA خيارات لاتخاذها، لذا يتم نقل \( \xi \) دون تغيير: \[\begin{aligned} \nonumber \xi(\underline{f}) &= \xi(parent(\underline{f}))\end{aligned}\] يختار NDA فعلاً واحداً يمكن أن يوفر حقيقة من مجموعة الأفعال التي تشكل \(children(f)\): \[\begin{aligned} \label{eqn:CCAct} \xi(\underline{a}) &= \frac{\xi(parent(\underline{a}))}{\left| children(parent(\underline{a})) \right|}\end{aligned}\] حيث \(\underline{r}\)، \(\underline{f}\)، \(\underline{a}\) هي عقد الجذر، الحقيقة، والفعل على التوالي.
أدنى سلف مشترك (LCA) لعقدتين \(\underline{n}\) و \(\underline{m}\) هو أدنى عقدة في الشجرة التي تكون سلفاً لكلتا العقدتين: \[% \label{eqn:LCAdef} \nonumber LCA(\underline{n},\underline{m}) = \underset{\underline{i} \in T^{path}_{\Pi}(\underline{n}) \cap T^{path}_{\Pi}(\underline{m})}{argmax}(|T^{path}_{\Pi}(\underline{i})|)\] هذه العملية تجميعية ويمكن تعميمها على أي عدد من العقد.
بعد ذلك، نصف منهجنا لحساب مقياس الأهمية المقترح. نبدأ ببعض الأساسيات. سيتم توفير الكود المستخدم لتنفيذ واختبار هذا على الرابط التالي 1.
تسمح لنا المعادلة [eqn:localrel] بأن نعتبر الأحفاد لعقدة معينة بشكل مستقل عن الفروع الأخرى الناشئة من أسلافها. يمكن تطبيق هذا بشكل تكراري لحساب مقياس الأهمية المحلي لجذر الشجرة: \(\Xi(l, \underline{r}) = \Xi(l)\).
العبارات التالية صحيحة بوضوح، وتسمح لنا بتجاهل مقياس الأهمية المحلي \(\Xi(l, \underline{n})\) لأي عقدة بدون أحفاد لهم \(label(\underline{n}) = l\): \[\begin{aligned} \shortintertext{ $\texttt{إذا } label(\underline{n}) = l $ } \nonumber &\implies &\Xi(l, \underline{n}) =& 1 \shortintertext{ $ \texttt{إذا } T^{desc}_{\Pi}(\underline{n}) \cap L(l) = \emptyset $ } \nonumber &\implies &\Xi(l, \underline{n}) =& 0\end{aligned}\] نظراً لعقدة \( \underline{n} \) وأحد أحفادها بحيث أن جميع العقد التي تحمل العلامة \(l\) وهي حفيدة لإحداها هي أيضاً حفيدة للأخرى: \[\begin{aligned} \shortintertext{$ \texttt{إذا } T^{desc}_{\Pi}(\underline{n}) \cap L(l) = T^{desc}_{\Pi}(\underline{d}) \cap L(l) $ } \nonumber &\implies &\Xi(l, \underline{n}) =& P\left( \underline{d} \in S_{\Pi}^{desc}(\underline{n}) \right) &\times \Xi(l, \underline{d}) \\ \nonumber && =& P\left( \underline{d} \in S_{\Pi} | \underline{n} \in S_{\Pi} \right) &\times \Xi(l, \underline{d}) \\ \label{eqn:NodeToDesc} && =& \frac{\xi(\underline{d})}{\xi(\underline{n})} &\times \Xi(l, \underline{d})\end{aligned}\]
الآن، لنفكر في المعادلة [eqn:XiFactBasic] عندما يكون لكل طفل \(\underline{c}\) لعقدة حقيقة \(\underline{f}\) سليل واحد \(\underline{d}\) بتسمية \(label(\underline{d}) = l\): \[\begin{aligned} \nonumber \Xi(l, \underline{f}) =& \sum_{ \underline{c} \in children(\underline{f}) } \frac { \Xi(l, \underline{c}) } { \left| children(\underline{f}) \right| }\end{aligned}\] باستخدام المعادلة [eqn:CCAct]، يمكن كتابتها كالتالي: \[\begin{aligned} \nonumber =& \sum_{ \underline{c} \in children(\underline{f}) } \frac { \Xi(l, \underline{c}) } { \frac { \xi(\underline{f}) } { \xi(\underline{c}) } } \\ \nonumber =& \sum_{\underline{c} \in children(\underline{f})} \frac {\Xi(l, \underline{c}) \times \xi(\underline{c})} {\xi(\underline{f})}\end{aligned}\] بعد ذلك، باستخدام المعادلة [eqn:NodeToDesc]، يمكن إعادة كتابتها كالتالي: \[\begin{aligned} \nonumber =& \sum_{ \substack { \underline{c} \in children(\underline{f}) \\ \underline{l}~\models T_{\Pi}^{desc}(\underline{c})~\cap~L(l) } } \frac { \frac { \xi(\underline{l}) } { \xi(\underline{c}) } \times \Xi(l, \underline{l}) \times \xi(\underline{c}) } { \xi(\underline{f}) } \\ \nonumber =& \sum_{ \underline{l}~\in~T_{\Pi}^{desc}(\underline{f})~\cap~L(l) } \frac { \xi(\underline{l}) } { \xi(\underline{f}) } \\ \label{eqn:XiFact} =& \frac { 1 } { \xi(\underline{f}) } \sum_{ \underline{l}~\in~T_{\Pi}^{desc}(\underline{f})~\cap~L(l) } \xi(\underline{l})\end{aligned}\] إذا كان جميع السلالة لعقدة \( \underline{d} \in T_{\Pi}^{desc}(\underline{n}) \) إما بتسمية \(label(\underline{d}) = l\)، أو هي عقد حقائق التي تنطبق عليها المعادلة [eqn:XiFact]، يمكن تكرار هذه العملية، مما يؤدي إلى إلغاء مزيد من الحدود \( \frac{1}{\xi(\underline{c})} \). إذا كان بعض العقد بتسمية \(label(\underline{d_i}) = l\) لها \( LCA(\underline{d_1},\underline{d_2}) = \underline{a} \) التي هي فعل (أي، aLCA؛ انظر أدناه)، فإن المعادلة [eqn:NodeToDesc] لا تنطبق بين \( \underline{c_i} \) و \( \underline{d_i}\). ستنطبق بين \( \underline{a_i} \) و \( \underline{c_i} \)، ولكن يجب حساب \( \Xi(l,~\underline{a}) \) وفقاً للمعادلة [eqn:XiActBasic]: \[\begin{aligned} \nonumber \Xi(l, \underline{f}) =& \frac { 1 } { \xi(\underline{f}) } \sum_{ \underline{l} \in fLCAs } \xi(\underline{l}) + \sum_{ \underline{a} \in aLCAs } \frac { \xi(\underline{a}) } { \xi(\underline{f}) } \times \Xi(l, \underline{a}) \\ \label{eqn:XiAnyFact} =& \frac { 1 } { \xi(\underline{f}) } \left( \sum_{ \underline{l} \in fLCAs } \xi(\underline{l}) \right. + \left. \sum_{ \underline{a} \in aLCAs } \xi(\underline{a}) \times \Xi(l, \underline{a}) \right)\end{aligned}\] حيث:
aLCAs - أدنى جد مشترك للأفعال: أي عقدة فعل هي الجد المشترك الأدنى لأي مجموعة من \( L(l) \cap T_{\Pi}^{desc}(\underline{f})\)
fLCAs - أدنى جد مشترك للحقائق: أي عقدة بتسمية \( l \) التي تتفرع مساراتها عند عقد الحقائق:
\(
fLCAs =
\left\{
\forall \underline{l} \in L(l) :
LCA(\underline{l}_i,\underline{l}_j) \in F \cap T_{\Pi}^{desc}(\underline{f})
\right\}
\)
يمكن حساب \(\Xi(l)\) من \(L(l)\) بتحديد aLCAs، حساب \(\Xi(l,\underline{c})\) لأطفالهم المباشرين بالمعادلة [eqn:XiAnyFact]، ودمجهم وفقاً للمعادلة [eqn:XiActBasic].
للمشكلات العملية، \( T_{\Pi} \) قد تكون كبيرة جداً، مما يحول دون تمثيلها بالكامل. يمكن العثور على حد أدنى لـ \( \Xi(l) \) باستخدام شجرة مستكشفة جزئياً \( \overline{T_{\Pi}} \). العقد التي لـ \( \xi(\underline{n}) \) قيمة صغيرة تساهم بأقل في \( \Xi(l) \)، وتوجد بعيداً عن الجذر، مما يؤدي إلى تقارب هذا الحد الأدنى بسرعة نحو الأعلى كلما تم استكشاف المنطقة القريبة من الجذر. نستخدم الخوارزمية [alg:exploration] لأخذ عينات من \( \overline{T_{\Pi}} \) من \( T_{\Pi} \). عتبة الاستكشاف \( \rho \) هي تقدير لنسبة كمية المعلومات الموجودة في الحدود مقارنة بالشجرة المستكشفة. وجدنا أن أداء \( h_{\Xi} \) كمعيار ليس حساساً للتغييرات الصغيرة في قيمة \( \rho \). ما لم يذكر خلاف ذلك، نستخدم \( \rho = 0.2 \) في بقية هذه الورقة. يضمن الشرط الأول في الحلقة الخارجية أثناء الخوارزمية [alg:exploration] أن أخذ العينات لا ينتهي مبكراً بسبب تقلب مصطلحاته عندما تكون صغيرة.
لاحظ أن هذا الإجراء في أخذ العينات يختلف عن أخذ العينات الذي يؤديه NDA الافتراضي. كلا إجراءي أخذ العينات يختاران الإجراءات التي تلبي حقيقة حدودية عشوائياً، لكن NDA يستكشف جميع الحقائق التي هي شروط مسبقة لهذه الإجراءات، بينما يختار إجراء أخذ العينات في الخوارزمية [alg:exploration] شرطاً مسبقاً واحداً. هذا يضمن أن \( T_{\Pi} \) يتم أخذ عينات منها بتنوع أكبر دون التركيز كثيراً على عدد قليل من العينات القريبة من الجذر التي تتفرع على نطاق واسع، مما يؤدي إلى تجاهل أشقائها.
لقد تم إجراء الكثير من الأبحاث لإيجاد أقل سلف مشترك لزوج من العقد في شجرة. تمت ترجمة هذه المشكلة إلى مشكلة حساب استعلام الحد الأدنى للمدى (Fischer2006). تعقيد هذه العملية هو \( O(h) \) لمعالجة الشجرة مسبقاً، حيث \(h\) هو ارتفاع الشجرة، ثم \( O(1) \) لكل استعلام عن زوج من العقد. وبالتالي، ستكلف هذه الطريقة \( O(h + n^2) \) لإيجاد أقل سلف مشترك لكل زوج من العقد، حيث \(n\) هو عدد العقد التي نريد إيجاد أقل سلف مشترك لها.
بدلاً من هذا الإجراء المعتمد، يمكننا الاستفادة من حقيقة أن العديد من أقل الأسلاف المشتركة سيتم مشاركتها بين أزواج متعددة؛ حيث يوجد في أقصى الحالات \(hn\) أقل سلف مشترك فريد. نقوم أولاً بفرز العقد حسب مساراتها (بتعقيد \(O(hn\log(n)) \) ). لا يهم الترتيب، المهم فقط أن العقد التي لها نفس المسار حتى مسافة معينة من الهدف تكون في مجموعة متجاورة، لذا يتم معاملة العقد كرُموز في تسلسل (أي المسار الذي يبدأ عند الهدف) ويتم فرزها أبجدياً حسب تسمياتها. يتم التنقل على طول المسارات المفروزة (بأسوأ تعقيد حالة \( O(hn) \))، والتحقق من الاختلافات بين العقد في المسارات (وما إذا كانت عقد فعلية أم لا) المتجاورة في ترتيب الفرز ينتج قائمة مرتبة من أقل الأسلاف المشتركة الفعلية (aLCAs). يتم حساب مجموعات من aLCAs مرة واحدة لكل حقيقة، ثم يتم تصفيتها بواسطة \(\sigma\) عندما يحتاج إلى حساب \(h_{\Xi}(\sigma)\).
في أي حالة معينة \( \sigma \)، جميع الحقائق في الحالة \( f \in \sigma \) صحيحة ولا تحتاج إلى تحقيق من قبل المخطط. يجب ألا يأخذ مقياس الصلة المعتمد على الحالة لتسمية معينة، \( \Xi_{\sigma}(l) \)، في الاعتبار أجزاء من \( \overline{T_{\Pi}} \) التي تحقق هذه الحقائق على أنها ذات صلة. يمثل مقياس الصلة المطبق على حالة \( \Xi_{\sigma}(l) \) احتمال أن يتم اختيار عقدة بتسمية \( l \) بواسطة NDA، إذا توقفت عند العقد التي هي صحيحة في الحالة \( \sigma \) (لأنها لا تحتاج إلى إجراء لتزويدها). يتم حسابه وفقاً للمعادلات [eqn:XiAnyFact] و [eqn:XiActBasic] المطبقة على الشجرة المقطوعة عند العقد بتسميات في \( \sigma \): \[\nonumber \overline{T_{\Pi}/\sigma} = \overline{T_{\Pi}} \left/ \bigcup_{\substack{ \forall \underline{f} \in L(f) \\ \forall f \in \sigma }} T^{desc}_{\Pi}(\underline{f}) \right.\] يتم العثور على هذا لجميع الحقائق، ويتم حساب المنهجية لحالة كما يلي: \[\nonumber h_{\Xi}(\sigma) = \sum_{l \in F} \Xi_{\sigma}(l)\] بما أن منهجية مقياس الصلة هي مجموع الاحتمالات، \(h_{\Xi}(\sigma) \in \mathbf{R}\). من ناحية أخرى، يتطلب نظام التخطيط LAMA أن تعود المنهجيات بقيمة صحيحة. للسماح باستخدام ومقارنة مع LAMA، يتم تقريب \(h_{\Xi}(\sigma)\) إلى العدد الصحيح الأقرب، مع فقدان بعض المعلومات في العملية.
لقد قمنا بتقييم التجارب التالية:
يُعتبر مقياس درجة الصلة S1 أبطأ من مقياس عد المعالم البارزة S2 في حل مشكلات التخطيط القياسية، ولكنه قادر على إيجاد خطة في معظم الأوقات؛ و
يحسن مقياس درجة الصلة S1 بشكل كبير القدرة على إيجاد الخطط مقارنة بمقياس عد المعالم البارزة S2 في المجالات التي لا تحتوي على معالم بارزة غير تافهة.
تستند الفرضية H1 إلى الفهم القائل بأنه عندما يتم استكشاف الشجرة بالكامل (أي \( \overline{T_{\Pi}} = T_{\Pi} \))، ستحصل المعالم البارزة على درجة صلة \( \Xi(l) = 1 \) والحقائق التي لا تظهر في أي خطط صالحة ستحصل على درجة صلة \( \Xi(l) = 0 \). بمعنى آخر، يوفر استخدام مقياس درجة الصلة الوصول إلى جميع المعلومات المتاحة لخوارزمية التخطيط باستخدام مقياس عد المعالم البارزة، مع الأخذ في الاعتبار أيضاً معلومات إضافية حول الحقائق ذات الصلة ولكن غير الأساسية، مما سيؤدي إلى حساب إضافي. الفرضية H2 صحيحة لأنه، بينما لن يكون لدى مقياس عد المعالم البارزة S2 أي معالم بارزة غير تافهة لتوجيه بحثه، فإن مقياس درجة الصلة S1 سيظل يمتلك تدرجاً إرشادياً معلوماتياً للمتابعة، مع إمكانية قيادته إلى حلول (أفضل) لمشكلات التخطيط.
تم تقييم هذه الفرضيات باستخدام بنية مخطط لاما (Richter2010)، باستخدام إما مقياس درجة الصلة S1 أو مقياس عد المعالم البارزة الحالي S2؛ استخدام S2 كان معيارنا الأساسي. يستخدم لاما إجراء بحث \(A^*\) الموزون (باستخدام الوزن الافتراضي = 10) مع أحد المقياسين (S1 أو S2). تم تقييد جميع البحوث بحد أقصى للذاكرة العشوائية يبلغ 8GB. تمت مقارنة أدائهم في حل جميع المشكلات الـ 674 المحددة في مجلد الأمثلة لمستودع HSP2 (Bonet2001) وفقاً للمقاييس الأدائية التالية:
نسبة المشكلات التي تم حلها/لم يتم حلها؛
الوقت المستغرق في البحث عن خطة قبل العثور على واحدة؛
عدد الحالات الموسعة قبل العثور على خطة؛ و
طول الخطة الموجودة.
هذه مقاييس معترف بها جيداً لتقييم أداء هذه المشكلات التخطيطية.
لتقييم H2، قمنا بإنشاء مواصفات PDDL جديدة للمجالات التي لا تحتوي على معالم باستثناء الحقائق الموجودة في الهدف والحالة الأولية. تم تحقيق ذلك من خلال دمج زوج من المشكلات، \( \pi_1 \)، \( \pi_2 \) التي تم حلها باستمرار باستخدام كلتا الخطتين بطريقة تمنع تفاعلهما. هذا يضمن أن كل مشكلة جديدة يمكن حلها بواسطة 2 خطتين على الأقل لا تتداخل فيها الحقائق أو الأفعال المعنية.
لتوليد \( merged(\Pi_1, \Pi_2) \)، تم إضافة تسمية فريدة لكل مشكلة إلى جميع العناصر المحددة بالمجال أو المشكلة (الأنواع، الثوابت، المفاهيم، الأفعال، الأشياء) في كل مشكلة. هذا يضمن عدم مشاركة أي عنصر اسماً مع العناصر في المشكلة التي يتم دمجها معها. إذا لم تُستخدم مشكلة الأنواع، يتم تطبيق نوع جديد يتكون فقط من تسميتها الفريدة على جميع الثوابت والأشياء داخلها. ثم تتألف المشكلة المُدمجة الجديدة من جميع العناصر المسماة من مشكلتي المصدر، مع التعديلات التالية:
يتم تعريف فعلين جديدين:
\( a_1: pre(a_1) = G_1; ef\!f(a_1) = \{winning\}\)
\( a_2: pre(a_2) = G_2; ef\!f(a_2) = \{winning\}\).
تحتوي المشكلة المدمجة على هدف واحد:
\( G_{merged} = \{winning\}\)
تم إنشاء ما مجموعه 500 مشكلة بهذا الإجراء من خلال اختيار زوج عشوائي من المشكلات من مجموعة تلك التي تم حلها بشكل فردي بواسطة S1 و S2. البرنامج المستخدم لهذا غير قادر على التعامل مع PDDL الذي، على الرغم من أنه صالح، لا يتبع بعض الاتفاقيات. كلما حدث ذلك، تم اختيار زوج جديد عشوائياً للتقييم التجريبي.
من بين 674 مشكلة تخطيط في مستودع أمثلة HSP2، يُظهر الجدول [tab:standardsolvefail] عدد المشكلات التي تم حلها باستخدام كل من الاستراتيجيات (أي، S1، S2) مع مخطط LAMA. لاحظ أن S2 قدم أداء أفضل ولكن S1 تمكن من إيجاد خطط لمعظم المشكلات التي حلها S2.
تم حلها بواسطة | S1 | S2 | كلاهما | لا أحد |
---|---|---|---|---|
عدد المشكلات | 273 | 370 | 261 | 147 |
للمشكلات التي تم حلها بواسطة كلتا الاستراتيجيتين:
المتوسط النسبي بين أوقات البحث (ث) لـ \(\textbf{S1}/\textbf{S2} = 951.34 \pm 3303.31\)؛
المتوسط النسبي بين عدد الحالات الموسعة لـ \(\textbf{S1}/\textbf{S2} = 6.86 \pm 29.53\)؛ و
المتوسط النسبي بين طول الخطة الموجودة لـ \(\textbf{S1}/\textbf{S2} = 1.13 \pm 0.29\).
هذه النتائج كانت ضمن التوقعات وتدعم بقوة الفرضية H1.
من بين 500 مشكلة تم توليدها وفقاً للإجراء الموضح في القسم [sec:lmfgeneration]، يلخص الجدول [tab:mergedsolvefail] عدد المشكلات التي تم حلها باستخدام كل من الاستراتيجيات (S1, S2) باستخدام مخطط LAMA. لاحظ أن الأداء كان أفضل باستخدام S1 مقارنة بـ S2.
تم الحل بواسطة | S1 | S2 | كلاهما | لا أحد |
---|---|---|---|---|
عدد المشكلات | 335 | 122 | 108 | 151 |
تُظهر النتائج أن S1 قد تم قياسه على أنه أفضل بكثير من S2 وفقاً لمقاييس الأداء M2، M3، و M4 لغالبية هذه المشكلات المدمجة. S2 فشل في حل معظم هذه الفئة من المشكلات. بالنسبة للمشكلات التي تم حلها بواسطة كلتا الاستراتيجيتين:
المتوسط النسبي بين أوقات البحث (ث) لـ \(\textbf{S1}/\textbf{S2} = 123.08 \pm 295.25\)؛
المتوسط النسبي بين عدد الحالات الموسعة لـ \(\textbf{S1}/\textbf{S2} = 0.64 \pm 1.77\)؛ و
المتوسط النسبي بين طول الخطة الموجودة لـ \(\textbf{S1}/\textbf{S2} = 2.17 \pm 2.40\).
هذه النتائج تدعم بقوة فرضية H2.
المخطط لا يتأثر بالتغييرات الصغيرة في \(\rho\). يظهر أن استكشاف المزيد من الشجرة (أي التوقف عندما يتم الوصول إلى نسبة أقل بين المعلومات في الحدود و\( \overline{T_{\Pi}} \)) لا يحسن من قدرة \( h_{\Xi} \) على حل المشكلات. استخدام ذاكرة الوصول العشوائي الإضافية، يجعل من الصعب على المخطط حل المشكلات ضمن حدود ذاكرة الوصول العشوائي الخاصة بهم.
توفر النتائج التجريبية بعض الرؤى المثيرة للاهتمام. حساب درجة الصلة لشجرة مستكشفة بالكامل (\( \overline{T_{\Pi}} = T_{\Pi} \)) على أنها عدد الحقائق التي تعتبر معالم للخطط المنطلقة من \( \sigma \) (حيث \( \Xi_\sigma(l) = 1\))، مضافاً إليها الصلة المحسوبة لحقائق أخرى. في حالة مشكلات التخطيط القياسية، بالإضافة إلى استغراق وقت أطول لحساب واستخدام هذه المعلومات الإضافية، يبدو أن استخدام الإرشاد المقترح من قبلنا يعيق قدرة المخطط على إيجاد خطة ضمن حدود الموارد المفروضة. تفسيرنا لذلك هو أن الحقائق ذات الصلة ولكن ليست ضرورية، التي يكون لها \( \Xi_\sigma(l) \) عالياً ولكن أقل من 1، توجه المخطط نحو خطط متنافسة محتملة. هذا "التشتت" يؤدي إلى إيجاد خطط تتضمن عناصر من خطط جزئية أخرى كان من الممكن أن يجدها، مما يؤدي إلى خطط أطول. في المشكلات التي يكون فيها تداخل أقل بين الخطط المحتملة، تكون النسبة بين طول الخطط (عندما يجد كل من S1 و S2 خطة) أكبر. الخطط التي وجدها S1 في المشكلات الخالية من المعالم تحتوي على أفعال من كلتا المشكلتين المصدر، بينما الخطط التي وجدها S2 لا تفعل ذلك. المعلومات المشتتة تزيد أيضاً من تكلفة الاستكشاف (M2 و M3)، مما يؤدي إلى زيادة عدد المشكلات التي لا يمكن حلها ضمن حدود الموارد (RAM).
بالنسبة للمشكلات الخالية من المعالم، يمكن لـ S2 فقط أن يخبر أن خطة جزئية قد تكون جيدة عندما يجد أحد حقائق الهدف. حتى ذلك الحين، يبحث على سطح مسطح، مما يزيد المسافة من الحالة الأولية في جميع الاتجاهات. بالمقابل، S1، أي الإرشاد المقترح لدرجة الصلة، قادر على تسلق سطح معلوماتي يوجهه نحو الخطط المحتملة. نظراً لأن S1 يكافئ المخطط لإيجاد حقائق ذات صلة بخطط بديلة، ولكن قد تكون منفصلة، فإنه يميل إلى تضمين بعض الأفعال في الخطة النهائية التي لم تسهم في تحقيق الهدف. نعتقد أن هذا يفسر سبب إيجاده لخطط أطول من S2، خاصة في المشكلات المعروفة بأنها قابلة للحل بخطط منفصلة. هذا هو منتج غير مقصود من الطريقة التي تم بها إنشاء هذه المجالات وقد لا يكون الحال في المشكلات التي تم إنشاؤها بطرق أخرى.
بشكل عام، الملاحظة الرئيسية هي أن إرشاد درجة الصلة الخاص بنا قادر على توجيه مخطط LAMA نحو حل فئة من مشكلات التخطيط التي يكون فيها عد المعالم غير فعال. يأتي ذلك على حساب كونه أكثر تكلفة للحساب، وأداء أسوأ في المشكلات القياسية. لذلك، يمكن التوصية به فقط لفئة المشكلات التي يتفوق فيها؛ تلك التي لديها عدد قليل أو لا توجد معالم غير تافهة. لاحظ، مع ذلك، أن المعالم يتم تحديدها قبل أن تبدأ إجراءات بحث الخطة، مما يعني أن هناك طريقة سهلة وطبيعية للاستفادة من كلا الإرشادين: اختر عد المعالم في المشكلات التي تحتوي على معالم محددة جيداً، واستخدم إرشاد درجة الصلة الخاص بنا للمشكلات التي تحتوي فقط على معالم تافهة. في الأعمال المستقبلية، نأمل في استكشاف هذه الرؤى بشكل أكبر مع مشكلات تخطيط إضافية (وأكثر تعقيداً).