Bộ lọc hạt

Một cách xử lý kỹ thuật hơn cho bài đăng trên blog này ban đầu được xuất bản trên blog Udacity .

Rô-bốt sử dụng một thuật toán đơn giản nhưng mạnh mẽ đáng ngạc nhiên để tìm ra vị trí của chúng trên bản đồ, một vấn đề được các kỹ sư gọi là bản địa hóa. Thuật toán được gọi là lọc hạt trông tuyệt vời. Phần đầu tiên của bài báo gồm hai phần này đã được xuất bản tại đây . Trong bài viết đầu tiên này, chúng tôi sẽ làm sáng tỏ toán học cần thiết để xây dựng các bộ lọc hạt của riêng bạn.

Ô tô tự lái được thiết kế để hoạt động giống như người lái xe. Một hệ thống xe tự lái điển hình được xây dựng từ sáu thành phần. Mỗi thành phần trong số sáu thành phần giải quyết một vấn đề quan trọng cần thiết cho việc lái xe, xe tự lái hoặc các mặt khác. Các thành phần có thể được coi là thực hiện các chức năng bắt chước trình điều khiển của con người, đó là:

Bản địa hóa : Chúng ta đang ở đâu?
Lập kế hoạch tuyến đường : Làm thế nào để chúng ta đến đích?
Nhận thức : Có gì khác ở xung quanh?
Dự đoán : Môi trường sẽ như thế nào sau một thời gian ngắn nữa?
Lập kế hoạch : Khóa học mà chúng ta sẽ theo dõi trong vài giây tới là gì?
Kiểm soát : Làm thế nào chúng ta sẽ đi theo hướng chúng ta muốn?

Nội địa hóa cho con người có xu hướng rất dễ dàng. Chúng ta thường nhớ lại từ bộ nhớ nơi chúng ta đang ở trên thế giới, thường được hỗ trợ bởi thiết bị GPS như điện thoại thông minh giúp chúng ta xác định vị trí của mình chính xác hơn nhiều trên bản đồ. Chúng tôi cũng sử dụng các manh mối trực quan như biển báo điều hướng, vạch kẻ đường và hiểu biết của chúng tôi về các phương tiện khác, con đường và môi trường xung quanh để đảm bảo rằng chúng tôi luôn đi đúng làn, đi đúng đường và đi đúng hướng.

Khi nói đến nội địa hóa, lái xe tự động cũng yêu cầu vị trí và hướng xe đang di chuyển, còn được gọi là tiêu đề. Tuy nhiên, không giống như con người, mức độ chính xác mà xe tự hành yêu cầu là rất cao. Chỉ biết rằng xe đang đi trên làn đường bên phải và đi song song với làn đường đó là chưa đủ. Độ chính xác cao là cần thiết để lập kế hoạch. Nếu nội địa hóa sai lệch hơn vài centimet về vị trí hoặc hơn vài độ về tiêu đề, thành phần lập kế hoạch có thể tạo ra một hướng đi tai hại dẫn đến va chạm giữa nhiều kết quả không mong muốn khác.

Giống như con người, các phương tiện tự hành có được ước tính đầu tiên về vị trí và hướng đi từ GPS. Máy thu GPS, ngay cả những máy thu nhỏ được tìm thấy trên điện thoại thông minh, có xu hướng khá chính xác. Tuy nhiên, độ chính xác của thông tin bản địa hóa nhận được từ GPS là không đủ để lái xe tự hành an toàn. Ví dụ: vị trí được báo cáo có thể sai lệch từ một mét đến vài mét hoặc trong trường hợp xấu nhất thậm chí còn hơn thế nữa.

Độ chính xác dao động thường xuyên và mạnh tùy thuộc vào các yếu tố như số lượng vệ tinh mà máy thu có thể nhìn thấy, sự phản xạ của chùm tia vệ tinh khỏi các vật thể lớn như tòa nhà và sự hấp thụ của các yếu tố khí quyển.

Nếu điều đó chưa đủ tệ, thì tốc độ GPS cập nhật thông tin bản địa hóa cũng khá chậm, dao động trong khoảng 1–10Hz. Ngay cả ở tần số 10Hz, một phương tiện di chuyển với tốc độ chậm 20 km/h sẽ di chuyển khoảng nửa mét giữa hai lần cập nhật GPS.

Để giảm thiểu sự không chắc chắn trong nội địa hóa do chuyển động, xe tự hành sử dụng các đơn vị đo lường quán tính (IMU). IMU nhanh và chính xác đồng thời đo gia tốc và tốc độ rẽ của xe. Thông tin này sau đó có thể được sử dụng để xác định vị trí của ô tô giữa hai lần cập nhật GPS liên tiếp. IMU có xu hướng tích lũy các lỗi xấp xỉ nhỏ theo thời gian nhưng đó không phải là vấn đề mà chúng ta đang giải quyết ở đây.

Vấn đề cốt lõi mà hệ thống bản địa hóa cần phải giải quyết là các bản cập nhật GPS vốn đã không chính xác. Ví dụ, thay vì báo cáo một vị trí chính xác, GPS sẽ báo cáo một khu vực nhỏ trên mặt đất nơi có thể có phương tiện khi GPS tự cập nhật. Chúng tôi gọi khu vực này là một điểm GPS.

Vấn đề thực hiện định vị chính xác dẫn đến vấn đề giảm diện tích của điểm GPS.

Một trong những kỹ thuật đã được sử dụng trong chế tạo rô-bốt để định vị chính xác, bắt đầu từ một kỹ thuật kém chính xác hơn được gọi là lọc hạt . Nó rất hữu ích khi môi trường có một số điểm mốc, nghĩa là các đối tượng lớn, cố định không thường xuyên thay đổi vị trí, hình thức và kích thước. Đây có thể là các tòa nhà, tháp điện thoại di động, trụ cầu, cột điện hoặc tín hiệu giao thông và biển báo.

Để hiểu cách lọc hạt, chúng ta sẽ sử dụng phép loại suy. Giả sử bạn mệt mỏi trở về phòng khách sạn, tắt đèn và úp mặt xuống giường. Bạn thức dậy vào giữa đêm và muốn biết bạn đang ở đâu. Tất nhiên, bạn nhớ mình đã đâm vào giường nhưng bạn sẽ muốn biết mình đang quay mặt về hướng nào, công tắc đèn ở đâu và dép của bạn ở đâu. Điều này đòi hỏi sự chính xác hơn là một hồi ức mờ nhạt về việc ở trên giường.

Để nhanh chóng định hướng bản thân, bạn tận dụng môi trường xung quanh. Trước tiên, bạn hãy tưởng tượng mình đang ở những vị trí khác nhau trên giường. Sau đó, bạn cảm nhận các đối tượng 'mốc' trong môi trường xung quanh bằng cách chạm và xác định chúng. Bạn có thể đẩy một chai nước ra khỏi bàn gần đó hoặc vấp ngón chân vào ghế. Những quan sát này cung cấp cho bạn manh mối quan trọng về nơi bạn có khả năng ở trong lĩnh vực giường khách sạn. Vì bạn nhớ vị trí của cái chai, cái bàn và cái ghế so với giường, nên bạn có thể suy ra vị trí của mình trên giường chính xác hơn. Với mỗi lần quan sát mới, bạn có thể loại trừ một số vị trí nhất định trên giường và tăng cơ hội ở những vị trí khác.

Đây chính xác là cách lọc hạt hoạt động cho các phương tiện tự lái. Được trang bị một vị trí GPS ban đầu, chiếc xe biết vị trí gồ ghề của nó và hướng đi trên bản đồ. Vị trí thô này sau đó được chia thành các ô tưởng tượng nhỏ. Phương tiện cũng biết những địa danh nào ở gần vị trí gồ ghề đó. Sau đó, phương tiện sẽ thăm dò khoảng cách đến các mốc này bằng cách sử dụng một nắp đậy trên tàu. Sau đó, hệ thống định vị sẽ đối chiếu các phép đo này với từng ô tưởng tượng. Khi ngày càng có nhiều điểm mốc được thăm dò, hầu hết các ô bị loại trừ và chỉ một số ô có khả năng cao vẫn là vị trí có thể xảy ra.

Cái tên lọc hạt xuất phát từ thực tế là vị trí của từng ô tưởng tượng được biểu thị bằng hạt trên bản đồ và chúng tôi loại trừ các hạt bằng cách lọc chúng bằng cách tính khoảng cách đến các mốc và loại bỏ các hạt dường như không ở đúng khoảng cách các địa danh.

Hình ảnh động bên dưới hiển thị vị trí ban đầu của các hạt trải rộng trên một khu vực rộng lớn, có thể trải rộng trên một số làn đường, đường và khu vực trống. Việc cảm nhận hay thăm dò môi trường được thể hiện bằng các tia Blue. Chấm màu xanh lá cây đại diện cho vị trí có khả năng xảy ra nhất ban đầu sẽ nhảy xung quanh bản đồ nhưng sẽ ổn định rất nhanh khi ngày càng có nhiều hạt bị loại trừ bằng cách cảm nhận môi trường.

Lọc hạt là một thuật toán cực kỳ đơn giản hỗ trợ nhiều rô-bốt và ô tô tự lái. Nvidia Drive Labs đã phát hành một video ngắn về cách bản địa hóa có thể hưởng lợi từ các bản đồ phong phú với nhiều địa danh khác nhau. Uber ATG đã xuất bản một blog về cách họ cải thiện độ chính xác của GPS tại đây .