Search Space Reduction Using Swamp Hierarchies

In various domains, such as computer games, robotics, and transportation networks, shortest paths may need to be found quickly. Search time can be significantly reduced if it is known which parts of the graph include ``swamps''---areas that cannot lie on the only available shortest path, and can thus safely be pruned during search. We introduce an algorithm for detecting hierarchies of swamps, and exploiting them. Experiments support our claims of improved efficiency, showing significant reduction in search time.

• Publication year

  2010

• Venue

  Symposium on Combinatorial Search

• Publication date

  2010-07-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1609/socs.v1i1.18156
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Memory-Based Heuristics for Explicit State Spaces

  2009cited by this paper
• Using swamps to improve optimal pathfinding

  2009cited by this paper
• Abstraction-Based Heuristics with True Distance Computations

  2009cited by this paper
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks

  2008cited by this paper
• Memory-Efficient Abstractions for Pathfinding

  2007cited by this paper
• Efficient Triangulation-Based Pathfinding

  2006cited by this paper
• Improved Heuristics for Optimal Path-finding on Game Maps

  2006cited by this paper
• Partial Pathfinding Using Map Abstraction and Refinement

  2005cited by this paper
• Near Optimal Hierarchical Path-Finding

  2004cited by this paper
• PHA*: performing A* in unknown physical environments

  2002cited by this paper
• Pattern Databases

  1979cited by this paper

• Convexity Hierarchies in Grid Networks

  2023cites this paper
• A Fast Bi-Directional A* Algorithm Based on Quad-Tree Decomposition and Hierarchical Map

  2021cites this paper
• Path Planning Method for UAVs Based on Constrained Polygonal Space and an Extremely Sparse Waypoint Graph

  2021cites this paper
• Search-Aware Conditions for Probably Approximately Correct Heuristic Search

  2021cites this paper
• Repairing Compressed Path Databases on Maps with Dynamic Changes

  2021cites this paper
• Watershed Graphs for Faster Path Planning in Binary Occupancy Grids

  2020cites this paper
• Homotopy based optimal configuration space reduction for anytime robotic motion planning

  2020cites this paper
• Speed Optimization for Incremental Updating of Grid-Based Distance Maps

  2019cites this paper
• Comparative analysis of selected path-planning approaches in large-scale multi-agent-based environments

  2018cites this paper
• A Fast Global Flight Path Planning Algorithm Based on Space Circumscription and Sparse Visibility Graph for Unmanned Aerial Vehicle

  2018cites this paper
• A new weighted pathfinding algorithms to reduce the search time on grid maps

  2017cites this paper
• The FastMap Algorithm for Shortest Path Computations

  2017cites this paper
• Adaptive Artificial Intelligence in Real-Time Strategy Games

  2017cites this paper
• Shortest Alternate Path Discovery through Recursive Bounding Box Pruning

  2017cites this paper
• Rectangle expansion A * pathfinding for grid maps

  2016influential citation
• Optimization Using Boundary Lookup Jump Point Search

  2016cites this paper
• Combining Bounding Boxes and JPS to Prune Grid Pathfinding

  2016cites this paper
• Reducing Search Space of A * Algorithm Using Obstacle Information

  2015cites this paper
• Expected Path Degradation when Searching over a Sparse Grid Hierarchy

  2015cites this paper
• Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling

  2014cites this paper
• Identifying Hierarchies for Fast Optimal Search

  2014cites this paper
• Improving Jump Point Search

  2014cites this paper
• Fast and Optimal Pathfinding

  2014influential citation
• Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence

  2014cites this paper
• Research on Optimal Path Finding Algorithm

  2013cites this paper
• The Hierarchy in Grid Graphs

  2013cites this paper
• The Hierarchy in Grid Graphs (Extended Abstract)

  2013cites this paper
• Subgoal Graphs for Optimal Pathfinding in Eight-Neighbor Grids

  2013cites this paper
• Contraction Hierarchies on Grid Graphs

  2013cites this paper
• Online Detection of Dead States in Real-Time Agent-Centered Search

  2013influential citation
• The JPS Pathfinding System

  2012cites this paper
• Improving Heuristics for Pathfinding in Games

  2011cites this paper
• Path Queries on Massive Graphs Based on Multi-granular Graph Partitioning

  2011cites this paper
• Symmetry-Based Search Space Reduction For Grid Maps

  2011influential citation
• Fast Pathfinding via Symmetry Breaking

  2011cites this paper
• Online Graph Pruning for Pathfinding On Grid Maps

  2011influential citation
• Path Symmetries in Undirected Uniform-Cost Grids

  2011influential citation
• Pruning Techniques in Search and Planning ( Research

  2011cites this paper