Minimizing maximum cost in task coverage problem with multiple mobile sensors: A heuristic approach based on all-pairs shortest path

We address a task coverage problem to cover all given tasks with a given number of mobile sensors. In this context, we consider tasks as certain points or regions that should be probed by sensors. Our work is to find initial tasks to deploy sensors in advance, and find an efficient set of search paths from the initial tasks that completely covers all tasks and minimizes the maximum cost among paths. This is a challenging issue for various sensor applications, particularly those related to time-critical missions, such as search and rescue operations. We propose an algorithm that selects a set of all-pairs shortest paths with fewer duplicated tasks and extends each path using remaining tasks while covering all tasks and avoiding cost increases. Experimental results demonstrate that the proposed algorithm provides efficient solutions compared to existing algorithms in terms of coverage and maximum path costs.