A Heuristic Search Algorithm for Solving First-Order MDPs
We present a heuristic search algorithm for solving first-order MDPs (FOMDPs). Our approach combines first-order state abstraction that avoids evaluating states individually, and heuristic search that avoids evaluating all states. Firstly, we apply state abstraction directly on the FOMDP avoiding propositionalization. Such kind of abstraction is referred to as firstorder state abstraction. Secondly, guided by an admissible heuristic, the search is restricted only to those states that are reachable from the initial state. We demonstrate the usefullness of the above techniques for solving FOMDPs on a system, referred to as FCPlanner, that entered the probabilistic track of the International Planning Competition (IPC'2004).
Code (0)
등록된 구현이 없습니다.
Tasks
Heuristic SearchSimilar Papers 제목 키워드 기반
A*+BFHS: A Hybrid Heuristic Search Algorithm
We present a new algorithm A*+BFHS for solving problems with unit-cost operators where A* and IDA* fail due to memory limitations and/or the existence of many distinct paths between the same pair of nodes. A*+BFHS is bas…
Heuristic SearchA Comparative Study of Meta-heuristic Algorithms for Solving Quadratic Assignment Problem
Quadratic Assignment Problem (QAP) is an NP-hard combinatorial optimization problem, therefore, solving the QAP requires applying one or more of the meta-heuristic algorithms. This paper presents a comparative study betw…
Combinatorial OptimizationAvoiding and Escaping Depressions in Real-Time Heuristic Search
Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is inaccurate compared to the actual cost to re…
Heuristic SearchGame Solving with Online Fine-Tuning
Game solving is a similar, yet more difficult task than mastering a game. Solving a game typically means to find the game-theoretic value (outcome given optimal play), and optionally a full strategy to follow in order to…
Board GamesLearning Variable Ordering Heuristics for Solving Constraint Satisfaction Problems
Backtracking search algorithms are often used to solve the Constraint Satisfaction Problem (CSP). The efficiency of backtracking search depends greatly on the variable ordering heuristics. Currently, the most commonly us…
Deep Reinforcement LearningGraph Neural NetworkReinforcement Learning