Chào các bạn, trong bài viết trước về KPIs, chúng ta đã biết cách “chấm điểm” một thuật toán quản lý năng lượng. Nhưng câu hỏi đặt ra là: Đâu là điểm số cao nhất (Max Score) mà một hệ thống có thể đạt được?
Nếy một thuật toán AI điều khiển và nó tiết kiệm được 500g Hydro cho một chuyến đi. Làm sao bạn biết đó là kết quả tốt nhất? Liệu có cách nào tiết kiệm ít hơn chẳng hạn như 400g được không?
Để trả lời câu hỏi này, trong lĩnh vực điều khiển hệ thống, có một “thước đo chuẩn mực” (Benchmark) để kiểm tra xem hệ thống đó có được tối ưu chưa, một trong số đó có thuật toán gọi là Dynamic Programming (Quy hoạch động - DP).
Hôm nay, bài viết này sẽ giới thiệu về DP không phải dưới dạng những công thức toán học khô khan, mà dưới góc nhìn của dân Computer Science (CS), một bài toán cổ điển mà bất cứ ai học CS cũng đều đã gặp là Bài toán tìm đường đi ngắn nhất trên đồ thị. 🗺️
1. Bối cảnh: Bài toán chia năng lượng (The Power Split Problem)
Hãy tưởng tượng chiếc xe Fuel Cell Hybrid (FCHEV) của chúng ta có 2 nguồn năng lượng:
- Fuel Cell (FC): Như một nhà máy điện, hoạt động hiệu quả khi chạy ổn định, nhưng rất ghét tăng giảm đột ngột.
- Battery (Pin): Như một cái kho đệm năng lượng, có thể phản ứng cực nhanh, cũng có thể nạp/xả tùy ý, nhưng dung lượng có hạn.
Khi người lái (Driver) đạp ga yêu cầu một công suất (ví dụ: cần 50kW để tăng tốc), bộ điều khiển EMS (Energy Management System) phải trả lời câu hỏi:
“Tôi nên lấy bao nhiêu từ Fuel Cell và bao nhiêu từ Battery để tổng lượng Hydro tiêu thụ là ít nhất?”
Vấn đề là, quyết định ở giây thứ 1 sẽ ảnh hưởng đến giây thứ 1000. Nếu bây giờ bạn dùng Battery quá nhiều, lát nữa Battery cạn sạch năng lượng ( thấp), bạn buộc phải dùng năng lượng của Fuel Cell hết công suất để sạc bù, lúc đó hiệu suất sẽ cực tệ.
2. Dynamic Programming: Kẻ biết trước tương lai
Do vậy, bài toán EMS trở nên phức tạp vì quyết định hiện tại ảnh hưởng đến tương lai. Chúng ta cần một chiến lược điều khiển thông minh để cân bằng việc sử dụng Fuel Cell và Battery sao cho tổng lượng Hydro tiêu thụ trong toàn bộ hành trình là ít nhất.
Trong lĩnh vực Computer Science, Dynamic Programming (DP) là một kỹ thuật để giải quyết các bài toán tối ưu phức tạp bằng cách chia nhỏ nó thành các bài toán con đơn giản hơn.
Trong bài toán EMS, DP có một “siêu năng lực”: Nó biết trước tương lai.
Giả sử chúng ta biết trước toàn bộ hành trình xe chạy (Driving Cycle) - ví dụ ta biết chắc chắn xe sẽ chạy trên chu trình lái cao tốc (Highway Driving Cycle) dài 1800 giây với vận tốc cụ thể từng giây. DP sẽ tính toán ngược từ đích về vạch xuất phát để tìm ra chuỗi hành động tối ưu nhất.
Đó là lý do DP được gọi là Global Optimization (Tối ưu toàn cục). Không có thuật toán nào có thể tiết kiệm nhiên liệu hơn DP (về mặt lý thuyết).
3. Góc nhìn CS: DP là bài toán “Tìm đường đi ngắn nhất”
Với góc nhìn của các bạn Kỹ thuật (Engineering), DP thường được biểu diễn bằng phương trình Bellman. Nhưng với bạn có nền tảng về CS, hãy hình dung thế này:
Chúng ta biến bài toán điều khiển xe thành một Đồ thị (Graph) khổng lồ.
- Trục hoành (X): Thời gian (từ 0 đến 1800s).
- Trục tung (Y): Trạng thái năng lượng của Pin ( - State of Charge), ví dụ từ 40% đến 80%.
Chúng ta chia lưới (grid) hay còn gọi là rời rạc hoá (discretize) không gian này thành các điểm (Nodes).
- Tại mỗi điểm (t, SOC), chúng ta có thể quyết định mức công suất mà Fuel Cell sẽ cung cấp (ví dụ: từ 0kW đến 50kW, chia thành các bước nhỏ).
- Xe quyết định dùng Fuel Cell ở mức công suất , pin sẽ chuyển sang trạng thái ở giây tiếp theo .
- Hàm chi phí (Cost Function): Chính là lượng Hydro tiêu thụ trong 1 giây đó.
Nhiệm vụ của DP: Tìm một đường đi từ điểm đầu (t=0, SOC=60%) đến điểm cuối (t=1800, SOC=60%) sao cho tổng trọng số (ở đây là tổng lượng Hydro tiêu thụ) trên đường đi là NHỎ NHẤT.
Nguyên lý tối ưu của Bellman: “Nếu con đường tối ưu đi từ A đến C có đi qua B, thì đoạn đường từ B đến C cũng phải là đoạn đường tối ưu nhất.”
Nhờ nguyên lý này, thay vì thử tỉ tỉ trường hợp (Brute force), DP tính toán ngược từ giây cuối cùng về giây đầu tiên, lưu trữ chi phí rẻ nhất tại mỗi điểm (Memoization).
4. Tại sao gọi là “Tiêu chuẩn vàng” (Benchmark)?
Nếu DP xịn như vậy, tại sao các hãng xe nổi tiếng ứng dụng DP vào chạy luôn?
Mặc dù DP là phương pháp tối ưu nhất về mặt lý thuyết, nhưng nó có Nhược điểm chí mạng: khiến nó không thể áp dụng trực tiếp trong thực tế:
- Non-causal: DP cần biết trước toàn bộ hành trình. Trong thực tế, khi bạn lái xe ra đường, xe không thể biết trước 10 phút nữa bạn có gặp đèn đỏ hay không.
- Computational Cost (Chi phí tính toán): Như đã bàn ở bài KPIs, DP tốn hàng giờ để tính toán. Chip trên xe hơi không thể chịu nổi.
Vậy học DP để làm gì? Để làm thước đo (Benchmark).
Khi bạn phát triển một thuật toán điều khiển hệ thống, chẳng hạn như AI (Deep Reinforcement Learning) hay Rule-based có thể chạy thực tế (Real-time), bạn cần so sánh nó với DP.
- Nếu thuật toán điều khiển của bạn tiêu thụ nhiên liệu chỉ kém DP có 2% thì chứng tỏ thuật toán của bạn tối ưu! 🥇
- Ngược lại nếu kém DP 30% thuật toán của bạn còn cần phải cải thiện thêm.
Kết luận
Dynamic Programming (DP) không phải là lời giải cho bài toán thực tế (Real-time application), nhưng nó là ngọn hải đăng chỉ đường. Nó cho chúng ta biết “giới hạn vật lý” của hệ thống nằm ở đâu. Việc phát triển và xây dựng code thành công DP cho hệ thống Fuel Cell là bước đầu tiên để khẳng định bạn hiểu sâu sắc về hệ thống và bài toán tối ưu.
Trong bài viết tiếp theo, mình sẽ chia sẻ cách triển khai code DP bằng MATLAB để tiếp tục giải quyết bài toán này. Từ việc xây dựng Cost Function đến việc xử lý lưới trạng thái (State Grid).
Hẹn gặp lại các bạn nhé! 💻