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

📅 آخر تحديث: ٢٤ يوليو ٢٠٢٦
✍️ نُشر في: ٢٤ يوليو ٢٠٢٦
📷 يحتوي على 4 صور
الموسوعة الحرة
جزء من سلسلة عن
الذكاء الاصطناعي
الأهداف الرئيسية
النهج
التطبيقات
فلسفة
تاريخ
المصطلحات
  • ف
  • ت
  • هـ

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

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

ملخص

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

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

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

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

  • حالة أولية معروفة فريدة من نوعها،
  • أفعال لا تنتهي
  • الأفعال الحتمية
  • والتي لا يمكن تناولها إلا مرة واحدة في كل مرة،
  • ووكيل واحد.

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

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

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

عمليات اتخاذ القرار ماركوف في الوقت المنفصل (MDP) هي مشاكل تخطيطية مع:

  • أفعال لا تنتهي
  • الأفعال غير الحتمية مع الاحتمالات،
  • إمكانية الملاحظة الكاملة،
  • تعظيم وظيفة المكافأة،
  • ووكيل واحد.

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

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

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

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

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

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

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

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

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

الاختزال إلى مشاكل أخرى

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

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

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

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

التخطيط المبني على التفضيلات

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

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

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

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

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

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

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

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

التخطيط المطابق هو عندما يكون العميل غير متأكد من حالة النظام، ولا يمكنه إجراء أي ملاحظات. ثم يكون لدى العميل معتقدات حول العالم الحقيقي، لكنه لا يستطيع التحقق منها من خلال إجراءات الاستشعار، على سبيل المثال. يتم حل هذه المشكلات بتقنيات مماثلة لتلك المستخدمة في التخطيط الكلاسيكي، [12] [13] ولكن حيث تكون مساحة الحالة أسيّة في حجم المشكلة، بسبب عدم اليقين بشأن الحالة الحالية. الحل لمشكلة التخطيط المطابق هو سلسلة من الإجراءات. أظهر هاسلوم وجونسون أن مشكلة التخطيط المطابق تكون مكتملة EXPSPACE ، [14] ومكتملة 2EXPTIME عندما يكون الموقف الأولي غير مؤكد، وهناك عدم حتمية في نتائج الإجراءات. [10]

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

  • يستخدم تلسكوب هابل الفضائي نظامًا قصير المدى يسمى SPSS ونظام تخطيط طويل المدى يسمى Spike [ بحاجة لمصدر ] .

انظر أيضا

القوائم

مراجع

  1. ^ غلاب، مالك؛ ناو، دانا س؛ ترافيرسو، باولو (2004)، التخطيط الآلي: النظرية والتطبيق، مورجان كوفمان ، ISBN 1-55860-856-7, تم أرشفته من الأصل في 2009-08-24 , تم استرجاعه في 2008-08-20
  2. ^ فيدال، تييري (يناير 1999). "التعامل مع الطوارئ في شبكات القيود الزمنية: من الاتساق إلى قابلية التحكم". مجلة الذكاء الاصطناعي التجريبي والنظري . 11 (1): 23--45. CiteSeerX 10.1.1.107.1065 . doi :10.1080/095281399146607. 
  3. ^ Neufeld, Xenija و Mostaghim, Sanaz و Sancho-Pradel, Dario و 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)
  4. ^ سانيلي، فاليريو وكاشمور، مايكل وماجازيني، دانييلي ويوتشي، لوكا (2017). التفاعل بين الإنسان والروبوت على المدى القصير من خلال التخطيط والتنفيذ المشروط. وقائع المؤتمر الدولي للتخطيط والجدولة الآلية (ICAPS). مؤرشف من الأصل في 2019-08-16 . تم الاسترجاع في 2019-08-16 .{{cite conference}}: CS1 maint: multiple names: authors list (link)
  5. ^ بيوت، مارك أ وسميث، ديفيد إي (1992). التخطيط غير الخطي المشروط (PDF) . أنظمة تخطيط الذكاء الاصطناعي. إلسفير. ص 189-197.{{cite conference}}: CS1 maint: multiple names: authors list (link)
  6. ^ كارلسون، لارس (2001). التخطيط التدريجي المشروط في ظل عدم اليقين. IJCAI. ص 431-438.
  7. ^ ليو، دافني هاو (2008). دراسة استقصائية للتخطيط في الوكلاء الأذكياء: من الأنظمة ذات الدوافع الخارجية إلى الأنظمة ذات الدوافع الداخلية (تقرير فني). التقرير الفني TR-2008-936، قسم علوم الكمبيوتر، جامعة روتشستر. مؤرشف من الأصل في 2023-03-15 . تم الاسترجاع في 2019-08-16 .
  8. ^ ألكسندر ألبوري؛ هيكتور بالاسيوس؛ هيكتور جيفنر (2009). نهج قائم على الترجمة للتخطيط الطارئ. المؤتمر الدولي المشترك للذكاء الاصطناعي (IJCAI). باسادينا، كاليفورنيا: AAAI. مؤرشف من الأصل في 2019-07-03 . تم الاسترجاع في 2019-07-03 .
  9. ^ ليتمان، مايكل إل. (1997). التخطيط الاحتمالي القياسي: التمثيلات والتعقيد. المؤتمر الوطني الرابع عشر للذكاء الاصطناعي. مطبعة معهد ماساتشوستس للتكنولوجيا. ص 748-754. مؤرشف من الأصل في 2019-02-12 . تم الاسترجاع في 2019-02-10 .
  10. ^ من قبل Jussi Rintanen (2004). تعقيد التخطيط مع إمكانية الملاحظة الجزئية (PDF) . Int. Conf. Automated Planning and Scheduling. AAAI. مؤرشف (PDF) من الأصل في 2020-10-31 . تم الاسترجاع في 2019-07-03 .
  11. ^ دي جياكومو، جوزيبي؛ روبين، ساشا (2018). أسس نظرية الأتمتة للتخطيط المالي لأهداف LTLf وLDLf. IJCAI. مؤرشف من الأصل في 2018-07-17 . تم الاسترجاع في 2018-07-17 .
  12. ^ بالاسيوس، هيكتور؛ جيفنر، هيكتور (2009). "تجميع عدم اليقين بعيدًا في مشاكل التخطيط المتوافقة ذات العرض المحدود". مجلة أبحاث الذكاء الاصطناعي . 35 : 623-675. arXiv : 1401.3468 . doi : 10.1613/jair.2708 . مؤرشف من الأصل في 2020-04-27 . تم الاسترجاع في 2019-08-16 .
  13. ^ Albore, Alexandre; Ramírez, Miquel; Geffner, Hector (2011). Effective heuristics and belief tracking for planning with incomplete information. المؤتمر الدولي الحادي والعشرون حول التخطيط والجدولة الآلية (ICAPS). مؤرشف من الأصل في 2017-07-06 . تم الاسترجاع في 2019-08-16 .
  14. ^ هاسلوم، باتريك؛ جونسون، بيتر (2000). بعض النتائج حول تعقيد التخطيط باستخدام معلومات غير كاملة . محاضرات في علوم الكمبيوتر. المجلد 1809. سبرينغر برلين هايدلبرغ. ص 308-318. doi :10.1007/10720246_24. ISBN 9783540446576. المؤتمر: التطورات الحديثة في تخطيط الذكاء الاصطناعي

قراءة إضافية

  • فلاهافاس، آي. "التخطيط والجدولة". EETN . مؤرشف من الأصل في 2013-12-22.
  • المؤتمر الدولي حول التخطيط والجدولة الآلية
Retrieved from "https://en.wikipedia.org/w/index.php?title=Automated_planning_and_scheduling&oldid=1220700521"
Original text
Rate this translation
Your feedback will be used to help improve Google Translate