AI planning & acting & learning: Hierarchical Task Networks (HTN)

AI planning & acting & learning: Hierarchical Task Networks (HTN)

level: AI คอร์สบัณฑิตศึกษาทั่วไป

Ai planning เป็นหัวข้อนึงของสายวิชาปัญญาประดิษฐ์ โดยทั่วไประดับมอปลายหรือปอตรี ใช้มากในเกม เช่น OX หรือ tic-tac-toe และมักเป็นโจทย์ตัวอย่างในการฝึกเขียนโปรแกรมในปริภูมิค้นหาเช่น depth-first search หรือ breadth-first search โดยนิยามปริภูมิค้นหา สเตท โอเปอร์แรนด์ ทำนองนั้น แล้วระบบจะส่งผลลัพธ์มาให้ที่ค้นหา เป็นแบบนึง

การค้นหาอีกแบบเช่น การค้นหาเชิงเส้น ตัวอย่างโจทย์ประมาณว่า มีฟังก์ชันนึง y=f(x) ต้องการหาค่าเหมาะที่สุด จะสูงสุดหรือต่ำสุด อาจจะในช่วงจำนวนจริงนึงๆ ก็สามารถที่จะใช้วิธีเช่น bisection หรือ วิธีนิวตัน (แกรเดียนต์) หาค่าได้ หรือกำหนดการเชิงเส้นก็มีวิธีแบบ simplex หรือ interior point

ทีนี้ถ้าธรรมดา ก็ไม่ใช่วิชาระดับบัณฑิตศึกษา

ใน AI planning & acting & learning ระดับที่เค้าตีพิมพ์กันแถว AAAI IJCAI ทำนองนั้น มีอาจารย์เขียนหนังสือออกมา ใช้สอน https://projects.laas.fr/planning/aptp/index.html ออกมาสามเวอร์ชั่นแล้ว เล่มแรก planning เล่มสอง planning & acting https://projects.laas.fr/planning/apa/index.html เล่มสาม planning & acting & learning https://projects.laas.fr/planning/ โดยส่วนมากเป็นเปเปอร์ในหัวข้อนี้ ที่มีวิวัฒนาการ

เริ่มแรก จาก slide บทที่ 1 intro เวอร์ชั่นสอง [1] สรุปรวมๆว่าเทคนิคแนวไหนคือ จะมี actor เป็น agent ที่ perform actions โดยภายในการวางแผน deliberation functions จะแบ่งเป็นสองส่วน คือ actions อะไรที่จะทำ กับ acting คือจะทำอย่างไร ดังภาพ โดยการวางแผนนั้นขึ้นกับการทำนายและการค้นหา (ไม่ใช่การค้นหาอย่างเดียว)

นิยามปัญหาใน AI planning แคปมาจาก [1]

ทีนี้จะพูดถึงวิธีวางแผนแบบ hierarchical task networks (HTN) [2] ใน descriptive models อาจเขียนด้วยภาษาเช่น PDDL หรือ STRIPS ที่คล้ายๆภาษาพวก declarative เช่น Prolog จะมี state methods task ที่เราจะไม่ค้นหาแบบ brute-force แต่จะเอาสูตรปฏิบัติการมาต่อกันเป็นจิ๊กซอว์แผนผังแทน โดยมี precondition action/task result subtasks เป็นตัวเชื่อม ดังภาพ โดยผลลัพธ์คือ task networks ที่ใช้การได้จริง เป็นแผนที่มีลักษณะเป็น hierarchy โมเดลนี้ ถ้าเรากำหนดตัวปัญหาลงไป ก็มี solver ที่จะแสดงผลลัพธ์คืนให้เราเหมือนวิธีค้นหาหรือหาค่าเชิงเส้นอื่นๆ หรือทำมือก็ได้

task ส่วนมากสามารถ decomposed ไปเป็น subtasks ได้ ตามระดับนามธรรมที่ต่างกัน เช่น จะบิน ก็ 1. ซื้อตั๋วเครื่องบินจากสนามบินเอ ไปสนามบินบี 2. เดินทางไปสนามบินเอ 3. บินจากสนามบินเอไปสนามบินบี 4. เดินทางไปที่หมาย ดังภาพ แคปมาจากสไลด์ [2]

References

[1] https://www.cs.umd.edu/users/nau/apa/slides/chap1.pdf

[2] https://www.cs.umd.edu/users/nau/apa/slides/chap2b.pdf