A Method for Automated Definition of Abstraction Hierarchy in Hierarchical Problem Solving System

• NISHIMURA Kazuhiko

  Systems and Software Engineering Laboratory, Toshiba Corporation

• MATSUMOTO Kazunori

  Systems and Software Engineering Laboratory, Toshiba Corporation

Bibliographic Information

Other Title

• 階層的問題解決システムにおける抽象階層の決定方法

Abstract

In this paper, we describe techniques to improve efficiency of problem solving systems. Abstraction has been expected to be one of the most applicable method for that purpose. ABSTRIPS is a typical problem solver which introduces the idea of abstraction into STRIPS. It solves a problem hierarchically by considering relative importance of operator's preconditions. That is, firstly ABSTRIPS solves the problem in the most abstract space, and then it successively embodies the answer. We have to assign critical values to all preconditions before abstract problem solving. These values are used to define abstraction hierarchy. Some heuristics are proposed to assign them. However we can not expect fully automatic assigning, that is, user assistance is required. We propose new method to assign the critical values automatically. This method consists of following four stages: (1) generating operator taxonomic hierarchies from a set of primitive operators. In this case, two operators which share one or more literals on their add lists are allocated in the same hierarchy. (2) assigning provisional critical values to operator's preconditions according to their locations in the hierarchy. (3) analyzing difficulty of achieving each precondition, and (4) determining final critical values by considering both provisional values and difficulty. We have been implemented ABSTRIPS-like problem solver to show the effectiveness of our method. Final part of this paper, we investigate the exprimental results and identify some problems to be solved in the future works.

Journal

• Journal of the Japanese Society for Artificial Intelligence

  Journal of the Japanese Society for Artificial Intelligence 6 (5), 701-709, 1991-09-01

  The Japanese Society for Artificial Intelligence

Keywords

• abstraction
• hierarchical planning
• problem solving

Details

• CRID: 1390567172582005504
• NII Article ID: 110002807478
• NII Book ID: AN10067140
• DOI: 10.11517/jjsai.6.5_701
• ISSN: 24358614
• ISSN: 21882266
• Text Lang: ja
• Data Source:
  • JaLC
  • CiNii Articles
• Abstract License Flag: Disallowed