Skip to content
กลับไปยังผลการค้นหา

สมการฮามิลตัน-ยาโคบี-เบลล์แมน

ผู้เสนอ
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 ผ่านโครงข่ายประสาทเทียม)

วิธีการทำงาน

วิธีการทำงาน

1

เขียนสมการ HJB: −∂V/∂t = min_u[L(x,u) + ∇V^T f(x,u)] พร้อมเงื่อนไขปลาย (terminal condition) V(x,T)=Φ(x)

2

แก้สมการเชิงอนุพันธ์ย่อย HJB โดยใช้วิธีการแยกตัวแปร (separation of variables) วิธีการลักษณะเฉพาะ (method of characteristics) หรือวิธีการเชิงตัวเลข (finite difference, finite element)

3

การควบคุมที่เหมาะสมที่สุดคือ u*(x,t) = argmin_u[L(x,u) + ∇V^T f(x,u)]; กฎการป้อนกลับนี้ได้มาจากการแก้สมการ HJB

4

ตรวจสอบว่า 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) (โครงข่ายประสาทเทียม) หรือจำกัดขอบเขตให้อยู่ในปริภูมิย่อยมิติไม่สูง

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Kirk, D. E. (2004). Optimal Control Theory: An Introduction (2nd ed.). Dover Publications.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว