Trang chủ Công nghệ & Ứng dụng Công nghệ & Ứng dụng Phát triển mạng lưới hiệu quả thông qua phân tích hành vi loài kiến

Phát triển mạng lưới hiệu quả thông qua phân tích hành vi loài kiến

Các nhà nghiên cứu tại học viện MiT đã phân tích hành vi của đàn kiến để phát triển một thuật toán tối ưu hơn trong mạng truyền thông công nghiệp. Thuật toán này có thể nâng cao khả năng ra quyết định giữa các robot và truyền thông trong mạng Ad-hoc.

 

Sự di chuyển của đàn kiến

Khi quan sát hoạt động của loài kiến, ta thấy rằng chúng thực sự xuất sắc trong việc liên kết và tập trung với các con kiến khác trong đàn. Khả năng này giúp chúng thực thi hành động trong nhiều hoạt động khác nhau của loài, đặc biệt là trong quá trình đàn kiến lựa chọn một tổ kiến mới.

Các nhà sinh vật học từ lâu đã đặt ra những nghi vấn rằng, phải chăng loài kiến xây dựng mật độ của chúng dựa trên tần số chúng va chạm với nhau khi chúng di chuyển để tìm kiếm những môi trường mới. Nghi vấn đó đã được củng cố bởi một bài nghiên cứu mới đây, đến từ Phòng thí nghiệm Trí tuệ nhân tạo và Khoa học máy tính của học viện MIT. Nghiên cứu chỉ ra rằng, sự quan sát từ sự khám phá ngẫu nhiên môi trường xung quanh giúp loài kiến phân bố mật độ của chúng một cách hết sức nhanh chóng. Không chỉ giúp các nhà sinh vật học giải đáp nghi vấn của mình, bài nghiên cứu có thể áp dụng để phân tích các mạng xã hội, đưa ra các quyết định chung trong một nhóm Robot cùng hoạt động, hay truyền thông trong các mạng Ad-hoc, ví dụ như các mạng Sensor làm việc trong các môi trường khắc nghiệt.

“Một cách trực quan, chúng ta có thể thấy rằng nếu một nhóm người đi bộ ngẫu nhiên xung quanh một khu vực, số lần mà họ va chạm vào nhau có thể được coi là mật độ của đám đông”, Cameron Musco, một đồng tác giả của bài báo phát biểu. “Cái mà chúng ta đang làm sẽ mang lại một phân tích chính xác sau quan sát trực quan đó, và cũng cho chúng ta một sự ước lượng rất đúng đắn, chính xác hơn hẳn các ước lượng thô khác.”

Mô hình mạng Ad-Hoc không dây

Di chuyển ngẫu nhiên

Musco và các đồng tác giả của anh, đã đặc tính hóa môi trường của loài kiến giống như một mạng lưới, với một số lượng con kiến nhất định phân bố ngẫu nhiên trong mạng lưới. Một con kiến trong đàn - chúng ta gọi là con kiến thám hiểm, sẽ xuất phát tại một điểm trong mạng lưới, và bắt đầu di chuyển tới các nút liên kết khác. Từ các nút liên kết đó, nó lại tiếp tục di chuyển tới các nút khác nữa… Trong thống kê, đây được gọi là “di chuyển ngẫu nhiên”. Con kiến thám hiểm sẽ đếm số con kiến mà nó gặp tại mỗi nút mà nó di chuyển tới trong mạng lưới.

Trong nghiên cứu của mình, các nhà nghiên cứu đã so sánh di chuyển ngẫu nhiên với lấy mẫu ngẫu nhiên. Nói dễ hiểu hơn, họ so sánh các nút được chọn trong mạng lưới một cách ngẫu nhiên với số nút mà con kiến thám hiểm di chuyển tới cũng theo một cách ngẫu nhiên. Và họ thấy rằng, tính toán theo sự di chuyển ngẫu nhiên sẽ cho kết quả mật độ đàn kiến nhanh hơn và chính xác hơn phương pháp lấy mẫu ngẫu nhiên. Kết quả này rất quan trọng vì trong nhiều trường hợp thực tế, không thể lựa chọn lấy mẫu ngẫu nhiên. Chỉ có một cách để khám phá nó là lựa chọn một thành viên độc lập và tiến hành theo dõi các kết nối của thành viên trong đàn. Tương tự như vậy, trong mạng Ad-Hoc, một thiết bị chỉ biết được vị trí của các thiết bị lân cận. Nó không thể biết được toàn bộ mạng lưới hệ thống. Một thuật toán sử dụng “di chuyển ngẫu nhiên” để tổng hợp thông tin từ nhiều thiết bị khác, sẽ dễ hơn nhiều khi sử dụng một thiết bị để mô tả đặc điểm của toàn bộ mạng lưới.

Có thể sử dụng thuật toán trên để điều khiển hoạt động của bầy Robot

Sự va chạm lặp lại

Kết quả của các nhà nghiên cứu gây ngạc nhiên, bởi mỗi điểm của di chuyển ngẫu nhiên, con kiến khám phá rất có thể quay lại điểm mà nó đã từng đi qua. Điều này khiến cho di chuyển ngẫu nhiên có thể bị trùng lặp cao hơn tại các điểm nút so với phương pháp lấy mẫu ngẫu nhiên.

Ban đầu, Musco và các cộng sự cho rằng đây là một vấn đề mà thuật toán tính toán mật độ của nhóm phải khắc phục. Nhưng nhóm sử dụng các phương pháp lọc các điểm trùng lặp trong di chuyển ngẫu nhiên và phương pháp này có vẻ lại làm cho thuật toán của họ trở nên thiếu hiệu quả hơn. Cuối cùng, sau một thời gian dài nghiên cứu, họ đã có thể tìm được lý do hợp lý cho vấn đề này.

Nếu bạn đang đi bộ ngẫu nhiên xung quang một mạng lưới, bạn sẽ không gặp tất cả mọi người bởi bạn không đi tới toàn bộ các điểm trong mạng lưới. Do đó, sẽ có một số người ở phía xa của mạng lưới mà có thể bạn sẽ không bao giờ gặp. Nhưng khi phần trăm bạn gặp những người ở xa càng ít, thì phần trăm bạn gặp những người ở gần sẽ càng nhiều hơn”, Musco nói. “Tôi sẽ cần đếm tất cả các tương tác của tôi với những người ở gần để tính bù cho trường hợp có những người ở xa mà tôi sẽ không bao giờ gặp. Nó giải quyết một cách hoàn hảo vấn đề cân bằng. Rất dễ để có thể chứng minh điều này, nhưng nó lại không thực sự trực quan. Vì thế, chúng ta cần nhiều thời gian để nhận ra điều này”.

Tổng quát hóa

Mạng lưới mà các nhà nghiên cứu sử dụng cho môi trường hoạt động của đàn kiến chỉ là một ví dụ đặc biệt của một cấu trúc dữ liệu được gọi là biểu đồ. Một biểu đồ có các nút, được biểu thị bởi các vòng tròn, và các cạnh biểu thị bởi các đường kết nối với các nút. Trong lưới, mỗi nhân là một nút và nó chỉ có chung cạnh với các nút ở lân cận mình.

Nếu biểu đồ không kết nối đủ tốt với nhau, ví dụ, biểu đồ kiểu chuỗi, trong đó một nút chỉ kết nối tới 02 nút lân cận, rất dễ xảy ra hiện tượng “over sampling”. Nếu trong chuỗi có 100 nút, một di chuyển tịnh tiến có thể gặp một nút khác với 5 hoặc 6 lần lặp lại liên tục trên quãng đường di chuyển.

Trong bài báo, các nhà nghiên cứu đã phân tích các di chuyển ngẫu nhiên bởi một con kiến đơn lẻ. Nếu quan sát và tính toán dựa trên di chuyển ngẫu nhiên của nhiều con kiến, có thể ước lượng kết quả nhanh chóng và chính xác hơn nhiều. “Nếu không phải là một đàn kiến, mà là một đàn Robot, chúng có thể giao tiếp với nhau và nói “Ồ, đây là tính toán của tôi”, Musco nói.

NHẬT MINH  (Theo www.mit.edu)

Số 187 (9/2016)♦Tạp chí tự động hóa ngày nay


Newer news items:
Older news items:

 

Hỗ trợ online

Hỗ trợ Web
Mr Phương: 0988906030

Liên kết & Quảng cáo


 
 
 






 

 

Nhà tài trợ


Sửa biến tần

Mới cập nhật

Tìm kiếm

Quảng cáo&Liên kết