컴포넌트 서비스 기반의 휴리스틱 탐색 계획기 = A Heuristic Search Planner Based on Component Services

다국어 초록 (Multilingual Abstract)

Nowadays, one of the important functionalities required from robot task planners is to generate plans to compose existing component services into a new service. In this paper, we introduce the design and implementation of a heuristic search planner, JPLAN, as a kernel module for component service composition. JPLAN uses a local search algorithm and planning graph heuristics. The local search algorithm, EHC+, is an extended version of the Enforced Hill-Climbing(EHC) which have shown high efficiency applied in state-space planners including FF. It requires some amount of additional local search, but it is expected to reduce overall amount of search to arrive at a goal state and get shorter plans. We also present some effective heuristic extraction methods which are necessarily needed for search on a large state-space. The heuristic extraction methods utilize planning graphs that have been first used for plan generation in Graphplan. We introduce some planning graph heuristics and then analyze their effects on plan generation through experiments.

국문 초록 (Abstract)

최근 들어 로봇 작업 계획기에 요구되는 중요한 기능 중의 하나가 이미 존재하는 컴포넌트 서비스들을 결합하여 새로운 서비스로 조합해낼 수 있는 계획 기능이다. 본 논문에서는 이러한 컴포넌트 서비스 조합을 위한 커널모듈로 개발된 휴리스틱 탐색 계획기인 JPLAN의 설계와 구현에 대해 설명한다. JPLAN은 효율적인 상태 공간 탐색을 위해 지역 탐색 알고리즘과 계획 그래프 휴리스틱을 이용한다. 본 논문에서 제안하는 지역 탐색 알고리즘인 EHC+는 FF 등의 상태 공간 계획기에 적용되어 높은 효율성을 보인 Enforced Hill-Climbing (EHC)을 확장한 것이다. EHC+는 EHC에 비해 소량의 추가적인 지역 탐색을 필요로 하지만 목표 상태까지 전체 탐색 양을 줄일 수 있고 더 짧은 계획을 얻을 수있다. 또한 본 본문에서는 대규모 상태 공간 탐색에 필수적인 효과적인 휴리스틱 추출 방법을 제안한다. 본 논문에서 제안하는 휴리스틱 추출방법은 Graphplan에서 계획 생성을 위해 처음 제안된 계획 그래프를 이용한다. 본 논문에서는 이러한 계획 그래프 기반의 다양한 휴리스틱들을 소개하고, 이들이 계획 생성에 미치는 효과를 실험을 통해 분석해본다.

참고문헌 (Reference)

• 1 J. Hoffmann, "What Makes The Difference Between HSP and FF?" 2001
• 2 J.Peer, "Web Service Composition as AI Planning" University of St. Gallen 2005
• 3 D. Roman, "WSMO Working Draft V1.0"
• 4 J. Hoffmann, "The FF Planning System: Fast Plan Generation through Heuristic Search" 14 : 253-302, 2001
• 5 M. Klusch, "Semantic Web Service Composition Planning with OWLS-XPlan" AAAI 2005
• 6 B. Bonet, "Planning as Heuristic Search" 129 : 5-33, 2000
• 7 D.McDermott, "PDDL-the Planning Domain Definition Language" 1998
• 8 OWL Services Coalition, "OWL-S: Semantic Markup for Web Services"
• 9 H.S. Kim, "Mapping Semantic Web Service Descriptions to Planning Domain Knowledge" 2006
• 10 E. Sirin, "HTN Planning for Web Service Composition Using SHOP2" 1 (1): 377-396, 2004
• 11 B. Bonet, "HSP: Heuristic Search Planner" 21 (21): 2000
• 12 A. Blum, "Fast Planning through Planning Graph Analysis" 1995
• 13 A. Gerevini, "Fast Plan Adaptation through Planning Graphs: Local and Systematic Search Techniques" AAAI 2000
• 14 H. Geffner, "Classical, Probabilistic and Contingent Planning: Three Models, One Algorithm" 1998
• 15 M. Ghallab, "Automated Planning: Theory and Practice" Morgan Kaufmann 2004
• 16 A. Mediratta, "Applying Planning in Composition of Web Services with a User-Driven Contingent Planner,IBM Research Report RI 06002" 2006