Unmanned Aerial Vehicles (UAVs) or drones are increasingly used for urban applications like traffic monitoring and construction surveys. Autonomous navigation allows drones to visit waypoints and accomplish activities as part of their mission. A common activity is to hover and observe a location using on-board cameras. Advances in Deep Neural Networks (DNNs) allow such videos to be analyzed for automated decision making. UAVs also host edge computing capability for on-board inferencing by such DNNs. To this end, for a fleet of drones, we propose a novel Mission Scheduling Problem (MSP) that co-schedules the flight routes to visit and record video at waypoints, and their subsequent on-board edge analytics. The proposed schedule maximizes the utility from the activities while meeting activity deadlines as well as energy and computing constraints. We first prove that MSP is NP-hard and then optimally solve it by formulating a mixed integer linear programming (MILP) problem. Next, we design two efficient heuristic algorithms, JSC and VRC, that provide fast sub-optimal solutions. Evaluation of these three schedulers using real drone traces demonstrate utility-runtime trade-offs under diverse workloads.
翻译:无人驾驶航空飞行器(无人驾驶飞行器)或无人驾驶飞机(无人驾驶飞行器)正越来越多地用于城市应用,如交通监测和建筑调查等。自主导航允许无人驾驶飞机访问中点并完成活动,作为其任务的一部分。一项共同活动是用机载相机盘旋和观察一个地点。深神经网络的进展允许对此类视频进行分析,以便自动决策。无人驾驶飞行器也为此类DNNS的登机推理提供边际计算能力。为此,我们提议为一组无人驾驶飞机设计一个新的任务规划问题(MSP),共同安排飞行路线,在航道点访问并记录视频,随后在机载边缘进行分析。拟议时间表在满足活动最后期限以及能源和计算限制的同时最大限度地利用这些活动的效用。我们首先证明MSP是硬的,然后通过制定混合整数线性编程(MILP)问题来最佳地解决。我们设计了两种高效的超光滑算算算法,即JSC和VRC,以提供快速的亚光度分辨率解决方案。使用实际的无人驾驶飞机跟踪器对这三种时间表进行评估。