Vidhya Balasubramanian
Dmitri V. Kalashnikov
ABSTRACT
This paper considers the problem of Multi-Geography Route Planning (MGRP) where the geographical information may be spread over multiple heterogeneous interconnected maps. We first design a flexible and scalable representation to model individual geographies and their interconnections. Given such a representation, we develop an algorithm that exploits precomputation and caching of geographical data for path planning. A utility-based approach is adopted to decide which paths to precompute and store. To validate the proposed approach we test the algorithm over the workload of a campus level evacuation simulation that plans evacuation routes over multiple geographies: indoor CAD maps, outdoor maps, pedestrian and transportation networks, etc. The empirical results indicate that the MGRP algorithm with the proposed utility based caching strategy significantly outperforms the state of the art solutions when applied to a large university campus data under varying conditions.
- V. Balasubramanian. Supporting scalable activity modeling in simulators. PhD Thesis. Google Scholar
Digital Library
- A. Bandera, C. Urdiales, and F. Sandoval. A hierarchical approach to grid-based and topological maps integration for autonomous indoor navigation. In IEEE/RSJ IROS, 2001.Google ScholarCross Ref
- S. Behnke. Local multiresolution path planning. In In Proc. of 7th RoboCup Int'l Symposium, 2004.Google ScholarCross Ref
- Y. Björnsson, M. Enzenberger, R. Holte, and J. Schaeffer. Fringe search: Beating a* at pathfinding on computer game maps. In Proc. of the IEEE CIG, 2005.Google Scholar
- Y. Björnsson and K. Halldorson. Improved heuristics for optimal path-finding on game maps. In AIIDE, 2006.Google Scholar
- A. Botea, M. Muller, and J. Schaeffer. Near optimal hierarchical path-finding. In J. Game Development, 2004.Google Scholar
- A. Car, H. Mehner, and G. Taylor. Experimenting with hierarchical wayfinding. Technical Report 011999, 1999.Google Scholar
- E. P. F. Chan and H. Lim. Optimization and evaluation of shortest path queries. 16(3):343--369, 2007. Google ScholarDigital Library
- S. Chen, D. V. Kalashnikov, and S. Mehrotra. Adaptive graphical approach to entity resolution. In Proc. of ACM IEEE Joint Conference on Digital Libraries (JCDL), 2007. Google ScholarDigital Library
- B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 73, 1996. Google ScholarDigital Library
- A. Fetterer and S. Shekhar. A performance analysis of hierarchical shortest path algorithms. In Ninth IEEE Int'l Conf. on Tools with Artificial Intelligence, 1997. Google ScholarDigital Library
- A. V. Goldberg. Shortest path algorithms: Engineering aspects. In ISAAC, 2001. Google ScholarDigital Library
- J. E. Guivant, E. M. Nebot, J. Nieto, and F. R. Masson. Navigation and mapping in large unstructured environments. I. J. Robotic Res., 23(4--5), 2004.Google Scholar
- Y. Huang, N. Jing, and E. Rundensteiner. Hierarchical optimization of optimal path finding for transportation applications. In Proc. of CIKM, 1996. Google ScholarDigital Library
- N. Jing, Y. W. Huang, and E. Rundensteiner. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation. In TKDE, 1998. Google ScholarDigital Library
- D. B. Johnson. Efficient algorithms for shortest paths in sparse networks. In J. of the ACM, volume 24, 1977. Google ScholarDigital Library
- S. Jung and S. Pramanik. An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowl. Data Eng., 14(5), 2002. Google ScholarDigital Library
- D. V. Kalashnikov and S. Mehrotra. Domain-independent data cleaning via analysis of entity-relationship graph. ACM Transactions on Database Systems (ACM TODS), 31(2):716--767, June 2006. Google ScholarDigital Library
- D. V. Kalashnikov, S. Mehrotra, and Z. Chen. Exploiting relationships for domain-independent data cleaning. In SIAM Data Mining (SDM), 2005.Google ScholarCross Ref
- B.-Y. Ko, J.-B. Song, and S. Lee. Real-time building of a thinning-based topological map with metric features. In IEEE/RSJ Conf. on Intel. Robots and Systs., 2004.Google Scholar
- M. Kolahdouzan and C. Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. VLDB, 2004. Google ScholarDigital Library
- B. Lorenz, H. Ohlback, and E. Stoffel. A hybrid spatial model for representing indoor environments. In W2GIS'06. Google ScholarDigital Library
- S. Pallottino and M. G. Scutella. Shortest path algorithms in transportation models: classical and innovative aspects. Technical Report TR-97-06, 1997. Google ScholarDigital Library
- J.-S. Park, M. Penner, and V. K. Prasanna. Optimizing graph algorithms for improved cache performance. IEEE Trans. Parallel Distrib. Syst., 15(9), 2004. Google ScholarDigital Library
- S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. 2003. Google ScholarDigital Library
- H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In ACM SIGMOD, 2008. Google ScholarDigital Library
- Seidel. On the all-pairs-shortest-path problem. In STOC'92. Google ScholarDigital Library
- S. Shekhar, A. Fetterer, and Goyal. Materialization trade-offs in hierarchical shortest path algorithms. In SSD'97. Google ScholarDigital Library
- S. Shekhar and H. Xiong. Encyclopedia of GIS. 2008. Google ScholarDigital Library
- W. White, A. Demers, C. Koch, J. Gehrke, and Rajagopalan. Scaling games to epic proportions. In ACM SIGMOD, 2007. Google ScholarDigital Library
Recommendations
Efficient Approaches for Multi-requests Route Planning in Urban Areas
MDM '13: Proceedings of the 2013 IEEE 14th International Conference on Mobile Data Management - Volume 01In recent years, with the rapid developments of wireless technologies, researches on Location-Based Services (LBSs) have attracted extensive attentions and one active topic among them is constraint-based route planning on a Point-Of-Interest (POI) ...
Online Route Replanning for Scalable System-Optimal Route Planning
SIGSPATIAL '21: Proceedings of the 29th International Conference on Advances in Geographic Information SystemsRoute planning in transportation networks is typically performed as a single optimization at trip departure. In this paper, we consider the impact of within-trip replanning on the performance of the overall network in a fully-algorithmic route selection ...
Cognition-based hierarchical en route planning for multi-agent traffic simulation
A cognition-based en route planning approach is devised under the E-BDI framework.A hierarchical en route planning approach is proposed to handle a large-scale network.An integrated traffic simulation platform is developed for the demonstration.The ...
Comments