ĐẠ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 THÁI NGUYÊN - 2008 ĐẠ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 Chuyên ngƠnh: Khoa học máy tính Mƣ số: 60.48.01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA H C: PGS – TS ĐẶNG QUANG Á THÁI NGUYÊN - 2008 MỤC LỤC 1 M CL 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 1 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 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 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 2.3.7. Ng 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 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 ng trình Đềmô......................................................... 69 3.2.2. Ph 3.3.1. Ch 2 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.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 3 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 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 4 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 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....................... Hình 2.16: C – Space vƠ nhiệm vụ tìm đ 55 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 5 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 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 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. 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 . THÁI NGUYÊN 11/2008 Ng i viết luận văn Đinh Thị Thuý Quỳnh 7 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 I TỔNG QUAN MẠNG NƠRON NHÂN TẠO 1.1. GI I THIỆU MẠNG NƠRON 1.1.1 Những kiến trúc tính toán Khái niệm tính toán có thể đ ợc hiểu theo nhiều cách. Tr ớc đơy, việc tính toán bị ảnh h ng b i quan niệm tính toán theo ch ng trình (Programed computing). Theo quan điểm nƠy, để giải quyết bƠi toán thì b ớc đầu tiên ta cần thiết kế giải thuật sau đó cƠi đặt giải thuật đó trên cấu trúc hiện hƠnh có u thế nhất. Quan sát các hệ sinh học, đặc biệt lƠ bộ nƣo ng i ta thấy chúng có những đặc điểm sau: (1) Bộ nƣo tích hợp vƠ l u trữ kinh nghiệm: Tức lƠ bộ nƣo có khả năng tự phơn loại vƠ liên kết các dữ liệu vƠo. (2) Bộ nƣo xem xét kinh nghiệm mới dựa trên những kinh nghiệm đƣ l u trữ. (3) Bộ nƣo có khả năng dự đoán chính xác những tình huống mới dựa trên những kinh nghiệm tự tổ chức tr ớc đơy. (4) Bộ nƣo không yêu cầu thông tin hoƠn hảo. (5) Bộ nƣo thể hiện một kiến trúc chấp nhận lỗi tức lƠ có thể khôi phục sự mất đi của một vƠi noron bằng cách thích nghi với noron còn lại hoặc bằng cách đƠo tạo bổ xung. (6) C chế hoạt động của bộ nƣo đôi khi không rõ rƠng trong vận hƠnh. Ví dụ với một số bƠi toán chúng ta có thể cung cấp nghiệm nh ng không thể giải thích đ ợc các b ớc tìm nghiệm. 8 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 (7) Bộ nƣo có khuynh h ớng đ a ra những giải pháp trong một trạng thái cơn bằng hoặc có khuynh h ớng dẫn đến trạng thái đó Từ đó ta nhận thấy, tính toán dựa trên các hệ sinh học khác với tính toán theo ch ng trình các đặc điểm sau: - Quá trình tính toán đ ợc tiến hƠnh song song vƠ phơn tán trên nhiều noron - Tính toán thực chất lƠ quá trình học chứ không phải theo một s đồ định sẵn từ tr ớc. Dựa trên nhữnh đặc điểm nƠy một ph ng pháp tính toán mới có nền tảng từ sinh học lƠ mạng noron nhơn tạo (Artifical Neural Networks_ ANNs) đƣ ra đ i vƠ có tiềm năng tr thƠnh kiến trúc tính toán chiếm u thế. 1.1.2 Lịch sử phát triển c a m ng noron. Mạng noron nhơn tạo đ ợc xơy dựng từ những năm 1940 nhằm mô phỏng một số chức năng của bộ nƣo ng nƣo ng i. Dựa trên quan điểm cho rằng bộ i lƠ bộ điều khiển. Mạng noron nhơn tạo đ ợc thiết kế t ng tự nh noron sinh học sẽ có khả năng giải quyết hƠng loạt các bƠi toán nh tính toán tối u, điều khiển, công nghệ robot… Quá trình nghiên cứu vƠ phát triển noron nhơn tạo có thể chia thƠnh 4 giai đoạn nh sau: - Giai đoạn 1: Có thể tính từ nghiên cứu của William (1890) về tơm lý học với sự liên kết các noron thần kinh. Năm 1940 Mc Culloch vƠ Pitts đƣ cho biết noron có thể mô hình hoá nh thiết bị ng ỡng (Giới hạn) để thực hiện các phép tính logic vƠ mô hình mạng noron của Mc Culloch – Pitts cùng với giải thuật huấn luyện mạng của Hebb ra đ i năm 1943. 9 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 - Giai đoạn 2: vƠo khoảng gần những năm 1960, một số mô hình noron hoƠn thiện h n đƣ đ ợc đ a ra nh : Mô hình Perceptron của Rosenblatt (1958), Adalile của Widrow (1962). Trong đó mô hình Perceptron rất đ ợc quan tơm vì nguyên lý đ n giản, nh ng nó cũng có hạn chế vì nh Marvin Minsky vƠ Seymour papert của MIT ( Massachurehs Insritute of Technology) đƣ chứng minh nó không dùng đ ợc cho các hƠm logic phức (1969). Còn Adaline lƠ mô hình tuyến tính, tự chỉnh, đ ợc dùng rộng rƣi trong điều khiển thích nghi, tách nhiễu vƠ phát triển cho đến nay. - Giai đoạn 3: Có thể tính vƠo khoảng đầu thập niên 80. Những đóng góp lớn cho mạng noron trong giai đoạn nƠy phải kể đến Grossberg, Kohonen, Rumelhart vƠ Hopfield. Trong đó đóng góp lớn của Hopfield gồm hai mạng phản hồi: Mạng r i rạc năm 1982 vƠ mạng liên tục năm 1984. Đặc biệt, ông đƣ dự kiến nhiều khả năng tính toán lớn của mạng mƠ một n ron không có khả năng đó. Cảm nhận của Hopfield đƣ đ ợc Rumelhart, Hinton vƠ Williams đề xuất thuật toán sai số truyền ng ợc nổi tiếng để huấn luyện mạng noron nhiều lớp nhằm giải bƠi toán mƠ mạng khác không thực hiện đ ợc. Nhiều ứng dụng mạnh mẽ của mạng noron ra đ i cùng với các mạng theo kiểu máy Boltzmann vƠ mạng Neocognition của Fukushima. - Giai đoạn 4: Tính từ năm 1987 đến nay, hƠng năm thế giới đều m hội nghị toƠn cầu chuyên ngƠnh n ron IJCNN (International Joit Conference on Neural Networks). Rất nhiều công trình đ ợc nghiên cứu để ứng dụng mạng n ron vƠo các lĩnh vực nh : Kỹ thuật tính, điều khiển, bƠi toán tối u, y học, sinh học, thống kê, giao thông, hoá học,...Cho đến nay mạng n ron đƣ tìm vƠ khẳng định đ ợc vị trí của mình trong rất nhiều ứng dụng khác nhau. 10 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 1.1.3. N ron sinh học. Hệ thần kinh gồm hai lớp tế bƠo: N ron (tế bƠo thần kinh) vƠ glia (tế bƠo glia). N ron lƠ thƠnh phần c bản của hệ thần kinh, chúng có chức năng xử lý thông tin. Glia thực hiện chức năng hỗ trợ. Vì vậy tr ớc khi nghiên cứu về n ron nhơn tạo chúng ta sẽ trình bƠy khái quát về cấu tạo vƠ hoạt động của n ron sinh học. N ro sinh học có nhiều loại, chúng khác nhau về kích th ớc vƠ khả năng thu phát tín hiệu. Tuy nhiên chúng có cấu trúc vƠ nguyên lý hoạt động chung nh sau: Mỗi n ron sinh học gồm có 3 thƠnh phần: Thơn n ron với nhơn bên trong (soma), một đầu dơy thần kinh ra (axon) vƠ một hệ thống phơn nhánh hình cơy (Dendrite) để nhận các thông tin vƠo. Trong thực tế có rất nhiều dơy thần kinh vƠo vƠ chúng bao phủ một diện tích rất lớn (0,25mm2). Đầu dơy thần kinh ra đ ợc rẽ nhánh nhằm chuyển giao tín hiệu từ thơn n ron tới n ron khác. Các nhánh của đầu dơy thần kinh đ ợc nối với các khớp thần kinh (synapse). Các khớp thần kinh nƠy đ ợc nối với thần kinh vƠo của các n ron khác. Các n ron có thể sửa đổi tín hiệu tại các khớp. Hình ảnh đ n giản của một n ron thể hiện trong hình 1.1. Hình 1.1. 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. Chúng tích hợp các tín hiệu vƠo, khi tổng tín hiệu v ợt quá một ng ỡng nƠo đó chúng tạo tín hiệu ra vƠ gửi tín hiệu nƠy tới các n ron khác thông qua dơy thần kinh. Các n ron liên kết với nhau thƠnh mạng. Mức độ bền vững của các liên kết nƠy xác định một hệ số gọi lƠ trọng số liên kết. 1.1.4. N ron nhơn t o. Mô phỏng n ron sinh học, ta có n ron nhơn tạo. Mỗi n ron có rất nhiều dơy thần kinh vƠo, nghĩa lƠ mỗi n ron có thể tiếp nhận đồng th i nhiều dữ liệu. Giả sử n ron i có N tín hiệu đầu vƠo, mỗi tín hiệu vƠo Sj đ ợc gán một trọng số wij t ng ứng. Ta có thể ớc l ợng tổng tín hiệu đầu vƠo đi vƠo n ron (neti) theo một số dạng sau: (i) Dạng truyến tính neti   wij S j N i 1 (ii) Dạng toƠn ph (1.1) ng neti   wij S 2j N i 1 (iii) (1.2) Dạng mặt cầu neti  p 2  wij ( S j  wij )2 N i 1 (1.3) Trong đó p vƠ wij lần l ợt lƠ bán kính vƠ tơm cầu.  HƠm kích hoạt. HƠm biến đổi tín hiệu đầu vƠo net cho tín hiệu đầu ra out đ ợc gọi lƠ hƠm kích hoạt. HƠm nƠy có đặc điểm lƠ không ơm vƠ bị chặn. Có nhiều dạng 12 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 hƠm kích hoạt. Ng i ta th ng sử dụng một hƠm kích hoạt chung cho toƠn mạng. Một số hƠm kích hoạt th ng đ ợc sử dụng. + HƠm McCuloch-Pitts 1 nÕu net   out  f net    0 nÕu net   (1.4) Trong đó  lƠ ng ỡng. + HƠm McCuloch-Pitts trễ 1 nÕu net  UTP  out  f net   0 nÕu net  LTP  f net  nÕu kh¸c  (1.5) Trong đó UTP>LTP UTP lƠ ng ỡng trên (Upper Trip Point) LTP lƠ ng ỡng d ới (Lower Trip Point) + HƠm Sigmoid. out  f(net)  1 1  e - (net 0) (1.6) Trong đó  >0 lƠ hằng số xác định độ nghiêng của hƠm.  Nút bias: LƠ một nút thêm vƠo nhằm lƠm tăng khả năng thích nghi của mạng n ron trong quá trình học. Trong các mạng n ron có sử dụng bias, mỗi n ron có thể có một trọng số t ng ứng với bias. Trọng số nƠy luôn có giá trị lƠ 1. 13 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ô hình của một nút xử lý (nút thứ i): V1 Wi1 Vj Wij U i   Vi  f ( U i ) Vi WiN VN Hình 1.2. Mô hình một nơron nhân tạo. U i   WijV j   N (1.7) i 1 j i Vi  f i ( U i ) (1.8) Trong đó: Ui lƠ tổng tín hiệu vƠo tại n ron i. Vi lƠ tín hiệu ra tại n ron i. Wij lƠ trọng số liên kết từ n ron i đến n ron j i lƠ ng ỡng (đầu vƠo ngoƠi ) kích hoạt n ron i fi lƠ hƠm kích hoạt của n ron i 1.1.5. M ng n ron nhơn t o Mạng n ron nhơn tạo (Artificial Neural Network) lƠ một cấu trúc mạng đ ợc hình thƠnh nên b i một số l ợng lớn các n ron nhơn tạo liên kết với nhau. Mỗi n ron có các đặc tính đầu vƠo, đầu ra vƠ thực hiện một chức năng tính toán cục bộ. 14 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ới việc giả lập các hệ thống sinh học, các cấu trúc tính toán mạng n ron có thể giải quyết đ ợc lớp các bƠi toán nhất định nh : bƠi toán lập lịch, bƠi toán tìm kiếm, bƠi toán nhận dạng mẫu, bƠi toán xếp loại,... Mạng n ron còn giải quyết đ ợc lớp các bƠi toán sử dụng dữ liệu không đầy đủ, xung đột m hoặc xác suất. Những bƠi toán nƠy đ ợc đặ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; không gian nghiệm có thể rỗng, có nghiệm duy nhất hoặc có một số nghiệm bình đẳng nh nhau. NgoƠi ra, mạng n ron nhơn tạo còn thích hợp để tìm nghiệm của những bƠi toán đòi hỏi đầu vƠo lƠ những cảm nhận b i con ng i nh : Tiếng nói, nhìn vƠ nhận dạng,... Tuy nhiên việc ánh xạ từ một bƠi toán bất kỳ sang một giải pháp mạng n ron lại lƠ một việc không đ n giản. Mạng n ron lƠ một cấu trúc xử lý song song, thông tin phơn tán vƠ có các đặc tr ng nổi bật sau:  LƠ mô hình toán học dựa trên bản chất của n ron sinh học.  Bao gồm một số l ợng lớn các n ron liên kết với nhau.  Mạng n ron có khả năng học, khái quát hoá tập dữ liệu học thông qua việc gán vƠ hiệu chỉnh các trọng số liên kết.  Tổ chức theo kiểu tập hợp mang lại cho mạng n ron khả năng tính toán rất lớn, trong đó không có n ron nƠo mang thông tin riêng biệt. Mạng n ron nhơn tạo có một số mô hình thông dụng sau: a. Mạng truyền thẳng: - Mạng truyền thẳng một lớp: LƠ mô hình liên kết c bản vƠ đ n giản nhất. Các n ron tổ chức lại với nhau tạo thƠnh một lớp, tín hiệu đ ợc truyền theo một h ớng nhất định nƠo đó. Các đầu vƠo đ ợc nối với các n ron theo trọng 15 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 số khác nhau, sau quá trình xử lý cho ra một chuỗi các tín hiệu ra. Nếu mạng lƠ mô hình LTU thì nó đ ợc gọi lƠ mạng perception, còn mạng n ron theo mô hình LGU thì đ ợc gọi lƠ Adaline. x1 y1 x2 y2 xm yn Hình 1.3. Mô hình mạng truyền thẳng một lớp Với mỗi giá trị đầu vƠo x =[x1, x2, ..., xm]T qua quá trình xử lí của mạng sẽ thu đ ợc một bộ đầu ra t ng ứng y =[y1, y2,..., yn]T với ph ng pháp xác định nh sau: yi  f i(  wij x j   i ) m j 1 i  1,n (1.9) Trong đó: m: Số tín hiệu vƠo. n: Số tín hiệu ra. Wi T  [ wi1 , wi 2 ,...,win ] T lƠ véc t trọng số của n ron thứ i. fi: lƠ hƠm kích hoạt của n ron thứ i. : LƠ ng ỡng của n ron thứ i. - Mạng truyền thẳng nhiều lớp: Với cấu trúc đ n giản nh trên, khi giải quyết các bƠi toán phức tạp mạng truyền thẳng một lớp sẽ gặp rất nhiều khó 16 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ăn. Để khắc phục nh ợc điểm nƠy, ng i ta đ a ra mạng truyền thẳng nhiều lớp. Đơy lƠ mạng truyền thẳng gồm nhiều lớp kết hợp với nhau. Lớp nhận tín hiệu gọi lƠ lớp đầu vƠo (input layer), lớp đ a các tín hiệu ra gọi lƠ lớp đầu ra (output layer), các lớp giữa lớp vƠo vƠ lớp ra gọi lƠ lớp ẩn (hidden layers). Cấu trúc của mạng n ron truyền thẳng nhiều lớp đ ợc mô tả trong hình 1.4. Lớp ẩn Lớp vƠo Lớp ra x1 y1 y2 x2 ... ... ... ... xm yn Hình 1.4. Mạng nơron truyền thẳng nhiều lớp.  Mạng hồi quy. - Mạng hồi quy một lớp có nối ng ợc. x1 y1 x2 y2 xN ym Hình 1.5. Mạng hồi quy một lớp có nối ngược. - Mạng hồi quy nhiều lớp có nối ng ợc. 17 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 x1 y1 x2 y2 ... ... ... ... xN yM Hình 1.6. Mạng hồi quy nhiều lớp có nối ngược. 1.1.6. Tiếp c n n ron cho tính toán. 1.1.6.1. Đào tạo và lập trình. NgƠy nay máy tính đ ợc ứng dụng rộng rƣi trong tất cả các lĩnh vực của đ i sống xƣ hội. Giải quyết một bƠi toán bằng máy tính cũng có rất nhiều ph ng pháp khác nhau. Thông th ng, thì ph ng pháp lập trình chiếm u thế. Tuy nhiên lập trình đòi hỏi một cú pháp hình thức vƠ một loạt các ngôn ngữ, cũng nh kỹ năng của con ng i. Một giải pháp điển hình để giải quyết vấn đề trong hệ sinh học lƠ đào tạo. Ví dụ, trẻ con không đ ợc “lập trình” nh ng chúng học theo ví dụ vƠ thích nghi. Dĩ nhiên, để tiếp cận đƠo tạo khả thi, máy tính phải có thể đƠo tạo đ ợc vƠ phải có dữ liệu đƠo tạo. Một trong những giải pháp để giải quyết vấn đề nƠy lƠ sử dụng mạng n ron. Mạng n ron có những đặc điểm nổi bật sau:  Các hệ n ron hoạt động nh các hệ thông tin có thể đƠo tạo đ ợc, thích nghi vƠ thậm chí tự tổ chức.  Các mạng n ron phát triển một chức năng dựa trên dữ liệu đƠo tạo mẫu. 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ế. 1.1.6.2. Luật học Các luật học đóng vai trò quan trọng trong việc xác định một mạng n ron nhơn tạo. Một cách đ n giản về khái niệm học của mạng n ron lƠ cập nhật các trọng số trên c s các mẫu. Theo nghĩa rộng thì học có thể đ ợc chia lƠm hai loại: Học tham số vƠ học cấu trúc. a. Học tham số: Các thủ tục học nƠy nhằm tìm kiếm ma trận trọng số sao cho mạng có khả năng đ a ra dự báo sát với thực tế. Dạng chung của luật học tham số có thể đ ợc mô tả nh sau: Wij  rx j ,i  1, N ; j  1, M Tron đó: Wij lƠ sự thay đổi trọng số liên kết từ n ron j đến n ron i. xj lƠ tín hiệu vƠo n ron j.  lƠ tốc độ học nằm trong khoảng (0,1). r lƠ hằng số học. Vấn đề đặt ra đơy lƠ tín hiệu học r đ ợc sinh ra nh thế nƠo để hiệu chỉnh trọng số của mạng. Có thể chia học tham số ra thƠnh ba lớp nhỏ h n: Học có chỉ đạo, học tăng c ng vƠ học không có chỉ đạo. Việc xác định r phụ thuộc vƠo từng kiểu học. - Học có tín hiệu chỉ đạo: LƠ quá trình mạng học dựa vƠo sai số giữa đầu ra thực vƠ đầu ra mong muốn để lƠm c s cho việc hiệu chỉnh trọng số. Sai số nƠy chính lƠ hằng số học r. Luật học điển hình của nhóm nƠy lƠ luật 19 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 Delta của Widrow(1962) nêu ra dùng để xấp xỉ trọng số của Adaline dựa trên nguyên tắc giảm gradient. Trong nhóm luật học nƠy cũng cần phải kể đến luật học perceptron của Rosenblatt(1958). Về c bản luật học nƠy thay đổi các giá trị trọng số trong th i gian học, còn luật perceptron thì thêm hoặc bỏ trọng số tuỳ theo giá trị sai số lƠ d ng hay ơm. Một loạt các luật học khác cũng dựa trên t t ng nƠy. Luật Oja lƠ cải tiến vƠ nơng cấp của luật Delta. Luật truyền ng ợc lƠ m rộng của luật Delta cho mạng nhiều lớp. Đối với mạng truyền thẳng th ng sử dụng luật truyền ng ợc để chỉnh trọng số với tín hiệu chỉ đạo từ bên ngoƠi vƠ ng i ta gọi mạng nƠy lƠ mạng lan truyền ng ợc. - Học không có tín hiệu chỉ đạo: Luật học nƠy sử dụng đầu ra của mạng lƠm c s để hiệu chỉnh các trọng số liên kết. Hay trong luật nƠy chính lƠ tín hiệu ra của mạng. Điển hình lƠ luật Hebb(1949) th ng dùng cho các mạng tự liên kết. Luật LVQ (learning Vector Quantization) dùng cho mạng tự tổ chức một lớp mạng ánh xạ đặc tr ng của Kohonen. Luật học Hebb lƠ luật sinh học xuất phát từ tiên đề của Hebb cho rằng: Giữa hai n ron có quan hệ vƠ có thay đổi thế năng mạng thì giữa chúng có sự thay đổi trong số liên kết. Nói cách khác trọng số đ ợc điều chỉnh theo mối t ng quan tr ớc vƠ sau, nghĩa lƠ: Wij  yi x j , i  1, N , j  1, M (1.11) Trong đó: Wij lƠ sự thay đổi trọng số liên kết từ n ron i đến n ron j. xj lƠ tín hiệu vƠo n ron j 20 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 yi lƠ tín hiệu ra của n ron i.  lƠ tố độ học, nằm trong khoảng(0,1). Luật Hebb giải thích việc chỉnh trọng số trong phạm vi cục bộ của mạng mƠ không cần tín hiệu chỉ dạo từ bên ngoƠi. Hopfield cũng cải tiến luật Hebb cho các mạng tự liên kết thƠnh 16 dạng khác nhau theo kiểu luật Hebb, luật đối Hebb, luật Hopfield,... Nh vậy ứng với mỗi nhóm mạng th ng áp dụng một luật học nhất định. Nếu tồn tại hƠng chục loại mạng khác nhau thì số luật học có thể tăng lên rất nhiều lần. Đối với mạng phản hồi th ng sử dụng luật Hebb vƠ các luật cải tiến của nó để chỉnh trọng số mƠ không cần tín hiệu chỉ đạo từ bên ngoƠi. - Học tăng cường: Trong một số tr ng hợp, thông tin phản hồi chỉ lƠ tín hiệu bao gồm hai trạng thái cho biết tín hiệu đầu ra của mạng lƠ đúng hay sai. Quá trình học dựa trên các thông tin h ớng dẫn nh vậy đ ợc gọi lƠ học có củng cố (học tăng c ng) vƠ tín hiệu mang thông tin phản hồi đ ợc gọi lƠ tín hiệu củng cố cho quá trình học. Ta có thể thấy rằng quá trình học nƠy lƠ một dạng của quá trình học có tín hiệu chỉ đạo b i vì mạng nhận đ ợc một số thông tin phản hồi từ bên ngoƠi. b. Học cấu trúc: Tìm kiếm các tham số của cấu trúc mạng để tìm ra một cấu trúc mạng hoạt động tốt nhất. Trong thực tế việc học cấu trúc lƠ tìm ra số lớp ẩn vƠ tìm ra số n ron trong mỗi lớp đó. Giải thuật di truyền th dụng trong các cấu trúc nh ng th ng đ ợc sử ng chạy rất lơu, thậm chí ngay cả đối với mạng có kích th ớc trung bình. NgoƠi ra kỹ thuật gọt tỉa mạng hay mạng tăng dần cũng đ ợc áp dụng trong việc học cấu trúc của mạng có kích th ớc t ng đối nhỏ. 21 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 1.2. PHẠM VI ỨNG DỤNG C A MẠNG NƠRON. 1.2.1. Những bƠi toán thích h p. Mạng n ron đ ợc coi nh một hộp đen để biến đổi véc t đầu vƠo m biến thƠnh vect đầu ra n biến. Tín hiệu ra có thể lƠ các tham số thực (tốt nhất nằm trong khoảng [0,1], hoặc [-1,1], số nhị phơn 0,1, hay số l ỡng cực -1, +1). Số biến của vect ra không hạn chế song sẽ ảnh h ng tới th i gian tính vƠ tải nguyên liệu của máy tính. Nói chung, các lớp bƠi toán áp dụng cho n ron có thể phơn chia lƠm 4 loại: - Phơn lớp (clasification). - Mô hình hoá (modening). - Biến đổi, thực hiện ánh xạ từ không gian đa biến nƠy vƠo không gian đa biến khác t ng ứng (transformation add mapping). - Liên kết vƠ kỹ thuật dịch chuyển cửa sổ (asosiation and moving window). 1.2.1.1. Phân loại. Một trong các công việc đ n giản vƠ th ng đ ợc sử dụng nhiều trong quản lý các đối t ợng đa biến lƠ phơn loại (phơn lớp một đối tuợng vƠo các nhóm, nhóm con hay chủng loại). Ví dụ: bƠi toán phơn lớp ảnh, nhận dạng mẫu,... Khi phải phơn loại một quyết định phức tạp, chúng ta phải bắt đầu với việc nghiên cứu, thống kê các mối liên quan giữa nhiều đối t ợng. Có thể nói việc xơy dựng một cơy phơn lớp vƠ các quyết định phải đ ợc thực hiện tr ớc khi thủ tục học đ ợc tiến hƠnh. Nếu kết quả cuối cùng không thoả mƣn, chúng ta cần phải xem xét lại cách biểu diễn các đối t ợng hoặc cơy phơn lớp hoặc thay đổi cả hai. 22 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 1.2.1.2. Mô hình hoá. Các hệ thống phơn loại đ a ra các cơu trả l i r i rạc nh có, không hoặc một số nguyên định danh các đối t ợng đầu vƠo thuộc lớp nƠo. Mô hình hoá yêu cầu hệ thống phải sản sinh ra các cơu trả l i mang tính liên tục. Trong quá trình mô hình hoá cần một số l ợng nhỏ các số liệu để xơy dựng mô hình. Mô hình nƠy có thể đ a ra các dự báo cho tất cả các đối t ợng đầu vƠo. Việc tìm ra đ ng cong phù hợp với các số liệu thực nghiệm lƠ một trong những ứng dụng thuộc dạng nƠy. Trong bất kỳ loại mô hình nƠo cũng phải tuơn theo một giả định lƠ: Các thay đổi nhỏ của tín hiệu vƠo chỉ gơy ra những biến đổi nhỏ của tín hiệu ra. Trong các vấn đề đa biến mạng n ron có nhiều u thế h n so với các mô hình hoá cổ điển sử dụng các hƠm giải tích. B i vì trong ph ng pháp mô hình hoá cổ điển, đối với mỗi đầu ra ta phải xác định một hƠm cụ thể cùng một bộ các tham số. Trong khi đó đối với mạng n ron thì không phải quan tơm tới những hƠm đó. Tuy nhiên, trong các ph ng pháp mô hình hoá cổ điển, các hệ số có thể có một số ý nghĩa nƠo đó đối với vấn đề cần giải quyết, trái lại các trọng số của mạng không mang một ý nghĩa nƠo cả. Trong nhiều ứng dụng khá đặc biệt, khi sai số thực hiện khá lớn chúng ta có thể mô hình hoá bằng cách cơn xứng hoá giữa tín hiệu vƠo vƠ tín hiệu ra. Trong các tr ng hợp nƠy, sử dụng mạng nh một bảng tra lƠ đủ, mặc dù các bảng nƠy sẽ cho l i giải gống nhau trong một khoảng nƠo đó của tín hiệu vƠo. Đối với việc chọn chiến l ợc học, chúng ta cần quan tơm tới sự phơn bố của các đối t ợng dùng để học. Nếu số l ợng đối t ợng dùng cho việc học lƠ ít vƠ đ ợc phơn bố đều trong toƠn không gian, khi đó số liệu có thể đ ợc dùng ngay cho việc mô hình hoá. Trái lại, nếu các đối t ợng lƠ nhiều, sẵn có nh ng phơn bố ngẫu nhiên trong không gian biến, đầu tiên ta phải giảm thiểu chúng 23 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 sao cho vẫn bao trùm toƠn không gian, sau đó mới dùng lƠm số liệu cho việc mô hình hoá. 1.2.1.4. Liên kết. Liên kết lƠ tìm ra đối tuợng đích có mối quan hệ với một đối t ợng vƠo, thậm chí cả khi đối t ợng vƠo bị hỏng hoặc hoƠn toƠn không biết. Theo một nghĩa nƠo đó, liên kết có thể đ ợc coi lƠ phơn loại. Thủ tục học cho vấn đề nƠy lƠ học có tín hiệu chỉ đạo. Lĩnh vực nghiên cứu các quá trình phụ thuộc th i gian lƠ một trong những lĩnh vực chính trong nghiên cứu quá trình điều khiển. đơy, ng i sử dụng dự báo đ ợc hƠnh vi của hệ thống đa biến dựa trên một chỗi số liệu đ ợc ghi nhận theo th i gian. Trong mô hình hoá phụ thuộc th i gian, các biến của các tín hiệu vƠo bao gồm các giá trị hiện tại vƠ quá khứ của các biến quá trình, trong đó tín hiệu ra dự đoán giá trị trong t ng lai của những biến quá trình đó. Về nguyên tắc các hiểu biết nƠy có thể có độ dƠi tuỳ ý, nh ng ng lai chỉ bao gồm một b ớc th i gian. trong quá trình kiểm soát, hiểu biết t Việc học dịch chuyển tới b ớc tiếp theo tạo ra các cửa sổ bao gồm số b ớc th i gian của vect ra. Để tạo ra mô hình hoƠn chỉnh của một quá trình, tất cả các biến quá trình phải đ ợc huấn luyện tại đầu ra của mạng, nh ng không phải tất cả các biến trong quá trình đều ảnh h ng nh nhau đối với kết quả cuối cùng, chỉ có một số biến lƠ đáng quan tơm. Do đó chúng ta chỉ phải chọn các biến đó cho quá trình học. Kỹ thuật dịch chuyển cửa sổ có thể đ ợc sử dụng để giải quyết các vấn đề chuỗi các sự kiện vƠ đối t ợng nh trong các lĩnh vực về môi tr ng theo th i gian, kiểm soát hỏng hóc. 24 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 1.2.2. Các lĩnh vực ứng d ng c a m ng n ron Kể từ khi ra đ i vƠ phát triển mạng n ron đƣ đ ợc ứng dụng trong rất nhiều lĩnh vực. Do vậy, liệt kê đ ợc tất cả các ứng dụng của mạng n ron lƠ không thực tế. Tuy nhiên, ta có thể đ a ra một số ứng dụng điển hình của mạng n ron nh sau: - Xử lý ảnh, nhìn máy: Gồm trùng khớp ảnh, tiền xử lý ảnh, phơn đoạn vƠ phơn tích ảnh, nén ảnh,... - Xử lý tín hiệu: Phơn tích tín hiệu địa chấn vƠ hình thái học. - Nhận dạng mẫu: Gồm việc tách các nét đặc biệt của mẫu, phơn loại vƠ phơn tích tín hiệu của rada, nhận dạng vƠ hiểu tiếng nói, nhận dạng vơn tay, ký tự, chữ viết,... - Y học: Phơn tích vƠ hiểu tín hiệu điện tơm đồ, chuẩn đoán bệnh, xử lý ảnh y học. - Quơn sự: Các hệ phát hiện thuỷ lôi, phơn loại luồng rada, nhận dạng ngu i nói. - Các hệ tƠi chính: Gồm phơn tích thị tr ng chứng khoán, định giá bất động sản, cấp phát thẻ tín dụng vƠ th ng mại an toƠn. - Trí tuệ nhơn tạo: Gồm các hệ chuyên gia,... - Dự đoán: Dự đoán các trạng thái của hệ thống,... - Quy hoạch, kiểm tra vƠ tìm kiếm: Gồm cƠi đặt song song các bƠi toán thoả mƣn rƠng buộc, tìm nghiệm bƠi toán ng i du lịch, điều khiển vƠ robot 1.2.3. u như c điểm c a m ng n ron. Ưu điểm: 25 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 - Xử lý song song - Thiết kế hệ thống thích nghi - Không đòi hỏi các đặc tr ng m rộng của bƠi toán (chủ yếu dựa trên tập học). - Có thể chấp nhận lỗi do tính song song. Nh ợc điểm: - Không có các quy tắc hoặc h ớng dẫn thiết kế rõ rƠng đối với một ứng dụng nhất định. - Không có cách tổng quát để đánh giá hoạt động bên trong mạng - Việc học đối với mạng có thể khó (hoặc không thể) thực hiện. - Khó có thể đoán tr ớc đ ợc hiệu quả của mạng trong t ng lai (khả năng tổng quát hoá). 1.3. MẠNG HOPFIELD Trong mạng hồi quy tín hiệu ra của một n ron có thể đ ợc truyền nguợc lại lƠm tín hiệu vƠo cho các noron các lớp tr ớc, hoặc các n ron trong cùng một lớp. Phần nƠy sẽ trình bƠy mô hình mạng tiêu biểu thuộc lớp mạng hồi quy, đó lƠ mạng Hopfield. Mạng Hopfield đ ợc bắt đầu nghiên cứu từ năm 1982. Đơy lƠ mạng một lớp với thông tin vƠ quá trình xử lý có nối ng ợc. Công trình của Hopfield có rất nhiều ứng dụng, đặc biệt trong bộ nhớ liên kết vƠ trong các bƠi toán tối u điển hình nh bƠi toán lập lộ trình di chuyển cho robot. Giả sử mạng đ ợc xơy dựng d ới dạng mạng một lớp, mỗi n ron đ ợc truyền ng ợc lại lƠm tín hiệu vƠo cho các n ron khác nh ng bản thơn các 26 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 ron không tự liên kết với chính nó. Khi đó mô hình mạng Hopfield đ ợc biểu diễn nh hình 1.7. Tín hiệu ra của n ron j nƠo đó đ ợc truyền ng ợc lại lƠm tín hiệu vƠo cho các n ron khác trong mạng một cách đầy đủ thông qua trọng số tu ng ứng. Đầu vƠo X1 Y1 X2 Y2 XN YM Đầu ra Hình 1.7. Mô hình mạng Hopfiled. Ký hiệu wij lƠ liên kết giữa hai n ron i vƠ j (wij = wji), Vi lƠ đầu ra của n ron i. Ta coi véc t (V1, V2, ..., Vn) lƠ trạng thái của mạng. Tại mỗi th i điểm t mỗi n ron i tổng hợp các tín hiệu Vj từ các n ron khác vƠ tín hiệu từ bên ngoƠi (bias). U i  WijV j ( t )  I i (1.13) i Tuỳ theo từng hƠm kích hoạt fi mƠ n ron i cho đầu ra lƠ Vi(t+1)= fi(Vi(t)). Mạng đạt trạng thái cơn bằng nếu: Vi(t)= Vi(t+1), i. Ta định nghĩa hƠm năng l ợng của mạng lƠ: E  E( V1 ,...,Vn )   1 n  2 i 1 WijViV j   I iVi n n j 1 i j i 1 (1.14) 27 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 Tuỳ theo ph ng thức hoạt động của mạng mƠ ng i ta phơn mạng Hopfield thƠnh mạng Hopfield r i rạc vƠ mạng Hopfield liên tục. 1.3.1. M ng Hopfield rời r c. Mạng Hopfield r i rạc lƠ mạng đ ợc tính r i rạc (đầu ra r i rạc) vƠ lƠm việc chế độ không đồng bộ. Tr ng hợp mạng nhận các giá trị nhị phơn {0, 1}: - HƠm kích hoạt đ ợc xác định nh sau: fi f 1 khi net  0 f ( net )   0 khi net  0 (1.15) Việc cho hƠm kích hoạt (1.15) t ng đ ng với quy tắc chuyển trạng thái của mạng . Vi(t+1) = Vi(t) + Vi Trong đó Vi đ ợc cho b i công thức    1 nÕu Wij Vj (t)  Ii  0 vµ Vi (t)  0  j  Vi  1 nÕu WijVj (t)  Ii  0 vµ V(t)=1 i j   trong c¸c tr-êng hîp kh¸c  0 (1.16) 1.3.2. M ng Hopfield liên t c. Mạng Hopfield liên tục lƠ mạng mƠ trạng thái của nó đ ợc mô tả b i ph ng trình động học: dU i   WijV j  I i dt j (1.17) Vi  f i ( U i ) 28 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 đó fi lƠ hƠm kích hoạt. đơy ta cũng giả thiết Wij =Wji vƠ Wii=0. Dễ thấy rằng nếu hƠm năng l ợng đ ợc cho b i 1.14 thì. dU i E  dt Vi 1.4. MẠNG NƠRON TRONG K THUẬT ROBOT Những nghiên cứu của mạng n ron đ ợc xuất phát từ ý t hiểu những nguyên lý hoạt động của bộ nƣo con ng ng lƠ tìm i, từ đó ứng dụng để thiết kế các hệ thống có thể thực hiện những nhiệm vụ phức tạp. Thực tế, mạng n ron có liên quan đến các lĩnh vực nh : học, thích nghi, khái quát hoá vƠ tối u hóa. Trong các lĩnh vực nƠy thì: sự đoán nhận, học, hoạt động vƠ quyết định lƠ những vấn đề liên quan mật thiết với kỹ thuật dò đ ng. Việc ứng dụng mạng n ron vƠo kỹ thuật tìm đ ng cho phép cải thiện những khả năng học vƠ thích nghi đáp ứng đ ợc những thay đổi trong môi tr ng có thông tin không chính xác, không nhất quán vƠ không đầy đủ. Kỹ thuật n ron có khả năng xử lý hiệu quả những dữ liệu không chính xác, kích th ớc lớn, đơy sẽ lƠ công việc khó khăn nếu sử dụng ph ng pháp truyền thống. Mạng n ron lƠ một hệ thống cho phép xử lý những thông tin song song vƠ phơn tán trên từng n ron, những n ron nƠy đ ợc kết nối với nhau theo một mô hình nhất định. Việc học trong mạng n ron có thể đ ợc giám sát hoặc không đ ợc giám sát. Học giám sát lƠ quá trình học sử dụng những thông tin mẫu đƣ đ ợc phơn loại, trong khi học không giám sát chỉ sử dụng những thông tin tối thiểu không đ ợc phơn loại. Những giải thuật học không giám sát có độ phức tạp tính toán thấp h n cho kết quả chính xác h n những giải thuật học giám sát. 29 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 NgoƠi ra mạng n ron còn đ ợc ứng dụng trong bƠi toán phơn loại vƠ nhận dạng. 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. & Goldberg, K. 1993). Không chỉ có vậy mạng n ron nƠy còn đ ợc ứng dụng trong việc xác định các quỹ đạo di chuyển của ng i máy. Để giúp robot tránh những ch ớng ngại vật mạng n ron với ph ng pháp huấn luyện lƠ tr ợt dốc vƠ lan truyền đƣ đ ợc sử dụng. Để dẫn đ ng cho ng i máy di chuyển trong môi tr đ ợc sử dụng. Trong môi tr ng hoạt động mạng n ron giám sát đƣ ng hoạt động của mình ng i máy học b i mạng n ron, tại mỗi b ớc robot dự đoán các b ớc kế tiếp vƠ từ đó phát sinh những tín hiệu điều khiển robot di chuyển. 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. Từ những ứng dụng của mạng n ron trong kỹ thuật robot, ta nhận thấy việc ứng dụng công nghệ nƠy lƠ vô cùng quan trọng, nó sẽ lƠ giải pháp khả thi có tính đột phá để nơng cao khả năng hoạt động của robot trong môi tr ng hoạt động, từ đó ứng dụng vƠo thực tế cuộc sống. 1.5. NHẬN XÉT Mạng truyền thẳng vƠ mạng hồi quy lƠ hai mô hình tiêu biểu của mạng n ron nhơn tạo, Mỗi loại mạng sẽ có những u nh ợc điểm riêng. Nắm vững những u nh ợc điểm của chúng sẽ gúp ta lựa chọn mô hình mạng thích hợp cho từng ứng dụng sẽ thiết kế. Những u nh ợc điểm của từng mô hình mạng sẽ đ ợc thể hiện qua những nhận xét sau: - Mạng truyền thẳng một lớp dễ phơn tích nh ng không mô tả đ ợc mọi hƠm. Mạng nhiều lớp khắc phục đ ợc nh ợc điểm trên 30 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 nh ng lại rất khó phơn tích vƠ gặp khó khăn trong quá trình xơy dựng mạng. Mặt khác mạng truyền thẳng nhiều lớp có thể gơy sai số tích luỹ qua các lớp. - Mạng phản hồi một lớp (tiêu biểu lƠ mạng Hopfield) có cấu trúc đ n giản vì thế dễ phơn tích, không chứa sai số tích luỹ. - Mạng n ron truyền thẳng chỉ đ n thuần tính toán các tín hiệu ra dựa trên các tín hiệu vƠo vƠ trọng số liên kết giữa các n ron đƣ xác định sẵn trong mạng. Do đó chúng không có trạng thái bên trong nƠo khác ngoƠi trọng số W. Đối với mạng hồi quy, trạng thái bên trong của mạng đ ợc l u trữ tại các ng ỡng của n ron. Nói chung các mạng hồi quy không ổn định, mạng cần phải tính toán rất lơu, thậm chí có thể lặp vô hạn tr ớc khi đ a ra kết quả mong muốn. Quá trình học của mạng hồi quy cũng phức tạp h n mạng truyền thẳng rất nhiều. Tuy vậy các mạng hồi quy có thể cho phép mô phỏng các hệ thống t ng đối phức tạp trong thực tế. 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. GI I THIỆU ROBOT NHÂN TẠO. Cùng với sự phát triển của khoa học, công nghệ robot ngƠy cƠng đ ợc ứng dụng rộng rƣi trong các lĩnh vực của đ i sống xƣ hội. Chúng có thể lƠ những thiết bị điều khiển tự động trong các dơy truyền công nghiệp, hoặc có thể lƠ những robot lƠm việc trong những môi tr đôi khi không thể tiếp cận đ ợc nh : môi tr ng phức tạp mƠ con ng i ng nhiệt độ cao, áp suất lớn, ng ngoƠi khoảng không vũ trụ... Không chỉ có vậy, robot còn đ ợc môi tr ứng dụng rất nhiều trong đ i sống ví dụ nh : Robot lau dọn sƠn nhƠ, robot h ớng dẫn di chuyển, robot phục vụ trong các toƠ nhƠ cao tầng, robot phẫu thuật,... Robot đ ợc ứng dụng rộng rƣi vƠ có nhiều tính năng u việt nh vậy song không phải ai cũng có thể hiểu về nguyên lý của những tác vụ mƠ robot có thể thực hiện. Sau đơy sẽ lƠ những trình bƠy s l ợc về nguyên tắc cấu tạo vƠ nguyên lý lƠm việc của một mobile robot. 2.1.1. Tổng quan Các nhơn tố cấu thƠnh robot:  Về cấu tạo: Robot phải d ợc trang bị bộ cảm nhận để cảm nhận các thông tin về môi tr ng nh : sensor, encoder, camera,... Các bộ phận thực hiện hƠnh động: bánh xe để chuyển động, cánh tay…  Các tri thức mƠ robot cần đ ợc trang bị lƠ: Cấu trúc của môi tr ng lƠm việc, các hoƠn cảnh mƠ robot có thể gặp vƠ các hƠnh động mƠ robot cần thực hiện trong các hoƠn cảnh đó, ... Các tri thức nƠy cần phải đ ợc thể hiện một cách thích hợp sao cho thuận tiện cho việc l u trữ, tìm kiếm vƠ suy diễn. 32 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 khả năng của robot: Robot cần có khả năng phơn biệt đ ợc các đối t ợng mƠ nó gặp, thực hiện các thao tác, di chuyển an toƠn trong môi tr ng sao cho đ ng đi lƠ tối u vƠ không va trạm với các vật cản. 2.1.2. Giải pháp thiết kế Để thiết kế robot ta phải hoƠn thiện các công đoạn sau: * Xem robot nh một đối t ợng lập trình bao gồm: - Dữ liệu: Các trạng thái của môi tr ng lƠm việc, giá trị của sensor, encoder... - Tác vụ: LƠ tập các hƠnh động c bản mƠ robot có thể thực hiện nh : Tiến, lùi, rẽ trái, rẽ phải, ... * Mô hình hoá môi tr ng lƠm việc * Mô hình hoá đối t ợng robot sẽ gặp, xử lý các tác vụ trong môi tr việc, cùng với việc xử lý dữ liệu vƠ các trạng thái trong môi tr * Nhúng các giải thuật tìm đ một đ ng lƠm ng ng vƠ giải thuật xử lý sự kiện cho robot để có ng đi tốt từ vị trí ban đầu tới đích vƠ xử lý các tình huống ngoại lệ nh va chạm. * Phơn chia vƠ module hoá các khối trên robot. * Xơy dựng các thƠnh phần robot bao gồm: Lập trình, mạch phần cứng, c cấu c khí. Cả ba quá trình nƠy phải triển khai đồng bộ với nhau vƠ chúng có tác động rất lớn tới nhau, sự hoƠn thiện phần nƠy lƠ tiền đề để xơy dựng phần kia. * C chế hiển thị vƠ Debug lỗi qua các giao tiếp Led/LCD hay với PC. 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: - Tiến - Lùi - Rẽ trái - Rẽ phải -Các tác vụ khác Kết quả Robot Giải thuật lập lộ trình, xử lý sự kiện vƠ ngoại lệ. Hình 2.1. Các thành phần cấu thành robot Tất cả các thƠnh phần trên góp phần cấu thƠnh một robot hoƠn chỉnh. Ta có thể ví các c cấu c khí giống nh thể xác. Các mạch điện tử giống nh các mạch máu, các n ron thần kinh, các giác quan bên ngoƠi. Ch ng trình giống nh bộ nƣo giúp điều khiển c thể thông qua hệ thống mạch. 2.2. BÀI TOÁN LẬP LỘ TRÌNH. 2.2.1. Mở đ u. Để robot có thể hoạt động trong môi tr ng vƠ thực hiện tốt các chức năng của nó thì ngoƠi các c cấu c khí, các mạch điện tử ra thì các ch trình điều khiển lƠ không thể thiếu. Nh đƣ trình bƠy trên, ch ng ng trình có thể ví nh bộ nƣo để điều khiển mọi hoạt động của robot. Nh vậy để robot có thể hoạt động hiệu quả thì ch ng trình phải đ ợc thiết kế tốt, phù hợp với các đặc tính điện tử, c khí. Nền tảng của các ch ng trình nƠy chính lƠ các giải thuật nhằm mô phỏng những hoạt động bậc cao của con ng i vƠo trong những mô tả mức thấp để sao cho có thể h ớng dẫn robot hoạt động. 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. Giải thuật nƠy sẽ h ớng dẫn robot di chuyển từ vị trí ban đầu tới vị trí 34 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 sao cho tránh đ ợc những va trạm trên đ việc lập lộ trình t ng đi. Ta có thể hình dung ng tự nh bƠi toán di chuyển một chiếc piano. Giả sử ta cần thiết kế một giải thuật giúp máy tính thiết kế chính xác đ ng đi để di chuyển chiếc piano từ vị trí nƠy đến vị trí khác với dữ liệu đầu vƠo lƠ cấu trúc toƠ nhƠ vƠ vị trí của piano. Việc lập lộ trình cho robot thông thu ng không quan tơm đến động lực học mƠ chỉ quan tơm tới việc tìm đ đến đích tránh va trạm với môi tr ng vƠ di chuyển ng xung quanh. Khái niệm lập lộ trình xuất hiện trong khá nhiều lĩnh vực tiêu biểu nh : Lý thuyết điều khiển vƠ trí tuệ nhơn tạo.  Trong lý thuyết điều khiển: Vấn đề nƠy đ ợc đề cập tới nh việc thiết kế những hệ thống vật lý mô tả b i những ph ng trình vi phơn. Những hệ thống đó có thể bao gồm những hệ thống c khí nh ô tô hoặc máy bay, những hệ thống điện nh lọc tiếng ồn, hoặc cả những hệ thống xuất hiện trong nhiều lĩnh vực đa dạng khác nh hóa học, kinh tế học vƠ xƣ hội học. Tr ớc đơy, lý thuyết điều khiển lƠ điều khiển m phản hồi, cho phép một sự hồi đáp có khả năng thích ứng trong th i gian thực hiện, tập trung về sự ổn định, mƠ bảo đảm rằng vấn đề động lực học không gơy cho hệ thống tr nên lộn xộn mất điều khiển. Một tiêu chuẩn quan trọng cho sự tối u hóa để tối giản tiêu thụ tƠi nguyên, nh năng l ợng hoặc th i gian. Trong các tƠi liệu về lý thuyết điều khiển gần đơy, việc lập lộ trình chuyển động đôi khi đ ợc quy dẫn đến việc xơy dựng đầu vƠo tới một hệ thống động lực phi tuyến để điều khiển robot từ vị trí ban đầu tới một vị trí đích xác định. Trong lĩnh vực nƠy luôn mong muốn có một thuật toán lý t ng sao cho vẫn xử lý tốt bƠi toán khi những dữ liệu đầu vƠo lƠ không chắc chắn hoặc xuất hiện từ những mẫu không chính xác. 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. Thay vì việc di chuyển trong một không gian liên tục bƠi toán sẽ đ ợc quy dẫn về vấn đề tìm kiếm lộ trình trong một không gian trạng thái, t ng tự nh bƠi toán khối lập ph ng Rubik hoặc bƠi toán dịch chuyển số. Mặc dù những vấn đề nƠy hoƠn toƠn có thể đ ợc mô hình hoá trong không gian liên tục song việc giải quyết bƠi toán trong không gian trạng thái cho phép xơy dựng các thuật toán lựa chọn một dƣy hoạt động thích hợp để điều khiển hoạt động của robot. Hình 2.2. Khối Rubik (a), bài toán dịch chuyển số (b). Thuật ngữ lập lộ trình bao hƠm rất nhiều thao tác song trong khuơn khổ của đề tƠi ta chỉ quan tơm tới các thuật toán lập lộ trình. 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? - Nó đ ợc cƠi đặt nh thế nƠo trong máy tính? - Thế nƠo đ ợc coi lƠ hoƠn tất? - Chất l ợng của nó đ ợc đánh giá ra sao? - Đố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. Mặt khác việc lập lộ trình dựa trên các giải thuật đƣ đạt đ ợc những thƠnh công lớn trong các lĩnh vực: công nghệ, lý thuyết khoa học, công nghệ robot, thiết kế sản xuất, không gian vũ trụ,...Những lý do trên đƣ thúc đẩy việc học tập vƠ nghiên cứu những giải thuật lập lộ trình, góp phần phát triển vƠ ứng dụng chúng vƠo các lĩnh vực trong thực tế. 2.2.2. Các ví d thực tế. Ví dụ 1: BƠi toán Alpha 1.0 puzzle do Boris Yamrom đề xuất. 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. Giải pháp cho bƠi toán nƠy do James Kuffner đề xuất. BƠi toán nƠy thể hiện trong hình 2.3. Việc giải các bƠi toán trong hình 2.2 có thể dễ dƠng đ ợc thực hiện b i tính đều đặn vƠ đối xứng của những thƠnh phần tham gia vƠo di chuyển. Tuy nhiên, những đặc điểm nƠy không có trong bƠi toán 2.3. Bên cạnh đó nó còn yêu cầu phải giải quyết vấn đề trong không gian liên tục. BƠi toán nƠy sẽ đ ợc giải quyết trong một vƠi phút trên máy tính cá nhơn chuẩn sử dụng kỹ thuật thăm dò nhanh tróng trên cấu trúc cơy dầy đặc. Hình 2.3. Tìm giải thuật để kéo hai thanh thép tách ra Mặc dù các vấn đề trình bƠy trên chỉ lƠ trò ch i giải trí song trong thực tế có rất nhiều ứng dụng quan trọng có nguyên lý t ng tự nh những trò 37 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 i nƠy. Điều nƠy khẳng định lý thuyết chuyển động không đ n thuần lƠ trò ch i giải trí mƠ nó có rất nhiều ứng dụng trong thực tế. Ví dụ 2: Di chuyển một piano lớn qua một căn phòng bằng cách sử dụng ba robot di động với cánh tay thao tác bên trên chúng. Hình 2.4 mô tả quá trình di chuyển. Trong quá trình di chuyển yêu cầu phải tránh đ ợc những va trạm giữa robot với những đồ vật khác. Vấn đề sẽ tr nên phức tạp h n khi cấu trúc của căn phòng không đ ợc biết tr ớc. Hình 2.4. Sử dụng robot di động để di chuyển piano Ví dụ 3: Giả sử ta đang trong một hƠnh lang hoƠn toƠn tối, với một chiếc đèn trên tay. Yêu cầu phải tìm kiếm một ng i bất kỳ nƠo đó. Khi thực hiện nhiệm vụ nƠy có một vƠi cơu hỏi đ ợc đặt ra: - Liệu có tồn tại một chiến l ợc đảm bảo rằng sẽ tìm thấy tất cả mọi ng i không? - Nếu không thì thực hiện nh thế nƠo để tiếp tục tìm kiếm vƠ hoƠn thƠnh nhiệm vụ nƠy? - Đơu lƠ n i ta cần dịch chuyển đến b ớc tiếp theo? - LƠm thế nƠo để tránh đ ợc việc thăm dò một chỗ nhiều lần? Những vấn đề đề xuất trong ví dụ nƠy cũng xuất hiện trong nhiều ứng dụng của kỹ thuật robot. Để đảm bảo cho robot thực hiện các nhiệm vụ trên 38 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 thì chúng phải đ ợc trang bị những hệ thống cảm biến vƠ cần phải có một chiến l ợc để robot định vị những vật khác. Qua những ví dụ nêu trên ta nhận thấy các giải thuật lập lộ trình không chỉ có ứng dụng trong công nghệ robot mƠ nó có thể đ ợc ứng dụng trong rất nhiều lĩnh vực của thực tế nh : Tìm kiếm cứu nguy, lƠm sạch chất độc, thiết kế an toƠn trong các toƠ nhƠ, giúp những máy bay tự lái v ợt qua những ch ớng ngại vật, lƠ c s tính toán cho tầu vũ trụ tránh những va trạm trong môi tr ng phức tạp. 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. 2.2.3. BƠi toán l p l trình chuyển đ ng cho robot. 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. Yêu cầu tìm ra một đ ng đi liên tục từ vị trí ban đầu đến vị trí đích sao cho tránh đ ợc những va trạm với những vật cản trên đ th ng đi. Quá trình xác định lộ trình 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ể tóm tắt bƠi toán nh sau: Đ u vƠo (Input): Những mô tả hình học của ng i máy, môi tr ng vƠ những ch ớng ngại vật, vị trí ban đầu vƠ vị trí đích. Đ u ra (output): Đ tại đ ng đi từ vị trí đầu đến vị trí đích hoặc thông báo không tồn ng đi. 39 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 2.3. CÁC THÀNH PH N CƠ B N C A VIỆC LẬP LỘ TRÌNH Mặc dù công việc lập lộ trình lƠ một công việc khá phức tạp vƠ phải trải qua rất nhiều công đoạn, song ta có thể hệ thống hoá các thƠnh phần của bƠi toán nƠy. 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. - 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. Không gian trạng thái có thể bao bồm các đối t ợng r i rạc (hữu hạn, hoặc vô hạn đếm đ ợc) hoặc liên tục (vô hạn không đếm đ ợc). 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. Trong đa số các ứng dụng, kích th ớc của không gian trạng thái (số những trạng thái hoặc tổ hợp các trạng thái) lƠ quá lớn để có thể thể hiện rõ rƠng từng trạng thái. 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. 2.3.2. 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. Sự tối u về mặt th i gian trong bƠi toán nƠy có thể hiểu nh việc điều khiển một chiếc ô tô v ợt qua một ch ớng ngại vật cƠng nhanh cƠng tốt. Trong những giải thuật ng i ta chú ý đến th i gian tổng thể đ a robot từ trạng thái ban đầu đến trạng thái đích. Trong các giải thuật lập lộ trình chuyển động ng i ta tránh chỉ rõ th i gian cụ thể trên một lộ trình cụ thể mƠ ớc l ợng th i gian trong tr ng hợp xấu nhất. 40 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 2.3.3. HƠnh đ ng (Actions) Trên một lộ trình có thể phát sinh những hƠnh động (thao tác) trên những trạng thái. Trong lý thuyết vƠ kỹ thuật điều khiển rôbôt, thuật ngữ hƠnh động liên quan đến việc nhập đầu vƠo vƠ điều khiển. một số cách tiếp cận về vấn đề lộ trình, hƠnh động phải đ ợc chỉ rõ để sao cho có thể thay đổi đ ợc trạng thái khi nó thực thi. Điều nƠy có thể đ ợc biểu thị nh một hƠm đánh giá trạng thái của tr trình vi phơn bình th ng hợp th i gian riêng biệt hoặc nh một ph ng ng cho th i gian liên tục. Trong thực tế có một vƠi vấn đề về hƠnh động cần đ ợc quan tơm, đó lƠ: Những hƠnh động tự nhiên có thể gơy hậu quả rắc rối cho sự điều khiển của ng i chế tạo. Đ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. 2.3.4. Tr ng thái ban đ u vƠ kết thúc: Một lộ trình bắt đầu từ một vƠi trạng thái ban đầu nƠo đó vƠ cố gắng đi đến một trạng thái đích xác định hoặc bất kỳ trạng thái nƠo trong tập hợp của những trạng thái đích. Những hƠnh động sẽ đ ợc lựa chọn để đạt đ ợc điều đó. 2.3.5. 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:  Tính khả thi : Sẽ tìm đ ợc một lộ trình để đ a robot đến trạng thái đích, không quan tơm đến hiệu quả của quá trình nƠy.  Sự tối u : Lộ trình tìm đ ợc lƠ khả thi vƠ tối u theo một tiêu chí nƠo đó (tối u về mặt th i gian, tối u về không gian,...) Trong luận văn nƠy, chúng ta chỉ tập trung vƠo tính khả thi, việc đạt đ ợc sự tối u lƠ rất khó khăn, đơy có thể lƠ h ớng để m rộng đề tƠi. 41 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 2.3.6. 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. 2.3.7. 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. Trong vƠi tr ng hợp, con ng i tr thƠnh những ng i lập lộ trình b i việc phát triển một lộ trình lƠm việc trong tất cả các tình trạng. Mô hình lập lộ trình đƣ cho đ ợc đ a tới cho con ng trình t ng ứng. Trong tr i, vƠ con ng ng hợp nƠy con ng i “ tính toán ” một lộ i vẫn lƠm tròn vai trò của giải thuật. 2.3.8. L trình Hiểu một cách đ n giản: Lộ trình lƠ một bản kế hoạch mƠ nhìn vƠo đó ng i ta có thể xác định đ ợc cần đi nh thế nƠo mƠ không va phải những ch ớng ngại vật vƠ đến đ ợc đích xác định. Khái niệm c s của lộ trình lƠ không gian. Không gian nói chung chứa đựng các loại thực thể đó lƠ: Ch ớng ngại vật (Obstacles), khoảng trống tự do (Free Space) vƠ robot - Chư ng ng i v t: LƠ thƠnh phần “ th ng xuyên” chiếm chỗ trong không gian, hay nói cách khác lƠ n i mƠ robot không thể đi vƠo. Ví dụ nh bức t ng của một toƠ nhƠ. - Khoảng trống tự do: LƠ n i còn trống trong không gian mƠ robot có thể đi vƠo. Để 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. Thực thi : Thực thi lộ trình bằng cách mô phỏng hoặc trên thiết bị c khí thực (robot) trong thế giới vật lý thực. 2. Cải tiến : Cải tiến nó để có đ ợc một lộ trình tốt h n. 3. 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 ng đ ợc thực thi b i một máy. Một con 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. Có hai cách để thực hiện trên máy, đó lƠ: Cách 1: Trong Hình 2.5a, ng i lập lộ trình tạo ra một lộ trình, mƣ hóa nó theo một cách nƠo đó vƠ nhập vƠo máy. Trong tr đ ợc nhập ch của ch ng hợp nƠy sau khi đƣ ng trình thì máy sẽ tự trị tức lƠ tuần tự thực hiện những b ớc ng trình vƠ không còn sự t ng tác với ng i lập trình nữa. 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. Cách 2: Đ ợc miêu tả trong Hình 2.5 b. Trong tr sản sinh b i ng ng hợp nƠy, lộ trình i lập lộ trình mƣ hóa trọn vẹn trong máy. Đơy lƠ một lộ trình đặc biệt chủ định cho máy vƠ đ ợc thiết kế để giải quyết những nhiệm vụ đặc biệt cho tr ớc h ớng tới ng i lập lộ trình. Giải thuật nƠy chỉ h ớng tới để thiết kế cho một số máy để giải quyết đầy đủ một số nhiệm vụ cụ thể. Khi đó chỉ cần một số ít ng i vƠ máy cũng có thể giải quyết đ ợc nhiệm vụ đ ợc giao. Sự Cải tiến: Nếu một lộ trình đ ợc sử dụng để cải tiến, thì ng i lập lộ trìn sẽ coi nó nh đầu vƠo vƠ xác định một lộ trình mới. 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. Sự cải tiến có thể đ ợc ứng dụng nhiều lần, để sản sinh một dƣy các lộ trình cải tiến, khi đó lộ trình cuối cùng có sự thực thi tốt nhất. (a) (b) 44 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) (d) Hình 2.6. Một số lộ trình và sự cải tiến lộ trình Ví d : - Lộ trình đầu tiên (a)- di chuyển một robot di động trong nhƠ, chấp nhận một sự va chạm - tự do trên đ ng đi qua tòa nhƠ. - Cải tiến sang lộ trình thứ hai (b) lộ trình đòi hỏi phải thỏa mƣn những sự rƠng buộc c s khác nhau của sự điều khiển chuyển động. - Lộ trình thứ ba (c) xem xét lƠm sao để di chuyển robot dọc theo đ ng với những tốc độ khác nhau, đồng th i quan tơm đến động lực học. - Lộ trình thứ t (d) hợp nhất thông tin phản hồi để bảo đảm rằng ng i máy có khả năng cƠng đóng cƠng tốt với lộ trình mặc dù hƠnh vi lƠ không thể đoán tr ớc. 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. Để thực hiện đ ợc điều nƠy lộ trình nguyên bản phải bảo đảm tính dừng, để lộ trình lớn h n có thể thực thi chúng nhiều lần khi cầ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. Không có giới hạn tới chiều sơu cơy hoặc số các đỉnh con. Trong việc lập lộ trình có thứ bậc, dòng t tr ng đ ợc vẽ nhiều h ớng. Ví dụ, môi tr máy khác nh M2, t ng tác giữa máy vƠ môi ng E1 của máy M1, có thể chứa ng tác đó với môi tr ng E2 của nó, nh trong Hình2.7. 2.3.9. 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. Những ph ng pháp nƠy đủ tổng quát để sử dụng trong nhiều ứng dụng của nhiều lĩnh vực khác nhau, nh máy tính sinh học, thiết kế với sự trợ giúp của máy tính, đồ hoạ máy tính... 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. KHÔNG GIAN C U HÌNH 2.4.1. Các khái ni m không gian cấu hình. Không gian cấu hình (cấu hình không gian) lƠ không gian của tất cả những cấu hình có thể của robot. 2.4.1.1. Chướng ngại (Obstacle): LƠ những phần của không gian “Th xuyên” bị choán chỗ, ví dụ, nh trong những bức t ng ng của một tòa nhƠ. 46 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 0. KỦ hi u: A: Một thực thể đ n –(the robot) W: Không gian Euclidean đó A di chuyển; B1,…Bm: ch ớng ngại vật phơn bổ cố định trong W Hình 2.8- Không gian cấu hình - Cấu hình ch ớng ngại vật: LƠ cấu hình của từng ch ớng ngại vật - Miền ch ớng ngại vật: LƠ hợpSpace của tất cả các cấu hình ch ớng ngại vật Free From Robot Motion Planning J.C. Latombe 2.4.1.2 Không gian trống ( Free Space- Cfree): LƠ phần bù của toƠn bộ không gian với miền ch ớng ngại vật. City College of New York 2.4.2. Mô hình cấu hình. Để 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. Có nhiều ph ng pháp để mô hình 47 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á không gian đơy chúng ta quan tơm chủ yếu đến hai loại chính đó lƠ: mô hình hình học vƠ mô hình nửa đại số. 2.4.2.1. Mô hình hình học. Có rất nhiều ph ng pháp vƠ kỹ thuật trong mô hình hình học. Tuỳ theo từng ứng dụng mƠ ta có thể lựa chọn các giải pháp khác nhau. Tuy nhiên có hai giải pháp th ng đ ợc lựa chọn để biểu diến W, đó lƠ: 1) Không gian 2 chiều, khi đó W = R2. 2) Không gian 3 chiều, khi đó W = R3 . C Cfree qslug Cobs qrobot Hình 2. 9 Một Robot điểm di chuyển trong không gian 2D, C-space là R2 C y Cfree qgoal Z Cobs qstart x Hình 2.10: Một Robot điểm di chuyển trong không gian 3D, C-space là R3 Tuy nhiên, trong thực tế có nhiều không gian phức tạp h n, nh bề mặt của một hình cầu, khi đó cần những không gian có số chiều lớn h n để biểu 48 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 diễn chúng. Song trong khuôn khổ của luận văn ta không bƠn tới những lĩnh vực nƠy. 1- Mô hình đa giác : Trong không gian hai chiều 2D, W = R2. Vùng ch ớng ngại vật O lƠ một tập các đa giác lồi. Biểu diễn một m-đa giác trong O đ ợc mô tả b i hai đặc tr ng đỉnh vƠ cạnh. Mỗi đỉnh t ng ứng tới một “góc” của đa giác, vƠ mỗi cạnh t ng ứng với một đoạn nối giữa một cặp của đỉnh. Đa giác có thể đ ợc chỉ rõ b i đ ng nối liên tiếp các cặp đỉnh của m điểm bên trong R2 theo thứ tự ng ợc chiều kim đồng hồ: ( x1, y1), ( x2, y2),... , ( xm, ym). Hình 2.11 : Một đa giác lồi có thể được xác định bởi phép giao của các nửa - mặt phẳng. Một hình đa giác trong O có thể đ ợc biểu thị nh phép giao của m nửa mặt phẳng. Mỗi nửa mặt phẳng t mƠ nằm một bên của đ ng ứng tới tập hợp của tất cả các điểm ng thẳng trùng với cạnh của một đa giác. Hình 2.11 cho thấy một ví dụ của một hình bát giác đ ợc biểu diễn nh phép giao của tám nửa mặt phẳng. Một cạnh của đa giác đ ợc chỉ rõ b i hai điểm, nh (x1, y1) vƠ ( x2, y2). Xem xét ph vƠ (x2,y2). Một ph ng trình của một đ ng thẳng đi qua (x1,y1) ng trình có thể đ ợc xác định có dạng: ax+ by + c = 0. Trong đó a, b, c  R lƠ những hằng số đ ợc xác định từ x1, y1, x2, y2. Cho ánh xạ f : R2  R xác định b i hƠm f(x, y ) = ax + by + c . 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) < 0 lƠ những điểm nằm bên trái của đ ng thẳng, f(x,y)> 0 lƠ những điểm nằm bên phải. Để cho f i(x, y) biểu thị hƠm f dẫn xuất ra từ đ ng thẳng mƠ t ng ứng với cạnh từ (xi, yi) tới (xi +1, yi +1) với 1  i < m. Để cho fm(x, y) biểu thị ph mƠ t ng trình đ ng thẳng ng ứng với cạnh từ (xm, ym) tới ( x1, y1). Để cho một nửa mặt phẳng Hi cho 1  i  m đ ợc xác định một tập con của W: H i  x , y W | f i x , y   0 (2.1) Hình 2.12: Dấu hiệu của f(x, y) phân chia R 2 vào ba vùng : f(x, y) < 0 , f(x, y) > 0, f(x, y) = 0. Một tập lồi, m – cạnh, vùng O ch ớng ngại đa giác đ ợc biểu thị nh sau: O  H 1  H 2 ...  H m (2.2) Trong đa số các ứng dụng các tập con không lồi có thể vẫn đ ợc chấp nhận. Khi đó vùng ch ớng ngại O đ ợc biểu thị nh sau: O  O1  O2 ...  Om (2.3) Trong đó mỗi Oi lƠ một đa giác lồi, với Oi vƠ Oj ( i  j) không cần r i nhau. Với cách nƠy, chúng ta có thể biểu diễn đ ợc rõ rƠng các không gian rất phức tạp. Trong những không gian phức tạp ta cần phải biểu diễn thông qua sự kết hợp hữu hạn giữa phép hợp, giao, vƠ hiệu của tập hợp mẫu. Tuy nhiên, để đ n giản hoá việc biểu diễn các mẫu ng i ta cố gắng sử dụng cách biểu diễn theo phép hợp vƠ giao của các mẫu. Một tập hợp hiệu th ng tránh sử dụng để 50 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 biểu diễn mẫu. Để lƠm đ ợc nh vậy ng i ta thay những điểm f i(x,y) < 0 trong mẫu Hi b i những điểm - fi(x,y)  0 vƠ định nghĩa lại một mẫu Hi ’. Một mẫu phức tạp đ ợc kết hợp b i những mẫu đ n giản có thể loại bỏ đ ợc phép hiệu bằng cách áp dụng những phép biến đổi theo các luật của đại số Boolean. Chú ý rằng sự biểu diễn của một đa giác không lồi không phải lƠ duy nhất. Có nhiều cách để phơn tách O thƠnh các đa giác. Do vậy cần phải cẩn thận lựa chọn cách phơn tách để tối u hóa việc tính toán trong những giải thuật sử dụng mô hình. Trong đa số các tr đ ợc cho phép giao nhau. Lý t ng hợp, những thƠnh phần có thể ng nhất lƠ việc lựa chọn cách biểu thị O sao cho tối thiểu nhất các mẫu. đơy một logic vị từ đƣ đ ợc định nghĩa nh sau:  : W  {TRUE, FALE}. HƠm trả về giá trị TRUE cho một điểm trong W nằm bên trong O, ng ợc lại lƠ FALSE. Cho một đ ng thẳng f(x, y ) = 0 để e(x, y) biểu thị một vị từ lôgíc trả về giá trị TRUE nếu f(x, y) = 0, vƠ ng ợc lại lƠ FALSE . Một vị từ t sau: ng ứng tới một vùng đa giác lồi đ ợc biểu diễn b i các phép hội nh  ( x , y )  e1 ( x , y )  e2 ( x , y )  ...  em ( x , y ) (2.4) Vị từ  (x, y) trả về giá trị TRUE nếu điểm (x, y) nằm trong vùng đa giác lồi, ng ợc lại lƠ FALSE. Một vùng ch ớng ngại mƠ gồm có n đa giác lồi đ ợc biểu diển b i tuyển nh sau: ( x , y )  1 ( x , y )   2 ( x , y )  ...   n ( x , y ) Mặc dầu tồn tại những ph (2.5) ng pháp hiệu quả h n, song  có thể kiểm tra cho một điểm ( x, y) nằm trong trong O với th i gian O(n), trong đó n lƠ số mẫu xuất hiện trong biểu diễn của O ( Mỗi mẫu đ ợc ớc l ợng trong hằng số th i gian). Bất kỳ mệnh đề lôgíc phức tạp đến đơu đều có thể đ ợc tách nhỏ thƠnh những chuẩn tuyển (Đơy th ng đ ợc gọi “ tổng của những tích ” trong 51 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 khoa học máy tính). Nh vậy chúng ta có thể nói bất kỳ một không gian O nƠo đều luôn đ ợc biểu diễn bằng hợp của hữu hạn các phép giao những mẫu. 2- Mô hình đa di n: Trong không gian ba chiều W = R3 , những khái niệm có thể đ ợc khái quát hóa từ tr ng hợp không gian 2D b i việc thay thế đa giác bằng khối đa diện vƠ việc thay thế nửa mặt phẳng b i nửa không gian mẫu. Một danh giới biểu diễn có thể đ ợc định nghĩa d ới dạng ba đặc tr ng : Đỉnh, cạnh, vƠ mặt. Một vƠi cấu trúc dữ liệu đ ợc đ a ra để biểu diễn đa diện, ví dụ, cấu trúc dữ liệu chứa ba kiểu bản ghi : mặt, nửa cạnh, vƠ đỉnh (một nửa cạnh lƠ cạnh có h ớng). Giả sử O lƠ một đa diện lồi, nh trong Hình 2.13. Một biểu diễn ba chiều có thể đ ợc xơy dựng từ những đỉnh. Mỗi mặt của O có ít nhất ba đỉnh dọc theo ranh giới của nó. Giả thiết rằng những đỉnh nƠy không cộng tuyến, một ph ng trình của mặt phẳng đi qua chúng có dạng: ax + by + cz + d = 0 (2. 6) Trong đó a, b, c, d  R lƠ những hằng số. Một lần nữa, f có thể xơy dựng bằng ánh xạ f : R3  R vƠ f(x, y, z) = ax + by + cz + d. (2.7) với m mặt. Cho mỗi mặt của O, một nửa - không gian Hi đ ợc định nghĩa nh một tập con của W: H i ( x , y , z ) W | f i ( x , y , z )  0 (2.8) Điều quan trọng lƠ chọn fi để nó giữ những giá trị ơm trong đa diện. Trong mô hình đa giác, để thích hợp với định nghĩa fi việc xuất phát đi quanh biên theo thứ tự ng ợc chiều kim đồng hồ. Trong tr ng hợp của một đa diện, ranh giới của mỗi mặt lƠ các cạnh cũng đ ợc lấy ng ợc chiều kim đồng hồ; (Hình 2.13b). 52 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 Hình 2.13: (a)Đa diện. (b) biểu diễn các cạnh của mỗi mặt trong đa diện. Ph ng trình cho mỗi mặt đ ợc xác định nh sau: Chọn ba đỉnh liên tiếp p1, p2, p3 (không cộng tuyến ) theo thứ tự ng ợc chiều kim đồng hồ. Cho v12 biểu thị vect từ p1 tới p2, v23 biểu thị vect từ p2 đến p3. Tích v= v12xv23 lƠ vect nằm trong mặt phẳng gọi lƠ vect hồi. Véc t [a b c] song song với mặt phẳng. Nếu những thƠnh phần của nó đ ợc chọn lƠ a = v[1], b = v[2], c = v[3], thì f(x, y, z) = 0 cho mọi điểm trong nửa - không gian chứa đa diện. Trong tr ng hợp đa giác mẫu, một đa diện lồi có thể đ ợc định nghĩa nh phép giao của một số hữu hạn của các nửa - không gian t ng ứng với mỗi mặt. Một đa diện không lồi có thể đ ợc định nghĩa nh phép hợp của một số hữu hạn các đa diện lồi. Vị từ  (x, y, z) có thể đ ợc định nghĩa t TRUE nếu ( x, y, z)  O, vƠ FALSE trong tr ng tự lƠ ng hợp ng ợc lại. 2.4.2.2. Mô hình nửa đại số. Trong những mô hình đa giác vƠ đa diện, f lƠ một hƠm tuyến tính. Trong mô hình nửa đại số đối với không gian 2D, f lƠ đa thức với những hệ số bất kỳ vƠ hai biến thực x vƠ y. Trong không gian 3 chiều, f lƠ một đa thức với ba biến thực x, y, z. Lớp mô hình nửa đại số bao gồm cả hai mô hình đa diện vƠ đa giác, mƠ sử dụng tr ớc hết cho đa diện. Một tập hợp điểm xác định b i một mẫu đa thức đ n đ ợc gọi lƠ tập hợp đại số; Một tập hợp điểm có thể thu 53 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 b i một số hữu hạn của những phép hợp vƠ phép giao những tập hợp đại số đ ợc gọi một tập nửa đại số. Xem xét tr ng hợp của không gian 2D. Một biểu diễn 3 chiều có thể đ ợc định nghĩa nh sau: H  ( x , y )  W | f(x, y)  0 (2.9) Hình 2.14 : (a) sử dụng f để phân chia R2 thành hai vùng. (b) sử dụng bốn mẫu đại số để mô hình hoá vùng mặt. Ví dụ 1 : cho f = x2 + y2 - 4. Trong tr tròn bán kính r=2, tơm đ ợc đặt đúng ng hợp nƠy, H đại diện đ gốc. Điều nƠy t ng ng ứng tới tập hợp của những điểm (x, y) cho f(x, y) = 0, điều nƠy đ ợc miêu tả trong Hình 2.14a. Ví dụ 2 : (khuôn mặt) xem xét việc xơy dựng một mô hình của vùng đậm mƠu trong Hình 2.14b. Giả sử vòng tròn ngoƠi có bán kính r1 vƠ tơm đ ợc đặt tại gốc. Giả thiết “ đôi mắt ” có bán kính r2 vƠ r3 vƠ tơm t ng ứng lƠ ( x2, y2) vƠ ( x3, y3) cho “ miệng ” lƠ một hình ê-líp với trục chính a vƠ trục phụ b tơm lƠ ( 0, y4). Khi đó các hƠm đ ợc định nghĩa nh sau: f1  x 2  y 2  r12 f 2  (( x  x2 )2  ( y  y 2 )2  r22 ) f 3  (( x  x3 )2  ( y  y3 )2  r32 ) (2.10) f 4  ( x 2 / a 2  ( y  y 4 )2 / b 2  1 ) 54 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 f2, f3, vƠ f4, lƠ những ph ng trình đ ng tròn vƠ hình ê-líp đ ợc nhơn với - 1 để sinh ra những mẫu đại số cho tất cả các điểm bên ngoƠi đ hoặc hình ê-líp. Vùng O đậm mƠu đ ợc t O  H1  H 2  H 3  H 4 Trong tr ng tròn ng ứng nh sau: (2.11) ng hợp của những mô hình nửa đại số, phép giao của các mẫu không nhất thiết có kết quả trong một tập con lồi W. Nhìn chung, nó có thể cần thiết để hình thƠnh O b i việc lấy hợp vƠ giao của những mẫu đại số. Rõ rƠng biểu diễn bằng mô hình nửa đại số có thể khái quát hóa dễ dƠng tr ng hợp không gian 3 chiều. Ta có dạng đại số nguyên thuỷ của mẫu : H  (x, y, z)  W | f(x, y, z)  0 (2.12) Có thể sử dụng để định nghĩa một biểu diễn của ch ớng ngại 3 chiều O vƠ một vị từ lôgíc  . Ph ng trình (3.10) vƠ (3.13) đủ để biểu thị bất kỳ mô hình nƠo mƠ ta cần quan tơm. Có thể định nghĩa mẫu theo nhiều cách khác nhau dựa vƠo những quan hệ khác nhau, nh : f(x, y, z)  0, f(x, y, z) = 0, f(x, y,z) < 0, f(x, y, z) = 0, và f(x, y, z)  0 Xét mẫu: H  (x, y, z)  W | f(x, y, z)  0 (2.13) Có thể biểu diễn theo cách khác nh - f(x, y, z)  0, vƠ - f có thể đ ợc xem xét nh một hƠm đa thức mới của x, y, z. Một ví dụ qua hệ bằng: H  (x, y, z)  W | f(x, y, z)  0 Có thể thay H = H1  H2, với H1: H  (x, y, z)  W | f(x, y, z)  0 (2.15) vƠ H2 H  (x, y, z)  W | f(x, y, z)  0 (2.14) (2.16) Quan hệ < tăng thêm sức mạnh sẽ rất có ý nghĩa khi xơy dựng những mô hình không chứa đ ng biên ngoƠi. Chú ý rằng phần đậm mƠu luôn luôn bên trái khi đi theo những mũi tên. 55 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 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 2.4.3. 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). 2.4.3.1. Định nghĩa cấu hình chướng ngại. Đầu ch ng chúng ta đƣ có khái niệm s khai về cấu hình không gian ch ớng ngại vật. Bơy gi chúng ta sẽ nghiên cứu chi tiết h n về vấn đề nƠy. 1-Vùng chướng ngại cho một vật thể Giả thiết không gian W = R2 hoặc W = R3, Chứa đựng một vùng ch ớng ngại O  W. Đồng th i cũng giả thiết đơy một robot cứng, A  W, ( A vƠ O đ ợc trình bƠy nh những mô hình nửa đại số ( bao gồm những mô hình đa diện vƠ đa giác). Cho q  C biểu thị cấu hình của A, trong đó q=(xt, yt,  ) với W = R2 vƠ q = ( xt, yt, zt, h) với W = R3 (h lƠ đ n vị quaternion). Vùng ch ớng ngại, Cobs  C, đ ợc định nghĩa nh sau: Cobs  q  C | A( q )  O   Cobs lƠ tập hợp của tất cả các cấu hình q, (2.17) đó A(q) (trạng thái của robot tại cấu hình q) giao với vùng ch ớng ngại O. O vƠ A(q) lƠ những tập hợp đóng bên trong W, vùng ch ớng ngại lƠ một tập hợp đóng trong C. Những cấu hình còn lại đ ợc gọi không gian trống, mƠ đ ợc định nghĩa vƠ Cfree= C\Cobs. 56 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ừ đó C lƠ một không gian tôpô vƠ Cobs lƠ đóng, Cfree phải lƠ một tập hợp m . Điều đó có nghĩa lƠ robot có thể đến gần những ch ớng ngại một cách tuỳ ý trong những phần của Cfree miễn lƠ đ int( O )  int( A( q ))   ng biên của chúng không giao nhau. and O  A( q )   (2.18) Nếu A chạm vƠo O thì q  Cobs. Điều kiện nhận biết duy nhất lƠ những đ biên của chúng cắt nhau.Ý t ng ng robot có thể đến gần những ch ớng ngại một cách tuỳ ý có thể không có ý nghĩa thực tiễn trong kỹ thuật rôbôt, nh ng nó lƠm cho những giải thuật lập lộ trình chuyển động tr nên minh bạch. Khi Cfree m , nó không thể đạt đ ợc sự tối u nh tìm kiếm đ Trong tr ng ngắn nhất. ng hợp nƠy, tập đóng, cl(Cfree), cần phải thay vƠo để sử dụng. 2- Chướng ngại vật có nhiều vật thể: Nếu robot phức tạp thì vấn đề tr nên rắc rối h n, đơy chúng ta chỉ nghiên cứu giải thuật với các robot điểm. Hình 2.16 : C-space và nhiệm vụ tìm đường từ qI đến qG trong Cfree. C = Cfree  Cobs. Chúng ta sẽ dùng ký hiệu Ai cho mối liên kết i, mặc dù vƠi tham số của q có thể không thích hợp cho mối liên kết chuyển động Ai. Ví dụ, trong một dơy chuyền động học, cấu hình của vật thể thứ hai không phụ thuộc vƠo góc giữa vật thể thứ chín vƠ vật thể thứ m i. Gọi P lƠ tập hợp của những cặp va chạm, trong đó mỗi sự va chạm lƠ một cặp đôi, (i,j)  P,trong đó i,j lƠ chỉ số mối liên kết vƠ i, j  { 1, 2,. . . , m }, 57 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ới i  j. Nếu (i,j) xuất hiện bên trong P, nó có nghĩa lƠ Ai vƠ Aj ch a cho phép để trong một cấu hình, q, nghĩa lƠ Ai(q)  Aj(q)   Cho m vật thể, P thông th ng có kích th ớc O(m2); Tuy nhiên, trong thực tế có thể để loại trừ nhiều cặp b i sự phơn tích hình học nƠo đó của sự kết nối. Sử dụng P, xem xét những sự va chạm của robot có thể định nghĩa : m   Cobs    q  C | Ai ( q )  O       q  C | Ai ( q )  A ( q )    (2.19)  i 1   i , j P  Nh vậy, một cấu hình q  C trong Cobs nếu tồn tại ít nhất một mối liên kết va chạm với O hoặc một cặp trong những mối liên kết P va chạm với O. 2.4.4. Đị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. Cụ thể bƠi toán nƠy có các thƠnh phần chính sau: 1. Một không gian W lƠ một trong hai tr ng hợp W = R2 hoặc W=R3. 2. Một vùng ch ớng ngại lƠ một mô hình nửa đại số O  W trên không gian. 3. Một robot cũng lƠ một mô hình nửa đại số đ ợc định nghĩa trong W. Nó có thể lƠ một robot đ n A hoặc lƠ một tập hợp của m những mối liên kết A1, A2,. ,Am. 4. Không gian C cấu hình xác định b i việc chỉ rõ tập hợp của tất cả những sự biến đổi có thể đ ợc áp dụng cho robot đ ợc dẫn xuất từ Cobs vƠ Cfree. 5. Trong một cấu hình, qI Cfree lƠ trạng thái ban đầu. 6. Trong một cấu hình, qG Cfree đ ợc chỉ định lƠ trạng thái đích. Một cặp cấu hình ban đầu vƠ cấu hình đích th ng đ ợc gọi một cặp truy vấn (hoặc truy vấn) ký hiệu lƠ ( qI, qG). 58 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 7. Một giải thuật phải tính toán thiết lập đ ợc một đ ng dẫn liên tục đầy đủ từ qI đến qG:  : [ 0, 1 ]  Cfree, nh vậy  (0) = qI vƠ  (1) = qG, hoặc phải chỉ ra rằng một đ ng dẫn nh vậy không tồn tại. 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. 3.1. MẠNG NƠRON NHÂN TẠO VÀ BÀI TOÁN LẬP LỘ TRÌNH. Những năm tr ớc đơy, một số nghiên cứu về khoa học máy học đ ợc trình bƠy vƠ đƣ đ ợc áp dụng để h ớng dẫn robot cải thiện các khả năng vƠ thao tác. Một trong những vấn đề quan trọng trong thiết kế vƠ phát triển hệ thống ng i máy di động thông minh lƠ khả năng tìm đ gồm cả khả năng lập lộ trình trong môi tr môi tr ng hoạt động của nó. Tuy nhiên, ng hoạt động của robot có thể không chính xác, rộng lớn, thay đổi hoặc có cấu trúc không rõ rƠng. Ng tr ng, điều nƠy bao i máy phải hiểu rõ về cấu trúc môi ng vƠ đi đ ợc đến đích mƠ không có sự va chạm, điều nƠy đòi hỏi ng i máy phải có khả năng nhận thức, xử lý dữ liệu, đoán nhận, học, suy luận, hƠnh động vƠ ra quyết định. Những khả năng nƠy đ ợc xơy dựng dựa trên chìa khóa lƠ một loại trí tuệ nhơn tạo, tái sản xuất loại trí tuệ nƠy, cho tới nay vẫn lƠ một tham vọng mƠ con ng i mong muốn đạt tới để xơy dựng vƠ phát triển những hệ máy thông minh, đặc biệt lƠ đối với sự chuyển động của ng i máy. Để đạt đ ợc sự hợp lý trong các hƠnh động tự động của mình thì ng i máy đòi hỏi phải có hai khả năng c bản lƠ: Cảm nhận vƠ suy luận, dựa trên những thông tin về các trạng thái lơn cận thu nhận đ ợc b i hệ thống cảm biến. Những khả năng nƠy đ ợc thể hiện qua các giải thuật vƠ căn cứ vƠo các giải thuật nƠy để điều khiển robot hoạt động. 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. Công việc xác định lộ trình lƠ tìm ra một đ ng đi liên tục từ vị trí ban đầu đến vị trí đích sao cho tránh đ ợc những va trạm với những vật cản trên đ ng đi. 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) + Không gian tìm kiếm lƠ xơy dựng các cấu hình các mối quan hệ của đối t ợng đƣ cho vƠ các ch ớng ngại vật. + Quá trình tìm đ ng lƠ xác định một đ ng đi từ vị trí đầu đến vị trí đích sao cho tránh đ ợc sự va chạm với các vật cản. Nhiều ph ng pháp sử dụng ý t ng xơy dựng không gian cấu hình đƣ đ ợc đề xuất để giải quyết bƠi toán tìm đ ng. Tuy nhiên các ph ng pháp nƠy cũng tỏ rõ một số nh ợc điểm nh : những tính toán để tạo ra không gian cấu hình từ cấu trúc của ng i máy vƠ các ch ớng ngại vật rất phức tạp, số b ớc tìm kiếm sẽ tăng theo cấp luỹ thừa với số nút t ng ứng. Những nh ợc điểm nêu trên chính lƠ động lực để các nhƠ khoa học nghiên cứu giải pháp mới đó lƠ sử dụng những giải thuật song song với tốc độ tính toán đ ợc cải tiến để giải quyết bƠi toán trên. Mạng n ron lƠ một cấu trúc mạng cho phép dữ liệu đ ợc xử lý song song vƠ phơn tán gần nh đồng th i trên nhiều n ron. 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. 61 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.2. ỨNG DỤNG MẠNG HOPFIELD GI I QUY T BÀI TOÁN LẬP LỘ TRÌNH CHO ROBOT. 3.2.1. 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. Việc di chuyển đòi hỏi Robot phải có khả năng tránh các ch ớng ngại vật vƠ tìm đ ng đi tới đích. Trong lĩnh vực nƠy có một vƠi cách tiếp cận, xung quanh vấn đề môi tr Một trong những ph wallfollowing. Trong ph ng pháp tìm đ ng tĩnh vƠ động. ng tự động lƠ ph ng pháp nƠy, Robot tự động tìm đ chuyển động dọc theo những bức t ng ng pháp ng dựa vƠo một khoảng cách đặt sẵn, trong khi xem xét những ch ớng ngại chỉ lƠ những bức t ng khác. Tuy nhiên, với những tính toán đ n giản, cách tiếp cận nƠy chỉ có những ứng dụng đối với một số robot không đòi hỏi phải có những chuyển động phức tạp nh : Robot dọn dẹp sƠn nhƠ trong một hƠnh lang dƠi. Một sự cải tiến dựa trên ph pháp nƠy lƠ cách tiếp cận dò tìm mép, n i những vị trí các đ ng ng biên thẳng đứng của ch ớng ngại đ ợc định rõ vƠ robot di chuyển xung quanh tất cả các mép đó. Tuy nhiên cách tiếp cận nƠy phụ thuộc quá lớn vƠo sự chính xác của bộ sensor(cảm biến). Sự phối hợp có tác động lớn tới khả năng tự động tìm đ ng lƠ ph ng pháp Potential Fields, đ ợc đề xuất b i Khatib. đơy, những ch ớng ngại đ ợc xem nh những tơm điểm đẩy ra vƠ những đích nh những tơm điểm hấp dẫn. Robot đi ngang qua con đ khả năng nhất. Một nh ợc điểm của ph ng của đ ng dốc ít ng pháp nƠy lƠ phải giả thiết rằng mô hình của những ch ớng ngại vật phải đuợc biết tr ớc. Những nh ợc điểm nêu trên sẽ phần nƠo đ ợc khắc phục khi sử dụng mạng n ron. 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. Cụ thể, ta đƣ sử dụng một mô hình lỏng lẻo dựa vƠo học cạnh tranh. Các ch ớng ngại vật có thể xuất hiện bất kì trên đ ng di chuyển của Robot vƠ đ những vị trí ng nhiên chúng cũng có hình giáng tuỳ ý. Không giống đa số các cách tiếp cận tr ớc đơy, ph ng pháp nƠy không yêu cầu bức tranh toƠn cảnh về lộ trình của robot. Mỗi n ron trong mạng n ron chỉ có những kết nối cục bộ, chúng liên tục cập nhật để thể hiện những hoạt động đ ợc phát sinh trong môi tr ng hoạt động từ đó h ớng dẫn Robot về đích. Tất cả điều nƠy xảy ra trong th i gian thực vƠ khi đó quá trình xác định đ ng đi sẽ diễn ra một các nhanh chóng. 3.2.2. Phư ng pháp do Yang vƠ Meng đề xuất. Ý tưởng Mô hình của chúng ta thực chất dựa vƠo n ron đ ợc mô phỏng theo cách thức hoạt động của n ron sinh học. Phần nƠy sẽ trình bƠy những mô hình mạng đ ợc phát triển b i Yang vƠ Meng. Mô hình nƠy sẽ lƠ c s để giải quyết bƠi toán trên. Một n ron có n đầu vƠo. Khi đó, kiến trúc mạng sẽ t không gian cấu hình Robot N- chiều. Môi tr lƠ môi tr ng ứng tới một ng hoạt động N ron về c bản ng động trong không gian cấu hình . Những n ron đ ợc sắp đặt trong ngữ cảnh r i rạc của không gian cấu hình . N ron i đ ợc gắn liền với đại l ợng xi lƠ tín hiệu vƠo tại n ron i vƠ các tín hiệu từ bên ngoƠi Ii. Ph ng trình (1) xác định trạng thái của n ron i: k dxi   Ax i  ( B  xi )([ I i ]    wij [ x j ]  )  ( D  xi )[ I i ]  dt j 1 (3.1) Những tham số A, B vƠ D cho biết tốc độ thấp, cao vƠ rất cao của hoạt động thần kinh, t ng ứng. Biến xi lƠ một biến liên tục   D , B  . Giá trị I=E nếu n ron thứ i t ng ứng tới một đích, I = - E nếu nó lƠ một ch ớng ngại, trong các tr ng hợp khác I = 0. (I lƠ tín hiệu từ bên ngoƠi _bias) E lƠ một số 63 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 d ng t ng đối lớn. [Ii ]- lƠ kìm hƣm đ ợc nhập vƠo đ ợc gơy ra b i những ch ớng ngại, trong khi ([ I i ]   wij [ x j ]  ) LƠ kích thích nhập vƠo  k j 1 cho đích vƠ kết nối cục bộ giữa những n ron. - HƠm phi tuyến [ a] + vƠ [a] - đ ợc định nghĩa nh sau: [a] += Max { a, 0 } [a] - = Max {- a, 0 }. - qi vƠ qj lƠ véc t xác định vị trí của n ron i vƠ j t - Trọng số wij t ng ứng. ng ứng của đầu vƠo i với đ n vị j đ ợc xác định nh sau: wij  f (| d ij |) , đơy d ij | qi  q j | LƠ khoảng cách giữa i vƠ những n ron q trong . f(a) lƠ hƠm kích hoạt. HƠm nƠy đƣ đ ợc Yang vƠ Meng sử dụng.  lƠ một số d   f (a)  a 0 0  a  r0 a  r0 va a0 (3.2) ng. HƠm chức năng nƠy bảo đảm rằng một n ron có những kết nối cục bộ trong một vùng nhỏ xung quanh nó với bán kính lƠ r0. Nh vậy hiệu ứng của những ch ớng ngại lƠ đại l ợng cục bộ còn hiệu ứng của đích lƠ đại l ợng toƠn cục. Sự chuyển động của Robot đ ợc quyết định b i việc chọn một n ron chiếm u thế trong không gian của các n ron. Cho a đ ợc định vị trong S, vị trí nƠy biểu thị b i qp, định vị vị trí qn tiếp theo bằng cách gọi lệnh định vị. qn  xq  max( xi ,i  1,2,...,k ) n (3.3) Trong đó k lƠ số những n ron lơn cận. B ớc tiếp theo ta lại tiếp tục xem xét những n ron lơn cận với n ron t ng xứng với vị trí hiện tại của Robot vƠ 64 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 sẽ di chuyển tới vị trí xác định b i một n ron lơn cận chiếm u thế tiếp theo ( bao gồm cả n ron t ng xứng với vị trí hiện th i). Tóm tắt phương pháp  Ký hiệu: qI: Vị trí đầu. qG: Vị trí đích. qp: Vị trí hiện hƠnh. qn: Vị tí tiếp theo. Kt: dùng để kiểm tra xem có còn xác định đ ợc vị trí tiếp theo  Ph khác với vị trí hiện hƠnh không. ng pháp B1: Kh i tạo + Xác định vị trí đầu qI + Xác định vị trí đích qG + Gán qp=qI B2: Chừng nƠo qp<>qG vƠ KT=true thì còn lƠm các công việc sau: + Tính các xi căn cứ vƠo ph ng trình động học (3.1) vƠ hƠm f(a) (3.2) + Xác định vị trí tiếp theo qn dựa vƠo (3.3) + 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 cứu, ta nên xem xét các ph ng pháp đang nghiên ng trình ( 3.1), ( 3.2) vƠ (3.3), đơy sẽ lƠ c s để trình bƠy các vấn đề tiếp theo. i. Theo (3.3), một n ron với giá trị xi cƠng cao sẽ cƠng có khả năng thu hút Robot, trong khi một n ron với một giá trị thấp h n sẽ đẩy lùi robot. ii. B vƠ - D lƠ cận trên vƠ cận d ới của xi. iii. Số hạng thứ hai sử dụng toán tử [ ]+, Số hạng nƠy hiển thị những ảnh h ng của những giá trị d ng tính ( Đơy có thể lƠ những đích tiềm tƠng hoặc những điểm thu hút Ii vƠ xj). Số hạng thứ ba sử dụng toán tử []- lƠ ảnh h ng của những giá trị ng ợc (những ch ớng ngại tiềm tƠng hoặc những phản xạ của Ii). iv. Chính trong Số hạng thứ hai ảnh h ng của những n ron lơn cận đ ợc xem xét. Giá trị nƠy thể hiện những đặc điểm trong khi tính đến ảnh h ng (của) những n ron lơn cận thông qua số l ợng [ xi ]+ đƣ đ ợc chọn. Điều nƠy bảo đảm rằng những n ron nối ng ợc lơn cận sẽ không ảnh h ng đến hoạt động của n ron i. Điều nƠy có nghĩa lƠ mặc dầu có những tín hiệu về một đích nƠo đó đ ợc truyền lan từ một n ron khác tới lơn cận của nó song thông tin về một ch ớng ngại vật sẽ không thể sinh ra theo ph ng thức t ng tự nh trên nếu ta áp dụng ph ng trình (3.1). Điều nƠy thể hiện sự thu hút robot về phía đích vƠ kh ớc từ ch ớng ngại vật trên đ ng chúng di chuyển. Trong thực tế, khi đ ợc đặt trong một mê cung phức tạp với một đích xa robot th ng vấp phải ch ớng ngại vật hoặc tìm cách đi xuyên qua nó. Những ví dụ d ới đơy sẽ thể hiện rõ h n về những nhận xét trên. v. Phép toán cộng trong (3.1) đ ợc thực hiệu qua tất cả các n ron lơn cận kể cả chính nó. Từ (3.2) ta có wii=f(0)=0 do dii=0. 66 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 vi. Theo (3.3), vị trí mới của robot sẽ đ ợc xác định bằng cách tìm ra n ron có giá trị tín hiệu đầu vƠo cao nhất, kể cả bản thơn nó. Vì vậy robot không thể lùi lại khi gặp một mê cung phức tạp phía tr ớc trên lộ trình của mình. Trong tr ng hợp xấu nhất robot có thể tự giao động quanh một vị trí nƠo đó. Từ đó ta có thể thấy rõ sự logic của việc xác định sự u tiên của các n ron mƠ robot đi qua. 3.2.3. Mô hình Yang vƠ Meng cải tiến Ý tưởng Dựa vƠo những nhận xét nêu trên mô hình có thể đ ợc sửa đổi nh sau: + Theo iv ta cần sửa đổi (1) nh sau: k k dxi   Ax i  ( B  xi )([ I i ]     wij [ x j ]  )  ( D  xi )([ I i ]     wij [ x j ]  ) dt j 1 j 1 (3.4) Trong đó: 0    1, Chú ý:   1, 0   1   0 ứng với mô hình nguyên bản của Yang vƠ Meng + Để giải quyết những vấn đề đƣ đề cập trong vi, một kỹ thuật mới đ ợc đ a ra. Để đảm bảo cho Robot có khả năng quay lại vị trí th ớc đó mƠ nó đƣ đi qua, ngoƠi giá trị nhập vƠo Ii ta cần đ a vƠo thêm nột giá trị để xác định quá trình quay tr lại của robot (gọi giá trị nƠy lƠ giá trị ng ợc).Ta có thể lấy ngay ví dụ trong mô phỏng trên nh sau: Vị trí đến thăm vƠo lần cuối cùng ta cho giá trị ng ợc lƠ -E / 8, vị trí đến thăm tr ớc đó 2 b ớc ta xác định giá trị ng ợc lƠ -E / 16 vƠ vị trí đến thăm tr ớc đó 3 b ớc thì giá trị đ ợc gán lƠ -E / 32... Tất cả những vị trí đƣ duyệt qua ta đều xác định giá trị ng ợc nƠy vƠ cập nhật cho Ii t trí nh đƣ nêu ng ứng. Điều nƠy cũng đảm bảo robot sẽ không bị kẹt tại một vị vi. MƠ tại mỗi b ớc robot bắt buộc phải di chuyển tới một vị trí nƠo đó hiệu quả h n. Tóm tắt phương pháp 67 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ý hiệu: qI: Vị trí đầu. qG: Vị trí đích. qp: Vị trí hiện hƠnh. qn: Vị tí tiếp theo. Ti: giá trị ng ợc của n ron i Kt: dùng để kiểm tra xem có còn xác định đ ợc vị trí tiếp theo không  Ph ng pháp B1: Kh i tạo + Xác định vị trí đầu qI + Xác định vị trí đích qG + Kh i tạo Ti + Gán qp=qI B2: Chừng nƠo qp<>qG vƠ KT=true thì còn lƠm các công việc sau: + Tính các xi căn cứ vƠo ph ng trình động học (3.4) vƠ hƠm f(a) (3.2) + Xác định vị trí tiếp theo qn dựa vƠo (3.3) + 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. CÁC K T QU TH NGHIỆM 3.3.1. Chư ng trình đề mô Với những lý thuyết đƣ nghiên cứu, tác giả đƣ cƠi đặt mô hình thử nghiệm bằng ngôn ngữ Visual Basic. Môi tr ng lƠm việc của robot đ ợc thể hiện bằng các mê cung, các mê cung nƠy đ ợc tạo thƠnh dựa trên l ới với các ô định tr ớc. Cụ thể giao diện ch ng trình đ ợc trình bƠy trong hình 3.1 vƠ hình 3.2: Hình 3.1. Giao diện chương trình mô hình nguyên bản. Hìmh 3.2. Giao diện chương trình mô hình cải tiến. Chức năng vƠ hoạt động của các nút lệnh trong ch ng trình: + Nút kh i tạo: Đ a l ới tr về trạng thái sẵn sƠng để tạo một mê cung vƠ xác định một lộ trình mới. 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. + Nút XĐ vị trí đầu: Cho phép xác định vị trí xuất pháp của robot. + Nút XĐ vị trí cuối: Cho phép xác định vị trí đích. + Nút Thực hiện: Khi click nút nƠy trên l ới sẽ hiển thị sự di chuyển của robot vƠ lộ trình t Để cƠi đặt các ch ng ứng. ng trình thử nghiệm ta cần phải lựa chọn các tham số cho phù hợp. Trong ch ng trình đề mô các tham số đ ợc lựa chọn nh sau: + Mô hình nguyên bản: A=10, B=D =1, =1, r0=2 vƠ E = 100. + Mô hình cải tiến: E = 100, A = 10, B = 5, D = 1, r0 = 1.41,  = 0.9 vƠ  = 0.2. Ch ng trình cƠi đặt bằng ngôn ngữ Visual basic sẽ thể hiện trực quan các kết quả mô phỏng vì nó cung cấp nhiều công cụ để thể hiện giao diện đồ hoạ sinh động thơn thiện với ng Robot thể hiện trong ch i sử dụng. ng trình đềmô lƠ các robot điểm còn trong thực tế với những robot phức tạp ta cần phải tính đề tác động của cấu trúc của robot đối với việc di chuyển vƠ lộ trình mƠ not xác định. Khi cải đặt ch ng trình trong thực tế các tham số nhập từ môi tr ng ngoƠi sẽ đ ợc robot thu nhận thông qua các thiết bị cảm biến trong quá trình di chuyển của nó. Với ph thể về cầu trúc môi tr ng pháp nƠy robot cũng không cần phải hiểu cụ ng cũng nh các ch ớng ngại vật trong quá trình di chuyển nó sẽ căn cứ vƠo thuật toán mƠ xác định vị trí khả thi để di chuyển tới. Với ph ng pháp nƠy thì công việc khó khăn lƠ xơy dựng cấu hình không gian vƠ cấu hình ch ớng ngại trình bƠy trong ch ng 2 lƠ không còn cần thiết, do đó sẽ đẩy nhanh đ ợc tốc độ xác định lộ trình. 70 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.2. So sánh các kết quả Trong mục nƠy ta sẽ đ a ra các kết quả so sánh giữa mô hình nguyên bản vƠ mô hình sửa đổi, trong nhiều tr ng hợp mê cung vƠ đích có độ phức tạp khác nhau. Cho hai robot điểm di chuyển trong hai mê cung có cấu trúc giống hệt nhau. 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. Các dấu tròn đánh dấu con đ ng mƠ robot đƣ đi qua. Ta sẽ quan sát quá trình di chuyển của robot vƠ đ a ra những nhận xét cho hai mô hình. Từ những kết quả của ch ng trình mô phỏng ta có thể thấy rõ tính khả thi cũng nh hiệu quả của từng ph ng pháp. Đồng th i thấy đ ợc những u nh ợc điểm của chúng. Từ đó có thể lựa chọn chính xác các ph các tr ng án trong ng hợp cụ thể. + Mê cung 1 Hình 3.3a. Mê cung 1 Hình 3.3b. Mô hình nguyên bản Hình 3.3c. Mô hình sửa đổi + Mê cung 2 71 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 Hình 3.4a. Mê cung Hình 3.4b. Mô hình nguyên bản Hình 3.4c. Mô hình sửa đổi + Mê cung 3 Hình 3.5a. Mê cung Hình 3.5b. Mô hình nguyên bản Hình 3.5b. Mô hình sửa đổi 72 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 Nhận xét: + Trong mê cung 1 đ ng đi tới đích lƠ khá dễ dƠng. Khi đó cả hai mô hình đều dẫn dắt robot tới đích vƠ hai mô hình đều thực hiện tốt nh nhau. + Trong mê cung 2 ta đặt một vật cản chia đôi khu vực đích. Với mô hình nguyên bản robot mắc bẫy vƠ không hoƠn thƠnh sứ mệnh của mình. Trong khi mô hình sửa đổi có thể h ớng dẫn robot tránh bẫy bằng cách loại trừ những noron hiện th i vƠ bắt buộc robot đi qua con đ ng có thể băng qua vật cản để đến đích. + Trong mê cung 3 lƠ một tr ng hợp đ n giản. Tuy nhiên với mô hình nguyên bản thì lại gặp tr ngại vƠ robot không thể đi đ ợc đến đích. Truy nhiên ph ng trình (3.4) lại khắc phục đ ợc điều nƠy khi đó robot sẽ xoay s vƠ tìm cách đi xung quanh ch ớng ngại vật để đến đích. + Từ các kết quả trên ta cũng nhận thấy việc lựa chọn các tham số cũng lƠ công việc khá quan trọng, nó quyết định quá trình xác định các lộ trình. Song lƠm cách nƠo để lựa chọn đ ợc các tham só tối u lƠ một vấn đề khá khó khăn vƠ đơy cũng có thể coi lƠ một h ớng m của luận văn. + 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 nếu tồn tại đ ng pháp cải tiến sẽ luôn xác định đ ợc một lộ trình ng đi từ vị trí đầu đến vị trí đích. 3.3.3. Kết luận Ph ng pháp nguyên bản của Yang vƠ Meng đƣ trình bƠy trên đ ợc phát triển với mục đích điều khiển các thiết bị máy móc chuyển động tránh các vật cản. Đơy lƠ một mô hình lỏng lẻo với nền tảng lƠ học cạnh tranh đ ợc ánh xạ vƠo một mạng n ron. Trong đó, mỗi n ron chỉ có những kết nối cục bộ vƠ ph ng pháp nƠy không đòi hỏi bức tranh toƠn cảnh về môi tr ng hoạt động của robot khi xác định lộ trình. 73 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 Tuy nhiên ph những môi tr ph ng pháp nƠy sẽ kém hiệu quả khi robot hoạt động trong ng phức tạp. Để khắc phục điều nƠy ng i ta đƣ cải tiến ng pháp của Yang vƠ meng bằng cách thay đổi một số tham số trong (3.1), khi đó ta có ph ng trình (3.4). Ph định đ ợc lộ trình vƠ tránh đ ợc bẫy trên đ ng pháp nƠy cho phép robot xác ng di chuyển. Để mô phỏng hoạt động của hai mô hình nêu trên, ng i ta đƣ thể hiện hoạt động của robot trong 3 mê cung với cấu trúc khác nhau. Khi đó rõ rƠng ph ng pháp cải tiến tỏ ra rất hiệu quả. Trong khi, ph chỉ tìm ra đ ng đi trong mê cung 1 thì ph xoay s vƠ tìm ra đ ng pháp nguyên bản ng pháp cải tiến đƣ giúp robot ng tới đích trong cả 3 mê cung. Với ph ng pháp cải tiến tại mỗi b ớc robot bắt buộc phải tiến tới một vị trí khác có nhiều khả năng tiến tới đích h n điều nƠy giúp robot không bị kẹt tại một điểm vƠ tăng khả năng di chuyển đến đích của robot. Tuy nhiên, những ph ng pháp nƠy vẫn thể hiện một nh ợc điểm đó lƠ khi robot gặp tr ngại vƠ không thể đến đích chúng bắt buộc phải xác định lại toƠn bộ lộ trình vƠ điều nƠy hoƠn toƠn có thể đ ợc khắc phục bằng cách lựa chọn những tham số tối u để có một lộ trình tốt nhất. Việc xác định các tham số tối u lƠ một công việc không đ n giản vì ch a có một c s khoa học nƠo để h ớng dẫn việc nƠy. Do vậy, đơy có thể coi lƠ một h ớng m của luận vă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. Đƣ hệ thống c s của mạng n ron nhơn tạo, đặc biệt lƠ mạng Hopfield, nêu khái quát những ứng dụng của mạng n ron trong công nghệ robot. 2. Đƣ 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ó. 3. Đƣ 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. 5. Đƣ cƠi đặt thử nghiệm hai mô hình đƣ nghiên cứu trên máy tính, kết quả đạt đ ợc phản ánh chính xác những kết quả nghiên cứu. Các định hướng nghiên cứu tiếp theo Để xác định một lộ trình tốt nhất thì việc lựa chọn tham số phù hợp lƠ vô cùng cần thiết, tuy nhiên việc đó khá khó khăn vì ch a có một c s khoa học nƠo về lĩnh vực nƠy. Vì vậy h ớng nghiên cứu tiếp theo của luận văn lƠ tìm ra ph ng pháp lựa chọn tham số sao cho lộ trình tìm đ ợc lƠ tối u. 75 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ÀI LIỆU THAM KH O 1. Đặng Quang Á, Một cách nhìn về việc sử dụng mạng Hopfield giải các bƠi toán thỏa mƣn rang buộc vƠ tối u có rƠng buộc, Báo cáo tại Hội thảo quốc gia “Một số vấn đề chọn lọc của công nghệ thông tin”, Hải phòng 6/2001. 2. Đặng Quang Á, ng dụng của mạng n ron trong tính toán, Sách “Hệ m , mạng n ron vƠ ứng dụng”, Chủ biên: Bùi công C ng, Nguyễn Doƣn Ph ớc, NhƠ XBKH-KT, HƠ nội, 2001, 199-211. 3. Nguyễn Đình Thúc, Lập trình tiến hoá, NhƠ XB Giáo dục, 2001. 4. Bekey, G. A. & Goldberg, K.Y, Neural Networks in Robotics. luwer Academic Publishers, ISBN 0-7923-9268-X, Boston(1993). 5. Brady M. , Robot Motion: Planning and Control, The MIT Press, ISBN 0262-02182-X, Cambridge(1982). 6. Janglová D. , Neural Networks in Mobile Robot Motion, International Journal of Advanced Robotic Systems,V. 1 No 1 (2004), 15-22. 7. Subhrajit Bhattacharya, Siddharth Talapatra, Robot Motion Planning Using Neural Networks: A Modified Theory, International Journal of Lateral Computing, Vol.2, No.1, 2005, 9-13. 76 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 PHỤ LỤC Mã l nh chư ng trình thử nghi m. Option Explicit Dim nutlenh, di, dj, ci, cj As Integer Dim x(1 To 12, 1 To 12) As Double Dim E(1 To 12, 1 To 12) As Double Dim Tt(1 To 12, 1 To 12) As Double Dim i, j, k, a, b, p, duong As Integer Dim m, tong, delta As Double Dim kt As Boolean Dim hd(1 To 12, 1 To 12) As Integer Private Sub Cmbkhoitao_Click() Dim i, j As Integer 'ma tran kich thich phan ung sua For i = 1 To 12 For j = 1 To 12 x(i, j) = -0.5 E(i, j) = 0 Tt(i, j) = 0 hd(i, j) = 0 Next Next 'khoi tao nut lenh nutlenh = 0 'Khoi tao luoi For i = 1 To 12 For j = 1 To 12 If i <> 11 Then T(Val(Str(i) & Str(j))).BackColor = &H80000005 T(Val(Str(i) & Str(j))).Text = "" T(Val(Str(i) & Str(j))).Font.Size = 8 T(Val(Str(i) & Str(j))).ForeColor = &H0& T(Val(Str(i) & Str(j))).Font.Bold = False Else If j > 9 Then T(Val(Str(i) & Str(j))).BackColor = &H80000005 T(Val(Str(i) & Str(j))).Text = "" T(Val(Str(i) & Str(j))).Font.Size = 8 77 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(Val(Str(i) & Str(j))).ForeColor = &H0& T(Val(Str(i) & Str(j))).Font.Bold = False Else T(Val(Str(i) & Str(0) & Str(j))).BackColor = &H80000005 T(Val(Str(i) & Str(0) & Str(j))).Text = "" T(Val(Str(i) & Str(0) & Str(j))).Font.Size = 8 T(Val(Str(i) & Str(0) & Str(j))).ForeColor = &H0& T(Val(Str(i) & Str(0) & Str(j))).Font.Bold = False End If End If Next j Next i Timer1.Enabled = False End Sub Private Sub Cmbmecung_Click() nutlenh = 1 End Sub Private Sub Cmbthoat_Click() Unload Me End Sub Private Sub Cmbthuchien_Click() i = di j = dj kt = False duong = 1 Timer1.Enabled = True End Sub Private Sub Cmbvtdau_Click() nutlenh = 2 End Sub Private Sub Cmbvtdich_Click() nutlenh = 3 End Sub Private Sub Form_Load() nutlenh = 0 Timer1.Enabled = False End Sub Sub T_Click(Index As Integer) 'tao me cung Dim i, j As Integer 78 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 Dim p, q, xhd As Integer If nutlenh = 1 Then T(Index).BackColor = &H80000006 For i = 1 To 12 For j = 1 To 12 If (i <> 11) Or (j > 9) Then If Val(Str(i) & Str(j)) = Index Then x(i, j) = -1 E(i, j) = -100 'Text1.Text = E(i, j) Tt(i, j) = 1 End If Else If Val(Str(i) & "0" & Str(j)) = Index Then x(i, j) = -1 E(i, j) = -100 Tt(i, j) = 1 'Text1.Text = E(i , j) End If End If Next j Next i End If 'xac dinh vi tri dau If nutlenh = 2 Then T(Index).ForeColor = &HFF& T(Index).Font.Bold = True T(Index).Font.Size = 12 T(Index).Text = " o" For i = 1 To 12 For j = 1 To 12 If (i <> 11) Or (j > 9) Then If (Val(Str(i) & Str(j)) = Index) Then di = i dj = j Tt(i, j) = 1 End If Else If (Val(Str(i) & "0" & Str(j)) = Index) Then di = i 79 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 dj = j Tt(i, j) = 1 End If End If Next j Next i End If 'xac dinh vi tri dich If nutlenh = 3 Then T(Index).ForeColor = &HC00000 T(Index).Font.Bold = True T(Index).Font.Size = 12 T(Index).Text = " o" For i = 1 To 12 For j = 1 To 12 If (i <> 11) Or (j > 9) Then If (Val(Str(i) & Str(j)) = Index) Then E(i, j) = 100 ci = i cj = j End If Else If (Val(Str(i) & "0" & Str(j)) = Index) Then E(i, j) = 100 ci = i cj = j End If End If Next j Next i End If End Sub Public Function max(a As Double, b As Double) As Double Dim m As Double If a > b Then m=a Else m=b End If max = m 80 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 End Function Public Function tinh_x(a As Integer, b As Integer) As Integer Dim tong, delta As Double tong = 0 If (a - 1 > 0) Then tong = tong + max(x(a - 1, b), 0) End If If (b - 1 > 0) Then tong = tong + max(x(a, b - 1), 0) End If If a + 1 <= 12 Then tong = tong + max(x(a + 1, b), 0) End If If b + 1 <= 12 Then tong = tong + max(x(a, b + 1), 0) End If delta = -10 * x(a, b) + (1 - x(a, b)) * (max(E(a, b), 0) + tong) - (-1 + x(a, b)) * max(-E(a, b), 0) x(a, b) = x(a, b) + delta tinh_x = 1 End Function Private Sub Timer1_Timer() If ((i <> ci) Or (j <> cj)) And (kt = False) Then If i <> 11 Or j > 9 Then T(Val(Str(i) & Str(j))).ForeColor = &H0& T(Val(Str(i) & Str(j))).Font.Size = 1 T(Val(Str(i) & Str(j))).Font.Bold = True T(Val(Str(i) & Str(j))).Text = " o" Else T(Val(Str(i) & Str(0) & Str(j))).ForeColor = &H0& T(Val(Str(i) & Str(0) & Str(j))).Font.Size = 1 T(Val(Str(i) & Str(0) & Str(j))).Font.Bold = True T(Val(Str(i) & Str(0) & Str(j))).Text = " o" End If Else If i <> 11 Or j > 9 Then T(Val(Str(i) & Str(j))).ForeColor = &HFF& T(Val(Str(i) & Str(j))).Font.Size = 12 T(Val(Str(i) & Str(j))).Font.Bold = True T(Val(Str(i) & Str(j))).Text = " o" 81 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 Else T(Val(Str(i) & Str(0) & Str(j))).ForeColor = &HFF& T(Val(Str(i) & Str(0) & Str(j))).Font.Size = 12 T(Val(Str(i) & Str(0) & Str(j))).Font.Bold = True T(Val(Str(i) & Str(0) & Str(j))).Text = " o" End If End If If ((i <> ci) Or (j <> cj)) And (kt = False) Then If (i - 1 > 0) Then If E(i - 1, j) <> -100 Then 'k = tinh_x(i - 1, j) a=i-1 b=j tong = 0 If (a - 1 > 0) Then tong = tong + max(x(a - 1, b), 0) End If If (b - 1 > 0) Then tong = tong + max(x(a, b - 1), 0) End If If a + 1 <= 12 Then tong = tong + max(x(a + 1, b), 0) End If If b + 1 <= 12 Then tong = tong + max(x(a, b + 1), 0) End If delta = -10 * x(a, b) + (1 - x(a, b)) * (max(E(a, b), 0) + tong) - (-1 + x(a,b)) * max(E(a, b), 0) x(a, b) = x(a, b) + 0.1 * delta '****** End If End If If (j - 1 > 0) Then If E(i, j - 1) <> -100 Then 'k = tinh_x(i, j - 1) a=i b=j-1 tong = 0 If (a - 1 > 0) Then tong = tong + max(x(a - 1, b), 0) 82 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 End If If (b - 1 > 0) Then tong = tong + max(x(a, b - 1), 0) End If If a + 1 <= 12 Then tong = tong + max(x(a + 1, b), 0) End If If b + 1 <= 12 Then tong = tong + max(x(a, b + 1), 0) End If delta = -10 * x(a, b) + (1 - x(a, b)) * (max(E(a, b), 0) + tong) - (-1 + x(a,b)) * max(E(a, b), 0) x(a, b) = x(a, b) + 0.1 * delta '****** End If End If If (j + 1 <= 12) Then If E(i, j + 1) <> -100 Then 'k = tinh_x(i, j + 1) a=i b=j+1 tong = 0 If (a - 1 > 0) Then tong = tong + max(x(a - 1, b), 0) End If If (b - 1 > 0) Then tong = tong + max(x(a, b - 1), 0) End If If a + 1 <= 12 Then tong = tong + max(x(a + 1, b), 0) End If If b + 1 <= 12 Then tong = tong + max(x(a, b + 1), 0) End If delta = -10 * x(a, b) + (1 - x(a, b)) * (max(E(a, b), 0) + tong) - (-1 + x(a,b)) * max(-E(a, b), 0) x(a, b) = x(a, b) + 0.1 * delta '******** End If 83 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 End If If (i + 1 <= 12) Then If E(i + 1, j) <> -100 Then 'k = tinh_x(i + 1, j) a=i+1 b=j tong = 0 If (a - 1 > 0) Then tong = tong + max(x(a - 1, b), 0) End If If (b - 1 > 0) Then tong = tong + max(x(a, b - 1), 0) End If If a + 1 <= 12 Then tong = tong + max(x(a + 1, b), 0) End If If b + 1 <= 12 Then tong = tong + max(x(a, b + 1), 0) End If delta = -10 * x(a, b) + (1 - x(a, b)) * (max(E(a, b), 0) + tong) - (-1 + x(a,b)) * max(-E(a, b), 0) x(a, b) = x(a, b) + 0.1 * delta '***** End If End If 'xac dinh gia tri lon nhat m = -1000000 p=0 If i - 1 > 0 Then If (m < x(i - 1, j)) And E(i - 1, j) <> -100 And Tt(i - 1, j) = 0 Then m = x(i - 1, j) End If End If If (j - 1 > 0) Then If (m < x(i, j - 1)) And E(i, j - 1) <> -100 And Tt(i, j - 1) = 0 Then m = x(i, j - 1) End If End If If (i + 1 <= 12) Then If (m < x(i + 1, j)) And E(i + 1, j) <> -100 And Tt(i + 1, j) = 0 Then 84 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 = x(i + 1, j) End If End If If (j + 1 <= 12) Then If (m < x(i, j + 1)) And E(i, j + 1) <> -100 And Tt(i, j + 1) = 0 Then m = x(i, j + 1) End If End If 'dinh vi vi tri tiep theo If i - 1 > 0 Then If (m = x(i - 1, j)) And (p = 0) And (E(i - 1, j) <> -100) And Tt(i - 1, j) = 0 Then i=i-1 p=1 End If End If If j - 1 > 0 Then If (m = x(i, j - 1)) And (p = 0) And (E(i, j - 1) <> -100) And Tt(i, j - 1) = 0 Then j=j-1 p=1 End If End If If i + 1 <= 12 Then If (m = x(i + 1, j)) And (p = 0) And (E(i + 1, j) <> -100) And Tt(i + 1,j)=0 Then i=i+1 p=1 End If End If If j + 1 <= 12 Then If (m = x(i, j + 1)) And (p = 0) And (E(i, j + 1) <> -100) And Tt(i, j +1)=0 Then j=j+1 p=1 End If End If If m <> -1000000 Then If i <> 11 Or j > 9 Then T(Val(Str(i) & Str(j))).ForeColor = &HFF& 85 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(Val(Str(i) & Str(j))).Font.Size = 12 T(Val(Str(i) & Str(j))).Font.Bold = True T(Val(Str(i) & Str(j))).Text = " o" Else T(Val(Str(i) & Str(0) & Str(j))).ForeColor = &HFF& T(Val(Str(i) & Str(0) & Str(j))).Font.Size = 12 T(Val(Str(i) & Str(0) & Str(j))).Font.Bold = True T(Val(Str(i) & Str(0) & Str(j))).Text = " o" End If Tt(i, j) = Tt(i, j) + 1 duong = duong + 1 Else kt = True End If End If End Sub 86 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