Incentive Mechanism and Path Planning for Uav Hitching Over Traffic Networks

Ziyi Lu, Na Yu, Xuehe Wang

TL;DR

This paper proposes a novel multimodal logistics framework where drones (UAVs) "hitchhike" on ground vehicles to overcome their inherent battery and range limitations. By combining a dynamic pricing incentive for crowdsourced drivers with a two-layer path-planning algorithm, the system significantly extends delivery range and achieves a 325% increase in delivery success rates compared to traditional direct-flight methods.

What Problem Does This Paper Address?

While Unmanned Aerial Vehicles (UAVs) offer a fast, "green," and agile solution for urban logistics, they are severely hampered by limited energy capacity. Most commercial drones can only handle short-distance deliveries before needing a recharge.

Existing solutions often suggest using public transit (like buses), but these are restricted by fixed schedules and routes. Crowdsourcing—inviting private ground vehicles to carry drones—offers more flexibility but introduces two major hurdles:

  1. Incentives: Why would a driver go out of their way to carry a drone? Drivers have private costs (fuel, time) and need a fair, dynamic reward system.
  2. Complexity: Planning a path that involves hopping between moving vehicles while avoiding mid-air or landing-zone conflicts between multiple drones is a computationally "NP-hard" nightmare.

Methods

The authors tackle these challenges using a two-stage model:

Stage I: The Incentive Mechanism

To motivate ground vehicles, the researchers designed a dynamic pricing scheme. Using dynamic programming, the system calculates an optimal reward based on traffic density and the driver's private costs.

  • The Logic: If the drone has been waiting a long time (high response time), the system automatically increases the price to attract more drivers.
  • Steady State: They prove that the price eventually converges to a "steady state" that balances the platform's payout with the drone's waiting time.

Stage II: Two-Layer Path Planning

Once the "waiting times" at various interchange points are predicted from Stage I, the system plans the actual delivery.

  • Layer 1 (Task Allocation): This layer decides which drone delivers which package and in what order. The authors treat this as a variation of the Traveling Salesman Problem but simplify it into a Minimum Cost Circulation (MCC) problem to ensure it can be solved quickly (polynomial time).
  • Layer 2 (Pathfinding): They introduce the Conflict Avoidance-Based Path Search (CABPS) algorithm. Unlike standard algorithms that might crash when too many drones are in the air, CABPS uses a "near-optimal" approach. It plans paths successively and treats previously planned paths as "occupied" time-stamped intervals at interchange points, effectively preventing collisions without the massive computational overhead of global optimization.

Datasets

The paper evaluates the model using simulated traffic networks based on real-world scenarios.

  • Network Scale: A fixed network graph ($G_T$) with 846 nodes.
  • Parameters: They varied the number of depots ($K=1$ to $30$), packages ($M=10$ to $600$), and drones ($N=1$ to $30$) to test scalability.
  • Benchmarks: The authors compared their "multi-hop hitching" approach against "direct flight" and "single-hop hitching" (carrying the drone only once).

Key Insights and Ideas

  • Hitching as a Range Extender: The most significant "aha" moment is that by treating ground vehicles as mobile energy-saving platforms, drones can complete tasks that would be physically impossible via direct flight.
  • The Price of Waiting: The paper mathematically demonstrates that a higher monetary reward directly correlates to shorter "vehicle response times," which is the primary bottleneck in crowdsourced logistics.
  • Polynomial Efficiency: By decomposing the problem into two layers and using suboptimal (but "bounded") algorithms, the authors turned a problem that usually takes exponential time into one that can be solved in seconds, even with hundreds of packages.
  • Pessimistic Speed: Even in a "pessimistic case" (long wait times), the multimodal system is still twice as fast as using ground vehicles alone for delivery.

Key Results

  • Success Rate: The multi-hop hitching network reached a 0% failure rate as the number of available transit edges increased, whereas direct flight failed ~70% of the time due to battery exhaustion.
  • Delivery Range: The success rate of UAV package delivery increased by 325% in experimental trials.
  • Computation Speed: For a complex scenario with 600 packages and 20 depots, the task allocation took only ~6 seconds, proving the system is viable for real-time logistics.
  • Conflict Reduction: As the capacity of interchange points (how many drones can land at once) increases, total delivery time drops significantly due to fewer "waiting-for-clearance" delays.

Limitations and Future Work

  • Simplified Energy Model: The paper ignores the time required to charge or swap batteries at depots, which is a significant factor in real-world operations.
  • Traffic Assumptions: The pricing model assumes a "non-trivial traffic density." In rural areas with very few cars, the incentive mechanism might struggle to find a carrier regardless of the price.
  • Interchange Point Constraints: The current model assumes drones can only hitch/unhitch at specific "interchange points" equipped with cameras. Future work could explore more flexible "on-the-fly" docking.
  • Communication: The study assumes perfect communication between the platform, drones, and vehicles; real-world latency or signal loss in "urban canyons" wasn't modeled.

Summary updated

Abstract

Package delivery via the UAVs is a promising transport mode to provide efficient and green logistic services, especially in urban areas or complicated topography. However, the energy storage limit of the UAV makes it difficult to perform long-distance delivery tasks. In this paper, we propose a novel multimodal logistics framework, in which the UAVs can call on ground vehicles to provide hitch services to save their own energy and extend their delivery distance. This multimodal logistics framework is formulated as a two-stage model to jointly consider the incentive mechanism design for ground vehicles and path planning for UAVs. In Stage I, to deal with the motivations for ground vehicles to assist UAV delivery, a dynamic pricing scheme is proposed to best balance the vehicle response time and payments to ground vehicles. It shows that a higher price should be decided if the vehicle response time is long to encourage more vehicles to offer a ride. In Stage II, the task allocation and path planning of the UAVs over traffic network is studied based on the vehicle response time obtained in Stage I. To address pathfinding with restrictions and the performance degradation of the pathfinding algorithm due to the rising number of conflicts in multi-agent pathfinding, we propose the suboptimal conflict avoidance-based path search (CABPS) algorithm, which has polynomial time complexity. Finally, we validate our results via simulations. It is shown that our approach is able to increase the success rate of UAV package delivery. Moreover, we estimate the delivery time of the UAV in a pessimistic case, it is still twice as fast as the delivery time of the ground vehicle only.
BibTeX
@misc{lu2022incentive,
  author = {Ziyi Lu and Na Yu and Xuehe Wang},
  title = {{Incentive Mechanism and Path Planning for Uav Hitching Over Traffic Networks}},
  year = {2022},
  eprint = {2210.00490},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.00490},
}

Loading related content...

Figure