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:

1. GIỚI THIỆU

Robot di động đang được sử dụng rộng rãi
trong nhiều lĩnh vực thay thế con người như
trong nông nghiệp, công nghiệp, cứu hộ cứu
nạn, thăm dị, khai phá vũ trụ. Bài tốn lập
lịch đường đi cho robot di động tìm ra một
hay nhiều tuyến đường khả thi, an toàn và
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 tố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
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
giải gần tối ưu. Bài báo này 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. Hiệu
quả của giải thuật IABC được so sánh với
giải thuật trước đó ABC dưới nền tảng sử
dụng phân rã bản đồ bằng giải thuật Maklink.
Các kết quả thực nghiệm đã chứng tỏ hiệu
quả của giải thuật đề xuất IABC tốt hơn giải
thuật ABC cơ bản [1].
2. KIẾN THỨC NỀN TẢNG

2.1. Đồ thị Maklink
Phương pháp mơ hình hóa mơi trường
Maklink là một phương pháp tiếp cận theo
không gian trống giữa các chướng ngại vật

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
chạm với chướng ngại vật [2]. Đồ thị này
được xây dựng bằng cách sử dụng trung điểm
các đường liên kết tự do (Hình 1a). Các điểm
này tương ứng với nút (đỉnh) trong đồ thị và
đường nối giữa chúng là các cung trong đồ
thị (Hình 1b).

a)

b)

Hình 1. Đồ thị Maklink
2.2. Giải thuật tối ưu hóa đàn ong nhân tạo
Thuật tốn được đề xuất bởi Karaboga vào

năm 2005 [1]. Ý tưởng của thuật tốn là các
nguồn thức ăn, trong q trình tìm kiếm,
những con ong sẽ thay đổi vị trí nguồn thức
ăn thành vị trí nguồn thức ăn tốt nhất. Giải
thuật ABC có ba loại ong: ong làm việc, ong
giám sát và ong trinh sát. Những con ong làm
việc sẽ tìm kiếm các nguồn thức ăn, nếu tìm
được thức ăn thì các chú sẽ chia sẻ thơng tin
về nguồn thức ăn đó cho ong giám sát. Ở tổ
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.
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
thức ăn tốt hơn thì sẽ được ong quan sát lựa
chọn hơn. Ong trinh sát có nhiệm vụ loại bỏ
nguồn thức ăn khơng thể cải tiến và tìm kiếm
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
tính như sau:
 Tìm nguồn thức ăn mới:
vij = xij + Øij(xij – kij)
 Tính xác suất của mỗi đường đi.
fit
Probi =

fit
 Tìm đường đi
xij= minj + α(maxj – minj)
 Tính giá trị hàm đánh giá:
 1
1  fi ( fi  0 )

fiti= 
 1 ( fi  0 )
1 | fi |
Trong đó:
xij: đường đi được chọn để thay đổi;
kij: điểm lân cận;
Ø: giá trị ngẫu nhiên trong khoảng [-1,1];
fi: chi phí hàm của mục tiêu;
fiti: giá trị fitness của nguồn thức ăn thứ i;
maxj và minj : ràng buộc trên dưới của x;
α: giá trị ngẫu nhiên trong khoảng [0,1].
2.3. Hàm đánh giá
Độ dài đường đi Pa ngắn nhất:
Length(Pa) =  in0 diS( P0 ,Pn )
3. GIẢI THUẬT ĐỀ XUẤT IABC

Đầu vào:
 Tập m chướng ngại vật {Oi} có tọa độ k
đỉ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):

Những điểm cải tiến:
 Tìm n đường đi ngẫu nhiên từ điểm đầu
đến điểm kết thúc. Tính độ dài đường đi, tính
fitness cho mỗi đường đi
 Đưa ra các giải pháp mới cho các ong
trinh sát. So sánh độ dài đường đi và lưu lại
nguồn thức ăn tốt nhất.
4. KẾT QUẢ THỰC NGHIỆM

Bài báo thực hiện ba thực nghiệm sau để
phân tích hiệu quả của giải thuật ABC và
IABC dựa vào độ đo thời gian chạy trung
bình của giải thuật (Ttb), độ dài trung bình
(Ttb) và tỉ lệ thành cơng trung bình (Tltb):
Thực nghiệm 1: Phân tích sự ảnh hưởng
của hình dạng chướng ngại vật.
Thực nghiệm 2: Phân tích sự ảnh hưởng
của mật độ con ong.
4.1. Ảnh hưởng hình dạng chướng ngại vật
Có 5 bộ dữ liệu khác nhau được sự dụng
trong thực nghiệm này. Tuy nhiên, môi
trường làm việc của Robot phức tạp bao gồm
nhiều chứng ngại vật là các đa giác lồi và lõm
để bẫy Robot, nhằm kiểm tra khả năng tìm
đường của Robot trong các mơi trường khó.
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
đị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,
chướng ngại vật hình chữ T và chữ U chỉ có
tỉ lệ thành cơng chỉ là 80%.

Hình 3. Kết quả thực nghiệm 1
Hình 2. Lưu đồ giải thuật cải tiến IABC

Từ kết quả ở Hình 3 cho thấy, giải thuật
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
chướng ngại vật khác nhau, các mơi trường
có chung điểm xuất phát và điểm đích và
khác nhau về mật độ và vị trí của chướng
ngại vật.
Bảng 1. So sánh giải thuật ABC
và IABC trong thực nghiệm 1
Bộ dữ liệu
Bộ dữ liệu 1
Bộ dữ liệu 2
Bộ dữ liệu 3
Bộ dữ liệu 4
Bộ dữ liệu 5

Giải
thuật


Ttb
(ms)

Ltb tìm
được

Tltb

ABC

331

123

100 %

IABC

331

122

100 %

ABC

451

126


100 %

IABC

451

117

100 %

ABC

290

134

100 %

IABC

290

132

100 %

ABC

594


139

80 %

IABC

594

135

80 %

ABC

316

151

80 %

IABC

316

133

80 %

Sự tăng dần trong mật độ con ong thì tỉ lệ

thành cơng của hai giải thuật càng thấp đi và
sự chênh lệch giữa hai giải thuật IABC và
ABC sẽ càng bị rút ngắn. Nhưng dựa vào kế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)
về độ dài đường đi của giải thuật IABC so
với giải thuật ABC.
Bảng 2. So sánh giải thuật ABC
và IABC trong thực nghiệm 2
Giải
thuật

Ttb
(ms)

Ltb

Tltb

ABC

319

111

100 %

IABC

319


111

100 %

ABC

319

111

100 %

IABC

319

111

100 %

Bộ dữ liệu 2 ABC
(10 con ong) IABC

531

168

100 %


531

106

100 %

Bộ dữ liệu 3 ABC
(20 con ong) IABC

1447

139

100 %

1447

136

100 %

Bộ dữ liệu 4 ABC
(50 con ong) IABC

5958

153

70 %


5958

142

70 %

Bộ dữ liệu 5 ABC 27015
(100 con ong) IABC 27015

153

40 %

153

40 %

Bộ dữ liệu
Bộ dữ liệu 1
(5 con ong)
Bộ dữ liệu 1
(5 con ong)

4.2. Ảnh hưởng của mật độ Ong
Mật độ ong được sinh ngẫu nhiên trong
khoảng [5,100] và có 5 bộ dữ liệu khác nhau
trong thực nghiệm này.

5. TÀI LIỆU THAM KHẢO


Hình 4. Kết quả thực nghiệm 2 trong
nhiều môi trường với mật độ ong [5-100]
Kết quả thực nghiệm Hình 4 và Bảng 2
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.

[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,
volume 91, pages 563-567, 1991.
[3] Zhang, H. Y., Lin, W. M., và Chen, A. X.
(2018). Path planning for the mobile robot:
A review. Symmetry, 10(10), 450.

70