برنامهریزی خودکار
برنامهریزی خودکار شاخهای از هوش مصنوعی است که به محاسبه توالی اقداماتی میپردازد که با توجه به توصیف رسمی از اقدامات موجود، یک وضعیت اولیه جهان را به یک وضعیت هدف مطلوب تبدیل میکند.
Definition
برنامهریزی خودکار عبارت است از محاسبه یک برنامه — مجموعهای مرتب (یا تا حدی مرتب) از اقدامات — که با توجه به مدلی از چگونگی تغییر وضعیت جهان توسط هر اقدام، به طور اثباتپذیری به یک هدف از یک وضعیت اولیه دست مییابد.
Scope
این حوزه شامل نمایش مسائل برنامهریزی (حالات، اقدامات با پیششرطها و اثرات، اهداف) و الگوریتمهایی است که آنها را حل میکنند: برنامهریزی کلاسیک در دامنههای قطعی و کاملاً قابل مشاهده، روشهای گراف برنامهریزی و جستجوی اکتشافی، برنامهریزی شبکه وظایف سلسلهمراتبی، و گسترش آن به زمان، منابع و زمانبندی. این حوزه به فرمالیسمهای استانداردی مانند STRIPS و PDDL و پیچیدگی برنامهریزی میپردازد. برنامهریزی تحت عدم قطعیت احتمالی به استدلال تحت عدم قطعیت مرتبط است، و یادگیری مدلهای اقدام یا سیاستها از دادهها به زیرشاخه یادگیری ماشین تعلق دارد.
Sub-topics
Core questions
- چگونه اقدامات، حالات و اهداف به اندازه کافی فشرده نمایش داده میشوند تا دامنههای بزرگ را توصیف کنند؟
- چگونه مسئله برنامهریزی با وجود فضای حالت به طور نمایی بزرگ، به طور کارآمد جستجو میشود؟
- چگونه اکتشافیهای قابل قبول و آموزنده به طور خودکار از توصیف دامنه استخراج میشوند؟
- چگونه میتوان برنامهها را به صورت سلسلهمراتبی ساختاردهی کرد و چگونه محدودیتهای زمانی و منابع در آن گنجانده میشوند؟
Key concepts
- حالات، اقدامات، اهداف
- پیششرطها و اثرات
- STRIPS و PDDL
- جستجوی فضای حالت رو به جلو و رو به عقب
- گرافهای برنامهریزی
- اکتشافیهای مستقل از دامنه
- شبکههای وظایف سلسلهمراتبی
- برنامهریزی و زمانبندی زمانی
Key theories
- نمایش اقدام STRIPS
- فرمالیسم STRIPS اقدامات را با پیششرطها و اثرات افزودن/حذف بر روی مجموعهای از گزارهها توصیف میکند و یک نمایش فشرده و فاکتور شده ارائه میدهد که برنامهریزی را به یک جستجو در حالات نمادین تبدیل میکند تا یک شمارش از حالات صریح جهان.
- جستجوی اکتشافی مستقل از دامنه برای برنامهریزی
- برنامهریزهای مدرن، برنامهریزی را به عنوان جستجوی اکتشافی در نظر میگیرند و اکتشافیها را به طور خودکار از توصیف مسئله استخراج میکنند، به عنوان مثال با نادیده گرفتن اثرات حذف یا بهرهبرداری از ساختار علّی، که عملکرد عمومی قوی را امکانپذیر میسازد.
- برنامهریزی به عنوان سلسلهمراتبی از کلاسهای مسئله
- برنامهریزی طیفی از برنامهریزی قطعی کلاسیک تا انواع سلسلهمراتبی، زمانی و با محدودیت منابع را در بر میگیرد که هر یک دارای نمایشها و پیچیدگیهای مشخصی هستند و در نظریه استاندارد برنامهریزی خودکار سازماندهی شدهاند.
Clinical relevance
برنامهریزی خودکار در رباتیک و سیستمهای خودمختار، عملیات فضاپیما و مأموریت، لجستیک و زنجیره تأمین، تولید، و تولید بازی و روایت کاربرد دارد؛ برنامهریزهایی که از این تکنیکها مشتق شدهاند، فضاپیماهای خودمختار واقعی را کنترل کرده و جریانهای کاری پیچیده را هماهنگ میکنند.
History
برنامهریزی خودکار با STRIPS برای ربات Shakey در SRI حدود سال 1971 آغاز شد و برنامهریزی را به عنوان اثبات قضیه بر روی توصیفات اقدام چارچوببندی کرد. این حوزه از طریق برنامهریزی با ترتیب جزئی، پیشرفت Graphplan (1995)، و ظهور برنامهریزهای جستجوی اکتشافی سریع و مستقل از دامنه و استاندارد PDDL از اواخر دهه 1990 به بعد، که از طریق مسابقات بینالمللی برنامهریزی پیگیری شد، پیشرفت کرد.
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Malik Ghallab
- Dana Nau
- Paolo Traverso
- Malte Helmert
Related topics
Seminal works
- fikes1971
- ghallab2004
- helmert2006
Frequently asked questions
- برنامهریزی خودکار چه تفاوتی با جستجوی عمومی دارد؟
- برنامهریزی خودکار شکلی از جستجو است، اما بر اساس توصیفی اعلامی و فاکتور شده از اقدامات (پیششرطها و اثرات) کار میکند، نه یک تابع جانشین مبهم. این ساختار به برنامهریزها اجازه میدهد تا به طور خودکار اکتشافیها را استخراج کرده و در مورد اینکه کدام اقدامات مرتبط هستند استدلال کنند، کاری که جستجوی عمومی نمیتواند انجام دهد.
- PDDL چیست؟
- PDDL، زبان تعریف دامنه برنامهریزی، یک زبان استاندارد برای توصیف دامنهها و مسائل برنامهریزی است — اشیاء، محمولات، اقدامات، وضعیت اولیه و هدف. این زبان به برنامهریزهای مستقل از دامنه اجازه میدهد تا بر روی یک معیار مشترک مقایسه شوند، همانند مسابقات بینالمللی برنامهریزی.