Abstract：Environment modeling is the basis for path planning of mobile robots. In this paper, a novel quadtree environment model based on location code is proposed for partially known or completely unknown environments. According to the one-to-one relationship between location codes of quadnodes and Cartesian coordinates, operations on quadtree are converted to the location code space, thus the operations are simplified. Several important operations are investigated and the detailed algorithms are also given. Based on the environment model, A* algorithm is applied to the path planning. The results demonstrate the validity of the proposed model.
1 Zelins ky A.A Mobile Robot Exploration Algorithm.IEEE Trans On Rob Auto,1992,8(6):707-717
2 Jung D,Gupta K K.Octr ee-based Hierarchical Distance Maps for Collision Detection.J Rob Sys,1997,14(11):789-806
3 Kam bhampati S,Davis L S.Multiresolution Path Planning for Mobile Robot.IEEE Trans,On Rob Auto,1986,RA-2(3):135-145
4 Noborio Het al.Aquadt ree-based Pat h-planning A lgorithm for a Mobile Robot.J Rob Sys,1990,7(4):555-574
5 Samet H.N eighb uor Finding Techniques for Image Repren sented by Quadtree.Compu Graph Image Proc,1982,18:37-57
6 Samet H.Distance Tranforma for Image Represented by Quadtrees.IEEE Trans On Patt Anal And Mach Intell,1982,PAMI-4(3):298-303