1
ROBOT DI ĐỘNG TỰ ĐỊNH VỊ KHÔNG DÙNG CỘT MỐC

Đoàn Hiệp
(+)
TS. Nguyễn Văn Giáp
(++)
(+)
Sinh viên thuộc Chương trình Đào tạo Kỹ sư chất lượng cao tại Việt Nam
(++)
Bộ môn Cơ Điện Tử , Khoa Cơ Khí, Trường Đại học Bách Khoa TPHCM

TÓM TẮT
Công việc khó khăn nhất trong điều khiển một
robot di động tự trò, đó là việc robot tự đònh vò chính
xác vò trí và hướng của nó trong không gian làm
việc. Bài báo này nhằm giới thiệu một phương pháp
đònh vò robot bằng giải thuật đònh vò không dùng cột
mốc hiện. Ý tưởng chính của giải thuật này là xác
đònh những vò trí khả thi của robot trong không gian
làm việc, sử dụng tín hiệu của cảm biến siêu âm như
là một thiết bò xác đònh khoảng cách và hướng của
robot đối với các chướng ngại vật cố đònh, để từ đó
suy ra vò trí của robot bằng cách so sánh bản đồ
toàn cục và bản đồ cục bộ quanh robot.
Từ khóa: Đònh vò, Dò đường, Cột mốc hiện, Robot di động
tự trò
ABSTRACT
An important challenge of an autonomous mobile
robot is finding its current pose (position and
orientation) within working environment. This paper

chướng ngại vật. Dựa vào bản đồ tìm được, robot sẽ
xác đònh vò trí của nó bằng việc đi tìm những vò trí
khả thi.
3. MỘT SỐ KHÁI NIỆM CƠ SỞ
3.1 Robot di động tự trò và cột mốc
Robot di động tự trò là robot có tất cả những gì
cần thiết tích hợp bên trong robot. [Marsland02]
Nghóa là robot có các pin, cảm biến, máy tính và
chương trình điều khiển để nó không được kết nối
với bất kỳ sự hỗ trợ bên ngoài nào. Chương trình
điều khiển cũng phải có khả năng điều khiển robot
mà không cần sự trợ giúp của con người. Như vậy,
cột mốc (landmark) [Borenstein96] cũng là một
hình thức hỗ trợ thông tin từ bên ngoài, được sử
dụng khá phổ biến trong nhiều ứng dụng khác.
Trong đề tài này, cột mốc không được sử dụng.
3.2 Vectơ đònh vò
Sóng siêu âm truyền đi trong không khí với vận
tốc khoảng 343 m/s. Cảm biến siêu âm phát ra và
thu về các mặt sóng siêu âm, sau đó khuếch đại
cường độ của sóng với hàm mũ theo thời gian. Cảm
biến xác đònh thời gian sóng di chuyển trong không
gian, để suy ra khoảng cách từ nó đến chướng ngại
vật gần nhất, nằm trong vùng quét của cảm biến
[Thuan03]. Vectơ đònh vò đối với một cảm biến đo
khoảng cách khi nó ghi nhận một thông số s là một
vectơ có độ lớn bằng s và có chiều là chiều của cảm
biến đó. (xem hình 1) [Brown00]
3.3 Vò trí khả thi
Ý tưởng cơ bản nhất của thuật toán đònh vò với

Hình 3: Vùng quét của cảm biến siêu âm
Vùng quét của cảm biến siêu âm được chia thành
3 vùng chính. Vùng I, là vùng mà cảm biến ghi
nhận có vật cản, vùng II là vùng từ vùng I đến cảm
biến, dường như không có vật cản nào, vùng III là
vùng phía sau vật cản, là vùng chưa biết, trong
thuật toán không quan tâm đến vùng này. (xem hình
3)
Gọi s là khoảng cách đo được của cảm biến, H là
sự kiện ô lưới đã bò chiếm và –H là sự kiện ô lưới
còn trống. Phân bố xác suất trên vùng quét của cảm
biến siêu âm là một phân bố Gauss theo phương
hướng kính, phân bố này sẽ được đơn giản hoá
thành một cung tròn trong thuật toán. Vì vậy, nếu
cho trước một thông số cảm biến, chúng ta có thể
tính được xác suất cảm biến ghi nhận được vật cản
nằm tại một ô lưới, nếu đã thực sự có một vật cản
nào đó nằm trong vùng quét của cảm biến siêu âm,
[Murphy00],[Moravec89] theo công thức sau:
Vùng I:
Max
R
rR
HsP *
2
)()(
)|(
β
αβ
−

HPHsPHPHsP
HPHsP
sHP
−−−
=
(3)
trong đó, P(H) là xác suất của sự kiện H, đây là
thời điểm lần đầu tiên ô lưới được quét, giá trò khởi
tạo là xác suất ngẫu nhiên:
5.0)(1)()(
=−=−=
HPHPHP
(4)
Một vấn đề khác lại được đặt ra là nếu có nhiều
cảm biến cùng quét qua một ô lưới, hay là sau một
thời gian di chuyển, robot lại quét qua ô lưới đó.
Như vậy, việc cập nhật cho các ô lưới phải dựa vào
thông tin có trước của ô lưới đó, như sau:
)|()|()|()|(
)|()|(
)|(
11
1
−−
−
−−+
=
nnnn
nn
n

giới hạn của bài báo, chúng tôi không trình bày nội
dung chi tiết của phương pháp này.
4.2 Thuật toán đònh vò
Thay vì sử dụng khái niệm vò trí khả thi bằng hình
học như phần trên đã trình bày, để đưa vào chương
trình tính toán, hình ảnh vò trí khả thi có thể được rút
ra từ bản đồ được chia lưới theo công thức toán học
sau:
)),0( () (),( zlMzMzMFP Θ−Θ∂=
(6)
Trong đó, FP thay cho chữ feasible poses có
nghóa là vò trí khả thi, M là tập hợp các điểm nằm
trên biên chướng ngại vật, và z là vectơ đònh vò mà
robot xác đònh được,
)(X∂
là ký hiệu cho tập hợp
các điểm biên của tập hợp X,
Θ
là ký hiệu của
phép trừ Minkowskii và l(x,y) là ký hiệu của một
đoạn thẳng hở nối hai điểm x và y, nhưng không kể
hai điểm x và y. [Brown00]
Tổng Minkowskii là tổng của một tập hợp với
một vectơ, kết quả của phép cộng này là một tập
hợp được xác đònh bằng việc cộng tất cả các phần
tử của tập hợp với vectơ đó. Hình ảnh sau đây mô
tả phép trừ Minkowskii (hình 7) và các vò trí khả thi
tìm được dùng công thức (6) (hình 8).

Hình 7: Hiệu Minkowskii

toán vò trí khả thi với một sai số
ε
nào đó. Sai số
ε
này được xác đònh dựa trên phân bố của cảm
biến siêu âm. Bán kính
ε
là bán kính sao cho xác
suất xuất hiện chướng ngại vật trong phạm vi bán
kính đó là 90%. Vì vậy, công thức (7) sẽ được viết
lại như sau:
)))1(,0( ()B(z (),(
z
zlMMzMFP
ε
εε
−Θ−⊕Θ=
(9)
o
o
Q
o
-Q
P
QP Θ
o
4
Trong đó,
ε
B

nhận một vectơ đònh vò như hình 11. [Elfes85]

Hình 11: Dùng nhiều cảm biến
để ghi nhận một vectơ đònh vò
Góc
1
θ
giới hạn ở đây bằng bao nhiêu thì tốt
nhất, vì góc này càng lớn thì càng ổn đònh, nhưng
nó phụ thuộc vào khoảng cách từ cảm biến đến
chướng ngại vật chưa biết. Ở đây chúng tôi chọn
o
30
1
=
θ
. Điều đó có nghóa là, trong quá trình di
chuyển, robot sẽ lưu lại các “vệt quét” của cảm
biến siêu âm trước đó, nếu “vệt quét” cũ giao với
vệt quét mới tại một điểm hợp với vò trí mới và cũ
của cảm biến một góc lớn hơn 30
o
thì ta xác nhận
điểm đó là chướng ngại vật, và chọn vectơ đònh vò
đi qua điểm đó. Trong trường hợp góc ghi nhận
không tốt, ta sẽ phải dùng phương pháp ATM (Arc
Transversal Median) [CNL03] để tìm ra điểm trọng
tâm trong các điểm nghi ngờ và chọn vectơ đònh vò
đi qua điểm đó.


314
≈
lần. Với kết quả này, bán kính sai
số
ε
sẽ vào khoảng 15 cm đến 20 cm. Đây là một
kết quả lý tưởng.
Cuối cùng, cho dù có hạn chế được sai số của
cảm biến, trong một môi trường chưa biết, không có
một sự khẳng đònh nào rằng robot sẽ ghi nhận các
vectơ đònh vò như khi thăm dò bản đồ (hình 13). Hay
nói cách khác, tập hợp vò trí khả thi của robot như
trong công thức (8) sẽ có thể là một tập rỗng, hoặc
một tập hợp mà các phần tử không liên thông (có
nhiều vò trí khả thi của robot nằm nhiều nơi cách xa
nhau trên bản đồ).

Hình 13: Chướng ngại vật di động
Bằng cách đưa vào một hàm đặc trưng như sau,
việc tìm ra vò trí khả thi có thể được thực hiện dễ
dàng.
1
θ
θ
)sin(
10
θ
)tan(
10
θ

),(
χ
(12)
Vậy, vò trí của robot là vò trí phù hợp với nhiều
vectơ đònh vò được robot ghi nhận nhất:






==
∈
)),,((sup),,(|),( qZMrnkpZMrnkpZMLoc
Cq
(13)
Trong đó, C là tập hợp tất cả các ô lưới trong bản
đồ. Mặc dù vậy, Loc(M,Z) có thể sẽ là một tập hợp
các điểm liên thông. Để tìm ra một điểm duy nhất,
ta sẽ tính tổng của các hàm rnk() của các điểm lân
cận, điểm có giá trò cao nhất sẽ là vò trí tức thời của
robot. Nếu lấy tổng các điểm lân cận gần nhất vẫn
không tìm ra được điểm duy nhất, chúng ta sẽ lấy
tổng các điểm lân cận tiếp theo.
Ngoài ra, để hạn chế vùng tính toán vò trí của
robot và nâng cao độ chính xác, robot có thể được
hỗ trợ thuật toán dead reckoning dựa vào việc tính
toán vò trí theo sự điều khiển mong muốn và đưa
vào một sai số tích luỹ theo quãng đường di chuyển
của robot. Sai số của phương pháp dead reckoning

(b) ©
Hình 16: (a) Robot bắt đầu quét bản đo
(b) Robot đang thăm dò bản đồ
(c)Robot hoàn thành việc quét bản đồ