Breadth-First Search vs. Restarting Random Walks for Escaping Uninformed Heuristic Regions
Created by
Haebom
Category
Empty
저자
Daniel Platnick, Dawson Tomasz, Eamon Earl, Sourena Khanzadeh, Richard Valenzano
개요
Greedy Best-First Search (GBFS) 및 Enforced Hill-Climbing (EHC)과 같은 탐욕적 검색 방법은 휴리스틱 지역 최소값 또는 고원과 같은 비정보 휴리스틱 영역(UHR)에 직면했을 때 어려움을 겪는 경우가 많습니다. 본 연구에서는 BrFS(Breadth-first search)와 RRWs(Restarting Random Walks)의 두 가지 UHR 탈출 방법을 이론적 및 경험적으로 비교합니다. 먼저 UHR 및 랜덤 워크 절차의 속성을 기반으로 BrFS 및 RRWs를 사용하여 UHR을 탈출하는 데 예상되는 런타임을 도출한 다음, RRWs가 BrFS보다 예상되는 런타임이 더 빠른 경우를 식별하기 위해 해당 결과를 사용합니다. 그런 다음 UHR을 탈출하기 위해 EHC를 BrFS를 사용하는 표준 EHC와 RRWs를 사용하는 EHC-RRW 변형을 비교하여 해당 방법을 평가합니다. EHC-RRW는 EHC가 이전에 효과적인 것으로 나타난 경우 강력한 예상 런타임 보장을 보여줍니다. 또한 PDDL 계획 벤치마크에서 이러한 접근 방식을 사용하여 UHR 탈출에 대한 상대적인 효과를 더 잘 이해하기 위한 실험을 수행합니다.
시사점, 한계점
•
BrFS와 RRWs를 사용하여 UHR 탈출에 대한 이론적 분석을 제공합니다.
•
UHR 탈출에 대한 RRWs가 BrFS보다 예상되는 런타임이 더 빠른 경우를 식별합니다.
•
EHC-RRW가 EHC에 비해 더 나은 예상 런타임을 제공함을 보여줍니다.
•
PDDL 계획 벤치마크에서 실험을 수행하여 방법의 상대적 효과를 평가합니다.
•
본 논문은 UHR 탈출에 대한 두 가지 방법의 효과를 비교하는 데 초점을 맞추며, 다른 UHR 탈출 방법과의 비교는 포함되지 않을 수 있습니다.
•
특정 UHR의 특성에 따라 성능이 달라질 수 있습니다.
•
PDDL 계획 벤치마크 외의 다른 문제 도메인에 대한 일반화 가능성이 추가로 연구되어야 합니다.