برنامهریزی کلاسیک و STRIPS
برنامهریزی کلاسیک به مسئله یافتن دنبالهای از اقدامات برای رسیدن به یک هدف در یک محیط قطعی، کاملاً قابل مشاهده و ایستا میپردازد، با استفاده از نمایش فاکتور شده اقدامات به سبک STRIPS بر اساس پیششرطها و اثرات.
Definition
برنامهریزی کلاسیک به دنبال دنبالهای از اقدامات قطعی است که یک حالت اولیه کاملاً شناخته شده را به حالتی تبدیل میکند که هدف را برآورده سازد، جایی که هر اقدام با شرایطی که برای اعمال آن باید برقرار باشند و تغییراتی که ایجاد میکند، توصیف میشود.
Scope
این موضوع مدل برنامهریزی کلاسیک و مفروضات آن (اقدامات قطعی، قابلیت مشاهده کامل، یک عامل واحد، زمان اتمی)، نمایشهای STRIPS و ADL/PDDL از حالتها و اقدامات، روشهای اساسی حل مسئله جستجوی فضای حالت رو به جلو (پیشروی) و رو به عقب (پسروی) و برنامهریزی با ترتیب جزئی، و پیچیدگی محاسباتی برنامهریزی گزارهای را پوشش میدهد. راهنمایی اکتشافی و گرافهای برنامهریزی در موضوع مرتبط مورد بررسی قرار میگیرند و انواع غیرقطعی یا احتمالی خارج از محدوده هستند.
Core questions
- چه مفروضاتی مدل برنامهریزی کلاسیک را تعریف میکنند و چه زمانی مناسب هستند؟
- چگونه نمایش STRIPS یک حالت را به گزارهها و یک اقدام را به پیششرطها و اثرات افزودن/حذف تقسیم میکند؟
- جستجوی پیشروی و پسروی به عنوان استراتژیهای برنامهریزی چه تفاوتی دارند؟
- پیچیدگی محاسباتی برنامهریزی کلاسیک به طور کلی چقدر دشوار است؟
Key concepts
- مدل قطعی، کاملاً قابل مشاهده
- پیششرطها و اثرات STRIPS
- لیستهای افزودن و حذف
- PDDL و ADL
- جستجوی پیشروی (رو به جلو)
- جستجوی پسروی (رو به عقب)
- برنامهریزی با ترتیب جزئی
- پیچیدگی وجود برنامه
Key theories
- نمایش STRIPS
- STRIPS جهان را به عنوان مجموعهای از گزارههای صحیح و هر اقدام را با یک لیست پیششرط به علاوه لیستهای افزودن و حذف توصیف میکند، بنابراین اعمال یک اقدام به سادگی گزارهها را اضافه و حذف میکند؛ این مدل فاکتور شده اساس تقریباً تمام برنامهریزان کلاسیک است.
- جستجوی پیشروی و پسروی
- برنامههای کلاسیک را میتوان با جستجوی رو به جلو از حالت اولیه با اعمال اقدامات قابل اجرا (پیشروی) یا رو به عقب از هدف با محاسبه زیرهدفهای پسروی شده (پسروی) یافت، با برنامهریزی با ترتیب جزئی که تعهد به یک ترتیب کلی اقدام را کاهش میدهد.
- پیچیدگی برنامهریزی
- تصمیمگیری در مورد اینکه آیا یک برنامه STRIPS گزارهای وجود دارد، به طور کلی PSPACE-کامل است، که به طور رسمی توضیح میدهد چرا برنامهریزی دشوار است و روشهای اکتشافی و ساختاری را برای عملی کردن آن تحریک میکند.
Clinical relevance
نمایشهای برنامهریزی کلاسیک رابط مشترک برای برنامهریزی وظایف ربات، مونتاژ خودکار و لجستیک، و هر کاربردی هستند که در آن اقدامات قطعی باید به ترتیب برای رسیدن به یک هدف انجام شوند؛ برنامهریزان کلاسیک مبتنی بر PDDL، ابزارهای اصلی این حوزه و مسابقات بینالمللی برنامهریزی هستند.
History
STRIPS در حدود سال 1971 در SRI برای کنترل ربات Shakey توسعه یافت و مدل اقدام پیششرط/اثر را معرفی کرد که برنامهریزی کلاسیک را تعریف میکند. برنامهریزی با ترتیب جزئی در دهههای 1970-80 به بلوغ رسید، بایلندر در سال 1994 کامل بودن PSPACE برنامهریزی گزارهای را اثبات کرد، و استاندارد PDDL بعدها معیارهای این حوزه را یکپارچه ساخت.
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Tom Bylander
- Earl D. Sacerdoti
Related topics
Seminal works
- fikes1971
- bylander1994
Frequently asked questions
- مفروضات برنامهریزی کلاسیک چیست؟
- برنامهریزی کلاسیک یک عامل واحد را فرض میکند که در یک محیط قطعی، کاملاً قابل مشاهده و ایستا عمل میکند، با اقداماتی که زمان واحدی را میبرند و یک حالت اولیه کاملاً شناخته شده. کاهش هر یک از این مفروضات، به عنوان مثال اجازه دادن به عدم قطعیت یا همزمانی، منجر به مسائل برنامهریزی غنیتری فراتر از مدل کلاسیک میشود.
- لیست افزودن و لیست حذف STRIPS به چه معناست؟
- هنگامی که یک اقدام STRIPS اعمال میشود، گزارههای موجود در لیست افزودن آن صحیح میشوند و گزارههای موجود در لیست حذف آن نادرست میشوند؛ سایر گزارهها بدون تغییر باقی میمانند. این قانون بهروزرسانی ساده چیزی است که STRIPS را به یک نمایش فشرده و از نظر محاسباتی مناسب از نحوه تغییر جهان توسط اقدامات تبدیل میکند.