Lập tuyến đường tránh va cho tàu biển áp dụng thuật toán Floyd

Bài viết này đề xuất một phương pháp tránh va dựa vào thuật toán Floyd, một mạng lưới điểm waypoint dựng sẵn sẽ được thiết kế để bao phủ khu vực tàu chủ hành hải. Các điểm waypoint an toàn sẽ được kết nối với nhau để tạo ra đường chạy tàu mới, đảm bảo cho con tàu luôn đến đích an toàn và tránh khỏi các nguy cơ đâm va.
Nội dung trích xuất từ tài liệu:
Lập tuyến đường tránh va cho tàu biển áp dụng thuật toán FloydCHÀO MỪNG NGÀY THÀNH LẬP TRƯỜNG 01/4/2018 LẬP TUYẾN ĐƯỜNG TRÁNH VA CHO TÀU BIỂN ÁP DỤNG THUẬT TOÁN FLOYD COLLISION-AVOIDING ROUTE BY APPLYING FLOYD ALGORITHM ĐINH GIA HUY, NGUYỄN MẠNH CƯỜNG, PHAN VĂN HƯNG Khoa Hàng hải, Trường ĐHHH Việt NamTóm tắt Sự nở rộ của ngành khoa học máy tính vào những năm 1990 đã bổ sung một hướng đi mới cho các nghiên cứu tự động tránh va tàu biển. Việc nghiên cứu áp dụng các thuật toán tìm đường của máy tính vào quá trình tránh va tàu biển đã được quan tâm đến. Bài báo này đề xuất một phương pháp tránh va dựa vào thuật toán Floyd, một mạng lưới điểm waypoint dựng sẵn sẽ được thiết kế để bao phủ khu vực tàu chủ hành hải. Các điểm waypoint an toàn sẽ được kết nối với nhau để tạo ra đường chạy tàu mới, đảm bảo cho con tàu luôn đến đích an toàn và tránh khỏi các nguy cơ đâm va. Chương trình mô phỏng sẽ được xây dựng nhằm ghi lại toàn bộ chuyển động tàu và đưa ra những phân tích đánh giá cụ thể để chứng minh tính hiệu quả của hệ thống. Từ khóa: Mô hình MMG, thuật toán Floyd, mạng, điểm chuyển hướng tàu, nhóm Heuristic.Abstract The computer science has been booming as never before from 1990s, contributing to an enlargement of novel concepts for automatic collision avoidance at sea. The study of applying shortest path search in computer field into an automatic collision avoidance performance has been considered. This article proposes a collision avoidance method based on the Floyd algorithmic, a net of waypoints is constructed to cover the own ship’s navigable area. The safety waypoint will be connected together in order to product new route, ensuring that own ship’s will arrive safety and avoid the risk of collisions. The simulation is generated to record the entire dynamic motion of ship and provide detailed analysis to demonstrate the effectiveness of the system. Keywords: MMG model, Floyd algorithm, net, waypoint, Heuristic group.1. Đặt vấn đề Các hệ thống lập tuyến đường tự động cho tàu biển có thể được phân chia thành 2 nhóm cơbản phụ thuộc vào phương pháp tiếp cận để thiết kế thuật toán nguồn của hệ thống. Cụ thể nhómthứ nhất là deterministic approach, các hệ thống luôn tuân theo một tập hợp các bước tính toán vàluật phức tạp để tìm ra đường tránh va hiệu quả. Trong khi đó ở nhóm thứ hai, heuristic approachlại đi tìm các khoảng trống của không gian tìm kiểm để đưa ra những đường chạy tàu gần như tốiưu thỏa mãn đủ yêu cầu của nhà thiết kế hệ thống. Cho đến nay, các nghiên cứu ở trên cả 2 nhómđều đưa ra được những hệ thống tự động tránh va (TĐTV) hiệu quả, tuy nhiên ưu thế của cả hai làtương đương khi các hệ thống TĐTV ở nhóm thứ nhất có ưu thế trong việc dễ dàng tuân thủ theocác quy tắc tránh va quốc tế hay các mục đích tránh va nhất định, còn nhóm thứ hai lại nhanh chóngđưa ra đường đi ngắn nhất và gần như tối ưu. Để áp dụng các thuật toán nhóm Heuristic vào hệ thống TĐTV, một ma trận điểm chuyểnhướng (waypoint) sẽ được xây dựng bao phủ toàn bộ khu vực tàu hành hải, được gọi là “mạng(net)”. Phương pháp xây dựng mạng rất phổ biến trong các hệ thống TĐTV và như một tiền đề đểáp dụng các thuật toán nhóm Heuristic. Phương thức này được sử dụng trong các nghiên cứu: GiaHuy Dinh & Nam-Kyun Im (2017) [1], Ki-Yin Chang (2003) [2], Minh Duc Nguyen [3], Blaich, M. et al(2012) [4],… Các thuật toán sẽ tự bỏ đi các điểm trong mạng bị che khuất bởi mục tiêu hay vùngnguy hiểm xung quanh mục tiêu, một đường chạy tàu ngắn nhất nối từ vị trí tàu hiện tại đi qua cácđiểm còn lại trong mạng tới vị trí điểm đích sẽ được đáp ứng bởi thuật toán. Những thuật toán rấthiệu quả thường được sử dụng đó là Dijkstra do Dijkstra giới thiệu năm 1959 hay thuật toán di truyền(Genetic algorithm), thuật toán đàn kiến, A*,... Bài báo này đề xuất việc sử dụng thuật toán Floyd,ưu điểm của thuật toán này là có thể áp dụng cho một mạng có kích thước lớn hơn nhiều so với mộtsố thuật toán nhóm Heuristic khác. Ngoài ra với sự thay đổi đột ngột và nhanh chóng của các mụctiêu, đường chạy tàu mới sẽ được vẽ lại ngay mà không cần thực hiện quá trình tính toán mới.2. Thuật toán Floyd Thuật toán Floyd được nhà khoa học Robert Floyd giới thiệu năm 1962, lý thuyết thuật toánFloyd có thể được mô tả như sau: Với một đồ thị có hướng, trọng số G = (V, E) với n đỉnh và mTạp chí Khoa học Công nghệ Hàng hải Số 54 - 4/2018 25 CHÀO MỪNG NGÀY THÀNH LẬP TRƯỜNG 01/4/2018cạnh. Mục tiêu là đi tìm d(u, v), tất cả lộ trình từ đỉnh u tới đỉnh v trong đồ thị. Trong đó, thuật toán đitính chi phí của các lộ trình và tìm ra c[u, v], lộ trình có chi phí thấp nhất từ đỉnh u tới v. Với mỗi đỉnhk thuộc đồ thị cho ta 1 tới n lộ trình. Lộ trình có chi phí thấp nhất c[u, v] được tính bằng công thức: c[u, v]  min(c[u, v], c[u, k ]  c[k , v]) (1) Cách tìm lộ trình có chi phí nhỏ nhất: For k:=1 to n do For u:= 1 to n do For v:= 1 to n do c[u, v]  min(c[u, v], c[u, k ]  c[k , v]) Giả định Ck[u,v] là chi phí của lộ trình ngắn nhất từ u tới v đi qua các đỉnh của tập hợp {1,2, ..., k}. Hiển nhiên, khi k=0 thì: c 0 [u , v]  c[u , v] (2) Lộ trình ngắn nhất từ u tới v chỉ đi qua các đỉnh chuyển tiếp {1, 2, …, k}, tuy nhiên:  Nếu không đi qua đỉnh k, mà chỉ đi qua các đỉnh {1, 2, 3, …, k-1}, ...