Route planning services inherently require knowledge of user origins and destinations, creating privacy risks that prevent many users from adopting shared mobility services. This work is important because it demonstrates how to achieve privacy guarantees while maintaining practical routing efficiency. The innovation lies in the use of hierarchical route planning with privacy-preserving mechanisms that allows distributed computation without centralizing sensitive location data.
This paper develops a hierarchical privacy-preserving route planning approach for autonomous vehicles and shared mobility services. The work addresses the challenge of computing optimal routes while protecting user location privacy through a novel combination of network partitioning and distributed computation. The approach uses Private Information Retrieval techniques to compute routes without revealing origin-destination pairs to service providers, while maintaining routing efficiency comparable to non-private approaches.
The hierarchical privacy-preserving approach achieves near-optimal route efficiency while providing strong privacy guarantees, with routes differing by only 5-20% from optimal paths depending on privacy parameters. Computational overhead is manageable, with query processing completing in reasonable time for practical transit applications. The approach validates that privacy and efficiency are not inherently incompatible, providing a model for privacy-preserving transit systems.
@article{talusan2023tcps2,
author = {Tiausas, Francis and Yasumoto, Keiichi and Talusan, Jose Paolo and Yamana, Hayato and Yamaguchi, Hirozumi and Bhattacharjee, Shameek and Dubey, Abhishek and Das, Sajal K.},
journal = {ACM Trans. Cyber-Phys. Syst.},
title = {HPRoP: Hierarchical Privacy-preserving Route Planning for Smart Cities},
year = {2023},
issn = {2378-962X},
month = {oct},
number = {4},
volume = {7},
abstract = {Route Planning Systems (RPS) are a core component of autonomous personal transport systems essential for safe and efficient navigation of dynamic urban environments with the support of edge-based smart city infrastructure, but they also raise concerns about user route privacy in the context of both privately owned and commercial vehicles. Numerous high-profile data breaches in recent years have fortunately motivated research on privacy-preserving RPS, but most of them are rendered impractical by greatly increased communication and processing overhead. We address this by proposing an approach called Hierarchical Privacy-Preserving Route Planning (HPRoP), which divides and distributes the route-planning task across multiple levels and protects locations along the entire route. This is done by combining Inertial Flow partitioning, Private Information Retrieval (PIR), and Edge Computing techniques with our novel route-planning heuristic algorithm. Normalized metrics were also formulated to quantify the privacy of the source/destination points (endpoint location privacy) and the route itself (route privacy). Evaluation on a simulated road network showed that HPRoP reliably produces routes differing only by ≤ 20\% in length from optimal shortest paths, with completion times within ∼ 25 seconds, which is reasonable for a PIR-based approach. On top of this, more than half of the produced routes achieved near-optimal endpoint location privacy (∼ 1.0) and good route privacy (≥ 0.8).},
address = {New York, NY, USA},
articleno = {27},
contribution = {colab},
doi = {10.1145/3616874},
issue_date = {October 2023},
keywords = {privacy-preserving routing, location privacy, shared mobility, route planning, distributed computation, private information retrieval, transportation networks, user privacy},
numpages = {25},
publisher = {Association for Computing Machinery},
url = {https://doi.org/10.1145/3616874},
month_numeric = {10}
}