یک الگوریتم مبتنی بر استراتژی برای حرکت اهداف در یک محیط با چندین عامل

بیشتر مطالعات در زمینه الگوریتم های جستجو فقط به دنبال کردن عوامل متمرکز شده است ، در حالی که نسبتاً کمتری به الگوریتم های هدف مورد توجه قرار گرفته است که از استراتژی هایی برای فرار از چندین عامل پیگیری استفاده می کنند. در این مطالعه ، یک الگوریتم هدفمندترین هدف ، Trailmax ، برای مشکلات مختلف مسیریابی عامل افزایش یافته و پیاده سازی شده است. الگوریتم ارائه شده با هدف حداکثر رساندن زمان ضبط در صورت امکان تا زمان وقوع. تجزیه و تحلیل تجربی در معیارهای بازی مبتنی بر شبکه انجام می شود ، اندازه گیری هزینه ضبط ، موفقیت فرار و تجزیه و تحلیل آماری نتایج انجام می شود. الگوریتم جدید ، Trailmax چند تعقیب کننده ، مراحل فرار را تا زمان ضبط در مقایسه با الگوریتم های هدف موجود دو برابر می کند و موفقیت فرار هدف را 13 ٪ و در برخی موارد فردی 37 ٪ افزایش می دهد.

روی نسخه خطی کار می کنید؟

معرفی

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

بسیاری از الگوریتم های مناسب برای دنبال کردن نمایندگان در حوزه های بازی های ویدئویی و رایانه ای ، روباتیک ، انبارها [1] و برنامه های نظامی و نظارتی پیشنهاد شده است [2]. برخی از این الگوریتم ها برای یک عامل واحد مانند MTS [3] ، d* lite [4] یا RTTEs [5] و برخی از آنها چند عامل هستند ، به عنوان مثال ، FAR [6] ، WHCA* [7] ، CBS[8] و MAMT [9]. این الگوریتم ها با هدف یافتن کوتاهترین مسیر به محل (های) هدف. در حالی که کوتاهترین مسیر مهم است ، زمان اجرا نیز ضروری است ، همانطور که توسط الگوریتم های اکتشافی در زمان واقعی در نظر گرفته می شود [10].

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

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

الگوریتم های هدف که وجود دارد معمولاً دارای استراتژی هایی مانند حداکثر رساندن فاصله فرار [12] ، حرکات تصادفی به سمت موقعیت های انتخاب شده و انسداد شده برای فرار از اسیر [13] یا در یک رویکرد مدرن به نام trailmax ، حداکثر رساندنزمان بقا در محیط با در نظر گرفتن حرکات احتمالی پیگیری عوامل در هر مرحله زمانی [14].

مشکلات مسیر چند عامل (MAPF) به تفصیل در ادبیات مورد تجزیه و تحلیل قرار گرفته است [15]. این مشکلات به عنوان NP سخت شناخته شده است [1]. به عنوان نمونه ای از چنین مشکلی در یک بازی ویدیویی زمانی است که همه عوامل غیر بازیکن باید در یک مسیر بدون درگیری در یک محیط استاتیک یا پویا از محل شروع به مکان هدف حرکت کنند [16].

الگوریتم های توسعه یافته برای حرکت ، به عبارت دیگر فرار از اهداف ، می توانند مطالعه تجربی مشکلات MAPF را معنی دار تر ، مفید و چالش برانگیزتر کنند. بنابراین ، چگونه می توانیم در موارد موجود پیشرفت کنیم؟ما قبلاً الگوریتم [17] را بر اساس Trailmax معرفی کردیم که می تواند برای چندین هدف متحرک برای فرار از چندین عامل در یک محیط پویا استفاده شود. طراحی خوب چنین الگوریتم می تواند به اهداف کمک کند تا از لحاظ هوشمندانه تر ، عقلانی و با روشی مانند انسان فرار کنند.

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

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

کارهای مرتبط

در این بخش چندین الگوریتم هدف موجود در ادبیات ارائه شده است. در زیر شرح مختصری از هر الگوریتم است.

الگوریتم های هدف

اگرچه تحقیقات زیادی در ادبیات با تأکید بر الگوریتم ها برای دنبال کردن عوامل وجود دارد ، اما مطالعات کمی در مورد الگوریتم ها برای اهداف موبایل انجام می شود. الگوریتم A* یک نمونه کلاسیک است که به عنوان الگوریتم برای بسیاری از عوامل دنبال کننده و همچنین الگوریتم های هدف اجرا می شود [15].

Trailmax. Trailmax یک الگوریتم هوشمند است که مبتنی بر یک استراتژی است. این مسیری را برای هدف با توجه به حرکات احتمالی عامل دنبال کننده ایجاد می کند ، یعنی با گسترش گره های همسایه فعلی و مجاور آن به طور همزمان ، مسیرهای ممکن را محاسبه می کند [14].

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

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

این یک الگوریتم پیشرفته استراتژی هدف است که بهترین عملکرد را در برابر عوامل تعقیب انجام می دهد ، با هدف این که اهداف را کمتر قابل جذب یا دشوارتر می کند [12].

مینیماکسهنگامی که به عنوان الگوریتم هدف استفاده می شود ، یک جستجوی مخالف را انجام می دهد که متناوب بین تعقیب کنندگان و هدف حرکت می کند. هنگامی که نماینده تعقیب کننده به حالت هدف نزدیک می شود ، هدف خود را از وضعیت نماینده دنبال می کند. برای سریعتر کردن الگوریتم ، Minimax با جستجوی هرس Alph a-Beta اجرا می شود ، جایی که آلفا (α) و بتا (β) به طور مداوم به روز می شوند تا از اکتشاف شاخه های زیر قطبی جلوگیری شود [18]. عمق مورد استفاده 5 است ، یعنی نتایج پس از حداکثر 5 حرکت هر طرف در نظر گرفته می شود.

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

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

فرار سادهالگوریتم دیگر برای اهداف ، Flee Simple (SF) است که می تواند برای فرار از عوامل تعقیب کننده به حالتهای از پیش تعریف شده روی نقشه استفاده شود [19]. الگوریتم SF به شرح زیر است. در ابتدای جستجو ، هدف برخی از مکان های تصادفی را روی نقشه مشخص می کند. هنگامی که هدف شروع به حرکت می کند ، به دورترین مکان دور از تعقیب کنندگان حرکت می کند. برای از بین بردن عوامل تعقیب کننده ، مانند الگوریتم های اکتشافی افزایشی ، d* lite [4] و MT-Agraptive a* [20] ، که می تواند از حالت هدف جستجو کند ، جهت به سمت مکان انتخاب شده در هر پنج مرحله تغییر می کند و اگر اگراین دورترین مکان است ، همچنان حرکت می کند. تعداد مکانهای موجود در نقشه و تعداد مراحل قبل از تغییر ، پارامترهای الگوریتم است.

حریص . این الگوریتم استاندارد حریص است که به طور مکرر بهترین انتخاب های بهینه محلی را ایجاد می کند که به امید ، منجر به راه حل های جهانی می شود. این یک رویکرد ساده و سریع برای حل یک مشکل است که از اکتشافی های زیر بهینه و به راحتی محاسبه می شود [21].

حریص با حداکثر رساندن شکاف به سمت تعقیب کنندگان ، فاصله منهتن تجمعی را طی می کند. این گزینه ها را ارزیابی می کند و به آن حالت منتقل می شود. هنگامی که در آن مرحله قرار دارد ، در صورت عدم دسترسی به حداکثر حالت دیگر ، تا زمان اسیر باقی می ماند [19].

الگوریتم های هدف ، بدون استراتژی ، اما در نظر گرفتن موقعیت یک عامل دنبال کننده ، راه خود را به دورترین حالت ممکن می کشند. هنگامی که یک هدف از تعقیب کننده فرار می کند ، که در سناریوهای چند عامل ، گاهی اوقات ممکن است در مسیر سایر عوامل تعقیب کننده قرار بگیرد. این مسئله در چارچوب های MAPF ایجاد می کند. برای جلوگیری از این محدودیت ، مطالعه در این مقاله همه تعقیب کنندگان را در نظر می گیرد و این رویکرد جدید یک استراتژی برنده برای هدف فراهم می کند.

دنبال کردن الگوریتم ها

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

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

این یک رویکرد گسترده است و تغییرات آن با تکنیک های مختلف جستجوی توصیف شده است [22].

stmta*. در مواردی که بیش از یک هدف وجود داشته باشد ، یک استراتژی مؤثر برای دنبال کردن عوامل به پیروزی در بازی کمک می کند. الگوریتم استراتژی چندگانه Target A* (STMTA*) از روش هایی برای اختصاص هوشمندانه به اهداف به اهداف استفاده می کند تا فرصتی برای ضبط اهداف سریعتر ایجاد کند [23]. تمام مسیرها به سمت اهداف محاسبه می شوند و بر اساس استراتژی داده شده ، ترکیب بهینه انتخاب می شود. پس از تعیین استراتژی ، عوامل دنبال کننده اهداف خود را می دانند ، همه عوامل از الگوریتم A* برای حرکت به سمت اهداف استفاده می کنند.

مسیرها مسافتی از تعقیب کننده تا هدف است. بسته به استراتژی واگذاری ، فاصله بین جفت های هدفمند تعقیب کننده ترجیح داده می شود. برای تکلیف اولیه ، هزینه جمع بندی یا معیارهای هزینه مختلط به حداقل می رسد [12]. جمع بندی جمع آوری تمام مسافت ها (N) و هزینه های مختلط طولانی ترین مسافت ، Makespan (M) را می گیرد اما در موارد شکست کراوات ، از مجموع مسافت ها استفاده می کند. رویکرد ذکر شده پس از اسیر شدن اهداف اختصاصی آنها ، به تسهیل مجدد مأمورین توجه نمی کند.

انواع این الگوریتم با استفاده از معیارهای مختلف مانند دوقلو هزینه ، پوشش هزینه و وزنه برداری ، معرفی و توسعه داده شد [24]. STMTA* از این سه معیار در طول آزمایشات استفاده می کند زیرا مطالعه قبلی عملکرد آنها را اندازه گیری کرده است و به طور کلی ، آنها نتایج بهتری نسبت به سایر معیارهای هزینه تولید می کنند. در طول آزمایشات ، در صورت گرفتاری هر هدف ، عامل تعقیب بسته به استراتژی دنبال شده به هدف دیگری منتقل می شود.

معیار هزینه دوقلو ، مجموع مسافت n را با makespan m ، ((n* m) ) ضرب می کند. در مواقع ، اگر یک کراوات لازم باشد ، میانگین N و M گرفته می شود.

معیار وزن وزن این مقادیر را با درصد معین ضرب می کند ، در کل 100 ٪ و آنها را اضافه می کند. در طول آزمایشات ، از نسبت 50/50 برای معیار وزنه بردار ، ((n*0. 5)+(m*0. 5) ) استفاده شد. ترکیبی با کمترین مقدار برای معیارهای دوقلو و هزینه و وزن انتخاب شده است.

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

تعقیب کننده های متعدد Trailmax: رویکرد پیشنهادی

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

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

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

به همین دلیل خاص ، یک الگوریتم هدف که قادر به شناسایی نزدیک به عوامل مختلف و فرار از همه تعقیب کنندگان باشد ، یک الگوریتم جدید ، به نام Trailmax چند تعقیب کننده (MPTM) ، توسعه یافته است.

الگوریتم MPTM از یک روش مشابه به عنوان Trailmax استفاده می کند اما برای مشکلات MAPF تقویت شده است. دو مزیت احتمالی وجود دارد که می تواند از گسترش Trailmax به مشکلات MAPF ناشی شود. اول ، هدف می تواند محل وضعیت سایر اهداف را شناسایی کرده و با آنها همکاری کند. دوم ، این می تواند فرار را نه تنها از یک عامل تعقیب کننده بلکه از هر یک از نمایندگان فرار ، تضمین کند. در اینجا تمرکز روی شماره دوم است. این جامع است ، به این معنی که تمام حرکات ممکن از عوامل را در نظر می گیرد. بنابراین ، نسبتاً محاسباتی فشرده است و در صورت وجود راه حل ارائه می دهد.

الگوریتم

کد شبه برای الگوریتم MPTM در الگوریتم 1 به تصویر کشیده شده است. ابتدا ، مکان های فعلی همه بازیکنان (تعقیب کنندگان و هدف) باید در خط 2 آغاز شوند. مرحله بعدی گروه بندی همه بازیکنان با توجه به نقش آنها و پیوستن آنها است. موقعیت در صف های مربوطه ، همه تعقیب کنندگان به pursuer_node_queue و یک هدف به target_node_queue. در این مرحله ، همه بازیکنان هزینه تجمعی صفر ، خطوط 3 تا 5 را خواهند داشت تا بتوانید کد را آسان تر کنید ، هر هزینه حرکت برابر با یک خواهد بود ، مگر اینکه در انتظار عمل باشد ، پس صفر است. این با این فرض است که هیچ فاصله اکتیله ای وجود ندارد. با این حال ، این الگوریتم با سرعت و مسافت های مختلف کار می کند.

این الگوریتم چهار لیست مختلف دارد. target_node_queue و pursuer_node_queue حاوی گره های گسترده و بازدید شده مانند حالت فعلی یا کشورهای همسایه برای هدف و تعقیب کنندگان است. لیست های target_closed و pursuer_closed حاوی حالت هایی هستند که قبلاً توسط بازیکنان بازدید و اشغال شده اند.

از آنجا که این الگوریتم هدف است ، در خط 7 ، ابتدا شروع می شود تا بررسی کند که آیا قبلاً گرفتار شده است یا خیر. در صورت وجود گره های هدف در Target_Node_queue ، حلقه ها را حلقه کنید. از آنجا که این اولین قدم است ، فقط حاوی موقعیت فعلی هدف است. سپس ، هزینه تجمعی C ، بالاترین مقدار را برای هدف C محاسبه می کند_حرفو تعقیب کنندگان ج_آدر خطوط 9 و 10 اگر C_حرفپایین تر یا برابر با C است_آ، سپس هدف گره های خود را گسترش می دهد ، خط 11.

در طول گسترش گره ها برای اهداف در خطوط 12-15، ابتدا گره هدف از صف_ target_node_ حذف می شود و اگر قبلاً در لیست نباشد و در لیست pursuer_closed نباشد، در داخل target_closed قرار می گیرد. همچنین بررسی می کند که آیا گره والد هدف در pursuer_closed نیست. هدف از طریق همسایگان مجاور موجود خود حلقه می زند و آنها را به target_node_queue اضافه می کند. این مراحل تا زمانی تکرار می شوند که هیچ حالتی برای گسترش باقی نماند. گره ها مانند جستجوی عرضی-اول، اول-در-اول-خروجی گسترش می یابند.

زمانی که هدف ج_حرفبالاتر از c است_آ، شرط خط 11، تعقیب کنندگان نوبت را می گیرند و شروع به گسترش گره های خود می کنند. بخش اصلی این الگوریتم خطوط بین 16 و 28 است که در آن هر تعقیب کننده از طریق حالت خود حلقه می زند و گره های خود را مستقل از سایر تعقیب کننده ها گسترش می دهد. هدف باید موقعیت حالات و حلقه های تعقیب کننده را از طریق هر بازیکن بداند. اگر یک عامل تعقیب کننده باشد، این عامل خاص از pursuer_node_queue حذف می شود و در داخل pursuer_closed قرار می گیرد اگر قبلاً وارد نشده باشد. همسایه ها به pursuer_node_queue اضافه می شوند. هر حالتی که توسط تعقیب کننده بازدید می شود در لیست target_closed وجود دارد، سپس target_caught_states افزایش می یابد و با اندازه target_closed مقایسه می شود که اگر برابر باشد true برمی گرداند.

خطوط 29-32 یک مسیر ایجاد می کنند. آخرین عنصر در target_closed دورترین حالتی است که هدف می تواند به آن حرکت کند. این لیست برای شناسایی مسیر معکوس می شود و اولین عنصر در لیست اقدامی است که هدف انجام می دهد. این تابع در هر مرحله تکرار می شود تا بهترین اقدام را برای هدف پیدا کند.

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

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

بهبودهای بیشتر

استراتژی TrailMax برای سناریوهای یک به یک نماینده کار می کند و دریافت بهترین هزینه از لیست برای هر بازیکن ساده است. اما این مورد برای الگوریتم MPTM نیست زیرا بسیاری از عوامل تعقیب کننده را در یک جستجو در نظر می گیرد. pursuer_node_queue حاوی اطلاعاتی برای همه تعقیب کنندگان و جهت حرکت آنها با هزینه است.

قبلاً مورد بحث قرار گرفته است که هزینه اولیه برای همه بازیکنان صفر است. هنگامی که خط 11 خوانده می شود ، درست خواهد بود و هدف برای گسترش و افزایش هزینه خود توسط یک مورد به نوبه خود خواهد بود. در تکرار بعدی ، این شرط نادرست خواهد بود ، زیرا هزینه هدف 1 است و هزینه تمام تعقیب کنندگان هنوز صفر است. این گسترش برای تعقیب کنندگان صورت می گیرد. از آنجا که بسیاری از تعقیب کنندگان وجود دارند ، خط 20 درخواست اولین هزینه تعقیب کننده را از pursuer_node_queue درخواست می کند. سپس این تعقیب کننده هزینه خود را به 1. افزایش می دهد و افزایش می یابد. در اینجا مشکلی وجود دارد زیرا Trailmax بهترین هزینه را برای هر تکرار درخواست می کند. خوب بود اگر فقط یک تعقیب کننده وجود داشته باشد ، اما این مسئله با تعقیب کنندگان متعدد است. اگر بهترین هزینه برای تعقیب کنندگان متعدد در نظر گرفته شود ، فقط اولین تعقیب کننده گسترش می یابد زیرا فقط هزینه آن افزایش می یابد. این منجر به این واقعیت می شود که فقط همان تعقیب کننده با بهترین هزینه درخواست می شود و همه تعقیب کنندگان دیگر بدون گسترش با هزینه اولیه صفر باقی می مانند.

برای رفع مشکل فوق ، هزینه درخواست شده در خطوط 10 و 20 بهترین هزینه نیست بلکه هزینه ای برای هر تعقیب کننده به ترتیب از گره pursuer_ _queue است. این فرصت بیشتری را برای هدف برای ارزیابی همه اقدامات تعقیب کنندگان و تصمیم گیری دقیق تر می دهد.

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

ارزیابی تجربی

در این بخش ، نتایج تجربی برای نشان دادن کارآیی الگوریتم پیشنهادی ارائه خواهد شد. ابتدا ، تنظیم آزمایشی شرح داده خواهد شد ، سپس نتایج عملکرد الگوریتم MPTM که در بخش قبلی شرح داده شده است گزارش می شود.

راه اندازی آزمایشی

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

این سناریوها برای داشتن چندین هدف انتخاب شدند و برای آزمایشات ، در ابتدا ، دو و بعد از سه هدف مورد آزمایش قرار گرفتند. ترکیبی از تعقیب کنندگان در مقابل اهداف در جدول 2 نمایش داده شده است. این سناریوها به درک رفتار الگوریتم MPTM کمک می کنند تا اهداف از تعداد بیشتری برخوردار باشند.

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

شواهد نشان می دهد که الگوریتم جدید MPTM از الگوریتم های SF ، Minimax و حریص در تعداد مراحل موجود در کلیه تنظیمات آزمون استفاده می کند.

در حالی که این آزمایش ها برای مطالعه الگوریتم های هدف طراحی شده اند ، همچنین جالب است که توجه داشته باشید که الگوریتم STMTA* با تغییرات استراتژی انتساب آن ، عملکرد کلی را بهتر از PRA* انجام می دهد.

از آزمایشات آماری نیز در هزینه های ضبط استفاده می شود تا دریابید که کدام یک از نتایج به طور قابل توجهی متفاوت است. الگوریتم MPTM پیشنهادی در برابر الگوریتم های SF ، حریص و MMX موجود مقایسه شده است. فقط از نتایج الگوریتم وزن STMTA* برای مقایسه استفاده می شود زیرا به طور کلی بهترین نتایج را در بین سایر الگوریتم های تعقیب کننده نشان داده است ، همانطور که در جدول 2 نشان داده شده است. هزینه های ضبط به طور معمول توزیع نمی شوند. بنابراین ، نتایج آماری با استفاده از تست های جمع رتبه Wilcoxon به دست می آید. از سطح معنی داری 0. 05 استفاده می شود. مقادیر به دست آمده از تست های آماری بر روی نقشه در جدول 3 ارائه شده است.

مانند هزینه های ضبط ، نرخ موفقیت نیز به نسبت های تعقیب کننده و هدف بستگی دارد. این موفقیت متناسب با تعداد تعقیب کنندگان و اهداف بود. تعقیب کنندگان بیشتر برای همان تعداد اهداف ، اسارت را افزایش دادند. میزان موفقیت زمانی افزایش یافت که تعداد اهداف افزایش یافته در مقابل همان تعداد عوامل ، همانطور که در نمودار نمایش داده می شود ، شکل 3 را ببینید.

رفتار الگوریتم MPTM در نقشه هایی که موانعی دارند که می توانند در اطراف آن باشند ، بهتر است ، به عنوان مثال ، نقشه های نشان داده شده در شکل ، 1. این نوع نقشه ها ممکن است برای الگوریتم های هدف تطبیقی مناسب باشد زیرا فرصت های فرار را ارائه می دهند اما ممکن استاگر آنها استراتژی مانند استراتژی تله ندارند [26] برای الگوریتم های عامل دنبال کننده دشوار باشید. نقشه های AR0311SR ، AR0527SR و AR0707SR دارای کوچه های مرده یا کور هستند و بنابراین یافتن مسیر فرار را دشوارتر می کند و منجر به عملکرد پایین تر در این نقشه ها می شود.

با برخی از الگوریتم ها ، دنبال کردن عوامل گاهی در گرفتن اهداف ناکام هستند ، اگرچه اینها از تعداد بیشتری برخوردار هستند. آنها ممکن است یک هدف را به خود جلب کنند اما نتوانند دیگری را بگیرند ، یا هدف خود را دنبال کنند ، یا تا زمان وقوع در بن بست پایان دهند. این معمولاً در PRA* مشاهده می شود ، زیرا برخلاف STMTA* هیچ استراتژی واگذاری قبل از شروع حرکت وجود ندارد.

به طور متوسط ، بیش از همه نقشه ها در هر پیکربندی بازیکن ، میزان موفقیت می تواند 13 ٪ بهتر از Minimax ، حریص و SF باشد.

زمان سنجی . در این بخش زمان گرفته شده برای هر الگوریتم در همان آزمایشات اندازه گیری شده است که هزینه ضبط و میزان موفقیت را اندازه گیری می کند. هر آزمایش در ثانیه ثبت می شود و به طور متوسط در تمام آزمایشات انجام می شود.

جدول 5 نتایج هر الگوریتم هدف را ارائه می دهد. SF ، حریص و MMX قبل از حرکت به اندازه MPTM محاسبه نمی کنند ، بنابراین نتایج آنها در مقایسه با MPTM کوچکتر و نزدیک تر است ، که تفاوت های بیشتری دارد.

الگوریتم MPTM پیشنهادی در برابر الگوریتم های SF ، حریص و MMX اندازه گیری و مقایسه می شود. MPTM با ماندن طولانی تر روی نقشه ها نتایج بهتری ارائه می دهد و موفق به فرار از عوامل تعقیب کننده می شود. تعداد مراحل هزینه ضبط است ، جایی که در بعضی موارد MPTM به ترتیب از ضبط 2. 6 ، 2. 9 و 2. 4 برابر بیشتر از SF ، حریص و MMX جلوگیری می کند. علاوه بر این ، این نتایج از نظر آماری با استفاده از آزمون جمع رتبه Wilcoxon برای تعیین اهمیت یافته ها مورد آزمایش قرار گرفت. جدول 3 مقادیر p را نشان می دهد و با اطمینان 95 ٪ اعتماد به نفس ، بیشترین نتایج نشان دهنده تفاوت های معنی داری است. اندازه گیری مهم دیگر ، میزان موفقیت است که بیش از انتظارات برای MPTM با 91. 08 ٪ از گرفتار شدن ، پایین تر است ، پایین تر است ، در حالی که SF و MMX 100 ٪ گرفتار می شوند و حریص با 99. 98 ٪.

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

نتیجه

هدف از این مقاله ارائه راه حلی برای مشکلات MAPF و توسعه یک الگوریتم هدف است که می تواند چندین تعقیب کننده را در نظر بگیرد و یک فرار هوشمندانه ایجاد کند. مطالعات جالب بسیاری در مورد الگوریتم های جستجو انجام شده است ، و از جمله آنها راه حل هایی برای چارچوب های MAPF است. فقط چند مطالعه در مورد الگوریتم های هدف ، به ویژه در محیط های چند هدف انجام شده است.

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

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

مسئله هزینه های محاسباتی نسبتاً بالا می تواند در تحقیقات بیشتر ، به عنوان مثال ، با بررسی استفاده از اکتشافی که بخش هایی از فضای جستجو را قطع می کند ، مورد بررسی قرار گیرد. اگرچه این مطالعه بر فرار از تعقیب کنندگان متعدد متمرکز شده است ، تحقیقات بیشتر برای گسترش MPTM برای همکاری با اهداف دیگر بسیار جالب خواهد بود.

منابع

1. Li J ، Gange G ، Harabor D ، Stuckey PJ ، Ma H ، Koenig S تکنیک های جدید برای تقارن زوج در یافتن مسیر چند عامل. ارائه شده در کنفرانس بین المللی مجموعه مقالات برنامه ریزی و برنامه ریزی خودکار (2020).
2. Panait L ، Luke S Leaing Multi-Agent Leaing: وضعیت هنر. 11 ، 387-434 (2005) ؛https://doi. org/10. 1007/S10458-005-2631-2.
3. Ishida t جستجوی هدف با اطلاعات. ارائه شده در جلسه دهم کنفرانس ملی اطلاعات مصنوعی. صص 525-532 (1992).
4. Koenig S ، Likhachev M: D* lite. ارائه شده در مجموعه مقالات کنفرانس ملی اطلاعات مصنوعی (2002).
5. Undeger C ، Polat F. RTTES: جستجوی زمان واقعی در محیط های پویا. Appl intel. 2007 ؛ 27: 113 29. https://doi. org/10. 1007/S10489-006-0023-1. Articlegoogle Scholar
6. Wang K-HC ، Botea A: مسیر سریع و کارآمد با حافظه چند عامل. ارائه شده در ICAPS 2008 - مجموعه مقالات هجدهمین کنفرانس بین المللی برنامه ریزی و برنامه ریزی خودکار (2008).
7. مسیریابی تعاونی نقره D. ارائه شده در مجموعه مقالات اولین کنفرانس AAAI در مورد هوش مصنوعی و سرگرمی های دیجیتال تعاملی (AIIDE 05) ، مارینا دل ری ، کالیفرنیا (2005).
8. Sharon G ، Ste R ، Felner A ، Sturtevant NR. جستجوی مبتنی بر درگیری برای مسیریابی بهینه چند عامل. Artif Intel. 2015 ؛ 219: 40-66. https://doi. org/10. 1016/j. artint. 2014. 11. 006. ArticleMathscinetMathgoogle Scholar
9. Goldenberg M ، Kovarsky A ، Wu X ، Schaeffer J چندین عامل در جستجوی هدف در حال حرکت هستند. ارائه شده در کنفرانس مشترک بین المللی IJCAI در مورد اطلاعات مصنوعی (2003).
10. LOH PKK ، Prakash EC: الگوریتم های جستجوی هدف در حال حرکت رمان برای بازی های رایانه ای. 7 ، 27: 1 27: 16 (2009) ؛https://doi. org/10. 1145/1541895. 1541907.
11. Moldenhauer C: الگوریتم های جستجوی درخت بازی برای بازی پلیس و سارق ، (2009).
12. Xie F ، Botea A ، Kishimoto یک رویکرد مقیاس پذیر برای تعقیب چندین هدف متحرک با چندین عامل. ارائه شده در مجموعه مقالات بیست و یکمین کنفرانس مشترک بین المللی اطلاعات مصنوعی ، ملبورن ، استرالیا (2017) ؛https://doi. org/10. 24963/ijcai. 2017/624.
13. Pellier D ، Fiorino H ، Métivier M: برنامه ریزی هنگام تغییر اهداف: یک رویکرد جستجوی هدف در حال حرکت. ارائه شده در دوازدهمین کنفرانس بین المللی پیشرفت در برنامه های کاربردی عملی سیستم های چند عامل ناهمگن: مجموعه PAAMS (2014) ؛https://doi. org/10. 1007/978-3-319-07551-8_20.
14. Moldenhauer C ، Sturtevant NR: ارزیابی استراتژی های اجرای پلیس. ارائه شده در کنفرانس مشترک بین المللی IJCAI در مورد هوش مصنوعی (2009).
15. Sigurdson D ، Bulitko V ، Yeoh W ، Heández C ، Koenig S: Pathfinding چند عامل با جستجوی اکتشافی در زمان واقعی. ارائه شده در چهاردهمین کنفرانس IEEE در زمینه اطلاعات محاسباتی و بازی ها (CIG) (2018). https://doi. org/10. 1109/cig. 2018. 8490436.
16. Chouhan SS ، Niyogi R. Dimpp: یک الگوریتم توزیع کامل برای برنامه ریزی مسیر چند عامل. J Exp تئوری artif stlent. 2017 ؛ 29: 1129-48. https://doi. org/10. 1080/0952813x. 2017. 1310142. Articlegoogle Scholar
17. Afzalov A ، Lotfi A ، Inden B ، Aydin ME: الگوریتم Trainmax Trailmax چند تعقیب کننده برای محیط های پویا. در: ICAART 2021 - برنامه های سیزدهمین کنفرانس بین المللی نمایندگان و هوش مصنوعی (2) ، صص 437 (2021). https://doi. org/10. 5220/0010392404370443.
18. Bulitko V ، sturtevant N انتزاع برای تعقیب هدف در زمان واقعی: یک مطالعه مقدماتی. ارائه شده در مجموعه مقالات کارگاه AAAI در مورد یادگیری برای جستجو (2006).
19. Isaza A ، Lu J ، Bulitko V ، Greiner R یک رویکرد مبتنی بر پوشش برای دنبال کردن هدف در حال حرکت چند عامل. ارائه شده در مجموعه مقالات چهارم کنفرانس هوش مصنوعی و سرگرمی دیجیتال تعاملی ، AIIDE 2008 (2008).
20. Koenig S ، Likhachev M ، Sun X سرعت جستجوی هدف را سرعت می بخشد. ارائه شده در مجموعه مقالات ششمین کنفرانس مشترک بین المللی در مورد عوامل خودمختار و سیستم های چند منظوره ، هونولولو ، هاوایی (2007) ؛https://doi. org/10. 1145/1329125. 1329353.
21. Burke EK ، Burke EK ، Kendall G ، Kendall G Methodologies: آموزش مقدماتی در بهینه سازی و تکنیک های پشتیبانی تصمیم گیری. اسپرینگر (2014).
22. Sturtevant NR ، Sigurdson D ، Taylor B ، Gibson T Pathfinding و انتزاع با هزینه های زمین پویا. ارائه شده در مجموعه مقالات پانزدهمین کنفرانس AAAI در مورد هوش مصنوعی و سرگرمی های دیجیتال تعاملی ، AIIDE 2019 (2019).
23. Afzalov A ، Lotfi A ، aydin Me یک الگوریتم جستجوی استراتژیک در محیط چند عامل و چند هدف. صص 195. اسپرینگر (2021) ؛https://doi. org/10. 1007/978-981-16-4803-8_21.
24. Afzalov A ، He J ، Lotfi A ، Aydin ME: رویکرد برنامه ریزی مسیر چند عامل با استفاده از تغییرات استراتژی واگذاری در دستیابی به اهداف در حال حرکت. در: نوآوری هوشمند ، سیستم ها و فناوری ها. اسپرینگر (2021) ؛https://doi. org/10. 1007/978-981-16-2994-5_38.
25. Ste R ، Sturtevant NR ، Felner A ، Koenig S ، Ma H ، Walker TT ، Li J ، Atzmon D ، Cohen L ، Kumar TKS ، Boyarski E ، Barták R Pathfinding Multi-Agent: تعاریف ، انواع و بسته ها. ارائه شده در مجموعه مقالات دوازدهمین سمپوزیوم بین المللی در جستجوی ترکیبی ، SOCS 2019 (2019).
26. جان Tch ، Prakash EC ، Chaudhari NS. برنامه های استراتژیک تیم AI PATH: مسیریابی احتمالی. Int J Comput Games Technol. 2008 ؛ 2008: 1-6. https://doi. org/10. 1155/2008/834616. Articlegoogle Scholar

اطلاعات نویسنده

نویسندگان و وابستگی ها

1. دانشگاه ناتینگهام ترنت ، پردیس کلیفتون ، ناتینگهام ، NG11 8NS ، بریتانیا عزیزخون افزالوف و احمد لوتفی
2. موسسه ریاضیات ماکس پلانک در علوم ، Inselstraße 22 ، 04103 ، لایپزیگ ، آلمان بنیامین ایندن
3. دانشگاه غرب انگلیس ، Coldharbour LN ، Bristol ، BS16 1Qy ، UK Mehmet Emin Aydin

1. عزیزخون افضلوف