Ứng dụng mạng nơron hopfield để giải bài toán liên kết điểm dấu trong bám quỹ đạo mục tiêu ra đa

Ra đa P.N.Huy, B.Q.Thắng, “Ứng dụng mạng nơron Hopfield quỹ đạo mục tiờu ra đa.” 30 ứNG DụNG MạNG NƠRON HOPFIELD Để GIảI BàI TOáN LIÊN KếT ĐIểM DấU TRONG BáM QUỹ ĐạO MụC TIÊU RA ĐA phạm ngọc huy*, bùi quý thắng** Tóm tắt: Bài báo trình bày kết quả nghiên cứu ứng dụng mạng nơron nhân tạo Hopfield để tính xác suất liên kết giữa điểm dấu mục tiêu và quỹ đạo trong các thuật toán liên kết dữ liệu theo xác suất (PDA) và thuật toán liên kết dữ liệu theo xác suất đồng thời (JPDA) áp dụng trong các bộ lọc bám quỹ đạo mục tiêu của hệ thống tự động xử lý cấp 2 thông tin trên các đài ra đa hiện đại. Các kết quả mô phỏng đã chứng minh ưu điểm của các thuật toán này. Từ khoá: Liên kết dữ liệu theo xác suất (PDA), Liên kết dữ liệu theo xác suất đồng thời (JPDA), Bộ lọc Kalman, Tỷ số hợp lý, Tiờu chuẩn lân cận gần nhất, Bài toỏn TSP. 1. mở đầu Việc bám mục tiêu trong điều kiện có nhiễu là một trong những vấn đề rất phức tạp trong xử lý cấp 2 tin tức ra đa. Tính chất phức tạp thể hiện ở chỗ khi có nhiễu, thì ngay kể cả việc ra đa có hệ thống chống nhiễu tốt thì số lượng điểm dấu giả đến đầu vào xử lý cấp 2 cũng rất đáng kể. Do vậy, bên cạnh bài toán truyền thống là làm chính xác các tham số quỹ đạo trong quá trình bám, thì việc nhận diện và lọc lấy điểm dấu trong số các điểm dấu thu nhận để làm mới tham số quỹ đạo, nối dài nó trong khi bám là một nhiệm vụ quan trọng không kém. Đây chính là việc liên kết điểm dấu (LKĐD) với quỹ đạo. Trong các tài liệu [1, 2, 5], đã cho thấy rằng rằng: xử lý liên kết dữ liệu và lọc bám là hai phần không thể tách rời của bám quỹ đạo mục tiêu. Để giải quyết vấn đề LKĐD, trong lý thuyết ra đa, thường thường có một số cách tiếp cận như sau: Cách thứ nhất, dựa trên việc sử dụng hàm hợp lý. Tại chu kỳ nhịp lấy tin xác định, điểm dấu được chọn trong số điểm dấu thu được để nối dài quỹ đạo đang xét phải có hệ số hợp lý lớn nhất. Thuật toán lân cận gần nhất áp dụng cách tiếp cận này. Ưu điểm của thuật toán này là đơn giản, dung lượng tính toán ít, phù hợp với mục tiêu đơn. Nhược điểm: Khi có nhiều mục tiêu, quỹ đạo giao cắt nhau thì thuật toán này sẽ không hiệu quả. Cách tiếp cận thứ hai-Bayes tối ưu, tại từng chu kỳ nhịp lấy tin, tiến hành tính toán xác suất hậu nghiệm các phương án (có thể) xây dựng quỹ đạo mục tiêu theo dữ liệu của tất cả các chu kỳ nhịp lấy tin trước đó. Quỹ đạo được chọn là quỹ đạo có xác suất hậu nghiệm lớn nhất. Dễ nhận thấy rằng, số các phương án quỹ đạo sẽ vô cùng lớn kéo theo dung lượng tính toán sẽ tăng lên rất nhiều. Một cách tiếp cận thứ ba được đề xuất, nó dung hòa được các ưu, nhược điểm của các cách tiếp cận trên đó là Bayes cận tối ưu mà đại diện là các thuật toán LKĐD theo xác suất PDA(Probabilistic Data Association) và JPDA (Joint Probabilistic Data Association) [3]. 2. liên kết điểm dấu theo xác suất Giả sử có T mục tiêu đang được bám quỹ đạo tại thời điểm k được mô hình hóa bằng hệ thống động học tuyến tính rời rạc theo thời gian mô tả bằng phương trình : ( + 1) = ()() + (), = 1,2, , (1) trong đó, () là các véctơ trạng thái mục tiêu kích thước 1, () là ma trận chuyển trạng thái mô tả tính chất động học của mục tiêu và () là véctơ tạp của mục tiêu. Chỉ số t tương ứng với mục tiêu thứ t. Trạng thái ban đầu (0) với = 1, 2, , được giả thiết là tạp trắng với trung bình (0|0) và ma trận hiệp biến (0|0) đã biết. Các vectơ tạp đối với mỗi mục tiêu được giả thiết là không tương quan có trung bình bằng 0, phân bố Gauss với hiệp biến đã biết: 0)(;)(})]()[({ ³ kQkQkwkwE tkj tTtt d (2) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 31, 06 - 2014. 31 trong đó, chỉ số “t“ biểu thị ma trận chuyển vị và d là hàm delta Cronecker (d = 1, = ; d = 0, ). Phương trình đo là: () = ()() + (), = 1,2, , (3) trong đó, () là véctơ đo kích thước 1, () là ma trận đã biết và () ma trận tạp được giả thiết có trung bình bằng 0, phân bố Gauss với phương sai đã biết là: {()()}= ()d , ()³ 0 (4) Để ước lượng trạng thái động học của mục tiêu trong lọc và bám quỹ đạo, công cụ lọc Kalman thường được sử dụng [2]. Theo đó, ta có trạng thái của mục tiêu tại thời điểm k và hàm hiệp biến ngoại suy: )(xˆ)(F)1(xˆ kkkkk  ; Tkkkkkk )](F[)(P)(F)1(P  (5) giá trị đo ngoại suy: )1(xˆ)1(H)1(zˆ kkkkk  (6) với sai số đo: )1(zˆ)1(z)1(z~ xkkk  (7) Trong điều kiện có nhiễu, việc giảm sự phức tạp tính toán của phương trình cập nhật là rất cần thiết để hạn chế số lượng các điểm dấu. Một quá trình lựa chọn để kết hợp điểm dấu vào bộ ước lượng trạng thái từ hàng loạt các điểm dấu cần xem xét là cần thiết. Quá trình này là hình thành một cửa sóng đa kích thước để loại ra một số điểm dấu thu nhận được. Theo[1], Bar-Shalom đã đề xuất thủ tục hợp thức cho một điểm dấu từ một mục tiêu để liên kết với một quỹ đạo đã có như sau. Nếu: ( + 1) = ( + 1) − ̂ ( + 1|) ( + 1) ( + 1) − +1 = +1′+1−1 +1 g (8) được định nghĩa như là khoảng cách thống kê của điểm dấu zj tính từ vị trí dự đoán ̂ thì điểm dấu thứ j là ( + 1) được hợp thức cho mục tiêu t khi giá trị khoảng cách bé hơn tham số ngưỡng g. Vùng được định nghĩa bằng phương trình (8) được gọi là vùng hợp lệ hay là cửa sóng, nó là một elipsoid tập trung xác suất. Các điểm dấu nằm trong cửa sóng được xem là hợp lệ, các điểm dấu nằm ngoài bị loại bỏ. Nếu điểm dấu thứ j tương ứng là của mục tiêu thứ t thì ( + 1)có một phân bố g với M bậc tự do, M là bậc của x(k). Tham số ngưỡng g được lấy từ bảng phân bố g - bình phương từ trung bình trọng số của lượng đổi mới phương trình (8) định nghĩa vùng hợp lệ. Đại lượng = g được coi như độ lệch chuẩn của cửa sóng. Ngưỡng thường được chọn tiên nghiệm và giữ bằng hằng số cho mọi ứng dụng. 2.1. Thuật toán LKĐD theo xác suất PDA Theo [3], LKĐD theo xác suất PDA là một thuật toán Bayess cận tối ưu, trong đó, giả thiết rằng chỉ có mục tiêu cần quan tâm quỹ đạo của nó đã được khởi tạo. PDA tập trung vào một vài giả thiết quan trọng nhất bằng việc hình thành một cửa sóng hợp lệ có tâm nằm ở vị trí dự đoán ̂ của mục tiêu tại mỗi thời điểm lấy tin. Một trong những điểm dấu hợp lệ có thể bắt nguồn từ mục tiêu trong khi những điểm dấu còn lại được giả thiết từ nhiễu và được mô hình hóa như những biến ngẫu nhiên phân bố độc lập đồng nhất. Tập điểm dấu đo hợp lệ được định nghĩa tại phương trình (8), điều này dẫn đến tập tích lũy các điểm dấu đo cho mục tiêu t tính đến thời điểm k là: () ≡ {()} ớ = 1, (9) P.N.Huy, B.Q.Thắng32 Xác suất được đưa ra bằng cách lập ra giả thiết cơ bản của PDAF như sau: {()|( − 1 kỳ vọng có điều kiện của trạng thái mục tiêu (|) = Đó là ước lượng PDA tổng quát bằng tổng tất cả các ước lượng có trọng số của các giả thuyết khác nhau. Nếu xác suất của việc tính như sau : () ở đây, () là hàm hợp lý cho mỗi tín hiệu điểm dấu: () = ⎩ ⎪ ⎨ ⎪ ⎧ ì [(1 − () 1 (2) |()| 0 trong đó, l là hàm mật độ nhiễu, số máy thu trong khi G(k) là xác suất điểm dấu rơi vào vùng cửa sóng. 2.2. Thuật toán LKĐD theo xác suất đồng thời JPDA Điểm hạn chế của thuật toán PDA là chỉ có thể áp dụng cho một mục tiêu tại mỗi thờ điểm. Hạn chế này có thể khắc phục bằng cách sử dụng thuật toán JPDA trong đó xem xét nhiều mục tiêu một cách đồng thời. Dựa trên ma trận hợp lệ, các giả thuyết liên kết dữ liệu (các sự kiện khả thi) được tạo ra hướng đến các ràng buộc liên kết JPDA như 1. Mỗi điểm dấu đo chỉ có thể có một nguồn gốc (từ mục tiêu hoặc từ nhiễu) 2. Không thể có hơn một điểm dấu có nguồn gốc từ một mục tiêu 3. Tất cả các điểm dấu phải được gán Mỗi sự kiện khả thi đại diện bằng một ma trận giả thuyết của ma trận hợp lệ . Các phần tử của Ω = 1 ế Ω = 1 ế Ω = 1 à 0 Tương tự với các ràng buộc trên, trong ngoại trừ = 0 và có chính xác một phần tử bằng 1 trong mỗi hàng. Theo [3], dựa trên mỗi ma trận giả thuyết được lập, xác suất có điều kiện của sự kiện khả thi được tính toán theo công thức: Ω| = 1 ở đây, là tập của tất cả các điểm dấu tính đến thời điểm hiện thời lượng điểm dấu được phát hiện trong các sự kiện khả thi và j được liên kết với mục tiêu t chung tất cả các điểm dấu tới cả đội hình mục tiêu là : , “Ứng dụng mạng nơron Hopfield quỹ đạo mục ti )}= [();(| − 1), (| − 1)] j tại thời điểm k có thể tính như sau: () (|) phát hiện đúng là D(k) thì xác suất LKĐD được = () ∑ () ()] ế = 0 − 1 2 () () , ế ≠ 0 à[Ω()] = 1 ỏ ườ ℎợ ℎỏ D(k) là xác suất phát hiện đúng và là một hàm của thông : Ω có kích thước giống như Ω được định nghĩa như sau: 1 à để ấ đượ ả ℎế ừ ℎễ để ấ đượ ả ℎế ừ ụ ờ ỏ ườ ℎợ ℎỏ Ω có ít nhất một phần tử bằng 1 trong mỗi cột () (.) () : k , c là hằng số, Ω = 1 biểu thị rằng điểm dấu . Hàm hợp lý chung () tương ứng với giả thuyết liên kết Ra đa ờu ra đa.” (10) (11) (12) (13) i (14) (15) là số Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 31, 06 - 2014. 33 () = ⎩ ⎪ ⎨ ⎪ ⎧ ì [(1 − ()()] , ế = 0 1 (2) |()| − 1 2 () () ế ≠ 0 à[Ω()] = 1 0 ỏ ườ ℎợ ℎỏ (16) ở đây, l được định nghĩa là mật độ nhiễu, () là xác suất phát hiện đúng. Xác suất hậu nghiệm liên kết chung cho tất cả các giả thuyết được tính toán như sau: () = (Ω|)Ω (17) () = 1 − () (18) Xác suất liên kết JPDA sử dụng để cập nhật phương trình trạng thái sử dụng lượng đổi mới được tổng hợp như ở PDA. 3. ứng dụng mạng nơron hopfield Trong liên kết điểm dấu Từ các trình bày ở trên về LKĐD, ta thấy rằng cơ sở của việc liên kết là sử dụng xác suất liên kết của của điểm dấu với mục tiêu để quyết định sự kiện điểm dấu thu nhận được có phải thuộc quỹ đạo của mục tiêu đang bám sát hay không. Các xác suất liên kết này được xác định theo các công thức (12) và (17) với đầu vào là các hàm hợp lý được xác định theo các công thức (13) và (16). Với số lượng mục tiêu tăng lên thì dung lượng tính toán các xác suất này sẽ phải tăng theo hàm lũy thừa [3]. Vì vậy, để đảm bảo bám sát quỹ đạo các mục tiêu trong vùng quan sát trong tình huống nhiễu phức tạp trong thời gian thực, cần phải có một công cụ tính toán xác suất liên kết theo phương pháp mới. Công cụ mạng nơron nhân tạo Hopfield là một sự lựa chọn thích hợp. ý tưởng sử dụng mạng nơron nhân tạo trong liên kết điểm dấu rađa bắt nguồn từ bài toán kinh điển người bán hàng rong - TSP (Traveling salesman Problem). Nội dung bài toán là: Một người bán hàng rong phải đi đến tất cả n thành phố và trở lại đúng nơi xuất phát, khoảng cách giữa các thành phố là biết trước, mỗi thành phố chỉ được đến tối đa một lần. Hãy sắp xếp lộ trình cho người đó sao cho tổng quãng đường đi là ngắn nhất. Theo [3], mạng Hopfield sẽ đạt tới trạng thái cân bằng khi hàm năng lượng của nó đạt tới giá trị cực tiểu. Vì vậy, từ bài toán cho trước, ta xây dựng một hàm mục tiêu F nào đó (đã được xử lý các ràng buộc) và buộc F = E (E là hàm năng lượng), sau đó tìm ra mối liên hệ giữa các biến của chúng. Đây là lý do mà mạng Hopfield rất phù hợp với các bài toán tối ưu tổ hợp như: bài toán người bán hàng, tìm đường đi tối ưu cho tuyến đường xe bus trường học, bài toán người đưa thư,... ở đây, việc xác định xác suất LKĐD ( )ix k từ các hàm hợp lý cũng gần giống và tương tự như giải bài toán người bán hàng rong. Các điều kiện ràng buộc đối với vấn đề LKĐD(Data Association Problem - DAP) sẽ được hình thành từ những cách đặt vấn đề sau: - Tổng trọng số từng cột phải thỏa mãn biểu thức 0 ( ) 1 n i x x k   - Không thể thu được hai điểm dấu đồng thời từ một mục tiêu và cũng không thể có một điểm dấu của đồng thời hai mục tiêu. Hàm năng lượng LKĐD có dạng là: Ra đa P.N.Huy, B.Q.Thắng, “Ứng dụng mạng nơron Hopfield quỹ đạo mục tiờu ra đa.” 34 21 2 3 , , , , , 2 24 5 , , ( 1) 2 2 2 ( ) ( ) 2 2 DAP x i x j x i y i x i x i j i i x y x i x i j x i x x i l x i x i j i l x M M M E V V V V V M M V V                     (19) trong đó, i x  là hàm chuẩn hóa của tỉ số hợp lý ( )i x p k có dạng: 0 ( ) ( ) i i x nx i l l p k p k     (20) Từ đó, việc xây dựng mạng chính là triển khai đầy đủ các điều kiện ràng buộc đối với hàm năng lượng. Theo [3], sau khi biến đổi và rút gọn, hàm năng lượng trọng số có thể viết lại dưới dạng: ∗ = − 1 2 ,,, ì , ì , − , ì , (21) Các trọng số tiếp hợp , , ,x i y j T hoàn toàn không phụ thuộc vào hàm hợp lý chuẩn hóa và được xác định giá trị như sau: ,,, = {[]} ế , ế , () ế , ế , (22) Các hệ số M1...M5 có thể được điều chỉnh để kiểm soát việc nhấn mạnh vào các đặc tính và ràng buộc khác nhau. M4 có giá trị lớn sẽ làm cho Vx,i gần đến i x  điều này tương đương với xác xuất liên kết PDA thông thường. Nếu M1,M2,M3 lớn thì phương pháp liên kết điểm dấu sẽ trở thành NNPDA (Nearest-Neighbor PDA). Một tổ hợp cân bằng cho cả 5 số hạng trên sẽ dẫn đến một kết quả đầy đủ nhất cho tất cả các đặc tính của thuật toán JPDA. 4. mô phỏng và kiểm nghiệm 4.1. Đặt đầu bài Như trên đã đặt vấn đề, có thể phát biểu đầu bài tính toán kiểm nghiệm kết quả nghiên cứu lý thuyết như sau: ứng dụng công cụ mạng Hopfield tính toán xác suất LKĐD dùng trong lọc, bám quỹ đạo trong xử lý cấp 2 tin tức rađa với số lượng quỹ đạo Imax được xử lý. Tiến hành đánh giá chúng theo các tiêu chí lựa chọn. 4.2. Các dữ liệu đầu vào Với đầu bài như trên, dữ liệu đầu vào sẽ bao gồm: - Số lượng quỹ đạo có thể thực hiện không vượt quá Imax. - Số các chu kỳ nhịp lấy tin là kmax . - Trong từng chu kỳ nhịp lấy tin k và ứng với mỗi quỹ đạo, tồn tại không quá một điểm dấu chân thực và không quá số điểm dấu giả đưa vào ban đầu. 4.3. Các kết quả đầu ra cần có Các quỹ đạo được lọc, bám hiển thị trong hệ tọa độ Đề-các. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 31, 06 - 2014. 35 4.4 Thuật toán tổng quát Như đã chỉ ra trên Hình 1, lưu đồ thuật toán tổng quát sẽ bao gồm các thuật toán sau: - Thuật toán tạo và xuất dữ liệu mô phỏng đầu vào . - Thuật toán mạng Hopfield tính xác suất liên kết điểm dấu. - Thuật toán lọc Kalman dùng để lọc, bám quỹ đạo, ước lượng các tham số quỹ đạo. 1:k maxkk  1:  kk Hình 1. Lưu đồ thuật toán tổng quát . Kết quả mô phỏng như hình 2. a. Bám sát 3 mục tiêu b. Bám sát 5 mục tiêu c. Bám sát 20 mục tiêu Hình 2. Kết quả mô phỏng quỹ đạo. Nhận xét: Với môi trường mô phỏng ở mức trung bình (Máy tính Destop cores I5, 3GHz, RAM 4GB, HDD 400GB, HĐH Windows 7 Ultimate), phần mềm mô phỏng sử dụng MATLAB R10a, từ kết quả nhận được(hình 2 và 3) ta có những nhận xét, đánh giá như sau: - Số lượng các quỹ đạo được bám sát đầy đủ theo đầu bài đặt ra(3,5 và 20 quỹ đạo). - Khi mục tiêu cơ động (tốc độ và hướng bay mục tiêu thay đổi), bộ lọc bám nơron vẫn đảm bảo bám sát, không có hiện tượng mất bám. - Các giá trị sai số bám sát, ước lượng tốc độ của các bộ lọc bám có các điểm dấu đầu vào được gán với quỹ đạo mục tiêu bằng phương pháp mạng nơron đều thỏa mãn các điều kiện ban đầu (Tốc độ trung bình của mục tiêu là 400m/s). - Khi số lượng mục tiêu tăng lên chất lượng, bám sát cũng thay đổi tương ứng theo hướng giảm dần biểu hiện ở sự nhấp nhô, gấp khúc của đường quỹ đạo. Khi tăng đến 20 mục tiêu mới xuất hiện sự mất bám sát. Với cấu hình phần cứng ở trên, kết quả này là chấp nhận được. Ra đa P.N.Huy, B.Q.Thắng, “Ứng dụng mạng nơron Hopfield quỹ đạo mục tiờu ra đa.” 36 a. Sai số bám sát b. Ước lượng tốc độ mục tiêu Hình 3. Sai số bám sát và ước lượng tốc độ. 5. kết luận Phương pháp lọc bám dùng mạng nơron để liên kết điểm dấu đã hoàn toàn thỏa mãn các tiêu chí của một bộ bám sát quỹ đạo mục tiêu ra đa. Các chỉ tiêu tham số của nó đều bằng và tốt hơn các bộ lọc bám dùng LKĐD theo xác suất sử dụng phương pháp tính PDA, JPDA theo cách giải tích. Các kết quả tính toán mô phỏng ở trên đã chứng minh tính đúng đắn của kết luận này. Tài liệu tham khảo [1]. Bar-Shalom, ”Radar Tracking and Data Association,” Orlando Acad. Press, Inc. 1998. [2]. Blackman,“Multiple-Target tracking with radar application,”MA, Artech House. 2005 [3]. Thomas K. Rob, “A Comparison of Conventional And Neural Network Data Association Techniques For Multi-target tracking,” Electrical And Computer Engineering Royal Military College of Canada . Kingston, Ontario-Nov, 1999. [4]. D.Sengupta and R.T. Iltis, “Neural Solution to the Multi-target Data Association Problem,” IEEE Transaction On Aerospace & Electro. Sys., AES- (1989), pp.96-108. [5]. Фарина Ф , Cтудер Ф., “Цифровая Обработка РЛИ. Сопровождение Целей,” Изд. Радио и Связъю , 1993. c. 88-98, 160-167. abstract The hopfield network application for solution to data associate problem in radar target trajectory tracking The paper presents studied results by the Hopfield Neural network application to compute associate probabilities between the target’s plot and trajectory in Probabilistic Data Association Algorithms (PDAA), and Joint Probabilistic Data Association (JPDA), which are used in the target,s trajectory tracking filter for the automatic radar informations secondary processing system of the modern radars. Their advantages are carried out by simulative results. Keywords: PDA, JPDA, PDAF, JPDAF, Kalman Filter, EKF, Likelihood ratio, Traveling Problem. Nhận ngày 24 tháng 10 năm 2014 Hoàn thiện ngày 10 tháng 05 năm 2014 Chấp nhận đăng ngày 25 tháng 05 năm 2014 Địa chỉ: * Viện KTQS Phòng không - Không quân ** Học viện KTQS