Cách tiếp cận bắn nhiều lần trong tìm xấp xỉ đường đi ngắn nhất có ràng buộc trên các bề mặt đa diện trong không gian 3 chiều
Người báo cáo: Nguyễn Thị Lê (Học viện An ninh nhân dân)

Thời gian: 9h, Thứ 4 ngày 04/01/2023 theo hình thức hybrid (kết hợp trực tiếp và trực tuyến).

Địa điểm: Phòng 302 nhà A5 Viện Toán học.

Link seminar: meet.google.com/gaq-qqdn-wzh

Tóm tắt báo cáo: Bài toán đường đi ngắn nhất hình học trong các không gian thấp chiều được hiểu là tính toán một đường đi ngắn nhất nối hai điểm trong một miền hình học cho trước trong 2D hoặc 3D. Việc phân loại các bài toán đường đi ngắn nhất trong không gian thấp chiều phát sinh từ một số tham số xác định bài toán. Người ta gọi một bài toán là bài toán đường đi có ràng buộc ngắn nhất nếu có các ràng buộc của đường đi, miền hình học đầu vào, khoảng cách được sử dụng cho hàm mục tiêu hoặc chiều của bài toán, v.v. Trong luận án này, ba dạng sau đây của bài toán đường đi ngắn nhất có ràng buộc được trình bày:

  1. Bài toán sơi dây lồi
  2. Bài toán đường đi ngắn nhất dọc theo một dãy các chùm đoạn thẳng và ứng dụng của nó vào bài toán lập đường đi cho robot tự hành
  3. Bài toán tìm đường đi ngắn nhất ít dốc trên bề mặt địa hình đa diện

Để giải quyết ba bài toán này, chúng tôi sử dụng cách tiếp cận bắn nhiều lần.

Phương pháp này xuất phát từ ý tưởng của phương pháp bắn nhiều lần được đề xuất để giải quyết bài toán giá trị biên của phương trình vi phân thường và bài toán điều khiển tối ưu. Sử dụng ý tưởng đó, phương pháp bắn nhiều lần trong hình học tính toán lần đầu tiên được An, Hải và Hoài đưa ra năm 2013 để tìm ra các đường đi ngắn nhất trong đa giác đơn. Sau đó họ mở rộng cách tiếp cận để giải quyết bài toán đường đi ngắn nhất trên bề mặt khối đa diện lồi trong 3D. Phương pháp này cũng được An và Trang sử dụng thành công để tìm đường đi ngắn nhất giảm dần trên bề mặt địa hình. Mục tiêu của luận án tập trung vào việc áp dụng cách tiếp cận bắn nhiều lần cho ba bài toán đường đi ngắn nhất có ràng buộc nói trên, đưa ra các thuật toán tương ứng và thực thi chúng.

Back