Spatial Information Research

Korea Spatial Information Society (대한공간정보학회)
권호 표지

Study on the Method to Create a Pedestrian Path Using Space Decomposition based on Quadtree

쿼드트리 기반의 공간분할 기법을 활용한 경로 생성 방안에 관한 연구

  • 가칠오 (서울대학교 건설환경공학부) ;
  • 우호석 (서울대학교 건설환경공학부) ;
  • 유기윤 (서울대학교 건설환경공학부)
  • Received : 2010.06.25
  • Accepted : 2010.10.04
  • Published : 2010.10.31
Download PDF
⟨ Previous Next ⟩

Abstract

Recently, the target of navigation system is moving from the cars to pedestrians. Many researches are in progress regarding pedestrian navigation, However, in most cases, the path-finding is based on the existing node/link network model. which is widely used for the car navigation, and thus showing its limitation. The reasons arc that a) unlike with a car, the paths that pedestrians take arc not limited to the roads, b) pedestrians an~ not restricted in rotation or direction, and c) they can freely move within the walkable space. No alternatives have been offered yet, especially for openspaces such as a park or square. Therefore, in this research, we suggested appropriate methods to create paths that can be used in pedestrian navigation service, by using motion-planning technology, which is used in the field of robotics for planning the motion of an object, and conducted tests for their applicability.

최근들어 대표적인 위치기반 서비스인 내비게이션은 기존 차량 중심의 서비스에서 보행자 중심의 서비스로 그 대상이 확대되고 있다. 이에 따라 최근에 보행자 내비게이션 관련하여 다양한 연구가 진행되고 있다 하지만, 내비게이션에서 가장 중요한 경로 서비스에 있어 대부분의 경우 차량 내비게이션에서 널리 활용되고 있는 노드/링크 네트워크 모델을 그대로 활용함으로써 한계점을 드러내고 있다. 그 이유로는 보행자는 차량과 달리 이동 공간이 도로로 한정되어 있지 않으며, 회전 규제, 방향 등에 제약을 받지 않고 보행이 가능한 공간에서 자유롭게 이동하는 등 보행 관련 특성들을 제대로 반영하지 못하기 때문이다. 특히, 공원, 광장 등의 오픈 페이스(open space)는 보행자기 많이 활용하는 공간임에도 불구하고 이에 대한 대안을 제공하지 못하고 있다. 따라서 본 연구에서는 게임 및 로보틱스 분야에서 객체의 이동을 계획하는 모션 플래닝(motion-planning) 기법을 응용하여 보행자 내비게이션 서비스에 적합한 경로 생성 기법을 제시하고, 그 활용 가능성을 테스트하였다.

Keywords

References

  1. Elias, B., Hampe, M. and Sester, M., 2004. "A daptive visualisation of landmarks using an M RDB", Map-based Mobile Services Theories, Methods and Implementations. Springer, pp. 75-88.
  2. 박인혜, 이지영, 2009, "실내 공간에서의 시간 가변적 최적 경로 탐색", 한국GIS학회지, 제17권, 제 3호, pp.361-370.
  3. Goodchild, M. F., 2000, "GIS and Transportation: Status and Challenges", GeoInformatica, Vol 4. pp.127-139. https://doi.org/10.1023/A:1009867905167
  4. Yuefeng Liu, Ting Liu, Min Lu and Huabo Sun, 2009, "Study on the Pedestrian Network Model Oriented to Pedestrian Navigation", 2009 Third International Conference on Multimedia and Ubiquitous Engineering, pp. 465-470.
  5. Elias, B., 2007, "Pedestrian navigation-Creating a tailored geodatabase for routing", In Proceeding from 4th Workshop on Positioning, Navigation and Communication, pp. 41-47.
  6. Zheng Pan, Lei Yan, Adam C., Winstanley, A. Stewart Fotheringham and Jianghua Zheng, 2009, "A 2-D ESPO Algorithm and Its Application in Pedestrian Path Planning Consi-dering Human Behavior", 2009 Third International Conference on Multimdedia and Ubiquitous Engineering, pp. 485-491.
  7. Jianghua Zheng, Adam C. Winstanley, Zheng Pan and Seamus Coveney, 2009, "Spatial Characteristics of Walking Areas for Pedestrian Navigation", 2009 Third International Conference on Multimdedia and Ubiquitous Engineering, pp. 452-428.
  8. Walter, V., Kada, M. and Chen, H., 2006, "Shortest path analyses in raster maps for pedestrian navigation in location based systems". International Symposium on Geospatial Databases for Sustainable Development, Goa, India, ISPRS Technical Commission IV (on CDROM) Ebenfalls erschienen in GIS 2006, pp. 8-11.
  9. PUN-CHENG, L.S.C., TANG, M.Y.F. and CHEUNG, I.K.L., 2007, "Exact cell decomposition on base map features for optimal path finding", International Journal of Geographical Information Science , 21(2), pp. 175-185. https://doi.org/10.1080/13658810600852206
  10. M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf, 2000, "Computational Geometry: Algorithms and Applications(second edition)", Springer.
  11. Jiang, B., Liu, X., 2010, "Automatic generation of the axial lines of urban environments to capture what we perceive", International Journal of Geographical Information Science, 24(4), pp. 545 -558. https://doi.org/10.1080/13658810902950351
  12. 전철민, 2006, "GIS 기반 Space Syntax를 이용한 대중교통 접근성", 한국공간정보시스템학회, 제8 권, 제3호, pp.25-33.
  13. Srikanta Patnaik, 2007, "Robot Cognitionand Navigation: An Experiment with Mobile Robots", Springer.
  14. Samet, H., 1982, "Neighbor finding techniques for images represented by quadtrees", Computer Graphics and ImageProcessing, 18(1), pp. 37-57. https://doi.org/10.1016/0146-664X(82)90098-3
  15. Gargantini, I., 1982, "An Effective Way to Represent Quadtrees", Communications of ACM, 25(12), pp. 905-910. https://doi.org/10.1145/358728.358741
  16. Voros, J., 1997, "A strategy for repetitive neighbor finding in images represented by quadtrees", Pattern Recognition Letters, 18(1997), pp. 955-962. https://doi.org/10.1016/S0167-8655(97)80001-3
  17. 우호석, 가칠오, 유기윤, 2010, "보행 경로 생성을 위한 쿼드트리 인접 쿼드 확산 기법", 한국지형공간정보학회 춘계학술대회, pp. 197-200.
  18. Hart, P. E., Nilsson, N. J. and Raphael, B., 1968, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2), pp. 100-107. https://doi.org/10.1109/TSSC.1968.300136
  19. Mcmaster, R. B., Shea, K. S., 1992, "Generalization in digital cartography", Association of American Geographers.