Merging of Octree Based 3D Occupancy Grid Maps

Abstract

A technique for merging 3D octree occupancy grid maps into a single global map of an evironment is proposed and implemented in software. Octrees are a memory efficient way to represent a 3D environment by recursively subdividing space at multiple depths in a tree structure. The use of an octree representation of a 3D environment allows large environments to be mapped while limiting the amount of memory used in comparison to other techniques. When multiple robots are used to map an environment, a more accurate map of a larger space can be produced in less time. Techniques are introduced to address information from multi-depth sources in each map's tree structure as well as techniques to address relative transformations between maps that are not axis aligned. These techniques allow the octree representation of an environment to be extended to multi-robot applications, specifically those situations where relative map reference frame transformations are unknown prior to mapping. Given the flexibility of this work to situations involving no prior knowledge of map transformations, this work also explores the problem of merging maps when the sources of map transformations are uncertain. Therefore registration techniques using commonly mapped portions of the environment to obtain a better estimate of transformations between maps are explored. The application of these techniques is demonstrated by merging maps built by robots in simulated and real-world environments. The results of this work show that the techniques proposed in this work to merge octree based occupancy grids are valid and that an octree based occupancy grid is a suitable map representation for multi-robot problem spaces requiring a 3D model of the environment.

Une technique pour la fusion de deux mappes représentées en forme de grilles d’occupation octree en 3D vers une seule mappe globale d’un environnement est proposée et implémentée en logiciel. Les Octrees sont efficaces en utilisation de la mémoire pour représenter un environnement 3D en sous-divisant récursivement l’espace dans une structure d’arbre à profondeurs multiples. L’utilisation de la représentation octree d’un environnement 3D nous permet de mapper de vastes environnements tout en limitant la mémoire utilisée en comparaison avec les autres techniques. Lorsque plusieurs robots sont utilités pour mapper un environnement, une mappe plus précise d’un espace plus grand peut être générée en moins de temps. Des techniques sont introduites pour dénouer l’information de différentes sources qui ont une profondeur différente dans chaque structure ainsi que des techniques qui visent les transformations relatives entre les mappes qui ne sont pas alignées sur leurs axes. Ces techniques permettent à la représentation par octree d’un environnement à être portée aux applications multi-robots, spécifiquement dans les situations où les transformations de cadre de référence relatif à chaque mappe sont inconnues avant le mappage. Étant donné la flexibilité de ce travail qui adressent les situations qui impliquent aucune connaissance des transformations des mappes avant le mappage, ce travail explore aussi le problème de la fusion de mappes quand les sources de transformations des mappes sont incertaines. Donc les techniques de régistration qui utilisent des portions communes mappées de l’environnement pour obtenir un meilleur estimé des transformations entre les mappes sont aussi examinées. L’application de ces techniques est démontrée en fusionnant des mappes construites par des robots dans des environnements simulés et dans le monde réel. Les résultats de ce travail démontrent que les techniques proposées dans ce travail pour faire la fusion des mappes en forme de grilles d’occupation octree sont valides et que les grilles d’occupation octree sont une représentation satisfaisante pour les mappes générées par un espace couvert par plusieurs robots qui ont besoin d’un modèle de l’environnement en 3D.