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

سال انتشار: 1392
محل انتشار: بیست و یکمین کنفرانس مهندسی برق ایران
کد COI اختصاصی: ICEE21_849
زبان مقاله: انگلیسی
تعداد مشاهده: 1530

نویسندگان

آزمایشگاه هوش مصنوعی، دانشکده برق و کامپیوتر، دانشگاه صنعتی اصفهان،

چکیده

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

کلیدواژه ها

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

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.