موضوع مقاله: D* | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # D* | مقدمه: D* (تلفظ "دی استار") هر یک از سه الگوریتم جستجوی افزایشی زیر است: D* اصلی، توسط آنتونی استنتز، یک الگوریتم جستجوی افزایشی آگاهانه است. | ## بخش 1: D* | D* متمرکز یک الگوریتم جستجوی (اکتشافی) افزایشی آگاهانه توسط آنتونی استنتز است که ایده‌های A * و *D اصلی را ترکیب می‌کند. هر سهٔ این الگوریتم‌های جستجو مسائل برنامه‌ریزی مسیر مبتنی بر فرض را حل می‌کنند، از جمله برنامه‌ریزی با فرض فضای آزاد، که در آن یک ربات باید در یک زمین ناشناخته به مختصات هدف داده شده برود. که در مورد قسمت ناشناخته زمین فرضیاتی ارائه می‌شود (به عنوان مثال: هیچ مانعی در زمین وجود ندارد) و ربات کوتاه‌ترین مسیر را از مختصات فعلی خود به مختصات هدف تحت این مفروضات می‌یابد. هنگامی که اطلاعات نقشه جدید (مانند موانع ناشناخته قبلی) را مشاهده می‌کند، اطلاعات را به نقشه خود اضافه می‌کند و در صورت لزوم کوتاهترین مسیر جدید را از مختصات فعلی خود به مختصات هدف داده شده دوباره برنامه‌ریزی می‌کند. این فرایند را تکرار می‌کند تا زمانی که به مختصات هدف برسد یا تعیین کند که نمی‌توان به مختصات هدف رسید. هنگام عبور از زمین ناشناخته، موانع جدید ممکن است به‌طور مکرر کشف شوند، بنابراین این برنامه‌ریزی باید سریع باشد. الگوریتم‌های جستجوی افزایشی (آگاهانه) سرعت جستجو را برای دنباله‌هایی از مشکلات جستجو مشابه با استفاده از تجربه مشکلات قبلی برای تسریع در جستجوی مورد فعلی افزایش می‌دهند. با فرض تغییر نکردن مختصات هدف، هر سه الگوریتم جستجو از جستجوی *A مکرر کارآمدتر هستند. | ## بخش 2: D* | D* و انواع آن به‌طور گسترده‌ای برای ربات‌های سیار و ناوبری وسیله نقلیه خودمختار استفاده می‌شوند. در حقیقت، حتی آزمایشگاه استنتز در برخی از پیاده‌سازی‌ها از D* Lite به جای *D استفاده می‌کند. نام *D از اصطلاح "*Dynamic A" آمده‌است، زیرا الگوریتم مانند *A رفتار می‌کند با این تفاوت که هنگام اجرای الگوریتم هزینه‌های قوس می‌توانند تغییر کند. برخلاف *A متعارف، که مسیر را از ابتدا تا انتها دنبال می‌کند، *D با جستجوی عقبگرد از گره هدف شروع می‌شود. وقتی گره شروع گره ای است که در مرحله بعدی گسترش می‌یابد، الگوریتم به پایان می‌رسد و می‌توان با دنبال کردن نشانگرهای عقب("backpointers")، مسیر رسیدن به هدف را پیدا کرد. رسیدگی به موانع وقتی مانع در مسیر مورد نظر شناسایی شد، تمام نقاطی که تحت تأثیر قرار می‌گیرند با برچسب RAISE مشخص شده و دوباره در لیست OPEN قرار می‌گیرند. قبل از اینکه گره RAISED هزینه اش افزایش یابد، الگوریتم همسایگان خود را بررسی می‌کند و بررسی می‌کند که آیا می‌تواند هزینه گره را کاهش دهد. در غیر اینصورت، حالت RAISE به تمام فرزندان گره‌ها، یعنی گره‌هایی که دارای نشانه‌های برگشتی هستند، انتشار می‌یابد. | ## بخش 3: D* | بوسیله این نکته، از «لمس شدن» یک سری از نقاط توسط امواج جلوگیری می‌شود؛ بنابراین الگوریتم فقط در نقاطی که در تغییر هزینه تأثیر دارند کار کرده‌است. هیچ‌یک از نقاط نمی‌توانند مسیر جدیدی را از طریق همسایه به مقصد پیدا کنند؛ بنابراین، آنها به انتشار افزایش هزینه‌های خود ادامه می‌دهند. فقط نقاط خارج از کانال را می‌توان یافت، که می‌تواند از طریق یک مسیر مناسب به مقصد منجر شود. به این ترتیب دو موج پایین توسعه می‌یابند که به صورت نقاطی که با اطلاعات مسیر جدید بعنوان غیرقابل دستیابی مشخص شده‌اند، گسترش می‌یابد. به این ترتیب، فقط حالت‌هایی که مهم هستند به روز می‌شوند، به همان روشی که *A فقط هزینه برخی از گره‌ها را محاسبه می‌کند. فهم آن ساده‌تر است و می‌تواند در تعداد کمتری خط کدش پیاده‌سازی و اجرا شود، از این رو نام آن "D* Lite" است. D * Lite مبتنی بر برنامه‌ریزی مادام العمر *A است که چند سال قبل توسط کونیگ و لیخاچف معرفی شد. D * آرشیو حداقل هزینه در مقابل هزینه فعلی برای *D، تمایز بین حداقل هزینه و هزینه‌های فعلی مهم است. | ## جمع‌بندی | تابعی که حداقل هزینه را برمی‌گرداند همیشه کمترین هزینه به نقطه فعلی را برمی‌گرداند زیرا اولین ورودی OpenList است.