جستجوی لحظه‌ای

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

روش‌های کلی

روش محاسبه مجدد مسیر (به انگلیسی: Recalculating paths)

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

• هر N مرحله یک‌بار.
• زمانی که CPU زمان آزاد داشته باشد.
• زمانی که از یک ایستگاه بین راهی (به انگلیسی: waypoint) عبور کنیم.
• زمانی که محیطِ نزدیکمان تغییر کند.

مسکل اصلیِ این روش این است که هر بار اطلاعات مسیر محاسبه شدهٔ قبلی را دور می‌ریزیم. در نتیحه این روش برای جاهایی که مسیرهای طولانی در پیش داریم مناسب نمی‌باشد.

روش پیرایش مسیر (به انگلیسی: Path splicing)

در این روش از استراتژی local repair استفاده می‌کنیم؛ برای محیطِ نزدیک (تا یک شعاع مشخص)، مسیر را دوباره محاسبه می‌کنیم و فرض می‌کنیم که برای نقاط دورتر، باقیِ مسیر نیازی به محاسبهٔ مجدد ندارد تا زمانی که به به آن نقاط برسیم. مراحل این روش به این صورت است:

1. فرض کنید مسیر از N گام تشکیل شده است.
2. M گام ابتدایی را مجدداً حساب می‌کنیم.

متغیر M باید بسته به شرایط مسئله انتخاب شود. به طور کلی اگر مقدار M زیاد در نظر گرفته شود، محاسبهٔ مسیر پرهزینه می‌شود و اگر مقدار آن کم در نظر گرفته شود، مسیر محاسبه شده از حالت بهینه دور می‌شود.

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

روش نگاه کردن برای تغییرات نقشه (به انگلیسی: Watching for map changes)

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

مزیت این روش در این است که تا زمانی که مانعی حرکت نکرده است، نیازی به به روزرسانی مسیر نیست. در نتیجه این روش برای مواقعی که اکثر ناحیه‌ها تغییر زیادی نمی‌کنند مناسب می‌باشد.

روش پیش‌بینی حرکت موانع

در صورتی که حرکت موانع قابل پیش‌بینی باشد، می‌توان مسیر را با احتساب موقعیت آینده آن پیدا کرد. این روش را می‌توان با الگوریتم *A پیاده‌سازی کرد.

منابع

1. https://en.wikipedia.org/wiki/Real-time_Search
2. http://theory.stanford.edu/~amitp/GameProgramming/MovingObstacles.html

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

الگوریتم *A