Bài Toán Tìm Đường Ngắn Nhất Trên Đồ Thị Cho Hai Đối Tượng Có Ràng Buộc Khoảng Cách

Luận văn thạc sĩ trình bày bài toán tìm đường ngắn nhất trên đồ thị cho hai đối tượng với ràng buộc khoảng cách, ứng dụng trong khoa học máy tính.

• Tác giả: Trần Nhật Hoàng Anh
• Người hướng dẫn: PGS. Trần Văn Hoài
• Trường học: Đại học Bách Khoa - ĐHQG-HCM
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Bài Toán Tìm Đường Ngắn Nhất Trên Đồ Thị Cho Hai Đối Tượng Có Ràng Buộc Khoảng Cách
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2018
• Địa điểm: Thành Phố Hồ Chí Minh

Tóm tắt

I. Tổng Quan Về Bài Toán Tìm Đường Đi Ngắn Nhất Giới Thiệu

Bài toán tìm đường đi ngắn nhất là một vấn đề cốt lõi trong nhiều lĩnh vực, từ navigation cho robot đến quy hoạch đường đi trong game AI. Trong môi trường tĩnh, bài toán này trở nên tương đối dễ giải quyết, nhưng khi có nhiều đối tượng cùng di chuyển và tương tác, độ phức tạp tăng lên đáng kể. Đặc biệt, khi các đối tượng này có ràng buộc về khoảng cách, bài toán trở thành một thách thức lớn hơn. Theo nghiên cứu của Trần Nhật Hoàng Anh, bài toán được đặt ra là tìm đường đi cho hai robot trong môi trường tĩnh, sao cho chúng luôn duy trì một khoảng cách nhất định. Vấn đề này không chỉ là tối ưu hóa đường đi mà còn là đảm bảo sự phối hợp giữa các đối tượng. Bài toán tìm đường ngắn nhất cho hai đối tượng có ràng buộc về khoảng cách không chỉ là một bài toán lý thuyết, nó có ứng dụng thực tế trong nhiều lĩnh vực. Ví dụ, trong lĩnh vực robotics, nó có thể được sử dụng để điều khiển hai robot làm việc cùng nhau. Trong lĩnh vực game development, nó có thể được sử dụng để tạo ra các nhân vật AI di chuyển một cách phối hợp.

1.1. Tầm Quan Trọng của Thuật Toán Tìm Đường Hiệu Quả

Sự hiệu quả của thuật toán tìm đường có ảnh hưởng trực tiếp đến hiệu suất của các hệ thống sử dụng chúng. Một thuật toán chậm chạp có thể làm chậm trễ hoạt động của robot, làm giảm trải nghiệm người dùng trong game hoặc làm tăng chi phí trong các ứng dụng logistics. Vì vậy, việc nghiên cứu và phát triển các thuật toán hiệu quả là rất quan trọng. Một thuật toán tìm đường hiệu quả có thể giúp robot di chuyển nhanh hơn, chính xác hơn và tiêu thụ ít năng lượng hơn. Trong game, một thuật toán hiệu quả có thể tạo ra các nhân vật AI thông minh hơn và phản ứng nhanh hơn. Trong logistics, một thuật toán hiệu quả có thể giúp tối ưu hóa lộ trình vận chuyển và giảm chi phí.

1.2. Ứng Dụng Thực Tế Từ Robot Đến Game và Tự Động Hóa

Ứng dụng của bài toán tìm đường trải dài trên nhiều lĩnh vực. Trong robotics, nó được sử dụng để điều khiển robot di chuyển trong môi trường phức tạp, tránh chướng ngại vật và thực hiện các nhiệm vụ cụ thể. Trong game, nó được sử dụng để tạo ra các nhân vật AI di chuyển một cách tự nhiên và tương tác với môi trường. Trong tự động hóa, nó được sử dụng để tối ưu hóa lộ trình vận chuyển và điều khiển các thiết bị tự động. Các thuật toán như A* và Dijkstra được sử dụng rộng rãi trong các ứng dụng này. Trong lĩnh vực automotive, bài toán tìm đường được áp dụng trong các hệ thống autonomous driving, giúp xe tự hành di chuyển an toàn và hiệu quả trên đường.

II. Thách Thức Trong Tìm Đường Ngắn Nhất Cho Hai Đối Tượng

Việc tìm đường đi ngắn nhất cho hai đối tượng trong một môi trường tĩnh không chỉ đơn thuần là tìm hai đường đi riêng lẻ. Thách thức chính nằm ở việc đảm bảo rằng hai đối tượng luôn duy trì một khoảng cách nhất định trong suốt quá trình di chuyển. Điều này đòi hỏi phải có sự phối hợp giữa hai đối tượng, và việc tối ưu hóa trở nên phức tạp hơn nhiều. Theo luận văn của Trần Nhật Hoàng Anh, bài toán này có thể được mô hình hóa thành một bài toán tối ưu hóa trên đồ thị, trong đó mỗi đỉnh của đồ thị đại diện cho một vị trí có thể của hai đối tượng. Việc tìm đường đi ngắn nhất trở thành việc tìm một chuỗi các đỉnh liên tiếp trên đồ thị sao cho tổng chi phí của các cạnh là nhỏ nhất và các ràng buộc về khoảng cách được thỏa mãn. Thêm vào đó, việc xử lý collision avoidance cũng là một thách thức quan trọng.

2.1. Ràng Buộc Về Khoảng Cách Duy Trì Sự Phối Hợp

Việc duy trì khoảng cách giữa hai đối tượng tạo ra một ràng buộc phức tạp. Các thuật toán phải đảm bảo rằng hai đối tượng không quá gần nhau (tránh va chạm) và không quá xa nhau (duy trì sự phối hợp). Điều này đòi hỏi phải có sự điều chỉnh liên tục trong quá trình di chuyển. Các ràng buộc về khoảng cách có thể được biểu diễn dưới dạng các bất đẳng thức trong bài toán tối ưu hóa. Việc giải quyết bài toán này đòi hỏi phải sử dụng các kỹ thuật tối ưu hóa phức tạp, chẳng hạn như quy hoạch tuyến tính nguyên (ILP).

2.2. Collision Avoidance Tránh Va Chạm Trong Môi Trường Tĩnh

Tránh va chạm là một yêu cầu cơ bản trong bài toán tìm đường. Các thuật toán phải đảm bảo rằng hai đối tượng không va chạm với nhau hoặc với các chướng ngại vật trong môi trường. Điều này đòi hỏi phải có một mô hình chính xác về môi trường và các thuật toán để phát hiện và tránh va chạm. Các kỹ thuật collision avoidance có thể bao gồm việc sử dụng các heuristic để ước lượng rủi ro va chạm và điều chỉnh đường đi để tránh các khu vực nguy hiểm. Việc tích hợp collision avoidance vào bài toán tối ưu hóa làm tăng thêm độ phức tạp của bài toán.

2.3. Tối Ưu Hóa Chi Phí Đường Đi Tìm Đường Đi Ngắn Nhất

Mục tiêu chính của bài toán là tìm đường đi ngắn nhất cho hai đối tượng. Điều này đòi hỏi phải tối ưu hóa chi phí của đường đi, thường được đo bằng tổng khoảng cách mà hai đối tượng di chuyển. Tuy nhiên, việc tối ưu hóa chi phí đường đi phải được thực hiện đồng thời với việc thỏa mãn các ràng buộc về khoảng cách và collision avoidance. Điều này tạo ra một bài toán tối ưu hóa đa mục tiêu, đòi hỏi phải có các kỹ thuật tối ưu hóa phức tạp để giải quyết.

III. Giải Pháp Thuật Toán A và Biến Thể Cho Bài Toán

Thuật toán A* là một trong những thuật toán tìm đường phổ biến nhất và được sử dụng rộng rãi trong nhiều lĩnh vực. A* sử dụng một hàm heuristic để ước lượng chi phí từ một đỉnh hiện tại đến mục tiêu, giúp nó tìm kiếm một cách hiệu quả hơn. Trong bài toán tìm đường cho hai đối tượng, A* có thể được mở rộng để xem xét các ràng buộc về khoảng cách và collision avoidance. Một biến thể của A* có thể được sử dụng để tìm kiếm trên một đồ thị mà mỗi đỉnh đại diện cho một vị trí có thể của hai đối tượng. Hàm heuristic có thể được thiết kế để ước lượng chi phí đến mục tiêu, đồng thời xem xét các ràng buộc về khoảng cách và collision avoidance. Theo Trần Nhật Hoàng Anh, việc sử dụng cây tứ phân (quadtree) có thể giúp biểu diễn môi trường một cách hiệu quả và tăng tốc độ tìm kiếm.

3.1. Sử Dụng Hàm Heuristic Để Tối Ưu Hóa Tìm Kiếm

Hàm heuristic đóng vai trò quan trọng trong hiệu suất của A*. Một hàm heuristic tốt có thể giúp A* tìm thấy đường đi ngắn nhất một cách nhanh chóng, trong khi một hàm heuristic kém có thể làm chậm quá trình tìm kiếm hoặc thậm chí dẫn đến kết quả không tối ưu. Hàm heuristic phải được thiết kế cẩn thận để ước lượng chính xác chi phí đến mục tiêu, đồng thời xem xét các ràng buộc của bài toán. Việc sử dụng khoảng cách Euclid hoặc khoảng cách Manhattan là các lựa chọn phổ biến cho hàm heuristic.

3.2. Biểu Diễn Môi Trường Bằng Cây Tứ Phân Quadtree

Cây tứ phân là một cấu trúc dữ liệu phân cấp được sử dụng để biểu diễn môi trường một cách hiệu quả. Cây tứ phân chia môi trường thành các ô vuông nhỏ hơn, cho phép thuật toán tập trung vào các khu vực quan trọng hơn. Việc sử dụng cây tứ phân có thể giúp giảm đáng kể số lượng đỉnh cần xem xét trong quá trình tìm kiếm, tăng tốc độ tìm kiếm. Theo Trần Nhật Hoàng Anh, cây tứ phân có thể được sử dụng để biểu diễn môi trường trong bài toán tìm đường cho hai đối tượng.

3.3. Triển Khai A Với Ràng Buộc Khoảng Cách và Va Chạm

Việc triển khai A* với các ràng buộc về khoảng cách và va chạm đòi hỏi phải có sự điều chỉnh trong quá trình tìm kiếm. Khi một đỉnh mới được xem xét, thuật toán phải kiểm tra xem các ràng buộc này có được thỏa mãn hay không. Nếu không, đỉnh đó sẽ bị loại bỏ. Việc kiểm tra các ràng buộc có thể làm chậm quá trình tìm kiếm, nhưng nó đảm bảo rằng kết quả là một đường đi hợp lệ. Các kỹ thuật như phạt (penalty) có thể được sử dụng để khuyến khích thuật toán tìm kiếm các đường đi thỏa mãn các ràng buộc.

IV. Phương Pháp Biến Đổi Đồ Thị Kết Hợp Cây Tứ Phân Hướng Tiếp Cận Mới

Một phương pháp tiếp cận khác để giải quyết bài toán tìm đường cho hai đối tượng là sử dụng phương pháp biến đổi đồ thị kết hợp cây tứ phân. Phương pháp này chuyển đổi môi trường thành một đồ thị, trong đó mỗi đỉnh của đồ thị đại diện cho một vị trí có thể của hai đối tượng và mỗi cạnh đại diện cho một sự di chuyển có thể giữa hai vị trí. Cây tứ phân được sử dụng để biểu diễn môi trường và giúp giảm số lượng đỉnh trong đồ thị. Theo Trần Nhật Hoàng Anh, việc biến đổi đồ thị có thể giúp thuật toán tìm đường tìm kiếm một cách hiệu quả hơn bằng cách tập trung vào các khu vực quan trọng hơn của môi trường. Phương pháp này kết hợp ưu điểm của cả lý thuyết đồ thị và cell decomposition, tạo ra một giải pháp hiệu quả cho bài toán.

4.1. Xây Dựng Đồ Thị Từ Môi Trường Sử Dụng Cây Tứ Phân

Việc xây dựng đồ thị từ môi trường sử dụng cây tứ phân là một bước quan trọng trong phương pháp này. Cây tứ phân được sử dụng để chia môi trường thành các ô vuông nhỏ hơn, và mỗi ô vuông được biểu diễn bởi một đỉnh trong đồ thị. Các cạnh trong đồ thị đại diện cho các sự di chuyển có thể giữa các ô vuông. Quá trình xây dựng đồ thị phải đảm bảo rằng các ràng buộc về khoảng cách và va chạm được xem xét. Điều này có thể được thực hiện bằng cách loại bỏ các cạnh đại diện cho các sự di chuyển không hợp lệ.

4.2. Áp Dụng Thuật Toán Tìm Đường Trên Đồ Thị Đã Biến Đổi

Sau khi đồ thị đã được xây dựng, thuật toán tìm đường có thể được áp dụng để tìm đường đi ngắn nhất cho hai đối tượng. Thuật toán A* là một lựa chọn phổ biến, nhưng các thuật toán khác như Dijkstra hoặc BFS cũng có thể được sử dụng. Thuật toán phải xem xét các ràng buộc về khoảng cách và va chạm trong quá trình tìm kiếm. Điều này có thể được thực hiện bằng cách điều chỉnh hàm heuristic hoặc bằng cách sử dụng các kỹ thuật phạt.

4.3. Ưu Điểm Của Phương Pháp Biến Đổi Đồ Thị So Với Các Phương Pháp Khác

Phương pháp biến đổi đồ thị có một số ưu điểm so với các phương pháp khác. Nó có thể xử lý các môi trường phức tạp với nhiều chướng ngại vật. Nó có thể xem xét các ràng buộc về khoảng cách và va chạm một cách hiệu quả. Và nó có thể được sử dụng để tìm đường đi ngắn nhất cho nhiều đối tượng. Tuy nhiên, phương pháp này cũng có một số nhược điểm. Việc xây dựng đồ thị có thể tốn thời gian, và đồ thị có thể trở nên rất lớn đối với các môi trường phức tạp. Do đó, việc tối ưu hóa quá trình xây dựng đồ thị là rất quan trọng.

V. Ứng Dụng và Thực Nghiệm Đánh Giá Hiệu Quả Giải Pháp Tìm Đường

Để đánh giá hiệu quả của các giải pháp tìm đường, các thí nghiệm thực tế và mô phỏng là cần thiết. Các thí nghiệm có thể được thực hiện trên robot thực tế hoặc trong môi trường mô phỏng. Các thí nghiệm nên được thiết kế để đánh giá các khía cạnh khác nhau của giải pháp, chẳng hạn như tốc độ, độ chính xác và khả năng xử lý các môi trường phức tạp. Kết quả của các thí nghiệm có thể được sử dụng để so sánh các giải pháp khác nhau và để xác định các lĩnh vực cần cải thiện. Theo Trần Nhật Hoàng Anh, các thí nghiệm trên môi trường thực tế cho thấy rằng các giải pháp đề xuất có thể tìm đường đi một cách hiệu quả và chính xác trong nhiều tình huống khác nhau.

5.1. Thiết Lập Môi Trường Thí Nghiệm và Các Tiêu Chí Đánh Giá

Việc thiết lập môi trường thí nghiệm và các tiêu chí đánh giá là rất quan trọng để đảm bảo rằng các thí nghiệm là có ý nghĩa và có thể so sánh được. Môi trường thí nghiệm nên được thiết kế để phản ánh các tình huống thực tế mà giải pháp sẽ được sử dụng. Các tiêu chí đánh giá nên được chọn để đo lường các khía cạnh quan trọng nhất của giải pháp, chẳng hạn như tốc độ, độ chính xác và khả năng xử lý các môi trường phức tạp. Các tiêu chí đánh giá có thể bao gồm thời gian tìm đường, độ dài đường đi, số lượng va chạm và mức tiêu thụ năng lượng.

5.2. So Sánh Các Thuật Toán Khác Nhau Về Tốc Độ và Độ Chính Xác

Việc so sánh các thuật toán khác nhau về tốc độ và độ chính xác là một bước quan trọng trong quá trình đánh giá. Các thuật toán nên được thử nghiệm trong cùng một môi trường và sử dụng cùng một tiêu chí đánh giá. Kết quả của các thí nghiệm có thể được sử dụng để xác định thuật toán nào phù hợp nhất cho một tình huống cụ thể. Các thuật toán nên được so sánh về thời gian tìm đường, độ dài đường đi, số lượng va chạm và mức tiêu thụ năng lượng.

5.3. Phân Tích Kết Quả và Đề Xuất Cải Tiến Cho Giải Pháp

Việc phân tích kết quả của các thí nghiệm và đề xuất cải tiến cho giải pháp là một bước quan trọng trong quá trình phát triển. Kết quả của các thí nghiệm có thể được sử dụng để xác định các lĩnh vực mà giải pháp hoạt động tốt và các lĩnh vực cần cải thiện. Các đề xuất cải tiến có thể bao gồm việc điều chỉnh các tham số của thuật toán, thay đổi cấu trúc dữ liệu hoặc sử dụng một thuật toán khác. Việc phân tích kết quả và đề xuất cải tiến nên được thực hiện một cách liên tục trong suốt quá trình phát triển.

VI. Kết Luận và Hướng Phát Triển Tương Lai Của Bài Toán

Bài toán tìm đường cho hai đối tượng với ràng buộc khoảng cách là một vấn đề quan trọng và đầy thách thức. Các giải pháp đã được đề xuất, như thuật toán A* và phương pháp biến đổi đồ thị, có thể giải quyết bài toán một cách hiệu quả trong nhiều tình huống khác nhau. Tuy nhiên, vẫn còn nhiều lĩnh vực cần cải thiện, chẳng hạn như khả năng xử lý các môi trường động và phức tạp hơn. Trong tương lai, bài toán này sẽ tiếp tục đóng vai trò quan trọng trong nhiều lĩnh vực, từ robotics và game AI đến tự động hóa và logistics. Theo Trần Nhật Hoàng Anh, các hướng phát triển có thể bao gồm việc sử dụng các kỹ thuật học máy để tối ưu hóa thuật toán và việc phát triển các giải pháp có thể xử lý các ràng buộc phức tạp hơn.

6.1. Tóm Tắt Các Kết Quả Đạt Được và Những Hạn Chế Còn Tồn Tại

Các giải pháp đã được đề xuất có thể giải quyết bài toán tìm đường cho hai đối tượng với ràng buộc khoảng cách một cách hiệu quả trong nhiều tình huống khác nhau. Tuy nhiên, vẫn còn một số hạn chế cần được giải quyết. Các giải pháp hiện tại có thể không hiệu quả trong các môi trường động hoặc phức tạp. Chúng cũng có thể không thể xử lý các ràng buộc phức tạp hơn, chẳng hạn như các ràng buộc về thời gian hoặc năng lượng. Việc giải quyết các hạn chế này là một thách thức quan trọng cho tương lai của bài toán.

6.2. Hướng Nghiên Cứu Tương Lai Học Máy Môi Trường Động Ràng Buộc Phức Tạp

Trong tương lai, có nhiều hướng nghiên cứu có thể được theo đuổi để cải thiện các giải pháp tìm đường cho hai đối tượng với ràng buộc khoảng cách. Một hướng là sử dụng các kỹ thuật học máy để tối ưu hóa thuật toán và để học các chiến lược tìm đường hiệu quả. Một hướng khác là phát triển các giải pháp có thể xử lý các môi trường động, nơi các chướng ngại vật có thể di chuyển hoặc thay đổi vị trí. Một hướng nữa là phát triển các giải pháp có thể xử lý các ràng buộc phức tạp hơn, chẳng hạn như các ràng buộc về thời gian hoặc năng lượng. Những hướng nghiên cứu này có thể dẫn đến các giải pháp hiệu quả hơn và linh hoạt hơn cho bài toán tìm đường.

6.3. Tầm Quan Trọng Của Bài Toán Trong Bối Cảnh Trí Tuệ Nhân Tạo

Bài toán tìm đường đóng vai trò quan trọng trong bối cảnh trí tuệ nhân tạo (AI). Các giải pháp tìm đường được sử dụng để điều khiển robot, tạo ra các nhân vật AI trong game và tối ưu hóa lộ trình vận chuyển trong logistics. Khi AI tiếp tục phát triển, bài toán tìm đường sẽ trở nên quan trọng hơn bao giờ hết. Các giải pháp tìm đường hiệu quả và linh hoạt sẽ là cần thiết để tạo ra các hệ thống AI thông minh hơn và hữu ích hơn. Việc nghiên cứu và phát triển các giải pháp tìm đường là một lĩnh vực quan trọng trong AI và có tiềm năng tạo ra những tác động lớn đến nhiều lĩnh vực khác nhau.

Trích đoạn nội dung tài liệu

đặt vấn đề như là tìm kiếm trên N đồ thị đường đi tối ưu thỏa mãn ràng buộc khoảng cách. Giải pháp DPC lặp lại việc tìm kiếm trên các đồ thị này với sự gia tăng dần dần của các ràng buộc khoảng cách cho đến khi đạt được sự hội tụ đầy đủ. Các ràng buộc này là ràng buộc mềm, được chấp nhận vi phạm theo hàm phạt (penalty function) kiểu kỹ thuật tăng cường đối số Lagrange. Các tác giả đã chứng minh rằng dưới điều kiện cụ thể giải thuật đảm bảo hội tụ thành giải pháp tối ưu.

Thực nghiệm cho thấy thuật toán hội tụ nhanh chóng cho các nhóm tối đa sáu đối tượng cùng hoạt động trong môi trường lộn xộn. Và các kết quả mô phỏng cũng cho thấy việc triển khai và thực hiện thuật toán trên ba robot tìm đường trên môi trường lộn xộn trong khi tuân theo các giới hạn khoảng cách theo tham số thời gian. Các tác giả mở rộng bài toán này trong [40]: mỗi robot được cho một tập hợp các tác vụ không có thứ tự mà nó phải thực thi trước khi nó di chuyển đến mục tiêu của nó, trong khi các hàm mục tiêu, các ràng buộc mềm về khoảng cách và độ phức tạp được kế thừa từ giải thuật DPC trên. bằng cách xây dựng đồ thị trạng thái - tác vụ và đề xuất một hàm heuristic hiệu quả để thực hiện tìm kiếm trên đồ thị này.

Giải thuật sẽ quyết định thứ tự thực hiện các tác vụ sao cho đạt được lời giải tối 6 Luận văn thạc sĩ - Khoa học máy tính ưu đồng thời các ràng buộc khoảng cách được thỏa mãn cùng với việc thực hiện thành công các tác vụ. Mariusz Glabowski và các cộng sự [26], Yogita Gigras, Kusum Gupta[27] cho thấy rằng các giải thuật Meta-Heuristic đã giải quyết bài toán tìm đường đi ngắn nhất cho nhiều đối tượng khá hiệu quả và cho lời giải gần tối ưu. Đây là một bài toán tối ưu tổ hợp, dạng bài toán có độ phức tạp tính toán cao thuộc lớp NP khó. Kết quả thực nghiệm cho thấy giải thuật đàn kiến vượt trội hơn so với tối ưu hóa bầy hạt trong thời gian tính toán.

Bên cạnh đó còn có giải thuật mô phỏng luyện kim SA (Simulated Annealing), giải thuật di truyền GA (Genetic Algorithm) được áp dụng cho bài toán này bởi các tác giả O. Với độ phức tạp tính toán cao của các bài toán tối ưu tổ hợp cũng như đòi hỏi về mặt thời gian, việc giải các bài toán này với tính chất tuần tự của giải thuật sẽ gặp phải những vấn đề về thời gian thực hiện chương trình, tốc độ xử lý, khả năng lưu trữ của bộ nhớ, xử lý dữ liệu với quy mô lớn. Kích thước bài toán tăng lên và không gian tìm kiếm càng lớn yêu cầu cần phải song song hóa các giải thuật [29] để tăng tốc độ và hiệu quả của giải thuật. Yongbo Chen, Jianqiao Yu và hai cộng sự khác [24] trình bày một thuật toán hiệu quả và khả thi cho bài toán tìm đường cho nhiều máy bay không người lái (multi-UAVs) trong môi trường thực tế biết trước.

Các tác giả cải tiến phương pháp artificial potential field. Để tránh đụng độ giữa các UAV, các tác giả đưa ra khái niệm định dạng, quy tắc để thay đổi định dạng và quá trình tái cấu trúc; tức là các UAV luôn di chuyển theo một định dạng xác định trước, tuy nhiên trong một số trường hợp chúng có thể rời khỏi đội hình và tính độ lỗi cho đường đi đó. Bài báo này áp dụng định dạng hình xương cá và kích thước của nó được thể hiện trong hình 2. Mô hình tìm đường cho lead plane được thực hiện độc lập trước, các wingman cần phải theo các vị trí được gọi là "điểm mục tiêu ảo" để duy trì định dạng.

Yếu tố khoảng 7 Luận văn thạc sĩ - Khoa học máy tính Hình 2.1: Sơ đồ mô hình đa UAV [24] cách giữ các UAV là ràng buộc mềm. Kết quả của mô phỏng thực nghiệm đã chứng minh rằng phương pháp đề xuất có khả năng tìm đường tốt và khắc phục được vấn đề "vùng chết" trong vấn đề tìm đường, đồng thời chỉ ra rằng các sai số định dạng lớn trong khu vực ảnh hưởng của các chướng ngại vật, và nhỏ ở khu vực không có chướng ngại vật. Wagner và Choset [25] hiện thực giải thuật M* trên không gian được biểu diễn như hệ tọa độ có số chiều thay đổi cho bài toán lập kế hoạch đường đi cho nhiều robot (multirobot path planning). Đây là một bài toán tối ưu về robot trong lĩnh vực trí tuệ nhân tạo và kết quả của bài toán là n đường đi tối ưu cho n robot đồng thời tránh được sự đụng độ giữa các robot.

Các giải thuật để giải bài toán này có thể được chia thành hai loại: ghép và tách các robot. Mỗi loại đều có ưu điểm và nhược điểm riêng. Các tác giả đã khai thác 8 Luận văn thạc sĩ - Khoa học máy tính các lợi ích của mỗi loại giải thuật, kết hợp chúng để đưa ra lời giải M*. M* được chứng minh là thực sự đầy đủ và tối ưu, đồng thời thực nghiệm cũng cho thấy độ phức tạp trung bình của nó thì nhỏ hơn độ phức tạp trung bình của giải thuật A*.

Tuy nhiên, M* có một điểm yếu. Nó sẽ thất bại trong trường hợp có một số lượng robot đủ lớn đổ dồn về một điểm, bởi vì khi đó M* phải tìm kiếm trên một không gian với số chiều quá lớn. Số lượng robot bao nhiêu là đủ lớn và giải pháp khả thi cho trường hợp này rM* cũng được nghiên cứu tiếp theo. Và dĩ nhiên để tìm được lời giải với những ràng buộc về bộ nhớ máy tính và thời gian, rM* không còn đảm bảo được tính đầy đủ và tối ưu của M*.2 Các phương pháp tìm đường (path – plan- ning) cho một robot đã được nghiên cứu Các phương pháp tổ hợp gồm các giải thuật tìm đường cổ điển sinh ra một đồ thị liên thông dựa trên các tính toán hình học, được gọi là roadmap, tượng trưng cho sự liên thông của workspace: đồ thị tầm nhìn (visibility graph), sơ đồ Voronoi (Voronoi diagram), cell decomposition.

Dựa trên tính toán hình học chính xác, các giải thuật thuộc phương pháp này đều có tính đầy đủ, có nghĩa là cho bất kỳ bài toán cụ thể nào, thuật toán sẽ tìm ra lời giải tốt nhất hoặc sẽ báo cáo chính xác rằng không có lời giải nào tồn tại. Một vài giải thuật thì hiệu quả và dễ hiện thực. Tuy nhiên một vài giải thuật thì đánh đổi tính đầy đủ với tính thực tế, tức là nó có thể có độ phức tạp thời gian tuyệt với nhưng lại khó hiện thực. Định nghĩa 2: Một roadmap G(V, E) là một đồ thị được dùng để rời rạc hóa không gian liên tục Xf ree sao cho thỏa mãn hai tính chất sau: − Khả năng tiếp cận: Bất kỳ điểm nào thuộc Xf ree thì đều có thể đến được từ một đỉnh nào đó của roadmap.

Cho điểm cấu hình q ∈ Xf ree , thì luôn tìm được một cách dễ dàng và hiệu quả π[0, 1] → Xf ree sao cho π(0) = q 9 Luận văn thạc sĩ - Khoa học máy tính và π(1) = ν với ν ∈ V. − Bảo tồn liên thông: đảm bảo tính liên thông của free configuration space. Cho hai điểm cấu hình q1 , q2 ∈ Xf ree theo điều kiện 1 tìm được 2 đỉnh v1 , v2 ∈ V , nếu tồn tại đường đi π[0, 1] → Xf ree sao cho π(0) = q1 và π(1) = q2 thì tồn tại π 0 [0, 1] → G sao cho π 0 (0) = v1 và π 0 (1) = v2 .1 Đồ thị tầm nhìn Đồ thị tầm nhìn là một trong những phương pháp tìm đường sớm nhất và xây dựng các đường dẫn thông qua kết nối mỗi cặp đỉnh của các chướng ngại vật bằng một đường thẳng mà không đi qua bên trong các chướng ngại vật. Phân tích đồ thị tầm nhìn là một bài toán đầy thách thức vì cấu trúc tổ hợp của đồ thị tầm nhìn vẫn chưa được hiểu đầy đủ.

Định nghĩa 3: Đồ thị tầm nhìn là một đồ thị vô hướng G (V, E) được xác định cụ thể như sau: − V là tập hợp các đỉnh của vật cản và điểm khởi đầu, mục tiêu mà robot cần di chuyển. − E là tập con của VxV, hai đỉnh của G tạo thành một cạnh khi và chỉ khi đoạn thẳng hoặc là cạnh của vật cản hoặc hai đỉnh có thể đi được đến nhau mà không bị cản trở bởi bất kì vật cản nào. Input: một tập n điểm là đỉnh của các chướng ngại vật, điểm khởi đầu, điểm kết thúc. Output: một danh sách các điểm có thể nhìn thấy được của mỗi điểm Một số thuật toán sinh đồ thị tầm nhìn với độ phức tạp thời gian được cải tiến - Naı̈ve algorithm - Cách đơn giản nhất để xây dựng đồ thị tầm nhìn là xét mỗi cặp đỉnh (u,v) có giao nhau với bất kỳ cạnh nào của vật cản hay không.

10 Luận văn thạc sĩ - Khoa học máy tính Hình 2.2: Một ví dụ tìm đường sử dụng đồ thị tầm nhìn. [12] Nếu không, hai đỉnh u, v là hai đỉnh có thể nhìn thấy nhau và cạnh (u,v) được thêm vào tập cạnh của đồ thị tầm nhìn. Dĩ nhiên là để hoàn thành được đồ thị tầm nhìn thì quá trình kiểm tra này phải lặp lại với tất cả cặp đỉnh, số cặp đỉnh phải xét là n2 (n là số đỉnh). Giải thuật có độ phức tạp thời gian là O(n3 ).

Đối với lưu trữ, giải thuật cần ít nhất là O(n) cho input, và O(|e|) không gian bộ nhớ để lưu lại đồ thị tầm nhìn. Năm 1979, Lozano-Perez và Wesley, trình bày giải thuật Naı̈ve cho khối đa diện [13]. - Thuật toán của Lee lần đầu tiên trình bày một giải pháp mới và có ý nghĩa, chạy trong thời gian O(n2 log n). Ông đã cải tiến giải thuật Naı̈ve bằng cách sử dụng một biến thể của thuật toán sweep-line, kết hợp cấu trúc dữ liệu là cây tìm kiếm nhị phân để xử lý việc chèn và xóa danh sách cạnh.

Nhờ sử dụng thuật toán sắp xếp tối ưu, thao tác tìm kiếm, chèn và xóa cạnh có độ phức tạp thời gian là O(log n).