Memory-Bounded Delayed D* الگوریتم

مسیریابی شامل یافتن دنباله ایی از حالات از مبدأ به مقصد می باشد. الگوریتم اکتشافی – A* در محیط های ایستا و الگوریتم D* Lite در محیط های پویا به صورت گسترده استفاده می شوند. این الگوریتم ها به طور نامحدودی حافظه را اشغال می کنند و در بدترین شرایط ممکن است تمامی رأس های گراف را بسطدهند. برای حل این مشکل از الگوریتم های SMA* و MD* Lite استفاده می شود. الگوریتم DelayedD* با به تأخیر انداختن گسترش یال هایی که هزینه ی آن ها افزایش یافته است، زمان محاسبه ی مسیر جدید را در مقایسه با D* Lite به نصف کاهش می دهد. اما هنوز مشکل حافظه در این الگوریتم وجود دارد. در این مقاله حافظه ی مورد نیاز الگوریتم Delayed D* به صورتی بهبود داده شده است که با استفاده از کمترین حافظه ی ممکن، مسیر بهینه را به دست آورد و درمقایسه با MD* Lite زمان اجرا به کمتر از نصف رسیده است

کلیدواژه ها:

الگوریتم - A* ، الگوریتم Delayed D* Lite ، مسیریابی