无人机
卡车
计算机科学
布线(电子设计自动化)
僵局
运输工程
运筹学
计算机网络
工程类
遗传学
政治
法学
政治学
生物
航空航天工程
作者
Shushman Choudhury,Kiril Solovey,Mykel J. Kochenderfer,Marco Pavone
出处
期刊:Cornell University - arXiv
日期:2021-01-01
被引量:3
标识
DOI:10.48550/arxiv.2110.08802
摘要
We address the problem of routing a team of drones and trucks over large-scale urban road networks. To conserve their limited flight energy, drones can use trucks as temporary modes of transit en route to their own destinations. Such coordination can yield significant savings in total vehicle distance traveled, i.e., truck travel distance and drone flight distance, compared to operating drones and trucks independently. But it comes at the potentially prohibitive computational cost of deciding which trucks and drones should coordinate and when and where it is most beneficial to do so. We tackle this fundamental trade-off by decoupling our overall intractable problem into tractable sub-problems that we solve stage-wise. The first stage solves only for trucks, by computing paths that make them more likely to be useful transit options for drones. The second stage solves only for drones, by routing them over a composite of the road network and the transit network defined by truck paths from the first stage. We design a comprehensive algorithmic framework that frames each stage as a multi-agent path-finding problem and implement two distinct methods for solving them. We evaluate our approach on extensive simulations with up to $100$ agents on the real-world Manhattan road network containing nearly $4500$ vertices and $10000$ edges. Our framework saves on more than $50\%$ of vehicle distance traveled compared to independently solving for trucks and drones, and computes solutions for all settings within $5$ minutes on commodity hardware.
科研通智能强力驱动
Strongly Powered by AbleSci AI