Luận văn Thạc sĩ Kỹ thuật: Nghiên cứu thuật toán tìm đường bao phủ cho một nhóm robot di động

Chia sẻ: Sơ Dương | Ngày: | Loại File: PDF | Số trang:83

Thêm vào BST

Báo xấu

28
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài "Nghiên cứu thuật toán tìm đường bao phủ cho một nhóm robot di động" nghiên cứu nhằm 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), 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ế.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Kỹ thuật: Nghiên cứu thuật toán tìm đường bao phủ cho một nhóm robot di động

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Ữ Thuật ngữ/Chữ viết tắt Viết đầy đủ 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à off- line. 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