Tổng quan nghiên cứu

Trong kỷ nguyên tự động hóa và công nghiệp 4.0, hệ thống điều khiển đa tác nhân (Multi-Agent Systems) đang trở thành trọng tâm phát triển với tốc độ tăng trưởng hơn 15% mỗi năm trong các ứng dụng logistics, cứu hộ và quân sự. Vấn đề cốt lõi đặt ra là làm thế nào để điều phối chuyển động của nhiều robot tự hành cùng hoạt động trong không gian tĩnh hai chiều có vật cản, vừa đảm bảo tránh va chạm tuyệt đối, vừa duy trì liên lạc ổn định. Khi hai robot hoạt động theo cặp để thực hiện nhiệm vụ trinh sát hoặc vận chuyển hàng hóa, việc duy trì khoảng cách vật lý tối ưu là điều kiện tiên quyết. Tuy nhiên, việc tìm đường đi ngắn nhất đồng thời cho cả hai đối tượng thường dẫn đến bùng nổ tổ hợp trong không gian trạng thái tích hợp $N = \dim(C_1) + \dim(C_2)$, khiến các thuật toán cổ điển rơi vào độ phức tạp hàm mũ.

Luận văn thạc sĩ chuyên ngành Khoa học Máy tính của học viên Trần Nhật Hoàng Anh, dưới sự hướng dẫn khoa học của PGS. Trần Văn Hoài tại Trường Đại học Bách khoa – Đại học Quốc gia Thành phố Hồ Chí Minh, đã giải quyết triệt để thách thức này. Đề tài tập trung nghiên cứu và đề xuất giải pháp tối ưu cho bài toán tìm đường ngắn nhất tránh vật cản cho hai robot có ràng buộc khoảng cách cố định (luôn cách nhau đúng một cạnh trên đồ thị) và tích hợp cơ chế cho phép một robot tạm dừng trong khi robot kia di chuyển.

Nghiên cứu được triển khai toàn diện trong thời gian 11 tháng (từ ngày 10/07/2017 đến ngày 17/06/2018) và bảo vệ thành công vào ngày 17/07/2018. Ý nghĩa khoa học và thực tiễn của công trình thể hiện qua việc giảm độ phức tạp tính toán từ mức hàm mũ xuống thời gian đa thức $O(|V_H| \log |V_H| + |E_H|)$, đảm bảo tỷ lệ tránh va chạm đạt 100% và tìm ra nghiệm đường đi ngắn nhất tương đương với phương pháp quy hoạch toán học tối ưu toàn cục.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng vững chắc của lý thuyết điều khiển robot hiện đại, lý thuyết đồ thị và quy hoạch toán học với các mô hình và khái niệm cốt lõi:

Thứ nhất, mô hình Không gian cấu hình (Configuration Space - C-space): Không gian hoạt động tự do $C_{free}$ được xác định bằng cách loại bỏ vùng không gian chướng ngại vật $C_{obs}$ khỏi không gian cấu hình tổng thể $C$, tức là $C_{free} = C \setminus C_{obs}$. Đối với hệ hai robot, không gian trạng thái tích hợp được định nghĩa là $X = C_1 \times C_2$, trong đó vùng va chạm $X_{obs}$ bao gồm va chạm giữa robot với chướng ngại vật và va chạm trực tiếp giữa robot với robot.

Thứ hai, lý thuyết biến đổi đồ thị và đồ thị đường (Line Graph): Từ đồ thị môi trường ban đầu $G(V, E)$, nghiên cứu xây dựng đồ thị trạng thái chuyển tiếp $H(V_H, E_H)$. Mỗi đỉnh trong $H$ đại diện cho một cặp vị trí hợp lệ của hai robot thỏa mãn điều kiện cách nhau đúng một cạnh. Cấu trúc cạnh của $H$ phản ánh các bước di chuyển hợp lệ: cả hai robot cùng đổi vị trí hoặc một robot di chuyển trong khi robot còn lại tạm dừng.

Thứ ba, thuật toán tìm kiếm Heuristic A* và Cây tứ phân (Quadtree): Thuật toán A* áp dụng hàm lượng giá $f(x) = g(x) + h(x)$ với hàm $h(x)$ là khoảng cách Euclid cải biên để định hướng tìm kiếm trên đồ thị trạng thái $H$. Cấu trúc cây tứ phân chia không gian 2D thành 4 vùng con đệ quy để phân hoạch môi trường xấp xỉ (Approximate Cell Decomposition), giúp xác định nhanh các ô lân cận và xây dựng lộ trình di chuyển.

Thứ tư, mô hình Quy hoạch tuyến tính nguyên nhị phân (0-1 Binary Integer Linear Programming - BILP): Bài toán tìm đường được mô hình hóa toán học với hàm mục tiêu tối thiểu hóa tổng quãng đường di chuyển của hai robot dưới các hệ ràng buộc bảo toàn luồng, không đụng độ và duy trì khoảng cách tại mỗi bước thời gian $t$.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm mô phỏng kết hợp kiểm chứng lý thuyết toán học chặt chẽ:

Nguồn dữ liệu và cỡ mẫu: Thực nghiệm được tiến hành trên tập dữ liệu gồm hơn 50 cấu hình bản đồ không gian hai chiều tĩnh với số lượng chướng ngại vật biến thiên từ 10 đến 120 vật cản đa giác lồi. Kích thước đồ thị môi trường được khảo sát từ 64 đỉnh đến 512 đỉnh trên hai dạng cấu trúc địa hình chính: đồ thị hình học dày (dense geometric graph) và đồ thị hình học thưa (sparse geometric graph).

Phương pháp chọn mẫu: Lựa chọn mẫu môi trường ngẫu nhiên có kiểm soát theo các mức độ phân mảnh không gian khác nhau nhằm đánh giá tính tổng quát và độ bền vững của giải thuật trước các tình huống góc chết (deadlock) và hành lang hẹp.

Lý do lựa chọn phương pháp phân tích: Việc kết hợp phân hoạch cây tứ phân với phép biến đổi đồ thị $H$ cho phép chuyển đổi bài toán đa tác nhân phức tạp về bài toán tìm đường đơn trên đồ thị trạng thái với thời gian thực thi đa thức. Để kiểm chứng tính tối ưu tuyệt đối của giải thuật đề xuất, tác giả đã lập trình mô hình 0-1 ILP bằng ngôn ngữ mô hình hóa GNU MathProg và giải bằng bộ công cụ mã nguồn mở GLPK (GNU Linear Programming Kit) phiên bản 4.45 làm chuẩn đối sánh. Toàn bộ quá trình nghiên cứu và thử nghiệm được hoàn thành xuyên suốt trong 11 tháng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích thực nghiệm và đối soát toán học đã mang lại các phát hiện khoa học quan trọng:

Thứ nhất, giải thuật biến đổi đồ thị $H$ kết hợp A* đạt hiệu năng thời gian vượt trội. Trên các tập dữ liệu đồ thị hình học dày quy mô 256 đỉnh, thời gian thực thi của phương pháp $H$ giảm từ 70% đến 88% so với phương pháp giải mô hình quy hoạch tuyến tính nhị nguyên bằng GLPK 4.45. Cụ thể, khi số lượng cạnh của đồ thị $G$ tăng cao, GLPK mất từ 18,5 giây đến hơn 45,2 giây để tìm lời giải, trong khi thuật toán đề xuất chỉ mất từ 0,42 giây đến 1,35 giây.

Thứ hai, tính tối ưu của đường đi được bảo toàn 100%. Chiều dài quãng đường di chuyển của hai robot thu được từ thuật toán trên đồ thị $H$ hoàn toàn trùng khớp với giá trị hàm mục tiêu tối ưu toàn cục do solver ILP tính toán (độ lệch sai số bằng 0%). Điều này chứng minh rằng việc rời rạc hóa trạng thái và áp dụng heuristic Euclid không làm mất đi tính tối ưu của nghiệm.

Thứ ba, cấu trúc cây tứ phân nâng cao hiệu quả quản lý không gian. So với phương pháp phân lưới ô vuông đều truyền thống (Uniform Grid), cây tứ phân giúp giảm 42% dung lượng bộ nhớ lưu trữ bản đồ và tăng tốc độ truy vấn các ô lân cận (neighbor finding) lên gấp 2,8 lần nhờ cơ chế chia nhánh thích ứng theo mật độ vật cản.

Thứ tư, cơ chế tạm dừng (pause mode) loại bỏ hoàn toàn hiện tượng bế tắc chuyển động. Trong 100% các trường hợp thử nghiệm tại các nút thắt cổ chai nơi hai robot phải đổi hướng hoặc đi qua khe hẹp, việc cho phép một robot dừng lại làm điểm tựa đã giúp tìm ra lộ trình hợp lệ mà các phương pháp di chuyển đồng bộ bắt buộc đều thất bại.

Thảo luận kết quả

Nguyên nhân chính giúp giải thuật đề xuất đạt tốc độ vượt trội nằm ở việc chuyển đổi không gian tìm kiếm. Thay vì phải giải quyết bài toán tối ưu tổ hợp đa chiều với hàng nghìn biến nhị phân $x_{u,v,t}$ như trong mô hình ILP, phép quy dẫn đồ thị $H$ đã loại bỏ từ đầu toàn bộ các trạng thái vi phạm khoảng cách hoặc va chạm chướng ngại vật. Do đó, thuật toán A* chỉ cần duyệt trên tập đỉnh hợp lệ với độ phức tạp tính toán đa thức.

Khi so sánh với các nghiên cứu tiền nhiệm, giải pháp này vượt trội hơn phương pháp DPC của Subhrajit Bhattacharya vốn chỉ sử dụng hàm phạt Lagrange cho ràng buộc mềm và dễ rơi vào cực tiểu địa phương. Đồng thời, nghiên cứu cũng khắc phục được hạn chế của thuật toán M* của Wagner và Choset, vốn bị suy giảm hiệu năng nghiêm trọng khi các robot tập trung tại cùng một khu vực hẹp do số chiều không gian tăng đột biến.

Về mặt trực quan hóa dữ liệu, các kết quả thực nghiệm được biểu diễn rõ nét thông qua biểu đồ đường so sánh thời gian thực thi (ms) theo số lượng vật cản giữa phương pháp $H$ và phương pháp ILP. Bên cạnh đó, bảng tổng hợp các chỉ số mở rộng nút (expanded nodes) và độ dài đường đi minh chứng rõ ràng tính ưu việt của thuật toán trong cả môi trường thưa lẫn môi trường dày đặc chướng ngại vật.

Đề xuất và khuyến nghị

Dựa trên các đóng góp lý thuyết và kết quả thực nghiệm của luận văn, các đề xuất ứng dụng và phát triển được đưa ra như sau:

Thứ nhất, tích hợp thuật toán biến đổi đồ thị $H$ vào hệ thống quản lý xe tự hành AGV trong các nhà kho thông minh. Mục tiêu là giảm 30% thời gian chờ và tắc nghẽn tại các giao lộ kho hàng, hoàn thành triển khai thử nghiệm trong vòng 6 tháng do Bộ phận R&D Logistics và Tự động hóa chủ trì thực hiện.

Thứ hai, mở rộng mô hình toán học từ bài toán 2 robot sang đội hình $k$ robot ($k \ge 3$) với các ràng buộc khoảng cách linh hoạt theo dạng khoảng $[d_{min}, d_{max}]$. Mục tiêu duy trì thời gian lập lộ trình dưới 2,5 giây cho nhóm 5 robot, thực hiện trong lộ trình 12 tháng bởi Nhóm nghiên cứu Trí tuệ Nhân tạo và Điều khiển học.

Thứ ba, phát triển module cập nhật bản đồ động thời gian thực bằng cách kết hợp cây tứ phân động (Dynamic Quadtree) với cảm biến LiDAR. Mục tiêu nâng cao độ chính xác nhận diện vật cản di động lên 99,5% và thời gian phản hồi dưới 50 mili-giây, thực hiện trong 9 tháng do Đội ngũ Kỹ sư Phần mềm Robot đảm nhiệm.

Thứ tư, chuẩn hóa và công bố bộ dữ liệu kiểm thử mã nguồn mở (Open-Source Benchmark Suite) cho bài toán tìm đường đa tác nhân có ràng buộc khoảng cách tại Việt Nam. Mục tiêu cung cấp 100 kịch bản bản đồ chuẩn hóa cho cộng đồng học thuật trong vòng 3 tháng tới.

Đối tượng nên tham khảo luận văn

Công trình luận văn thạc sĩ này mang lại giá trị học thuật và ứng dụng chuyên sâu cho 4 nhóm đối tượng:

Thứ nhất, học viên cao học và nghiên cứu sinh ngành Khoa học Máy tính và Kỹ thuật Robot: Tiếp cận phương pháp luận chặt chẽ trong việc mô hình hóa không gian trạng thái, kỹ thuật quy dẫn đồ thị và cách thức chuyển đổi bài toán tối ưu tổ hợp phức tạp về thời gian đa thức.

Thứ hai, kỹ sư phát triển phần mềm điều khiển xe tự hành (AGV/AMR) và kho bãi tự động: Vận dụng trực tiếp giải thuật tìm đường phối hợp cặp để tối ưu hóa lộ trình vận chuyển hàng hóa, hạn chế xung đột tại các cung đường hẹp trong nhà xưởng quy mô trên 100 nút giao.

Thứ ba, chuyên gia công nghệ điều phối thiết bị bay không người lái (UAV/Drones): Áp dụng cơ chế duy trì khoảng cách và tạm dừng để thiết lập đường bay cho các cặp UAV trinh sát, đo đạc địa hình hoặc cứu hộ vùng ngập lụt với độ an toàn 100%.

Thứ tư, giảng viên và nhà nghiên cứu chuyên sâu về Lý thuyết tối ưu hóa: Sử dụng mô hình quy hoạch tuyến tính nhị nguyên (0-1 ILP) và mã nguồn GNU MathProg trong luận văn làm học liệu mẫu cho các môn học Quy hoạch toán học và Thiết kế giải thuật nâng cao.

Câu hỏi thường gặp

Thuật toán biến đổi đồ thị $H$ khác gì so với giải thuật A* truyền thống? A* truyền thống chỉ tìm đường cho một điểm di chuyển trên đồ thị không gian $G(V, E)$. Thuật toán đề xuất thực hiện A* trên đồ thị trạng thái mở rộng $H(V_H, E_H)$, trong đó mỗi đỉnh đại diện cho trạng thái kép của hai robot thỏa mãn khoảng cách 1 cạnh, giúp xử lý đồng thời chuyển động của cả hai đối tượng trong thời gian thực.

Tại sao luận văn lại cho phép một robot tạm dừng trong quá trình di chuyển? Trong không gian có vật cản, nhiều vị trí hẹp không cho phép cả hai robot cùng đổi chỗ đồng thời mà không vi phạm khoảng cách hoặc va chạm. Việc cho phép một robot đứng yên đóng vai trò như điểm tựa hình học, giúp robot thứ hai xoay chuyển linh hoạt, loại bỏ hoàn toàn các góc chết chuyển động.

Cấu trúc cây tứ phân (Quadtree) đóng vai trò gì trong hiệu năng của hệ thống? Cây tứ phân giúp phân hoạch không gian hai chiều liên tục thành các ô đa giác lồi rời rạc một cách thích ứng. Nhờ đó, hệ thống giảm 42% bộ nhớ lưu trữ so với phân lưới đều và cho phép thuật toán xác định nhanh các ô lân cận tự do mà không cần duyệt qua toàn bộ bản đồ.

Mô hình Quy hoạch tuyến tính nhị nguyên (0-1 ILP) được sử dụng nhằm mục đích gì? Mô hình 0-1 ILP được xây dựng bằng GNU MathProg và giải qua GLPK 4.45 đóng vai trò làm hệ quy chiếu chuẩn (ground truth). Việc so sánh kết quả thực nghiệm với ILP giúp tác giả chứng minh bằng số liệu rằng giải thuật trên đồ thị $H$ đạt nghiệm tối ưu toàn cục tuyệt đối.

Thuật toán có áp dụng được cho môi trường có chướng ngại vật di động không? Hiện tại, thuật toán được tối ưu cho môi trường tĩnh hai chiều để đảm bảo thời gian đa thức và tính đầy đủ. Để ứng dụng cho môi trường động, hệ thống cần tích hợp thêm cơ chế tái lập kế hoạch cục bộ (local replanning) hoặc kết hợp trường thế năng động để phản ứng kịp thời với vật cản tức thời.

Kết luận

Luận văn thạc sĩ của tác giả Trần Nhật Hoàng Anh đã giải quyết thành công bài toán tìm đường ngắn nhất cho hai đối tượng có ràng buộc khoảng cách trên đồ thị trong không gian tĩnh hai chiều:

  • Xây dựng thành công phương pháp quy dẫn đồ thị $G$ sang đồ thị trạng thái $H$, giải quyết bài toán tìm đường đa đối tượng trong thời gian đa thức.
  • Tích hợp hiệu quả cấu trúc cây tứ phân giúp tối ưu hóa không gian cấu hình tự do và giảm thiểu chi phí bộ nhớ.
  • Đề xuất cơ chế tạm dừng linh hoạt, đảm bảo tính đầy đủ xác suất và loại bỏ hoàn toàn nguy cơ bế tắc chuyển động.
  • Mô hình hóa toán học chính xác bài toán bằng quy hoạch tuyến tính nhị nguyên 0-1 ILP để kiểm chứng tính tối ưu 100% của giải thuật.
  • Cung cấp kết quả thực nghiệm toàn diện chứng minh thời gian tính toán giảm tới 88% so với các phương pháp giải tối ưu cổ điển.

Theo lộ trình phát triển từ 3 đến 12 tháng tới, các hướng mở rộng về đội hình đa robot và tích hợp cảm biến thời gian thực sẽ tiếp tục hoàn thiện giải pháp. Quý độc giả, nhà nghiên cứu và doanh nghiệp quan tâm có thể ứng dụng trực tiếp mô hình toán học và giải thuật này để nâng cao hiệu suất cho các hệ thống logistics và tự hành thông minh.