Luận văn Nghiên cứu, thiết kế robot dò đường đi bằng sóng siêu âm

Nếu phương pháp điều hướng theo phản ứng không kết hợp với bất cứ quá trình lập kế hoạch chuyển động nào thì có thể sẽ không đưa robot theo quỹ đạo tối ưu. Phương pháp điều khiển lai ra đời nhằm kết hợp các hoạt động có tính toán bậc cao với các hoạt động phản ứng bậc thấp. Các hoạt động phản ứng giúp robot an toàn và xử lý các tình trạng khẩn cấp trong khi phần điều khiển có tính toán sẽ giúp robot đạt được mục đích cuối cùng. Phương pháp điều khiển lai ghép có thể cho ta kết quả khả quan hơn khi chỉ sử dụng phương pháp điều hướng theo phản ứng hoặc điều hướng theo tính toán. Tính cấp thiết của đề tài 1.4. Vấn đề được quan tâm khi nghiên cứu về robot tự hành là làm thế nào để robot biết được vị trí nó đang đứng và có thể di chuyển tới một vị trí xác định, đồng thời truyền thông tin của các bức tường trong mê cung mà nó đi qua. Để giải quyết vấn đề này tác giả đề xuất sử dụng mobile robot di chuyển bằng bánh dò dường trong một mê cung đơn giản, có các bức tường là vật liệu có thể phản hồi tốt sóng siêu âm ta có thể sử dụng cảm biến siêu âm thông qua module thu phát không dây truyền nhận dữ liệu với máy tính từ đó tìm ra được đường đi ngắn nhất thoát khỏi mê cung. Đó là lý do tác giả chọn đề tài “Nghiên cứu, thiết kế robot dò đƣờng đi bằng sóng siêu âm”. Việc nghiên cứu thành công đề tài này sẽ mở ra một hướng tiếp cận mới và góp phần thúc đẩy việc ứng dụng của robot ngày càng nhiều vào trong đời sống hằng ngày và trong nghiên cứu chế tạo. Ngoài ra, mô hình cũng sẽ là sự bổ sung cần thiết về các giải pháp công nghệ di chuyển của các mobile robot làm phong phú những lựa chọn giải pháp về chuyển động trong không gian cho các robot. Mục tiêu và nội dung nghiên cứu 1.5. 1.5.1. Mục tiêu của đề tài - Xây dựng mô hình toán cho Mobile Robot có hai bánh chủ động. 12 - Xây dựng thuật giải tìm đường đi và truyền dữ liệu mê cung cho Mobile Robot. - Thi công mô hình thực nghiệm cho Mobile Robot dò đường bằng sóng siêu âm. - Viết giao diện dò đường cho Mobile Robot theo thời gian thực qua phần mềm Matlab GUI. - Từ dữ liệu mê cung do Mobile Robot tìm được, áp dụng thuật toán tìm đường đi ngắn nhất trong mê cung cho Mobile Robot. 1.5.2. Nội dung nghiên cứu 1.5.2.1 Đối tƣợng nghiên cứu - Giải thuật tìm đường đi cho Mobile Robot. - Giải thuật tìm đường đi ngắn nhất. - Module RF UART, module cảm biến siêu âm. - Vi điều khiển ARM. 1.5.2.2 Phạm vi nghiên cứu - Đề tài chỉ nghiên cứu về Mobile Robot có hai bánh chủ động. - Do Robot di chuyển bên trong nhà xưởng, bỏ qua các lực tác động bên ngoài ảnh hưởng đến hoạt động của Robot. Vì vậy luận văn chỉ xây dựng mô hình động học cho Robot. - Thiết kế giải thuật tìm đường đi cho Mobile Robot. - Lựa chọn giải thuật tìm đường đi ngắn nhất cho Mobile Robot. - Hiển thị kết quả lên phần mềm Matlab và thi công mô hình thực nghiệm. Tổng quan về lĩnh vực nghiên cứu 1.6. 1.6.1. Giới thiệu tổng quan chung về lĩnh vực nghiên cứu Vấn đề dùng robot vẽ bản đồ là một lĩnh vực nghiên cứu rất được quan tâm trong ngành robotics và trí tuệ nhân tạo trong hai thập niên gần đây. Quá trình hình thành bản đồ của môi trường xung quanh robot liên quan đến hai việc: mô hình hóa các yêu tố vật lý của môi trường và xây dựng được một robot tự hành hoàn hảo. Hiện tại, con người đã nghiên cứu và tạo ra nhiều phương pháp vẽ bản đồ cho các môi trường tĩnh, có cấu trúc nhất định và có kích thước giới hạn. Tuy nhiên, đối 13 với môi trường không có cấu trúc nhất định, động và có kích thước lớn, các nhiên cứu vẫn còn hạn chế và cần nghiên cứu thêm. Hầu hết các robot tự hành phải thực hiện hai qua trình song song : định vị bản thân và nhận diện vật cản của môi trường xung quanh. Tiếp theo là di chuyển, Robot tự hành nên di chuyển như thế nào và cơ cấu di chuyển nào là sự lựa chọn tốt nhất. Bài toán dẫn đường là vấn đề cơ bản trong nghiên cứu và chế tạo Robot tự hành. Bài toán dẫn đường cho robot tự hành được chia làm 2 loại: bài toán toàn cục (global) và bài toán cục bộ (local). Ở bài toàn cục, môi trường làm việc của robot hoàn toàn xác định,đường đi và vật cản là hoàn toàn biết trước. Ở bài toán cục bộ, môi trường hoạt động của robot là chưa biết trước hoặc chỉ biết một phần. Các cảm biến và thiết bị định vị cho phép robot xác định được vật cản, vị trí của nó trong môi trường giúp nó đi tới được mục tiêu. Các nghiên cứu trong và ngoài nước cũng đang hướng theo hai bài toán này. 1.6.2. Tình hình nghiên cứu trên thế giới A New shortes path finding algorithm a maze sloving robot with simulator Trong bài báo này tác giả không sử dụng các thuật toán tìm đường kinh điển như Wall-Follow, Pledge, Tremaux, Flood Fill mà dựa trên giải thuật mới. Trong thuật toán này Robot sẽ đi qua hoặc truy cập hầu hết các khối mê cung và tìm tất cả các con đường có sẵn dẫn đến đích, mỗi con đường sẽ được so sánh với con đường tìm thất trước đó và chọn con đường ngắn nhất. Phương pháp này có thể không phải là nhanh nhất trong một số trường hợp nhưng nó đảm bảo tìm được đường đi ngắn nhất, ít phức tạp nhất và sẽ tốn ít bộ nhớ vi điều khiển hơn so với thuật toán kinh điển. Thuật toán này chỉ tìm được đường đi với mê cung đã biết trước. 14 Hình 1.9. Sơ đồ tìm đường đi của giải thuật Hình 1.10. Giao diện mô phỏng mê cung A Mobile Robot sloving a virtual Maze Environment Bài báo giới thiệu một khái niệm mới trong việc tìm đường cho Robot trong mê cung đó là sử dụng các mê cung ảo trong kiểm tra tối ưu với các thuật toán khác nhau. Mô phỏng Robot di động trong môi trường ảo, tính toán sau đó điều khiển Robot qua truyền thông không dây. Tác giả đã thiết kế giao diện (GUI) của mê cung ảo và hệ thống tọa độ ảo của mê cung. Robot sử dụng thuật toán bám tường cải tiến để tìm đường đi thông qua các mê cung ảo được thiết kế sẵn. Trong bài báo này, hai thuật toán tìm đường đã được sử dụng để tìm đường và một thuật toán để tối ưu hóa đường đi. Để điều khiển và giao tiếp giữa Robot và máy 15 tính tác giả sử dụng các chuẩn giao tiếp không dây. Tuy nhiên bài báo chỉ dừng lại ở mê cung đã biết trước, còn các mê cung chưa xác định thì bài báo chưa đề cập đến. Hình 1.11. Giao diện (GUI) mô phỏng mê cung Hình 1.12. Tọa độ ảo của mê cung Design and Implementation of a Robot for Maze-Solving using Flood-Fill Algorithm. Bài báo mô tả các bước thực hiện một robot dùng để tìm đường trong mê cung dựa trên thuật toán Floodfill. Phát hiện các bức tường trong mê cung bằng cách sử dụng cảm biến siêu âm. Hiệu chỉnh đường thẳng bằng bộ điều khiển PI (D). Các robot có thể học được mê cung, tìm tất cả các tuyến đường và tìm đường đi ngắn nhất. 16 Tác giả sử dụng mô hình robot cỡ nhỏ để tìm hiểu làm thế nào điều hướng robot trong môi trường chưa biết dựa trên các thông tin đã biết trước và thông tin thu thập được từ cảm biến, từ đó đưa ra các quyết định của mình. Hình 1.13. Robot cỡ nhỏ sử dụng trong bài báo Tác giả đã chứng minh được thuật toán floodfill là công cụ hiệu quả để giải quyết bài toán tìm đường trong một mê cung đơn giản. Để đưa ra các quyết định điều hướng cho robot tác giả dựa trên đầu vào từ nhiều cảm biến, cụ thể là cảm biến siêu âm và đọc encoder trên động cơ. Robot có thể định vị chính xác vị trí của nó trong mê cung khi bị sai lệch do lỗi thiết kế cơ khí bằng cách sử dụng một bộ điều khiển PI. Robot có thể dò hết mê cung trong lần đầu tiên và thứ hai. Trong lần chay thứ ba robot có thể chạy đến vị trí đích nhanh nhất bằng thuật toán flloofill với thông tin của mê cung đã tìm được trong hai phần trước. Hình 1.14. Mê cung thiết kế và mê cung thực tế 17 Hướng phát triển của bài báo trong tương lai bao gồm việc mở rộng mê cung lớn hơn và phức tạp hơn. Như vậy khi cung được thiết kê và xây dựng lại các robot sẽ phải giải quyết các vấn đề phức tạp hơn. Để đạt độ chính xác cao trong việc phát hiện các bức tường, robot cần được trang bị các cảm biến tốt hơn như cảm biến laser. Kinh phí trang bị cảm biến laser nhiều hơn cảm biến siêu âm tuy nhiên khả năng quét các bức tường trong mê cung với một góc rộng hơn so với góc quét của cảm biến siêu âm. Tuy nhiên bài báo không thực hiện việc trao đổi dữ liệu, vẽ mê cung với máy tính theo thời gian thực. 1.6.3. Tình hình nghiên cứu trong nƣớc Bài báo “Study on Control of Wall-Following Mobile Robot Using Sonar Sensor ” Tác giả sử dụng phương pháp dò đường Wall-Following vì tác giả cho rằng đây là một phương pháp đơn giản, hữu ích trong cả hai môi trường mê cung đã biết và chưa biết. Phương pháp này được sử dụng nhiều trong các bài toán tìm đường mê cung. Robot dò đường theo kiểu “Wall-Following” thường được trang bị cảm biến có khả năng đo hướng và khoảng cách, chẳng hạn như cảm biến laser, cảm biến hồng ngoại nhưng ở đây tác giả chọn cảm biến siêu âm vì giá thành thấp và sử dụng phổ biến. Bộ quan sát của Busawon được sử dụng để ước lượng khoảng cách giữa Robot và một bức tường với khoảng cách cho trước. Hình 1.15. Robot thí nghiệm Hình 1.16. Kết quả thí nghiệm 18 Bài báo “Thiết kế Robot Mini tự hành dò đƣờng trong mê cung” Bài báo đã chỉ ra được vấn đề rất được quan tâm khi nghiên cứu về robot tự hành là làm thế nào để robot biết được vị trí nó đang đứng và có thể di chuyển tới một vị trí xác định, đồng thời có thể tự động tránh được các chướng ngại vật trên đường đi, cụ thể bài báo sử dụng thuật toán tìm đường flooding. Đồng thời thiết kế được mạch cảm biến, chọn được khung máy, động cơ, vi điều khiển, mạch điều khiển động cơ, mạch nguồn. Hình 1.17. Sơ đồ khối Mobile Robot Bài báo cơ bản đã giải quyết được vấn đề tìm đường, Robot chạy được với các mê cung khác nhau nhưng về phần cơ khí chưa đạt độ chính xác như yêu cầu, cảm biến không hiệu quả ở các môi trường khác nhau, phải sử dụng nguồn bên ngoài. Hình 1.18. Robot chạy trong mê cung Lựa chọn và cách bố trí bánh xe 1.7. Phân tích, chọn bánh xe và cách bố trí bánh xe: 19 Dựa vào yêu cầu luận văn là dò đường trong một mê cung có bề mặt đường đi phẳng, không lồi lõm. Do đó ta sẽ chọn bánh xe thường kết hợp bánh xe tự lựa làm bộ phận chuyển động cho robot. Bánh xe yêu cầu có độ linh hoạt cao, dễ dàng xoay trở trong mê cung tác giả nêu ra một số phương án bố trí bánh xe:  Hai bánh chuyển động vi sai và thêm 2 điểm tiếp xúc. Hình 1.19. Hai bánh chuyển động vi sai Phương án này sử dụng hai động cơ dẫn động và hai bánh xe tự lựa làm cho robot di chuyển rất linh hoạt trong mê cung. Nhưng nếu cả bốn bánh tiếp xúc đất không hoàn hảo sẽ khiến robot không bám được đường đi, các tín hiệu đưa về bộ xử lí bị sai lệch dẫn đến robot không đi đúng đường.  Hai bánh truyền động được nối với trục ở phía sau, một bánh lái ở phía trước. Hình 1.20. Hai bánh truyền động phía sau Phương án này chỉ sử dụng một động cơ dẫn động cho hai bánh sau và một bánh trước điều khiển do vậy khi di chuyển bánh điều khiển phải điều chỉnh liên tục hai bánh sau để cho robot đi đúng đường. Nếu phối hợp không tốt sẽ làm cho robot vượt quá vị trí yêu cầu. Điều này làm giảm khả năng linh hoạt của robot, robot sẽ xoay trở rất kém trong không gian nhỏ. - Hai bánh truyền động ở giữa và có điểm thứ 3 tiếp xúc 20 Hình 1.21. Hai bánh truyền động ở giữa có điểm thứ ba tiếp xúc Phương án này làm tăng tính linh hoạt của robot trong không gian nhỏ, đây là điều mà luận văn yêu cầu. Do vậy tác giả sử dụng phương án này. 21 Chƣơng 2: MÊ CUNG VÀ GIẢI THUẬT TÌM ĐƢỜNG TRONG MÊ CUNG Robot vẽ bản đồ 2.1. 2.1.1. Vấn đề định vị của Robot tự hành Vấn đề của robot tự hành là làm thế nào để robot có thể nhận biết môi trường và thực thi các nhiệm vụ đề ra. Robot tự hành nên di chuyển như thế nào và cơ cấu di chuyển nào là hợp lý nhất cho một môi trường hoặc một số môi trường xác định. Do vậy, điều hướng là vấn đề cơ bản trong nghiên cứu và chế tạo Robot tự hành. Có thể nói, muốn điều hướng thành công, nhất thiết robot phải được trang bị hoàn thiện 4 khâu sau: Mapping: là công việc lập bản đồ môi trường hoạt động của robot. Nếu robot chưa được cung cấp dữ liệu trước thì robot phải có khả năng lập bản đồ. Path planning: là việc hoạch định đường đi sắp tới của robot, sau khi nó biết được bản đồ và biết được nó đang ở vị trí nào. Motion control: là việc điều khiển cho robot di động, tức là điều khiển các cơ cấu để robot đi theo con đường thu được từ bài toán “path planning”. Trong các ứng dụng robot, có hai phương pháp định vị thường được sử dụng là phương pháp định vị tuyệt đối (APM) và phương pháp định vị tương đối (Relative Positioning Methods - RPM). Phương pháp định vị tương đối chủ yếu dựa trên bài toán dead-reckoning, đây là phương pháp định vị được sử dụng rộng rãi và “truyền thống” nhất là đối với robot tự hành. Robot sẽ được trang bị cảm biến (thường là encoder) để xác định số vòng quay của bánh xe, từ đó suy ra khoảng cách đã di chuyển, cùng với một la bàn số để suy ra góc quay so với hướng ban đầu. Từ hai thông tin trên ta xác định được tọa độ (x, y) và hướng hiện tại (θ) của robot tại mỗi thời điểm t. Tuy nhiên, nguyên tắc cơ bản của phương pháp dead-reckoning là tích lũy thông tin về chuyển động theo thời gian, điều này dẫn tới sự tích lũ sai số. Sự tích lũy này làm cho sai số vị trí tăng tỉ lệ theo khoảng cách chuyển động của Robot. Ưu điểm của phương pháp này là nguyên lý toán học đơn giản, các bước đọc và xử lí thông tin cảm biến đơn giản, dễ sử dụng. Muốn giảm sai số cho phương pháp dead-reckoning, cần phải tang độ chính xác động học, nghĩa là tăng độ chính xác cho các chi tiết cơ khí như độ đồng trục của 2 motor, khoảng cách giữa 2 bánh xe, đường kính bánh xe. 22 Phương pháp định vị tuyệt đối thì lại dùng thêm các cảm biến khác ngoài encoder như dùng beacon, cột mốc, so sánh các bản đồ cục bộ và bản đồ toàn cục, định vị bằng vệ tinh (GPS) Trong mỗi phương pháp định vị tuyệt đối, người ta sử dụng các thuật toán và cảm biến khác nhau, nhưng đều là những phương pháp chủ yếu dùng cho mobile robot ngày nay. Theo kinh nghiệm, người ta thường dùng phương pháp định vị tương đối để giới hạn phạm vi xử lý trước khi dùng phương pháp định vị tuyệt đối để xác định vị trí robot. Như vậy, cho dù sử dụng bất kỳ phương pháp định vị nào đi nữa thì phương pháp dead- reckoning dường như luôn là sự lựa chọn đầu tiên. Tại một thời điểm, khi xác định được vị trí của mình robot cần lấy thông tin về môi trường xung quanh, thông thường robot sẽ sử dụng cảm biến siêu âm hoặc camera xử lí hình ảnh. 2.1.2. Sóng siêu âm Sóng siêu âm là sóng âm thanh có tần số lớn hơn tần số âm nghe thấy (trên 20KHz). Chỉ có một số loài vật như dơi, ong có thể cảm nhận được sóng siêu âm. Sóng siêu âm có thể phát hiện ra hầu hết các đối tượng là kim loại hoặc không phải kim lọa, chất lỏng hoặc chất rắn, vật trong hoặc mờ đục (vật có hệ số phản xạ sóng âm thanh đủ lớn). Dựa vào đặc điểm vận tốc âm thanh là hằng số, thời gian sóng âm thanh đi từ bộ phận phát đến đối tượng và quay trở lại bộ phận thu liên hệ trực tiếp đến độ dài quãng đường người ta chế tạo ra cảm biến siêu âm để xác định vị trí của các vật. Robot sử dụng cảm biến siêu âm bằng cách phát ra sóng siêu âm khi gặp vật cản thì phản xạ lại, dựa vào thời gian di chuyển của sóng đi và về sẽ xác định được khoảng cách tới vật cản. Ưu điểm của cảm biến siêu âm: Khoảng cách cảm biến phát hiện của cảm biến có thể lên tới 15m. Sóng phản hồi của cảm biến không phụ thuộc vào màu sắc của bề mặt đối tượng hay tính chất phản xạ ánh sáng của đối tượng. 23 Tín hiệu ngõ ra có thể là digital hoặc analog. Tín hiệu từ cảm biến là digital báo có hay không sự xuất hiện của đối tượng trong vùng cảm nhận của cảm biến, tín hiệu từ cảm biến là analog chứa đựng thông tin khoảng cách của đối tượng đến cảm biến. Tín hiệu đáp ứng của cảm biến tiệm cận analog tỉ lệ tuyến tính với khoảng cách. Điều này đặc biệt lí tưởng cho các ứng dụng ngư theo dõi các mức vật chất, mức độ chuyển động của đối tượng. Phương pháp sử dụng hiện tượng sóng phản xạ có các bước tính toán khá đơn giản, dễ sử dụng, được áp dụng trong nhiều lĩnh vực tuy nhiên cần lưu ý một số khuyết điểm. Nhược điểm của cảm biến siêu âm: Cảm biến siêu âm yêu câu đối tượng phải có diện tích bề mặt đủ lớn. Sóng phản hồi cảm biến nhận được cò thể chịu ảnh hưởng của sóng âm thanh tạp âm. Cảm biến siêu âm yêu cầu một khoảng thời gian sau mỗi lần sóng phát đi để sẵn sàng nhận sóng phản hồi. Kết quả cảm biến tiệm cận siêu âm nhìn chung chậm hơn các cảm biến khác. Với các dối tượng có mật độ vật chất thấp như bọt hay vải quần áo rất khó để phát hiện với khoảng cách lớn. Cảm biến siêu âm bị giới hạn bởi khoảng cách phát hiện nhỏ nhất. Bề mặt phẳng phản hồi năng lượng của sóng siêu âm tốt hơn bề mặt ghề ghề, tuy nhiên góc tạo thành giữa cảm biến và mặt phẳng phải vuông góc với nhau. Tuy nhiên với yêu cầu luận văn trong môi trường xác định như nhà xưởng, bề mặt phản xạ là các bức tường, không cần tín hiệu đáp ứng quá nhanh, thì cảm biến siêu âm hoàn toàn phù hợp với yêu cầu của bài toán tìm đường trong mê cung. 2.1.3. Camera xử lí hình ảnh Robot sẽ đượng trang bị trước những “kiến thức” về môi trường (các hình ảnh của môi trường được chụp, mã hóa thành các đường, điểm và hình khối). Camera quay lại hình ảnh của môi trường, truyền dữ liệu của môi trường cho hệ thống xử lí 24 hình ảnh để xác định khoảng cách tới các hình khối của môi trường. Phương pháp này tuy nhận được các hình ảnh cụ thể của môi trường nhưng việc tính toán, xử lí hình ảnh, lọc nhiễu rất tốn thời gian và phức tạp. 2.1.4. Lựa chọn phƣơng án định vị và nhận diện vật cản Để đạt được mục đích định vị và nhận diện vật cản một cách hiệu quả cần áp dụng nhiều phương pháp như sau: Sử dụng phương pháp dead-reckoning để xác định quãng đường và góc quay của robot sau các quãng thời gian nhất định. Sử dụng cảm biến siêu âm gắn trên robot để xác định khoảng cách từ robot đến các vật cản quanh nó. Sau một thời gian nhất định, các vật cản sẽ đóng vai trò như các cột mốc để robot điều chỉnh lại tọa độ tuyệt đối của mình so với gốc. Mê cung và các thuật toán tìm đƣờng trong mê cung 2.2. Hiện nay, từ một số loại mê cung cơ bản, người ta đã phát triển nhiều loại mê cung với độ phức tạp khác nhau như block maze, logic maze, planair maze, weave maze Trong luận văn này chỉ tập trung vào hai loại mê cung cơ bản là mê cung đơn kết nối (simply connected maze) và mê cung đa kết nối (multiply connected maze). Mê cung đơn kết nối (simply connected maze): tất cả các bức tường kết nối với nhau hoặc kết nối với đường bao mê cung. Do cấu tạo của mê cung khá đơn giản nên ta có thể dùng giải thuật “ bám tường”, người đi sẽ tìm được lối ra trên tường bao, nếu mê cung là mê cung kín thì sẽ trở về điểm xuất phát, người đi sẽ không bỏ sót bất cứ đường nào trong mê cung. Hình 2.1. Mê cung đơn kết nối 25 Mê cung đa kết nối (multiply connected maze): mê cung loại này bao gồm nhiều mảng, mỗi mảng là các tường kết nối nhau nhưng hoàn toàn không kết nối với đường bao hoặc với các tường khác. Với loại mê cung này nếu áp dụng giải thuật “bám tường” sẽ khiến cho robot lặp đi lặp lại các bước di chuyển trước mà không thể thoát ra khỏi mê cung. Hình 2.2. Mê cung đa kết nối Do vậy các thuật toán tìm đường trong mê cung được phát triển để giải quyết bài toán này. Các thuật toán tìm đường đi trong mê cung là những phương pháp được tự động hóa để giải một mê cung. Các thuật toán chọn đường ngẫu nhiên, bám theo tường, Pledge, và Trémaux được xây dựng để cung cấp cho robot hướng đi trong mê cung mà hoàn toàn không biết trước về mê cung, còn các thuật toán lấp kín đường cụt và đường đi ngắn nhất được thiết kế để sử dụng khi đã biết trước toàn bộ mê cung. Thuật toán tìm đƣờng ngẫu nhiên 2.3. Đây là giải thuật đơn giản nhất, giải thuật này chỉ đơn giản là chạy theo một đường thẳng cho đến khi gặp một đường giao nhau thì đưa ra quyết định ngẫu nhiên về hướng tiếp theo để chạy. Mặc dù phương pháp này cuối cùng cũng thoát ra dược khỏi mê cung, nhưng thuật toán này có thể phải thực hiện trong khoảng thời gian rất lâu, thời gian thực thi không thể biết trước, robot thường xuyên lặp lại những ô đã đi trước đó. Sau khi kết thúc quá trình, robot không thu về được thông tin của mê cung đã đi qua. Thuật toán bám theo tƣờng 2.4. Thuật toán bám theo tường (wall follower) là một quy tắc nổi tiếng nhất để vượt qua mê cung, còn được gọi là quy tắc tay trái hoặc quy tắc tay phải. Nếu là mê cung đơn kết nối nghĩa là tất cả các bức tường của nó được kết nối với nhau hoặc kết nối với 26 đường bao quanh mê cung, thì bằng cách dò một tay lên một bức tường của mê cung người đi đảm bảo không bị lạc và tìm được lối ra nếu có một lối ra trên đường bao; hoặc nếu không có lối ra thì sẽ quay trở lại lối vào và sẽ đi qua tất cả các đường của mê cung ít nhất 1 lần. Hình 2.3. Thuật toán bám theo tường Robot thực hiện giải thuật bám tường như sau: luôn có một bên ( trái hoặc phải) của robot bám vào tường của mê cung trong suốt quá trình di chuyển. Nếu mê cung có điểm ra nằm ở giữa thì sẽ có trường hợp robot lặp lại lộ trình quanh mê cung liên tục mà không đến được điểm ra. Thuật toán Pledge 2.5. Nếu mê cung có các tường rời nhau, đồng thời lối ra của mê cung nằm trên tường bao của mê cung, thì thuật toán bám tường vẫn có thể tìm được đường ra. Tuy nhiên, nếu điểm vào nằm trong mê cung và tách rời khỏi lối ra, thì bám theo tường sẽ chỉ có thể đi thành một vòng cục bộ và không tìm được lối ra. Giải thuật Pledge được thiết kế để vượt qua vật cản, bằng cách chọn một hướng đi bất kì. Khi gặp vật cản thì chuyển sang di chuyển bám theo tường dọc theo vật cản, kết hợp với đếm góc quay. Sau khi bám tường và quay mà trở về lại đúng hướng đi ban đầu đồng thời tổng tổng góc quay bằng zero thì tức là đã vượt qua khỏi vật cản, thì không cần bám tường nữa và tiếp tục di chuyển theo hướng ban đầu đã chọn. Chỉ thoát khỏi bám tường khi thỏa mãn hai điều kiện: “ hướng hiện tại trùng với hướng ban đầu” và “tổng số góc đã quay bằng 0”. Thuật toán giúp cho robot từ bất cứ điểm nào trong mê cung cũng có thể tìm được lối ra nằm rìa ngoài mê cung. 27 Hình 2.4. Thuật toán Pledge Thuật toán Trémaux 2.6. Thuật toán Trémaux sử dụng phương pháp ghi nhớ đường đi trong mê cung, một đường trong mê cung sẽ được ghi nhớ bằng cách đánh dấu bởi một trong ba trọng thái: chưa qua, đã qua một lần hoặc hai lần. Một ô trong mê cung đã đi qua sẽ được đánh dấu. Tại điểm bắt đầu có thể chọn một hướng bất kì ( nếu có nhiều hơn một hướng ). Khi đến một ngã giao, nếu các đường rẽ đều chưa đi qua, thì chọn ngẫu nhiên một ô để đi và đánh dấu ô ấy đã đi qua một lần. Khi gặp một ngã giao mà đường trước mặt theo hướng đi hiện tại đã có một dấu, và đường đang đi hiện tại mới chỉ đánh dấu một lần, thì quay trở lại và đánh dấu đường ấy lần hai. Nếu đến một ngã giao mà không rơi và hai trường hợp trên thì chọn đường đi có số lần ít đánh dấu nhất, và nhớ đánh dấu đường ấy luôn. Khi đến đích thì những con đường chỉ đánh dấu một lần là đường dẫn trở về điểm xuất phát. Nếu không có điểm đích robot sẽ di chuyển về điểm ban đầu và đường đi sẽ là các ô được đánh dấu hai lần. Giải thuật này có ưu điểm ở bước chọn ngã rẽ cho robot, bước này không còn ngẫu nhiên mà được quyết định từ các hướng đi cũ và các ô lân cận. Theo các thuật toán ở trên và yêu cầu về mê cung cũng như thiết kế robot, ta sẽ chọn lựa giải thuật chọn đường, bám tường và Trémaux để tiến hành mô phỏng ở phần sau. 28 Hình 2.5. Thuật toán Tremaux Sau khi có được thông tin về mê cung, các tường đã được xác định, ta sẽ dùng giải thuật khác để tìm đường đi ngắn nhất cho robot từ một điểm bất kì đến điểm đích. Có hai thuật toán cơ bản giúp tìm đường đi ngắn nhất. Thuật toán lấp kín đƣờng cụt 2.7. Lấp kín đường cụt (dead – end filling) là một thuật toán để giải mê cung bằng cách lấp kín tất cả các ngã cụt, chỉ để lại một đường chính xác không bị lấp. Nó có thể được sử dụng để giải các mê cung trên giấy hoặc với một phần mềm máy tính, nhưng nó không giải quyết được những mê cung chưa biết bởi vì phương pháp này phải biết trước toàn bộ mê cung. Giải thuật được thực hiện lặp đi lặp lại theo quy trình như sau:  Bước 1: xét các ô là đường cụt (các ô có 3 mặt là tường, trừ ô đích) 29 Hình 2.6. Bước 1 giải thuật lấp đường cụt  Bước 2: lấp đường đi từ các ô này đến ngã rẽ gần nhất Hình 2.7. Bước 2 giải thuật lấp đường cụt  Bước 3: lặp lại bước 1 đến khi không còn đường cụt, sẽ thu được 1 số đường đi đến đích. Thuật toán tìm đƣờng đi ngắn nhất (floodfill) 2.8. Giải thuật floodfill thực tế thường được dùng để tìm đường đi từ ngoài vào trung tâm mê cung khi chưa biết thông tin về mê cung. Tuy nhiên tác giả sẽ ứng dụng logic của giải thuật này để tìm đường đi ngắn nhất từ vị trí vào đến vị