برنامه ریزی های با ترتیب جزیی در AI
برنامه ریزی های با ترتیب جزیی در AI
روش های برنامه ریزی که تاکنون در پست های قبلی مان مطرح کردیم، برنامه ریزی هایی کاملا مرتب را می سازند که شامل دنباله های اکیدا خطی از فعالیت ها هستند. این نمایش مستقل بودن بسیاری از زیرمسئله ها را نادیده می گیرد.
جوابی برای مسئله حمل بار هوایی، شامل دنباله ای با ترتیب کلی از فعالیت ها است، ولی اگر 30 بسته در یک هواپیما در یک فرودگاه بارگیری شوند و 50 بسته در هواپیمای دیگر در فرودگاه دیگری بارگیری شود، بعید است که با 80 فعالیت بارکردن، به ترتیب اکیدا خطی برسیم، این دو مجموعه از فعالیت ها باید مستقل از هم باشند.
روش دیگر این است که برنامه ریزی ها بصورت ساختارهایی با ترتیب جزیی نمایش داده شوند: هر برنامه ریزی، مجموعه ای از فعالیت ها و مجموعه ای از محدودیت ها به شکل Before(ai , ai) است که می گوید یک فعالیت قبل از فعالیت دیگر رخ می دهد.
برنامه ریزی هایی با ترتیب جزیی، با جست وجو در فضای برنامه ریزی ها، به جای جست وجو در فضای حالت ایجاد می شوند. با یک برنامه ریزی خالی شروع می کنیم که فقط شامل "حالت شروع" و هدف است و هیچ فعالیتی بین آنها وجود ندارد. سپس رویه جست وجو، به دنبال یک نقص یا عیب در این برنامه ریزی می گردد و سعی می کند با اضافه کردن فعالیتی به برنامه ریزی، آن را درست کند (یا اگر نتواند برنامه ریزی را درست کند، جست وجو به عقب انجام می شود و سعی می کند کار دیگری انجام می دهد).
نقص، هر چیزی است که مانع از این می شود که برنامه ریزی جزیی به یک جواب تبدیل شود. برای مثال، یک نقص در برنامه ریزی خالی این است که هیچ فعالیتی به At(Spare , Axle) دست پیدا نمی کند. یک روش برطرف کردن این نقص این است که فعالیت PutOn(Spare , axle) به آن اضافه شود. البته این کار باعث می شود که نقص های دیگری وارد شوند: پیش شرط های فعالیت جدید دست یافتنی نیستند.
رویه جست وجو، عمل اضافه کردن به برنامه ریزی را ادامه می دهد (در صورت نیاز به عقب برمیگردد) تا تمام نقص ها برطرف شوند. در هر مرحله کمترین تعهد را برای برطرف کردن نقص انجام می دهیم.
در دهه های 1980 و 1990 "برنامه ریزی با ترتیب جزیی" بعنوان بهترین روش اداره کردن مسئله های برنامه ریزی با زیرمسئله های مستقل مطرح بودند – سرانجام این روش تنها روشی بود که انشعاب های مستقل برنامه ریزی را صریحا نمایش می داد. از طرف دیگر عیبش این است که حالت ها را در مدل گذار حالت، صریحا نمایش می دهد.
به این ترتیب پیچیدگی های محاسباتی به وجود می آید. تا آنها اجازه داد زیرمسئله های مستقل را که برنامه ریزی ترتیب جزیی برای آنها طراحی شده بود، به خوبی شناسایی کنند. در نتیجه برنامه ریزان ترتیب جزیی، در مسئله های برنامه ریزی کلاسیک کاملا خودکار، رقابتی عمل نمی کنند.
اما برنامه ریزی ترتیب جزیی، در این حوزه بعنوان یک روش مهم باقی می ماند. برای بعضی از کارهای ویژه، مثل زمانبندی عملیات ها، برنامه ریزی ترتیب جزیی همراه با روش های ابتکاری خاص دامنه، انتخاب مناسبی است. بسیاری از سیستم ها، از کتابخانه هایی از برنامه ریزی های سطح بالا استفاده می کنند.
برنامه ریزی ترتیب جزیی، در دامنه هایی نیز به کار می رود که در انها، درک برنامه ریزی ها برای انسان ها مهم است. برنامه ریزی های عملیاتی برای فضاپیما و گردش گر مریخ توسط برنامه ریزان ترتیب جزیی تولید می شوند و قبل از فرستادن آنها به این وسایل جهت اجرا، توسط انسان ها تست می شود. روش پالایش برنامه ریزی پی بردن به عملکرد الکوریتم های برنامه ریزی را آسان تر می سازد و بررسی می کند که درست هستند.
