D*
D* (تلفظ "دی استار") هر یک از سه الگوریتم جستجوی افزایشی زیر است:
- D* اصلی ، [1] توسط آنتونی استنتز، یک الگوریتم جستجوی افزایشی آگاهانه است.
- D* متمرکز [2] یک الگوریتم جستجوی (اکتشافی) افزایشی آگاهانه توسط آنتونی استنتز است که ایده های A * [3] و *D اصلی را ترکیب می کند. *D متمرکز ناشی از توسعه بیشتر *D اصلی است.
- D* Lite [4] یک الگوریتم جستجوی اکتشافی افزایشی توسط Sven Koenig و Maxim Likhachev است که بر اساس *LPA بنا شده است، [5] یک الگوریتم جستجوی اکتشافی افزایشی است که ایده های A* و Dynamic SWSF-FP را ترکیب می کند. [6]
هر سه ی این الگوریتم های جستجو مسائل برنامه ریزی مسیر مبتنی بر فرض را حل می کنند، از جمله برنامه ریزی با فرض فضای آزاد، [7] که در آن یک ربات باید در یک زمین ناشناخته به مختصات هدف داده شده برود. که در مورد قسمت ناشناخته زمین فرضیاتی ارائه می شود (به عنوان مثال: هیچ مانعی در زمین وجود ندارد) و ربات کوتاه ترین مسیر را از مختصات فعلی خود به مختصات هدف تحت این مفروضات می یابد. سپس ربات مسیر را دنبال می کند. هنگامی که اطلاعات نقشه جدید (مانند موانع ناشناخته قبلی) را مشاهده می کند، اطلاعات را به نقشه خود اضافه می کند و در صورت لزوم کوتاهترین مسیر جدید را از مختصات فعلی خود به مختصات هدف داده شده دوباره برنامه ریزی می کند. این فرایند را تکرار می کند تا زمانی که به مختصات هدف برسد یا تعیین کند که نمی توان به مختصات هدف رسید. هنگام عبور از زمین ناشناخته، موانع جدید ممکن است به طور مکرر کشف شوند، بنابراین این برنامه ریزی باید سریع باشد. الگوریتم های جستجوی افزایشی (آگاهانه) سرعت جستجو را برای دنباله هایی از مشکلات جستجو مشابه با استفاده از تجربه مشکلات قبلی برای تسریع در جستجوی مورد فعلی افزایش می دهند. با فرض تغییر نکردن مختصات هدف، هر سه الگوریتم جستجو از جستجوی *A مکرر کارآمدتر هستند.
D* و انواع آن به طور گسترده ای برای ربات های سیار و ناوبری وسیله نقلیه خودمختار استفاده می شوند. سیستم های فعلی معمولاً بیشتر از D* Lite یا D* Focused مبتنی بر D* Lite هستند. در حقیقت، حتی آزمایشگاه استنتز در برخی از پیاده سازی ها از D* Lite به جای *D استفاده می کند. [8] چنین سیستم های ناوبری شامل یک سیستم نمونه آزمایشی که در مریخ نوردهای Opportunity و Spirit و سیستم ناوبری برنده در DARPA Urban Challenge تست شده اند که هر دو در دانشگاه کارنگی ملون توسعه یافته اند.
D* اصلی توسط آنتونی استنتز در سال 1994 معرفی شد. نام *D از اصطلاح "*Dynamic A" آمده است،[9] زیرا الگوریتم مانند *A رفتار می کند با این تفاوت که هنگام اجرای الگوریتم هزینه های قوس می توانند تغییر کند.
عملکرد
عملکرد اساسی *D در زیر بیان شده است.
مانند الگوریتم Dijkstra و *A، الگوریتم *D لیستی از گره های مورد ارزیابی را نگهداری می کند، معروف به "لیست OPEN". گره ها به عنوان یکی از چندین حالت زیر مشخص شده اند:
- جدید، یعنی هرگز در لیست OPEN قرار نگرفته است
- OPEN، یعنی در حال حاضر در لیست OPEN است
- CLOSED، یعنی دیگر در لیست OPEN نیست
- RAISE، نشان می دهد هزینه آن بالاتر از هزینه آخرین باری که در لیست OPEN بوده است
- LOWER، نشان می دهد هزینه آن کمتر از هزینه آخرین باری است که در لیست OPEN قرار داشت
گسترش(تابع)
این الگوریتم با تکرار عملیات انتخاب یک گره از لیست OPEN و ارزیابی آن کار می کند. سپس تغییرات گره را در همه گره های همسایه منتشر کرده و در لیست OPEN قرار می دهد. این فرایند انتشار "گسترش" نامیده می شود. برخلاف *A متعارف، که مسیر را از ابتدا تا انتها دنبال می کند، *D با جستجوی عقبگرد از گره هدف شروع می شود. هر گره توسعه یافته دارای یک "backpointer" است که به گره بعدی منتهی به هدف اشاره دارد و هر گره هزینه دقیق رسیدن به هدف را می داند. وقتی گره شروع گره ای است که در مرحله بعدی گسترش می یابد، الگوریتم به پایان میرسد و می توان با دنبال کردن نشانگرهای عقب("backpointers")، مسیر رسیدن به هدف را پیدا کرد.
- توسعه در حال انجام است. گره پایان (زرد) در وسط ردیف بالای نقاط قرار دارد و گره شروع در وسط ردیف پایین قرار دارد. رنگ قرمز نشان دهنده مانع است. رنگ سیاه/ آبی گره های منبسط شده را نشان می دهند (روشنایی نشان دهنده هزینه است). رنگ سبز گره هایی را نشان می دهد که در حال گسترش هستند.
- توسعه به پایان رسیده.و مسیر به رنگ فیروزه ای مشخص شده است.
رسیدگی به موانع
وقتی مانع در مسیر مورد نظر شناسایی شد، تمام نقاطی که تحت تأثیر قرار می گیرند با برچسب RAISE مشخص شده و دوباره در لیست OPEN قرار می گیرند. قبل از اینکه گره RAISED هزینه اش افزایش یابد، الگوریتم همسایگان خود را بررسی می کند و بررسی می کند که آیا می تواند هزینه گره را کاهش دهد. در غیر اینصورت، حالت RAISE به تمام فرزندان گره ها، یعنی گره هایی که دارای نشانه های برگشتی هستند، انتشار می یابد. سپس این گره ها ارزیابی شده و حالت RAISE منتقل شده و موجی را تشکیل می دهند. هنگامی که یک گره RAISED می تواند کاهش یابد، قسمت داخلی آن به روز می شود و وضعیت LOWER را به همسایگان خود منتقل می کند. این امواج RAISE و LOWER قلب *D هستند.
بوسیله این نکته،از "لمس شدن" یک سری از نقاط توسط امواج جلوگیری می شود. بنابراین الگوریتم فقط در نقاطی که در تغییر هزینه تأثیر دارند کار کرده است.
- مانعی اضافه شده است (با رنگ قرمز) و گره هایی با برچسب RAISE (به رنگ زرد) مشخص شده اند.
- توسعه در حال انجام است. رنگ زرد گره هایی را نشان می دهد که با RAISE مشخص شده اند، و رنگ سبز نشان دهنده گره هایی است که با LOWER مشخص شده اند.
بن بست دیگری رخ می دهد
این بار نمی توان از بن بست به راحتی عبور کرد. هیچ یک از نقاط نمیتوانند مسیر جدیدی را از طریق همسایه به مقصد پیدا کنند. بنابراین، آنها به انتشار افزایش هزینه های خود ادامه می دهند. فقط نقاط خارج از کانال را می توان یافت، که می تواند از طریق یک مسیر مناسب به مقصد منجر شود. به این ترتیب دو موج پایین توسعه می یابند که به صورت نقاطی که با اطلاعات مسیر جدید بعنوان غیرقابل دستیابی مشخص شده اند، گسترش می یابد.
- کانال با اضافه شدن موانع مسدود شده است (قرمز)
- گسترش در حال انجام است (موج Raise به رنگ زرد ، موج Lower به رنگ سبز)
- مسیر جدید پیدا شد (به رنگ فیروزه ای)
Pseudocode
while (!openList.isEmpty()) {
point = openList.getFirst();
expand(point);
}
Expand
void expand(currentPoint) {
boolean isRaise = isRaise(currentPoint);
double cost;
for each (neighbor in currentPoint.getNeighbors()) {
if (isRaise) {
if (neighbor.nextPoint == currentPoint) {
neighbor.setNextPointAndUpdateCost(currentPoint);
openList.add(neighbor);
} else {
cost = neighbor.calculateCostVia(currentPoint);
if (cost <neighbor.getCost()) {
currentPoint.setMinimumCostToCurrentCost();
openList.add(currentPoint);
}
}
} else {
cost = neighbor.calculateCostVia(currentPoint);
if (cost <neighbor.getCost()) {
neighbor.setNextPointAndUpdateCost(currentPoint);
openList.add(neighbor);
}
}
}
}
Check for raise
boolean isRaise(point) {
double cost;
if (point.getCurrentCost()> point.getMinimumCost()) {
for each(neighbor in point.getNeighbors()) {
cost = point.calculateCostVia(neighbor);
if (cost <point.getCurrentCost()) {
point.setNextPointAndUpdateCost(neighbor);
}
}
}
return point.getCurrentCost()> point.getMinimumCost();
}
انواع
D متمرکز
همانطور که از نام آن مشخص است، *D متمرکز یک الگوریتم گسترش یافته از *D است که از یک روش ابتکاری برای تمرکز انتشار RAISE و LOWER به سمت ربات استفاده می کند. به این ترتیب، فقط حالت هایی که مهم هستند به روز می شوند، به همان روشی که *A فقط هزینه برخی از گره ها را محاسبه می کند.
D* Lite
D* Lite براساس *D اصلی یا *D متمرکز نیست، اما همان عمل را انجام میدهد. فهم آن ساده تر است و می تواند در تعداد کمتری خط کدش پیاده سازی و اجرا شود، از این رو نام آن "D* Lite" است. از نظر عملکرد، بهتر یا برابر با *D متمرکز است. D * Lite مبتنی بر برنامه ریزی مادام العمر *A است که چند سال قبل توسط کونیگ و لیخاچف معرفی شد. D * آرشیو
حداقل هزینه در مقابل هزینه فعلی
برای *D، تمایز بین حداقل هزینه و هزینه های فعلی مهم است. مورد اول فقط در زمان جمع آوری مهم است ولی مورد دوم بسیار حیاتی است زیرا OpenList را مرتب می کند. تابعی که حداقل هزینه را برمی گرداند همیشه کمترین هزینه به نقطه فعلی را برمی گرداند زیرا اولین ورودی OpenList است.
منابع
- Stentz, Anthony (1994), "Optimal and Efficient Path Planning for Partially-Known Environments", Proceedings of the International Conference on Robotics and Automation: 3310–3317
- Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning", Proceedings of the International Joint Conference on Artificial Intelligence: 1652–1659
- Hart, P.; Nilsson, N.; Raphael, B. (1968), "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Trans. Syst. Science and Cybernetics, SSC-4 (2): 100–107, doi:10.1109/TSSC.1968.300136
- Koenig, S.; Likhachev, M. (2005), "Fast Replanning for Navigation in Unknown Terrain", Transactions on Robotics, 21 (3): 354–363, doi:10.1109/tro.2004.838026
- Koenig, S.; Likhachev, M.; Furcy, D. (2004), "Lifelong Planning A*", Artificial Intelligence, 155 (1–2): 93–146, doi:10.1016/j.artint.2003.12.001
- Ramalingam, G.; Reps, T. (1996), "An incremental algorithm for a generalization of the shortest-path problem", Journal of Algorithms, 21 (2): 267–305, doi:10.1006/jagm.1996.0046
- Koenig, S.; Smirnov, Y.; Tovey, C. (2003), "Performance Bounds for Planning in Unknown Terrain", Artificial Intelligence, 147 (1–2): 253–279, doi:10.1016/s0004-3702(03)00062-6
- (Thesis). Missing or empty
|title=
(help) - Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning", Proceedings of the International Joint Conference on Artificial Intelligence: 1652–1659