TL;DR
This paper introduces "PALMA," a novel pruning technique for real-time heuristic search (RTHS) algorithms. PALMA aggressively prunes expanded states from the search space, adding new "shortcut" edges to maintain connectivity and guarantee goal reachability, significantly outperforming state-of-the-art RTHS methods.
What Problem Does This Paper Address?
Real-time heuristic search (RTHS) algorithms are crucial for domains like video games and robotics where agents must make decisions under strict time constraints. A major challenge in RTHS is "scrubbing," where agents repeatedly revisit states due to suboptimal heuristic functions, leading to inefficient exploration and poor solution quality. While various techniques exist to mitigate scrubbing, this paper focuses on a more aggressive pruning approach that can be applied to a wide range of RTHS algorithms, aiming to improve both solution quality and efficiency.
Methods
The core of the paper is the PALMA (Pruning with Arbitrary Lookaheads and Macro Actions) algorithm. PALMA operates by pruning the "Closed list" (states expanded in the current search episode) from the search graph. The key innovation is bridged pruning:
- Pruning: All states in the Closed list are removed from the agent's representation of the search graph.
- Bridging: If removing these states disconnects the "frontier" (the Open list, i.e., states on the boundary of the explored region), PALMA adds new "shortcut" edges. These edges connect states that were previously in different disconnected components of the frontier. The cost of these new edges is the shortest path cost between the connected states in the original graph before pruning.
This bridging mechanism ensures that the goal remains reachable even after pruning, guaranteeing completeness without relying on heuristic learning. PALMA can be applied on top of any RTHS algorithm that fits the standard framework (Algorithm 1 in the paper), which interleaves local search, heuristic updates, and agent movement. The paper implements PALMA on top of LSS-LRTA (PALMA(LSS-LRTA)).
Datasets
The paper evaluates PALMA on standard pathfinding benchmarks from the MovingAI pathfinding repository. These include:
- Five 1024x1024 StarCraft maps.
- Thirty 512x512 maze maps (with corridor widths of 4, 8, 16).
- 512x512 World of Warcraft III (WC3) maps.
- 512x512 room maps.
- The same maze maps but with 1% of obstacles removed.
For each map type, 100 random solvable problems were generated.
Key Insights and Ideas
- Aggressive Pruning is Beneficial: The paper demonstrates that aggressively pruning all expanded states (not just a single state as in prior work) can significantly improve performance when connectivity is maintained.
- Bridging Guarantees Completeness: The novel "bridged pruning" concept is crucial. By adding shortcut edges to reconnect the frontier, PALMA ensures the goal remains reachable, making heuristic learning optional for completeness. This is a significant advantage over many existing RTHS algorithms that rely heavily on heuristic updates to avoid local minima.
- Online, Adaptive Pruning: Unlike methods like Contraction Hierarchies that require offline preprocessing, PALMA performs pruning online, adapting to the current search state.
- General Applicability: PALMA is designed to be a plug-in module for various RTHS algorithms, enhancing their performance without requiring fundamental changes to their core logic.
Key Results
- PALMA(LSS-LRTA) significantly outperforms state-of-the-art RTHS algorithms like LSS-LRTA, wLSS-LRTA, and EDA across multiple benchmarks.
- For lower lookahead values, improvements can exceed an order of magnitude in terms of solution cost and runtime.
- PALMA consistently requires the fewest search episodes among the compared algorithms.
- In 15 out of 20 benchmark combinations (map type x lookahead value), PALMA(LSS-LRTA*) was the dominant algorithm, achieving both the lowest solution cost and the lowest runtime.
- The number of connected components in the Open list (r) is typically small (average < 2 in many cases), meaning bridging is often not needed or requires minimal effort.
Limitations and Future Work
- Representation vs. World: The paper notes that PALMA modifies the agent's representation of the search graph. The actual traversable world remains unchanged. When PALMA adds a new edge, it implicitly remembers the sequence of states in the original graph that would need to be traversed.
- Future Work: The authors suggest exploring how pruning information from one problem instance could be reused for solving other instances. They also plan to evaluate PALMA in scenarios with partial terrain knowledge.
Summary updated