Balanced-flow algorithm for path network planning in hierarchical spaces.

Path planning is an important and classical problem in theoretical research and practical applications. In the complex and hierarchical space scenarios, path planning faces more difficulties and challenges due to the structural particularity. Considering the directivity of paths in hierarchical spaces, it is more important to guarantee the fluency and efficiency of the paths in hierarchical spaces. In this paper, we introduce a path network planning problem from multi-source to multi-destination in hierarchical spaces, namely Balanced-Flow Path Network Planning (BF-PNP) problem, and prove its NP-completeness. To balance the flow rate among the layers in the space, we propose a batch scheduling algorithm with the objective of minimizing the scheduling time consumption. To evaluate the performance on efficiency and time complexity, we perform a series of simulations and the results indicate the advantages of the proposed algorithm. [ABSTRACT FROM AUTHOR]