درخت رفتار (هوش مصنوعی، رباتیک و کنترل)
درخت رفتار یک مدل ریاضیاتی از اجرای نقشه و طرح است که در علوم کامپیوتر ، رباتیک ، سیستم های کنترل و بازی های ویدیویی استفاده می شود. آن ها جابجایی های بین یک مجموعه محدود از وظایف را به روش مدولار توصیف می کنند. قدرت آنها از قابلیت آنها در ایجاد وظایف بسیار پیچیده که متشکل از کارهای ساده میباشد،ناشی می شود بدون اینکه از نحوه اجرای وظایف ساده نگران باشند . درختان رفتار شباهت هایی با ماشین های حالات متناهی دارند با این تفاوت اساسی که عنصر اصلی سازنده یک رفتار،یک وظیفه میباشد، نه یک حالت. درک ساده ی انسان باعث می شود که درختان رفتار ، کمتر دچار خطا شوند و در جامعه توسعه دهندگان بازی بسیار محبوب باشند. همچنین درختان رفتار چندین معماری کنترل دیگر را تعمیم می دهند. از نظر ریاضی ، آنها گراف جهتدار غیرمدور به حساب می آیند. درختان رفتار از صنعت بازی های رایانه ای به عنوان ابزاری قدرتمند برای مدل سازی رفتار شخصیت های غیرقابل بازی (NPC) نشات گرفته اند. آنها به طور گسترده ای در بازی های ویدیویی رده بالا مانند Halo ، Bioshock و Spore مورد استفاده قرار گرفته‌اند . فعالیت ها و پژوهش های اخیر ،درختان رفتار را به عنوان یک چارچوب کنترل چند مأموریتی برای پهپاد ها ، ربات های پیچیده ، بازوی مکانیکی ربات و سیستم های چند روبات پیشنهاد می کنند. درختان رفتاری اکنون به بلوغی رسیده اند که در کتابهای درسی هوش مصنوعی بازی ویدیویی ، و همچنین در محیط های بازی عمومی مانند Unity (موتور بازی) و Unreal Engine (تیم های غیر واقعی) به آنها پرداخته شود.
درختان رفتاری به خاطر الگوی توسعه ی خود ، محبوب شدند: این که بتوانند فقط با برنامه ریزی اقدامات NPC و سپس طراحی یک ساختار درختی (معمولاً از طریق کشیدن و رها کردن ) که گره های برگ آن ها ، اعمال هستند و گره های داخلی ، تصمیم گیری NPC را تعیین می کنند ، رفتاری پیچیده را ایجاد کنند. از نظر بصری درختان رفتاری شهودی اند و به آسانی طراحی ، آزمایش و اشکال زدایی می شوند و نسبت به دیگر شیوه های ایجاد رفتار مدولار بودن، مقیاس پذیری و قابلیت استفاده مجدد بیشتر فراهم می کنند .
در گذر سالها ، پیاده سازی های متنوع درختان رفتاری ، هم از نظر کارایی و بهره وری و هم از نظر توانایی برای تأمین خواسته های صنعت ، بهبود می یافتند ، تا اینکه به درختان رفتار رویداد محور تکامل پیدا کردند . درختان رفتار رویداد محور ، با تغییر اینکه درخت چگونه به صورت درونی به اجرای خود رسیدگی میکند ، و با معرفی نوع جدیدی از گره که می تواند به حوادث واکنش نشان دهد و گره های در حال اجرا را سقط کند وبیندازد ، برخی از مسائل مقیاس پذیری درختان رفتار کلاسیک را حل کردند. امروزه ، مفهوم درخت رفتار رویداد محور یک استاندارد است و در بیشتر پیاده سازی ها استفاده می شود ، حتی اگر برای سادگی هنوز "درختان رفتار" نامیده شوند.
یک درخت رفتاری از نظر گرافیکی به عنوان یک درخت جهت دار نشان داده می شود که در آن ، گره ها به عنوان ریشه ، گره های روند کنترلی یا گره های عملیات(وظایف) طبقه بندی شده اند. برای هر جفت گره متصل به هم ، گره برونگرا یا بیرونی والد و گره ورودی یا درونی فرزند نامیده می شود. ریشه فاقد والد است و دقیقاً یک فرزند دارد ، گره های روند کنترلی دارای یک والد و حداقل یک فرزند و گره های عملیات دارای یک والد و بدون فرزند هستند. از لحاظ گرافیکی(از منظر گراف) ، فرزندان گره روند کنترل در زیر آن ، به ترتیب از چپ به راست قرار می گیرند .
اغازعملیات یک درخت رفتار از ریشه ی آن است ، آن هم هنگامی که به گره های فرزند خود (تیک) نشان معین را ارسال کند. زمانی که به عملیات یک گره در درخت رفتار اجازه داده شود، آن گره چنانچه عملیات آن هنوز به پایان نرسیده باشد ، به والدش یک وضعیت در حال اجرا را برمی گرداند و اگر به هدف خود برسد وضعیت موفقیت را ، به والدش برمی گرداند در غیر این صورت وضعیت شکست را برمی گرداند.
از یک گره ی روند کنترل برای کنترل کردن وظایف فرعی که از آن تشکیل شده است ، استفاده میشود . یک گره روند کنترل ممکن است یک گره انتخاب کننده (بازگشتی) یا یک گره توالی باشد. هر یک از آنها در نوبت خود وظایف فرعی خود را انجام می دهند. وقتی که یک وظیفه فرعی به پایان میرسد و وضعیت خود (موفقیت یا شکست) را برمی گرداند ، گره روند کنترل انتخاب می کند که آیا وظیفه فرعی بعدی را اجرا کند یا خیر.
از گره های Fallback برای یافتن و اجرای اولین گره ی فرزندی که شکست نمی‌خورد (وضعیت شکست را برنمی گرداند) استفاده می شود. گره Fallback بلافاصله توسط کد وضعیت موفقیت یا در حال اجرا بودن را، زمانی که یکی از فرزندانش وضعیت موفقیت یا وضعیت در حال اجرا بودن را بازگرداند ، برمی گرداند (شکل I و شبه کد زیر را ببینید). کودکان از به ترتیب از چپ به راست علامت گذاری می شوند.
در شبه کد زیر ، الگوریتمی برای ترکیب بندی fallback آمده است :
گره های توالی برای یافتن و اجرای اولین فرزندی که هنوز موفق نشده است استفاده می شوند. یک گره توالی هنگامی که یکی از فرزندانش وضعیت خرابی یا در حال اجرا را بازگرداند ، بلافاصله کد وضعیت شکست یا کد وضعیت در حال اجرا را برمی گرداند (شکل 2 و شبه کد زیر را ببینید). فرزندان به ترتیب از چپ به راست علامت گذاری می شوند.
در شبه کد زیر ،الگوریتمی برای ترکیب بندی گره توالی آمده است :
به منظور استفاده از ابزارهای تئوری کنترل برای تجزیه و تحلیل درختان رفتار ، آنها می توان را به صورت سه تایی تعریف کرد.
formula_1
که formula_2 شاخص درخت است ، formula_3 یک میدان برداری است که از سمت راست یک معادله تفاضلی عادی نشان می دهد ، formula_4 یک واحد زمانی است و formula_5 وضعیت بازگشت است که می تواند برابر با در حال اجرا formula_6 ، موفقیت formula_7 ، یا شکست formula_8 باشد .
توجه : وظیفه ، یک درخت رفتاری منحط است که هیچ والد و فرزندی ندارد.
عملیات یک درخت رفتار توسط معادلات استاندارد تفاضلی معمول زیر شرح داده شده است:
formula_9
formula_10
جایی که formula_11 زمان مجزا را نشان می دهد ، و formula_12 فضای حالت سیستم است که توسط درخت رفتار مدل شده است.
دو درخت رفتار formula_13 و formula_14 می توانند با استفاده از یک عملگر Sequence به یک درخت رفتار پیچیده تر formula_15 تبدیل شوند.
formula_16
سپس وضعیت formula_17 و قسمت بردار formula_18 مرتبط با formula_15 تعریف شده‌اند (برای formula_20 ) را برمی گرداند ، به شرح زیر است:
formula_21
formula_22