Optimal sequential planning is hard

Optimal sequential planning is harder than satisficing planning.
While there is no difference in theoretical complexity
in the general case (Bylander 1994), many of the classical
planning domains are provably easy to solve sub-optimally,
but hard to solve optimally (Helmert 2003).
Moreover, strikingly different scaling behaviour of satisficing
and optimal planners has been observed in practice
(Hoffmann and Edelkamp 2005). In fact, this disparity
even extends to planning domains which are known to
be easy to solve optimally in theory. If we apply two stateof-
the-art optimal planning algorithms (Haslum et al. 2007;
Helmert, Haslum, and Hoffmann 2007) to the GRIPPER domain,
neither of them can optimally solve more than 8 of the
standard suite of 20 benchmarks within reasonable run-time
and memory limits, whereas the whole suite is solved in a
few milliseconds by satisficing planners like FF (Hoffmann
and Nebel 2001). Moreover, those 8 tasks are quickly solved
by breadth-first search, showing no significant advantage of
sophisticated heuristic methods over brute force.
Copyright
c 2008, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved

ผลลัพธ์ (ไทย) 1:

การวางแผนตามลำดับสูงสุดได้ยากกว่า satisficing วางแผนในขณะที่ไม่แตกต่างในความซับซ้อนของทฤษฎีในกรณีทั่วไป (Bylander 1994), มากมายที่คลาสสิกโดเมนที่วางแผนได้ง่าย provably แก้ย่อยอย่างเหมาะสมแต่ยากที่จะแก้ปัญหาอย่างเหมาะสม (Helmert 2003)นอกจากนี้ แตกต่างกว่าปรับพฤติกรรม satisficingและวางแผนเหมาะสมได้ถูกตรวจสอบในทางปฏิบัติ(Hoffmann และ Edelkamp 2005) ในความเป็นจริง disparity นี้ยังขยายไปถึงโดเมนซึ่งเป็นที่รู้จักการวางแผนเป็นเรื่องง่ายที่จะแก้ปัญหาอย่างเหมาะสมในทฤษฎี ถ้าเราใช้สอง stateof-เด่นสุดวางอัลกอริทึม (Haslum et al. 2007Helmert, Haslum และ Hoffmann 2007) โดเมน GRIPPERไม่ของพวกเขาสามารถแก้ปัญหาอย่างเหมาะสมมากกว่า 8 ของการชุดมาตรฐานของเกณฑ์มาตรฐาน 20 ภายในเวลาทำงานที่เหมาะสมและหน่วยความจำจำกัด ในขณะที่ชุดทั้งหมดถูกแก้ไขในการไม่กี่มิลลิวินาที โดยวางแผน satisficing ชอบ FF (Hoffmannก Nebel 2001) นอก งานที่ 8 จะแก้ไขได้อย่างรวดเร็วโดยค้นหาครั้งแรกกว้าง ไม่มีประโยชน์ที่สำคัญของการแสดงวิธีแล้วซับซ้อนกว่าแรงเดรัจฉานลิขสิทธิ์ c 2008 สมาคมเพื่อความก้าวหน้าของเทียมปัญญา (www.aaai.org) สงวนลิขสิทธิ์ทั้งหมด

ผลลัพธ์ (ไทย) 2:

วางแผนที่ดีที่สุดตามลำดับเป็นงานหนักกว่า satisficing วางแผน.
ในขณะที่มีความแตกต่างในความซับซ้อนทางทฤษฎีไม่ในกรณีทั่วไป (Bylander 1994) หลายคลาสสิกโดเมนการวางแผนเป็นเรื่องง่ายที่สรรพสิ่งที่จะแก้ปัญหาย่อยอย่างดีที่สุดแต่ยากที่จะแก้ปัญหาได้อย่างดีที่สุด (Helmert 2003) . นอกจากนี้ยังมีการปรับพฤติกรรมที่แตกต่างกันอย่างยอดเยี่ยมของ satisficing และวางแผนที่ดีที่สุดได้รับการปฏิบัติในทางปฏิบัติ(ฮอฟและ Edelkamp 2005) ในความเป็นจริงความแตกต่างนี้แม้จะขยายไปถึงโดเมนการวางแผนที่เป็นที่รู้จักกันเป็นเรื่องง่ายที่จะแก้ปัญหาได้อย่างดีที่สุดในทางทฤษฎี ถ้าเราใช้สอง stateof- ศิลปะขั้นตอนวิธีการวางแผนที่ดีที่สุด (Haslum et al, 2007;. Helmert, Haslum และ Hoffmann 2007) กับโดเมนกริปเปอร์ที่ไม่ใช่ของพวกเขาได้อย่างดีที่สุดสามารถแก้มากกว่า8 ของชุดมาตรฐาน20 มาตรฐานภายในที่เหมาะสม เวลาทำงานและข้อจำกัด ของหน่วยความจำในขณะที่ชุดทั้งสามารถแก้ไขได้ในไม่กี่มิลลิวินาทีโดยsatisficing วางแผนเช่น FF (ฮอฟและNebel 2001) นอกจากนี้ผู้ที่ 8 งานที่ได้รับการแก้ไขได้อย่างรวดเร็วโดยการค้นหากว้างแรกแสดงไม่มีประโยชน์ที่สำคัญของวิธีการแก้ปัญหาที่มีความซับซ้อนมากกว่าแรงเดรัจฉาน. ลิขสิทธิ์ค 2008 สมาคมเพื่อความก้าวหน้าของเทียมหน่วยสืบราชการลับ(www.aaai.org) สงวนลิขสิทธิ์

ผลลัพธ์ (ไทย) 3:

วางแผนลำดับขั้นที่เหมาะสมยากกว่า satisficing การวางแผน .
ในขณะที่ไม่มีความแตกต่างในทางทฤษฎีที่ซับซ้อน
ในกรณีทั่วไป ( bylander 1994 ) , จำนวนมากของโดเมนการวางแผนคลาสสิก
ก็อาจง่ายที่จะแก้ซับอย่างระวัง แต่ยากที่จะแก้ปัญหาได้อย่างดีที่สุด

( helmert 2003 ) นอกจากนี้ แตกต่างกันมากการปรับพฤติกรรมของ satisficing
และนักวางแผนที่เหมาะสมได้รับการตรวจสอบในการปฏิบัติ
( Hoffmann และ edelkamp 2005 ) ในความเป็นจริงนี้ยังรวมไปถึงการวางแผนกัน

เป็นโดเมนที่เป็นที่รู้จักกันเพื่อง่ายที่จะแก้ปัญหาได้อย่างดีที่สุดในทางทฤษฎี ถ้าเราใช้สองสภาพ -
ศิลปะที่เหมาะสมการวางแผนขั้นตอนวิธี ( haslum et al . 2007 ;
helmert haslum และฮอฟแมน , 2007 ) กับ gripper โดเมน
ไม่ของพวกเขาสามารถได้อย่างดีที่สุดแก้ปัญหามากกว่า 8
ห้องมาตรฐาน 20 มาตรฐานภายใน
ระยะเวลาที่เหมาะสมและข้อ จำกัด หน่วยความจำ ส่วนแต่งงานทั้งหมดจะแก้ไขได้ในไม่กี่มิลลิวินาที โดยนักวางแผน ชอบ
satisficing FF ( Hoffmann
เนเบิลและ 2001 ) นอกจากนี้ ที่ 8 งานได้อย่างรวดเร็วแก้ไข
โดยความกว้างแรกค้นหา แสดงไม่แตกต่างกัน ประโยชน์ของวิธีฮิวริสติกที่ซับซ้อนกว่าการใช้กำลัง
.
ลิขสิทธิ์
c 2008 สมาคมเพื่อความก้าวหน้าของปัญญาประดิษฐ์
( www.aaai . org )สงวนสิทธิทั้งหมด