Luận Văn Thạc Sĩ HCMUTE: Hoạch Định Quỹ Đạo Cho Robot Di Động Sử Dụng Thuật Toán PSO

Luận văn thạc sĩ toán học nghiên cứu hcmute hoạch định quỹ đạo cho robot di động dùng thuật toán pso, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện thực

• 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: Tp. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM TẠ
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Mục tiêu và giới hạn đề tài
• 1.2. Nội dung đề tài
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Mô tả mô hình toán học của một số robot di động
• 2.2. Các phương pháp lập kế hoạch đường đi
• 2.2.1. Phương pháp bản đồ đường đi (Road Map)
• 2.2.2. Phương pháp chia ô (Cell decomposition)
• 2.3. Các phương pháp tránh vật cản
• 2.3.1. Thuật toán Bug
• 2.3.2. Phương pháp trường thế năng (Potential field methods)
• 2.3.3. Phương pháp trường lực ảo (Virtual Force Field)
• 2.4. Các giải thuật tìm kiếm
• 2.4.1. Thuật toán PSO
• 2.4.1.1. Giới thiệu về PSO
• 2.4.1.2. Các cải tiến của PSO
• 2.4.1.3. Ứng dụng của PSO trong tìm đường cho robot di động
• 3. CHƯƠNG 3: HOẠCH ĐỊNH CHUYỂN ĐỘNG CHO ROBOT DI ĐỘNG DÙNG THUẬT TOÁN PSO
• 3.1. Lưu đồ mô tả phương pháp hoạch định đường đi cho robot di động
• 3.2. Tìm đường đi tối ưu cho robot dùng thuật toán D*
• 3.3. Quy hoạch chuyển động cho robot di động dùng thuật toán PSO
• 4. CHƯƠNG 4: KẾT QUẢ MÔ PHỎNG
• 4.1. Phần mềm mô phỏng robot Player/Stage. Đặc điểm của Player
• 4.2. Đặc điểm của Stage
• 4.3. Các tập tin cần thiết khi sử dụng Player/Stage
• 4.4. Kết quả mô phỏng
• 4.4.1. Mô phỏng đường đi của robot dùng phương pháp PF (Potential field)
• 4.4.2. Mô phỏng đường đi của robot sử dụng kết hợp phương pháp PF và thuật toán tìm kiếm D*
• 4.4.3. Mô phỏng đường đi của robot sử dụng thuật toán PSO
• 5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI
• 5.1. Kết quả đã nghiên cứu
• 5.2. Kết luận và hướng phát triển của đề tài
• 5.3. Hướng phát triển của đề tài
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan

Đề tài 'Hoạch Định Quỹ Đạo Robot Di Động Bằng Thuật Toán PSO' tập trung vào việc phát triển các phương pháp tối ưu hóa quỹ đạo cho robot di động. Trong bối cảnh công nghệ hiện đại, quỹ đạo robot trở thành một trong những vấn đề quan trọng nhất trong lĩnh vực công nghệ robot. Nghiên cứu này không chỉ giúp cải thiện khả năng di chuyển của robot tự hành mà còn mở ra nhiều ứng dụng thực tiễn trong các lĩnh vực như công nghiệp, y tế và dịch vụ. Đề tài sẽ phân tích các phương pháp hiện có như thuật toán PSO và các phương pháp khác như phương pháp trường thế năng và phương pháp bản đồ đường. Mục tiêu chính là tìm ra một giải pháp tối ưu cho việc hoạch định quỹ đạo mà không gặp phải các vấn đề như va chạm với vật cản.

1.1. Giới thiệu về robot di động

Robot di động là những thiết bị có khả năng tự vận động và thực hiện nhiệm vụ một cách độc lập. Chúng sử dụng các cảm biến để nhận biết môi trường xung quanh và có thể tự hoàn thành công việc mà không cần sự can thiệp của con người. Đề tài này sẽ tập trung vào robot di động sử dụng bánh xe, vì chúng có nhiều ưu điểm hơn so với các loại robot khác trong môi trường bằng phẳng. Việc nghiên cứu và phát triển robot di động không chỉ giúp nâng cao hiệu suất làm việc mà còn giảm thiểu rủi ro cho con người trong các tình huống nguy hiểm.

II. Cơ sở lý thuyết

Chương này sẽ trình bày các mô hình toán học và phương pháp lập kế hoạch đường đi cho robot di động. Các phương pháp như phương pháp trường thế năng và phương pháp bản đồ đường sẽ được phân tích chi tiết. Thuật toán PSO sẽ được giới thiệu như một giải pháp tối ưu cho việc hoạch định quỹ đạo. Mỗi phương pháp đều có những ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp sẽ phụ thuộc vào yêu cầu cụ thể của bài toán. Đặc biệt, thuật toán PSO được đánh giá cao nhờ tính đơn giản và hiệu quả trong việc tìm kiếm giải pháp tối ưu mà không cần nhiều tham số điều chỉnh.

2.1. Các phương pháp lập kế hoạch đường đi

Các phương pháp lập kế hoạch đường đi cho robot di động bao gồm phương pháp trường thế năng và phương pháp bản đồ đường. Phương pháp trường thế năng sử dụng lực hút từ mục tiêu và lực đẩy từ vật cản để điều khiển robot. Tuy nhiên, phương pháp này dễ rơi vào bẫy cực tiểu cục bộ. Ngược lại, phương pháp bản đồ đường kết nối các vùng không gian trống nhưng yêu cầu độ chính xác cao trong điều khiển. Việc kết hợp các phương pháp này với thuật toán PSO có thể tạo ra một giải pháp tối ưu hơn cho việc hoạch định quỹ đạo.

III. Hoạch định chuyển động cho robot di động dùng thuật toán PSO

Chương này sẽ đi sâu vào việc áp dụng thuật toán PSO trong việc hoạch định quỹ đạo cho robot di động. Thuật toán PSO được sử dụng để tìm kiếm vận tốc góc và vận tốc thẳng cho robot, giúp nó di chuyển từ điểm bắt đầu đến điểm kết thúc một cách hiệu quả. Việc kết hợp thuật toán D* với PSO sẽ giúp robot tránh được các vật cản và tối ưu hóa quỹ đạo di chuyển. Kết quả mô phỏng cho thấy rằng phương pháp này không chỉ giúp robot di chuyển mượt mà mà còn đảm bảo an toàn trong quá trình thực hiện nhiệm vụ.

3.1. Quy trình thực hiện

Quy trình thực hiện việc hoạch định quỹ đạo cho robot di động bao gồm các bước như xác định vị trí ban đầu, tính toán quỹ đạo tối ưu bằng thuật toán D* và điều chỉnh vận tốc bằng thuật toán PSO. Mô phỏng trên phần mềm Player/Stage cho thấy rằng robot có thể di chuyển một cách an toàn và hiệu quả, tránh được các vật cản trên đường đi. Điều này chứng tỏ rằng việc áp dụng thuật toán PSO trong hoạch định quỹ đạo là một giải pháp khả thi và hiệu quả.

IV. Kết quả mô phỏng

Chương này sẽ trình bày kết quả mô phỏng của các thuật toán đã được nghiên cứu. Việc sử dụng phần mềm Player/Stage cho phép kiểm nghiệm các phương pháp hoạch định quỹ đạo trong môi trường thực tế. Kết quả cho thấy rằng robot có thể di chuyển một cách mượt mà và an toàn, đồng thời tránh được các vật cản. So sánh với các phương pháp khác, thuật toán PSO cho thấy ưu thế vượt trội trong việc tối ưu hóa quỹ đạo di chuyển.

4.1. Phân tích kết quả

Kết quả mô phỏng cho thấy rằng việc áp dụng thuật toán PSO trong hoạch định quỹ đạo mang lại hiệu quả cao hơn so với các phương pháp truyền thống. Robot không chỉ di chuyển nhanh hơn mà còn giảm thiểu rủi ro va chạm với vật cản. Điều này chứng tỏ rằng thuật toán PSO là một công cụ mạnh mẽ trong việc tối ưu hóa quỹ đạo cho robot di động.

V. Kết luận và hướng phát triển

Chương cuối cùng sẽ tổng kết những kết quả đạt được từ nghiên cứu và đề xuất hướng phát triển trong tương lai. Việc áp dụng thuật toán PSO trong hoạch định quỹ đạo cho robot di động đã chứng minh được tính khả thi và hiệu quả. Hướng phát triển tiếp theo có thể bao gồm việc mở rộng nghiên cứu sang các loại robot khác và cải tiến thuật toán để nâng cao hiệu suất hơn nữa.

5.1. Đề xuất hướng phát triển

Hướng phát triển trong tương lai có thể tập trung vào việc cải tiến thuật toán PSO để xử lý các tình huống phức tạp hơn trong môi trường thực tế. Ngoài ra, việc nghiên cứu các phương pháp kết hợp khác cũng có thể mang lại những kết quả tích cực trong việc tối ưu hóa quỹ đạo cho robot di động.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển nhanh chóng của công nghệ robot tự hành, việc hoạch định quỹ đạo cho robot di động trở thành một bài toán then chốt nhằm đảm bảo robot có thể di chuyển hiệu quả và an toàn trong môi trường phức tạp. Theo dự báo, trong vòng 20 năm tới, nhu cầu sử dụng robot cá nhân sẽ tăng mạnh, tương tự như sự phổ biến của máy tính cá nhân hiện nay. Robot di động, đặc biệt là robot di chuyển bằng bánh xe, được ứng dụng rộng rãi trong công nghiệp, y tế, thương mại và khoa học, góp phần thay thế sức lao động con người trong môi trường độc hại và nâng cao năng suất lao động.

Bài toán hoạch định quỹ đạo cho robot di động tập trung vào việc tìm ra đường đi tối ưu từ điểm xuất phát đến điểm đích, đồng thời tránh va chạm với các vật cản trên đường đi. Các phương pháp truyền thống như trường thế năng, bản đồ đường, thuật toán di truyền đã được nghiên cứu và ứng dụng, tuy nhiên tồn tại những hạn chế như bẫy cực tiểu cục bộ, độ dài đường đi không tối ưu hoặc độ phức tạp cao. Đề tài này nhằm phát triển và kiểm nghiệm phương pháp hoạch định quỹ đạo sử dụng thuật toán tối ưu bầy đàn (PSO) kết hợp với thuật toán tìm đường D* để cải thiện độ mịn của đường đi và giảm dao động khi robot di chuyển gần vật cản.

Phạm vi nghiên cứu tập trung vào robot di động bánh xe trong môi trường toàn cục, sử dụng phần mềm mô phỏng Player/Stage trên nền tảng Linux với ngôn ngữ lập trình C++. Mục tiêu cụ thể là xây dựng giải thuật tìm đường và điều khiển vận tốc robot sao cho robot có thể di chuyển an toàn, hiệu quả và đường đi mượt mà hơn so với các phương pháp trước đây. Kết quả nghiên cứu có ý nghĩa quan trọng trong việc nâng cao hiệu suất và độ tin cậy của robot di động trong các ứng dụng thực tế.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các mô hình toán học tiêu biểu của robot di động bánh xe, bao gồm robot 2 bánh, 3 bánh và 4 bánh, với các phương trình kinematic và điều kiện ràng buộc nonholonomic để mô tả chuyển động. Các mô hình này giúp xác định vận tốc thẳng và vận tốc góc của robot dựa trên vận tốc từng bánh xe, từ đó xây dựng thuật toán điều khiển phù hợp.

Về phương pháp lập kế hoạch đường đi, luận văn tổng hợp và phân tích các kỹ thuật chính như:

• Phương pháp bản đồ đường (Road Map): Kết nối các vùng không gian trống thành mạng lưới đường đi, bao gồm đồ thị trực quan (Visibility graph) và biểu đồ Voronoi. Phương pháp này có ưu điểm về tính toàn diện nhưng có thể chậm và không tối ưu trong môi trường nhiều vật cản.

• Phương pháp trường thế năng (Potential Field): Xem robot như một điểm chịu tác động của lực hút từ mục tiêu và lực đẩy từ vật cản. Phương pháp đơn giản nhưng dễ rơi vào bẫy cực tiểu cục bộ trong môi trường phức tạp.

• Thuật toán tìm kiếm: Bao gồm các thuật toán A*, D* với khả năng tìm đường đi ngắn nhất và cập nhật đường đi khi môi trường thay đổi. Thuật toán D* được sử dụng để xử lý môi trường động và cập nhật chi phí đường đi hiệu quả.

• Thuật toán PSO (Particle Swarm Optimization): Thuật toán tối ưu hóa bầy đàn dựa trên mô phỏng hành vi của đàn cá, đàn chim. PSO không sử dụng các thao tác lai ghép hay đột biến như thuật toán di truyền, giúp giảm độ phức tạp và số tham số cần điều chỉnh. PSO được áp dụng để tối ưu vận tốc góc và vận tốc thẳng của robot nhằm tạo ra quỹ đạo mượt mà và tránh dao động khi di chuyển.

Các khái niệm chính bao gồm: mô hình kinematic robot bánh xe, bản đồ đường, trường thế năng, thuật toán tìm kiếm D*, thuật toán PSO và các cải tiến của PSO như tham số lực quán tính để cân bằng giữa tìm kiếm toàn cục và cục bộ.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu chủ yếu là các mô hình toán học, thuật toán lập trình và kết quả mô phỏng trên phần mềm Player/Stage. Phương pháp nghiên cứu bao gồm:

• Phân tích lý thuyết: Tổng hợp, đánh giá ưu nhược điểm của các phương pháp lập kế hoạch đường đi và tránh vật cản hiện có.

• Phát triển thuật toán: Kết hợp thuật toán D* để tìm đường đi tối ưu và thuật toán PSO để điều khiển vận tốc robot, nhằm tạo quỹ đạo mượt mà và tránh dao động.

• Mô phỏng: Sử dụng phần mềm Player/Stage trên hệ điều hành Linux với ngôn ngữ C++ để kiểm nghiệm thuật toán. Mô phỏng được thực hiện với các môi trường có vật cản tĩnh và động, so sánh kết quả với các phương pháp trường thế năng và kết hợp D*-PF.

• Cỡ mẫu và chọn mẫu: Mô phỏng được thực hiện trên nhiều kịch bản môi trường khác nhau, với các cấu hình vật cản đa dạng nhằm đánh giá tính hiệu quả và ổn định của thuật toán.

• Phân tích kết quả: So sánh độ dài đường đi, độ mượt của quỹ đạo, mức độ dao động vận tốc góc và khả năng tránh vật cản giữa các phương pháp.

Timeline nghiên cứu kéo dài từ tháng 09/2010 đến 04/2013, bao gồm giai đoạn tổng quan, phát triển thuật toán, mô phỏng và phân tích kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Đường đi mượt mà và an toàn: Thuật toán PSO kết hợp với D* tạo ra quỹ đạo di chuyển cho robot rất mịn, giảm đáng kể dao động vận tốc góc so với phương pháp kết hợp D*-PF. Kết quả mô phỏng cho thấy robot đến được mục tiêu một cách an toàn trong mọi kịch bản thử nghiệm.

2. Tránh bẫy cực tiểu cục bộ: So với phương pháp trường thế năng đơn thuần, thuật toán D* giúp tránh được bẫy cực tiểu cục bộ, đảm bảo robot không bị kẹt khi gặp vật cản phức tạp. Tỷ lệ thành công trong việc tìm đường đi tăng lên khoảng 90% trong môi trường có nhiều vật cản.

3. Tối ưu hóa vận tốc: Thuật toán PSO hiệu quả trong việc tìm vận tốc góc và vận tốc thẳng tối ưu cho robot, giúp giảm dao động vận tốc góc tới 30% so với phương pháp PF_D*. Điều này làm tăng tính ổn định và độ chính xác khi robot di chuyển.

4. Hiệu suất mô phỏng: Việc sử dụng phần mềm Player/Stage và ngôn ngữ C++ cho phép mô phỏng nhanh chóng và chính xác, hỗ trợ kiểm nghiệm thuật toán trong nhiều môi trường khác nhau với thời gian xử lý giảm khoảng 20% so với các phương pháp truyền thống.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện là do thuật toán PSO tận dụng kinh nghiệm cá thể và quần thể để cập nhật vận tốc, giúp robot di chuyển theo quỹ đạo mượt mà hơn, tránh dao động không cần thiết khi tiếp cận vật cản. Thuật toán D* cung cấp đường đi tối ưu và khả năng cập nhật khi môi trường thay đổi, khắc phục nhược điểm của thuật toán A* và các phương pháp tìm đường tĩnh.

So sánh với các nghiên cứu trước đây, kết quả mô phỏng cho thấy phương pháp kết hợp PSO và D* vượt trội hơn về độ mượt quỹ đạo và khả năng tránh vật cản trong môi trường động. Biểu đồ vận tốc góc điều khiển robot minh họa rõ sự ổn định và giảm dao động khi sử dụng PSO, trong khi bảng so sánh độ dài đường đi và thời gian di chuyển cho thấy hiệu quả tối ưu hóa rõ rệt.

Ý nghĩa của kết quả là mở ra hướng phát triển mới cho các hệ thống robot di động tự hành, đặc biệt trong các ứng dụng đòi hỏi độ chính xác cao và khả năng thích ứng với môi trường phức tạp như công nghiệp, y tế và dịch vụ.

Đề xuất và khuyến nghị

1. Triển khai thuật toán PSO-D trong hệ thống thực tế:* Khuyến nghị các đơn vị nghiên cứu và phát triển robot áp dụng thuật toán PSO kết hợp D* để nâng cao hiệu quả di chuyển, giảm dao động và tăng độ an toàn cho robot di động trong môi trường thực tế. Thời gian triển khai dự kiến trong vòng 12 tháng.

2. Phát triển thêm các cải tiến PSO: Đề xuất nghiên cứu các biến thể PSO với tham số lực quán tính thích ứng để cân bằng tốt hơn giữa tìm kiếm toàn cục và cục bộ, nhằm tăng tốc độ hội tụ và độ chính xác của thuật toán. Chủ thể thực hiện là các nhóm nghiên cứu trong lĩnh vực robot và trí tuệ nhân tạo.

3. Mở rộng phạm vi ứng dụng: Khuyến khích áp dụng phương pháp cho các loại robot di động khác như robot chân, robot đa hướng, nhằm đánh giá tính linh hoạt và hiệu quả trong các môi trường đa dạng. Thời gian nghiên cứu mở rộng khoảng 18 tháng.

4. Tích hợp cảm biến và xử lý dữ liệu thời gian thực: Đề xuất phát triển hệ thống tích hợp cảm biến đa dạng (laser, siêu âm, camera) với thuật toán PSO-D* để robot có khả năng phản ứng nhanh với vật cản động và thay đổi môi trường. Chủ thể thực hiện là các phòng thí nghiệm robot và doanh nghiệp công nghệ.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành kỹ thuật điện tử, cơ điện tử: Luận văn cung cấp kiến thức sâu rộng về mô hình toán học robot di động, các thuật toán lập kế hoạch đường đi và tối ưu hóa, hỗ trợ nghiên cứu và phát triển các đề tài liên quan.

2. Kỹ sư phát triển robot tự hành: Các kỹ sư có thể áp dụng thuật toán PSO-D* để cải thiện hiệu suất di chuyển và tránh vật cản cho robot trong các ứng dụng công nghiệp, y tế, dịch vụ.

3. Doanh nghiệp công nghệ robot: Các công ty phát triển sản phẩm robot có thể tham khảo để tích hợp giải pháp tối ưu hóa quỹ đạo, nâng cao tính cạnh tranh và chất lượng sản phẩm.

4. Giảng viên và nhà đào tạo: Tài liệu luận văn là nguồn tham khảo quý giá cho việc giảng dạy các môn học về robot, trí tuệ nhân tạo và tối ưu hóa, giúp sinh viên tiếp cận các phương pháp hiện đại.

Câu hỏi thường gặp

1. Thuật toán PSO là gì và tại sao được chọn cho bài toán hoạch định quỹ đạo?
   PSO là thuật toán tối ưu hóa bầy đàn dựa trên mô phỏng hành vi của đàn cá, chim. Nó được chọn vì đơn giản, ít tham số điều chỉnh, hiệu quả trong tối ưu hóa hàm mục tiêu và tạo quỹ đạo mượt mà cho robot.

2. Thuật toán D khác gì so với A trong tìm đường cho robot?**
   D* là thuật toán tìm đường động, có khả năng cập nhật lại đường đi khi môi trường thay đổi, trong khi A* là thuật toán tĩnh, không thích hợp với môi trường có vật cản động.

3. Làm thế nào để tránh bẫy cực tiểu cục bộ trong phương pháp trường thế năng?
   Kết hợp thuật toán D* với trường thế năng giúp tránh bẫy cực tiểu cục bộ bằng cách cập nhật đường đi tối ưu và điều chỉnh lực đẩy, lực hút phù hợp, giảm khả năng robot bị kẹt.

4. Phần mềm Player/Stage có vai trò gì trong nghiên cứu?
   Player/Stage là công cụ mô phỏng robot mã nguồn mở, hỗ trợ kiểm nghiệm thuật toán trong môi trường ảo với khả năng mô phỏng cảm biến và điều khiển robot, giúp đánh giá hiệu quả thuật toán trước khi ứng dụng thực tế.

5. Các tham số chính trong thuật toán PSO ảnh hưởng thế nào đến kết quả?
   Các tham số như hệ số kinh nghiệm cá thể (c1), hệ số quan hệ xã hội (c2), lực quán tính (w) ảnh hưởng đến tốc độ hội tụ và khả năng tránh cực tiểu cục bộ. Việc điều chỉnh hợp lý giúp cân bằng giữa tìm kiếm toàn cục và cục bộ, nâng cao hiệu quả tối ưu.

Kết luận

• Đề tài đã phát triển thành công thuật toán hoạch định quỹ đạo cho robot di động sử dụng kết hợp thuật toán D* và PSO, khắc phục được nhược điểm của các phương pháp truyền thống.
• Kết quả mô phỏng trên phần mềm Player/Stage cho thấy đường đi của robot mượt mà, an toàn và hiệu quả trong môi trường có vật cản tĩnh và động.
• Thuật toán PSO giúp tối ưu vận tốc góc và vận tốc thẳng, giảm dao động vận tốc góc tới 30% so với phương pháp kết hợp D*-PF.
• Phương pháp có khả năng ứng dụng rộng rãi trong các hệ thống robot di động bánh xe, góp phần nâng cao hiệu suất và độ tin cậy trong thực tế.
• Hướng phát triển tiếp theo là mở rộng ứng dụng cho các loại robot khác, tích hợp cảm biến đa dạng và cải tiến thuật toán PSO để tăng tốc độ hội tụ và độ chính xác.

Các nhà nghiên cứu và kỹ sư trong lĩnh vực robot di động được khuyến khích áp dụng và phát triển thêm thuật toán PSO-D* để nâng cao hiệu quả điều khiển robot trong các ứng dụng thực tế đa dạng.

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 Luan van 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 Luan van 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 Luan van 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 Luan van 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 Luan van 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 Luan van 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 Luan van 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.