CHƯƠNG 1: CƠ SỞ LÝ THUYẾT 1.1 Tổng quan về robot di động 1.1 Giới thiệu về robot di động Robot di động tự động là một loại máy móc được điều khiển bởi phần mềm, có thể di chuyển từ nơi này sang nơi khác mà không cần sự hỗ trợ từ con người [3]. Không giống như những robot trong công nghiệp chỉ có thể làm việc trong những môi trường đặc thù, robot di động có thể di chuyển trong vùng được xác định trước để thực hiện các yêu cầu cấn thiết mà ở đó con người không thể đến được.2 Phân loại robot di động Ta có thể chia robot di động thành các nhóm như sau: robot di động dùng bánh (Wheeled Mobile Robots – WMRs) [4], robot di động dùng chân (Legged Mobile Robots – LMRs) [5], máy bay không người lái (Unmanned Aerial Vehicles– UAVs) [6], robot tự động dưới nước (Autonomous Underwater Vehicles – AUVs) [7]. Một số ví dụ ở các nhóm robot được trình bày tại Bảng 1-1. Một số loại robot di động STT Loại robot Đặc điểm, cấu trúc Hình ảnh Robot hai bánh cân 1 bằng WMRs Robot 4 bánh lái vi 2 sai 1 Robot động vật 4 3 chân LMRs 4 Robot nhện 5 UAVs Quadcopter 6 Pluto Plus ROVs AUVs Battlespace 7 Preparation AUVs 2 1.3 Ràng buộc Nonholonomic trong robot di động Một hệ thống hay robot có số cơ cấu chấp hành nhỏ hơn số bậc tự do thì sẽ có ràng buộc Nonholonomic.
Có nghĩa là thay vì di chuyển 6 hướng (6 bậc tự do) thì robot chỉ có thể di chuyển được 3 hướng (đi thẳng, rẽ trái, rẽ phải) và ba hướng còn lại là ràng buộc Nonholonomic. Hoặc giống như Drone, cũng có cơ cấu chấp hành nhỏ hơn số bậc tự do nên cũng sẽ bị ràng buộc trong không gian làm việc của nó. Một ví dụ về ràng buộc Nonholonomic là bánh xe lăn. Giả sử một bánh xe ở trên một địa điểm nhất định (trên mặt đất).
Ban đầu van bánh xe ở một vị trí nhất định trên bánh xe. Nếu bánh xe di chuyển xung quanh và quay về chính xác vị trí ban đầu, thì van nó sẽ không ở vị trí trước đó nữa mà nằm ở vị trí khác. Vị trí mới đó phụ thuộc vào quãng đường đi được. Nếu như bánh xe là holonomic, thì cái van phải luôn nằm ở đúng trên vị trí ban đầu mặc dù bánh xe có lăn đường đi như thế nào đi nữa, vì vậy hệ thống này được gọi là Nonholonomic.
Hoặc đối với máy bay khi đang bay không thể ngay lập tức dừng lại trên không hay chuyển động lùi tức thời, nếu có thêm cơ cấu chấp hành thì máy bay sẽ có thể cố định ở trên không hoặc chuyển động lùi. Một ràng buộc Nonholonomic là ràng buộc mà hướng di chuyển của xe phải khả thi và di chuyển được. Ví dụ về ràng buộc Nonholonomic Ràng buộc Holonomic sẽ ràng buộc về cấu trúc và vị trí, còn ràng buộc Nonholonomic sẽ ràng buộc về vận tốc nên sẽ liên quan đến các biểu thức đạo hàm và được sử dụng nhiều hơn trong nghiên cứu robot. Đối với robot di độnng Car-like cũng là một đối tượng có ràng buộc Nonholonomic nên việc điều khiển robot cần được áp dụng các phương pháp, giải thuật phù hợp.2 Cấu trúc robot di động Car-like Car-like robot là một loại robot di động có cấu hình bao gồm bốn bánh xe, hai bánh trước của robot sẽ đảm nhiệm việc đánh lái để thực hiện rẽ trái hoặc rẽ phải và 3 luôn song song với nhau.
Hai bánh sau được cố định và song song với thân xe, có nhiệm vụ dẫn động cho xe di chuyển. Hình 1-2 minh họa về cấu trúc của Car-like robot. Cấu trúc robot di động Car-like Trong đó, xP , yP là tọa độ của trung điểm trục cặp bánh xe trước P , xQ , yQ là tọa độ của trung điểm trục cặp bánh xe sau Q , D là khoảng cách giữa hai trục bánh xe trước và sau, v là vận tốc tuyến tính của robot, là góc định hướng của robot so với trục x , là góc đánh lái của robot. Như đã trình bày ở mục 1.3, Car-like robot là một đối tượng có ràng buộc Nonholonomic.
Chi tiết về ràng buộc Nonholonomic trong Car-like robot được trình bày ở mục 2.3 Lập kế hoạch đường đi và các giải thuật tìm đường đi của robot di động 1.1 Giới thiệu về lập kế hoạch đường đi Hình 1-3. Một ví dụ về path planning Lập kế hoạch đường đi (Path planning) là quá trình tạo ra một đường hình học, không đề cập đến bất kỳ quy luật thời gian nào [8]. Lập kế hoạch đường đi liên quan 4 đến việc xác định robot sẽ di chuyển như thế nào để đạt được mục đích của nó. Vấn đề của lập kế hoạch đường đi bao gồm tính toán những khoảng trống giữa điểm bắt đầu và điểm kết thúc.
Ngoài việc tránh vật cản, robot phải thỏa mãn một số điều kiện tối ưu của robot. Hình 1-3 là ví dụ về lập kế hoạch đường đi từ điểm A đến điểm B. Môi trường tự nhiên (môi trường thực) thường có những chỗ gồ ghề và những chỗ lõm xuống hay cả hai, trạng thái của vật cản có thể là đứng yên (không thay đổi vị trí trong khoảng thời gian cố định) hay chuyển động (thay đổi vị trí). Do đó lập kế hoạch đường đi có thể là cục bộ (local path planning) hay toàn cục (global path planning).
Local path planning là robot chuyển động và thu thập dữ liệu cùng lúc, lấy dữ liệu của môi trường từ các cảm biến. Trong trường hợp này robot có khả năng tạo ra đường đi mới để phản hồi sự thay đổi của môi trường. Global path planning chỉ có thể biểu diễn ở môi trường tĩnh, trong trường hợp này, một thuật toán sẽ tạo ra một đường đi hoàn chỉnh từ điểm bắt đầu đến điểm kết thúc trước khi robot di chuyển, sau đó robot sẽ thực hiện di chuyển từ điểm đầu đến điểm cuối. Hình 1-4 minh hoạt về hai trường hợp lập kế hoạch đường đi cục bộ và toàn cục.
Lập kế hoạch đường đi toàn cục (a) và cục bộ (b) 1.2 Một số phương pháp, giải thuật sử dụng để lập kế hoạch đường đi Tùy vào các môi trường, không gian làm việc khác nhau ta sẽ lập đường đi khác nhau và sử dụng các giải thuật khác nhau sao cho tối ưu nhất đối với robot di động. Có một số phương pháp phổ biến thường được sử dụng để lập kế hoạch đường đi như: Road maps (ví dụ Hình 1-5) [9], Cell decomposition [10], Potential fields [11], Vector field histograms [12], … 5 Hình 1-5. Phương pháp Road map tìm đường đi Bên cạnh đó cũng có một số phương pháp được đề xuất để lập kế hoạch đường đi trong bản đồ toàn cục như là: Thuật toán A* [13], thuật toán RRT* [14], … Ở đề tài này, nhóm sinh viên đề xuất sử dụng phương pháp kết hợp giữa giải thuật di truyền, trường thế năng nhân tạo và đường cong Dubins để lập kế hoạch đường đi tối ưu cho robot di động Car-like.4 Lý thuyết về giải thuật di truyền 1.1 Giới thiệu chung về giải thuật di truyền Giải thuật di truyền (Genetic Algorithm – GA), được Holland đề xuất vào năm 1975, là giải thuật tìm kiếm lời giải tối ưu dựa trên nguyên tắc phỏng theo quá trình tiến hóa và quy luật di truyền của sinh vật trong tự nhiên [15]. Giải thuật là các bước học tập mô phỏng theo cơ chế di truyền của sinh vật như: Luật di truyền của Mendel, thuyết tiến hóa của Darwin, … Bản chất toán học của GA là giải thuật tìm kiếm theo xác suất.
Hình 1-6 mô tả quá trình tiến hóa và chọn lọc tự nhiên, thế hệ mới luôn được sinh ra để bổ sung, thay thế thế hệ cũ. Cá thể nào thích nghi với môi trường sống tốt hơn sẽ có nhiều khả năng tồn tại và phát triển, ngược lại cá thể nào không thể thích nghi với môi trường sẽ bị đào thải. Quá trình chọn lọc tự nhiên GA là thuật toán tổng quát có khả năng giải quyết các bài toán ở nhiều lĩnh vực. Lời giải của GA không đảm bảo rằng sẽ tìm được lời giải tối ưu toàn cục cho bài toán 6 nhưng khi chưa tìm ra phương án, hoặc phương án chưa hiệu quả thì GA là một sự lựa chọn tốt để đưa ra kết quả hợp lý.2 Giải thuật di truyền cơ bản Để áp dụng GA giải bài toán tối ưu, trước hết phải mã hóa lời giải bài toán thành chuỗi nhiễm sắc thể (NST).
Mỗi NST bao gồm nhiều gen, một bộ gen tương ứng với một lời giải của bài toán cũng như đại diện cho một cá thể trong quần thể. Để có thể đánh giá được quần thể đó ta cần một hàm thích nghi. Thế hệ đầu tiên hay còn được gọi là quần thể ban đầu gồm nhiều cá thể được khởi động ngẫu nhiên. Qua quá trình tiến hóa và chọn lọc tự nhiên, những cá thể thích nghi nhất với môi trường sống sẽ tồn tại và có cơ hội tham gia vào quá trình sinh sản để tạo ra thế hệ con tốt hơn.
Cá thể có độ thích nghi càng cao thì càng có nhiều cơ hội bắt cặp với cá thể khác để sinh ra cá thể con. Khi hai cá thể được bắt cặp với nhau sinh ra thế hệ con thì thế hệ con sẽ được thừa hưởng các đặc tính của hai cá thể trước đó, quá trình này gọi là lai ghép. Trong quá trình tiến hóa, một số cá thể có thể bị đột biến, một hoặc một số gen trong chuỗi NST của cá thể bị thay đổi thành gen khác. Khi tình trạng này xảy ra, các cá thể có thể có tính trạng xấu hoặc tính trạng tốt vượt trội so với các cá thể khác.
Qua quá trình tiến hóa, các cá thể được đánh giá và chọn lọc ra cá thể tốt hơn, cuối cùng chọn ra được cá thể tốt nhất, từ đó dẫn đến lời giải bài toán cuối cùng là tối ưu. Lưu đồ giải thuật GA cơ bản được thể hiện trong Hình 1-7. Bắt đầu 1 Khởi động quần thể Đột biến Đánh giá Giải mã Mã hóa Đánh giá Chọn lọc Sai Hội tụ Đúng Lai ghép Kết thúc 1 Hình 1-7. Lưu đồ giải thuật di truyền 7 1.3 Các toán tử trong giải thuật di truyền 1.1 Khởi tạo quần thể ban đầu Bước đầu tiên của GA là khởi động quần thể ban đầu.
Quần thể ban đầu gồm N cá thể được khởi tạo ngẫu nhiên. Quần thể càng có nhiều cá thể thì quần thể đó càng đa dạng, dẫn đến lời giải của bài toán càng tối ưu. Tuy nhiên điều này dẫn đến là tốc độ hội tụ chậm, tốn nhiều thời gian, chi phí tính toán.