Planning unobstructed paths in traffic-aware spatial networks

Shang, Shuo, Liu, Jiajun, Zheng, Kai, Lu, Hua, Pedersen, Torben Bach and Wen, Ji-Rong (2015) Planning unobstructed paths in traffic-aware spatial networks. GeoInformatica, 19 4: 723-746. doi:10.1007/s10707-015-0227-9

Author Shang, Shuo
Liu, Jiajun
Zheng, Kai
Lu, Hua
Pedersen, Torben Bach
Wen, Ji-Rong
Title Planning unobstructed paths in traffic-aware spatial networks
Journal name GeoInformatica   Check publisher's open access policy
ISSN 1384-6175
Publication date 2015-10-01
Sub-type Article (original research)
DOI 10.1007/s10707-015-0227-9
Open Access Status Not Open Access
Volume 19
Issue 4
Start page 723
End page 746
Total pages 24
Place of publication New York, NY, United States
Publisher Springer New York
Collection year 2016
Language eng
Formatted abstract
Route planning and recommendation have received significant attention in recent years. In this light, we study a novel problem of planning unobstructed paths in traffic-aware spatial networks (TAUP queries) to avoid potential traffic congestions. We propose two probabilistic TAUP queries: (1) a time-threshold query like “what is the path from the check-in desk to the flight SK 1217 with the minimum congestion probability to take at most 45 minutes?”, and (2) a probability-threshold query like “what is the fastest path from the check-in desk to the flight SK 1217 whose congestion probability is less than 20 %?”. These queries are mainly motivated by indoor space applications, but are also applicable in outdoor spaces. We believe that these queries are useful in some popular applications, such as planning unobstructed paths for VIP bags in airports and planning convenient routes for travelers. The TAUP queries are challenged by two difficulties: (1) how to model the traffic awareness in spatial networks practically, and (2) how to compute the TAUP queries efficiently under different query settings. To overcome these challenges, we construct a traffic-aware spatial network Gta (V, E) by analyzing uncertain trajectories of moving objects. Based on Gta (V, E), two efficient algorithms are developed to compute the TAUP queries. The performances of TAUP queries are verified by extensive experiments on real and synthetic spatial data.
Keyword Efficiency
Probabilistic path planning
Spatio-temporal databases
Traffic-aware spatial networks
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2016 Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 3 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 4 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 20 Oct 2015, 00:26:06 EST by System User on behalf of Scholarly Communication and Digitisation Service