OREGON STATE UNIVERSITY

You are here

Iterative Learning of Weighted Rule Sets for Greedy Search

TitleIterative Learning of Weighted Rule Sets for Greedy Search
Publication TypeConference Paper
Year of Publication2010
AuthorsXu, Y., A. Fern, and S. Yoon
Conference NameInternational Conference on Automated Planning and Scheduling (ICAPS-10)
Date Published05/2010
Conference LocationMenlo Park, CA
Abstract

Greedy search is commonly used in an attempt to generate solutions quickly at the expense of completeness and optimality. In this work, we consider learning sets of weighted action-selection rules for guiding greedy search with application to automated planning. We make two primary contributions over prior work on learning for greedy search. First, we introduce weighted sets of action-selection rules as a new form of control knowledge for greedy search. Prior work has shown the utility of action-selection rules for greedy search, but has treated the rules as hard constraints, resulting in brittleness. Our weighted rule sets allow multiple rules to vote, helping to improve robustness to noisy rules. Second, we give a new iterative learning algorithm for learning weighted rule sets based on RankBoost, an efficient boosting algorithm for ranking. Each iteration considers the actual performance of the current rule set and directs learning based on the observed search errors. This is in contrast to most prior approaches, which learn control knowledge independently of the search process. Our empirical results have shown significant promise for this approach in a number of domains.

Notes

Best Paper Runner-Up Award