계층적 작업 망 계획을 위한 변환-기반의 접근법
A Translation-based Approach to Hierarchical Task Network Planning
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
계층적 작업 망(HTN) 계획방식은 문제영역의 고유한 제어지식을 효과적으로 이용할 수 있는 대표적인 계획방식으로서, 오랫동안 복잡도가 높은 실세계 응용분야들에 널리 이용되어 왔다. 하지만 아직은 HTN 계획방식에 대한 이론적 정형화와 표준화가 미흡하며, HTN 계획기들 사이에도 원리와 성능 면에서 약간의 차이를 보이고 있다. 본 논문에서는 HTN 계획 영역 명세를 표준 PDDL 명세로 변환하는 효과적인 방법을 제시한다. 이 방법의 주된 장점은 표준 PDDL 명세를 이해할 수 있는 많은 영역-독립적인 고전적 계획기들에서도 HTN 명세에 포함된 영역 고유의 제어지식을 효과적으로 이용할 수 있다는 점이다. 본 논문에서는 블록쌓기, 로봇 심부름, 하노이 탑 등 3 가지 다른 문제영역에 HTN 명세변환 방법을 적용해보고, 전향-추론 휴리스틱 상태-공간 계획기인 FF를 이용한 실험을 통해 변환-기반의 HTN 계획방식의 효율성을 분석해본다.
Abstract
Hierarchical Task Network(HTN) planning, a typical planning method for effectively taking advantage of domain-specific control knowledge, has been widely used in complex real applications for a long time. However, it still lacks theoretical formalization and standardization, and so there are some differences among existing HTN planners in terms of principle and performance. In this paper, we present an effective way to translate a HTN planning domain specification into the corresponding standard PDDL specification. Its main advantage is to allow even many domain-independent classical planners to utilize domain-specific control knowledge contained in the HTN specifications. In this paper, we try our translation-based approach to three different domains such as Blocks World, Office Delivery, Hanoi Tower, and then conduct some experiments with a forward-chaining heuristic state-space planner, FF, to analyze the efficiency of our approach.
참고문헌 (11)
- 김인철, "컴포넌트 서비스 기반의 휴리스틱 탐색 계획기", 정보처리학회논문지B, 15(2), pp.159~170 (2008), 한국정보처리학회
- M. Ghallab, "Automated Planning: Theory and Practice" (2004), Morgan Kaufmann
- K. Currie, "O-Plan: The Open Planning Architecture", Artificial Intelligence, 52(1), pp.49~86 (1991)
- D. Wilkins, "Practical Planning: Extending the Classical AI Planning Paradigm" (1988), Morgan Kaufmann
- D. Nau, "SHOP2: An HTN Planning System", JAIR, 20, pp.379~404 (2003)
- A. Gerevini, "Combining Domain-Independent Planning and HTN Planning: The Duet Planner", Proceedings of ECAI-08, pp.573~577 (2008)
- B.Srivastava, "A Limited Extension of PDDL for Planning with Non-Primitive Actions", Proceedings of ICAPS-03 Workshop on Planning Competition (2003)
- R. Alford, "Translating HTNs to PDDL: A Small Amount of Domain Knowledge Can Go a Long Way", Proceedings of IJCAI-09, pp.1629~1634 (2009)
- J. Hoffmann, "The FF Planning System: Fast Plan Generation through Heuristic Search", JAIR, 14, pp.253~302 (2001)
- J. Baier, "Exploiting Procedural Domain Control Knowledge in State-of-the-Art Planners", Proceedings of ICAPS-07 (2007)
- A. Albore, "A Translation-based Approach to Contingent Planning", Proceedings of IJCAI-09, pp.1623~1628 (2009)