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

申請號：	201410484603.3	申請日：	2014-09-19
公開（公告）號：	CN104298858A	公開（公告）日：	2015-01-21
發明（設計）人：	梁志偉;魏志鵬;沈杰	申請（專利權）人：	南京郵電大學
主分類號：	G06F19/00	分類號：	G06F19/00
代理公司：	南京經緯專利商標代理有限公司 32200	代理人：	吳庚水;朱小兵
地址：	210023 江***	國省代碼：	江蘇;32
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	robocup 救援平臺基于地圖劃分方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【權利要求書】：

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

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

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

2.根據權利要求1所述的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繼續執行。

3.根據權利要求2所述的RoboCup救援平臺中基于聚類和凸包的地圖劃分方法，其特征在于：所述的步驟A21中初始簇中心的確定通過Canopy初始聚類進行預處理以及距離最遠原則保證各簇的中心分布均勻來確定，具體包括以下步驟：

步驟A211：確定兩個距離D₁、D₂，其中D₁＞D₂，為地圖上節點之間的平均距離，Δd是一個先驗值；

步驟A212：設S為所有節點的集合，從集合S中隨機移除一個節點P，對于S中的所有其它節點分別計算與P點的距離：若該節點與P點的距離小于D₁，則將該節點加入到P所代表的Canopy簇中；若該節點與P點的距離小于D₂，則將該節點加入到P所代表的Canopy簇中，并從集合S中將該節點移除；迭代一次后，重新從S中選擇新的P點，重復本步驟，直至S集合中的所有節點都遍歷；

步驟A213：從S集合中掃描結束后，生成M個Canopy簇，進行操作如下：首先隨機選擇一個Canopy簇，設該簇中心為c₁；然后選擇離c₁最遠的Canopy簇，設該簇中心為c₂；其次選擇距離c₁、c₂最遠的Canopy簇，設該簇中心為c₃；以此類推，最終從M個Canopy簇中選擇k個簇中心，即得到K-means初始簇中心c₁,c₂,...,c_k。