Chương 1 TỔNG QUAN 1.1 Giới thiệu Trong những năm gần đây với sự phát triển vượt bậc của ngành khoa học máy tính và điều khiển học đã giúp ngành robotics ngày càng phát triển mạnh mẽ, đặc biệt là lĩnh vực robot tự hành (mobile robot). Theo dự đoán của các chuyên gia trong tương lai không xa 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 hiện nay và robot di động sẽ là tâm điểm của một cuộc cách mạng công nghệ lớn sau Internet. Có thể kể đến một số loại robot được quan tâm nhiều trong thời gian qua là: Tay máy robot, Robot di động (Mobile Robots), Robot phỏng sinh học, Robot cá nhân,… Xu thế phát triển robot hiện nay tập trung nhiều về robot di động vì những ưu điểm nổi bật và tính năng đa dạng ứng dụng của nó. Do nhu cầu dịch vụ xã hội ngày càng phát triển cao nên đòi hỏi hệ thống robot di động phải đủ thông minh để đáp ứng các yêu cầu đặt ra, tùy theo nhu cầu, mục đích sử dụng và chọn loại robot thích hợp.
Thông thường lĩnh vực robot di động được các nhà khoa học chia ra làm 3 loại chính đó là: Xe tự hành trên mặt đất - AGV, Robot tự hành dưới nước - AUV, Máy bay không người lái - UAV. Thông thường bài toán về điều khiển robot di động phải thỏa mãn 3 câu hỏi mà Leonard và Durant Whyte [1991] tóm tắt đưa ra là : “robot đang ở đâu ?”, “robot sẽ đi tới đâu ?”, “robot sẽ đi tới đó như thế nào ?”. Để trả lời cho 3 câu hỏi này robot phải: có một mô hình môi trường (đã cho hoặc tự xây dựng); nhận biết và phân tích môi trường; tìm vị trí của nó trong môi trường; lập kế hoạch và điều khiển chuyển động. Trong lĩnh vực này, các nhà nghiên cứu thường quan tâm nhiều về các bài toán quỹ đạo di chuyển cho robot, giúp robot tránh các vật cản trên đường đi và đến đích an toàn với chi phi thấp nhất có thể.
Do vậy, bài toán về thiết kế và tối ưu quỹ đạo cho robot di động được quan tâm nhiều trong thời gian qua. Một số hình ảnh cho thấy sự phát triển 1 các loại robot di động thông minh liên quan tới các bài toán hoạch định quỹ đạo khi di chuyển.1: hình (a) robot lau nhà hãng iRobot; hình (b) xe lăn thông minh Hình 1.2: Lĩnh vực máy bay không người lái trong quân sự Hình 1.3: Lĩnh vực Robot tự hành dưới nước 2 1.2 Sơ lược các phương pháp hoạch định quỹ đạo Trong luận văn tác giả tiếp cận loại robot di động tự hành bằng bánh xe. Có rất nhiều bài toán và thuật toán được đưa ra cho robot tự hành bằng bánh xe nhưng vẫn chưa hoàn thiện và vẫn còn đang được phát triển. Một trong số các bài toán được các nhà nghiên cứu quan tâm nhiều cho lĩnh vực này là bài toán hoạch định quỹ đạo đường đi tối ưu cho robot di động, nhằm mục đích cuối cùng đưa robot đến vị trí mong muốn an toàn, tránh vật cản trên đường đi, đường quỹ đạo di chuyển đủ trơn để robot di chuyển ít bị dao động, tránh các bẫy cục bộ do vật cản gây ra,.
Khái niệm về bài toán hoạch định quỹ đạo: Quy hoạch quỹ đạo là di chuyển từ điểm A tới điểm B, đồng thời tránh vật cản theo thời gian. Điều này có thề được tính toán bằng phương pháp rời rạc hoặc liên tục. Quy hoạch quỹ đạo là lĩnh vực quan trọng trong robot và nó đóng vai trò rất lớn trong việc tự động hóa phương tiện di chuyển. Có 2 thuật ngữ cơ bản: Quy hoạch đường đi: đưa ra quỹ đạo hay đường đi, tránh vật cản mà không phụ thuộc vào thời gian, nghĩa là không cần xác định thời gian robot di chuyển từ điểm A tới điểm B.
Quy hoạch quỹ đạo: đưa ra quỹ đạo hay đường đi, tránh vật cản đi từ A đến B trong một thời gian nhất định. Về cơ bản, quy hoạch quỹ đạo là quy hoạch đường dẫn bên cạnh việc lập kế hoạch di chuyển dựa trên các yếu tố vận tốc, chuyển động và các đặc tính động học của robot. Nghĩa là xác định một quỹ đạo đường đi để cho robot di chuyển đến vị trí mục tiêu đã định mà không va chạm vật cản trong vùng làm việc. Việc lập kế hoạch đường đi trước hết là phải đưa ra một bản đồ và vị trí mục tiêu, sau đó là một chiến lược để giải quyết bài toán robot phải quyết định làm gì để đạt được mục tiêu.
Sơ lược các phương pháp giải quyết các bài toán hoạch định quỹ đạo cho robot tự hành bằng bánh xe như sau: 1.1 Phương pháp trường thế năng (Potential Field) 3 Hình 1.4: Quỹ đạo được hoạch định theo phương pháp trường thế năng Phương pháp trường thế năng xem robot như một điểm di chuyển trong một trường thế năng do mục tiêu và các vật cản trong môi trường tạo ra. Mục tiêu thì tạo ra thế hút còn các vật cản tạo ra thế đẩy. Robot ở trong trường thế năng là đối tượng chịu tác động của lực hút từ gradient của thế hút để đưa robot đến mục tiêu, đồng thời chịu tác động của lực đẩy từ gradient của thế đẩy để giữ cho robot tránh va chạm với vật cản. Vector lực tổng hợp bao gồm tổng của vector lực hút và vector lực đẩy đóng vai trò như lực gia tốc làm cho robot di chuyển tới vị trí mới và giải thuật được lặp lại đến khi robot đến mục tiêu.
Phương pháp trường thế năng đơn giản và dễ thực hiện đối với các môi trường có vật cản đơn giản hoặc khoảng cách giữa điểm bắt đầu và mục tiêu ngắn, đối với khoảng cách xa, vật cản phức tạp thì phương pháp này dễ rơi vào bẫy cực tiểu cục bộ. Để khắc phục được nhược điểm của phương pháp này người ta thường kết hợp với phương pháp hoạch định phân tách sơ đồ Voronoi. Tất nhiên, đường tìm được trong Vonoroid thường xa hơn so với đường tối ưu về tổng độ dài. Sơ đồ Voronoid có một hạn chế là sự giới hạn về khoảng cách của cảm biến vị trí.
Vì thuật toán tìm đường đi chọn khoảng cách tối 4 đa giữa robot và vật cản trong môi trường nên các cảm biến có tầm hoạt động ngắn của robot sẽ sai khi cảm nhận về môi trường xung quanh. Tuy nhiên, một lợi điểm quan trọng của phương pháp Voronoid diagram so với hầu hết các kỹ thuật tránh vật cản khác là khả năng thực thi. Cho một kế hoạch đường đi đã được lập bằng phương pháp Voronoid diagram, một robot với các cảm biến khoảng cách như laser hoặc siêu âm, có thể đi theo đường Voronoid trong môi trường thực bằng cách sử dụng thuật toán đơn giản của Voronoid diagram: robot làm tăng tối đa các giá trị cực tiểu cục bộ mà cảm biến của nó đọc được. Hệ thống điều khiển này sẽ giữ cho robot đi đúng trên đường Voronoid, điều này sẽ giảm thiểu khả năng sai sót.5: Quỹ đạo hoạch định khi kết hợp sơ đồ Voronoi và trường thế năng 1.2 Phương pháp bảng đồ đường (Road Map) 5 Phương pháp Road Map kết nối các vùng không gian trống của robot trong một mạng lưới các đường thẳng hoặc đường cong 1D gọi là các bản đồ đường đi.
Có hai phương pháp Road Map được chấp nhận với những kiểu đường đi thay đổi đột ngột: đồ thị trực quan (visibility graph) và biểu đồ Voronoi (Voronoi diagram). + Phương pháp đồ thị trực quan (visibility graph) thì cho các đường đi sẽ bám sát theo vật cản và đường đi cuối cùng là kết quả có độ dài ngắn nhất. + Phương pháp biểu đồ Voronoi thì các đoạn đường càng cách xa vật cản càng tốt.3 Phương pháp Q-learning Q-learning là phương pháp học tăng cường rất hiệu quả cho bài toán tìm đường, do phương pháp này thực hiện theo kiểu off-policy. Vì vậy phương pháp này được kết hợp với các phương pháp khác để giải quyết một số bài toán đặc biệt như tìm đường đi trong mạng (Q routing) hay tìm đường của hệ thống multi-agent (Ant-Q).
Và một số công trình trong nước đã áp dụng thành công phương pháp này để giải quyết một số bài toán tìm đường cụ thể [13]. Phương pháp này cũng có thể được coi là thuộc nhóm phương pháp hoạch định dựa vào lưới tọa độ. Trước đây, người ta giải quyết các bài toán tìm đường bằng các giải thuật tìm đường cổ điển. Tuy nhiên các thuật toán tìm đường có rất nhiều hạn chế, ví dụ như đòi hỏi môi 6 trường phải xác định, cố định và không xử lý tốt nhiều tình huống thực tế.
Ngày nay con người ứng dụng trí tuệ nhân tạo, cùng với sự hỗ trợ của máy tính robot có thể tự tìm ra quy luật hành động nói chung, tìm đường đi nói riêng thông qua các kinh nghiệm thu được từ những hành động thực hiện trước đó; hay còn gọi là học tăng cường. Có nhiều phương pháp học tăng cường khác nhau, trong đó Q-learning được áp dụng khá phổ biến ở nước ta trong việc giải quyết bài toán tìm đường đi. Một trong các ứng dụng thực tế của phương pháp này hoạch định quỹ đạo dùng cho các robot lau nhà.4 Phương pháp thuật toán di truyền (Genetic Algorithms) Đây là phương pháp tìm kiếm đường đi toàn cục và tối ưu hóa ngẫu nhiên dựa trên kỹ thuật tiến hóa, thông qua ba quá trình cơ bản như: chọn lọc tự nhiên, lai ghép và đột biến. Chính vì các quá trình trên nên GA rất hiệu quả trong việc giải quyết các bài toán tìm cực trị của hàm phi tuyến.
Giải thuật di truyền dùng để tìm đường đi tối ưu cho robot tự hành di chuyển trong môi trường tĩnh, được miêu tả bởi bản đồ với các điểm nút và các đường nối [4], thuộc nhóm hoạch định đường đi dựa vào việc lấy mẫu. Vị trí của mục tiêu và vật cản phục vụ cho việc tìm đường đi tối ưu cho robot, được cung cấp trong không gian làm việc 2 chiều. Số gien trong một nhiễm sắc thể là đặc trưng số vật cản trên bản đồ. Và từ đó hiệu chỉnh lại độ dài của nhiễm sắc thể.
Tiêu chuẩn đánh giá đường đi tối ưu là đường có độ dài ngắn nhất.7: Hoạch định đường đi cho robot dùng thuật toán GA 7 Hình 1.8: Không gian làm việc (Workspace Map) Theo [10] kết quả đưa ra sau khi tính toán là: { 0-4-6-6-7-9-15-15}. Cũng sử dụng công cụ là giải thuật di truyền nhưng một số công trình khác lại giải bài toán hoạch định đường đi cho robot theo phương pháp lưới tọa độ [4]. Và cho kết quả rất khả quan Hình 1.