퍼셉트론 학습을 이용한 다기준 보행자 길찾기 알고리즘의 개발
Development of a Multi-criteria Pedestrian Pathfinding Algorithm by Perceptron Learning
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Pathfinding for pedestrians provided by various navigation programs is based on a shortest path search algorithm. There is no big difference in their guide results, which makes the path quality more important. Multiple criteria should be included in the search cost to calculate the path quality, which is called a multi-criteria pathfinding. In this paper we propose a user adaptive pathfinding algorithm in which the cost function for a multi-criteria pathfinding is defined as a weighted sum of multiple criteria and the weights are learned automatically by Perceptron learning. Weight learning is implemented in two ways: short-term weight learning that reflects weight changes in real time as the user moves and long-term weight learning that updates the weights by the average value of the entire path after completing the movement. We use the weight update method with momentum for long-term weight learning, so that learning speed is improved and the learned weight can be stabilized. The proposed method is implemented as an app and is applied to various movement situations. The results show that customized pathfinding based on user preference can be obtained.
Abstract
Pathfinding for pedestrians provided by various navigation programs is based on a shortest path search algorithm. There is no big difference in their guide results, which makes the path quality more important. Multiple criteria should be included in the search cost to calculate the path quality, which is called a multi-criteria pathfinding. In this paper we propose a user adaptive pathfinding algorithm in which the cost function for a multi-criteria pathfinding is defined as a weighted sum of multiple criteria and the weights are learned automatically by Perceptron learning. Weight learning is implemented in two ways: short-term weight learning that reflects weight changes in real time as the user moves and long-term weight learning that updates the weights by the average value of the entire path after completing the movement. We use the weight update method with momentum for long-term weight learning, so that learning speed is improved and the learned weight can be stabilized. The proposed method is implemented as an app and is applied to various movement situations. The results show that customized pathfinding based on user preference can be obtained.
참고문헌 (14)
- S. Roy, "Analysis of the momentum LMS algorithm", IEEE transactions on acoustics, speech, and signal processing, 38(12), pp.2088~2098 (1990)
- "Pedestrian Navigation"[URL]
- "Seoul City Open Data"[URL]
- "SK Planet Developers"[URL]
- F. B. Zhan, "Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures", Journal of Geographic Information and Decision Analysis, 1(1), pp.69~82 (1998)
- D. Ostrowski, "Comparative Analysis of the Algorithms for Pathfinding in GPS Systems", ICN 2015 : The Fourteenth International Conference on Networks, pp.102~108 (2015)
- H. Antikainen, "Using the Hierarchical Pathfinding A* Algorithm in GIS to Find Paths through Rasters with Nonuniform Traversal Cost", International Journal of Geo-Information, pp.996~1014 (2013)
- T. Miksa, "Comparison of heuristic methods applied to optimization of computer networks", Proc. of 11th International Conference on Networks,IARIA, pp.34~38 (2012)
- A. Botea, "Ultra-Fast Optimal Pathfinding without Runtime Search", Proceedings of the Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, pp.122~127 (2011)
- A. R. Soltani, "A multicriteria based path finding application for construction site layouts", Proceedings of Sixth International Conference on Information Visualization, pp.779~784 (2002)
- P. Pahlavani, "Multi-criteria route planning based on a driver’s preferences in multi-criteria route selection", Transportation Research Part C, 40, pp.14~35 (2014)
- A. Simeon, "Towards Realistic Pedestrian Route Planning", OASIcs-OpenAccess Series in Informatics, 48, pp.1~15 (2015), Schloss Dagstuhl Leibniz Zentrum fuer Informatik
- A. U. Kemloh Wagoum, "Modelling dynamic route choice of pedestrians to assess the criticality of building evacuation", Advances in Complex Systems, 15(7) (2012)