Lattice occupied voxel lists for representation of spatial occupancy

The characteristics of a variety of 3D lattices are assessed for their performance when applied to typical robotics problems. The lattices studied are the Cubic, Body Centred Cubic (BCC), Face Centred Cubic (FCC), hexagonal prismatic and finally the Mean Centred Cuboidal (MCC). An algorithm for generic quantization to any low dimensional lattice is presented allowing this analysis to be easily extended to other 3D lattices of interest. Tests are undertaken on uniform sampled random data and laser range data from mobile robot platforms including an autonomous skid steer loader. The improvements in accuracy, memory requirements and consistency under rotation for the alternative lattices over the cubic lattice are typically 5-10%. The radial distribution of lattice points is studied through the distribution of points assigned to the same lattice cell and that in neighbouring cells. For instance only 12 neighbouring cells need checking for the FCC lattice as opposed to the cubic lattice which requires 26. Not only are fewer checks required but the distance variation associated with points in adjacent voxels of the FCC lattice is substantially lower than that of a cubic lattice. For the FCC lattice these point distances have a 30% smaller standard deviation and a 40% smaller range. These results make algorithms, such as collision checking and scan/map matching, which often involve many proximity checks, significantly faster and more accurate.