Giáo viên hướng dẫn : TS. Vũ Đức Lung
Học viên thực hiện : Thái Quốc Thắng
Đồng Nai, tháng 11 năm 2013
TÌM HIỂU VÀ XÂY DỰNG PHẦN MỀM HỖ
TRỢ BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN
NHẤT TRÁNH VẬT CẢN CHO XE TỰ
HÀNH TRONG KHÔNG GIAN 2D
ĐỀ TÀI:
TRƯỜNG ĐẠI HỌC LẠC HỒNG
CNTT - CAO HỌC KHÓA 3
1
 NỘI DUNG TRÌNH BÀY
1. Giới thiệu bài toán.
2. Mục tiêu.
3. Giải pháp cho bài toán.
4. Hiện thực và đánh giá kết quả.
5. Kết luận và hướng phát triển.
2
1. Giới thiệu bài toán:
3
1. Giới thiệu bài toán:
- Xe tự hành không có khả năng tránh vật cản
trên đường đi. Vì xe tự hành không tự động tìm
cho mình được một đường đi.
- Khi di chuyển, xe tự hành có khả năng di
chuyển ra khỏi đường đi. Do đó, xe tự hành có
thể sẽ không di chuyển về đúng điểm đích.
- Xe tự hành không có khả năng ghi nhận lại
hình ảnh quan sát được trên đường đi, để làm
dữ liệu thông tin phát triển sau này.
4

được áp dụng nhiều trong các lĩnh vực như
sinh tin học, CAD/CAM, layout, xử lý ảnh,…
và đặc biệt rất nhiều trong lĩnh vực robot.
7
- Bài toán đặt ra là tìm ra đường đi tốt nhất theo
một tiêu chuẩn tối ưu nào đó, sao cho đối
tượng di chuyển từ điểm bắt đầu đến điểm đích
trên đường đi này mà không va vào các vật cản
trong môi trường hai hoặc nhiều chiều.
3. Giải pháp cho bài toán
3.2. Đường đi ngắn nhất trong visibilty graph:
Cho một tập S là các đa giác rời nhau…
Khi đó G
vis
(S) = (V(S), E
vis
) là visibility graph của tập
S, với điều kiện E
vis
= {uv  u, v  V(S), u thấy v}
…và V(S) là đỉnh của tập S.
Định nghĩa: u thấy v    C
free

P
start

P
goal


và P
goal
trong không gian tự do.
Đầu ra: Đường đi ngắn nhất giữa hai điểm P
start
và
P
goal
.
1. G
vis

VisibilityGraph  P
start
, P
goal
}).
2. Gán mỗi cung (v,w) trong G
vis
một trọng số bằng
chính chiều dài của đoạn 
3. Sử dụng giải thuật Dijkstra để tính đường đi ngắn
nhất giữa điểm P
start
, P
goal
.
9
3. Giải pháp cho bài toán
3.3. Sử dụng giải thuật Dijkstra để tìm đường đi:

= false, kiểm tra.
Nếu d
u
> d
v
+ w(v,u) thì d
u
:= d
v
+ w(v,u).
Ghi nhớ đỉnh v: p
u
:= v. Quay lại bước B2.
10
Độ phức tạp của giải thuật O(n
2
)
4. Khối chức năng điều khiển xe tự hành
 Bao gồm 2 chức năng:
1. Chức năng xác định vị trí hiện tại của xe tự
hành.
2. Chức năng bám đường đi chính xác cho xe tự
hành dựa trên Bộ điều khiển PID.
11
4. Khối chức năng điều khiển xe tự hành
4.1. Chức năng xác định vị trí hiện tại của xe:
Màn hình giao diện chính của khối chức năng xác
định vị trí hiện tại của xe:
12
Red_Filter

4. Khối chức năng điều khiển xe tự hành
4.2. Chức năng bám đường đi chính xác:
4.2.1. Lý thuyết bộ điều khiển PID:
 Khâu tỷ lệ “P”:
Làm thay đổi giá trị đầu ra, tỷ lệ với giá trị sai số
hiện tại. “P” được gọi là độ lợi tỷ lệ. Được cho bởi:
P
out
= K
p
e(t)
Trong đó:
P
out
: Thừa số tỷ lệ của đầu ra
K
p
: Độ lợi tỷ lệ, một thông số điều chỉnh
e : Sai số
t : Thời gian hiện tại hay thời gian tức thời
14
4. Khối chức năng điều khiển xe tự hành
4.2. Chức năng bám đường đi chính xác:
4.2.1. Lý thuyết bộ điều khiển PID:
 Khâu tỷ lệ “I”:
Làm tăng tốc chuyển động của quá trình tới điểm
đặt và khử số dư sai số ổn định với một tỷ lệ chỉ phụ
thuộc vào bộ điều khiển. Được cho bởi:
I
out




e(t)
Trong đó:
D
out
: Thừa số vi phân của đầu ra
K
i
: Độ lợi vi phân, một thông số điều chỉnh
e : Sai số
t : Thời gian hiện tại hay thời gian tức thời
16
4. Khối chức năng điều khiển xe tự hành
4.2. Chức năng bám đường đi chính xác:
4.2.1. Lý thuyết bộ điều khiển PID:
Tổng chập của ba tác động này dùng để điều chỉnh
quá trình thông qua một phần tử điều khiển. Cho u(t)
là đầu ra của bộ điều khiển, biểu thức cuối cùng của
giải thuật PID là:
u(t) = MV(t) = K
p
e(t) + K
i


  




w
(i+1)
w
i
x
t
x

n
i

i


i

e
t
= x
t
tan(µ
t
)n
i
Gọi P là một đường đi được xác định bởi một chuỗi N
điểm
Khi đó, vị trí hiện tại được cho x
t


PI K
u
/2.2 1.2K
p
/T
u
-
Classic PID 0.60K
u
2K
p
/T
u
K
p
T
u
/8
19
Bảng phương pháp điều chỉnh Ziegler–Nichols:
5. Chức năng ghi và truyền hình ảnh:
Trong quá trình di chuyển xe tự hành sử dụng một
Camera IP giao tiếp qua thiết bị Wireless và kết nối máy
tính điều khiển thông qua thiết bị Access Point để truyền
hình ảnh quan sát được về cho máy tính điều khiển.
Thiết lập kết nối không dây giữa các thiết bị thông qua
thông qua Access Point:
20
Kết nối Camera và máy tính
vào AP1

q Thầy Cô và các bạn
đã quan tâm theo dõi !!!