Foundations of Software Science and Computation Structures - 18th International Conference, FOSSACS 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015, Proceedings
Foundations of Software Science and Computation Structures - 18th International Conference, FOSSACS 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015, Proceedings
复制标题
软件科学与计算结构基础 - 第 18 届国际会议，FOSSACS 2015，作为欧洲软件理论与实践联合会议的一部分举行，ETAPS 2015，英国伦敦，2015 年 4 月 11-18 日，会议记录
DOI：
10.1007/978-3-662-46678-0_21
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Ho H
中科院分区：
文献类型：
--
作者：
Ho H
考虑一组有限的目标，每个目标都分配了相对的截止日期，并且每对目标都分配了固定的飞行时间。给定一群相同的无人机，能否确保某些无人机在最多目标相对截止日期的持续时间间隔内重复访问每个目标？循环路由无人机问题（cr-uav）是这个任务是否有解决方案的问题。这个问题可以在 PSPACE 中通过将其建模为时间自动机网络来直接解决。文献中声称存在单个无人机的特殊情况是 NP 完全的。在本文中，我们证明即使在单无人机情况下，cr-uav 问题实际上也是 PSPACE 完全的。
Consider a finite set of targets, with each target assigned arelative deadline, and each pair of targets assigned a fixed transitflight time. Given a flock of identical UAVs, can one ensure that every target is repeatedly visited by some UAV at intervals of duration at most the target’s relative deadline? TheCyclic-Routing UAV Problem(cr-uav)is the question of whether this task has a solution.This problem can straightforwardly be solved in PSPACE by modelling it as a network of timed automata. The special case of there being a single UAV is claimed to be NP-complete in the literature. In this paper, we show that thecr-uavProblem is in fact PSPACE-complete even in the single-UAV case.