การค้นหาแบบดีสตาร์

ขั้นตอนวิธีดีสตาร์ (อังกฤษ: 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*

เชื่อมโยงภายนอก

• เอกสารเผยแพร่ฉบับดั้งเดิมของ แอนโทนี่ สเตนซ์ (ภาษาอังกฤษ)

อ้างอิง

1. Stentz, Anthony (1994). "Optimal and Efficient Path Planning for Partially-Known Environments". Proceedings of the International Conference on Robotics and Automation: 3310–3317.
2. Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning", In Proceedings of the International Joint Conference on Artificial Intelligence: 1652–1659
3. 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.
4. S. Koenig and M. Likhachev. Fast Replanning for Navigation in Unknown Terrain. Transactions on Robotics, 21, (3), 354–363, 2005.
5. S. Koenig, M. Likhachev and D. Furcy. Lifelong Planning A*. Artificial Intelligence Journal, 155, (1–2), 93–146, 2004.
6. G. Ramalingam, T. Reps, An incremental algorithm for a generalization of the shortest-path problem, Journal of Algorithms 21 (1996) 267–305.