D*

D* (изговара се „Д звезда") је било који од следећа три сродна инкрементациона алгоритма претраге:

• Оригинални D*,^[1] од А. Stentz, који је управо заснован на инкрементационом алгоритму претраге.
• Фокусирани D*,^[2] који је заснован на инкрементационом хеуристички алгоритау претраге у комбинацији са идејама А*^[3] и оригиналном D*. Он резултат за даљи развој оригиналног D*.
• D* Lite,^[4] је инкрементациони хеуристички алгоритам за претрагу, конструисаног од стране S. Koenig and M. Likhachev изграђеног на осову LPA*,^[5] то је инкрементациони хеуристички алгоритам за претрагу који комбинује идеје А* и динамичког SWSF-FP.^[6]

Сва три алгоритма претраге засноване су на истим основним претпоставкама, а то је проблем планирања путање, у којој робот мора да се креће ка датом циљу чије су координате на непознатом терену. Он прави претпоставке о непознатом делу терена (нпр. да на том терену не постоје препреке и сл.) и проналази најкраћи пут од своје тренутне координате до координате циља под овим претпоставкама. Робот потом следи пут. Када се посматра нова мапа информација, додају се и информације о мапи и ако је потребно, репланирање новог најкраћег пута од својих тренутне координате. Алгоритам понавља процес док робот не достигне циљне координате или утврди да циљне координате не могу бити постигнуте. При прелазу кроз непознат терен, нове препреке могу бити често откривене, тако да ово репланирање треба да буде брзо.

D* и његове варијанте су у широкој употреби за мобилне роботе као и код аутономних возила за навигацију. Тренутни системи се обично заснива на D* Lite.

D*

Оригинални D* представио је Ентони Стенц 1994. D* Име потиче од термина „Динамичан А* ", јер се алгоритам понаша као звезда.

Операције

Основне операције D* су наведене у наставку. Као и Дијкстра алгоритам и А*, и D* води листу чворова које треба проценити, која је позната као „отворена листа“. Чворови су означене једном од следећих ознака:

• НОВ, што значи да се никада није стављен на отвореној листи;
• ОТВОРЕН, што значи да је тренутно на отвореној листи;
• ЗАТВОРЕН, што значи да више није на отвореној листи;
• РАСТ, показује да је његово цена већа него када је последње пут био у отвореној листи;
• ОПАДАЊЕ, указује да је његово цена мсња него када је последње пут био у отвореној листи;

Проширење

Алгоритам ради тако итеративно изабира чвор из отворене листе и означује га. Тада се пропагира промене чвора да код цве суседне чворове и ставља их на отвореној листи. Овај процес се зове „експанзија“. За разлику од А*, који следи пут од почетка до краја, D* почиње претраживањем уназад од циљног чвора. Сваки такав чвор има показивач уназад који се односи на следећи чвор који води до циља, а сваки чвор зна тачну цену на мети. Када почетни чвор следећи који треба буде „проширен“, то значи да је алгоритам завршен, а пут до циља може се наћи једноставно пратећи показиваче уназад.

Руковање препрекама

Када се открије препрека на путу кроз који се жели прећи, све тачке које су погођене поново се постављају у отвореној листи, и њих ожначавамо са РАСТ. Пре тога тим чворовима се повећава цени, међутим, алгоритам проверава своје суседе и испитује да ли може да смањи трошкове на чвора. Ако не, стсње се с преноси на све потомке чворова, односно, чворови који имају показиваче на њега. Тада се чворови оцењују. Када чворови означени са „РАСТ“ могу бити редуковани, њихов бекпоинтер се ажурира и прелазу стање „ОПАДАЊА“. Ови таласи подизање и спуштање су срце D*. Алгоритам је само радио на тачкама које су погођене променама цене.

Још једна препрека

Овог пута, препрека се не може заобићи тако елегантно. Ниједна тачка не може да пронађе нови пут преко комшија. Стога, они настављају да пропагирају своје повећање цене. Само изван канала се могу наћи тачке, које могу довести до одредишта путем одрживог пута. На тај начин се два нижа таласа развијају, тако што се прошире до недоступних означених тачка са новим информацијама о рутама.

Фокусирани D*

Као што само име сугерише, са фокусом D* је продужетак од D* који користи хеуристике да се фокусира на пропагира РАСТ и ОПАДАЊЕ ка роботу. На овај начин, само се важна стања ажурирају, на исти начин на који се израчунава цена у А* само за неке од чворов.

D* Lite

D* Lite се не заснива на оригинални D* или D* Фокусирани, али примењује исту понашање. То је једноставније за разумевање и може се реализовати у мањим бројем линија кода, зато се и назив "D* Lite". По пперформансама он је бољи од фокусираног D*. D* Lite је заснована на доживотном планирању А*, који је уведен од стране К. Лихачев неколико година раније.

Минимална цена наспрам текућој цени

За D*, важно је направити разлику између текуће и минималне цене. Прво је важно у тренутку наплате, а други је критичн јер се сортира отворена листа. Функција која даје минималну цену је увек има најнижу цену у тренутној тачки, јер је то први улазак у отворену листу за њу.

Референце

1. Stentz, Anthony (1994), „Optimal and Efficient Path Planning for Partially-Known Environments”, Proceedings of the International Conference on Robotics and Automation: 3310—3317, CiteSeerX 10.1.1.15.3683  
2. Stentz, Anthony (1995), „The Focussed D* Algorithm for Real-Time Replanning”, Proceedings of the International Joint Conference on Artificial Intelligence: 1652—1659, CiteSeerX 10.1.1.41.8257  
3. 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 
4. 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 
5. Koenig, S.; Likhachev, M.; Furcy, D. (2004), „Lifelong Planning A*”, Artificial Intelligence Journal, 155 (1–2): 93—146, doi:10.1016/j.artint.2003.12.001 
6. Ramalingam, G.; Reps, T. (1996), „An incremental algorithm for a generalization of the shortest-path problem”, Journal of Algorithms, 21: 267—305, doi:10.1006/jagm.1996.0046 

Спољашње везе

• Sven Koenig's web page
• Anthony Stentz's web page