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

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

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

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

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

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

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

مفاهیم کلیدی

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

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

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

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

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

شکل 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

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

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

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

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

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

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

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

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

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

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

ترکیب توالی

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

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

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

${\displaystyle 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}}}$

${\displaystyle 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
• درختان رفتار برای هوش مصنوعی: نحوه عملکرد آنها
• درختان رفتار: هوش مصنوعی ساده و در عین حال قدرتمند برای ربات شما