정보과학회 논문지 C : 컴퓨팅의 실제
Current Result Document :
| 한글제목(Korean Title) |
부분적으로 관측가능하고 비결정적인 계획문제를 풀기 위한 휴리스틱 탐색 알고리즘 |
| 영문제목(English Title) |
A Heuristic Search Algorithm for Solving Partially-Observable, Non-Deterministic Planning Problems |
| 저자(Author) |
김현식
박찬영
김인철
Hyunsik Kim
Chanyoung Park
Incheol Kim
|
| 원문수록처(Citation) |
VOL 15 NO. 10 PP. 0786 ~ 0790 (2009. 10) |
한글내용
(Korean Abstract) |
본 논문에서는 불완전한 인식과 비결정적 동작을 함께 포함한 조건부 계획문제를 풀기 위한 새로운 휴리스틱 탐색 알고리즘 HSCP를 소개한다. HSCP 탐색 알고리즘은 하나의 완전한 해 그래프가 구해질 때까지 AND-OR 탐색시도를 반복한다. HSCP 알고리즘의 AND-OR 탐색시도는, 기존의 휴리스틱 AND-OR 탐색 알고리즘들인 AO*나 LAO*와는 달리, 오직 하나의 후보 해 그래프를 확장하는데 집중한다. 또한, 실시간 동적 프로그래밍 알고리즘들인 RTDP와 LRTDP와는 달리, 모든 상태들의 가치 평가치가 수렴할 때까지 미루지 않고 바로 해를 구한다. 따라서 HSCP 탐색 알고리즘은 양질의 조건부 계획을 매우 효율적으로 구해줄 수 있다는 장점이 있다.
|
영문내용
(English Abstract) |
In this paper, we present a new heuristic search algorithm, HSCP, that can solve conditional/contingent planning problems with nondeterministic actions as well as partial observations. The algorithm repeats its AND-OR search trials until a complete solution graph can be found. However, unlike existing heuristic AND-OR search algorithms such as AO* and LAO*, the AND-OR search trial conducted by HSCP concentrates on only a single candidate of solution subgraphs to expand it into a complete solution graph. Moreover, unlike real-time dynamic programming algorithms such as RTDP and LRTDP, the AND-OR search trial of HSCP finds a solution immediately when it possible without delaying it until the estimated value of every state converges. Therefore, the HSCP search algorithm has the advantage that it can find a sub-optimal conditional plan very efficiently. |
| 키워드(Keyword) |
조건부 계획문제
휴리스틱 탐색
믿음 상태
Conditional Planning Problem
Heuristic Search
Belief State
|
| 파일첨부 |
PDF 다운로드
|
