คำตอบโดยตรง
Lifelong Planning A* หรือ LPA* เป็นอัลกอริทึมหาเส้นทางสั้นที่สุดซ้ำบนกราฟเดิม เมื่อค่าต้นทุนของเส้นเชื่อมบางเส้นเปลี่ยน มันเก็บผลค้นหาครั้งก่อนแล้วซ่อมค่าที่ไม่สอดคล้องกัน แทนที่จะเริ่มคำนวณทุกจุดใหม่ตั้งแต่ต้นทุกครั้ง ภายใต้สมมติฐานของกราฟและ heuristic มันคืนเส้นทางสั้นที่สุดหลังการซ่อม แต่ไม่ได้แปลว่าจะเร็วกว่า A* ทุกกรณี
บทความนี้อธิบาย LPA* แบบเดินหน้าจากจุดเริ่มต้นคงที่ S ไปยังเป้าหมายคงที่ G บนกราฟกำกับขนาดเล็ก ตัวอย่างแล็บเป็น SIMULATION สำหรับเรียนรู้การทำงานของ g, rhs, คิวลำดับความสำคัญ และการซ่อมหลังเปลี่ยน edge cost เท่านั้น ไม่มีหุ่นยนต์เคลื่อนที่ ไม่มีแผนที่ซ่อน ไม่มีโมเดลภาษา และไม่มีการฝึกหรืออัปเดตน้ำหนักโมเดล
ขอบเขตนี้ต่างจากบทความ Active Neural SLAM ที่แยกเป้าหมายสำรวจ เส้นทาง และ action และ 3D Scene Graphs ที่ยึดแผนกับโครงสร้างฉาก ซึ่งตอบคนละคำถามกับการซ่อม shortest path บนกราฟกำกับ
ทำไมต้องเก็บผลค้นหาไว้
สมมติระบบต้องหาทางต้นทุนต่ำสุดจาก S ไป G ซ้ำ ๆ เมื่อถนนปิดหรือค่าผ่านทางเปลี่ยน ระบบต้องคำนวณเส้นทางใหม่จากกราฟปัจจุบัน
ทางตรงไปตรงมาคือเรียก A* ใหม่ทุกครั้ง วิธีนี้เรียบง่ายและเป็น baseline ที่ดี แต่เมื่อมีการแก้ต้นทุนบ่อย ผลค้นหาหลายส่วนอาจยังใช้ได้ การเริ่มใหม่ก็ทิ้งข้อมูลเหล่านั้น
LPA* แยก “ค่าที่ระบบเชื่อว่าถูกต้องแล้ว” ออกจาก “ค่าที่ควรเป็นตามข้อมูลเพื่อนบ้านหนึ่งก้าว” ถ้าสองค่านี้ยังตรงกัน จุดนั้นก็สอดคล้องเฉพาะที่ หาก edge cost เปลี่ยนแล้วทำให้ค่าประมาณขัดกัน จุดนั้นจะเข้า priority queue เพื่อให้ระบบตรวจและส่งผลต่อจุดข้างเคียง การซ่อมจึงเริ่มจากบริเวณที่ได้รับผล ไม่ได้หมายความว่าทุกครั้งจะมีงานน้อย: การเปลี่ยนแปลงที่กระทบเส้นทางส่วนใหญ่ยังอาจทำให้ต้องประมวลผลหลายจุด
งานวิจัย Koenig, Likhachev และ Furcy เสนอ LPA* เป็นการผสานการค้นแบบใช้ heuristic กับการค้นแบบเพิ่มทีละส่วน ผู้เขียนรายงานประโยชน์ในบางชุดปัญหา โดยเฉพาะเมื่อการเปลี่ยนแปลงไม่มากและต้นไม้การค้นเดิมกับใหม่ทับซ้อนกันมาก อย่างไรก็ตามพวกเขาระบุว่า LPA* ใช้เวลาต่อการขยายจุดมากกว่า A* และยังต้องทำความเข้าใจว่าเงื่อนไขใดทำให้คุ้มในงานจริง รายละเอียดและข้อจำกัดนี้เป็น REPORTED CLAIM จากบทความต้นฉบับ ไม่ใช่ผลที่เราทำซ้ำ (บทความและบทสรุปผู้เขียน; ต้นฉบับ PDF ที่ผู้เขียนฝากไว้)
รากฐาน: g กับ rhs ตอบคนละคำถาม
กำหนดกราฟกำกับแบบมีน้ำหนัก มีจุดยอดและ edge ที่ชี้ทิศทาง ค่า edge c(u,v) คือค่าใช้จ่ายจาก u ไป v จุดเริ่มต้น S และเป้าหมาย G คงที่ตลอดชุดการค้นหา ค่าต้นทุนที่ใช้เดินได้ต้องเป็นบวก ส่วน edge ที่ใช้ไม่ได้อาจแทนด้วยอนันต์ หรือใน Lab ใช้ null เพื่อแสดงว่าไม่มีทางเชื่อม
FACT: LPA* เก็บสองค่าต่อจุดยอด g(v) และ rhs(v). ค่า g(v) คือค่าประมาณระยะทางจาก S ที่เก็บไว้ในสถานะค้นหา ซึ่งอาจล้าสมัยหลังกราฟเปลี่ยน ส่วน rhs(v) คือค่าหนึ่งก้าวที่คำนวณจาก predecessor ของ v (Koenig, Likhachev, & Furcy, §4):
rhs(S) = 0
rhs(v) = min [g(u) + c(u,v)] สำหรับ edge กำกับทุกเส้นที่เข้า v
ถ้าไม่มี predecessor ที่ไปถึงได้ ค่า rhs(v) เป็นอนันต์ สภาวะที่ g(v) = rhs(v) เรียกว่า locally consistent หรือสอดคล้องเฉพาะที่ ถ้า g(v) > rhs(v) มีค่าหนึ่งก้าวที่ต่ำกว่าค่า g เดิม จุดนี้เรียก overconsistent ถ้า g(v) < rhs(v) ค่า g เดิมต่ำกว่าค่า rhs ใหม่ เรียก underconsistent
เหตุที่ต้องมีสองค่าแทนการเขียนทับค่าเดิมทันที คือเราต้องรู้ว่าการเปลี่ยนต้นทุนทำให้ค่าระยะทางสั้นลงหรือยาวขึ้น การลดต้นทุนอาจเปิดทางที่ดีกว่าและทำให้ rhs ต่ำกว่า g การเพิ่มต้นทุนอาจทำให้ค่า g เดิมต่ำเกินจริงจน rhs สูงกว่า g สองกรณีนี้ต้องซ่อมต่างกัน
LPA* ใช้คีย์สองส่วนเรียงลำดับแบบ lexicographic:
Key(v) = [min(g(v), rhs(v)) + h(v,G), min(g(v), rhs(v))]
ในเวอร์ชันทั่วไป h เป็น heuristic ที่ไม่ติดลบและ consistent กับกราฟ สำหรับแล็บนี้กำหนด h=0 ทุกจุด ซึ่งยัง consistent และทำให้เห็นผลของการเก็บสถานะเดิมโดยไม่ต้องถกเรื่องการประมาณระยะทาง ค่าคีย์ที่เท่ากันในเครื่องมือใช้ลำดับรหัสจุดยอดแบบ ASCII เพื่อให้ผู้เรียนเห็นลำดับเดิมทุกครั้ง นี่เป็นกติกาเพื่อความทำซ้ำได้ใน UI ไม่ใช่เงื่อนไขจำเป็นเฉพาะของ LPA*
Architecture: จาก edge ที่เปลี่ยนไปยังจุดที่ต้องซ่อม
ใน LPA* แบบ forward ค่า g แทนค่าประมาณระยะทางจาก S ไปยังจุดอื่น และอาจยังล้าสมัยหลังมีการแก้กราฟ ดังนั้น rhs(v) มองย้อนหนึ่งก้าวไปยัง predecessor ที่นำเข้ามายัง v เมื่อ edge (u,v) เปลี่ยน จุดที่ต้องเรียก UpdateVertex คือ v เพราะสมการสำรองค่าของ v ใช้ต้นทุน edge นี้โดยตรง ถ้ากราฟเป็นแบบไม่มีทิศทาง ต้องแทนถนนสองทางด้วย edge กำกับสองเส้น และปรับปลายทางของทั้งคู่เมื่อเปลี่ยนราคา (LPA* Figure 6 และ Appendix A.1)
ขั้นตอน UpdateVertex(v) คำนวณ rhs ใหม่จาก predecessor ทั้งหมด ลบรายการเก่าของ v ออกจากคิว แล้วใส่ v กลับเข้าไปก็ต่อเมื่อ g(v) และ rhs(v) ไม่เท่ากัน เมื่อจุดกลับมาสอดคล้องก็ไม่จำเป็นต้องค้างในคิว (Figure 6, journal manuscript)
เมื่อ ComputeShortestPath ทำงาน มันหยิบจุดที่คีย์ต่ำสุดออกมา หาก g>rhs ระบบตั้ง g=rhs แล้วอัปเดต successors เพราะค่าระยะทางจากจุดนี้อาจเปลี่ยน หาก g<rhs ระบบตั้ง g=∞ จากนั้นอัปเดตจุดเดิมและ successors เพื่อให้ผลกระทบกระจายต่อไป คิวและคีย์ถูกดูแลผ่าน UpdateVertex ตาม pseudocode พื้นฐานของ Figure 6 (ต้นฉบับ)
การซ่อมหยุดเมื่อเป้าหมาย G สอดคล้อง และคีย์ต่ำสุดที่เหลือในคิวไม่ต่ำกว่าคีย์ของ G หาก g(G) ยังเป็นอนันต์เมื่อจบ ก็ไม่มีเส้นทางที่ต้นทุนจำกัดในกราฟปัจจุบัน จุดอื่นบางจุดอาจยังไม่สอดคล้อง เพราะไม่จำเป็นต่อการหาคำตอบที่ G ตามเงื่อนไขหยุดนี้
ลำดับการทำงาน: ตัวอย่างกราฟเล็กที่เปลี่ยนจริง
กราฟสาธิตประกอบด้วยจุด S, A, B, C, D, X, G และ edge กำกับ 10 เส้น: S→A, A→B, B→G, S→C, C→D, D→G, A→D, C→B, S→X, X→G ค่าเริ่มต้นของสามเส้นแรกคือ 2, 2, 2 จึงได้เส้นทาง S→A→B→G ต้นทุนรวม 6 เส้นทางสำรองผ่าน C และ D มีต้นทุน 9 ส่วนทางผ่าน X มีต้นทุน 40 เมื่อการค้นครั้งแรกจบ จุด X ยังอยู่ในคิว เพราะไม่จำเป็นต้องประมวลผลจุดที่ไม่อาจปรับคำตอบของ G ภายใต้เงื่อนไขหยุด
เมื่อแก้ต้นทุน edge B→G จาก 2 เป็น 8 คำตอบเดิมที่มีต้นทุน 6 ต้องตรวจใหม่ การคำนวณ rhs ของ G เห็นทางผ่าน D ที่มีค่า 9 จึงทำให้ G underconsistent: g เดิมยังเป็น 6 แต่ rhs ใหม่เป็น 9 ก่อนซ่อม UI แสดงสถานะ NEEDS_REPAIR และซ่อน path จนกว่าจะคำนวณคำตอบชุดใหม่ เมื่อซ่อมแล้ว ได้เส้นทาง S→C→D→G ต้นทุน 9 และมี repair expansions 2 ตาม trace ของ Lab
ถ้าเปลี่ยน D→G จาก 5 เป็น 1 แทน rhs(G) ลดจาก 6 เป็น 5 ขณะที่ g เดิมเป็น 6 กรณีนี้ overconsistent และหลังซ่อมคำตอบใหม่คือ S→C→D→G ต้นทุน 5 โดยมี repair expansion 1 ตาม trace ทั้งสองกรณีช่วยให้เห็นว่าการเพิ่มและลดต้นทุนทำให้เกิดความไม่สอดคล้องคนละทิศ
ถ้าเปลี่ยน X→G จาก 20 เป็น 10 การเปลี่ยนแปลงอยู่นอกเส้นทางที่ดีที่สุดและไม่ทำให้คำตอบปัจจุบันแย่ลง ในสถานะฐาน X ยังอยู่ในคิวแต่คีย์ไม่ต่ำกว่าคีย์ G จึงซ่อมด้วย 0 repair expansions และคำตอบต้นทุน 6 ไม่เปลี่ยน จำนวน expansion ในตัวอย่างเล็กไม่ใช่คำทำนายเวลาในระบบใหญ่ และไม่ได้บอกว่าอัลกอริทึมหนึ่งเร็วกว่าอีกอัลกอริทึม
ถ้าตัดเส้นทางเข้าถึง G ทุกเส้นด้วยการตั้ง cost เป็น blocked ระบบต้องจบเป็น NO_PATH และไม่แสดง path ว่างว่าเป็นเส้นทางจริง ใน fixture นี้ repair expansions เท่ากับ 2 หากเปิด X→G กลับมาเป็น 2 หลังสถานะ no path เส้นทางใหม่คือ S→X→G ต้นทุน 22 และ repair expansions เท่ากับ 1 การเปิด edge กลับจึงเป็นการลดต้นทุนจากอนันต์ลงสู่ค่าบวก และ LPA* ซ่อมกราฟต่อได้
LPA* path repair explorer
Change one directed edge, inspect the inconsistent state, then step through the same incremental search used to plan the original route.
Directed graph
A highlighted route is shown only when the current search is READY. Edge arrows keep their fixed direction.
Search status
Priority queue U
g and rhs values
| Vertex | g | rhs | Consistent |
|---|
Last pop
No pop yet.
Work counters
What this model means
This is the finite, fixed Figure 6 forward-search example with h=0 and positive integer edge costs. A blocked edge has no transition. It has no robot movement or hidden world. When a changed edge leaves a vertex inconsistent, LPA* reuses earlier g values and repairs the affected part of the search. A consistent goal alone does not prove that repair is finished: the queue’s minimum key must also be no smaller than the goal key. READY can still leave unrelated vertices in U.
Interactive Explorer — SIMULATION: กราฟ S ถึง G นี้เป็นข้อมูลที่กำหนดไว้ชัดเจน ลองเริ่มจากค่าเริ่มต้น แล้วเปลี่ยนต้นทุนหนึ่ง edge เพื่อดู g, rhs และคิวก่อนกดซ่อม อ่านสถานะ NEEDS_REPAIR ก่อนเสมอ เพราะ path จะแสดงหลังการซ่อมจบตามเงื่อนไขหยุด ตัวนับ expansions คือจำนวนครั้งที่จุดถูกนำออกจากคิวและประมวลผลในกติกานี้ ไม่ใช่มิลลิวินาทีหรือผล benchmark
เปรียบเทียบสามวิธี: LPA*, A* เริ่มใหม่ และ Dijkstra เริ่มใหม่
| วิธี | ใช้อะไรจากการค้นก่อนหน้า | การค้นครั้งแรก | สิ่งที่ต้องอ่านให้ถูก |
|---|---|---|---|
| LPA* | เก็บ g/rhs และซ่อมจุดที่ไม่สอดคล้อง | ตรงกับ A* เมื่อใช้ heuristic และการตัดสินกรณีเสมอแบบเดียวกัน | อาจลดจำนวนงานบางชนิดเมื่อผลเดิมยังเกี่ยวข้อง แต่เพิ่ม bookkeeping และอาจไม่คุ้มเมื่อกระทบกว้าง |
| A* เริ่มใหม่ | ไม่เก็บผลค้นเดิมเป็นสถานะซ่อม | ใช้ heuristic นำการค้นไปหา G | เป็น baseline ที่มีประโยชน์ แต่ต้นทุนต่อการขยายจุดขึ้นกับโค้ดและโครงสร้างข้อมูล |
| Dijkstra เริ่มใหม่ | ไม่เก็บผลค้นเดิมเป็นสถานะซ่อม | เท่ากับแนวคิด A* เมื่อ h=0 | คำนวณจากต้นทางโดยไม่ใช้ heuristic; สำหรับแล็บ h=0 จึงเป็น baseline ที่ตรงกับการตั้งค่า |
FACT: ผลลัพธ์ที่ต้องเทียบคือเส้นทางและต้นทุนสั้นที่สุดภายใต้กราฟปัจจุบัน การเทียบอย่างเป็นธรรมต้องใช้กราฟ ชุดการเปลี่ยนต้นทุน เกณฑ์หยุด และ tie-breaking ที่ระบุชัด (LPA* §4 และ §8)
REPORTED CLAIM: งานต้นฉบับ LPA* เปรียบเทียบกับ breadth-first search, A* และ DynamicSWSF-FP ในชุดกราฟของผู้เขียน และรายงานทั้ง runtime บนเครื่องทดลองของยุคนั้นกับจำนวน vertex expansions และ heap operations รายงานนั้นเป็นผลของชุดทดลองในบทความ ไม่ใช่ผลทดสอบของ Lab นี้ (§8)
ANALYSIS: จำนวน expansion ไม่ใช่ตัวแทน runtime สำหรับเปรียบเทียบ incremental search ต่างวิธี ผู้เขียนเตือนว่าการขยายหนึ่งจุดมีต้นทุนไม่เท่ากันตามโครงสร้างข้อมูลและ implementation และ expansions ใช้เป็น runtime proxy ไม่ได้ ดังนั้นอย่าสรุปจากตัวเลข “ซ่อม 2 จุด” เทียบกับ “ค้นใหม่ 6 จุด” ว่าวิธีแรกเร็วกว่า หากต้องการสรุปเวลา ต้องทดสอบ implementation ที่ระบุรุ่นและสภาพแวดล้อมเดียวกัน พร้อมรายงาน runtime โดยตรง (คำเตือนผู้เขียน)
การประยุกต์ใช้: เมื่อคำตอบเดิมยังมีส่วนที่เป็นประโยชน์
ใน paper ผู้เขียนสาธิตการวางเส้นทางบน grid และใช้ LPA* เป็นฐานให้ SHERPA สำหรับ heuristic search ใน symbolic planning ระบบดังกล่าวเป็นการประยุกต์ผ่าน planner อีกชั้นหนึ่ง ไม่ใช่หลักฐานว่า LPA* โดยลำพังรองรับงานทุกชนิด (LPA* §9)
ANALYSIS: แนวคิด incremental repair อาจเป็นส่วนหนึ่งของ planner สำหรับ Agent ที่แก้กราฟเส้นทางหรือสถานะที่นิยามชัด เมื่อมีต้นทุนและการเปลี่ยนแปลงที่ตรวจสอบได้ แต่การเชื่อมต่อกับ Agent เป็นการออกแบบระบบแยก และไม่ใช่คุณสมบัติของ LPA* หรือหลักฐานว่า Agent เรียนรู้
LPA* ใช้กับโจทย์ที่แก้ shortest path ซ้ำบนกราฟเดิม เช่น ปรับต้นทุนเครือข่ายหรือเส้นทาง เมื่อกราฟชัดเจนและเก็บสถานะค้นเดิมได้ การเปลี่ยนเล็กอาจเอื้อให้ใช้ข้อมูลเดิมต่อ ส่วนการเปลี่ยนกว้างอาจลดประโยชน์ จึงควรเลือกจากรูปแบบอัปเดตและต้นทุนจริง
LPA* six mission challenge
Read the live search state and choose the next valid action and vertex. Each mission starts from its own fixture.
Directed graph
Search state
Queue U
| Vertex | g | rhs |
|---|
เกม 6 ภารกิจ — SIMULATION: แต่ละภารกิจให้ผู้เล่นอ่านกราฟ g/rhs และคิว แล้วเลือกการกระทำที่สอดคล้องกับสถานะ: ยอมรับ rhs, ทำให้ค่าที่ล้าสมัยใช้ไม่ได้, ใช้ path เมื่อ READY หรือหยุดเมื่อไม่มีทางไปถึง G เกมใช้กติกาและกราฟเดียวกับ Explorer เป้าหมายคือเรียนรู้การอ่านสถานะ ไม่ใช่ทดสอบความฉลาดหรือประสิทธิภาพของ AI
ข้อจำกัด: สิ่งที่ LPA* ไม่ได้ตอบ
ผู้เขียนเผยแพร่ โค้ด LPA* สำหรับ grid ที่มี random costs โดยหน้าโครงการเตือนว่าโค้ดบางส่วนค่อนข้างเก่า โค้ดสาธารณะจากงานปี 2002 นี้ใช้ optimized stopping test ที่ต่างจาก Figure 6 ซึ่งเป็นพื้นฐาน Lab ไม่ได้ build หรือรันโค้ดดังกล่าว; compatibility และ license สำหรับการนำไปใช้ยัง UNKNOWN (คำเตือนเรื่อง code และ runtime)
LPA* รับกราฟและต้นทุนจากระบบภายนอก ถ้าข้อมูลผิด เส้นทางสั้นที่สุดก็สั้นที่สุดตามข้อมูลผิดนั้น อัลกอริทึมไม่ตรวจความปลอดภัย ไม่รู้การเปลี่ยนแปลงจนมีข้อมูลใหม่ และไม่แทน uncertainty เชิงความน่าจะเป็นโดยอัตโนมัติ
LPA* แบบ forward ในบทความนี้ตรึง S และ G ไว้ จุดเริ่มใหม่หรือเป้าหมายใหม่เป็นปัญหาที่ต้องตรวจว่า formulation และ heuristic ยังใช้ได้หรือไม่ ส่วน D* Lite ถูกออกแบบให้ค้นย้อนจาก goal เพื่อทำ navigation เมื่อ current robot state เคลื่อนที่ และมี km สำหรับจัดการการเปลี่ยน reference point ของ heuristic การกล่าวว่า LPA* และ D* Lite เป็นชื่อเรียกแทนกันจะทำให้ทิศทางการอัปเดตและตัวแปรผิด
ค่ากลาง g, rhs, predecessor และ queue เป็นสถานะของตัววางแผนบนกราฟ ไม่ใช่ context window ของ LLM ไม่ใช่ retrieved memory และไม่ใช่ model weights การเปลี่ยนต้นทุนแล้วซ่อม shortest path ก็ไม่ใช่การเรียนรู้โมเดลภาษา
แล็บเป็นกราฟสาธิตขนาดเล็กที่กำหนดแน่นอน ตัวเลข expansion ที่เห็นเป็น trace ของกติกาจำลอง จึงใช้ฝึกอ่านการเปลี่ยนสถานะเท่านั้น ไม่ได้ทำซ้ำการทดลองของ Koenig และคณะ ไม่ได้วัด runtime และไม่ใช่ benchmark
คำถามที่ควรทดสอบต่อ
คำถามต่อไปคือการเปลี่ยนแบบใดทำให้ LPA* คุ้มกว่า A* ใหม่ และ heuristic หรือ priority queue เปลี่ยนผลอย่างไร ต้องตอบด้วยกราฟและ implementation ที่ระบุชัด พร้อมวัด runtime และหน่วยความจำจริง
เมื่อจุดเริ่มหรือเป้าหมายเปลี่ยน ต้องตรวจว่าสูตรและ heuristic ยังใช้ได้หรือไม่ Lab นี้ตรึง S และ G จึงไม่ตอบคำถามสำหรับหุ่นยนต์หรือ Agent ทั่วไป
ประเด็นสำคัญ
- LPA* แก้ shortest path ซ้ำโดยเก็บ
gและrhsจากการค้นก่อนหน้า - ใน formulation แบบ forward เมื่อ edge กำกับ
(u,v)เปลี่ยน ต้องอัปเดต rhs ของปลายทาง v - จุดที่
gไม่เท่ากับrhsคือจุดที่ต้องซ่อม; การเพิ่มและลดต้นทุนทำให้เกิดคนละชนิดของความไม่สอดคล้อง - LPA* รับประกันคำตอบ shortest path ภายใต้สมมติฐานของกราฟและ heuristic แต่ไม่ได้รับประกันว่าจะเร็วกว่าการค้นใหม่
- ตัวนับ expansions ใน Lab เป็น trace สำหรับการสอน ไม่ใช่ตัวแทน runtime หรือ benchmark
คำถามที่พบบ่อย
LPA* ต่างจาก A* อย่างไร?
A* ใช้ heuristic ช่วยค้น shortest path สำหรับโจทย์หนึ่งครั้ง ส่วน LPA* ใช้โครงสร้างคล้าย A* และเพิ่มการเก็บค่าที่ค้นไว้ เพื่อปรับคำตอบหลัง edge costs เปลี่ยน การค้นครั้งแรกเทียบเท่า A* เมื่อใช้ heuristic และ tie-breaking ที่เหมาะสม
rhs คือค่า shortest path ที่รับรองแล้วหรือไม่?
ไม่ใช่ rhs เป็น one-step lookahead จากค่า g ของ predecessor ส่วน g คือค่าที่การค้นเก็บไว้ ทั้งคู่ตรงกันเมื่อจุดนั้น locally consistent
ถ้า edge เป็นทางเดียว ต้องอัปเดตจุดใด?
ถ้าเปลี่ยน directed edge (u,v) ให้เรียก UpdateVertex ที่ v เพราะต้นทุน edge นี้เป็นหนึ่งในตัวเลือกที่ใช้คำนวณ rhs(v) ถ้าความเชื่อมโยงสองทางเปลี่ยน ต้องอัปเดตแต่ละ directed edge และปลายทางของมัน
LPA* รับประกันว่าจะทำงานเร็วกว่า A* หรือไม่?
ไม่ งานวิจัยรายงานข้อได้เปรียบในบางชุดปัญหา แต่จำนวนงานขึ้นกับการทับซ้อนระหว่างการค้นเดิมกับใหม่, heuristic, โครงสร้างกราฟ, priority queue และ implementation ตัวเลข expansion ไม่ใช่ตัวแทน runtime สากล
D* Lite เป็นอัลกอริทึมเดียวกันหรือไม่?
D* Lite สร้างจากแนวคิด LPA* แต่กลับทิศทางการค้นสำหรับงานนำทางจาก goal ไปยังตำแหน่งปัจจุบันของหุ่นยนต์ และเพิ่ม km เพื่อชดเชยการเคลื่อนของจุดอ้างอิง heuristic จึงไม่ควรนำตัวแปรหรือทิศทางของ D* Lite มาใส่ใน LPA* แบบ forward
แล็บแสดงว่า AI เรียนรู้จากผลลัพธ์หรือไม่?
ไม่ แล็บคำนวณค่าระยะทางบนกราฟที่กำหนด ไม่มี neural network, LLM, model weights, sensor หรือการเรียนรู้จากข้อมูล
แหล่งอ้างอิง
- Sven Koenig, Maxim Likhachev, and David Furcy. “Lifelong Planning A*.” Artificial Intelligence 155(1–2), 93–146 (2004). DOI record · Publisher record · Author bibliography and erratum.
- Author-hosted journal manuscript PDF. PDF front matter identifies it as a preprint submitted 24 May 2005; the journal publication is 2004.
- Sven Koenig’s LPA* demonstration and code page, including code links and cautions about tie-breaking, runtime, and implementation efficiency.
- Sven Koenig and Maxim Likhachev. “D* Lite,” AAAI 2002. Author paper PDF hosted by CMU · CMU publication record.
- Sven Koenig, Fast Replanning (Incremental Heuristic Search), especially the caution that expansions are not runtime proxies and that algorithm performance varies with implementation and setup.
ใส่ความเห็น