شجرة السلوك (الذكاء الاصطناعي، والروبوتات، والتحكم)

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

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

خلفية

نموذج شجرة السلوك الذي يجسد خطة البحث والإمساك لروبوت ذي ذراعين

اقترح رودني بروكس في ورقته البحثية بعنوان "نظام تحكم متعدد الطبقات قوي لروبوت متحرك" بنية تحكم قائمة على السلوك. في هذا الاقتراح الأولي، يمكن استخدام قائمة من السلوكيات كبدائل لبعضها البعض. لاحقًا، تم توسيع هذا النهج وتعميمه ليصبح تنظيمًا شجريًا للسلوكيات، مع تطبيقات واسعة في صناعة ألعاب الفيديو كأداة فعالة لنمذجة سلوك الشخصيات غير القابلة للعب (NPCs). [ 3 ] [ 4 ] [ 5 ] [ 6 ] وقد استُخدمت هذه البنية على نطاق واسع في ألعاب فيديو شهيرة مثل Halo و Bioshock و Spore . تقترح الدراسات الحديثة استخدام أشجار السلوك كإطار عمل للتحكم متعدد المهام في الطائرات بدون طيار ، والروبوتات المعقدة، وأنظمة التلاعب الروبوتية، وأنظمة الروبوتات المتعددة. [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] لقد وصلت أشجار السلوك الآن إلى مرحلة النضج التي يمكن تناولها في كتب الذكاء الاصطناعي للألعاب، [ 13 ] [ 14 ] بالإضافة إلى بيئات الألعاب العامة مثل Unity (محرك الألعاب) و Unreal Engine (انظر الروابط أدناه).

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

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

المفاهيم الأساسية

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

يبدأ تنفيذ شجرة السلوك من الجذر الذي يرسل إشارات دورية بتردد معين إلى أبنائه. الإشارة الدورية هي إشارة تمكين تسمح بتنفيذ الابن. عندما يُسمح بتنفيذ عقدة في شجرة السلوك، فإنها تُرجع إلى الأصل حالة " قيد التشغيل " إذا لم ينتهِ تنفيذها بعد، أو "نجاح" إذا حققت هدفها، أو "فشل" في غير ذلك.

عقدة تدفق التحكم

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

عقدة الاختيار (الاحتياطية)

الشكل الأول: تمثيل بياني لتكوين احتياطي من N مهمة.

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

في الشفرة الزائفة، تكون خوارزمية التركيب الاحتياطي كما يلي:

1 for i from 1 to n do 2 حالة الطفل ← علامة (طفل(i)) 3 إذا كانت حالة الطفل = قيد التشغيل 4 العودة الجارية 5 else if childstatus = success 6. نجاح العودة 7 نهاية 8 فشل الإرجاع

عقدة التسلسل

الشكل الثاني. تمثيل بياني لتكوين تسلسلي لـ N مهمة.

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

في الشفرة الزائفة، تكون خوارزمية تركيب التسلسل كما يلي:

1 for i from 1 to n do 2 حالة الطفل ← علامة (طفل(i)) 3 إذا كانت حالة الطفل = قيد التشغيل 4 العودة الجارية 5 else if childstatus = failure 6 فشل في العودة 7 نهاية 8 إرجاع نجاح

تعريف فضاء الحالة الرياضية

من أجل تطبيق أدوات نظرية التحكم على تحليل أشجار السلوك، يمكن تعريفها على أنها ثلاثية. [ 17 ]

تيأنا={وأنا،رأنا،Δت}،{\displaystyle T_{i}=\{f_{i},r_{i},\Delta t\},}

أينأنا∈شمال{\displaystyle i\in \mathbb {N} }هو فهرس الشجرة،وأنا:Rن→Rن{\displaystyle f_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}هو حقل متجه يمثل الطرف الأيمن من معادلة فرق عادية،Δت{\displaystyle \Delta t}هي خطوة زمنية و رأنا:Rن→{Rأنا،Sأنا،Fأنا}{\displaystyle r_{i}:\mathbb {R} ^{n}\rightarrow \{R_{i},S_{i},F_{i}\}}حالة العودة، والتي يمكن أن تكون إما "قيد التشغيل" أو "قيد التشغيل".Rأنا{\displaystyle R_{i}}، نجاحSأنا{\displaystyle S_{i}}أو الفشلFأنا{\displaystyle F_{i}}.

ملاحظة : المهمة عبارة عن شجرة سلوك متدهورة بدون أب ولا ابن.

تنفيذ شجرة السلوك

يتم وصف تنفيذ شجرة السلوك بواسطة معادلات الفرق العادية القياسية التالية:

xك+1(تك+1)=وأنا(xك(تك)){\displaystyle x_{k+1}(t_{k+1})=f_{i}(x_{k}(t_{k}))}

تك+1=تك+Δت{\displaystyle t_{k+1}=t_{k}+\Delta t}

أينك∈شمال{\displaystyle k\in \mathbb {N} }يمثل الزمن المتقطع، و x∈Rن{\displaystyle x\in \mathbb {R} ^{n}}هي فضاء الحالة للنظام الذي تم نمذجته بواسطة شجرة السلوك.

تركيب التسلسل

شجرتان سلوكيتانتيأنا{\displaystyle T_{i}}وتيج{\displaystyle T_{j}}يمكن تجميعها في شجرة سلوك أكثر تعقيدًاتي0{\displaystyle T_{0}}باستخدام عامل التسلسل.

تي0=تسلسل(تيأنا،تيج).{\displaystyle T_{0}={\mbox{sequence}}(T_{i},T_{j}).}

ثم أعد الحالةر0{\displaystyle r_{0}}والحقل المتجهيو0{\displaystyle f_{0}}مرتبط بـتي0{\displaystyle T_{0}}تم تعريفها (لـ)S1{\displaystyle {\mathcal {S}}_{1}}) كما يلي:

ر0(xك)={رج(xك) لو xك∈S1رأنا(xك) خلاف ذلك .{\displaystyle r_{0}(x_{k})={\begin{cases}r_{j}(x_{k})&{\text{ إذا كان }}x_{k}\in {\mathcal {S}}_{1}\\r_{i}(x_{k})&{\text{ خلاف ذلك }}.\end{cases}}}

و0(xك)={وج(xك) لو xك∈S1وأنا(xك) خلاف ذلك .{\displaystyle f_{0}(x_{k})={\begin{cases}f_{j}(x_{k})&{\text{ إذا كان }}x_{k}\in {\mathcal {S}}_{1}\\f_{i}(x_{k})&{\text{ خلاف ذلك }}.\end{cases}}}

انظر أيضاً

مراجع

  1. ↑ كوليدانشيز، ميشيل؛ أوغرين، بيتر (2017). "كيف تُضفي أشجار السلوك طابعًا معياريًا على أنظمة التحكم الهجينة وتُعمم تركيبات السلوك التسلسلي، وبنية التضمين، وأشجار القرار" . معاملات IEEE في مجال الروبوتات . 33 (2): 372-389 . doi : 10.1109/TRO.2016.2633567 . S2CID 9518238 . 
  2. ^ كوليدانشيز، ميشيل؛ أوغرين ، بيتر (2018). أشجار السلوك في الروبوتات والذكاء الاصطناعي: مقدمة . الصحافة اتفاقية حقوق الطفل. أرخايف : 1709.00084 . دوى : 10.1201/9780429489105 . رقم ISBN 978-1-138-59373-2. S2CID 27470659 . 
  3. ↑ إيسلا، د. (2005). "التعامل مع التعقيد في الذكاء الاصطناعي في لعبة هالو 2" . مؤتمر مطوري الألعاب (المجلد 12) . مؤرشف من الأصل في 11 مايو 2012.
  4. ↑ إيسلا، د. (2008). هالو 3 - بناء معركة أفضل .{{cite book}}تم |work=تجاهله ( مساعدة )
  5. 1 2 أجيس، راميرو أ.؛ جوتفريدي، سيباستيان؛ غارسيا، أليخاندرو ج. (2020). "امتداد لأشجار السلوك الموجهة بالأحداث لتسهيل تنسيق العوامل المتعددة غير اللاعبين في ألعاب الفيديو" (ملف PDF) . أنظمة الخبراء مع التطبيقات . 155 (1) 113457. doi : 10.1016/j.eswa.2020.113457 . S2CID 218995637 . 
  6. ↑ ليم، سي يو؛ باومغارتن، ر.؛ كولتون، س. (2010). "أشجار السلوك المتطورة للعبة التجارية DEFCON" (ملف PDF) . تطبيقات الحوسبة التطورية . سلسلة محاضرات في علوم الحاسوب. المجلد 6024. برلين: سبرينغر. الصفحات 100-110 . doi : 10.1007/978-3-642-12239-2_11 . ISBN   978-3-642-12238-5أُرشف من النسخة الأصلية (PDF) بتاريخ 14 يوليو 2020. تم الاطلاع عليه بتاريخ 14 يوليو 2020 .
  7. ↑ أوغرين، بيتر (2012). "زيادة نمطية أنظمة التحكم في الطائرات بدون طيار باستخدام أشجار سلوك ألعاب الكمبيوتر" (ملف PDF) . مؤتمر AIAA للتوجيه والملاحة والتحكم، مينيابوليس، مينيسوتا . الصفحات 13-16 . 
  8. ↑ كوليدانشيز، ميشيل؛ مارزينوتو، أليخاندرو؛ أوغرين، بيتر (2014). "تحليل أداء أشجار السلوك العشوائي" (ملف PDF) . المؤتمر الدولي لهندسة الروبوتات والأتمتة (ICRA) لعام 2014. الصفحات 3265-3272 . doi : 10.1109/ICRA.2014.6907328 . ISBN  978-1-4799-3685-4. S2CID 14719083 . 
  9. ↑ مارزينوتو، أليخاندرو؛ كوليدانشيز، ميشيل؛ سميث، كريستيان؛ أوغرين، بيتر (2014). "نحو إطار عمل موحد لتقنيات التحكم في الروبوتات" (ملف PDF) . المؤتمر الدولي لهندسة الروبوتات والأتمتة (ICRA)، 2014، معهد مهندسي الكهرباء والإلكترونيات .
  10. ↑ كلوكنر، أندرياس. "ربط البلوتوث بالعالم باستخدام منطق الوصف." في مؤتمر AIAA للتوجيه والملاحة والتحكم، بوسطن، ماساتشوستس. 2013.
  11. ^ كلوكنر ، أندرياس (2013). “أشجار السلوك لإدارة مهمة الطائرات بدون طيار”. جي ياهريستاجونج . ص 57 – 68. 
  12. ↑ باغنيل، ج. أندرو؛ كافالكانتي، فيليبي؛ كوي، لي؛ وآخرون (2012). "نظام متكامل للتحكم الآلي في الروبوتات" (ملف PDF) . المؤتمر الدولي للروبوتات والأنظمة الذكية (IROS)، 2012، IEEE/RSJ . IEEE. الصفحات 2955-2962 . doi : 10.1109/IROS.2012.6385888 . hdl : 20.500.11937/14608 . ISBN   978-1-4673-1736-8. S2CID 419179 . 
  13. ↑ ميلينغتون؛ فونج (2009). الذكاء الاصطناعي للألعاب . مطبعة سي آر سي. رقم ISBN 978-0-12-374731-0.
  14. ↑ رابين، س. (2014). الذكاء الاصطناعي الاحترافي للألعاب . مطبعة سي آر سي. رقم ISBN 978-1-4665-6596-8.
  15. ↑ شامباندارد، أليكس جيه؛ دنستان، فيليب (2012). "مجموعة أدوات بدء تشغيل شجرة السلوك" (ملف PDF) . محترفو الذكاء الاصطناعي في الألعاب: خلاصة حكمة محترفي الذكاء الاصطناعي في الألعاب . الصفحات 72-92 . 
  16. ↑ كرافت إيه آي (2015). "مقدمة في قواعد شجرة السلوك - أساسيات القواعد النحوية" . مؤرشف من الأصل بتاريخ 20 سبتمبر 2021. تم الاطلاع عليه بتاريخ 28 يوليو 2021 .
  17. ↑ كوليدانشيز، ميشيل؛ أوغرين، بيتر (2014). "كيف تُضفي أشجار السلوك نمطيةً على المتانة والسلامة في الأنظمة الهجينة" (ملف PDF) . في المؤتمر الدولي للروبوتات والأنظمة الذكية (IROS)، 2014، IEEE/RSJ . IEEE.