Bài toán quan sát đa mục tiêu: Sự tồn tại lời giải tối ưu và thuật toán Kalman tìm nghiệm theo ngưỡng xác định

g xác định.” 154 
nhận xét 3. Đã nêu ở mục trên (mục 2) chúng ta nhận được lời giải của bài toán 
quan sát đa mục tiêu. 
Định nghĩa 3.3. Lời giải *{ | 0,1, , 1}
t
t T    được gọi là lời giải tối ưu từng 
bước hay tối ưu cục bộ nếu *
(1: 1)
[ | (1 : 1)] max [ | ],
t
t t t
P Y t P Y t

 

   . Ở đây, 
(1: 1)
[ | ]
t t
P Y

 là xác suất hậu nghiệm của phép gán 
t
 . 
Chúng ta có một số kết quả sau: 
Mệnh đề 3.1. Với các điều kiện của bài toán quan sát đa mục tiêu đang xét, luôn 
tồn tại lời giải tối ưu từng bước. 
Chứng minh. Do M  , ta suy ra ,
t
n M t    . 
Hay nói một cách khác, 
t
n là các biến ngẫu nhiên bị chăn đều bởiM . Từ đó 
suy ra tính hữu hạn của { }, 0,1, , 1
t
t T     . 
Do đó, tại mỗi ( 0,1, , 1)t t T   , tập 
(1: 1)
{ [ | ],
t t t
P Y 

 có thể có} là tập 
hữu hạn bị chặn trên. Bởi vậy, *
t
 sao cho 
*
(1: 1) (1: 1)
[ | ] max [ | ]
t
t t t t
P Y P Y

 
 
 . 
Nhận xét 5. Với phương pháp chứng minh và kết quả của Mệnh đề 3.1, tuy chúng 
ta khẳng định rằng tồn tại lời giải tối ưu từng bước nhưng thuật toán kiến thiết để 
tìm lời giải đó chưa được chỉ ra. 
Một suy nghĩ trực quan là ta tìm từng biểu thức giải tích 
(1: 1)
[ | ]
t t
P Y

 và từ đó 
tìm cực trị của nó. Chúng ta có kết quả sau. 
Mệnh đề 3.2. Phân phối hậu nghiệm của phép gán 
t
 được tính theo công thức: 
(1: 1)
[ | ] . . . .
t t
P Y ABC D F

 (4) 
trong đó: 
( ) ( ); ( )
(1 )
k kt
t T NT t
k k
Y Y t Y t f Y
A p p

  
   
( ) ( ); ( ) ( 1)j jt
t T NT t
j j
Y Y t Y t f Y Y t
B p p

   
   
1
1
#( ( 1))
mà ( ) ( ) ( )
,
#( ( 1))!
NT
st
t
Y t
s s
NT s f Y Y t
C e p p
Y t 
 




 
 

  
#( ( 1))
,
#( ( 1))!
FA
Y t
FA
D e
Y t
 



 xác định trong nhận xét 1 
F là hằng số chuẩn hóa 
Chứng minh. Việc chứng minh dựa vào tính độc lập chuyển động của các mục 
tiêu cũng như các mục tiêu giả và tính trực tiếp từ công thức xác suất tích. 
Nhận xét 6. Trong thực tế, bài toán quan sát đa mục tiêu người ta thường quan 
tâm đến số lượng các mục tiêu tại mỗi thời điểm, quỹ đạo của các mục tiêu, thời 
điểm xuất hiện và biến mất của các mục tiêu mà không cần quan tâm quỹ đạo này 
là của mục tiêu thứ mấy (hay mục tiêu cụ thể nào) trong số các mục tiêu. Bởi vậy, 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 155
trong thực tế, người ta coi vai trò của các mục tiêu là không phân biệt, do vậy, 
người ta thường xét mô hình với giả thiết các mục tiêu xuất hiện và biến mất với 
xác xuất như nhau. Nghĩa là ,
k
p p k  . Dẫn đến, ta có quyền đặt 
k k
q p p  là 
hằng số (đã biết) và công thức xác suất hậu nghiệm (4) sẽ trở thành: 
2 3
0 1 2
(1: )
2 3
[ | ] (1 )
! !
n n
n n n q
t t
P Y q q e e F
n n
 
   (5) 
Do vậy, việc tìm *
t
 trong trường hợp này trở thành đơn giản hơn, tức là tìm 
cực trị của hàm 4 biến 
2 3
0 1 2
0 1 2 3
2 3
( , , , ) (1 )
! !
x x
x x x q
f x x x x F p q e e
x x
    với điều 
kiện ràng buộc: {0,1,2, }, 0, 3
i
x i    ;
0 t
x n ;
1 2 3 1t
x x x n

   . 
Sử dụng tính đồng biến của hàm ( ) lnz z và dùng phương pháp giải tích ta 
có thể đưa ra lời giải của bài toán trên bằng phương pháp nhân tử Lagrange (tuy 
rằng không đơn giản). 
Nhận xét 7. Dễ dàng từ Định nghĩa 3.3 và từ việc chứng minh Mệnh đề 3.1, thấy 
rằng lời giải tối ưu từng bước chưa chắc đã là duy nhất. 
Do vậy, có nhiều phương pháp và cách tiếp cận để xây dựng lời giải xấp xỉ tối 
ưu (chấp nhận được). Trong phần tiếp theo, chúng tôi sẽ trình bày một trong số các 
cách xây dựng lời giải chấp nhận được theo ngưỡng xác định cho trước. 
4. MỘT THUẬT TOÁN TÌM LỜI GIẢI CHẤP NHẬN ĐƯỢC 
 THEO NGƯỠNG XÁC ĐỊNH 
4.1. Lọc Kalman 
Lọc Kalman có những đặc điểm phù hợp để nghiên cứu các bài toán xử lý tín 
hiệu và các bài toán liên kết dữ liệu. Ở đây, chúng tôi nêu một số nét chính: mô 
hình và ký hiệu cần sử dụng cho mục đích trình bày kết quả của phần này (xem lọc 
Kalman trong [5]). 
Xét lọc Kalman với thời gian rời rạc. 
Phương trình trạng thái: 
1
( ) ( , ( ), ( ))
k k k k
Y t F t Y t V t

 (6) 
với mô hình quan sát:       , ,k k k kZ t H t Y t W t (7) 
trong đó: ( ) Yn
k
Y t   là véctơ trạng thái; 
Y
n là số chiều của véc tơ trạng 
thái; ( ) Zn
k
Z t   là véctơ quan sát;
 Z
n là số chiều của véctơ quan sát. 
(.,.,.) : [0, ] Y Y Y
n n n
F T      là ánh xạ mô tả hệ động lực chuyển trạng thái. 
(.,.,.) : [0, ] Y Z Z
n n n
H T      là ánh xạ mô tả mô hình quan sát. 
( )V t là nhiễu hệ thống,được giả thiết là nhiễu trắng có ma trận hiệp phương sai R . 
( )W t là nhiễu quan sát,được giả thiết là nhiễu trắng có ma trận hiệp phương saiQ . 
( )W t và ( )V t được giả thiết là không tương quan. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
N. T. Hằng, N. H. Nam, “Bài toán quan sát đa mục tiêu nghiệm theo ngưỡng xác định.” 156 
Lọc Kalman cho ta ước lượng theo tiêu chuẩn sai số trung bình bình phương bé 
nhất:  
ˆ( | )
ˆ ˆ ˆ( | ) min ( ( ) )( ( ) ) |
ny
T j
Y i j
Y i j arg E Y i Y Y i Y Z

  

, với 
1 2
{ ( ), ( ), , ( )}jZ z t z t z j  là dãy quan sát cho tới thời điểm
k
t j . 
 Với ước lượng đó, hiệp phương sai của ước lượng được định nghĩa là: 
 ˆ ˆ( | ) {( ( ) )( ( ) ) | }T jP i j E Y i Y Y i Y Z   
Thuật toán Kalman được thực hiện theo hai bước gồm bước dự báo và bước 
điều chỉnh. Kết quả sau khi sử dụng lọc Kalman (sau bước điều chỉnh) là: ˆ( | )Y k k 
là ước lượng của trạng thái ( )Y k ;  |P k k là hiệp phương sai của ước lượng đó. 
4.2. Thuật toán tìm lời giải chấp nhận được theo ngưỡng cho trước 
Ở mục này, chúng ta sẽ đưa ra thuật toán tìm lời giải cho bài toán quan sát đa 
mục tiêu có sai lệch không vượt quá ngưỡng cho trước. 
Giả sử 0  là một số cho trước. Giá trị  sẽ được gọi là ngưỡng sai lệch. 
Theo trình bày trong mục 3 của bài báo này, chúng ta xây dựng lời giải theo 
Định nghĩa 3.2 thỏa mãn một số yêu cầu cụ thể như sau. 
Giả sử tại thời điểm t ta có ( )Y t là tập các giá trị quan sát, tại thời điểm 
1t  có tập giá trị quan sát là ( 1)Y t  . 
 Phép gán 
t
 được xác định như sau: với ( )j
t
Y Y t , ta xét với một giá trị bất 
kỳ 
1 1
, ( 1)s s
t t
Y Y Y t
 
  . Với dây chuyền dữ liệu có j
t
Y là đỉnh cuối tại thời điểm 
t , ta hợp thêm giá trị 
1
s
t
Y

 tại thời điểm 1t  . Sử dụng lọc Kalman với dãy dữ liệu 
đó và tính ( 1 | 1)P t t  (theo lọc Kalman). 
Định nghĩa 4.1. Phép gán 
t
 được thực hiện theo nguyên tắc sau 
1. 
*
1
( )t j s
t t
f Y Y




 khi và chỉ khi thỏa mãn hai điều kiện 
a. Nếu ký hiệu hiệp phương sai ứng với 
*
1
s
t
Y

 là *( 1 | 1)P t t  thì 
 *( 1 | 1) min ( 1 | 1)
s
P t t P t t

     
b. *( 1 | 1)P t t    . 
2. Trong trường hợp ngược lại, nếu *( 1 | 1)P t t    thì ( )t j
t
f Y

 

. 
Lời giải { | 0,1, , 1}
t
t T   
được gọi là lời giải chấp nhận được với 
ngưỡng sai lệch không vượt quá  cho trước. 
Từ định nghĩa ta thấy rằng, { | 0,1, , 1}
t
t T    cũng là lời giải có độ sai 
lệch cực tiểu và không vượt quá ngưỡng  cho trước. 
 Chú ý: Dễ thấy rằng lời giải theo phương pháp trên có độ lệch cực tiểu nhưng 
chưa chắc đã là duy nhất. 
Nhận xét 8. Phương pháp xây dựng lời giải chấp nhận được nêu trên đồi hỏi mức 
độ tính toán tương đối lớn. Song việc đó không đáng ngại vì dễ dàng xây dựng 
được thuật toán có thể cài đặt trên máy tính và tận dụng các chương trình mẫu sẵn 
có (chẳng hạn về lọc Kalman). 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 157
5. KẾT LUẬN 
Với việc nghiên cứu bài toán quan sát đa mục tiêu (MTT), với mô hình toán học 
được định nghĩa ở mục 2, chúng tôi đã đưa ra khái niệm lời giải tối ưu từng bước 
và đồng thời chứng minh được sự tồn tại của lời giải này và chúng tôi cũng xây 
dựng được thuật toán tìm lời giải chấp nhận được theo ngưỡng xác định cho trước 
bằng công cụ lọc Kalman. Các kết quả của bài báo là những kết quả được công bố 
lần đầu tiên và đã được báo cáo tại một số xemina chuyên ngành. 
Lời cảm ơn: Nhóm tác giả xin cảm ơn TS. Trịnh Quốc Anh, giảng viên Khoa Toán - Cơ - Tin 
học của Đại học KHTN Hà Nội, người đã cung cấp nhiều tài liệu khoa học quý báu giúp chúng tôi 
hoàn thành nghiên cứu này. 
TÀI LIỆU THAM KHẢO 
[1]. Y.Bar Shalom and WW.D.Blair, “Multitarget - Multisemson Tracking: 
Applications and Advanc”, vol 3, 2000, Artech House. 
[2]. Y.Bar Shalom and T.E.Fortmann, “Tracking and Data Association”, 1988, 
Academic. 
[3]. S.Blackman, “Multiple Target Tracking with Radar Applications”, 1988, 
Artech House. 
[4]. S.Blackman and R.Popoli, “Design and Analysis of Modern Tracking 
Systems”, 1999, Artech House. 
[5]. H.F.Durmant - Whyte,”Introduction to Estimation and the Kalman Filter”, 
2000, Australian Center for Filed Robities. 
[6]. Lindsten F, “Rao-Blackwellised Particle Methods for Inference and 
Identification”, 2011, Linkoping University. 
[7]. L.D.Stone, C.A.Barlon and T.L.Cornin, “Bayesian Multiple Target Tracking”, 
1999, Artech House. 
ABSTRACT 
THE EXISTENCE OF AN OPTIMAL SOLUTION AND KALMAN ALGORITHM 
TO FIND A SOLUTION ACCEPTABLE UNDER PREDETERMITED 
THRESHOLD FOR PROBLEM OF MULTI-TARGET TRACKING 
In this paper, we present some research results on the problem of Multi-
Target Tracking: offer optimal concepts step by step, to prove the 
existence of an optimal solution step by step and build a solution 
acceptable under predetermined threshold. 
Keywords: Multi-target tracking, Data combination (data link), Catenary, Assignment, Pace optimal. 
Nhận bài ngày 22 tháng 07 năm 2016 
Hoàn thiện ngày 04 tháng 10 năm 2016 
Chấp nhận đăng ngày 14 tháng 12 năm 2016 
Địa chỉ: 1 Trường ĐH Mỏ địa chất; 
2 Côc C«ng nghÖ Th«ng tin, Bé Tæng Tham m­u, BQP. 
*Email: hangntmdc@gmail.com