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

ขั้นตอนวิธีดีสตาร์ (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  point.getMinimalcost)
{
for each(neighbor in currentPoint.getNeighbor)
{
cost = currentPoint.calculateCostOver(neighbor);
if(cost  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*
== เชื่อมโยงภายนอก ==
เอกสารเผยแพร่ฉบับดั้งเดิมของ แอนโทนี่ สเตนซ์ (ภาษาอังกฤษ)
== อ้างอิง ==
ขั้นตอนวิธีการค้นหา
ขั้นตอนวิธีกราฟ