Delivery Drones Could Hitchhike on Public Transit to Massively Expand Their Range

Beyond the technical and social issues with drone delivery, there are real questions about whether it would actually be an efficient and cost-effective way of moving stuff around urban environments. A significant problem with delivery drones right now is that they're generally not much use if you want to send something relatively heavy very far away, especially if you want them to also be able to make pinpoint deliveries throughout cities safely. The problem is that drones run on batteries, which substantially limit their range, especially once you load them up with cargo.

One approach to try to offset the low range of delivery drones by flying them from vehicles that can serve as base stations. This idea has been tested by companies like Mercedes-Benz and Matternet, and also by UPS and Workhorse, among others. Now here's another idea: Instead of deploying a fleet of private vans, you could rely on a vast network of vehicles that's already on the road: public buses. In a paper presented at ICRA this month, researchers from Stanford's Intelligent Systems Laboratory and Autonomous Systems Lab have explored how a transit-based delivery drone system might work, and it turns out that it might work really well-in cities like San Francisco and Washington, D.C., hitchhiking on buses could potentially help drones more than quadruple their package delivery range.

The first thing to understand about this paper is that it's not trying to solve any of the practical problems surrounding the real-world deployment of a delivery network involving drones and buses, like how you'd get a drone to land on a moving bus, for instance. What the paper is about is how you'd get a potential network of drones and vehicles to operate efficiently, and how big of a difference that might be able to make in a package delivery context.

Using San Francisco as a model, the system is able to schedule drones in such a way that hopping around on the bus system allows them to make deliveries anywhere in under an hour

In a metropolitan area like San Francisco, the idea is that you'd have a bunch of package depots scattered around the city. You'd also have a bunch of drones, and every day, you'd need to figure out how to get all of those packages where they need to go in the minimum amount of time, using the existing bus routes and schedule to boost their range when necessary. And when I say you," that's where this research comes in, because it's solving a big optimization problem that involves which drones make which deliveries in what order, when they should use buses, and for how long. It gets more complicated too, because there are conflicts that have to be resolved when buses can only carry a few drones at a time and you don't want the drones occupying the same space on the network at the same time. Oh, and don't forget that part of this planning process involves getting the drones back to their depots, too.

When you start considering fleets of hundreds of drones delivering packages to thousands of locations, the computation involved can get demanding, but the solution the researchers came up with runs in just a few minutes on a relatively modest desktop computer. Using San Francisco (150 km²) as a model, the system is able to schedule drones (based loosely on the specs of the DJI Mavic 2) in such a way that hopping around on the bus system allows them to make deliveries anywhere in under an hour. In a larger city with more customers like Washington DC (400 km²), deliveries might take almost two hours, with drones hopping between flight and buses up to eight times on one single route, boosting their range by as much as 450 percent.

Since this is just in simulation, there's obviously lots that would need to be done before it could get anywhere close to being implemented on actual hardware, and we asked lead author Shushman Choudhury a few questions about how practical considerations might change things and what he's working on next. If you have questions of your own, the paper's ICRA website is here.

IEEE Spectrum: What are some ways in which things would get more complicated if you started to look at practical challenges to implementing your system? What real-world effects would you need to account for, both negative (like traffic during rush hour) or positive (like potentially being able to recharge on a bus)?

There are a slew of challenges to deploying this idea in practice, some of which we highlight in the final section of the paper as directions for future work. Not all of those challenges would necessarily be handled by our high-level optimization, e.g. safely controlling a drone to land on a bus. Our collaborators on an NSF grant are looking at other aspects of this problem.

Delays and disruptions to the timetable are challenges that we can potentially account for, and there are ideas from transit planning for human riders that we could adapt; delivery window constraints are another modification that our framework could in principle handle. The potential for recharging on a bus is interesting; now it might make sense to stay longer on a bus than might be suitable if there was no charging available, in order to regain charge. That additional degree of freedom could give us better solutions but it also makes the optimization problem larger.

Can you elaborate on how the differences between San Francisco and D.C. play into delivery network efficiency? Are there ways in which changes to transit networks could make drone delivery based on your system work better?

The difference is a bit difficult to pin down verbally, without visualizations or mathematical metrics, but I'll try. Essentially, for Washington, D.C., we considered a much larger area of operation, and the portion of the WMATA bus network that we considered has less coverage than in San Francisco. That is, there are more geographic locations in the WMATA setting that are further away from the nearest bus stop or that have fewer bus routes that come close enough to them for the drone delivery to even be feasible. For such settings, it is more likely that certain bus routes become bottlenecks, given the finite drone capacity that they have. On the algorithm side, this makes planning the drone routes take longer, in terms of CPU cycles, because more high-level capacity conflicts are generated and need to be resolved. Naturally, it also affects the actual delivery time if a far off location can only be accessed by one or a few long bus routes.

A public transit network could certainly be modified to make our system work better overall, e.g., adding more routes to less well-served areas or a higher frequency of trips along the same route; there would have to be a cost-benefit analysis to determine if it is worth the expense. A related possible direction for future work is to assume the ground transit vehicles can also be freely rerouted (say if they are delivery trucks rather than public buses) and jointly route them as well as the delivery drones.

Your framework currently focuses on minimizing delivery time, but could the algorithm be altered to (for example) maximize energy efficiency, or minimize flight times over residential areas?

Yes, our framework allows us to optimize other objective functions, so long as we can represent the cost metric as a function of a flight path or flight + transit path from one geographic location to another. We can model delivery constraints, i.e., a certain depot cannot deliver to certain locations, transit connection constraints, i.e., certain bus stops are not accessible by a particular drone for whatever reason, and no-fly links as well. Depending on how extensive the constraints or modifications are, there might need to be some adjustments to our algorithm, and some of those are directions for future algorithms research.

Efficient Large-Scale Multi-Drone Delivery Using Transit Networks," by Shushman Choudhury, Kiril Solovey, Mykel J. Kochenderfer, and Marco Pavone from Stanford University, was presented at ICRA 2020. < Back to IEEE Journal Watch