Discovery of Multiple Patrolling Paths on Road Networks

  • 黃 昊慈

Student thesis: Master's Thesis


The patrolling path planning is an important issue frequently considered in the application of various domains such as police patrolling in urban security epidemic prevention in public health route design for public transportation and automatic robot guardian Given a road network and a set of task points the patrolling problem is to find a set of paths that traveling along the points to achieve the purpose of monitoring or guarding the territory The multiple patrolling paths (MMP) is a generalization of patrolling problems satisfying constraints of path number and length of which the objective is modeling the POI coverage and application- dependent requirement as a submodular function To efficiently deal with the high computational complexity of MMP Problem we pro- pose a solution Multiple Patrolling Path Discovery(MPPD) consisting of two methods to deal with diverse applications with different consideration Candidate-Selection is divided into two phases namely candidate-generation and path-selection In the phase of candidate-generation we implement a couple of heuristic methods for generating optimal path candidates by adopt- ing several classical shortest path algorithms Using paths generated in the previous phase as candidates we use a Greedy algorithm to select paths By introducing CELF optimization we accelerate the process of path-selection with the guarantee of performance owing to the property of submodularity Utilizing the Expectation-Maximization (EM) Algorithm Seed- Expansion addresses the problem by identifying the optimal seeds for path expansion While Candidate-Selection provides the solution with higher revenue along with execution time Seed- Expansion efficiently generates a path set maintaining in a certain level of quality
Date of Award2018 Aug 9
Original languageEnglish
SupervisorKun-Ta Chuang (Supervisor)

Cite this