Learning Heuristic Functions in Classical Planning Master Thesis

The goal of classical domain-independent planning is to find a sequence of actions that lead from a given initial state to a goal state that satisfies some goal criteria. Most planning systems use heuristic search algorithms to find such a sequence of actions. A critical part of the heuristic search … See more

The goal of classical domain-independent planning is to find a sequence of actions that lead from a given initial state to a goal state that satisfies some goal criteria. Most planning systems use heuristic search algorithms to find such a sequence of actions. A critical part of the heuristic search is the heuristic function. In order to find a sequence of actions from an initial state to a goal state efficiently, this heuristic function has to guide the search towards the goal. It is difficult to create such an efficient heuristic function. Arfaee et al. show that it is possible to improve a given heuristic function by applying machine learning techniques on a single domain in the context of heuristic search. To achieve this improvement of the heuristic function, they propose a bootstrap learning approach that subsequently improves the heuristic function.In this thesis we will introduce a technique to learn heuristic functions that can be used in classical domain-independent planning based on the bootstrap-learning approach introduced by Arfaee et al. In order to evaluate the performance of the learned heuristic functions, we have implemented a learning algorithm for the Fast Downward planning system. The experiments have shown that a learned heuristic function generally decreases the number of explored states compared to blind-search. The total time to solve a single problem increases because the heuristic function has to be learned before it can be applied.

See less