Một robot đi từ A tới B là bài toán đã biết. Hai mươi robot cùng một kho hàng thì phát sinh những câu hỏi hoàn toàn mới: ai làm việc gì, ai nhường ai, và điều gì xảy ra khi một cái hỏng.
Ba bài toán cơ bản
Phân bổ nhiệm vụ. Có danh sách việc và có nhiều robot. Ai làm việc nào để tổng thời gian ngắn nhất. Đây là bài toán tối ưu tổ hợp và nó khó nhanh khi số lượng tăng.
Lập kế hoạch đường đi không xung đột. Nhiều robot cùng không gian, đường đi không được cắt nhau ở cùng thời điểm. Khác với tránh vật cản tĩnh vì mọi thứ đều đang di chuyển và mọi thứ đều có kế hoạch.
Đồng bộ. Vài nhiệm vụ cần nhiều robot cùng lúc — hai robot khiêng một vật dài. Cần phối hợp thời gian chính xác.
Vì sao không giải riêng từng bài toán được. Phân bổ nhiệm vụ ảnh hưởng tới đường đi, đường đi ảnh hưởng tới thời gian hoàn thành, thời gian lại ảnh hưởng tới phân bổ tối ưu. Ba bài toán liên đới.
Cách thực dụng. Giải tách rời và chấp nhận không tối ưu. Phân bổ trước theo tiêu chí đơn giản, rồi lập kế hoạch đường đi, rồi sửa nếu xung đột. Kém tối ưu về lý thuyết nhưng chạy được ở quy mô thật.
Tập trung hay phân tán
Quyết định kiến trúc quan trọng nhất.
Tập trung. Một máy chủ biết vị trí mọi robot, tính toàn bộ kế hoạch, gửi lệnh xuống. Cho lời giải tốt hơn vì có thông tin đầy đủ.
Điểm yếu của tập trung. Máy chủ hỏng thì cả đội dừng. Cần mạng ổn định liên tục. Và độ phức tạp tính toán tăng nhanh theo số robot.
Phân tán. Mỗi robot tự quyết định dựa trên thông tin cục bộ và trao đổi với robot lân cận. Bền hơn — một cái hỏng thì các cái khác vẫn chạy.
Điểm yếu của phân tán. Không tối ưu toàn cục. Có thể xảy ra tình huống hai robot cùng nhường nhau mãi, hoặc cùng lao vào một nhiệm vụ.
Kiến trúc lai — phổ biến nhất trong thực tế. Máy chủ phân bổ nhiệm vụ và quản lý ưu tiên ở mức chậm; mỗi robot tự lo điều hướng và tránh va chạm ở mức nhanh. Chia đúng theo tần số cần thiết.
Nguyên tắc thiết kế. Việc gì cần phản ứng nhanh thì để robot tự quyết. Việc gì cần nhìn toàn cục thì để máy chủ. Và mọi robot phải có hành vi an toàn khi mất kết nối.
Tránh va chạm giữa các robot
Chi tiết thực tế gây nhiều sự cố nhất.
Vì sao khó hơn tránh người. Hai robot cùng thuật toán sẽ ra quyết định giống nhau — cùng lách một bên, cùng dừng, cùng đi lại. Tính đối xứng gây bế tắc.
Cách phá đối xứng. Gán mỗi robot một mã ưu tiên. Khi xung đột, robot ưu tiên thấp nhường. Đơn giản và hiệu quả, miễn là mã không đổi trong lúc đàm phán.
Đặt trước chỗ và thời gian. Robot đăng ký với máy chủ rằng nó sẽ chiếm đoạn hành lang này trong khoảng thời gian này. Cái khác thấy chiếm rồi thì chờ hoặc đi đường khác. Rất hiệu quả trong kho có tuyến đường cố định.
Bế tắc vòng tròn. Ba robot chờ nhau theo vòng, không cái nào đi được. Cần cơ chế phát hiện và phá vòng — thường bằng cách cho một cái lùi lại.
Điểm nghẽn cố định. Cửa hẹp, thang máy, chỗ sạc. Cần quản lý như tài nguyên có hàng đợi, không để các robot tự đàm phán tại chỗ.
Kinh nghiệm vận hành. Phần lớn sự cố đội robot xảy ra ở điểm nghẽn. Thiết kế mặt bằng có đủ chỗ tránh nhau ở những nơi đó giải quyết được nhiều hơn mọi cải tiến thuật toán.
Đội robot không đồng nhất
Trường hợp thực tế hơn và ít được nghiên cứu hơn.
Thực tế hiếm khi đồng nhất. Kho hàng có robot chở hàng nặng và robot chở hàng nhẹ. Khách sạn có robot giao đồ và robot lau sàn. Khả năng khác nhau, tốc độ khác nhau, kích thước khác nhau.
Phân bổ nhiệm vụ phức tạp hơn. Không phải robot nào cũng làm được mọi việc. Phải xét khả năng, không chỉ khoảng cách.
Ưu tiên khác nhau. Robot chở đồ ăn nóng nên được ưu tiên hơn robot lau sàn. Cần chính sách rõ ràng, không để mặc thuật toán tránh va chạm quyết.
Tốc độ khác nhau gây tắc. Robot chậm chặn robot nhanh trong hành lang hẹp. Cần chỗ tránh hoặc phân luồng theo thời gian.
Robot từ nhiều nhà cung cấp. Vấn đề thực tế lớn: mỗi hãng có giao thức riêng, không nói chuyện được với nhau. Chúng chỉ tránh nhau như tránh vật cản thường, không phối hợp.
Cách xử lý hiện nay. Tầng điều phối trung gian nói chuyện với từng hệ thống qua giao diện riêng. Tốn công tích hợp, nhưng là cách duy nhất khi đã lỡ mua nhiều hãng — và là lý do nên cân nhắc kỹ trước khi trộn nhà cung cấp.
Vận hành đội robot
Những gì cần chuẩn bị ngoài phần thuật toán.
Quản lý sạc là bài toán riêng. Robot phải tự đi sạc mà không làm gián đoạn công việc. Số chỗ sạc có hạn. Cần chính sách — sạc khi rảnh, ưu tiên robot pin thấp, dự phòng khi nhiều cái cùng cần.
Giám sát tập trung. Người vận hành cần thấy tất cả robot ở đâu, đang làm gì, cái nào có vấn đề. Không có màn hình này thì quản lý hai mươi robot là không khả thi.
Xử lý khi một cái hỏng. Nhiệm vụ đang dở phải giao lại cho cái khác. Robot hỏng nằm giữa lối đi thành vật cản cho cả đội — cần quy trình xử lý nhanh.
Cập nhật phần mềm. Không thể dừng cả đội. Cần cập nhật lần lượt và có khả năng quay lui.
Đo hiệu quả toàn đội. Chỉ số quan trọng không phải tốc độ từng robot mà là thông lượng tổng và thời gian chờ. Thêm robot có lúc làm giảm thông lượng vì tắc nghẽn tăng.
Điểm bão hoà. Mỗi mặt bằng có số robot tối đa mà thêm nữa thì hiệu quả giảm. Biết con số đó trước khi mua thêm là việc đáng làm, và cách biết chắc chắn nhất là mô phỏng lưu lượng trên chính mặt bằng đó.
Câu hỏi thường gặp
Ba bài toán cơ bản khi có nhiều robot là gì?
Phân bổ nhiệm vụ, lập kế hoạch đường đi không xung đột, và đồng bộ cho các nhiệm vụ cần nhiều robot cùng lúc. Ba bài toán này liên đới nên thực tế phải giải tách rời và chấp nhận không tối ưu.
Kiến trúc nào phổ biến nhất trong thực tế?
Kiến trúc lai — máy chủ phân bổ nhiệm vụ và quản lý ưu tiên ở mức chậm, mỗi robot tự lo điều hướng và tránh va chạm ở mức nhanh. Mọi robot phải có hành vi an toàn khi mất kết nối.
Vì sao hai robot tránh nhau khó hơn robot tránh người?
Vì hai robot cùng thuật toán ra quyết định giống nhau — cùng lách một bên hoặc cùng dừng. Phải phá đối xứng bằng cách gán mã ưu tiên cho từng robot.
Chỉ số nào quan trọng khi vận hành đội robot?
Thông lượng tổng và thời gian chờ, không phải tốc độ từng robot. Mỗi mặt bằng có điểm bão hoà mà thêm robot làm giảm hiệu quả do tắc nghẽn tăng.
Đọc thêm trong Thị giác máy cho robot và Benchmark & tập dữ liệu.