Tài liệu Phát triển thuật toán tìm đường bao phủ cho robot lau nhà

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ---------------------------- PHẠM TUẤN KHANH PHÁT TRIỂN THUẬT TOÁN TÌM ĐƯỜNG BAO PHỦ CHO ROBOT LAU NHÀ LUẬN VĂN THẠC SĨ KỸ THUẬT CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN GƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN HOÀNG VIỆT Hà Nội – 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ---------------------------- PHẠM TUẤN KHANH PHÁT TRIỂN THUẬT TOÁN TÌM ĐƯỜNG BAO PHỦ CHO ROBOT LAU NHÀ LUẬN VĂN THẠC SĨ KỸ THUẬT CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGÔ LAM TRUNG Hà Nội – 2017 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ LỜI CẢM ƠN Tác giả xin chân thành cảm ơn TS. Ngô Lam Trung đã nhiệt tình giúp đỡ, hỗ trợ tác giả cả về định hướng nghiên cứu lẫn môi trường phát triển cũng như đã tận tình chỉ dẫn để tác giả có thể hoàn thành luận văn này. Dù đã hết sức cố gắng nhưng chắc chắn nội dung luận này vẫn còn nhiều thiếu sót, do đó tác giả luôn mong muốn được sự chỉ bảo, góp ý của các thầy cô và các bạn để có thể hoàn thiện hơn nữa luận văn này. -----------------------------------------------------------------------------------------------------------------------------------------1 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ MỤC LỤC DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ............................................................................ 4 DANH MỤC CÁC BẢNG .......................................................................................................................... 5 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .................................................................................................... 6 PHẦN MỞ ĐẦU.......................................................................................................................................... 7 CHƯƠNG 1. GIỚI THIỆU MỘT SỐ THUẬT TOÁN TÌM ĐƯỜNG BAO PHỦ HIỆN NAY........... 9 1.1 Bài toán tìm đường đi bao phủ cho robot ......................................................................... 9 1.2 Phân loại thuật toán bao phủ ............................................................................................. 9 1.3 Một số thuật toán bao phủ đang được sử dụng hiện nay .............................................. 10 1.3.1. Thuật toán đơn giản nhất..................................................................................................... 10 1.3.2. Thuật toán phân chia vùng làm việc cổ điển ....................................................................... 10 1.3.3. Thuật toán phân chia vùng làm việc dựa trên các điểm mốc .............................................. 12 1.3.4. Thuật toán dựa trên lưới (grid-based) ................................................................................. 13 1.3.5. Sử dụng nhiều robot ............................................................................................................ 14 CHƯƠNG 2. TỔNG QUAN VỀ ROS ..................................................................................................... 16 2.1 ROS là gì? .......................................................................................................................... 16 2.2 Các thành phần trong kiến trúc của ROS ...................................................................... 16 2.2.1. 2.2.1.1. Messages ..................................................................................................................... 18 2.2.1.2. Services ....................................................................................................................... 19 2.2.1.3. Code ............................................................................................................................ 20 2.2.1.4. Packages ...................................................................................................................... 20 2.2.1.5. Stacks .......................................................................................................................... 20 2.2.2. Computational Level ........................................................................................................... 21 2.2.2.1. Nodes .......................................................................................................................... 21 2.2.2.2. Master ......................................................................................................................... 21 2.2.2.3. Parameter Server ......................................................................................................... 21 2.2.2.4. Messages ..................................................................................................................... 21 2.2.2.5. Topic ........................................................................................................................... 22 2.2.2.6. Services ....................................................................................................................... 22 2.2.2.7. Bag .............................................................................................................................. 22 2.2.3. 2.3 File System Level................................................................................................................ 17 Community Level ............................................................................................................... 22 Lập trình cho robot dùng ROS ........................................................................................ 23 -----------------------------------------------------------------------------------------------------------------------------------------2 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà -----------------------------------------------------------------------------------------------------------------------------------------CHƯƠNG 3. PHÁT TRIỂN THUẬT TOÁN TÌM ĐƯỜNG BAO PHỦ VỚI NHIỀU ROBOT DÙNG ROS................................................................................................................................................ 27 Các thông số kỹ thuật của robot sử dụng trong nghiên cứu và môi trường phát triển 27 3.1 3.1.1 Các thông số kỹ thuật của robot sử dụng trong nghiên cứu ............................................... 27 3.1.2 Môi trường phát triển .......................................................................................................... 29 3.1.2.1 Các giả định về môi trường hoạt động của robot ............................................................ 29 3.1.2.2 Hệ điều hành và công cụ phát triển ................................................................................. 29 Phát triển thuật toán cho bài toàn tìm đường bao phủ với nhiều robot ...................... 30 3.2 3.2.1. Phát triển thuật toán Spiral-STC cho một robot .................................................................. 30 3.2.2. Mô hình thiết kế cho bài toán tìm đường bao phủ với nhiều robot ..................................... 44 3.2.3. Tạo bản đồ và định vị robot trên bản đồ ............................................................................. 46 3.2.3.1. Tạo bản đồ................................................................................................................... 46 3.2.3.2. Định vị robot trên bản đồ ............................................................................................ 49 3.2.4. Điều khiển robot đi đến một điểm cho trước trên bản đồ ................................................... 52 3.2.5. Giao tiếp giữa các robot ...................................................................................................... 54 3.2.6. Framework lập trình phát triển các thuật toán tìm đường bao phủ trên lưới cho robot lau nhà dùng ROS .................................................................................................................................... 57 3.2.7. Các kết quả đạt được ........................................................................................................... 60 KẾT LUẬN ................................................................................................................................................ 61 TÀI LIỆU THAM KHẢO ........................................................................................................................ 63 -----------------------------------------------------------------------------------------------------------------------------------------3 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Các ký hiệu, chữ viết tắt ROS BA* Spiral-STC BSA SLAM AMCL [] Ý nghĩa Robot Operating System The Boustrophedon motion and the A* search Spiral Spanning Tree Coverage Backtracking Spiral Algorithm Simultaneous Localization and Mapping Adaptive Monte Carlo localization Sử dụng thông tin trong tài liệu tham khảo -----------------------------------------------------------------------------------------------------------------------------------------4 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ DANH MỤC CÁC BẢNG Bảng 2-1. Ví dụ minh họa về một message ................................................................................................ 18 Bảng 2-2. Kiểu dữ liệu dùng trong message của ROS ................................................................................ 19 Bảng 2-3. Định nghĩa kiểu Header trong ROS ........................................................................................... 19 Bảng 3-1. Các thông số kỹ thuật của Kobuki base ..................................................................................... 28 Bảng 3-2. Các topic của TurtleBot2 được sử dụng trong quá trình thực hiện luận văn .............................. 29 Bảng 3-3. Đường đi giữa hai megacell theo chiều ngược kim đồng hồ...................................................... 37 Bảng 3-4. Đường đi giữa hai megacell theo chiều kim đồng hồ................................................................. 41 -----------------------------------------------------------------------------------------------------------------------------------------5 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1-1. Quét dic-dắc để bao phủ một cell hình chữ nhật ........................................................................ 10 Hình 1-2. Phân chia theo hình thang ........................................................................................................... 11 Hình 1-3. Phân chia boustrophedon ............................................................................................................ 12 Hình 1-4.Thuật toán BA* ........................................................................................................................... 12 Hình 1-5. Minh họa ý tưởng chung về thuật toán dựa trên lưới.................................................................. 13 Hình 1-6. Thuật toán Spiral-STC ................................................................................................................ 14 Hình 1-7. Thuật toán phân chia boustrophedon cho nhiều robot ................................................................ 15 Hình 1-8. Thuật toán cây bao trùm để tạo đường đi cho ba robot .............................................................. 15 Hình 1-9. Thuật toán Multi-robot Forest Coverage (MFC) ........................................................................ 15 Hình 2-1. Kiến trúc chung của ROS ........................................................................................................... 16 Hình 2-2. Các thành phần trong hệ thống file của ROS.............................................................................. 17 Hình 2-3. Minh họa về lưu trữ trong hệ thống file của ROS ...................................................................... 18 Hình 2-4. Mối quan hệ giữa Stack và Package ........................................................................................... 20 Hình 2-5. Các thành phần trong Computational Level ............................................................................... 21 Hình 2-6. Màn hình mô phỏng turtlesim..................................................................................................... 24 Hình 3-1. Cấu tạo TurtleBot2 ..................................................................................................................... 27 Hình 3-2. Robot bao phủ một cell trong Spiral-STC .................................................................................. 31 Hình 3-3. Một bản đồ được tạo ra bởi công cụ tạo bản đồ của ROS .......................................................... 31 Hình 3-4. Xác định vị trí megacell xuất phát của robot .............................................................................. 32 Hình 3-5. Lựa chọn megacell cạnh megacell xuất phát để bắt đầu di chuyển ............................................ 32 Hình 3-6. Lựa chọn megacell trong quá trình di chuyển theo Spiral-STC ................................................. 33 Hình 3-7. Lưu trữ danh sách các megacell đã đi qua của robot .................................................................. 42 Hình 3-8. Lược đồ cho phát triển thuật toán thuật toán Sprial-STC đối với một robot .............................. 43 Hình 3-9. Mô hình nhiều robot cho bài toán tìm đường bao phủ................................................................ 45 Hình 3-10. Công cụ giả lập robot gazebo ................................................................................................... 47 Hình 3-11. Công cụ hiển thị RVIZ ............................................................................................................. 48 Hình 3-12. Định vị robot trên bản đồ .......................................................................................................... 50 Hình 3-13. Mô hình liên hệ move_base,map_server,amcl và robot ........................................................... 53 Hình 3-14. Mô hình hoạt động của Map Center ......................................................................................... 57 Hình 3-15. Framework cho khâu tạo bản đồ ............................................................................................... 58 Hình 3-16. Framework cho khâu điều khiển robot theo thuật toán ............................................................ 59 -----------------------------------------------------------------------------------------------------------------------------------------6 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ PHẦN MỞ ĐẦU Với mong muốn có một nghiên cứu đầy đủ về việc làm sao phát triển thuật toán tìm đường bao phủ áp dụng được trên một robot thực tế cũng như xây dựng mô hình hoạt động cho nhiều robot hoạt động đồng thời để giải quyết bài toán tìm đường bao phủ chính là lý do để tác giả lựa chọn đề tài “Phát triển thuật toán tìm đường bao phủ cho robot lau nhà” . Để thực hiện đề tài, tác giả lựa chọn nghiên cứu tìm hiểu việc xây dựng mô hình nhiều robot chạy thuật toán Spiral-STC(Spanning Tree Coverage) để giải quyết bài toán tìm đường bảo phủ một bản đồ cho trước. Trong đó thuật toán Spiral-STC sẽ được phát triển chi tiết trên nền tảng ROS(Robot Operating System) với một số thay đổi đề phù hợp với mô hình nhiều robot. Robot được tác giả lựa chọn để nghiên cứu và cài đặt thuật toán là TurtleBot do Kobuki sản xuất. Qua quá trình thực hiện luận văn này, tác giả đã đạt được một số kết quả:  Tìm hiểu về hệ điều hành ROS, cơ chế vận hành điều khiển robot trên nền tảng ROS  Tìm hiểu một số thuật toán tìm đường bao phủ đang có hiện nay, cụ thể hóa việc phát triển thuật toán Sprial-STC cho một robot trên nền tảng ROS  Xây dựng mô hình nhiều robot cùng chạy thuật toán Sprial-STC để bao phủ một bản đồ cho trước trên nền tảng ROS  Thử nghiệm và đánh giá kết quả trên môi trường giả lập cũng như môi trường thật Việc trình bày quá trình thực hiện và các kết quả đạt được của luận văn được thể hiện qua cấu trúc của luận văn này được bố cục như sau: PHẦN MỞ ĐẦU CHƯƠNG 1. GIỚI THIỆU MỘT SỐ THUẬT TOÁN TÌM ĐƯỜNG BAO PHỦ 1.1 1.2 1.3 Bài toán tìm đường đi bao phủ cho robot Phân loại thuật toán bao phủ Một số thuật toán bao phủ đang được sử dụng hiện nay CHƯƠNG 2. TỔNG QUAN VỀ ROS 2.1 ROS là gì -----------------------------------------------------------------------------------------------------------------------------------------7 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ 2.2 2.3 Các thành phần trong kiến trúc của ROS Lập trình cho robot dùng ROS CHƯƠNG 3. PHÁT TRIỂN THUẬT TOÁN TÌM ĐƯỜNG BAO PHỦ VỚI NHIỀU ROBOT DÙNG ROS 3.1 3.2 Các thông số kỹ thuật của robot sử dụng trong nghiên cứu và môi trường phát triển Phát triển thuật toán cho bài toán tìm đường bao phủ với nhiều robot KẾT LUẬN TÀI LIỆU THAM KHẢO -----------------------------------------------------------------------------------------------------------------------------------------8 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ CHƯƠNG 1. GIỚI THIỆU MỘT SỐ THUẬT TOÁN TÌM ĐƯỜNG BAO PHỦ HIỆN NAY 1.1 Bài toán tìm đường đi bao phủ cho robot Bài toán tìm đường đi bao phủ là bài toán xác định một đường đi qua tất cả các điểm thuộc một khu vực nào đó kết hợp vòng tránh chướng ngại vật nếu có. Đây là vấn đề nghiên cứu quan trọng đối với rất nhiều hệ thống robot có ứng dụng trong thực tế như robot hút bụi, robot cắt cỏ, robot rà phá bom mìn, robot thu hoạch mùa vụ, robot lau cửa kính, robot sơn tự động… Lấy ví dụ robot hút bụi, khi hoạt động phải đảm bảo làm sạch toàn bộ diện tích sàn làm việc, đồng thời phải phát hiện và tránh được các vật cản như bàn ghế, đồ đạc trong phòng. Để giải quyết bài toán này cần xây dựng các thuật toán tìm đường đi bao phủ, hay còn được gọi ngắn gọn hơn là thuật toán bao phủ. Theo tham khảo từ tài liệu [1], các thuật toán bao phủ cần thỏa mãn các yêu cầu cơ bản như sau: 1. Robot phải đi qua tất cả các điểm trong vùng hoạt động, nói cách khác, đường đi của robot phải bao phủ toàn bộ vùng hoạt động. 2. Robot không được thực hiện/hạn chế các đường đi chồng lấn lẫn nhau. 3. Robot phải hoạt động liên lục và tuần tự theo các đường đi không lặp lại. 4. Robot phải tránh các vật cản xuất hiện trong vùng hoạt động. 5. Quỹ đạo chuyển động của robot cần đơn giản (hình tròn hoặc đường thẳng) để đơn giản hóa phần điều khiển robot. 6. Đường đi của robot cần được tối ưu hóa dựa vào những điều kiện nhất định Ngoải ra, cũng theo [1], ta có thể phân loại các thuật toán bao phủ và liệt kê một số thuật toán bao phủ đang được sử dụng hiện nay như các nội dung tiếp theo đây. 1.2 Phân loại thuật toán bao phủ 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ủ hoàn toàn 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ủ hoàn toàn 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 online và offline. Thuật toán offline 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 bảo phủ phải được biết trước khi robot hoạt động. Ngược lại, các thuật toán online 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 -----------------------------------------------------------------------------------------------------------------------------------------9 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ 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 online 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. 1.3 1.3.1. Một số thuật toán bao phủ đang được sử dụng hiện nay Thuật toán đơn giản nhất 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ế. 1.3.2. Thuật toán phân chia vùng làm việc cổ điển Đây là phương pháp cổ điển nhất, có thể coi 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 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ủ. 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 dícdắc hoặc quét theo vòng tròn. 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. Hình 1-1 mô tả ví dụ một vòng quét dic-dắc để bao phủ một cell hình chữ nhật. Hình 1-1. Quét dic-dắc để bao phủ một cell hình chữ nhật -----------------------------------------------------------------------------------------------------------------------------------------10 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ Thuật toán đơn giản nhất theo cách tiếp cận này là thuật toán phân chia theo hình thang. Thuật toán này phân chia vùng làm việc đa giác thành các cell hình thang như trên hình 1-2. 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ủ hoàn toàn 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 dícdắc 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 khá hiệu quả với các vùng làm việc đơn giản dạng đa giác. Đây là thuật toán offline vì robot cần biết thông tin về môi trường làm việc trước khi thực hiện tìm đường. Hình 1-2. Phân chia theo hình thang Thuật toán thứ hai phát triển theo phương pháp cổ điển và được ứng dụng khá nhiều là thuật toán phân chia boustrophedon. Boustrophedon(bu-strơ-fi-đơn) là từ gốc Hy Lạp, có nghĩa là “đường đi của con bò” liên hệ với hình ảnh con bò kéo cày thành các đường díc-dắc trên mặt ruộng. 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 díc-dắc lại. Qua đó số lượng cell trên đồ thị kề sẽ giảm đi và làm giảm tổng quãng đường robot phải chạy để bao phủ toàn bộ vùng làm việc. Ví dụ về thuật toán phân chia boustrophedon được chỉ ra trong hình 1-3. Có thể thấy các cell C3, C5, C7 ở hình 1-2 đã được nối thành một cell duy nhất ở vị trí tương ứng trong hình 1-3. Thuật toán này cũng là thuật toán offline. -----------------------------------------------------------------------------------------------------------------------------------------11 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ Hình 1-3. Phân chia boustrophedon Gần đây có một số thuật toán bao phủ online được phát triển dựa trên cách tiếp cận của thuật toán phân chia boustrophedon, tiêu biểu là thuật toán BA*(The Boustrophedon motion and the A* search algorithm). 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ủ hoàn toàn. Hình 1-4 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. Hình 1-4.Thuật toán BA* 1.3.3. Thuật toán phân chia vùng làm việc dựa trên các điểm mốc Phương pháp này đề xuất phân chia không gian làm việc của robot thành các cell dựa trên các điểm mốc tự nhiên đặc trưng cho hình dạng của không gian làm việc và của các chướng ngại vật. Phương pháp được thực hiện bằng cách quét một đường quét dịch chuyển dần trong không gian làm việc của robot. Trong quá trình quét robot sẽ thu nhận dữ liệu và xây dựng bản đồ địa hình của không gian làm việc. Từ đó robot xác định -----------------------------------------------------------------------------------------------------------------------------------------12 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ đường biên của các cell và đi quét các cell tới khi bao phủ toàn bộ vùng không gian làm việc. 1.3.4. Thuật toán dựa trên lưới (grid-based) Tìm đường đi bao phủ dựa trên lưới (grid-based) 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 biểu diễ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 (grid map). 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 1-5 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. Do đó phương pháp này thường được áp dụng cho môi trường trong nhà để tránh số ô của lưới tăng lên quá cao. Hình 1-5. Minh họa ý tưởng chung về thuật toán dựa trên lưới Với cách tiếp cận của phương pháp này, bài toán tìm đường đi bao phủ trở thành tìm đường đi tối ưu để duyệt qua tất cả các ô không chứa vật cản trên lưới, mỗi ô một lần. Một lớp thuật toán đã được phát triển để giải bài toán này, tiêu biểu là thuật toán SpiralSTC(Spiral Spanning Tree Coverage). Spiral-STC là thuật toán tìm đường online trong đó đường đi của robot được xây dựng theo hình xoắn ốc. Toàn bộ lưới ô vuông được chia thành các mega-cell kích thước 2x2, mỗi mega-cell chứa bốn cell nhỏ hơn có kích thước bằng kích thước robot. Đường đi của robot được hình thành bằng cách xuất phát từ megacell chứa vị trí bắt đầu của robot rồi đi sang các mega-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 mega-cell nào trống thì robot bắt đầu đi theo chiều ngược lại. Do kích thước mega-cell là 2x2, robot sẽ không bao giờ đi qua một cell nhỏ 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. Hình 1-6 mô tả một ví dụ áp dụng thuật toán Spiral-STC. -----------------------------------------------------------------------------------------------------------------------------------------13 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ Hình 1-6. Thuật toán Spiral-STC Backtracking Spiral Algorithm (BSA), một thuật toán mở rộng của Spiral-STC, đã được đưa ra nhằm cho phép robot quét cả các ô lưới bị chiếm một phần bởi vật cản. Vì các ô này đều nằm ở chân tường, hoặc biên của vật cản nên để quét các ô này robot chỉ cần thực hiện thuật toán đi theo tường (wall following) nào đó. Bên cạnh các thuật toán trên, nhiều thuật toán khác cũng đã được đề xuất để tìm đường trên grid map như thuật toán wavefront, thuật toán dùng mạng nơ-ron. 1.3.5. Sử dụng nhiều robot Phương pháp tiếp cận sử dụng nhiều robot hoạt động song song rõ ràng sẽ 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 để giảm thiểu sai số định vị, hay đảm bảo tỷ lệ bao phủ 100% ngay cả 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, cây bao trùm, mạng nơ-ron. Hình 1-7 mô tả hoạt động của thuật toán phân chia boustrophedon cho nhiều robot. Các robot được chia thành hai nhóm: explorer và coverer. Nhóm explorer có nhiệm vụ thu thập thông tin bản đồ môi trường làm việc, từ đó phân vùng làm việc để nhóm coverer thực hiện bao phủ. -----------------------------------------------------------------------------------------------------------------------------------------14 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ Hình 1-7. Thuật toán phân chia boustrophedon cho nhiều robot Phương pháp tìm đường đi bao phủ dựa trên grid map cũng được phát triển rất nhiều cho cấu hình nhiều robot. Hình 1-8 mô tả một ví dụ khi áp dụng thuật toán cây bao trùm để tạo đường đi cho ba robot trong cùng một vùng làm việc. Hình 1-9 mô tả thuật toán Multi-robot Forest Coverage (MFC) để xây dựng đường đi heuristic cho một đội gồm nhiều robot. Hình 1-8. Thuật toán cây bao trùm để tạo đường đi cho ba robot Hình 1-9. Thuật toán Multi-robot Forest Coverage (MFC) -----------------------------------------------------------------------------------------------------------------------------------------15 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ CHƯƠNG 2. TỔNG QUAN VỀ ROS 2.1 ROS là gì? ROS viết tắt của Robot Operating System, là một hệ điều hành mã nguồn mở chạy trên nền Ubuntu, được cài đặt trong rất nhiều robot hiện nay. ROS là một tập hợp các công cụ(tool), thư viện(library), các quy chuẩn(convention) nhằm mục đích đơn giản hóa việc tạo ra các ứng dụng điều khiển robot với nhiều platform xây dựng robot khác nhau hay nói cách khác ROS cung cấp một framework để viết các ứng dụng điều khiển robot. Về cơ bản, ROS có những đặc tính thiết yếu của một hệ điều hành như khả năng thực hiện các tác vụ (task) song song, giao tiếp, trao đổi dữ liệu với nhau giữa các tác vụ, quản lý dữ liệu,… Hơn thế nữa, để ROS có thể ứng dụng trong lĩnh vực robotics, ROS còn được phát triển riêng biệt về các thư viện, công cụ dành cho việc thu thập, xử lý, hiển thị, điều khiển,… ROS là một dự án lớn với nhiều người sáng lập cũng như nhận được sự đóng góp công sức của nhiều người. Nhu cầu về một framework có tính mở cũng như hỗ trợ cộng tác đã xuất hiện trong cộng động nghiên cứu về lĩnh vực robot từ sớm với rất nhiều các dự án khác nhau tại đại học Stanford từ giữa những năm 2000 như các dự án tích hợp, nhúng trí tuệ nhân tạo(AI) Stanford AI Robot (STAIR) hay dự án Personal Robots(PR) nhằm tạo ra các nguyên mẫu robot (prototype) với hệ thống phần mềm có tính động(dynamic) và mềm dẻo, dễ tương thích(flexible). Năm 2007, công ty Willow Garage dựa trên các kết quả nghiên cứu trước đó đã phát triển ROS và đưa ROS ra cộng động nguồn mở và nhận được sự đóng góp của rất nhiều nhà nghiên cứu vào các cấu phần cốt lõi(core) cũng như các gói phần mềm(packages) nền tảng của ROS. Cho đến nay ROS đã tạo ra một hệ sinh thái phần mềm(ROS ecosystem) với hơn 10.000 người dùng trên toàn cầu. 2.2 Các thành phần trong kiến trúc của ROS Kiến trúc chung của ROS được mô tả trong hình 2.2-1 Hình 2-1. Kiến trúc chung của ROS -----------------------------------------------------------------------------------------------------------------------------------------16 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ Kiến trúc chung của ROS được phân chia thành 3 tầng(level): - - - File System Level:là tầng tổ chức hệ thống file của ROS như cấu trúc thư mục, các file tối thiểu phải có để hệ thống hoạt động, ở tầng này cũng bao gồm các tool để quản lý source code, dịch source code, định nghĩa các message sử dụng trong hệ thống Computational Level hay Computation Graph Level: là nơi xử lý giao tiếp giữa các tiến trình(process) trong một hệ thống hoặc giữa các hệ thống với nhau thông qua các message được định nghĩa ở File System Level Community Level: Là nơi cho phép các thành viên trong cộng đồng sử dụng ROS chia sẻ kinh nghiệm, hiểu biết, thuật toán.. thông qua các module mã nguồn mở của mình 2.2.1. File System Level Hệ thống file của ROS bao gồm các thành phần như hình 2-2: Hình 2-2. Các thành phần trong hệ thống file của ROS Hệ thống file của ROS chia làm các thư mục(folder) và trong các thư mục này có một số file có một số file mô tả chức năng của chúng tương ứng với các thành phần như hình 2-2. Hình 2-3 bên dưới là môt minh họa về tổ chức hệ thống file của ROS -----------------------------------------------------------------------------------------------------------------------------------------17 Phạm Tuấn Khánh CH2015B CNTT - Phát triển thuật toán tìm đường bao phủ cho robot lau nhà ------------------------------------------------------------------------------------------------------------------------------------------ Hình 2-3. Minh họa về lưu trữ trong hệ thống file của ROS 2.2.1.1. Messages Một message đơn giản là một cấu trúc dữ liệu, bao gồm các trường được định kiểu. Các kiểu dữ liệu chuẩn (như integer, floating point, boolean,…) và mảng (array) với kiểu chuẩn đều được hỗ trợ. Messages có thể bao gồm các cấu trúc và các mảng lồng nhau (giống như kiểu structs trong ngôn ngữ C). Khi tạo ra một message, message đó sẽ được lưu trong một file .msg trong thư mục msg bên trong thư mục chứa package. Cấu trúc message bao gồm 2 phần: field và constant trong đó field mô tả kiểu dữ liệu còn constant là tên trường trong message. Bảng 2-1 bên dưới mô tả về một message đơn giản. Field int32 float32 string Constant id vel name Bảng 2-1. Ví dụ minh họa về một message Bảng 2-2 bên dưới mô tả các kiểu dữ liệu tương ứng với các ngôn ngữ lập trình mà ROS sử dụng -----------------------------------------------------------------------------------------------------------------------------------------18