Automated planning and scheduling
خودکار منصوبہ بندی اور شیڈولنگ، جسے بعض اوقات محض اے آئی منصوبہ بندی کے طور پر ظاہر کیا جاتا ہے، مصنوعی ذہانت کی ایک شاخ ہے جو حکمت عملیوں یا عمل کے سلسلے کے ادراک سے متعلق ہے، عام طور پر ذہین ایجنٹوں، خود مختار روبوٹ اور بغیر پائلٹ والی گاڑیوں کے ذریعے عمل درآمد کے لیے۔ کلاسیکی کنٹرول اور درجہ بندی کے مسائل کے برعکس، حل پیچیدہ ہوتے ہیں اور انہیں کثیر جہتی جگہ میں دریافت اور بہتر بنایا جانا چاہیے۔ منصوبہ بندی کا تعلق فیصلہ کے نظریہ سے بھی ہے۔ دستیاب ماڈلز کے ساتھ معروف ماحول میں، منصوبہ بندی آف لائن کی جا سکتی ہے۔ عمل درآمد سے پہلے حل تلاش کیے جا سکتے ہیں اور ان کا جائزہ لیا جا سکتا ہے۔ متحرک طور پر نامعلوم ماحول میں، حکمت عملی کو اکثر آن لائن نظر ثانی کرنے کی ضرورت ہوتی ہے۔ نمونوں اور پالیسیوں کو اپنانا ضروری ہے۔ حل عام طور پر مصنوعی ذہانت میں عام طور پر دیکھے جانے والے تکراری آزمائش اور غلطی کے عمل کا سہارا لیتے ہیں۔ ان میں متحرک پروگرامنگ، کمفورمیشن لرننگ اور کمبینٹوریئل آپٹیمائزیشن شامل ہیں۔ منصوبہ بندی اور شیڈولنگ کو بیان کرنے کے لیے استعمال ہونے والی زبانوں کو اکثر عملی زبانیں کہا جاتا ہے۔ جائزہ دنیا کی ممکنہ ابتدائی حالتوں کی تفصیل، مطلوبہ اہداف کی تفصیل، اور ممکنہ اقدامات کے ایک سیٹ کی تفصیل کو دیکھتے ہوئے، منصوبہ بندی کا مسئلہ ایک ایسے منصوبے کی ترکیب کرنا ہے جس کی ضمانت دی جاتی ہے (جب ابتدائی ریاستوں میں سے کسی پر لاگو ہوتا ہے) تاکہ ایسی ریاست پیدا کی جا سکے جس میں مطلوبہ اہداف ہوں (ایسی ریاست کو گول اسٹیٹ کہا جاتا ہے)۔ منصوبہ بندی کی مشکل کا انحصار استعمال شدہ آسان مفروضوں پر ہے۔ کئی جہتوں میں مسائل کی خصوصیات کے لحاظ سے منصوبہ بندی کے مسائل کی کئی کلاسوں کی نشاندہی کی جا سکتی ہے۔ کیا یہ اقدامات فیصلہ کن ہیں یا غیر فیصلہ کن؟ غیر متعین اقدامات کے لیے، کیا متعلقہ امکانات دستیاب ہیں؟ کیا ریاستی متغیرات مجرد ہیں یا مسلسل؟ اگر وہ مجرد ہیں، تو کیا ان کے پاس ممکنہ اقدار کی صرف ایک محدود تعداد ہے؟ کیا موجودہ حالت کو غیر واضح طور پر دیکھا جا سکتا ہے؟ مکمل مشاہدہ اور جزوی مشاہدہ ہو سکتا ہے۔ کتنی ابتدائی ریاستیں ہیں، محدود یا من مانی طور پر کئی؟ کیا اعمال کی کوئی مدت ہوتی ہے؟ کیا بیک وقت کئی اقدامات کیے جا سکتے ہیں، یا کیا ایک وقت میں صرف ایک ہی عمل ممکن ہے؟ کیا کسی منصوبے کا مقصد کسی مقررہ ہدف کی حالت تک پہنچنا ہے، یا انعامی تقریب کو زیادہ سے زیادہ کرنا ہے؟ کیا صرف ایک ایجنٹ ہے یا کئی ایجنٹ ہیں؟ کیا ایجنٹ باہمی تعاون کرتے ہیں یا خود غرض؟ کیا تمام ایجنٹ الگ الگ اپنے منصوبے بناتے ہیں، یا منصوبے تمام ایجنٹوں کے لیے مرکزی طور پر بنائے جاتے ہیں؟ سب سے آسان ممکنہ منصوبہ بندی کا مسئلہ، جسے کلاسیکی منصوبہ بندی کا مسئلہ کہا جاتا ہے، اس کا تعین اس طرح ہوتا ہے: ایک منفرد معلوم ابتدائی حالت، بے مدتی اقدامات، تعییناتی اقدامات، جو ایک وقت میں صرف ایک ہی بار کیے جا سکتے ہیں، اور ایک واحد ایجنٹ۔ چونکہ ابتدائی حالت کو غیر واضح طور پر جانا جاتا ہے، اور تمام اعمال متعین ہوتے ہیں، اس لیے اعمال کے کسی بھی سلسلے کے بعد دنیا کی حالت کی درست پیش گوئی کی جا سکتی ہے، اور مشاہدے کا سوال کلاسیکی منصوبہ بندی کے لیے غیر متعلقہ ہے۔ مزید، منصوبوں کو اعمال کے سلسلے کے طور پر بیان کیا جا سکتا ہے، کیونکہ یہ ہمیشہ پہلے سے معلوم ہوتا ہے کہ کن اقدامات کی ضرورت ہوگی۔ غیر متعین اقدامات یا ایجنٹ کے قابو سے باہر دیگر واقعات کے ساتھ، ممکنہ سزائے موت ایک درخت بناتی ہے، اور منصوبوں کو درخت کے ہر نوڈ کے لیے مناسب اقدامات کا تعین کرنا ہوتا ہے۔ ڈسکریٹ ٹائم مارکوف فیصلہ سازی کے عمل (ایم ڈی پی) کے ساتھ مسائل کی منصوبہ بندی کر رہے ہیں: بے وقت اعمال، امکانات کے ساتھ غیر متعین اقدامات، مکمل مشاہدہ، انعام کی تقریب کو زیادہ سے زیادہ کرنا، اور ایک واحد ایجنٹ۔ جب مکمل مشاہدے کو جزوی مشاہدے سے تبدیل کیا جاتا ہے، تو منصوبہ بندی جزوی طور پر قابل مشاہدہ مارکوف فیصلہ عمل (پی او ایم ڈی پی) سے مطابقت رکھتی ہے۔ اگر ایک سے زیادہ ایجنٹ ہیں، تو ہمارے پاس ملٹی ایجنٹ پلاننگ ہے، جس کا گیم تھیوری سے گہرا تعلق ہے۔ ڈومین کی آزاد منصوبہ بندی AI منصوبہ بندی میں، منصوبہ ساز عام طور پر ایک ڈومین ماڈل (ممکنہ اقدامات کے ایک سیٹ کی تفصیل جو ڈومین کا نمونہ بناتی ہے) کے ساتھ ساتھ ابتدائی حالت اور مقصد کے ذریعہ حل کیے جانے والے مخصوص مسئلے کو ان پٹ کرتے ہیں، ان کے برعکس جس میں کوئی ان پٹ ڈومین مخصوص نہیں ہوتا ہے۔ اس طرح کے منصوبہ سازوں کو "ڈومین انڈیپینڈنٹ" کہا جاتا ہے تاکہ اس حقیقت پر زور دیا جا سکے کہ وہ ڈومین کی ایک وسیع رینج سے منصوبہ بندی کے مسائل کو حل کر سکتے ہیں۔ ڈومینز کی عام مثالیں بلاک اسٹیکنگ، لاجسٹکس، ورک فلو مینجمنٹ، اور روبوٹ ٹاسک پلاننگ ہیں۔ لہذا ان تمام مختلف ڈومینز میں منصوبہ بندی کے مسائل کو حل کرنے کے لیے ایک واحد ڈومین آزاد منصوبہ ساز کا استعمال کیا جا سکتا ہے۔ دوسری طرف، ایک روٹ پلانر ڈومین مخصوص پلانر کی خصوصیت ہے۔ منصوبہ بندی ڈومین ماڈلنگ زبانیں منصوبہ بندی ڈومینز اور مخصوص منصوبہ بندی کے مسائل کی نمائندگی کے لیے سب سے زیادہ استعمال ہونے والی زبانیں، جیسے کلاسیکی منصوبہ بندی کے لیے ایس ٹی آر آئی پی ایس اور پی ڈی ڈی ایل، ریاستی متغیرات پر مبنی ہیں۔ دنیا کی ہر ممکنہ حالت ریاستی متغیرات کے لیے اقدار کی تفویض ہے، اور اقدامات اس بات کا تعین کرتے ہیں کہ جب یہ عمل کیا جاتا ہے تو ریاستی متغیرات کی اقدار کیسے بدلتی ہیں۔ چونکہ ریاستی متغیرات کا ایک مجموعہ ایک ریاستی جگہ کو متحرک کرتا ہے جس کا سائز سیٹ میں ایکسپونینشل ہوتا ہے، اسی طرح منصوبہ بندی، بہت سے دوسرے کمپیوٹیشنل مسائل کی طرح، جہت اور مشترکہ دھماکے کی لعنت کا شکار ہوتی ہے۔ منصوبہ بندی کے مسائل کو بیان کرنے کے لیے ایک متبادل زبان درجہ بندی کے ٹاسک نیٹ ورک کی ہے، جس میں کاموں کا ایک مجموعہ دیا جاتا ہے، اور ہر کام کو یا تو ایک ابتدائی عمل کے ذریعے حاصل کیا جا سکتا ہے یا دوسرے کاموں کے مجموعے میں تقسیم کیا جا سکتا ہے۔ اس میں لازمی طور پر ریاستی متغیرات شامل نہیں ہوتے ہیں، حالانکہ زیادہ حقیقت پسندانہ ایپلی کیشنز میں ریاستی متغیرات ٹاسک نیٹ ورک کی تفصیل کو آسان بناتے ہیں۔ کلاسیکی پلاننگ فارورڈ چیننگ اسٹیٹ اسپیس سرچ کی منصوبہ بندی کے لیے الگورتھم، ممکنہ طور پر ہیورسٹکس بیکورڈ چیننگ سرچ کے ساتھ بڑھایا گیا، ممکنہ طور پر ریاستی رکاوٹوں کے استعمال سے بڑھایا گیا (دیکھیں ایس ٹی آر آئی پی ایس، گراف پلان) جزوی ترتیب کی منصوبہ بندی دیگر مسائل میں کمی تجویز کردہ اطمینان بخش مسئلے (سیٹ پلان) میں کمی۔ ماڈل چیکنگ میں کمی-دونوں بنیادی طور پر ریاستی جگہوں کو عبور کرنے کے مسائل ہیں، اور کلاسیکی منصوبہ بندی کا مسئلہ ماڈل چیکنگ کے مسائل کے ذیلی طبقے سے مطابقت رکھتا ہے۔ عارضی منصوبہ بندی کو کلاسیکی منصوبہ بندی سے ملتے جلتے طریقوں سے حل کیا جا سکتا ہے۔ بنیادی فرق یہ ہے کہ متعدد، عارضی طور پر اوور لیپنگ کارروائیوں کے امکان کے ساتھ ساتھ ایک مدت کے ساتھ لیا جاتا ہے، کہ کسی ریاست کی تعریف میں موجودہ مطلق وقت کے بارے میں معلومات شامل ہونی چاہئیں اور ہر فعال عمل پر عمل درآمد کس حد تک آگے بڑھا ہے۔ مزید برآں، عقلی یا حقیقی وقت کے ساتھ منصوبہ بندی میں، ریاستی جگہ لامحدود ہو سکتی ہے، کلاسیکی منصوبہ بندی یا انٹیجر ٹائم کے ساتھ منصوبہ بندی کے برعکس۔ عارضی منصوبہ بندی کا شیڈولنگ کے مسائل سے گہرا تعلق ہوتا ہے جب غیر یقینی صورتحال شامل ہوتی ہے اور اسے ٹائمڈ آٹومیٹا کے لحاظ سے بھی سمجھا جا سکتا ہے۔ غیر یقینی صورتحال کے ساتھ سادہ عارضی نیٹ ورک (ایس ٹی این یو) شیڈولنگ کا ایک مسئلہ ہے جس میں قابو پانے کے قابل اقدامات، غیر یقینی واقعات اور عارضی رکاوٹیں شامل ہیں۔ اس طرح کے مسائل کے لیے متحرک کنٹرول ایبلٹی شیڈولنگ کی ایک قسم ہے جس میں کنٹرول کے قابل اقدامات کو رد عمل سے چالو کرنے کے لیے عارضی منصوبہ بندی کی حکمت عملی کی ضرورت ہوتی ہے کیونکہ غیر یقینی واقعات کا مشاہدہ کیا جاتا ہے تاکہ تمام رکاوٹوں کو پورا کرنے کی ضمانت دی جا سکے۔ ممکنہ منصوبہ بندی ممکنہ منصوبہ بندی کو قدر کی تکرار اور پالیسی کی تکرار جیسے تکراری طریقوں سے حل کیا جا سکتا ہے، جب ریاستی جگہ کافی کم ہو۔ جزوی مشاہدے کے ساتھ، ممکنہ منصوبہ بندی کو اسی طرح تکراری طریقوں سے حل کیا جاتا ہے، لیکن ریاستوں کے بجائے عقائد کی جگہ کے لیے بیان کردہ قدر کے افعال کی نمائندگی کا استعمال کرتے ہوئے۔ ترجیح پر مبنی منصوبہ بندی ترجیح پر مبنی منصوبہ بندی میں، مقصد نہ صرف ایک منصوبہ تیار کرنا ہے بلکہ صارف کی مخصوص ترجیحات کو پورا کرنا بھی ہے۔ زیادہ عام انعام پر مبنی منصوبہ بندی میں فرق، مثال کے طور پر ایم ڈی پیز کے مطابق، ترجیحات کی قطعی عددی قدر ضروری نہیں ہے۔ مشروط منصوبہ بندی متعین منصوبہ بندی کو ایس ٹی آر آئی پی ایس منصوبہ بندی کے نظام کے ساتھ متعارف کرایا گیا تھا، جو ایک درجہ بندی منصوبہ ساز ہے۔ ایکشن کے ناموں کو ایک ترتیب میں ترتیب دیا جاتا ہے اور یہ روبوٹ کے لیے ایک منصوبہ ہے۔ درجہ بندی کی منصوبہ بندی کا موازنہ خودکار طور پر پیدا ہونے والے رویے کے درخت سے کیا جا سکتا ہے۔ نقصان یہ ہے کہ ایک عام طرز عمل کا درخت کمپیوٹر پروگرام کی طرح اتنا اظہار خیال نہیں کرتا ہے۔ اس کا مطلب یہ ہے کہ رویے کے گراف کے اشارے میں ایکشن کمانڈز ہوتے ہیں، لیکن کوئی لوپس یا اگر تب بیانات نہیں ہوتے ہیں۔ مشروط منصوبہ بندی رکاوٹ پر قابو پا لیتی ہے اور ایک تفصیلی نوٹیشن متعارف کراتی ہے جو کنٹرول فلو سے ملتی جلتی ہے، جسے پاسکل جیسی دیگر پروگرامنگ زبانوں سے جانا جاتا ہے۔ یہ پروگرام کی ترکیب سے بہت ملتا جلتا ہے، جس کا مطلب ہے کہ ایک منصوبہ ساز سورس کوڈ تیار کرتا ہے جسے ایک مترجم کے ذریعے انجام دیا جا سکتا ہے۔ مشروط منصوبہ ساز کی ابتدائی مثال "وارپلان-سی" ہے جسے 1970 کی دہائی کے وسط میں متعارف کرایا گیا تھا۔ عام ترتیب اور پیچیدہ منصوبے میں کیا فرق ہے، جس میں اگر تب بیانات ہوتے ہیں؟ اس کا تعلق کسی منصوبے کے رن ٹائم پر غیر یقینی صورتحال سے ہے۔ خیال یہ ہے کہ ایک منصوبہ سینسر سگنلز پر رد عمل ظاہر کر سکتا ہے جو منصوبہ ساز کے لیے نامعلوم ہیں۔ منصوبہ ساز پہلے سے دو انتخاب کرتا ہے۔ مثال کے طور پر، اگر کسی شے کا پتہ چلا ہے، تو عمل اے انجام دیا جاتا ہے، اگر کوئی شے غائب ہے، تو عمل بی انجام دیا جاتا ہے۔ مشروط منصوبہ بندی کا ایک بڑا فائدہ جزوی منصوبوں کو سنبھالنے کی صلاحیت ہے۔ ایک ایجنٹ کو شروع سے آخر تک ہر چیز کی منصوبہ بندی کرنے پر مجبور نہیں کیا جاتا بلکہ وہ مسئلے کو حصوں میں تقسیم کر سکتا ہے۔ یہ ریاستی جگہ کو کم کرنے میں مدد کرتا ہے اور بہت زیادہ پیچیدہ مسائل کو حل کرتا ہے۔ ہنگامی منصوبہ بندی ہم "عارضی منصوبہ بندی" کی بات کرتے ہیں جب ماحول سینسر کے ذریعے قابل مشاہدہ ہوتا ہے، جو ناقص ہو سکتا ہے۔ اس طرح یہ ایک ایسی صورت حال ہے جہاں منصوبہ بندی ایجنٹ نامکمل معلومات کے تحت کام کرتا ہے۔ عارضی منصوبہ بندی کے مسئلے کے لیے، منصوبہ اب اعمال کا ایک سلسلہ نہیں بلکہ ایک فیصلہ درخت ہے کیونکہ منصوبہ کے ہر مرحلے کی نمائندگی ایک مکمل طور پر قابل مشاہدہ حالت کے بجائے ریاستوں کے ایک سیٹ کے ذریعے کی جاتی ہے، جیسا کہ کلاسیکی منصوبہ بندی کے معاملے میں ہوتا ہے۔ منتخب کردہ اقدامات کا انحصار نظام کی حالت پر ہوتا ہے۔ مثال کے طور پر، اگر بارش ہوتی ہے، تو ایجنٹ چھتری لینے کا انتخاب کرتا ہے، اور اگر ایسا نہیں ہوتا ہے، تو وہ اسے نہ لینے کا انتخاب کر سکتے ہیں۔ مائیکل ایل لٹمین نے 1998 میں دکھایا کہ شاخ سازی کے اقدامات کے ساتھ، منصوبہ بندی کا مسئلہ ایکس پی ٹی آئی ایم ای مکمل ہو جاتا ہے۔ ملحقہ منصوبہ بندی کے ایک خاص معاملے کی نمائندگی FOND مسائل کے ذریعے کی جاتی ہے-"مکمل طور پر قابل مشاہدہ اور غیر متعین" کے لیے۔ اگر مقصد ایل ٹی ایل ایف (محدود ٹریس پر لکیری ٹائم منطق) میں متعین کیا گیا ہے تو مسئلہ ہمیشہ ایکس پی ٹی آئی ایم ای مکمل اور 2 ایکس پی ٹی آئی ایم ای مکمل ہوتا ہے اگر مقصد ایل ڈی ایل ایف کے ساتھ متعین کیا گیا ہے۔ مطابقت پذیر منصوبہ بندی تب ہوتی ہے جب ایجنٹ نظام کی حالت کے بارے میں غیر یقینی ہو، اور وہ کوئی مشاہدہ نہیں کر سکتا۔ اس کے بعد ایجنٹ کو حقیقی دنیا کے بارے میں یقین ہوتا ہے، لیکن مثال کے طور پر سینسنگ ایکشن سے ان کی تصدیق نہیں کر سکتا۔ ان مسائل کو کلاسیکی منصوبہ بندی سے ملتی جلتی تکنیکوں کے ذریعے حل کیا جاتا ہے، لیکن جہاں موجودہ حالت کے بارے میں غیر یقینی صورتحال کی وجہ سے ریاستی جگہ مسئلہ کے سائز میں متغیر ہوتی ہے۔ مطابقت پذیر منصوبہ بندی کے مسئلے کا حل اعمال کا ایک سلسلہ ہے۔ ہاسلم اور جونسن نے مظاہرہ کیا ہے کہ مطابقت پذیر منصوبہ بندی کا مسئلہ EXPSPACE مکمل ہے، اور 2EXPTIME مکمل ہے جب ابتدائی صورتحال غیر یقینی ہو، اور اعمال کے نتائج میں غیر عزم ہو۔ منصوبہ بندی کے نظام کی تعیناتی ہبل خلائی دوربین ایس پی ایس ایس نامی ایک قلیل مدتی نظام اور اسپائیک نامی ایک طویل مدتی منصوبہ بندی کے نظام کا استعمال کرتی ہے۔ ایکشن تفصیل زبان اداکار ماڈل مصنوعی ذہانت کی ایپلی کیشنز رکاوٹ اطمینان کا مسئلہ رد عمل منصوبہ بندی شیڈولنگ (کمپیوٹنگ) حکمت عملی (گیم تھیوری) فہرست ایس ایم ٹی حل کرنے والوں کی فہرست رکاوٹ پروگرامنگ زبانوں کی فہرست ابھرتی ہوئی ٹیکنالوجیز کی فہرست مصنوعی ذہانت کے حوالہ جات مزید پڑھنے بیرونی روابط خودکار منصوبہ بندی اور شیڈولنگ پر بین الاقوامی کانفرنس