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

ขั้นตอนวิธีดีสตาร์ () เป็นขั้นตอนวิธีที่ใช้ในการหาเส้นทางการเคลื่อนที่ของหุ่นยนต์ จัดเป็นขั้นตอนวิธีการค้นหาแบบฮิวริสติกแบบหนึ่งเพราะมีการนำเทคนิคฮิวริสติกมาใช้ ขั้นตอนวิธีดีสตาร์นี้ได้ถูกนำมาใช้อย่างแพร่หลายซึ่งขั้นตอนวิธีดีสตาร์จะทำการสร้างเส้นทางการเคลื่อนที่ที่เหมาะสมที่สุดให้การวางแผนการเคลื่อนที่ของหุ่นยนต์เป็นไปอย่างมีประสิทธิภาพ ผู้นิยามและนำเสนอขั้นตอนวิธีนี้คือ แอนโทนี สเตนซ์ ซึ่งได้สร้างและพัฒนาไว้ในปี ค.ศ. 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:

 ดีสตาร์แบบดั้งเดิม
 โฟกัสดีสตาร์ ()  เป็นขึ้นตอนวิธีที่นำแนวคิดที่สำคัญของขั้นตอนวิธีเอสตาร์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. เป็นขั้นตอนวิธีที่พัฒนาเพิ่มเติมขึ้นมาโดย สเวน โคนิก () และ แมซิม ลิคาเชฟ () ซึ่งสร้างขึ้นมาโดยได้แนวคิดมาจากขั้นตอนวิธี LPA* S. Koenig, M. Likhachev and D. Furcy. Lifelong Planning A*. Artificial Intelligence Journal, 155, (1–2), 93–146, 2004., และนำมารวมกับแนวคิดของขั้นตอนวิธีเอสตาร์ และ Dynamic SWSF-FPG. Ramalingam, T. Reps, An incremental algorithm for a generalization of the shortest-path problem, Journal of Algorithms 21 (1996) 267–305..
 ดูเพิ่ม 
 ขั้นตอนวิธีเอสตาร์
 D* Lite
 Field D*

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

 อ้างอิง 

หมวดหมู่:ขั้นตอนวิธีการค้นหา
หมวดหมู่:ขั้นตอนวิธีกราฟ