Tìm đường cho robot tròn trong mặt phẳng là bài toán ai cũng hình dung được. Tìm đường cho cánh tay bảy khớp thì trực giác không giúp được nữa, và khái niệm giúp vượt qua chỗ đó gọi là không gian cấu hình.
Ý tưởng cốt lõi
Bài toán gốc rắc rối vì robot có hình dạng. Muốn biết một tư thế có va chạm không, phải kiểm mọi phần thân robot với mọi vật cản. Làm việc này ở mọi điểm trên đường đi là cực kỳ tốn.
Mẹo là đổi cách mô tả. Thay vì mô tả robot trong không gian vật lý, mô tả nó bằng tập giá trị các khớp. Cánh tay sáu khớp thì mỗi tư thế là một bộ sáu số. Toàn bộ tư thế có thể có tạo thành một không gian sáu chiều.
Trong không gian đó, robot là một điểm. Dù thân nó dài và cồng kềnh đến đâu, mỗi tư thế vẫn chỉ là một điểm.
Vật cản biến thành vùng cấm. Mọi bộ giá trị khớp khiến robot va vào vật cản tạo thành một vùng trong không gian cấu hình. Vùng còn lại là vùng đi được.
Bài toán trở thành: tìm đường liên tục cho một điểm từ tư thế đầu tới tư thế cuối, không đi vào vùng cấm. Về mặt khái niệm là bài toán tìm đường quen thuộc, chỉ ở số chiều cao hơn.
Vì sao số chiều làm mọi thứ khó
Đây là nguồn gốc của gần như mọi khó khăn trong lĩnh vực này.
Thể tích tăng theo hàm mũ. Chia mỗi chiều thành mười mức: hai chiều cho một trăm ô, sáu chiều cho một triệu ô, mười hai chiều cho một nghìn tỷ. Cách chia lưới rồi tìm đường — hiệu quả trong mặt phẳng — trở thành bất khả thi.
Không gian gần như trống nhưng không đi thẳng được. Nghịch lý quen thuộc: phần lớn không gian cấu hình là vùng đi được, nhưng đường thẳng nối hai điểm thường xuyên cắt qua vùng cấm.
Vùng cấm có hình dạng không hình dung nổi. Một cái cột tròn đơn giản trong không gian vật lý biến thành một vùng hình thù phức tạp trong không gian cấu hình. Không có công thức đơn giản để mô tả nó.
Vì thế không ai dựng vùng cấm một cách tường minh. Thay vào đó, hệ thống chỉ kiểm tra từng điểm cụ thể xem có va chạm không, khi cần. Đây là quyết định thiết kế then chốt dẫn tới toàn bộ họ phương pháp lấy mẫu.
Số bậc tự do càng cao càng linh hoạt nhưng càng khó lập kế hoạch. Cánh tay bảy khớp có thể với tới một điểm bằng vô số tư thế khác nhau — vừa là ưu điểm vừa là gánh nặng tính toán.
Kiểm tra va chạm — nút thắt thật sự
Phần chiếm nhiều thời gian tính toán nhất và ít được nói tới nhất.
Mọi thuật toán lập kế hoạch đều gọi hàm kiểm va chạm rất nhiều lần. Thường chiếm trên tám mươi phần trăm thời gian chạy. Tối ưu chỗ này có tác dụng lớn hơn đổi thuật toán.
Cách làm nhanh. Bọc mỗi bộ phận bằng hình đơn giản — hình cầu, hình trụ, hộp. Kiểm hai hình đơn giản có giao nhau không thì rất nhanh. Bọc rộng hơn thực tế một chút để an toàn.
Phân cấp. Kiểm hình bao lớn trước; nếu không giao nhau thì bỏ qua toàn bộ chi tiết bên trong. Loại được phần lớn phép kiểm ngay từ đầu.
Đừng quên tự va chạm. Cánh tay nhiều khớp có thể tự đâm vào chính mình. Bài toán này thường bị bỏ sót trong triển khai và gây hỏng phần cứng thật.
Kiểm dọc đoạn nối. Hai tư thế đều an toàn không có nghĩa là đường nối giữa chúng an toàn. Phải lấy mẫu dọc đoạn — bước lấy mẫu quá thưa là lỗi phổ biến, và nó cho ra kế hoạch trông đẹp nhưng va chạm khi chạy thật.
Ràng buộc ngoài va chạm
Thực tế còn nhiều điều kiện nữa mà bài toán thuần hình học bỏ qua.
Giới hạn khớp. Mỗi khớp chỉ xoay trong một khoảng. Thu hẹp không gian cấu hình ngay từ đầu.
Giới hạn tốc độ và gia tốc. Đường đi hình học không nói gì về thời gian. Chuyển từ đường đi sang quỹ đạo theo thời gian là bước riêng và có ràng buộc riêng.
Ràng buộc giữ tư thế. Bưng cốc nước thì tay phải giữ phương thẳng đứng suốt đường đi. Ràng buộc này cắt không gian cấu hình xuống một mặt con có số chiều thấp hơn, và lấy mẫu ngẫu nhiên gần như không bao giờ rơi trúng mặt con đó — cần kỹ thuật riêng.
Ràng buộc động lực học. Với robot di động, không phải hướng nào cũng đi được. Xe không đi ngang được. Robot chân phải giữ thăng bằng.
Ràng buộc lực. Khi robot chạm vào vật thể, phải kiểm soát lực chứ không chỉ vị trí. Đây là chỗ lập kế hoạch chuyển động thuần tuý không còn đủ và phải ghép với điều khiển.
Mỗi ràng buộc thêm vào làm bài toán khó hơn đáng kể, và đó là lý do các bài toán thao tác thực tế khó hơn nhiều so với bài toán tìm đường cho robot di động.
Ý nghĩa thực tế của cách nghĩ này
Vì sao đáng bỏ công hiểu.
Nó giải thích vì sao robot đi đường vòng lạ. Đường ngắn nhất trong không gian cấu hình không phải đường ngắn nhất trong không gian vật lý. Robot vòng ra ngoài rồi vào lại vì đường thẳng trong không gian khớp bị chặn.
Nó giải thích vì sao thêm khớp không luôn tốt. Linh hoạt hơn nhưng không gian tìm kiếm lớn hơn theo hàm mũ.
Nó giải thích vì sao lập kế hoạch có lúc thất bại mà mắt người thấy rõ có đường. Đường đó có thể đi qua vùng hẹp trong không gian cấu hình mà lấy mẫu ngẫu nhiên khó tìm thấy.
Nó cho biết chỗ nào nên đầu tư. Nếu lập kế hoạch chậm, hãy tối ưu kiểm va chạm trước, giảm số chiều bằng cách cố định vài khớp thứ hai, rồi mới đổi thuật toán.
Và nó là ngôn ngữ chung của lĩnh vực. Mọi bài báo về lập kế hoạch chuyển động đều giả định người đọc quen khái niệm này — không có nó thì phần lớn tài liệu không đọc được.
Câu hỏi thường gặp
Không gian cấu hình là gì?
Cách mô tả robot bằng tập giá trị các khớp thay vì hình dạng vật lý. Trong không gian đó mỗi tư thế là một điểm, nên bài toán tìm đường cho vật thể có hình dạng thành bài toán tìm đường cho một điểm.
Vì sao số chiều cao làm bài toán khó?
Thể tích tăng theo hàm mũ nên cách chia lưới trở thành bất khả thi, và vùng cấm có hình dạng phức tạp không mô tả tường minh được — nên hệ thống chỉ kiểm từng điểm cụ thể khi cần.
Phần nào chiếm nhiều thời gian tính toán nhất?
Kiểm tra va chạm, thường trên tám mươi phần trăm thời gian chạy. Tối ưu chỗ này bằng hình bao đơn giản và kiểm phân cấp có tác dụng lớn hơn đổi thuật toán.
Vì sao robot có lúc đi đường vòng trông rất lạ?
Vì đường ngắn nhất trong không gian cấu hình không phải đường ngắn nhất trong không gian vật lý. Đường thẳng trong không gian khớp có thể bị vùng cấm chặn.
Đọc thêm trong SLAM & định vị và Từ lab ra thực tế.