tinrobotics / teachingCác học phần ↗

LẬP LỘ TRÌNH DI CHUYỂN · ĐẠI HỌC

Mô phỏng thuật toán
lập lộ trình di chuyển.

Từ A* và Dijkstra trên lưới đến RRT, RRT* và PRM trong không gian liên tục. Hãy tự đặt vật cản, chạy từng bước và xem mỗi thuật toán tạo đường đi ra sao.

5 THUẬT TOÁN · 2 CÁCH TIẾP CẬN

Đường nào ngắn hơn?
Thuật toán xây đường ra sao?

Cách đọc kết quả ↓
Chỉnh bản đồ

Nhấn hoặc kéo trên một bản đồ; bản đồ bên cạnh sẽ đổi theo. Dùng phím mũi tên để chọn ô, Enter để đặt. Mỗi lần sửa sẽ bắt đầu lại phép so sánh.

Sẵn sàng. Hai thuật toán dùng cùng một bản đồ.
CÓ HEURISTIC

A*

f(n) = g(n) + h(n)

Bản đồ A*: kết quả được ghi ở bên dưới.
Ô đã xét
0
Đang chờ
1
Chi phí đường
—
Số cạnh
—

Chưa lấy ô nào ra khỏi hàng đợi.

KHÔNG HEURISTIC

Dijkstra

f(n) = g(n)

Bản đồ Dijkstra: kết quả được ghi ở bên dưới.
Ô đã xét
0
Đang chờ
1
Chi phí đường
—
Số cạnh
—

Chưa lấy ô nào ra khỏi hàng đợi.

Vật cảnĐã xétĐang chờVừa chọnĐường tìm đượcS Điểm đầuG Điểm đích

Thử đoán trước: A* có cần xét hết vùng quanh điểm đầu không?

Xem hàng đợi và chi phí từng ô

Chọn một ô trên bản đồ bằng phím mũi tên để đọc chi phí.

A* · 5 ô có ưu tiên cao nhất

    Dijkstra · 5 ô có ưu tiên cao nhất

      Các ô có cùng mức ưu tiên được xử lý theo thứ tự đưa vào hàng đợi. Danh sách ở đây sắp thêm theo tọa độ để dễ đọc; đường tối ưu có thể không duy nhất.

      ĐỌC KẾT QUẢ

      Ít ô hơn chưa có nghĩa
      là đường ngắn hơn.

      Một bước ngang hoặc dọc có chi phí 10; một bước chéo có chi phí 14. Chi phí đường là tổng các bước, nên hai đường có số cạnh khác nhau vẫn có thể có cùng chi phí. Đây là đơn vị quy ước của lưới, chưa quy đổi ra mét hay năng lượng.

      “Ô đã xét” là số ô được lấy ra khỏi hàng đợi để xử lý, kể cả ô đích. “Đang chờ” là số ô đã được tìm thấy nhưng chưa xử lý. Mỗi lần bấm “Tiến một bước”, mỗi thuật toán còn chạy sẽ lấy ra một ô.

      Vì sao A* vẫn tìm được đường tối ưu?

      g(n) là chi phí tốt nhất hiện biết từ S đến ô n; h(n) là ước lượng chi phí còn lại đến G. A* ưu tiên ô có tổng f nhỏ nhất, còn Dijkstra chỉ dùng g để xếp thứ tự.

      Với 4 hướng, A* dùng khoảng cách Manhattan: h = 10(Δx + Δy). Với 8 hướng, A* dùng khoảng cách octile: h = 14 min(Δx, Δy) + 10|Δx − Δy|.

      Ở đây, Δx và Δy là độ chênh lệch tuyệt đối về cột và hàng giữa ô đang xét với đích.

      Hai ước lượng này không vượt chi phí ngắn nhất còn lại và nhất quán với chi phí cạnh đang dùng. A* và Dijkstra vì thế phải tìm được cùng chi phí tối ưu nếu có đường, dù có thể chọn những đường khác nhau.

      Đường chéo chỉ được phép khi cả hai ô kề cạnh đều trống. Quy tắc này tránh đi xuyên qua góc vật cản.

      Ba thử nghiệm trên lớp

      1. Đường trống. Chạy trên bản đồ trống, ghi chi phí và số ô đã xét của mỗi thuật toán. Vì sao hai kết quả chi phí bằng nhau?
      2. Đích ở sau bức vách. Chọn “Một cửa hẹp”, rồi tự chuyển điểm đích. Khi phải đi vòng, ước lượng đến đích còn giúp được bao nhiêu?
      3. Không có đường. Chọn “Vách ngăn kín”. Trước khi chạy, dự đoán thuật toán nào sẽ dừng trước. Hãy kiểm tra xem cả hai có phải xét toàn bộ vùng đi tới được từ S không.

      Ghi lại bản đồ, cách di chuyển, chi phí và số ô đã xét. Hãy so sánh trên cùng cấu hình; tốc độ hoạt ảnh chỉ giúp theo dõi, không phải phép đo thời gian tính toán.