Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ขั้นตอนวิธีดีสตาร์ (อังกฤษ: D* algorithm) เป็นขั้นตอนวิธีที่ใช้ในการเคลื่อนที่ของหุ่นยนต์ จัดเป็นขั้นตอนวิธีการค้นหาแบบฮิวริสติกแบบหนึ่งเพราะมีการนำเทคนิคฮิวริสติกมาใช้ ขั้นตอนวิธีดีสตาร์นี้ได้ถูกนำมาใช้อย่างแพร่หลายซึ่งขั้นตอนวิธีดีสตาร์จะทำการสร้างเส้นทางการเคลื่อนที่ที่เหมาะสมที่สุดให้การวางแผนการเคลื่อนที่ของหุ่นยนต์เป็นไปอย่างมีประสิทธิภาพ ผู้นิยามและนำเสนอขั้นตอนวิธีนี้คือ แอนโทนี สเตนซ์ ซึ่งได้สร้างและพัฒนาไว้ในปี ค.ศ. 1994 ที่มหาวิทยาลัยคาร์เนกีเมลลอน
นิยาม
ขั้นตอนวิธีการนี้เป็นส่วนขยายของขั้นตอนวิธีเอสตาร์ โดยสืบทอดแนวคิดโดยตรงมาจากแนวคิดของ ขั้นตอนวิธีของ Dijkstra โดยทั้งขั้นตอนวิธีเอสตาร์และขั้นตอนวิธี Dijkstra จะไม่สามารถตอบสนองต่อการเปลี่ยนแปลงในกราฟในระหว่างหรือหลังจากการขยายตัวของกระบวนการในขั้นตอนวิธี ในทั้งสองขั้นตอนวิธีนี้ที่ผู้ใช้อาจจะต้องทิ้งผลทั้งหมดและเริ่มต้นใหม่อีกครั้งเมื่อมีการเปลี่ยนแปลงเกิดขึ้น โดยเฉพาะอย่างยิ่งเมื่อทำงานร่วมกับหุ่นยนต์ภายใต้เงื่อนไขที่เป็นจริง (เช่นช่วงเซ็นเซอร์จำกัด , สภาพแวดล้อมที่ไม่คุ้นเคย)
ชื่อของขั้นตอนวิธีนี้ได้มีที่มามาจากความที่ขั้นตอนวิธีนี้เป็นขั้นตอนวิธีที่ถูกพัฒนาต่อยอดมาจากขั้นตอนวิธีเอสตาร์ซึ่งมีการเปลี่ยนแปลงให้สามารถเปลี่ยนแปลงค่าพารามิเตอร์ต่างๆในระหว่างการวิเคราะห์หาเส้นทาง ซึ่งความสามารถที่เพิ่มเข้ามานี้นั้นสามารถเรียกได้ว่ามีความเป็น "ไดนามิก" จึงเปรียบได้ว่าขั้นตอนวิธีนี้เป็นไดนามิกเอสตาร์ เราจึงตั้งชื่อของขั้นตอนวิธีนี้ว่า ขั้นตอนวิธีดีสตาร์
หลักการ
ทุกๆจุดที่ถูกรู้จักแล้วจะถูกนำเข้ามาเก็บไว้ใน โอเพ่นลิสต์ (เป็นรายการสำหรับเก็บจุดที่เอาไว้เก็บจุดต่างๆได้) โดยที่ตอนเริ่มต้นนั้นเราจะมีเพียงแค่จุดสุดท้ายหรือเป้าหมายซึ่งจะถูกเก็บอยู่ใน โอเพ่นลิสต์ เพียงตัวเดียว ซึ่งจนกว่าจะเจอจุดเริ่มต้นของเรา โอเพ่นลิสต์ นั้นจะถูกเพิ่มจุดและมาและนำจุดออกไปอยู่เรื่อยๆ เพื่อค้นหาเส้นทางในการเคลื่อนที่ระหว่างจุดเริ่มต้นไปยังจุดสุดท้าย
การขยายตัวของจุด
เริ่มต้นเราตัดสินใจว่าเลือกว่าจุดปัจจุบันที่เลือกมานั้นกำลังขยายไปสู่สถานะสูงขึ้นหรือไม่(ซึ่งหลังจากนั้นจะเปลี่ยนแปลงไปสู่สถานะต่ำกว่าโดยอัตโนมัติ) ถ้าพบว่าเป็นสถานะต่ำกว่าก็จะทำงานตามขั้นตอนของขั้นตอนวิธีเอสตาร์ตามปกตินั่นคือจุดที่อยู่รอบๆจุดของเรานั้นจะถูกตรวจสอบเพื่อหาว่าจะไปต่อทางจุดไหนต่อไปถึงจะดีกว่าจุดก่อนหน้าที่เคยหาเอาไว้ ซึ่งถ้าเป็นไปตามนี้นั่นหมายถึงจุดต่างๆที่อยู่รอบจุดของเราจะถูกนำมาคำนวณหาค่าใหม่และจะถูกเพิ่มเข้าไปยัง โอเพ่นลิสต์ ด้วย แต่ถ้าพบว่าก่อนหน้านั้นเป็นสถานะสูงขึ้น ค่าของจุดเราก็จะถูกส่งผ่านโดยทันทีไปให้กับจุดต่างๆที่กำลังมองเราเป็นเป้าหมายที่อยู่รอบๆจุดเรา ซึ่งการกระทำเหล่านี้เป็นการพยายามลดค่าของจุดต่างๆให้ได้เป็นค่าที่น้อยที่สุดซึ่งเป็นการทำการหาค่าที่ดีที่สุดนั่นเอง
ตัดสินใจสถานะสูงขึ้นหรือต่ำกว่า
การตัดสินใจนั้นจะขึ้นอยู่กับค่าปัจจุบันและค่าต่ำสุดของจุดๆนั้น ถ้าเส้นทางปัจจุบันมากกว่าค่าต่ำสุดจะถือว่าเข้าสู่สถานะสูงขึ้น และจะตามด้วยการทำการเพิ่มค่าต่อไป แต่อย่างไรก็ตามมันก็จะตรวจสอบว่าจะมีจุดใดๆที่อยู่รอบๆตัวมันหรือไม่ที่จะสามารถลดค่าให้กับจุดเราได้ ถ้าในจุดเหล่านั้นมีที่ถูกเซตและคำนวณค่าใหม่ไว้ก่อนแล้ว และถ้าทุกๆจุดที่อยู่รอบๆนั้นได้ถูกตรวจสอบแล้วและถูกตรวจสอบว่าค่าต่ำสุดตรงกับค่าปัจจุบันในกรณีนี้เราจะนำเข้าไปสู่สถานะต่ำกว่าถ้าเป็นกรณีอื่นนอกจากนี้มันจะยังคงอยู่ในสถานะสูงขึ้นและค่าของมันก็จะถูกเพิ่มขึ้น
กระบวนการ
การขยายตัวเริ่มต้น
ขั้นตอนสิธีนี้จะเริ่มต้นโดยการวนเลือกจุดแต่บะจุดจากโอเพ่นลิสต์มาจัดการทีละตัว จากนั้นมันก็จะส่งผ่านค่าที่เปลี่ยนแปลงไปยังจุดที่อยู่รอบๆตัวและเก็บจุดรอบๆตัวนั้นไปไว้ยังโอเพ่นลิสต์ ซึ่งกระบวกการของขั้นตอนวิธีดีสตาร์นี้จะตรงกันข้ามกับขั้นตอนวิธีเอสตาร์ตรงที่การขยายตัวของจุดจะเริ่มจากจุดเป้าหมายมาสู่จุดเริ่มต้นไม่ใช่จุดเริ่มต้นไปสู้จุดเป้าหมายอย่างในขั้นตอนวิธีเอสตาร์ และจุดต่างๆที่ถูกขยายไปนั้นจะมีสิ่งที่เรียกว่าตัวชี้ย้อนกลับ(back pointer) เพื่อชี้ไปยังจุดที่อยู่ในเส้นทางจุดถัดไปซึ่งจะนำทางไปสู่จุดมุ่งหมายได้ และขั้นตอนวิธีนี้จะหยุดทางงานเมื่อจุดถัดไปที่เรียกเข้ามานั้นเป็นจุดเริ่มต้นนั่นคือสิ้นสุดการทำงานเจอเส้นทางที่ต้องการแล้วซึ่งเส้นทางนี้นั้นสามารถหาได้อย่างง่ายๆจากการไล่ค้นหาเรื่อยๆตามตัวชี้ย้อนกลับ
การจัดการสิ่งกีดขวาง
เมื่อสิ่งกีดขวางนั้นถูกพบในระหว่างการหาเส้นทาง ทุกๆจุดที่ถูกผลกระทบจากการเปลี่ยนแปลงนี้จะถูกนำเข้ามาเก็บไว้ในโอเพ่นลิสต์และในครั้งนี้แต่ละจุดนั้นก็จะถูกทำเครื่องหมายว่าอยู่ในสถานะสูงขึ้น อย่างไรก็ตามจุดที่อยู่รอบๆก็จะถูกตรวจสอบว่าสามารถลดค่าของจุดได้หรือไม่ ถ้าไม่ก็จะส่งผ่านสถานะสูงขึ้นไปยังจุดที่เป็นจุดลูกของจุดๆนั้นซึ่งตัวชี้ย้อนกลับจะเป็นตัวชี้นั่นเอง และจะมีการสร้างเวฟขึ้นมา เมื่อจุดที่อยู่ในสถานะสูงขึ้นสามารถลดค่าได้ตัวชี้ย้อนกลับของมันก็จุดถูกอัปเดตค่าและก็จะส่งผ่านสถานะต่ำกว่าไปยังจุดที่อยู่รอบๆ ซึ่งเวฟของสถานะสูงขึ้นและต่ำกว่านั้นเป็นหัวใจที่สำคัญของขั้นตอนวิธีดีสตาร์
การเกิดสิ่งกีดขวางเพิ่มขึ้นอีก
ในครั้งนี้จะมีสิ่งกีดขวางที่อยู่ในลักษณะปิดมิดซึ่งจะทำให้เส้นทางการขยายของเราไม่สามารถผ่านไปได้โดยตรง โดยไม่มีจุดใดเลยที่จะสามารถหาเส้นทางใหม่จากจุดที่อยู่รอบๆได้ ดังนั้นจุดเหล่านั้นก็จะแพร่ขยายค่าต่อไปเรื่อยๆก็จะสามารถเจอเส้นทางใหม่ที่สามารถพาไปยังจุดเป้าหมายได้
รหัสเทียม
อัลกอรึทึมสามารถแสดงด้วยรหัสเทียมได้ดังนี้
while(openList.isNotEmpty()) { point = openList.firstElement(); expanding(point); } void expanding(currentPoint) { boolean isRaise = isRaise(currentPoint); double cost; for each(neighbor in currentPoint.getNeighbor()) { if(isRaise) { if(neighbor.nextPoint == currentPoint) { neighbor.setNextPointAndUpdateCost(currentPoint); openList.add(neighbor); } else { cost = neighbor.calculateCostOver(currentPoint); if(cost < neighbor.getcost()) { currentPoint.setCurrentCostToMinimalCost(); openList.add(currentPoint); } } } else { cost=neighbor.calculateCostOver(currentPoint); if(cost < neighbor.getcost()) { neighbor.setNextPointAndUpdateCost(currentPoint); openList.add(neighbor); } } } } boolean isRaise(point) { double cost; if(point.getCurrentCost() > point.getMinimalcost()) { for each(neighbor in currentPoint.getNeighbor()) { cost = currentPoint.calculateCostOver(neighbor); if(cost < point.getCurrentCost()) { currentPoint.setNextPointAndUpdateCost(neighbor); } } } return point.getCurrentCost() > point.getMinimalCost(); } ขั้นตอนวิธีอื่นๆที่เกี่ยวข้องหรือใกล้เคียง
ดีสตาร์ is any one of the following three related incremental search algorithms:
- ดีสตาร์แบบดั้งเดิม
- โฟกัสดีสตาร์ (อังกฤษ: Focussed D*) เป็นขึ้นตอนวิธีที่นำแนวคิดที่สำคัญของขั้นตอนวิธีเอสตาร์ และ ดีสตาร์แบบดั้งเดิม มารวมเข้าไว้ด้วยกัน
- ดีสตาร์ไลท์ (อังกฤษ: D* Lite) เป็นขั้นตอนวิธีที่พัฒนาเพิ่มเติมขึ้นมาโดย สเวน โคนิก (อังกฤษ: Sven Koenig) และ แมซิม ลิคาเชฟ (อังกฤษ: Maxim Likhachev) ซึ่งสร้างขึ้นมาโดยได้แนวคิดมาจากขั้นตอนวิธี LPA* , และนำมารวมกับแนวคิดของขั้นตอนวิธีเอสตาร์ และ Dynamic SWSF-FP.
ดูเพิ่ม
- ขั้นตอนวิธีเอสตาร์
- D* Lite
- Field D*
เชื่อมโยงภายนอก
- เอกสารเผยแพร่ฉบับดั้งเดิมของ แอนโทนี่ สเตนซ์ (ภาษาอังกฤษ)
อ้างอิง
- 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", In Proceedings of the International Joint Conference on Artificial Intelligence: 1652–1659
- P. Hart, N. Nilsson and B. Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Trans. Syst. Science and Cybernetics, SSC-4(2), 100–107, 1968.
- S. Koenig and M. Likhachev. Fast Replanning for Navigation in Unknown Terrain. Transactions on Robotics, 21, (3), 354–363, 2005.
- S. Koenig, M. Likhachev and D. Furcy. Lifelong Planning A*. Artificial Intelligence Journal, 155, (1–2), 93–146, 2004.
- G. Ramalingam, T. Reps, An incremental algorithm for a generalization of the shortest-path problem, Journal of Algorithms 21 (1996) 267–305.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
khntxnwithidistar xngkvs D algorithm epnkhntxnwithithiichinkarekhluxnthikhxnghunynt cdepnkhntxnwithikarkhnhaaebbhiwristikaebbhnungephraamikarnaethkhnikhhiwristikmaich khntxnwithidistarniidthuknamaichxyangaephrhlaysungkhntxnwithidistarcathakarsrangesnthangkarekhluxnthithiehmaasmthisudihkarwangaephnkarekhluxnthikhxnghunyntepnipxyangmiprasiththiphaph phuniyamaelanaesnxkhntxnwithinikhux aexnothni setns sungidsrangaelaphthnaiwinpi kh s 1994 thimhawithyalykharenkiemllxnniyamkhntxnwithikarniepnswnkhyaykhxngkhntxnwithiexstar odysubthxdaenwkhidodytrngmacakaenwkhidkhxng khntxnwithikhxng Dijkstra odythngkhntxnwithiexstaraelakhntxnwithi Dijkstra caimsamarthtxbsnxngtxkarepliynaeplnginkrafinrahwanghruxhlngcakkarkhyaytwkhxngkrabwnkarinkhntxnwithi inthngsxngkhntxnwithinithiphuichxaccatxngthingphlthnghmdaelaerimtnihmxikkhrngemuxmikarepliynaeplngekidkhun odyechphaaxyangyingemuxthanganrwmkbhunyntphayitenguxnikhthiepncring echnchwngesnesxrcakd sphaphaewdlxmthiimkhunekhy chuxkhxngkhntxnwithiniidmithimamacakkhwamthikhntxnwithiniepnkhntxnwithithithukphthnatxyxdmacakkhntxnwithiexstarsungmikarepliynaeplngihsamarthepliynaeplngkhapharamietxrtanginrahwangkarwiekhraahhaesnthang sungkhwamsamarththiephimekhamaninnsamartheriykidwamikhwamepn idnamik cungepriybidwakhntxnwithiniepnidnamikexstar eracungtngchuxkhxngkhntxnwithiniwa khntxnwithidistarhlkkarthukcudthithukruckaelwcathuknaekhamaekbiwin oxephnlist epnraykarsahrbekbcudthiexaiwekbcudtangid odythitxnerimtnnneracamiephiyngaekhcudsudthayhruxepahmaysungcathukekbxyuin oxephnlist ephiyngtwediyw sungcnkwacaecxcuderimtnkhxngera oxephnlist nncathukephimcudaelamaaelanacudxxkipxyueruxy ephuxkhnhaesnthanginkarekhluxnthirahwangcuderimtnipyngcudsudthay karkhyaytwkhxngcud erimtneratdsinicwaeluxkwacudpccubnthieluxkmannkalngkhyayipsusthanasungkhunhruxim sunghlngcaknncaepliynaeplngipsusthanatakwaodyxtonmti thaphbwaepnsthanatakwakcathangantamkhntxnkhxngkhntxnwithiexstartampktinnkhuxcudthixyurxbcudkhxngeranncathuktrwcsxbephuxhawacaiptxthangcudihntxipthungcadikwacudkxnhnathiekhyhaexaiw sungthaepniptamninnhmaythungcudtangthixyurxbcudkhxngeracathuknamakhanwnhakhaihmaelacathukephimekhaipyng oxephnlist dwy aetthaphbwakxnhnannepnsthanasungkhun khakhxngcuderakcathuksngphanodythnthiipihkbcudtangthikalngmxngeraepnepahmaythixyurxbcudera sungkarkrathaehlaniepnkarphyayamldkhakhxngcudtangihidepnkhathinxythisudsungepnkarthakarhakhathidithisudnnexng tdsinicsthanasungkhunhruxtakwa kartdsinicnncakhunxyukbkhapccubnaelakhatasudkhxngcudnn thaesnthangpccubnmakkwakhatasudcathuxwaekhasusthanasungkhun aelacatamdwykarthakarephimkhatxip aetxyangirktammnkcatrwcsxbwacamicudidthixyurxbtwmnhruximthicasamarthldkhaihkbcuderaid thaincudehlannmithithukestaelakhanwnkhaihmiwkxnaelw aelathathukcudthixyurxbnnidthuktrwcsxbaelwaelathuktrwcsxbwakhatasudtrngkbkhapccubninkrninieracanaekhaipsusthanatakwathaepnkrnixunnxkcaknimncayngkhngxyuinsthanasungkhunaelakhakhxngmnkcathukephimkhunkrabwnkarkarkhyaytwerimtn khntxnsithinicaerimtnodykarwneluxkcudaetbacudcakoxephnlistmacdkarthilatw caknnmnkcasngphankhathiepliynaeplngipyngcudthixyurxbtwaelaekbcudrxbtwnnipiwyngoxephnlist sungkrabwkkarkhxngkhntxnwithidistarnicatrngknkhamkbkhntxnwithiexstartrngthikarkhyaytwkhxngcudcaerimcakcudepahmaymasucuderimtnimichcuderimtnipsucudepahmayxyanginkhntxnwithiexstar aelacudtangthithukkhyayipnncamisingthieriykwatwchiyxnklb back pointer ephuxchiipyngcudthixyuinesnthangcudthdipsungcanathangipsucudmunghmayid aelakhntxnwithinicahyudthangnganemuxcudthdipthieriykekhamannepncuderimtnnnkhuxsinsudkarthanganecxesnthangthitxngkaraelwsungesnthangninnsamarthhaidxyangngaycakkarilkhnhaeruxytamtwchiyxnklb karcdkarsingkidkhwang emuxsingkidkhwangnnthukphbinrahwangkarhaesnthang thukcudthithukphlkrathbcakkarepliynaeplngnicathuknaekhamaekbiwinoxephnlistaelainkhrngniaetlacudnnkcathukthaekhruxnghmaywaxyuinsthanasungkhun xyangirktamcudthixyurxbkcathuktrwcsxbwasamarthldkhakhxngcudidhruxim thaimkcasngphansthanasungkhunipyngcudthiepncudlukkhxngcudnnsungtwchiyxnklbcaepntwchinnexng aelacamikarsrangewfkhunma emuxcudthixyuinsthanasungkhunsamarthldkhaidtwchiyxnklbkhxngmnkcudthukxpedtkhaaelakcasngphansthanatakwaipyngcudthixyurxb sungewfkhxngsthanasungkhunaelatakwannepnhwicthisakhykhxngkhntxnwithidistar karekidsingkidkhwangephimkhunxik inkhrngnicamisingkidkhwangthixyuinlksnapidmidsungcathaihesnthangkarkhyaykhxngeraimsamarthphanipidodytrng odyimmicudidelythicasamarthhaesnthangihmcakcudthixyurxbid dngnncudehlannkcaaephrkhyaykhatxiperuxykcasamarthecxesnthangihmthisamarthphaipyngcudepahmayidrhsethiymxlkxruthumsamarthaesdngdwyrhsethiymiddngni while openList isNotEmpty point openList firstElement expanding point void expanding currentPoint boolean isRaise isRaise currentPoint double cost for each neighbor in currentPoint getNeighbor if isRaise if neighbor nextPoint currentPoint neighbor setNextPointAndUpdateCost currentPoint openList add neighbor else cost neighbor calculateCostOver currentPoint if cost lt neighbor getcost currentPoint setCurrentCostToMinimalCost openList add currentPoint else cost neighbor calculateCostOver currentPoint if cost lt neighbor getcost neighbor setNextPointAndUpdateCost currentPoint openList add neighbor boolean isRaise point double cost if point getCurrentCost gt point getMinimalcost for each neighbor in currentPoint getNeighbor cost currentPoint calculateCostOver neighbor if cost lt point getCurrentCost currentPoint setNextPointAndUpdateCost neighbor return point getCurrentCost gt point getMinimalCost khntxnwithixunthiekiywkhxnghruxiklekhiyngdistar is any one of the following three related incremental search algorithms distaraebbdngedim ofksdistar xngkvs Focussed D epnkhuntxnwithithinaaenwkhidthisakhykhxngkhntxnwithiexstar aela distaraebbdngedim marwmekhaiwdwykn distarilth xngkvs D Lite epnkhntxnwithithiphthnaephimetimkhunmaody sewn okhnik xngkvs Sven Koenig aela aemsim likhaechf xngkvs Maxim Likhachev sungsrangkhunmaodyidaenwkhidmacakkhntxnwithi LPA aelanamarwmkbaenwkhidkhxngkhntxnwithiexstar aela Dynamic SWSF FP duephimkhntxnwithiexstar D Lite Field D echuxmoyngphaynxkexksarephyaephrchbbdngedimkhxng aexnothni setns phasaxngkvs xangxingStentz 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 In Proceedings of the International Joint Conference on Artificial Intelligence 1652 1659 P Hart N Nilsson and B Raphael A Formal Basis for the Heuristic Determination of Minimum Cost Paths IEEE Trans Syst Science and Cybernetics SSC 4 2 100 107 1968 S Koenig and M Likhachev Fast Replanning for Navigation in Unknown Terrain Transactions on Robotics 21 3 354 363 2005 S Koenig M Likhachev and D Furcy Lifelong Planning A Artificial Intelligence Journal 155 1 2 93 146 2004 G Ramalingam T Reps An incremental algorithm for a generalization of the shortest path problem Journal of Algorithms 21 1996 267 305