การวางแผนและการจัดตารางเวลาอัตโนมัติ (Automated Planning and Scheduling)

การวางแผนและการจัดตารางเวลาอัตโนมัติ (Automated Planning and Scheduling) การวางแผนและการจัดตารางเวลาอัตโนมัติ หรือที่เรียกสั้นๆ ว่า AI Planning เป็นสาขาหนึ่งของปัญญาประดิษฐ์ (Artificial Intelligence) ที่มุ่งเน้นไปท

สรุปใจความสำคัญ

การวางแผน AI แตกต่างจากการควบคุมแบบดั้งเดิมตรงที่ต้องค้นหาคำตอบในพื้นที่หลายมิติ
Classical Planning เป็นรูปแบบที่ง่ายที่สุด โดยมีสถานะเริ่มต้นเดียวและการดำเนินการที่กำหนดผลลัพธ์ได้แน่นอน
Domain Independent Planning ช่วยให้ตัววางแผนตัวเดียวสามารถแก้ปัญหาในหลากหลายโดเมนได้ เช่น โลจิสติกส์และหุ่นยนต์

การวางแผนและการจัดตารางเวลาอัตโนมัติ หรือที่เรียกสั้นๆ ว่า AI Planning เป็นสาขาหนึ่งของปัญญาประดิษฐ์ (Artificial Intelligence) ที่มุ่งเน้นไปที่การสร้างกลยุทธ์หรือลำดับการดำเนินการ เพื่อให้ตัวแทนอัจฉริยะ (Intelligent Agents), หุ่นยนต์อัตโนมัติ หรือยานพาหนะไร้คนขับ สามารถบรรลุเป้าหมายที่กำหนดไว้ได้

ความแตกต่างสำคัญระหว่างการวางแผน AI กับปัญหาการควบคุมแบบดั้งเดิมคือ ความซับซ้อนของคำตอบ ซึ่งต้องถูกค้นหาและปรับให้เหมาะสมในพื้นที่หลายมิติ (Multidimensional Space) นอกจากนี้ การวางแผนยังมีความเกี่ยวข้องอย่างใกล้ชิดกับทฤษฎีการตัดสินใจ (Decision Theory)

ประเภทของการวางแผนตามสภาพแวดล้อม

การวางแผนสามารถแบ่งออกเป็นสองรูปแบบหลักตามลักษณะของสภาพแวดล้อม:

การวางแผนแบบออฟไลน์ (Offline Planning): ใช้ในสภาพแวดล้อมที่ทราบข้อมูลแน่นอนและมีแบบจำลองพร้อมใช้งาน สามารถค้นหาและประเมินคำตอบได้ก่อนที่จะเริ่มดำเนินการจริง
การวางแผนแบบออนไลน์ (Online Planning): ใช้ในสภาพแวดล้อมที่มีการเปลี่ยนแปลงตลอดเวลาหรือไม่ทราบข้อมูลล่วงหน้า กลยุทธ์จะต้องถูกปรับปรุงในขณะที่ดำเนินการ โดยอาศัยกระบวนการลองผิดลองถูก เช่น การโปรแกรมเชิงพลวัต (Dynamic Programming), การเรียนรู้แบบเสริมกำลัง (Reinforcement Learning) และการหาค่าที่เหมาะสมที่สุดเชิงผสม (Combinatorial Optimization)

ภาพรวมของปัญหาการวางแผน

โจทย์พื้นฐานของการวางแผนคือ การสังเคราะห์แผนงานที่รับประกันได้ว่า เมื่อนำไปใช้กับสถานะเริ่มต้น (Initial States) ใดๆ จะนำไปสู่สถานะเป้าหมาย (Goal State) ที่ต้องการ โดยความยากของปัญหานั้นขึ้นอยู่กับข้อสมมติฐานที่นำมาใช้ ดังนี้:

ลักษณะการดำเนินการ: เป็นแบบกำหนดได้แน่นอน (Deterministic) หรือไม่แน่นอน (Non-deterministic)
ตัวแปรสถานะ: เป็นแบบไม่ต่อเนื่อง (Discrete) หรือต่อเนื่อง (Continuous)
การสังเกตการณ์: สามารถสังเกตสถานะปัจจุบันได้อย่างชัดเจนทั้งหมด (Full Observability) หรือเพียงบางส่วน (Partial Observability)
จำนวนตัวแทน: มีตัวแทนเพียงตัวเดียว หรือมีหลายตัวแทน (Multi-agent) ซึ่งอาจร่วมมือกันหรือแข่งขันกัน

ระดับความซับซ้อนของปัญหาการวางแผน

ประเภทการวางแผน	ลักษณะสำคัญ
Classical Planning	สถานะเริ่มต้นเดียว, การดำเนินการกำหนดได้แน่นอน, ไม่มีระยะเวลา, ตัวแทนเดี่ยว
Markov Decision Processes (MDP)	การดำเนินการไม่แน่นอน (มีค่าความน่าจะเป็น), สังเกตได้ทั้งหมด, เน้นการเพิ่มรางวัลสูงสุด
POMDP	คล้ายกับ MDP แต่การสังเกตการณ์ทำได้เพียงบางส่วน (Partial Observability)
Multi-agent Planning	มีตัวแทนหลายตัว เกี่ยวข้องกับทฤษฎีเกม (Game Theory)

การวางแผนแบบไม่ขึ้นกับโดเมน (Domain Independent Planning)

ในทาง AI planning ตัววางแผน (Planner) มักจะรับข้อมูลสองส่วนคือ แบบจำลองโดเมน (Domain Model) ซึ่งอธิบายชุดของการดำเนินการที่เป็นไปได้ และ ปัญหาเฉพาะ (Specific Problem) ซึ่งระบุสถานะเริ่มต้นและเป้าหมาย

ตัววางแผนที่สามารถแก้ปัญหาได้หลากหลายโดเมน (เช่น การเรียงบล็อก, การขนส่งโลจิสติกส์, การจัดการเวิร์กโฟลว์) โดยไม่ต้องเขียนโปรแกรมใหม่สำหรับแต่ละงาน เรียกว่า Domain Independent Planner ซึ่งต่างจากตัววางแผนเฉพาะทาง (Domain-specific Planner) เช่น โปรแกรมวางแผนเส้นทาง (Route Planner) ที่ออกแบบมาเพื่อการนำทางโดยเฉพาะ

คำถามที่พบบ่อย

AI Planning คืออะไร?

คือสาขาของ AI ที่เน้นการสร้างลำดับการดำเนินการเพื่อให้ตัวแทนอัจฉริยะหรือหุ่นยนต์บรรลุเป้าหมายที่กำหนดไว้

ความแตกต่างระหว่าง Offline และ Online Planning คืออะไร?

Offline Planning ทำก่อนการดำเนินการในสภาพแวดล้อมที่ทราบข้อมูลแน่นอน ส่วน Online Planning ปรับเปลี่ยนกลยุทธ์ในขณะดำเนินการในสภาพแวดล้อมที่เปลี่ยนแปลงตลอดเวลา

MDP และ POMDP ต่างกันอย่างไร?

MDP (Markov Decision Processes) มีการสังเกตสถานะได้ทั้งหมด (Full Observability) ในขณะที่ POMDP (Partially Observable MDP) สามารถสังเกตสถานะได้เพียงบางส่วน