The cyclic-routing UAV problem is PSPACE-complete

DOI10.1007/978-3-662-46678-0_21MaRDI QIDQ2949448zbMATH OpenOpenAlexFDO

Authors Hsi-Ming Ho, Joël Ouaknine

Publication date 1 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.2874, http://shura.shu.ac.uk/25239/8/Ho_Cycling-RoutingUAVProblem%28AM%29.pdf

zbMATH Keywords

unmanned air vehicles

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Abstract: Consider a finite set of targets, with each target assigned a relative deadline, and each pair of targets assigned a fixed transit flight 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? The Cyclic-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 the CR-UAV Problem is in fact PSPACE-complete even in the single-UAV case.

Recommendations

• Cyclic-routing of unmanned aerial vehicles
• Cyclic routing of unmanned aerial vehicles
• Real-time optimal time-critical target assignment for UAVs
• Length-constrained cycle partition with an application to UAV routing*
• Single-task tours

Cited in

(4)

• Cyclic-routing of unmanned aerial vehicles
• Optimization for drone and drone-truck combined operations: a review of the state of the art and future directions
• Cyclic routing of unmanned aerial vehicles
• Length-constrained cycle partition with an application to UAV routing*

This page was built for publication: The cyclic-routing UAV problem is PSPACE-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2949448)