[發明專利]RoboCup救援平臺中基于聚類和凸包的地圖劃分方法

在審

• 申請號: 201410484603.3
• 申請日: 2014-09-19
• 公開（公告）號: CN104298858A
• 公開（公告）日: 2015-01-21
• 發明（設計）人: 梁志偉;魏志鵬;沈杰
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 吳庚水;朱小兵

技術領域

本發明屬于機器人仿真技術領域，具體涉及一種RoboCup救援平臺中基于聚類和凸包的地圖劃分方法。

背景技術

多智能體協作一直是人工智能領域的研究熱點，在機器人救援領域中救援機器人的協作面臨著環境未知且動態變化、通信及資源受限等諸多挑戰。RoboCup機器人救援智能體仿真平臺中機器人的感知信息也具有局部性、相對性、不準確等特點。

作為救援智能體協作的基礎，世界模型(World?Model)是一個可以獲取和保存所有客觀對象信息的結構集合，包括各救援智能體的異構類型、位置、狀態以及災難環境中其它對象的相關狀態信息。世界模型是整個多智能體協作的基石，是所有外部環境和內部自身狀態的整合，是救援智能體進行所有推理和決策的前提，類似人腦的存儲結構，體現了智能體對當前環境的認知能力。

因此針對RoboCup機器人救援智能體仿真平臺中機器人的感知信息的不足，需要設計一種新的救援智能體的世界模型構建和信息更新模型，智能體在行動前和行動中使用該模型對地圖信息進行認知，獲得對動態變化對象的狀態估計，從而使智能體對災難環境的認知接近真實環境，為智能體的上層行為決策提供有力支持。

發明內容

本發明的目的是提供一種RoboCup救援平臺中基于聚類和凸包的地圖劃分方法解決現有技術中存在的RoboCup機器人救援智能體仿真平臺中機器人的感知信息也具有局部性、相對性、不準確的問題。

本發明解決其技術問題所采用的技術方案是：提出一種RoboCup救援平臺中基于聚類和凸包的地圖劃分方法，智能體在行動前和行動中使用世界模型對地圖信息進行認知，包括對地圖建筑按距離進行聚類劃分和對燃燒建筑群進行動態凸集識別，獲得對動態變化對象的狀態估計。

RoboCup救援平臺中基于聚類和凸包的地圖劃分方法，所述方法包括以下步驟：

步驟A：對于地圖建筑按距離進行聚類劃分；

步驟B：對燃燒建筑群進行動態凸集識別。

進一步地，本發明的RoboCup救援平臺中基于聚類和凸包的地圖劃分方法，所述的步驟A具體包括以下步驟：

步驟A1：將地圖信息抽象化：設每個道路和建筑均抽象成一個個頂點，將地圖抽象成無向圖的數據結構G＜N,E＞，其中N表示頂點集合，E表示邊集合，邊是頂點的有序偶對，若兩個頂點之間存在一條邊，表示著兩個頂點具有相鄰關系；

步驟A2：進行基于K-means聚類方法的地圖聚類：將整個地圖上的各個節點基于距離采用迭代更新的方法分成多個簇；設二維數據集合X＝{x_i|x_i∈R²,i＝1,2,...,N}聚集成k個簇w₁,w₂,...,w_k，它們的中心依次為c₁,c₂,...,c_k，其中n_i是簇w_i中所有數據點的個數；N為數據集合X的大小，所述K-means聚類方法具體包括以下步驟：

步驟A21：從X中隨機選擇k個初始簇中心c₁,c₂,...,c_k；

步驟A22：將數據集合X按最小歐式距離原則分配到最近鄰的聚類簇中：若滿足d_ij(x_i,c_j)＜d_im(x_i,c_m)，則將x_i劃分到c_j所在的簇中，m＝1,...,k；j＝1,...,k；j≠m；i＝1,...,N；其中，d_ij表示x_i到c_j的最小歐式距離；d_im表示x_i到c_m的最小歐式距離；

步驟A23：根據公式更新計算每個簇的質心

步驟A24：如果對于任意都成立，則算法結束，將作為新的質心；否則令c_i＝c_i^*，返回步驟A22繼續執行。

進一步地，本發明的RoboCup救援平臺中基于聚類和凸包的地圖劃分方法，所述的步驟A21中初始簇中心的確定通過Canopy初始聚類進行預處理以及距離最遠原則保證各簇的中心分布均勻來確定，具體包括以下步驟：