在城市環境中，於街道密集分布的監視器經常成為搜尋失蹤者和偵破案件的重要證據，同一距離下的兩條路段，擁有較多監視器覆蓋的路段理應將比另一條路段有更高的可能性留存證據，使得行走於該路段的安全性更佳。基於以上想法，本研究提出了一個注重監視器分布的路徑規劃系統，通過利用現有的監視器位置資料和道路網絡資料，定義尋路時會計算的監視器點位，使用改進過的A-star演算法搜尋路徑。其結果將會偏向選擇監視器覆蓋較多且有效率的路徑而不是最短的路徑。本研究在台北市的實際資料集上進行了實驗，結果顯示本研究的方法能夠有效地生成符合用戶需求的安全路徑。

In urban environments, surveillance cameras densely distributed on streets often become important evidence for searching for missing persons and solving cases. Under the same distance, a road section covered by more surveillance cameras should have a higher probability of retaining evidence than another road section, making it safer to walk on that road section. Based on the above idea, this study proposes a path planning system that focuses on the distribution of surveillance cameras. By using existing surveillance camera location data and road network data, it defines the surveillance camera points that will be calculated during pathfinding, and uses an improved A-star algorithm to search for paths. The result will tend to choose a path covered by more surveillance cameras and efficient rather than the shortest path. This study conducted experiments on actual data sets in Taipei City, and the results showed that the method of this study can effectively generate safe paths that meet user needs.

目錄	III
圖目錄	IV
表目錄	V
第一章 緒論	1
1.1研究背景與動機	1
1.2研究目的	2
第二章 文獻探討	3
2.1 Dijkstra algorithm	3
2.2 A* search algorithm	4
2.3 Ant colony optimization	5
2.4 Silhouette analysis and K-means	7
2.5 相關研究	8
第三章 研究方法	11
3.1 收集監視器位置資料	12
3.2 界定搜尋範圍	13
3.3 分群計算	13
3.4 製作監視器點位有向圖	14
3.5 進行尋路	14
第四章 實驗結果	16
4.1研究平台及實驗條件	16
4.2 實驗結果	16
第5章 結論與未來研究方向	32
5.1 結論	32
5.2 未來研究方向	32
參考文獻	34
圖目錄
圖一、螞蟻群集覓食習性示意圖	5
圖二、本研究的流程圖	11
圖三、搜尋範圍範例	13
圖四、有向圖規則示意	14
圖五、本研究於台北市區域進行尋路的實驗結果	17
圖六、本研究於台北市區域進行尋路的實驗結果	19
圖七、本研究於台北市區域進行尋路的實驗結果	21
圖八、本研究於台北市區域進行尋路的實驗結果	22
圖九、本研究於台北市區域進行尋路的實驗結果	24
圖十、本研究於台北市區域進行尋路的實驗結果	26
圖十一、本研究於台北市區域進行尋路的實驗結果	28
圖十二、本研究於台北市區域進行尋路的實驗結果	30
表目錄
表一、資料樣本及欄位	12
表二、實驗結果圖五之數據	18
表三、實驗結果圖六之數據	20
表四、實驗結果圖七之數據	21
表五、實驗結果圖八之數據	23
表六、實驗結果圖九之數據	25
表七、實驗結果圖十之數據	27
表八、實驗結果圖十一之數據	29
表九、實驗結果圖十二之數據	31

Edsger Wybe Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, pp. 269-271, 1959. 
Huijuan Wang, Yuan Yu, Quanbo Yuan, “Application of Dijkstra algorithm in robot path-planning,” 2011 Second International Conference on Mechanic Automation and Control Engineering, Hohhot, 2011, pp. 1067-1069. 
Zhenyu Zhu, Lianbo Li, Wenhao Wu, Yang Jiao, “Application of improved Dijkstra algorithm in intelligent ship path planning,” 2021 33rd Chinese Control and Decision Conference, Kunming, China, 2021, pp. 4926-4931. 
Li-sang Liu, Jia-feng Lin, Jin-xin Yao, Dong-wei He, Ji-shi Zheng, Jing Huang, Peng Shi, “Path Planning for Smart Car Based on Dijkstra Algorithm and Dynamic Window Approach,” Wireless Communications and Mobile Computing, vol. 2021, 12 pages, 2021. 
Said Broumi, Assia Bakal, Mohamed Talea, Florentin Smarandache, Luige Vladareanu, “Applying Dijkstra algorithm for solving neutrosophic shortest path problem,” 2016 International Conference on Advanced Mechatronic Systems, Melbourne, VIC, Australia, 2016, pp. 412-416. 
Peter E. Hart, Nils J. Nilsson, Bertram Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, 1968. 
Guangzhong Dong, Fangfang Yang, Kwok-Leung Tsui, Changfu Zou, “Active Balancing of Lithium-Ion Batteries Using Graph Theory and A-Star Search Algorithm,” IEEE Transactions on Industrial Informatics, vol. 17, no. 4, pp. 2587-2599, 2021. 
Saeid Sedighi, Duong-Van Nguyen, Klaus-Dieter Kuhnert, “Guided Hybrid A-star Path Planning Algorithm for Valet Parking Applications,” 2019 5th International Conference on Control, Automation and Robotics, Beijing, China, 2019, pp. 570-575. 
Imad S. AlShawi, Lianshan Yan, Wei Pan, Bin Luo, “Lifetime Enhancement in Wireless Sensor Networks Using Fuzzy Approach and A-Star Algorithm,” IEEE Sensors Journal, vol. 12, no. 10, pp. 3010-3018, 2012.
Tao Zheng, Yanqiang Xu, Da Zheng, “AGV Path Planning based on Improved A-star Algorithm,” 2019 IEEE 3rd Advanced Information Management, Communicates, Electronic and Automation Control Conference, Chongqing, China, 2019, pp. 1534-1538.
Marco Dorigo, Vittorio Maniezzo, Alberto Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29-41, 1996. 
Marco Dorigo, Mauro Birattari, Thomas Stutzle, “Ant colony optimization,” IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, 2006.
Marco Dorigo, Luca M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, 1997.
Peter J. Rousseeuw, “Silhouettes: A graphical aid to the interpretation and validation of cluster analysis,” Journal of Computational and Applied Mathematics, vol. 20, pp. 53-65, 1987.
Panote Siriaraya et al., “Beyond the Shortest Route: A Survey on Quality-Aware Route Navigation for Pedestrians,” IEEE Access, vol. 8, pp. 135569-135590, 2020.
Cristina Olaverri Monreal, Matthias Pichler, Gerd Krizek, Sebastian Naumann, “Shadow as Route Quality Parameter in a Pedestrian-Tailored Mobile Application,” IEEE Intelligent Transportation Systems Magazine, vol. 8, no. 4, pp. 15-27, 2016.
“OpenStreetMap Foundation,” https://osmfoundation.org/.
“How To Get OpenStreetMap Data,” https://osmfoundation.org/wiki/How_To_Get_OpenStreetMap_Data.
Deilami, Kaveh, Julie Rudner, Andrew Butt, Tania MacLeod, Geoff Williams, Harmen Romeijn, and Marco Amati, “Allowing Users to Benefit from Tree Shading: Using a Smartphone App to Allow Adaptive Route Planning during Extreme Heat,” Forests, vol. 11, no. 9: 998, 2020.
Adam D. Sobek, Harvey J. Miller, “U-Access: a web-based system for routing pedestrians of differing abilities,” Journal of Geographical Systems, vol. 8,  pp. 269-287, 2006.
Achituv Cohen, Sagi Dalyot, “Route planning for blind pedestrians using OpenStreetMap,” Environment and Planning B: Urban Analytics and City Science, vol. 48, no. 6, pp. 1511-1526, 2021.
Alexandra Millonig, Katja Schechtner, “Developing Landmark-Based Pedestrian-Navigation Systems,” IEEE Transactions on Intelligent Transportation Systems, vol. 8, no. 1, pp. 43-49, 2007.
Lauri Sintonen et al., “OSRM-CCTV: CCTV-aware routing and navigation system for privacy and safety,” Business Modeling and Software Design: 12th International Symposium, Fribourg, Switzerland, 2022.
Limao Zhang, Mengjie Liu, Xianguo Wu, Simaan M. AbouRizk, “Simulation-based route planning for pedestrian evacuation in metro stations: A case study,” Automation in Construction, vol. 71, no. 2, pp. 430-442, 2016.
Samuel Elsmore, Irwan Fario Subastian, Flora Dilys Salim, Margaret Hamilton, “VDIM: Vector-based Diffusion and Interpolation Matrix for Computing Region-based Crowdsourced Ratings Towards Safe Route Selection for Human Navigation,” 13th International Conference on Mobile and Ubiquitous Multimedia, Melbourne, Australia, 2014.
Tessio Novack, Zhiyong Wang, Alexander Zipf, “A System for Generating Customized Pleasant Pedestrian Routes Based on OpenStreetMap Data,” Sensors, vol. 2018, no. 11: 3794, 2018.
Damianos Gavalas, Vlasios Kasapakis, Charalampos Konstantopoulos, Grammati Pantziou, Nikolaos Vathis, “Scenic route planning for tourists,” Personal and Ubiquitous Computing, vol. 21, pp. 137-155, 2017. 
Zhe Zhang, Ju Jiang, Jian Wu, Xiaozhou Zhu, “Efficient and optimal penetration path planning for stealth unmanned aerial vehicle using minimal radar cross-section tactics and modified A-Star algorithm,” ISA Transactions, vol. 134, pp. 42-57, 2023.
Gang Tang, Congqiang Tang, Christophe Claramunt, Xiong Hu, Peipei Zhou, “Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment,” IEEE Access, vol. 9, pp. 59196-59210, 2021.
Narayan Kumar, Amit Kumar, “An Optimized Path Selection Algorithm for the Minimum Number of Turns in Path Planning Using a Modified A-Star Algorithm,” International Conference on Innovative Computing and Communications, Singapore, 2023.
“台北市政府警察局錄影監視系統設置地點,” https://cctv.police.gov.taipei/News.aspx?n=52DDBB5D1E50AF72&sms=94AC2E5C069CB36A.
“Google 地圖平台說明文件,” https://developers.google.com/maps/documentation?hl=zh-tw.
“aco-routing 1.0.6,” https://pypi.org/project/aco-routing/.