We propose a hierarchical planning algorithm that efficiently finds the optimal plan for the given planning problem. A key challenge to the hierarchical planning approach is that a higher-level plan may fail to properly guide the planning at the lower level. To handle this we view this problem as the balancing problem between exploration and exploitation and use the Monte-Carlo tree search algorithm to efficiently focus on seemingly promising high-level plans. We also present a theoretical analysis on the optimality of our algorithm and show that under certain conditions, our algorithm is guaranteed to find the optimal plan. We showed that our method outperforms existing algorithms in the continuous path planning domain.
본 논문에서는 주어진 계획 문제에 대해 최적의 계획을 효율적으로 찾는 계층적 계획 알고리즘을 제안한다. 계층적 계획 접근 방식의 핵심 과제는 상위 수준의 계획이 하위 수준의 계획을 제대로 안내하지 못할 수 있다는 것인데, 이를 해결하기 위해 우리는 이 문제를 탐색과 활용 사이의 균형 문제로 보고 몬테 카를로 트리 탐색 알고리즘을 사용하여 유망해 보이는 높은 수준의 계획에 효율적으로 집중하는 방법을 제시했다. 또한 알고리즘이 최적의 경로를 찾을 수 있는지에 대한 이론적 분석을 제시하고 특정 조건에서 알고리즘이 최적의 계획을 찾도록 보장됨을 증명했다. 그리고 연속 행동 공간 상의 경로 탐색 문제에서 본 논문에서 제안한 알고리즘이 기존 알고리즘보다 성능이 우수함을 실험을 통해 확인했다.
