Institute of Cartography and Geoinformatics Institute Search for Persons Shkedova Theses
Occupancy-free Space Modeling and Navigation Path Planning in a 3D Voxel Grid Environment for Urban Digital Twin Applications

Occupancy-free Space Modeling and Navigation Path Planning in a 3D Voxel Grid Environment for Urban Digital Twin Applications

Led by:  Shkedova, Feuerhake
Team:  Shkedova, Feuerhake
Year:  2023
Date:  13-11-23


The urban digital twin is an innovative concept within smart city technology, aiming to develop integrated and intelligent systems by harnessing diverse data from a multitude of sensors. Three-dimensional (3D) geodata plays a pivotal role in the representation and operation of urban digital twins. Tasks such as smart space management and navigation have become increasingly essential in urban digital twin applications, and they can be effectively facilitated using a foundation of 3D geospatial data. Therefore, this master thesis focuses on the modeling of unoccupied space and navigation path planning, employing a 3D voxel grid environment representation. The objective of the thesis is to develop a suitable approach for defining vacant space within urban area, which is utilized to enable collision-free 3D navigation. To achieve this, it is proposed to integrate the point cloud data of the Hannover urban area into a 3D voxel grid structure. In this context, grid cells containing point cloud data are treated as obstacles, while unoccupied cells are collectively constitute the occupancy-free space. The identified vacant space serve as a graph for implementing the shortest path algorithm. Ultimately, both the occupancy-free space and an illustrative route through it are visualized to demonstrate the approach viability.



  1. The relevant literature and existing methods review
  2. Occupancy-free space modelling and the 3D navigation path computation within urban area of Hannover
    1. 3D voxel grid structure formation from point cloud data set
    2. Implementation of the approach for unoccupied space definition in a 3D voxel grid environment
    3. Implementation of a shortest path algorithm
    4. Visualization of the modeled occupancy-free space and the route
  3. Evaluation of the performed results
  4. Writing the documentation and the report


  • Point cloud data from mobile mapping system measured in urban area of Hannover


  • Knowledge of programming language, such as Python or others.
  • Familiarity with “SLAM and path planning” and “ Laser Scanning - Modelling and Interpretation” courses would be advantageous


M.Sc. Olga Shkedova (

Dr.-Ing Udo Feuerhake (

Prof. Dr.-Ing. habil. Monika Sester (

Institut für Kartographie und Geoinformatik, Appelstr. 9a, 30167 Hannover