Bài viết 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. | Bản đồ hành lang tường minh: Bản đồ cho bài toán tìm đường đa đối tượng 33 TẠP CHÍ KHOA HỌC CÔNG NGHỆ GIAO THÔNG VẬN TẢI, SỐ 34-11/2019 BẢN ĐỒ HÀNH LANG TƯỜNG MINH: BẢN ĐỒ CHO BÀI TOÁN TÌM ĐƯỜNG ĐA ĐỐI TƯỢNG EXPLICIT CORRIDOR MAP: ROADMAP FOR MULTIPLE MOVING OBJECTS PATH FINDING PROBLEM 1 Trần Nhật Hoàng Anh, 2Vương Bá Thịnh 1 Đại học Giao thông vận tải Thành phố Hồ Chí Minh 2 Đại học Bách Khoa – ĐHQG Thành phố Hồ Chí Minh Tóm tắt: 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. Từ khóa: Lưới điều hướng, tìm đường. Chỉ số phân loại: Abstract: Path planning from position A to position B, while avoiding obstacles and responding to changes in the surrounding environment is a big and fundamental task, especially uneasy for rô bốts. Path finding for rô bốts can only be calculated once the roadmap for the environment has been identified. In this paper, we present a way to build for the environment that contains obstructions an Explicit Corridor Map (ECM), which can be simply updated as the environment changes. For a planar environment with n obstacle vertices, storage complexity is ( ) and computational
