Phương pháp lấy mẫu — vì sao ngẫu nhiên lại hiệu quả

Không gian cấu hình sáu chiều không chia lưới được. Lời giải mà cả ngành hội tụ về là bỏ tham vọng khảo sát toàn bộ không gian, chỉ lấy mẫu ngẫu nhiên vài nghìn điểm và nối chúng lại. Nghe như bỏ cuộc, nhưng nó hiệu quả đến bất ngờ.

Cây mở rộng ngẫu nhiên

Cách hoạt động. Bắt đầu từ tư thế xuất phát, coi là gốc cây. Lặp lại: lấy một điểm ngẫu nhiên trong không gian cấu hình, tìm nút gần nhất trên cây, mọc một nhánh ngắn từ nút đó về phía điểm ngẫu nhiên. Nếu nhánh không va chạm thì thêm vào cây. Dừng khi cây chạm tới vùng đích.

Vì sao nó phủ tốt. Xu hướng tự nhiên của thuật toán là mở rộng về những vùng chưa có nút nào — vì điểm ngẫu nhiên rơi vào vùng trống thì nút gần nhất ở xa, và nhánh mọc theo hướng đó. Cây tự động vươn ra chỗ chưa khám phá.

Ưu điểm lớn nhất. Không cần biết hình dạng vùng cấm, chỉ cần hàm trả lời điểm này có va chạm không. Nhờ vậy dùng được cho robot bất kỳ với vật cản bất kỳ.

Nhược điểm. Đường đi ra rất xấu — ngoằn ngoèo, nhiều đoạn thừa. Phải làm mượt sau.

Tính chất lý thuyết. Hoàn chỉnh theo xác suất: nếu tồn tại lời giải, xác suất tìm ra tiến tới một khi số mẫu tăng. Không đảm bảo tìm ra trong thời gian hữu hạn, và không đảm bảo lời giải tốt.

Bản đồ đường đi xác suất

Cách tiếp cận song song, hợp với bài toán khác.

Cách hoạt động. Giai đoạn một: rải ngẫu nhiên nhiều điểm khắp không gian, giữ lại điểm không va chạm, nối các điểm gần nhau bằng đoạn thẳng nếu đoạn đó không va chạm. Được một đồ thị. Giai đoạn hai: khi có yêu cầu cụ thể, nối điểm đầu và điểm cuối vào đồ thị rồi tìm đường trên đồ thị.

Điểm mạnh. Đồ thị dựng một lần dùng nhiều lần. Rất hợp với cánh tay cố định trong môi trường ít đổi — dựng đồ thị lúc cài đặt, sau đó mỗi lệnh mới chỉ tốn thời gian tìm đường trên đồ thị.

Điểm yếu. Môi trường đổi thì đồ thị hỏng. Không hợp với robot di động trong không gian thay đổi.

So sánh với cây mở rộng. Cây hợp với truy vấn một lần trong môi trường lạ; đồ thị hợp với nhiều truy vấn trong môi trường quen. Đây là tiêu chí chọn rõ ràng nhất giữa hai họ.

Điểm chung. Cả hai đều dựa trên lấy mẫu, đều hoàn chỉnh theo xác suất, và đều gặp cùng một vấn đề: vùng hẹp.

Vùng hẹp — điểm yếu chung

Chỗ mọi phương pháp lấy mẫu đều khó.

Vấn đề. Nếu lời giải bắt buộc đi qua một khe hẹp trong không gian cấu hình, xác suất một điểm ngẫu nhiên rơi trúng khe đó rất thấp. Thuật toán có thể chạy rất lâu mà không tìm ra.

Ví dụ vật lý. Luồn một vật dài qua khung cửa hẹp. Chỉ một dải rất mỏng các tư thế là hợp lệ.

Triệu chứng. Thuật toán chạy nhanh với đa số bài toán rồi đột nhiên treo với một bài toán trông không khó hơn. Đây là dấu hiệu điển hình của vùng hẹp.

Cách khắc phục — lấy mẫu thiên lệch. Lấy nhiều mẫu hơn gần bề mặt vật cản, vì vùng hẹp luôn nằm sát vật cản.

Cách khắc phục — mọc cây từ hai đầu. Một cây từ điểm đầu, một cây từ điểm cuối, cố nối lại. Thường nhanh hơn nhiều lần.

Cách khắc phục — thêm gợi ý của người. Cho trước một vài tư thế trung gian để chia bài toán thành các đoạn dễ. Không thanh lịch nhưng cực kỳ hiệu quả trong sản xuất, và các hệ thống công nghiệp làm đúng như vậy.

Từ tìm được đường tới đường tốt

Đường đầu tiên tìm được thường không dùng được ngay.

Vì sao xấu. Thuật toán dừng ngay khi chạm đích, không quan tâm chất lượng. Đường ra ngoằn ngoèo, dài hơn cần thiết, có đoạn quay ngược.

Làm mượt bằng cắt góc. Chọn hai điểm bất kỳ trên đường, thử nối thẳng; nếu đoạn thẳng không va chạm thì bỏ toàn bộ phần ở giữa. Lặp nhiều lần. Đơn giản, nhanh, cải thiện rất rõ.

Biến thể tối ưu dần. Có họ thuật toán vừa tìm vừa cải thiện, đảm bảo hội tụ về lời giải tối ưu khi thời gian tăng. Cho đường đẹp hơn, tốn thời gian hơn, và trong nhiều ứng dụng thì lời giải đủ tốt tìm nhanh có giá trị hơn lời giải tối ưu tìm chậm.

Chuyển sang quỹ đạo theo thời gian. Đường đi hình học chưa nói tốc độ. Phải gán thời gian sao cho tôn trọng giới hạn tốc độ và gia tốc, và làm trơn để không giật ở các điểm gấp khúc.

Thứ tự thực dụng. Tìm bất kỳ đường nào, cắt góc, rồi gán quỹ đạo thời gian. Ba bước tách rời này là cấu trúc chuẩn trong hầu hết hệ thống thật.

Chỗ các phương pháp này không đủ

Ranh giới cần biết trước khi áp dụng.

Môi trường thay đổi trong lúc chạy. Kế hoạch được tính trước cho một ảnh chụp môi trường. Người bước vào giữa đường thì kế hoạch hỏng. Cần lớp tránh vật cản phản ứng nhanh chạy song song, và ghép hai tầng này lại là bài toán riêng.

Bài toán có tiếp xúc. Lắp một chi tiết vào lỗ khít đòi hỏi chạm và trượt theo bề mặt — nghĩa là cố tình ở sát ranh giới vùng cấm. Phương pháp lấy mẫu vốn tránh chỗ đó nên không hợp; cần điều khiển theo lực.

Vật thể mềm hoặc biến dạng. Dây, vải, dây điện. Không gian cấu hình của chúng có số chiều rất lớn và không rõ ràng.

Nhiệm vụ dài nhiều bước. Sắp xếp lại nhiều vật thể cần lập kế hoạch ở tầng nhiệm vụ trước, rồi mới tới tầng chuyển động. Đây là nhánh nghiên cứu riêng.

Yêu cầu thời gian thực chặt. Lấy mẫu ngẫu nhiên có thời gian chạy không đoán trước được. Hệ thống cần đảm bảo thời gian thường dùng cách khác hoặc dựng sẵn kế hoạch từ trước.

Dù vậy, với bài toán tìm đường trong không gian tĩnh, họ phương pháp này vẫn là công cụ mặc định và đã như vậy suốt hơn hai thập kỷ.

Câu hỏi thường gặp

Đọc thêm trong Benchmark & tập dữ liệu và Điều khiển & lý thuyết.