TỔNG QUAN
Lý do chọn đề tài
Luận văn này có nội dung về nghiên cứu và thử nghiệm thuật toán tìm đường bao phủ CCD* trong môi trường không biết trước
Lý do lựa chọn đề tài này có thể bao gồm những lý do sau:
Về mặt yêu cầu, mục đích ứng dụng:
Với sự phát triển của công nghệ, việc sử dụng robot để hỗ trợ con người trong cuộc sống ngày càng trở nên phổ biến Nhiều người thường dành thời gian cho việc quét dọn nhà cửa, một công việc lặp đi lặp lại và nhàm chán, đặc biệt là đối với những người bận rộn không có đủ thời gian Do đó, việc ứng dụng robot trong dọn dẹp thực tế sẽ giúp con người tiết kiệm thời gian và giảm bớt gánh nặng trong công việc này.
Bài toán bao phủ có nhiều ứng dụng thực tiễn quan trọng và ngày càng được giải quyết hiệu quả hơn nhờ vào việc sử dụng robot Sự phát triển này không chỉ nâng cao khả năng xử lý bài toán mà còn mở ra nhiều cơ hội mới trong các lĩnh vực khác nhau.
Robot đang ngày càng được ứng dụng rộng rãi trong nhiều lĩnh vực, chẳng hạn như làm sạch sàn nhà, cắt cỏ, khai thác và thu hoạch nông sản, sơn, cũng như xử lý các chất thải nguy hiểm.
Về mặt công nghệ tác giả muốn:
- Tìm hiểu và sử dụng ros, gazebo và tìm hiểu về lập trình nhúng
- Tìm hiểu về các thuật toán tìm đường
- Thực hành lập trình cho robot
Thực hiện đề tài không chỉ giúp tác giả rèn luyện tư duy logic mà còn nâng cao kỹ năng quản lý dự án và lập trình, từ đó tích lũy kinh nghiệm quý báu cho các dự án thực tế trong tương lai.
Giới thiệu một số khái niệm liên quan
1.2.1 Robot dịch vụ là gì?
Robot dịch vụ là loại robot hỗ trợ con người trong các công việc lặp đi lặp lại, công việc trong nhà, hoặc những nhiệm vụ ở môi trường bẩn và nguy hiểm Những robot này thường được điều khiển tự động bởi hệ thống điều khiển tích hợp Theo Liên đoàn Robot Quốc Tế (IFR), robot dịch vụ được định nghĩa là robot hoạt động bán tự động hoặc hoàn toàn tự động, thực hiện các dịch vụ hữu ích cho con người và thiết bị, không bao gồm các hoạt động sản xuất.
1.2.2 Các ứng dụng của robot dịch vụ Ứng dụng có thể có của robot chủ yếu là để hỗ trợ trong công việc của con người Hiện nay có các ứng dụng trong một số lĩnh vực như sau:
Robot dịch vụ công nghiệp được ứng dụng để thực hiện nhiều nhiệm vụ, từ những công việc đơn giản như kiểm tra hàn đến các nhiệm vụ phức tạp trong môi trường khắc nghiệt, như tháo dỡ nhà máy điện hạt nhân Chúng cũng có khả năng thực hiện các hành động lặp đi lặp lại, như lắp ráp và tự động hóa các quy trình sản xuất Những robot này thường được gọi là "Robot công nghiệp".
Robot dịch vụ đang ngày càng được áp dụng rộng rãi trong các nhà hàng, quán bar và khách sạn Chúng có khả năng thực hiện nhiều công việc như dọn dẹp, pha chế đồ uống phức tạp và tiếp đón khách hàng, giúp nâng cao hiệu quả phục vụ và trải nghiệm của khách.
Robot gia đình ngày càng trở nên phổ biến, thực hiện các nhiệm vụ thường ngày mà con người thường làm như lau chùi sàn nhà và cắt cỏ Những thiết bị này không chỉ giúp tiết kiệm thời gian mà còn nâng cao hiệu quả trong công việc nhà, mang lại sự tiện lợi cho cuộc sống hàng ngày.
11 dọn dẹp hồ bơi Chúng cũng có thể đóng vai trò củamột người quản gia trong gia đình
Hệ thống robot trong khoa học đóng vai trò quan trọng khi thực hiện các thao tác lặp đi lặp lại trong nghiên cứu Những robot tự động này có khả năng thực hiện các nhiệm vụ khoa học mà con người gặp khó khăn hoặc không thể thực hiện, chẳng hạn như khám phá các vùng biển sâu và không gian bên ngoài Trái Đất.
Hình 1: Một ứng dụng thực tế của robot dịch vụ
1.2.3 Tìm đường bao phủ là gì?
Tìm đường bao phủ (Coverage Path Planning - CPP) là quá trình xác định lộ trình tối ưu để robot có thể đi qua tất cả các điểm cần thiết trong một khu vực nhất định, đồng thời tránh các vật cản Nhiệm vụ này rất quan trọng trong nhiều ứng dụng robot, bao gồm robot hút bụi, lau nhà, sơn tường, vẽ tranh, robot dò mìn, máy cắt cỏ và máy làm sạch cửa sổ Các yêu cầu đặt ra cho robot khi thực hiện nhiệm vụ này rất đa dạng và cần được xem xét kỹ lưỡng.
- Robot phải đi qua tất cả các điểm và bao phủ vùng mục tiêu cần quét một cách hoàn thiện
- Robot phải thực hiện di chuyển mà không được đè các vùng quét lên nhau
- Các tác vụ thực hiện liên tục và tuần tự mà đường đi không bị lặp lại
- Robot phải tránh được các vật cản
- Sử dụng quỹ đạo di chuyển đơn giản (đi thẳng hoặc vòng tròn )
- Bổ sung các đường dẫn tùy chọn khi có thể
Trong môi trường phức tạp, việc đáp ứng tất cả các điều kiện cần thiết không phải lúc nào cũng khả thi, do đó cần sắp xếp các mức ưu tiên khác nhau để phù hợp với từng điều kiện Giải quyết bài toán tìm đường trong những trường hợp tổng quát và thực tiễn là một thách thức lớn Một số ví dụ điển hình như bài toán “Người bán hàng” (Covering/Travelling Salesman problem), bài toán “Phòng trưng bày” (Art Gallery problem) và bài toán “Người đi tuần tra” (Watchman Route problem) đều liên quan đến việc tìm đường và được phân loại là các bài toán NP-khó.
Thuật toán bao phủ được chia thành hai loại chính: bao phủ tối ưu và bao phủ đầy đủ Thuật toán được coi là bao phủ đầy đủ khi có khả năng chứng minh rằng nó có thể bao phủ toàn bộ vùng làm việc một cách chặt chẽ Ngược lại, thuật toán bao phủ tối ưu được áp dụng trong các trường hợp mà robot phải đối mặt với các ràng buộc như thời gian hoạt động, nguồn năng lượng và kích thước, nhằm tối đa hóa diện tích bao phủ mà không thể đảm bảo bao phủ toàn bộ vùng làm việc.
Các thuật toán bao phủ được chia thành hai loại chính: online và offline Thuật toán offline yêu cầu thông tin tĩnh và môi trường cần bao phủ phải được biết trước khi robot hoạt động Ngược lại, thuật toán online không cần thông tin trước, cho phép robot tự xác định môi trường theo thời gian thực nhờ vào các cảm biến gắn trên nó Điều này giúp robot hoạt động linh hoạt trong những môi trường chưa được biết đến Các thuật toán online sử dụng cảm biến để đánh giá và di chuyển đến mục tiêu, do đó, chúng còn được gọi là giải thuật bao phủ dựa trên cảm biến.
Nội dung đề tài
Luận văn này trình bày chi tiết những vấn đề như sau:
- Tìm hiểu tổng quan về các phương pháp giải quyết bài toán bao phủ:
Có ba phương pháp chính để giải quyết bài toán bao phủ: đầu tiên là phương pháp phân chia vùng làm việc cổ điển, tiếp theo là phương pháp dựa trên lưới ô vuông, và cuối cùng là phương pháp sử dụng nhóm robot Ngoài ra, có thể kết hợp hai hoặc nhiều phương pháp trên để đạt hiệu quả tối ưu trong việc giải quyết bài toán này.
- Tìm hiểu và nghiên cứu thuật toán tìm đường bao phủ CCD*
Thuật toán CCD* là một phương pháp tiếp cận dựa trên lưới ô vuông, nhằm mục tiêu chính là giải quyết bài toán bao phủ thông qua việc cải tiến thuật toán này.
- Tiến hành cài đặt thử nghiệm thuật toán trên môi trường mô phỏng Gazebo và trên môi trường thật với robot Kobuki
Tác giả đã sử dụng ngôn ngữ lập trình C++ và IDE Eclipse, kết hợp với phiên bản ROS Indigo trên hệ điều hành Ubuntu 14.04, để lập trình thuật toán chia ô cho robot Sau đó, họ tiến hành thử nghiệm trong môi trường mô phỏng Gazebo cũng như trong thực tế.
Kết quả đã thực hiện được
Cho tới thời điểm hiện tại, tác giả đã thực hiện được những công việc như sau:
- Tìm hiều về các công cụ hỗ trợ như Gazebo, ROS…
- Tìm hiểu về các phương pháp giải quyết bài toán bao phủ, hiểu về một số thuật toán bao phủ tiêu biểu
Trong quá trình thử nghiệm lập trình thuật toán, robot đã được kiểm tra và thu được kết quả khả quan Cụ thể, robot hoạt động bình thường trong môi trường gazebo và có khả năng xử lý tình huống khi chạy vào đường cụt, cho phép nó quay lại một cách linh hoạt Ngoài ra, robot cũng thực hiện đúng thuật toán khi hoạt động trong môi trường thực tế.
PHƯƠNG PHÁP GIẢI QUYẾT BÀI TOÁN BAO PHỦ
Các phương pháp giải quyết bài toán bao phủ
Thuật toán bao phủ đơn giản nhất cho robot là điều khiển chúng di chuyển ngẫu nhiên trong vùng làm việc, đảm bảo rằng nếu hoạt động đủ lâu, toàn bộ khu vực sẽ được bao phủ Phương pháp này được áp dụng trong nhiều robot hút bụi, như Trilobite của Electrolux và Roomba của iRobot, nhờ vào sự đơn giản và không yêu cầu tính toán phức tạp hay cảm biến đắt tiền Tuy nhiên, hiệu quả của phương pháp này giảm sút khi vùng làm việc lớn và có nhiều vật cản phức tạp, dẫn đến chi phí hoạt động tăng cao.
16 của robot tính theo thời gian và năng lượng tiêu thụ trở nên rất lớn, không thể chấp nhận được trong thực tế
Trên toàn cầu, nhiều nghiên cứu đã được thực hiện để giải quyết hiệu quả bài toán tìm đường đi bao phủ, và các nghiên cứu này có thể được phân loại thành bốn hướng chính.
2.1.1 Phương pháp phân chia vùng làm việc cổ điển Đây là nhóm phương pháp cổ điển nhất, có thể coi là điểm khởi đầu để xây dựng các nhóm phương pháp mới hơn về sau Ý tưởng cơ bản là phân chia toàn bộ vùng làm việc của robot thành các cell đơn giản, không chồng lấn, và không chứa vật cản Tổng diện tích các cell này bằng diện tích mà robot phải bao phủ Vì các cell không chứa vật cản, nên robot có thể dễ dàng bao phủ từng cell bằng các thao tác đơn giản như quét kiểu díc-dắc hoặc quét theo vòng tròn Do đó, bài toán tìm đường đi bao phủ trở thành bài toán phân chia vùng làm việc của robot thành các cell Hình dưới mô tả ví dụ một vòng quét díc-dắc để bao phủ một cell hình chữ nhật [1]
Hình 2: Bao phủ một cell hình chữ nhật bằng thao tác di chuyển díc-dắc a Giải thuật phân chia theo hình thang
Thuật toán phân chia theo hình thang là phương pháp đơn giản nhất trong việc chia vùng làm việc đa giác thành các cell hình thang Hình thức này tạo ra một đồ thị kề thể hiện mối quan hệ không gian giữa các cell, từ đó đảm bảo bao phủ hoàn toàn vùng làm việc.
Robot cần tìm một lộ trình đi qua tất cả các ô trên đồ thị kề, thực hiện di chuyển theo đường dích-dắc tại mỗi ô và theo đúng thứ tự đã xác định Thuật toán hình thang được áp dụng hiệu quả cho các khu vực làm việc đơn giản dạng đa giác Đây là một thuật toán offline, yêu cầu robot phải nắm rõ thông tin về môi trường làm việc trước khi tiến hành tìm đường.
Hình 3: Ví dụ về thuật toán phân chia hình thang
Thuật toán phân chia boustrophedon, phát triển theo phương pháp cổ điển, được ứng dụng rộng rãi trong lĩnh vực robot quét Từ gốc Hy Lạp, "boustrophedon" có nghĩa là “đường đi của con bò”, mô tả cách bò kéo cày theo các đường dích-dắc trên ruộng Thuật toán này tương tự như thuật toán phân chia hình thang nhưng cho phép nối các ô kề nhau, giúp robot quét hiệu quả hơn Nhờ đó, số lượng ô trên đồ thị kề giảm đi, làm giảm tổng quãng đường mà robot cần di chuyển để bao phủ toàn bộ khu vực làm việc Ví dụ minh họa cho thuật toán này có thể thấy rõ trong hình 4, nơi các ô C3, C5, C7 ở hình 3 đã được kết hợp thành một ô duy nhất.
Hình 4: Ví dụ về thuật toán phân chia boustrophedon b Giải thuật phân chia boustrophedon
Gần đây, một số thuật toán bao phủ online đã được phát triển dựa trên phương pháp của thuật toán phân chia Boustrophedon, nổi bật là thuật toán BA* Thuật toán này chia vùng làm việc của robot thành các vùng boustrophedon có hình dạng phức tạp, cho phép robot quét một lần Trong quá trình hoạt động, thuật toán BA* tìm kiếm các vùng boustrophedon và sử dụng cơ chế quay lui để đảm bảo tất cả các vùng đều được phát hiện và không gian làm việc được bao phủ hoàn toàn Hình 5 minh họa ví dụ về việc phân chia các vùng boustrophedon theo thuật toán BA*, với bốn vùng được đánh số từ 1 đến 4 cùng quỹ đạo di chuyển của robot.
Hình 5: Ví dụ về thuật toán BA*
2.1.2 Phương pháp bao phủ dựa trên lưới ô vuông (grid-based methods)
Phương pháp tìm đường đi bao phủ dựa trên lưới (grid-based) là một trong những cách tiếp cận hiệu quả nhất trong việc giải quyết bài toán này Nó sử dụng bản đồ dạng lưới ô vuông để biểu diễn môi trường làm việc của robot, trong đó mỗi ô được gán giá trị cho biết liệu đó là chướng ngại vật hay không Toàn bộ lưới giúp xác định hình dạng không gian hoạt động và vị trí các vật cản Kích thước ô vuông thường tương đương với kích thước robot, vì vậy phương pháp này thường được áp dụng trong môi trường trong nhà nhằm giảm số lượng ô trong lưới.
Hình 6: Ví dụ về grid map với hai chướng ngại vật a Thuật toán STC
Thuật toán cây bao trùm
Thuật toán này sử dụng phương pháp lưới ô vuông, chia vùng làm việc thành các ô vuông kích thước 2Dx2D, với D là kích thước của robot Mỗi ô chứa bốn ô nhỏ hơn (subcell) có kích thước bằng robot và bỏ qua những ô bị chiếm bởi vật cản Các ô trống tạo thành một cấu trúc đồ thị, trong đó các nút là tâm điểm của từng ô và các cạnh là đoạn thẳng nối các tâm điểm của các ô liền kề.
Hình 7: Phân chia cell trong thuật toán cây bao trùm
Phương pháp này chuyển đổi bài toán tìm đường đi bao phủ thành bài toán tối ưu, nhằm duyệt qua tất cả các ô không có vật cản trên lưới, mỗi ô một lần Để giải quyết vấn đề này, một lớp thuật toán dựa trên cây bao trùm đã được phát triển, trong đó nổi bật là thuật toán Spiral-STC (Spiral Spanning Tree Coverage).
Thuật toán Spiral-STC là một phương pháp tìm đường on-line cho robot, trong đó đường đi được tạo ra theo hình xoắn ốc Robot bắt đầu từ vị trí xuất phát và di chuyển qua các ô trống lân cận theo chiều ngược kim đồng hồ Quá trình này tiếp tục cho đến khi không còn ô trống, sau đó robot sẽ quay lại theo chiều ngược lại Với kích thước ô là 2Dx2D, robot đảm bảo không đi qua một subcell nào hai lần và sẽ trở về vị trí ban đầu sau khi đã phủ toàn bộ diện tích làm việc Hình 8 minh họa ví dụ về đường đi của robot khi áp dụng thuật toán Spiral-STC.
Hình 8: Đường bao phủ của robot khi áp dụng thuật toán Spiral – STC
Giải thuật Spiral-STC xây dựng một cây bao trùm cho đồ thị và sử dụng cây này để tạo ra đường dẫn bao phủ Trong quá trình này, robot chia nhỏ mỗi cell thành bốn subcell có kích thước D, tương đồng với kích thước và hình dạng của dụng cụ quét Dụng cụ quét di chuyển theo đường dẫn của các subcell, lần lượt bao phủ toàn bộ tập hợp các cell trống Một cell được coi là "mới" khi tất cả bốn subcell của nó chưa được bao phủ, trong khi nếu chỉ cần một subcell đã được bao phủ, cell đó sẽ được xem là "cũ".
Phương pháp này chuyển đổi bài toán tìm đường đi bao phủ thành bài toán tối ưu, nhằm duyệt qua tất cả các ô không có vật cản trên lưới, mỗi ô chỉ một lần.
Thuật toán tràn sóng wavefront là một phương pháp offline sử dụng lưới đại diện cho môi trường, có kích thước gấp hai lần kích thước robot, nhằm lập kế hoạch bao phủ hoàn chỉnh Thuật toán yêu cầu ô bắt đầu và ô mục tiêu, và thực hiện quá trình lan truyền sóng từ ô mục tiêu đến ô bắt đầu để gán nhãn cho từng phần tử trong lưới Quá trình này bắt đầu bằng việc gán nhãn số 0 cho ô mục tiêu, sau đó là số 1 cho các ô xung quanh, và tiếp tục lặp lại cho đến khi tất cả các ô đều được gán nhãn Khi quá trình transform hoàn tất, kế hoạch bao phủ được xác định bằng cách bắt đầu từ ô bắt đầu và chọn các ô lân cận có nhãn cao nhất chưa được thăm, với trường hợp nhiều ô cùng nhãn thì một ô sẽ được chọn ngẫu nhiên.
Hình 9: Gán các ô bằng cách lan truyền bước sóng với ô bắt đầu (S) và ô đích (G)
Hình 10: Kế hoạch bao phủ sử dụng biến đổi khoảng cách với thuật toán wavefront
2.1.3 Phương pháp sử dụng nhiều robot
Giải thuật này được thiết kế để tối ưu hóa việc bao phủ đường đi của một nhóm robot trong môi trường chưa xác định, nhằm giảm thời gian làm việc bằng cách hạn chế sự lặp lại các vùng di chuyển Tác giả cho rằng hiệu quả làm việc chỉ đạt tối đa khi số lượng vùng lặp lại là ít nhất Giải thuật sử dụng phương pháp phân chia cell hai chiều tương tự như trong giải thuật bao phủ đường cày với robot đơn, nhưng mở rộng để đảm bảo các robot khám phá hết các vùng riêng lẻ và phân bố hợp lý giữa các vùng Giải pháp chủ yếu là tính toán để hạn chế sự giao thoa di chuyển giữa các robot, với các robot di chuyển chủ yếu theo đường thẳng Để quét toàn bộ khu vực làm việc, robot được chia thành hai nhóm: nhóm explorer (robot thăm dò) đi dọc ranh giới vùng mục tiêu, trong khi nhóm coverer (robot bao phủ) thực hiện nhiệm vụ bao phủ.
LÝ THUYẾT VÀ CẢI TIẾN THUẬT TOÁN CCD*
Lý thuyết về thuật toán CCD*
CCD* là thuật toán kết hợp giữa thuật toán D* và thuật toán PT Thuật toán D* là phiên bản động của A*, chuyên tìm kiếm với điểm đầu và điểm cuối, nhưng CCD* chỉ áp dụng một phần ý tưởng của D* Trong khi đó, thuật toán PT cung cấp cách xác định đường đi dựa trên trọng số của các ô.
3.2.1 Bản đồ chiếm dụng và sự biểu diễn robot
Bản đồ chiếm dụng được hình thành từ việc phân chia các ô có kích thước 𝑒 𝑐𝑒𝑙𝑙, đại diện cho tập phần tử 𝑀 = {1, … , 𝑀} trong hệ tọa độ Đề Các, với tâm là ô trung tâm 𝑐 𝑖 ∈ 𝑅 2 Mỗi ô chứa thông tin về mức độ chiếm dụng của phần môi trường mà nó bao phủ Để đại diện cho tất cả các chướng ngại vật trong môi trường, một hàm chiếm dụng có trọng số 𝜊 𝑖 ∈ 1,2, … , 𝑀 𝑐 + 1,∞ được sử dụng, với tập chướng ngại vật ký hiệu là 𝑂 = 𝑖 ∈ 𝑀 ∨ 𝑜 𝑖 = ∞ và tập các ô chưa bị chiếm dụng ký hiệu là N = M\O Hàm chiếm dụng được định nghĩa rõ ràng để thể hiện mức độ chiếm dụng trong không gian.
Hàm số mô tả quy trình tạo ra mặt nạ chi phí an toàn xung quanh các chướng ngại vật bằng cách giảm dần giá trị chiếm dụng từ vị trí chướng ngại vật đến khu vực trống Kích thước của mặt nạ chi phí an toàn được xác định bởi số nguyên cố định của các ô 𝑀 𝑐 Ví dụ, mặt nạ chi phí an toàn của bản đồ lưới chiếm dụng có trọng số với 𝑀 𝑐 = 4 ô được minh họa trong hình bên dưới.
Mặt nạ chi phí an toàn của bản đồ lưới chiếm dụng có trọng số 𝑴 𝒄 = 𝟒 được thiết lập với giả định rằng công cụ lau dọn gắn trên robot có hình vuông kích thước bằng kích thước của số nguyên các ô và lớn hơn robot Điều này cho phép robot được đại diện bằng một mặt nạ hình vuông trên bản đồ, bao quát chu vi của nó Để robot có thể đứng ở bất kỳ ô nào chưa bị chiếm dụng, tất cả các vật cản cần được mở rộng cho số nguyên của ô 𝑀 𝑅.
Robot được biểu diễn bởi một mặt nạ hình vuông có kích thước 2 ∙ 𝑀 𝑅 + 1 ô, với vị trí của robot đặt tại ô R và các vật cản được thể hiện bằng ô màu đen Đồ thị có trọng số không liên kết 𝐺 𝑁, 𝐸, 𝑊 được hình thành từ bản đồ chiếm dụng, trong đó các ô chưa bị chiếm dụng 𝑁 đại diện cho tập các nút trong đồ thị Hai nút 𝑖 và 𝑗 được coi là hàng xóm nếu khoảng cách giữa chúng thỏa mãn điều kiện 𝑐 𝑖 − 𝑐 𝑗 ∞ = 𝑒 𝑐𝑒𝑙𝑙 Tập các cạnh trong đồ thị được định nghĩa là 𝐸 = 𝑖, 𝑗, với 𝑖 và 𝑗 là các nút kề nhau trong tập 𝑁.
Tập các trọng số 𝑊 = 𝑤 𝑖,𝑗 𝜖𝑁, 𝑖 𝑣à 𝑗 𝑙à à𝑛𝑔 𝑥ó𝑚 được định nghĩa là chi phí di chuyển giữa hai hàng xóm, giá trị được xác định như sau:
Một đường trong đồ thị 𝐺 𝑁, 𝐸, 𝑊 được định nghĩa là một chuỗi các nút Ví dụ đường 𝑃 có độ dài 𝐿 được định nghĩa như sau:
𝑃 = 𝑛 1, 𝑛 2,…., 𝑛 𝐿 nếu 𝑛 𝑖 , 𝑛 𝑖+1 𝜖𝐸, 𝑖 = 1,2, … , 𝐿 − 1 (3) Chi phí của đường 𝑃là tổng các trọng số của các cạnh nằm trên đường đi đó:
Chi phí tối ưu của đường đi từ điểm S đến G được ký hiệu là g(S, G), trong đó G đại diện cho chi phí tối thiểu trong các đường có thể đi từ S đến G Nếu không tồn tại đường đi từ S đến G, thì g(S, G) sẽ bằng vô cùng (∞) Để đơn giản, hàm này có thể được ký hiệu là g(n) ≡ g(n, G).
Trong khoa học máy tính, A* là một giải thuật tìm kiếm trong đồ thị, được sử dụng để tìm đường đi từ nút khởi đầu đến nút đích Giải thuật này áp dụng hàm "đánh giá heuristic" để phân loại các nút dựa trên ước lượng tuyến đường tốt nhất Nhờ đó, A* duyệt các nút theo thứ tự đánh giá heuristic, trở thành một ví dụ điển hình của tìm kiếm theo lựa chọn tốt nhất (best-first search).
Giải thuật A* được giới thiệu lần đầu vào năm 1968 bởi các nhà nghiên cứu Peter Hart, Nils Nilsson và Bertram Raphael Trong nghiên cứu của họ, thuật toán này ban đầu được gọi là A; khi kết hợp với một hàm đánh giá heuristic phù hợp, A* cho phép đạt được hiệu suất tối ưu, từ đó lý giải cho tên gọi A*.
Năm 1964, Nils Nilsson đã phát minh ra phương pháp tiếp cận dựa trên khám phá nhằm tăng tốc độ cho giải thuật Dijkstra, được gọi là A1.
Năm 1967, Bertram Raphael đã cải tiến đáng kể thuật toán A2 nhưng chưa thể chứng minh tính tối ưu của nó Đến năm 1968, Peter E Hart đã giới thiệu một chứng minh cho thấy A2 là tối ưu khi áp dụng một đánh giá heuristic phù hợp, từ đó giúp đạt được hiệu suất tối ưu Chứng minh của Hart cũng chỉ ra rằng các thuật toán A2 mới là những giải pháp hiệu quả hơn.
29 nhất có thể được đưa ra các điều kiện Do đó ông đặt tên cho giải thuật mới là A* (A sao, A-star)
Bài toán tìm đường thường được giải bằng thuật toán A*, thuật toán này xây dựng dần các tuyến đường từ điểm xuất phát cho đến khi tìm thấy đường đi đến đích A* chỉ phát triển những tuyến đường có khả năng dẫn đến mục tiêu, nhờ vào việc sử dụng thông tin để xác định các tuyến đường tiềm năng.
Đánh giá heuristic trong thuật toán A* giúp xác định khoảng cách từ một điểm bất kỳ đến đích, thường sử dụng khoảng cách đường chim bay như một ước lượng cho khoảng cách giao thông Khác với các thuật toán tìm kiếm theo lựa chọn tốt nhất, A* còn tính đến khoảng cách đã đi qua, đảm bảo rằng nó luôn tìm ra đường đi ngắn nhất nếu có Tuy nhiên, A* không nhất thiết chạy nhanh hơn các thuật toán tìm kiếm đơn giản hơn, đặc biệt trong môi trường phức tạp như mê cung, nơi có thể cần phải di chuyển xa khỏi đích trước khi quay lại Việc ưu tiên thử các nút gần đích hơn có thể dẫn đến tốn thời gian trong những trường hợp này.
Hình 13 : Mô phỏng đồ thị giải thuật A*
Đỉnh A có giá trị h(A) = 60, đỉnh B h(B) = 53, đỉnh C h(C) = 36, đỉnh D h(D) = 35, đỉnh E h(E) = 35, đỉnh F h(F) = 19, đỉnh G h(G) = 16, đỉnh H h(H) = 38, đỉnh I h(I) = 23, đỉnh J h(J) = 0, và đỉnh K h(K) = 7 Đỉnh bắt đầu là A và đỉnh kết thúc là K Để ước lượng khoảng cách từ đỉnh hiện tại đến đỉnh kết thúc, ta sử dụng công thức f(x) = g(x) + h(x), trong đó g là khoảng cách ngắn nhất từ đỉnh hiện tại đến đích Ví dụ, f(A) = 0 + 60.
Bước P Các đỉnh nối với P Open Close
Hình 14 : Cây tìm kiếm tương ứng với đồ thị trên
Năm 1994, Stentz đã giới thiệu một thuật toán tìm kiếm trên đồ thị nổi bật, có khả năng tái lập kế hoạch nhanh chóng khi môi trường thay đổi Thuật toán này được biết đến như phiên bản động của thuật toán A*, nhưng không sử dụng hàm phỏng đoán.
Thuật toán D* tính toán chi phí 𝑔 𝑛 cho đường đi tối ưu từ nút đã được duyệt n đến điểm đích G, đồng thời xác định giá trị của hàm khóa k(n) trong quá trình lập kế hoạch Hàm k(n) này lưu trữ thông tin về giá trị g(n) cũ trước khi có sự thay đổi trọng số trong đồ thị.
Thuật toán CCD*
3.3.1 Kế hoạch ban đầu của đường bao phủ hoàn toàn
Thuật toán D * bắt đầu bằng việc thực hiện tìm kiếm toàn bộ đồ thị G (N, E, W) từ nút khởi đầu S Đối với mỗi nút n trong đồ thị, D * tính toán chi phí g(n) từ nút bắt đầu, cùng với k(n) và backpointer b(n) để hỗ trợ việc lập lại đường đi Để ngăn chặn việc truy cập các nút đã được ghé thăm, thuật toán sử dụng hàm nhị phân visited(n) = {0, 1}.
Để tránh chồng chéo trong quá trình tìm đường, các hàm chồng chéo nhị phân được sử dụng và giá trị của nó được lưu trữ cho mỗi nút Tất cả các nút ban đầu được thiết lập để không bị ghé qua và không chồng chéo, với nút C hiện tại bắt đầu từ nút S Đường đi bao phủ hoàn toàn được tạo ra bằng cách theo dõi sự gia tăng của giá trị g quanh nút C, bắt đầu từ nút S Các nút không bị ghé qua và không chồng chéo có thể truy cập được và giữ khoảng cách từ nút C hiện tại cho kích thước robot Nút tiếp theo trên đường bao phủ hoàn toàn là nút có giá trị g nhỏ nhất trong số các nút xung quanh Kết nối giữa hai nút trên đường bao phủ được lưu trữ như con đường phụ trợ Paux Các nút xa khỏi Paux được thiết lập để ghé qua, và nếu không có nút ứng viên nào tồn tại xung quanh, tìm kiếm D* sẽ được thực hiện từ nút C hiện tại Tìm kiếm này sẽ dừng lại nếu không tìm thấy nút đầu tiên hoặc nếu các nút được tìm thấy gần vật cản không tồn tại Cuối cùng, con đường ngắn nhất từ C đến M được tính toán và nút M sẽ trở thành nút C hiện tại cho các thuật toán lặp kế tiếp.
Hình 17: Bước đi ban đầu của thuật toán CCD*
Tại bước đi ban đầu S, nó thực hiện tìm kiếm CCD* với g(n) là bé nhất với công thức tính g(n) là : g(n) = min (||C s -Ci|| * Max(O j , O j ))
Thuật toán 1: Tiến hành bao phủ
11: D*'(C) and stop at visited(M) = 0 or ||c M - c o || = e cell , o O and ∃n, visited(n) = 0, ||c M - c n || < M R e cell
12: If no such node M exists
17: C M // Set the new current node
Bước 1:Gán nút hiện tại là S
Bước 2: Đưa nút hiện tại vào trong 𝑃 𝑎𝑢𝑥
Bước 3: Xét với mọi nút thuộc 𝑃 𝑎𝑢𝑥 , nút m thuộc tập N, khoảng cách giữa m và n nhỏ hơn bán kính robot thì giá trị hàm visited(m)=1
Bước 4:Xét với mọi nút thuộc 𝑃 𝑎𝑢𝑥 , nút m thuộc tập N, khoảng cách giữa m và n nhỏ hơn 2 lần bán kính robot thì giá trị hàm overlapped(m) = 1
Bước 5:Đưa các nút mà khoảng cách từ nút đó tới nút hiện tại đang xét bằng 2R+1, chưa được duyệt, không bị overlap vào tập 𝑁 𝑐
Bước 6: Nếu 𝑁 𝑐 khác rỗng, tìm điểm M thuộc tập 𝑁 𝑐 có chi phí nhỏ nhất
Bước 7: Ngược lại, nếu 𝑁 𝑐 rỗng thì sẽ tiến hành chạy lại thuật toán D* và gọi là D*’
Bước 8: Nếu sau khi chạy lại D*’ mà không tìm được điểm M thì thuật toán kết thúc, trả lại đường đi bao phủ 𝑃
Bước 10: Gán nút hiện tại là M
Bước 11: Đường đi bao phủ 𝑃 sẽ là hợp của 𝑃 và 𝑃 𝑎𝑢𝑥
S là nút bắt đầu (start), C là nút hiện tại đang xét (current node)
𝑃 𝑎𝑢𝑥 : đường đi giữa 2 nút sẽ được lưu tạm thời vào đây
𝑃: là đường đi bao phủ toàn bộ bản đồ mà ta cần tìm
N: là tập các nút, ký hiệu mỗi nút là n,m
c : là tọa độ của nút trên bản đồ được viết tắt, thực chất c gồm 2 giá trị (x,y)
𝑐 𝑛 − 𝑐 𝑚 : đây là khoảng cách giữa 2 nút n và m
𝑀 𝑅 : là bán kính robot, 𝑒 𝑐𝑒𝑙𝑙 là kích thước của ô
visited(m): hàm kiểm tra xem nút m đã đi qua chưa
overlapped(m): kiểm tra nút m có bị duyệt ít nhất 1 lần không
𝑁 𝑐 : là tập hợp những nút mà robot có thể đi đến từ vị trí hiện tại C
D*’ : lần chạy thứ hai của thuật toán D*, ký hiệu như này để tránh bị nhầm với lần chạy 1
3.3.2 Lập lại kế hoạch con đường bao phủ hoàn toàn
Khi các nút lân cận của robot di chuyển và thay đổi vùng chiếm hữu, quá trình lập kế hoạch lại con đường sẽ được khởi động để tìm ra lộ trình mới từ vị trí hiện tại của robot Thuật toán CCD* thực hiện việc này bằng cách sử dụng D* để tính toán các giá trị g mới, sau đó áp dụng thuật toán 1 để xác định con đường bao phủ hoàn toàn Việc hoàn tất tính toán con đường bao phủ phụ thuộc vào các giá trị g được tính toán qua tìm kiếm D* và các nút mà robot đã đi qua trong quá trình theo dõi con đường bao phủ trước khi có sự thay đổi trong môi trường.
Trong quá trình tính toán, các hàm visited R (n) và overlapped R (n) được sử dụng để xác định các giá trị của con đường bao phủ hoàn toàn cho các hàm visited(n) và overlapped(n) Thông tin lưu trữ D* giúp tối thiểu hóa số lượng nút được kiểm tra Con đường bao phủ hoàn toàn P được theo dõi bởi các robot đến vị trí cuối cùng và sẽ được tính toán lại khi có sự thay đổi trong môi trường.
Thuật toán 2: Chuyển động của robot – thuật toán CCD*
10: if ||cn - cR|| < MR ecell
12: if ||cn - cR|| < 2MR ecell
Bước 1: Khởi tạo, trong đó g(n) là chi phí của điểm hiện tại so với điểm xuất phát, b(n) là điểm trước đó trên đường đi Biến 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 𝑅 được sử dụng để đánh dấu các điểm đã được thăm, trong khi 𝑜𝑣𝑒𝑟𝑙𝑎𝑝𝑝𝑒𝑑 𝑅 đánh dấu các điểm đã bị trùng lặp khi di chuyển theo đường đang xét.
Bước 2: Gán vị trí xuất phát là R
Bước 3: Nếu R = S hoặc hàm changed-nodes(R) được gọi
Bước 4: Tiến hành tính lại đường đi từ đầu
Bước 5 trong quá trình dò tìm nút R sử dụng hàm path-following Thuật toán đầu tiên cho phép robot tìm ra một lộ trình bao phủ toàn bộ bản đồ Tuy nhiên, nếu môi trường thay đổi, chẳng hạn như vị trí vật cản, thuật toán thứ hai sẽ khởi động lại quá trình tìm đường để điều chỉnh lộ trình Khi coverage xác định được đường đi, nút R sẽ được cập nhật dần dần trong lộ trình đó.
Trình bày và cải tiến thuật toán
Để đơn giản hóa thuật toán, ta thiết lập Mr = 0, tức là kích thước của một ô (cell) bằng kích thước của robot và dụng cụ quét Vì ba kích thước này bằng nhau, thuật toán sẽ chỉ dừng lại khi visited(M) = 0.
39 khảo của các sinh viên nghiên cứu để triển khai thuật toán dễ dàng hơn Sau đây là các trường hợp gặp phải với thuật toán:
3.4.1 Trường hợp robot bao phủ hoàn toàn:
Robot sử dụng thuật toán CCD* đi theo trọng số g(n) min, thực hiện replanning tại ô số 11 khi gặp vật cản tại đường đi theo kế hoạch ban đầu
Hình 18: Thuật toán bao phủ hoàn toàn
3.4.2 Vấn đề gặp phải khi sử dụng thuật toán CCD*:
Khi triển khai thuật toán, có thể gặp phải vấn đề khi thuật toán không bao phủ hoàn toàn trong một số trường hợp Đặc biệt, khi gặp đường cụt, thuật toán sẽ không thể quay lui, dẫn đến những hạn chế trong quá trình thực hiện.
Hình 19: Trường hợp thuật toán không bao phủ hoàn toàn
Thuật toán di chuyển theo thứ tự từ ô Start (8) đến các ô 4, 3, 7, 9, 10, 12 và 11 Khi gặp đường cụt, thuật toán sẽ quay lại và coi ô hiện tại là điểm bắt đầu mới Tại ô 11, robot không thể tiếp tục di chuyển, dẫn đến việc thuật toán kết thúc tại đây Điều này cho thấy rằng thuật toán không hoàn toàn bao phủ tất cả các ô.
Khi sử dụng thuật toán D* và D*' với trọng số tối thiểu mà không thể thoát khỏi đường cụt, chúng tôi đề xuất thêm một lần sử dụng D*'' để giải quyết vấn đề này Thuật toán sẽ không quay lui với trọng số tối thiểu, mà thay vào đó sẽ sử dụng trọng số tối đa để thoát khỏi vòng lặp Hình ảnh dưới đây minh họa đường đi của thuật toán khi áp dụng D*''.
Khi thuật toán lập lại kế hoạch tại vị trí G nhưng vẫn gặp đường cụt, cần thực hiện lệnh tìm kiếm D*'' với g(n) là giá trị lớn nhất cho đến khi thoát khỏi đường cụt và tìm được ô mới Sau đó, thuật toán sẽ quay về tìm kiếm D* với giá trị g(n) nhỏ nhất.
Hình 20: Cải tiến thuật toán để thoát khỏi đường cụt và bao phủ hoàn toàn
Thuật toán 1(đã cải tiến): Tiến hành bao phủ
11: D*’(C) and stop at visited(M) = 0 //D*’ ở đây là xét với mininal g’ 12: If no such node M exists
13: D*’’(C) and stop at visited(M) = 0 //D*’’ ở đây là xét với maximum g’ 14: If no such node M exists
CÀI ĐẶT VÀ THỬ NGHIỆMTHUẬT TOÁN CCD*
Môi trường thực tế
4.2 Robot trong môi trường thực tế
4.2.1 Giới thiệu về robot Kobuki
Hình 24: Robot Kobuki a) Khái niệm
Kobuki, hay còn gọi là iClebo Kobuki, là một thiết bị di động giá rẻ được thiết kế cho giáo dục và nghiên cứu trong lĩnh vực robot Với khả năng hoạt động liên tục, Kobuki không chỉ cung cấp năng lượng cho các máy tính khác mà còn cho các bộ phận cảm biến và vận động Đặc biệt, Kobuki được trang bị dụng cụ đo hành trình cải tiến bằng con quay hồi chuyển đã hiệu chỉnh, giúp di chuyển với độ chính xác cao.
Tốc độ di chuyển tịnh tiến tối đa: 70 cm/s
Tốc độ quay góc tối đa: 180 deg/s (với tốc độ trên 110 deg/s, con quay hồi chuyển sẽ giảm hiệu năng)
Tải trọng: 5 kg (sàn cứng), 4 kg (thảm mềm)
Cảm biến vách: Không chạy ra khỏi vách có độ sâu lớn hơn 5 cm
Thời gian chạy: Từ 3 đến 7 tiếng tuỳ kích thước pin
Thời gian sạc: Từ 1.5 đến 2.6 tiếng tuỳ kích thước pin
Kết nối với máy vi tính qua cổng USB hoặc chân RX/TX
Phát hiện quá tải động cơ: Tự động ngắt nguồn khi dòng lớn hơn 3A
Con quay hồi chuyển: Đã hiệu chỉnh
Bộ giảm chấn: trái, giữa, phải
Cảm biến vách: trái, giữa, phải
Cảm biến bánh xe: trái, phải
Tốc độ dữ liệu cảm biến: 50 Hz
Đường kính: 351.5 mm, chiều cao: 124.8 mm, cân nặng: 2.35 kg (khi lắp pin loại nhỏ 4S1P) d) Đặc tả phần mềm
Bộ điều khiển viết bằng C++ cho Linux và Windows
Phần mềm mô phỏng Gazebo
4.2.2 Giới thiệu về cảm biến laser Hokuyo
Hình 25: Cảm biến laser Hokyuo
Cảm biến Hokuyo là thiết bị dò tầm quét laser, lý tưởng cho việc nhận dạng môi trường Nó được thiết kế đặc biệt cho các robot thông minh thế hệ mới, tích hợp hệ thống tự động và bảo mật thông tin cá nhân.
Độ chính xác và phân giải cao, góc nhìn rộng cung cấp giải pháp tốt nhất cho robot tự động di chuyển trong môi trường không biết trước
Kích thước nhỏ gọn tạo nên nhiều không gian thiết kế thoải mái Nguồn năng lượng tiêu thụ ít, có khả năng hoạt động thời gian dài
Không chịu ảnh hưởng bởi độ sáng môi trường, hiệu quả tốt cả trong bóng tối
Nhận diện kích thước và vị trí vật thể mà không cần thăm dò quá gần c) Ứng dụng
Hỗ trợ robot tự động nhận biết môi trường xung quanh
Phát hiện kẻ xâm nhập
Dùng trong cửa tự động, phân tích hành vi đặc thù của con người
Phát hiện vật cản d) Đặc tả
Nguồn điện: 5 V DC, dòng tiêu thụ: 500 mA hoặc ít hơn (800 mA khi khởi động)
Phạm vi đo lường: Trong tầm 60 đến 4095 mm, góc rộng 240 độ
Độ chính xác: Trong vùng 60 – 1000 mm sai số 10 mm, trong vùng 1000 – 4095 sai số 1%
Độ phân giải góc: Một bước xấp xỉ 0.36 độ (360 độ/1024 bước)
Thời gian quét: 100 ms cho một lần
Cổng kết nối: USB và RS-232C
Khi cài đặt và thử nghiệm giải thuật trong môi trường thực tế, quá trình diễn ra tương tự như trong mô phỏng, nhưng ở tầng thấp nhất, file launch để khởi tạo môi trường trở nên đơn giản hơn Điều này là do chỉ cần thiết lập giao tiếp với robot mà không cần những mô tả khởi tạo phức tạp như trong mô phỏng.
Khi vận hành thực tế trên robot Kobuki, có thể xảy ra một số sai sót, do đó cần điều chỉnh các tham số khác nhau tùy thuộc vào từng loại robot Laser Hokuyo khi quét có thể gặp lỗi, và khi robot di chuyển, laser có thể bị xê dịch, dẫn đến sự không đồng nhất trong việc xác định hướng và tọa độ tương đối Điều này làm cho các phép tính để xác định vị trí vật cản trở nên không chính xác Việc thêm các tham số điều chỉnh về tỷ lệ ngưỡng và độ lớn miền lấy mẫu giúp tăng khả năng chịu lỗi, đảm bảo rằng các sai số phát sinh vẫn nằm trong mức chấp nhận được.
Trong quá trình di chuyển, robot có thể gặp vấn đề khi địa hình không bằng phẳng, dẫn đến việc trượt trong lúc phanh Nếu chạy trên bề mặt có ma sát cao, bộ lập mã trên bánh xe có thể xử lý không chính xác, khiến tọa độ robot ngày càng khác biệt so với tọa độ thực tế Để cải thiện độ chính xác trong di chuyển, các tham số điều chỉnh hướng, tốc độ tịnh tiến, tốc độ góc và độ lệch tọa độ giới hạn cần được áp dụng Một số robot có động cơ bên yếu hơn thường bị lệch hướng, vì vậy các tham số này sẽ được điều chỉnh dần dần để tăng cường tốc độ cho bên động cơ yếu, giúp robot duy trì sự cân bằng tốt hơn.
Robot có khả năng bao phủ toàn bộ bản đồ 3x3 trong thời gian 6 phút, thực hiện 12 lần lập kế hoạch lại Thuật toán hoạt động hiệu quả trong môi trường thực tế và phát huy tối đa ưu điểm khi hoạt động trong một môi trường chưa được biết trước.
Hình 26: Áp dụng giải thuật CCD* cho robot Kobuki
