Thực hành Chương 3: Tìm kiếm và cải thiện đường
Lập lộ trình di chuyển – Đại học Nguyễn Tất Thành. Gói chạy ngoại tuyến, dùng cùng mô hình và dữ liệu với bài giảng.
Dijkstra và A* trên cùng một đồ thị
Trước khi chạy, dự đoán cách thuật toán mở rộng vùng tìm kiếm. Robot đĩa có bán kính 0,45 m cộng biên 0,15 m. Điểm đầu S=(2,6), đích G=(18,6), miền 20 m × 12 m.
Đã mở rộngĐang chờ hoặc đường kết quảĐỉnh hiện tại
Lượt mở rộng tính cả lần lấy đích ra bằng mục còn hiệu lực. Mục cũ bị bỏ qua không được tính. Khi hòa khóa, ưu tiên h nhỏ hơn rồi thứ tự chèn. Dijkstra luôn dùng h=0.
Cạnh chéo cần cả hai nút trung gian ngang và dọc tự do, đồng thời toàn đoạn phải qua bộ kiểm hình học. Chi phí tối ưu được hiểu trên đồ thị đã xây.
Thay đổi mức đánh đổi với rủi ro
Đây là trường xác suất minh họa, không có vật cản cứng ở giữa. Các nút trong dải giữa có p=0,12, các nút còn lại p=0,005. Ta giả sử các biến cố ở những nút khác nhau độc lập.
J = L + λR, R = −Σ ln(1−pi), P(có nút bị chiếm) = 1−Π(1−pi)
Các xác suất này thuộc mô hình nút độc lập của bài học. Chúng chưa biểu diễn xác suất va chạm thật của toàn thân robot.
Chi phí R cộng ở các nút đến sau điểm đầu. Xác suất toàn đường tính cả nút đầu. Khoản đầu này giống nhau cho mọi đường nên không đổi thứ tự tối ưu.
Nếu cùng một ô tĩnh được đi lại nhiều lần, không được nhân như các biến cố độc lập mới. Tương quan và sai số vị trí cần mô hình riêng.
RRT và RRT*: cùng mẫu, khác liên kết cha
Cả hai cách chạy tiếp tục tới hết ngân sách và giữ đường tốt nhất. Bước mở rộng 2 m, goal bias 0,05, bán kính hiệu dụng 0,60 m. RRT* dùng rn=min(2,24√(ln n/n)) m và cập nhật chi phí cả cây con khi nối lại.
Hình động hiện các ảnh chụp trạng thái thật ở mốc 50, 100, 200, 300, 600, 1200 nếu có. Nó không dựng lại quá khứ từ các cha cuối cùng.
Cùng số vòng chưa là cùng số lần kiểm cạnh hoặc thời gian chạy. Trước lời giải đầu, đồ thị để trống phần chi phí. Chưa có đường trong ngân sách không được gán độ dài bằng 0.
Đây là demo hình học, chưa phải triển khai ROS 2, OMPL hoặc kiểm thử phần cứng. Không suy ra tối ưu liên tục từ một ngân sách hữu hạn.
Ưu tiên cạnh trong một batch minh họa
Mốc lời giải đang giữ là cbest=18,5. Khóa qua cạnh dùng nhãn tiền tố hiện tại và các cận ước lượng. Hãy dự đoán quyết định trước mỗi lần bấm.
key(u,v) = gT(u) + ĉ(u,v) + ĥ(v)
Đây là mô phỏng ba cạnh để học cơ chế. Nó chưa triển khai BIT* đầy đủ với nhiều batch, cập nhật hàng đợi và cắt tỉa.
Khi nhãn cây thay đổi, khả năng cải thiện của một cạnh có thể thay đổi. Nhận một cạnh cũng chưa có nghĩa đã tìm được đường đầy đủ tới đích. Bài mở rộng dùng triển khai BIT* của OMPL.