Cài Đặt Phần Cứng Tìm Đường Đi Ngắn Nhất Trong Mê Cung 10x10 Bằng Deep-Q-Learning

Khóa luận trình bày ứng dụng deep Q learning trong việc tìm đường đi ngắn nhất trong mê cung 10x10, khám phá tiềm năng của kỹ thuật máy tính.

• Tác giả: Nguyễn Duy Thanh
• Người hướng dẫn: ThS. Phạm Thanh Hùng
• Trường học: Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Kỹ sư ngành Kỹ thuật máy tính
• Đề tài: Cài Đặt Phần Cứng Tìm Đường Đi Ngắn Nhất Trong Mê Cung 10x10 Bằng Deep-Q-Learning
• Loại tài liệu: Khóa luận tốt nghiệp
• Năm xuất bản: 2022
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• 1. CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN ĐỀ TÀI
• 1.1. Hướng nghiên cứu đề tài
• 1.2. Mục tiêu đề tài
• 2. CHƯƠNG 2: HỌC TĂNG CƯỜNG VÀ CÁC THUẬT TOÁN LIÊN QUAN
• 2.1. Học tăng cường
• 2.2. Loss Function: Mean Square Error
• 2.3. Thuật toán Gradient descent Momentum
• 2.4. Activation Function: ReLU
• 2.5. Quy trình ra quyết định Markov
• 3. CHƯƠNG 3: THIẾT KẾ TỔNG QUAN HỆ THỐNG
• 3.1. Mô tả tổng quan hệ thống
• 3.2. Quy trình thiết kế hệ thống
• 4. CHƯƠNG 4: THIẾT KẾ CHI TIẾT
• 4.1. Khối Fully Connected
• 4.2. Khối Policy Generator
• 4.3. Khối Update Parameter
• 4.4. Khối Shortest action
• 5. CHƯƠNG 5: HIỆN THỰC, MÔ PHỎNG VÀ ỨNG DỤNG CỦA THIẾT KẾ VÀO FPGA
• 5.1. Mô phỏng thuật toán bằng phần mềm Python
• 5.2. Giới thiệu FPGA Xilinx và mục đích sử dụng
• 5.3. Tổng hợp thiết kế trên Virtex 7
• 5.4. Hệ thống SOC kết nối IP
• 5.5. So sánh kết quả thiết kế với các nghiên cứu liên quan
• 6. CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI
• 6.1. Khó khăn gặp phải
• 6.2. Hướng phát triển
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu tổng quan về cài đặt phần cứng tìm đường đi ngắn nhất

Trong bối cảnh công nghệ ngày càng phát triển, việc ứng dụng Deep-Q-Learning vào việc tìm đường đi ngắn nhất trong mê cung 10x10 trở nên cần thiết. Đề tài này không chỉ giúp hiểu rõ hơn về các thuật toán học sâu mà còn mở ra hướng đi mới cho các ứng dụng trong lĩnh vực robot và trí tuệ nhân tạo. Việc cài đặt phần cứng cho bài toán này sẽ giúp tối ưu hóa hiệu suất và độ chính xác của thuật toán.

1.1. Tầm quan trọng của việc giải quyết bài toán mê cung

Giải quyết bài toán mê cung không chỉ là một thách thức trong lĩnh vực trí tuệ nhân tạo mà còn có ứng dụng thực tiễn trong nhiều lĩnh vực như robot tự hành và logistics. Việc tìm đường đi ngắn nhất giúp tiết kiệm thời gian và tài nguyên.

1.2. Tổng quan về Deep Q Learning

Deep-Q-Learning là một phương pháp học tăng cường mạnh mẽ, cho phép các tác nhân (agents) học hỏi từ môi trường thông qua các hành động và phản hồi. Phương pháp này đã được chứng minh là hiệu quả trong nhiều bài toán phức tạp.

II. Vấn đề và thách thức trong việc tìm đường đi ngắn nhất

Mặc dù có nhiều phương pháp để giải quyết bài toán tìm đường đi ngắn nhất, nhưng việc áp dụng Deep-Q-Learning vào mê cung 10x10 vẫn gặp phải nhiều thách thức. Các vấn đề như độ phức tạp tính toán, khả năng hội tụ của thuật toán và việc tối ưu hóa phần cứng là những yếu tố cần được xem xét kỹ lưỡng.

2.1. Độ phức tạp của bài toán

Bài toán tìm đường đi ngắn nhất trong mê cung có thể trở nên phức tạp khi kích thước mê cung tăng lên. Điều này đòi hỏi các thuật toán phải có khả năng xử lý và tính toán hiệu quả.

2.2. Khả năng hội tụ của Deep Q Learning

Khả năng hội tụ của Deep-Q-Learning phụ thuộc vào nhiều yếu tố như cấu trúc mạng nơ-ron, hàm mất mát và các tham số học. Việc điều chỉnh các yếu tố này là rất quan trọng để đạt được kết quả tốt nhất.

III. Phương pháp cài đặt phần cứng cho Deep Q Learning

Cài đặt phần cứng cho bài toán tìm đường đi ngắn nhất trong mê cung 10x10 sử dụng Deep-Q-Learning bao gồm việc thiết kế các khối chức năng như môi trường (Environment), tác nhân (Agent) và các khối cập nhật tham số. Việc tối ưu hóa các khối này sẽ giúp cải thiện hiệu suất của hệ thống.

3.1. Thiết kế khối môi trường Environment

Khối môi trường chịu trách nhiệm cung cấp trạng thái hiện tại cho tác nhân và thực hiện các hành động. Việc thiết kế khối này cần đảm bảo tính chính xác và hiệu quả trong việc xử lý thông tin.

3.2. Thiết kế khối tác nhân Agent

Tác nhân là phần quan trọng trong hệ thống, nó thực hiện các hành động dựa trên trạng thái hiện tại. Việc tối ưu hóa khối tác nhân sẽ giúp cải thiện khả năng tìm đường đi ngắn nhất.

3.3. Cập nhật tham số và tối ưu hóa

Khối cập nhật tham số cần được thiết kế để đảm bảo rằng các trọng số của mạng nơ-ron được cập nhật một cách hiệu quả, giúp cải thiện khả năng học của hệ thống.

IV. Ứng dụng thực tiễn và kết quả nghiên cứu

Việc cài đặt phần cứng cho bài toán tìm đường đi ngắn nhất trong mê cung 10x10 bằng Deep-Q-Learning đã cho thấy những kết quả khả quan. Các thử nghiệm cho thấy độ chính xác của thuật toán trên phần cứng đạt được kết quả tương đương với mô hình phần mềm, đồng thời tiết kiệm tài nguyên tính toán.

4.1. Kết quả so sánh với giải thuật Lee

Kết quả thực nghiệm cho thấy rằng thuật toán Deep-Q-Learning có thể đạt được độ chính xác tương đương với giải thuật Lee, nhưng với thời gian xử lý nhanh hơn.

4.2. Tài nguyên phần cứng sử dụng

Việc đánh giá tài nguyên phần cứng cho thấy rằng hệ thống có thể hoạt động hiệu quả trên các nền tảng FPGA, giúp tối ưu hóa chi phí và hiệu suất.

V. Kết luận và hướng phát triển tương lai

Cài đặt phần cứng cho bài toán tìm đường đi ngắn nhất trong mê cung 10x10 bằng Deep-Q-Learning đã mở ra nhiều cơ hội mới trong nghiên cứu và ứng dụng. Hướng phát triển tương lai có thể bao gồm việc mở rộng kích thước mê cung và cải thiện thuật toán để đạt được hiệu suất tốt hơn.

5.1. Khó khăn gặp phải trong quá trình nghiên cứu

Trong quá trình nghiên cứu, một số khó khăn đã được ghi nhận như việc tối ưu hóa tham số và cấu trúc mạng nơ-ron. Những vấn đề này cần được giải quyết để cải thiện hiệu suất của hệ thống.

5.2. Hướng phát triển tiếp theo

Hướng phát triển tiếp theo có thể bao gồm việc áp dụng các thuật toán học sâu khác và mở rộng nghiên cứu sang các bài toán phức tạp hơn trong lĩnh vực trí tuệ nhân tạo.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Trong lĩnh vực trí tuệ nhân tạo, sự phát triển của học sâu (Deep Learning) và học tăng cường (Reinforcement Learning - RL) đã mở ra nhiều hướng giải quyết cho các bài toán điều hướng tự động. Bài toán giải mê cung (Maze solving) là một bài toán nền tảng, có giá trị ứng dụng thực tiễn cao trong điều khiển chuyển động của robot, hệ thống định vị vệ tinh, quy hoạch lộ trình giao thông cũng như tối ưu hóa luồng vận chuyển hàng hóa tự động giữa các điểm trong kho bãi.

Khóa luận xuất phát từ nghiên cứu tiền đề "Design Hardware Accelerator for Dyna-Q Algorithm to Solve 5x5 Maze Problem" của nhóm tác giả Hiếu, Thiện, Phúc. Nghiên cứu trước đây ứng dụng giải thuật Dyna-Q-Learning để tìm đường đi ngắn nhất trên ma trận kích thước 5x5. Tuy nhiên, giải thuật Dyna-Q bộc lộ hạn chế nghiêm ngặt khi mở rộng kích thước mê cung do hiện tượng bùng nổ không gian trạng thái trong bảng tra cứu (lookup table). Nhằm vượt qua giới hạn này, nhóm tác giả đề xuất giải pháp thay thế Dyna-Q-Learning bằng Deep-Q-Learning (kết hợp mạng nơ-ron xấp xỉ hàm giá trị với học tăng cường) để giải quyết bài toán tìm đường đi tối ưu trên không gian mê cung kích thước 10x10.

Mục tiêu và nhiệm vụ nghiên cứu của đề tài được xác định gồm ba nội dung chính:

1. Nghiên cứu, phân tích nền tảng lý thuyết về Học tăng cường (Reinforcement Learning), mạng nơ-ron nhân tạo (Neural Network), giải thuật Deep-Q-Learning, thuật toán lan truyền ngược (Backpropagation) và phương pháp tối ưu hóa Gradient Descent Momentum (GDM).
2. Nghiên cứu, phân tích, thiết kế kiến trúc phần cứng và hiện thực giải thuật giải bài toán tìm đường đi ngắn nhất trong mê cung 10x10 bằng ngôn ngữ mô tả phần cứng Verilog HDL (RTL).
3. Hiện thực, kiểm chứng và đánh giá thiết kế trên kit phần cứng FPGA Xilinx Virtex-7 VC707 dưới dạng lõi IP tích hợp trong hệ thống vi hệ thống trên chip (SoC).

Về đối tượng và phạm vi nghiên cứu:

• Đối tượng nghiên cứu: Tác nhân tự hành (Agent) hoạt động trong môi trường mê cung kích thước 10x10.
• Phạm vi tri giác và không gian: Môi trường mê cung gồm 100 ô trạng thái có bố trí tường chắn (ô quái) và ô đích (kho báu). Tác nhân chỉ nhận diện thông tin của duy nhất ô mà nó đang đứng (không có tầm nhìn quan sát các ô phía trước).
• Phạm vi công nghệ và thời gian: Khóa luận kỹ sư ngành Kỹ thuật Máy tính, hoàn thành năm 2022 tại Trường Đại học Công nghệ Thông tin - Đại học Quốc gia Thành phố Hồ Chí Minh, thực thi trên nền tảng phần mềm Python, ModelSim, Xilinx Vivado và kit FPGA Virtex-7 VC707.

Cơ sở lý thuyết và phương pháp

Khung lý thuyết của đề tài xây dựng dựa trên sự kết hợp giữa học tăng cường và mạng nơ-ron tích hợp:

• Học tăng cường (Reinforcement Learning): Mô hình hóa tương tác giữa Tác nhân (Agent) và Môi trường (Environment) thông qua cơ chế thử và sai (trial-and-error). Các thành phần cơ bản bao gồm Trạng thái (State), Hành động (Action), Phần thưởng (Reward), Chính sách (Policy) và Tập tương tác (Episode).
• Quy trình ra quyết định Markov (Markov Decision Process - MDP): Biểu diễn bài toán dưới dạng bộ tứ $(S, A, R, P)$ dựa trên tính chất Markov (không nhớ), trong đó trạng thái kế tiếp chỉ phụ thuộc vào trạng thái hiện tại và hành động được thực thi.
• Giải thuật Deep-Q-Learning: Giải quyết bài toán mở rộng trạng thái bằng cách sử dụng mạng nơ-ron thay cho bảng tra cứu lookup table truyền thống để xấp xỉ hàm giá trị $Q(s, a)$. Đầu vào của mạng là 100 trạng thái của mê cung, đầu ra là 4 giá trị Q tương ứng với 4 hành động. Kỹ thuật phát lại kinh nghiệm (Experience Replay) lưu trữ các bộ chuyển đổi $[s, a, r, s']$ vào bộ nhớ đệm và tiến hành lấy mẫu ngẫu nhiên thành các batch để huấn luyện mạng, giúp đa dạng hóa dữ liệu và loại bỏ nguy cơ quá khớp (overfitting) do các trạng thái liên tiếp có tính tuần tự.
• Hàm mất mát và tối ưu hóa: Sử dụng hàm sai số bình phương trung bình (Mean Square Error - MSE hay L2 Loss). Thuật toán tối ưu Gradient Descent Momentum (GDM) với hệ số $\gamma = 0.9$ được sử dụng để cập nhật trọng số và bias thông qua lan truyền ngược (Backpropagation) dựa trên quy tắc chuỗi (chain rule), giúp vượt qua các điểm cực tiểu cục bộ (local minimum).
• Hàm kích hoạt (Activation Function): Sử dụng hàm ReLU ($f(x) = \max(0, x)$) tại các tầng ẩn nhằm tăng tốc độ hội tụ (nhanh hơn 6 lần so với hàm Tanh) và tiết kiệm chi phí phần cứng do không phải tính toán hàm số mũ phức tạp.
• Định dạng dữ liệu: Tất cả các tính toán ma trận trọng số, sai số và giá trị Q đều được thực thi theo chuẩn số thực dấu chấm động 32-bit (Floating-Point 32-bit IEEE 754).

Phương pháp nghiên cứu thực tế gồm hai giai đoạn:

1. Mô phỏng thuật toán bằng phần mềm: Sử dụng ngôn ngữ Python để mô hình hóa giải thuật Deep-Q-Learning trong mê cung 10x10; đồng thời áp dụng giải thuật tìm kiếm theo chiều rộng Lee (Lee Algorithm) trên phần mềm làm chuẩn đối đối chứng độ chính xác của đường đi ngắn nhất.
2. Thiết kế và kiểm chứng phần cứng: Hiện thực thiết kế ở mức thanh ghi (Register-Transfer-Level - RTL) bằng ngôn ngữ Verilog HDL. Mô phỏng chức năng và kiểm tra dạng sóng thời gian trên ModelSim, sau đó tổng hợp logic, triển khai định tuyến (Place & Route) và nạp thử nghiệm trên phần cứng FPGA Virtex-7 VC707 thông qua phần mềm Xilinx Vivado.

Thiết kế và triển khai

Hệ thống phần cứng hoàn chỉnh gồm 4 khối chức năng chính: Khối Môi trường (Environment), Khối Tác nhân (Agent), Khối Lan truyền ngược (Backprop) và Khối Hành động ngắn nhất (Shortest action).

Khối chức năng	Vai trò và nhiệm vụ kỹ thuật trong kiến trúc phần cứng
Environment	Lưu trữ mảng trạng thái mê cung 10x10 (100 ô); tiếp nhận hành động từ Agent; tính toán và trả về trạng thái kế tiếp (nextstate), điểm thưởng (reward) và cờ báo kết thúc (isgameon).
Agent	Tiếp nhận trạng thái từ Environment; tính toán 4 giá trị Q thông qua 2 tầng Fully Connected (FC1, FC2); quyết định xuất hành động ngẫu nhiên hay tối ưu qua khối Policy Generator.
Backprop	Lưu trữ các bộ chuyển đổi kinh nghiệm (transition); lấy mẫu ngẫu nhiên 32 tập dữ liệu; tính toán đạo hàm hàm mất mát và cập nhật trọng số, bias cho mạng nơ-ron bằng thuật toán GDM.
Shortest action	Ghi nhận chuỗi hành động trong chế độ run_episode; so sánh tổng số bước đi với kỷ lục hiện tại để lưu trữ đường đi ngắn nhất đến đích qua 50 episode.

Cơ chế phân định điểm thưởng và mã hóa ô trong khối Environment được thiết lập cụ thể:

Trường hợp di chuyển của tác nhân	Điểm thưởng nhận được (Reward)
Bước đi bình thường (từ ô trắng sang ô trắng)	-50
Đi vào ô đã từng đi qua (visited)	-200
Đi vào ô tường chắn (ô quỷ) hoặc va vào biên mê cung	-1000
Đi đến ô có kho báu (ô đích)	+1000

Mê cung 10x10 được biểu diễn bằng các mã trạng thái: số 0 thể hiện ô bình thường, số 1 thể hiện ô tường (ô quỷ), số 2 là ô kho báu và số 4 là vị trí hiện tại của tác nhân. Khi tác nhân chạm đích, trạng thái kết thúc (terminal_state) được định nghĩa bằng 100 giá trị số thực dấu chấm động 32-bit 32'b10111111100000000000000000000000 (tương ứng giá trị -1.0).

Kiến trúc các khối con chi tiết:

• Phân rã khối Environment: Gồm control_env, ram_state_map, mux21, state_map, mem_visited, mux41 và total_check_step. Trong đó, total_check_step tích hợp in_state_map, in_mem_visited và check_step để kiểm tra va chạm, xác định ô đã đi qua và gán thưởng.
• Phân rã khối Agent: Tầng FC1 nhận 100 trạng thái đầu vào, xuất 16 trạng thái ẩn; tầng FC2 nhận 16 trạng thái ẩn, xuất 4 giá trị Q (tương ứng 4 hành động: 00 - phải, 01 - trái, 10 - xuống, 11 - lên). Khối tính toán Fully Connected sử dụng bộ nhân và bộ cộng dấu chấm động 32-bit kết hợp khối ReLU. Khối Policy Generator sử dụng thanh ghi dịch phản hồi tuyến tính random_lfsr tạo số ngẫu nhiên 8-bit để so sánh với số lượng episode hiện tại, điều khiển bộ ghép kênh mux21 chuyển đổi giữa khám phá ngẫu nhiên và khai thác giá trị Q cực đại (POLICY MAX).
• Phân rã khối Backprop: Chứa bộ đệm lưu trữ chuyển trạng thái. Khi tích lũy đủ 32 transition, khối TD ERROR kích hoạt bộ sinh ngẫu nhiên để chọn 32 mẫu, tính toán sai số TD và đạo hàm hàm mất mát. Các khối TD UPDATE OP và TD UPDATE IP áp dụng quy tắc chuỗi để tính đạo hàm theo trọng số và bias cho tầng đầu ra và tầng đầu vào. Sau đó, 4 khối UPDATE WEIGHT OP, UPDATE BIAS OP, UPDATE WEIGHT IP, UPDATE BIAS IP thực hiện thuật toán GDM để cập nhật trực tiếp vào bộ nhớ của Agent và Backprop.

Nội dung chính theo từng chương

Chương 1: Giới thiệu tổng quan đề tài

Chương 1 phân tích bối cảnh bùng nổ của trí tuệ nhân tạo, sự phát triển của Deep Learning và vị trí của học tăng cường trong các bài toán tự hành. Tác giả khảo sát nghiên cứu trước đây về việc thiết kế bộ tăng tốc phần cứng cho thuật toán Dyna-Q giải mê cung 5x5 của nhóm tác giả Hiếu, Thiện, Phúc; chỉ ra điểm nghẽn giới hạn kích thước của thuật toán này do dung lượng bảng tra cứu Q-value tăng theo cấp số nhân. Từ đó, chương 1 xác định hướng nghiên cứu đề tài là ứng dụng Deep-Q-Learning để thay thế Dyna-Q nhằm mở rộng không gian giải quyết mê cung lên kích thước 10x10, thiết lập mục tiêu thiết kế phần cứng RTL trên ngôn ngữ Verilog và triển khai trên FPGA Virtex-7 VC707.

Chương 2: Cơ sở lý thuyết

Chương 2 cung cấp toàn bộ nền tảng toán học và thuật toán được sử dụng trong đề tài. Nội dung trình bày chi tiết về quy trình ra quyết định Markov (MDP), hàm giá trị $Q(s, a)$, công thức sai khác thời gian Temporal Difference (TD), và nguyên lý hoạt động của mạng nơ-ron truyền thẳng đa tầng. Tác giả đi sâu phân tích hạn chế của bảng tra cứu Q-learning khi số trạng thái lớn (ví dụ không gian 10.000 trạng thái và 1.000 hành động đòi hỏi bảng tra 10 triệu ô), dẫn chứng sự cần thiết của Deep-Q-Learning cùng cơ chế Experience Replay để chống quá khớp. Bên cạnh đó, các công thức toán học của hàm mất mát sai số bình phương trung bình (MSE), thuật toán tối ưu Gradient Descent Momentum, hàm kích hoạt ReLU cùng hiện tượng "Dying ReLU" và phương pháp tính lan truyền ngược (Backpropagation) qua từng lớp nơ-ron được diễn giải đầy đủ.

Chương 3: Thiết kế tổng quan

Chương 3 xây dựng sơ đồ khối tổng thể của hệ thống gồm 4 phân vùng chức năng: Environment, Agent, Backprop và Shortest action. Tác giả thiết lập chu trình vận hành của hệ thống: Environment cung cấp trạng thái cho Agent, Agent suy luận hành động chuyển sang cho Environment thực thi; các dữ liệu chuyển trạng thái được tích lũy vào Backprop để lấy mẫu cập nhật trọng số và bias sau mỗi chu kỳ 32 mẫu. Chương này cũng chuẩn hóa quy trình thiết kế 5 bước: (1) Tìm hiểu giải thuật; (2) Mô phỏng kiểm chứng thuật toán bằng Python; (3) Hiện thực RTL cho các khối chính; (4) Tích hợp khối và xây dựng bộ điều khiển trung tâm; (5) Mô phỏng dạng sóng trên ModelSim và thực hiện Post-Implementation trên Xilinx Vivado.

Chương 4: Thiết kế chi tiết

Chương 4 là chương trọng tâm kỹ thuật, mô tả chi tiết giao tiếp tín hiệu, sơ đồ logic và chức năng của từng khối thành phần ở mức RTL. Tác giả trình bày cấu trúc chi tiết của khối Environment và khối xử lý Total_check_step, bao gồm cơ chế đọc/ghi bộ nhớ trạng thái mê cung và bộ nhớ mem_visited để kiểm soát các ô đã đi qua. Tiếp đó, cấu trúc khối Agent được phân tích với 2 lớp kết nối đầy đủ (FC1, FC2), chi tiết hóa việc xử lý dấu chấm động 32-bit và cơ chế chọn hành động của Policy Generator. Khối Backprop được phân rã thành các bộ tính toán đạo hàm TD ERROR, TD UPDATE OP, TD UPDATE IP cùng các khối cập nhật tham số sử dụng GDM. Cuối cùng, nguyên lý hoạt động của khối Shortest action được mô tả thông qua cơ chế so sánh và lưu vết số lượng hành động nhỏ nhất sau mỗi episode kết thúc.

Chương 5: Hiện thực thiết kế, mô phỏng và nạp ứng dụng của thiết kế vào FPGA

Chương 5 trình bày toàn bộ kết quả thực nghiệm và kiểm chứng hệ thống. Đầu tiên, tác giả mô phỏng thuật toán trên môi trường Python để xác nhận tác nhân tìm được đường đi ngắn nhất đến ô kho báu sau khi huấn luyện, đồng thời đối chiếu trực tiếp với kết quả từ giải thuật kinh điển Lee Algorithm để kiểm tra tính chính xác của lộ trình. Tiếp theo, các kết quả mô phỏng RTL trên phần mềm ModelSim được công bố thông qua các dạng sóng thời gian của khối Environment, quá trình truyền thẳng (Forward), và các tín hiệu cập nhật trọng số (newweightOP, newweightIP), bias mới (newbiasOP, newbiasIP). Kết quả dạng sóng phần cứng được đối chiếu trùng khớp hoàn toàn với kết quả tính toán trên phần mềm Python. Cuối cùng, tác giả trình bày việc tổng hợp thiết kế thành lõi IP trên công cụ Xilinx Vivado, tích hợp vào mô hình SoC kết nối bus và triển khai tạo bitstream trên kit phần cứng FPGA Virtex-7 VC707.

Chương 6: Kết luận và hướng phát triển của đề tài

Chương 6 tổng kết các kết quả đạt được của khóa luận trong việc hiện thực thành công kiến trúc phần cứng cho giải thuật Deep-Q-Learning giải mê cung 10x10. Tác giả nêu rõ các trở ngại kỹ thuật đã gặp phải, chủ yếu liên quan đến độ phức tạp tính toán của các khối số thực dấu chấm động 32-bit và việc đồng bộ dữ liệu giữa các bộ nhớ đệm. Đồng thời, chương này đề xuất các định hướng nâng cấp tiếp theo của đề tài.

Kết quả và đóng góp

Kết quả thực nghiệm của khóa luận được xác lập trên cả hai phương diện phần mềm và phần cứng:

• Tính chính xác của thuật toán: Mô hình phần mềm Python và thiết kế phần cứng RTL đều huấn luyện thành công tác nhân tìm được đường đi ngắn nhất trong mê cung 10x10. Kết quả đường đi và các hành động thực thi của tác nhân trùng khớp hoàn toàn với kết quả kiểm chứng của giải thuật tìm đường kinh điển Lee Algorithm.
• Kiểm chứng thiết kế RTL: Dạng sóng mô phỏng của quá trình tính toán lan truyền xuôi (Forward), hàm mất mát và các giá trị trọng số mới (newweightOP, newweightIP), bias mới (newbiasOP, newbiasIP) trên ModelSim phản ánh độ chính xác số học tuyệt đối so với mô hình tham chiếu trên Python.
• Hiện thực phần cứng trên FPGA: Thiết kế được đóng gói thành công thành khối IP chuẩn, kết nối hoàn chỉnh trong hệ thống SoC trên phần mềm Vivado, thực hiện tổng hợp, gán chân, tạo bitstream và kiểm tra mức tiêu thụ tài nguyên, công suất trên bo mạch phần cứng Xilinx Virtex-7 VC707.

Đóng góp của khóa luận so với các nghiên cứu trước:

• Vượt qua giới hạn kích thước của nghiên cứu tiền đề: Khóa luận đã giải quyết thành công bài toán mê cung kích thước 10x10 (gồm 100 ô trạng thái), vượt trội so với giới hạn mê cung 5x5 (25 trạng thái) sử dụng giải thuật Dyna-Q của nhóm tác giả Hiếu, Thiện, Phúc.
• Khắc phục triệt để bùng nổ bộ nhớ: Bằng việc đưa mạng nơ-ron xấp xỉ hàm giá trị Q và kỹ thuật Experience Replay lên phần cứng RTL, hệ thống triệt tiêu sự phụ thuộc vào bảng tra cứu bộ nhớ dung lượng lớn khi không gian trạng thái mở rộng.
• Tối ưu hóa tri giác cục bộ: Tác nhân tìm ra lộ trình ngắn nhất đến kho báu chỉ dựa trên thông tin tọa độ của duy nhất ô hiện tại, không đòi hỏi phần cứng phải thu nhận hay xử lý tầm nhìn bao quát các ô phía trước.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của đề tài được tác giả ghi nhận:

• Độ phức tạp phần cứng cao: Việc sử dụng toàn bộ các phép tính toán ma trận, hàm mất mát và cập nhật tham số theo định dạng số thực dấu chấm động 32-bit (FP32) đòi hỏi nhiều tài nguyên tính toán số học trên FPGA.
• Phạm vi thử nghiệm: Hệ thống mới kiểm nghiệm dừng lại ở quy mô mê cung 10x10 với số lượng 50 episode huấn luyện và tối đa 100 bước đi mỗi episode.
• Mức độ triển khai thực tế: Đề tài đã hoàn thành mô phỏng RTL, tổng hợp IP và tạo bitstream trên kit FPGA Virtex-7 VC707 nhưng chưa ghép nối trực tiếp với cơ cấu chấp hành phần cứng của cánh tay robot hoặc xe tự hành thực tế.

Hướng nghiên cứu và phát triển tiếp theo:

• Mở rộng kiến trúc phần cứng để xử lý các không gian mê cung có kích thước và độ phức tạp lớn hơn 10x10.
• Nghiên cứu tối ưu hóa việc sử dụng tài nguyên phần cứng và cải thiện tốc độ xử lý, xem xét tối ưu hóa định dạng dữ liệu số học (như số dấu phẩy tĩnh hoặc giảm số bit dấu chấm động) và cấu trúc đường ống pipeline.
• Chuyển giao và tích hợp lõi IP phần cứng lên hệ thống robot di động thực tế để thực hiện điều khiển điều hướng thời gian thực trong môi trường vật lý.

Giá trị tham khảo

Khóa luận là tài liệu kỹ thuật có giá trị tham khảo chuyên sâu cho sinh viên, học viên cao học và kỹ sư thuộc các chuyên ngành Kỹ thuật Máy tính, Thiết kế Vi mạch, Điện tử - Viễn thông và Khoa học Máy tính. Tài liệu đặc biệt hữu ích cho những đề tài nghiên cứu về bộ tăng tốc phần cứng cho trí tuệ nhân tạo (AI Hardware Accelerator) và hiện thực học tăng cường sâu (Deep Reinforcement Learning) trên nền tảng FPGA.

Các nội dung có giá trị tham chiếu cao nhất trong công trình bao gồm:

• Thiết kế chi tiết mức RTL của khối Lan truyền ngược (Backprop) sử dụng phương pháp tối ưu hóa Gradient Descent Momentum hoàn toàn bằng phần cứng.
• Kỹ thuật xây dựng bộ đệm phát lại kinh nghiệm (Experience Replay Buffer) và cơ chế lấy mẫu ngẫu nhiên 32 mẫu thông qua thanh ghi dịch phản hồi tuyến tính (LFSR).
• Quy trình chuẩn hóa kiểm thử đối chiếu từ mô hình thuật toán trên Python, giải thuật Lee Algorithm, mô phỏng chức năng trên ModelSim cho đến đóng gói lõi IP SoC trên phần mềm Xilinx Vivado.

Câu hỏi thường gặp

1. Tác nhân (Agent) nhận được những thông tin đầu vào nào từ môi trường để tìm đường đi trong mê cung?
Tác nhân chỉ tiếp nhận duy nhất thông tin về kích thước mê cung và tọa độ trạng thái của ô mà nó đang đứng (được mã hóa thành vector 100 trạng thái đầu vào, thể hiện bằng số thực dấu chấm động 32-bit). Tác nhân hoàn toàn không nhìn thấy hoặc nhận biết thông tin của các ô nằm ở phía trước.

2. Hệ thống quy định mức điểm thưởng và phạt (Reward) cụ thể như thế nào cho từng hành động của tác nhân?
Điểm thưởng được khối total_check_step trong Environment tính toán theo 4 mức cố định: phạt -50 điểm cho mỗi bước đi bình thường (phí tối thiểu di chuyển từ ô trắng sang ô trắng); phạt -200 điểm nếu đi vào ô đã từng đi qua; phạt -1000 điểm nếu đi vào ô tường chắn (ô quỷ) hoặc đi ra ngoài biên mê cung; và thưởng +1000 điểm khi tác nhân đi vào ô có kho báu (ô đích).

3. Khối Backprop bắt đầu kích hoạt quá trình cập nhật trọng số cho mạng nơ-ron vào thời điểm nào và sử dụng phương pháp gì?
Khối Backprop chỉ bắt đầu kích hoạt quá trình cập nhật trọng số khi bộ nhớ đệm đã lưu trữ đủ 32 bộ chuyển trạng thái (transition). Khi đó, khối TD ERROR sẽ lấy mẫu ngẫu nhiên 32 tập dữ liệu, tính toán đạo hàm hàm mất mát MSE và sử dụng thuật toán Gradient Descent Momentum (GDM) kết hợp quy tắc chuỗi để cập nhật đồng thời các ma trận trọng số và vector bias mới cho cả tầng ẩn và tầng đầu ra của mạng nơ-ron trong Agent và Backprop.

4. Tại sao nhóm tác giả lại thay thế giải thuật Dyna-Q-Learning bằng Deep-Q-Learning?
Nghiên cứu tiền đề sử dụng Dyna-Q-Learning phải lưu trữ bảng tra cứu Q-value dạng ma trận trạng thái - hành động. Khi kích thước mê cung mở rộng, số lượng trạng thái tăng nhanh khiến kích thước bảng tra vượt quá tầm kiểm soát và tiêu tốn bộ nhớ nghiêm trọng (chẳng hạn 10.000 trạng thái và 1.000 hành động tạo ra bảng tra 10 triệu ô). Deep-Q-Learning sử dụng mạng nơ-ron để xấp xỉ hàm giá trị Q, giúp giải quyết triệt để vấn đề dung lượng bộ nhớ khi xử lý mê cung 10x10.

5. Kết quả tìm đường đi ngắn nhất của thiết kế phần cứng được kiểm chứng độ chính xác với giải thuật nào?
Độ chính xác của đường đi ngắn nhất được nhóm tác giả kiểm chứng bằng cách so sánh trực tiếp kết quả huấn luyện với lộ trình tìm kiếm tối ưu của giải thuật Lee (Lee Algorithm) – một giải thuật kinh điển dựa trên tìm kiếm theo chiều rộng (BFS) để tìm đường đi ngắn nhất trong ma trận trên mô hình phần mềm.

Kết luận

Khóa luận tốt nghiệp của sinh viên Nguyễn Duy Thanh và Trần Nguyễn Minh Triết đã nghiên cứu, thiết kế và hiện thực thành công kiến trúc phần cứng chuyên dụng cho giải thuật Deep-Q-Learning giải bài toán tìm đường đi ngắn nhất trong mê cung 10x10. Hệ thống đã khắc phục được rào cản bùng nổ không gian bộ nhớ của giải thuật Dyna-Q truyền thống trên mê cung 5x5 thông qua việc kết hợp mạng nơ-ron nhân tạo và cơ chế Experience Replay trên mức RTL. Toàn bộ thiết kế được kiểm chứng độ chính xác số học thông qua việc đối chiếu với giải thuật Lee trên phần mềm, đồng thời hoàn thành quá trình đóng gói lõi IP, kết nối SoC và tạo bitstream trên nền tảng FPGA Xilinx Virtex-7 VC707, cung cấp một giải pháp tham khảo giá trị cho các hướng nghiên cứu bộ tăng tốc phần cứng trí tuệ nhân tạo.

Trích đoạn nội dung tài liệu

Đặt vấn đề Trong những năm gần đây, AI hiện diện trong mọi lĩnh vực của đời sống con người, từ kinh tế, giáo dục, y khoa cho đến những công việc nhà, giải trí hay thậm chí là trong quân sự. Những ứng dụng nổi bật trong việc phát trién AI đến từ nhiều lĩnh vực để giải quyết nhiều vấn đề khác nhau. Nhưng những đột phá phần nhiều đến từ Deep Learning (học sâu) - một mảng nhỏ đang mở rộng dần đến từng loại công việc, từ đơn giản đến phức tạp. Deep Learning đã giúp máy tính thực thi những việc tưởng chừng như không thê vào 15 năm trước: phân loại cả ngàn vật thê khác nhau trong các bức ảnh, tự tạo chú thích cho ảnh, bắt chước giọng nói và chữ viết của con người, giao tiếp với con người, hay thậm chí cả sáng tác văn, phim, ảnh, âm nhạc [1].

Trong số tat cả các loại mô hình Machine Learning, Reinforcement Learning (RL) là mô hình được sử dụng đề xử lí bài toán trong đề tài. Học tăng cường (Reinforcement Learning) là một trong ba kiéu hoc máy chính bên cạnh hoc giám sat (Supervised Learning) và học không giám sát (Unsupervised Learning). Phương pháp này được học theo cách tự nó huấn luyện và học tập dựa vào những mức điểm thưởng và mức phạt khi nó thực hiện một hành động trong môi trường. Bản chất là tác nhan(Agent) tương tac với môi trường(Environment) thông qua hành động(Action).

Kiểu học này được ứng dụng trong Makerting, Robotics, Gaming, Image Processing,. Shao và cộng sự thiết kế tăng tốc phần cứng dựa trên FPGA cho Trust Region Policy Optimization (TRPO), một thuật toán nâng cao trong Deep Reinforcement Learning và chuyền hóa quá trình huấn luyện của họ dé điều khiển một cánh tay robot thực sự [2I. Việc giải mê cung (Maze solving) đang phát triển rất nhanh và nhận được sự quan tâm ở lĩnh vực robot cũng như các cuộc thi quốc tế về robot. Thuật toán giải mê cung được ứng dụng trong việc định vi vệ tinh, tìm đường đi trên các con đường hay việc tìm đường đi cho việc chuyền hàng hoá giữa 2 điểm trong kho hàng.

Hướng nghiên cứu đề tài Trong đề tài nghiên cứu “DESIGN HARWARE ACCELERATOR FOR DYNA-Q ALGORITHM TO SOLVE 5x5 MAZE PROBLEM” của tác giả Hiếu, Thiện, Phúc sử dụng giải thuật Dyna-Q-Learning dé thực hiện việc tìm đường đi ngắn nhất trong ma trận. Tuy nhiên giải thuật đó sẽ bị hạn chế đối với những ma trận có kích thước lớn hơn. Dựa vào đó nhóm đề xuất giải pháp sử dụng Deep-Q-Learning dé thay thé cho Dyna-Q-Learning và kết hợp với Học tăng cường (Reinforcement Learning) dé giải quyết vấn đề kích thước ma trận. Trong đề tài, đối tượng (Agent) chỉ tiếp xúc với môi trường mê cung và chỉ nhận thông tin của ô mà nó đang đứng (không cần nhìn các ô phía trước).

Với ít thông tin về môi trường, đôi tượng của nhóm có thê tìm ra con đường tôi ưu đên kho báu. Mục tiêu đề tài Trong khoá luận luận này, nhóm sẽ nghiên cứu, phân tích và tìm hiểu lý thuyết về Reinforcement Learning, Deep Q Learning, Backpropagation, Neural Network. Phan kế tiếp nhóm sẽ nghiên cứu, phân tích và thiết kế, hiện thực việc giải quyết bài toán tìm đường đi ngắn nhất trong mê cung 10x10 bằng ngôn ngữ phần cứng Verilog và hiện thực việc giải bài toán trên board FPGA Virtex-7 VC707. Học tăng cường Bản chất của Reinforcement Learning là trial-and-error, nghĩa là thử đi thử lại và rút ra kinh nghiệm sau mỗi lần thử như vậy.

Bằng cách tận dụng sức mạnh của tìm kiếm và nhiều thử nghiệm, Reinforcement Learning hiện là cách hiệu quả nhất dé gợi ý sự sáng tạo của máy móc [3]. State Action Reward gent Hinh 2.1 : Agent va Environment Dưới đây là một số thuật ngữ quan trong liên quan đến học tăng cường : e Tác nhân (Agent) : nó là một thực thể giả định thực hiện các hành động trong một môi trường đề đạt được một số phần thưởng. e Hanh động (Action) : là phương thức của tác nhân cho phép nó tương tác với môi trường và thay đôi môi trường. e Môi trường (Environment) : một tinh huống mà một tác nhân phải đối mặt.

e Phan Thuong (Reward) : ngay lập tức được trao cho tác nhân khi nó thực hiện một hành động cụ thê. e Trạng thái (State) : tình trạng hiện tai của tác nhân do môi trường trả lại. e_ Chính sách (Policy) : Là một chiến lược được thực hiện bởi tác nhân dé quyết định hành động tiếp theo dựa trên trạng thái hiện tại. e Tập (Episode) : loạt tương tác giữa tác nhân và môi trường từ lúc bắt đầu đến kết thúc.

Loss Function: Mean Square Error Mean Square Error (MSE) hay còn được gọi là L2 Loss là ham loss function đơn giản nhất và phô biến nhất. MSE được sử dụng cho các mô hình hồi quy, đặc biệt là các mô hình hồi quy tuyến tính. Dé tính toán MSE, ta sẽ lay độ chênh lệch của mô hình dự đoán và mô hình thực tế. MSE không bao giờ âm bởi vì nó luôn bình phương các sai số.

Công thức MSE được tính bằng tổng các bình phương của hiệu giữa giá trị thực (yi: target) và giá trị mà mô hình của chúng ra dự đoán (¥;: predicted). Công thức của MSE: 2. Thuật toán Gradient descent momentum Thuật toán Gradient descent (GD) thường được so sánh với tác dụng của trọng lực lên một hòn bi đặt trên một mặt có dạng như hình một thung lũng giống như hình 2. Bat kế ta đặt hòn bi ở A hay B thì cuối cùng hòn bi cũng sẽ lăn xuống và kết thúc ở vị trí C.

a) GD b) GD c) GD with momentum Hình 2.2 : So sánh Gradient Descent với các hiện tượng vật lý Tuy nhiên, nếu như bề mặt có hai đáy thung lũng như Hình 2.2 (b) thì tùy vào việc đặt bi ở A hay B, vị trí cuối cùng của bi sẽ ở C hoặc D. Điểm D là một điểm local minimum chúng ta không mong muôn. Nếu suy nghĩ một cách vật lý hơn, vẫn trong Hình 2.2 (b), nếu vận tốc ban đầu của bi khi ở điểm B đủ lớn, khi bi lăn đến điểm D, theo đà, bi có thể tiếp tục di chuyên lên dốc phía bên trái của D. Và nếu giả sử vận tốc ban đầu lớn hơn nữa, bi có thé vượt dốc tới điểm E rồi lăn xuống C như trong Hình 2.

Dựa trên hiện tượng này, một thuật toán được ra đời nhăm khắc phục việc nghiệm cua GD rơi vào một diém local minimum không mong muôn. Thuật toán đó có tên là Momentum. Công thức Momentum: xnew = xold - (gama.gradient) Trong đó : e xnew: tọa độ mới e xold: tọa độ cũ e gama: parameter , thường = 0.9 e learningrate : tốc độ hoc e gradient : đạo hàm của hàm f Ưu điểm: Thuật toán tối ưu giải quyết được van dé Gradient Descent không tiến được tới điểm global minimum mà chỉ dừng lại ở local minimum. Nhược điểm : Tuy momentum giúp hòn bi vượt dốc tiến tới điểm đích, nhưng khi tới gần đích, nó vẫn mat khá nhiều thời gian giao động qua lại trước khi dừng han, điều này được giải thích vì viên bi có da.

Activation Function: ReLU =2 ReLU(X) GWNrF©ŒO+owYRP | _ xẻ o 7.3 : Dé thị hàm ReLU Hàm ReLU đang được sử dụng khá nhiều trong những năm gần đây khi huấn luyện 5. ReLU đơn giản lọc các giá trị < 0. Nhìn vào công thức chúng ta dễ dàng hiểu được cách hoạt động của nó. Một số ưu điểm khá vượt trội của nó so với Sigmoid và Tanh [4] : « Tốc độ hội tụ nhanh hơn hắn.

ReLU có tốc độ hội tụ nhanh gấp 6 lần Tanh. Điều này có thê do ReLU không bị bão hoà ở 2 đầu như Sigmoid và Tanh. e Tinh toán nhanh hơn. Tanh và Sigmoid sử dụng hàm exp và công thức phức tạp hơn ReLU rất nhiều do vậy sẽ tốn nhiều chi phí hơn dé tính toán.

Tuy nhiên ReLU cũng có một nhược điểm: e - Với các node có giá trị nhỏ hơn 0, qua ReLU activation sẽ thành 0, hiện tượng day gọi là “Dying ReLU“. Nếu các node bị chuyền thành 0 thì sẽ không có ý nghĩa với bước linear activation ở lớp tiếp theo và các hệ số tương ứng từ node day cũng không được cập nhật với gradient descent. => Leaky ReLU ra đời. « Khi learning rate lớn, các trọng số (weights) có thé thay đổi theo cach làm tat cả neuron dừng việc cập nhật.

Mê cung 10x10 Môi trường : Mê cung 10x10 với các quỷ (ô tường) và kho báu (ô đích) Mục tiêu : Tìm đường đi ngắn nhất trong mê cung. Luật : e Nếu đi vào 6 quỷ hoặc ra khỏi mê cung thi sẽ quay lại ô trước đó e Tác nhân (Agent) chỉ có thé biết về kích thước mê cung và thông tin của 6 hiện tại của nó. Không thé nhìn thấy được thông tin của ô phía trước. e Khi đến được kho báu trò chơi sẽ kết thúc.

Quy trình ra quyết định Markov Quy trình ra quyết định Markov (Markov Decision Process -MDP) là một framework giúp agent dua ra quyết định tại một state nào đó. Dé áp dụng được framework nay, ta giả sử các states có thuộc tính Markov (Markov Property): mỗi state chỉ phụ thuộc vào state trước nó vào xác suất chuyển đổi giữa 2 states này. Trong một "thế giới hoàn hảo", nếu ta lặp lại một hành động thì sẽ cho ra 2 kết quả giống hệt nhau. Nhưng mọi việc không đơn giản như vậy vì hau hét mọi sự việc đêu là các tiên trình ngẫu nhiên (stochastic process) [5].

Giả sử agent đang ở vị trí như hình đưới, việc nó đến đó bằng cách nào không quan trọng, nó có thể vòng từ trên bức tường xuống hoặc chui từ dưới lên hoặc thậm chí chạy sang trái sang phải 1000 lần trước khi đến nơi. Dù là cách nào thì khi agent đã ở đó, xác suất đi lên, sang trái/phải vẫn giống nhau. Có thé hiểu đơn giản Markov property là tính "không nhớ" (memoryless). Với Markov property, chúng ta có thé áp dung MDP dé biéu diễn bài toán dưới dạng: (S,A,R,P) Trong đó: e S là tập các states.

e A là tập các actions. e R là reward nhận được khi chuyền state. e P là phân bồ xác suất chuyên đổi. Việc biểu diễn này rat quan trọng, khi mà ta không phải lưu một chuỗi các states trước đó dé biéu diễn state hiện tại khiến cho việc tính toán trở nên phức tạp và tiêu tốn bộ nhớ.

z Vậy là chúng ta đã biết được MDP, nhưng áp dụng vào RL như thế nào. Làm thế nào mà agent biết phải chon action nào dé đạt được reward lớn nhất. Câu trả lời là sử dụng một giá trị gọi là Q-value được tính bằng công thức: O(s, a) = r(s,a) + ymax QO(s’, a) a Hình 2.