i
LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứ ủa riêng tôi trong đó có sựu c giúp
đỡ ấ ớ ủ ầy hướ ẫ r t l n c a th ng d n . TS Ngô Lam Trung
Các n i dung nghiên c u, s u và k t qu nêu trong luộ ứ ố liệ ế ả ận văn là trung thực
và ch c ai công b trong bưa từng đượ ố ất kỳ công trình nào khác.
Trong lu n m t s tài li c li t kê t i ph n ận văn, tôi có tham khảo đế ộ ố ệu đã đượ ệ ạ ầ
Tài li u tham kh o i lu . Các tài li u tham kh c trích d n trung ệ ả ở cuố ận văn ệ ảo đượ ẫ
thực trong luận văn.
Hà Nội, ngày… tháng … năm 2016
Tác giả
Nguy n Thùy Linh ễ
ii
LỜI CẢM ƠN
Trướ ảm ơn đ ờc tiên, tôi xin chân thành c TS Ngô Lam Trung ã dành th i gian
quý báu, t n tình h ng d n ch b o, góp ý cho tôi trong su t quá trình th c hiậ ướ ẫ ỉ ả ố ự ện
lu t nghiận văn ố t ệp.
Tôi xin đượ ảm ơn sự giúp đỡ ệ ủ ầc c nhi t tình c a các Th y giáo, Cô giáo trong
trườ Đạng i học Bách Khoa.
Đặ ệt, tôi xin được bi c bày t lòng bi c t i các Th y giáo, Cô giáo ỏ ết ơn sâu sắ ớ ầ
trong Vi n Công ngh thông tin và Truy n thông ã tham gia gi ng d y tôi trong ệ ệ ề đ ả ạ
quá trình h c t p t ng. Các thọ ậ ại Trườ ầy cô đã tậ ả ạn tình gi ng d y, truyền đạ ết ki n
thứ ạ ền đề ận văn. Tôi xin cám ơn các bạc, t o ti cho tôi hoàn thành lu n sinh viên
trong phòng Phòng thí nghi m H ng Máy tính c bi t v i hai b n sinh viên ệ ệ thố và đặ ệ ớ ạ
Trần Đức Sơn và ễ ữ ạ ứu irobot đã hỗ ợNguy n H u M nh trong nhóm nghiên c tr tôi
m i m tôi hoàn thành lu ọ ặ ểt đ ận văn.
Cuố ải cùng, tôi xin chân thành c m ơn các bạn bè, đồ ệ ấng nghi p và nh t là gia
đình tôi đã quan tâm và tạ ọi điề ệ ố ất, độ ổ ũ ốo m u ki n t t nh ng viên, c v tôi trong su t
quá trình h p và nghiên c hoàn thành t t nghi p này. ọc tậ ứu để ốt luận văn tố ệ
Xin trân trọ ảng c m ơn!
Hà Nội, ngày 14 tháng 11 năm 2016
Tác giả
Nguy n Thùy Linh ễ
iii
PHỤ LỤC
L I CAM ....................................................................................................... iỜ ĐOAN
L ............................................................................................................ ỜI CẢM ƠN ii
PHỤ Ụ L C .................................................................................................................. iii
DANH MỤ ẼC HÌNH V ............................................................................................ vi
DANH M VIỤ ỪC CÁC T ẾT T T NGẮ ẬT VÀ THU Ữ ......................................... viii
L U ............................................................................................................. 1ỜI MỞ ĐẦ
CHƯƠNG 1: TỔNG QUAN ....................................................................................... 3
1.1. Lý do chọn đề ................................................................................................ 3tài
1.2. Giới thiệu mộ ố ệt s khái ni m liên quan ............................................................... 4
1.2.1. ch v là gì? ................................................................................... 4 Robot dị ụ
1.2.2. Các ng d ng c a robot d ................................................................ 4 ứ ụ ủ ịch vụ
1.2.3. ng bao ph là gì? .......................................................................... 5 Tìm đườ ủ
1.3. Các phương pháp giả ế ụ ế ậ ủi quy t và các công c ti p c n bài toán bao ph ............. 6
1.3.1. quy ................................................. 6 Phương pháp giải ết bài toán bao phủ
1.3.2. Các công c p c n bài toán .................................................................... 7 ụtiế ậ
1.4. N tài và k t qu c ......................................................... 7ội dung đề ế ả thực hiện đượ
1.4.1. N .......................................................................................... 7 ội Dung đề tài
1.4.2. K c .............................................................................. 7 ết quảthực hiện đượ
CHƯƠNG 2: PHƯƠNG PHÁP GIẢ Ế ỦI QUY T BÀI TOÁN BAO PH .................... 9
2.1. Một số phương pháp giải quyết bài toán bao phủ với đơn robot ....................... 9
2.1.1. n ......................................... 9 Phương pháp phân chia vùng làm việc cổ điể
2.1.1.1. t toán phân chia theo hình thang ............................................ 10 Thuậ
2.1.1.2. t toán phân chia Boustrophedon ............................................ 11 Thuậ
2.1.2. ........................................................ 12 Phương pháp dự ớa trên lư i ô vuông
2.1.2.1. t toán tràn sóng wavefront ..................................................... 13 Thuậ
2.1.2.2. ................................................................ 14 Thuật toán cây bao trùm.
iv
2.2. Phương pháp giải quyết sử dụng một nhóm robot ........................................... 16
CHƯƠNG 3 Ế Ể Ậ: LÝ THUY T VÀ PHÁT TRI N THU T TOÁN MSTC ................ 19
3.1. Các tiêu chí đánh giá ........................................................................................ 19
3.2. Thuậ ủ ớt toán bao ph v i mộ ự n môi trườt nhóm robot d a trên cây bao trùm trê ng
đã biết ...................................................................................................................... 19
3.2.1. c bao ph ...................................................................................... 19 Khu vự ủ
3.2.2. t toán MSTC Offline ........................................................................ 20 Thuậ
3.2.2.1. Xây d ng cây bao trùm .................................................................. 20 ự
3.2.2.2. MSTC Offline không quay lui ....................................................... 22
3.2.2.3. Phân tích các tiêu chí c t toán .............................................. 25 ủa thuậ
3.3. Thuậ ủ ớ ộ ới môi trường chưa rõt toán bao ph v i m t nhóm robot v .................... 26
3.3.1. c bao ph ...................................................................................... 26 Khu vự ủ
3.3.2. t toán ORMSTC ............................................................................... 27 Thuậ
3.3.3. Phân tích các tiêu chí c t toán ........................................................ 31 ủa thuậ
3.3.3.1. Tính m nh m ................................................................................ 31 ạ ẽ
3.3.3.2. toàn b ..................................................................... 31 Tính bao phủ ộ
3.3.3.3. a ........................................................................ 32 Tính không dư thừ
3.4. Đề ấ ả ế ể ậ xu t c i ti n và phát tri n thu t toán MSTC ............................................... 32
3.4.1. xu t và phát tri n thu t toán ORMSTC d a trên cách t o cây con trên Đề ấ ể ậ ự ạ
MSTC-offline..................................................................................................... 32
3.4.1.1. c bao ph ............................................................................ 32 Khu vự ủ
3.4.1.2. ng c n thu t toán ............................................................. 33 Ý tưở ải tiế ậ
3.4.1.3. Phát tri n thu t toán ....................................................................... 35 ể ậ
3.4.1.4. Phân tích các tiêu chí c t toán c n ................................. 38 ủa thuậ ải tiế
3.4.2. n khai thu t toán MSTC - .......................................................... 40 Triể ậ Full
3.4.2.1. c bao ph ............................................................................ 40 Khu vự ủ
3.4.2.2. ng thu t toán ......................................................................... 41 Ý tưở ậ
3.4.2.3. Phát tri n thu t toán ....................................................................... 43 ể ậ
3.4.2.4. n ......................... 47 Phân tích các tiêu chí đánh giá thuật toán cải tiế
v
CHƯƠNG 4: CÀI ĐẶ Ử Ệ ẬT VÀ TH NGHI M CÁC THU T TOÁN MSTC ........... 50
4.1. Giới thi t s m sệu mộ ố ụ ầ ề công c , ph n m ử ụ d ng ................................................ 50
4.1.1. u v ROS.................................................................................... 50 Giới thiệ ề
4.1.2. u v Gazebo ............................................................................... 51 Giới thiệ ề
4.1.3. u robot Kobuki ........................................................................... 51 Giới thiệ
4.1.4. u Hokuyo ................................................................................... 52 Giới thiệ
4.2. Giả ế ế ữi quy t bài toán giao ti p gi a các robot ..................................................... 53
4.2.1. V phát sinh ...................................................................................... 53 ấn đề
4.2.2. ng l p trình socket v t toán MSTC ....................................... 54 Áp dụ ậ ới thuậ
4.3. V quay lui robot và gi i quy t tính m nh m khi th nghi m thu 57ấn đề ả ế ạ ẽ ử ệ ật toán
4.3.1. V phát sinh ...................................................................................... 57 ấn đề
4.3.2. di chuy n cell c .......... 59 Áp dụng phương pháp khoảng cách để ển đế ần đi
4.4. V trong tính m nh m c a thu t toán MSTC ........................................... 60ấn đề ạ ẽ ủ ậ
4.5. K nghi m .......................................................................................... 61ết quảthử ệ
4.5.1. nghi ng mô ph ng: ................................................. 61 Thử ệm trên môi trườ ỏ
4.5.2. ng gi l p ............................................ 68 Đánh giá thuật toán trên môi trườ ả ậ
4.5.3. nghi ng th ....................................................... 69 Thử ệm trên môi trườ ực tế
K N ............................................................................................................... 73ẾT LUẬ
A. K n ............................................................................................................ 73ết luậ
B. Những điể ưa hoàn thiệm ch n ........................................................................... 73
C. H ng phát tri tài ..................................................................................... 74ướ ển đề
TÀI LIỆ ẢU THAM KH O ......................................................................................... 75