XÂY DỰNG THUẬT TOÁN KHỚP BẢN ĐỒ
(MAP MATCHING) ỨNG DỤNG LOGIC MỜ
ThS. ĐẶNG QUANG THẠCH
Bộ môn Điều khiển học
Khoa Điện - Điện tử
Trường Đại học Giao thông Vận tải
Tóm tắt: Trong các hệ thống giám sát, dẫn đường sử dụng hệ thống định vị toàn cầu
GPS ta cần hiển thị vị trí của xe trên bản đồ số sao cho biểu tượng xe phải nằm trên tuyến
đường nó đang chạy nhưng do sai số của phép định vị nên nhiều khi ta thấy xe không chạy
trên đường mà có thể nằm giữa các tòa nhà hay dưới mặt hồ… Để xử lý tính huống này người
ta sử dụng các thuật toán khớp bản đồ (map matching). Nguyên tắc chung của các phương
pháp khớp bản đồ là sử dụng dữ liệu về trạng thái hoạt động hiện tại và trong quá khứ kết hợp
dữ liệu trong CSDL GIS để xác định một điểm trên đường có nhiều khả năng là vị trí hiện tại
của xe nhất. Bài báo này trình bày về một phương pháp khớp bản đồ trên cơ sở sử dụng các
bộ suy diễn bằng logic mờ (fuzzy logic).
Summary: GPS - based Tracking and Routing systems need to display vehicle symbols
on digital maps at specific points on the road where the vehicle is moving. However, due to
errors in positioning, sometimes we see vehicle symbols running through a building or under a
lake. To overcome this problem, we can use a method termed “Map matching”. According to
this method we use infomation on operation status in the past and data in GIS Database to
locate a point which is most likely to be the current position of the vehicle on the road. This
paper introduces a method based on fuzzy logic to solve the above problem.
ĐT
I. CÁC CƠ SỞ XÂY DỰNG THUẬT TOÁN
1. Thông tin nhận được từ các máy thu GPS
Các máy thu GPS xử lý tín hiệu nhận được từ vệ tính sau đó cung cấp cho ta dữ liệu theo
các đặc tả trong chuẩn NMEA, đây là tài liệu chuẩn hóa về 2 nội dung: (1) chuẩn hóa giao diện
kết nối giữa máy thu GPS và máy tính, (2) chuẩn hóa về định dạng dữ liệu máy thu GPS gửi về
máy tính. Theo nội dung thứ 2, máy thu gửi dữ liệu về máy tính dưới dạng các câu, mỗi câu
chứa một số trường thông tin khác nhau, trường thông tin đầu tiên phục vụ phân loại câu, các
trường còn lại là kết quả xử lý tín hiệu nhận từ vệ tinh. Để phục vụ bài toán định vị và thực hiện
thuật toán map matching ta quan tâm đến dữ liệu trong các câu: $GPRMC, $GPGSV. Trong đó
$GPRMC (Recommended Minimum sentence C) chứa các thông tin về vị trí (kinh độ, vĩ độ),
tốc độ và thời gian. Một câu $GPRMC hoàn chỉnh có dạng như sau:
$GPRMC,123519,A,4807.038,N,01131.000,E,022.4,084.4,230394,003.1,W*6A
Trong đó:
123519 Thời điểm máy thu chốt số liệu: 12:35:19 UTC
A Trạng thái: A (Active) dữ liệu hợp lệ hoặc V (Void): dữ liệu không hợp lệ
4807.038,N Vĩ độ (Latitude) : 48 deg 07.038' N
01131.000,E Kinh độ (Longitude) : 11 deg 31.000' E
022.4 Tốc độ di chuyển tính bằng đơn vị knots
084.4 Góc của quỹ đạo chuyển động tại điểm hiện tại
230394 Ngày: 23/3/1994
003.1,W Biến thiên từ trường
*6A Mã kiểm soát lỗi
Câu $GPGSV (Satellites in view) chứa các thông tin cho biết trạng thái các vệ tinh trong
tầm nhìn, trong đó có: số lượng vệ tinh, vị trí các vệ tinh, cường độ tín hiệu. Mỗi vệ tinh có một
mã PRC (Pseudo-Random Code) riêng vì vậy PRC được sử dụng như mã số để để phân biệt các
vệ tinh với nhau. Vị trí tương đối của vệ tinh với máy thu được xác định qua 2 tham số azimuth
(phương vị) và elevation (cao độ). Cường độ tín hiệu của một vệ tinh được đánh giá thông qua
thông số SNR (signal-to-noise ratio), đây là một số nguyên trong khoảng 0 đến 100, giá trị này
càng lớn càng tốt. Thông tin về các vệ tinh trong tâm nhìn được gửi về theo định kỳ, dữ liệu mỗi
lần gửi có thể chứa trong trong nhiều câu $GPGSV liên tiếp. Các câu trong cùng một nhóm có 3
từ đầu tiên có giá trị bằng nhau, chúng có ý nghĩa như sau:
ĐT
STT từ trong câu Nội dung
1 Tổng số câu chứa dữ liệu sẽ được gửi về
2 Số thứ tự của câu
3 Số vệ tinh trong tầm nhìn của máy thu
Các nhóm bốn từ tiếp theo trong câu cung cấp thông tin về từng vệ tinh trong tầm nhìn,
các từ trong mỗi nhóm có ý nghĩa như sau:
STT từ trong nhóm Nội dung
1 Mã số của vệ tinh (PRN)
2 Phương vị, đơn vị là độ
3 Cao độ, đơn vị là độ
4 Cường độ tín hiệu (SNR), đơn vị là dB
Từ cuối cùng bắt đầu bằng dấu “*” là Mã kiểm tra lỗi*
Ví dụ: Dưới đây là dữ liệu về các vệ tinh trong tầm nhìn nhận được từ máy thu GPS, dữ
liệu này được gửi về trong 3 câu liên tiếp sau:
$GPGSV,3,1,12,18,60,031,40,21,56,194,45,09,44,039,40,22,39,332,29*78
$GPGSV,3,2,12,31,36,212,,14,34,288,29,05,30,126,43,12,24,107,35*77
$GPGSV,3,3,12,30,22,153,33,24,21,160,36,26,14,048,,15,02,061,*75
Câu thứ nhất cho ta thông tin sau:
3: Có tổng số 3 câu trong nhóm
1: Câu thứ nhất
12: 12 vệ tinh trong tâm nhìn
18: Mã số vệ tinh (PRN) = 18
60: Cao độ vệ tinh 18 (60o)
031: Phương vị vệ tinh 18 (31o)
40: Cường độ tín hiệu vệ tinh 18
21: Vệ tinh 21
56: Cao độ vệ tinh 21 (56o)
194: Phương vị vệ tinh 21 (194o)
45: Cường độ tín hiệu vệ tinh 21
ĐT
09: Vệ tinh 9
44: Cao độ vệ tinh 9
039: Phương vị vệ tinh 9
40: Cường độ tín hiệu vệ tinh 9
22: Vệ tinh 22
39: Cao độ vệ tinh 22
332: Phương vị vệ tinh 22
29: Cường độ tín hiệu
*78: Mã kiểm soát lỗi
Nếu biểu diễn dữ liệu này bằng đồ họa ta sẽ nhận được hình 1, ở đó cao độ được biểu diễn
bằng các đường tròn đồng tâm, đường tròn ngoài cùng tương ứng với góc cao độ bằng 0o, tâm
các đường tròng (vị trí đặt máy thu) tương ứng góc cao độ bằng 90o, khoảng cách giữa các
đường tròn là 30o. Phương vị vệ tinh là góc giữa đường thẳng nối vệ tinh với tâm và hướng bắc.
Số ghi bên dưới mỗi vệ tinh là mã PRN. Cường độ tín hiệu các vệ tinh là đồ thị dạng cột phía
dưới.
Hình 1. Phân bố và cường độ tín hiệu các vệ tinh
2. Độ chính xác của các máy thu GPS
Ta có thể kiểm tra các thông số về độ chính xác của các máy thu GPS từ catalog cung cấp kèm
máy. Hai thông số cơ bản có ý nghĩa với người dùng nhất trong số đó là: Sai số vị trí và sai số tốc độ.
Một máy thu có sai số vị trí ep có nghĩa là nếu máy thu báo tọa độ Pi thì thực tế vị trí thật của nó
là một điểm bất kỳ trong phạm vi đường tròng tâm Pi bán kính r = ep. Nếu sai số tốc độ là ev (ev ≥ 0)
và máy thu báo tốc độ hiện tại là vi thì tốc độ thực là một giá trị trong khoảng [vi-ev, vi+ev].
3. Phép định vị tương đối và phép định vị tuyệt đối
Phép định vị tuyệt đối cho kết quả là vị trí tuyệt đối trong hệ tọa độ địa lý, toạ độ này là kết
quả tính toán của từng lần độc lập nhau, phép định vị tuyệt đối chỉ có thể chính xác khi không tồn
tại sai số trong dữ liệu đầu vào, yêu cầu này là bất khả thi trong thực tế. Trong khi đó phép định vị
tương đối là kết quả tổng hợp của nhiều lần định vi tuyệt đối (2 lần trở nên) tham chiêu lẫn nhau.
Nếu các lần của phép định vị tướng đối được thực hiện trong một khoảng thời gian và không gian
đủ gần nhau thì có thể coi sai số trong các số liệu đầu vào là như nhau, do đó ta có thể xây dựng
phép tham chiếu giữa các lần để triệt tiêu sai số này. Phép tính khoảng cách và tốc độ là ví dụ tiêu
biểu của phép định vị tương đối. Để đo khoảng cách người ta thực hiện đồng thời 2 phép định vị
tuyệt đối bằng 2 máy thu, mỗi máy định vị một điểm, sau đó tính khoảng cách giữa 2 điểm này.
Để tính tốc độ chuyển động, máy thu tính khoảng cách giữa 2 lân định vị liên tiếp sau đó chia cho
khoảng thời gian giữa 2 lần định vị. Các tài liệu lý thuyết về định vị dùng GPS cũng khẳng định
phép định vị tương đối có độ chính xác cao hơn phép định vị tuyệt đối.
ĐT
Theo các giả thiết trên thì độ lớn và phương của vận tốc chuyển động có sai số thấp hơn
nên có thể sử dụng để nâng cao độ chính xác của phép định vị. Cụ thể ta sẽ dùng thông tin này
để chỉ ra vị trí của máy thu trong đường tròn Pi.
II. THUẬT TOÁN SUY DIỄN MỜ CHO BÀI TOÁN KHỚP BẢN ĐỒ KHI XE CHẠY
TRÊN ĐƯỜNG
i
v
r
Hình 2. Các giả thiết
Hình 2 mô tả các yếu tố bất định trong bài toán khớp bản đồ. Giả sử tại thời điểm ti-1 máy
thu cho vị trí của xe là Pi-1, vị trí trên đường tương ứng tại thời điểm đó là O, tại thời điểm ti
máy thu cho vị trí Pi, theo những phân tích về sai số trong phép định vị ở trên tọa độ thật của xe
có thể là một điểm nào đó trong đường tròng tâm Pi bán kính ep. Trong khoảng thời gian ti-ti-1
nếu xe chạy với tốc độ vmin = vi-ev thì quãng đường đi được là đoạn từ O đến N. Nếu xe chạy với
tốc độ vmax = vi + ev thì quãng đường đi được là đoạn từ O đến X. Như vậy vị trí của xe phải là
một điểm nào đó trong đoạn từ N đến X. Ta chia đoạn từ O đến X thành các đoạn: ON, OND,
OD, ODX, OX. Trong đó các đoạn OND, OD, ODX là khoảng cách xe đi được với tốc độ v,
vmin > v > vmax.
Định nghĩa đầu vào:
I1: Giá trị thực của I1 là độ dài của đoạn thẳng từ điểm Pi-1 đến Pi. Sau khi được mờ hóa nó
được so sánh với các tập mờ: OX,ODX,OD,OND,ON . 5 tập mờ trên là giá trị mờ hóa
độ lớn của các đoạn thẳng tương ứng: ON, OND, OD, ODX, OX.
Vì vận tốc xe thay đổi theo thời gian nên độ dài của đoạn OX cũng thay đổi trong từng chu
kỳ xử lý, vì vậy trước mỗi chu kỳ cần tính toán lại các tập mờ
OX,ODX,OD,OND,ON trên cơ sở giá trị thực tế của các đoạn thẳng ON, OND, OD,
ODX, OX.
I2: Giá trị thực của I2 là hệ số góc của các đoạn thẳng nối Pi-1 và Pi. Sau khi được mờ hóa I2
được so sánh với các tập mờ OX,ODX,OD,OND,ON . 5 tập mờ trên là kết quả mờ hóa hệ
số góc của các đoạn thẳng tương ứng ON, OND, OD, ODX, OX.
Tương tự như đối với các tập mờ I1, do độ cong của các đoạn đường là khác nhau nên các
tập mờ của biến I2 cũng sẽ được tính lại trong môi chu kỳ xử lý.
ĐT
Đầu ra: Đầu ra có thứ nguyên là độ dài có giá trị thực biến thiên trong khoảng từ 0 đến
Len(NX), trong đó Len(NX) là độ dài đoạn đường từ N đến X. Miền giá trị thực này được mờ
hóa thành các tập mờ N (miN), ND (miD miN), D (miD), DX (miD maX), X (maX). Giải mờ
đầu ra ta sẽ xác định được vị trí hiện tại của xe là một điểm trong đoạn đường từ N đến X.
Tập luật: Các luật trong hệ suy diễn được thể hiện trong hình 3
N N ND D D
NN ND ND D D
ND DDDDX
D D DX DX DX
DDX DX X X
I1
I2
ON
OND
OD
ODX
OX
OD
ODX OX
ON
OND
Hình 3.
III. THUẬT TOÁN SUY DIỄN MỜ CHO BÀI TOÁN KHỚP BẢN ĐỒ KHI XE TRONG
BÃI ĐỖ
Khi xe đã đi vào bãi đỗ ta không thể tiếp tục đặt biểu tượng của nó trên mặt đường, Bài
toán lúc này là xác định chính xác vị trí của xe trong bãi đỗ. Trong thực tế xe đứng yên một chỗ
