1 Incentive Mechanism and Path Planning for UA V Hitching over Trafﬁc Networks

2025-04-28 0 0 806.02KB 14 页 10玖币

侵权投诉

Incentive Mechanism and Path Planning for UAV

Hitching over Trafﬁc Networks

Ziyi Lu, Na Yu and Xuehe Wang, Member, IEEE

Abstract—Package delivery via the UAVs is a promising

transport mode to provide efﬁcient and green logistic services,

especially in urban areas or complicated topography. However,

the energy storage limit of the UAV makes it difﬁcult 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 trafﬁc network is studied based

on the vehicle response time obtained in Stage I. To address

pathﬁnding with restrictions and the performance degradation of

the pathﬁnding algorithm due to the rising number of conﬂicts

in multi-agent pathﬁnding, we propose the suboptimal conﬂict

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.

Index Terms—Crowdsourcing, UAV hitching, Minimal-

connecting tours, Conﬂict avoidance.

I. INTRODUCTION

A. Background

In recent years, the continuous expansion of the e-commerce

market has promoted the rapid development of the express

logistics industry [1]. Especially during the epidemic, people’s

living habits have changed dramatically in order to maintain

social distance. New logistics service models have emerged in

order to avoid face-to-face contact, such as non-contact deliv-

ery [2]. However, the rapid development of urban logistics has

also brought a series of problems, such as trafﬁc congestion,

air pollution, low logistics efﬁciency [3]. Due to its agility

and mobility, the delivery services enabled by the Unmanned

Aerial Vehicle (UAV) are not restricted by terrain and trafﬁc

conditions, which can freely pass through urban region during

rush hours to provide logistics services ﬂexibly and efﬁciently.

Many companies all over the world have launched commercial

UAV delivery services, such as Amazon, Google, and UPS

Z. Lu, N. Yu and X. Wang (corresponding author) are with the School

of Artiﬁcial Intelligence, Sun Yat-sen University, Zhuhai 519082, China

(E-mail: Luzy6@mail2.sysu.edu.cn, yuna25@mail2.sysu.edu.cn, wangx-

uehe@mail.sysu.edu.cn). X. Wang is also with the Guangdong Key Laboratory

of Big Data Analysis and Processing, Guangzhou 510006, China.

in the United States, DHL in Germany, and JD, SF-express

in China [4]. However, due to the limitation of UAV energy

capacity, current UAV logistics services are limited to short-

distance delivery [5]. Therefore, how to expand the range of

UAV delivery services is an urgent problem to be solved.

With the development of new technologies such as 5G,

Internet of Things (IoT), and Artiﬁcial Intelligence (AI),

crowdsourcing, as a mode of using large-scale network users

to assist in speciﬁc tasks, has received more and more attention

from different application platforms, and has been widely

used in various scenarios, such as food delivery riders, car

sharing, and data cleaning, etc [6]. Inspired by the crowd-

sourcing model, the ground vehicles such as trucks can be

utilized to offer riding for the UAVs, which greatly saves

the battery consumption of UAVs and extend their delivery

distance. Amazon has proposed a UAV-truck riding strategy to

allow UAVs to land on transportation vehicles from different

shipping companies for temporary transport, by making an

agreement with the owner of the transportation vehicles [7].

In addition, the technology of docking UAVs on stationary

or high-speed moving vehicles is relatively mature [8], [9],

which lays the foundation for the development of air-ground

collaborative multimodal logistics system.

However, this new multimodal logistics system based on

crowdsourcing faces the following challenges:

•Incentives for ground vehicles’ cooperation. The provi-

sion of hitch services by ground vehicles is the basis

for the implementation of multimodal logistics systems.

However, the ground vehicles incur hitching costs (e.g.,

fuel consumption) when offer riding service, and they

should be rewarded and well motivated to assist UAV

delivery. Moreover, the ground vehicles are heteroge-

neous in nature. They will randomly arrive the targeting

interchange point and their private costs for offering

riding service are different and unknown. Thus, the

pricing design under the incomplete vehicle information

is challenging. In addition, a higher monetary reward

leads to a shorter vehicle response time (i.e., UAV

waiting time), which improves the delivery efﬁciency of

multimodal logistics system. For sustainable management

of the multimodal logistics system, the pricing strategy

should be dynamic to best balance the payment to ground

vehicles and their response time.

•Crowdsourcing-based multimodal logistics system model-

ing under time-varying trafﬁc networks and UAV energy

constraint. By integrating the UAVs with the ground

vehicles, the UAVs should decide where to hitch on

ground vehicles and whether hopping between different

arXiv:2210.00490v1 [eess.SY] 2 Oct 2022

vehicles to complete one delivery task, which creates

large number of interchange points on the basis of the

road network for path planning. Moreover, due to the

mobility of ground vehicles and the instability of trafﬁc

conditions, the modeling of the integrated system is

challenging.

•Design of fast and efﬁcient task allocation and path

planning algorithms for the multimodal logistics system.

The ground vehicles’ arrivals and response time in the

vicinity of the UAVs at a certain time are unknown.

In addition, the path planning of the UAVs should be

carefully designed to prevent conﬂicts between UAVs,

such as multiple UAVs landing at the same vehicle at the

same time. Such combinatorial optimization problems are

often NP-hard problems and challenging to solve.

B. Main Contributions

To tackle the above challenges, a two-stage model is pro-

posed to jointly analyze the incentive mechanism design for

ground vehicles and path planning for UAVs. We summarize

our main contributions as follows:

•Crowdsourcing-based multimodal logistics system mod-

eling. To our best knowledge, this paper is the ﬁrst work

studying the crowdsourcing-based multimodal logistics

system, in which the ground vehicles are invited to offer

hitching services for UAVs. Such multimodal logistics

system effectively extends the range and efﬁciency of

UAV deliveries. We formulate this system as a two-

stage model to jointly study the incentive mechanism

design for ground vehicles and path ﬁnding for UAVs.

In Stage I, a dynamic pricing scheme is proposed to

motivate the ground vehicles to assist UAV delivery under

the incomplete information about the ground vehicles’

random arrivals and private hitching costs. In Stage II,

the task allocation and path planning of the UAVs over

trafﬁc network by considering the UAV energy constraint

and the conﬂicts between UAVs.

•Dynamic pricing for ground vehicle under incomplete

information. To balance the payment to ground vehicles

and their response time for efﬁcient delivery, a optimal

dynamic pricing scheme is proposed under incomplete

information case regarding ground vehicles’ random ar-

rivals and private hitching costs. We prove that if the

vehicle response time is long, a high price offer should

be decided to encourage the ground vehicles to assist

delivery. According to the proposed dynamic pricing, the

vehicle response time for each interchange station can be

predicted and utilized for the path planning in Stage II.

•Algorithm Design for fast and efﬁcient task allocation and

path planning. To reduce the computation complexity,

the deployment of UAV delivery tasks is split into two

layers. In task allocation layer, we propose a near-optimal

algorithm with polynomial computation complexity to

generate the delivery sequence. In path planning layer,

to avoid the computational burden due to the order-of-

magnitude increase in conﬂicts, we propose a conﬂict

avoidance-based path search algorithm and prove that the

bounded suboptimal paths for all UAVs can be obtained

in polynomial time.

C. Related work

The access path planning problem for UAVs can be viewed

as the Traveling Salesman Problem (TSP) [10], [11]. This type

of combinatorial optimization problem is a classical NP-hard

problem. Once the order of package delivery for all UAVs is

found, the system begins to ﬁnd the optimal delivery path for

each UAV. Classical algorithms such as A∗or Dijkstra for

solving the shortest path are often used to solve the optimal

UAV trajectory problem [12], [13]. In addition, control theory

is also utilized for modeling and solving UAV path planning

problems [14], [15]. The constraints of UAV energy storage

and conﬂicts between UAVs make the UAV path planning

problem more challenging, which is NP-hard to get the optimal

solution. Some methods such as Conﬂict-based search (CBS)

[16], have been shown to be efﬁcient methods to solve this

Multi-Agent Path Finding (MAPF) problem.

Utilizing the ground vehicles to extend the UAVs’ delivery

range has attracted wide attentions from both academia and

industry. The researchers in Stanford University have shown

that combining UAVs with the existing transit network can

increase the delivery coverage of UAVs by up to 360% [17].

However, using buses for UAV delivery lacks fault tolerance.

For example, the bus schedules may not be accurate. If the

UAV happens to miss the arrival time of the current bus, the

UAV needs to wait longer for the next bus to arrive, or has to

change its route, which may cause the delivery task to fail. In

the crowdsourcing-based system considered in this paper, the

request is sent to the ground vehicle at the time when the UAV

needs the hitching service and any passing-by ground vehicle

along the UAV’s routes can be the UAV carrier, so there is

no case of missing a vehicle. E-commerce giant Amazon has

proposed in its patent that commercial vans from different

operators can be used to assist UAVs in delivery services [7].

However, this is also based on the pre-signed agreement with

the van operators. The number of available commercial vans

is limited and cannot cover the entire transportation network,

which will greatly reduce the efﬁciency of UAV delivery. In

this paper, the ground vehicles (such as trucks, buses) with

wide coverage are added to the logistics network based on

crowdsourcing technology, which helps keep the waiting time

for UAVs to a minimum.

The rest of this paper is organized as follows. The system

model is given in Section II, in which the multimodal logistics

system is formulated as two stages. In Section III, the incentive

mechanism for the crowdsourcing-based hitching services is

designed in Stage I. Sections IV and V discuss the task

allocation and multi-agent path ﬁnding for the UAVs in Stage

II. Section VI validates our results via simulations. Section

VII concludes this paper.

II. SYSTEM MODEL

In this paper, we aim to solve the UAV’s limited ﬂight

range problem caused by its energy constraint in the process

of delivery. We propose an efﬁcient multimodal logistics

Package Destination

Depot

…

UAV

Motivation For Ground Vehicle

Vehicle Response Time

Delivery Task Allocation Each UAV Path Finding

Vehicle

Each subtask

STAGE IIncentives for crowdsourcing

STAGE II Path planning for UAV

Layer 1Layer 2

Fig. 1. Two-stages multimodal logistics system: In stage I, the incentive

mechanism for the crowdsourcing-based hitching services is designed, and

the expected vehicle response time is predicted for the following path ﬁnding

algorithm design. In stage II, the path planning problem is decomposed into

two layers: ﬁrst assign delivery tasks to all UAVs in Layer 1, and then ﬁnd

the shortest time-consuming path for each UAV on the basis of the vehicle

response time in Layer 2. In the UAVs path ﬁnding section, we use the solid

point to represent the interchange point, the dotted line to represent the ﬂight

route of UAVs and the solid line to represent the transit route of UAVs.

system to improve the delivery range of UAVs, in which

a crowdsourcing mechanism is implemented by inviting the

ground vehicles (trucks, buses, etc.) to offer the hitch service

for UAVs.

A. Problem

Consider a logistics system with NUAVs performing

delivery tasks to Mknown delivery addresses from Kde-

pots. Denote the set of Mdelivery addresses as VG=

{g1, . . . , gM} ⊂ R2and the set of Kdepot locations as

VD={d1, . . . , dK} ⊂ R2. We assume that any package

can be dispatched from any depot and the depot can also

charge or change the battery of the UAV quickly. When a

UAV delivers a package from a depot to a delivery location,

the UAV can call a vehicle on the ground to provide a hitch

service, which signiﬁcantly extends the UAV’s delivery range.

In order to facilitate management, we specify that the UAV can

stop and wait for ground vehicles only at speciﬁc interchange

points equipped with surveillance cameras for safety’s sake.

We generate Lpotential interchange routes on the trafﬁc

network starting and ending at certain interchange points,

where the UAV can wait for ground vehicles while performing

delivery tasks. The set of interchange points is denoted as

VI={i1, . . . , iL0} ⊂ R2(L0≤L).

In the crowdsourcing-based multimodal logistics system,

the goal is to (i) design the optimal dynamic pricing to deal

with the tradeoff between the payment to ground vehicles and

UAVs’ waiting time; (ii) ﬁnd the delivery path of each UAV

to deliver all packages in a reasonable combination of UAVs’

own ﬂight path and transit routes on the trafﬁc network, while

minimizing the maximum delivery time for each UAV without

exceeding the storage capacity limit of the UAV.

B. Approach

In a crowdsourcing-based air-ground collaborative logistics

system, the behavioral decisions of the ground vehicles will

affect the UAV transportation efﬁciency. If the UAV waits

long time for the ground vehicles’ response to assist in

transportation, the passage time of the corresponding road

section will be prolonged, which will lead to the delay of UAV

mission completion time. Therefore, it is crucial to design

an effective crowdsourcing incentive mechanism to encourage

the ground vehicles to assist delivery. The passage time of

each road section will also inﬂuence the design of subsequent

task allocation and path planning algorithms. However, higher

incentives can shorten the UAV waiting time, but cause an

increase in UAV platform’s cost. Therefore, we will design a

dynamic pricing scheme to best balance the reward expendi-

ture to ground vehicles and the expected vehicle response time

of each road section.

Completing all package delivery requests means that each

package needs to be assigned to one and only one UAV. So

this problem can be viewed as a variation of the traveler

problem. Because of the limitations of UAV carrying capacity

and energy storage, we specify that a UAV can only deliver

one package at a time and return to some depot for charging

after completing the delivery task (charging time for UAVs

is ignored here). The delivery time of a package by a UAV

consists of the UAV ﬂight time and the ride time including

the vehicle response time (i.e., UAV waiting time) and the

vehicle traveling time when carrying the UAV. We describe

the energy storage limit of each UAV as a maximum ﬂight

time constraint, and each UAV must not exceed the maximum

ﬂight time when performing its delivery tasks. In addition, to

avoid collisions between UAVs, multiple UAVs can’t land at

the same interchange point at the same time. The above joint

optimization problem for UAV-vehicle path planning can be

modeled as mixed integer linear programming. However, most

of the existing mixed integer linear programming algorithms

can only handle small-scale models, which are not suitable

for large number of UAVs/packages and vast trafﬁc network

scenarios. We decompose the joint path planning problem

into two layers of decision models for discussion, and design

algorithms with low computational complexity at each layer,

respectively.

We formulate our multimodal logistics system as two stages

as shown in Fig. 1. In stage I, we predict the vehicle response

time at each interchange point based on our designed dynamic

pricing scheme, and update this information into the time

weights of the interchange routes in the trafﬁc network for

the following path planning. In Stage II, we ﬁrst analyze the

task allocation of UAVs to solve the problem of which UAV

delivers which packages and the order of delivery between

packages, and then the path ﬁnding for each delivery subtask.

To be speciﬁc, for task allocation in Layer 1, we temporarily

ignore the speciﬁc route of the UAV from the depot to the

package delivery address. We only decide which packages

are sent from which depot and which UAV is responsible for

which series of packages to be delivered, depending on the

estimated time (the shortest path from a certain depot to the

destination) between the depot and delivery location. We use

linear programming algorithms with relaxation conditions that

accomplish the task allocation problem in polynomial time.

For path ﬁnding in Layer 2, we take one UAV to deliver a

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1IncentiveMechanismandPathPlanningforUAVHitchingoverTrafcNetworksZiyiLu,NaYuandXueheWang,Member,IEEEAbstractPackagedeliveryviatheUAVsisapromisingtransportmodetoprovideefcientandgreenlogisticservices,especiallyinurbanareasorcomplicatedtopography.However,theenergystoragelimitoftheUAVmakesitdifcult...

展开>> 收起<<

1 Incentive Mechanism and Path Planning for UA V Hitching over Trafﬁc Networks.pdf

共14页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Incentive Mechanism and Path Planning for UA V Hitching over Trafﬁc Networks

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: