Đặ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.