معرفی الگوریتم GRAPHPLAN
معرفی الگوریتم GRAPHPLAN
در الگوریتم GRAPHPLAN میتوان یک برنامه ریزی را مستقیما از گراف برنامه ریزی، به جای استفاده از گراف برای به دست آوردن روش ابتکاری، استخراج کرد. الگوریتم GRAPHPLAN به طور مکرر با استفاده از EXPAND-GRAPH سطحی را به گراف برنامه ریزی استفاده میکند. وقتی تمام اهداف بدون انحصار متقابل در گراف نشان داده شدند، GRAPHPLAN تابع EXTRACT-SOLUTION را فراخوانی میکند تا یک برنامه ریزی را پیدا کند که مسئله را حل کند. اگر با شکست مواجه شود، سطح دیگری را بسط می دهد و دوباره تلاش می کند و وقتی دلیلی برای ادامه کار وجود نداشته باشد، با خطا خاتمه می یابد.
بعنوان یک مثال کاربردی، عملکرد الگوریتم GRAPHPLAN را در "مسئله لاستیک زاپاس" ردیابی میکنیم. در شروع الگوریتم، گراف برنامه ریزی را بصورت گرافی با یک سطح (S0) ایجاد میکند که حالت شروع را نشان میدهد. fluentهای مثبت حاصل از حالت شروع توصیف مسئله و همچنین fluentهای منفی مرتبط، ایجاد میشوند.
آثار فعالیت های پایدار برای تمام لیترال های S0 به سطح S1 اضافه می شوند. سپس EXPAND-GRAPH رابطه های انحصار متقابل را جست وجو می کند و آنها را به گراف برنامه ریزی اضافه میکند.
در این زمان وقتی به عقب برمی گردیم تا به ابتدای حلقه برسیم، تمام لیترال ها از هدف، در S2 نمای شداده می شوند و هیچ کدام با دیگری انحصار متقابل نیست. یعنی ممکن است جوابی وجود داشته باشد، و EXTRACT-SOLUTION سعی می کند آنرا بیابد. در اصل، EXTRACT-SOLUTION یک CSP بولی را حل میکند که متغیرهای آن فعالیت هایی در هر سطح هستند و مقادیر هر متغیر در داخل یا خارج برنامه ریزی وجود دارند.
از طرف دیگر EXTRACT-SOLUTION را می توان بعنوان مسئله جست وجوی عقبگرد تعریف کرد، که در آن هر حالت در جست وجو، شامل اشاره گری به یک سطح در گراف برنامه ریزی و مجموعه ای از اهداف تامین نشده است. این مسئله جست وجو را بصورت زیر تعریف می کنیم:
► حالت شروع ، آخرین سطح از گراف برنامه ریزی، یعنی Sn است که به همراه آن مجموعه ای از اهداف مسئله ی برنامه ریزی وجود دارد.
► فعالیت های موجود در حالتی در سطح Si ، انتخاب هر زیرمجموعه ای از فعالیت های موجود در Ai-1 است که متناقض نیستند و اثرات آنها، اهداف موجود در حالت را در برمیگیرد. حالت حاصل دارای Si-1 است و مجموعه اهداف آن بعنوان پیش شرط هایی برای مجموعه فعالیت های انتخاب شده است. منظور از متناقض نیستند، مجموعه ای از فعالیت هاست که هیچ کدام از دو فعالیت انحصار متقابل نیستند و پیش شرط های هیچ کدام از دو فعالیت نیز انحصار مقتابل نیستند.
► هدف رسیدن به حالتی در سطح S0 است که تمام اهداف تامین شوند.
► هزینه هر فعالیت یک است.
در موردی EXTRACT-SOLUTION برای یافتن جوابی برای مجموعه ای از اهداف در یک سطح خاص با شکست مواجه می شود، جفت (level , goals) را بعنوان یک جفت نامطلوب ثبت می کنیم، درست مثل آنچه در یادگیری محدودیت در SCPها انجام میشود.
هر وقت EXTRACT-SOLUTION دوباره با همان سطح و اهداف فراخوانی میشود، می توانیم جفت نامطلوب ثبت شده را بیابیم و به جای جست وجوی دوباره، فورا خطا را برگردانیم.
برنامه ریزی، PSPACE-complete است و ساختن گراف برنامه ریزی دارای زمان چندجمله ای است، لذا می توان نتیجه گرفت که استخراج جواب، در بدترین حالت تصمیم ناپذیر است. لذا به رهنمون های ابتکاری نیاز داریم تا در جست وجوی عقبگرد بتوانیم فعالیت هایی را انتخاب کنیم. یک روش، استفاده از الگوریتم حریصانه براساس هزینه سطح لیترال هاست.
برای هر مجموعه از اهداف به ترتیب زیر پیش می رویم:
1- ابتدا لیترالی با بیشترین هزینه سطح را انتخاب کنید.
2- برای رسیدن به ان لیترال، ابتدا فعالیتی با ساده ترین پیش شرط را انتخاب کنید. یعنی فعالیتی را انتخاب کنید که مجموع هزینه های سطح پیش شرط های آن کمترین هزینه باشد.
شبه کد الگوریتم GRAPHPLAN
function GRAPPLAN(problem) returns solution or failure
graph <-- INITIAL-PLANNING-GRAPH (problem)
goals <-- CONJUCTS(problem.GOAL)
nogoods <-- an empty hash table
for tl = 0 to ∞ do
if goals all non-mutex in St of graph then
solution <-- EXTRACT-SOLUTION (graph, goals, NUMLEVELS(graph) , nogoods)
if solution ≠ failure then return solution
if graph and nogoods have both leveled off then return failure
graph <-- EXPAND-GRAPH(graph, problem)
.gif)
