컴포넌트 서비스 기반의 휴리스틱 탐색 계획기
A Heuristic Search Planner Based on Component Services
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
최근 들어 로봇 작업 계획기에 요구되는 중요한 기능 중의 하나가 이미 존재하는 컴포넌트 서비스들을 결합하여 새로운 서비스로 조합해낼 수 있는 계획 기능이다. 본 논문에서는 이러한 컴포넌트 서비스 조합을 위한 커널모듈로 개발된 휴리스틱 탐색 계획기인 JPLAN의 설계와 구현에 대해 설명한다. JPLAN은 효율적인 상태 공간 탐색을 위해 지역 탐색 알고리즘과 계획 그래프 휴리스틱을 이용한다. 본 논문에서 제안하는 지역 탐색 알고리즘인 EHC+는 FF 등의 상태 공간 계획기에 적용되어 높은 효율성을 보인 Enforced Hill-Climbing (EHC)을 확장한 것이다. EHC+는 EHC에 비해 소량의 추가적인 지역 탐색을 필요로 하지만 목표 상태까지 전체 탐색 양을 줄일 수 있고 더 짧은 계획을 얻을 수 있다. 또한 본 본문에서는 대규모 상태 공간 탐색에 필수적인 효과적인 휴리스틱 추출 방법을 제안한다. 본 논문에서 제안하는 휴리스틱 추출 방법은 Graphplan에서 계획 생성을 위해 처음 제안된 계획 그래프를 이용한다. 본 논문에서는 이러한 계획 그래프 기반의 다양한 휴리스틱들을 소개하고, 이들이 계획 생성에 미치는 효과를 실험을 통해 분석해본다.
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.
참고문헌 (16)
- A. Blum, "Fast Planning through Planning Graph Analysis", Proc. of IJCAI-95 (1995)
- B. Bonet, "HSP: Heuristic Search Planner", AI Magazine, 21(2) (2000)
- B. Bonet, "Planning as Heuristic Search", Journal of Artificial Intelligence, 129, pp.5~33 (2000)
- PDDL-the Planning Domain Definition Language, "D.McDermott", ~ (1998)
- H. Geffner, "Classical, Probabilistic and Contingent Planning: Three Models, One Algorithm", Proceedings of AIPS'98 Workshop on Planning as Combinatorial Search (1998)
- A. Gerevini, "Fast Plan Adaptation through Planning Graphs: Local and Systematic Search Techniques", Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems (AIPS-00) (2000), AAAI
- M. Ghallab, "Automated Planning: Theory and Practice" (2004), Morgan Kaufmann
- J. Hoffmann, "The FF Planning System: Fast Plan Generation through Heuristic Search", Journal of Artificial Intelligence Research, 14, pp.253~302 (2001)
- J. Hoffmann, "What Makes The Difference Between HSP and FF?", of IJCAI-2001 (2001)
- H.S. Kim, "Mapping Semantic Web Service Descriptions to Planning Domain Knowledge", Proceedings of WC-06 (2006)
- M. Klusch, "Semantic Web Service Composition Planning with OWLS-XPlan", Proceedings of the 1st Intl. AAAI Fall Symposium on Agents and the Semantic Web (2005), AAAI
- Applying Planning in Composition of Web Services with a User-Driven Contingent Planner,IBM Research Report RI 06002, "A. Mediratta", ~ (2006)
- OWL Services Coalition, "OWL-S: Semantic Markup for Web Services", ~ (2003)
- J.Peer, "Web Service Composition as AI Planning" (2005), University of St. Gallen
- D. Roman, "WSMO Working Draft V1.0", ~ (2004)
- E. Sirin, "HTN Planning for Web Service Composition Using SHOP2", J. Web Sem, 1(4), pp.377~396 (2004)