Project "Preprocessing-Based Path-Planning Algorithms"
(scroll down for publications)
Path planning on graphs has many applications in video games, robotics, and
navigation systems. Preprocessing-based path-planning (PBPP) algorithms first
analyze a given graph in a preprocessing phase to generate auxiliary
information which can then be used to significantly speed-up online
shortest-path queries. The performance of these algorithms can be
characterized by their runtime/memory trade-off, as it is often possible to
achieve shorter runtimes by using more memory. A number of competitions have
been held to evaluate PBPP (and other) algorithms, including a DIMACS
Implementation Challenge and the Grid-Based Path-Planning Competition.
One example of PBPP algorithms is contraction hierarchies and our
closely-related (N-level) subgoal graphs, that essentially reinvented a
similar concept with its own advantages and disadvantages. We now study what
their properties and relationship are, how to combine their features, and how
to develop even better PBPP algorithms. Another example of PBPP algorithms is
FastMap, that embeds a given non-negative edge-weighted undirected graph in a
Euclidean space and approximately preserves the pairwise shortest path
distances between vertices. We now study applications of FastMap to heuristic
search in a variety of domains, such as path finding and networking.
For example, the Euclidean space can be used either for heuristic
guidance of A* or for geometric interpretations that facilitate the
application of techniques from analytical geometry.
Code
Representative Publications on Subgoal Graphs
- D. Harabor, T. Uras, P. Stuckey and S. Koenig. Regarding Jump Point Search and Subgoal Graphs. In International Joint Conference on Artificial Intelligence (IJCAI), 1241-1248, 2019. [downloadable]
- T. Uras and S. Koenig. Understanding Subgoal Graphs by Augmenting Contraction Hierarchies. In International Joint Conference on Artificial Intelligence (IJCAI), 1506-1513, 2018. [downloadable]
- T. Uras and S. Koenig. Fast Near-Optimal Path Planning on State Lattices with Subgoal Graphs. In Symposium on Combinatorial Search (SoCS), 106-114, 2018. [downloadable]
- T. Uras and S. Koenig. Feasibility Study: Subgoal Graphs on State Lattices. In Symposium on Combinatorial Search (SoCS), 100-108, 2017. [downloadable]
- T. Uras and S. Koenig. An Empirical Comparison of Any-Angle Path-Planning Algorithms [Short Paper]. In Symposium on Combinatorial Search (SoCS), 206-210, 2015. [downloadable]
- T. Uras and S. Koenig. Speeding-up Any-Angle Path-Planning on Grids [Short Paper]. In International Conference on Automated Planning and Scheduling (ICAPS), 234-238, 2015. [downloadable]
- T. Uras and S. Koenig. Identifying Hierarchies for Fast Optimal Search. In AAAI Conference on Artificial Intelligence (AAAI), 2014. [downloadable]
- T. Uras, S. Koenig and C. Hernandez. Subgoal Graphs for Optimal Pathfinding in Eight-Neighbor Grids. In International Conference on Automated Planning and Scheduling (ICAPS), 2013. [downloadable]
- T. Uras, S. Koenig and C. Hernandez. Subgoal Graphs for Eight-Neighbor Gridworlds [Competition Abstract]. In Symposium on Combinatorial Search (SoCS), 2012. [downloadable]
Representative Publications on FastMap
- A. Li, P. Stuckey, S. Koenig and S. Kumar. Rapidly Computing Approximate Graph Convex Hulls via Fast Map. In International Conference on Machine Learning, Optimization, and Data Science (LOD), (in print), 2024. [downloadable]
- A. Li, P. Stuckey, S. Koenig and S. Kumar. A FastMap-Based Framework for Efficiently Computing Top-K Projected Centrality. In International Conference on Machine Learning, Optimization, and Data Science (LOD) 2023 - Part 1, G. Nicosia, V. Ojha, E. La Malfa, G. La Malfa, P. M. Pardalos and R. Umeton (editor), volume 14505 of 158-173. Springer, 2024. [downloadable]
- A. Li, P. Stuckey, S. Koenig and S. Kumar. Solving Facility Location Problems via FastMap and Locality Sensitive Hashing. In Symposium on Combinatorial Search (SoCS), (in print), 2024. [downloadable]
- A. Li, P. Stuckey, S. Koenig and S. Kumar. A FastMap-Based Algorithm for Block Modeling. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), 232-248, 2022. [downloadable]
- O. Thakoor, A. Li, S. Koenig, S. Ravi, E. Kline and S. Kumar. The FastMap Pipeline for Facility Location Problems. In International Conference on Principles and Practice of Multi-Agent Systems (PRIMA), 417-434, 2022. [downloadable]
- S. Gopalakrishnan, L. Cohen, S. Koenig and S. Kumar. Embedding Directed Graphs in Potential Fields Using FastMap-D. In Symposium on Combinatorial Search (SoCS), 48-56, 2020. [downloadable]
- J. Li, A. Felner, S. Koenig and S. Kumar. Using FastMap to Solve Graph Problems in a Euclidean Space. In International Conference on Automated Planning and Scheduling (ICAPS), 273-278, 2019. [downloadable]
- L. Cohen, T. Uras, S. Jahangiri, A. Arunasalam, S. Koenig and S. Kumar. The FastMap Algorithm for Shortest Path Computations. In International Joint Conference on Artificial Intelligence (IJCAI), 1427-1433, 2018. [downloadable]
Many publishers do not want authors to make their papers available
electronically after the papers have been published. Please use the
electronic versions provided here only if hardcopies are not yet
available. If you have comments on any of these papers, please send me an
email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that
was developed as part of an undergraduate research project, advised by Sven Koenig.
Home Page of Sven Koenig