« Home « Kết quả tìm kiếm

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ĐINH THỊ THUÝ QUỲNH ỨNG DỤNG MẠNG NƠRON TRONG BÀI TOÁN XÁC ĐỊNH LỘ TRÌNH CHO ROBOT LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Tóm tắt Xem thử

- ĐINH THỊ THUÝ QUỲNH ỨNG DỤNG MẠNG NƠRON TRONG BÀI TOÁN XÁC ĐỊNH LỘ TRÌNH CHO ROBOT LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN THÁI NGUYÊN - 2008 ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN.
- 30 CHƢƠNG 2 GIỚI THIỆU BÀI TOÁN LẬP LỘ TRÌNH CHO ROBOT.
- Bài toán lập lộ trình.
- Bài toán lập lộ trình chuyển động cho robot.
- Các thành phần cơ bản của việc lập lộ trình.
- Ngƣời lập lộ trình.
- Lộ trình.
- Lập lộ trình chuyển động.
- Đị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.
- Mạng nơron nhân tạo và bài toán lập lộ trình.
- Ứng dụng mạng Hopfield giải bài toán lập lộ trình.
- Khái quát một số phƣơng pháp lập lộ trình.
- 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.
- 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.
- 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 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 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.
- 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.
- Mô hình nơron sinh học 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Hoạt động của nơron sinh học có thể đƣợc mô tả nhƣ sau: Mỗi nơron nhận tín hiệu vào từ các tế bào thần kinh khác.
- 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn  Các mạng nơron có thể cung cấp những kiến trúc tính toán thông qua đào tạo hơn là thiết kế.
- Giải pháp giải quyết bài toán phân loại trong lộ trình di chuyển của ngƣời máy là succesfully phƣơng pháp này có nền tảng là mạng nơron cạnh tranh ( Bekey, G.A.
- Có thể nói việc ứng dụng mạng nơron để lập lộ trình di chuyển cho robot sẽ giúp cho robot di chuyển linh hoạt hơn và đây cũng là một công việc quan trọng trong kỹ thuật robot.
- 31 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn CHƢƠNG 2 GIỚI THIỆU BÀI TOÁN LẬP LỘ TRÌNH CHO ROBOT 2.1.
- Các thành phần cấu thành nên robot có thể đƣợc mô hình hoá bởi sơ đồ sau: 33 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Trạng thái về môi trƣờng, sensor, vật cản,...=>Data Các tác vụ cơ bản.
- BÀI TOÁN LẬP LỘ TRÌNH.
- Một trong những giải thuật nhƣ vậy là giải thuật lập lộ trình chuyển động cho robot.
- Ta có thể hình dung việc lập lộ trình tƣơng tự nhƣ bài toán di chuyển một chiếc piano.
- 35 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn  Trong trí tuệ nhân tạo: Thuật ngữ lập lộ trình AI lại thể hiện những đặc điểm riêng biệt.
- Muốn hiểu sâu sắc về các giải thuật lập lộ trình ta phải trả lời đƣợc các câu hỏi.
- Thế nào là một lộ trình.
- Một lộ trình đƣợc mô tả nhƣ thế nào.
- Đối tƣợng nào sẽ sử dụng nó? Có thể nói lập lộ trình là một công việc khá phức tạp vì vậy đòi hỏi phải nghiên cứu và đƣa ra những giải pháp (giải thuật) hợp lý để giải quyết 36 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn bài toán này.
- Bài toán này đã đƣợc Nancy Amato xây dựng nhƣ là một chuẩn để đánh giá các nghiên cứu về việc lập lộ trình của trƣờng đại học Texas A&M.
- Thậm chí thuật toán lập lộ trình còn đƣợc ứng dụng trong những kỹ thuật máy tính phỏng sinh học nhƣ robot khám bệnh, những mô hình hình học ứng dụng tới từng phân tử cũng có thể đƣợc giải quyết bởi giải thuật lập lộ trình.
- Bài toán lập lộ trình có thể đƣợc phát biểu nhƣ sau: Cho đối tƣợng với vị trí ban đầu và vị trí đích với một tập các chƣớng ngại vật có các vị trí khác nhau trong không gian làm việc.
- Quá trình xác định lộ trình thƣờng chia làm hai thao tác chính đó là: xây dựng không gian cấu hình và tìm đƣờng.
- Cụ thể việc lập lộ trình gồm những thành phần cơ bản sau: 2.3.1.
- Trạng thái của bài toán lập lộ trình là một hình trạng của bài toán nó chính là vị trí tƣơng đối của robot với các đối tƣợng trong môi trƣờng di chuyển - Không gian trạng thái gồm tất cả các hình trạng có thể xuất hiện.
- Việc xây dựng không gian trạng thái hoàn toàn phụ thuộc vào thuật toán lập lộ trình tƣơng ứng.
- Tuy nhiên, định nghĩa không gian trạng thái vẫn là một thành phần quan trọng trong việc trình bày, phân tích, thiết kế những giải thuật để giải quyết bài toán lập lộ trình.
- Thời gian Toàn bộ vấn đề lập lộ trình là những dãy quyết định đƣợc thực hiện trong suốt thời gian thực hiện.
- Thời gian lập lộ trình ảnh hƣởng đến các quyết định liên tiếp trong quá trình xác lập lộ trình.
- Điều này làm nảy sinh những hành động nhƣng ta hoàn toàn có thể ƣớc đoán để ứng dụng vào vấn đề lập lộ trình.
- Tiêu chuẩn Ta sẽ đánh giá các thuật toán lập lộ trình dựa trên hai tiêu chuẩn sau.
- Giải thuật Giải thuật là một thành phần quan trọng không thể thiếu trong công việc lập lộ trình.
- Nó là nền tảng để xác định nhanh chóng, chính xác một lộ trình di chuyển của robot.
- Người lập lộ trình Một ngƣời lập lộ trình có thể hiểu là đối tƣợng tạo nên lộ trình, nó có thể là máy móc hoặc con ngƣời.
- Nếu ngƣời lập lộ trình là một máy, thì nó sẽ đƣợc xem nhƣ một giải thuật lập lộ trình.
- Mô hình lập lộ trình đã cho đƣợc đƣa tới cho con ngƣời, và con ngƣời “ tính toán ” một lộ trình tƣơng ứng.
- Khái niệm cơ sở của lộ trình là không gian.
- Để quyết định xem robot có thể đi đƣợc vào đó hay không chúng ta cần tìm hiểu khái niệm Configuation Space ( Cấu hình không gian) 42 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn - Robot: Những vật thể đƣợc mô hình hoá hình học và có thể kiểm soát theo một lộ trình đã lập.
- Hình 2.5 : (a) Người lập lộ trình thiết kế giải thuật lập lộ trình.
- b) Người lập lộ trình thiết kế toàn bộ máy.
- Khi sử dụng một lộ trình ta cần quan tâm đến những khái niệm sau: 1.
- Cải tiến : Cải tiến nó để có đƣợc một lộ trình tốt hơn.
- Mô hình có thứ bậc : Coi lộ trình nhƣ một hành động của một lộ trình ở mức độ cao hơn.
- Những khái niệm này có thể đƣợc giải thích kỹ hơn nhƣ sau: Sự thực thi: Một lộ trình thông thƣờng đƣợc thực thi bởi một máy.
- Một con ngƣời cũng có thể thực thi một lộ trình.
- Tuy nhiên, trong trƣờng hợp này chúng ta tập trung nghiên cứu quá trình thực hiện lộ trình trên máy.
- Tất nhiên, mô hình này có thể đƣợc mở rộng cho phép cải tiến qua thời gian để nhận những lộ trình tốt hơn.
- Cách tiếp cận này đã có trong những lộ trình thực 43 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn tế, tuy nhiên, chúng chƣa đƣợc ƣa chuộng bởi những lộ trình cần phải thiết kế trƣớc để tính đến thông tin mới trong thời gian thực thi.
- Lộ trình mới này tính đến nhiều khía cạnh của vấn đề hơn, hoặc nó có thể đơn giản và hiệu quả hơn.
- Một số lộ trình và sự cải tiến lộ trình Ví dụ.
- Mô hình thứ bậc: Một lộ trình đƣợc coi nhƣ một hoạt động của một lộ trình lớn hơn.
- Hình 2.7: Mô hình có thứ bậc, một máy có thể chứa đựng một máy khác 45 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lộ trình nguyên bản có thể hình dung nhƣ một chƣơng trình con trong lộ trình lớn hơn.
- Mô hình có thứ bậc có thể đƣợc biểu diễn với bất kỳ số lộ trình nào, kết quả của mỗi lộ trình sẽ đƣợc lƣu trong một nút của cây lộ trình.
- Nhƣ vậy mô hình chung của lộ trình có thứ bậc là một cây trong đó mỗi đỉnh của cây là một lộ trình.
- Đỉnh gốc là lộ trình chính.
- Con của một đỉnh bất kỳ là một lộ trình con.
- Trong việc lập lộ trình có thứ bậc, dòng tƣơng tác giữa máy và môi trƣờng đƣợc vẽ nhiều hƣớng.
- Lập lộ trình chuyển động Đây là nguồn cảm hứng chính cho những vấn đề và tất cả các giải thuật của kỹ thuật rôbôt.
- Một cách nói khác chính xác hơn cho việc lập lộ trình chuyển động là “ Lập lộ trình trong không gian liên tục ” 2.4.
- City College of New York 17 Để có thể thực hiện đƣợc các giải thuật lập lộ trình ta cần phải biểu diễn đƣợc không gian cấu hình vào máy.
- 49 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Không mất tính tổng quát ta có thể giả thiết f(x,y.
- Không gian cấu hình chướng ngại Một giải thuật lập lộ trình chuyển động phải tìm thấy một đƣờng dẫn trong không gian rỗng (Free Space) từ cấu hình ban đầu(qI) đến cấu hình đích (qG).
- Định nghĩa chính xác về vấn đề lập lộ trình chuyển động.
- Cuối cùng ta đã đủ công cụ để định nghĩa chính xác vấn đề lập lộ trình.
- 59 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 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.
- MẠNG NƠRON NHÂN TẠO VÀ BÀI TOÁN LẬP LỘ TRÌNH.
- Trong kỹ thuật robot thì việc xác định lộ trình là một công việc quan trọng.
- Ta có thể hiểu khái quát bài toán xác định lộ trình nhƣ sau: Cho đối tƣợng với vị trí ban đầu và vị trí đích với một tập các chƣớng ngại vật có các 60 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vị trí khác nhau trong không gian làm việc.
- Thông thƣờng quá trình xác định lộ trình có thể chia làm hai thao tac chính, đó là: xây dựng không gian tìm kiếm và tìm đƣờng.
- Ta có thể tham khảo các cách tiếp cận liên quan tới việc lập lộ trình chuyển động trong (Latombe, J.C1991.
- Do đó, giải pháp sử dụng mạng nơron giải quyết bài toán lập lộ trình là một hƣớng đi đúng đắn.
- Chƣơng này, sẽ giới thiệu một số cách tiếp cận sử dụng mạng nơron để lập lộ trình cho robot di chuyển tự do giữa những chƣớng ngại vật đã biết trong cấu trúc môi trƣờng hoạt động của robot.
- ỨNG DỤNG MẠNG HOPFIELD GIẢI QUYẾT BÀI TOÁN LẬP LỘ TRÌNH CHO ROBOT.
- Khái quát một số phương pháp lập lộ trình và khả năng ứng dụng của mạng Hopfield.
- Một trong những vấn đề then chốt của hệ thống robot di động là lập lộ trình chuyển động trong thời gian thực.
- Những cách tiếp cận Mạng Nơron đã đƣợc sử dụng trong khá nhiều thuật toán lập lộ trình và phần này sẽ trình bày cách tiếp cận dựa trên 62 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn mạng nơron hồi quy Hopfield.
- qp = q n B3: Nếu qp=qG thì + Thông báo xác định thành công một lộ trình Ngƣợc lại + Thông báo không xác định đƣợc lộ trình B4: Kết thúc Nhận xét: 65 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Trƣớc khi thảo luận về những kết quả của phƣơng pháp đang nghiên cứu, ta nên xem xét các phƣơng trình ( 3.1.
- qp = q n + Xác định giá trị ngƣợc Tn + In= Tn B3: Nếu qp=qG thì + Thông báo xác định thành công một lộ trình Ngƣợc lại + Thông báo không xác định đƣợc lộ trình B4: Kết thúc 68 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3.3.
- 69 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn + Nút tạo mê cung: Sau khi click vào nút này ta có thể click vào các ô trên lƣới để tạo mê cung.
- Robot 1 sử dụng phƣơng pháp lập lộ trình do Yang và Meng đề xuất.
- Robot 2 sử dụng mô hình cải tiến để xác định lộ trình.
- Mô hình nguyên bản có thể không xác định đƣợc lộ trình mặc dù thực tế lộ trình vẫn tồn tại.
- Phƣơng pháp cải tiến sẽ luôn xác định đƣợc một lộ trình nếu tồn tại đƣờng đi từ vị trí đầu đến vị trí đích.
- Phƣơng pháp này cho phép robot xác định đƣợc lộ trình và tránh đƣợc bẫy trên đƣờng di chuyển.
- 74 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn KẾT LUẬN Trong luận văn “Ứng dụng mạng nơron trong bài toán xác định lộ trình cho robot” em đã hoàn thành những nhiệm vụ sau: 1.
- Đã trình bày khái quát về một phƣơng pháp thiết kế một mobile robot, bài toán lập lộ trình và các thành phần của nó.
- Đã trình bày về cấu hình không gian và cấu hình chƣớng ngại vật, một trong những công việc khá phức tạp khi xác định lộ trình cho robot bằng phƣơng pháp truyền thống 4.
- Đã nghiên cứu về phƣơng pháp lập lộ trình dựa vào mạng nơron do Yang và Meng đề xuất và phƣơng pháp cải tiến dựa trên mô hình nguyên bản của Yang và Meng