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

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 149
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 
Nguyễn Thị Hằng1*, Nguyễn Hải Nam2 
Tóm tắt: Trong bài báo này, chúng tôi xét bài toán quan sát đa mục tiêu: đưa ra 
khái niệm lời giải tối ưu từng bước, chứng minh sự tồn tại lời giải tối ưu và đồng 
thời đề xuất 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. 
Từ khóa: Quan sát đa mục tiêu, Kết hợp dữ liệu, Dây chuyền, Phép gán, Tối ưu từng bước. 
1. MỞ ĐẦU 
Bài toán quan sát đa mục tiêu được áp dụng rất rộng rãi trong thực tế. Trong 
lĩnh vực quân sự như: các hệ thống phòng không, các hệ thông giám sát, các hệ 
thống trinh sát điện tử,... Trong lĩnh vực dân sự như: các hệ thống giám sát giao 
thông, các hệ thống giám sát không lưu, các hệ thống giám sát, bảo vệ,... . 
Bài toán quan sát đa mục tiêu đã được nhiều tác giả đề xuất, xem xét và đưa ra 
khá nhiều phương pháp giải quyết [1 - 4], [7]. Phương pháp phổ biến nhất để giải 
bài toán đa mục tiêu là phương pháp ước lượng tuần tự Bayes (Bayesian sequential 
Estimation) mà tư tưởng cơ bản của phương pháp này là cập nhật một cách đệ quy 
hàm phân bố hậu nghiệm các trạng thái của mục tiêu. Tất cả các thuật toán quan 
sát đa mục tiêu đã được công bố cho đến thời điểm này đều rất phức tạp bởi lẽ nó 
gắn với các mô hình xác suất rất phức tạp. Có thể điểm qua các phương pháp đó 
như: Thuật toán lân cận gần nhất toàn cục (GNN); Thuật toán kết hợp dữ liệu xác 
suất đồng thời (JPDA), kết hợp dữ liệu đa giả thiết (MHT); Bộ lọc PHD; Bộ lọc 
hạt Rao – Blackwellized (RBMCDA), .... [6]. Cho đến nay, hầu như các thuật toán 
đối với bài toán quan sát đa mục tiêu di động đều hoặc sử dụng các thuật toán kết 
hợp dữ liệu nói trên hoặc cải tiến nhỏ các thuật toán đó. Điều cần nhấn mạnh là tất 
cả các thuật toán đã được công bố đối với bài toán quan sát đa mục tiêu di động 
đều chỉ đưa ra lời giải chấp nhận được theo một nghĩa nào đó. 
Trong bài báo này, chúng tôi xét bài toán quan sát đa mục tiêu di động tổng 
quát, trong đó, chúng tôi đưa ra các khái niệm lời giải tối ưu từng bước, chứng 
minh sự tồn tại lời giải tối ưu từng bước đối với bài toán đó, đồng thời, chúng tôi 
cũng đưa ra một thuật toán tìm lời giải chấp nhận được theo ngưỡng cho trước. 
2. BÀI TOÁN QUAN SÁT ĐA MỤC TIÊU: MÔ HÌNH TOÁN HỌC 
VÀ CÁC KHÁI NIỆM, ĐỊNH NGHĨA LIÊN QUAN 
Giả sử ta cần quan tâm đến một số đối tượng di động (hay còn gọi là mục tiêu) 
nào đó trong 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 X
n
là không gian trạng 
thái của mục tiêu, 
X
n là số chiều của véctơ trạng thái,  gọi là miền quan sát. 
Ký hiệu 1,T , 
 T là khoảng thời gian của quá trình quan sát. Do các thời 
điểm quan sá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 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.” 150 
sát t chúng ta hiểu là 1,t T và 
 t , nói một cách khác, ta giả thiết các thời 
điểm quan sát là 
i
t với , 1,2,...,
i
t i i 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, được ký hiệu là  ( )
t t
K K . Giả thiết rằng, mục tiêu thứ k xuất hiện ở 
vị trí ngẫu nhiên có phân bố đều trong  tại thời điểm k
i
t và di chuyển một cách 
độc lập đối với các mục tiêu khác trong  đến thời điểm k
f
t thì biến mất. Cũng 
giả thiết rằng, mục tiêu thứ , 1
t
k k K , tồn tại với xác suất 
 , (0 1)
k k
p p và biến mất với xác suất 1
k
p . Số mục tiêu tại mỗi thời điểm 
trong  ,  ( ),
t t
K K là biến ngẫu nhiên có phân phối Poisson với tham số 
  , 0 . 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. 
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 gây ra. Cũng tương tự như giả thiết đặt ra với các mục tiêu, giả thiết rằng có 
 ( )
t t
N N mục tiêu giả trong  tại thời điểm t . Mục tiêu giả thứ 
j , 1
t
j N , tồn tại với xác suất 
j
q , (0 1)
j
q và biến mất với xác suất 
 1
j
q . Số mục tiêu giả tại mỗi thời điểm trong  , là biến ngẫu nhiên có phân bố 
Poisson với tham số   , 0 . Các mục tiêu giả xuất hiện, tồn tại và biến mất là 
độ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, mục tiêu giả 
xuất hiện ở vị trí ngẫu nhiên có phân phối đều trong  . 
Bài toán quan sát đa mục tiêu yêu cầu từ các số liệu quan sát được, xác định số 
mục tiêu tại mỗi thời điểm, quỹ đạo (vết) của từng mục tiêu trong miền quan sát và 
trong quá trình quan sát. 
Nhận xét 1. Tham số  hoàn toàn biểu diễn được qua các , 1
k t
p k K . Hoàn 
toàn tương tự, tham số  cũng hoàn toàn biểu diễn được qua các , 1
j t
q j N . 
Trên thực tế, các mục tiêu giả có vai trò như nhau nên ta không cần phân loại 
các mục tiêu giả. Bởi vậy, ta có thể giả thiết là mô hình đang xét có một loại mục 
tiêu giả, ký hiệu là FA, có phân phối Poisson với tham số   , 0 . 
Nhận xét 2. Đặt    ( ) ( ) ( )
t t t
M K N sẽ không hạn chế nhiều nếu chúng ta 
giả thiết ( )
t
M bị chặn đều h.c.c, nghĩa là tồn tại ,0
t t
A A , sao 
cho  ( ) . .
t t
M A h c c . Gọi  inf ( ) . . 1t t ttM A A M h c c (ở đây [ ]a là 
phần nguyên của a). Khi đó 0 ,M M . 
Bằng việc bổ sung thêm vào mô hình các mục tiêu xuất hiện với xác suất bằng 
0, chúng ta luôn có thể xét bài toán quan sát đa mục tiêu với số lượng mục tiêu cố 
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 151
định là M. Việc bổ sung này không ảnh hưởng đến tính đúng đắn của các công 
thức cũng như tính chính xác của lời giải bài toán trong phương pháp giải được 
trình bày trong bài báo này. 
Mô hình toán học của bài toán quan sát đa mục tiêu và các định nghĩa 
liên quan. 
Ký hiệu: , 1,2,...,k
t
X k M là trạng thái của mục tiêu thứ k , Xnk
t
X , 
X
n 
là số chiều của véctơ trạng thái. Mô hình chuyển động (chuyển trạng thái) của mục 
tiêu thứ k được mô tả bởi hệ động lực phi tuyến tổng quát trong không gian trạng 
thái X
n
 như sau: 
 1 ( )
k k k
t k t t
X F X V
 (1) 
với : X Xn n
k
F là ánh xạ đo được từ X
n
 vào X
n
; Xnk
t
V là nhiễu trắng 
với ma trận hiệp phương sai kQ . Các , 1,2,...,k
t
V k M là không tương quan. Mô 
hình quan sát (đo đạc) được xác định bởi: 
 ( ) W
t t t
Y G X (2) 
với : X Y
n n
G , 
Y
n là số chiều của véctơ quan sát, G là ánh xạ đo được từ 
 X
n
vào Y
n
, W Yn
t
là nhiễu trắng với ma trận hiệp phương sai là R và W
t
không tương quan với các , 1,2,...,k
t
V k M . Trong mô hình trên, k
t
V được gọi là 
nhiễu hệ thống còn W
t
 được gọi là sai số đo đạc (quan sát). 
Ký hiệu: ( ) { 1,2,...| , }j
t t
Y t Y j n là tập các giá trị quan sát được tại thời 
điểm t ; 
t
n là số các kết quả quan sát được tại thời điểm t ; 
 
1
(1 : ) ( )
t
i
Y t Y t là 
tập các giá trị quan sát được cho đến thời điểm t . 
Yêu cầu của bài toán quan sát đa mục tiêu là từ các kết quả quan sát, xác định 
(ước lượng) được các quỹ đạo của các mục tiêu. Lưu ý rằng, tập các giá trị quan sát 
tại thời điểm t , tập ( )Y t chứa các giá trị quan sát hoặc của mục tiêu này, hoặc của 
mục tiêu khác, hoặc của mục tiêu giả FA, chưa phân định được. 
Chúng ta đưa ra một số định nghĩa và một số kết quả bổ trợ sau. 
Định nghĩa 2.1. Một quỹ đạo của mục tiêu thứ k xuất hiện tại thời điểm k
i
t và 
biến mất tại thời điểm k
f
t là [ , ] , [1, ], [1, ]|k k
i f
k k k k k k
t i f i ft t
X X t t t t T t T . 
Với 
s
A là các tập hợp, ta sử dụng ký hiệu tích trực tiếp 
 
1
1 2
( , , , ) | , 1, .
s n s s
n
s
A a a a a A s n
   
Định nghĩa 2.2. Một dây chuyền (hay có thể gọi là một liên kết dữ liệu) với thời 
điểm đầu 
i
t và thời điểm cuối 
f
t và ký hiệu [ , ]
i f
d d t t là một phần tử của tập 
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.” 152 
tích ( )
f
i
t
t t
Y t
 nghĩa là 
1
1 2
1
[ , ] , , , , , ( ),
t tf is
i i f
f
i
jj j j
i f t t t t
t
t t
d d t t Y Y Y Y Y t
   
 trong 
đó, sj
t
Y được gọi là đỉnh tại thời điểm t của dây chuyền [ , ]
i f
d d t t . 
Định nghĩa 2.3. Dây chuyền [ , ]
i f
d t t được gọi là ảnh của quỹ đạo 
[ , ]k k
i f
k
t t
X của mục 
tiêu thứ k nếu ;
k k
i i f f
t t t t và giá trị đỉnh sj
t
Y là giá trị quan sát của k
t
X tại 
thời điểm t qua mô hình quan sát (2) với mọi 
1
, , ,
i i f
t t t t
  . 
Nhận xét 3. Nếu xác định được dây chuyền ảnh [ , ]
i f
d t t thì việc ước lượng quỹ 
đạo 
[ , ]k k
i f
k
t t
X là việc làm đã có nhiều công trình công bố, chẳng hạn người ta có thể 
dùng lọc Kalman để ước lượng quỹ đạo đó (xem [5] ). 
Như vậy, yêu cầu của bài toán quan sát đa mục tiêu trở thành yêu cầu dùng các 
phương pháp liên kết dữ liệu để xác định được các dây chuyển ảnh “một cách tốt 
nhất”. Để tiện cho việc trình bày ở phần sau, chúng ta đưa vào khái niệm xác suất 
cảm sinh trên không gian các giá trị quan sát (có thể gọi là không gian mẫu) và đưa 
ra công thức tính đối với xác suất đó. 
Với mục tiêu thứ k có xác suất xuất hiện là ,0 1
k k
p p , qua mô hình quan 
sát (2), giả sử: 
( ) k k
t t t
Y G X W (2’) 
là giá trị quan sát tại thời điểm t của mục tiêu thứ k . Với 
t
W là nhiễu trắng có ma 
trận hiệp phương sai R đã cho; với (.)G là ánh xạ đo được, ta có thể biểu diễn (2’) 
dưới dạng: ( )k k
t t
Y H X , trong đó, : X Y
n n
H là ánh xạ đo được. 
 Ký hiệu 1( )H A là nghịch ảnh của tập ,, Y
n
A A ta có: 
 1[ ] [ ( )]k k
t t
Y A X H A (3) 
Như vậy, phân phối xác suất của k
t
Y hoàn toàn xác định qua phân phối của k
t
X . 
Phân phối này chúng ta gọi là phân phối cảm sinh trên không gian các giá trị quan 
sát (không gian mẫu). 
Nói riêng, mục tiêu thứ k là k
t
X xuất hiện ở thời điểm t với xác suất là 
k
p , thì 
giá trị quan sát nó , ( )k k
t t
Y Y Y t , có xác suất xuất hiện là xác suất cảm sinh 
k
p 
(
k
p được tính theo 
k
p theo mối quan hệ (3)). 
3. SỰ TỒN TẠI LỜI GIẢI TỐI ƯU TỪNG BƯỚC CỦA BÀI TOÁN 
QUAN SÁT ĐA MỤC TIÊU 
 Giả sử tại thời điểm t , ta có 
t
n giá trị quan sát ( ) { | 1,2, , },j
t t
Y t Y j n  
trong đó: ( )
t
n T là số đỉnh của dây chuyền liên kết dữ liệu cho đến thời điểm t (số 
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 153
đỉnh của dây chuyền tính đến thời điểm t ), tập giá trị này ký hiệu là ( )
T
Y t ; 
( )
t
n NT giá trị đơn lẻ là điểm khởi tạo cho các dây chuyền mới, tập giá trị này ký 
hiệu là ( )
NT
Y t ; ( )n FA giá trị là giá trị quan sát do mục tiêu giả gây ra, tập các giá 
trị này ký hiệu là ( )
FA
Y t . Ta có: 
 t t t tn T n NT n FA n và ( ) ( ) ( ) ( )T NT FAY t Y t Y t Y t  . 
Đến thời điểm 1t , ta có 
1 1
( 1) { | 1,2, , }s
t t
Y t Y s n
  là tập các giá trị 
quan sát được tại thời điểm 1t . Ký hiệu: ( 1) { }Y Y t   
Định nghĩa 3.1. Một phép gán 
t
 tại thời điểm t là một ánh xạ: 
: ( ) ( 1)tf Y t Y t

  thỏa mãn điều kiện ( ( ) ( )) ( ( ))t t
T NT FA
f Y t Y t f Y t
 
   . 
Nhận xét 4. Với phép gán 
t
 tại thời điểm t, ta có: 
 Dây chuyền liên kết dữ liệu tại thời điểm t có điểm cuối 
là , ( ) ( )k k
t t T NT
Y Y Y t Y t  , sẽ kết thúc nếu ( )t k
t
f Y

  . 
 Dây chuyền liên kết dữ liệu tại thời điểm t là , ( ) ( )k k
t t T NT
Y Y Y t Y t  , sẽ 
tiếp tục kéo dài nếu 
1
( ) ( 1)t k s
t t
f Y Y Y t

 và khi đó, 
1
s
t
Y
 được gọi là 
đỉnh của dây chuyền tại thời điểm 1t . 
 Giá trị quan sát 
1 1
, ( 1)j j
t t
Y Y Y t
 , được xem là số đo của mục tiêu giả 
nếu 
1
1
( )t j
t FA
f Y Y t

 . 
 Các giá trị thuộc tập hợp mà ta sẽ ký hiệu là ( 1)
NT
Y t được xác định 
bởi ( 1) ( 1) ( ( ))t
NT
Y t Y t f Y t

  được gọi là các giá trị mới xuất hiện, 
khởi đầu cho một dây chuyền mới. 
 Tại thời điểm xuất phát ta coi tập (0)Y là tập tất cả các giá trị mục tiêu và 
báo động giả. Ta có #( (0))Y M hữu hạn (ký hiệu #( )A là lực lượng của 
tậpA ) 
 Số các phép gán 
t
 có thể có tại thời điểm t là hữu hạn. 
Như vậy, với một phép gán 
t
 tại thời điểm t thì tập giá trị quan sát tại thời 
điểm 1t sẽ được phân hoạch thành 3 tập rời nhau: 
 ( 1) ( 1) ( 1) ( 1)
T NT FA
Y t Y t Y t Y t   
Quá trình gán lại tiếp tục tại thời điểm 1, 2, .t t  
Định nghĩa 3.2. Một lời giải hay còn gọi là một chiến lược liên kết dữ liệu đối 
với bài toán quan sát đa mục tiêu là họ các phép gán { | 0,1, , 1}.
t
t T  
Dễ dàng thấy rằng một chiến lược liên kết dữ liệu { | 0,1, , 1}
t
t T  cho 
ta một họ các dây chuyền ảnh trong không gian các dữ liệu quan sát 
(1: )T
Y . Dựa vào 
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.” 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