Journal of Science and Technique - Vol. 20, No. 01 (Feb. 2025)
68
HOẠCH ĐỊNH ĐƯỜNG BAY CHO UAV CÓ CÁNH CỐ ĐỊNH,
ỨNG DỤNG PHƯƠNG PHÁP CÂY NGẪU NHIÊN
VÀ GIẢI THUẬT DI TRUYỀN CẢI TIẾN
Nguyễn Đăng Minh1,*
1Viện Hàng không Vũ trụ Viettel
Tóm tắt
Bài báo trình y kết quả nghiên cứu phương pháp hoạch định đường bay cho các UAV
cánh cố định hoạt động trong môi trường phỏng. Phương pháp hoạch định đường bay
dựa trên ứng dụng y ngẫu nhiên thông minh giải thuật di truyền cải tiến. Trong đó,
phương pháp cây ngẫu nhiên kết hợp với c điều kiện phi tuyến được ứng dụng để khởi
tạo những đường bay khả thi, các toán tử giải thuật di truyền cải tiến được áp dụng đtìm
kiếm đường bay tối ưu. Kết quả phỏng cho thấy hiệu quả tính khả thi của phương
pháp đề xuất, sở để phát triển các hệ thống hoạch định đường bay cho c UAV hoạt
động trong môi trường thực.
T kha: Hoạch đnh đường bay; UAV có cánh c định; cây ngẫu nhiên; gii thut di truyn cải tiến.
1. Đặt vấn đề
Hoạch định đường đi (path planning/route planning) nhm tìm kiếm mt tuyến
đưng kh thi t v trí xuất pt đến đích trong một môi trưng nhất định [1]. Vn đề
hoạch định đường đi cóng dng đa dạng trong nhiu lĩnh vực c quân s và dân s như:
hoạch định đường đi cho bt t nh UAVs (unmanned aerial vehicles), UGVs
(unmanned ground vehicles), AUVs (autonomous underwater vehicles), ASVs
(autonomous surface vehicles) bt công nghip; ng dng trong vic lp kế hoch
dẫn đường trong ngành hàng không, ng hải đường b. Kho sát v các phương
pháp hoch định đường đi cho rô bt t hành, các ng dụng, cũng như những đánh giá về
ưu, nhược đim ca chúng th tìm thy trong [2]-[5], tuy nhiên s không được tho
lun đây. Trong bài báo y, tác gi tp trung ch yếu vào vấn đề hoạch định đường
bay cho máy bay không người lái (UAV) có cánh c định ng dụng trong lĩnh vực quân
s để thc hin nhim v tn công mc tiêu trên bin.
Để gii quyết vấn đề hoạch định đường bay cho UAVs, mt loạt các phương pháp
tiếp cận đã được nghiên cu, th k đến như: phương pháp tối ưu a đồ th (Graph
* Tác giả liên hệ, email: nguyendangminh2604@gmail.com
DOI: 10.56651/lqdtu.jst.v20.n01.810
Tạp chí Khoa học và Kỹ thuật - ISSN 1859-0209
69
optimization) bao gm Visibility Graphs [6], Voronoi diagrams [7], [8], Rapidly
Exploring Random Trees [9], [10], Probabilistic Roadmap [11]; các phương pháp tìm
kiếm (Heuristic/Metaheuristic) bao gm A* [12]-[17], Theta* [18]-[20], Evolutionary
Algorithms [21]-[28]; phương pháp Potential Field [1], [29]. Ngoài ra, kho sát v c
phương pháp hoạch định đường bay cho UAVs và các vấn đề còn tn ti có th tìm thy
trong [2], [4].
So vi bài toán hoạch định đường bay trong các ng dng khác, hoạch định
đường bay cho UAVs tn công những điểm khác bit [30]: (1) UAVs bay độ cao
thấp để gim thiu kh năng bị ra đa đối phương phát hiện; (2) đường bay không vượt
quá gii hn vt lý của UAVs như bán kính lượn ti thiểu, quãng đường bay ln nht,
khong cách ti thiu giữa hai điểm điều hướng; (3) đường bay phi tránh vt cn
tránh vùng nguy him (no-fly zones); (4) đường bay phải đáp ng mt s yêu cầu như
góc lượn tối đa, hướng tiếp cn mục tiêu để đảm bo xác sut thành công ca nhim v.
Kết hp những điều kin ràng buc (2)-(4) k trên làm cho vấn đề hoạch định đường
bay tối ưu trở thành vấn đ tối ưu phi tuyến đa tiêu chuẩn phc tp v mt tính toán.
Các phương pháp tiếp cận trên cơ sở thut toán A* Genetic Algorithm (GA) đã được
chng minh kh năng giải quyết vấn đề y [12], [17], [21], [22], [24], [28].
Trong [12], so sánh kết qu thc nghim ca tác gi cho thy mc thut toán A*
kh năng x nhanh hơn, tuy nhiên thut toán GA li cho kết qu tốt hơn, bên cạnh đó
thut toán GA còn nhiu tiềm năng để ci tiến cũng như áp dụng các k thut khác
giúp gim thi gian tính toán, ví d như kỹ thut tính toán song song.
T vic nghiên cứu các công trình đã đưc công b trước đây, nhm áp dng vào
bài toán thc tế là phát trin h thng lp kế hoch cho UAVs chiến đấu trên môi trường
bin, tác gi nhn thy rng thut toán GA mt la chn tt. Tuy nhiên, mt s k
thut s dng trong các công b trước đây thể phù hp hiu qu vi bài toán ca
họ, nhưng còn thể ci tiến hoc thay thế để hiu qu hơn với ng dng c th đã nêu
trên. Có th k đến như:
(1) Hu hết các cách tiếp cận đều được phát trin vi bản đồ cu trúc (grid-
based hoc graph-based). Theo đó, mt không gian (C-space) được nh toán cu hình
hoàn chỉnh trước khi tìm kiếm đường đi trên đó [31]. Vic xây dng C-space để biu
diễn môi trường hoạt động thc tế ca UAVs là vấn đề phc tp v mt tính toán, không
nhng thế, kích thước vùng hoạt động, mc độ chi tiết s chiu ca C-space nh
hưởng ln ti thi gian cũng như hiu qu m kiếm ca thut toán hoạch định đường
Journal of Science and Technique - Vol. 20, No. 01 (Feb. 2025)
70
bay. Ngoài ra, trong ng dng thc tế, thông tin môi trường thường xuyên thay đi nên
không gian C-space cũng phải được cp nhật, quá trình này đòi hỏi không ít thi gian.
(2) Vic khi tạo đường bay ngẫu nhiên chưa biết có kh thi (feasible) hay không
(đường bay kh thi một đường bay an toàn và UAV th bay được), sau đó tìm
kiếm đường bay kh thi nh các toán t GA t ra khá tn kém và khó áp dng nhng k
thut b tr để tăng chất lượng các toán t GA giúp thúc đẩy quá trình tiến hóa.
(3) Vic xây dựng hàm đánh giá đường bay da trên tng khong cách gia các
điểm điều hướng chưa đầy đủ, qu đạo bay ca UAVs bao gồm các đon thng
các đoạn qu đạo cong khi đổi hướng. Điều này có th dẫn đến những đánh giá sai lầm
khi trên thc tế đường bay tng khong cách giữa các điểm điều hướng lớn hơn
nhưng lại có qu đạo bay ngắn hơn, hoặc một đường bay kh thi li tr thành không kh
thi vi phạm điều kiện quãng đường bay ln nht. Ngoài ra, các công b trước đây
cũng không đánh giá số ợng điểm điều hướng và tổng đi s góc lượn trên một đường
bay trong khi nhng tham s y ảnh hưởng đến quá trình điều khin và kh năng bám
qu đạo được lp trình sn của UAVs, đặc bit khi môi trường hoạt động b chế áp
không th s dng các h thống định v v tinh có độ chính xác cao, bt buc UAV phi
s dng các h thống định v quán tính kết hp với đo cao vô tuyến.
(4) Ngoài ra, vic thiết kế cu trúc d liệu đường bay chưa hợp làm tăng khi
ng tính toán không cn thiết, d điểm điều hướng (waypoint) ch thông tin ta
độ, các thông tin khác như khoảng cách vi waypoint liền trước, góc lượnphải tính
toán li mi khi cần đánh giá đưng bay (Trong bài báo này, thut ng “điểm điều
hướng” và thuật ng “waypoint” được dùng thay thế cho nhau).
Ci tiến những điểm hn chế k trên những đóng góp chính của bài báo y.
Nhng phn còn li ca bài báo s được trình bày như sau: Phần 2 trình bày phương
pháp xây dng bản đ khu vc hot động ca UAV t thông tin môi trưng thc tế,
tính ti các yếu t nhm gim thiểu nguy rủi ro mất an toàn cho UAVs cũng như
nguy cơ bị đối phương phát hin cnh báo sm trên hành trình bay. Phn 3 trình bày v
các ràng buc của đường bay cho UAVs hoạt động trên bin. Phn 4 trình bày v
phương pháp thiết lp tối ưu đường bay trong đó đề xut mt s k thut nhm ci
tiến chất lượng thuật toán; đề xut hàm đánh giá đường bay vi các yếu t liên quan ti
độ dài qu đạo bay, tổng đại s góc lượn s điểm điều hướng trên đường bay; trình
bày một phương pháp cho phép đưa các điu kin ràng buc phi tuyến tính vào quá
trình thiết lập đường bay kh thi; mt s k thut b tr nâng cao chất lượng ca các
toán t GA nhằm thúc đẩy quá trình tiến hóa cũng được trình y trong phn y. Kết
qu thc nghiệm được trình bày Phn 5, phn tng hp tho lun ca tác gi được
trình bày Phn 6.
Tạp chí Khoa học và Kỹ thuật - ISSN 1859-0209
71
2. Bản đồ không gian hoạt động ca UAVs
Như đã trình bày trên, nghiên cu này tp trung gii quyết vấn đề hoạch định
đưng bay ng dng trong h thng lp kế hoch cho UAVs tn ng mc tiêu trên bin,
phân tích yêu cu cho thy các UAVs phi được lp trình bay sát mt bin nhm hn chế
kh ng bị phát hin bi ra đa cảnh gii của đối phương, khi đó để đảm bo an toàn
UAVs phi bay vòng tránh các vt cn, vùng cm bay có sn trong môi trường hot động.
T những đặc điểm trên, để giảm độ phc tp, bản đồ khu vc hoạt động ca UAVs s
đưc xây dng trong không gian hai chiu (Trong bài o này, thut ng “bn đồ tìm
kiếm” “bản đồ không gian hoạt động” dùng thay thế cho nhau, trong mt s trường
hp gi tắt “bản đồ”). Nghiên cứu này không xem xét hoạch định đường bay trc
tuyến, để hn chế ri ro tim n, tác gi c gắng đưa các yếu t không chc chn c
yếu t đng của môi trường trong sut thi gian hoạt động ca UAVs vào quá trình xây
dng bn đ.
Hình 1a mt d v bản đồ khu vc hoạt động của UAVs, trong đó các vt
cản địa hình như đo ni, các dải đất hoc các công trình trên biển được biu din bng
các đa giác. Khu vực ra đa trinh sát của đối phương hoặc vùng ha lc phòng không
kh năng gây sát thương b trí c định hoặc trên tàu được biu din bng các vòng
tròn đỏ. Khu vc hoạt động ca các lực lượng đồng minh hoc trung lập được biu din
bng các hình tròn màu xám hoặc cũng thể biu din bằng các hình đa giác y tình
hung thc tế.
a) Khu vc hoạt động ca UAVs
b) Vt cản địa hình
Hình 1. Ví d v bản đồ khu vc hoạt động ca UAVs.
Journal of Science and Technique - Vol. 20, No. 01 (Feb. 2025)
72
2.1. Mô hình vt cản địa hình
Vt cn địa nh th các đảo ni, di đất ven bin hoc các công trình xây
dng trên bin, các vt cn loi này c định trong môi trường hoạt động ca UAV. Do sai
s ca các h thống định vị, đường bay cn phải được thiết lp cách các vt cn mt
khong
d
để đm bo an toàn.
Sai s trungnhnh phương vị trí ca UAV sau khong thi gian bay
f
t
giây tính
t c cất cánh đượcc định bi biu thc:
22
t
p p p
t nav ls

(1)
trong đó:
t
p
nav
- sai s trung bình bình phương vị trí ca UAV sau khong thi gian
f
t
giây;
- sai s trung bình bình pơng vị trí xut phát.
Trong bài báo này, tác gi xem xét các yếu t ngu nhiên tuân theo lut phân b
chun. Theo quy tắc “ba sigma”,
3p
t
d

khoảng cách an toàn để tránh va chm vi
các vt cn, trên lý thuyết, xác suất UAVs va vào đường biên ca vt cn 0,994.
Để m rng các vt cn dạng đa giác, một thut toán đã được phát trin da trên nguyên
tc các cạnh đa giác mới song song vi cạnh đa giác cần m rng, thut toán s duyt và
loi b bớt các đỉnh thừa đồng thi ct bớt các đỉnh góc nhọn để đm bảo đa giác
m rng không chiếm quá nhiu không gian. Hình 1b th hin vt cản là đa giác màu xám
đa giác vật cn o được m rng nh thut toán, đa giác vật cn o này s đưc s
dụng để kim tra tránh va chm trong qtrình hoạch định đường bay.
ơng tự, đối vi nhng vùng nguy him c định dng hình tròn, để đảm bo an
toàn cũng cần m rng mt khong ti thiu bng
3p
t
, điều này ch đơn giản là m rng
n kínhng nguy him tm một lượng ơng đương.
2.2. Mô hình vùng cấm bay di động
ng nguy him tính cht di động như vùng ra đa trinh t hoặc vùng ha lc
đưc b trí trên tàu của đối phương. Sự dch chuyn của các vùng này cũng chính sự
dch chuyn ca u, vn tc dch chuyn nm trong di
max
0, v
ph thuc vào loi tàu.
Do s không chc chn v ng vn tc dch chuyn của u đối phương trong thời
gian hoạt động ca UAV nên không th biết chc chn v trí ca nó. Tuy nhiên, th
chc chn rằng đối phương phải di chuyn trong mt khu vc hình tròn tâm trùng vi
v trí ti thời điểm ln cui cùng nhn được thông tin v đối phương và bán kính
e
t
r
đưc
tính bng công thc (2):