D*
D* (تلفظ "دی استار") هر یک از سه الگوریتم جستجوی افزایشی زیر است:
هر سه ی این الگوریتم های جستجو مسائل برنامه ریزی مسیر مبتنی بر فرض را حل می کنند، از جمله برنامه ریزی با فرض فضای آزاد، که در آن یک ربات باید در یک زمین ناشناخته به مختصات هدف داده شده برود. که در مورد قسمت ناشناخته زمین فرضیاتی ارائه می شود (به عنوان مثال: هیچ مانعی در زمین وجود ندارد) و ربات کوتاه ترین مسیر را از مختصات فعلی خود به مختصات هدف تحت این مفروضات می یابد. سپس ربات مسیر را دنبال می کند. هنگامی که اطلاعات نقشه جدید (مانند موانع ناشناخته قبلی) را مشاهده می کند، اطلاعات را به نقشه خود اضافه می کند و در صورت لزوم کوتاهترین مسیر جدید را از مختصات فعلی خود به مختصات هدف داده شده دوباره برنامه ریزی می کند. این فرایند را تکرار می کند تا زمانی که به مختصات هدف برسد یا تعیین کند که نمی توان به مختصات هدف رسید. هنگام عبور از زمین ناشناخته، موانع جدید ممکن است به طور مکرر کشف شوند، بنابراین این برنامه ریزی باید سریع باشد. الگوریتم های جستجوی افزایشی (آگاهانه) سرعت جستجو را برای دنباله هایی از مشکلات جستجو مشابه با استفاده از تجربه مشکلات قبلی برای تسریع در جستجوی مورد فعلی افزایش می دهند. با فرض تغییر نکردن مختصات هدف، هر سه الگوریتم جستجو از جستجوی *A مکرر کارآمدتر هستند.
D* و انواع آن به طور گسترده ای برای ربات های سیار و ناوبری وسیله نقلیه خودمختار استفاده می شوند. سیستم های فعلی معمولاً بیشتر از D* Lite یا D* Focused مبتنی بر D* Lite هستند. در حقیقت، حتی آزمایشگاه استنتز در برخی از پیاده سازی ها از D* Lite به جای *D استفاده می کند. چنین سیستم های ناوبری شامل یک سیستم نمونه آزمایشی که در مریخ نوردهای Opportunity و Spirit و سیستم ناوبری برنده در DARPA Urban Challenge تست شده اند که هر دو در دانشگاه کارنگی ملون توسعه یافته اند.
D* اصلی توسط آنتونی استنتز در سال 1994 معرفی شد. نام *D از اصطلاح "*Dynamic A" آمده است، زیرا الگوریتم مانند *A رفتار می کند با این تفاوت که هنگام اجرای الگوریتم هزینه های قوس می توانند تغییر کند.
عملکرد اساسی *D در زیر بیان شده است.
مانند الگوریتم Dijkstra و *A، الگوریتم *D لیستی از گره های مورد ارزیابی را نگهداری می کند، معروف به "لیست OPEN". گره ها به عنوان یکی از چندین حالت زیر مشخص شده اند:
این الگوریتم با تکرار عملیات انتخاب یک گره از لیست OPEN و ارزیابی آن کار می کند. سپس تغییرات گره را در همه گره های همسایه منتشر کرده و در لیست OPEN قرار می دهد. این فرایند انتشار "گسترش" نامیده می شود. برخلاف *A متعارف، که مسیر را از ابتدا تا انتها دنبال می کند، *D با جستجوی عقبگرد از گره هدف شروع می شود. هر گره توسعه یافته دارای یک "backpointer" است که به گره بعدی منتهی به هدف اشاره دارد و هر گره هزینه دقیق رسیدن به هدف را می داند. وقتی گره شروع گره ای است که در مرحله بعدی گسترش می یابد، الگوریتم به پایان میرسد و می توان با دنبال کردن نشانگرهای عقب("backpointers")، مسیر رسیدن به هدف را پیدا کرد.
وقتی مانع در مسیر مورد نظر شناسایی شد، تمام نقاطی که تحت تأثیر قرار می گیرند با برچسب RAISE مشخص شده و دوباره در لیست OPEN قرار می گیرند. قبل از اینکه گره RAISED هزینه اش افزایش یابد، الگوریتم همسایگان خود را بررسی می کند و بررسی می کند که آیا می تواند هزینه گره را کاهش دهد. در غیر اینصورت، حالت RAISE به تمام فرزندان گره ها، یعنی گره هایی که دارای نشانه های برگشتی هستند، انتشار می یابد. سپس این گره ها ارزیابی شده و حالت RAISE منتقل شده و موجی را تشکیل می دهند. هنگامی که یک گره RAISED می تواند کاهش یابد، قسمت داخلی آن به روز می شود و وضعیت LOWER را به همسایگان خود منتقل می کند. این امواج RAISE و LOWER قلب *D هستند.
بوسیله این نکته،از "لمس شدن" یک سری از نقاط توسط امواج جلوگیری می شود. بنابراین الگوریتم فقط در نقاطی که در تغییر هزینه تأثیر دارند کار کرده است.
این بار نمی توان از بن بست به راحتی عبور کرد. هیچ یک از نقاط نمی‌توانند مسیر جدیدی را از طریق همسایه به مقصد پیدا کنند. بنابراین، آنها به انتشار افزایش هزینه های خود ادامه می دهند. فقط نقاط خارج از کانال را می توان یافت، که می تواند از طریق یک مسیر مناسب به مقصد منجر شود. به این ترتیب دو موج پایین توسعه می یابند که به صورت نقاطی که با اطلاعات مسیر جدید بعنوان غیرقابل دستیابی مشخص شده اند، گسترش می یابد.
while (!openList.isEmpty()) {
void expand(currentPoint) {
boolean isRaise(point) {
همانطور که از نام آن مشخص است، *D متمرکز یک الگوریتم گسترش یافته از *D است که از یک روش ابتکاری برای تمرکز انتشار RAISE و LOWER به سمت ربات استفاده می کند. به این ترتیب، فقط حالت هایی که مهم هستند به روز می شوند، به همان روشی که *A فقط هزینه برخی از گره ها را محاسبه می کند.
D* Lite براساس *D اصلی یا *D متمرکز نیست، اما همان عمل را انجام میدهد. فهم آن ساده تر است و می تواند در تعداد کمتری خط کدش پیاده سازی و اجرا شود، از این رو نام آن "D* Lite" است. از نظر عملکرد، بهتر یا برابر با *D متمرکز است. D * Lite مبتنی بر برنامه ریزی مادام العمر *A است که چند سال قبل توسط کونیگ و لیخاچف معرفی شد. D * آرشیو
برای *D، تمایز بین حداقل هزینه و هزینه های فعلی مهم است. مورد اول فقط در زمان جمع آوری مهم است ولی مورد دوم بسیار حیاتی است زیرا OpenList را مرتب می کند. تابعی که حداقل هزینه را برمی گرداند همیشه کمترین هزینه به نقطه فعلی را برمی گرداند زیرا اولین ورودی OpenList است.