جستوجوی عقبگرد در فضای حالت

جستوجوی عقبگرد در فضای حالت

در جست وجوی عقبگرد از الگوریتم برنامه ریزی، از هدف شروع می کنیم و فعالیت ها را به طور منعکس اجرا میکنیم تا دنباله ای از مراحل را پیدا کنیم که ما را به حالت شروع می رساند. این روش، جست وجوی حالت های مرتبط نیز نامیده میشود، زیرا فقط فعالیت هایی را در نظر می گیریم که با هدف یا حالت فعلی مربوط می شوند. همانند جست وجوی حالت باور، مجموعه ای از حالت های مرتبط وجود دارند که در هر مرحله باید در نظر گرفته شوند (نه فقط یک حالت).

از هدف شروع می کنیم، که ترکیب عطفی لیترال هایی است که مجموعه ای از حالت ها را توصیف میکند. بطور کلی جست وجوی عقبگرد فقط وقتی کار می کند که بدانیم چگونه از یک توصیف حالت به توصیف حالت قبلی برسیم.

برای مثال، جست وجوی عقبگرد برای جواب مسئله n وزیر، سخت است، زیرا روش آسانی برای توصیف حالت هایی وجود ندارد که یک حرکت دور از هدف هستند. خوشبختانه نمایش PDDL طوری طراحی شد که انجام فعالیت های عقبگرد را آسان می سازد (اگر دامنه ای بتواند در PDDL بیان شود،آنگاه میتوان جست وجوی عقبگرد را روی آن انجام داد). با توجه به هدف پایه ای g و فعالیت های پایه ای a، عقبگرد از g روی a توصیف حالت g’ را به دست میدهد که به صورت زیر تعریف میشود:

g’ = ( g – ADD(a) ) U Precond(a).

یعنی، آثاری که توسط این فعالیت اضافه شدند، لازم نبود که قبلا true باشند و در نتیجه پیش شرط ها باید از قبل برقرار بوده باشند، وگرنه این فعالیت نمی توانست اجرا شود. توجه کنید که DEL(a) در این فرمول ظاهر نمی شود. علتش این است که تا زمانی که می دانیم fluentها در DEL(a) پس از انجام این فعالیت، دیگر true نیستند، نمی دانیم که آیا قبلا true بودند یا خیر و در نتیجه نمی توان چیزی راجع به آنها گفت.

برای استفاده از امتیاز کامل جست وجوی عقبگرد، لازم است علاوه بر حالت ها و فعالیت های پایه ای، حالت ها و فعالیت های نمونه سازی نشده جزیی را نیز اداره کنیم.

نکته آخر تصمیم گیری درباره فعالیت هایی است که کاندیدایی برای برای عبور از آنها هستیم. در جهت پیشرو، فعالیت هایی را انتخاب میکنیم که قابل اجرا بودند (آن فعالیت هایی که می توانستند مرحله بعدی در برنامه ریزی باشند). در جست وجوی عقبگرد، فعالیت های مرتبط را در نظر می گیریم (آن فعالیت هایی که می توانستند آخرین مرحله در برنامه ریزی ای باشند که منجر به حالت هدف فعلی می شود).

برای اینکه فعالیتی مرتبط با هدفی باشد، بدیهی است که باید در هدف سهم داشته باشد: حداقل یکی از آثار فعالیت (مثبت یا منفی) باید از عنصری از هدف یکسان سازی شود. آنچه که چندان روشن نیست، این است که فعالیت نباید اثری داشته باشد که عنصری از هدف را نقیض کند. اکنون اگر هدف A ʌ B ʌ C باشد و اثر فعالیت برابر با A ʌ B ʌ ¬ C باشد، آنگاه یک حس گفتگو وجود دارد که در آن این فعالیت خیلی مرتبط با هدف است. اما از نظر تکنیکی که در اینجا تعریف شد، مرتبط نیست، زیرا این فعالیت نمی توانست مرحله پایانی یک جواب باشد (همیشه حداقل به یک مرحله بیشتر نیاز داریم تا به C برسیم).

برای اغلب مسئله ها جست وجوی عقبگرد ضریب انشعاب را نسبت به جست وجوی پیشرو، کوچک تر نگه می دارد. به هر حال با توجه به این حقیقت که جست وجوی عقبگرد به جای استفاده از تک تک حالتها از مجموعه ای از حالت ها استفاده میکند، پیدا کردن ابتکارات خوب دشوار است. به همین دلیل اغلب سیستم های فعلی از جست وجوی پیشرو استفاده می کنند.