สมการฮามิลตัน-ยาโคบี-เบลล์แมน
- ผู้เสนอ
- Richard Bellman
- ปี
- 1957
- ประเภท
- algorithm
- กลุ่มวิธี
- Optimal Control
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
สมการฮามิลตัน-ยาโคบี-เบลล์แมน (HJB) เป็นสมการเชิงอนุพันธ์ย่อยที่อธิบายฟังก์ชันต้นทุนที่เหมาะสมที่สุดในการไปถึง (optimal cost-to-go) ในการโปรแกรมพลวัต พัฒนาโดยเบลล์แมนในปี 1957 สมการ HJB ให้ทั้งเงื่อนไขที่จำเป็นและเพียงพอสำหรับความเป็นที่สุด (optimality) ทำให้สามารถวิเคราะห์เชิงทฤษฎีและหาผลเฉลยเชิงตัวเลขสำหรับปัญหาการควบคุมที่เหมาะสมที่สุดได้อย่างสง่างาม สมการ HJB เป็นพื้นฐานสำคัญของการเรียนรู้แบบเสริมกำลัง (reinforcement learning) การโปรแกรมพลวัตโดยประมาณ (approximate dynamic programming) และการควบคุมแบบเรียลไทม์
แนวคิดเบื้องหลังวิธีการ
หลักการสำคัญของ HJB คือการโปรแกรมพลวัต: ต้นทุนที่เหมาะสมที่สุดจากสถานะ x ณ เวลา t เท่ากับต้นทุนทันทีบวกกับต้นทุนที่เหมาะสมที่สุดจากสถานะใหม่ หาก V(x,t) คือต้นทุนที่เหมาะสมที่สุดในการไปถึงจากสถานะ x ณ เวลา t สมการจะเป็น V(x,t) = min_u [L(x,u) + V(x+f(x,u)dt, t+dt)] เมื่อพิจารณาลิมิตเมื่อ dt→0 จะได้สมการ HJB: −∂V/∂t = min_u[L(x,u) + (∂V/∂x)^T f(x,u)] การแก้สมการ HJB จะได้ V(x,t) ซึ่งสามารถนำไปสกัดการควบคุมที่เหมาะสมที่สุด u*(x,t) = argmin_u[...] ได้ แตกต่างจากหลักการของปองตรีแยง (Pontryagin) ซึ่งให้เงื่อนไขที่จำเป็นเท่านั้น สมการ HJB ให้เงื่อนไขที่เพียงพอ: หากพบผลเฉลย V(x,t) การควบคุมที่ได้จะรับประกันความเป็นที่สุด
ประวัติศาสตร์
เบลล์แมนพัฒนาการโปรแกรมพลวัตและสมการ HJB ในทศวรรษ 1950 ซึ่งเป็นการปฏิวัติทฤษฎีการควบคุมที่เหมาะสมที่สุด สูตร HJB ให้เงื่อนไขเพียงพอซึ่งแตกต่างจากปองตรีแยง ตัวแก้สมการเชิงตัวเลขได้รับการพัฒนาตั้งแต่ทศวรรษ 1980 เป็นต้นมา รูปแบบสมัยใหม่รวมถึงผลเฉลยแบบหนืด (viscosity solutions) (Lions, Crandall) สำหรับกรณีที่ไม่เรียบ และวิธีการเชิงตัวเลขสำหรับสมการ PDE มิติสูง
ควรใช้เมื่อใด
ใช้ HJB สำหรับการสังเคราะห์การควบคุมที่เหมาะสมที่สุดแบบออฟไลน์ (offline) เมื่อความเป็นที่สุดและหลักประกันเชิงทฤษฎีมีความสำคัญ เหมาะอย่างยิ่งสำหรับระบบไม่เชิงเส้น (nonlinear systems) ปัญหาเวลาที่เหมาะสมที่สุด (time-optimal problems) และเกม (games) สมการ HJB มีความโดดเด่นในการวิเคราะห์ สำหรับการคำนวณ วิธีการเชิงตัวเลขอาจมีค่าใช้จ่ายสูง ใช้ HJB เมื่อโครงสร้างระบบไม่ซับซ้อน (มิติไม่สูง) หรือเมื่อต้องการฟังก์ชันค่า (value function) สำหรับการเรียนรู้และการควบคุมแบบปรับตัว
ข้อจำกัดและข้อควรพิจารณา
- การแก้สมการ HJB มีค่าใช้จ่ายในการคำนวณสูง; ปัญหาความสาปแช่งของมิติ (curse of dimensionality) ของสมการ PDE (หน่วยความจำ/การคำนวณเพิ่มขึ้นแบบทวีคูณตามมิติของสถานะ)
- ผลเฉลยเชิงวิเคราะห์หายาก; ตัวแก้สมการ PDE เชิงตัวเลขมีความซับซ้อนและอาจไม่แม่นยำ
- การตรวจสอบผลเฉลยทำได้ยาก; การตรวจสอบเงื่อนไขเพียงพอเชิงตัวเลขไม่น่าเชื่อถือ
- ไม่มีแนวทางโดยตรงในการเลือกวิธีการเชิงตัวเลข; ขึ้นอยู่กับปัญหา
- ต้องระบุเงื่อนไขปลายหรือโครงสร้างฟังก์ชันค่า; หากละเว้น คุณภาพของผลเฉลยจะลดลง
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ให้เงื่อนไขความเป็นที่สุดทั้งที่จำเป็นและเพียงพอ; ผลเฉลยรับประกันความเป็นที่สุด (ไม่ใช่แค่จุดวิกฤต)
- ใช้ได้กับระบบไม่เชิงเส้น แปรตามเวลา และมีข้อจำกัด
- ฟังก์ชันค่า V(x,t) เข้ารหัสข้อมูลทั้งหมดเกี่ยวกับพฤติกรรมที่เหมาะสมที่สุด มีประโยชน์สำหรับการวิเคราะห์ความไว (sensitivity)
- ขยายไปยังการควบคุมแบบสุ่ม (stochastic control) และเกมเชิงอนุพันธ์ (differential games) ได้อย่างเป็นธรรมชาติ
- เป็นรากฐานของการเรียนรู้แบบเสริมกำลังและการโปรแกรมพลวัตโดยประมาณ
การประยุกต์ใช้
- การบินและอวกาศ: การหาค่าที่เหมาะสมที่สุดของวิถีเชื้อเพลิงน้อยที่สุด (minimum-fuel trajectory optimization) โดยใช้การวิเคราะห์การควบคุมที่เหมาะสมที่สุดของเชื้อเพลิงโดยใช้ HJB
- หุ่นยนต์: การวางแผนการเคลื่อนที่ที่เหมาะสมที่สุด (optimal motion planning) โดยใช้เกรเดียนต์ของฟังก์ชันค่า
- การเงิน: การจัดการพอร์ตการลงทุนที่เหมาะสมที่สุด (optimal portfolio management) ผ่านสมการ HJB
- ทฤษฎีเกม: การวิเคราะห์สมดุลในเกมเชิงอนุพันธ์ (differential games)
- การเรียนรู้ของเครื่อง: ฟังก์ชันค่าในการเรียนรู้แบบเสริมกำลัง (การประมาณ HJB ผ่านโครงข่ายประสาทเทียม)
วิธีการทำงาน
วิธีการทำงาน
เขียนสมการ HJB: −∂V/∂t = min_u[L(x,u) + ∇V^T f(x,u)] พร้อมเงื่อนไขปลาย (terminal condition) V(x,T)=Φ(x)
แก้สมการเชิงอนุพันธ์ย่อย HJB โดยใช้วิธีการแยกตัวแปร (separation of variables) วิธีการลักษณะเฉพาะ (method of characteristics) หรือวิธีการเชิงตัวเลข (finite difference, finite element)
การควบคุมที่เหมาะสมที่สุดคือ u*(x,t) = argmin_u[L(x,u) + ∇V^T f(x,u)]; กฎการป้อนกลับนี้ได้มาจากการแก้สมการ HJB
ตรวจสอบว่า V(x,t) สอดคล้องกับสมการ HJB และเงื่อนไขขอบเขต; สิ่งนี้เป็นการรับรองความเป็นที่สุด (เงื่อนไขเพียงพอ)
ข้อผิดพลาดที่พบบ่อย
- สมมติว่าผลเฉลย HJB หาได้ง่าย; การแก้สมการ PDE ต้องใช้ความเชี่ยวชาญและมักต้องประมาณค่า
- การใช้ความละเอียดกริดไม่เพียงพอในวิธีการเชิงตัวเลข; การสุ่มตัวอย่างน้อยเกินไปทำให้เกิดผลเฉลยปลอม
- สับสนระหว่างเงื่อนไขที่จำเป็น (ปองตรีแยง) กับเงื่อนไขเพียงพอ (HJB); ผลเฉลย PMP อาจไม่เหมาะสมที่สุด
- การละเลยผลเฉลยแบบหนืด (viscosity solutions); ผลเฉลยแบบคลาสสิกอาจไม่มีอยู่จริงสำหรับฟังก์ชันต้นทุนที่ไม่เรียบ (nonsmooth)
คำถามที่พบบ่อย
ความสาปแช่งของมิติ (curse of dimensionality) ใน HJB คืออะไร?
HJB เป็นสมการ PDE ในปริภูมิสถานะ (state space); การแบ่งปริภูมิสถานะ n มิติออกเป็น m จุดกริดต้องใช้กริดเซลล์ m^n สำหรับ n=10, m=100 จะได้ 10^20 เซลล์ ซึ่งเป็นไปไม่ได้! นี่คือความสาปแช่งของมิติ วิธีการบรรเทา: ใช้กริดแบบเบาบาง (sparse grids) การประมาณฟังก์ชัน (function approximation) (โครงข่ายประสาทเทียม) หรือจำกัดขอบเขตให้อยู่ในปริภูมิย่อยมิติไม่สูง
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วKirk, D. E. (2004). Optimal Control Theory: An Introduction (2nd ed.). Dover Publications.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว