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,以提供快速的亚光度分辨率解决方案。使用实际的无人驾驶飞机跟踪器对这三种时间表进行评估。

0
下载
关闭预览

相关内容

启发式算法(heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。现阶段,启发式算法以仿自然体算法为主,主要有蚁群算法、模拟退火法、神经网络等。
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
专知会员服务
109+阅读 · 2020年3月12日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
人工智能 | ACCV 2020等国际会议信息5条
Call4Papers
6+阅读 · 2019年6月21日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
计算机 | ISMAR 2019等国际会议信息8条
Call4Papers
3+阅读 · 2019年3月5日
TCN v2 + 3Dconv 运动信息
CreateAMind
4+阅读 · 2019年1月8日
计算机类 | 11月截稿会议信息9条
Call4Papers
6+阅读 · 2018年10月14日
人工智能 | ICAPS 2019等国际会议信息3条
Call4Papers
3+阅读 · 2018年9月28日
人工智能 | AAAI 2019等国际会议信息7条
Call4Papers
5+阅读 · 2018年9月3日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年8月6日
VIP会员
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
人工智能 | ACCV 2020等国际会议信息5条
Call4Papers
6+阅读 · 2019年6月21日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
计算机 | ISMAR 2019等国际会议信息8条
Call4Papers
3+阅读 · 2019年3月5日
TCN v2 + 3Dconv 运动信息
CreateAMind
4+阅读 · 2019年1月8日
计算机类 | 11月截稿会议信息9条
Call4Papers
6+阅读 · 2018年10月14日
人工智能 | ICAPS 2019等国际会议信息3条
Call4Papers
3+阅读 · 2018年9月28日
人工智能 | AAAI 2019等国际会议信息7条
Call4Papers
5+阅读 · 2018年9月3日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员