- Trang Chủ
- Luận Văn - Báo Cáo
- 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
Xem mẫu
- 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♦
nguon tai.lieu . vn
