برنامه ریزی به عنوان قیاس منطقی مرتبه اول

برنامه ریزی به عنوان قیاس منطقی مرتبه اول

 

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

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

 

حساب موقعیت بصورت زیر کار میکند:

► حالت اولیه، موقعیت نام دارد. اگر s  یک موقعیت و a یک فعالیت باشد، آنگاه RESULT(s , a) نیز یک موقعیت است. موقعیت های دیگری وجود ندارند. بنابراین هر موقعیت متناظر با دنباله ای از فعالیت ها است. موقعیت را می توان به عنوان نتیجه ی اجرای فعالیت ها دانست، اما توجه کنید که دو موقعیت فقط در صورتی یکسان هستند که شروع و فعالیت های آنها یکسان باشند:

RESULT (s , a) = RESULT (s’ , a’) ↔ s = s’ ᴧ a = a’

 

►  تابع با رابطه ای که می تواند از موقعیتی به موقعیت دیگر تغییر کند، fluent نام دارد. بنا به قرارداد، موقعیت s همیشه آخرین آرگومان fluent است.

 

► هر یک از پیش شرط های فعالیت، با یک اصل احتمالات توصیف می شود که مشخص می کند فعالیت چه زمانی می تواند انجام شود . اصل احتمال به شکل φ(s) → Poss(a , s) است که φ(s) فرمولی شامل s است که پیش شرط ها را توصیف می کند.

 

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

 

► به اصل فعالیت یکتا نیاز داریم، به طوری که عامل بتواند استنتاج کند که مثلا a ≠ Release(g) است. برای هر جفت متمایز از اسامی فعالیت ها مثل Ai و Aj یک اصل موضوعی داریم که می گوید این فعالیت ها متفاوتند:

Ai(x , …) ≠ Aj(y, …)

و برای هر نام فعالیت Ai یک اصل موضوعی داریم  که می گوید دو کاربرد آن نام فعالیت، برابرند اگر و فقط اگر تمام آرگومان های آنها برابر باشند:

Ai(x1 , … , xn) = Aj(y1 , … , yn) ↔ x1 = y1 ᴧ … ᴧ xn = yn

 

► جواب در صورتی یک موقعیت است  (و در نتیجه دنباله ای از فعالیت هاست) که هدف را تامین کند.

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