เวลาวางแผนให้หุ่นยนต์จัดของ ส่งยานไปยังจุดหมาย หรือทำงานหลายขั้นตอน ระบบต้องเลือกการกระทำจากสถานะปัจจุบันไปให้ถึงเป้าหมาย การค้นหาแบบ optimal ต้องการทั้งแผนที่ถูกต้องและต้นทุนรวมต่ำที่สุด แต่จำนวนสถานะที่ต้องพิจารณาอาจโตเร็วมาก นักวางแผนจึงใช้ heuristic เพื่อประมาณว่าจากสถานะหนึ่งยังเหลือต้นทุนอย่างน้อยเท่าไร ค่าประมาณที่ดีช่วยให้ค้นหาได้ตรงทาง ส่วนค่าที่สูงเกินจริงอาจทำให้ระบบทิ้งเส้นทางที่ดีที่สุดไป
คำตอบสั้น ๆ: LM-cut คือ admissible heuristic ที่หา action cuts ซึ่งทุก relaxed plan ต้องผ่าน แล้วจัดสรรต้นทุนคงเหลือให้ cuts ทีละส่วน จึงมักให้ lower bound แน่นกว่า hmax โดยไม่คิดต้นทุน action เกินงบ
เริ่มจากคำถามว่า “อย่างน้อยต้องเสียเท่าไร”
ให้มอง planning task เป็นชุดของข้อเท็จจริง (facts) ที่แทนสถานะ ชุดการกระทำ (actions) ที่มีเงื่อนไขก่อนทำ ผลที่เกิดขึ้น และต้นทุน รวมถึงสถานะเริ่มต้นกับเป้าหมาย สำหรับสถานะ s ให้ h*(s) หมายถึงต้นทุนของแผนที่ถูกที่สุดจาก s ไปยังเป้าหมาย ถ้าไม่มีแผน ค่า h*(s) เป็นอนันต์
FACT — heuristic h(s) เป็น admissible เมื่อ h(s) ≤ h*(s) ทุกสถานะ กล่าวคือค่าประเมินต่ำได้ แต่ห้ามสูงกว่าต้นทุนจริง คุณสมบัตินี้สำคัญกับ A* ที่ต้องรับประกันแผนต้นทุนต่ำสุด
จุดตั้งต้นของ LM-cut คือการลดความซับซ้อนของงาน โดยลบผลลบของ action ออก เช่น หาก action ทำให้ fact หนึ่งเป็นเท็จ ใน relaxed task เราแกล้งไม่สนใจการลบนั้น Facts ที่เคยเป็นจริงจึงยังคงจริงต่อไป การผ่อนคลายนี้ทำให้เป้าหมายเอื้อมถึงง่ายขึ้นหรือเท่าเดิม ดังนั้นต้นทุนของแผนที่ถูกที่สุดใน relaxed task จะไม่สูงกว่าต้นทุนจริงของงานเดิม
hmax: มองเส้นทางที่แพงที่สุดของเป้าหมาย
ใน delete relaxation คำนวณค่าของ fact แต่ละตัวจาก action ที่ทำให้ fact นั้นจริง โดยเลือก action ที่มีค่า cost(a) + ค่าสูงสุดของ preconditions ต่ำที่สุด: hmax(p) = min_a [cost(a) + max_{q ∈ pre(a)} hmax(q)] สำหรับ action a ที่เพิ่ม p. Facts ที่จริงอยู่แล้วมีค่า 0; หากไม่มี achiever ค่าจะเป็น ∞. สำหรับหลายเป้าหมาย hmax คือค่า hmax ที่มากที่สุดในบรรดาเป้าหมาย
ค่าแบบ max ปลอดภัยเป็น lower bound แต่เป้าหมายหลายข้ออาจไม่ได้เพิ่มค่าประมาณครบทุกข้อ
สัญลักษณ์ที่ใช้ต่อไป: hmax(s) คือค่าประมาณจากกฎ max, hadd(s) คือค่าประมาณแบบบวก และ hLM-cut(s) คือผลรวม δ จาก cuts ที่สร้างสำหรับสถานะ s. h*(s) คือ optimal cost จริง ดังนั้น admissibility ของ LM-cut เขียนได้ว่า hLM-cut(s) ≤ h*(s).
hadd: บวกทุกเป้าหมาย แต่อาจนับซ้ำ
อีกแนวทางหนึ่งคือ hadd ซึ่งรวมต้นทุนของเป้าหมายและ preconditions แทนที่จะเลือกเฉพาะค่ามากที่สุด จึงเห็นภาระจากหลายเป้าหมาย แต่ action ร่วมอาจถูกนับซ้ำ ทำให้ไม่ admissible โดยทั่วไป
LM-cut รวมต้นทุนหลายส่วนโดยไม่บวกต้นทุน action เกินจริง: มันระบุจุดตัดที่ทุกแผนแบบผ่อนคลายต้องผ่าน แล้วแบ่งงบต้นทุนทีละรอบ
Landmark ของ LM-cut คือกลุ่ม action
คำว่า landmark ใน LM-cut หมายถึง disjunctive action landmark: เซตของ actions ที่ทุกแผนจากสถานะปัจจุบันไปยังเป้าหมายต้องใช้สมาชิกอย่างน้อยหนึ่งตัว ไม่ได้หมายความว่าทุก action ในเซตต้องเกิดขึ้น และไม่ใช่ fact landmark ที่บอกว่า fact ใดต้องเป็นจริงในแผนทุกแผน
ตัวอย่างเช่น หากต้องเปิดประตูด้วยกุญแจสีแดงหรือบัตรผ่าน เซต {ใช้กุญแจแดง, ใช้บัตรผ่าน} อาจเป็น action landmark ได้ เพราะทุกแผนต้องเลือกอย่างน้อยหนึ่งทางเลือก จุดสำคัญคือ landmark แบบนี้เป็นข้อจำกัดแบบ “อย่างน้อยหนึ่งในกลุ่ม” ซึ่งเหมาะกับการคิดต้นทุนขั้นต่ำของกลุ่มได้
FACT — LM-cut สร้าง landmarks จากกราฟ justification ของ hmax ใน delete relaxation ไม่ได้ค้นหา landmark ทุกชนิด แต่ใช้โครงสร้างที่คำนวณได้เพื่อรับรอง cuts ตาม Helmert และ Domshlak, ICAPS 2009 (บทความต้นฉบับ, PDF).
ภาพรวม: สถานะและ actions เข้า hmax; จาก fact labels และ supporters ระบบสร้าง goal zone กับ before-goal zone; เส้นขอบเป็น cut; จากนั้นจัดสรรต้นทุนขั้นต่ำและคำนวณซ้ำด้วย residual costs.
ข้อมูลเข้าและออกมีรูปแบบชัดเจน: task ประกอบด้วย facts, initial state, goals และ actions โดยแต่ละ action มี preconditions, add effects, delete effects และ cost. ภายในหนึ่งรอบ ใช้ fact-label map hmax, supporter ต่อ action, justification edges, goal zone, before-goal zone, cut ที่อ้าง action IDs, ค่า δ, ledger ของต้นทุนคงเหลือ และ accumulator ของ heuristic. ผลออกคือค่าประมาณหรือ dead-end ของ relaxed task; search ใช้ค่านี้จัดลำดับสถานะ ส่วนการตรวจแผนจริงต้องใช้ transition semantics ที่รวม delete effects และตรวจ goal แยกต่างหาก
จุดตรวจช่วยแยก error จากผลปกติ: cost ติดลบหรือ feature ที่ implementation ไม่รองรับต้องปฏิเสธก่อนคำนวณ; hmax = ∞ เป็น dead end ที่รับรองได้จาก relaxation; หาก hmax ยังบวกแต่หา cut ไม่ได้ หรือ δ ≤ 0 ทั้งที่ยังมีต้นทุนบวก แปลว่าการสร้าง graph/cut มีปัญหา; เมื่อ search คืนแผน ต้องตรวจ preconditions, add/delete effects และ goals บน task จริง เพราะ heuristic ไม่ได้สร้างแผนจริงให้
จาก hmax สู่ cut
สำหรับ action ทุกตัว supporter คือ precondition ที่มี hmax สูงสุด (เมื่อเสมอกันขึ้นกับ tie-breaking) จาก supporter นี้ กราฟ justification เชื่อมไปยัง positive effects ทุกตัวของ action ไม่ใช่เฉพาะ effect ที่มีค่า hmax สูงสุด; มีการเพิ่ม goal จำลองเพื่อรวมหลายเป้าหมายเข้าด้วยกัน การเลือก achiever ที่ดีที่สุดของแต่ละ fact เป็นส่วนของการคำนวณ label แต่ไม่ใช่ความหมายของ supporter ต่อ action
เมื่อเลือก goal ที่มีค่า hmax สูงสุด ระบบไล่ย้อนจาก goal จำลองผ่าน justification edges ที่มีต้นทุนคงเหลือศูนย์ เพื่อกำหนด goal zone. before-goal zone คือ facts ที่เข้าถึงได้จากสถานะปัจจุบันโดยไม่เข้า goal zone. Facts ที่เหลืออาจอยู่ใน neither zone.
Actions ที่มีเส้นเชื่อมข้ามจาก before-goal zone ไปยัง goal zone รวมกันเป็น cut การเอา actions ใน cut นี้ออกจะขวางทุกเส้นทาง justification จากสถานะเริ่มต้นไปยังเป้าหมายที่เลือก และใน relaxed task จะมี landmark อยู่ในทุกแผน กล่าวคือแผนใด ๆ ต้องใช้ action ใน cut อย่างน้อยหนึ่งตัว
รอบหนึ่งเพิ่ม δ ซึ่งเป็นต้นทุนคงเหลือน้อยที่สุดของ actions ใน cut เข้า heuristic accumulator แล้วหัก δ จากต้นทุนคงเหลือของทุก action ใน cut เพื่อกันงบให้ landmark รอบนี้
จากนั้นคำนวณ hmax และ justification graph ใหม่ ทำซ้ำจนค่าเป้าหมายเป็นศูนย์ หรือพบว่า relaxed task ไปไม่ถึงเป้าหมาย
ทำไมการหักต้นทุนหลายรอบไม่ทำให้ค่าประเมินเกินจริง
หัวใจของ admissibility อยู่ที่ cost partitioning หรือง่าย ๆ คือการแบ่งต้นทุน action ออกเป็นส่วน ๆ อย่างมีขอบเขต ในแต่ละรอบ cut เป็น action landmark ใน relaxed task ดังนั้นทุก relaxed plan ต้องจ่ายต้นทุนให้ action อย่างน้อยหนึ่งตัวใน cut ค่า δ ที่ต่ำที่สุดของกลุ่มจึงเป็น lower bound สำหรับการผ่าน landmark รอบนั้น
เมื่อหัก δ จากทุก action ใน cut แต่ละ action จะเหลืองบลดลงเท่าที่จ่ายไปแล้ว หาก action หนึ่งไปอยู่ใน cut หลายรอบ มันถูกหักทีละส่วน และยอดที่หักรวมกันไม่เกินต้นทุนตั้งต้นของมัน เพราะทุกรอบใช้ค่าต้นทุนคงเหลือ ณ เวลานั้นและลดลงจนไม่มีส่วนบวกเหลือให้ตัดอีก
สำหรับ relaxed plan ใด ๆ ทุก cut ที่ LM-cut สร้างต้องถูกผ่าน และต้นทุนที่จัดสรรให้ cuts รวมกันไม่เกินต้นทุนของ actions ในแผนนั้น เมื่อ relaxed plan ที่ถูกที่สุดมีต้นทุนไม่เกินแผนจริง ค่ารวมของ cuts จึงไม่เกินต้นทุนแผนจริงด้วย LM-cut จึงเป็น admissible heuristic สำหรับต้นทุนแบบไม่ติดลบในกรอบ planning แบบคลาสสิกที่กำหนด
ANALYSIS — hmax เก็บค่าของเป้าหมายที่แพงที่สุด ขณะที่ LM-cut รวม lower bounds จากหลาย cuts ได้โดย cost partitioning คุมไม่ให้ใช้งบ action ซ้ำเกินจริง
ตัวอย่าง: เครื่องมือหนึ่งชิ้นช่วยสองเป้าหมาย
เริ่มจาก start และต้องทำให้ A กับ B เป็นจริง มี actions ดังนี้: get-tool ใช้ start เพื่อสร้าง tool มีต้นทุน 3; make-A ใช้ tool เพื่อสร้าง A มีต้นทุน 1; make-B ใช้ tool เพื่อสร้าง B มีต้นทุน 1
SIMULATION — แผนที่ดีที่สุดทำ get-tool หนึ่งครั้ง แล้วทำ make-A กับ make-B รวมต้นทุน 5. แต่ละเป้าหมายมี hmax = 4 จึงได้ hmax = 4; hadd นับต้นทุนเครื่องมือซ้ำและได้ 8 ซึ่งเกินต้นทุนจริง
LM-cut ได้ 5: cut ของเป้าหมายหนึ่งเรียกเก็บ 1, อีกเป้าหมายเรียกเก็บ 1 แล้ว cut ที่เหลือคือ get-tool ราคา 3. ดังนั้น hmax = 4 ≤ hLM-cut = 5 = h*, ส่วน hadd = 8.
เปรียบเทียบค่าจากตัวอย่างสี่แบบ
SIMULATION — ตารางนี้เป็นตัวอย่างคำนวณ ไม่ใช่ benchmark. ค่า h* คือต้นทุน optimal จริง; hadd อาจนับต้นทุนร่วมซ้ำ
| ตัวอย่าง | hmax | hadd | hLM-cut | h* |
|---|---|---|---|---|
เป้าหมายอิสระ: ทำ x ราคา 3 และ y ราคา 5 |
5 | 8 | 8 | 8 |
action ร่วมราคา 5 สร้างทั้ง x และ y |
5 | 10 | 5 | 5 |
| ทางตรงถึง goal ราคา 7 หรือใช้ chain สาม action ราคาข้อละ 1 | 3 | 3 | 3 | 3 |
delete trap: ใช้ token ทำ a ราคา 2 แล้วลบ token; ทำ b ราคา 3 ต้องใช้ token; เป้าหมาย a และ b |
3 | 5 | 5 | ∞ |
แถวแรกไม่มีต้นทุนร่วม จึงนับเป้าหมายทั้งสองได้ ส่วนแถวสอง hadd นับ action ราคา 5 สองครั้ง แต่ LM-cut แบ่งต้นทุน shared action ครั้งเดียว
แถวสามแสดงกรณีที่เส้นทาง chain ราคา 3 ชนะ action ตรงราคา 7. อย่าสรุปจากตัวอย่างนี้ว่า LM-cut จะเท่ากับ optimal cost เสมอ
แถวสุดท้ายเป็น delete trap: make-a ลบ token จึงทำ make-b ไม่ได้จริง แต่ relaxed task เพิกเฉยต่อการลบและมองว่าทำได้ทั้งคู่ ค่า 5 ยังเป็น lower bound เมื่อเทียบกับ h* = ∞; ค่าจำกัดไม่ยืนยันว่ามีแผนจริง
การสิ้นสุด การเสมอกัน และสถานะที่ไปไม่ถึง
ต้นทุน action ต้องไม่ติดลบ เพราะข้อพิสูจน์ cost partitioning อาศัยการแบ่งงบต้นทุนที่ไม่ลดต่ำกว่าเดิม ในการทำงานจริง action ต้นทุนศูนย์ยังมีบทบาทต่อกราฟ: เส้นเชื่อมศูนย์ช่วยขยาย goal zone ย้อนหลัง ส่วน cut ที่ข้ามจาก before-goal zone ไปยัง goal zone จะมีต้นทุนคงเหลือบวก จึงเลือก δ บวกได้และลดต้นทุนของ action อย่างน้อยหนึ่งตัวจนเป็นศูนย์ในรอบนั้น จำนวนการตัดจึงมีขอบเขตจากจำนวนการลดต้นทุนเป็นศูนย์ของ actions
ถ้าสถานะเป็นเป้าหมายแล้ว heuristic เป็นศูนย์ หาก hmax = ∞ แปลว่าแม้ delete relaxation ก็ไปไม่ถึงเป้าหมาย จึงเป็น dead end จริงด้วย แต่ค่า hmax จำกัดอาจยังซ่อน dead end จาก delete effects ได้
การเลือกเป้าหมายหรือ hmax supporter เมื่อมีค่าซ้ำอาจเปลี่ยน cut sequence และบางครั้งเปลี่ยนค่าประมาณ Fast Downward 26.6 มีตัวเลือก goal-zone และ border tie-breaking (เอกสารรุ่น 26.6, release notes) ซึ่งเปลี่ยนการเลือก supporter แต่ไม่เปลี่ยนหลัก cost partitioning และไม่ทำให้ heuristic consistent
Admissible ไม่เท่ากับ consistent
Consistency ตรวจทุก transition ว่า h(s) ≤ cost(a) + h(s') เมื่อ action a พา s ไป s'. คุณสมบัตินี้ช่วยให้ search บางแบบไม่ต้องเปิดสถานะเดิมซ้ำ
FACT — เอกสาร Fast Downward 26.6 ระบุ LM-cut admissible: yes, consistent: no. A* แบบ graph search จึงต้องจัดการ reopen เพื่อรักษา optimality; การเป็น lower bound ไม่ได้แปลว่า consistent
LM-cut ใช้ได้กับงานแบบใด
ผลทางทฤษฎีของงานต้นฉบับครอบคลุม planning แบบคลาสสิกที่มีต้นทุน actions ไม่ติดลบ โดยอธิบายใน propositional STRIPS และกล่าวว่าผลลัพธ์ใช้กับ SAS+ ได้ด้วย ส่วนการใช้งานหนึ่ง ๆ อาจมีข้อจำกัดมากกว่ากรอบทฤษฎี เอกสาร Fast Downward ระบุว่า heuristic นี้รองรับ action costs แต่ไม่รองรับ conditional effects หรือ axioms ในระบบดังกล่าว
ควรแยกข้ออ้างให้ชัด: “LM-cut เป็น admissible” เป็นคุณสมบัติของ heuristic ภายใต้ formalism และสมมติฐานที่ระบุ ส่วน “โปรแกรม X รองรับ task Y” เป็นข้อเท็จจริงเฉพาะ implementation และเวอร์ชัน ระบบหนึ่งอาจแปลง input ก่อน หรือปฏิเสธ language feature บางอย่างได้ แม้จะมีวิธีขยายแนวคิดทางทฤษฎีก็ตาม
REPORTED CLAIM — การทดลองต้นฉบับปี 2009 รันบน Linux ด้วย Intel E8400 3 GHz ใช้ timeout 30 นาทีและ memory limit 1.5 GB (บางการทดลองของ Gamer ใช้ 2 GB) งานความแม่นยำวัดค่า initial-state heuristic เฉพาะ benchmark ที่คำนวณ h+ ได้ ส่วนงาน optimal planning เปรียบเทียบ A* configurations ในระบบเดียวกันเป็นหลัก เงื่อนไขนี้เป็นบริบทของงานเก่า ไม่ใช่ผล benchmark ปัจจุบัน; บทความนี้ไม่ได้ทำซ้ำการทดลองหรือนำคะแนนมาอ้าง
LM-cut ยังเป็น heuristic สำหรับช่วยจัดลำดับการค้นหาสถานะ ไม่ใช่อัลกอริทึมที่รับข้อความภาษาธรรมชาติแล้วตอบแผนเอง และไม่ใช่ตัวแทนของ planner ทั้งระบบ Planner ยังต้องมี state representation, successor generation, search algorithm, การตรวจ dead end และเงื่อนไขการจัดการ heuristic ที่ไม่ consistent ด้วย
LM-cut ไม่ฝึก weights และไม่ใช้ retrieval หรือ external memory; มันคำนวณจาก task, state และ action costs ที่ส่งเข้าแต่ละครั้ง โดย ledger ของ residual costs เป็นข้อมูลชั่วคราวระหว่างหาค่า heuristic. จึงไม่ควรอธิบายผลของมันว่าเป็นความรู้ที่โมเดลเรียนมา หรือโยงกับความสามารถวางแผนของ LLM โดยไม่มีการทดลองแยกต่างหาก
ทิศทางพัฒนาต่อ
Fast Downward 26.6 เพิ่ม goal-zone และ border tie-breaking ตามแนวคิดงานปี 2020 ซึ่งแสดงว่าการเลือก supporter ยังเป็นจุดปรับปรุงด้านเวลาและคุณภาพ estimate ได้ แบบฝึกในบทความนี้ใช้ tie-breaking แบบคงที่เพื่อให้ trace ทำซ้ำได้; มันไม่ได้แทนพฤติกรรมของทุก configuration. งานต่อไปควรเปรียบเทียบตัวเลือกบน workload ที่ระบุชัด วัดทั้งค่า heuristic, เวลาคำนวณต่อสถานะ, จำนวนการขยายและการ reopen แล้วรายงานเวอร์ชันกับ options. ผลที่ได้จาก workload หนึ่งยังไม่บอกว่าตัวเลือกใดชนะในโดเมนอื่น
คำถามที่พบบ่อย
LM-cut กับ landmark heuristic ทั่วไปเหมือนกันไหม?
LM-cut ใช้แนวคิด landmark แต่สร้าง disjunctive action landmarks จาก cut ในกราฟ justification ของ hmax ภายใต้ delete relaxation อย่าสับสนกับ fact landmarks หรือ landmark heuristics ที่ใช้นิยามและ cost partitioning แบบอื่น
ทำไมไม่ใช้ hadd ซึ่งมักสูงกว่า?
เพราะค่าสูงกว่าอาจมาจากการนับ action ร่วมซ้ำ ถ้าต้องการการค้นหา optimal ค่าที่เกินต้นทุนจริงทำให้ heuristic ไม่ admissible LM-cut เพิ่มความแรงอย่างมีการควบคุม โดยจัดสรรต้นทุน residual ให้ cut ที่ต้องผ่านและไม่ใช้เงินเกินต้นทุนที่มี
ถ้า LM-cut คืนค่าจำกัด แปลว่ามีแผนหรือไม่?
ไม่เสมอไป ค่าจำกัดบอกว่า relaxed task มีเส้นทางถึงเป้าหมายในแบบที่เพิกเฉยต่อ delete effects แต่ task จริงอาจติด dead end เพราะ actions ลบ facts ที่จำเป็นต่อเป้าหมายอื่น
ใช้ LM-cut กับ A* ได้ไหม?
ได้ใน planner ที่รองรับ heuristic และจัดการความไม่ consistent อย่างถูกต้อง Fast Downward ยกตัวอย่างการใช้ astar(lmcut()) แต่เอกสารก็ระบุว่า LM-cut ไม่ consistent จึงต้องพิจารณาพฤติกรรมการเปิดสถานะซ้ำของ search algorithm ด้วย
ทำไมผลจากเครื่องมือสองชุดอาจไม่เท่ากัน?
tie-breaking ของ hmax supporters และเป้าหมายมีผลต่อ cut ที่ได้ จึงควรบันทึก planner รุ่นและ options เมื่อรายงานตัวเลข
ทดลองคิดด้วยตนเอง
ลองสร้างโจทย์ที่มีเป้าหมายสองข้อ แล้วเปลี่ยนจาก action แยกกันเป็น action ร่วม ถามว่า hmax เลือกเป้าหมายใด, hadd นับต้นทุนใดซ้ำ และทุกแผนต้องผ่าน cut ใด
สำรวจ LM-cut ทีละรอบ
This deterministic explorer follows the delete-relaxed hmax justification graph, marks its zero-cost goal plateau, then reduces the cost of the entering landmark actions.
เครื่องมือสำรวจแสดงค่าของ hmax, hadd, LM-cut พร้อม trace ของแต่ละ cut และ residual ledger หลังหักต้นทุน ผู้ใช้เลือก preset อิสระ, shared action, ทางเลือกเส้นทาง หรือ delete trap ได้ การกด reset คืนต้นทุนเริ่มต้น และผลเป็นเพียงการจำลอง ไม่ได้เรียก search หรือ LLM
เกมจัดสรรต้นทุนคงเหลือ
Choose a candidate set of actions that every delete-relaxed plan must use. A valid cut charges its minimum remaining action cost, then subtracts that amount from every action in the cut.
เกมฝึกแนวคิดอาจให้ผู้เล่นเลือก cut ที่ครอบคลุมทุกเส้นทาง relaxed plan แล้วจัดสรร δ จากต้นทุนที่เหลือ หากตัด action ที่ไม่ใช่ landmark ผู้เล่นจะเห็นตัวอย่างแผนที่หลุดผ่าน cut หากตัดซ้ำเกินงบ action ใด เกมจะแสดง residual cost ติดลบให้เห็นข้อผิดพลาด
สรุปประเด็นสำคัญ
เกมฝึกให้เลือก cut ที่ทุก relaxed plan ต้องผ่าน แล้วจ่าย δ จาก ledger ของต้นทุนคงเหลือ เกมแสดง lower bound ที่เพิ่มขึ้นและเตือนเมื่อตัด action ที่ไม่ครอบคลุมหรือใช้ต้นทุนเกินงบ จากนั้น reset เริ่มโจทย์เดิมใหม่
ANALYSIS — LM-cut มักให้ค่ามากกว่า hmax และยัง admissible ภายใต้ classical planning ที่มี action costs ไม่ติดลบ แต่ hadd ไม่ admissible โดยทั่วไป, LM-cut ไม่ consistent, ค่าจำกัดไม่รับประกันว่ามีแผนจริง และ support ของ implementation ขึ้นกับเวอร์ชัน
แหล่งอ้างอิง
- Helmert, M. & Domshlak, C. (2009). Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway?, ICAPS 2009, 162–169. PDF ต้นฉบับจากผู้เขียน
- Fast Downward. เอกสาร heuristic LM-cut รุ่น 26.6: ตัวเลือก, language features และ properties รวม admissible/consistent.
- Fast Downward. Release notes 26.6: สถานะรุ่นและรายการเปลี่ยนแปลงล่าสุด.
- Fast Downward. โค้ด wrapper ของ LM-cut และ directory ของการคำนวณ landmark cuts.
- Lauer, P. & Fickert, M. (2020). Beating LM-cut with LM-cut: Quick Cutting and Practical Tie Breaking for the Precondition Choice Function, HSDIP 2020. Fast Downward อ้างงานนี้ประกอบตัวเลือก tie-breaking ปัจจุบัน; PDF นี้ยังไม่ได้ตรวจโดยตรง จึงอ้างรายละเอียดตัวเลือกจากเอกสาร Fast Downward รุ่น 26.6 เท่านั้น.
ใส่ความเห็น