التخطيط الآلي والجدولة

يستخدم الروبوت أسيمو أجهزة الاستشعار وخوارزميات ذكية لتجنب العقبات والتحرك على الدرج.

التخطيط الآلي والجدولة والتي يشار إليها أحيانًا بتخطيط الذكاء الاصطناعي ، وهي فرع من الذكاء الاصطناعي الذي يتعلق بتحقيق الاستراتيجيات أوتسلسل الإجراءات ، وعادة ما يتم تطبيقه من قبل عملاء أذكياء ، وروبوتات مستقلة ومركبات بدون طيار . على عكس مشاكل التحكم والتصنيف الكلاسيكية ، فإن الحلول معقدة ويجب اكتشافها وتحسينها في مساحة متعددة الأبعاد. ويرتبط التخطيط أيضًا بنظرية القرار .

في البيئات المعروفة مع النماذج المتاحة ، يمكن إجراء التخطيط دون اتصال بالإنترنت. ويمكن إيجاد الحلول وتقييمها قبل التطبيق. أما في البيئات غير المعروفة ديناميكيًا ، فغالبًا ما بحاجة الاستراتيجية إلى المراجعة عبر الإنترنت. مع ضرورة تكيف النماذج والسياسات. وعادة ما تلجأ الحلول إلى عمليات التجربة والخطأ التكرارية الشائعة في الذكاء الاصطناعي . وتضم هذه البرمجة الديناميكية ، التفهم المعزز والتحسين التوافقي . وغالبًا ما تسمى اللغات المستخدمة لوصف التخطيط والجدولة بلغات العمل .

نظرة عامة

بالنظر إلى وصف الحالات الأولية المحتملة للعالم ، والأهداف المرغوبة ، ووصف لمجموعة من الإجراءات المحتملة ، فإن معضلة التخطيط هي تجميع خطة مضمونة (عند تطبيقها على أي من الحالات الأولية) لتوليد حالة تحتوي على الأهداف المرجوة (تسمى هذه الحالة بحالة الهدف).

تعتمد صعوبة التخطيط على الافتراضات المبسطة المستخدمة. ويمكن تحديد الكثير من فئات مشاكل التخطيط اعتمادًا على خصائص المشاكل في عدة أبعاد.

هل الأفعال حتمية أم لا حتمية،يا ترى؟ وبالنسبة إلى الإجراءات غير المحددة ، هل الاحتمالات المرتبطة بها متاحة؟
هل متغيرات الحالة منفصلة أم مستمرة،يا ترى؟ إذا كانت منفصلة ، فهل لديهم عدد محدود فقط من القيم المحتملة؟
هل يمكن ملاحظة الحالة الراهنة على نحولا لبس فيه،يا ترى؟ يمكن حتى تكون هناك ملاحظة كاملة وقابلية ملاحظة جزئية.
كم عدد الحالات الأولية الموجودة ، هل هي محدودة أوتعسفية؟
هل الإجراءات لها مدة؟
هل يمكن اتخاذ الكثير من الإجراءات في نفس الوقت ، أم حتى إجراء واحد فقط ممكن في جميع مرة؟

هل الهدف من الخطة هوالوصول إلى حالة هدف معين ، أوتعظيم وظيفة المكافأة؟
هل يوجد وكيل واحد فقط أم حتى هناك عدة وكلاء،يا ترى؟ هل الوكلاء متعاونون أم أنانيون،يا ترى؟ وهل يقومون ببناء خططهم الخاصة بشكل منفصل ، أم حتى الخطط يتم وضعها على نحومركزي لجميع الوكلاء

يتم تحديد أبسط معضلة تخطيط ممكنة تعهد باسم معضلة التخطيط الكلاسيكي ، من خلال:

حالة أولية معروفة وفريدة من نوعها
إجراءات لا تنتهي
الإجراءات الحتمية
والتي يمكن اخذها مرة
ووكيل واحد

نظرا لأن الحالة الأولية معروفة بنحولا لبس فيه ، وجميع الإجراءات الحتمية ، يمكنها التنبؤ بدقة بحالة العالم بعد أي تسلسل من الإجراءات ، ومسألة قابلية الملاحظة لا علاقة لها بالتخطيط الكلاسيكي
علاوة على ذلك ، يمكن تعريف الخطط على أنها تسلسل للإجراءات ، لأنه الاجراءات المطلوبة تكون دائما معروفه مسبقًا .
ومع الإجراءات غير المحددة أوالأحداث الأخرى خارج سيطرة الوكيل ، تشكل عمليات الإعدام المحتملة شجرة ، ويجب على الخطط تحديد الإجراءات المناسبة لكل عقدة من الشجرة.
عمليات اتخاذ القرار ماركوف (MDP) هي مشاكل التخطيط مع:

اجراءات لا تنتهي
أفعال غير محددة مع احتمالات ، قابلية الملاحظة الكاملة
الإجراءات الحتمية ,
تعظيم وظيفة المكافأة
ووكيل واحد

عندما يتم استبدال القابلية للملاحظة الكاملة بالملاحظة الجزئية ، يتوافق التخطيط مع عملية اتخاذ القرار التي يمكن ملاحظتها جزئيًا (POMDP).

إذا كان هناك أكثر من وكيل واحد ، فلدينا تخطيط متعدد الوكلاء ، والذي يرتبط ارتباطًا وثيقًا بنظرية اللعبة .

التخطيط المستقل للنطاق

في تخطيط الذكاء الاصطناعي ، عادة ما يقوم المخططون بإدخال نموذج المجال (وصف لمجموعة من الإجراءات المحتملة التي تمثل المجال) بالإضافة إلى المشكلة المحددة التي يتعين حلها حسب الحالة والهدف الأولي ، على عكس تلك التي لا يوجد فيها تحديد مجال الإدخال. يُطلق على هؤلاء المخططين اسم "مستقل عن النطاق" للتأكيد على حقيقة أنه يمكنهم حل مشكلات التخطيط من مجموعة واسعة من المجالات. ومن الأمثلة النموذجية على مجالات تكديس الكتل ، والخدمات اللوجستية ، وإدارة سير العمل ، وتخطيط مهام الروبوت. وبالتالي يمكن استعمال مخطط مستقل لنطاق واحد لحل مشاكل التخطيط في جميع هذه المجالات المتنوعة. من ناحية أخرى ، يعد مخطط المسار نموذجيًا لمخطط خاص بمجال محدد

تخطيط لغات نمذجة المجال

تعتمد اللغات الأكثر استخدامًا لتمثيل مجالات التخطيط ومشكلات التخطيط المحددة ، مثل STRIPS وPDDL للتخطيط الكلاسيكي ، على متغيرات الحالة. جميع حالة ممكنة من العالم هدفها تعيين القيم لمتغيرات الحالة ، وتحدد الإجراءات كيف من الممكن أن تتغير قيم متغيرات الحالة عند اتخاذ هذا الإجراء. نظرًا لأن مجموعة من متغيرات الحالة تحث على مساحة الحالة التي لها حجم هائل في المجموعة , فإن التخطيط على غرار الكثير من المشاكل الحسابية الأخرى ، يعاني من لعنة الأبعاد والانفجار التوافقي .

اللغة البديلة لوصف مشاكل التخطيط هي تلك الخاصة بشبكات المهام الهرمية ، حيث يتم إعطاء مجموعة من المهام ، ويمكن تطبيق جميع مهمة إما عن طريق إجراء بدائي أوتتحلل إلى مجموعة من المهام الأخرى. لا يتضمن هذا بالضرورة متغيرات الحالة ، على الرغم من حتى متغيرات الحالة في التطبيقات الأكثر واقعية تبسط وصف شبكات المهام.

خوارزميات التخطيط

التخطيط الكلاسيكي

التسلسل إلى الأمام بحالة الفضاء في الفضاء ، من الممكن مع تعزيز الاستدلال
البحث المتسلسل إلى الوراء ، من الممكن يتم تعزيزه باستخدام قيود الحالة (انظر STRIPS ، Graphplan )
تخطيط جزئي

التقليل من المشاكل الأخرى

الحد من معضلة الإرضاء الافتراضية ( satplan ).
الحد من فحص النموذج - كلاهما بشكل أساسي مشاكل في اجتياز مساحات الدولة ، وتتوافق معضلة التخطيط الكلاسيكي مع فئة فرعية من مشاكل فحص النموذج.

التخطيط الزمني

يمكن حل التخطيط الزمني بطرق مماثلة للتخطيط الكلاسيكي. والفرق الرئيسي هوبسبب إمكانية اتخاذ الكثير من الإجراءات المتداخلة مؤقتًا في وقت واحد ، وحتى تعريف الحالة يجب حتى يتضمن معلومات حول الوقت المطلق الحالي ومدى تقدم تطبيق جميع إجراء نشط. علاوة على ذلك ، في التخطيط مع الوقت العقلاني أوالحقيقي ، قد تكون مساحة الحالة غير محدودة ، على عكس التخطيط الكلاسيكي أوالتخطيط مع الوقت السليم. وان التخطيط الزمني يرتبط ارتباطًا وثيقًا بمشكلات الجدولة .ويمكن أيضًا فهم التخطيط الزمني من حيث التوقيت الآلي .

التخطيط الاحتمالي

يمكن حل التخطيط الاحتمالي بأساليب متكررة مثل تكرار القيمة وتكرار السياسة ، عندما تكون مساحة الحالة صغيرة بما فيه الكفاية. فمع قابلية الملاحظة الجزئية ، يتم حل التخطيط الاحتمالي بالمثل بالطرق التكرارية ، ولكن باستخدام تمثيل وظائف القيمة المحددة لمساحة المعتقدات بدلاً من الحالات.

التخطيط القائم على التفضيل

في التخطيط القائم على التفضيل ، الهدف ليس فقط إنتاج خطة ولكن أيضًا لإرضاء التفضيلات المحددة من قبل المستخدم. هناك اختلافات في التخطيط القائم على المكافأة الأكثر شيوعًا ، على سبيل المثال الذي يتوافق مع MDPs . ولا تحتوي التفضيلات بالضرورة على قيمة رقمية دقيقة.

التخطيط المشروط

تم إدخال التخطيط الحتمي مع نظام تخطيط STRIPS ، وهومخطط هرمي. يتم ترتيب أسماء الإجراءات في تسلسل , وهذه خطة للروبوت. ويمكن مقارنة التخطيط الهرمي بشجرة سلوكية يتم إنشاؤها تلقائيًا. العيب هوحتى شجرة السلوك العادية ليست معبرة مثل برامج الكمبيوتر. وهذا يعني حتى تدوين الرسم البياني للسلوك يحتوي على أوامر إجرائية ، ولكن لا تحتوي حلقات أوعبارات إذا-ثم. مع ذلك يتخطى التخطيط المشروط المأزق ويقدم تدوينًا تفصيليًا مشابهًا لتدفق التحكم ، من لغات برمجة أخرى معروفة مثل باسكال . وهويشبه إلى حد كبير هجريب البرنامج ، وهذا يعني حتى المخطط يولد رمز المصدر الذي يمكن تطبيقه بواسطة المترجم.

مثال مبكر لمخطط شرطي هو"Warplan-C" الذي تم تقديمه في منتصف السبعينيات. ما الفرق بين التسلسل العادي والخطة المعقدة التي تحتوي على عبارات "إذا ثم"،يا ترى؟ يتعلق الأمر بالشك عند التشغيل الخطة. الفكرة هي حتى الخطة يمكن حتى تتفاعل مع إشارات المستشعر غير المعروفة للمخطط. ويجهز المخطط خيارين مقدمًا. على سبيل المثال ، إذا تم الكشف عن الهدف، يتم تطبيق الإجراء A ، إذا كان الهدف مفقودًا ، يتم تطبيق الإجراء B. الميزة الرئيسية للتخطيط المشروط هي القدرة على التعامل مع الخطط الجزئية . عندها لا يضطر الوكيل إلى التخطيط لكل شيء من البداية إلى النهاية ، ولكن يمكنه تقسيم المشكلة إلى اجزاءوهذا يساعد على تقليل مساحة الحالة ويحل مشاكل أكثر تعقيدًا.

التخطيط الطارئ

نتحدث عن "التخطيط الطارئ" عندما تكون البيئة قابلة للرصد من خلال أجهزة الاستشعار ، والتي يمكن حتى تكون معيبة. وبالتالي فهي حالة يتصرف فيها وكيل التخطيط في ظل معلومات غير كاملة. وبالنسبة لمشكلة التخطيط االطارئ ، لم تعد الخطة تعبير عن سلسلة من الإجراءات بل شجرة قرارات لأن جميع خطوة من الخطة يتم تمثيلها بمجموعة من الحالات بدلاً من حالة واحدة يمكن ملاحظتها تمامًا ، كما هوالحال في التخطيط الكلاسيكي. تعتمد الإجراءات المختارة على حالة النظام. على سبيل المثال ، إذا كانت تمطر ، يختار الوكيل حتى يأخذ المظلة ، وإذا لم تمطر ، فقد يختار عدم أخذها.

أظهرت ميكائيل L. يتمان في عام 1998 أنه مع الإجراءات المتفرعة تصبح معضلة التخطيط EXPTIME -complete. و تتمثل حالة معينة من التخطيط المتجاور بمشاكل FOND - "للملاحظة بشكل تام وغير حتمية". إذا كان الهدف محددًا في LTLf (منطق الوقت الخطي في التتبع المحدود) ، فإن المشكلة تكتمل دائمًا EXPTIME و2 EXPTIME إذا تم تحديد الهدف باستخدام LDLf.

التخطيط المطابق

التخطيط المطابق هوعندماقد يكون الوكيل غير متأكد من حالة النظام ، ولا يمكنه إجراء أي ملاحظات.ولدى الوكيل بعد ذلك معتقدات حول العالم الحقيقي ، لكنه لا يستطيع التحقق منها بأفعال الاستشعار ، على سبيل المثال. يتم حل هذه المشاكل من خلال تقنيات مماثلة لتلك الموجودة في التخطيط الكلاسيكي ، ولكن حيث تكون مساحة االحالة اسيا مع حجم المشكلة بسبب عدم اليقين بشأن الحالة الحالية.

عندها يوجد حل لمشكلة التخطيط المطابقة وهوتسلسل الإجراءات. وقد أثبتت Haslum وجونسون حتى معضلة التخطيط المطابق هوEXPSPACE -complete، و2EXPTIME-كاملة عندماقد يكون الوضع الأولي غير مؤكد، وليس هناك الحالات غير الحتمية في نتائج الأعمال.

نشر نظم التخطيط

يستخدم تلسكوب هابل الفضائي نظامًا قصير المدى يسمى SPSS ونظام تخطيط طويل المدى يسمى سبايك .

انظر أيضا

ذكاء اصطناعي
جدولة (حاسوب)

القوائم

التقنيات التكنولوجية التي نشأت حديثا

المراجع

^ Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), , Morgan Kaufmann, ISBN , مؤرشف من الأصل في 24 أغسطس 2009 CS1 maint: ref=harv (link)
^ 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. صيانة CS1: أسماء متعددة: قائمة المؤلفون (link)
^ 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. ISBN .