Thuật toán tránh vật cản cho robot dựa trên cải tiến kỹ thuật Elastic Strips

Điều khiển – Cơ điện tử - Truyền thông N.M.Ngọc, P.Đ.Lâm, Đ.N.Toàn, “Thuật toán tránh vật cản Elastic Strips.” 92 THUẬT TOÁN TRÁNH VẬT CẢN CHO ROBOT DỰA TRÊN CẢI TIẾN KỸ THUẬT ELASTIC STRIPS Nông Minh Ngọc*1, Phạm Đình Lâm1, Đỗ Năng Toàn2 Tóm tắt: Bài báo trình bày về một phương pháp tránh vật cản được kế thừa và cải tiến từ phương pháp Elastic strips cho mobile robot. Thuật toán Elastic strips nguyên gốc dựa trên việc tính toán quỹ đạo di chuyển của mobile robot và cập nhật quỹ đạo mới theo thời gian thực dựa trên lý thuyết về trường lực nhân tạo (Artificial Potential Field) được đề xuất bởi O. Khatib. Mobile robot sẽ di chuyển từ vị trí ban đầu đến điểm đích được xác định trước đó, trong suốt hành trình di chuyển, dựa trên hệ thống cảm biến để phát hiện vật cản, thuật toán được áp dụng và tính toán cập nhật vị trí kế tiếp cho robot tại từng thời điểm cụ thể. Từ khóa: Collision avoidance, Avoidance obstacle, Elastic strips, Mobile robot. 1. MỞ ĐẦU Ngày nay, công nghệ robot ngày càng được áp dụng và phục vụ phổ biến trong sản xuất và trong cuộc sống hàng ngày. Robot đã có một vị trí quan trọng khó có thể thay thế được, thay thế con người trong các công việc nguy hiểm, môi trường độc hại và hơn thế nữa. Lĩnh vực robotic ngày càng chiếm được sự quan tâm của các nhà nghiên cứu khoa học, nghiên cứu xã hội, trong đó việc nghiên cứu công nghệ robot đang là một hướng nghiên cứu hoàn toàn phù hợp trong xã hội hiện đại, và công nghệ toàn cầu phát triển. Cùng với sự phát triển của công nghệ robot, các chức năng và yêu cầu về hệ thống cảm biến, các thuật toán áp dụng cho robot vượt vật cản, cảnh báo các va chạm đối với các đối tượng, môi trường hoạt động của robot đã và đang được đề ra và đòi hỏi sự chính xác nhằm đảm bảo các hoạt động của robot gần nhất, chính xác nhất đối với các hoạt động của con người trong thực tại. Bởi vậy, tránh va chạm hay cảnh báo va chạm của robot đã và đang là một trong những vấn đề quan trọng được nghiên cứu và áp dụng thành công cho các mobile robot, robot tay máy. Hầu hết mọi robot đều phải được trang bị tính năng phát hiện, xử lý và né tránh va chạm đối với các đối tượng, môi trường hoạt động của mình, hệ thống này giúp cho robot phát hiện vật cản, ngăn chặn các va chạm đáng tiếc có thể xảy ra. Để thực hiện được việc này, ngoài việc trang bị hệ thống cảm biến (quang học, laser, hình ảnh) thì việc cài đặt và thực hiện các thuật toán phát hiện và tránh va chạm là một trong những cách thức giúp cho robot lựa chọn và đưa ra các quyết định trong các tình huống được cảnh báo về va chạm trong quá trình hoạt động của mình. Trong đó, các yêu cầu về tính chính xác, tính ổn định, tính thời gian thực và đảm bảo các yêu cầu về mặt tính toán của các thuật toán này chiếm vai trò quan trọng. Trong những năm gần đây, đã có nhiều nghiên cứu về vượt vật cản theo thời gian thực được đề xuất, các nghiên cứu này tập trung vào việc phát hiện các vật cản (thông qua hệ thống cảm biến); tính toán các giá trị về khoảng cách, vị trí của vật cản; tính toán vị trí và thay đổi quỹ đạo di chuyển theo thời gian thực đảm bảo không xảy ra va chạm hay tắc nghẽn trong quá trình di chuyển. Phương pháp chia lưới xác định (Certainty grid) được đề xuất bởi P. Moravec [1], phương pháp này biểu diễn vùng hoạt động của robot bằng một mảng hai chiều các phần Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2016 93 tử hình vuông, gọi là các cell. Mỗi cell chứa một giá trị xác định (Certainty value) gọi là CV thể hiện mức độ đáng tin cậy rằng có vật cản xuất hiện trong cell đó. Giá trị của CV là khoảng cách đo hướng tâm đến vật cản gần nhất nhằm trong phạm vi hình nón được xác định thông qua hệ thống cảm biến siêu âm. Hình 1. Phương pháp chia lưới xác định. Hạn chế của phương pháp này là việc sử dụng hàm xác suất cập nhật giá trị CV của lưới xác định, đồng thời giá trị CV của các cell gần trục, gần biên sẽ không đúng với thực tế, đồng thời có nhiều vấn đề đã xảy ra trong việc tính toán khoảng cách của các vật cản dẫn đến việc giá trị sai lệch của các giá trị các định CV. Phương pháp trường lực nhân tạo-Artificial Potential Field (APF) là ý tưởng được đề xuất bởi O.Khatib [2], trong đó robot di chuyển trong một trường lực nhân tạo được tạo ra bởi các vector lực từ (lực phản, lực ngẫu nhiên, lực hấp dẫn) các vật cản và vị trí đích. APF là vector tổng hợp lực của các lực đối với vật cản (lực phản) và lực hướng đích (lực kéo). Thông qua vector tổng hợp lực này, vị trí mới của robot sẽ được tính toán và quá trình đó được lặp đi lặp lại cho đến khi robot đến được vị trí đích. Hình 2. Phương pháp Artificial Potential Field. Điều khiển – Cơ điện tử - Truyền thông N.M.Ngọc, P.Đ.Lâm, Đ.N.Toàn, “Thuật toán tránh vật cản Elastic Strips.” 94 Mở rộng đề xuất của O.Khatib về lý thuyết trường lực nhân tạo APF, một số tác giả đã phát triển nâng cấp và ứng dụng lý thuyết này nhằm giải quyết các bài toán vượt vật cản cho robot như: Krogh và Thorpe [10] cũng đã đề nghị một phương pháp kết hợp cho việc lập quỹ đạo chuyển động toàn cục hay cục bộ cho robot theo hướng tiếp cận khái quát hóa trường tiềm năng- “Generalized Potential Field”. Các cách tiếp cận trên đều có những cải tiến đáng kể, nhưng thuần túy dựa trên lý thuyết mà không được cài đặt cho robot với dữ liệu cảm biến thực sự. Bởi vậy, Brooks [8,9] và Arkin [1] đã tiến hành cài đặt phương pháp này cho một mobile robot (được trang bị một hệ thống cảm biến siêu âm xung quanh). Việc cài đặt của Brooks bằng cách xử lý, đọc từng tín hiệu của cảm biến siêu âm và tính toán các vector lực đẩy nếu có của các vật cản. Nếu như tổng hợp các vector lực đẩy đó vượt qua một ngưỡng nhất định, robot dừng lại, chuyển hướng di chuyển trùng với hướng của lực tổng hợp và di chuyển tiếp. Tác giả O. Khatib [2, 3, 11, 12] đã đề xuất một phương pháp vượt vật cản cho mobile robot đó là “Dải đàn hồi- Elastic strips”, ý tưởng đề ra đó là việc xác định robot di chuyển từ vị trí xuất phát đến điểm đích trên một quỹ đạo cố định và trong quá trình di chuyển, robot sẽ gặp các vật cản và lúc này quỹ đạo của robot được thay đổi theo lý thuyết của một dải dây đàn hồi. Khi tiếp cận với vật cản, trường lực ảo sẽ được phát sinh giữa robot và vật cản dựa trên lý thuyết về trường lực tiềm năng (Potential Field). Phương pháp Elastic strips cho thấy khả năng dẫn hướng cho mobile robot trong quá trình di chuyển ổn định và hiệu quả hơn so với phương pháp APF đã đề xuất ở trên. Các ứng dụng của Elastic strips cũng đã được cài đặt thuận lợi và dễ dàng cho hệ thống robot nhiều bậc tự do, tay máy. Sự kết hợp nhịp nhàng giữa khâu lập lịch di chuyển với khâu thực thi chuyển động của robot đã được kiểm chứng và đem lại kết quả tốt. Đồng thời, thuật toán này cũng tối ưu hóa và hỗ trợ cho mobile robot có thể di chuyển theo quỹ đạo đã được thiết kế, có khả năng vượt các vật cản trong quá trình di chuyển và đặc biệt hơn, thuật toán này phù hợp với những môi trường thực tế. 2. CẢI TIẾN PHƯƠNG PHÁP ELASTIC STRIPS 2.1. Phương pháp Elastic Strips Phương pháp Elastic strips đã được đề xuất bởi O.Khatib [4, 7, 11] với giả thiết rằng robot di chuyển trên một quỹ đạo từ điểm bắt đầu đến điểm kết thúc, trong môi trường thực tế. Khi đó: quỹ đạo di chuyển của robot sẽ được ví như dải đàn hồi. Ưu điểm của phương pháp đó là việc cài đặt dễ dàng cho robot tự hành và tay máy, tối ưu hơn cho thuật toán tránh vật cản trong hệ thời gian thực và môi trường thực tế (không xác định). Tác giả đã giả thiết rằng quỹ đạo dưới tác động của các lực hướng đích, phản lực (nếu có) từ các vật cản thì dải đàn hồi sẽ được điều chỉnh và cập nhật tại mỗi thời điểm cụ thể trong quá trình di chuyển của robot. 2.1.1. Nội lực (Internal force) Nội lực- hay nói cách khác là lực điều khiển hướng đích được ví như một trường lực ảo được tạo do điểm đích tác động lên robot nhằm kéo robot hướng về điểm đích ban đầu. Việc xác định và tính toán nội lực dựa trên công thức (1).                   111 1 1 i j i j i j i ji j i j i j ci e pppp dd d kf (1) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2016 95 Hình 3. Thành phần nội lực và ngoại lực của phương pháp Elastic Strips. Trong đó: 1ijp , 1i jp , 1i jp : trạng thái vị trí của robot tại thời điểm i-1, i, i+1, 1ijd , i jd , 1i jd : khoảng cách vị trí của robot tại thời điểm i-1, i, i+1, ck : hệ số lực của nội lực được thiết lập cho việc tính toán. Hình 4. Quỹ đạo di chuyển của robot trên cơ sở phương pháp Elastic Strips. 2.1.2. Ngoại lực (External force) Ngoại lực- được ví như là phản lực (nếu có) tạo ra từ vật cản tác động lên robot trong quá trình di chuyển khi được phát hiện bởi hệ thống cảm biến. Việc tính toán lực này được xác định thông qua công thức (2), (3) dựa trên khoảng cách ngắn nhất có thể có của các vật cản trong môi trường với robot.       otherwise ddifddK PV obssafeobssaferext 0 )( 2 1 )( min, 2 min, (2) d d ddkVf obssaferexti r )( min, (3) Trong đó: safed : khoảng cách an toàn giới hạn của robot, Điều khiển – Cơ điện tử - Truyền thông N.M.Ngọc, P.Đ.Lâm, Đ.N.Toàn, “Thuật toán tránh vật cản Elastic Strips.” 96 min,obsd : khoảng cách ngắn nhất giữa vật cản và robot, rk : hệ số lực của ngoại lực được thiết lập cho việc tính toán. Hình 5. Các thành phần xác định ngoại lực của Elastric Strips. 2.1.3. Tổng hợp lực và cập nhật quỹ đạo chuyển động Việc tổng hợp các lực (nội lực, ngoại lực) sẽ được tiến hành tại mỗi thời điểm di chuyển của robot dựa trên công thức (4).  Tziyixii i r i e i ffff fff ,,, ,, ;   (4) Đồng thời, qua đó việc cập nhật vị trí mới và quỹ đạo chuyển động của robot sẽ được mô tả trong hình 6 dựa trên việc tính toán tọa độ (x, y, z) của robot tại công thức (5), (6), góc quay của robot cũng sẽ được tính toán và cập nhật theo công thức (7). Hình 6. Mô phỏng quỹ đạo chuyển động của robot theo phương pháp Elastric Strips.                zi j curi j i yi j curi j i xi j curi j i fzzz fyyy fxxx ,, 1 ,, 1 ., 1 (5) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2016 97          j curiupdatei j curiupdatei j curiupdatei zzz yyy xxx ,, ,, ,, (6)                curiiupdatei i x y ,, 2arctan   (7) 2.2. Cải tiến phương pháp Elastic Strips 2.2.1. Đánh giá phương pháp Elastic Strips Phương pháp Elastic Strips nguyên gốc đảm bảo đầy đủ các tiêu chí cho việc cài đặt cho robot đáp ứng các đòi hỏi về độ tính toán, thời gian thực và đảm bảo tính ổn định, liên tục cho quỹ đạo của robot. Tuy nhiên, khi phân tích về phương pháp và thuật toán gốc, chúng tôi nhận thấy còn một số vấn đề cần phải cải thiện. Cụ thể: 1. Khi dựa duy nhất vào một điểm gần nhất của vật cản, phương pháp gốc không xác lập cho robot cách di chuyển đến điểm tiếp theo trong trường hợp hướng vector ngoại lực trùng với vector nội lực hướng đích của robot (hình 7a). 2. Khi không gian giữa 2 vật cản không đủ lớn, robot sẽ di chuyển và tính toán cập nhật quỹ đạo chuyển động nhưng quỹ đạo này sẽ không mịn, thậm chí robot bị tắc lại mà không đi đến được điểm đích (hình 7b). (a) (b) Hình 7. Một số vấn đề tồn tại của phương pháp Elastic Strips gốc. 2.2.2. Đề xuất cải tiến Đề xuất này nhằm cải tiến phương pháp Elastic Strips gốc áp dụng cho robot tự hành nhằm đáp ứng tốt hơn cho robot di chuyển theo thời gian thực; Tránh được một số nhược điểm còn tồn tại của phương pháp gốc, trong những trường hợp cụ thể. Kết quả được kiểm chứng thông qua phương pháp lập luận và mô phỏng trên hệ thống tính toán. Cụ thể đề xuất: +) Việc tính toán các thành phần lực của phương pháp cải tiến vẫn dựa trên các công thức tính toán (1), (2), (3). Tuy nhiên, đối với nội lực- thành phần này vẫn được giữ nguyên, còn đối với thành phần ngoại lực, thay vì chỉ dựa vào duy nhất một điểm gần nhất của vật cản với robot, ta sẽ tính toán và dựa vào 02 thành phần ngoại lực, một bên trái- dựa Điều khiển – Cơ điện tử - Truyền thông N.M.Ngọc, P.Đ.Lâm, Đ.N.Toàn, “Thuật toán tránh vật cản Elastic Strips.” 98 vào điểm gần nhất bên trái, một bên phải- dựa vào điểm gần nhất bên phải theo hướng di chuyển hiện tại của robot (hình 8). Trong hình 8, robot có nhiệm vụ di chuyển từ vị trí hiện tại đến vị trí đích (target), tại thời điểm tính toán robot phát hiện các chướng ngại vật thứ nhất phía bên trái (OBS1) và chướng ngại vật thứ hai phía bên phải (OBS2) Hình 8. Xác định thành phần ngoại lực của phương pháp cải tiến. +) Công thức tính toán Tính toán ngoại lực trái (L) và phải (R) theo công thức (8)             otherwise ddifddK PV otherwise ddifddK PLV RobssafeRobssafer Rext LobssafeLobssafer Lext 0 )( 2 1 )( 0 )( 2 1 )( min, 2 min, _ min, 2 min, _ (8) Lực tổng hợp được xác định tại công thức (9)  Tziyixii i r i r i e i ffff RfLfff ,,, ,, );()(   (9) +) Thuật toán cải tiến MCA checking {Initial of algorithm} Initial position, target position {positions of robot} Kr, Kc {factor of internal force, external force} d_safe {distance safety of robot} while !( reach to target position) do {Call the collision checking module} if true then {Calculated the internal force } {Calculated the internal force (on the left) } {Calculated the internal force (on the right)} {Calculated the Elastic force} {Trajectory modification} else {continues moving to target point} end if Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2016 99 3. MÔ PHỎNG VÀ KẾT QUẢ 3.1. Số liệu mô phỏng Bảng số liệu mô phỏng. Tham số mô phỏng Case 1 Case 2 Case 3 Vị trí ban đầu của Robot (0, 0); (0,0); (0,0) Vị trí đích của Robot (3500,5000) (4000,3500) (5000,4000) Giá trị Kc 0.8 0.8 0.6 Giá trị Kr 0.6 0.6 0.3 Giới hạn an toàn 1000 (mm) 1000 (mm) 1000 (mm) Bán kính ngoài của Robot 350 (mm) 350 (mm) 350 (mm) 3.2. Phương pháp, công cụ mô phỏng Ngôn ngữ mô phỏng  MAT LAB 8.1  Ngôn ngữ tính toán: C++ Máy tính mô phỏng  PC Intel Core i3 - 4160  CPU: (3.6 GHz , 3MB Cache)  Ram: 2GB DDR3 3.3. Kết quả mô phỏng và bình luận 3.3.1. Đặt bài toán Trong các trường hợp cụ thể được thiết lập các thông số mô phỏng ở trên, thuật toán sẽ được cài đặt trong 03 trường hợp cụ thể: - Trường hợp thứ nhất, giải quyết tình huống robot di chuyển khi vector ngoại lực trùng với vector nội lực. - Trường hợp thứ hai và thứ ba, giải quyết tình huống robot di chuyển trong các điều kiện thông thường nhằm đối sánh quỹ đạo chuyển động của robot khi áp dụng thuật toán gốc và thuật toán cải tiến. 3.3.2. Kết quả mô phỏng Với số liệu đẩu vào, các kết quả mô phòng đã được kiểm chứng và chứng minh tính đúng đắn của phương pháp cải tiến. Trong trường hợp này với phương pháp gốc, robot không thể di chuyển đến được điểm đích và va chạm với vật cản khi hướng vector ngoại lực trùng với vector nội lực hướng đích của robot (hình 9a). Đối với phương pháp cải tiến, dù quỹ đạo không được mịn, tuy nhiên robot tránh được va chạm và hướng đến đích (hình 9b). Trong các trường hợp (2), (3) kết quả mô phòng tại hình 10, 11 cho thấy, cả hai phương pháp (gốc, cải tiến) đều đưa ra cho robot một quỹ đạo chuyển động và tránh được vật cản, hướng đến đích. Tuy nhiên, với phương pháp cải tiến quỹ đạo của robot mịn hơn, trơn hơn so với quỹ đạo của phương pháp gốc. Điều khiển – Cơ điện tử - Truyền thông N.M.Ngọc, P.Đ.Lâm, Đ.N.Toàn, “Thuật toán tránh vật cản Elastic Strips.” 100 (a) (b) Hình 9. Kết quả mô phỏng trong trường hợp 1. (a) (b) Hình 10. Kết quả mô phỏng trong trường hợp có 2 vật cản. (a) (b) Hình 11. Kết quả mô phỏng trong trường hợp 3 vật cản. 4. KẾT LUẬN Phương pháp Elastic Strips cải tiến đã khắc phục được một số tồn tại cụ thể được chỉ ra đối với phương pháp gốc. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2016 101 Thuật toán cải tiến đã giải quyết được những tồn tại của thuật toán gốc được xác định cụ thể trong nội dung bài báo. Việc đối sánh với các kết quả mô phỏng đã được kiểm chứng, phương pháp cải tiến hoàn toàn có thể cài đặt cho mô hình mobile robot vượt chướng ngại vật theo thời gian thực. Trong các trường hợp tổng quát, việc cải tiến thuật toán Elastic Strips gốc cần phải được hoàn thiện hơn, đảm bảo phù hợp trong mọi trường hợp cụ thể và các điều kiện thực tế. Đồng thời, thuật toán cần được cài đặt thử nghiệm trên các mô hình robot tự hành và tay máy làm cơ sở đánh giá tổng quát cho thuật toán cải tiến được đề nghị. TÀI LIỆU THAM KHẢO [1]. P. Moravec, “Certainty Grids for Mobile Robots”, Proceedings of the NASA/JPL Space Telerobotics Workshop, Vol. 3 (1987), pp. 307~312. [2]. Khatib, O, "Real-Time Obstacle Avoidance for Manipulators and Mobile Robots." 1985 IEEE International Conference on Robotics and AutomationSt. Louis, Missouri, March 25-28, 1985, pp. 500-505. [3]. O. Khatib, "Robot In Human Environments: basic Autonomous Capabilities", The International journal of Robotics Research, Vol. 18 (1999), No. 7, pp. 684~696. [4]. Nak Yong Ko, Reid G. Simmons, Dong Jin Seo, “Trajectory Modification Using Elastic Force for Collision Avoidance of a Mobile Manipulator”, PRICAI Workshop, August, 2006, pp. 1214~1224. [5]. Kyung-Hyun Choi, Minh-Ngoc Nong, “A Real Time Collision Avoidance Algorithm for Mobile robot based on Elastic force”, World Academy of Science, Engineering and Technology International Journal of Mechanical, Aerospace, Industrial, Mechatronic and Manufacturing Engineering Vol. 2, No. 5(2008), pp. 666-669. [6]. Nguyễn Văn Tính, Phạm Thượng Cát, Phạm Minh Tuấn, Trần Thuận Hoàng, “An Improved-VFH Obstacle Avoidance Method for Mobile Robot” Tạp chí tự động hóa ngày nay số 145 (2013). [7]. Arkin, R. C., "Motor Schema-Based Mobile Robot Navigation." The International Journal of Robotics Research August 1989, pp. 92-112. [8]. Brooks, R. A., "A Robust Layered Control System for a Mobile Robot." IEEE Journal of Robotics and Automation Vol. RA-2, No. 1, 1986, pp. 14-23. [9]. Brooks, R. A. and Connell, J. H., "Asynchronous Distributed Control System for a Mobile Robot." Proceedings of the SPIE, Mobile Robots Vol. 727, 1987, pp. 77-84. [10]. Krogh, B. H., "A Generalized Potential Field Approach to Obstacle Avoidance Control." International Robotics Research Conference, Bethlehem, Pennsylvania, 1984. [11]. Andria A. Remirez, Robert J. Webster, III, "A Path Generation Method for a Autonomous Mobile Robot based on a Virtual Elastic Force" The Journal of the Korea institute of electronic communication sciences, Volume 8, Issue 1, 2013, pp. 149-157. [12]. Kwon, Young-Kwan,"A New Continuum Robot With Crossed Elastic Strips: Extensible Sections With Only One Actuator per Section" ASME 2015 Dynamic Systems and Control Conference, Vol. 3, 2015. Điều khiển – Cơ điện tử - Truyền thông N.M.Ngọc, P.Đ.Lâm, Đ.N.Toàn, “Thuật toán tránh vật cản Elastic Strips.” 102 ABSTRACT A COLLISION AVOIDANCE ALGORITHM FOR ROBOT BASED ON THE IMPROVED- ELASTIC STRIPS METHOD In this paper, a collision avoidance method based on the improved-Elastic Strips method for mobile robot is presented. The original one calculated and created the trajectory of robot on real-time based on the theory of Artificial Potential Field was suggested by O, Khatib. To avoid the obstacles, the robot has to modify the trajectory based on the signal received from the sensor system. The algorithm is applied and computational for new position of robot in the sampling time. Keywords: Collision avoidance, Avoidance obstacle, Elastic strips, Mobile robot. Nhận bài ngày 12 tháng 05 năm 2016 Hoàn thiện ngày 23 tháng 06 năm 2016 Chấp nhận đăng ngày 04 tháng 07 năm 2016 Địa chỉ: 1 Đại học Thái Nguyên, Phường Tân Thịnh, TP Thái Nguyên; 2 Viện Công nghệ thông tin, Đại học Quốc gia Hà Nội. * Email: ngocnm@tnu.edu.vn