Cyclic-routing of Unmanned Aerial Vehicles
Cyclic-routing of Unmanned Aerial Vehicles
复制标题
无人机的循环路由
DOI：
10.1016/j.jcss.2019.02.002
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
O. Strichman
中科院分区：
文献类型：
--
作者：
Nir Drucker;M. Penn;O. Strichman
无人机（UAV）执行的各种任务都涉及在相对时限约束下对预定义的一组地面目标进行永久监视，即，目标必须被“无限期地”重新访问，并且在每个目标的两次连续成功扫描之间的时间上存在上限。问题的解决方案是一组路线-每个无人机一个-共同满足这些约束。我们的目标是找到一个使用最少无人机的解决方案。我们表明，决策版本的问题（givenk，是否有一个解决方案与无人机？）是PSPACE完整的。在实践方面，我们提出了一个组合的方法，结合约束求解和模型检查的优势。我们提出了一个经验评估的不同的解决方案的方法上的几百个随机生成的实例。
Various missions carried out by Unmanned Aerial Vehicles (UAVs) are concerned with permanent monitoring of a predefined set of ground targets underrelative deadlineconstraints, i.e., the targets have to be revisited ‘indefinitely’ and there is an upper bound on the time between two consecutive successful scans of each target. Asolutionto the problem is a set of routes—one for each UAV—that jointly satisfy these constraints. Our goal is to find a solution with the least number of UAVs. We show that the decision version of the problem (givenk, is there a solution withkUAVs?) is PSPACE-complete. On the practical side, we propose a portfolio approach that combines the strengths of constraint solving and model checking. We present an empirical evaluation of the different solution methods on several hundred randomly generated instances.