Boids

 یک برنامه زندگی مصنوعی است که توسط کریگ رینولدز در سال 1986 ساخته شده است ، که رفتار هجوم پرندگان را شبیه سازی می کند. مقاله وی در این زمینه در سال 1987 در بخش کنفرانس ACM SIGGRAPH منتشر شد. [1] نام "boid" با نسخه کوتاه شده "شی پرنده" مطابقت دارد که اشاره به یک شی پرنده دارد. [2] اتفاقاً "boid" همچنین تلفظ گویشی متروپولیتن نیویورک برای "پرنده" است.

قوانینی که در Boids ساده اعمال می شود:

 جدایش، جدایی

هم ترازی

 انسجام

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

جدایی: برای جلوگیری از شلوغ کردن همسایگان محلی هدایت کنید

تراز بندی: به سمت متوسط ​​عنوان گله های محلی حرکت کنید

انسجام: جهت حرکت به سمت موقعیت متوسط ​​(مرکز جرم) همسایگان محلی را هدایت کنید

می توان قوانین پیچیده تری را اضافه کرد، مانند جلوگیری از مانع و هدف یابی.

از زمان پیشنهاد رینولدز، مدل اساسی به چندین روش مختلف گسترش یافته است. به عنوان مثال ، Delgado-Mata و همکاران [3] مدل اساسی را برای ترکیب اثرات ترس گسترش داد. از بوی بد برای انتقال احساسات بین حیوانات ، از طریق فرمونهایی که به عنوان ذرات در یک گاز انبساط آزاد مدل سازی می شوند ، استفاده شد. هارتمن و بنس [4] نیرویی مکمل برای صف بندی معرفی کردند که آنها آن را تغییر رهبری می نامند. این هدایت فرصت بید را برای تبدیل شدن به یک رهبر و تلاش برای فرار تعریف می کند.

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

چارچوب boids اغلب در گرافیک رایانه ای مورد استفاده قرار می گیرد، نمایشی واقع گرایانه از گله های پرندگان و موجودات دیگر، مانند مدرسه ماهی ها یا گله های حیوانات را ارائه می دهد. به عنوان مثال در بازی ویدیویی Half-Life 1998 برای موجودات پرنده مانند پرنده ای که در پایان بازی در Xen دیده می شد، در پرونده های بازیboid  نامیده می شد.

از مدل Boids می توان برای کنترل مستقیم و تثبیت تیم های وسایل نقلیه زمینی بدون سرنشین ساده (UGV) [5]  یا وسایل هوایی میکرو (MAV) [6] در رباتیک های دسته جمعی استفاده کرد. برای تثبیت تیمهای ناهمگن UAV-UGV، مدل برای استفاده از محلی سازی نسبی پردازنده توسط ساسکا و همکاران سازگار شد. [7]

در زمان پیشنهاد ، رویکرد رینولدز یک گام عظیم به جلو در مقایسه با تکنیک های سنتی مورد استفاده در انیمیشن رایانه ای برای تصاویر متحرک بود. اولین انیمیشن ایجاد شده با این مدل استنلی و استلا در: شکستن یخ (1987) بود ، و پس از آن اولین فیلم سینمایی در فیلم تیم برتون (Batman Returns) بازگشت (1992) با دسته های خفاش رایانه ای تولید شده و ارتش های پنگوئن که در خیابان های گاتهام راهپیمایی می کردند شهر. [8]

 مدل boids برای سایر کاربردهای جالب استفاده شده است. برای برنامه ریزی خودکار ایستگاه های رادیویی چندکاناله اینترنتی اعمال شده است. [9] همچنین برای تجسم اطلاعات [10] و برای کارهای بهینه سازی استفاده شده است. [11]

گله گذاری رفتاری است که هنگام گروهی از پرندگان، که گله خوانده می شوند، در حال جستجوی غذا یا پرواز هستند.

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

این مقاله در مورد مدل سازی رفتار جمع شدن است. از دیدگاه مدل ساز ریاضی ، "هجوم آوردن" حرکت جمعی توسط گروهی از موجودات خودران است و یک رفتار جمعی حیوان است که توسط بسیاری از موجودات زنده مانند پرندگان ، ماهی ها ، باکتری ها و حشرات به نمایش گذاشته می شود. [1] این یک رفتار نوظهور تلقی می شود که ناشی از قوانین ساده ای است که توسط افراد دنبال می شود و شامل هیچ هماهنگی مرکزی نمی شود.

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

 رفتار Flocking در سال 1987 توسط کریگ رینولدز با برنامه شبیه سازی خود، Boids در رایانه شبیه سازی شد. [2] این برنامه عوامل ساده (boids) را شبیه سازی می کند که مجاز به حرکت بر اساس مجموعه ای از قوانین اساسی هستند. نتیجه این کار شبیه گله پرندگان ، دسته ماهی یا دسته ای از حشرات است. [3]

اندازه گیری

اندازه گیری هجوم پرندگان با استفاده از دوربین های پرسرعت [4] و تجزیه و تحلیل رایانه ای برای آزمایش قوانین ساده گله ای که در بالا ذکر شد، انجام شده است. مشخص شده است که آنها به طور کلی در مورد هجوم پرندگان صادق هستند، اما قانون جذب برد طولانی (انسجام) برای نزدیکترین 5-10 همسایه پرنده گله ای اعمال می شود و مستقل از فاصله این همسایگان از پرنده است. علاوه بر این، یک ناهمسانگردی با توجه به این تمایل منسجم وجود دارد، انسجام بیشتری نسبت به همسایگان به طرف پرنده نشان داده می شود، نه در جلو یا عقب. این امر احتمالاً به دلیل میدان دید پرنده در حال پرواز به طرفین بیشتر از مستقیم یا عقب است.

مطالعه اخیر دیگری مبتنی بر تجزیه و تحلیل تصاویر دوربین های پر سرعت گله ها در بالای رم است و با فرض حداقل قوانین رفتاری از یک مدل رایانه ای استفاده می کند. [5] [6] [7] [8]

مدل های اساسی رفتار هجوم آوردن توسط سه قانون ساده کنترل می شود:

 جدایی - از شلوغی همسایگان جلوگیری کنید (دافعه کوتاه برد)

همسویی - به سمت متوسط ​​رفتن به همسایگان بروید

انسجام - هدایت به سمت موقعیت متوسط ​​همسایگان (جاذبه دور برد)

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

 از زمان پیشنهاد رینولدز، مدل اساسی به چندین روش مختلف گسترش یافته است. به عنوان مثال، Delgado-Mata و همکاران. [9] مدل اساسی را برای ترکیب تأثیرات ترس گسترش داد. از بوی بد برای انتقال احساسات بین حیوانات ، از طریق فرمونهایی که به عنوان ذرات در یک گاز انبساط آزاد مدل سازی می شوند ، استفاده شد. هارتمن و بنس [10] نیرویی مکمل برای صف بندی معرفی کردند که آنها آن را تغییر رهبری می نامند. این هدایت شانس رهبر شدن پرنده و تلاش برای فرار را تعریف می کند. هملریک و هیلدنبرانت [11] از جاذبه ، تراز و اجتناب استفاده کردند و این را با تعدادی از صفات سارهای واقعی گسترش دادند: اول ، پرندگان مطابق با آیرودینامیک بال ثابت پرواز می کنند ، در حالی که هنگام چرخش می غلتند (بنابراین از دست دادن بالابر). دوم ، آنها با تعداد محدودی از همسایگان 7 نفره (مانند سارهای واقعی) هماهنگی دارند. سوم ، آنها سعی می کنند بالای یک مکان خواب بمانند (مانند سارها در سحر) ، و وقتی اتفاق می افتد که از محل خواب به سمت خارج حرکت کنند ، با چرخش به آن باز می گردند چهارم ، آنها با سرعت ثابت نسبی حرکت می کنند. نویسندگان نشان دادند که خصوصیات رفتار پرواز و همچنین تعداد زیادی گله و تعداد کم شرکای متقابل برای ایجاد شکل متغیر گله های سارها ضروری است.

پیچیدگی

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

یک پیاده سازی اساسی از یک الگوریتم دسته بندی دارای پیچیدگی است {O (n ^ {2})} O (n ^ {2}) - هر پرنده در جستجوی همه پرندگان دیگر برای یافتن آنهایی است که در محیط آن قرار می گیرند.

پیشرفت های احتمالی:

 تقسیم فضایی bin-lattice. کل منطقه ای که گله می تواند در آن حرکت کند، به سطل های مختلفی تقسیم شده است. هر سطل زباله کدام پرندگان را در خود ذخیره می کند. هر بار که یک پرنده از این سطل به سطل دیگر منتقل می شود ، شبکه باید به روز شود.

مثال: شبکه 2D (3D) در یک شبیه سازی انبوه 2D (3D).

پیچیدگی: { O (nk)} O (nk) ، k تعداد سطل های زباله اطراف است که باید در نظر گرفت. درست زمانی که سطل پرنده در { O (1)} O (1) پیدا می شود

لی اسپکتور، جون کلاین، کریس پری و مارک فاینشتاین ظهور رفتار جمعی را در سیستم های محاسبات تکاملی بررسی کردند. [12]

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

پیچیدگی

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

یک پیاده سازی اساسی از یک الگوریتم دسته بندی دارای پیچیدگی است {\ displaystyle O (n ^ {2})} O (n ^ {2}) - هر پرنده در جستجوی همه پرندگان دیگر برای یافتن آنهایی است که در محیط آن قرار می گیرند.

پیشرفت های احتمالی:

 تقسیم فضایی bin-lattice. کل منطقه ای که گله می تواند در آن حرکت کند ، به سطل های مختلفی تقسیم شده است. هر سطل زباله کدام پرندگان را در خود ذخیره می کند. هر بار که یک پرنده از این سطل به سطل دیگر منتقل می شود ، شبکه باید به روز شود.

مثال: شبکه 2D (3D) در یک شبیه سازی انبوه 2D (3D).

پیچیدگی: { O (nk)} O (nk) ، k تعداد سطل های زباله اطراف است که باید در نظر گرفت. درست زمانی که سطل پرنده در { O (1)} O (1) پیدا می شود

لی اسپکتور، جون کلاین، کریس پری و مارک فاینشتاین ظهور رفتار جمعی را در سیستم های محاسبات تکاملی بررسی کردند. [12]

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