گراف های برنامه ریزی در هوش مصنوعی

گراف های برنامه ریزی در هوش مصنوعی

استفاده از ساختمان داده خاصی به نام گراف برنامه ریزی در مسائل مربوط به هوش مصنوعی، میتواند تخمین بهتری از ابتکارات را ارائه دهد. این ابتکارات می توانند به هر تکنیک جست وجویی که تاکنون معرفی کرده ایم، اعمال شوند. از طرف دیگر با استفاده از الگوریتمی به نام GRAPHPLAN می توان در فضایی که به وسیله گراف برنامه ریزی ایجاد شد، جوابی را جست وجو کرد.

مسئله برنامه ریزی سوال میکند که آیا می توان با "حالت شروع" به هدف رسید یا خیر. فرض کنید درختی از تمام فعالیت های ممکن، از حالت شروع به حالت های پسین و حالت های پسین آنها و غیره داریم. اگر این درخت را بطور مناسبی شاخص گذاری کنیم، فقط با مراجعه به آن می توان فورا به این نوع پرسش ها پاسخ داد: "آیا میتوان از حالت G به حالت S₀ رسید؟"

گراف برنامه ریزی یک تقریب با اندازه چند جمله ای از این درخت است که سریعا میتواند ساخته شود. گراف برنامه ریزی نمی تواند بطور قطعی پاسخ دهد که آیا از S₀ قابل دسترس هست یا خیر، اما می تواند تخمین بزند که برای رسیدن به G باید از چند مرحله عبور کند. وقتی گزارش می شود که هدف غیرقابل دسترس است، این تخمین همیشه درست است و هرگز تعداد مراحل را بیش از حد تخمین نمی زند و در نتیجه یک ابتکار قابل قبول است.

گراف برنامه ریزی، گراف جهتداری است که بصورت چندین سطح سازمان دهی شده است. سطح S₀ برای حالت شروع، شامل گره هایی است که این گره ها، FLUENTهایی را نشان می دهند که در S₀ وجود دارند. سپس سطح A₀ شامل گره هایی برای هر فعالیت پایه ای است که ممکن است در S₀ قابل اجرا باشند، سپس سطوح S_i و بعد از آنها سطوح A_i وجود دارند تا به شرط پایان برسیم.

به بیان ساده  S_iشامل تمام لیترال هایی اس که می توانستند در زمان t نگهداری شوند و این به فعالیت هایی بستگی دارد که در مراحل زمانی قبلی اجرا شدند. A_i نیز شامل تمام فعالیت هایی است که پیش شرط های آنها می توانستند در زمان t ارضا شوند.

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

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

اکنون پیوندهای انحصاری متقابل را برای فعالیت ها و لیترال ها تعریف می کنیم. رابطه انحصاری متقابل در صورتی بین دو فعالیت در یک سطح خاص برقرار می شود که هر یک از سه شرط زیر برقرار باشند:

► اثرات ناسازگار. یک فعالیت، اثر فعالیت دیگر را نقیض می کند.

► تداخل . یکی از اثرات یک فعالیت، نقیض پیش شرط دیگری است.

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

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

گراف برنامه ریزی بر حسب اندازه مسئله برنامه ریزی، چندجمله ای است. برای یک مسئله ی برنامه ریزی با L لیترال و a فعالیت، هر S_i بیش از L گره و L² پیوند انحصار متقابل ندارد و هر A_i  بیش از a +L گره، (a + l)² پیوند انحصار متقابل و 2(aL + L)  پیش شرط و پیوندهای اثر ندارد. بنابراین اندازه گرافی با n سطح برابر با O( n(a + L)²) است. زمان لازم برای ساخت گراف، پیچیدگی مشابهی دارد.