Q Learning with practical demo of rocket landing

💡

Q-Learning là một thuật toán học tăng cường (Reinforcement Learning) cơ bản mà ai cũng từng phải tìm hiểu qua khi bắt đầu học đến Machine Learning. Thông thường, khi học đến Q-Learning, thầy hay đưa ra một ví dụ để mô tả là một con robot tự tìm đường đến mục tiêu trong bảng vuông. Vấn đề là, ví dụ ấy tuy dễ hiểu trong giảng dạy nhưng lại khá mơ hồ trong ứng dụng thực tế cho thuật toán. Mình đã từng tự hỏi: “Ủa, tại sao không áp dụng các thuật toán tìm đường ngắn nhất cho con robot mà lại dùng Q-Learning?“. Trong bài viết này mình, bên cạnh việc giới thiệu với các bạn kỹ thuật này, mình sẽ áp dụng Q-Learning để giải quyết bài toán hạ cánh tàu vũ trụ, hy vọng sẽ gần gũi và trực quan hơn với các bạn.

Q-Learning là gì?

Q-Learning là một thuật toán học tăng cường (Reinforcement Learning) cho phép một agent học cách tương tác với một môi trường để tối đa lợi ích (reward). Không như học có giám sát (supervised learning), Q-Learning không cần dữ liệu đã gán nhãn. Thay vào đó, agent tự tìm tòi, tương tác với môi trường để nhận lại các phản hồi từ môi trường và dần dần học được cách hành động tối ưu.

💡

Nói một cách nôm na dễ hiểu, huấn luyện bằng Q-Learning cũng hơi giống huấn luyện một chú cún vậy. Mỗi lần bạn giơ tay lên, chú cún ngồi xuống, bạn thưởng cho cún một viên kẹo. Lâu dần, chú cún của bạn sẽ học được thói quen rằng mỗi lần bạn giơ tay lên, chú sẽ ngồi xuống.

Nguyên lý hoạt động

Để huấn luyện một agent trong Q-Learning, bạn phải sẽ quan tâm đến các thành phần:

Trạng thái hiện tại $s$ của môi trường
Hành động $a$ mà agent đã tương tác với môi trường hiện tại
Phần thưởng nhận được $r$
Trạng thái mới $s'$ của môi trường

Trong quá trình học, một bảng Q-Table được xây dựng dùng để lưu lại giá trị phần thưởng đạt được ứng với các hành động $a$ trong môi trường $s$ cụ thể nhằm làm cơ sở để cải thiện hành động sau để mang lại kết quả tối ưu hơn. Tóm lại, nó như cuốn sổ tay để mỗi khi agent gặp một tình huống nào đó, nó dựa vào các ghi chép kinh nghiệm, ở đây là các giá trị $Q(s,a)$, mà chọn ra phương án tối ưu cho tình huống ấy. Ví dụ, khi huấn luyện tàu vũ trụ hạ cánh (trong demo bên dưới), đối với trạng thái (state) tại vị trí $x,y$ và vận tốc hiện tại là $v_x, v_y$ có 4 hành động (action) mà tàu vũ trụ có thể làm: NONE, UP, LEFT, RIGHT. Ứng với 4 hành động ấy là 4 điểm số đánh giá mức độ thuận lợi (reward). Máy tính sẽ có xu hướng chọn hành động thuận lợi nhất.

Công thức huấn luyện cũng được xây dựng dựa trên tinh thần đó như sau:

$$Q(s,a) = Q(s,a) + \alpha[r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$$

Trong đó:

$s,a$ - lần lượt là trạng thái và hành động đã chọn
$s'$ - là trạng thái mới sau trạng thái $s$ sau khi chọn tương tác bằng hành động $a$
$a'$ - hành động tối ưu tại trạng thái mới (Có giá trị $Q$ cao nhất)
$r$ - là phần thưởng nhận được
$\alpha$ - tốc độ học (learning rate)
$\gamma$ - mức độ quan tâm đến tương lai (discount factor)

Learning rate $\alpha$ quyết định mức độ mà giá trị $Q$ hiện tại được cập nhật dựa trên kinh nghiệm mới. Giá trị $\alpha$ nằm trong khoảng $0 \to 1$:

$\alpha = 1$: $Q(s,a)$ sẽ bị triệt tiêu, lúc này quá trình huấn luyện chỉ tin vào kinh nghiệm mới
$\alpha = 1$: ngược lại, $Q(s,a)$ sẽ không đổi, không học gì mới

💡

Một learning rate phù hợp giúp mô hình học ổn định mà không quá dao động.

Discount factor quyết định mức độ agent quan tâm đến phần thưởng trong tương lai, nghĩa là:

$\gamma = 0$: lúc này phần tối ưu $\displaystyle \max_{a'}Q(s',a')$ sẽ bị triệt tiêu, agent chỉ quan tâm đến phần thưởng mà không quan tâm đến hành động các trạng thái mới
$\gamma \approx 1$: ngược lại, agent sẽ quan tâm đến phần thưởng lấy được trong các hành động trong tương lai

Thuật toán

Khởi tạo Q-Table với tất cả các trạng thái và hành động có giá trị ban đầu là $0$
Lặp lại mỗi lần huấn luyện (episode):
- Đặt agent ở trạng thái bắt đầu
- Lặp lại cho đến khi kết thúc lần huấn luyện:
  - Chọn hành động $a$ từ trạng thái hiện tại $s$
  - Thực hiện hành động, quan sát phần thưởng $r$ và trạng thái mới $s'$
  - Cập nhật giá trị $Q$: $ Q(s,a) = Q(s,a) + \alpha[r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$
  - Cập nhật trạng thái hiện tại $s \leftarrow s'$
Kết thúc khi Q-Table hội tụ hoặc sau số vòng lặp nhất định

Ví dụ minh họa

Trong bản đồ trên, robot có thể di chuyển theo 4 hướng: lên, xuống, trái, phải. Mục tiêu của robot là đi từ vị trí bắt đầu $(0,0)$ đến ô lá cờ $(4, 4)$, tránh các chướng ngại vật là các ô có bomb.

Chúng ta sẽ dùng Q-Learning để huấn luyện robot tự động dò đường để đi đến lá cờ.

Đầu tiên, chúng ta thiết lập phần thưởng như sau:

Mỗi bước đi sẽ nhận phần thưởng là $-1$. Thực chất đây là hình phạt thì đúng hơn 😛 nhằm tránh việc robot tối ưu phần thưởng bằng cách cứ đi qua đi lại mà không chịu bò tới đích.
Nếu đâm và bomb thì sẽ nhận thưởng $-10$ (một hình phạt khác 😁)
Nếu đến được đích thì sẽ nhận phần thưởng $100$

💡

Chú ý rằng, đây không phải là bài toán tìm đường đi ngắn nhất mà trong đó thông tin về bản đồ đã được cung cấp từ trước. Thay vào đó, robot không hề biết gì về thông tin bản đồ, các vị trí có bomb mà chỉ thực hiện dò từng bước và ghi lại các kết quả trải nghiệm (reward) thông qua các thông tin về các bước đi ở mỗi vị trí.

Các hành động (action) có thể được chọn tại mỗi vị trí là: LÊN, XUỐNG, PHẢI, TRÁI.

Q-Table là một mảng hai chiều có dạng [vị trí][hành động] trả về giá trị số đại diện cho một hành động diễn ra tại một vị trí $(x,y)$ cụ thể trên bản đồ. Như vậy, một cách ước lượng thì bảng Q-Table sẽ có khoảng $m \times n \times 4$ phần tử, với $m,n$ lần lượt là chiều dài và chiều rộng của bản đồ.

Để giúp cho robot có khả năng lâu lâu thử nghiệm một hành động mới đối với một trạng thái đã biết mà không sa vào thói quen, mình có thể áp dụng chiến lược epsilon-greedy bằng cách thiết lập một tỷ lệ epsilon nhỏ $\varepsilon$, robot sẽ thực hiện một hành động ngẫu nhiên mà không lựa chọn theo tối ưu đã biết trước đó.

// Chọn hành động theo chính sách epsilon-greedy
function chooseAction(state) {
  if (random() < epsilon) {
    return floor(random(actions.length)); // Chọn ngẫu nhiên để khám phá
  }
  return qTable[state].indexOf(max(qTable[state])); // Chọn hành động tốt nhất
}

Demo Robot tìm đường

Tại mỗi ô, các giá trị cuả Q-Value nằm ở các góc tương ứng.

Ứng dụng Q-Learning - Nhiệm vụ hạ cánh tàu vũ trụ

Trong ứng dụng này, mình sẽ dùng Q-Learning để cố gắng hạ cánh tàu vũ trụ trong điều kiện có trọng lực kéo xuống, và có gió ngẫu nhiên đẩy tàu văng sang trái hoặc sang phải. Tàu có các động cơ đẩy: TRÁI, PHẢI, LÊN. Tàu hạ cánh thành công nếu:

Hạ cánh vào vùng quy định
Vận tốc tiếp đất bao gồm vận tốc hướng xuống và vận tốc hướng ngang phải bé hơn các giá trị cho trước.

Mô tả hàm thưởng getReward():

Hạ cánh thành công: đúng chỗ và trong giới hạn vận tốc cho phép, thưởng $+100,000$
Bay ra khỏ biên màn hình: phạt $-50,000$
Bay càng xa khỏi khu vực hạ cánh phạt càng nặng
Vận tốc phải giảm dần khi càng gần mặt đất, nếu không phạt nặng
Thời gian bay càng lâu, phạt càng nặng

function getReward(t = 0) {
    const maxDistance = width / 2; // Khoảng cách tối đa từ tâm đến biên
    const epsilon = 0.1; // Hằng số nhỏ tránh chia cho 0

    // kiểm tra nếu tàu đã hạ cánh thành công
    if (lander.y + lander.size / 2 >= groundY) {
        landed = true; // Đánh dấu là đã hạ cánh
        let inZone = lander.x > landingZone.x && lander.x < landingZone.x + landingZone.w;
        if (inZone && Math.abs(lander.vy) < safeVy && Math.abs(lander.vx) < safeVx) {
            return 100000; // Phần thưởng lớn khi hạ cánh thành công trong vùng hạ cánh
        } else {
            return -5000; // Phạt lớn khi hạ cánh không thành công
        }
    }

    // kiểm tra nếu tàu ra ngoài biên
    if (lander.x < 0 || lander.x > width || lander.y < 0) {
        return -50000; // Va chạm với biên
    }

    // Khi đang bay
    let reward = 0;

    // Khoảng cách đến trung tâm vùng hạ cánh
    let distanceToLandingZone = Math.abs(lander.x - (landingZone.x + landingZone.w / 2));
    reward += -distanceToLandingZone / maxDistance; // Chuẩn hóa khoảng cách

    // Phạt vận tốc, tăng mạnh khi gần mặt đất
    let distanceToGround = Math.abs(lander.y - groundY);
    let totalVelocity = Math.abs(lander.vx) + Math.abs(lander.vy);
    reward += -totalVelocity / (Math.sqrt(distanceToGround) + epsilon);

    // Phạt thời gian
    reward += -t; // Tăng hình phạt thời gian

    return reward;
}

Ở phần trạng thái, chúng ta sẽ dùng 4 thông số:

$x,y$ - vị trí tàu vũ trụ hiện tại
$v_x,v_y$ - tốc độ theo phương ngang và phương đứng

Tuy nhiên vì đây là các số thực, dễ làm bùng nổ tổ hợp trạng thái cho Q-Table nên mình đã phân cụm hóa không gian trạng thái bằng cách:

Rời rạc hóa vận tốc:
- $-1$ nếu $v < -v_{\text{safe}}$
- $0$ nếu $-v_{\text{safe}} < v < v < v_{\text{safe}}$
- $1$ nếu $v > v_{\text{safe}}$
Rời rạc hóa vùng không gian thành $m$ phần ngang và $n $ phần dọc

Source code:

/ Rời rạc hóa trạng thái để dùng làm key cho Q-table
function getState() {
    // Rời rạc hóa vị trí (ví dụ: chia thành 6x6 grid)
    let xState = constrain(floor(lander.x / (width / nWidthParts)), 0, nWidthParts - 1);
    let yState = constrain(floor(lander.y / (height / nHeightParts)), 0, nHeightParts - 1);

    // Rời rạc hóa vận tốc (ví dụ: chia thành các khoảng)
    let vxThreshold = 1.0;
    let vyThreshold = 1.5;
    let vxState = 0;
    if (lander.vx > vxThreshold) vxState = 1;
    else if (lander.vx < -vxThreshold) vxState = -1;

    let vyState = 0;
    if (lander.vy > vyThreshold) vyState = 1;
    else if (lander.vy < -vyThreshold) vyState = -1; // Có thể thêm nhiều mức hơn

    // Kết hợp thành chuỗi trạng thái
    return `${xState},${yState},${vxState},${vyState}`;
}

Ngoài ra, cấu trúc chương trình cũng tương tự như của Demo Robot.

Train tới khoảng lần thứ 200 thì bắt đầu hạ cánh ổn hơn. Các bạn kiên nhẫn chờ nhé 😝

Q-Learning - Nhiệm vụ hạ cánh tàu vũ trụ