Báo cáo khoa học: PHƯƠNG PHÁP Q-LEARNING VÀ ỨNG DỤNG CỦA PHƯƠNG PHÁP NÀY TRONG VIỆC GIẢI QUYẾT MỘT SỐ BÀI TOÁN TÌM ĐƯỜNG

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

459
lượt xem 55
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

PHƯƠNG PHÁP Q-LEARNING VÀ ỨNG DỤNG CỦA PHƯƠNG PHÁP NÀY TRONG VIỆC GIẢI QUYẾT MỘT SỐ BÀI TOÁN TÌM ĐƯỜNG ThS. CHÂU MẠNH QUANG Bộ môn Thiết kế máy Khoa Cơ khí Trường Đại học Giao thông Vận tải Tóm tắt: Q-learning là phương pháp học tăng cường rất hiệu quả cho bài toán tìm đường do phương pháp này được thực hiện theo kiểu off-policy. Vì vậy phương pháp này được điều chỉnh hoặc kết hợp với một số phương pháp khác để giải quyết các bài toán đặc biệt như tìm đường trong mạng (Q-routing) hay tìm đường của hệ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo khoa học: PHƯƠNG PHÁP Q-LEARNING VÀ ỨNG DỤNG CỦA PHƯƠNG PHÁP NÀY TRONG VIỆC GIẢI QUYẾT MỘT SỐ BÀI TOÁN TÌM ĐƯỜNG

PHƯƠNG PHÁP Q-LEARNING VÀ ỨNG DỤNG CỦA PHƯƠNG PHÁP NÀY TRONG VIỆC GIẢI QUYẾT MỘT SỐ BÀI TOÁN TÌM ĐƯỜNG ThS. CHÂU MẠNH QUANG Bộ môn Thiết kế máy Khoa Cơ khí Trường Đại học Giao thông Vận tải Tóm tắt: Q-learning là phương pháp học tăng cường rất hiệu quả cho bài toán tìm đường do phương pháp này được thực hiện theo kiểu off-policy. Vì vậy phương pháp này được điều chỉnh hoặc kết hợp với một số phương pháp khác để giải quyết các bài toán đặc biệt như tìm đường trong mạng (Q-routing) hay tìm đường của hệ thống multi-agent (Ant-Q). Summary: Q-learning is a very effective reinforcement learning method in solving path finding problem because it uses off-policy approach. Thus, this method is also modified or combined with other methods to deal with some special cases of the path finding problem. Some examples are Q-routing for network routing problems and Ant-Q for transferring knowledge in the multi-agent environment. CT 2 I. ĐẶT VẤN ĐỀ Trước đây người ta giải quyết bài toán tìm đường bằng cách sử dụng các thuật toán tìm đường cổ điển. Tuy nhiên các thuật toán tìm đường có rất nhiều hạn chế ví dụ như đòi hỏi môi trường phải xác định và cố định và không xử lý được nhiều tình huống thực tế. Với sự phát triển của trí tuệ nhân tạo, ngày nay các phương tiện với sự trợ giúp của máy tính có thể “học”, hay nói cách khác là tự tìm ra được quy luật hành động nói chung hay tìm đường nói riêng thông qua các kinh nghiệm thu được từ những hành động được thực hiện trước đó. Cách học từ những kinh nghiệm trong quá khứ này được gọi là học tăng cường. Có nhiều phương pháp học tăng cường khác nhau, trong đó phương pháp Q-learning là có hiệu quả nhất trong việc giải quyết bài toán tìm đường. Nội dung của bài bào này minh họa cho tính hiệu quả của phương pháp Q- learning và một số biến thể của phương pháp này để giải quyết bài toán tìm đường trong những môi trường đặc biệt như mạng máy tính hay multi-agent. II. HỌC TĂNG CƯỜNG Học tăng cường là phương pháp học thông qua tương tác với môi trường. Mô hình của học tăng cường gồm có 3 thành phần chính: tác tử (agent), môi trường (environment) và giá trị phản
hồi (reward). Quá trình học là một quá trình lặp đi lặp lại (iteration) các hành động (action). Sau khi thực hiện mỗi hành động thì agent nhảy từ vị trí (hay trạng thái - state) này sang vị trí (trạng thái) khác, và đồng thời nhận được giá trị phản hồi (reward) từ hành động cũ. Dựa vào các giá trị phản hồi nhận được agent có thể điều chỉnh luật chọn hành động (policy) của mình trong các bước tiếp theo. Việc điều chỉnh và tối ưu hóa luật chọn hành động dựa vào các giá trị phản hồi chính là quá trình học tăng cường. Rõ ràng là quy luật chọn lựa hành động của agent thu được sau quá trình học càng gần tối ưu nếu quá trình học càng kéo dài và số lượng các tình huống mà agent gặp phải là càng nhiều. Hình 1. Mô hình tương tác agent - môi trường Với mô hình học tăng cường như vậy thì vấn đề cần giải quyết là các thông tin phản hồi (reward) được xử lý như thế nào. Sau mỗi hành động thì agent nhận được một giá trị phản hồi và sau một quá trình học lâu dài thì số lượng các thông tin phản hồi này là rất lớn mà tại mỗi thời điểm không thể quan tâm đến tất cả mọi giá trị này được. Để giải quyết vấn đề này thì mô hình học tăng cường được đưa về mô hình Markov (MDP - Markov Decision Process), là sự mở rộng của chuỗi Markov. Chuỗi Markov là một quá trình ngẫu nhiên mà giá trị hàm xác suất (probability distribution function) của mỗi bước tiếp theo chỉ phụ thuộc vào các thông số của bước trước đó, điều này cho phép ta chỉ quan tâm tới giá trị phản hồi ngay trước đó tại mỗi vị CT 2 trí. Lý thuyết học tăng cường hiện nay dựa vào mô hình Markov, do đó các bài toán không thể đưa về được mô hình Markov thì không thể giải quyết được bằng phương pháp học tăng cường. Mô hình Markov (MDP) đ ược định nghĩa là tập hợp (tuple) : S: tập các vị trí (hay trạng thái - state). A: tập các hành động (action). T: SxA -> P(S): là hàm xác suất (probability distribution function) cho từng cặp vị trí - hành động. Hàm này gán giá trị xác suất cho từng cặp vị trí - hành động. ρ: SxA -> R: là payoff function, gán giá trị phản hồi cho từng hành động tại vị trí xác định. Mô hình Markov có thể là xác định (với từng cặp vị trí - hành động xác định thì cho ra vị trí kế tiếp giống nhau ở mọi thời điểm) hoặc không xác định. Với mô hình Markov xác suất chuyển đến vị trí s’ từ vị trí s và hành động a là: a P ss' = Pr{s t+1 =s’|s t =s,a t =a} Và giá trị phản hồi là: a R ss' = E{r t+1 |s t = s,a t = a,s t+1 = s’}
Ta gọi giá trị “return” là tổng của các giá trị phản hồi tính từ thời điểm hiện tại cho đến khi agent đạt đến đích, hoặc đến cuối giai đoạn (nếu quá trình học được chia thành nhiều giai đoạn - episode). R t = r t +1 +r t+2 +…+r T Trong đó T là bước cuối cùng trước khi đến đích. Thực nghiệm cho thấy nếu ta giảm dần mức độ quan trọng của các bước ở các thời điểm xa với thời điểm hiện tại thì quá trình học sẽ hội tụ nhanh hơn. Điều đó có nghĩa là ta cần thêm vào hệ số khấu hao γ. Giá trị phản hồi ở thời điểm cách hiện tại bao nhiêu bước thời gian thì sẽ được nhân với giá trị khấu hao γ bấy nhiêu lần. Như vậy giá trị “return” sẽ được tính như sau: ∞ ∑γ r R t = r t +1 +γr t+2 +γ 2 r t +3 +… = k t +k +1 k =0 Mọi thuật toán của học tăng cường đều dựa trên hàm giá trị. Hàm giá trị cung cấp giá trị dự đoán mức độ “tốt” của agent ở vị trí hiện tại trong quá trình tìm đến đích. Hàm này chính là giá trị “return” ước tính tại từng vị trí (hay cặp vị trí - hành động) ứng với một luật chọn hành động (policy) xác định nào đó. Ta có thể xác định hàm giá trị theo vị trí hay theo cặp giá trị vị trí - hành động. Hàm giá trị theo vị trí (state - value function) V ứng với luật chọn hành động π tại vị trí s được xác định như sau: ∞ CT 2 V π (s) = E π {R t |s t = s} = E π { ∑ γ k rt +k +1 |s t = s} k =0 Hàm giá trị theo cặp vị trí - hành động (action - state value function) Q được xác định như sau: ∞ Q π (s,a) = E π {R t |s t = s,a t = a} = E π { ∑ γ k rt +k +1 |s t = s,a t = a} k =0 Quá trình học tăng cường là quá trình tìm kiếm policy tối ưu, có nghĩa là quá trình điều chỉnh giá trị của hàm giá trị về giá trị tối ưu. Quá trình điều chỉnh được thực hiện bởi việc lặp đi lặp lại một số lượng lớn bước thực hiện các hành động, gọi là iteration. Một luật chọn hành động là tối ưu nếu và chỉ nếu giá trị của hàm giá trị ứng với luật chọn hành động đó luôn lớn hơn hoặc bằng hàm giá trị của các luật chọn hành động khác. Gọi V* và Q* là các hàm giá trị tối ưu ta có thể xác định các hàm này bằng cách sau: V*(s) = max V π (s) π Q*(s, a) = max Q π (s,a) π Có nghĩa là giá trị các hàm V* và Q* chính là giá trị của các hàm V và Q ứng với luật chọn hành động tối ưu (cho ra giá trị V(s) hay Q(s, a) lớn nhất tại mỗi vị trí s) [2].
Các loại thuật toán học tăng cường thông thường gồm có lập trình động (dynamic programming), Monte-Carlo và phương pháp TD (temporal-difference). Tuy nhiên các phương pháp lập trình động và Monte-Carlo không hiệu quả do đòi hỏi bộ nhớ quá lớn, hoặc mô hình phải xác định hay khó hội tụ nên ít khi cho ra kết quả tối ưu. Phương pháp TD là sự kết hợp của những phương pháp kể trên và cho phép giải quyết được nhiều bài toán thực tế bởi vì phương pháp này không đòi hỏi môi trường xác định và có khả năng hội tụ cao. Một biến thể của phương pháp TD được gọi là Q-learning, là phương pháp học kiểu TD theo hướng off-policy, rất hiệu quả trong việc giải quyết các bài toán tìm đường. III. PHƯƠNG PHÁP Q-LEARNING Đây là phương pháp học theo kiểu off-policy. Quá trình học tăng cường có thể được thực hiện theo hai cách: off-policy và on-policy. On-policy sử dụng một luật chọn hành động để thực hiện các bước hành động để tối ưu hóa chính luật chọn hành động đó. Phương pháp off-policy sử dụng một luật chọn hành động để thực hiện các hành động nhưng với mục đích là để tối ưu hóa một luật chọn hành động khác. Phương pháp này sử dụng hàm Q (action-state value function). Hàm Q được xác định bằng phương pháp Q-learning như sau: Q(s t ,a t ) ← Q(s t ,a t ) + α[r t+1 + γ max Q(s t+1 ,a) - Q(s t ,a t )] a Với γ là giá trị khấu hao cho giá trị Q của bước tiếp theo như đã được trình bày ở phần trước, và α là CT 2 “step size” - tham số đưa thêm vào để điều chỉnh mức độ tối ưu của quá trình học. Luật hành động học được chính là tập các hành động tại từng vị trí mà Q(s,a) tại vị trí đó lớn nhất [2]. Với cách điều chỉnh giá trị của hàm Q theo từng bước như vậy ta có thể mô tả thuật toán như sau: đầu tiên ta gán giá trị Q ban đầu cho các vị trí. Vị trí đích có giá trị phản hồi (reward) rất lớn. Vị trí “nguy hiểm” có giá trị âm rất lớn. Các vị trí khác có giá trị phản hồi là 1. Khi agent nhảy vào vị trí nào thì nhận được giá trị phản hồi của vị trí đó. Sau đó ta thực hiện lặp đi lặp lại các quá trình thực hiện hành động và cứ sau mỗi bước thực hiện hành động thì lại điều chỉnh lại giá trị hàm Q cho các vị trí liên quan đến hành động vừa được thực hiện. Luật chọn hành động dùng để học thông thường là ε-greedy. Toàn bộ quá trình thực hiện thuật toán cho một quá trình (episode) được trình bày như sau: Gán giá trị khởi đầu cho Q(s, a) Repeat (cho từng episode) Đặt s vào vị trí bắt đầu Repeat (cho từng bước của episode) Chọn hành động a (chẳng hạn bằng phương pháp ε-greedy)
Thực hiện bước a, nhận được giá trị phản hồi r và vị trí tiếp theo s’ Điều chỉnh giá trị hàm Q: Q(s, a) ← Q(s, a) + α[r + γ max Q(s’, a’) – Q(s, a)] a' s ← s’ Until s là vị trí đích hoặc đã thực hiện hết số lượng bước giới hạn của episode. Với phương pháp này thì luật chọn hành động để học thông thường được thực hiện theo phương pháp ε-greedy trong khi việc điều chỉnh giá trị hàm Q ứng với mỗi cặp vị trí – hành động (s,a) được thay đổi dựa trên giá trị Q tối ưu của cặp (s’,a’) kế tiếp mà hành động a’ không nhất thiết là hành động được chọn theo “policy” đang được áp dụng. Do đó phương pháp này thuộc loại off-policy. Xét về lý thuyết ta có thể nhận thấy phương pháp kiểu off-policy cho phép khám phá được nhiều hơn so với on-policy nên khả năng tìm ra được những lối đi mới có quãng đường ngắn hơn là cao hơn so với phương pháp on-policy. Thực nghiệm cũng xác nhận quan điểm này. Để minh họa cho lập luận trên và đồng thời để mô tả cách áp dụng thuật toán Q-learning vào bài toán tìm đường thông thường ta có thể thực hiện bài toán kinh điển gridworld bằng phương pháp Q-learning và bằng một phương pháp khác theo kiểu on-policy và so sánh kết quả. Phương pháp on-policy được chọn là SARSA – là phương pháp học rất hiệu quả theo kiểu on- CT 2 policy. Với phương pháp SARSA thì hàm Q được điều chỉnh sau mỗi bước thực hiện hành động theo công thức sau: Q(s t , a t ) ← Q(s t , a t ) + α[r t+1 + γQ(s t+1 , a t +1 ) - Q(s t , a t )] Bài toán được thực hiện bằng việc cho agent tìm đường di chuyển từ điểm khởi đầu đến điểm đích với các chướng ngại vật. Agent sẽ khởi động từ vị trí ô xanh và đích là ô đỏ. Các ô màu xám biểu thị cho vật cản. Các bước đi gồm có sang trái, sang phải, đi lên, đi xuống. Luật hành động chính là hướng đi tối ưu cho từng vị trí để đến được đích với số bước đi ngắn nhất (hình vẽ 2). Quá trình thực hiện được chia thành nhiều giai đoạn (episode), mỗi giai đoạn được kết thúc sau khi agent đến được đích hoặc agent thực hiện hết một số lượng bước được quy định. Trong quá trình thực hiện các bước đều có điều chỉnh lại giá trị hàm Q cho các vị trí liên quan. Thực nghiệm được tiến hành với các tham số thay đổi nhằm kiểm tra hiệu quả của từng thuật toán với từng điều kiện nhất định. Trong quá trình thực nghiệm thì số lượng giai đoạn cũng như bước nhảy cho mỗi giai đoạn được chọn thích hợp để thể hiện rõ sự khác biệt về kết quả các phương pháp học. Mỗi lần học thì kết quả được đo 3 lần và chọn ra kết quả tốt nhất. Bài toán được thực hiện cho cả 2 phương pháp SARSA và Q-learning, áp dụng phương pháp ε- greedy để chọn hành động và thay đổi giá trị các tham số α, γ, ε trong khoảng từ 0 - 1.
Hình 2. Chương trình thực nghiệm. Các mũi tên màu xanh là các hướng đi tối ưu - chính là bộ luật hành động tối ưu. Các mũi tên màu hồng là các hướng đi tối ưu đã học được. Các thông số cần được xác định là số ô chưa được tìm ra “policy” tối ưu và quãng đường ngắn nhất xác định được. Kết quả thống kê số ô chưa tìm được “policy” tối ưu được ghi lại trong các bảng thực nghiệm của [5]. Do khuôn khổ của bài báo có hạn nên chỉ trình bày được một vài kết quả thực nghiệm: Q-learning, ε = 0.75, 100 episode, max 100 bước/episode CT 2 γ=1 γ = 0.75 γ = 0.5 γ = 0.25 γ=0 α=1 72 22 31 66 74 α = 0.75 50 64 66 51 74 α = 0.5 55 41 42 46 74 SARSA, ε = 0.75, 100 episode, max 100 bước/episode γ=1 γ = 0.75 γ = 0.5 γ = 0.25 γ=0 α=1 72 74 68 73 74 α = 0.75 72 64 60 73 74 α = 0.5 66 68 51 54 74 Từ kết quả thực nghiệm được tiến hành ở [5] cho thấy mặc dù kết quả thực nghiệm phụ thuộc vào nhiều yếu tố (các tham số α, γ, ε), đặc biệt là giá trị ε có ảnh hưởng rất nhiều đến kết quả học của Q-learning (ε càng bé thì quá trình khám phá được thực hiện càng ít dẫn đến kết quả học của Q-learning càng xấu đi), tuy nhiên xét về kết quả chung thì Q-learning thường tìm được luật hành động tối ưu cho nhiều ô hơn. Thực nghiệm tiếp theo so sánh kết quả thực tế của hai phương pháp học trong cùng điều kiện tham số. Kết quả được xác định ở đây là đường đi ngắn nhất từ điểm khởi đầu đến đích sau
khi thực hiện từng phương pháp học, được trình bày trong bảng dưới đây: ε = 0.75, α = 0.5, 80 episode, max 100 bước/episode γ=1 γ = 0.75 γ = 0.5 γ = 0.25 γ=0 Q-learning 22 18 18 18 24 SARSA 75 75 75 75 75 ε = 0.2, α = 0.5, 80 episode, max 100 bước/episode γ=1 γ = 0.75 γ = 0.5 γ = 0.25 γ=0 Q-learning 75 75 73 75 75 SARSA 75 75 75 75 75 Với kết quả thu được ở trên ta có thể kết luận rằng bài toán gridworld thích hợp hơn với phương pháp off-policy do cần phải tìm kiếm rộng ra cho mọi ô. Kết quả thực nghiệm cũng cho thấy với điều kiện chỉ thực hiện 80 giai đoạn, với tối đa là 100 bước đi cho mỗi giai đoạn và với giá trị ε khá lớn (ở đây là 0.75) thì phương pháp Q-learning đã bắt đầu cho ra kết quả tối ưu (18 bước). Trong khi đó phương pháp SARSA với mọi giá trị của ε vẫn chưa cho ra được kết quả tối ưu. Qua đó ta có thể kết luận rằng phương pháp Q-learning mang lại hiệu quả lớn trong việc giải quyết bài toán tìm đường. Do có hiệu quả cao trong các bài toán tìm đường nên phương pháp Q-learning còn được điều chỉnh hoặc kết hợp với các thuật toán khác để giải quyết các bài toán đặc biệt. Phần tiếp theo sẽ trình bày về phương pháp Q-routing áp dụng cho tìm đường trên mạng và phương pháp Ant-Q áp dụng cho việc tìm đường của hệ thống multi-agent, là những phương pháp kết hợp với Q-learning. CT 2 IV. PHƯƠNG PHÁP Q-ROUTING Phương pháp này là biến thể của phương pháp Q-learning, dùng để xác định đường truyền ngắn nhất trên mạng. Mỗi một server trên mạng có lưu giữ giá trị Q của riêng mình. Tập các giá trị Q của các nút trên mạng tạo thành bảng giá trị Q (Q table). Khi một server x gửi gói thông tin đến server d đi qua server y kế cận với x thì server y sẽ gửi lại giá trị phản hồi cho server x là khoảng thời gian ước tính của quãng đường từ y đến d. Sau khi nhận được giá trị phản hồi từ y, x chọn server z’ trong số các server kề cận với mình mà có giá trị Q nhỏ nhất để điều chỉnh lại giá trị Q của chính mình. Quá trình học được thực hiện bằng cách cho một số lượng ngẫu nhiên các server đồng loạt gửi các gói thông tin vào mạng và sau một số lần lặp đi lặp lại quá trình này đủ lớn thì giá trị Q của các server trên mạng hội tụ về gần với giá trị tối ưu. Thuật toán được mô tả như sau: Ta gọi: Qx(d,y) - là thời gian ước đoán mà từ x ta gửi được gói thông tin đến d đi qua y kề cận với x, bao gồm cả thời gian gói thông tin nằm trong hàng đợi của x. Thuật toán gồm các bước: Khi x nhận được gói thông tin thì gửi cho máy kề cận là y. Y được chọn theo quy luật học (learning policy).
Sau khi x đã gửi gói thông tin cho y, x nhận được giá trị phản hồi từ y. Giá trị phản hồi này là giá trị Q của z nào đó kề cận với y mà có giá trị Qy(d,z) nhỏ nhất. Gọi giá trị phản hồi này là t ta có: t = min z is a neighbor of y Qy(d,z). Giả sử gói thông tin được gửi đã nằm trong hàng đợi của x thời gian là q, và thời gian để chuyển gói tin từ x sang y là s. Khi đó giá trị Q mới được điều chỉnh cho x là: Qx(d,y) ← α ( q + s + t - Qx(d,y) ) Trong đó α là “learning rate”, tức là tỷ lệ khấu hao cho từng bước học. Sau khi quá trình học kết thúc thì trong quá trình vận hành của mạng, x sẽ chọn y có giá trị Q x (d,y) nhỏ nhất khi muốn gửi gói tin đến d. V. PHƯƠNG PHÁP ANT-Q Trong tình huống khi mà trong môi trường có nhiều agent cùng học một lúc (multi-agent environment) thì việc kết hợp, chuyển giao các kinh nghiệm đã được học giữa các agent được thực hiện nhờ thuật toán đàn kiến (Ant System - AS). Thuật toán đàn kiến được phát minh ra dựa trên việc quan sát hoạt động của đàn kiến. Quá trình hoạt động tìm đường của đàn kiến được mô tả như sau: Tất cả mọi con kiến hầu như là mù, chúng chỉ có thể tương tác với nhau và với môi trường bằng cách sử dụng pheromone: đi đến đâu chúng xịt pheromone ra đến đấy. Mỗi một con kiến CT 2 tại mỗi vị trí quyết định hướng đi tiếp theo dựa vào nồng độ pheromone của các hướng. Tại vị trí mà nồng độ pheromone xung quanh đều bằng nhau hoặc không có pheromone thì chúng sẽ quyết định hướng đi một cách ngẫu nhiên. Cứ như vậy thì các con kiến cứ đi theo bước chân của nhau và tạo thành một đường đi (path). Ta xét trường hợp tổ kiến ở vị trí 1 và nguồn thức ăn ở vị trí 2 như hình vẽ 3: Hình 3. Giả sử tại thời điểm ban đầu có 2 con kiến ra đi tìm thức ăn. Vì ban đầu chưa có pheromone nên chúng chọn 2 hướng đi khác nhau một cách ngẫu nhiên. Một hướng có đường đi đến nguồn thức ăn dài hơn hướng kia. Trong giai đoạn đầu các con kiến đi sau sẽ cảm nhận thấy nồng độ pheromone của cả 2 hướng là như nhau nên cũng chọn đi theo một trong 2 hướng một cách ngẫu nhiên. Tuy nhiên đường đi ngắn hơn làm cho khoảng thời gian di chuyển từ tổ đến nguồn thức ăn rồi quay trở lại của mỗi con kiến theo con đường đó cũng ngắn hơn và do đó mật độ di chuyển qua lại của đàn kiến tại mỗi vị trí của con đường ngắn sẽ cao hơn con đường dài.
Do mật độ qua lại lớn hơn dẫn đến kết quả là nồng độ pheromone trên con đường ngắn càng ngày càng cao hơn con đường dài. Kết quả cuối cùng là đàn kiến ngày càng từ bỏ con đường dài và đi theo con dường ngắn. Đến một lúc nào đó sẽ không còn con kiến nào đi theo con đường dài nữa mà tất cả đều đi theo con đường ngắn. Thuật toán dựa trên hoạt động của đàn kiến có một số biến thể. Dạng đơn giản nhất gọi là AS (Ant System). Thuật toán này chỉ dùng để giải quyết bài toán tìm đường. Ở mức cao hơn là thuật toán ACO (Ant Colony Optimization). Thuật toán này cho phép các agent trương tác với nhau để điều chỉnh hướng đi. Thuật toán ACO kết hợp với thuật toán Q-learning được gọi là Ant-Q. Nội dung chi tiết về các thuật toán sẽ được trình bày ở các phần kế tiếp. 5.1. AS Thuật toán này rất đơn giản. Mỗi agent được trang bị một buffer. Các agent được khởi động đi tìm đường một cách ngẫu nhiên bắt đầu ở vị trí xuất phát. Các vị trí mà agent đi qua được lưu vào buffer. Khi mà đường đi của agent nào đó đã vượt quá độ dài cho phép thì dù cho agent chưa đến được đích cũng bị “bay hơi” giữa chừng. Các agent đến được đích sẽ được kiểm tra buffer để xác định đường đi ngắn nhất. 5.2. ACO Thuật toán này có sử dụng đến yếu tố pheromone. Với một agent k nào đó tại vị trí I, agent chọn đi tới vị trí j liền kề với i theo xác suất sau: CT 2 Trong đó: η ij là giá trị heuristic cho bài toán. Với bài toán TSP (Trade Salesman Problem) thì η ij = 1/d ij với d ij là khoảng cách giữa 2 thành phố i và j. N ik là tập các vị trí lân cận của i mà agent k có thể đến được. τ ij là nồng độ pheromone trên đường đi từ i đến j. α, β là các giá trị chỉ thị mức độ quan trọng của τ và η. Giá trị của nồng độ pheromone cũng được điều chỉnh sau từng bước, bao gồm mức giảm trên tuyến đường theo thời gian với hằng số tỷ lệ ρ và mức tăng pheromone Δτ ij do agent k xịt ra. Nồng độ pheromone được giảm như sau: Tăng như sau: = v ới =
Với L k là “cost of solution” cho agent k, là một giá trị xác định mức độ “quan trọng” của agent k trong hệ thống multi-agent. Kết quả là: 5.3. Ant-Q Phương pháp này cũng tương tự như ACO nhưng có khác ở cách điều chỉnh nồng độ pheromone. Quy luật điều chỉnh này được lấy từ phương pháp Q-learning: Trong đó i là vị trí kề cận với j. Như vậy là bằng việc kết hợp với phương pháp Q-learning đã làm cho phương pháp ACO trở nên hiệu quả hơn và kết quả học của các agent được thể hiện qua nồng độ pheromone trên từng vị trí. VI. KẾT LUẬN Sử dụng phương pháp học tăng cường hiệu quả hơn sử dụng các phương pháp tìm đường cổ điển trong việc giải quyết bài toán tìm đường do đòi hỏi ít điều kiện ràng buộc hơn (môi trường không nhất thiết phải xác định, cố định, v.v …). Ngoài ra bằng cách áp dụng học tăng cường ta có thể xử lý được nhiều tình huống ví dụ như như là giúp agent tránh được các vị trí CT 2 “nguy hiểm” như “rơi xuống hố” hay “ngã xuống từ vách đá” từ nhiều bước trước đó - và những vấn đề mà các phương pháp tìm đường cổ điển không xử lý được. Q-learning là phương pháp học tăng cường rất hiệu quả trong việc giải quyết bài toán tìm đường. Nguyên nhân là do phương pháp này được thực hiện theo kiểu off-policy, có nghĩa là áp dụng một luật hành động để học và lại tối ưu hóa cho luật hành động khác. Do Q-learning hiệu quả trong việc giải quyết bài toán tìm đường nên phương pháp này được điều chỉnh hoặc kết hợp với một số phương pháp khác để giải quyết các bài toán đặc biệt như tìm đường trong mạng (Q-routing) hay tìm đường của hệ thống multi-agent (Ant-Q). Tài liệu tham khảo [1]. Reinforcement Learning: Theory and Application, I-TECH Education and Publishing, 2008. [2]. Reinforcement Learning: An Introduction, Richard S. Sutton, The MIT Press, 1998. [3]. Artificial Intelligence - A Modern Approach, Stuart Russel, Pearson Education Inc. 2003. [4]. Reinforcement Learning By Policy Search, PhD Dissertation, Leonid Peskin, 2002. [5]. Học tăng cường và quyết định Markov, luận văn thạc sĩ, Châu Mạnh Quang, 2009. [6]. Technical report: Comparison of the Q-Routing and Shortest Path Routing Algorithms. F. Tekiner, Z. Ghassemlooy and T.R. Srikanth♦