METHOD OF PATH NAVIGATION BASED ON HIERARCHICAL GRAPH AND METHOD OF PATH NAVIGATION IN IoT ENVIRONMENT USING THEREOF

摘要

The present invention relates to a hierarchical graph-based path search method. In the hierarchical graph-based path search method according to the present invention, a target space is configured as a grid map, and a start vertex and a target vertex are set by dividing a region, A first graph abstraction step of defining each vertex of the region as a basic hub to generate a first abstraction graph; A second graph abstraction step of defining a vertex having a higher connection centericity among vertices of each area of the first abstraction graph as a basic hub and connecting the basic hub to generate a second abstraction graph; A graph search step of searching a shortest path between the start vertex and the target vertex in the second abstraction graph; And a specifying step of projecting the path searched in the graph search step onto the grid map and specifying the path.;