LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi trong đó có sự giúp
đỡ rất lớn của thầy hướng dẫn TS Ngô Lam Trung.
Các nội dung nghiên cứu, số liệu và kết quả nêu trong luận văn là trung thực
và chưa từng được ai công bố trong bất kỳ công trình nào khác.
Trong luận văn, tôi có tham khảo đến một số tài liệu đã được liệt kê tại phần
Tài liệu tham khảo ở cuối luận văn. Các tài liệu tham khảo được trích dẫn trung
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

i


LỜI CẢM ƠN
Trước tiên, tôi xin chân thành cảm ơn 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ận văn tốt nghiệp.
Tôi xin được cảm ơn sự giúp đỡ nhiệt tình của các Thầy giáo, Cô giáo trong
trường Đại học Bách Khoa.
Đặc biệt, tôi xin được bày tỏ lòng biết ơn sâu sắc tới các Thầy giáo, Cô giáo
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ại Trường. Các thầy cô đã tận tình giảng dạy, truyền đạt kiến
thức, tạo tiền đề cho tôi hoàn thành luận văn. Tôi xin cám ơn các bạn sinh viên
trong phòng Phòng thí nghiệm Hệ thống Máy tính và đặc biệt với hai bạn sinh viên
Trần Đức Sơn và Nguyễn Hữu Mạnh trong nhóm nghiên cứu irobot đã hỗ trợ tôi
mọi mặt để tôi hoàn thành luậ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ạo mọi điều kiện tốt nhất, động viên, cổ vũ tôi trong suốt

quá trình học tập và nghiên cứu để hoàn thành tốt luận văn tốt nghiệp này.
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

ii


PHỤ LỤC
LỜI CAM ĐOAN ....................................................................................................... i
LỜI CẢM ƠN ............................................................................................................ ii
PHỤ LỤC .................................................................................................................. iii
DANH MỤC HÌNH VẼ ............................................................................................ vi
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ ......................................... viii
LỜI MỞ ĐẦU .............................................................................................................1
CHƯƠNG 1: TỔNG QUAN .......................................................................................3
1.1. Lý do chọn đề tài ................................................................................................3
1.2. Giới thiệu một số khái niệm liên quan ...............................................................4
1.2.1. Robot dịch vụ là gì? ...................................................................................4
1.2.2. Các ứng dụng của robot dịch vụ ................................................................4
1.2.3. Tìm đường bao phủ là gì? ..........................................................................5
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. Phương pháp giải quyết bài toán bao phủ .................................................6
1.3.2. Các công cụ tiếp cận bài toán ....................................................................7
1.4. Nội dung đề tài và kết quả thực hiện được .........................................................7
1.4.1. Nội Dung đề tài ..........................................................................................7
1.4.2. Kết quả thực hiện được ..............................................................................7
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. Phương pháp phân chia vùng làm việc cổ điển .........................................9
2.1.1.1.

Thuật toán phân chia theo hình thang ............................................10

2.1.1.2.

Thuật toán phân chia Boustrophedon ............................................11

2.1.2. Phương pháp dựa trên lưới ô vuông ........................................................12
2.1.2.1.

Thuật toán tràn sóng wavefront .....................................................13

2.1.2.2.

Thuật toán cây bao trùm.................................................................14

iii


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ột nhóm robot dựa trên cây bao trùm trên môi trường
đã biết ......................................................................................................................19
3.2.1. Khu vực bao phủ ......................................................................................19
3.2.2. Thuật toán MSTC Offline ........................................................................20
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ủa thuật toán ..............................................25

3.3. Thuật toán bao phủ với một nhóm robot với môi trường chưa rõ ....................26
3.3.1. Khu vực bao phủ ......................................................................................26
3.3.2. Thuật toán ORMSTC ...............................................................................27
3.3.3. Phân tích các tiêu chí của thuật toán........................................................31
3.3.3.1.

Tính mạnh mẽ ................................................................................31

3.3.3.2.

Tính bao phủ toàn bộ .....................................................................31

3.3.3.3.

Tính không dư thừa ........................................................................32

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.

Khu vực bao phủ ............................................................................32

3.4.1.2.

Ý tưởng cải tiến thuật toán .............................................................33

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ủa thuật toán cải tiến .................................38

3.4.2. Triển khai thuật toán MSTC - Full ..........................................................40
3.4.2.1.

Khu vực bao phủ ............................................................................40

3.4.2.2.

Ý tưởng thuật toán .........................................................................41

3.4.2.3.

Phát triển thuật toán .......................................................................43

3.4.2.4.


Phân tích các tiêu chí đánh giá thuật toán cải tiến .........................47

iv


CHƯƠNG 4: CÀI ĐẶT VÀ THỬ NGHIỆM CÁC THUẬT TOÁN MSTC ...........50
4.1. Giới thiệu một số công cụ, phần mềm sử dụng ................................................50
4.1.1. Giới thiệu về ROS....................................................................................50
4.1.2. Giới thiệu về Gazebo ...............................................................................51
4.1.3. Giới thiệu robot Kobuki ...........................................................................51
4.1.4. Giới thiệu Hokuyo ...................................................................................52
4.2. Giải quyết bài toán giao tiếp giữa các robot .....................................................53
4.2.1. Vấn đề phát sinh ......................................................................................53
4.2.2. Áp dụng lập trình socket với thuật toán MSTC .......................................54
4.3. Vấn đề quay lui robot và giải quyết tính mạnh mẽ khi thử nghiệm thuật toán 57
4.3.1. Vấn đề phát sinh ......................................................................................57
4.3.2. Áp dụng phương pháp khoảng cách để di chuyển đến cell cần đi ..........59
4.4. Vấn đề trong tính mạnh mẽ của thuật toán MSTC ...........................................60
4.5. Kết quả thử nghiệm ..........................................................................................61
4.5.1. Thử nghiệm trên môi trường mô phỏng: .................................................61
4.5.2. Đánh giá thuật toán trên môi trường giả lập ............................................68
4.5.3. Thử nghiệm trên môi trường thực tế .......................................................69
KẾT LUẬN ...............................................................................................................73
A. Kết luận ............................................................................................................73
B. Những điểm chưa hoàn thiện ...........................................................................73
C. Hướng phát triển đề tài .....................................................................................74
TÀI LIỆU THAM KHẢO .........................................................................................75

v



DANH MỤC HÌNH VẼ
Hình 1.1: Một ứng dụng thực tế của robot dịch vụ .....................................................5
Hình 2.1: Bao phủ một cell hình chữ nhật bằng thao tác đi ziczag ..........................10
Hình 2.2: Ví dụ về thuật toán phân chia hình thang .................................................11
Hình 2.3: Ví dụ về thuật toán BA* ...........................................................................12
Hình 2.4: Ví dụ phương pháp phân chia dựa trên lưới ô vuông với hai chướng ngại
vật ..............................................................................................................................13
Hình 2.5: Gán có số cho các ô bằng cách lan truyền bước sóng với ô bắt đầu (S) và
ô đích (G). .................................................................................................................14
Hình 2.6: Kế hoạch bao phủ sử dụng biến đổi khoảng cách với thuật toán wavefront
...................................................................................................................................14
Hình 2.7: Phân chia cell trong thuật toán cây bao trùm ............................................15
Hình 2.8: Đường bao phủ của robot khi áp dụng thuật toán Spiral – STC ...............16
Hình 2.9: Robot thực hiện bao phủ một cell theo thuật toán phân chia
boustrophedon sử dụng nhóm robot ..........................................................................18
Hình 3.1: Xây dựng cây bao trùm .............................................................................22
Hình 3.2: Đường đi cho đa robot ..............................................................................23
Hình 3.3: Nhóm robot sử dụng ORMSTC trên thuật toán Spiral-STC ....................34
Hình 3.4: Nhóm robot sử dụng MSTC- Offline........................................................35
Hình 3.5: (a): Cạnh có hai phía; (b): Cạnh có một phía; (c): Gấp đôi nút ở cell mất
kết nối cục bộ ............................................................................................................41
Hình 3.6: Vấn đề gặp phải khi thực hiện MSTC-full................................................42
Hình 3.7: Các subcell của cell được định nghĩa ........................................................43
Hình 3.8: Vấn đề gặp phải khi cell mất kế nối cục bộ ..............................................46
Hình 3.9: Vấn đề gặp phải khi cell mất kế nối cục bộ ..............................................47
Hình 4.1: Robot Kobuki ............................................................................................52
Hình 4.2: Laze Hokuyo .............................................................................................53
Hình 4.3: Mô hình client-server sử dụng ..................................................................54


vi


Hình 4.4: Tình huống robot chết nằm giữa hai subcell .............................................58
Hình 4.5: Tình huống robot còn sống không thể giúp robot đã chết ........................61
Hình 4.6: Sơ đồ hệ thống khi triển khai trong môi trường mô phỏng ......................62
Hình 4.7: Sơ đồ cấu trúc chương trình ......................................................................63
Hình 4.8: Thuật toán MSTC_Offline chạy với 2 robot .............................................65
Hình 4.9: Thuật toán ORMSTC chạy với 2 robot .....................................................65
Hình 4.10: Thuật toán MSTC chạy với 2 robot ........................................................66
Hình 4.11: Thuật toán MSTC-full chạy với 2 robot .................................................66
Hình 4.12: Thuật toán MSTC-full chạy khi biết kịp thời robot chết ........................67
Hình 4.13 Thuật toán MSTC-full chạy xong và thực hiện kiểm tra để quay lui để
bao phủ cho robot lỗi.................................................................................................68
Hình 4.14: Sơ đồ hệ thống khi triển khai trong môi trường thực tế..........................70
Hình 4.15: Hình ảnh chạy thuật toán trong thực tế ...................................................72

vii


DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ
Viết đầy đủ

Thuật ngữ/Chữ viết tắt
STC

Spanning Tree Coverage

BA*


Boustrophedon online A* search

MSTC

Multi-robot Spanning Tree Coverage

ORMSTC

On-line Robust Multi-robot STC

IFR

The International Federation of Robotics

CPP

Coverage Path Planning

ROS

Robot Operating System

viii


LỜI MỞ ĐẦU
Ý tưởng về việc chế tạo các cỗ máy có thể làm việc tự động có từ thời cổ đại,
nhưng những nghiên cứu về chức năng và khả năng ứng dụng không có bước tiến
nào đáng kể cho đến thế kỷ 20. Xuyên suốt lịch sử, robot học thường được nhìn

nhận là để bắt chước hành vi của con người, và thường quản lý các nhiệm vụ theo
cách thức tương tự.
Ngày nay, robot là một lĩnh vực phát triển nhanh chóng, nhờ công nghệ phát
triển liên tục, robot đã được chế tạo để phục vụ cho nhiều mục đích khác nhau.
Nhiều robot đã thay con người làm những công việc độc hại như tháo ngòi nổ bom,
mìn, thăm dò các con tàu bị đắm, đi vào thu thập thông tin ở những nơi độc hại, có
phóng xạ,.... Việc sử dụng robot để giải quyết bài toán bao phủ đã được ứng dụng
rất nhiều trong thực tiễn. Nhiệm vụ của robot là tìm kiếm và di chuyển theo một
thuật toán nào đó nhằm bao phủ được hết khu vực được giao. Khu vực làm việc của
robot có thể chứa những vật cản. Robot có thể được trạng bị các cảm biến hoặc các
thiết bị hỗ trợ khác để hỗ trợ cho công việc của mình.
Những năm gần đây, sử dụng nhóm nhiều robot trong bài toán bao phủ ngày
càng được quan tâm bởi tính hiệu quả và mạnh mẽ của nó. Lý do đầu tiên là bởi
nhiều robot có thể hoàn thành nhiệm vụ nhanh hơn so với một robot, bằng cách
phân chia khu vực làm việc giữa chúng. Lý do thứ hai là bởi sử dụng nhóm robot có
thể đảm bảo được việc hoàn thành xong công việc tốt hơn. Khi nhiều robot được sử
dụng, giả sử có một thành viên bị lỗi và không thể hoàn thành phần việc mình được
giao, các đồng nghiệp khác của nó có thể hỗ trợ để vẫn đảm bảo công việc chung
được hoàn thành.
Từ mong muốn muốn thử nghiệm một thuật toán tìm đường bao phủ cho
nhóm robot, trong luận văn này tập trung nghiên cứu, tìm hiểu, giải quyết những
vấn đề cụ thể như sau:
-

Tìm hiểu tổng quan về các thuật toán tìm đường bao phủ.

-

Nghiên cứu, tìm hiểu lý thuyết về thuật toán tìm bao phủ STC với nhóm robot
(thuật toán MSTC).


1


-

Lập trình thuật toán tìm đường bao phủ STC với nhóm robot trong môi trường
được biết trước (Offline - MSTC).

-

Lập trình phát triển thuật toán MSTC trên môi trường chưa biết (Online-MSTC).
Thực hiện chạy thử nghiệm kết quả đã lập trình được trong môi trường mô

phỏng và trong môi trường thực tế
Cấu trúc luận văn này gồm bốn chương với những nội dung chính như sau:
Chương 1: Tổng quan
-

Lý do chọn đề tài.

-

Giới thiệu một số khái niệm liên quan.

-

Giới thiệu các phương pháp giải quết và các công cụ tiếp cận bài toán
bao phủ.


-

Nội dung và kết quả thực hiện được

Chương 2: Cơ sở lý thuyết
-

Trình bày các phương pháp tiếp cận giải quyết bài toán bao phủ với
một robot.

-

Trình bày các phương pháp tiếp cận giải quyết bài toán bao phủ với
nhóm robot.

Chương 3: Lý thuyết và phát triển thuật toán MSTC.
-

Giới thiệu các tiêu chí đánh giá.

-

Thuật toán bao phủ với một nhóm các robot dựa trên cây bao trùm
trên môi trường đã biết.

-

Thuật toán bao phủ với một nhóm robot với môi trường chưa rõ

-


Đề xuất thuật toán MSTC

Chương 4: Thử nghiệm trong mô phỏng và trong thực tế
-

Giới thiệu một số công cụ, phần mềm sử dụng để phát triển.

-

Trình bày các vấn đề phát sinh khi lập trình thuật toán MSTC.

-

Trình bày những kết quả đạt được khi thử nghiệm trong mô phỏng và
trong thực tế.

2


CHƯƠNG 1. TỔNG QUAN
1.1. Lý do chọn đề tài
Luận văn này có nội dung về nghiên cứu và thử nghiệm thuật toán tìm đường
bao phủ MSTC với nhóm robot.
Lý do lựa chọn đề tài này có thể bao gồm những lý do sau:
-

Cùng với sự phát triển của công nghệ, càng ngày việc sử dụng robot để giúp
đỡ con người trong cuộc sống càng được phổ biến. Robot giúp cũng là đang
dần trở thành một sản phẩm công nghệ không thể thiếu trong cuộc sống của

con người. Robot lau nhà ra đời như một tất yếu của cuộc sống giúp con
người thoát khỏi những công việc có tính chất lặp đi lặp lại, nhàm chán.

-

Các bài toán bao phủ được đưa ra để robot có thể hoàn thành nhiệm vụ làm
sạch đồng thời không va đập với các vật cản trong quá trình di chuyển. Kế
hoạch tìm đường bao phủ (Coverage Path Planning - CPP) là nhiệm vụ tìm ra
đường đi có thể đi qua tất cả các điểm cần thiết trong một vùng hoặc không
gian cho trước, bên cạnh đó cũng phải tránh được những vật cản. Công việc
này là cần thiết cho rất nhiều ứng dụng ví dụ như các robot hút bụi, lau nhà,
sơn tường, vẽ tranh, robot dò mìn, máy cắt cỏ, máy làm sạch cửa sổ,...

-

Với khu vực bao phủ rộng lớn khi thực hiện với chỉ một robot duy nhất sẽ
gặp nhiều vấn đề xẩy ra như khi robot đó lỗi hay thời gian thực hiện công
việc. Phương pháp tiếp cận là sử dụng nhiều robot hoạt động song song, nhờ
đó cho phép rút ngắn thời gian bao phủ không gian làm việc bằng cách phân
chia công việc cho từng robot. Hay còn gọi là bài toán tìm đường bao phủ
cho một nhóm robot.

Về mặt công nghệ tác giả muốn:
-

Tìm hiểu lập trình nhúng.

-

Tìm hiểu về các thuật toán tìm đường.


-

Tìm hiểu cách thức giao tiếp giữa các robot.

-

Thực hành lập trình cho robot.

3


1.2. Giới thiệu một số khái niệm liên quan
1.2.1. Robot dịch vụ là gì?
Robot dịch vụ là loại robot hỗ trợ, thực hiện thay con người trong các công
việc; ví dụ như công việc có tính chất lặp đi lặp lại, các công việc trong nhà, công
việc phải thực hiện ở những chỗ dơ bẩn, nguy hiểm,…. Những robot này thường
được điều khiển tự động bởi một hệ thống điều khiển tích hợp được cài đặt thủ công
bên trong. Thuật ngữ “Robot dịch vụ” không có một định nghĩa chính xác. Liên
đoàn Robot Quốc Tế (The International Federation of Robotics – IFR) đã đề xuất
một định nghĩa: Một robot dịch vụ là một robot mà hoạt động bán tự động hoặc
hoàn toàn tự động để thực hiện các dịch vụ hữu ích cho của con người và thiết bị,
không bao gồm các hoạt động sản xuất.
1.2.2. Các ứng dụng của robot dịch vụ
Ứng dụng có thể có của robot chủ yếu là để hỗ trợ trong công việc của con
người. Hiện nay có các ứng dụng trong một số lĩnh vực như sau:
-

Ứng dụng trong công nghiệp: Robot dịch vụ công nghiệp có thể được sử
dụng để thực hiện các nhiệm vụ đơn giản, chẳng hạn như kiểm tra hàn. Nó

cũng có các nhiệm vụ phức tạp hơn, thực hiện trong các môi trường khắc
nghiệt, chẳng hạn như giúp đỡ trong việc tháo dỡ các nhà máy điện hạt
nhân. Robot cũng có thể được dùng để thực hiện những hành động lặp đi
lặp lại như lắp ráp, thực hiện các công việc tự động hóa khác. Nhưng robot
được sử dụng trong công nghiệp được gọi là "Robot công nghiệp".

-

Ứng dụng trong các nhà hàng, quán bar, khách sạn: Hiện nay, nhiều nhà
hàng, quán bar, khách sạn đã sử dụng robot dịch vụ. Các công việc mà
robot có thể thực hiện ví dụ như dọn dẹp, pha chế các đồ uống phức tạp,
hay thậm chí là tiếp đón khách hàng.

-

Ứng dụng trong gia đình: Robot trong gia đình thực hiện nhiệm vụ mà con
người thường xuyên thực hiện xung quanh nhà như lau chùi sàn nhà, cắt
cỏ, dọn dẹp hồ bơi,... Chúng cũng có thể đóng vai trò của một người quản
gia trong gia đình.

4


-

Ứng dụng trong khoa học: Hệ thống robot thực hiện nhiều chức năng như
tiến hành các thao tác lặp đi lặp lại trong nghiên cứu. Những robot tự động
cũng có thể thực hiện các nhiệm vụ khoa học mà con người khó hoặc
không thể thực hiện, ví dụ như các vùng biển sâu, không gian bên ngoài
Trái Đất....


Hình 1.1: Một ứng dụng thực tế của robot dịch vụ
1.2.3. Tìm đường bao phủ là gì?
Tìm đường bao phủ (Coverage Path Planning - CPP) là nhiệm vụ tìm ra
đường đi có thể đi qua tất cả các điểm cần thiết trong một vùng hoặc không gian
cho trước, bên cạnh đó cũng phải tránh được những vật cản. Công việc này là cần
thiết cho rất nhiều ứng dụng robot, ví dụ như các robot hút bụi, lau nhà, sơn tường,
vẽ tranh, robot dò mìn, máy cắt cỏ, máy làm sạch cửa sổ. Nhiệm vụ mà robot khi
thực hiện công việc này được đặt ra theo các yêu cầu như sau:
-

Robot phải đi qua tất cả các điểm và bao phủ vùng mục tiêu cần quét một
cách hoàn thiện.

-

Robot phải thực hiện di chuyển mà không được đè các vùng quét lên nhau.

-

Các tác vụ thực hiện liên tục và tuần tự mà đường đi không bị lặp lại.

-

Robot phải tránh được các vật cản.

-

Sử dụng quỹ đạo di chuyển đơn giản (đi thẳng hoặc vòng tròn...).


-

Bổ sung các đường dẫn tùy chọn khi có thể.
Tất cả những điều kiện trên không phải lúc nào cũng có thể đáp ứng được,

nhất là trong môi trường phức tạp. Vì vậy mà đôi lúc các mức ưu tiên khác nhau
ứng với mỗi điều kiện cần được sắp xếp để thỏa mãn cho phù hợp. Việc thực hiện
5


giải bài toán tìm đường trong trường hợp tổng quát hay áp dụng thực tế không phải
là điều dễ dàng, có thể kể ra ở đây một số ví dụ như: bài toán “Người bán hàng”
(Covering/Travelling Salesman problem), bài toán “Phòng trưng bày” (Art Gallery
problem) hay bài toán “Người đi tuần tra” (Watchman Route problem) đều là các
bài toán có liên hệ đến yêu cầu tìm đường, chúng đều là những bài toán NP-khó.
Các thuật toán bao phủ có thể được phân loại thành thuật toán bao phủ tối ưu
hoặc bao phủ đầy đủ. Nếu khả năng bao phủ toàn bộ vùng làm việc của thuật toán
được chứng minh chặt chẽ thì thuật toán được gọi là bao phủ đầy đủ. Trong trường
hợp ngược lại, nếu thuật toán nhằm tối đa hóa diện tích bao phủ trong điều kiện
robot chịu các ràng buộc như thời gian hoạt động, nguồn năng lượng, kích thước và
không thể đảm bảo bao phủ toàn bộ vùng làm việc, thì thuật toán được gọi là bao
phủ tối ưu.
Các thuật toán bao phủ cũng có thể được phân thành hai loại on-line và offline. Thuật toán off-line hoạt động dựa vào các thông tin tĩnh và các thông tin về
môi trường cần bao phủ phải được biết trước khi robot hoạt động. Ngược lại, các
thuật toán on-line không cần biết trước các thông tin này, mà robot sẽ tự xác định
các thông tin về môi trường theo thời gian thực dựa vào các cảm biến được gắn trên
robot. Do đó, các thuật toán on-line cho phép robot hoạt động linh hoạt ngay cả với
các môi trường mà robot hoàn toàn không biết trước. Các thuật toán on-line có sử
dụng các cảm biến để đánh giá và đi đến mục tiêu nên trong một số trường hợp còn
có thể được gọi là giải thuật bao phủ dựa trên cảm biến.

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ủ
1.3.1. Phương pháp giải quyết bài toán bao phủ
Có ba hướng chính để giải quyết bài toán bao phủ, đó là:
-

Phương pháp phân chia vùng làm việc cổ điển.

-

Phương pháp dựa trên lưới ô vuông.

-

Phương pháp sử dụng nhóm robot.

Kết hợp hai hay nhiều hướng giải quyết ở trên để giải quyết bài toán bao phủ.
MSTC chính là thuật toán dựa trên phương pháp tiếp cận vùng bao phủ thành lưới

6


các ô theo thuật toán cây bao trùm STC và kết hợp sử dụng một nhóm robot để bao
phủ.
Thuật toán MSTC được sử dụng trên các môi trường đã biết hay chưa biết có
thể gọi chúng là Offline -MSTC và Online-MSTC.
1.3.2. Các công cụ tiếp cận bài toán
Các công cụ tiếp cận bài toán gồm:
-

Tiến hành cài đặt thử nghiệm thuật toán trên môi trường mô phỏng

Gazebo có vật cản.

-

Sử dụng ROS phiên bản Indigo trên hệ điều hành Ubuntu 14.04.

-

Ngôn ngữ C++

-

Kết nối các nhóm robot bằng Client – Server trên C++

-

Chạy trên môi trường thực tế với robot Kobuki.

1.4. Nội dung đề tài và kết quả thực hiện được
1.4.1. Nội Dung đề tài
Nội dung đề tài này trình bày chi tiết những vấn đề như sau:
-

Tìm hiểu tổng quan về các phương pháp giải quyết bài toán bao phủ:

-

Tìm hiểu và nghiên cứu thuật toán tìm đường bao phủ MSTC cho nhóm
robot (MSTC-Offline và ORMSTC).


-

Đề xuất thuật toán MSTC mới cho nhóm robot.

-

Tiến hành cài đặt thử nghiệm thuật toán trên môi trường mô phỏng Gazebo
và trên môi trường thật với robot Kobuki.

1.4.2. Kết quả thực hiện được
Cho tới thời điểm hiện tại, tác giả đã thực hiện được những công việc như
sau:
-

Tìm hiều về các công cụ hỗ trợ trong lập trính nhúng.

-

Tìm hiểu về các phương pháp giải quyết bài toán bao phủ, hiểu về một số
thuật toán bao phủ tiêu biểu với một robot.

-

Tìm hiểu về các phương pháp giải quyết bài toán bao phủ MSTC tiêu biểu là
MSTC-Offline và ORMSTC.

7


-


Đề xuất các phương pháp giải quyết MSTC mới với môi trường có vật cản
2x2 và môi trường vật cản 1x1.

-

Thử nghiệm lập trình thuật toán trên thuật toán đề xuất MSTC với nhóm
robot, sau đó tiến hành cho chạy thử nghiệm và thu được kết quả:
o Chạy được trường hợp thuật toán chạy bình thường, không có robot nào
bị hỏng trong môi trường mô phỏng Gazebo.
o Xử lý được một số trường hợp có robot chết trong môi trường mô phỏng
Gazebo.

-

Chạy được trường hợp bình thường, không có robot nào bị hỏng trong môi
trường thực tế.

8


CHƯƠNG 2. PHƯƠNG PHÁP GIẢI QUYẾT BÀI TOÁN BAO PHỦ
Kế hoạch bao phủ bao phủ là một nhiệm vụ quan trọng đối với robot, với
nhiều ứng dụng thực tiễn chẳng hạn như làm sạch sàn, cắt cỏ, khai thác, thu hoạch,
sơn, và làm sạch các chất thải nguy hiểm,... Tại đây, robot được đưa ra một công
việc trong một vùng bị chặn, có thể có những chướng ngại vật, trở ngại. Robot được
giả định có một công cụ kết hợp của một hình dạng nhất định thường là các cảm
biến và/hoặc thiết bị truy câp theo vùng tuần tự. Robot cần phải “thăm” tất cả các
điểm trong khu vực làm việc. Thường thì kích thước công cụ của robot nhỏ hơn
nhiều so với khu vực làm việc của nó. Nhiệm vụ của robot là tìm kiếm và di chuyển

dọc theo một con đường sao cho nó bao phủ hoàn toàn. Đôi khi được gọi là tìm
kiếm hoàn toàn vùng, hoặc có thể là quét.
2.1. Một số phương pháp giải quyết bài toán bao phủ với đơn robot
Thuật toán bao phủ đơn giản nhất là điều khiển robot đi một cách ngẫu nhiên
trong vùng làm việc. Theo cách tiếp cận này, rõ ràng nếu robot hoạt động trong một
thời gian đủ lâu thì toàn bộ vùng làm việc của robot sẽ được bao phủ. Đây là thuật
toán được sử dụng trong nhiều robot hút bụi như Trilobite của Electrolux và nổi
tiếng nhất là Roomba của iRobot. Đặc điểm của phương pháp này là đơn giản,
không cần tính toán phức tạp và không cần các cảm biến đắt tiền trên robot. Tuy
nhiên, phương pháp này tỏ ra không hiệu quả nếu vùng làm việc của robot có kích
thước lớn và chứa nhiều vật cản có kết cấu phức tạp. Khi đó chi phí hoạt động của
robot tính theo thời gian và năng lượng tiêu thụ trở nên rất lớn không thể chấp nhận
được trên thực tế.
Trên thế giới đã có rất nhiều nghiên cứu nhằm giải quyết hiệu quả bài toán
tìm đường đi bao phủ. Các nghiên cứu này có thể được liệt kê vào ba hướng chính
như sau:
2.1.1. Phương pháp phân chia vùng làm việc cổ điển
Đây là nhóm phương pháp cổ điển nhất, có thể xem là điểm khởi đầu để xây
dựng các nhóm phương pháp mới hơn về sau. Ý tưởng cơ bản là phân chia toàn bộ
vùng làm việc của robot thành các cell đơn giản, không chồng lấn, và không chứa

9


vật cản. Tổng diện tích các cell này bằng diện tích mà robot phải bao phủ. Do đó,
bài toán tìm đường đi bao phủ trở thành bài toán phân chia vùng làm việc của robot
thành các cell. Vì các cell không chứa vật cản, nên robot có thể dễ dàng bao phủ
từng cell bằng các thao tác đơn giản như quét kiểu ziczag đường cày hoặc quét theo
vòng tròn. Công việc của các robot là làm sao để có thể bao phủ được hết các cell
đó, và việc di chuyển giữa các cell sao cho có thể tối ưu nhất có thể.


Hình 2.1: Bao phủ một cell hình chữ nhật bằng thao tác đi ziczag
2.1.1.1. Thuật toán phân chia theo hình thang
Đây là thuật toán off-line. Thuật toán cần biết thông tin môi trường làm việc
để thực hiện phân chia vùng làm việc thành các thành các hình thang, không chồng
chéo lên nhau. Việc phân chia các hình thang hình thành dựa trên chia theo trục
tung hoặc trục hoành như ở hình 2.2 dưới đây. Sau đó một đồ thị kề chỉ ra quan hệ
về mặt không gian giữa các cell sẽ được hình thành. Từ đó để đảm bảo bao phủ toàn
bộ vùng làm việc, robot cần tìm ra một đường đi qua tất cả các cell trên đồ thị kề.
Cuối cùng, robot thực hiện đi theo đường ziczag tại mỗi cell, và di chuyển giữa các
cell theo đúng thứ tự chỉ ra trong đường đi đã xác định trên đồ thị. Thuật toán hình
thang [1] khá hiệu quả với các vùng làm việc đơn giản dạng đa giác.

10


Hình 2.2: Ví dụ về thuật toán phân chia hình thang
2.1.1.2. Thuật toán phân chia Boustrophedon
Thuật toán dựa trên thuật toán trên và được ứng dụng khá nhiều là thuật toán
phân chia boustrophedon còn được gọi là thuật toán đường cày [1]. Thuật toán này
tương tự với thuật toán phân chia hình thang nhưng cho phép nối các cell kề nhau
mà robot có thể quét bởi một đường ziczag lại. Trong thuật toán này, một đỉnh chỉ
được xem xét khi nó có thể mở rộng cả lên trên và xuống dưới. Thuật toán
boustrophedon phát triển được kết hợp việc xây dựng lưới đồ thì A* tiêu biểu như
thuật toán BA*. Thuật toán được áp dụng phát triển trong bài toán bao phủ môi
trường chưa biết, thuật toán bao phủ on-line. Trong thuật toán này, vùng làm việc
của robot sẽ được chia thành các vùng boustrophedon có hình dạng phức tạp mà
robot có thể bao phủ trong một lần quét. Thuật toán BA* thực hiện tìm kiếm các
vùng boustrophedon ngay trong quá trình robot chạy, đồng thời đưa ra cơ chế quay
lui để đảm bảo tất cả các vùng boustrophedon đều được tìm thấy và không gian làm

việc của robot được bao phủ toàn bộ. Hình ở dưới đây mô tả một ví dụ phân chia
các vùng boustrophedon dựa vào thuật toán BA* với bốn vùng được đánh số từ 1
tới 4 và quỹ đạo di chuyển tương ứng của robot.

11


Hình 2.3: Ví dụ về thuật toán BA*
2.1.2. Phương pháp dựa trên lưới ô vuông
Tìm đường đi bao phủ dựa trên lưới (grid-based) [1] là hướng tiếp cận mạnh
và được quan tâm nhiều nhất khi giải quyết bài toán tìm đường đi bao phủ. Phương
pháp này thể hiện toàn bộ môi trường làm việc của robot trên một bản đồ dạng lưới
ô vuông. Mỗi ô trên lưới nhận một giá trị cho biết tại vị trí ô đó là chướng ngại vật
hay vùng không gian trống. Toàn bộ lưới cho biết hình dạng xấp xỉ của không gian
hoạt động của robot và các chướng ngại vật bên trong. Hình dưới đây mô tả một ví
dụ bản đồ lưới ô vuông với hai vật cản. Kích thước của mỗi ô vuông thường bằng
kích thước của robot hoặc là gấp hai lần kích thước robot.

12


Hình 2.4: Ví dụ phương pháp phân chia dựa trên lưới ô vuông với hai chướng
ngại vật
2.1.2.1. Thuật toán tràn sóng wavefront
Đây là thuật toán off-line, sử dụng lưới đại diện môi trường với kích thước
gấp hai lần kích thước robot. Thuật toán wavefront lập kế hoạch bao phủ hoàn thành
vào lưới điện trên. Phương pháp này đòi hỏi phải có ô bắt đầu và ô mục tiêu. Sự
thay đổi khoảng cách bằng cách lan truyền sóng từ ô mục tiêu đến ô bắt đầu sử
dụng để chỉ định số đặc trưng cho mỗi phần tử lưới. Đầu tiên thuật toán gán nhãn số
0 cho ô mục tiêu và sau đó gán nhãn số 1 cho tất cả các ô mà xung quanh ô đó. Quá

trình được thực hiện tương tự với các ô còn lại. Quá trình này lặp đi lặp lại từng
bước cho đến khi tất cả các ô được gán một số nhãn cụ thể. Quá trình đó được gọi là
quá trình transform (trán sóng). Hình 2.5 ví dụ thể hiện minh họa quy trình này trên
một môi trường [1]. Khi chuyển đổi khoảng cách được tính toán xong, kế hoạch bao
phủ có thể được tìm thấy bằng cách bắt đầu từ các ô bắt đầu và lựa chọn các ô lân
cận với các nhãn cao nhất chưa được thăm. Nếu có hai hoặc nhiều ô lân cận chưa
được thăm chia sẻ cùng một nhãn, thì một trong các ô được chọn ngẫu nhiên. Hình
2.6 thể hiện kế hoạch bao phủ thuật toán transform.

13


Hình 2.5: Gán có số cho các ô bằng cách lan truyền bước sóng với ô bắt đầu (S)
và ô đích (G).

Hình 2.6: Kế hoạch bao phủ sử dụng biến đổi khoảng cách với thuật toán
wavefront
2.1.2.2. Thuật toán cây bao trùm.
Thuật toán này thuộc phương pháp tiếp cận dựa trên lưới ô vuông đã đề cập
tới ở trên. Trong thuật toán này, chia nhỏ dần vùng làm việc thành các ô vuông kích
thước 2Dx2D gọi là cell, với D là kích cỡ mỗi robot (các robot được giả định là
giống nhau), mỗi ô chứa bốn ô con, gọi là subcell, có kích thước bằng kích thước
robot và bỏ qua những cell bị chiếm (một phần hoặc toàn phần) bởi vật cản. Các
cell trống tạo thành một cấu trúc đồ thị có các nodes là tâm điểm của từng cell và
các cạnh là đoạn thẳng nối tâm điểm các cell liền kề [2].

14


Hình 2.7: Phân chia cell trong thuật toán cây bao trùm

Lớp thuật toán dựa trên cây bao trùm tiêu biểu là thuật toán Spiral-STC
(Spiral Spanning Tree Coverage). Spiral-STC [2] là thuật toán tìm đường on-line
với đường đi của robot được xây dựng theo hình xoắn ốc. Đường đi của robot trong
thuật toán này được hình thành bằng cách xuất phát từ cell chứa vị trí bắt đầu của
robot rồi đi sang các cell trống bên cạnh theo chiều ngược chiều kim đồng hồ. Quá
trình tiếp tục tới khi không còn cell nào trống thì robot bắt đầu đi theo chiều ngược
lại. Do kích thước cell là 2Dx2D, robot sẽ không bao giờ đi qua một subcell hai lần
và sẽ quay lại vị trí ban đầu sau khi đã bao phủ toàn bộ diện tích làm việc. Thuật
toán có đường đi tối, mỗi ô được thăm chỉ với một lần. Hình 2.8 mô tả một ví dụ về
đường bao phủ của robot được hình thành khi áp dụng thuật toán Spiral-STC.

15


Hình 2.8: Đường bao phủ của robot khi áp dụng thuật toán Spiral – STC
Giải thuật Spiral-STC dần dần xây dựng một cây bao trùm cho đồ thị này và
sử dụng cây bao trùm đó để sinh ra đường dẫn bao phủ như sau: cùng với việc xây
dựng cây bao trùm, robot chia nhỏ mọi cell nó bắt gặp thành bốn subcell nhỏ đều có
kích thước D và có cùng kích thước cũng như hình dạng với dụng cụ quét. Dụng cụ
quét đi theo đường dẫn của các subcell vòng quanh dần dần theo cây bao trùm đã
được xây dựng cho đến khi toàn bộ tập hợp các cell trống được bao phủ. Ở đây một
cell trống là “mới” khi tất cả bốn subcell của nó chưa được bao phủ, ngược là thì coi
là “cũ”. Tức là chỉ cần 1 subcell trong cell đã được bao phủ, cell đó sẽ được coi là
“cũ”.
2.2. Phương pháp giải quyết sử dụng một nhóm robot
Phương pháp tiếp cận này sử dụng nhiều robot hoạt động song song, nhờ đó
cho phép rút ngắn thời gian bao phủ không gian làm việc bằng cách phân chia công
việc cho từng robot. Hơn thế nữa, khi kết hợp hoạt động của nhiều robot hệ thống
còn có thể giải quyết nhiều vấn đề khó khác. Chẳng hạn các robot có thể trợ giúp
lẫn nhau khi có robot gặp lỗi trong quá trình làm việc.

Các hệ thống sử dụng nhiều robot thường được xây dựng trên cơ sở mở rộng
các thuật toán tìm đường đi bao phủ của một robot như phân chia boustrophedon,

16


cây bao trùm, mạng nơ-ron. Ngoài ra cũng có một số thuật toán bao phủ dành riêng
cho hệ thống nhiều robot được phát triển.
Có thể nêu ra một số tiêu chí chính để đánh giá một thuật toán bao phủ, như
là “tính bao phủ toàn bộ” (tạo ra đường đi bao phủ toàn bộ được khu vực làm việc),
“tính hiệu quả” (robot di chuyển dựa theo thuật toán đó có thể hoàn thành công việc
trong thời gian nhanh nhất có thể), “tính mạnh mẽ” (các robot có thể hỗ trợ nhau
trong trường hợp có thành viên bị lỗi). Ngoài ra, người ta cũng xét cả tới việc không
dư thừa đường bao phủ, tức là không có một cell được quét lại hai lần trở lên.
Có thể lấy ví dụ tiêu biểu cho nhóm các thuật toán sử dụng phương pháp giải
quyết bài toán này là thuật toán phân chia boustrophedon sử dụng nhóm robot.
Thuật toán này nhằm bao phủ đường đi đầy đủ sử dụng một nhóm robot trong môi
trường chưa xác định (môi trường on-line). Nhóm tác giả của thuật toán này cho
rằng, việc sử dụng nhiều robot có thể giảm thời gian làm việc, tuy nhiên chỉ có thể
đạt được tối đa hiệu quả làm việc nếu như số lượng các vùng mà robot đi lặp lại là ít
nhất. Do đó thuật toán này tập trung vào việc giảm thiểu tối đa sự lặp đi lặp lại các
vùng di chuyển của robot. Thuật toán này sử dụng cùng một phương pháp phân tích
cell hai chiều như thuật toán bao phủ boustrophedon sử dụng robot đơn, nhưng nó
mở rộng để xử lý việc làm thế nào để các robot có thể đi hết các vùng đơn lẻ, và
làm thế nào để phân bố các robot giữa các vùng. Giải pháp của họ là tính toán để
hạn chế các thành viên trong nhóm robot di chuyển giao nhau trong quá trình làm
việc. Các robot sẽ di chuyển chủ yếu theo các đường thẳng. Để có thể quét được
toàn bộ vùng đang làm việc, các robot được chia làm hai nhóm để đảm nhận hai vai
trò: một vài robot, được gọi là explorer (robot thăm dò) đi men theo các ranh giới
của vùng mục tiêu hiện tại, trong khi các robot khác, được gọi là coverer (robot bao

phủ) thực hiện các chuyển động tới lui để có thể đi hết được các phần còn lại. Để
phân phối các nhiệm vụ cho các robot, cũng như phân phối các vùng hoạt động cho
từng robot, một cơ chế đấu giá tham lam được sử dụng [1].
Hình 2.9 mô tả việc hai robot explorer thực hiện di chuyển ở hai biên trên và
dưới của vùng mục tiêu, trong khi ba robot coverer thực hiện các chuyển động tới

17