Abstract
Automated planning is an important general problem solving technique in Artificial Intelligence. Given an initial state, a goal and a set of operators, we want to find a sequence of operators leading us to the goal. What makes planning interesting is that it can model different domains into planning tasks and solve them using a single method. In this work, we approach two different topics in planning. First, we study heuristics for the airport ground traffic problem and propose new heuristics that are better than any other known method. In the second part, we study tie-breakers for the A* search algorithm. We propose a new tie-breaking method that is proved to be the best possible and also show that our methods solve more instances than previous methods in literature.
Introduction
Automated planning involves finding a sequence of actions to transition from an initial state to a goal state. A major challenge in this field is the "state explosion problem," where the number of possible states grows exponentially with the complexity of the task. To navigate this, planners use heuristics—functions that estimate the cost to reach the goal—to guide the search toward promising paths.
This research addresses two specific limitations in current planning techniques: domain-specific inefficiency in complex logistics and the sub-optimal nature of standard tie-breaking strategies in the A* search algorithm.
Advancing Airport Logistics Heuristics
General-purpose heuristics often struggle with the specific constraints of real-world domains. The authors focus on airport ground traffic, introducing a challenging "Free Parking" variant where incoming planes can choose from multiple parking spots. This creates a combinatorial explosion of possible goal states that standard planners fail to navigate efficiently.
To address this, the paper proposes the Matching Heuristic. Unlike simpler methods that might assume multiple planes can occupy the same spot, the Matching Heuristic models the problem as a bipartite matching task. This ensures the heuristic estimate respects resource constraints, providing a significantly more accurate distance to the goal.
Optimizing A* Tie-Breaking
When the A* algorithm encounters multiple paths with the same estimated total cost ($f$-value), it must decide which to explore first. Inefficient tie-breaking can lead to the expansion of many "useless" states in the final layer of the search.
The authors introduce Cost Adaptation ($h_c$), a strategy that modifies action costs by adding a small constant $c$. By setting $c$ to a tiny value ($\epsilon$), the search naturally prioritizes paths with fewer steps among those with equal total costs. The authors prove that using a tie-breaker based on perfect heuristics with this added cost results in optimal expansion, meaning A* expands the absolute minimum number of states necessary to find a solution.
Key Results and Evaluation
The effectiveness of these methods was tested across several benchmarks, including 50 instances of the "Free Parking" airport variant and over 1,700 instances from the International Planning Competition (IPC).
In the "Free Parking" variant, the Matching Heuristic solved 33 instances, outperforming state-of-the-art general planners like LM-cut (26) and iPDB (28). It also reduced computation time dramatically, from over 15,000 seconds to approximately 2,158 seconds. For general search, the cost-adapted tie-breaker ($h^{FF}_{+1}$) became a new state-of-the-art, solving 562 IPC instances and outperforming previous deterministic standards.
The Inconsistency Trap
A critical insight from the study is that the theoretical guarantee of optimal expansion relies on the heuristic being consistent. If a heuristic is inconsistent, the algorithm can still be misled into expanding redundant states, as illustrated by the search tree comparisons in the authors' analysis.
Conclusion
This work demonstrates that while the AI field strives for universal planners, domain-specific logic like bipartite matching remains a powerful tool for solving complex real-world problems. Furthermore, the introduction of cost-adapted tie-breaking provides a mathematically grounded method to minimize search effort in A*, particularly in challenging zero-cost domains.
Summary updated