BẢN ĐỒ HÀNH LANG TƯỜNG MINH: BẢN ĐỒ CHO BÀI TOÁN TÌM ĐƯỜNG ĐA ĐỐI TƯỢNG

Abstract

Tìm đường đi từ vị trí A đến vị trí B, đồng thời tránh vật cản và phản ứng với sự thay đổi của môi trường xung quanh là một bài toán lớn và cổ điển, đặc biệt là không dễ đối với rô bốt. Tìm đường đối với rô bốt chỉ có thể tính toán một khi bản đồ cho môi trường đã được xác định. Trong bài báo này, nhóm tác giả trình bày cách xây dựng bản đồ hành lang tường minh (Explicit Corridor Map (ECM)) cho môi trường có chứa các vật cản và bản đồ có thể dễ dàng được cập nhật khi môi trường có sự thay đổi. Với một môi trường phẳng chứa n vật cản, độ phức tạp về mặt lưu trữ là ????????(????????) và tiêu tốn thời gian tính toán là ????????(???????? ???????????????????????? ????????). Kết quả thực nghiệm cho thấy ECM tính toán rất nhanh trên môi trường 2D, đồng thời việc tìm đường trên bản đồ này chỉ trong khoảng vài ms. Bản đồ hành lang tường minh cũng phù hợp với việc mô phỏng đám đông di chuyển.