Luận văn thạc sĩ: Hoạch định quỹ đạo cho Robot di động dùng thuật toán PSO

Luận văn thạc sĩ nghiên cứu hoạch định quỹ đạo cho robot di động. Áp dụng thuật toán PSO để tìm đường đi tối ưu và tránh vật cản hiệu quả.

• Tác giả: Lâm Văn Vũ
• Người hướng dẫn: TS. Ngô Văn Thuyên
• Trường học: Trường Đại Học Sư Phạm Kỹ Thuật Thành Phố Hồ Chí Minh
• Chuyên ngành: Kỹ Thuật Điện Tử
• Đề tài: Hoạch định quỹ đạo cho robot di động dùng thuật toán PSO
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2013
• Địa điểm: Thành Phố Hồ Chí Minh

Tóm tắt

I. Giới thiệu về Hoạch định Quỹ đạo Robot Di động

Hoạch định quỹ đạo robot di động là một lĩnh vực nghiên cứu quan trọng trong kỹ thuật điện tử và cơ điện tử. Đây là quá trình xác định đường đi tối ưu cho robot từ vị trí ban đầu đến vị trí đích trong môi trường có chứa vật cản. Robot di động cần có khả năng tự động lập kế hoạch chuyển động, tránh va chạm và hoàn thành nhiệm vụ một cách hiệu quả. Với sự phát triển của công nghệ, hoạch định đường đi trở thành yếu tố then chốt trong các ứng dụng robot tự động hóa, từ robot công nghiệp đến robot phục vụ. Nghiên cứu về phương pháp hoạch định quỹ đạo giúp nâng cao hiệu suất hoạt động và độ an toàn của robot trong thực tế.

1.1. Tầm quan trọng của Hoạch định Quỹ đạo

Hoạch định quỹ đạo là nền tảng cho các robot di động tự chủ. Nó cho phép robot tìm được đường đi ngắn nhất, an toàn và tránh được các vật cản trong môi trường. Các phương pháp hoạch định truyền thống như bản đồ đường đi (Road Map) và chia ô (Cell Decomposition) đã được ứng dụng rộng rãi nhưng vẫn có những hạn chế về tốc độ và hiệu quả trong các môi trường phức tạp.

1.2. Mục tiêu Nghiên cứu

Luận văn tập trung vào việc phát triển thuật toán PSO (Particle Swarm Optimization) để hoạch định quỹ đạo cho robot di động. PSO là một phương pháp tối ưu hóa heuristic hiệu quả, được lấy cảm hứng từ hành vi của bầy chim. Mục tiêu chính là so sánh hiệu suất của PSO với các phương pháp truyền thống và chứng minh ưu điểm của hoạch định quỹ đạo PSO.

II. Thuật toán PSO và Ứng dụng

Thuật toán PSO (Particle Swarm Optimization) là một kỹ thuật tối ưu hóa metaheuristic dựa trên hành vi xã hội của các đàn chim bay tìm kiếm thức ăn. Trong hoạch định quỹ đạo robot, PSO được sử dụng để tìm đường đi tối ưu bằng cách mô phỏng chuyển động của các hạt (particles) trong không gian tìm kiếm. Mỗi hạt đại diện cho một quỹ đạo tiềm năng, và chúng tương tác để tìm ra giải pháp tốt nhất. Ưu điểm của PSO bao gồm tốc độ hội tụ nhanh, khả năng tránh tối ưu cục bộ, và dễ dàng hiện thực hóa trên các nền tảng khác nhau. Phương pháp này được chứng minh là hiệu quả hơn nhiều phương pháp truyền thống trong các bài toán hoạch định đường đi phức tạp.

2.1. Nguyên lý Hoạt động của PSO

PSO bắt đầu với một quần thể các hạt ngẫu nhiên trong không gian tìm kiếm. Mỗi hạt có vận tốc và vị trí, được cập nhật dựa trên vị trí tốt nhất cá nhân (personal best) và vị trí tốt nhất toàn cầu (global best). Phương trình cập nhật vận tốc giúp hạt đi theo hướng tối ưu. Quá trình này lặp đi lặp lại cho đến khi tìm được giải pháp hội tụ.

2.2. Cải tiến và Ứng dụng Thực tế

Luận văn đề xuất các cải tiến PSO như điều chỉnh trọng số quán tính (inertia weight) và tham số học (learning parameters) để tăng hiệu quả. Ứng dụng PSO được kiểm nghiệm thông qua phần mềm mô phỏng Player/Stage, cho phép so sánh với các phương pháp truyền thống như trường thế năng (Potential Field).

III. Các Phương pháp Hoạch định Đường đi Truyền thống

Trước khi áp dụng thuật toán PSO, luận văn khảo sát các phương pháp hoạch định quỹ đạo truyền thống đã được sử dụng rộng rãi. Phương pháp bản đồ đường đi (Road Map) tạo một mạng lưới các đoạn thẳng nối các điểm quan trọng trong môi trường, giúp robot tìm đường đi từ điểm khởi động đến điểm đích. Phương pháp chia ô (Cell Decomposition) chia không gian làm việc thành các ô đơn giản hơn, tạo lập bản đồ lưới để lập kế hoạch. Phương pháp trường thế năng (Potential Field) coi robot chịu lực hấp dẫn từ mục tiêu và lực đẩy từ vật cản. Bên cạnh đó, phương pháp trường lực ảo (Virtual Force Field) kết hợp các lực này để dẫn robot. Mỗi phương pháp có ưu và nhược điểm riêng, và hoạch định đường đi hiệu quả phụ thuộc vào bản chất của bài toán.

3.1. Phương pháp Bản đồ Đường đi và Chia Ô

Phương pháp Road Map phù hợp với các môi trường tĩnh và có cấu trúc rõ ràng. Phương pháp Cell Decomposition dễ hiện thực nhưng có thể không tối ưu trong không gian cao chiều. Cả hai đều cần thời gian tiền xử lý để xây dựng bản đồ trước khi robot hoạt động.

3.2. Phương pháp Trường Thế năng

Trường thế năng là phương pháp phản ứng nhanh, thích hợp cho môi trường động. Tuy nhiên, nó dễ mắc kẹt tại tối ưu cục bộ khi các lực hấp dẫn và đẩy cân bằng nhau. Hoạch định đường đi PSO giải quyết nhược điểm này bằng cách tìm kiếm toàn cục.

IV. Kết quả Mô phỏng và Kết luận

Luận văn thực hiện mô phỏng hoạch định quỹ đạo sử dụng phần mềm Player/Stage, một công cụ mạnh mẽ để mô phỏng robot di động. Các kết quả mô phỏng so sánh ba phương pháp: trường thế năng (PF), kết hợp PF với thuật toán D*, và thuật toán PSO. Kết quả cho thấy PSO tìm được đường đi tối ưu hơn, đặc biệt trong các môi trường phức tạp với nhiều vật cản. Hoạch định quỹ đạo dùng PSO không chỉ tìm được đường đi ngắn hơn mà còn có tốc độ hội tụ nhanh hơn so với các phương pháp khác. Những phát hiện này chứng minh rằng PSO là một giải pháp đầu tiên trong lĩnh vực hoạch định quỹ đạo robot di động.

4.1. Thiết lập Mô phỏng và Kết quả

Phần mềm Player/Stage cung cấp môi trường mô phỏng 2D với khả năng mô phỏng cảm biến laser, camera và các động cơ robot. Kết quả mô phỏng cho thấy PSO giảm độ dài đường đi trung bình 15-25% so với trường thế năng, với thời gian tính toán chấp nhận được.

4.2. Hướng Phát triển Tương lai

Các hướng phát triển tiếp theo bao gồm: ứng dụng PSO cho hoạch định đường đi 3D, kết hợp với các cảm biến thực tế, và tối ưu hóa bổ sung. Hoạch định quỹ đạo robot sẽ tiếp tục là chủ đề nghiên cứu quan trọng trong robot tự chủ.

Trích đoạn nội dung tài liệu

Chương 1 Tổng quan pháp hoạch định quỹ đạo cho robot di động. Ngoài ra, mục tiêu nghiên cứu và giới hạn của đề tài cũng như nội dung chính của luận văn cũng được thể hiện trong chương này. Chương 2: Cơ sở lý thuyết Có năm phần chính được đề cập trong chương 2. Phần thứ nhất trình bày các mô hình toán dùng trong điều khiển mobile robot.

Các phương pháp lập kế hoạch đường đi như: Phương pháp bản đồ đường đi (Road Map), Phương pháp chia ô (Cell Decomposition). Các phương pháp tránh vật cản như: Thuật toán Bug, phương páp trường thế năng, phương pháp trường lực ảo (VFF). Các giải thuật tìm kiếm như: Giải thuật A*, giải thuật D*. Thuật toán PSO được trình bày ở phần thứ năm.

Chương 3: Hoạch định chuyển động cho robot di động dùng thuật toán PSO Đây là phần trọng tâm của đề tài. Chương này tập trung nghiên cứu các phương pháp tìm đường đi và qui trình thực hiện việc hoạch định đường đi, hoạch định đường đi dùng thuật toán PSO (trình bày rõ về bài toán tìm đường dùng thuật toán tìm kiếm D* và bài toán di chuyển dùng thuật toán PSO). Chương 4: Kết quả mô phỏng Chương này giới thiệu về đặc điểm, chức năng của công cụ mô phỏng robot mã nguồn mở Player/Stage. Thuật toán hoạch định đường đi cho robot di động dùng PSO kết hợp với trường thế năng được kiểm nghiệm trên công cụ mô phỏng này và chương trình điều khiển robot được xây dựng trên ngôn ngữ C++.

Kết quả mô phỏng sẽ được phân tích để tìm ra ưu, nhược điểm của từng giải thuật và so sánh kết quả đã nghiên cứu được với kết quả của các đề tài nghiên cứu trước đó. Chương 5: Kết luận và hướng phát triển của đề tài Chương này sẽ nhận xét ưu, nhược điểm của các giải thuật cải tiến mà đề tài đã đưa ra so với các giải thuật đã được nghiên cứu trước đây và đề xuất hướng phát triển của đề tài. 6 Chương 2 Cơ sở lý thuyết Chƣơng 2 CƠ SỞ LÝ THUYẾT 2. Mô tả mô hình toán học của một số robot di động Trong thực tế, một robot muốn di chuyển được thì phải được điều khiển bằng các thuật toán.

Mô hình toán học là một phần hỗ trợ cho thuật toán điều khiển, tùy môi trường làm việc mà ta có những robot khác nhau [4], [6]. Trong mục này, xem xét ba mô hình tiêu biểu, được ứng dụng rộng rãi trong thực tế. Đó là robot 2 bánh, 3 bánh và robot 4 bánh. Robot 2 bánh Robot di động chuyển động bằng bánh xe [6] bao gồm một đế được hỗ trợ bởi những bánh xe lăn.

Những bánh xe này cho phép chuyển động tương đối giữa đế và mặt đất. Những robot chuyển động bánh xe có kết cấu đơn giản, dễ xây dựng và có tỷ lệ tải trọng thuận lợi. Hơn nữa chuyển động bằng bánh thì dễ điều khiển, vấn đề vững vàng được đặt ra ít hơn, sử dụng ít năng lượng và có thể di chuyển với tốc độ cao. Khả năng di chuyển và điều khiển của robot di động chuyển động bằng bánh xe phụ thuộc phần lớn vào những bánh xe gắn liền.

Sự lựa chọn thông dụng nhất cho những phương tiện bằng bánh xe là bánh xe dạng đĩa, kết cấu hình học của nó cho phép: dễ lắp vào đế, dễ điều khiển, cấu trúc vật lý mạnh mẽ và dễ hoạt động trong sự có mặt của chấn động, những chỗ nứt hay sự không đều của mặt đất. Với một đế gồm nhiều bánh xe cho phép phân phối tải trọng và lực kéo giữa những bánh xe rất tốt, như vậy robot loại này có một lợi thế để thực hiện nhiệm vụ mà những robot di động loại khác khó có thể thực hiện được. Tuy nhiên, mặc dù có tính đa năng do sự hoạt động tự nhiên của bánh xe, nhưng phải chấp nhận những ràng buộc để đưa ra yêu cầu cho mỗi bánh xe là: không trượt ngang và quay mà không trượt. 7 Chương 2 Cơ sở lý thuyết Dựa vào hình 2.1 ta xác định ngõ điều khiển và hình dạng robot như sau: v  U   (2.2)     Trong đó: ( x, y ) là vị trí của robot  là góc định hướng cho robot v là vận tốc thẳng,  là vận tốc góc Quan hệ giữa ngõ vào điều khiển và vận tốc hai bánh xe ta được: Ở tại mọi thời điểm, bánh xe trái và phải của robot luôn quay theo quỹ đạo với cùng vận tốc gốc.

Cấu trúc robot 2 bánh L Khi đó,  (R+ )  VR (2.4) 2 Trong đó: VR là vận tốc thẳng của bánh xe phải, VL là vận tốc thẳng của bánh xe trái, r là bán kính danh định của mỗi bánh xe, bán kính đường cong tức thời của quỹ đạo robot. 8 Chương 2 Cơ sở lý thuyết Lấy (2.4) xác định đựơc: VR  VL v (2.6) L Mô hình toán của Kinematic và điều kiện ràng buộc nonholonomic trong hệ tọa độ toàn cục như sau: Hình 2. Cấu trúc robot với điều kiện ràng buộc nonholonomic trong hệ tọa độ toàn cục Biểu thức Kinematic:   x  cos  0   v  y    sin  0  .7)    0 1         Điều kiện rang buộc nonholonomic:    x   sin cos      x sin   y cos =0 (2. Robot 3 bánh Phương trình chuyển động với vận tốc v của robot (hình 2.3) thoả mãn phương trình động sau: 9 Chương 2 Cơ sở lý thuyết     x(t )  cos  (t ) 0        v(t )   y (t )    sin  (t ) 0 .

Cấu trúc robot 3 bánh 2. Robot 4 bánh Hình 2. Cấu trúc của robot di động 4 bánh Phương trình chuyển động với vận tốc v của robot thoả mãn phương trình động sau: 10 Chương 2 Cơ sở lý thuyết    x  cos  sin  0   v   y     sin  cos  0 . Các phƣơng pháp lập kế hoạch đƣờng đi Bài toán lập kế hoạch đường đi [5], [7], [8] 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. Bước đầu tiên của hệ thống lập kế hoạch đường đi là biến đổi kiểu môi trường liên tục thành bản đồ rời rạc để thích ứng cho việc chọn giải thuật lập kế hoạch đường đi. Có các phương pháp chính như sau: 2. Phương pháp bản đồ đường đi (Road Map) 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). Trong phương pháp đồ thị trực quan, 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. Còn trong 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.  Visibility graph Phương pháp Visibility graph (hình 2.5) có hai nhược điểm.

Thứ nhất, nó cực kỳ nhanh và hiệu quả cho các môi trường thưa thớt vật cản, nhưng có thể chậm và không hiệu quả bằng các phương pháp khác đối với các môi trường có mật độ vật cản cao. Thứ hai là có nhiều thiếu sót tiềm ẩn: Kết quả đường đi tìm được bởi Visibility graph có thể làm cho robot bị chạm vào vật cản trên đường đi đến đích. 11 Chương 2 Cơ sở lý thuyết Giải pháp chung là tăng kích thước vật cản lên một khoảng bằng với bán kính của robot, hoặc là điều chỉnh kết quả đường đi sau khi đã có kế hoạch đường đi cách xa vật cản ra một khoảng cách cho phép. Dĩ nhiên, điều này sẽ hy sinh sự tối ưu về độ dài của phương pháp Visibility graph.

Phương pháp đồ thị trực quan (Visibility graph)  Voronoi Phương pháp sơ đồ Voronoid (Voronoid diagram).6) là phương pháp vẽ đường đi hoàn chỉnh dựa trên khoảng cách tối đa giữa robot và vật cản trong bản đồ. 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. Voronoid diagram 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 đ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. 12 Chương 2 Cơ sở lý thuyết Hình 2.

Phương pháp chia ô (Cell decomposition) Ý tưởng của phương pháp chia ô là phân biệt rõ giữa khu vực hình học, hoặc các ô là những vùng trống và vùng bị chiếm giữ bởi vật cản. Có hai phương pháp chia ô là chia ô chính xác và chia ô gần đúng.7a mô tả phương pháp chia ô chính xác, trong đó đường biên của các ô được xác định dựa trên giới hạn hình học của vật cản. Các ô kết quả có thể là những ô hoàn toàn trống hoặc hoàn toàn bị chiếm giữ, vì vậy kế hoạch đường đi trong mạng được thực hiện giống như các phương pháp ở trên. Bất lợi chính của phương pháp chia ô chính xác là số lượng các ô, do sự tính toán khi lập kế hoạch đường đi phụ thuộc vào mật độ và độ phức tạp của vật cản trong môi trường.

Vì vậy, sự biểu diễn sẽ phụ thuộc vào độ lớn và độ thưa thớt của môi trường.