An Efﬁcient Dynamic Multi-Sources To Single-Destination DMS-SD Algorithm In Smart City Navigation Using Adjacent Matrix

2025-04-30 0 0 279.42KB 6 页 10玖币

侵权投诉

An Efﬁcient Dynamic Multi-Sources To

Single-Destination (DMS-SD) Algorithm In Smart

City Navigation Using Adjacent Matrix

Ziren Xiao

Department of EEE

Xi’an Jiaotong-Liverpool University

Suzhou, China

ziren.xiao20@xjtlu.edu.cn

Ruxin Xiao

Department of EEE

Xi’an Jiaotong-Liverpool University

Suzhou, China

ruxin.xiao21@student.xjtlu.edu.cn

Chang Liu

Department of EEE

Xi’an Jiaotong-Liverpool University

Suzhou, China

chang.liu2020@outlook.com

Honghao Gao

School of CES

Shanghai University

Shanghai, China

gaohonghao@shu.edu.cn

Xiaolong Xu

Jiangsu Key Lab. of BBSIP

NUPT

Nanjing, China

xuxl@njupt.edu.cn

Shan Luo

Department of CS

University of Liverpool

Liverpool, UK

shan.luo@liverpool.ac.uk

Xinheng Wang

Department of EEE

Xi’an Jiaotong-Liverpool University

Suzhou, China

xinheng.wang@xjtlu.edu.cn

Abstract—Dijkstra’s algorithm is one of the most popular clas-

sic path-planning algorithms, achieving optimal solutions across

a wide range of challenging tasks. However, it only calculates the

shortest distance from one vertex to another, which is hard to

directly apply to the Dynamic Multi-Sources to Single-Destination

(DMS-SD) problem. This paper proposes a modiﬁed Dijkstra

algorithm to address the DMS-SD problem, where the destination

can be dynamically changed. Our method deploys the concept

of the Adjacent Matrix from Floyd’s algorithm and achieves

the goal with mathematical calculations. We formally show that

all-pairs shortest distance information in Floyd’s algorithm is

not required in our algorithm. Extensive experiments verify the

scalability and optimality of the proposed method.

Index Terms—multiple sources path planning

I. INTRODUCTION

The emerging Industry 5.0 puts forward new requirements

for the future intelligent transportation system. Based on the

vision of Industry 4.0, beyond the autonomy, digitalization,

self-awareness, connectivity, and interoperability in the future

factory, Industry 5.0 also deﬁnes a new era of human-machine

collaborative work that places sustainability, human care, and

production resilience as the center [1] [2]. As an essential

part of a smart city, future smart transportation management,

which coordinates, schedules, and monitors the city trafﬁc,

is expected to evolve following this wave in realizing the

harmony among residents, urban, and society [3] [4]. To

date, multiple enabling technologies, such as the internet of

things, big data analytics, and artiﬁcial intelligence, drive the

modern transportation network that converges and analyses

This research was funded by: Key Program Special Fund in XJTLU under

project KSF-E-64; XJTLU Research Development Funding under projects

RDF-19-01-14 and RDF-20-01-15; the National Natural Science Foundation

of China (NSFC) under grant 52175030.

transportation data to schedule and navigate [5] [4]. In fu-

ture Industry 5.0, smart transportation management must also

reduce process waste and reinforce humanity’s design while

delivering adequate transportation. Thus, the future smart city

is calling for new concepts, methods, and technologies to

enhance its transportation management.

Smart navigation system plays a decisive role in smart

transportation management. As a coordinator in smart trans-

portation management, smart navigation systems schedule

and allocate residents’ commutes to optimize the city trafﬁc

condition [6]. In Industry 5.0, smart navigation system tends

to be increasingly important due to its inﬂuence on city

productivity and residents’ well-being. The vital point of the

smart navigation system is the collaborative action analysis

behind it. In real-time on-site situations, a smart navigation

system must rapidly receive and respond to all users’ states

to derive an optimal trafﬁc plan. Through the development

of modern cities, the growing city population and vehicles

have been introducing more commute units in transportation

networks. Besides, the constructions of infrastructures bring

in ﬂuctuating road conditions. Therefore, complexity in trans-

portation management keeps climbing rapidly. Thus, algo-

rithms of collaborative action analysis must evolve abreast.

Existing problems of collaborative action analysis remain

unsolved in navigation research, and the Dynamic Multi

Sources Single Destination problem (DMS-SD) is a critical

one in transportation management. Congregate activities, such

as sports competitions, outings, and business propagations,

are arguably residents’ most common daily affairs. Most

congregate activities can only commence when all engagers

have arrived. Therefore, while meeting at the same location,

each engager’s traveling time should be approximately the

same to prohibit the waiting time of engagers who arrive

arXiv:2210.14869v2 [cs.DS] 9 Dec 2022

earlier. Besides, the overall traveling time of each engager

must be minimized to ensure the punctuality of congregate

activities. As most road conditions in a city are generally the

same, it can be hypothesized that traveling time is generally

equivalent to traveling distance here. Moreover, on many

occasions, congregate activities ought to temporarily change

plans due to unpredicted issues (rain during outdoor activities,

incomplete venue constructions, ﬁre alarms, etc.). Thus, the

original place must change to ensure congregate activities

proceed, and so does the navigation destination.

As a summary of such a problem in navigation terms, DMS-

SD depicts a scenario in which multiple activity engagers need

to unite at a speciﬁed location, where each engager travels

equally and shortest distance. The intended destination may

change dynamically depending on real-time on-site situations.

Thus, route plans must be refreshed for every engager in cor-

respondence. Meanwhile, as Industry 5.0 emphasizes process

waste reduction, there are three additional requirements for

DMS-SD solutions: (1) DMS-SD solutions should emphasize

’dynamic’ so engagers can run the navigation system in real-

time software with reasonable computation time; (2) Com-

putation tasks of DMS-SD solutions should consume limited

resources to run in engagers’ mobile devices, rather than

introducing enormous loads to a central server; (3) DMS-SD

solutions should minimize the total distance to reduce power

consumption generated from traveling.

Conventionally, path planning algorithms simplify the prob-

lem into a point-to-point shortest time or shortest distance

problem, deﬁned as a Single Source to a Single Destination

Problem (SS-SD). Based on this simpliﬁcation, most existing

approaches seek optimal routes according to performance indi-

cators. For example, A* and Dijkstra algorithm can ensure an

optimal solution via exploitation of entire path computations

[7] [8]. However, these methods are not effective enough to

resolve DMS-SD problems as paths to all nodes must be

simulated to obtain the shortest path in iterations, especially in

a large-scale map. Besides, recent research also seeks solutions

via Q-learning-based reinforcement learning algorithms [9]

[10]. However, it is noticed to be challenging in DMS-SD

problems due to the complexity of reward design.

This paper proposes an innovative modiﬁed Dijkstra al-

gorithm to address the DMS-SD problem. This modiﬁed

algorithm introduces the Adjacent Matrix in classic Floyd’s

algorithm to store the shortest distance between nodes. Hence,

this storage method avoids the mass computation work in

Floyd’s algorithm about distance calculations for every pair

of nodes. On the base of adjustments brought by Adjacent

Matrix, a temporary destination could only associate with

the current locations of people in the DMS-SD problem.

Therefore, this algorithm possesses the capacity for the optimal

solution to the current state of people to navigate without a

pre-training model. More importantly, individuals keep their

personal preferences during decision-making. In this work,

considering individual preference an inﬂuential factor, multiple

preferences are provided to people, including distance, time,

and meeting place, to satisfy different meeting goals rather

than distance only. These beneﬁcial changes enhance the

completeness of problem-solving and fortify its user-friendly.

The contributions of this paper lie in the following:

•Resolving the DMS-SD problem that has not been well

discussed in past studies.

•Proposing an efﬁcient algorithm to address the DMS-SD

problem based on Dijkstra’s algorithm, which can effec-

tively compute an optimal solution without generating the

entire Adjacent Matrix. More importantly, the proposed

method can address a large scaled DMS-SD problem with

linearly increasing time.

The rest of the paper is organized as follows: Section 2 will

clarify the details of the modiﬁed Dijkstra algorithm. Section

3 will present evaluations of the modiﬁed Dijkstra algorithm

based on computation time, optimality, and dynamicity. Sec-

tion 4 will review related work about multi-agent path planning

to highlight the contribution and validation of this research.

Section 5 will conclude the paper and discuss future relevant

work.

II. THE MODIFIED DIJKSTRA’S(MD) ALGORITHM

Dijkstra’s algorithm was proposed by [8] in 1959. This

algorithm aims to search the shortest distance between a pair of

vertices. In our work, we record all shortest distances from the

source node to all other vertices using Adjacent Matrix, which

is typically used in Floyd’s algorithm. Then, by applying

several matrix calculations, we achieve our goal: every user

travels the shortest and equally distant to the destination based

on the current state. The proposed algorithm spends much less

time than Floyd’s algorithm on solving the DMS-SD problem

as well as efﬁciently generating an optimal solution.

A. Adjacent Matrix

The standard Adjacent Matrix (Madj ) is a 2-Dimensional

matrix used to represent the connection between vertices in a

graph. For example, provided a graph G= (V, E)where the

vertex set V={v1, v2, v3}and Eis the edge set, the initial

form of the Madj of Gcan be presented as in Eq. 1.

Madj =





v1v2v3

v10 2 4

v22 0 ∞

v34∞0







(1)

where the notation ∞means there is no direct road between

those two vertices. ∞can be updated to the actual number

later if the destination can be achieved via another vertex. In

our work, we use the Adjacent Matrix to present the shortest

distance from a person to all other nodes. This means the

matrix can be unsymmetric, as shown in Eq. 2

Madj =



v1v2v3v4

A0 2 4 1

B2 0 6 3



(2)

Where Aand Bare two people. Additionally, we use a tuple

(vx, vy)to represent the distance shown in the Madj . For

example, (A, v2)in Eq. 2 shows the distance from person

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

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

10 玖币 0人已下载

立即下载

摘要：

AnEfcientDynamicMulti-SourcesToSingle-Destination(DMS-SD)AlgorithmInSmartCityNavigationUsingAdjacentMatrixZirenXiaoDepartmentofEEEXi'anJiaotong-LiverpoolUniversitySuzhou,Chinaziren.xiao20@xjtlu.edu.cnRuxinXiaoDepartmentofEEEXi'anJiaotong-LiverpoolUniversitySuzhou,Chinaruxin.xiao21@student.xjtlu.edu...

展开>> 收起<<

An Efﬁcient Dynamic Multi-Sources To Single-Destination DMS-SD Algorithm In Smart City Navigation Using Adjacent Matrix.pdf

共6页,预览2页

还剩页未读，继续阅读

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

An Efﬁcient Dynamic Multi-Sources To Single-Destination DMS-SD Algorithm In Smart City Navigation Using Adjacent Matrix

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: