گرافهای برنامهریزی و اکتشافیها
گرافهای برنامهریزی و اکتشافیهای مستقل از دامنه، تکنیکهایی هستند که با تحلیل فشرده دسترسیپذیری و تخمین خودکار فاصله از یک حالت تا هدف، برنامهریزی کلاسیک را سریع کردند.
Definition
گراف برنامهریزی یک ساختار لایهای است که سطوح گزاره و عمل را با محدودیتهای mutex در هم میآمیزد تا دسترسیپذیری را تخمین بزند؛ اکتشافیهای برنامهریزی توابعی هستند که اغلب از چنین ساختارهایی یا از مسائل آرامسازی شده با حذف محاسبه میشوند و هزینه رسیدن به هدف از یک حالت را تخمین میزنند.
Scope
این موضوع ساختار دادهای گراف برنامهریزی معرفی شده توسط Graphplan را پوشش میدهد، شامل سطوح گزارهها و اقدامات و روابط انحصار متقابل (mutex) که نشان میدهد کدام حقایق و اقدامات نمیتوانند همزمان رخ دهند، و خانواده اکتشافیهای مستقل از دامنه که از مسائل آرامسازی شده (به ویژه نادیده گرفتن اثرات حذف) مشتق شدهاند و برنامهریزان جستجوی اکتشافی مدرن را هدایت میکنند. این موضوع به چگونگی محاسبه و استفاده از اطلاعات دسترسیپذیری برای هدایت جستجو میپردازد. مدل برنامهریزی کلاسیک زیربنایی در موضوع مرتبط پوشش داده شده است.
Core questions
- چگونه یک گراف برنامهریزی، گزارهها و اقدامات قابل دسترس را سطح به سطح نمایش میدهد؟
- روابط mutex چیست و چگونه ناسازگاری بین حقایق و اقدامات را نشان میدهند؟
- چگونه از آرامسازی حذف برای استخراج اکتشافیهای برنامهریزی قابل قبول یا آموزنده استفاده میشود؟
- چگونه این اکتشافیها برنامهریزی را به جستجوی اکتشافی کارآمد تبدیل میکنند؟
Key concepts
- گراف برنامهریزی
- سطوح گزاره و عمل
- انحصار متقابل (mutex)
- Graphplan
- آرامسازی حذف
- اکتشافیهای h-max و h-add
- اکتشافی FF و برنامههای آرامسازی شده
- جستجوی پیشرو اکتشافی
Key theories
- گراف برنامهریزی و Graphplan
- Graphplan یک گراف برنامهریزی میسازد که به طور فشرده نشان میدهد کدام گزارهها و اقدامات در هر سطح قابل دسترسی هستند و کدام جفتها متقابلاً انحصاری هستند، سپس با جستجوی معکوس در این ساختار، یک برنامه را استخراج میکند و سرعت برنامهریزی را به طور چشمگیری افزایش میدهد.
- اکتشافیهای آرامسازی حذف
- نادیده گرفتن اثرات حذف اقدامات، یک مسئله برنامهریزی آرامسازی شده را به وجود میآورد که حل آن بسیار آسانتر است؛ هزینه حل این آرامسازی، اکتشافیهای آموزنده و اغلب قابل قبول (مانند h-max و h-add و اکتشافی FF) را فراهم میکند که جستجوی پیشرو را هدایت میکنند.
- برنامهریزی جستجوی اکتشافی
- برنامهریزان کلاسیک پیشرفته، اکتشافیهای خودکار مشتق شده را با جستجوی بهترین-اول یا حریصانه و بهبودهایی مانند عملگرهای ترجیحی ترکیب میکنند و عملکرد کلی قوی را در دامنههای مختلف به دست میآورند.
Clinical relevance
گرافهای برنامهریزی و اکتشافیهای آرامسازی حذف، فناوری اصلی برنامهریزان برنده مسابقات هستند که در رباتیک، لجستیک و کنترل خودمختار استفاده میشوند، جایی که به برنامهریزان مستقل از دامنه اجازه میدهند مسائل بزرگ را به سرعت و بدون راهنمایی جستجوی دستی حل کنند.
History
Graphplan بلوم و فورست (1995، نسخه مجله 1997) گراف برنامهریزی را معرفی کرد و سرعت برنامهریزی را متحول ساخت. اواخر دهه 1990 و 2000 شاهد ظهور اکتشافیهای آرامسازی حذف بود، با برنامهریز FF (Hoffmann و Nebel، 2001) و سپس Fast Downward (Helmert، 2006) که جستجوی پیشرو اکتشافی را به عنوان رویکرد غالب تثبیت کردند.
Key figures
- Avrim L. Blum
- Merrick L. Furst
- Jörg Hoffmann
- Bernhard Nebel
- Malte Helmert
Related topics
Seminal works
- blum1997
- hoffmann2001
Frequently asked questions
- mutex در گراف برنامهریزی چیست؟
- رابطه mutex (انحصار متقابل) دو گزاره یا دو عمل را نشان میدهد که نمیتوانند هر دو در یک سطح برقرار باشند یا اعمال شوند، به عنوان مثال به این دلیل که یک عمل پیششرط دیگری را حذف میکند. Mutexها گراف برنامهریزی را به تقریب دقیقتری از دسترسیپذیری واقعی تبدیل میکنند.
- چرا نادیده گرفتن اثرات حذف یک اکتشافی مفید ارائه میدهد؟
- بدون اثرات حذف، دستیابی به یک هدف هرگز دیگری را از بین نمیبرد، بنابراین مسئله آرامسازی شده بسیار آسانتر حل میشود و هرگز دشوارتر از مسئله اصلی نیست. بنابراین، هزینه برنامه آرامسازی شده یک کران پایین یا تخمین آگاهانه از هزینه واقعی است که آن را به یک اکتشافی مؤثر برای هدایت جستجو تبدیل میکند.