برنامه ریزی خودکار
| بخشی از یک مجموعه درباره |
| هوش مصنوعی |
|---|
|
رویکردها |
|
واژه‌نامه |
برنامه ریزی خودکار (به انگلیسی: Automated planning and scheduling)، یا به زبان ساده تر برنامه ریزی هوشمند [۱]، شاخه ای از هوش مصنوعی است که در آن به تحقق راهبردها یا دنباله اعمالی پرداخته می شود که به طور معمول توسط کارگزار هوشمند، ربات خودمختار، و وسایل نقلیه بدون سرنشین (unmanned vehicles) اجرا می شوند. برخلاف مسایل کلاسیک سامانه کنترل و طبقه بندی آماری، راه حل ها پیچیده اند و باید در فضای چندبعدی کشف و بهینه سازی شوند. برنامه ریزی به تئوری تصمیم (decision theory) نیز مرتبط است. در محیط های شناخته شده با مدل های موجود، برنامه ریزی به صورت آفلاین قابل انجام است. راه حل ها قبل از اجرا قابل یافتن و ارزیابی می باشند. در محیط های پویای ناشناس، راهبردها نیاز به اصلاح آنلاین دارند. مدل ها و سیاست ها باید تطبیق داده شوند. راه حل ها معمولا متوسل به روندهای تکراری آزمون و خطا می شوند، که به طور معمول در هوش مصنوعی استفاده می شوند. این روندها شامل برنامه نویسی پویا، یادگیری تقویتی و بهینه سازی ترکیبیاتی می باشند. به زبان های مورد استفاده برای توصیف برنامه ریزی، زبان عملی گفته می شود.
نمای کلی[ویرایش]
با داشتن توصیفی از حالت های اولیه ممکن از محیط، اهداف دلخواه، و مجموعه ای از اعمال ممکن، مساله ی برنامه ریزی عبارت است از ترکیب برنامه ای که (در صورت اجرا روی هر کدام از حالات اولیه) تضمین کننده تولید حالتی است که حاوی اهداف خواسته شده باشد (به چنین حالتی، حالت هدف گفته می شود).
سختی برنامه ریزی به میزان ساده سازی فرضیات به کار گرفته وابسته است. بسته به خواص مسایل مختلف در ابعاد متفاوت، چندین دسته از مسایل برنامه ریزی را می توان تعریف کرد. تعدادی از این خواص در زیر آمده اند.
- اعمال موجود قطعیند (جبرگرایی) یا غیرقطعی؟ برای مسایل غیرقطعی، آیا احتمالات مرتبط با آن ها موجودند؟
- متغیرهای حالت گسسته اند یا پیوسته؟ در صورت گسسته بودن، آیا دارای تعداد متناهی از مقادبر می باشند یا خیر؟
- آیا حالت فعلی بدون ابهام قابل مشاهده است؟ مشاهده می تواند به صورت کامل یا جزیی باشد.
- چند حالت اولیه وجود دارد؟ متناهی، یا نامتناهی؟
- آیا اعمال زماندارند؟
- آیا چندین عمل به طور همزمان قابل انجامند، یا تنها انجام یک عمل در هر گام امکان پذیر می باشد؟
- آیا هدف یک برنامه رسیدن به یک حالت هدف تعیین شده است، یا به حداکثر رساندن یک تابع پاداش؟
- یک عامل وجود دارد یا چندین عامل؟ عامل ها همکاری می کنند یا خودخواهند؟ آیا هر عامل برنامه هایش را جداگانه می سازد، یا این برنامه ها به طور متمرکز برای همه ی عامل ها ساخته می شود؟
ساده ترین مساله ی برنامه ریزی، که تحت عنوان مساله ی برنامه ریزی کلاسیک شناخته می شود، به صورت زیر مشخص می شود:
- یک حالت اولیه ی یکتای معلوم
- اعمال بدون زمان
- اعمال قطعی
- که هر بار در یک زمان خاص فقط یک عمل می تواند انجام گیرد
- و یک عامل.
از آن جا که حالت اولیه بدون ابهام مشخص است، و همه اعمال قطعی می باشند، حالت محیط بعد از هر دنباله دلخواه از اعمال، به دقت قابل پیشگویی است، و پرسش قابل مشاهده بودن برای برنامه ریزی کلاسیک غیرضروری است.
علاوه بر این، برنامه ها را می توان به عنوان دنباله ای از اعمال تعریف کرد، زیرا همواره، اعمال مورد نیاز از ابتدا مشخص می باشد.
اگر اعمال غیرقطعی باشند یا عامل های دیگری خارج از کنترل عامل وجود داشته باشند، حالات اجرایی ممکن تشکیل درخت می دهند، و برنامه های اجرایی باید برای هر گره در درخت اعمال مناسب را تعیین کنند.
فرایندهای تصمیم‌گیری مارکوف گسسته، مسایل برنامه ریزی هستند که شامل موارد زیر می باشند:
- اعمال بدون زمان
- اعمال غیرقطعی با احتمالات
- قابلیت مشاهده به طور کامل
- به حداکثر رساندن یک تابع پاداش
- و یک عامل.
هنگامی که قابلیت مشاهده به صورت جزیی باشد، به این برنامه ریزی ، فرایندهای تصمیم‌گیری مارکوف با قابلیت مشاهده جزیی (partially observable Markov decision process) گفته می شود. اگر بیش از یک عامل موجود باشد، یک مساله برنامه ریزی چند عامله (multi-agent planning) داریم، که به نظریه بازی‌ها بسیار مرتبط می باشد.
برنامه ریزی مستقل از دامنه[ویرایش]
در برنامه ریزی هوش مصنوعی، برنامه ریزها به طور معمول یک مدل دامنه (توصیفیست از مجموعه ای از اعمال ممکن، که دامنه را مدل سازی می کنند)، و هم چنین صورت مساله دقیق مورد حل را وارد می کنند، که این صورت مساله توسط حالت اولیه و هدف مشخص می شود، برخلاف مسایلی که در آن ها هیچ دامنه ی ورودی مشخص نمی شود. چنین برنامه ریزهایی، به نشانه ی تاکید روی توانایی حل مسایل برنامه ریزی آن ها در دامنه های متعدد به طور گسترده، برنامه ریزهای مستقل از ورودی نامیده می شوند. به عنوان مثال هایی معمول، می توان به دامنه های پشته سازی بلوکی (block stacking)، لژستیک، مدیریت گردش کار، و برنامه ریزی وظایف ربات (robot task planning) اشاره کرد. بنابراین، در همگی دامنه های نام برده، می توان از یک برنامه ریز مستقل از دامنه برای حل مسایل برنامه ریزی بهره برد. در مقابل، یک برنامه ریز مسیر (route planner)، وابسته به دامنه می باشد.
برنامه ریزی زبان های مدل سازی دامنه[ویرایش]
رایج ترین زبان های مورد استفاده برای نمایش دامنه های برنامه ریزی و مسایل خاص این حوزه، مانند STRIPS وPDDL ، برای برنامه ریزی کلاسیک، به متغیرهای حالت وابسته اند. هر حالت ممکن برای محیط، یعنی تخصیص مقادیر به متغیرهای حالت، و اعمال موجود، چگونگی تغییر مقادیر متغیرهای حالت را به هنگام انجام آن عمل نشان می دهند. از آن جا که مجموعه ای از متغیرهای حالت، محیطی را نتیجه می دهند که دارای اندازه ی با توان نمایی در آن مجموعه است، بنابراین، همانند بسیاری از مسایل محاسباتی دیگر، برنامه ریزی نیز دارای مشکل مشقت بعدچندی و انفجار ترکیبیاتی (combinatorial explosion) می باشد.
شبکه های وظایف سلسله مراتبی (hierarchical task networks)، گروهی از زبان های جایگزین برای توصیف مسایل برنامه ریزی می باشند، که در آن ها با داشتن پاره ای از وظایف، هر وظیفه را می توان توسط یک تابع ابتدایی انجام داد، و یا آن را به مجموعه ای از وظایف کوچک تر تجزیه کرد. این روند لزوما شامل متغیرهای حالت نیست، هرچند وجود آن ها در کاربردهای واقع گرایانه تر، توصیف شبکه های وظایف را ساده تر می کند.
الگوریتم های برنامه ریزی[ویرایش]
برنامه ریزی کلاسیک[ویرایش]
- جست و جوی فضای حالت به صورت زنجیره‌سازی جلوسو (forward chaining)، که توسط الگوریتم جستجوی کاشف قابل تقویت است.
- جستجوی زنجیره سازی وارونه (backward chaining)، که با به اعمال محدودیت روی حالت ها تقویت می شود (مانند STRIPS و graphplan).
- برنامه ریزی ترتیب جزئی (partial-order planning)
کاهش به سایر مسایل[ویرایش]
- کاهش به مسئله صدق‌پذیری دودویی (satplan)
- کاهش به وارسی مدل. هردو اساسا از مسایل پیمایش فضای حالت می باشند، و مساله برنامه ریزی کلاسیک متناظر با زیرکلاسی از مسایل وارسی مدل است.
برنامه ریزی زمانی[ویرایش]
برنامه ریزی زمانی را می توان با روش هایی مشابه با برنامه ریزی کلاسیک حل کرد. تنها تفاوت آن ها در این است که در این نوع برنامه ریزی، احتمال انجام چندین عمل زمان دار، که با یکدیگر هم پوشانی دارند، به طور همزمان وجود دارد؛ بنابراین، تعریف یک حالت باید شامل اطلاعاتی درباره زمان مطلق کنونی و میزان پیشرفت هر عمل فعال در زمان حال باشد. علاوه براین، در برنامه ریزی با زمان حال یا گویا، برخلاف برنامه ریزی کلاسیک یا با زمان صحیح، فضای حالت ممکن است نامتناهی باشد. برنامه ریزی زمانی به مسایل زمان بندی (scheduling problems) ارتباط بسیاری دارد. برنامه ریزی زمانی را می توان از دیدگاه اتوماتون زمانی نیز بررسی کرد.
برنامه ریزی احتمالاتی[ویرایش]
برنامه ریزی احتمالاتی را می توان با روش هایی همانند تکرار مقادیر (value iteration) و تکرار سیاست (policy iteration) حل کرد، به شرط آن که فضای حالت کوچک باشد. درصورت جزیی بودن مشاهده پذیری، برنامه ریزی احتمالاتی را می توان به طور مشابه با روش های تکراری حل کرد، اما به جای استفاده از حالت ها، بایستی از یک نمایش از توابع مقدار تعریف شده برای فضای باورها بهره گرفت.
گسترش سیستم های برنامه ریزی[ویرایش]
- تلسکوپ فضایی هابل از یک سیستم کوتاه مدت به نام SPSS و بلندمدت به نام Spike استفاده می کند.
جستارهای وابسته[ویرایش]
منابع[ویرایش]
- ↑ Ghallab, Malik; Nau, .Dana S; Traverso, Paolo (2004). Automated Planning: Theory and Practice (به English). Morgan Kaufmann. ISBN 1-55860-856-7.صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد.
مطالعه بیشتر[ویرایش]
- Vlahavas, I. "Planning and Scheduling". EETN (به English). Archived from the original on 2013-12-22.صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد.
پیوند به بیرون[ویرایش]
This article "برنامه ریزی خودکار" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:برنامه ریزی خودکار. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
