LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của tôi. Các số liệu, kết quả nêu trong luận văn phản ánh trung thực nội dung và quá trình nghiên cứu của luận văn. Hồ Chí Minh, ngày 28 tháng 02 năm 2014 (Ký tên và ghi rõ họ tên) Châu Quang Hải iii LỜI CẢM TẠ Trong suốt quá trình thực hiện đề tài, ngƣời thực hiện đã đƣợc sự hƣớng dẫn tận tình của TS. Ngô Văn Thuyên – Phó Hiệu Trƣởng Trƣờng Đại Học Sƣ Phạm Kỹ Thuật TP HCM, giảng viên trƣờng Đại Học Sƣ Phạm Kỹ Thuật tp.
Hồ Chí Minh. Dƣới sự hƣớng dẫn của Thầy, đề tài đã đƣợc nghiên cứu và hoàn thành đúng thời hạn cũng nhƣ mục tiêu đề ra ban đầu. Ngƣời thực hiện xin gửi lòng tri ân sâu sắc đến TS. Ngô Văn Thuyên vì những kiến thức quý báu và các phƣơng pháp nghiên cứu mà thầy đã truyền dạy.
Ngƣời thực hiện gửi lòng tri ân đến quý thầy cô trƣờng Đại Học Sƣ Phạm Kỹ Thuật tp. Hồ Chí Minh, quý thầy cô trƣờng Đại Học Bách Khoa tp. Hồ Chí Minh đã tận tình hƣớng dẫn và truyền đạt những kiến thức, phƣơng pháp nghiên cứu và các kinh nghiệm trong suốt hai năm học. Những kiến thức và kinh nghiệm này chính là nền tảng giúp ngƣời thực hiện hoàn thành tốt luận văn này.
Ngƣời thực hiện chân thành cảm ơn quý anh chị, chân thành cảm ơn bạn bè và ngƣời thân đã tận tình giúp đỡ trong suốt khóa học cũng nhƣ trong quá trình thực hiện luận văn. Hồ Chí Minh, ngày 28 tháng 02 năm 2014 Ngƣời thực hiện Châu Quang Hải iv NHẬN XÉT CỦA GIÁO VIÊN HƢỚNG DẪN. HCM, ngày tháng năm 2014 TS. NGÔ VĂN THUYÊN v NHẬN XÉT CỦA CHỦ NHIỆM NGÀNH.
HCM, ngày tháng năm 2014 TRẦN THU HÀ vi NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN. TP HCM, ngày tháng năm 2014 vii NHẬN XÉT CỦA HỘI ĐỒNG BẢO VỆ LUẬN VĂN. TP HCM, ngày tháng năm 2014 viii TÓM TẮT Robot tự hành là một trong những bài toán quan trọng về việc robot tìm ra một đƣờng đi từ điểm bắt đầu đến điểm kết thúc mà không va chạm với vật cản thông qua dữ liệu từ cảm biến. Có rất nhiều phƣơng pháp hoạch định đƣờng đi cho robot tự hành đã đƣợc triển khai nhƣ: phƣơng pháp trƣờng thế năng (Potential Field), phƣơng pháp bản đồ đƣờng (Road Map), phƣơng pháp thuật toán di truyền (Genetic Algorithms),…nhƣng có khuyết điểm các phƣơng pháp trên là bị bẫy cực tiểu cục bộ (phƣơng pháp trƣờng thế năng), do đó đề tài sử dụng phƣơng pháp hoạch trƣờng thế năng kết hợp giữa thuật toán tìm đƣờng đi D* cho kết quả tránh đƣợc bẫy cực tiểu cục bộ.
Trong các phƣơng pháp trên thì robot cần biết truớc vị trí ban đầu, vậy vấn đề đặt ra là rôbot chƣa biết vị trí thì làm thế nào ? Với đề tài của Ths Lâm Văn Vũ đã nghiên cứu đƣợc robot tự hành sử dụng cảm biến sonar [1], nhƣng robot tự hành thì chúng ta phải khai báo tọa độ ban đầu, vậy làm thế nào robot đến đích nếu không biết tọa độ ban đầu ? Do đó vấn đề định vị đựơc đƣa ra, trong quá trình hoạt động, các cảm biến của robot sẽ bị ảnh hƣởng bởi nhiễu từ môi trƣờng bên ngoài lẫn bên trong cơ cấu chấp hành của nó. Điều này có nghĩa là thông tin nhận đƣợc từ cảm biến không còn chính xác và có thể làm cho robot không đến đƣợc mục tiêu đã đề ra. Do đó, robot phải thực hiện việc định vị liên tục trong quá trình di chuyển để xác định đúng vị trí của nó trong môi trƣờng và đƣa ra sự điều chỉnh hợp lý nhằm đạt kết quả mong muốn. Đề tài chọn phƣơng pháp định vị Monte Carlo (MCL – Monte Carlo Localization) bởi tính đơn giản và hiệu quả của nó khi thực hiện.
MCL có khả năng định vị tốt ngay cả khi robot không đƣợc cho biết trƣớc vị trí ban đầu. Khi thực hiện, robot cần đƣợc trang bị một hệ thống cảm biến (thƣờng là cảm biến đo khoảng cách và hành trình). Các thuật toán trong đề tài đƣợc viết bằng ngôn ngữ C++ và mô phỏng trên phần mềm Player/Stage. Kết quả mô phỏng cho thấy các thuật toán hoạt động rất tốt.
Robot có thể đến đƣợc điểm mục tiêu cho trƣớc ngay cả khi không đƣợc cho biết trƣớc vị trí ban đầu. ix ABSTRACT Autonomous robot is one of the important problems of the robot to find a path from start point to end point without colliding with obstacles through data from the sensor. There are many methods of path planning for autonomous robot has been implemented , such as the potential method ( Potential Field ), the road map method ( Road Map), genetic algorithm methods ( Genetic Algorithms ), cons. but there are methods that are trapped in local minima ( potential field method ), so that this thesis was planning to use the potential method to combine D* search path algorithm for results to avoid local minima traps.
In the above methods, the robot need to know the initial coordinate, so the question is how is the robotic location unknown? With the thesis of Van Vu Lam MA has studied the autonomous robot using sonar sensors [ 1 ], but autonomous robot, we must declare the original coordinates, so how robots going to the goal without knowing the initial coordinate? Therefore the localization problem is made, in the course of operation; the sensor of the robot will be affected by noise from the outside and inside environment of actuator. This means that the information received from the sensor is no longer accurate and can make the robot does not reach the set goals. Therefore, the localization of robot must perform continuous in the process of moving to define its place in the environment and make reasonable adjustments to achieve the desired results. This thesis chosen for the Monte Carlo method (MCL - Monte Carlo Localization) for its simplicity and its effectiveness when implemented.
MCL has a good ability to localize even when the robot is not known in advance to its initial position. When performing, the robot should be equipped with a sensor system (usually sensors measure the distance and journey). The algorithm in this thesis is written in C++ and Player/Stage simulation software. The simulation results show that the algorithm works very well.
Robots can reach a given target point even it didn’t know the initial coordinate. x MỤC LỤC LÝ LỊCH KHOA HỌC. i LỜI CAM ĐOAN. iii LỜI CẢM TẠ.
iv NHẬN XÉT CỦA GIÁO VIÊN HƢỚNG DẪN. v NHẬN XÉT CỦA CHỦ NHIỆM NGÀNH. vi NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN .vii NHẬN XÉT CỦA HỘI ĐỒNG BẢO VỆ LUẬN VĂN. ix DANH SÁCH CÁC HÌNH.
xiii DANH SÁCH CÁC BẢNG. xv Chƣơng 1 Giới Thiệu .2 Mục tiêu và giới hạn đề tài .3 Nội dung đề tài. 4 Chƣơng 2 Cơ Sở Lý Thuyết .1 Cảm biến laser đo khoảng cách .2 Mô tả mô hình toán học của một số robot di động .3 Vấn đề định vị cho robot tự hành .1 Bài toán định vị .2 Phân bố Gauss và Bộ lọc Bayes .3 Các mô hình của bộ lọc Bayes .4 Các phƣơng pháp đinh vị xác suất. 23 Chƣơng 3 Lặp kế hoạch đƣờng đi và Ứng dụng của MCL trong robot tự hành33 xi 3.1 Lập kế hoạch đƣờng đi .3 Phƣơng Pháp Tránh vật cản bằng Trƣờng Thế Năng (Potential Field) .2 Ứng dụng của MCL trong robot tự hành.1 Thuật toán MCL.2 Mô hình vận động của robot .3 Mô hình cảm biến của robot .4 Ứng dụng phƣơng pháp MCL trong điều khiển robot tự hành.
50 Chƣơng 4 Xây dựng mô hình và phân tích mô phỏng thiết kế .1 Phần mềm mô phỏng robot Player/Stage. Đặc điểm của Player. Đặc điểm của Stage.2 Kết quả mô phỏng trên phần mềm Player/Stage. Mô phỏng đƣờng đi của robot dùng phƣơng pháp PF (Potential field).
Mô phỏng đƣờng đi của robot dùng phƣơng pháp PF kết hợp với D*. Mô phỏng đƣờng đi của robot dùng phƣơng pháp MCL kết hợp PF & D*60 Chƣơng 5 .1 Kết quả đã nghiên cứu .2 Kết luận và hƣớng phát triển của đề tài .2 Hƣớng phát triển của đề tài. 65 Tài Liệu Tham Khảo. 66 xii DANH SÁCH CÁC HÌNH Hình 1.1 Một số loại robot tự hành.
1 Tạo mặt phẳng cắt ngang tại laser bằng gương quay trong cảm biến đo laser 2D. 2 Mặt phẳng tia laser với góc quét β. 3 Dữ liệu được thu thập của laser. 4 Cấu trúc robot 2 bánh.
5 Cấu trúc robot với điều kiện ràng buộc nonholonomic trong hệ tọa độ toàn cục. 6 Định vị dùng các cột mốc và một bộ quét laser onboard. Phân bố Gauss. Các phân bố mật độ trong mô hình cảm biến.
Mô hình mật độ đặc trưng của phân bố p ztk | xt , m . Sơ đồ phương pháp định vị lọc Kalman. Minh họa kết quả thuật toán định vị lọc Particle. Mô tả bản đồ và đường đi của thuật toánt A*.
Khoảng cách giữa các ô lưới. Mô tả bản đồ và đường đi của thuật toán D*. 4 Phương pháp tránh vật cản trường thế năng. 5 Mô hình một bước di chuyển của robot.
Lấy mẫu từ mô hình vận động. Lưu đồ thuật toán điều khiển robot với vị trí ban đầu không biết trước. Mô hình Client/Sever của Player. Kết nối giữa Player/Stage và Robot.
Mô hình robot và vật cản trên phần mềm Player/Stage. 4 Đường đi của robot sử dụng phương pháp PF đến được mục tiêu. 5 Robot tiếp cận mục tiêu với môi trường phức tạp hơn. 6 Robot không thể đến đích vì vật cản phức tạp.
7 Robot đã đến đích với vật cản phức tạp. 8 Robot di chuyển ngẫu nhiên trong môi trường. 9 Robot di chuyển bằng phương pháp D* & trường thế năng. 10 Robot đã đến đúng điểm mục tiêu đặt ra ban đầu.
63 xiv DANH SÁCH CÁC BẢNG Bảng 3. 1 Thuật toán MCL. 2 Thuật toán mô hình vận động của robot tự hành. 3 Thuật toán cho hàm sample(b).
4 Thuật toán cho mô hình cảm biến. 50 xv Chƣơng 1 Giới Thiệu 1.1 Tổng quan Trong những năm sắp tới đây mỗi ngƣời sẽ có nhu cầu sử dụng một robot cá nhân nhƣ cần một máy tính PC hiện nay và robot sẽ là tâm điểm của một cuộc cách mạng công nghệ lớn sau Internet. Cùng với sự phát triển của ngành cơ điện tử robot tự hành ngày càng đƣợc hoàn thiện hơn, đƣợc ứng dụng nhiều trong các ngành công nghiệp, thƣơng mại, y tế, khoa học, …và mang lại nhiều lợi ích cho đời sống xã hội, thay thế dần sức lao động của con ngƣời trong những điều kiện môi trƣờng độc hại nguy hiểm, tăng nhanh năng suất lao động…đặc biệt nó góp phần tích cực vào quá trình công nghiệp hóa hiện đại hóa nƣớc ta nói riêng và thế giới nói chung.