MIME-Version: 1.0 Server: CERN/3.0 Date: Tuesday, 07-Jan-97 15:56:31 GMT Content-Type: text/html Content-Length: 11451 Last-Modified: Wednesday, 28-Aug-96 17:38:15 GMT Speedup Learning

Speedup Learning/Learning for Planning

To view a paper, click on the open book image.

  1. Integrating EBL and ILP to Acquire Control Rules for Planning
    Tara A. Estlin and Raymond J. Mooney
    Proceedings of the Third International Workshop on Multi-Strategy Learning, pp. 271-279, Harpers Ferry, WV, May 1996. (MSL-96).

    Most approaches to learning control information in planning systems use explanation-based learning to generate control rules. Unfortunately, EBL alone often produces overly complex rules that actually decrease planning efficiency. This paper presents a novel learning approach for control knowledge acquisition that integrates explanation-based learning with techniques from inductive logic programming. EBL is used to constrain an inductive search for selection heuristics that help a planner choose between competing plan refinements. SCOPE is one of the few systems to address learning control information in the newer partial-order planners. Specifically, SCOPE learns domain-specific control rules for a version of the UCPOP planning algorithm. The resulting system is shown to produce significant speedup in two different planning domains.

  2. Multi-Strategy Learning of Search Control for Partial-Order Planning
    Tara A. Estlin and Raymond J. Mooney
    Proceedings of the Thirteenth National Conference on Aritificial Intelligence, pp. 843-848, Portland, OR, August, 1996. (AAAI-96)

    Most research in planning and learning has involved linear, state-based planners. This paper presents SCOPE, a system for learning search-control rules that improve the performance of a partial-order planner. SCOPE integrates explanation-based and inductive learning techniques to acquire control rules for a partial-order planner. Learned rules are in the form of selection heuristics that help the planner choose between competing plan refinements. Specifically, SCOPE learns domain-specific control rules for a version of the UCPOP planning algorithm. The resulting system is shown to produce significant speedup in two different planning domains.

  3. Integrating Explanation-Based and Inductive Learning Techniques to Acquire Search-Control for Planning
    Tara A. Estlin
    Ph.D. proposal, Department of Computer Sciences, University of Texas at Austin, 1996.

    Planning systems have become an important tool for automating a wide variety of tasks. Control knowledge guides a planner to find solutions quickly and is crucial for efficient planning in most domains. Machine learning techniques enable a planning system to automatically acquire domain-specific search-control knowledge for different applications. Past approaches to learning control information have usually employed explanation-based learning (EBL) to generate control rules. Unfortunately, EBL alone often produces overly complex rules that actually decrease rather than improve overall planning efficiency. This paper presents a novel learning approach for control knowledge acquisition that integrates explanation-based learning with techniques from inductive logic programming. In our learning system SCOPE, EBL is used to constrain an inductive search for control heuristics that help a planner choose between competing plan refinements. SCOPE is one of the few systems to address learning control information for newer, partial-order planners. Specifically, this proposal describes how SCOPE learns domain-specific control rules for the UCPOP planning algorithm. The resulting system is shown to produce significant speedup in two different planning domains, and to be more effective than a pure EBL approach.

    Future research will be performed in three main areas. First, SCOPE's learning algorithm will be extended to include additional techniques such as constructive induction and rule utility analysis. Second, SCOPE will be more thoroughly tested; several real-world planning domains have been identified as possible testbeds, and more in-depth comparisons will be drawn between SCOPE and other competing approaches. Third, SCOPE will be implemented in a different planning system in order to test its portability to other planning algorithms. This work should demonstrate that machine-learning techniques can be a powerful tool in the quest for tractable real-world planning.

  4. Hybrid Learning of Search Control for Partial-Order Planning
    Tara A. Estlin and Raymond J. Mooney
    New Directions in AI Planning, M. Ghallab and A. Milani, Eds, IOS Press, 1996, pp. 129-140.

    This paper presents results on applying a version of the DOLPHIN search-control learning system to speed up a partial-order planner. DOLPHIN integrates explanation-based and inductive learning techniques to acquire effective clause-selection rules for Prolog programs. A version of the UCPOP partial-order planning algorithm has been implemented as a Prolog program and DOLPHIN used to automatically learn domain-specific search control rules that help eliminate backtracking. The resulting system is shown to produce significant speedup in several planning domains.

  5. Integrating ILP and EBL
    Raymond J. Mooney and John M. Zelle
    SIGART Bulletin, Volume 5, number 1, Jan. 1994, pp 12-21.

    This paper presents a review of recent work that integrates methods from Inductive Logic Programming (ILP) and Explanation-Based Learning (EBL). ILP and EBL methods have complementary strengths and weaknesses and a number of recent projects have effectively combined them into systems with better performance than either of the individual approaches. In particular, integrated systems have been developed for guiding induction with prior knowledge (ML-SMART, FOCL, GRENDEL) refining imperfect domain theories (FORTE, AUDREY, Rx), and learning effective search-control knowledge (AxA-EBL, DOLPHIN).

  6. Learning Search-Control Heuristics for Logic Programs: Applications to Speedup Learning and Language Acquisition
    John M. Zelle
    Ph.D. proposal, Department of Computer Sciences, University of Texas at Austin, 1993.

    This paper presents a general framework, learning search-control heuristics for logic programs, which can be used to improve both the efficiency and accuracy of knowledge-based systems expressed as definite-clause logic programs. The approach combines techniques of explanation-based learning and recent advances in inductive logic programming to learn clause-selection heuristics that guide program execution. Two specific applications of this framework are detailed: dynamic optimization of Prolog programs (improving efficiency) and natural language acquisition (improving accuracy). In the area of program optimization, a prototype system, DOLPHIN, is able to transform some intractable specifications into polynomial-time algorithms, and outperforms competing approaches in several benchmark speedup domains. A prototype language acquisition system, CHILL, is also described. It is capable of automatically acquiring semantic grammars, which uniformly incorprate syntactic and semantic constraints to parse sentences into case-role representations. Initial experiments show that this approach is able to construct accurate parsers which generalize well to novel sentences and significantly outperform previous approaches to learning case-role mapping based on connectionist techniques. Planned extensions of the general framework and the specific applications as well as plans for further evaluation are also discussed.

  7. Combining FOIL and EBG to Speed-Up Logic Programs
    John M. Zelle and Raymond J. Mooney
    Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, pp. 1106-111, Chambery, France, 1993. (IJCAI-93)

    This paper presents an algorithm that combines traditional EBL techniques and recent developments in inductive logic programming to learn effective clause selection rules for Prolog programs. When these control rules are incorporated into the original program, significant speed-up may be achieved. The algorithm is shown to be an improvement over competing EBL approaches in several domains. Additionally, the algorithm is capable of automatically transforming some intractable algorithms into ones that run in polynomial time.

  8. Speeding-up Logic Programs by Combining EBG and FOIL
    John M. Zelle and Raymond J. Mooney
    Proceedings of the 1992 Machine Learning Workshop on Knowledge Compilation and Speedup Learning, Aberdeen Scotland, July 1992.

    This paper presents an algorithm that combines traditional EBL techniques and recent developments in inductive logic programming to learn effective clause selection rules for Prolog programs. When these control rules are incorporated into the original program, significant speed-up may be achieved. The algorithm produces not only EBL-like speed up of problem solvers, but is capable of automatically transforming some intractable algorithms into ones that run in polynomial time.


    estlin@cs.utexas.edu