Khi làm việc với robot trong không gian có vật cản, người ta thường gặp phải một vấn đề cơ bản: tìm đường tối ưu là bài toán NP-hard. Điều này không có nghĩa là không giải được, mà là không có thuật toán nào đảm bảo tìm ra lời giải tối ưu trong thời gian đa thức. Bài viết này khám phá tại sao lập kế hoạch chuyển động lại khó, những giới hạn thực tế của tính toán, và cách các nhóm làm robot hiện nay xoay xở với những ràng buộc đó để robot hoạt động được.
Tại sao lập kế hoạch chuyển động là bài toán khó
Không gian tìm kiếm lớn theo hàm mũ. Khi số chiều tăng (robot có nhiều khớp hơn), số trạng thái có thể có tăng lên theo hàm mũ. Một robot 7 khớp với mỗi khớp chia thành 100 vị trí rời rạc sẽ có 100^7 trạng thái khả thi để kiểm tra.
Kiểm tra va chạm tốn kém. Xác định xem một cấu hình có va chạm với vật cản hay không đòi hỏi tính toán hình học phức tạp, đặc biệt với các hình dạng tùy ý. Mỗi kiểm tra có thể tốn vài miligiây.
Đường dẫn phải liên tục và mịn. Không chỉ tìm được một chuỗi cấu hình không va chạm là đủ; đường dẫn phải liên tục (không nhảy cóc), và trong thực tế cần mịn để tránh tăng tốc đột ngột trên robot.
Nhiều tiêu chí tối ưu cùng lúc. Có thể cần cực tiểu hóa độ dài đường dẫn, thời gian thực thi, lượng năng lượng tiêu thụ, hoặc độ gập gềnh. Những tiêu chí này thường xung đột với nhau.
Các cấu hình thế nằm gần nhau. Trong không gian cấu hình, hai điểm gần nhau trong khoảng cách Euclid có thể tách biệt bởi một vùng có vật cản hẹp. Điều này làm cho phương pháp tìm kiếm local dễ kẹt.
Không có cấu trúc toàn cầu. Không gian cấu hình không có cấu trúc đặc biệt mà ta có thể khai thác; nó phụ thuộc hoàn toàn vào hình dạng và vị trí vật cản.
Chứng minh tính không-khả-thi cũng khó. Khi không tìm được đường dẫn, làm sao biết đó là vì bài toán thực sự không có lời giải hay vì ta chưa tìm đủ lâu?
Yêu cầu thời gian thực trong nhiều ứng dụng. Một robot xây dựng hoặc tháo gỡ cần lập kế hoạch trong vòng vài giây, không phải vài phút. Điều này buộc phải hy sinh chất lượng tối ưu lấy tính khả thi về thời gian.
Chuyển đổi giữa lập kế hoạch toàn cầu và phản ứng địa phương. Một kế hoạch tốt toàn cầu có thể không còn hợp lệ khi môi trường thay đổi hoặc cảm biến phát hiện vật cản chưa biết.
Độ phức tạp không chỉ lý thuyết mà còn thực tế. Ngay cả những thuật toán lý thuyết dễ hơn (như RRT) cũng có hằng số ẩn lớn và hiệu suất phụ thuộc mạnh vào tham số.
Các lớp độ phức tạp và ý nghĩa thực tế
P: những bài toán giải được nhanh. Nếu lập kế hoạch chuyển động nằm trong lớp P, sẽ tồn tại thuật toán chạy trong thời gian đa thức với kích thước đầu vào. Nhưng hầu hết các biến thể lập kế hoạch không nằm lớp P.
NP: những bài toán kiểm chứng nhanh nhưng giải khó. Cho một đường dẫn được đề xuất, có thể kiểm chứng nó hợp lệ trong thời gian đa thức (kiểm tra từng điểm trên đường có va chạm không). Nhưng tìm ra đường dẫn đó là khó.
NP-hard: những bài toán ít nhất là khó bằng bài toán khó nhất trong NP. Lập kế hoạch chuyển động với vật cản nhiều chiều là NP-hard. Điều này có nghĩa là nếu ta tìm được thuật toán đa thức cho nó, ta sẽ giải được P = NP, một trong những bài toán lớn nhất trong khoa học máy tính.
PSPACE-hard: thậm chí còn khó hơn NP-hard. Một số biến thể của lập kế hoạch chuyển động (như lập kế hoạch với tính không chắc chắn về cảm biến) nằm trong PSPACE-hard, tức là không chỉ cần thời gian hàm mũ mà còn cần bộ nhớ hàm mũ.
Ý nghĩa thực tế của NP-hard. Nó không nói rằng không thể giải được; nó nói rằng không có cách nào chạy nhanh trên mọi trường hợp. Nhưng trên các trường hợp cụ thể, hoặc với heuristic tốt, có thể giải rất nhanh.
Thuật toán xấp xỉ và heuristic là con đường duy nhất. Thay vì tìm lời giải tối ưu, ta tìm lời giải tốt trong thời gian hợp lý. Lời giải này có thể kém tối ưu 10-20%, nhưng nó khả thi.
Trade-off giữa chất lượng và thời gian là không tránh khỏi. Cho một ngân sách thời gian cố định, có thể thiết lập các tham số thuật toán để tìm được lời giải chấp nhận được trong thời hạn đó.
Các trường hợp đặc biệt dễ hơn. Nếu robot có ít chiều (2-3), hoặc vật cản có cấu trúc (như lưới), hoặc mục tiêu không cần tối ưu quá, thời gian tính toán giảm đáng kể.
Thực tế công nghiệp không đợi chứng minh lý thuyết. Các nhóm làm robot chọn thuật toán dựa vào kết quả thực nghiệm, không phải lý thuyết độ phức tạp. Một heuristic NP-hard nhưng chạy nhanh hơn thuật toán P với hằng số lớn thường được ưa chuộng.
Chiến lược cắt tỉa và giới hạn tìm kiếm
Cắt tỉa (pruning) loại bỏ các nhánh không hứa hẹn sớm. Thay vì khám phá toàn bộ không gian tìm kiếm, nếu một nhánh rõ ràng không dẫn tới lời giải, ta cắt nó đi. Điều này giảm không gian tìm kiếm từ hàm mũ xuống con số quản lý được.
Lower bound trên chi phí giúp cắt tỉa hiệu quả. Nếu ta biết đường dẫn tốt nhất từ cấu hình hiện tại tới đích không thể ngắn hơn D (ví dụ khoảng cách thẳng), và đường hiện tại đã dài hơn D, ta không cần khám phá tiếp.
Heuristic thông minh là chìa khóa. Một heuristic tốt (như khoảng cách đến đích, độ tự do còn lại) giúp tìm kiếm ưu tiên các cấu hình hứa hẹn trước. Điều này làm cho tìm kiếm nhanh hơn nhiều so với tìm kiếm mù.
A* và các biến thể khác nhau. Thuật toán A* kết hợp chi phí đã chạy và ước lượng chi phí còn lại, cho phép nó tìm kiếm một cách có hướng. Các biến thể như Theta* (cho đường dẫn thẳng) hoặc Lazy A* (kiểm tra va chạm sau) cải thiện thêm.
Giới hạn độ sâu tìm kiếm ngăn chặn thời gian không giới hạn. Nếu tìm kiếm không tìm được lời giải sau N bước, dừng lại và trả về lời giải gần đúng tốt nhất tìm được. Điều này đảm bảo thời gian chạy không vượt quá giới hạn.
Beam search giới hạn số lượng nút được khám phá đồng thời. Thay vì giữ toàn bộ danh sách nút mở, chỉ giữ K nút tốt nhất. Điều này tiết kiệm bộ nhớ và thời gian, với chi phí là có thể bỏ lỡ lời giải tối ưu.
Iterative deepening kết hợp tốc độ của tìm kiếm sâu và tính hoàn chỉnh của tìm kiếm rộng. Bắt đầu tìm kiếm với độ sâu nhỏ, tăng dần nếu không tìm được. Phương pháp này không lãng phí bộ nhớ nhưng vẫn đảm bảo tìm được lời giải nếu có.
Memoization tránh tính toán lại cùng một cấu hình. Nếu đã kiểm tra một cấu hình, lưu kết quả lại. Khi gặp cấu hình đó lần tới, dùng kết quả lưu thay vì tính lại.
Phân tầng (hierarchical decomposition) chia bài toán thành các bài toán nhỏ hơn. Lập kế hoạch ở mức cao (đi qua những khu vực rộng nào) rồi lập kế hoạch chi tiết ở mức thấp (chuyển động chính xác trong từng khu vực). Điều này giảm độ phức tạp toàn cầu.
Từ lý thuyết tới robot thực: chiến lược thực tế
Không có lời giải toàn quát, mỗi ứng dụng cần điều chỉnh. Một robot công nghiệp với không gian làm việc nhỏ và cấu hình cố định có thể dùng pre-computed roadmap. Một robot tự hành trong môi trường không biết trước cần lập kế hoạch incremental. Lựa chọn phương pháp phụ thuộc vào bài toán cụ thể.
Lập kế hoạch offline cho môi trường tĩnh, online cho môi trường động. Nếu vật cản không đổi, có thể dành thời gian để lập kế hoạch chi tiết lần đầu, rồi dùng lại. Nếu vật cản có thể xuất hiện bất kỳ lúc nào, phải lập kế hoạch nhanh mỗi lần phát hiện vật cản mới.
Sử dụng nhiều phương pháp song song để tăng cơ hội tìm được lời giải nhanh. Chạy RRT, PRM, và A* cùng lúc trên các luồng khác nhau, lấy kết quả của phương pháp nào tìm được lời giải trước. Phương pháp này tăng chi phí máy tính nhưng giảm thời gian chờ.
Anytime algorithm: trả về lời giải tốt ngay, rồi cải thiện nó dần. Thay vì chờ thuật toán tìm được lời giải tối ưu (có thể mất lâu vô hạn), trả về lời giải chấp nhận được ngay, và nếu còn thời gian, tiếp tục cải thiện nó. Điều này hữu ích cho các hệ thống real-time.
Caching và reuse: lưu các đường dẫn đã tính để dùng lại. Nếu robot thường xuyên đi giữa các vị trí cố định, lập kế hoạch lần đầu, lưu kết quả, và dùng lại. Cập nhật cache khi vật cản thay đổi.
Simplification và smoothing giảm độ dài đường dẫn sau khi tìm được. Một đường dẫn thô (từ RRT chẳng hạn) có thể dài và gập gềnh. Dùng các kỹ thuật như path shortcutting hoặc spline fitting để cải thiện nó mà vẫn không va chạm.
Sampling-based methods thích hợp khi số chiều cao. Với robot 10+ khớp, phương pháp lập kế hoạch dựa lưới trở nên không khả thi. RRT và PRM, mặc dù không đảm bảo tối ưu, vẫn tìm được lời giải trong thời gian chấp nhận được.
Exact methods khi số chiều thấp và có yêu cầu tối ưu cao. Với robot 2-3 chiều, hoặc khi cần đường dẫn tối ưu (ví dụ robot công nghiệp), các phương pháp dựa lưới hoặc các thuật toán tìm kiếm heuristic chặt có thể giải quyết.
Lập kế hoạch và điều khiển là hai thành phần riêng biệt. Lập kế hoạch tìm ra một chuỗi cấu hình (quỹ đạo tham khảo). Điều khiển theo dõi quỹ đạo đó và xử lý sai lệch do bất định vật lý. Khi vật cản xuất hiện, lập kế hoạch lại, điều khiển thích ứng.
Hướng tiếp cận hiện đại và xu hướng
Machine learning để học heuristic tốt. Thay vì thiết kế heuristic bằng tay, huấn luyện mạng thần kinh để dự đoán chi phí còn lại từ cấu hình hiện tại tới đích. Heuristic này có thể tốt hơn những gì con người thiết kế.
Deep reinforcement learning để học chính sách lập kế hoạch trực tiếp. Thay vì sử dụng một thuật toán chuẩn, huấn luyện một agent để học cách chuyển động từ cấu hình hiện tại sao cho tránh vật cản. Phương pháp này có thể nhanh hơn lập kế hoạch truyền thống trên robot real-time.
Differentiable planning: tối ưu hóa quỹ đạo bằng gradient descent. Nếu mô tả lập kế hoạch như một bài toán tối ưu mịn, có thể dùng gradient descent để cải thiện quỹ đạo. Phương pháp này kết hợp ưu điểm của tối ưu hóa cổ điển và học sâu.
GPU acceleration cho các tính toán hình học đồng thời. Với GPU, có thể kiểm tra va chạm cho hàng triệu cấu hình cùng lúc, tăng tốc độ lập kế hoạch lên vài trăm lần.
Asymptotic optimality: thuật toán sẽ tìm được lời giải tối ưu nếu chạy lâu đủ. RRT* là một ví dụ; nó là RRT nhưng với chi tiết giúp nó dần dần tìm được lời giải tốt hơn. Điều này cho phép ta có cả tính khả thi (tìm được lời giải nhanh) lẫn tính tối ưu (lời giải cải thiện theo thời gian).
Lập kế hoạch dựa trên mô phỏng cho các hệ thống phức tạp. Khi mô hình động học hoặc động lực học phức tạp, thay vì giải tích toán học, dùng mô phỏng vật lý để tìm quỹ đạo khả thi. Điều này cho phép xử lý các ràng buộc động (không chỉ hình học) như giới hạn momen xoắn, ma sát, hay tính quán tính.
Collaborative planning: nhiều robot lập kế hoạch cùng lúc. Khi có nhiều robot, lập kế hoạch cho từng robot độc lập không hiệu quả. Các phương pháp lập kế hoạch hợp tác xem xét tất cả robot cùng lúc, tìm ra các quỹ đạo mà chúng không va chạm với nhau.
Lập kế hoạch tạm thời (receding horizon): lập kế hoạch một cách ngắn hạn, thực thi, rồi lập kế hoạch lại. Thay vì lập kế hoạch toàn bộ từ đầu tới cuối, chỉ lập kế hoạch cho vài giây tới, thực thi, rồi lập kế hoạch lại dựa trên thông tin cảm biến mới. Phương pháp này thích hợp cho môi trường động.
Sự kết hợp giữa lập kế hoạch toàn cầu và phản ứng địa phương. Sử dụng một thuật toán lập kế hoạch toàn cầu (như RRT) để tìm ra một con đường tổng quát, rồi dùng một bộ điều khiển phản ứng (như potential field) để tránh vật cản chưa biết khi thực thi. Kết hợp này cung cấp sự cân bằng giữa tính toàn cầu và tính thích ứng.
Câu hỏi thường gặp
Tại sao lập kế hoạch chuyển động là NP-hard lại không phải là vấn đề lớn như ta tưởng?
NP-hard chỉ nói rằng không có thuật toán đa thức chạy nhanh trên mọi trường hợp. Nhưng trên các trường hợp thực tế cụ thể, heuristic tốt và cắt tỉa hiệu quả có thể giải được rất nhanh. Hơn nữa, chúng ta không cần lời giải tối ưu; một lời giải tốt trong thời gian chấp nhận được là đủ. Các robot công nghiệp chạy lập kế hoạch hàng ngày mà không gặp vấn đề gì.
Khi nào nên sử dụng phương pháp dựa lưới và khi nào nên sử dụng phương pháp lấy mẫu?
Phương pháp dựa lưới (A*, D*) phù hợp khi số chiều thấp (2-3) và có yêu cầu tối ưu cao. Chúng có thể tìm được lời giải tối ưu hoặc gần tối ưu. Phương pháp lấy mẫu (RRT, PRM) phù hợp khi số chiều cao (7+ khớp) hoặc khi hình dạng vật cản phức tạp. Chúng không đảm bảo tối ưu nhưng thường tìm được lời giải nhanh. Nhiều ứng dụng kết hợp cả hai: dùng lấy mẫu để tìm lời giải nhanh, rồi dùng lập kế hoạch chi tiết để cải thiện.
Làm thế nào để đảm bảo lập kế hoạch chuyển động hoàn thành trong thời gian cho phép trên robot thực?
Có một số chiến lược: (1) Sử dụng anytime algorithm để trả về lời giải tốt ngay, rồi cải thiện nếu còn thời gian. (2) Đặt giới hạn thời gian cứng cho thuật toán; nếu hết thời gian, dùng lời giải gần đúng tốt nhất tìm được. (3) Chạy nhiều thuật toán song song và dùng kết quả của cái tìm được lời giải trước. (4) Dùng caching và pre-computation để giảm lần tính toán. (5) Điều chỉnh tham số thuật toán (như số lần lấy mẫu trong RRT) dựa trên yêu cầu thời gian cụ thể.
Machine learning có thể thay thế hoàn toàn lập kế hoạch chuyển động truyền thống không?
Hiện tại chưa. Machine learning có thể học được các heuristic tốt hoặc chính sách lập kế hoạch, nhưng nó cần dữ liệu huấn luyện lớn và không đảm bảo tính an toàn (không va chạm) trên các tình huống chưa gặp. Lập kế hoạch truyền thống có các bảo đảm lý thuyết về tính hoàn chỉnh hoặc tính tối ưu (asymptotic). Xu hướng hiện tại là kết hợp cả hai: dùng ML để cải thiện các thành phần của lập kế hoạch truyền thống (như heuristic hoặc khởi tạo), nhưng vẫn giữ khung lập kế hoạch cơ bản.
Đọc thêm trong Benchmark & tập dữ liệu và Từ lab ra thực tế.
