Thiết kế giải thuật điều khiển cho robot tìm đường trong mê cung

Nội dung text: Thiết kế giải thuật điều khiển cho robot tìm đường trong mê cung

1. THIẾT KẾ GIẢI THUẬT ĐIỀU KHIỂN CHO ROBOT TÌM ĐƯỜNG TRONG MÊ CUNG Nguyễn Văn Thành Danh Viện Kỹ thuật HUTECH, Trường Đại học Công nghệ TP. Hồ Chí Minh GVHD: ThS. Lê Tấn Sang TÓM TẮT Nếu như hệ thống robotics là xương sống của cuộc cách mạng công nghiệp, thì robot di động được xem là xu hướng trong nghiên cứu các hệ thống robotics. Trong đó, bài toán tìm đường trong mê cung là một ứng dụng phổ biến của robot di động. Đây vừa là chủ đề học tập tại nhiều trường đại học, vừa là đề tài tại nhiều cuộc thi trong và ngoài nước. Từ đó, chúng tôi hướng tới việc nghiên cứu giải thuật điều khiển cho robot tìm đường trong mê cung. Giải thuật Flood Fill được xem xét, cải tiến và tiến hành mô phỏng để đánh giá. Từ khóa: điều khiển, điều hướng, hoạch định đường đi, mê cung, robot di động. 1 GIỚI THIỆU Trong nền sản xuất công nghiệp, các hệ thống Robot luôn giữ vai trò quan trọng và chủ chốt. Với những tay máy có khả năng làm việc với tốc độ cao, chính xác và liên tục, làm năng suất lao động tăng nhiều lần. Chúng có thể làm việc trong các môi trường độc hại như hàn, phun sơn, các nhà máy hạt nhân, hay lắp ráp các linh kiện điện tử tạo ra điện thoại, máy tính, một công việc đòi hỏi sự tỉ mỉ, chính xác cao. Tuy nhiên những robot này có một hạn chế chung đó là hạn chế về không gian làm việc. Không gian làm việc của chúng bị giới hạn bởi số bậc tự do tay máy và vị trí gắn chúng. Từ đó, các dạng Robot di động (RBDĐ) ra đời, mang lại khả năng hoạt động linh hoạt trong các môi trường khác nhau. Chúng có khả năng di chuyển độc lập, thực thi nhiệm vụ một cách hoàn toàn tự động. Với những cảm biến, chúng có khả năng nhận biết về môi trường xung quanh, xác định vị trí của bản thân. Ngày nay, Robot di động được ứng dụng rộng rãi trong các ngành công nghiệp, thương mại, y tế, các ứng dụng khoa học và phục vụ đời sống của con người. Dựa vào kết cấu truyền động, RBDĐ được chia làm ba dạng chính [1]. Thứ nhất, Robot hoạt động dưới nước dùng các dạng động cơ đẩy có gắn cánh quạt, giúp chúng có khả năng lặn, nổi, tiến, lùi, quay vòng trong môi trường nước. Điển hình là ROV (Remotely operated vehicle) và AUV (Autonomous underwater vehicle). Thứ hai, Robot bay trên không trung, phổ biến là máy bay trực thăng (Quadcopter). Thứ ba là các dạng RBDĐ di chuyển trên mặt đất, có thể dùng chân để đi lại hoặc dùng bánh xe. Trong các dạng trên, RBDĐ sử dụng 126
2. bánh xe được chọn để nghiên cứu về ứng dụng tìm đường trong mê cung. Bởi vì khả năng di chuyển nhanh, ổn định và môi trường bằng phẳng phù hợp cho chuyển động của bánh xe. Liên quan đến RBDĐ, có nhiều chủ đề được quan tâm như thiết kế kết cấu, định vị tọa độ, nhận dạng môi trường hoạt động, điều khiển chuyển động dẫn đường cho robot, tránh vật cản, [2] Bên cạnh đó, một số hướng mới có thể kể đến như xây dựng khả năng nhận thức hay trí thông minh cho robot [3]. Tìm đường trong mê cung được xem là một ứng dụng thực tế làm nổi bật ưu điểm của robot di động so với các dạng robot khác là khả năng khám phá không gian hoạt động. Đề tài vừa là đối tượng học tập tại nhiều trường đại học, vừa là bài toán cho nhiều cuộc thi trong và ngoài nước. Bài toán thoạt nhìn đơn giản với trí tuệ con người, nhưng với robot lại mang lại nhiều khó khăn và thách thức. Robot phải cảm nhận được xung quanh để tránh vật cản, phải ghi nhớ lại đường đi, phải di chuyển hợp lý để khỏi lạc trong mê cung. Từ đó, giải thuật tìm đường trong mê cung cũng nhận được nhiều sự quan tâm từ các nhà nghiên cứu. Thuật toán bám tường [4] là một quy tắc nổi tiếng nhất để vượt qua mê cung, còn được gọi là quy tắc tay trái hoặc quy tắc tay phải. Nếu là mê cung đơn kết nối nghĩa là tất cả các bức tường của nó được kết nối với nhau hoặc kết nối với đường bao quanh mê cung, thì bằng cách dò một tay lên một bức tường của mê cung, người đi đảm bảo không bị lạc và tìm được lối ra nếu có một lối ra trên đường bao. Hoặc nếu không có lối ra thì sẽ quay trở lại lối vào và sẽ đi qua tất cả các đường của mê cung ít nhất một lần. Ưu điểm của giải thuật này là đơn giản, nhưng tốn nhiều thời gian để thoát khỏi mê cung. Để khám phá mê cung hiệu quả hơn, giải thuật Flood Fill được giới thiệu [5]. Bằng việc tạo trước một mảng dữ liệu thể hiện độ ưu tiên từ điểm xuất phát đến điểm đích. Robot lúc này sẽ như một dòng chảy luôn ưu tiên chảy về vùng trũng hay đích đến. Trên nền tảng Flood Fill, hàng loạt cải tiến đã được ra đời để giảm thời gian thực hiện [6], [7]. Trên cơ sở đó, chúng tôi lựa chọn chủ đề robot tìm đường trong mê cung và các cải tiến của giải thuật Flood Fill làm chủ đề nghiên cứu. Bài tham luận được chia làm 5 phần. Phần 1 đưa ra giới thiệu về RBDĐ, các vấn đề nghiên cứu liên quan, ứng dụng tìm đường trong mê cung và giải thuật Flood Fill. Phần 2 mô tả về đối tượng nghiên cứu là robot sử dụng bánh xe truyền động. Phần 3 trình bày về giải thuật sử dụng. Phần 4 đưa ra các mô phỏng và hình ảnh mô hình thực tế. Cuối cùng là phần kết luận và hướng phát triển. 2 ROBOT DI ĐỘNG 2.1 Phương pháp dẫn đường Để robot có khả năng di chuyển linh hoạt trong mê cung, kết cấu Robot 3 bánh như Hình 1 được lựa chọn và thiết kế. Trục của hai bánh chủ động đặt ở phía sau, phía trước được lắp một bánh đa hướng. Hai cảm biến siêu âm lắp hai bên để đo khoảng cách với tường, từ đó suy ra được khoảng cách tương đối giữa trục xe với đường tâm của lối đi. 127
3. Hình 1. Sơ đồ nguyên lý robot Do robot di chuyển trên đường đi, có thành (vách) dựng ở hai bên (Hình 2). Nên để đi thẳng, robot chỉ cần bám theo đường chính giữa hay đường đối xứng của hai thành. Chúng ta có thể gọi là bám theo đường line ảo. Từ việc tính toán được vị trí của xe so với đường line ảo này nhờ cảm biến, giải thuật bám line sẽ trình bày ở mục 3.1 được áp dụng để dẫn hướng cho robot đi thẳng. a b e Hình 2. Vị trí tương đối giữa xe và trục chính giữa đường đi ba e (1) 2 2.2 Động học Mô hình xe được biểu diễn trên Hình 3. Nó bao gồm 2 bánh chủ động lắp trên cùng một trục và 1 bánh đa hướng. Chuyển động của robot được tạo bởi 2 động cơ độc lập cung cấp moment cho 2 bánh chủ động. Điểm M là trung điểm của hai bánh chủ động. Điểm tracking là . R là điểm tham chiếu bám line cho robot. 128
4. Phương trình động học tại điểm M: xM cos 0 v y sin 0 (2) M   0 1 Trong đó v và  là vận tốc dài và vận tốc góc của xe. Phương trình động học tại điểm C: xc xM d sin  yC yM d cos  (3) C  Với d là khoảng cách từ M đến C. Phương trình động học tại R: xR vr cos R yR vR sin R (4) R R Trong đó vR là vận tốc mong muốn của xe tại điểm tham chiếu. y e3 R yR e1 e2 yC C M yM x O xM xR xC Hình 3. Mô hình động học bám line của xe 3 GIẢI THUẬT ĐIỀU KHIỂN 3.1 Giải thuật bám đường dẫn Sai số của xe so với điểm tham chiếu được xác định như sau: e1 cos sin 0 xR xC e sin cos 0 y y (5) 2 R C e3 0 0 1 R C 129
5. Để đơn giản quá trình điều khiển, ta giả sử xe sẽ chạy với vận tốc bằng vận tốc tham chiếu, nên có e1 0 . Bên cạnh đó, do mê cung có đường đi dạng thẳng, nên hướng của xe thường không thay đổi nhiều, nên có thể cho e3 0. Như vậy, quá trình điều khiển điểm tracking đến điểm tham chiếu chỉ còn đầu vào là sai số e2 . Và trên thực tế, được xác định trực tiếp từ hệ thống cảm biến. Áp dụng giải thuật PD để đưa sai số về không, có được: v v R (6) de2  K pe2 Kd dt 3.2 Giải thuật tìm đường trong mê cung Giải thuật Flood Fill Đối với bài toán giải mê cung, trong đó robot phải tìm được điểm trung tâm nhanh nhất thì Flood Fill được sử dụng nhiều và dễ dàng nhúng trên các bộ điều khiển. Giải thuật được mô tả thông qua các bước ở Hình 4. Đầu tiên, mê cung được đánh trọng số thay đổi từ điểm xuất phát cho đến điểm đích. Robot bắt đầu di chuyển tại góc dưới bên trái, lúc này robot phát hiện có vách tường bên phải, nên quyết định đi thẳng đến ô liền kề có trọng số thấp hơn (Hình 4a). Robot tiếp tục di chuyển đến ô có trọng số thấp hơn phía trên và phát hiện có vách tường bên phải (Hình 4b). Nhận thấy, 2 ô liền kề đều có trọng số lớn hơn, nên phải điều chỉnh trọng số tại ô hiện tại lớn hơn ô liền kề (Hình 4c). Tiếp tục di chuyển đến ô liền kề có trọng số thấp hơn và cập nhật trọng số. Quá trình được thực hiện lặp đi lặp lại đến khi di chuyển đến điểm đích (Hình 4d, 4e, 4f). a) b) c) d) e) f) Hình 4. Các bước giải thuật Flood Fill 130
6. Cải tiến Để tăng tốc độ tìm kiếm, ta có thể thêm 2 hiệu chỉnh sau. Thứ nhất là nhận biết vị trí ngõ cụt, tại các ô này sẽ được đánh trọng số rất lớn để robot không cần di chuyển tới nữa. Thứ hai, giữ nguyên độ chênh lệch trọng số ban đầu giữa các ô liền kề không có vách ngăn. Bởi vì, độ chênh lệch trọng số ban đầu là độ chênh lệch tối thiểu từ vị trí xuất phát đến vị trí đích và luôn tuân theo quy luật này. 4 MÔ PHỎNG Giải thuật Flood Fill và một số cải tiến được mô phỏng trên Matlab cho ứng dụng tìm đường trong mê cung. Mê cung sử dụng có dạng 16x16 ô. Thời gian di chuyển giữa 2 ô liền kề là 2 giây, không xét thời gian chuyển hướng. Kết quả đạt được là robot sẽ tìm được vị trí của điểm trung tâm, nhưng thời gian của Flood Fill cải tiến nhanh hơn nhiều so với giải thuật Flood Fill cơ bản (Hình 5). Giải thuật cải tiến có thời gian thực hiện nhanh hơn, do không cần phải đi lại các ngõ cụt và việc cập nhật các trọng số hiệu quả hơn. a) Flood Fill b) Flood Fill cải tiến Hình 5. Giải thuật tìm đường trong mê cung 5. KẾT LUẬN Bài tham luận đã đưa ra giải thuật tìm đường trong mê cung cho robot di động. Giải thuật dựa trên nền Flood Fill kết hợp với một số cải tiến. Giải thuật được mô phỏng và so sánh. Từ đó, nhận thấy ưu điểm là giảm đáng kể thời gian giải mê cung. Bên cạnh đó, bài tham luận cũng đưa ra các mô hình động học cho robot bám line và cách dẫn đường cho robot. Tác giả sẽ tiếp tục hoàn thiện mô hình thực tế để chạy thực nghiệm, so sánh với kết quả mô phỏng. Từ đó, tiếp tục đề xuất các cải tiến để đạt hiệu quả hơn. 131
7. TÀI LIỆU THAM KHẢO [1] M. Russo and M. Ceccarelli, “A Survey on Mechanical Solutions for Hybrid Mobile Robots,” Robotics, vol. 9, no. 2, p. 32, May 2020. [2] Iris F.A. Vis, “Survey of research in the design and control of automated guided vehicle systems,” European Journal of Operational Research, vol. 170, no. 3, pp. 677-709, 2006. [3] S. Primatesta, L. O. Russo and B. Bona, "Dynamic trajectory planning for mobile robot navigation in crowded environments," 2016 IEEE 21st International Conference on Emerging Technologies and Factory Automation (ETFA), Berlin, Germany, 2016, pp. 1-8. [4] P. van Turennout, G. Honderd and L. J. van Schelven, "Wall-following control of a mobile robot," Proceedings 1992 IEEE International Conference on Robotics and Automation, Nice, France, 1992, pp. 280-285 vol.1. [5] Elshamarka, Ibrahim and A. B. Saman. “Design and Implementation of a Robot for Maze-Solving using Flood-Fill Algorithm.” International Journal of Computer Applications , 2012, pp. 8-13. [6] Tjiharjadi, Semuil. “Design and Implementation of Flood Fill and Pledge Algorithm for Maze Robot.” Computer Science, 2019. [7] Tjiharjadi, S., Wijaya, M., & Setiawan, E, “Optimization Maze Robot Using A* and Flood Fill Algorithm.”, International Journal of Mechanical Engineering and Robotics Research, 2017. 132