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

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
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
Nguyễn Thị Hằng
Trường Đại học Mỏ - Địa chất, Hà Nội
E-mail: nguyenthihang@humg.edu.vn
Ngày nhận bài: 09/05/2019, ngày sửa chữa: 13/09/2019, ngày duyệt đăng: 13/09/2019
Xem sớm trực tuyến: 13/09/2019, định danh DOI: 10.32913/mic-ict-research-vn.v2019.n1.861
Biên tập lĩnh vực điều phối phản biện và quyết định nhận đăng: TS. Nguyễn Việt Dũng
Tóm tắt: Trong thực tế quan sát quỹ đạo đa mục tiêu di động, có lúc hệ thống quan sát không thể nhận biết được mục
tiêu, do các mục tiêu chuyển động quá gần nhau trong khi độ phân giải của hệ thống quan sát bị hạn chế, hoặc do một
số mục tiêu bị che khuất bởi các mục tiêu khác vì một lý do quan trắc nào đó. Trường hợp này cũng thường xảy ra trong
những môi trường có số lượng mục tiêu lớn (dày đặc) và mật độ nhiễu lớn. Các thuật toán bám mục tiêu, bám quỹ đạo
hiện hành gặp khó khăn và thường mất bám, mất quỹ đạo bám. Trong bài báo này, chúng tôi trình bày một phương pháp
liên kết dữ liệu và thuật toán bám quỹ đạo đệ quy từng bước theo thời gian quan sát với sự sử dụng tối đa dữ liệu lịch
sử của quỹ đạo. Thuật toán khắc phục được tình trạng mất bám, mất quỹ đạo bám trong môi trường có mục tiêu bị che
khuất. Thuật toán là sự kết hợp tư tưởng của phương pháp liên kết dữ liệu đa giả thiết và lọc Kalman mở rộng. Bài báo
cũng chứng minh sự tồn tại của lời giải tối ưu từng bước và đưa ra thuật toán tìm lời giải ε-tối ưu.
Từ khóa: Mục tiêu, quỹ đạo, ảnh, bám mục tiêu, quỹ đạo bám, che khuất, dây chuyền, dây chuyền dữ liệu.
Title: An Optimal Algorithm for Multi-Target Tracking with Obscured Targets
Abstract: In multiple-target tracking, there are difficult cases that the tracking system cannot detect targets, that is when targets
move too closely to each other beyond the resolution of the tracking system, or some targets are possibly obscured
by others. This also happens in environments with a large number of targets. In such cases, state-of-the-art tracking
algorithms fail to track targets or their orbits. In this paper, we propose a data association tracking method and
corresponding recursive tracking algorithm taking into account as many past orbit data as possible. This algorithm is
able to track targets and orbits in cases of obscured targets. This algorithm combines the data association method of
multiple hypothesis tracking and the extended Kalman filtering. In addition, we also prove the existence of the optimal
tracking solution at each step and give the algorithms for finding the ε-optimal solution.
Keywords: Target, orbit, image, target tracking, orbit tracking, obscured, chain, data transmission.
I. GIỚI THIỆU
Mô hình quan sát đa mục tiêu di động (MTT: Multiple-
Target Tracking) được ứng dụng rộng rãi trong thực tiễn
hoạt động xã hội, trong nhiều lĩnh vực cả ở dân sự lẫn trong
quân sự. Trong dân sự, các mô hình đã và đang được ứng
dụng như: hệ thống điều khiển và giám sát không lưu, hệ
thống điều khiển giao thông, hệ thống giám sát đại dương,
hệ thống bảo vệ và giám sát người qua lại trong một vùng
được bảo vệ. Trong quân sự, các mô hình đã và đang được
áp dụng như: hệ thống radar phòng thủ tên lửa đạn đạo, hệ
thống phòng không, hệ thống giám sát vùng mục tiêu bảo
vệ nào đó, hệ thống giám sát và theo dõi phòng không.
Công cụ vật lý được sử dụng trong các hệ thống quan
sát có thể là video, radar, hay cảm biến (sensor) nào đó.
Công cụ toán học (phần hồn của hệ thống) được sử dụng
cho đến thời điểm hiện tại là các kết quả, các thuật toán
nghiên cứu về MTT.
Phương pháp toán học phổ biến để giải bài toán MTT là
phương pháp ước lượng tuần tự Bayes (Bayesian Sequential
Estimation). Phương pháp này về bản chất 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 xây dựng trên nguyên tắc
này cho đến thời điểm hiện tại được công bố đều là các
thuật toán không tầm thường vì nó được gắn với các mô
hình xác suất rất phức tạp.
47
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
Các thuật toán chính hiện hành bao gồm: thuật toán
lân cận gần nhất toàn cục (GNN: Global Nearest Neigh-
bors) [1–3], thuật toán kết hợp dữ liệu xác suất đồng
thời (JPDA: Joint Probabilistic Data Association) [4–6],
thuật toán kết hợp dữ liệu đa giả thiết (MHT: Multiple
Hypothesis Tracking) [7–10], thuật toán kết hợp dữ liệu xác
suất đồng thời gần nhất (NNJPDA: Nearest Neighbor Joint
Probabilistic Data Association) [11, 12]. Các thuật toán này
rất hiệu quả, đã và đang được sử dụng trong thực tế. Ví dụ,
hệ thống giám sát điều khiển không lưu (hệ radar ASDE-X)
sử dụng thuật toán JPDA, hệ radar mảng pha Cobra Dane
nhằm phát hiện và giám sát tầm xa các tên lửa đạn đạo
xuyên lục địa sử dụng thuật toán NNJPDA kết hợp với bộ
lọc Kalman mở rộng (EKF: Extended Kalman Filter), hệ
thống radar trên biển X-band (SBX) của Hải quân Mỹ cũng
sử dụng thuật toán NNJPDA kết hợp với bộ lọc EKF, hệ
thống radar mảng pha cảnh báo sớm (UEWR: Upgraded
Early Warning Radar) nằm trong hệ thống phòng thủ tên
lửa quốc gia Mỹ sử dụng thuật toán MHT kết hợp với bộ
lọc EKF, hệ thống radar THAAD sử dụng thuật toán JPDA
cổ điển kết hợp với bộ lọc EKF, hệ thống video giám sát
hoạt động con người trong một vùng bảo vệ (của Đức) dùng
thuật toán MHT.
Thuật toán MHT được đề xuất bởi Reid còn thuật toán
JPDA được đề xuất bởi Bar-Shalom. Song từ khi được đề
xuất cho đến các cài đặt trong ứng dụng hiện nay, đã có
nhiều nhà toán học nghiên cứu, bố sung và phát triển so
với các đề xuất ban đầu. Động lực của các nghiên cứu bổ
sung và phát triển đó là: đặc thù của các đối tượng quan
sát, đặc thù của mô hình quan sát và đặc biệt là sự phát
triển của các công cụ vật lý - các công cụ “giá mang” và
“nền tảng kỹ thuật” của các thuật toán đó.
Tuy nhiên, các thuật toán hiện hành đối với bài toán
MHT chưa được giải quyết triệt để một tồn tại mà bài báo
này hướng tới để giải quyết, đó là mô hình MTT với hiện
tượng mục tiêu bị che khuất. Trong thực tế quan sát quỹ
đạo đa mục tiêu di động, có lúc các mục tiêu chuyển động
quá gần nhau trong khi độ phân giải của hệ thống quan
sát bị hạn chế, hoặc do một lý do quan trắc nào đó mà
một số mục tiêu bị che khuất bởi các mục tiêu khác. Các
tình huống này làm cho không phát hiện được mục tiêu.
Các thuật toán bám mục tiêu, bám quỹ đạo hiện hành gặp
khó khăn và thường mất bám, mất quỹ đạo bám. Trường
hợp này cũng thường xảy ra trong những môi trường có số
lượng mục tiêu lớn (dày đặc) và mật độ nhiễu lớn.
Bài báo này trình bày một số kết quả mới về bài toán
MTT trong điều kiện tổng quát, đặc biệt khi hiện tượng
mục tiêu bị che khuất có thể xảy ra1. Trước hết, chúng tôi
1Một phần của các kết quả này đã được trình bày tại hội nghị khoa
học quốc tế “Vietnam International Applied Mathematics Conference
(VIAMC)" vào tháng 12/2017 và tại hội thảo khoa học về “Một số phương
pháp thống kê hiện đại và các ứng dụng" vào tháng 07/2019.
đưa ra phương pháp liên kết dữ liệu thông qua hệ thống ánh
xạ xác định đệ quy từng bước. Hệ thống ánh xạ này không
chỉ quan tâm tới bản thân số liệu quan sát mà còn tính đến
cả lịch sử quỹ đạo quá khứ có thể có của số liệu đó. Bởi
vậy phương pháp liên kết dữ liệu này khắc phục được hiện
tượng mục tiêu bị che khuất (nếu xảy ra) và không làm mất
mục tiêu, mất quỹ đạo bám, v.v. Tiếp đến, dựa vào ý tưởng
và quan điểm của thống kê Bayes, chúng tôi đưa ra khái
niệm lời giải tối ưu từng bước theo nghĩa làm cực đại xác
suất hậu nghiệm tại mỗi bước, cũng như chứng minh sự tồn
tại lời giải tối ưu từng bước đối với phương pháp liên kết
dữ liệu đề xuất. Cuối cùng, dựa vào phương pháp dùng lọc
Kalman để ước lượng quỹ đạo của mục tiêu trên cơ sở dữ
liệu quan sát, chúng tôi đưa ra khái niệm lời giải ε-tối ưu.
Bản chất của khái niệm này là, khi dùng dữ liệu quan sát
của dây chuyền dữ liệu ảnh, theo phương pháp ước lượng
của lọc Kalman để ước lượng quỹ đạo của mục tiêu thì
phương sai P (t|t) không vượt quá ε (cho trước tùy ý bé)
với mọi t và đối với mọi quỹ đạo của mọi mục tiêu được
quan tâm trong bài toán MTT. Với khái niệm đó, chúng tôi
đã đưa ra thuật toán xây dựng lời giải ε-tối ưu mà bản chất
là xây dựng hệ thống ánh xạ liên kết dữ liệu đã nêu. Trong
khuôn khổ giới hạn của bài báo, chúng tôi chỉ trình bày
chi tiết các bước của thuật toán và sơ đồ logic cài đặt chi
tiết, mà chưa đề cập đến mô phỏng và áp dụng cho một
ứng dụng thực tiễn cụ thể.
Cấu trúc tiếp theo của bài báo như sau. Mục II trình bày
mô hình toán học của bài toán cùng các khái niệm và kết
quả bổ trợ ban đầu. Mục III là về khái niệm lời giải tối ưu
từng bước và sự tồn tại lời giải tối ưu từng bước. Mục IV
xây dựng thuật toán đệ quy để tìm lời giải ε-tối ưu. Mục V
và VI là phần thảo luận và kết luận.
II. BÀI TOÁN QUAN SÁT ĐA MỤC TIÊU
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 R là miền
không gian mà ta cần quan tâm, hay còn gọi là miền quan
sát. Ở đây R ⊂ Rnx , với Rnx là không gian trạng thái của
mục tiêu, nx là số chiều của véc tơ trạng thái của mục tiêu.
Ký hiệu [0, T ], T ∈ R+, là khoảng thời gian mà ta cần
quan tâm, đượ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 t0, t1, t2, . . ., tn, với 0 =
t0 < t1 < . . . < tn = 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ứ i (ti), chúng ta có thể quy
ước T ∈ Z+, ti ∈ Z+ và đồng nhất ti = i, i = 0, 1, . . . , T ,
trong đó, t0 = 0 là lần quan sát đầu tiên của quá trình quan
sát và tn = T = n là lần quan sát cuối cùng.
Số mục tiêu có trong miền R tại thời điểm t, t ∈ [0, T ],
là ngẫu nhiên và ký hiệu là Mt = Mt(ω). Giả thiết rằng
mục tiêu loại thứ k (để ngắn gọn hơn ta gọi là mục tiêu thứ
48
Tập 2019, Số 1, Tháng 9
k), k ∈ Z+, xuất hiện ở vị trí ngẫu nhiên có phân phối đều
trong R tại thời điểm tki , tki ∈ [0, T ], và di chuyển (chuyển
động) một cách độc lập đối với các mục tiêu khác trong
R đến thời điểm tkf , tkf ∈ [0, T ], thì biến mất. Cũng giả
thiết rằng mục tiêu thứ k xuất hiện (tồn tại) với xác suất
pk, 0 < pk < 1, và biến mất (không tồn tại) với xác suất
1− pk. Số mục tiêu tại thời điểm t, t ∈ [0, T ], có trong R,
Mt = Mt(ω), 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 hoặc do các thiết bị kỹ thuật
và phương pháp quan trắc (đo đạc) 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ó
Gt = Gt(ω) mục tiêu giả trong miền quan sát R tại thời
điểm t, t ∈ [0, T ]. Mục tiêu giả thứ j xuất hiện với xác suất
qj , 0 < qj < 1, và biến mất với xác suất 1−qj . Số mục tiêu
giả tại thời điểm t trong miền quan sát R, Gt = Gt(ω), là
biến ngẫu nhiên 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 một cách độ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 R.
Trong thực tế, các mục tiêu giả có ảnh hưởng như nhau
nên ta không cần phân loại các mục tiêu giả. Không mất
tính tổng quát, ta coi các mục tiêu giả do clutter gây ra hay
do kỹ thuật quan trắc gây ra là một loại với tên gọi là báo
động giả (false alarm). Chúng ta coi báo động giả như là
một loại mục tiêu đặc biệt.
Nhận xét 1. Tham số β hoàn toàn có thể biểu diễn qua
các qj , 1 6 j 6 Gt và tham số λ hoàn toàn có thể biểu
diễn qua các pk, 1 6 k 6Mt.
Ký hiệu Xkt , t ∈ [0, T ], k = 1, 2, . . ., là trạng thái
của mục tiêu thứ k tại thời điểm t, Xkt ∈ Rnx , nx là
số chiều của véc tơ trạng thái. Mô hình chuyển động (mô
hình chuyển trạng thái) của mục tiêu thứ k được mô tả
bởi hệ động lực tổng quát trong không gian trạng thái Rnx
như sau:
Xkt+1 = Fk
(
Xkt
)
+ V kt , (1)
với Fk : Rnx → Rnx là ánh xạ đo được từ Rnx vào Rnx ,
V kt ∈ Rnx là nhiễu trắng với ma trận hiệp phương sai là
Qk, các V kt là không tương quan.
Mô hình quan sát được mô tả bởi
Yt = G (Xt) +Wt, (2)
với G : Rnx → Rny , ny là số chiều của véc tơ quan sát,
G là ánh xạ đo được từ Rnx vào Rny , Wt ∈ Rny là nhiễu
trắng với ma trận hiệp phương sai là R và Wt không tương
quan với các V kt .
Nói riêng đối với mục tiêu k, từ (2), ta có
Y kt = G
(
Xkt
)
+Wt (2’)
Trong mô hình (1)–(2) ở trên, V kt được gọi là nhiễu hệ
thống, Wt được gọi là sai số (nhiễu) đo đạc (quan sát).
Ký hiệu Y (t) = {Y jt |j = 1, 2, . . . , nt} là tập các giá trị
quan sát được tại thời điểm t, nt là số lượng các kết quả
quan sát được tại thời điểm t.
Ký hiệu Y (0 : t) = ∪ts=0Y (s) là tập các giá trị quan sát
được cho tới thời điểm t.
Cần lưu ý rằng tính hữu hạn và bị chặn của nt hiện tại
chưa được khẳng định, mà sẽ được nói tới ở phần dưới đây.
Ký hiệu d(x, y), là khoảng cách Euclid trong Rn, nghĩa
là với x = (x1, . . . , xn) ∈ Rn và y = (y1, . . . , yn) ∈
Rn thì
d(x, y) =
(
n∑
i=1
(xi − yi)2
) 1
2
.
Ký hiệu O(O;r), r > 0, là hình cầu mở tâm O bán
kính r, O(O;r) = {x ∈ Rn : d(O, x) < r}, và O(O,r),
r > 0, là hình cầu đóng tương ứng, O(O;r) = {x ∈ Rn :
d(O, x) 6 r}.
Trong thực tế, do độ phân giải của các cảm biến bị giới
hạn, nên trong bài toán MTT xảy ra tình trạng là, với r > 0
đủ nhỏ nào đó, nếu hai mục tiêu x và x′ cùng thuộc O(O;r)
(hoặc O(O;r)) thì dữ liệu quan sát được về chúng y và y′
tương ứng là như nhau và trùng với dữ liệu quan sát được
của tâm điểm O. Hiện tượng này trong bài báo này chúng
ta gọi là mục tiêu bị che khuất, nghĩa là mục tiêu x′ bị che
khuất bởi mục tiêu x hoặc ngược lại, mục tiêu x bị che
khuất bởi mục tiêu x′. Dưới đây, chúng ta phát biểu giả
thiết về mục tiêu bị che khuất (lưu ý là r phụ thuộc vào
công cụ và nguyên lý quan sát trong từng bài toán MTT
cụ thể).
Giả thiết 1. Tồn tại r, r > 0, sao cho đối với bài toán (1)–
(2) nếu Xkt và X
l
t cùng thuộc hình cầu O(Oi;r), O(Oi;r) ⊂
Rnx , thì dữ liệu quan sát được của chúng là như nhau, nghĩa
là, nếuXkt ∈ O(Oi;r) vàX lt ∈ O(Oi;r) thì Y kt ≡ Y lt ≡ Y Oit ,
với Y Oit là dữ liệu quan sát được của mục tiêu Xt khi
Xt ≡ Oi.
Giả thiết 2. Miền quan sát R là miền đóng và giới nội
trong Rnx (theo Metric d(·, ·)).
Từ đó, chúng ta có bổ đề sau.
Bổ đề 1. Với Giả thiết 1 và Giả thiết 2, tập nt, t ∈ [0, T ]
bị chặn đều, nghĩa là, tồn tại Nmax, Nmax < +∞, sao cho
nt 6 Nmax với mọi t ∈ [0, T ] .
49
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
Để chứng minh, chúng ta sử dụng một kết quả về phủ
trong lý thuyết tô-pô, được nêu như sau: Xét không gian
tô-pô (X , T ), M ⊂ X , nếu M là tập compact (com-pắc)
theo tô-pô T thì từ mọi phủ mở bất kỳ của M luôn trích
được phủ con hữu hạn. Sau đây là chứng minh bổ đề 1.
Chứng minh: Xét X ≡ Rnx , T là tô-pô cảm
sinh bởi Metric d(·, ·) trong Rnx , từ Giả thiết 2 suy
ra R là tập  ... ưu từng bước luôn tồn tại (định lý 1), song
việc tìm lời giải đó không đơn giản. Chúng ta có thể xác
định được biểu thức giải tích hiển của xác suất hậu nghiệm
P [ft|Y (0 : t)] (xem [13]) và giải bài toán tìm cực trị của
hàm nhiều biến để xác định f∗t . Nhưng việc đó rất phức tạp
và khó khăn trong việc cài đặt thuật toán giải trên máy tính.
Dựa trên ý tưởng của lọc Kalman khi xử lý tín hiệu để
ước lượng quỹ đạo của mục tiêu [14–16], ở đây chúng ta
đưa ra một quan điểm mới khác để xem xét sự tốt hay
không của lời giải theo định nghĩa 5, cụ thể như sau. Như
đã nêu ở định nghĩa 5, một lời giải xác định một họ các
dây chuyền liên kết dữ liệu trong Y (0 : T ), trong đó mỗi
dây chuyền là dây chuyền dữ liệu ảnh của một quỹ đạo
xác định của một mục tiêu xác định nào đó. Theo quan
điểm của lọc Kalman, chúng ta thấy rằng nếu dùng các giá
trị quan sát (dây chuyền dữ liệu ảnh) để ước lượng quỹ
đạo thực của mục tiêu tương ứng theo lọc Kalman thì dây
chuyền ảnh là tốt nếu như phương sai ước lượng P (t|t) là
bé nhất và không vượt quá một ngưỡng sai lệch cho trước
nào đó. Một lời giải {ft|t = t1, ....tn} là tốt nếu như mọi
dây chuyền của nó là tốt. Chính xác hơn, chúng ta có định
nghĩa sau đây.
Định nghĩa 7. Lời giải {f∗εt |t = t1, ....tn} được gọi là lời
giải tối ưu ε-ngưỡng (và gọi tắt là ε-tối ưu) nếu như mọi
dây chuyền liên liên kết dữ liệu của nó thỏa mãn các điều
kiện sau đây:
(i) Khi sử dụng dữ liệu của dây chuyền để ước lượng
quỹ đạo thực của mục tiêu tương ứng theo lọc Kalman thì
phương sai ước lượng P (t|t) là cực tiểu với mọi t thuộc
miền thời gian tồn tại của dây chuyền;
(ii) Giá trị phương sai ước lượng P (t|t) nêu trong (i)
không vượt quá ε, ε > 0, với mọi t thuộc miền thời gian
tồn tại của dây chuyền. Ở đây, ε > 0, ε cho trước tùy ý bé,
được gọi là ngưỡng chấp nhận của lời giải.
Chúng ta đưa ra thuật toán tìm lời giải ε-tối ưu (mà thực
chất là tìm họ ánh xạ {f∗εt |t = t1, ....tn}) trong mục IV
tiếp theo.
IV. THUẬT TOÁN TÌM LỜI GIẢI ε-TỐI ƯU
1. Lọc Kalman
Chúng ta nêu một số nét chính về mô hình và ký hiệu
cần sử dụng cho mục đích trình bày kết quả nghiên cứu
của bài báo ở mục này (xem Lọc Kalman trong [14–16]).
Xét lọc Kalman với thời gian rời rạc đối với mô hình bao
gồm: phương trình trạng thái của (1), mô hình quan sát
của (2’). Để tránh nhầm lẫn, chúng ta dùng ký hiệu Zt =
{Y kt1 , Y kt1 , ..., Y kt } là dãy số liệu quan sát được của mục
tiêu thứ k cho tới thời điểm t. Trong đó, cần lưu ý rằng
tki 6 t1 < t2 < · · · < t 6 tkf , Y kti ∈ Y (ti), Zt ⊂ Y (0 : t).
Lọc Kalman cho chúng ta ước lượng theo tiêu chuẩn sai
số trung bình bình phương bé nhất như sau:
X̂k(i|t) = arg min
Xki ∈Rnx
E
{
(Xki − X̂k)(Xki − X̂k)T |Zt
}
.
Hiệp phương sai của ước lượng là
P (i|t) = E
{
(Xki − X̂k)(Xki − X̂k)T |Zt
}
.
Lọc Kalman được thực hiện theo hai bước: dự báo và
hiệu chỉnh. Kết quả sau khi áp dụng lọc Kalman (sau bước
hiệu chỉnh) cho chúng ta kết quả: X̂k(t|t) là ước lượng
trạng thái Xkt và P (t|t) là hiệp phương sai của ước lượng
đó (Phương sai của ước lượng).
2. Thuật toán tìm lời giải ε-tối ưu
Giả sử cho ε là một số cho trước tùy ý bé. Giá trị ε sẽ
được gọi là ngưỡng sai lệch. Theo các định nghĩa 4, 5, 6
và 7, chúng ta xây dựng lời giải ε-tối ưu. Điều đó có nghĩa
là chúng ta đi xây dựng họ {f∗εt | t = t1, t2, . . . , tn} thỏa
mãn yêu cầu đòi hỏi. Tư tưởng của thuật toán là kết hợp
phương pháp MHT với lọc EKF.
Chúng ta cần một số khái niệm và ký hiệu sau đây. Xét tại
thời điểm t, t = t0, t1, . . . , tn nào đó. Ký hiệu Ll[t−, Y it ],
0 6 l 6 Card(f−1t (Y it )), Y it ∈ Y (t) là dây chuyền thứ l
có đỉnh cuối tại thời điểm t là Y it .
Trong trường hợp Card(f−1t (Y
i
t )) = 0, tương đương với
l = 0, nghĩa là Y it là số đo mới xuất hiện chưa được gắn
với dây chuyền nào trước đó. Nó có thể là điểm khởi đầu
(đỉnh đầu) cho một dây chuyền mới là ảnh của quỹ đạo của
mục tiêu mới xuất hiện nào đó. Nó cũng có thể là điểm cô
lập (hay số đo của FA) mà sẽ được kết luận khi thực hiện
thuật toán sau mốc thời gian t+ 1.
Ký hiệu DLl[t−, Y it ] là tập các đỉnh của dây chuyền
Ll[t
−, Y it ] (kể cả đỉnh cuối tính đến thời điểm t là Y
i
t ),
0 6 l 6 Card(f−1t (Y it )).
Với 1 6 j 6 nt+1, ký hiệu
Zt+1(j) = DL[t−, Y it ] ∪ {Y jt+1}
= {Y hs ∈ L[t−, Y it ] | 1 6 h 6 s, s 6 t} ∪ {Y jt+1}.
Trong bài toán MTT, các hàm Fk(·) trong mô hình biến
đổi trạng thái là chưa biết. Trong thực tế người ta có thể có
một số thông tin tiên nghiệm nào đó hay có thể có một số
dự báo nào đó về dạng, loại hoặc tính chất của các hàm này.
Những thông tin tiên nghiệm và dự báo về các hệ động lực
trong mô hình biến đổi trạng thái (quá trình chuyển động)
của mục tiêu Xkt được biểu diễn bởi họ {F kθ | θ ∈ Θ}.
52
Tập 2019, Số 1, Tháng 9
Thực tế không cần phân định một quỹ đạo cụ thể này là
quỹ đạo của mục tiêu thứ mấy, nên không mất tính tổng
quát người ta coi F kθ không phụ thuộc vào k, nghĩa là,
F kθ = Fθ, θ ∈ Θ.
Ký hiệu F = {Fθ | θ ∈ Θ} và gọi là tập thông tin tiên
nghiệm và dự báo mô tả về hệ động lực có thể có của các
mục tiêu cần quan sát. Cần lưu ý rằng nếu không có thông
tin tiên nghiệm hay dự báo nào thì khi xét phải xét với
mọi hàm là ánh xạ đo được: Fθ : Rnx → Rnx . Chúng ta
nghiên cứu chỉ với giả thiết Card(Θ) < +∞. Thông tin
tiên nghiệm và dự báo càng tốt thì Card(Θ) càng nhỏ và
số lượng tính toán trong thuật toán càng giảm đi.
Khi sử dụng lọc Kalman trong tính toán liên quan chặt
chẽ với mô hình biến đổi trạng thái F , mô hình quan sát
G và tập dữ liệu quan sát Zt. Song do mô hình quan sát
G là không thay đổi và đã biết nên chúng ta không cần chỉ
rõ sự phụ thuộc vào G. Khi thực hiện bài toán lọc, theo
(1) và (2’), với F = Fθ, bộ dữ liệu quan sát Zt+1(j), ta
tính được phương sai hiệu chỉnh ở bước t + 1 và ký hiệu
là PFθlij (t+ 1 | t+ 1).
Để đơn giản trong trình bày cũng như để thuận tiện trong
cài đặt, chúng tôi trình bày thuật toán tìm lời giải chấp nhận
được ε-tối ưu theo các bước như dưới đây. Sơ đồ khối xử
lý thuật toán được mô tả trong hình 1.
Bước 1: Chọn thời điểm hiện tại t, 1 6 t 6 T (thực hiện
tuần tự t = t0, t1, . . . , tn− 1, nếu t = tk thì t+ 1 = tk+1).
Tạo tập dữ liệu quan sát ở thời điểm t+1 (nếu t+1 6 T )
Y (t+ 1) = {Y jt+1 | 1 6 j 6 nt+1}.
Nếu không có số liệu thực tế từ bài toán MTT cụ thể thì tập
Y (t+ 1) được tạo bằng mô phỏng theo phân phối Poisson.
Bước 2: Chọn i, 1 6 i 6 nt, tương đương với xác
định Y it .
Với mỗi l, 0 6 l 6 Card(f−1t (Y it )) được xét tuần tự với
l = 0, 1, . . . ,Card
(
f−1t (Y
i
t )
)
,
sử dụng lọc Kalman tính PFθlij (t+ 1 | t+ 1) ứng với mọi j,
1 6 j 6 nt+1, nghĩa là ứng với mọi
Zt+1(j) = DLl
[
t−, Y it
] ∪ {Y jt+1}, 1 6 j 6 nt+1.
Tính
δli = min
16j6nt+1
{min
θ∈Θ
PFθlij (t+ 1 | t+ 1)}.
So sánh δli với ngưỡng ε cho trước. Nếu δli > ε, ta kết
luận dây chuyền Ll[t−, Y it ] kết thúc tại đỉnh cuối Y
i
t , tương
đương với f∗εt+1
(
Y it
)
= ∅. Nếu δli < ε, ký hiệu
(j∗, θ∗) = arg min
16j6nt+1
{min
θ∈Θ
PFθlij (t+ 1 | t+ 1)}.
Khi đó dây chuyền Ll[t−, Y it ] được nối tiếp từ đỉnh Y
i
t
sang đỉnh Y j∗t+1 theo quỹ đạo chuyển trạng thái Fθ∗ và để
rõ hơn ta ký hiệu thêm chỉ số F (t+1)θ∗ . Nghĩa là với Y
i
t là
đỉnh của dây chuyền Ll[t−, Y it ] ta có
f∗εt+1(Y
i
t ) = Y
j∗
t+1.
Cần lưu ý rằng ft+1 : M [Y (t)]→ Y t+1.
Bước 3: Kiểm tra l. Nếu l < Card(f−1t (Y
i
t )) thì quay
lại làm tiếp với l := l + 1. Còn nếu l = Card(f−1t (Y
i
t ))
thì kiểm tra i. Nếu i < nt thì quay lại bước 2 với việc thay
i := i+ 1, còn nếu i = nt thì chuyển sang bước 4.
Bước 4: Kiểm tra t + 1. Nếu t + 1 < T = tn, quay lại
bước 1 với việc thay t := t+ 1, còn nếu t+ 1 > T thì kết
thúc thuật toán.
Chú ý: Trong bước 2, chúng ta cần nhấn mạnh và nói
rõ hơn vấn đề sau.
Khi xét tới dây chuyền Ll[t−, Y it ], ta giả sử dây chuyền
này xuất phát từ đỉnh đầu Y ms tại thời điểm s, s ∈ [0, T ]
nào đó, khi đó ta hoàn toàn xác định
[s, t] = [ts, ts+1] ∪ (ts+1, ts+2] ∪ . . . ∪ (tk, t].
Do thuật toán là đệ quy tuần tự, nên khi xét đến thời điểm
t thì tất cả các quỹ đạo chuyển trạng thái tối ưu trên từng
khoảng giữa các bước là Fht∗ , h 6 t, đã được xác định. Ta
xây dựng “hàm dán” như sau:
FLS(•) = {Fht∗(•), với • ∈ (h− 1, h]; tq 6 h− 1;h 6 t}.
Hàm FLS mô tả hệ động lực của mục tiêu có ảnh quỹ
đạo là dây chuyền Ll[t−, Y it ]. Khi thực hiện bài toán lọc
theo (1) và (2’) trong bước 2, hệ động lực F được thực
hiện là
F (•) =
{
FLS(•), • 6 t,
Fθ(•), t 6 • 6 t+ 1.
Vì lẽ FLS(•) đã được xác định nên trong ký hiệu ta chỉ
ký hiệu phụ thuộc Fθ (trong ký hiệu PFθlij (t+ 1 | t+ 1)).
V. THẢO LUẬN
Các phương pháp tiên tiến hiện hành như đã nêu lên
trong mục I (GNN, JPDA, MHT, NNJPDA), đều không đề
cập đến khái niệm và xét trường hợp mục tiêu bị che khuất.
Do đó, trong trường hợp mục tiêu bị che khuất, các thuật
toán này không giải quyết được tình trạng có bị mất mục
tiêu, có bị mất quỹ đạo bám, liên quan đến hạn chế về
những xử lý trong cập nhật phần tử đổi mới (trạng thái mới
của mục tiêu).
Bài báo này đã giải quyết được vấn đề đó dựa trên phương
pháp liên kết dữ liệu thông qua hệ thống ánh xạ được xây
dựng đệ quy từng bước. Hệ thống ánh xạ này không chỉ
quan tâm tới bản thân số liệu quan sát mà còn tính đến cả
lịch sử quỹ đạo quá khứ có thể có của số liệu (bao gồm tập
dữ liệu DLl[t−, Y it ], thông tin lịch sử dáng điệu chuyển
53
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
Bắt đầu
Nhập: ε
t := 0; i := 0; l := −1; j := 0
t := t + 1, Nhập Y (t)
i := i + 1
l := l + 1
j := j + 1
Tính PFqlij (t + 1|t + 1)
δli = min
1≤j≤nt+1
min
θ∈Θ
P
Fq
lij (t + 1|t + 1)
j < nt+1
δli > ε
l < Card
(
f−1t (Y
i
t )
)
i < nt
t < T
Kết thúc
Y it là điểm cuối Nối Y
i
t với Y
j∗
t+1
Đúng Sai
Sai
Sai
Sai
Sai
Đúng
Đúng
Đúng
Đúng
Hình 1. Sơ đồ khối xử lý thuật toán.
trạng thái FLS(•). Với thuật toán tìm lời giải - tối ưu,
chúng ta sẽ ước lượng được quỹ đạo của mục tiêu thông
qua dữ liệu quan sát của dây truyền dữ liệu ảnh (lời giải
tối ưu ở đây được hiểu theo nghĩa làm cực đại xác suất hậu
nghiệm tại mỗi bước).
Mô hình mà bài báo nghiên cứu có rất nhiều ứng dụng
trong nhiều lĩnh vực cả dân sự lẫn quân sự. Một ví dụ
minh họa cho việc sử dụng phương pháp đề xuất là trong
hệ thống theo dõi phòng không. Mục tiêu quan sát là các
máy bay cần theo dõi. Hệ thống quan sát là hệ thống ra
đa phòng không trong đó thuật toán đề xuất có thể được
cài đặt để theo dõi sự biến mất của mục tiêu khi máy bay
bị bắn hạ hoặc ra ngoài vùng tác chiến. Việc bám quỹ đạo
của mục tiêu được thể hiện qua tiêu đồ tham mưu của bộ
chỉ huy.
Bài báo này tập trung xây dựng phương pháp và chứng
minh tính đúng đắn bằng toán học, cũng như đề xuất giải
thuật tương ứng. Do giới hạn số trang, việc nghiên cứu thực
nghiệm mô phỏng bằng dữ liệu mô phỏng và dữ liệu thực
tiễn sẽ được quan tâm trong những công trình tiếp theo.
54
Tập 2019, Số 1, Tháng 9
VI. KẾT LUẬN
Bài báo trình bày một số kết quả nghiên cứu mới về bài
toán MTT trong điều kiện có thể xảy ra tình trạng mục tiêu
bị che khuất, gây nên mất mục tiêu, mất quỹ đạo bám mà
các nghiên cứu hiện hành chưa giải quyết được. Trước hết,
chúng tôi đã xây dựng phương pháp liên kết dữ liệu đệ quy
bằng hệ thống ánh xạ không chỉ tính đến bản thân dữ liệu
quan sát mà còn tính đến cả lịch sử quỹ đạo của dữ liệu đó.
Hơn nữa, theo quan điểm của suy luận Bayes, đưa ra khái
niệm lời giải tối ưu từng bước làm cực đại xác suất hậu
nghiệm và chứng minh sự tồn tại của nó đối với phương
pháp liên kết dữ liệu như đã đưa ra. Cuối cùng, chúng tôi
đã kết hợp với lọc Kalman, đưa ra khái niệm lời giải tối
ưu ε-ngưỡng (gọi tắt là ε-tối ưu) và đưa ra thuật toán tìm
lời giải đó đối với phương pháp liên kết dữ liệu đã đưa ra.
TÀI LIỆU THAM KHẢO
[1] Y. Bar-Shalom, P. K. Willett, and X. Tian, Tracking and data
fusion. YBS Publishing, CT, 2011.
[2] S. Blackman and R. Popoli, Design and analysis of modern
tracking systems. Artech House, Norwood, MA, 1999.
[3] J. Yi, Y. Du, F. Liang, and C. Zhou, “An auto-tracking
algorithm for mesoscale eddies using global nearest neighbor
filter,” Limnology and Oceanography: Methods, vol. 15,
no. 3, pp. 276–290, 2017.
[4] Y. Bar-Shalom and X.-R. Li, Multitarget-multisensor track-
ing: principles and techniques. YBS Publishing, CT, 1995.
[5] K.-C. Chang and Y. Bar-Shalom, “Joint probabilistic data
association for multitarget tracking with possibly unresolved
measurements and maneuvers,” IEEE Transactions on Auto-
matic Control, vol. 29, no. 7, pp. 585–594, 1984.
[6] S. Yang, K. Thormann, and M. Baum, “Linear-time joint
probabilistic data association for multiple extended object
tracking,” in 2018 IEEE 10th Sensor Array and Multichannel
Signal Processing Workshop (SAM), 2018, pp. 6–10.
[7] S. S. Blackman, “Multiple hypothesis tracking for multiple
target tracking,” IEEE Aerospace and Electronic Systems
Magazine, vol. 19, no. 1, pp. 5–18, 2004.
[8] M. Mallick, S. Coraluppi, C. Carthel, V. Krishnamurthy,
and B. Vo, “Multitarget tracking using multiple hypothesis
tracking,” in Integrated Tracking, Classification, and Sensor
Management: Theory and Applications. Wiley Online
Library, 2012, ch. 2, pp. 165–201.
[9] D. Reid, “An algorithm for tracking multiple targets,” IEEE
transactions on Automatic Control, vol. 24, no. 6, pp. 843–
854, 1979.
[10] Z. Zhang, K. Fu, X. Sun, and W. Ren, “Multiple target
tracking based on multiple hypotheses tracking and modified
ensemble Kalman filter in multi-sensor fusion,” Sensors,
vol. 19, no. 14, p. 3118, 2019.
[11] W. D. Blair and M. Brandt-Pearce, “NNJPDA for track-
ing closely spaced Rayleigh targets with possibly merged
measurements,” in SPIE Conference on Signal and Data
Processing of Small Targets, vol. 3809, 1999, pp. 396–408.
[12] S. Varghese, P. Sinchu, and D. S. Bhai, “Tracking crossing
targets in passive sonars using NNJPDA,” Procedia Com-
puter Science, vol. 93, pp. 690–696, 2016.
[13] N. Hang and N. Nam, “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,” Tạp chí nghiên cứu Khoa học Công nghệ
Quân sự, no. 46, pp. 149–157, 2016.
[14] H. Durrant-Whyte et al., “Introduction to estimation and the
Kalman filter,” Autralia, Tech. Rep., 2001, version 2.2.
[15] S. Sa¨rkka¨, Bayesian filtering and smoothing. Cambridge
University Press, 2013.
[16] S. Yang and M. Baum, “Extended Kalman filter for extended
object tracking,” in 2017 IEEE International Conference on
Acoustics, Speech and Signal Processing (ICASSP), 2017,
pp. 4386–4390.
Nguyễn Thị Hằng sinh năm 1975. Bà tốt
nghiệp Đại học ngành Toán, tại Trường
Đại học Sư phạm Hà Nội năm 1996, Thạc
sỹ chuyên ngành Xác suất Thống kê, tại
Trường Đại học Khoa học Tự nhiên, Đại
học Quốc gia Hà Nội, năm 2000. Hiện công
tác tại Bộ môn Toán, Khoa Khoa học Cơ
bản, Trường Đại học Mỏ - Địa chất. Lĩnh
vực nghiên cứu bao gồm mô hình tuyến tính nhiều biến, mô hình
chuỗi thời gian, tiếp cận Bayes và lọc Bayes, bài toán theo dõi đa
mục tiêu di động.
55