درخت رفتار (هوش مصنوعی، رباتیک و کنترل)

درخت رفتار (Behavior Tree) روشی ساده و مؤثر برای طراحی رفتارهای پیچیده در ربات‌ها و هوش مصنوعی است.

درخت رفتار یک ساختار درختی است که از گره‌های مختلف تشکیل شده و برای کنترل تصمیم‌گیری در سامانه‌های خودکار مانند ربات‌ها و شخصیت‌های بازی‌های ویدیویی استفاده می‌شود.

این درخت شامل گره‌های کنترلی (مانند توالی و انتخاب) و گره‌های اجرایی (مانند اقدامات و شرایط) است. گره‌های کنترلی تعیین می‌کنند که کدام گره‌های فرعی باید اجرا شوند، در حالی که گره‌های اجرایی وظایف خاصی را انجام می‌دهند.

درخت‌های رفتار به دلیل ساختار ماژولار و قابلیت استفاده مجدد، امکان طراحی و نگهداری آسان‌تر رفتارهای پیچیده را فراهم می‌کنند. همچنین، آن‌ها به توسعه‌دهندگان اجازه می‌دهند تا رفتارهای سیستم را به‌صورت بصری طراحی و اشکال‌زدایی کنند.

درخت‌های رفتار ابتدا در صنعت بازی‌های ویدیویی برای کنترل شخصیت‌های غیرقابل‌بازی (NPCs) مورد استفاده قرار گرفتند و سپس در حوزه‌های دیگر مانند رباتیک، هواپیماهای بدون سرنشین (پهپادها) و سامانه‌های کنترل پیچیده گسترش یافتند.

مدل رفتار درختی طرح جستجو و درک یک ربات دو بازو.

پیش‌زمینه و پیدایش

درختان رفتار از صنعت بازی‌های رایانه‌ای به‌عنوان ابزاری قدرتمند برای مدل‌سازی رفتار شخصیت‌های غیرقابل‌بازی (NPC) منشأ گرفته‌اند. آن‌ها به‌طور گسترده در بازی‌های ویدیویی رده‌بالا مانند Halo، Bioshock و Spore مورد استفاده قرار گرفته‌اند. فعالیت‌ها و پژوهش‌های اخیر، درختان رفتار را به‌عنوان چارچوبی برای کنترل چند مأموریتی پهپادها، ربات‌های پیچیده، بازوی مکانیکی ربات و سامانه‌های چندرباته پیشنهاد می‌کنند. درختان رفتاری اکنون به بلوغی رسیده‌اند که در کتاب‌های درسی هوش مصنوعی بازی‌های ویدیویی، و همچنین در محیط‌های بازی عمومی مانند Unity (موتور بازی) و Unreal Engine (تیم‌های غیرواقعی) به آن‌ها پرداخته می‌شود.

درختان رفتاری به‌دلیل الگوی توسعهٔ خود محبوب شده‌اند: اینکه بتوان با برنامه‌ریزی اقدامات NPC و سپس طراحی یک ساختار درختی (معمولاً از طریق کشیدن و رها کردن) که گره‌های برگ آن‌ها اعمال هستند و گره‌های داخلی تصمیم‌گیری NPC را تعیین می‌کنند، رفتاری پیچیده ایجاد کرد. از نظر بصری، درختان رفتاری شهودی‌اند و به‌آسانی طراحی، آزمایش و اشکال‌زدایی می‌شوند و نسبت به دیگر شیوه‌های ایجاد رفتار، ماژولار بودن، مقیاس‌پذیری و قابلیت استفادهٔ مجدد بیشتری فراهم می‌کنند.

در گذر سال‌ها، پیاده‌سازی‌های متنوع درختان رفتاری، هم از نظر کارایی و بهره‌وری و هم از نظر توانایی در تأمین خواسته‌های صنعت، بهبود یافتند تا اینکه به درختان رفتار رویدادمحور تکامل پیدا کردند. درختان رفتار رویدادمحور، با تغییر در شیوهٔ اجرای درونی درخت و با معرفی نوعی جدید از گره که می‌تواند به رویدادها واکنش نشان دهد و گره‌های در حال اجرا را متوقف کند، برخی از مسائل مقیاس‌پذیری در درختان رفتار کلاسیک را حل کردند. امروزه، مفهوم درخت رفتار رویدادمحور به‌عنوان یک استاندارد شناخته می‌شود و در بیشتر پیاده‌سازی‌ها به‌کار می‌رود، حتی اگر همچنان برای سادگی "درختان رفتار" نامیده شوند.

مفاهیم کلیدی

درخت رفتاری به‌صورت گرافیکی به‌صورت درختی جهت‌دار نمایش داده می‌شود که در آن، گره‌ها به‌عنوان ریشه، گره‌های روند کنترلی یا گره‌های عملیات (وظایف) طبقه‌بندی شده‌اند. برای هر جفت گره متصل به هم، گره بیرونی «والد» و گره درونی «فرزند» نامیده می‌شود. ریشه فاقد والد است و دقیقاً یک فرزند دارد؛ گره‌های روند کنترلی دارای یک والد و دست‌کم یک فرزند هستند و گره‌های عملیات دارای یک والد و بدون فرزند هستند. از لحاظ گرافیکی (از منظر گراف)، فرزندان گره‌های روند کنترل در زیر آن، به‌ترتیب از چپ به راست قرار می‌گیرند.

آغاز عملیات یک درخت رفتار از ریشهٔ آن است، آن‌هم هنگامی که به گره‌های فرزند خود «تیک» (tick) یا علامت مشخصی را ارسال می‌کند. زمانی که به اجرای یک گره در درخت رفتار اجازه داده شود، آن گره، اگر عملیاتش هنوز پایان نیافته باشد، وضعیت «در حال اجرا» را به والدش بازمی‌گرداند؛ اگر به هدف برسد، وضعیت «موفقیت» و در غیر این صورت، وضعیت «شکست» را بازمی‌گرداند.

گرهٔ روند کنترل

از یک گرهٔ روند کنترل برای کنترل وظایف فرعیِ زیرمجموعه‌اش استفاده می‌شود. این گره ممکن است یک «گرهٔ انتخاب‌کننده» (بازگشتی) یا یک «گرهٔ توالی» باشد. هرکدام از آن‌ها وظایف فرعی‌شان را به‌ترتیب اجرا می‌کنند. پس از اجرای هر وظیفهٔ فرعی و بازگشت وضعیت (موفقیت یا شکست)، گرهٔ کنترل تصمیم می‌گیرد آیا وظیفهٔ بعدی اجرا شود یا خیر.

==== گرهٔ انتخاب‌کننده (بازگشتی) ====

شکل I: نمایش گرافیکی یک ترکیب بازگشتی از N وظیفه

از گره‌های Fallback برای یافتن و اجرای اولین گرهٔ فرزندی که شکست نمی‌خورد (وضعیت شکست برنمی‌گرداند) استفاده می‌شود. گرهٔ Fallback بلافاصله وضعیت «موفقیت» یا «در حال اجرا» را بازمی‌گرداند، به‌محض اینکه یکی از فرزندانش چنین وضعیتی را بازگرداند (شکل I و شبه‌کد زیر را ببینید). فرزندان از چپ به راست علامت‌گذاری می‌شوند.

در شبه کد زیر ، الگوریتمی برای ترکیب بندی fallback آمده است :

1 for i from 1 to n do
2 childstatus ← Tick(child(i))
3 if childstatus = running
4 return running
5 else if childstatus = success
6 return success
7 end
8 return failure

گره توالی

شکل دوم نمایش گرافیکی ترکیب توالی N وظیفه.

گره های توالی برای یافتن و اجرای اولین فرزندی که هنوز موفق نشده است استفاده می شوند. یک گره توالی هنگامی که یکی از فرزندانش وضعیت خرابی یا در حال اجرا را بازگرداند ، بلافاصله کد وضعیت شکست یا کد وضعیت در حال اجرا را برمی گرداند (شکل 2 و شبه کد زیر را ببینید). فرزندان به ترتیب از چپ به راست علامت گذاری می شوند.

در شبه کد زیر ،الگوریتمی برای ترکیب بندی گره توالی آمده است :

1 for i from 1 to n do
2 childstatus ← Tick(child(i))
3 if childstatus = running
4 return running
5 else if childstatus = failure
6 return failure
7 end
8 return success

تعریف ریاضی فضای حالت

به منظور استفاده از ابزارهای تئوری کنترل برای تجزیه و تحلیل درختان رفتار ، آنها می توان را به صورت سه تایی تعریف کرد.

$T_{i}=\{f_{i},r_{i},\Delta t\},$

که $i\in \mathbb {N}$ شاخص درخت است ، $f_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}$ یک میدان برداری است که از سمت راست یک معادله تفاضلی عادی نشان می دهد ، $\Delta t$ یک واحد زمانی است و $r_{i}:\mathbb {R} ^{n}\rightarrow \{R_{i},S_{i},F_{i}\}$ وضعیت بازگشت است که می تواند برابر با در حال اجرا $R_{i}$ ، موفقیت $S_{i}$ ، یا شکست $F_{i}$ باشد .

توجه : وظیفه ، یک درخت رفتاری منحط است که هیچ والد و فرزندی ندارد.

عملیات درخت رفتار

عملیات یک درخت رفتار توسط معادلات استاندارد تفاضلی معمول زیر شرح داده شده است:

$x_{k+t}(t_{k+1})=f_{i}(x_{k}(t_{k}))$

$t_{k+1}=t_{k}+\Delta t$

جایی که $k\in \mathbb {N}$ زمان مجزا را نشان می دهد ، و $x\in \mathbb {R} ^{n}$ فضای حالت سیستم است که توسط درخت رفتار مدل شده است.

ترکیب توالی

دو درخت رفتار $T_{i}$ و $T_{j}$ می توانند با استفاده از یک عملگر Sequence به یک درخت رفتار پیچیده تر $T_{0}$ تبدیل شوند.

$T_{0}={\mbox{sequence}}(T_{i},T_{j}).$

سپس وضعیت $r_{0}$ و قسمت بردار $f_{0}$ مرتبط با $T_{0}$ تعریف شده‌اند (برای ${\mathcal {S}}_{1}$ ) را برمی گرداند ، به شرح زیر است:

$r_{0}(x_{k})={\begin{cases}r_{j}(x_{k})&{\text{ if }}x_{k}\in {\mathcal {S}}_{1}\\r_{i}(x_{k})&{\text{ otherwise }}.\end{cases}}$

$f_{0}(x_{k})={\begin{cases}f_{j}(x_{k})&{\text{ if }}x_{k}\in {\mathcal {S}}_{1}\\f_{i}(x_{k})&{\text{ otherwise }}.\end{cases}}$

جستارهای وابسته

• درخت تصمیم
• سیستم ترکیبی
• معماری فرعی

پیوند به بیرون

• کتابخانه درخت رفتار ROS
• مستندات درخت رفتار Unreal Engine 4