đặt vấn đề Vào năm 1954, tại Northbrook, Illinois, Barrett-Cravens đã phát minh ra "Guide- O-Matic", phương tiện không người lái đầu tiên trên thế giới [1]. Tuy nhiên, cho đến khoảng năm 1980, thuật ngữ Automated Guided Vehicle (AGV) mới được phổ biến rộng rãi [2]. Phát triển theo thời gian, thị trường AGV hiện nay đang được đánh giá sẽ tiếp tục bùng nổ trong thời gian sắp tới. Dựa trên báo cáo phân tích thị trường [3], cho đến năm 2021, quy mô thị trường AGV toàn cầu đạt 3.81 tỷ USD và có tốc độ tăng trưởng kép trung bình tính đến năm 2030 là 10.
Trong đó, khu vực châu Á chiếm tỷ lệ cao nhất, lên đến hơn 36% thị trường AGV toàn cầu. Con số tăng trưởng ấn tượng này cho thấy tiềm năng phát triển rất lớn của AGV trong nền công nghiệp ngày nay nói chung và thị trường châu Á, đặc biệt là Việt Nam nói riêng khi chúng ta đang bước vào một thời kỳ chuyển đổi công nghệ mạnh mẽ Trên thế giới, có rất nhiều công ty chuyên nghiên cứu và phát triển những dòng robot AGV như: Swisslog Holding AG, Dematic, Bastian Solutions, Daifuku, JBT; Seegrid Corporation; TOYOTA Industries Corporation; Hyster-Yale Materials Handling,… Hình 1. AGV của Dematic Hình 1. AGV của Toyota Ở Việt Nam hiện tại, đi kèm với sự phát triển về các cơ sở sản xuất và nhu cầu sử ứng dụng AGV, các công ty chuyên thương mại và chế tạo AGV đã bắt đầu hình thành.
Mặc dù là những doanh nghiệp còn non trẻ nhưng họ cũng đã có những sản phẩm hoàn thiện và đáng tin dùng. Ví dụ: AFM Việt Nam, INTECH group, IDEA group,… 1 Hình 1. AGV của IDEA group Hình 1. AGV của INTECH group Sự phát triển mạnh mẽ của hệ thống Multi-AGV cả về số lượng, chủng loại và ứng dụng trên đa dạng hoá lĩnh vực là minh chứng cho lợi ích vô cùng to lớn mà hệ thống robot tự hành mang lại.
Đầu tiên, robot giúp tự động hóa quá trình vận chuyển hàng hóa, sản phẩm hay nguyên vật liệu. Quá trình vận chuyển này được thực hiện một cách nhanh chóng hơn, hiệu quả hơn, tiết kiệm hơn. Tiếp đến, việc sử dụng hệ thống robot giúp doanh nghiệp đơn giản hoá kiểm soát quá trình làm việc, tối ưu quy trình phân phối và kiểm duyệt sản phẩm. Ngoài ra, robot tự hành sẽ thay con người làm việc trong các môi trường có điều kiện khắc nghiệt, đảm bảo an toàn cho người lao động.
Vì những lợi ích to lớn và tiềm năng phát triển vô cùng lớn, hệ thống Multi-AGV được lựa chọn làm hướng nghiên cứu. Để hoạt động tốt trong môi trường phức tạp, một hệ thống Multi-AGV hoàn chỉnh cần thực hiện đầy đủ và tuân thủ 05 “nhiệm vụ cốt lõi” [4]: phân bổ nhiệm vụ, lập kế hoạch đường dẫn, định vị, lập kế hoạch chuyển động và quản lý phương tiện. Trong đó, lập kế hoạch chuyển động là một nhiệm vụ vô cùng quan trọng, có chức năng xác định trước các nguy cơ va chạm, deadlock và điều chỉnh thời gian di chuyển của AGV để tránh các sự cố đó diễn ra [4]. Trong quá trình di chuyển theo đường dẫn, AGV gặp phải các chướng ngại vật, có thể là chướng ngại vật tĩnh không lường trước được, có thể là con người hoặc các AGV khác trong hệ thống đang chuyển động.
Rõ ràng, việc va chạm với các đối tượng này phải được dự đoán, nhận diện và ngăn chặn. Ngoài ra, cũng cần phải ngăn chặn các deadlock - tình huống mà AGV không 2 thể thực hiện hành động nào nữa. Đó là chức năng chính của lập kế hoạch chuyển động. Với tầm quan trọng của nhiệm vụ này, đã có rất nhiều phương pháp được thực hiện nhằm tối ưu hoá việc lập kế hoạch chuyển động của hệ thống AGV, cũng như tránh các va chạm không mong muốn.
Mặc dù vậy, các phương pháp này vẫn chưa toàn diện, khi thực tế vẫn có nhiều trường hợp AGV xảy ra va chạm. Một trong số những nguyên nhân được xác định là các AGV di chuyển không tuân thủ chính xác thời gian được lập lịch. Bên cạnh đó, tốc độ của AGV ngày càng được cải thiện với mong muốn nâng cao hiệu suất của hệ thống Multi-AGV. Tuy nhiên, sự nâng cao tốc độ đồng nghĩa với việc tăng rủi ro cho sự ổn định của kiện hàng mà AGV đang vận chuyển.
Đó là 02 trong các vấn đề còn tồn đọng của hệ thống Multi-AGV cần được giải quyết. Với các lí do như đã nêu ở trên, đề tài này được thực hiện với các mục tiêu chính như sau: - Xây dựng “thuật toán lập kế hoạch chuyển động” dự đoán chính xác va chạm thông qua sự đảm bảo tuân thủ thời gian chuyển động của AGV. - Gia tăng độ ổn định của kiện hàng trong quá trình AGV di chuyển.2 Phạm vi của đề tài - Đối tượng thực nghiệm: thuật toán được xây dựng để ứng dụng vào hệ Multi-AGV trong nhà xưởng, di chuyển trên sa bàn dạng cross-docking. Trong việc mô phỏng thuật toán, để hạn chế số lượng phép tính toán nhưng vẫn mang tính tổng quát, sa bàn có kích thước 11x11 với tổng 121 node.
Số lượng AGV xét đến tối đa là 3 AGV. - Phương pháp thực hiện: thuật toán được thử nghiệm và chứng minh tính đúng đắn trên phần mềm mô phỏng MATLAB. Kết quả đều được kiểm chứng bằng việc so sánh với các nghiên cứu được đánh giá cao gần đây. Hệ thống Multi-AGV di chuyển trong sa bàn dạng cross-docking trong ứng dụng nhà xưởng 1.3 Các công trình nghiên cứu liên quan Liên quan đến các giải thuật lập kế hoạch chuyển động, nhận diện và tránh va chạm, đã có nhiều nghiên cứu được thực hiện và công bố, cũng như ứng dụng vào thực tế.
Đối với giải pháp Phi tập trung, AGV phản ứng dựa trên những gì nó cảm nhận cục bộ và thông tin liên lạc giữa các AGV gần nó để tránh va chạm. Ưu điểm của cách tiếp cận Phi tập trung là hệ thống có thể mở rộng số lượng AGV tốt hơn, tuy nhiên nó có nhiều điểm hạn chế hơn phương pháp Tập trung trong việc tránh va chạm và deadlock. Còn đối với giải pháp Tập trung, máy tính trung tâm sẽ tập hợp tất cả các dữ liệu thu thập được từ các AGV như: vị trí, mục tiêu,… và lên kế hoạch chung cho toàn bộ hệ thống sao cho các AGV vừa không va chạm với nhau, vừa cho hiệu suất hệ thống tốt nhất. Điều này khiến cho hệ thống AGV dễ quản lý hơn.
Vì vậy, cách tiếp cận Tập trung vẫn đang được áp dụng phổ biến hơn trong hệ thống Mụlti-AGV [7]. 4 Ngày nay, đã có nhiều hệ thống AGV hiện đại có phạm vi tự do, được trang bị hệ thống điều khiển phi tập trung dựa trên hành vi heuristic và thuật toán mờ [11]–[13]. Tuy nhiên, vì các hạn chế như đã nêu trên, chúng chưa được ứng dụng rộng rãi trong công nghiệp. Đối với cách tiếp cận Tập trung, đã có nhiều nghiên cứu được công bố và đưa vào ứng dụng thực tế.
Một trong những cách tiếp cận đơn giản nhất là Regional Control Method (RCM) được M. Farahani giới thiệu [9]. Ở đây, không gian hoạt động của AGV được phân chia và chỉ một AGV được hoạt động trong vùng đó, có thể là các tuyến đường cố định hoặc không cố định. Hàng hoá được trao đổi thông qua các trạm chuyển đổi.
Ưu điểm của phương pháp này là đơn giản, dễ quản lý và phù hợp với hệ thống Multi-AGV phục vụ trong quy trình sản xuất với các tuyến đường và thời gian gần như cố định. Tuy nhiên, nhược điểm của phương pháp này là năng suất và hiệu quả đối với các khu vực sản xuất quy mô lớn và phức tạp. Smolic-Rocak [5] sử dụng khung thời gian theo dạng vector tại các đoạn đường để định tuyến cho các AGV, đồng thời tìm kiếm sự xung đột của các AGV thông qua khung thời gian này. Hệ thống hoạch định đường đi và lên lịch trình cho từng AGV, sau đó giám sát việc thực hiện lịch trình đó.
Giải pháp của Smolic-Rocak [5] đưa ra để tránh xung đột là tại một thời điểm, mỗi đoạn đường chỉ cho phép 01 AGV đi qua. Phương pháp này có ưu điểm là hoạch định đường đi “động”, cho phép linh hoạt thay đổi trong quá trình di chuyển. Bên cạnh đó, nó có xét đến độ ưu tiên giữa các nhiệm vụ. Tuy nhiên phương pháp này không áp dụng tốt đối với sa bàn dạng cross-docking vì không tối ưu hết các tình huống va chạm của nó.
Yindong Lian, Wei Xie [6] lại sử dụng phương pháp hàng chờ tại các điểm node và các đoạn đường, để quản lý thứ tự di chuyển của AGV, từ đó tránh được va chạm.6 mô tả chiến lược tránh va chạm này. Hàng chờ của điểm b theo thứ tự là 𝐴𝐺𝑉1 và 𝐴𝐺𝑉2. Vì vậy, 𝐴𝐺𝑉1 được ưu tiên hơn khi qua điểm b và được đi trước. Lúc này, 𝐴𝐺𝑉2 phải dừng lại và chờ tại điểm e.
Sau khi 𝐴𝐺𝑉1 đi ra khỏi điểm b và đến điểm a thì 𝐴𝐺𝑉2 mới được được phép di chuyển đến điểm b và vượt qua giao lộ. Mô tả thuật toán tránh va chạm sử dụng phương pháp hàng chờ Yunlong Zhao [10] đã đưa ra một giải pháp giải quyết va chạm không phụ thuộc vào việc tính toán thời gian di chuyển của AGV. Các va chạm khả dĩ được xác định và giải quyết dựa trên phương pháp dynamic resource reservation (DRR), nghĩa là xem xét trạng thái của “tập hợp các điểm dùng chung” (các vị trí, các điểm node) trên tuyến đường mà các AGV sẽ đi qua - vùng có nguy cơ va chạm. Nếu có bất kì một AGV nào khác đang ở trong vùng đó, các AGV còn lại cần dừng lại cho đến khi AGV này ra khỏi vùng.
Ưu điểm của phương pháp này là tuyệt đối hoá xử lý va chạm. Tuy nhiên, nhược điểm của phương pháp này là cần cập nhật thường xuyên vị trí của các AGV và tính toán ra quyết định lại, một khối lượng tính toán vô cùng lớn. Đồng thời phương pháp này cũng hạn chế quy mô và hiệu suất của hệ thống. Mô tả thuật toán tránh va chạm sử dụng phương pháp hàng chờ Ngoài ra, Jose, K [8] kết hợp tìm kiếm và giải quyết các va chạm thông qua nhiệm vụ “phân bổ tác vụ cho các AGV”.
Ở đây, tác giả sử dụng giải thuật GA để phân 6 bố nhiệm vụ, đồng thời kiểm tra vị trí của các AGV tại mỗi thời điểm. Nếu vị trí toạ độ của 02 AGV bất kỳ khớp nhau tại cùng một thời điểm, thuật toán sẽ nhận diện một va chạm khả dĩ. Từ đó phương án sẽ bị loại khỏi “quần thể”.