Abstract: In order to solve the problem that the existing research results can not effectively solve the problem of uncertain data clustering in the dynamic obstacle space, according to whether the set of obstacles is changed, this paper proposes the uncertain data clustering algorithms in static obstacle space and dynamic obstacle space. These uncertain data clustering algorithms include STA_GOBSCAN (DBSCAN clustering algorithm for static obstacles in grid space), DYN_GOCBSCAN (DBSCAN clustering algorithm for dynamic increase of obstacles in grid space), DYN_GORBSCAN (DBSCAN clustering algorithm for dynamic reduction of obstacles in grid space) and DYN_ GOMBSCAN (DBSCAN clustering algorithm for dynamic movement of obstacles in grid space). The KL distance is used to measure the similarity of uncertain data, and the data space is divided by the grid. Theoretical research and experimental results show that the algorithms proposed in this paper have extremely high efficiency and accuracy.

Key words: static obstacles, dynamic obstacles, Kullback-Leibler divergence, uncertain data, grid

摘要： 为了解决已有研究成果无法有效解决动态障碍空间中的不确定数据聚类问题，根据障碍集合是否发生变化，分别解决静态障碍和动态障碍空间下的聚类问题。提出了静态障碍空间中的不确定数据聚类算法（DBSCAN clustering algorithm for static obstacles in grid space，STA_GOBSCAN）、障碍物动态增加情况下的不确定数据聚类算法（DBSCAN clustering algorithm for dynamic increase of obstacles in grid space，DYN_ GOCBSCAN）、障碍物动态减少情况下的不确定数据聚类算法（DBSCAN clustering algorithm for dynamic reduction of obstacles in grid space，DYN_GORBSCAN）和障碍物动态移动情况下的不确定数据聚类算法（DBSCAN clustering algorithm for dynamic movement of obstacles in grid space，DYN_GOMBSCAN），采用KL距离对不确定数据进行相似性度量，并利用网格对数据空间进行划分。理论研究和实验结果表明所提出的算法具有较高的效率和准确率。

关键词: 静态障碍, 动态障碍, KL距离, 不确定数据, 网格