Tài liệu Thuyet_minh_copy

CHƯƠNG 1: TỔNG QUAN CHƯƠNG 1: TỔNG QUAN 1.1. Đặt vấn đề Cờ là một trò chơi phổ biến, một môn thể thao trí tuệ dành cho hai người, với nhiều thể thức thi đấu đa dạng. Tuy nhiên, sẽ như thế nào nếu giao nhiệm vụ đánh cờ cho máy thực hiện? Với nhịp sống hiện đại, thật khó để ngồi cùng nhau say sưa một ván cờ. Bởi hiếm để tìm được người cùng đam mê, cùng chấp nhận bỏ ra hàng giờ để tìm niềm vui nơi nhau. Vì thế, các ứng dụng chơi cờ ra đời và phát triển nhằm mục đích đáp ứng nhu cầu đó. Nhưng dần cũng không thỏa được đam mê của các kỳ thủ, đơn giản tính trực quan trong cờ rất được chú trọng. Nhận thấy, việc tạo ra một Robot đủ thông minh để đánh cờ sẽ phần nào giải quyết được yêu cầu trên. Bằng sự kết hợp giữa trí tuệ nhân tạo và thị giác máy tính sẽ là câu trả lời cho vấn đề này. 1.2. Sơ lược lịch sử các máy tính chơi cờ 1.2.1. Chiếc “máy giấy” của Turing Một điều thú vị là chương trình chơi cờ đầu tiên được viết trước khi chiếc máy tính đầu tiên được phát minh. Alan Turing – một nhà toán học lớn thời kỳ đó, là người đứng đầu nhóm phá mã bí mật “Enigma” của Đức, có ảnh hưởng lớn đến kết cục của chiến tranh thế giới thứ 2. Ông rất thích chơi cờ, và mặc dù đã dành rất nhiều công sức để học cờ nhưng ông vẫn là một người chơi cờ tương đối yếu. Sau chiến tranh, ông viết những lệnh để hướng dẫn máy tính chơi cờ. Vào thời điểm đó, chưa có chiếc máy tính nào có thể chạy được các lệnh, nên chính ông thực hiện các lệnh đó, đóng vai bộ xử lý trung tâm và cần khoảng nửa tiếng cho một nước đi. Một ván cờ được ghi lại, trong đó chiếc “paper machine” của Turing thua một đồng nghiệp. 1.2.2. Cờ thay vì bom nguyên tử Năm 1946, nhà toán học John von Neumann được giao thiết kế một chiếc máy tính để phục vụ cho việc chế tạo bom nguyên tử. Năm 1950, một chiếc máy khổng lồ 1 CHƯƠNG 1: TỔNG QUAN mang tên MANIAC I được chế tạo. Với hàng nghìn bóng chân không và công tắc như trong hình 1.1, nó có thể thực hiện 10000 lệnh trong một giây. Hình 1.1. Cỗ máy MANIAC I [1] Thay vì ngay lập tức bắt tay vào việc chế tạo bom, các nhà khoa học bắt đầu thí nghiệm với chiếc máy. Một trong những điều đầu tiên họ làm là viết một chương trình chơi cờ, chơi trên một bàn cờ thu nhỏ 6x6 và không có Tượng. Mặc dù vậy, chương trình này vẫn cần 12 phút để tìm kiếm trước 4 ply (ply là nửa nước đi), với Tượng trên bàn cờ nó sẽ cần khoảng 3 tiếng. 1.2.3. Cờ và toán học Vấn đề chính với các chương trình chơi cờ là số lượng lớn các nước phải tính toán. Một vị trí trung bình sẽ có khoảng 40 nước đi hợp lệ. Nếu tính tất cả các nước đi đối phương đáp trả sẽ có 40×40 = 1600 vị trí. Điều này có nghĩa là sau hai ply, được coi là một nước đi trong cờ, 1600 vị trí có thể xảy ra. Sau hai nước nó là 2,5 triệu vị trí và sau ba nước là 4,1 tỷ. Trung bình một ván cờ kéo dài khoảng 40 nước. Số vị trí cần tính là khoảng 10 mũ 128, lớn hơn cả số nguyên tử có trong vũ trụ (chỉ khoảng 10 mũ 80). Và không có chiếc máy tính hay loại máy nào có thể chơi cờ bằng cách tìm ra tất cả các khả năng. Nhưng con người cũng không phải là hoàn hảo. Câu hỏi là máy cần tìm kiếm tới độ sâu nào (trước bao nhiêu nước) để có thể đối chọi được với khả năng chiến lược của con người. Những chiếc máy tính thời đầu có thể tạo và đánh giá khoảng 500 vị trí trong một giây hay 90000 vị trí trong ba phút, đó là thời gian cho 2 CHƯƠNG 1: TỔNG QUAN phép để đi một nước trong các cuộc thi đấu. Điều này có nghĩa là chỉ có thể tìm kiếm trước 3 ply (một nước đi rưỡi). Từ đó cho thấy, nó chơi rất kém – chỉ ngang một người mới tập chơi. Để tìm kiếm sâu hơn nữa, cần giải quyết được 15000 vị trí trong một giây, nhanh hơn gấp 30 lần. Nhưng tính toán trước 4 ply cũng chưa đủ sâu. Do đó máy tính dường như không bao giờ có thể chơi cờ ở trình độ kiện tướng. 1.2.4. Chiếc máy Belle Ken Thompson – một nhà khoa học không thể chờ đợi những chiếc siêu máy tính giá hàng triệu đô trở lên, để có thể chơi cờ nhanh hơn 5 đến 25 lần. Ông và một đồng nghiệp ở Bell Laboratorié quyết định chế tạo một chiếc máy chỉ chuyên để chơi cờ, sử dụng hàng trăm con chip và giá khoảng 20 nghìn đô la. Hình 1.2. Chiếc máy Belle [1] Họ gọi chiếc máy đó là “Belle”, với hình dáng như trong hình 1.2. Nó có thể tìm kiếm tới 180000 vị trí trong một giây (siêu máy tính vào thời đó chỉ có thể tìm được 5000 vị trí). Belle có thể tìm trước 8 tới 9 ply trong các cuộc thi đấu, giúp nó có thể được chơi trong hàng kiện tướng. Nó thắng giải vô địch thế giới máy tính chơi cờ đầu tiên và tất cả những giải đấu khác từ năm 1980 đến 1983 cho tới khi bị chiếc máy khổng lồ Cray X-MPs, đắt hơn nó một nghìn lần, qua mặt. 1.2.5. HiTech Vào giữa những năm 80, giáo sư Hans Berliner, một nhà khoa học máy điện toán ở Đại học Carnegie-Mellon tiếp tục công việc của Ken Thompson. Ông đã chế tạo một chiếc máy tính có phần cứng đặc biệt để chơi cờ, gọi là HiTech. Với 64 chip chạy song 3 CHƯƠNG 1: TỔNG QUAN song, HiTech suýt nữa đạt danh hiệu vô địch máy tính đánh cờ vua thế giới vào năm 1986 (một chiếc Cray thắng giải này). Sau đó các sinh viên Feng-hsiung Hsu, Murray Campbell và những người khác tự phát triển một chiếc máy tính khác, được gọi là ChipTest và sau đó Deep Thought. Giá của nó khoảng 5 nghìn đô la, và có thể tính toán được 500000 vị trí trong một giây. 1.2.6. Deep Blue Nó gồm có một máy chủ IBM SP/2, cùng với các con chip đặc biệt để tính toán nhanh. Mỗi con chip có thể xử lý 2 đến 3 triệu vị trí một giây. Bằng việc sử dụng hơn 200 con chip này, tốc độ tổng cộng của chương trình có thể tăng lên tới 200 triệu vị trí trong một giây. Trong hình 1.3, chiếc Deep Blue tại bảo tàng Lịch sử Máy tính. Hình 1.3. Deep Blue [3] Năm 1997, nó đã đánh bại kỳ thủ vô địch thế giới lúc đó là Garry Kasparov. Tuy nhiên, Deep Blue chỉ là một chiếc máy chơi cờ thuần túy và nó không có khả năng tự di chuyển quân cờ. 1.3. Một số robot chơi cờ 1.3.1. Tay máy chơi cờ vua a) Robot CHESSka (Nga) 4 CHƯƠNG 1: TỔNG QUAN Tháng 6/2009, robot CHESSka lần đầu tiên được giới thiệu bởi Konstantin Kosteniuk – một huấn luyện viên cờ vua, đồng thời là một người sở hữu rất nhiều bằng sáng chế. Đây là một robot chơi cờ thực thụ với một cánh tay tự động có thể thực hiện thao tác gắp các quân cờ, di chuyển chúng đến ô khác, sau đó nhấn vào đồng hồ bấm giờ để hoàn tất nước cờ. Cũng giống như IBM Deep Blue khi được đặt vào thử thách với cờ thủ Garry Kasparov, CHESSka đã từng thi đấu với nhiều đại kiện tướng thế giới, thắng Aleksander Grischuk (Vô địch cờ chớp thế giới 2006), hòa Vladimir Borisovich Kramnik (Vô địch cờ tiêu chuẩn thế giới 2000-2006). Trong hình 1.4, CHESSka đang chơi cờ với Kramnik trước phần đông khán giả. Hình 1.4. CHESSka đọ sức cùng nhà vô địch thế giới Kramnik [2] Về cách thức hoạt động, CHESSka không hề nhìn thấy bàn cờ mà đúng hơn là nó được kết nối với bàn cờ. Các quân cờ tương tác với bàn cờ, qua đó robot có thể phát hiện khi nào một quân cờ được di chuyển và vị trí của nó, sau đó robot sẽ phản hồi lại bằng cách thực hiện nước đi của mình. Cơ cấu bàn tay của robot gồm 3 ngạnh cho phép đóng mở để gắp hoặc thả các quân cờ. 5 CHƯƠNG 1: TỔNG QUAN Hình 1.5. CHESSka và KUKA Monster trong trận chung kết năm 2012 [2] Bằng việc đánh bại đối thủ KUKA Monster trong trận chung kết năm 2012, CHESSka đã giành ngôi quán quân trong giải Robot World Chess. Trong hình 1.5, một ván cờ đang diễn ra giữa hai robot. b) Robot Gambit (Mỹ) Gambit là kết quả nghiên cứu của nhiều khoa, nhiều phòng thí nghiệm tại các trường Đại học, cùng với sự tài trợ của Intel. Hình 1.6. Robot Gambit Nó sử dụng 2 camera để nhận diện nước đi, đặc biệt với thiết kế cơ khí độc đáo giúp tay máy có thể xếp gọn lại gần giống với tay người. 1.3.2. Các nghiên cứu robot chơi cờ tướng a) Robot NI Intelligent 6 CHƯƠNG 1: TỔNG QUAN Hình 1.7. Robot NI Intelligent Được thiết kế bởi Yusheng Cai, Di Wu và Chunxiao Wu tại National Intrument Company. Với kết cấu PPP vững chắc, robot đi một nước cờ trong thời gian khá nhanh. Đặc biệt, có khả năng nhận diện từng quân và kết hợp AI vào thuật toán chơi cờ. Trong hình 1.8, robot dùng nam châm điện để hút và thả, đã hoàn thành sắp xếp các quân trên bàn cờ. b) Tay máy chơi cờ tướng Là đề tài luận văn của hai sinh viên khoa Điện – Điện tử, trường Đại học Bách Khoa Tp. HCM, Vũ Văn Khắc và Lê Bạch Quý Cường. Robot được cấu tạo dạng cánh tay, với một khớp tịnh tiến (dùng động cơ DC servo), và hai khớp xoay (dùng động cơ bước). Đầu công tác sử dụng nam châm điện. Hình 1.8. Robot chơi cờ tướng - Đề tài mang lại một số kết quả: + Nhận diện được tương đối chính xác nước đi trong điều kiện đảm bảo ánh sáng. + Giải thuật chơi cờ: với độ sâu 5 (tìm kiếm trước 5 ply), thời gian suy nghĩ 5s. - Hạn chế: + Độ cứng vững kém. + Tốc độ di chuyển còn chậm. + Chưa nhận dạng được quân cờ. 7 CHƯƠNG 1: TỔNG QUAN c) Bàn máy 2D nhận dạng và xếp quân cờ tướng Là đề tài luận văn của sinh viên khoa Cơ Khí, trường Đại học Bách KhoaTp. HCM, Nguyễn Phú Hiền. Bàn máy sử dụng động cơ bước để điều khiển hai trục xy, kết hợp khí nén để di chuyển quân cờ. Bước đầu đã nhận dạng được quân cờ, tuy nhiên thiếu chính xác đối với các quân màu đỏ. Và chỉ dừng lại ở việc sắp xếp quân trên bàn cờ. Hình 1.9. Bàn máy 2D 1.4. Mục tiêu, nhiệm vụ và phạm vi đề tài 1.4.1. Đầu bài - Các thông số đầu vào: + Kích thước bàn cờ: 360mm ± 1 x 400mm ± 1 + Kích thước ô cờ: 40mm x 40mm + Kích thước quân cờ: Các quân có dạng hình trụ, đường kính 28mm và chiều cao 8mm. - Đặc điểm hệ thống: + Gắp và đặt quân cờ, phạm vi di chuyển chủ yếu là mặt bàn cờ (mặt phẳng ngang), loại “pick and place”. + Các quân cờ đứng khá sát nhau, để di chuyển quân cờ: nhấc quân cờ lên cao khỏi các quân cờ khác, di chuyển quân cờ trong mặt phẳng, thả quân cờ xuống. 8 CHƯƠNG 1: TỔNG QUAN - Quân trên bàn cờ phải đặt đúng luật và quá trình di chuyển quân không được làm thay đổi vị trí các quân khác. - Không yêu cầu về hướng của quân cờ khi đặt xuống, vậy 3 bậc tự do là đủ để xác định vị trí, thao tác gắp thả không tính là bậc tự do tiếp theo. 1.4.2. Mục tiêu - Tạo ra một robot chơi cờ tướng với kết cấu vững chắc, tốc độ xử lý và đánh cờ nhanh. - Áp dụng tối đa các kiến thức đã được học về cơ khí, điện tử, và điều khiển trên cơ sở tính toán, xây dựng một mô hình tương đương để kiểm chứng giải thuật, kết hợp với camera giúp chụp lại nước đi, dùng máy tính phân tích và đưa ra vị trí gắp thả, di chuyển quân cờ thông qua những tọa độ được gửi từ máy tính. 1.4.3. Nhiệm vụ - Thiết kế cơ khí, xây dựng bản vẽ, chế tạo robot. + Lựa chọn phương án, lựa chọn cơ cấu. + Thiết kế, chế tạo bàn máy di chuyển XY: đồ gá động cơ, gá cảm biến… + Thiết kế, chế tạo pulley, chọn đai, bộ phận kẹp đai. + Thiết kế, chế tạo đầu công tác. + Thiết kế giá treo camera. - Xây dựng giải thuật điều khiển. + Tính chọn động cơ dẫn động. + Chọn bộ điều khiển. + Phương pháp điều khiển. + Viết chương trình giao tiếp giữa máy tính với bộ điều khiển. - Ứng dụng xử lý ảnh để nhận diện quân cờ, nhận diện nước đi. + Lựa chọn, tính toán gá đặt, hiệu chuẩn camera. + Tìm hiểu các thuật toán cơ bản: Candy, Hough… 9 CHƯƠNG 1: TỔNG QUAN + Xây dựng bộ cơ sở dữ liệu để nhận dạng quân cờ. + Thiết kế giao diện. - Xây dựng giải thuật chơi cờ. + Tìm hiểu các thuật toán: Minimax, Alpha-Beta… + Thiết kế giao diện. + Đánh giá thực nghiệm. 1.4.4. Phạm vi - Xây dựng giải thuật chơi cờ ở cấp độ đơn giản nhất. - Dựa trên đặc tính của đối tượng, tiến hành xác định những thông số cần thiết nhằm hạn chế tính vạn năng, tăng tính chuyên biệt để đạt độ chính xác cao nhất có thể, cụ thể hóa lựa chọn, giảm bớt mức độ phức tạp trong điều khiển và chi phí thiết kế thực hiện. - Tương tự như thiết kế máy, quá trình thiết kế robot cũng có tính kế thừa, tức căn cứ trên mẫu các thiết kế sẵn có, các kết cấu điển hình, đã làm việc ổn định để giảm bớt công việc thiết kế, khảo sát, tìm bộ kích thước phù hợp cho robot của đề tài. 1.5. Tổ chức luận văn Với mục tiêu và nhiệm vụ đề ra, đề tài được phân thành các chương có nội dung như sau: - Chương 2: Lựa chọn phương án - Chương 3: Tính toán, thiết kế bàn máy 2D, đầu công tác. - Chương 4: Kết nối thiết bị, đấu dây mạch điện. - Chương 5: Xây dựng giải thuật điều khiển, giao tiếp máy tính. - Chương 6: Ứng dụng xử lý ảnh để nhận diện quân cờ, nhận diện nước đi. - Chương 7: Xây dựng giải thuật chơi cờ. - Chương 8: Thực thi chương trình, đánh giá thực nghiệm. - Chương 9: Tổng kết kết quả. Hướng phát triển đề tài. 10 CHƯƠNG 1: TỔNG QUAN 11 CHƯƠNG 1: TỔNG QUAN CHƯƠNG 2: LỰA CHỌN PHƯƠNG ÁN Trong chương này, một vài tiêu chí sẽ được thể hiện để thiết kế robot, cùng với những yêu cầu về độ chính xác, độ chính xác lặp lại, chi phí thấp… 2.1. Lựa chọn kết cấu robot Để chọn được kết cấu phù hợp, cần phân tích, dựa vào yêu cầu của người thiết kế và các thông số của môi trường, hệ thống. Một số các phân tích đề xuất: - Gắp và đặt quân cờ, phạm vi di chuyển chủ yếu là mặt bàn cờ (mặt phẳng ngang), loại “pick and place”. Có một số kiểu phù hợp: Cartesian, 6 Axis, SCARA, Cylindrical… - Không yêu cầu về hướng của quân cờ khi đặt xuống, vậy 3 bậc tự do là đủ để xác định vị trí, thao tác gắp thả không tính là bậc tự do tiếp theo. - Các quân cờ đặt khá sát nhau, vì vậy độ chính xác, và độ chính xác lặp lại là hai yêu cầu quan trọng. Dựa vào các yếu tố bên trên, có 3 kiểu kết cấu phù hợp. 2.1.1. Kết cấu Crane Hình 2.1. Robot P.P.P (Crane) Đặc điểm: Công suất tải lớn. Hệ thống điều khiển đơn giản. Độ chính xác và độ chính xác lặp lại rất cao (0,1 – 1mm với tải 10-1000Kg). Đòi hỏi phải xây dựng hệ thống tuyến tính. 2.1.2. Kết cấu Cylindrical 12 CHƯƠNG 1: TỔNG QUAN Hình 2.2. Robot R.P.P (Cylindrical) Đặc điểm: Độ chính xác và độ chính xác lặp lại cao (0,1-0,5mm với tải 5-100Kg). Sai số vị trí lớn khi vươn xa (kết cấu console). Vận tốc thấp (1000 mm/s). 2.1.3. Kết cấu SCARA Hình 2.3. Robot R.R.P (SCARA) Đặc điểm: - Không gian hoạt động nhỏ. - Độ chính xác lặp lại cao (<0,025 với tải 10-100Kg). - Công suất tải thấp. Kết cấu PPP (Crane) được chọn bởi có độ chính xác và độ chính xác lặp lại cao hơn hai kết cấu còn lại. Mặt khác, không gian làm việc của Crane là hình chữ nhật phù hợp với bàn cờ. 2.2. Lựa chọn hệ thống dẫn động Có 3 loại thường dùng trong robot: điện, khí nén, thủy lực. 2.2.1. Điện Ưu điểm: 13 CHƯƠNG 1: TỔNG QUAN Cơ cấu tác động nhanh và chính xác. Nguồn điện luôn có sẵn. Không ồn, không ô nhiễm môi trường. Nhược điểm: Khi ngắt nguồn hệ thống không thể giữ vị trí. Gây quá nhiệt khi hệ thống bị dừng hoạt động do quá tải. 2.2.2. Khí nén Ưu điểm: Giá thành thấp (cùng công suất). Phù hợp với các nhiệm vụ cần đáp ứng nhanh. Nguồn khí nén phổ biến. Cơ cấu tác động có thể dừng mà không hư hỏng. Nhược điểm: Cần thiết bị cấp nguồn khí nén. Khí xả gây ồn. 2.2.3. Thủy lực Ưu điểm: Chịu tải trọng lớn. Vận hành êm. Tự bôi trơn và làm nguội. Nhược điểm: Chi phí cao. Không thích hợp cho hệ thống đòi hỏi tác động nhanh. Nguồn dầu kém phổ biến. Rò rỉ nguy hiểm. 14 CHƯƠNG 1: TỔNG QUAN 2.3. Lựa chọn cơ cấu tác động 2.3.1. Động cơ bước Hình 2.4. Động cơ UPK599-NAC - Ưu điểm: + Dễ điều khiển. + Độ chính xác cao. + Có thể tự giữ vị trí mà không cần bộ hãm. - Nhược điểm: + Điều khiển vòng hở. + Không nhận biết được quá tải (khi nào xuất hiện trượt bước). 2.3.2. Động cơ DC servo Hình 2.5. Động cơ NISCA NF5475E - Ưu điểm: - Có hồi tiếp. 15 CHƯƠNG 1: TỔNG QUAN - Nhận biết quá tải thông qua hồi tiếp dòng. - Việc chọn độ chính xác độc lập với chọn công suất động cơ. - Nhược điểm: + Không có khả năng giữ tải. + Đa số hoạt động ở tốc độ cao (moment chịu tải không lớn). 2.3.3. Động cơ AC servo 2.4. Lựa chọn bộ truyền động Do kết cấu robot được chọn là PPP, nên cần phải chọn bộ truyền động tuyến tính. Có một số đề xuất được đưa ra. 2.4.1. Pulley – đai răng Hình 2.6. Pulley đai răng Kích thước nhỏ gọn. Giá thành thấp. Khoảng cách trục lớn. Công suất cao n = 0,92 – 0,98 2.4.2. Vít me – đai ốc 16 CHƯƠNG 1: TỔNG QUAN Hình 2.7. Vít me – đai ốc Làm việc êm. Hiệu suất cao. Ma sát trong thời gian dài, làm giảm hiệu suất. Vận tốc chậm. 2.4.3. Vít me bi Hình 2.8. Vít me bi Làm việc êm. Hiệu suất cao. Giá thành cao. 2.5. Lựa chọn đầu công tác 2.5.1. Tay gắp điện 17 CHƯƠNG 1: TỔNG QUAN Hình 2.8. Tay gắp điện Chính xác cao. Giá thành thấp. Cần không gian lớn. Lực giữ nhỏ. 2.5.2. Tay gắp khí nén Hình 2.9. Tay gắp khí nén Nhỏ gọn. Cần không gian lớn. 2.5.3. Giắc hút Hình 2.10. Giắc hút Chiếm ít không gian. Thích hợp với bề mặt phẳng. 2.5.4. Nam châm điện 18 CHƯƠNG 1: TỔNG QUAN 2.10. Nam châm điện 2.6. Giá treo camera Yêu cầu: - Độ cứng vững, ổn định cao để camera không bị rung, thay đổi vị trí khi chụp ảnh. - Không chiếm quá nhiểu không gian, tránh ảnh hưởng tầm nhìn của người chơi. - Không cản trở hoạt động gắp thả quân cờ. - Dễ dàng lắp đặt, hiệu chỉnh. Các phương án: - Hai thanh trượt: kết cấu đơn giản, không chiếm nhiều diện tích. Hình 2.11. Sơ đồ nguyên lý dạng hai thanh trượt - Crane: độ cứng vững cao. 19 CHƯƠNG 1: TỔNG QUAN Hình 2.12. Sơ đồ nguyên lý dạng Crane 20