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

الموسوعة الحرة

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

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

ملخص

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

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

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

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

  • حالة ابتدائية فريدة معروفة،
  • أفعال لا تدوم طويلاً،
  • الأفعال الحتمية،
  • والتي لا يمكن تناولها إلا واحدة تلو الأخرى،
  • ووكيل واحد.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

نموذج التعلم العملي

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

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

الدافع المعتاد لتعلم نماذج الإجراءات هو أن التحديد اليدوي لنماذج الإجراءات للمخططين غالبًا ما يكون مهمة صعبة ومستهلكة للوقت وعرضة للأخطاء (خاصة في البيئات المعقدة). [ 3 ] [ 4 ] [ 5 ]

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

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

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

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

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

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

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

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

تأخذ برامج التخطيط القائمة على التفضيلات هذه التفضيلات في الاعتبار عند وضع خطة لحل مشكلة معينة. ومن أمثلة برامج التخطيط القائمة على التفضيلات برنامج PPLAN [ 7 ] وبرنامج HTNPlan-P [ 8 ] ( التخطيط الهرمي لشبكة المهام القائم على التفضيلات ).

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

Deterministic planning was introduced with the STRIPS planning system, which is a hierarchical planner. Action names are ordered in a sequence and this is a plan for the robot. Hierarchical planning can be compared with an automatic generated behavior tree.[9] The disadvantage is, that a normal behavior tree is not so expressive like a computer program. That means, the notation of a behavior graph contains action commands, but no loops or if-then-statements. Conditional planning overcomes the bottleneck and introduces an elaborated notation which is similar to a control flow, known from other programming languages like Pascal. It is very similar to program synthesis, which means a planner generates sourcecode which can be executed by an interpreter.[10]

An early example of a conditional planner is “Warplan-C” which was introduced in the mid 1970s.[11] What is the difference between a normal sequence and a complicated plan, which contains if-then-statements? It has to do with uncertainty at runtime of a plan. The idea is that a plan can react to sensor signals which are unknown for the planner. The planner generates two choices in advance. For example, if an object was detected, then action A is executed, if an object is missing, then action B is executed.[12] A major advantage of conditional planning is the ability to handle partial plans.[13] An agent is not forced to plan everything from start to finish but can divide the problem into chunks. This helps to reduce the state space and solves much more complex problems.

Contingency planning

We speak of "contingent planning" when the environment is observable through sensors, which can be faulty. It is thus a situation where the planning agent acts under incomplete information. For a contingent planning problem, a plan is no longer a sequence of actions but a decision tree because each step of the plan is represented by a set of states rather than a single perfectly observable state, as in the case of classical planning.[14] The selected actions depend on the state of the system. For example, if it rains, the agent chooses to take the umbrella, and if it doesn't, they may choose not to take it.

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

التخطيط المتوافق

يحدث التخطيط المطابق عندما يكون العامل غير متأكد من حالة النظام، ولا يستطيع إجراء أي ملاحظات. في هذه الحالة، يكون لدى العامل معتقدات حول العالم الحقيقي، لكنه لا يستطيع التحقق منها من خلال إجراءات الاستشعار، على سبيل المثال. تُحل هذه المشكلات بتقنيات مشابهة لتلك المستخدمة في التخطيط الكلاسيكي، [ 18 ] [ 19 ] ولكن حيث يكون فضاء الحالة أسيًا بالنسبة لحجم المشكلة، نظرًا لعدم اليقين بشأن الحالة الراهنة. يتمثل حل مشكلة التخطيط المطابق في سلسلة من الإجراءات. وقد أثبت هاسلوم وجونسون أن مشكلة التخطيط المطابق هي مسألة كاملة من فئة EXPSPACE ، [ 20 ] ومسألة كاملة من فئة 2EXPTIME عندما يكون الوضع الأولي غير مؤكد، وتكون نتائج الإجراءات غير حتمية. [ 16 ]

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

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

انظر أيضاً

القوائم

مراجع

  1. ↑ غلاب، مالك؛ ناو، دانا س.؛ ترافيرسو، باولو (2004)، التخطيط الآلي: النظرية والتطبيق ، مورغان كوفمان ، ISBN 1-55860-856-7تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 24 أغسطس 2009 ، وتمت مراجعته بتاريخ 20 أغسطس 2008.
  2. ↑Action model learning amir2008خطأ في الاستشهاد: تم استدعاء المرجع المسمى ولكن لم يتم تعريفه مطلقًا (انظر صفحة المساعدة ).
  3. ↑ كالينان، إيثان ودي فينيزيا، ريبيكا وأرمسترونغ، فيكتوريا وباريديس، أليسون وشاكربورتي، تاتاغاتا ومويز، كريستيان (2022). MACQ: نظرة شاملة لتقنيات اكتساب النماذج (ملف PDF) . ورشة عمل ICAPS حول هندسة المعرفة للتخطيط والجدولة (KEPS).{{cite conference}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  4. ^ إينيتو، دييغو وخيمينيز سيلوريو، سيرجيو وأونينديا، إيفا (2019). "نماذج عمل التعلم مع الحد الأدنى من إمكانية الملاحظة" . الذكاء الاصطناعي . 275 : 104– 137. دوى : 10.1016/j.artint.2019.05.003 . اتش دي ال : 10251/144560 .{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  5. ^ خيمينيز، سيرجيو ودي لا روزا، توماس وفرنانديز، سوزانا وفرنانديز، فرناندو وبوراجو، دانيال (2012). "مراجعة التعلم الآلي للتخطيط الآلي" . مراجعة هندسة المعرفة . 27 (4): 433-467 . دوى : 10.1017 / S026988891200001X .{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  6. ↑ فيدال، تيري (يناير 1999). "التعامل مع الطوارئ في شبكات القيود الزمنية: من الاتساق إلى قابلية التحكم". مجلة الذكاء الاصطناعي التجريبي والنظري . 11 (1): 23-45. Bibcode : 1999JETAI..11...23V . CiteSeerX 10.1.1.107.1065 . doi : 10.1080/095281399146607 . 
  7. ↑ PPLAN ، Bienvenu et al.
  8. ↑ تخطيط ارتفاع ضغط الدم باستخدام التفضيلات ، سهرابي وآخرون.
  9. ↑ نيوفيلد، زينيا وموستاجيم، ساناز وسانشو-براديل، داريو وبراند، ساندي (2017). "بناء مخطط: دراسة استقصائية لأنظمة التخطيط المستخدمة في ألعاب الفيديو التجارية". معاملات IEEE في الألعاب . IEEE.{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  10. ↑ سانيلي، فاليريو وكاشمور، مايكل وماغازيني، دانييلي وإيوتشي، لوكا (2017). التفاعل قصير المدى بين الإنسان والروبوت من خلال التخطيط والتنفيذ المشروطين . وقائع المؤتمر الدولي للتخطيط والجدولة الآليين (ICAPS). مؤرشف من الأصل بتاريخ 16 أغسطس 2019. تم الاطلاع عليه بتاريخ 16 أغسطس 2019 .{{cite conference}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  11. ↑ بيوت، مارك أ. وسميث، ديفيد إي. (1992). التخطيط غير الخطي المشروط (ملف PDF) . أنظمة تخطيط الذكاء الاصطناعي. إلسيفير. ص 189-197 . {{cite conference}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  12. ↑ كارلسون، لارس (2001). التخطيط التدريجي المشروط في ظل عدم اليقين . المؤتمر الدولي المشترك للذكاء الاصطناعي. الصفحات 431-438 . 
  13. ↑ ليو، دافني هاو (2008). دراسة استقصائية للتخطيط في الأنظمة الذكية: من الأنظمة ذات الدوافع الخارجية إلى الأنظمة ذات الدوافع الداخلية (تقرير فني). التقرير الفني TR-2008-936، قسم علوم الحاسوب، جامعة روتشستر. مؤرشف من الأصل بتاريخ 15 مارس 2023. تم الاطلاع عليه بتاريخ 16 أغسطس 2019 .
  14. ↑ ألكسندر ألبور؛ هيكتور بالاسيوس؛ هيكتور جيفنر (2009). منهج قائم على الترجمة للتخطيط الطارئ . المؤتمر الدولي المشترك للذكاء الاصطناعي (IJCAI). باسادينا، كاليفورنيا: AAAI. مؤرشف من الأصل في 3 يوليو 2019. تم الاسترجاع في 3 يوليو 2019 .
  15. ↑ ليتمان، مايكل ل. (1997). التخطيط الاحتمالي الافتراضي: التمثيلات والتعقيد . المؤتمر الوطني الرابع عشر حول الذكاء الاصطناعي. مطبعة معهد ماساتشوستس للتكنولوجيا. الصفحات 748-754 . مؤرشف من الأصل بتاريخ 12 فبراير 2019. تم الاطلاع عليه بتاريخ 10 فبراير 2019 . 
  16. 1 2 جوسي رينتانين (2004). تعقيد التخطيط مع إمكانية الملاحظة الجزئية (ملف PDF) . المؤتمر الدولي للتخطيط والجدولة الآليين. AAAI. مؤرشف (ملف PDF) من الأصل بتاريخ 31 أكتوبر 2020. تم الاطلاع عليه بتاريخ 3 يوليو 2019 .
  17. ↑ دي جياكومو، جوزيبي؛ روبين، ساشا (2018). الأسس النظرية للأتمتة لتخطيط FOND لأهداف LTLf وLDLf . المؤتمر الدولي المشترك للذكاء الاصطناعي. مؤرشف من الأصل بتاريخ 17 يوليو 2018. تم الاطلاع عليه بتاريخ 17 يوليو 2018 .
  18. ↑ بالاسيوس، هيكتور؛ جيفنر، هيكتور (2009). "التخلص من عدم اليقين في مسائل التخطيط المتوافقة ذات العرض المحدود" . مجلة أبحاث الذكاء الاصطناعي . 35 : 623-675 . arXiv : 1401.3468 . doi : 10.1613/jair.2708 . مؤرشف من الأصل بتاريخ 27 أبريل 2020. تم الاطلاع عليه بتاريخ 16 أغسطس 2019 .
  19. ↑ ألبور، ألكسندر؛ راميريز، ميكيل؛ جيفنر، هيكتور (2011). أساليب استدلالية فعّالة وتتبع المعتقدات للتخطيط في ظل معلومات غير كاملة . المؤتمر الدولي الحادي والعشرون للتخطيط والجدولة الآليين (ICAPS). مؤرشف من الأصل بتاريخ 6 يوليو 2017. تم الاطلاع عليه بتاريخ 16 أغسطس 2019 .
  20. ↑ هاسلوم، باتريك؛ جونسون، بيتر (2000). بعض النتائج حول تعقيد التخطيط في ظل معلومات غير كاملة . سلسلة محاضرات في علوم الحاسوب. المجلد 1809. سبرينغر برلين هايدلبرغ. الصفحات 308-318 . doi : 10.1007/10720246_24 . ISBN   9783540446576مؤتمر : التطورات الحديثة في تخطيط الذكاء الاصطناعي

للمزيد من القراءة

  • فلاهافاس، آي. "التخطيط والجدولة" . EETN . مؤرشف من الأصل بتاريخ 22-12-2013.