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

التخطيط الآلي والجدولة Automated planning and scheduling، يتم الإشارة إليه أحيانًا على أنه تخطيط الذكاء الاصطناعي ببساطة،^[1] وهو فرع من الذكاء الاصطناعي يهتم بتحقيق الإستراتيجيات أو تسلسل الإجراءات، عادةً من أجل التنفيذ بواسطة الممثلات الذكية و الروبوتات المستقلة و المركبات دون سائق. على عكس مشاكل التحكم و التصنيف، فإن الحلول معقدة ويجب اكتشافها وتحسينها في الفضاء متعدد الأبعاد. ويرتبط التخطيط أيضًا بـ نظرية القرار.

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

نظرة عامة

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

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

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

يتم تحديد أبسط مسألة تخطيط ممكنة، والمعروفة باسم مسألة التخطيط الكلاسيكي، من خلال:

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

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

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

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

تخطط عملية قرار ماركوڤ للوقت المتقطع (MDP) للمسائل بواسطة:

إجراءات بلا حدود،
إجراءات غير حتمية مع احتمالات،
إمكانية الملاحظة الكاملة،
تعظيم تابع التعويض،
وممثل واحد.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

تم تقديم التخطيط الحتمي باستخدام نظام التخطيط STRIPS، وهو مخطط هرمي. حيث يتم ترتيب أسماء الإجراءات في تسلسل وتُعتبر خطة للروبوت. يمكن مقارنة التخطيط الهرمي مع شجرة السلوك.^[2] المساوئ هنا هي أن شجرة السلوك الطبيعي ليست معبرة مثل برنامج الحاسب. وهذا يعني أن تدوين الرسم البياني للسلوك يحتوي على أوامر إجراء، ولكن لا يحتوي على حلقات أو عبارات إذا-عندها if-then-. يتغلب التخطيط الشرطي على هذه المشكلة ويقدم تدوينًا تفصيليًا مشابهًا لـ تدفق التحكم، المعروف من لغات البرمجة الأخرى مثل پاسكال. وهو مشابه جدًا لـ تركيب البرنامج، وهذا يعني أن المخطط ينشئ رمز المصدر الذي يمكن تنفيذه بواسطة مترجم (محول).^[3]

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

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

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

أظهر ميكايل إل. لِتمان في عام 1998 أنه مع الإجراءات المتفرعة، تصبح مسألة التخطيط EXPTIME - كاملة.^[8]^[9] تمثل مسائل FOND حالة معينة من التخطيط المتجاور - "يمكن ملاحظتها بالكامل وغير حتمية". إذا تم تحديد الهدف في LTLf (منطق الزمن الخطي على التتبع المحدود)، فإن المسألة تكون دائمًا EXPTIME-كاملة^[10]و 2EXPTIME-كاملة إذا تم تحديد الهدف باستخدام LDLf.

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

التخطيط المطابق هو عندما يكون الممثل غير متأكد من حالة النظام، ولا يمكنه إجراء أي ملاحظات. عندئذ يكون لدى الممثل معتقدات حول العالم الحقيقي المحيط، لكن لا يمكنه التحقق منها بأفعال الاستشعار، على سبيل المثال. يتم حل هذه المشكلات من خلال تقنيات مشابهة لتلك الخاصة بالتخطيط الكلاسيكي،^[11]^[12] ولكن حين يكون فضاء الحالة أسية في حجم المشكلة، بسبب عدم اليقين بشأن الحالة الحالية. حل مسألة التخطيط المطابق هو سلسلة من الإجراءات. أظهر هاسلُم و جونسن أن مسألة التخطيط المطابق EXPSPACE - مكتمل،^[13] و 2 EXPTIME مكتمل عندما يكون الموقف الأولي غير مؤكداً، وهناك عدم حتمية في نتائج الإجراءات.^[9]

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

انظر أيضاً

قوائم

المراجع

^ Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automated Planning: Theory and Practice, Morgan Kaufmann, ISBN 1-55860-856-7, http://www.laas.fr/planning/
^ 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 Transactions on Games. IEEE.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^ Sanelli, Valerio and Cashmore, Michael and Magazzeni, Daniele and Iocchi, Luca (2017). "Short-term human robot interaction through conditional planning and execution" in Proc. of International Conference on Automated Planning and Scheduling (ICAPS)..
^ Peot, Mark A and Smith, David E (1992). "Conditional nonlinear planning" in Artificial Intelligence Planning Systems.: 189–197, Elsevier.
^ Karlsson, Lars (2001). "Conditional progressive planning under uncertainty" in IJCAI.: 431–438.
^ قالب:Cite techreport
^ (2009) "A Translation-Based Approach to Contingent Planning" in International Joint Conference of Artificial Intelligence (IJCAI)., Pasadena, CA: AAAI.
^ (1997) "Probabilistic Propositional Planning: Representations and Complexity" in Fourteenth National Conference on Artificial Intelligence.: 748–754, MIT Press.
^ ^أ ^ب (2004) "Complexity of Planning with Partial Observability" in Int. Conf. Automated Planning and Scheduling., AAAI.
^ (2018) "Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals" in IJCAI..
^ 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.
^ Albore, Alexandre (2011). "Effective heuristics and belief tracking for planning with incomplete information" in Twenty-First International Conference on Automated Planning and Scheduling (ICAPS)..
^ Haslum, Patrik; Jonsson, Peter (2000). "Some Results on the Complexity of Planning with Incomplete Information". Recent Advances in AI Planning. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 1809: 308–318. doi:10.1007/10720246_24. ISBN 9783540446576.

للاستزادة

Vlahavas, I. "Planning and Scheduling". EETN. Archived from the original on 2013-12-22.

وصلات خارجية

International Conference on Automated Planning and Scheduling

الكلمات الدالة:

[1] Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automated Planning: Theory and Practice, Morgan Kaufmann, ISBN 1-55860-856-7, http://www.laas.fr/planning/

[2] 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 Transactions on Games. IEEE.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[3] Sanelli, Valerio and Cashmore, Michael and Magazzeni, Daniele and Iocchi, Luca (2017). "Short-term human robot interaction through conditional planning and execution" in Proc. of International Conference on Automated Planning and Scheduling (ICAPS)..

[4] Peot, Mark A and Smith, David E (1992). "Conditional nonlinear planning" in Artificial Intelligence Planning Systems.: 189–197, Elsevier.

[5] Karlsson, Lars (2001). "Conditional progressive planning under uncertainty" in IJCAI.: 431–438.

[6] قالب:Cite techreport

[7] (2009) "A Translation-Based Approach to Contingent Planning" in International Joint Conference of Artificial Intelligence (IJCAI)., Pasadena, CA: AAAI.

[8] (1997) "Probabilistic Propositional Planning: Representations and Complexity" in Fourteenth National Conference on Artificial Intelligence.: 748–754, MIT Press.

[rintanen04-9] أ ^ب (2004) "Complexity of Planning with Partial Observability" in Int. Conf. Automated Planning and Scheduling., AAAI.

[10] (2018) "Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals" in IJCAI..

[11] 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.

[12] Albore, Alexandre (2011). "Effective heuristics and belief tracking for planning with incomplete information" in Twenty-First International Conference on Automated Planning and Scheduling (ICAPS)..

[13] Haslum, Patrik; Jonsson, Peter (2000). "Some Results on the Complexity of Planning with Incomplete Information". Recent Advances in AI Planning. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 1809: 308–318. doi:10.1007/10720246_24. ISBN 9783540446576.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]