Báo Cáo Lập lộ trình chuyển động cho robot

MỤC LỤC
MỤC LỤC .2
KÝ HIỆU – QUY ƯỚC .4
TÓM TẮT ĐỒ ÁN .5
NỘI DUNG ĐỒ ÁN 7
CHƯƠNG 1: GIỚI THIỆU BÀI TOÁN LẬP LỘ TRÌNH CHO ROBOT .7
1.1. Khái niệm cơ bản 7
1.1.1. Sơ lược về robot .7
1.1.2. Một số thuật ngữ chung trong việc lập lộ trình 7
1.2. Bài toán lập lộ trình .9
1.3. Ví dụ về lập kế hoạch và một số ứng dụng về lập lộ trình robot 10
1.3.1. Robot sắp xếp các khối 10
1.3.2. Robot mua hàng hóa 11
1.3.3. Sử dụng robot di động để di chuyển piano 11
1.3.4. Tìm đường cho robot di động 12
1.4. Một số giải thuật cơ bản 13
1.4.1. Giải thuật Bug 0 .14
1.4.2. Giải thuật Bug 1 .15
1.4.3. Giải thuật Bug 2 .16
1.4.4. So sánh hai giải thuật .17
1.5. Kết luận .19
CHƯƠNG 2: CẤU HÌNH KHÔNG GIAN TRẠNG THÁI .20
2.1. Các khái niệm không gian cấu hình 20
2.1.1. Chướng ngại (Obstacle) .20
2.1.2. Không gian tự do (Free Space – Cfree) .20
2.2. Các phép biến dổi của robot 21
2.2.1. Phép tịnh tiến .22
3
2.2.2. Phép quay .22
2.3. Không gian cấu hình chướng ngại vật 24
2.4. Kết luận .26
CHƯƠNG 3: MỘT SỐ PHƯƠNG PHÁP CHÍNH XÁC LẬP LỘ TRÌNH CHUYỂN ĐỘNG .27
3.1. Giới thiệu chung 27
3.2. Một số giải thuật lập lộ trình chính xác cho robot 27
3.2.1. Các giải thuật roadmap 27
3.2.1.1. Visibility Graph – Đồ thị tầm nhìn .27
3.2.1.2. Voronoi Diagram – Lược đồ Voronoi 30
3. 2.2. Cell Decomposition (Phân ly ô) .32
3.2.2.1. Exact Cell Decomposition 33
3.2.2.2. Approximate Cell Decomposition 35
3.3. Tổng kết 36
TÀI LIỆU THAM KHẢO .37
PHỤ LỤC 38
Phụ lục 1 - Demo các giải thuật cơ bản (Bug 1 – Bug 2) .38
Phụ lục 2 – Demo giải thuật Visibility Graph .38
Phụ lục 3 – Demo giải thuật Voronoi Diagram

TÓM TẮT ĐỒ ÁN
Lập lộ trình chuyển động cho robot là một hướng nghiên cứu khoa học với mục tiêu cung cấp tri thức để robot có đủ khả năng tự vận động, di chuyển trong không gian phức tạp (với nhiều chướng ngại) để đến được đích mà không bị lạc hay va vào các đối tượng khác.
Thông thường một lộ trình thường được xác lập trước để dẫn dắt robot đến vị trí đích. Với phương pháp này, môi trường robot đi qua phải được biết hoàn toàn và không thay đổi, đồng thời robot cần có cơ quan cảm giác để cảm nhận và cập nhật tri thức từ môi trường. Hạn chế của việc lập lộ trình trước đòi hỏi việc nghiên cứu tìm hiểu vạch lộ trình nội tại, và phụ thuộc vào các tri thức thu được từ môi trường hiện tại để xử lý các chướng ngại chưa biết khi robot băng qua môi trường.
Trên thế giới hiện nay tự động hóa robot là một lĩnh vực nghiên cứu thu hút một lực lượng đông đảo các nhà khoa học tham gia. Bài toán lập lộ trình cho robot là bài toán cơ bản để thiết kế và chế tạo robot, do vậy việc tìm hiểu bài toán và nghiên cứu các phương pháp lập lộ trình là rất quan trọng và cần thiết cho sự phát triển của ngành khoa học robot. Hiện nay, đã có một số nghiên cứu mới để giải quyết bài toán này như ứng dụng giải thuật di truyền - lập trình tiến hóa, ứng dụng mạng neuron trong việc xây dựng lộ trình chuyển động, ; nói chung, đây là một vấn đề mở, nhiều thử thách và đang rất được quan tâm. Đặc biệt trong nước nói chung và trong lĩnh vực AI của nước ta nói riêng, so với các hướng nghiên cứu như nhận dạng, xử lý ảnh, xử lý âm thanh, đây vẫn còn là một chủ đề khá mới mẻ và hầu như chưa có tài liệu một cách đầy đủ về đề tài này.
Trước tiên em xin chân thành cảm ơn thầy Lê Hoài Bắc, dưới sự gợi ý và chỉ dẫn của thầy, em đã được tạo điều kiện và cơ hội để tiếp cận với hướng nghiên cứu mới, đầy thú vị này: “Robot Motion Planning” – “Lập lộ trình chuyển động cho robot”. Mục tiêu của bài báo cáo đồ án này tập trung vào tường thuật lại các nội dung mà em đã thu thập và nắm được trong suốt quá tìm hiểu đồ án. Báo cáo đồ án ở đây gồm 3 chương, có thể được tóm tắt ngắn gọn như sau:
6
Chương 1: Trình bày tổng quan về bài toán lập lộ trình cho robot bao gồm: Các khái niệm cơ bản về robot, giới thiệu về bài toán lập lộ trình, ví dụ và một số ứng dụng về lập lộ trình robot, khái quát một số giải thuật lập lộ trình cơ bản.
Chương 2: Trình bày các khái niệm về cấu hình không gian trạng thái, cách biểu diễn không gian trong bài toán lập lộ trình robot.
Chương 3: Tìm hiểu sâu về một số phương pháp chính xác lập lộ trình chuyển động cho robot, cụ thể gồm các phương pháp: lớp giải thuật Roadmap (Các giải thuật tiêu biểu như: Visibiliity Graph (Đồ thị tầm nhìn), Voronoi Diagram (Lược đồ Voronoi)), các phương pháp Cell Decomposition (Phân giải ô). Đây là những cách tiếp cận tổ hợp với việc lập lộ trình chuyển động để tìm đường đi xuyên qua không gian cấu hình liên tục mà không cần đến các thuật toán xấp x