التخطيط الآلي والجدولة والتي يشار إليها أحيانًا بتخطيط الذكاء الاصطناعي ، [1] و هي فرع من الذكاء الاصطناعي الذي يتعلق بتحقيق الاستراتيجيات أو تسلسل الإجراءات ، وعادة ما يتم تنفيذه من قبل عملاء أذكياء ، وروبوتات مستقلة ومركبات بدون طيار . على عكس مشاكل التحكم والتصنيف الكلاسيكية ، فإن الحلول معقدة ويجب اكتشافها وتحسينها في مساحة متعددة الأبعاد. و يرتبط التخطيط أيضًا بنظرية القرار .
في البيئات المعروفة مع النماذج المتاحة ، يمكن إجراء التخطيط دون اتصال بالإنترنت. و يمكن إيجاد الحلول وتقييمها قبل التنفيذ. أما في البيئات غير المعروفة ديناميكيًا ، فغالبًا ما تحتاج الاستراتيجية إلى المراجعة عبر الإنترنت. مع ضرورة تكيف النماذج والسياسات. و عادة ما تلجأ الحلول إلى عمليات التجربة والخطأ التكرارية الشائعة في الذكاء الاصطناعي . و تشمل هذه البرمجة الديناميكية ، التعلم المعزز والتحسين التوافقي . و غالبًا ما تسمى اللغات المستخدمة لوصف التخطيط والجدولة بلغات العمل .
نظرة عامة
بالنظر إلى وصف الحالات الأولية المحتملة للعالم ، و الأهداف المرغوبة ، و وصف لمجموعة من الإجراءات المحتملة ، فإن مشكلة التخطيط هي تجميع خطة مضمونة (عند تطبيقها على أي من الحالات الأولية) لتوليد حالة تحتوي على الأهداف المرجوة (تسمى هذه الحالة بحالة الهدف).
تعتمد صعوبة التخطيط على الافتراضات المبسطة المستخدمة. و يمكن تحديد العديد من فئات مشاكل التخطيط اعتمادًا على خصائص المشاكل في عدة أبعاد.
- هل الأفعال حتمية أم لا حتمية؟ و بالنسبة إلى الإجراءات غير المحددة ، هل الاحتمالات المرتبطة بها متاحة؟
- هل متغيرات الحالة منفصلة أم مستمرة؟ إذا كانت منفصلة ، فهل لديهم عدد محدود فقط من القيم المحتملة؟
- هل يمكن ملاحظة الحالة الراهنة على نحو لا لبس فيه؟ يمكن أن تكون هناك ملاحظة كاملة وقابلية ملاحظة جزئية.
- كم عدد الحالات الأولية الموجودة ، هل هي محدودة أو تعسفية؟
- هل الإجراءات لها مدة؟
- هل يمكن اتخاذ العديد من الإجراءات في نفس الوقت ، أم أن إجراء واحد فقط ممكن في كل مرة؟
- هل الهدف من الخطة هو الوصول إلى حالة هدف معين ، أو تعظيم وظيفة المكافأة؟
- هل يوجد وكيل واحد فقط أم أن هناك عدة وكلاء؟ هل الوكلاء متعاونون أم أنانيون؟ و هل يقومون ببناء خططهم الخاصة بشكل منفصل ، أم أن الخطط يتم وضعها على نحو مركزي لجميع الوكلاء
يتم تحديد أبسط مشكلة تخطيط ممكنة تعرف باسم مشكلة التخطيط الكلاسيكي ، من خلال:
- حالة أولية معروفة وفريدة من نوعها
- إجراءات لا تنتهي
- الإجراءات الحتمية
- والتي يمكن اخذها مرة
- و وكيل واحد
- نظرا لأن الحالة الأولية معروفة بنحو لا لبس فيه ، و جميع الإجراءات الحتمية ، يمكنها التنبؤ بدقة بحالة العالم بعد أي تسلسل من الإجراءات ، ومسألة قابلية الملاحظة لا علاقة لها بالتخطيط الكلاسيكي
- علاوة على ذلك ، يمكن تعريف الخطط على أنها تسلسل للإجراءات ، لأنه الاجراءات المطلوبة تكون دائما معروفه مسبقًا .
- و مع الإجراءات غير المحددة أو الأحداث الأخرى خارج سيطرة الوكيل ، تشكل عمليات الإعدام المحتملة شجرة ، ويجب على الخطط تحديد الإجراءات المناسبة لكل عقدة من الشجرة.
- عمليات اتخاذ القرار ماركوف (MDP) هي مشاكل التخطيط مع:
- اجراءات لا تنتهي
- أفعال غير محددة مع احتمالات ، قابلية الملاحظة الكاملة
- الإجراءات الحتمية ,
- تعظيم وظيفة المكافأة
- و وكيل واحد
عندما يتم استبدال القابلية للملاحظة الكاملة بالملاحظة الجزئية ، يتوافق التخطيط مع عملية اتخاذ القرار التي يمكن ملاحظتها جزئيًا (POMDP).
إذا كان هناك أكثر من وكيل واحد ، فلدينا تخطيط متعدد الوكلاء ، والذي يرتبط ارتباطًا وثيقًا بنظرية اللعبة .
التخطيط المستقل للنطاق
في تخطيط الذكاء الاصطناعي ، عادة ما يقوم المخططون بإدخال نموذج المجال (وصف لمجموعة من الإجراءات المحتملة التي تمثل المجال) بالإضافة إلى المشكلة المحددة التي يتعين حلها حسب الحالة والهدف الأولي ، على عكس تلك التي لا يوجد فيها تحديد مجال الإدخال. يُطلق على هؤلاء المخططين اسم "مستقل عن النطاق" للتأكيد على حقيقة أنه يمكنهم حل مشكلات التخطيط من مجموعة واسعة من المجالات. ومن الأمثلة النموذجية على مجالات تكديس الكتل ، والخدمات اللوجستية ، وإدارة سير العمل ، وتخطيط مهام الروبوت. و بالتالي يمكن استخدام مخطط مستقل لنطاق واحد لحل مشاكل التخطيط في جميع هذه المجالات المختلفة. من ناحية أخرى ، يعد مخطط المسار نموذجيًا لمخطط خاص بمجال محدد
تخطيط لغات نمذجة المجال
تعتمد اللغات الأكثر استخدامًا لتمثيل مجالات التخطيط ومشكلات التخطيط المحددة ، مثل STRIPS و PDDL للتخطيط الكلاسيكي ، على متغيرات الحالة. كل حالة ممكنة من العالم هدفها تعيين القيم لمتغيرات الحالة ، وتحدد الإجراءات كيف تتغير قيم متغيرات الحالة عند اتخاذ هذا الإجراء. نظرًا لأن مجموعة من متغيرات الحالة تحث على مساحة الحالة التي لها حجم هائل في المجموعة , فإن التخطيط على غرار العديد من المشاكل الحسابية الأخرى ، يعاني من لعنة الأبعاد والانفجار التوافقي .
اللغة البديلة لوصف مشاكل التخطيط هي تلك الخاصة بشبكات المهام الهرمية ، حيث يتم إعطاء مجموعة من المهام ، ويمكن تنفيذ كل مهمة إما عن طريق إجراء بدائي أو تتحلل إلى مجموعة من المهام الأخرى. لا يتضمن هذا بالضرورة متغيرات الحالة ، على الرغم من أن متغيرات الحالة في التطبيقات الأكثر واقعية تبسط وصف شبكات المهام.
خوارزميات التخطيط
التخطيط الكلاسيكي
- التسلسل إلى الأمام بحالة الفضاء في الفضاء ، ربما مع تعزيز الاستدلال
- البحث المتسلسل إلى الوراء ، ربما يتم تعزيزه باستخدام قيود الحالة (انظر STRIPS ، Graphplan )
- تخطيط جزئي
التقليل من المشاكل الأخرى
- الحد من مشكلة الإرضاء الافتراضية ( satplan ).
- الحد من فحص النموذج - كلاهما بشكل أساسي مشاكل في اجتياز مساحات الدولة ، وتتوافق مشكلة التخطيط الكلاسيكي مع فئة فرعية من مشاكل فحص النموذج.
التخطيط الزمني
يمكن حل التخطيط الزمني بطرق مشابهة للتخطيط الكلاسيكي. والفرق الرئيسي هو بسبب إمكانية اتخاذ العديد من الإجراءات المتداخلة مؤقتًا في وقت واحد ، و أن تعريف الحالة يجب أن يتضمن معلومات حول الوقت المطلق الحالي ومدى تقدم تنفيذ كل إجراء نشط. علاوة على ذلك ، في التخطيط مع الوقت العقلاني أو الحقيقي ، قد تكون مساحة الحالة غير محدودة ، على عكس التخطيط الكلاسيكي أو التخطيط مع الوقت الصحيح. و ان التخطيط الزمني يرتبط ارتباطًا وثيقًا بمشكلات الجدولة .و يمكن أيضًا فهم التخطيط الزمني من حيث التوقيت الآلي .
التخطيط الاحتمالي
يمكن حل التخطيط الاحتمالي بأساليب متكررة مثل تكرار القيمة وتكرار السياسة ، عندما تكون مساحة الحالة صغيرة بما فيه الكفاية. فمع قابلية الملاحظة الجزئية ، يتم حل التخطيط الاحتمالي بالمثل بالطرق التكرارية ، ولكن باستخدام تمثيل وظائف القيمة المحددة لمساحة المعتقدات بدلاً من الحالات.
التخطيط القائم على التفضيل
في التخطيط القائم على التفضيل ، الهدف ليس فقط إنتاج خطة ولكن أيضًا لإرضاء التفضيلات المحددة من قبل المستخدم. هناك اختلافات في التخطيط القائم على المكافأة الأكثر شيوعًا ، على سبيل المثال الذي يتوافق مع MDPs . و لا تحتوي التفضيلات بالضرورة على قيمة رقمية دقيقة.
التخطيط المشروط
تم إدخال التخطيط الحتمي مع نظام تخطيط STRIPS ، وهو مخطط هرمي. يتم ترتيب أسماء الإجراءات في تسلسل , و هذه خطة للروبوت. و يمكن مقارنة التخطيط الهرمي بشجرة سلوكية يتم إنشاؤها تلقائيًا. [2] العيب هو أن شجرة السلوك العادية ليست معبرة مثل برامج الكمبيوتر. وهذا يعني أن تدوين الرسم البياني للسلوك يحتوي على أوامر إجرائية ، ولكن لا تحتوي حلقات أو عبارات إذا-ثم. مع ذلك يتخطى التخطيط المشروط المأزق ويقدم تدوينًا تفصيليًا مشابهًا لتدفق التحكم ، من لغات برمجة أخرى معروفة مثل باسكال . وهو يشبه إلى حد كبير تركيب البرنامج ، وهذا يعني أن المخطط يولد رمز المصدر الذي يمكن تنفيذه بواسطة المترجم.
مثال مبكر لمخطط شرطي هو "Warplan-C" الذي تم تقديمه في منتصف السبعينيات. ما الفرق بين التسلسل العادي والخطة المعقدة التي تحتوي على عبارات "إذا ثم"؟ يتعلق الأمر بالشك عند التشغيل الخطة. الفكرة هي أن الخطة يمكن أن تتفاعل مع إشارات المستشعر غير المعروفة للمخطط. و يجهز المخطط خيارين مقدمًا. على سبيل المثال ، إذا تم الكشف عن الهدف، يتم تنفيذ الإجراء A ، إذا كان الهدف مفقودًا ، يتم تنفيذ الإجراء B. الميزة الرئيسية للتخطيط المشروط هي القدرة على التعامل مع الخطط الجزئية . عندها لا يضطر الوكيل إلى التخطيط لكل شيء من البداية إلى النهاية ، ولكن يمكنه تقسيم المشكلة إلى اجزاءو هذا يساعد على تقليل مساحة الحالة ويحل مشاكل أكثر تعقيدًا.
التخطيط الطارئ
نتحدث عن "التخطيط الطارئ" عندما تكون البيئة قابلة للرصد من خلال أجهزة الاستشعار ، والتي يمكن أن تكون معيبة. وبالتالي فهي حالة يتصرف فيها وكيل التخطيط في ظل معلومات غير كاملة. و بالنسبة لمشكلة التخطيط االطارئ ، لم تعد الخطة عبارة عن سلسلة من الإجراءات بل شجرة قرارات لأن كل خطوة من الخطة يتم تمثيلها بمجموعة من الحالات بدلاً من حالة واحدة يمكن ملاحظتها تمامًا ، كما هو الحال في التخطيط الكلاسيكي. تعتمد الإجراءات المختارة على حالة النظام. على سبيل المثال ، إذا كانت تمطر ، يختار الوكيل أن يأخذ المظلة ، وإذا لم تمطر ، فقد يختار عدم أخذها.
أظهرت ميكائيل L. يتمان في عام 1998 أنه مع الإجراءات المتفرعة تصبح مشكلة التخطيط EXPTIME -complete. و تتمثل حالة معينة من التخطيط المتجاور بمشاكل FOND - "للملاحظة بشكل كامل وغير حتمية". إذا كان الهدف محددًا في LTLf (منطق الوقت الخطي في التتبع المحدود) ، فإن المشكلة تكتمل دائمًا EXPTIME و 2 EXPTIME إذا تم تحديد الهدف باستخدام LDLf.
التخطيط المطابق
التخطيط المطابق هو عندما يكون الوكيل غير متأكد من حالة النظام ، ولا يمكنه إجراء أي ملاحظات.و لدى الوكيل بعد ذلك معتقدات حول العالم الحقيقي ، لكنه لا يستطيع التحقق منها بأفعال الاستشعار ، على سبيل المثال. يتم حل هذه المشاكل من خلال تقنيات مشابهة لتلك الموجودة في التخطيط الكلاسيكي ، [3] ولكن حيث تكون مساحة االحالة اسيا مع حجم المشكلة بسبب عدم اليقين بشأن الحالة الحالية.
عندها يوجد حل لمشكلة التخطيط المطابقة و هو تسلسل الإجراءات. وقد أثبتت Haslum وجونسون أن مشكلة التخطيط المطابق هو EXPSPACE -complete، [4] و2EXPTIME-كاملة عندما يكون الوضع الأولي غير مؤكد، وليس هناك الحالات غير الحتمية في نتائج الأعمال.
نشر نظم التخطيط
- يستخدم تلسكوب هابل الفضائي نظامًا قصير المدى يسمى SPSS ونظام تخطيط طويل المدى يسمى سبايك .
مقالات ذات صلة
القوائم
المراجع
- Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automated Planning: Theory and Practice, Morgan Kaufmann, , مؤرشف من الأصل في 24 أغسطس 2009
- Neufeld, Xenija and Mostaghim, Sanaz and Sancho-Pradel, Dario and Brand, Sandy (2017). "Building a Planner: A Survey of Planning Systems Used in Commercial Video Games". IEEE.
- Palacios, Hector; Geffner, Hector (2009). "Compiling uncertainty away in conformant planning problems with bounded width". Journal of Artificial Intelligence Research. 35: 623–675. doi:10.1613/jair.2708. مؤرشف من الأصل في 27 أبريل 2020.
- Haslum, Patrik; Jonsson, Peter (2000). "Some Results on the Complexity of Planning with Incomplete Information". Springer Berlin Heidelberg. 1809: 308–318. doi:10.1007/10720246_24. .
قراءة متعمقة
- Vlahavas, I. "Planning and Scheduling". EETN. مؤرشف من الأصل في 22 ديسمبر 2013.