Hoạch định quỹ đạo cho robot di động dùng thuật toán PSO

Nội dung text: Hoạch định quỹ đạo cho robot di động dùng thuật toán PSO

1. HOẠCH ĐỊNH QUỸ ĐẠO CHO ROBOT DI ĐỘNG DÙNG THUẬT TOÁN PSO PLANNING FOR MOBILE ROBOT USING PSO ALGORITHM TS. Ngô Văn Thuyên, Lâm Văn Vũ Trường Đại học Sư phạm Kỹ thuật Tp. HCM TÓM TẮT Lập kế hoạch đường đi là bài toán nghiên cứu quan trọng trong lĩnh vực robot tự hành. Bài báo này trình bày một phương pháp để điều khiển robot di chuyển từ vị trí ban đầu trong môi trường đến đúng mục tiêu đặt ra. Đầu tiên một bản đồ được xây dựng để diễn tả không gian làm việc cuả robot di động; sau đó thuật toán D* được sử dụng để tìm các tọa độ ngắn nhất từ điểm đầu đến điểm kết thúc;thuật toán PSO (Particle Swarm Optimization) được sử dụng để tìm vận tốc góc và vận tốc thẳng tối ưu cho robot để robot có thể di chuyển theo đường đi cho trước; cuối cùng phương pháp trường thế năng được sử dụng để tránh vật cản trên đường đi. Kết quả mô phỏng trên phần mềm Player/Stage đã cho thấy tính hiệu quả của thuật toán trong việc điều khiển robot tự hành di chuyển đến mục tiêu. ABSTRACT Path planning is an important research problem in the field of autonomous robots. This paper presents a method to control the robot to move from the initial position in the environment to the correct target. First, a map is built to describe the working space of the mobile robot; then D * algorithm is used to find the shortest coordinates from the beginning to the end; PSO algorithm is used to find the angular velocity and the optimum linear velocity for the robot so that the robot can move in a given path; final potential field method is used to avoid obstacles along the way. Software simulation results on the Player/Stage shows that the effectiveness of the control algorithm in the autonomous robot moves to the target. 1. ĐẶT VẤN ĐỀ Algorithms), thuật toán PSO Phương pháp trường thế năng đơn giản và dễ thực Lập kế hoạch đường đi [4] là một trong hiện đối với các môi trường có ít vật cản, những bài toán quang trọng về robot di hoặc vật cản đơn giản khoảng cách giữa động, nghĩa là tìm ra một đường đi tối ưu điểm đầu và mục tiêu ngắn, đối với khoảng không va chạm vật cản từ điểm bắt đầu đến cách xa, vật cản phức tạp phương pháp này điểm kết thúc. Dẫn đường có thể chia làm dễ rơi vào bẫy cực tiểu cục bộ. Phương hai loại: Dẫn đường toàn cục (global path pháp bản đồ đường đòi hỏi việc điều khiển planning) và dẫn đường cục bộ (local path robot phải thực sự chính xác, việc tìm kiếm planning), trong bài toán dẫn đường toàn đường đi tương đối chậm đối với các môi cục robot biết trước hoàn toàn hoặc biết trường rộng lớn có nhiều vật cản. Phương trước một phần thông tin về môi trường, pháp GA phức tạp hơn và nhiều tham số ngược lại trong bài toán dẫn đường cục bộ điều chỉnh hơn so với PSO. GA chưa hiệu robot chưa biết thông tin về môi trường. quả trong một số lĩnh vực như: tối ưu hàm mục tiêu, huấn luyện mạng. PSO tạm dịch Có nhiều thuật toán và phương pháp để tối ưu hóa theo bầy đàn là một kỹ thuật tối hoạch định đường đi cho robot di động như ưu hóa ngẫu nhiên dựa trên một quần thể phương pháp trường thế năng, phương pháp được giới thiệu vào năm 1995 tại hội nghị bảng đồ đường, phương pháp GA (Genetic 1
2. của IEEE bởi Dr. Eberhart và Dr. Kennedy. PSO đã được ứng dụng rất thành công trong lĩnh vực robot. PSO có nhiều sự tương tự như kỹ thuật tính toán tiến hóa trong thuật toán di truyền. Cũng giống như GA, PSO được khởi tạo với một quần thể của các giải pháp ngẫu nhiên và tìm kiếm giải pháp tối ưu bằng việc cập nhật vị trí các phần tử. Tuy nhiên, không giống như GA, PSO không có các thao tác tiến hóa như lai ghép (crossover) hay đột biến (mutation). Vì vậy mà phương pháp PSO dễ dàng hơn, ít tham số điều chỉnh hơn. Bài báo này nghiên cứu và xây dựng giải thuật hoạch định quỹ đạo đường đi cho robot di động trong môi trường toàn cục Hình 2.1. Mô phỏng thuật toán D* với vật trên cơ sở kết hợp thuật toán PSO và giải cản tĩnh và động thuật D*_PF để điều khiển mobile robot tìm được đường đi tối ưu và đồng thời tránh 2.2. Quy hoạch chuyển động cho robot di được vật cản. Thuật toán đã được mô phỏng động dùng thuật toán PSO trên phần mềm Player/Stage với nhiều bản đồ môi trường khác nhau và cho kết quả rất PSO [1] là một kỹ thuật tính toán tiến hóa tốt. dựa trên sự mô phỏng của đàn cá và đàn chim. Trong PSO, mỗi giải pháp đơn, được 2. HOẠCH ĐỊNH ĐƯỜNG ĐI ĐẾN gọi là một phần tử (particle). Mỗi phần tử MỤC TIÊU có một giá trị thích nghi (fitness value), 2.1. Thuật toán tìm đường D* được đánh giá bằng hàm đo độ thích nghi * (fitness function) và một vận tốc để định Thuật toán D [6] được sử dụng để tìm kiếm hướng bay (cách tìm kiếm) của nó. các tọa độ trên bản đồ từ vị trí của robot đến điểm mục tiêu. Giống như thuật toán Biểu thức PSO tìm đường A*, phương pháp D* cũng cho k 1 k k k k k kết quả là một đường đi tối ưu từ điểm bắt Vi V i c1 r 1 P i X i c 2 r 2 P g X i (2.1) đầu đến điểm kết thúc. Tuy nhiên, so với A* * k 11 k k thì phương pháp D có ưu điểm hơn là sử XXVi i i (2.2) dụng được trong các môi trường động. Hình k k 1 2.1 Mô phỏng thuật toán D* với vật cản tĩnh và Trong đó: X i , X i vị trí của cá thể i tại động với bản đồ 256 nút (16x16), vật cản hình vòng lặp k, k+1. V k , V k 1 vận tốc cá thể i chữ U, thuật toán D* đã tìm được đường đi i i ngắn nhất từ điểm ban đầu có tọa độ (0, -6) đến tại vòng lặp k, k+1. c1 , c2 hệ số kinh nghiệm tọa điểm mục tiêu có tọa độ (0, 7) với tổng số và xã hội của cá thể. r1 , r2 số ngẫu nhiên nút tìm được là 20 nút. k k trong khoảng 0,1. Pi , Pg vị trí tốt nhất Ghi chú: của cá thể và quần thể i cho đến vòng lặp : Vật cản chưa biết k, k+1. Lưu đồ thuật toán điều khiển : Vật cản đã biết 2
3. 2.3 vì vậy vi và i được mã hóa là vị trí của các phần tử thuật toán PSO, nghĩa là k Xvi {,} i i , iN 1 trong đó N là số phần tử. Các bước tính toán để tìm vận tốc tối ưu cho robot di chuyển: Bước 1: Khởi tạo Khởi tạo vị trí của N phần tử ngẫu nhiên k X i trong không gian tìm kiếm. chính là vị trí của cá thể i tại vòng lặp k. Giả sử số lượng được khởi tạo là 100 phần tử, điều này có nghĩa là sẽ có 100 vận tốc góc i và 100 vận tốc thẳng vi được radom ngẫu nhiên sau mỗi lần khởi tạo * Giới hạn vận tốc Vị trí của mỗi cá thể đạt được có thể nằm Hình 2.2. Lưu đồ thuật toán điều khiển ngoài môi trường giới hạn. Để các cá thể di robot. chuyển giới hạn trong không gian đặt ra thì Thuật toán PSO được sử dụng để tìm vận vận tốc của cá thể trên mỗi chiều trong PSO tốc góc và vận tốc thẳng cho robot để robot phải trượt về đến vận tốc cực đại vmax , là có thể di chuyển từ vị trí hiện tại của robot thông số đặt biệt được cài đặt bởi người sử đến điểm kế tiếp trên đường đi cho bởi D* dụng. Nếu vận tốc vượt hơn thì nó sẽ một cách tối ưu theo hàm mục tiêu cho giới hạn về . Một ý khác, vị trí hiện tại trước. Hình 2.3 Mô tả đường dẫn giữa hai điểm A và B. Một cách tổng quát để robot của cá thể có trượt về một vị trí nhất định di chuyển từ điểm A đến điểm B được tối được đánh giá là gần nhất và hợp lệ bởi giải ưu ta phải quyết đồng thời ba bài toán: pháp. Nếu không thì giải pháp này là vô Đường đi phải ngắn nhất (shortest path), nghĩa [3]. quỹ đạo đường đi phải bằng phẳng (smooth vii()() k vmax if v k v max trajectory), đường đi phải an toàn (satisfy) (2.3) v( k ) 0 if v ( k ) 0 – có nghĩa là robot không bị va chạm với ii vật cản. Điều đó có nghĩa là robot không được phép đi vượt ra khỏi biên giới hạn trong việc hình thành chuyển động mịn. Tương tự như vậy, giới hạn về vận tốc quay được cho bởi biểu thức sau: ()()k  if  k  iimax max (2.4) ii()()k max if  k  max Bước 2: Tính toán hàm mục tiêu Ứng với các vận tốc vi , i ở bước 1, vị trí Hình 2.3. Dẫn đường giữa hai điểm tiếp theo của robot được tính bởi: Khi vận tốc thẳng v và vận tốc góc  cho xi( k 1) x i ( k ) c os i ( k ) 0 vk() robot sau mỗi chu kỳ được lựa chọn hợp y( k 1) y ( k ) sin ( k ) 0 i T (2.5) i i i  ()k lý, robot di chuyển theo đường đi số 2 hình i ii(kk 1) ( ) 0 1 3
4. Trong đó: xii( k 1); y ( k 1) là tọa độ của dựa vào giá trị hàm mục tiêu hiện tại và robot thứ i tại thời gian (k+1) trong tọa độ giá trị hàm mục tiêu trước xác định vị trí xy. xii( k ); y ( k ) là tọa độ của robot thứ i tại tốt nhất đến thời điểm hiện tại đang xét thời gian k trong tọa độ xy.  là góc quay cụ thể như sau: liên quan đến trục x. Vận tốc tịnh tiến pk if() p k f X k k 1 i i i vki ()và vận tốc góc i ()k . T thời gian pi Xk if() p k f X k lấy mẫu. i i i Thuật toán PSO dựa trên việc xác định giá ppkk 11 min( ) (2.9) trị mục tiêu tương đối giữa các cá thể. Hàm gi mục tiêu là sự kết hợp giữa khoảng cách và Bước 4: Cập nhật vận tốc và vị trí góc hình thành robot. Khoảng cách hình thành robot được cho bởi: Sau khi xác định được và trong bước 2 2 1 2 3 và kết hợp với các hằng số biết trước tiến dfi (( x f x i ) ( y f y i ) ) (2.6) hành cập nhật vận tốc và vị trí theo hai biểu thức (2.1) và (2.2) Trong đó: xyff, là vị trí tối ưu nhất trong Các bước trên sẽ lặp lại cho vòng lặp tiếp theo. quần thể. 2.3. Phương pháp trường thế năng xyii, là vị trí cần đạt được. Đây chính là khoảng cách giữa vị trí tối ưu nhất trong Trong phương pháp này robot được xem một quần thể sau mỗi lần khởi tạo và vị trí như là một điểm đặt dưới tác động của cần đạt được. Góc được xác định bởi: trường thế năng tạo bởi điểm mục tiêu và các vật cản [7]. Điểm mục tiêu tác động fi  i  f (2.7) một lực hút lên robot còn vật cản tác động Trong đó:  là góc hiện tại của robot. một lực đẩy. Tổng hợp của các lực này sẽ f tác động lên robot, lúc này được xem như  là góc định hướng của robot. một điểm trong không gian, giống như một i trường thế năng nhân tạo phẳng để hướng Ở đây, góc được xác định là góc lệnh giữa robot về phía mục tiêu và tránh va chạm với góc định hướng và góc xác định vị trí hiện các vật cản trong môi trường. tại của robot. Gọi là lưc̣ hút tác động lên vị trí Giá trị hàm mục tiêu được cho là: bởi điểm mục tiêu: fdfi 12 fi  fi (2.8) (2.10) Với là hệ số lực hút, là Trong đó 12, được gọi là các trọng số. Tùy theo từng bài toán về tối ưu mà ta chọn khoảng cách Ơ-clit từ đến mục tiêu. giá trị cho thích hợp. Tương tự, gọi là lực đẩy do vật cản tác động lên vị trí : Bước 3: Tìm vị trí tốt nhất k k Tìm Pi của cá thể và Pg của quần thể. k (2.11) Vị trí Pi tốt nhất lần đầu được khởi tạo k Với là hệ số lực đẩy, là trùng với vị trí X i của từng cá thể và vị trí tốt nhất Pk của quần thể lần đầu được khởi khoảng cách Ơ -clit từ tớ i vâṭ cản , g khoảng cách ngắn nhất từ q đến vật cản và k tạo bằng với vị trí Pi . Sau khi đã tính toán là khoảng cách ảnh hưởng của vật cản. được hàm mục tiêu cho từng vị trí cá thể 4
5. Kết quả lực tổng đặt lên Hình 3.2. Biểu diễn đường đi của robot sử robot gồm lực hút và lực đẩy giúp robot dụng thuật toán PSO với các thông số tránh xa các vật cản và hướng về phía mục Hằng số C1= C2 = 1.8. Vị trí ban đầu là (- tiêu. Có thể nói, trường thế năng là phương 7, -6) và điểm mục tiêu (5, 7). Tham số lực pháp tránh vật cản đơn giản và hiệu quả cho quán tính W = 0.5. Số chiều: 2 ( vận tốc robot tự hành. thẳng và vận tốc góc). Tồng số cá thể tìm kiếm là 100 (đại diện là vận tốc thẳng và 3. KẾT QUẢ MÔ PHỎNG vận tốc góc). Ngưỡng tác động đối với vật Bản đồ [2] có kích thước 16x16m, được cản là 0.6 ta thấy so với hình 2 (sử dụng chia ra thành 289 ô có kích thước bằng phương pháp PF_D* thì đường đi của nhau là 1x1m. Trong thí nghiệm này robot robot rất mịn và tiếp cận được mục tiêu một được đặt tại vị trí ban đầu là (-7, -6) và cách an toàn. điểm mục tiêu (5, 7). Trong phương pháp D* kết hợp PF lúc này robot di chuyển sẽ dao động rất nhiều, tuy nhiên robot vẫn tìm đến mục tiêu. Hình 3.1 cho thấy mức độ dao động của robot khi vật cản trong môi trường trở nên phức tạp. Robot sẽ mất nhiều năng lượng hơn cho việc tiếp cận mục tiêu của mình. Hình 3.3. Biểu đồ vận tốc góc điều khiển robot phương pháp PF_D* Hình 3.1. Đường đi của robot sử dụng kết hợp phương pháp PF_D* Hình 3.4. Biểu đồ vận tốc góc điều khiển robot phương pháp PSO Hình 3.3 Biểu diễn đồ thị vận tốc góc điều khiển robot bằng phương pháp PF_D*. Với đồ thị này ta nhận thấy vận tốc góc lớn nhất là 1.2 (rad/s) và nhỏ nhất là -1.3 (rad/s) Robot dao động nhiều. Hình 3.4 sử dụng phương pháp PSO so với hình 3.3 ta nhận thấy biên vận tốc góc ít thay đổi hơn, robot Hình 3.2. Đường đi của robot sử dụng ít dao động hơn, vận tốc góc lớn nhất là 0.4 phương pháp PSO (rad/s) và nhỏ nhất là -0.2 (rad/s). 5
6. KẾT LUẬN tế là rất tốt. Tuy nhiên việc điều chỉnh các thông số trong mô phỏng còn tùy thuộc rất Mô phỏng đường đi của robot sử thuật toán nhiều vào điều kiện môi trường làm việc, PSO đường đi tối ưu hơn so với phương thời gian di chuyển Phần mềm pháp tìm kiếm D*_PF, đường đi mịn hơn. Player/Stage góp phần đáp ứng tốt yêu cầu Tuy nhiên phải cài đặt các thông số cho phù này, làm cơ sở cho việc thực thi trên robot hợp. Việc hoạch định đường đi cho robot di thực để áp dụng trong thực tế. động dùng thuật toán PSO, kết quả mô phỏng trên phần mềm Player/Stage cho thấy khả năng ứng dụng của đề tài vào thực TÀI LIỆU THAM KHẢO [1] Van Thuyen Ngo, Swarm-Based Planning and Control of Robotic Formations, Sydney, Australia, 2008. [2] Jennifer Owen, How to Use Player/Stage, 2010. [3] Roland Siegwart and Illah R. Nourbakhsh, Introduction to Autonomous Mobile Robots, 2004. [4] Laumond, J. P., Robot Motion Planning and Control, Springer, London, 1998. [5] Aleksandar Lazinica, Particle Swarm Optimization, ISBN 978-953-7619-48, January 2009, 476 trang. [6] Omar Ilaya and Cees Bil, A Particle Swarm Optimisation Approach to Graph Permutations, RMIT University Australia. [7]. Sacramento, C., "Potential field methods and their inherent limitations for mobile robot navigation". Robotics and Automation., IEEE International Conference on August 2002: p. 345-402. 6
7. BÀI BÁO KHOA HỌC THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ Bài báo khoa học của học viên có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn Bản tiếng Việt ©, TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH và TÁC GIẢ Bản quyền tác phẩm đã được bảo hộ bởi Luật xuất bản và Luật Sở hữu trí tuệ Việt Nam. Nghiêm cấm mọi hình thức xuất bản, sao chụp, phát tán nội dung khi chưa có sự đồng ý của tác giả và Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh. ĐỂ CÓ BÀI BÁO KHOA HỌC TỐT, CẦN CHUNG TAY BẢO VỆ TÁC QUYỀN! Thực hiện theo MTCL & KHTHMTCL Năm học 2016-2017 của Thư viện Trường Đại học Sư phạm Kỹ thuật Tp. Hồ Chí Minh.