ROS Resources: Documentation | Support | Discussion Forum | Index | Service Status | Q&A answers.ros.org

# what's the principle of particle samples' clusters in the amcl packages?

Hello,

 when  I looked at the amcl package,i found amcl uses K-D Tree data structure to store the whole particle samples  as its leaf nodes. And also i found a particle samples set corresponds to some clusters,what's the principle of clustering  the K-D Tree


( https://github.com/ros-planning/navig... what's the knowledge in this function?

Thanks  very much , any advice would be appreciated!!

edit retag close merge delete

Sort by ยป oldest newest most voted

Let's look into pf_sample_set_t type.

typedef struct _pf_sample_set_t {
// The samples
int sample_count;
pf_sample_t *samples;

// A kdtree encoding the histogram
pf_kdtree_t *kdtree;

// Clusters
int cluster_count, cluster_max_count;
pf_cluster_t *clusters;

// Filter statistics
pf_vector_t mean;
pf_matrix_t cov;
int converged;
} pf_sample_set_t;


Sample particles are stored as an array hold by the pointer, samples, instead of kdtree. The kdtree is for constructing weight histogram of particles. The purposes of this histogram are to provide the number of non-empty bins for KLD-sampling and to calculate mean and covariance values from each cluster. This clustering algorithm for the kdtree histogram seems like a type of density-based clustering algorithms. Nodes connected to each other are labeled as a same cluster where connectivity is determined based on neighbor nodes. In pf_kdtree.c of amcl package, the neighbor node, nnode, of a node is

nkey[0] = node->key[0] + (i / 9) - 1;
nkey[1] = node->key[1] + ((i % 9) / 3) - 1;
nkey[2] = node->key[2] + ((i % 9) % 3) - 1;
nnode = pf_kdtree_find_node(self, self->root, nkey);


where key is the spatial information of a node.

more

@chung,thanks a lot !!!

( 2017-11-30 21:07:17 -0600 )edit