Occupancy-Grid Maps

Occupancy-grid maps (H.P. Moravec, 1988; H.P. Moravec et al, 1989; A. Elfes, 1987, A. Elfes, 1989; S. Thrun et al, 2005) :

Occupanny-grid map (bản đồ lưới) thể hiện môi trường được chia nhỏ thành các mắt lưới, các ô này có thể tự do( free) hoặc bị chiếm giữ( occupied), mỗi ô đại diện cho một diện tích thực tế trong môi trường thực và mỗi ô sẽ có một giá trị biểu diễn xác xuất nó có đang bị chiếm giữ hoặc tự do (chiếm giữ ở đây nghĩa là ở đó có vật cản, hoặc tường .., tự do(free) nghĩa là tại vị trí đó không có gì cả, và chúng ta có thể đi qua khu vực đó.

Giá trị occupancy của ô thứ nhất trong occupancy grid-map tại thời điểm t được biểu diễn bởi xác xuất p, .. P tại thời điểm t phải nằm trong khoảng từ 0 tới 1. Ta có thể hiểu rằng P= 1 nghĩa là ô đó bị chiếm giữ(occupied), P=0 nghĩa là ô đó trống(free), P=0.5 nghĩa là không biết(unknown) hoặc khu vực chưa khám phá (unexplored area).

Các bạn có đồng ý rằng, Robot không có bất kì nhận định nào về thế giới mà lần đầu nó bị đặt vào trong đó. Cũng như bạn bị bắt cóc đến một nơi xa lạ vậy, bạn hoàn toàn mất phương hướng. Do đó P sẽ có giá trị P=0.5 co tất cả i tại thời điểm t=0. Map sẽ được cập nhật thông qua log odds của occupancy. Sự vượt trội của log odd là nó có thể tránh được sự nhập nhằng giữa 0 và 1, vì đôi khi giá trị của nó sẽ là 0,3 hoặc 0,7. Do đó, ta có cách tính tình trạng bị chiếm giữ của ô thứ n trong grid-map theo công thức sau:

 

với lt-1 là log odds được tính từ giá trị occupancy của ô tại thời điểm t-1. Hình 1(a) miêu tả quá trình cập nhật của map. Ô màu đen thể hiện tia laser gặp phải vật cản ở đó ngược lại  các ô màu trắng thể hiện là những vị trí có tia laser đi qua nhưng không bị cản trở, ô màu xám là nơi tia laser không đi qua. Hình 1(b) thể hiện trường hợp tia laser không gặp vật cản nào nhưng đạt mức maximum của nó.

Hình ảnh dưới đây là Occupancy Grid map trong thực tế được tạo bởi một máy quét laser, khu vực rìa màu đen thể hiện vật cản, khu vực trắng là trống và khu vực màu xám là tia laser chưa đi qua.

Topological  Maps,

Không giống như occupancy grid map, topological maps (D. Kortenkamp et al, 1994; H. Choset, 1996; H. Choset et al, 1996) không thể hiện môi trường xung quanh một cách trực quan bằng cách chia nhỏ bản đồ ra như trên. Thay vào đó, topological map thể hiện môi trường quanh nó như một đồ thị (graph).

Giống như trong hình 3. Một danh sách những khu vực quan trọng như tường, góc, cửa hoặc hành lang, những khu vực này được thể hiện dưới dạng các điểm(node) m. Sự liên kết giữa các điểm m được thể hiện dưới các liên kết Uk. Trong rất nhiều topological map, khoảng cách giữa các khu vực cũng được thể hiện trong các sợi dây liên kết các nodes này. Sự ưu việt của topological map là nó thể hiện các khu vực trong map rất chi tiết, ta có thể zoom vào để xem đặc tính từng khu vực, điều này lý giải tại sao topological map được dùng để phát triển 3D-map.

Topological maps là sự lựa chọn tối ưu hơn nếu người dùng quan tâm dung lượng bộ nhớ. Trong trường hợp chúng ta sử dụng laptop hay raspberry pi có dung lượng bộ nhớ thấp. Đó là bởi vì ít memory cần để lưu giữ nodes so với một số lượng lớn các ô được sử dụng trong grid-map. Tuy nhiên điều này cũng đồng nghĩa với, graph-map sẽ ít chính xác hơn grid-map. Lý do là một số thông tin quan trọng ví dụ như vị trí của các ô màu xám mà tia laser không đến được sẽ không được hiển  thị trong bản đồ. Do đó khi robot sử dụng graph-map sẽ không thể di chuyển nhanh mà vẫn giữ an toàn như sử dụng grid-map, lời khuyên là khi sử dụng topological map thì nên cho robot di chuyển chậm thôi.