Thạc Sĩ Ứng dụng mạng nơron trong bài toán xác định lộ trình cho robot

LỜI NÓI ĐẦU


Nhờ các khả năng: Học, nhớ lại và khái quát hoá từ các mẫu huấn luyện hoặc dữ liệu, mạng nơron nhân tạo trở thành một phát minh mới đầy hứa hẹn của hệ thống xử lý thông tin. Các tính toán nơron cho phép giải quyết tốt những bài toán đặc trưng bởi một số hoặc tất cả các tính chất sau: Sử dụng không gian nhiều chiều, các tương tác phức tạp, chưa biết hoặc không thể theo dõi về mặt toán học giữa các biến. Ngoài ra phương pháp này còn cho phép tìm ra nghiệm của những bài toán đòi hỏi đầu vào là các cảm nhận của con người như: tiếng nói, nhìn và nhận dạng .

Bài toán lập lộ trình cho robot là một bài toán khá phức tạp, do khi tồn tại và hành động trong môi trường robot sẽ phải chịu rất nhiều sự tác động khác nhau. Tuy nhiên, các tính toán nơron lại cho phép giải quyết tốt các bài toán có nhiều tương tác phức tạp. Vì vậy, ứng dụng mạng nơron trong bài toán xác định lộ trình cho robot sẽ hứa hẹn là một giải pháp hiệu quả góp phần nâng cao hiệu năng làm việc của robot nhờ khả năng di chuyển nhanh chóng, chính xác trong các môi trường làm việc của mình.

Trên thế giới, đã có một số nghiên cứu ứng dụng mạng nơron trong bài toán lập lộ trình cho robot. Tuy nhiên, lĩnh vực này còn khá mới mẻ và chưa được ứng dụng rộng rãi ở nước ta. Trong nước cũng chưa có một tài liệu chính thống nào về lĩnh vực này. Với những ứng dụng ngày càng rộng rãi của công nghệ robot, việc nghiên cứu và áp dụng những thành tựu mới của công nghệ thông tin vào thiết kế và cải tiến các kỹ năng trong đó có kỹ năng tránh các vật cản khi di chuyển là một trong những vấn đề nóng đang rất được quan tâm. Chính vì những lý do trên em đã quyết định chọn đề tài: “Ứng dụng mạng nơron trong bài toán xác định lộ trình cho robot” Với mục đích tìm
hiểu về mạng nơron nhân tạo và bài toán lập lộ trình cho robot, ứng dụng mạng nơron vào bài toán trên.

Luận văn gồm 3 chương với các nội dung cơ bản sau:

Chương 1: Trình bày tổng quan về cơ sở của mạng nơron nhân tạo, và

nêu khái quát những ứng dụng của mạng nơron trong công nghệ robot.

Chương 2: Trình bày: bài toán lập lộ trình và những thành phần của

nó, không gian cấu hình, cấu hình chướng ngại vật.

Chương 3: Trình bày: hương pháp lập lộ trình của Yang và Meng, cải tiến mô hình nguyên bản do Yang và Meng đề xuất, cài đặt thử nghiệm hai mô hình đã trình bày, đưa ra những nhận xét về hiệu quả của hai mô hình đó.

Mặc dù đã hết sức nỗ lực, song do thời gian và kinh nghiệm nghiên cứu khoa học còn hạn chế nên không thể tránh khỏi những thiếu sót. Em rất mong nhận được sự góp ý của các thầy cô và bạn bè đồng nghiệp để hiểu biết của mình ngày một hoàn thiện hơn.

Qua luận văn này em xin chân thành cảm ơn: PGS .TS Đặng Quang Á - Viện Công nghệ thông tin đã tận tình giúp đỡ, động viên, định hướng, hướng dẫn em nghiên cứu và hoàn thành luận văn này. Em xin cảm ơn các thầy cô giáo trong viện Công nghệ thông tin, các thầy cô giáo khoa Công nghệ thông tin ĐH Thái nguyên, đã giảng dạy và giúp đỡ em trong hai năm học qua, cảm ơn sự giúp đỡ nhiệt tình của các bạn đồng nghiệp .





MỤC LỤC


1
MỤC LỤC
DANH MỤC HÌNH 4
LỜI NÓI ĐẦU 6
CHưƠNG 1 TỔNG QUAN MẠNG NƠRON NHÂN TẠO 8
1.1. Giới thiệu mạng nơron 8
1.1.1. Những kiến trúc tính toán . 8
1.1.2. Lịch sử phát triển của mạng nơron . 9
1.1.3. Nơron sinh học 11
1.1.4. Nơron nhân tạo 12
1.1.5. Mạng nơron nhân tạo 14
1.1.6. Tiếp cận nơron trong tính toán 18
1.2. Phạm vi ứng dụng của mạng nơron 22
1.2.1. Những bài toán thích hợp 22
1.2.2. Các lĩnh vực ứng dụng của mạng nơron . 24
1.2.3. ưu nhược điểm của mạng nơron 25
1.3. Mạng Hopfield . 26
1.3.1. Mạng Hopfield rời rạc . 28
1.3.2. Mạng Hopfiel liên tục . 28
1.4. Mạng nơron trong kỹ thuật robot . 29
1.5. Nhận xét . 30
CHưƠNG 2 GIỚI THIỆU BÀI TOÁN LẬP LỘ TRÌNH CHO ROBOT 32
2.1. Giới thiệu robot nhân tạo . 32
2.1.1. Tổng quan . 32
2.1.2. Giải pháp thiết kế 33
2.2. Bài toán lập lộ trình 34
2.2.1. Mở đầu 34
2.2.2. Các ví dụ thực tế . 37
2.2.3. Bài toán lập lộ trình chuyển động cho robot 39
2.3. Các thành phần cơ bản của việc lập lộ trình 40
2.3.1. Trạng thái 40
2.3.2. Thời gian . 40
2.3.3. Hành động . 41
2.3.4. Trạng thái đầu và trạng thái kết thúc 41
2.3.5. Tiêu chuẩn 41
2.3.6. Giải thuật 42
2.3.7. Người lập lộ trình 42
2.3.8. Lộ trình . 42
2.3.9. Lập lộ trình chuyển động 46
2.4. Không gian cấu hình . 46
2.4.1. Các khái niệm không gian cấu hình 46
2.4.2. Mô hình cấu hình 47
2.4.3. Không gian cấu hình chướng ngại 56
2.4.4. Định nghĩa chính xác về vấn đề lập lộ trình . 58
CHưƠNG 3 ỨNG DỤNG MẠNG NƠRON NHÂN TẠO TRONG BÀI TOÁN
LẬP LỘ TRÌNH CHO ROBOT . 60

3.1. Mạng nơron nhân tạo và bài toán lập lộ trình 60

3.2. Ứng dụng mạng Hopfield giải bài toán lập lộ trình . 62

3.2.1. Khái quát một số phương pháp lập lộ trình . 62
3.2.2. Phương pháp do Yang và Meng đề xuất 63
3.2.3. Mô hình Yang và Meng cải tiến 67
3.3. Các kết quả thử nghiệm 69
3.3.1. Chương trình Đềmô . 69
3.3.2. So sánh các kết quả 71
3.3.3. Kết luận 73
KẾT LUẬN . 75
TÀI LIỆU THAM KHẢO 76
PHỤ LỤC 77



DANH MỤC HÌNH


Hình 1.1: Mô hình nơron sinh học 11
Hình 1.2: Mô hình một nơron nhân tạo 14
Hình 1.3: Mô hình mạng truyền thẳng 1 lớp 16
Hình 1.4: Mô hình mạng truyền thẳng nhiều lớp . 17
Hình 1.5: Mạnh hồi quy 1 lớp có nối ngược 17
Hình 1.6: Mạnh hồi quy nhiều lớp có nối ngược . 18
Hình 1.7: Mô hình mạng Hopfield . 27
Hình 2.1: Các thành phần cấu thành Robot 34
Hình 2.2: Khối Rubitc (a); bài toán dịch chuyển số (b) . 36
Hình 2.3: Giải thuật kéo 2 thanh thép tách ra . 37
Hình 2.4: Sử dụng Robot di động để di chuyển Piano . 38
Hình 2.5: (a) người lập lộ trình thiết kế giải thuật lập lộ trình . 43
(b) Người lập lộ trình thiết kế toàn bộ máy . 43

Hình 2.6: Một số lộ trình và sự cải tiến lộ trình . 44

Hình 2.7: Mô hình có thứ bậc 1 máy có thể chứa đựng 1 máy khác 45

Hình 2.8: Không gian cấu hình . 47

Hình 2.9: Một Robot điểm di chuyển trong không gian 2D, C – Space là
R2 48

Hình 2.10: Một Robot điểm di chuyển trong không gian 3D, C – Space
là R3 48

Hình 2.11: Một đa thức lồi có thể được xác định bởi phép giao của các
nửa mặt phẳng . 49

Hình 2.12: Dấu hiệu của f(x,y) phân chia R2 thành 3 vùng: f(x,y) <0, f(x,y) >0, f(x,y) =0 50
Hình 2.13: (a)Đa diện. (b)Biểu diễn các cạnh của một mạt trong đa diện 53



Hình 2.14: (a) Sử dụng f để phân chia R2 thành 2 vùng. (b) Sử dụng màu
đạ số để mô hình hoá vùng mặt 54

Hình 2.15: Biểu thị một đa giác với những lỗ. Ngược chiều kim đồng hồ
cho biên ngoài và thuận chiều kim đồng hồ cho biên trong . 55

Hình 2.16: C – Space và nhiệm vụ tìm đường từ qI đến qG trong Cfree.
C = Cfree  Cobs . 57

Hình 3.1: Giao diện chương trình mô hình nguyên bản . 69

Hình 3.2: Giao diện chương trình mô hình cải tiến . 69

Hình 3.3: Mê cung 1 . 71

Hình 3.4: Mê cung 2 . 72

Hình 3.5: Mê cung 3 . 72