زمانبندی و برنامهریزی خودکار (به انگلیسی: 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)، گروهی از زبانهای جایگزین برای توصیف مسایل برنامهریزی میباشند، که در آنها با داشتن پاره ای از وظایف، هر وظیفه را میتوان توسط یک تابع ابتدایی انجام داد، یا آن را به مجموعه ای از وظایف کوچکتر تجزیه کرد. این روند لزوماً شامل متغیرهای حالت نیست، هرچند وجود آنها در کاربردهای واقع گرایانه تر، توصیف شبکههای وظایف را سادهتر میکند.
برنامهریزی زمانی (Temporal Planning) را میتوان با روشهایی مشابه با برنامهریزی کلاسیک حل کرد. تنها تفاوت آنها در این است که در این نوع برنامهریزی، احتمال انجام چندین عمل زمان دار، که با یکدیگر هم پوشانی دارند، بهطور همزمان وجود دارد؛ بنابراین، تعریف یک حالت باید شامل اطلاعاتی دربارهٔ زمان مطلق کنونی و میزان پیشرفت هر عمل فعال در زمان حال باشد. علاوه براین، در برنامهریزی با زمان حال یا گویا، برخلاف برنامهریزی کلاسیک یا با زمان صحیح، فضای حالت ممکن است نامتناهی باشد. برنامهریزی زمانی به مسایل زمانبندی (Scheduling Problems) ارتباط بسیاری دارد. برنامهریزی زمانی را میتوان از دیدگاه اتوماتون زمانی نیز بررسی کرد.
برنامهریزی احتمالاتی (Conditional Planning) را میتوان با روشهایی همانند تکرار مقادیر (Value Iteration) و تکرار سیاست (Policy Iteration) حل کرد، به شرط آن که فضای حالت کوچک باشد. درصورت جزئی بودن مشاهده پذیری، برنامهریزی احتمالاتی را میتوان بهطور مشابه با روشهای تکراری حل کرد، اما به جای استفاده از حالتها، بایستی از یک نمایش از توابع مقدار تعریف شده برای فضای باورها بهره گرفت.
در برنامهریزی ترجیحی (Preference-based Planning)، هدف تنها تولید یک برنامه نیست، بلکه، باید ترجیحات و اولویتهای مشخص شدهٔ کاربر را نیز ارضا نمود. یکی از تفاوتهای این نوع برنامهریزی با سایر انواع آنها همانند فرایندهای تصمیمگیری مارکوف، که مبتنی بر پاداشند، این است که ترجیحات موجود لزوماً دارای مقدار عددی دقیق نمیباشند.
برنامه ریزی قطعی (Deterministic Planning)، با ایجاد سیستم برنامه ریزی STRIPS، که سیستمی سلسله مراتبی است، معرفی شد. اسامی اعمال در یک دنباله، مرتب شده می باشند و این برنامه ی موجود برای ربات می باشد. برنامه ریزی سلسله مراتبی (Hierarchical planning) با یک درخت رفتار (Behavior Tree) که به صورت اتوماتیک تولید می شود، قابل قیاس است . ایراد این مساله در آن است که یک درخت رفتار نرمال به اندازه ی برنامه های کامپیوتری معنادار نیست. به عبارت دیگر، نمادگذاری گراف رفتار شامل دستورات انجام عمل می باشد، ولی حاوی مفاهیمی مانند حلقه (Loop) و یا عبارات شرطی if-then نمی باشد. برنامه ریزی شرطی (Conditional Planning) این ایراد را با معرفی یک نمادگذاری مفصل تر برطرف می کند؛ که بسیار مشابه مفهوم کنترل جریان در سایر زبان های برنامه نویسی مانند پاسکال می باشد. این نمادگذاری مشابه مفهوم بهم پیوستگی برنامه ها (Program Synthesis) است، بدین معنا که یک برنامه ریز کدی را تولید می کند که توسط interpreter قابل اجراست .
“Warplan-C” مثالی اولیه از برنامه ریز شرطی می باشد که در اواسط سال 1970 معرفی شد . تفاوت میان یک دنباله ی ساده و برنامه ای پیچیده متشکل از عبارات if-then در چیست؟ این اختلاف از عدم قطعیت در حین زمان اجرای برنامه (Runtime) نشأت می گیرد. بدین معنا که برنامه می تواند به سیگنال های سنسوری که برای برنامه ریز ناشناخته است، عکس العمل نشان دهد. برنامه ریز پیشاپیش دو انتخاب ممکن تولید می کند. برای نمونه، اگر یک شی فرضی شناسایی شود، برنامه ی A را اجرا می کند، و در صورت عدم شناسایی آن، برنامه ی B اجرا می شود . توانایی اجرای برنامه های جزیی (Partial Plans)، از مزایای برجسته ی برنامه ریزی شرطی به حساب می آید . عامل مجبور به برنامه ریزی همه موارد از ابتدا تا انتها نمی باشد، بلکه می تواند مساله را به بخش های کوچک تر تقسیم کند. این امر باعث کاهش فضای حالت و حل مسایل پیچیده تر می شود.
اگر محیط توسط سنسورها قابل مشاهده باشد، اصطلاح برنامه ریزی تصادفی (Contingent Planning) را به کار می بریم، که در آن ممکن است با خطا مواجه شویم. بنابراین، در این نوع برنامه ریزی، عامل با اطلاعات ناقص کار می کند. در برنامه ریزی تصادفی، برنامه ی موجود به صورت درخت تصمیم تعریف می شود، نه به صورت دنباله ای از اعمال، زیرا، برخلاف برنامه ریزی کلاسیک که در آن هر گام از برنامه توسط یک حالت قابل مشاهده ی کامل نمایش داده می شود، در برنامه ریزی تصادفی برنامه توسط مجموعه ای از حالات قابل نمایش است . اعمال انتخاب شده به وضعیت سیستم بستگی دارند. برای مثال، اگر باران ببارد، عامل به همراه بردن چتر را انتخاب می کند، و اگر این اتفاق نیفتد، ممکن است چتر را انتخاب نکند.
مایکل لیتمن در سال 1998 نشان داد که مساله برنامه ریزی همراه با اعمال منشعب (Branching Actions)، دارای پیچیدگی زمانی نمایی کامل (EXPTIME-complete) است . حالت خاصی از برنامه ریزی تصادفی توسط مسایل "قابل مشاهده ی کامل و غیرقطعی" یا همان “Fully-Observable and Non-deterministic (FOND) Problems” قابل بیان است. اگر هدف مساله در منطق زمانی خطی روی تریس متناهی (Linear Time Logic on Finite Trace (LTLf)) تعریف شود، آن گاه مساله همواره EXPTIME-complete است ، و اگر هدف در منطق پویای خطی روی تریس متناهی (Linear Dynamic Logic on Finite Trace (LDLf)) تعریف شود، مساله 2EXPTIME-complete می باشد.
اگر عامل در مورد حالت سیستم مردد باشد، و قادر به مشاهده ی هیچ چیز نباشد، آن گاه مساله، برنامه ریزی منطبق(Conformant Planning) نام دارد. در این نوع برنامه ریزی، عامل باورهایی درباره محیط واقعی دارد، اما به عنوان مثال، قادر به تایید صحت این باورها با اعمال حسی خود نیست. این دسته از مسایل راه حل هایی مشابه برنامه ریزی کلاسیک دارند ، با این تفاوت که فضای حالت، به دلیل عدم قطعیت حالت فعلی، دارای اندازه ای با توان نمایی می باشد. برای برنامه ریزی منطبق، راه حل مساله به صورت دنباله ای از اعمال تعریف می شود. هاسلوم و جانسون نشان داده اند که مساله برنامه ریزی منطبق دارای پیچیدگی مکانی نمایی کامل (EXPSPACE-complete) است ، و اگر وضعیت اولیه نامعلوم باشد و نتایج حاصل از اعمال همراه با عدم قطعیت باشند، این مساله دارای پیچیدگی زمانی نمایی کامل دو برابر (2EXPTIME-complete) می باشد .
This article uses material from the Wikipedia فارسی article زمانبندی و برنامهریزی خودکار, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). محتوا تحت CC BY-SA 4.0 در دسترس است مگر خلافش ذکر شده باشد. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki فارسی (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.