Thuật toán Viterbi cải tiến và bài toán xác định số mục tiêu trong mô hình quan sát đa mục tiêu

Nghiên cứu khoa học công nghệ 
 Tạp chí Nghiên cứu KH&CN quân sự, Số 73, 06 - 2021 145 
THUẬT TOÁN VITERBI CẢI TIẾN VÀ BÀI TOÁN XÁC ĐỊNH 
SỐ MỤC TIÊU TRONG MÔ HÌNH QUAN SÁT ĐA MỤC TIÊU 
Nguyễn Thị Hằng*, Lê Bích Phượng, Phạm Ngọc Anh 
Tóm tắt: Trong bài báo này chúng tôi trình bày kết quả nghiên cứu đối với bài toán 
quan sát quỹ đạo đa mục tiêu MTT (Multiple Target Tracking). Cụ thể là phương pháp 
tiếp cận: dùng mô hình Markov ẩn HMM (Hidden Markov Model) để xác định mục tiêu 
trong MTT. Để xác định mục tiêu trong tập dữ liệu quan sát trong môi trường có nhiễu (có 
cả mục tiêu thực và mục tiêu giả), bài báo đã sử dụng ý tưởng thuật toán Viterbi (Viterbi 
Algorithm) trong HMM để xác định phần ẩn của mô hình, phần mục tiêu trong tập quan 
sát có nhiễu. Tuy nhiên, trong MTT chỉ có thông tin quan sát trong quá khứ cho đến thời 
điểm hiện tại, bởi vậy biến lùi không tồn tại và do đó thuật toán “Tiến – Lùi” (Forward – 
Backward Algorithm) không thể áp dụng. Trong bài báo này chúng tôi đưa ra thuật toán 
Tiến (Forward Algorithm) và thuật toán Viterbi cải tiến (Modified Viterbi Algorithm) và 
trên cơ sở các kết quả đó áp dụng để giải quyết vấn đề xác định mục tiêu trong MTT. 
Từ khóa: Quan sát quỹ đạo đa mục tiêu (MTT); Mục tiêu; Mô hình Markov ẩn (HMM); Thuật toán Tiến – Lùi; Thuật 
toán Tiến; Thuật toán Viterbi; Thuật toán Viterbi cải tiến. 
1. MỞ ĐẦU 
Trong bài toán MTT (xem [1]) hai vấn đề quan trọng nhất là dựa trên tập dữ liệu quan sát để: 
xác định số lượng mục tiêu và quỹ đạo của từng mục tiêu đó. Trong [1], chúng tôi đã đưa ra 
phương pháp liên kết dữ liệu, dựa trên hệ ánh xạ được xây dựng đệ quy để giải quyết hai vấn đề 
đó. Song thuật toán trong [1] là thuật toán tổng quát, tính khả thi trong áp dụng thực tế thấp, do 
lượng tính toán quá lớn và phức tạp, thậm chí ngay cả tìm lời giải gần đúng “  -tối ưu”. Trong 
công bố này, chúng tôi đưa ra phương pháp tiếp cận mới là phương pháp sử dụng HMM để đưa 
ra lời giải giải tích tường minh song chỉ tập trung vào một mục đích là: xác định số mục tiêu 
trong MTT không phân biệt loại mục tiêu. 
Với các công trình về HMM đã được công bố cho đến thời điểm hiện tại [2-5], để giải bài 
toán cơ bản thứ hai của HMM người ta chỉ dùng thuật toán Viterbi dựa trên thuật toán “ Tiến – 
Lùi ”. Nhưng với MTT thì chỉ có thông tin quan sát quá khứ cho đến thời điểm hiện tại, bởi vậy, 
biến lùi không tồn tại và do đó thuật toán “Tiến – Lùi” và thuật toán Viterbi không thể áp dụng 
cho HMM được xây dựng tương ứng với MTT (việc xây dựng HMM đó được thực hiện trong 
mục 3 của bài báo này). Bởi lẽ đó trong bài báo chúng tôi xây dựng thuật toán tiến (Forward 
Algorithm) và trên cơ sở đó xây dựng thuật toán Viterbi cải tiến (thậm chí cho trường hợp HMM 
không thuần nhất), và áp dụng chúng để giải bài toán xác định mục tiêu trong MTT. 
Kết quả trình bày trong bài báo không những giải quyết được bài toán xác định mục tiêu trong 
MTT mà còn đóng góp làm phong phú thêm các nghiên cứu về HMM. 
Bài báo chia thành 4 mục: Mục 1 là mục mở đầu; Mục 2 trình bày thuật toán tiến và thuật 
toán Viterbi cải tiến; Mục 3 xây dựng HMM cho bài toán MTT và áp dụng các kết quả của mục 
2 để giải bài toán xác định mục tiêu trong MTT; Mục 4: kết luận. 
2. HMM KHÔNG THUẦN NHẤT, THUẬT TOÁN TIẾN VÀ 
THUẬT TOÁN VITERBI CẢI TIẾN 
Xét HMM có cấu trúc mô tả như sau: 
+ Tham số chỉ số trạng thái là ,m m + . 
+ Tập các trạng thái phân biệt 1 2{ , ,..., }mS S S S= . Khi đó, S được gọi là không gian trạng thái. 
Ký hiệu qt là trạng thái của HMM tại thời điểm t, khi đó, qt nhận giá trị trên S. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
 146 N. T. Hằng, L. B. Phượng, P. N. Anh, “Thuật toán Viterbi cải tiến  quan sát đa mục tiêu.” 
+ Tham số chỉ số lượng các giá trị quan sát là ,n n + . 
+ Tập tất cả các giá trị quan sát phân biệt 1 2{ , ,..., }nV v v v= . Khi đó, V được gọi là không gian 
các giá trị quan sát. Ký hiệu Ot là quan sát tại thời điểm t, khi đó, Ot nhận giá trị trên V. 
+ Phân phối của trạng thái ban đầu: { :1 }i i m = , trong đó: 1( ),1i iP q S i m = = . 
+ Phân phối xác suất chuyển trạng thái: 
• Trường hợp HMM thuần nhất: ij 1 ,i j m
A a
 = , trong đó: 
ij 1 | , ,1 ,l j l ia P q S q S l i j m+ = = =  (1) 
• Trường hợp HMM không thuần nhất: ij 1 ,
( ) ( )
i j m
A k a k
 = , trong đó; 
ij 1( ) | , 1 ,k j k ia k P q S q S i j m+ = = = (2) 
Lưu ý: để thuận tiện ija trong công thức (1) chúng ta còn dùng ký hiệu 1l lq qa + và trong công 
thức (2) cùng với ij( )a k chúng ta còn dùng ký hiệu 
1
( )
q qk k
a k
+
. 
+ Phân phối xác suất của các quan sát khi HMM ở trạng thái ,1jS j m 
1
( ) ,1j k n
b k j m
 = , 
Trong đó: j( ) | ,1 ,1t k t jb k P O v q s k n j m = = = . 
+ Ký hiệu: { ( ) : 1,2,...}A A k k= = . Khi đã xác định được tham số m,n thì HMM hoàn toàn xác 
định khi biết ( , , )A B = trong trường hợp thuần nhất và ( , , )B  = trong trường hợp 
không thuần nhất. Bởi vậy, người ta thường dùng ký hiệu bộ ba ( , , )A ...  HMM dựa trên dãy quan sát. 
Trong nghiên cứu HMM, người ta còn quan tâm tới bài toán cơ bản thứ 3 là bài toán điều 
chỉnh HMM, liên quan đến học máy (machine learning) thường được ứng dụng trong lý thuyết 
nhận dạng. 
Với các công trình được công bố cho đến thời điểm hiện tại về HMM [2-4], người ta đã đưa 
ra thuật toán “Tiến – Lùi” và thuật toán Viterbi để giải các bài toán cơ bản thứ nhất và thứ hai. 
Như đã nêu ở phần mở đầu: các thuật toán đó không áp dụng được cho HMM liên quan đến 
Nghiên cứu khoa học công nghệ 
 Tạp chí Nghiên cứu KH&CN quân sự, Số 73, 06 - 2021 147 
MTT. Chúng tôi xây dựng hai thuật toán: Thuật toán tiến và thuật toán Viterbi cải tiến đối với 
HMM không thuần nhất như sau: 
2.1. Bài toán cơ bản thứ nhất và thuật toán tiến 
Tại thời điểm kt t= bất kỳ, [1, ]kt T , với  , ta có dãy quan sát: 
1 2 ... tO O O O= (4) 
Công thức giải và thuật toán để giải bài toán cơ bản thứ nhất đối với dãy quan sát 
1 2 ... tO O O O= được trình bày qua bổ đề và thuật toán sau đây: 
Bổ đề 2.1. 
1
1 2( ... ) 1
( | ) ( 1) ( )
s s s
k
k
q q q s
q q q s
P O a s b O
−
 =
  
= − 
 
  (5) 
Trong đó, ký hiệu hình thức: 
0 1 1
(0) .q q qa = 
Chứng minh. Xét một dãy trạng thái bất kỳ cố định nào đó: 
1 2... tQ q q q= (6) 
Ở đây, 1q là trạng thái ban đầu. 
Khi đó, xác suất của dãy quan sát (4) tương ứng với dãy trạng thái (6) sẽ là 
1
( | , ) ( | , )
k
s s
s
P O Q P O q 
=
= (7) 
Trong (7), chúng ta đã sử dụng giả thiết độc lập thống kê của dãy quan sát (4). 
Từ đó, chúng ta có: 
1 1
( | , ) ( | , ) ( )
s
k k
s s q s
s s
P O Q P O q b O 
= =
= =  (8) 
Mặt khác chúng ta có : 
1 1 2 2 3 1
( | ) (1) (2)... ( 1)
k kq q q q q q q
P Q a a a k 
−
= − , với ký hiệu 
0 1 1
(0) :q q qa = , 
chúng ta có: 
1
1
( | ) ( 1)
s s
k
q q
s
P Q a s
−
=
= − (9) 
Từ công thức (8) và (9), chúng ta có: 
( )
1 1
1 2
...1 1
( | ) ( | , ). ( | ) ( 1). ( ) ( 1). ( )
s s s s s s
k
k k
q q q s q q q s
Q Q q q qs s
P O A P O Q A P Q A a s b o a s b o
− −
  = =
= = − = −
  
  
  
    
Bổ đề được chứng minh 
Để tính công thức (5), chúng ta thấy rằng, nếu tính trực tiếp thì độ phức tạp của thuật toán có 
cấp của 2 ttM phép toán. Trong HMM thuần nhất người ta đưa ra thuật toán tiến-lùi (Forward-
Backward Algorithm) để tính công thức (5). Đối với HMM với mục tiêu áp dụng để giải bài toán 
MTT thì thuật toán đó không dùng được. Ở đây, bài báo đưa ra thuật toán gọi là thuật toán tiến 
(Forward Algorithm) để tính công thức (5) như sau. 
• Thuật toán tiến 
Ký hiệu 1 2( ) ( ... ; | )ii P O O O q S   = = ; nghĩa là ( )i là xác suất của phần đầu của dãy 
quan sát cho đến thời điểm t và tại thời điểm t đó, trạng thái ,t i iq q S S S = = . Khi đó, 
Công nghệ thông tin & Cơ sở toán học cho tin học 
 148 N. T. Hằng, L. B. Phượng, P. N. Anh, “Thuật toán Viterbi cải tiến  quan sát đa mục tiêu.” 
( )i được gọi là biến tiến. 
Xác suất ( | )P O  cho bởi công thức (5) được tính theo biến tiến ( )i theo thủ tục quy nạp 
như sau: 
1/ Bước khởi đầu: 1 1( ) ( ),1 ;i ii b O i m = 
2/ Bước quy nạp: 1 1
1
( ) ( ) ( ) . ( )
M
ij j
i
j i a b O   + +
=
= 
 với 1 1 1,1 ;kt t j m − = − 
3/ Kết thúc: 
1 1
( | ) ( ) ( ).
k
m m
t t
i i
P O i i 
= =
= =  
Do khuôn khổ hạn chế, với mục đích chính là công bố kết quả nên bài báo không đưa chứng 
minh chi tiết thuật toán. 
2.2. Bài toán cơ bản thứ hai và thuật toán Viterbi cải tiến đối với HMM không thuần nhất 
Bài toán cơ bản thứ 2 đối với HMM mục đích là phát hiện ra phần ẩn của mô hình nghĩa là đi 
tìm dãy trạng thái hợp lý nhất, dãy trạng thái tối ưu tương ứng với dãy quan sát đã cho. 
Vấn đề quan trọng đầu tiên là tiêu chuẩn thế nào là hợp lý nhất? Thế nào là tối ưu? Có hai 
dạng yêu cầu như sau: 
Dạng 1: Cho dãy quan sát: 1 2... tO O O O= sinh ra bởi HMM không thuần nhất  . Hãy tìm 
trạng thái *t tq q= tối ưu theo nghĩa cực đại xác suất. 
Dạng 2: Cho dãy quan sát: 1 2... tO O O O= sinh ra bởi HMM không thuần nhất  . Hãy tìm 
dãy trạng thái * * * *1 2... tQ q q q= của  tối ưu theo nghĩa cực đại xác suất. 
a/ Phương pháp tìm lời giải cho dạng 1. 
Đây là bài toán tìm trạng thái tối ưu riêng biệt *t tq q= tại thời điểm hiện tại t. 
Chúng ta xây dựng biến: 
( ) ( | , )t t ii P q S O = = (10) 
Dễ dàng biểu diễn ( )t i qua biến tiến ( )t i theo công thức: 
( )
( )
( | )
t
t
i
i
P O


= (11) 
Từ công thức (10), chúng ta thu được lời giải: 
*
1
arg max ( )t t
i M
q i
= (12) 
• Thuật toán Viterbi cải tiến 1 
Theo thuật toán tiến của mục 2.1 chúng ta dễ dàng dùng thuật toán tiến để thu được ( )t i 
thông qua công thức (11) và từ đó thu được *tq qua công thức (12). 
b/ Thuật toán Viterbi cải tiến và lời giải của dạng 2 
Để tìm ra dãy trạng thái tốt nhất * * * *1 2... tQ q q q= khi cho trước dãy quan sát 1 2... tO O O O= của 
 , bài báo đề xuất thuật toán sau đây và gọi là thuật toán Viterbi cải tiến 2 đối với HMM không 
thuần nhất. Sở dĩ gọi là “thuật toán Viterbi cải tiến” vì về mặt kỹ thuật khá tương đồng với thuật 
toán Viterbi đã được công bố đối với HMM thuần nhất, song nó chỉ sử dụng thuật toán tiến và 
biến tiến. 
Chúng ta định nghĩa: 
Nghiên cứu khoa học công nghệ 
 Tạp chí Nghiên cứu KH&CN quân sự, Số 73, 06 - 2021 149 
1 2 1
1 2 1 1 2
...
( ) max ( ... , ; ... | )i
q q q
i P q q q q q S O O O

     
−
−= = (13) 
Nghĩa là ( )i là xác suất lớn nhất dọc theo dãy trạng thái đến cho đến thời điểm  và kết 
thúc ở  tại trạng thái iS . Lý luận tương tự thuật toán tiến ở mục 2.1, chúng ta có công thức quy 
nạp cho ( )i theo công thức sau: 
 1
1
( ) max ( ). ( 1) . ( )ij j
i m
i i a b O    −
= − (14) 
Để tính ra được dãy trạng thái cần tìm trong quá trình qui nạp theo công thức (14) chúng ta 
giữ lại đối số (trạng thái) đạt cực đại trong thừa số đầu vế phải của(14) đối với mỗi  và j . Bởi 
vậy, cùng với ( )i , chúng ta thực hiện quy nạp cùng với đại lượng ( )t j như sau: 
• Thuật toán Viterbi cải tiến 2 
1/ Bước khởi tạo: 1 1 1( ) ( ), ( ) 0, 1 ;i ii b O i i m = = 
2/ Bước quy nạp: 
 
 
1
1
1
1
( ) max ( ). ( 1) . ( ),2 ,1
( ) arg max ( ). ( 1) ,2 ,1
ij j
i mt
ij
i m
j i a b O t j m
j i a t j m
  
 
   
   
−
−
= − 
= − 
3/ Kết thúc:  * *
1 1
max ( ) ; arg max ( ) ;t t t
i m i m
P i q i 
= = 
4/ Truy ngược: * *1 1( ), 1, 2,..,1q q t t   + += = − − . 
Kết thúc thuật toán chúng ta xác định được dãy trạng thái tối ưu: * * * *1 2... tQ q q q= . 
3. ỨNG DỤNG HMM GIẢI BÀI TOÁN XÁC ĐỊNH MỤC TIÊU TRONG MTT 
3.1. Bài toán MTT 
Giả sử ta cần quan tâm đến một số đối tượng (hay còn gọi là mục tiêu) di động nào đó trong 
một miền không gian và trong một khoảng thời gian nào đó. Ký hiệu  là miền không gian mà 
ta cần quan tâm, ở đây xn , với xn là không gian trạng thái của mục tiêu, xn là số chiều 
của véc tơ trạng thái của mục tiêu.  được gọi là miền quan sát. 
Ký hiệu [1, ], 1,T T T + , là khoảng thời gian mà ta cần quan tâm. [1, ]T được gọi là 
khoảng thời gian của quá trình quan sát. Do các thời điểm quan sát: 
1 2 1 2, ,..., (1 ... )n nt t t t t t T= = là rời rạc nên không mất tính tổng quát. Khi nói đến thời điểm 
thứ ( )ii t , chúng ta có thể quy ước: , iT t
+ + và đồng nhất , 1,2,...,it i i n= = , trong đó, 
1 1t = là lần quan sát đầu tiên và nt T= là lần quan sát cuối cùng của quá trình quan sát. 
Số mục tiêu có trong miền  tại thời điểm , [1, ]t t T , là một số ngẫu nhiên chưa biết và 
được ký hiệu là ( )t tM M = . Giả thiết rằng, mục tiêu thứ ( )k k , xuất hiện ở vị trí ngẫu 
nhiên có phân phối đều trong  tại thời điểm , [1, ]k ki it t T , và chuyển động một cách độc lập 
đối với các mục tiêu khác trong  đến thời điểm , [1, ]k kj jt t T , thì biến mất. Giả thiết rằng, mỗi 
mục tiêu tồn tại với xác suất ,0 1m mp p , và biến mất với xác suất 1 mp− . Giả thiết 
( )t tM M = là biến ngẫu nhiên Poisson với tham số , 0m m  . Các mục tiêu xuất hiện, tồn tại 
và biến mất một cách độc lập với nhau. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
 150 N. T. Hằng, L. B. Phượng, P. N. Anh, “Thuật toán Viterbi cải tiến  quan sát đa mục tiêu.” 
Trong thời gian quan sát, trong miền quan sát có thể có các mục tiêu giả do các clutter hoặc 
do các thiết bị kỹ thuật và phương pháp quan trắc gây ra. Cũng tương tự như giả thiết đặt ra với 
các mục tiêu, mỗi mục tiêu giả xuất hiện với xác suất ,0 1g gp p . Số mục tiêu giả có trong 
miền quan sát  tại thời điểm , [1, ]t t T là một số ngẫu nhiên chưa biết và được ký hiệu là 
( )t tG G = là biến ngẫu nhiên Poisson với tham số , 0g g  . Các mục tiêu giả xuất hiện, tồn 
tại và biến mất một cách ngẫu nhiên, độc lập với nhau và độc lập với các mục tiêu. Cũng như các 
mục tiêu, các mục tiêu giả xuất hiện ở vị trí ngẫu nhiên có phân phối đều trong  . 
Ký hiệu: ( ) | 1,2,...,jt tY t Y j n= = là tập các giá trị quan sát được tại thời điểm t,
1 2, ,...., ;n tt t t t n= là số lượng quan sát được tại thời điểm t . 
Dễ thấy, ( ( ))tn Card Y t= là một biến ngẫu nhiên và ( ) ( ) ( )t t t tn n M G  = = + . Từ đó, ta 
có: ( ) ( )t t m gn n P  = + . 
Mỗi giá trị quan sát có thể là giá trị quan sát thu được từ mục tiêu nào đó hoặc có thể là giá trị 
quan sát do mục tiêu giả gây ra. Yêu cầu của bài toán MTT là: Hãy xác định số mục tiêu hiện có 
tại mỗi thời điểm t trong miền thời gian quan sát trong  , nghĩa là xác định ( )tM  . 
3.2. Mô hình xấp xỉ 
Do: ( ) ( )t mM P  và ( ) ( )t m gn P  + nên 0 tùy ý bé, 
* ( )M M  + = và 
* ( )N N  + = sao cho *[ ( ) ] 1tP M M  − và
* 1 , [1, ]tP n N t T −  . 
Chúng ta đưa vào giả thiết sau đây: 
Giả thiết 3.1. * *,M N + sao cho: 
( )* *( ) (mod ), [1, ]; (mod ), [1, ]t tM M P t T n N P t T    
Chúng ta sẽ gọi bài toán MTT dược phát biểu trong mục 3.1 với điều kiện tuân theo Giả thiết 
3.1 là mô hình xấp xỉ. Mô hình này là đối tượng nghiên cứu trong bài báo này. 
3.3. Ứng dụng HMM để giải bài toán MTT 
Xét bài toán MTT đã được phát biểu trong mục 3.1. Chúng ta xây dựng HMM như sau: 
1/ Tham số m và không gian trạng thái. 
Đặt: * 1m M= + , không gian trạng thái: *0 1, ,..., MS S S S= , trong đó, iS = “Có đúng i mục 
tiêu trong miền  tại thời điểm quan tâm tương ứng”, *0,1,...,i M= . 
2/ Tham số n và không gian các giá trị quan sát. 
Đặt * 1n N= + , không gian các giá trị quan sát: *0 1, ,..., NV v v v= , trong đó, kv = “Có đúng 
k giá trị quan sát tại thời điểm quan tâm tương ứng”, *0,1,...,k N= . 
3/ Phân phối xác suất chuyển trạng thái: *[ ],0 ,ijA a i j M= , trong đó: 
 
*
1 1 0
max 0;( )
( )
| . (1 )
!
m
k k
ii
j l i l l j l im
ij t j t i i m mM l i
l i j
a P q S q S D D e C C p p
i

−
− + − + −
+ −
= −
 = = = = −  
Ở đây, các hằng số chuẩn hóa 0D và 1D được tính theo công thức: 
* 1
0
0
( )
!
m
iM
m
i
D e
i

−
−
=
  
= 
 
 
Nghiên cứu khoa học công nghệ 
 Tạp chí Nghiên cứu KH&CN quân sự, Số 73, 06 - 2021 151 
 
*
*1 0
0 max 0;( )
( )
(1 )
!
m
iM i
j l i l l j l im
i m mM l i
i l i j
D D e C C p p
i
 − + − + −
+ −
= = −
  
= − 
 
  
4/ Phân phối xác suất của quan sát khi hệ thống ở trạng thái jS tại thời điểm t. 
  * *( ) ,0 ,0j kB b v k N j M= 
Trong đó: 
( )
2
0 
( ) | ( )
. 
!
m g
k
j k t k t j m g
khi k j
b v P O v q S
D e khi k j
k
   − +
 = = = = + 
Ở đây, 2D là hằng số chuẩn hóa được tính theo công thức 
* 1
( )
2
( )
!
m g
kN
m g
k j
D e
k
  
−
− +
=
 + 
= 
 
 
5/ Phân phối trạng thái ban đầu 
*{ },0i i M = , trong đó, 1 0
( )
[ ] .
!
m
i
m
i iP q S D e
i
 −= = = 
Như vậy, chúng ta có HMM được xây dựng ứng với bài toán MTT trong mục 3.2. Chúng ta 
ký hiệu HMM này là MTT . 
Áp dụng thuật toán tiến và thuật toán Viterbi cải tiến được trình bày trong mục 2, cho MTT 
với lưu ý là mô hình thuần nhất chỉ là trường hợp riêng của trường hợp không thuần nhất với 
( ) ,A k A k  . 
Khi đó, khi biết các giá trị 
1 2
, ,..., ( )
k kt t t t t
n n n n n= , theo thuật toán chúng ta xác định được số 
mục tiêu tương ứng: 
1 2
* * * * *, ,..., ( )
k kt t t t t
m m m m m= . 
4. KẾT LUẬN 
Bài toán xác định số lượng mục tiêu của mô hình MTT không phân biệt loại mục tiêu là đối 
tượng được nghiên cứu trong bài báo này. Đây cũng là vấn đề thời sự và cấp bách được quan tâm 
nhiều trong những năm gần đây, bài báo đã trình bày 2 kết quả sau: 
- Xây dựng hai thuật toán mới là: Thuật toán tiến và thuật toán Viterbi cải tiến đối với HMM 
không thuần nhất. 
- Áp dụng các thuật toán được xây dựng đưa ra lời giải bài toán xác định số mục tiêu trong 
mô hình MTT không phân biệt loại mục tiêu. 
TÀI LIỆU THAM KHẢO 
[1]. N.T.Hang, “Một thuật toán tối ưu bám quỹ đạo mục tiêu của bài toán quan sát đa mục tiêu trong 
trường hợp có mục tiêu bị che khuất”, Tạp chí các công trình nghiên cứu phát triển Công nghệ thông 
tin và Truyền thông, số 01 tháng 09. Tr 46-55, 2019. 
[2]. G. David Forney, “The Viterbi algorithm”, International Jour-nal of Pattern Recognition and Artificial 
Intelligence, 61 (3), pp. 268-278, 1973. 
[3]. George Slade, “The Viterbi algorithm demysti”, www.researchgate.net, 2013. 
[4]. Zoubin Ghahramani, “An Introduction to Hidden Markov Models and Bayesian Networks”, 
International Journal of Pattern Recogni-tion and Artificial Intelligence, 15 (1), pp. 9-42, 2001. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
 152 N. T. Hằng, L. B. Phượng, P. N. Anh, “Thuật toán Viterbi cải tiến  quan sát đa mục tiêu.” 
[5]. Olivier Cappe, Eric Moulines, and Tobias Ryden, “Inference in hidden Markov models”, Springer 
Series in Statistics. Springer, New York, 2005. 
ABSTRACT 
THE MODIFIED VITERBI ALGORITHM IN DETERMINING THE NUMBER OF 
TARGETS IN THE MULTIPLE TARGET TRACKING 
In this paper, we present some research results for the MTT (Multiple Target Tracking) 
problem. Specifically, the approach: Use the Hidden Markov Model HMM (Hidden Markov 
Model) to identify the target in MTT. To define the target in the data set observed in a noisy 
environment (with both real and drone targets), the paper used the idea of the Viterbi 
Algorithm in HMM to determine the hidden part of the model, target part in the set of noisy 
observations. But MTT only has observed information in the past until the present time, so 
the reversed variable does not exist, and therefore the algorithm “Forward-Backward” can 
not apply. In this paper, we give the Forward Algorithm and the Modified Viterbi 
Algorithm and based on the results that apply to solve the problem of targeting in MTT. 
Keywords: Markov chains; Hidden Markov model (HMM); Status; Status values; Observation signs; Observation 
sign sets; Trace functions. 
Nhận bài ngày 19 tháng 3 năm 2021 
Hoàn thiện ngày 20 tháng 4 năm 2021 
Chấp nhận đăng ngày 10 tháng 6 năm 2021 
Địa chỉ: Trường Đại học Mỏ - Địa chất. 
*Email: nguyenthihang@humg.edu.vn.