Hierarchical Task Planning through Abstraction for a Mobile Robot

Abstract

본 논문에서는 "Hierarchical Planning based on Abstraction of World Elements and Operators" (HiPAWO)라고 불리는 월드 엘리먼트와 오퍼레이터의 추상화에 기반한 새로운 계층적 작업 계획 방식을 제안한다. 여기에서 월드 엘리먼트의 추상화는 추상회된 로봇 동작의 세분화를 위해서 사용되고, 오퍼레이터의 추상화는 복합 로봇 동작의 계층적 분해에 사용된다. 이와 같은 두가지 추상화의 상승적인 통합을 위해서 본 논문에서는 "Joint of Action Hierarchies"(JAH)에 기반한 계층적 도메인 이론을 구성하였다. 도메인 이론은 월드의 초기 상태, 각 로봇 동작들의 전제 조건과 영향 그리고 각 복합 로봇 동작이 어떤 부속 동작들로 구성되어 있는지에 대해 명세화한다. JAH는 의도적으로 다수의 중복된 로봇 동작들을 인접한 레벨의 도메인 이론에 포함시키고 그 중복된 로봇 동작들로 인하여 인접한 레벨간의 관계성을 부여한다. 이 관계성을 통해서 추상화된 로봇 동작의 세분화 과정이 복합 로봇 동작의 분해 과정을 통해 이루어짐으로써 작업계획 생성의 효율성이 증가한다. 실험에서는 HiPAWO와 월드 엘리먼트와 오퍼레이터의 추상화 방법을 독립적으로 사용한 기존의 작업 계획 방식의 작업 계획 생성 시간을 비교, 분석하였다. 그 결과 제안하는 작업계획 방식이 다른 두 작업 계획 방식보다 더 뛰어난 효율성을 보여주었다.; Planning is to find an executable sequence of actions that achieves a given goal when it is performed starting in a given state. To automate the process of planning requires a formal statement, or model, of the problem. In classical AI planning, model is a view of planning as a state transformation problem: the world is seen as a space of states and the task of the planner is to drive, through the application of actions, the world to a state satisfying the stated goal. The state space in any non-trivial planning problem is very large since it is generated by combination of actions and states. Therefore, planners that search this space is required to have efficient search strategy like refinement or heuristic. To solve task planning efficiently, classical planning approaches use abstraction of world elements or abstraction of operators independently, but we use both of them. ”Hierarchical Planning based on Abstraction of World Elements and Operators”(HiPAWO) is proposed for mobile robots task planning, where abstraction of world elements is used for refinement planning and abstraction of operators is used for hierarchical decomposition of compound actions. Especially, a hierarchical domain theory based on Joint of Action Hierarchy(JAH) is proposed to improve efficiency of planning, where a number of same actions are included in both adjacent hierarchical levels of domain theories to provide relationships between adjacent hierarchical levels. To show the validities of our proposed HiPAWO, experimental results are illustrated and will be compared with two other classical planning methods.