The Study Of Using Spatial Topological Relationship Reasoning In 3D Path Finding Under Restricted Area

As the urbanization spreads all over the built-up area, people needs path finding technology to help them make better moving decisions. The path planning of subway and inner building becomes the key subject especially on path finding issues. This study proposes a possible solution to path finding problem in certain restricted area under three dimension situations. Thus several key subjects and technologies needs to be discussed and improved to help build the spatial topology reasoning based 3D path finding solution.This study reviews the classical path finding methods and application patterns, and generates the main concerns of path finding development and related tools. We concluded the disadvantages of current path finding solutions as below:firstly, classical path finding solutions don’t use spatial topology relationships. Secondly, the basic moving styles are not properly discussed. Thirdly, current data organization is inefficient. Fourthly, evaluation system of optimized path is not suitable for current applications. Fifthly the representation method of optimized path is not human based. Thus this study has introduced improved searching algorithm, spatial topology relationships and spatial reasoning contents with related math tools and patterns. Next we represent the research target of this study is to build a working 3D path finding solution in restricted area which uses spatial topology relationships and reasoning. To finish this task this study introduces the spatial topology relationships of 3D data, a new improved representation pattern of optimized path and a new optimized path evaluation method based on moving plan’s energy cost. Therefore the key subjects of this study are multi-layers data organization and path planning, proper usage of spatial topology relationships, quantitative spatial reasoning, and improvement of classical A* algorithm.The first key subject of this study is the fusion of spatial topology relationships and quantitative spatial reasoning. For the path finding solution needs spatial topology relationships, but at the beginning of path finding process there is no existing spatial topology relationships, so the first step is to transform current spatial objects’ quantitative relationships into spatial topology relationships. Thus this study has introduced an improved spatial topology relationship system in restricted area. This improved spatial topology relationship system defines each spatial topology relationship with its own quantitative description set, which means a spatial topology relationship contains several related spatial quantitative relationships. After setting up mapping system between spatial topology relationships and spatial quantitative relationships, we can use this mapping system to analyze and form spatial topology relationships up in restricted area.For the path finding uses mass searching data, the data need to be organized into multi-layer format. The multi-layer format of path finding environment data can use the built up spatial topology relationships. As the spatial topology relationships’basic unit is object, this study uses R-Tree based data organization system to store spatial data. Besides data organization system, this study also discusses data compression possibility in restricted area’s path finding applications by using current methods.The optimized path representation of our work is different from traditional one. For our path finding solution considers user concerned elements, which make optimized path’s representation is determined by user’s interest focus. And the interest focus directly affects detail level and spatial scale of the optimized path. Besides focus based path representation method, this paper proposes a user-system interaction model of path finding and a human energy cost based path finding pattern.The path planning solution of this study can be concluded into three parts: pre-calculation of path finding environment, setting of path finding environment and execution of multi-layer A* path finding algorithm. The pre-calculation of path finding environment contains the definition of basic unit and moving styles of the path finding solution. The setting of path finding environment contains the method of building up multi-layer data structure and extraction of spatial topology relationships from quantitative description for specific path finding situation. The execution of multi-layer A* path finding algorithm contains 3D A* algorithm’s using pattern under spatial topology relationship system and multi-layer data structure.The experiment of this study contains two parts, which are algorithm efficiency demonstration and application simulation. Among the comparison of our path finding solution and classical solutions, our solution has shown lower storage cost and time cost. But our solution does have disadvantages such as lower optimized path quality. In the simulation, our solution has shown it can be widely used in restricted area’s applications.In the conclusion, the new 3D path finding solution based on spatial topology reasoning can finish specific path finding task by using comparative low calculation cost and generate human interest focus based multi-layer optimized path. The researching subject of our ongoing work concentrates on the improvement of multi-layer data organization and representation, basic unit’s setting research,3D spatial topology relationships extension.This study contains several innovative ideas:1. The introduction of spatial topological relationships into path finding process.2. The fusion of multi-layer optimized path results.3. Improvement on three dimension path finding patterns.