ROS Resources: Documentation | Support | Discussion Forum | Index | Service Status | ros @ Robotics Stack Exchange
Ask Your Question

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

asked 2016-08-23 02:13:47 -0500

jxl gravatar image

updated 2016-08-23 02:43:41 -0500


 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

( what's the knowledge in this function?

Thanks  very much , any advice would be appreciated!!
edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2017-09-24 08:49:01 -0500

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.

edit flag offensive delete link more


@chung,thanks a lot !!!

jxl gravatar image jxl  ( 2017-11-30 21:07:17 -0500 )edit

Question Tools

1 follower


Asked: 2016-08-23 02:13:47 -0500

Seen: 463 times

Last updated: Aug 23 '16