경로 탐색 정확도 향상을 위한 격자 기반의 보행 안내 알고리즘
Grid-based Navigation Algorithm for Improving Accuracy of Path Finding
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
우리는 이전에 목적지까지 안전하게 보행할 수 있도록 하는 시각장애인용 보행지원 시스템을 개발하였다. 이 시스템은 실내외 특정 위치에 POI (Point of Interest)를 설정하고 실내에서는 인공 표식 (landmark), 실외에서는 지그비 (Zigbee) 모듈을 이용하여 사용자의 위치를 추정하고 보행 경로를 탐색 하였다. 본 논문에서는 이 시스템에서경로 탐색을 위해 이용한 격자 기반의 지도 저작 툴과 보행용 A* 알고리즘을 소개한다. 실내외의 POI, 고정 장애물이나 교차로, 출발지와 목적지 등의 위치는 지도 저작 툴을 이용하여 작성하였다. 벡터 기반의 지도보다 격자 기반의 지도를 작성하여 경로를 탐색함으로써 상세한 지도 작성으로 인한 경로 탐색 정확도를 향상시키고, 제안하는 보행용 알고리즘을 사용함으로써 빠른 경로 탐색이 가능하였다.
Abstract
We developed a guidance system for visually impaired person that guides the user to walk safely to the destination in the previous study. We set a POI (Point of Interest) of a specific location indoors and outdoors and tracks the user's position and navigate the walking path using artificial markers and ZigBee modules as landmark. In this paper, we introduce a grid-based map authoring tool and the A* algorithm to be used for navigation in the system. We map the important spots such as POI, fixed obstacles, intersections, departure point, and destination using the map authoring tool. These improved the accuracy of searching the path since we used not the vector-based map but the detailed grid-based map, and reduced searching time of the path by using a proposed algorithm.
참고문헌 (17)
- E. Leiserson, Charles, "A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers)", ACM Symp. on Parallelism in Algorithms and Architectures (2010)
- J. Kleinberg, "Algorithm Design", pp.92~94 (2006), Addison Wesley
- H. Thomas, "Introduction to Algorithms", pp.595~601 (2001), MIT Press and McGraw–Hill
- W, Zeng, "Finding shortest paths on real road networks: the case for A*", International Journal of Geographical Information Science, 23(4), pp.531~543 (2009)
- J. S. Baek, "A Study on the Autonomous Navigation Algorithm of the Unmanned Ground Combat Vehicle in Partially Unknown Environment", Defense Science & Technology, 12, pp.58~67 (2008)
- A. Stentz, "The Focused D* Algorithm for Real-Time Planning", Proceedings of the International Joint Conference on Artificial Intelligence, pp.1652~1659 (1995)
- Lifelong Planning A*, "S. Koenig", Georgia Institute of Technology, 93~146, pp.Technical Report GIT-COGSCI- 2002 (2001), 2
- S. Koenig, "D* Lite", Proceedings of the National Conference on Artificial Intelligence, pp.476~483 (2002)
- Path Planning with D* Lite, "D. Macka", Defense R&D, 9~18, pp.Defense R&D Canada Suffield TM 2005-242 (2005)
- B. Stout, "Smart Moves: Intelligent Path finding", pp.28~35 (1997), Game Developer Magazine
- Hougardy, "The Floyd–Warshall algorithm on graphs with negative cycles", Information Processing Letters, 10(8), pp.279~281 (2010)
- H. Cormen, Thomas, "Introduction to Algorithms", pp.646~640 (2001), MIT Press and McGraw-Hill
- 최해원, "센서네트워크에서 최소 전송에너지를 고려한 최적경로 라우팅 프로토콜", 한국차세대컴퓨팅학회 논문지, 5(3), pp.13~19 (2009), 한국차세대컴퓨팅학회
- 장민기, "교통약자의 보행안전을 위한 맞춤형 길안내 시스템", 한국차세대컴퓨팅학회 논문지, 9(5), pp.17~26 (2013), 한국차세대컴퓨팅학회
- 성동수, "평균 경로 거리를 고려한 비점진적 계층 회의 구성 방법", 한국차세대컴퓨팅학회 논문지, 10(5), pp.25~34 (2014), 한국차세대컴퓨팅학회
- J. Rozman, "Grid-Based Map Making Using Particle Filters", Int. J. Autonomic Comput, 1(2), pp.211~221 (2009)
- I. Q. Whishaw, "Dead reckoning (path integration) requires the hippocampal formation: evidence from spontaneous exploration and spatial learning tasks in light (allothetic) and dark (idiothetic) tests", Behavioural Brain Research, 127, pp.49~69 (2001)