Planning unobstructed paths in traffic-aware spatial networks

Shuo Shang*, Jiajun Liu, Kai Zheng, Hua Lu, Torben Bach Pedersen, Ji Rong Wen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

47 Citations (Scopus)

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.

Original languageEnglish
JournalGeoinformatica
Volume19
Issue number4
Pages (from-to)723-746
Number of pages24
ISSN1384-6175
DOIs
Publication statusPublished - 1 Oct 2015

Keywords

  • Efficiency
  • Probabilistic path planning
  • Spatio-temporal databases
  • Traffic-aware spatial networks

Fingerprint

Dive into the research topics of 'Planning unobstructed paths in traffic-aware spatial networks'. Together they form a unique fingerprint.

Cite this