intTypePromotion=1
ADSENSE

Cải tiến giải thuật đàn ong nhân tạo để lập lịch đường đi cho robot di động

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:3

19
lượt xem
2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết Cải tiến giải thuật đàn ong nhân tạo để lập lịch đường đi cho robot di động trình bày việc cải tiến giải thuật bầy ong nhân tạo (Improved Artificial Bee Colony Algorithm viết tắt, IABC) để tìm ra một hay nhiều tuyến đường khả thi và ngắn nhất cho robot di động di chuyển từ một điểm đầu đến một điểm đích không va chạm, trong môi trường tĩnh 2D có chướng ngại vật.

Chủ đề:
Lưu

Nội dung Text: Cải tiến giải thuật đàn ong nhân tạo để lập lịch đường đi cho robot di động

  1. Tuyển tập Hội nghị Khoa học thường niên năm 2021. ISBN: 978-604-82-5957-0 CẢI TIẾN GIẢI THUẬT ĐÀN ONG NHÂN TẠO ĐỂ LẬP LỊCH ĐƯỜNG ĐI CHO ROBOT DI ĐỘNG Trần Thị Cẩm Giang Trường Đại học Thủy lợi, email: giangttc@tlu.edu.vn 1. GIỚI THIỆU trong môi trường, để xây dựng một đồ thị đỉnh mới hỗ trợ việc tạo đường đi không va Robot di động đang được sử dụng rộng rãi chạm với chướng ngại vật [2]. Đồ thị này trong nhiều lĩnh vực thay thế con người như được xây dựng bằng cách sử dụng trung điểm trong nông nghiệp, công nghiệp, cứu hộ cứu các đường liên kết tự do (Hình 1a). Các điểm nạn, thăm dò, khai phá vũ trụ. Bài toán lập này tương ứng với nút (đỉnh) trong đồ thị và lịch đường đi cho robot di động tìm ra một đường nối giữa chúng là các cung trong đồ hay nhiều tuyến đường khả thi, an toàn và thị (Hình 1b). ngắn để tối ưu hóa sự tiêu thụ năng lượng vẫn là vấn đề then chốt. Mục tiêu đặt ra là tối ưu hóa tiêu thụ nặng lượng và chi phí sử dụng, cũng như tối đa hóa lợi nhuận, hiệu năng và tính chính xác cho robot [1, 2, 3]. Các thuật toán tìm kiếm cổ điển không thể giải quyết được các bài toán này trong thời gian giới hạn, môi trường có chướng ngại a) b) vật. Khi đó việc sử dụng các thuật toán xấp xỉ là một lựa chọn phù hợp để tìm thấy các lời Hình 1. Đồ thị Maklink giải gần tối ưu. Bài báo này cải tiến giải thuật 2.2. Giải thuật tối ưu hóa đàn ong nhân tạo bầy ong nhân tạo (Improved Artificial Bee Colony Algorithm viết tắt, IABC) để tìm ra Thuật toán được đề xuất bởi Karaboga vào một hay nhiều tuyến đường khả thi và ngắn năm 2005 [1]. Ý tưởng của thuật toán là các nhất cho robot di động di chuyển từ một điểm nguồn thức ăn, trong quá trình tìm kiếm, đầu đến một điểm đích không va chạm, trong những con ong sẽ thay đổi vị trí nguồn thức môi trường tĩnh 2D có chướng ngại vật. Hiệu ăn thành vị trí nguồn thức ăn tốt nhất. Giải quả của giải thuật IABC được so sánh với thuật ABC có ba loại ong: ong làm việc, ong giải thuật trước đó ABC dưới nền tảng sử giám sát và ong trinh sát. Những con ong làm dụng phân rã bản đồ bằng giải thuật Maklink. việc sẽ tìm kiếm các nguồn thức ăn, nếu tìm Các kết quả thực nghiệm đã chứng tỏ hiệu được thức ăn thì các chú sẽ chia sẻ thông tin quả của giải thuật đề xuất IABC tốt hơn giải về nguồn thức ăn đó cho ong giám sát. Ở tổ thuật ABC cơ bản [1]. ong giám sát đang chờ thông báo về vị trí và số mật của nguồn thức ăn nó vừa tìm được. 2. KIẾN THỨC NỀN TẢNG Ong quan sát sẽ chọn nguồn thức ăn tốt từ những nguồn thức ăn được tìm thấy. Nguồn 2.1. Đồ thị Maklink thức ăn tốt hơn thì sẽ được ong quan sát lựa Phương pháp mô hình hóa môi trường chọn hơn. Ong trinh sát có nhiệm vụ loại bỏ Maklink là một phương pháp tiếp cận theo nguồn thức ăn không thể cải tiến và tìm kiếm không gian trống giữa các chướng ngại vật nguồn thức ăn mới [1]. 68
  2. Tuyển tập Hội nghị Khoa học thường niên năm 2021. ISBN: 978-604-82-5957-0 Hàm đánh giá của mỗi nguồn thức ăn được Những điểm cải tiến: tính như sau:  Tìm n đường đi ngẫu nhiên từ điểm đầu  Tìm nguồn thức ăn mới: đến điểm kết thúc. Tính độ dài đường đi, tính vij = xij + Øij(xij – kij) fitness cho mỗi đường đi  Tính xác suất của mỗi đường đi.  Đưa ra các giải pháp mới cho các ong fit trinh sát. So sánh độ dài đường đi và lưu lại Probi = nguồn thức ăn tốt nhất. fit  Tìm đường đi 4. KẾT QUẢ THỰC NGHIỆM xij= minj + α(maxj – minj)  Tính giá trị hàm đánh giá: Bài báo thực hiện ba thực nghiệm sau để  1 phân tích hiệu quả của giải thuật ABC và 1  fi ( fi  0 ) IABC dựa vào độ đo thời gian chạy trung  fiti=  bình của giải thuật (Ttb), độ dài trung bình  1 ( fi  0 ) (Ttb) và tỉ lệ thành công trung bình (Tltb): 1 | fi | Thực nghiệm 1: Phân tích sự ảnh hưởng Trong đó: của hình dạng chướng ngại vật. xij: đường đi được chọn để thay đổi; Thực nghiệm 2: Phân tích sự ảnh hưởng kij: điểm lân cận; của mật độ con ong. Ø: giá trị ngẫu nhiên trong khoảng [-1,1]; 4.1. Ảnh hưởng hình dạng chướng ngại vật fi: chi phí hàm của mục tiêu; Có 5 bộ dữ liệu khác nhau được sự dụng fiti: giá trị fitness của nguồn thức ăn thứ i; trong thực nghiệm này. Tuy nhiên, môi maxj và minj : ràng buộc trên dưới của x; trường làm việc của Robot phức tạp bao gồm α: giá trị ngẫu nhiên trong khoảng [0,1]. nhiều chứng ngại vật là các đa giác lồi và lõm 2.3. Hàm đánh giá để bẫy Robot, nhằm kiểm tra khả năng tìm Độ dài đường đi Pa ngắn nhất: đường của Robot trong các môi trường khó. Length(Pa) =  in0 diS( P0 ,Pn ) Kết quả Hình 3 và Bảng 1 của thực nghiệm cho thấy hai giải thuật đều chạy ổn 3. GIẢI THUẬT ĐỀ XUẤT IABC định với các hình dạng dễ như hình tam giác, hình chữ nhật và hình tứ giác. Tuy nhiên, Đầu vào: chướng ngại vật hình chữ T và chữ U chỉ có  Tập m chướng ngại vật {Oi} có tọa độ k tỉ lệ thành công chỉ là 80%. đỉnh Oi = {Vj} ( 0 < i ≤ m, 0 < j ≤ k)  Điểm bắt đầu S và điểm đích T Đầu ra:  Đường đi Pa = ( P0, P1,…, Pn) mà robot cần tìm và độ dài đường đi đó. Lưu đồ giải thuật cải tiến (Hình 2): Hình 3. Kết quả thực nghiệm 1 Từ kết quả ở Hình 3 cho thấy, giải thuật Hình 2. Lưu đồ giải thuật cải tiến IABC IABC đã có sự cải thiện rõ về chiều dài 69
  3. Tuyển tập Hội nghị Khoa học thường niên năm 2021. ISBN: 978-604-82-5957-0 đường đi trong các trường hợp hình dạng Sự tăng dần trong mật độ con ong thì tỉ lệ chướng ngại vật khác nhau, các môi trường thành công của hai giải thuật càng thấp đi và có chung điểm xuất phát và điểm đích và sự chênh lệch giữa hai giải thuật IABC và khác nhau về mật độ và vị trí của chướng ABC sẽ càng bị rút ngắn. Nhưng dựa vào kết ngại vật. quả thực nghiệm, ta vẫn thấy được sự cải thiện rõ ràng với mật độ đàn ong ít (10, 20) Bảng 1. So sánh giải thuật ABC về độ dài đường đi của giải thuật IABC so và IABC trong thực nghiệm 1 với giải thuật ABC. Giải Ttb Ltb tìm Bộ dữ liệu Tltb Bảng 2. So sánh giải thuật ABC thuật (ms) được và IABC trong thực nghiệm 2 ABC 331 123 100 % Bộ dữ liệu 1 Giải Ttb IABC 331 122 100 % Bộ dữ liệu Ltb Tltb thuật (ms) ABC 451 126 100 % ABC 319 111 100 % Bộ dữ liệu 2 Bộ dữ liệu 1 IABC 451 117 100 % (5 con ong) IABC 319 111 100 % ABC 290 134 100 % ABC 319 111 100 % Bộ dữ liệu 3 Bộ dữ liệu 1 IABC 290 132 100 % (5 con ong) IABC 319 111 100 % ABC 594 139 80 % Bộ dữ liệu 4 Bộ dữ liệu 2 ABC 531 168 100 % IABC 594 135 80 % (10 con ong) IABC 531 106 100 % ABC 316 151 80 % Bộ dữ liệu 5 Bộ dữ liệu 3 ABC 1447 139 100 % IABC 316 133 80 % (20 con ong) IABC 1447 136 100 % 4.2. Ảnh hưởng của mật độ Ong Bộ dữ liệu 4 ABC 5958 153 70 % Mật độ ong được sinh ngẫu nhiên trong (50 con ong) IABC 5958 142 70 % khoảng [5,100] và có 5 bộ dữ liệu khác nhau Bộ dữ liệu 5 ABC 27015 153 40 % trong thực nghiệm này. (100 con ong) IABC 27015 153 40 % 5. TÀI LIỆU THAM KHẢO [1] ALPKIRAY et al, "Probabilistic Roadmap and Artificial Bee Colony Algorithm Cooperation For Path Planning", International Conference on Artificial Intelligence and Data Processing (IDAP), 2018. [2] Maki K Habib and Hajime Asama. Efficient method to generate collision free paths for an autonomous mobile robot based on new free space structuring approach. In IROS, Hình 4. Kết quả thực nghiệm 2 trong volume 91, pages 563-567, 1991. nhiều môi trường với mật độ ong [5-100] [3] Zhang, H. Y., Lin, W. M., và Chen, A. X. (2018). Path planning for the mobile robot: Kết quả thực nghiệm Hình 4 và Bảng 2 A review. Symmetry, 10(10), 450. cho thấy mật độ con ong ảnh hưởng rất lớn đối với kết quả của thực nghiệm. Với mật độ con ong càng nhiều sẽ càng khó tìm ra đường đi đến đích trong cả hai giải thuật. 70
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2