Xem mẫu
- 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
- 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) = in0 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
- 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
nguon tai.lieu . vn
