Path Planning — Hoạch định đường đi
Chạy tìm kiếm theo chiều rộng thật trên bản đồ bạn gõ vào và vẽ lại đường đi tìm được. Sửa vật cản rồi chạy lại để thấy đường đổi theo.
Sóng lan đều ra mọi hướng vì BFS không biết đích ở đâu — nó chạm 45 ô để tìm đường 31 bước. A* dùng heuristic hướng về đích chính là để cắt phần lớn diện tích này.
Phần chênh là cái giá của vật cản. Bằng 0 nghĩa là có đường đi hoàn toàn theo bậc thang thẳng tới đích và bản đồ gần như không cản trở gì.
Tỷ lệ 1.5 ô duyệt trên mỗi bước đường đi. BFS đảm bảo tối ưu nhưng trả giá bằng việc quét đều mọi hướng; đó là lý do bản đồ lớn cần A* hoặc Dijkstra có hàng đợi ưu tiên.
Mật độ vật cản càng cao thì đường đi càng dễ bị ép sát tường. Bản đồ thật cần nới rộng vật cản thêm bán kính robot trước khi chạy tìm đường, nếu không đường tìm được sẽ không đi lọt.
BFS ở đây dùng 4 hướng nên đường chéo phải đi thành bậc thang. Cho phép 8 hướng rút ngắn đường nhưng phải đổi chi phí bước chéo thành √2, nếu không kết quả không còn là đường ngắn nhất thật.
| Kích thước lưới | 10 × 7 |
| Số ô vật cản | 25 |
| Thuật toán | Breadth-first search, 4-connectivity |
| Đường đi | S......... •####.###. •••••#•••# ####•#•#•. •••••#•#•# •#####•#•• •••••••#.E |
Sóng lan đều ra mọi hướng vì BFS không biết đích ở đâu — nó chạm 45 ô để tìm đường 31 bước. A* dùng heuristic hướng về đích chính là để cắt phần lớn diện tích này.
Trên tổng 70 ô của lưới 10 × 7. Phần chưa duyệt là công sức tiết kiệm được do tìm thấy đích trước khi phải quét hết.
| Đoạn | Hướng | Số bước | Tới ô (cột, hàng) |
|---|---|---|---|
| 1 | xuống | 2 | (0, 2) |
| 2 | sang phải | 4 | (4, 2) |
| 3 | xuống | 2 | (4, 4) |
| 4 | sang trái | 4 | (0, 4) |
| 5 | xuống | 2 | (0, 6) |
| 6 | sang phải | 6 | (6, 6) |
| 7 | lên | 4 | (6, 2) |
| 8 | sang phải | 2 | (8, 2) |
| 9 | xuống | 3 | (8, 5) |
| 10 | sang phải | 1 | (9, 5) |
| 11 | xuống | 1 | (9, 6) |
| Kích thước lưới | 10 × 7 |
| Số ô vật cản | 25 |
| Thuật toán | Breadth-first search, 4-connectivity |
| Đường đi | S......... •####.###. •••••#•••# ####•#•#•. •••••#•#•# •#####•#•• •••••••#.E |
BFS 4-connectivity — cho đường ngắn nhất theo số ô
Đây là công thức thật mà mã nguồn chạy, không phải mô tả gần đúng.
API tại /api/v1/tools/grid-path gọi đúng hàm
này, nên kết quả trên trang và qua API không thể lệch nhau.
1.234.567 lẫn 1.234,56.Lập kế hoạch đường đi tìm lộ trình từ điểm đầu tới đích tránh vật cản. Bài toán chia hai lớp: thuật toán trên lưới (A*, Dijkstra) cho không gian rời rạc, và thuật toán lấy mẫu (RRT*, PRM) cho không gian nhiều chiều.
| Độ dài đường đi | so với đường tối ưu |
| Thời gian tính | phải nhỏ hơn chu kỳ điều khiển |
| Khoảng cách an toàn tới vật cản | ràng buộc an toàn |
Phần quan trọng nhất của trang này. Một phương pháp được mô tả mà không nói chỗ nó hỏng là phiên bản quảng cáo của phương pháp đó.
Chưa có mô hình nào gắn riêng cho chủ đề này. Đây là những mô hình của cả ngành — liên quan ở cấp ngành, không phải cấp chủ đề.
Lập kế hoạch đường đi tìm lộ trình từ điểm đầu tới đích tránh vật cản. Bài toán chia hai lớp: thuật toán trên lưới (A*, Dijkstra) cho không gian rời rạc, và thuật toán lấy mẫu (RRT*, PRM) cho không gian nhiều chiều.
1. Biểu diễn không gian: lưới chiếm dụng hoặc đồ thị. 2. Chọn thuật toán theo số chiều — A* không khả thi khi số chiều lớn. 3. Làm mượt đường đi sau khi tìm được để robot chạy êm. 4. Lập lại kế hoạch khi phát hiện vật cản mới (D* Lite).
Đường tối ưu về độ dài thường sát vật cản; cần phạt khoảng cách an toàn trong hàm chi phí. RRT* hội tụ về tối ưu nhưng rất chậm; trong thực tế thường dừng sớm và chấp nhận gần tối ưu.
Độ dài đường đi — so với đường tối ưu; Thời gian tính — phải nhỏ hơn chu kỳ điều khiển; Khoảng cách an toàn tới vật cản — ràng buộc an toàn.
Chưa xây dựng. Mục này hiện là điều hướng và tài liệu tham chiếu; chúng tôi không gắn nhãn 'live' cho thứ chưa chạy.