조합 탐색을 위한 경험적 허용 가능 신경 휴리스틱 학습

루빅스 큐브(Rubik's Cube), 슬라이딩 타일 퍼즐(sliding tile puzzles), 라이츠 아웃(Lights Out)과 같은 조합 퍼즐(combinatorial puzzles)에서 최적의 솔루션 경로를 찾는 것은 인공지능(AI) 분야의 고전적인 과제로 남아 있습니다. A*와 같은 휴리스틱 탐색(Heuristic search) 알고리즘은 실제 남은 비용(cost-to-go)을 절대 과대평가하지 않는 허용 가능한 휴리스틱(admissible heuristic)을 사용할 때만 경로의 최적성(optimality)을 보장합니다. DeepCubeA와 같은 심층 강화학습 (Deep reinforcement learning (RL)) 방법론은 비용-투-고 (cost-to-go) 휴리스틱을 근사하도록 심층 신경망을 학습시킵니다. 그러나 표준 평균 제곱 오차 (mean-squared error (MSE)) 학습은 정기적으로 과대평가(overestimation)를 발생시켜, 허용 가능성(admissibility)을 위반하고 솔루션의 최적성을 저해합니다. 본 논문에서는 검증 보정된(validation-calibrated) 허용 가능한 신경 휴리스틱을 학습하기 위한 일반화 가능한 프레임워크를 소개합니다. 우리는 과대평가에 페널티를 부여하기 위해 비대칭 손실 함수(Asymmetric Loss function)와 결합된 과소평가형 허용 가능 벨만 연산자(Admissible Bellman Operator)를 사용하여 가치 네트워크(value network)를 학습시킵니다. 잔여 신경 함수 근사 오차(residual neural function approximation errors)를 고려하기 위해, 우리는 검증 스크램블(validation scrambles)에 대해 계산된 사후 보정 안전 오프셋(post-hoc calibration safety offset)을 제안합니다. 우리는 우리의 보정된 신경 휴리스틱이 평가 프로토콜 하에서 관찰된 허용 가능성 위반이 없음을 입증하였으며, 표준 분석적 베이스라인(analytical baselines)과 비교했을 때 2x2 루빅스 큐브에서 탐색 노드 확장(search node expansions)을 최대 83.0%, 3x3 라이츠 아웃 그리드에서 19.9%, 8-퍼즐(8-Puzzle)에서 1.9%까지 줄이면서 실제 경로 최적성을 유지함을 보여줍니다.