P5 Presentation by Olivier Rodenberg: “The effect of A* pathfinding characteristics on the path length and performance in an octree representation of an indoor point cloud”
Date and time: Tuesday 28 June 2016 , 13:30.
Location: Architecture, TU Delft, BK-CZ E
Synopsis: This research presents a new workflow for path finding through an octree representation of an indoor point cloud. I applied the following steps: 1) the point cloud is processed so it fits best in an octree; 2) during the octree generation the interior empty nodes are filtered and further processed; 3) for each interior empty node the distance to the closest non empty node directly under it is computed; 4) a network graph is computed for all empty nodes; 5) the A* path finding algorithm is conducted. This workflow takes into account the connectivity for each node to all possible neighbours (face, edge and vertex and all sizes). Besides a collision avoidance system is pre-processed in two steps: first the clearance of each empty node is computed, and secondly the maximal crossing value between two empty neighbouring nodes is computed. The clearance is used to select interior empty nodes of appropriate size and the maximal crossing value is used to filter the network graph. And finally, both these datasets are used in A* path finding. Besides, benchmark tests are performed to identify the effects on path length and computation time due to: octree depth, path connectivity, pre processing neighbours and the distance types in path finding.
Supervisor 1: Associate professor dr. Sisi Zlatanova
Supervisor 2: ir. Edward Verbree
Co-reader: Dr.ir. Ben Gorte
Delegate: Dr.ir. Heidi Sohn