chương 1 Tự định vị là khả năng cốt lõi của Robot tự hành. Bài toán định vị trong môi trường đã biết hoặc trong môi trường chưa biết trước: - Nhận biết môi trường nhờ cảm biến. - Đồng thời ước tính vị trí của nó trong môi trường. Nguyên lý định vị: Robot tự hành có thể theo dõi chuyển động của mình bằng cách sử dụng Odometry khi điều hướng.
- Trong thực tế, Odometry không đủ tin cậy, làm cho Robot nhận thức sai về vị trí hiện tại của mình. - Robot cần thêm xác định vị trí của mình liên quan đến bản đồ môi trường. - Robot sử dụng các cảm biến (Laser, Camera, …) để xác định vị trí. Trích xuất dữ liệu từ cảm biến để tăng độ tin cậy trong thông tin về ước tính vị trí của nó.
[8] Định vị Markov là một phương pháp để ước lượng vị trí của một robot trong một môi trường chưa biết trước. Mô hình Markov mô tả xác suất di chuyển của robot và xác suất đo của các cảm biến, dựa trên các thông tin đã thu thập được. Ước lượng được xác suất của mỗi vị trí có thể là vị trí hiện tại của đối tượng di chuyển. [9] Bộ lọc Kalman sử dụng một mô hình toán học để dự đoán vị trí của Robot dựa trên các đầu vào từ GPS, mạng lưới cảm biến, camera hoặc cảm biến vô tuyến.
Bộ lọc Kalman tính toán lại vị trí dựa trên các đầu vào mới nhất và đưa ra ước tính vị trí chính xác hơn và dự đoán vị trí của hệ thống trong tương lai. [10] Một số phương pháp khác như Extended Kalman Filter (EKF) là một phương pháp ước lượng trạng thái cho các hệ động lực phi tuyến tính. Có một số hạn chế, bao gồm việc khó tính toán và sự ảnh hưởng của các sai số đo lường. Monte Carlo Localization - MCL sử dụng một tập hợp các mẫu (particles) để biểu diễn phân phối xác suất này, với mỗi mẫu đại diện cho một trạng thái ước lượng của robot.
MCL là một phương pháp đáng tin cậy và được sử dụng rộng rãi trong robot di động và robot bay tự động. Tuy nhiên, phương pháp này cũng có một số hạn chế, bao gồm độ phức tạp tính toán và độ chính xác bị ảnh hưởng bởi số lượng mẫu và cách chọn các tham số của phương pháp. Trong bài toán định vị cho Robot, các thông tin về vị trí phải đủ tin cậy để Robot hoạt động chính xác và ổn định. Do đó định vị cho Robot đóng vai trò làm 21 tiền đề thực hiện các nhiệm vụ tiếp theo.
Trong thực tế, để có được kết quả định vị một cách hiệu quả và đáng tin cậy, nhiều trường thông tin sẽ được kết hợp cho phương pháp giải định vị như encoder (odometry), cảm biến GPS, cảm biến gia tốc (IMU),. Trong nội dung luận văn, để đánh giá khả năng làm việc của thuật toán, chỉ dữ liệu Lidar 2D được sử dụng một cách độc lập. [6] Sau khi có những thông tin đã thu thập được, phân tích và tìm ra kết quả cuối cùng, ta cần kết hợp các giải thuật. Việc sử dụng Lidar 2D cho bài toán định vị robot tự hành hỗ trợ giải quyết bài toán dễ dàng hơn, xác định được không gian 2D xung quanh của Robot, kết hợp thuật toán để xác định được vị trí chính xác của Robot trong môi trường.
Qua chương tiếp theo, sẽ trình bày cơ sở một số giải thuật, từ đó chọn lựa giải thuật phù hợp nhất cho bài toán. 22 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT GIẢI THUẬT ĐỊNH VỊ 2.1 Định vị dựa trên giải thuật tiến hóa Sự phát triển của các giải pháp định vị robot từ cách tiếp cận dựa trên lý thuyết xác suất , trong đó lý thuyết Bayes được áp dụng đã rất chiếm ưu thế trong các nghiên cứu trong cộng đồng nghiên cứu robot tự hành. Họ các giải thuật tiến hóa (EAs) là kỹ thuật tối ưu hóa dựa trên tự nhiên được áp dụng rất rộng rãi cho các lĩnh vực và vấn đề khác nhau vì tính đơn giản và linh hoạt của nó. Các ứng dụng của EAs trong định vị robot tự hành và các vấn đề liên quan đã xuất hiện khá sớm [10].
Giải thuật di truyền (GA) đã được áp dụng để tăng cường bộ lọc Kalman trong việc định vị robot tự hành [4]. Đầu ra từ bộ lọc Kalman được coi là một giải pháp thô. Sau đó, một không gian giải pháp có điều kiện đã được GA tìm kiếm ra một giải pháp tốt. Do việc sử dụng không gian tìm kiếm có điều kiện, GA trở nên hiệu quả trong tính toán thời gian thực.
Các cách tiếp cận dựa trên giải thuật tiến hóa có khả năng xử lý các phân phối phi tuyến nhiễu non-Gaussian cũng như các không gian trạng thái của Robot. Tương tự như phương pháp định vị Monte Carlo, các phương pháp này biểu diễn phân bố của xác suất bằng cách duy trì một tập hợp các điểm trên tất cả các trạng thái tiềm năng có thể có của Robot và được tính trọng số bởi hàm mục tiêu. Ý tưởng là ước tính đệ quy tư thế (vị trí và hướng) của robot bằng một tập hợp các giải pháp khả thi. Sự khác biệt chính so với định vị Monte Carlo là việc sử dụng các kỹ thu ật thích ứng tiến hóa để hội tụ các giải pháp khả thi đối với tư thế ước tính của robot và cũng sử dụng hàm mục tiêu để đánh giá mức độ phù hợp hay xác định trọng số của từng “cá thể”.
[4] [7] Sự khác biệt chính giữa bài toán định vị robot tự hành và các bài toán tối ưu hóa cổ điển khác được giải quyết bằng giải thuật tiến hóa có thể được xác định như sau: (1) Mô hình trong bài toán định vị robot là một hệ thống động (vị trí của robot thay đổi khi nó di chuyển) và hệ thống tĩnh (các điểm mốc đứng yên) và vị trí của robot so với các mốc không biết trước; (2) Các phép đo được thực hiện giữa rô bốt và các điểm mốc, ví dụ: các phép đo khoảng cách bằng laser. Các cột mốc tĩnh có thể được mở rộng khi robot đi ra xa, cộng thêm phép đo luôn bị ảnh hưởng bởi nhiễu. Đối với các vấn đề tối ưu hóa cổ điển chủ yếu liên quan đến một hệ thống tĩnh. Từ góc độ tính toán dựa trên tiến hóa, một sai số tối thiểu giữa trạng thái ước tính của Robot và trạng thái thực sự có thể được xem là một đối tượng để tối ưu hóa (giảm thiểu hóa).
Dựa và quan điểm này, Tác giảxây dựng hàm mục tiêu là sai số tối thiểu giữa ước tính về trạng thái của robot (được chọn trong tập hợp các giải pháp tiềm năng) và giải pháp thực sự (nghiệm hội tụ của bài toán tối ưu).3 Họ các giải thuật tiến hóa Ngày nay, trong lĩnh vực nghiên cứu toán tối ưu, chúng ta có thể quan sát sự phát triển mạnh mẽ để tìm kiếm các kỹ thuật tối ưu hóa mới dựa trên tự nhiên. Hiện nay, toàn bộ họ thuật toán tối ưu hóa tiến hóa được gọi là thuật toán tính toán tiến hóa (Evolutionary Computation - EC). Trong lĩnh vực tính toán tiến hóa, chúng ta có thể kể đến các thuật toán chính sau: Giải thuật di truyền (Genetic Algorithm - GA), Lập trình di truyền (Genetic Programming - GP), phát triển khác biệt (Differential Evolution - DE), Chiến lược tiến hóa (Evolution Strategy - ES) và lập trình tiến hóa (Evolutionary Programming - EP). Mỗi kỹ thuật này có nhiều biến thể khác nhau và được sử dụng trong nhiều ứng dụng công nghiệp khác nhau.
Các thuật toán dựa trên tự nhiên có thể kể đến các thuật toán đàn đội thông minh (Swarm Intelligence Algorithms - SIAs) như tối ưu hóa đàn kiến (Ant Colony Optimization - ACO), tối ưu hóa đàn hạt (Particle Swarm Optimization - PSO) và các thuật toán cộng tác cộng đồng. Các phương pháp khác dựa trên tự nhiên, như họ thuật toán vật lý (ví dụ: tối ưu hóa giả lập (Simulated Annealing), tối ưu hóa cực đại (Extremal Optimization), tìm kiếm âm nhạc (Harmony Search), thuật toán văn hóa (Cultural Algorithm), tìm kiếm vô hướng (Gravitational Search), động lực hình thành sông (River Formation Dynamics), thuật toán lỗ đen (Black Hole Algorithm), hoặc họ thuật toán thông minh thực vật (ví dụ: thuật toán thụ phấn hoa (Flower Pollination Algorithm), tối ưu hóa cỏ xâm lấn (Invasive Weed Optimization), thuật toán đồng cỏ (Paddy Field Algorithm), thuật toán tối ưu hóa nhân tạo (Artificial Plant Optimization Algorithm), thuật toán quang hợp (Photosynthetic Algorithm), tối ưu hóa sự phát triển cây (Plant Growth Optimization), tối ưu hóa cây gốc (Rooted Tree Optimization) ít phổ biến hơn. Evolutionary algorithms (EAs) sử dụng các thuật ngữ được mượn từ di truyền học. Ví dụ, chúng ta nói về một quần thể các cá thể, và các thuật ngữ cơ bản là gene, chromosome, genotype, phenotype và allel.
Các thuật ngữ tương ứng với chúng và xuất phát từ từ vựng kỹ thuật cũng được sử dụng, chẳng hạn như chuỗi, chuỗi nhị phân và cấu trúc. - Quần thể là một tập hợp các cá thể có kích thước xác định. - Các cá thể của một quần thể trong Giải thuật di truyền là các bộ tham số nhiệm vụ được mã hoá dưới dạng các chromosome, có thể được coi là điểm tìm kiếm trong không gian chứa các giải pháp. - Chromosome - còn được gọi là chuỗi hoặc chuỗi mã - là các chuỗi được sắp xếp của các gene.
- Gene - còn được gọi là đặc điểm, dấu hiệ u hoặc bộ dò - tạo thành một phần tử đơn lẻ của genotype, của chromosome trong đặc biệt. - Genotype - còn được gọi là cấu trúc gen - là một tập hợp các nhiễm sắc thể của một cá thể nhất định. Do đó, các cá thể trong một quần thể có thể là genoty hoặc đơn giản chỉ là một nhiễm sắc thể (nếu genoty chỉ bao gồm một nhiễm sắc thể, điều này thường được giả định). 24 - Phenotype - là một tập hợp các giá trị tương ứng với một genoty cụ thể, đó là một cấu trúc được giải mã và do đó là một tập hợp các tham số nhiệm vụ (một giải pháp, điểm không gian tìm kiếm).
- Allel - là giá trị của một gene cụ thể, cũng được xác định là giá trị đặc trưng hoặc biến thể đặc trưng. - Locus - là một vị trí chỉ ra vị trí của một gene cụ thể trong chuỗi, nghĩa là trong nhiễm sắc thể (hình thức số nhiều của nó, có nghĩa là "vị trí", được gọi là loci). Một khái niệm rất quan trọng trong giải thuật di truyền là hàm thích ứng hay còn được gọi là hàm mục tiêu hoặc hàm đánh giá. Nó cấu thành thước đo mức độ phù hợp (thích ứng) của một cá nhân nhất định trong quần thể.