The M2M Pathfinding Algorithm Based on the Idea of Granular Computing
Haifeng Wan, Yingpeng Zhang, Shengzhou Luo, Ruijie Liu, Wensheng Ye · 2009
Macro-to-micro (M2M) model is an implementation model that inherits the GrC idea and extends it to some additional highly desirable characteristics. In this paper we introduce an effective pathfinding algorithm based on the M2M model. This algorithm takes O(n) time to preprocess, constructing the M2M data structure. Such hierarchical structure occupies O(n) bit memory space and can be updated in O(1) expected time to handle changes. Although the resulting path is not always the shortest one, it can make a trade-off between accuracy and time cost by adjusting a parameter - range value to satisfy various applications. At last, we will discuss the advantages of the M2M pathfinding algorithm (M2M-PF) and demonstrate the academic and applied prospect of M2M model.