A Heuristic Search Algorithm for Solving First-Order MDPs

Eldar Karabaev, Olga SkvortsovaUAI 2005

TL;DR

This paper introduces FOLAO, a novel heuristic search algorithm that tackles the challenge of solving complex Markov Decision Processes (MDPs) represented in first-order logic. By combining first-order state abstraction with heuristic search, FOLAO avoids the computationally expensive step of propositionalizing the entire problem, leading to significantly improved scalability for large and infinite domains.

What Problem Does This Paper Address?

Decision-theoretic planning problems are often modeled using Markov Decision Processes (MDPs). While classical dynamic programming approaches can solve MDPs, they suffer from exponential growth in complexity with the number of state variables. To overcome this, researchers have developed techniques like state abstraction (representing sets of states) and heuristic search (focusing on reachable states).

However, many realistic planning domains are best described using first-order logic (First-Order MDPs or FOMDPs). Existing methods for solving FOMDPs often resort to "propositionalization," which involves converting the first-order representation into a propositional one by instantiating all variables with all possible domain objects. This process is highly impractical, as the number of propositions can explode with the size of the domain, making it impossible to solve large or infinite-state problems. This paper addresses this scalability issue by proposing a method that directly operates on first-order representations without propositionalization.

Methods

The core contribution of this paper is the FOLAO (First-Order LAO) algorithm. It combines two key ideas:

  • First-Order State Abstraction: Instead of propositionalizing the problem, FOLAO* uses a representation called Probabilistic Fluent Calculus (PFC). PFC allows for the representation of states and actions using first-order logic. "CN-states" in PFC represent clusters of real-world states, effectively creating an abstraction layer that avoids dealing with individual states. This is termed "first-order state abstraction."
  • Heuristic Search: Similar to the symbolic LAO algorithm, FOLAO uses an admissible heuristic function to guide its search. This heuristic helps focus computation on the states that are most likely to lead to a solution, further pruning the search space.

FOLAO* operates in two alternating phases:

  1. Policy Expansion: This phase uses a "succ-operator" (which works on abstract states) to determine reachable abstract states from the initial state, guided by the current partial policy.
  2. Dynamic Programming (FOVIA): A modified version of the first-order value iteration algorithm (FOVIA) is used to update the values of the reachable abstract states and refine the policy. FOVIA itself operates on abstract states, avoiding explicit state enumeration.

The novelty lies in applying state abstraction directly to the first-order representation before any propositionalization, and then performing heuristic search on these first-order abstract states.

Datasets

The paper evaluates its approach using problems from the colored Blocksworld (BW) scenario. This scenario is a variation of the classical Blocksworld where blocks are assigned colors, and goal specifications are given in first-order terms, requiring an arrangement of colors rather than specific block arrangements. This domain was part of the International Planning Competition (IPC'2004) and is particularly suited for first-order representations.

Key Insights and Ideas

  • Propositionalization is the Bottleneck: The paper strongly emphasizes that the primary limitation of prior FOMDP solvers is the computationally prohibitive step of propositionalization.
  • First-Order Abstraction is Powerful: By directly leveraging first-order logic and state abstraction (CN-states), the system can represent and reason about large state spaces without explicit enumeration.
  • Heuristic Search Enhances First-Order Planning: Combining heuristic search with first-order state abstraction provides a significant performance boost, as the search is guided towards promising abstract states.
  • Scalability to Infinite Domains: The approach is inherently designed to handle domains with infinitely many objects, a feat impossible for propositionalization-based methods.
  • PFC as a Compact Representation: The use of Probabilistic Fluent Calculus (PFC) offers a more compact representation of MDP components (value functions, policies) compared to propositional ADDs.

Key Results

The paper presents experimental results comparing their proposed FCPlanner (which implements FOLAO) against symbolic LAO on colored Blocksworld problems.

  • Performance Improvement: FCPlanner significantly outperforms symbolic LAO in terms of total time to solve problems, especially as the problem size (number of blocks) increases. For instance, symbolic LAO struggles with problems larger than seven blocks, while FCPlanner can handle up to seventeen blocks.
  • Heuristic Computation: While FCPlanner's heuristic computation time (H.time) is sometimes longer than symbolic LAO's, it covers a larger number of abstract states. The paper argues that these abstract states are "simpler" in symbolic LAO due to prior propositionalization.
  • Scalability: The results clearly demonstrate that FCPlanner scales much better than symbolic LAO* on larger problems, a direct consequence of avoiding propositionalization.
  • Competition Success: FCPlanner achieved competitive results in the IPC'2004 probabilistic track, outperforming other planners on colored BW problems.

Limitations and Future Work

  • PFC Expressiveness: The current version of PFC is less expressive than some other first-order logics (like Situation Calculus), particularly concerning universally-closed goal descriptions which might still require some form of groundization.
  • Optimization Techniques: The authors express interest in exploring how optimization techniques used in modern propositional planners can be integrated with first-order state abstraction.
  • Future Competitions: They aim to tackle problems with partially defined goal/initial states and domains with infinitely many objects in future competitions.
  • PFC Language Extensions: Investigating extensions to the PFC language and understanding the trade-off between its expressive power and the tractability of FOMDP solutions is a key future direction.

Summary updated

BibTeX
@inproceedings{karabaev2005heuristic,
  author = {Eldar Karabaev and Olga Skvortsova},
  title = {{A Heuristic Search Algorithm for Solving First-Order MDPs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2005},
}
Figure