Handling Infinite Domain Parameters in Planning Through Best-First Search with Delayed Partial Expansions

이 논문은 제어 매개변수를 검색 공간의 추가 제약이 아닌 의사결정점으로 명시적으로 다루고, 지연된 부분 확장을 활용한 휴리스틱 탐색 알고리즘을 제안하여 무한한 도메인 파라미터를 가진 계획 문제를 해결하는 새로운 방법을 제시합니다.

핵심

이 논문은 로봇이나 AI 가 복잡한 미션을 수행할 때, "얼마만큼" 힘을 써야 하는지 같은 무한한 선택지를 어떻게 효율적으로 찾아내는지에 대한 새로운 방법을 제안합니다.

기존의 AI 계획 (Planning) 은 주로 "A 를 할지, B 를 할지"처럼 유한한 선택지만 다뤘습니다. 하지만 현실 세계에서는 "속도를 1.5 로 할지, 1.53 으로 할지"처럼 **무한히 많은 숫자 (연속적인 값)**를 결정해야 하는 경우가 많습니다. 이걸 '제어 파라미터 (Control Parameters)'라고 부르는데, 기존 방법들은 이걸 마치 '규칙'처럼 처리해서 검색 공간을 좁히는 데 그쳤습니다.

저자들은 이걸 **'결정해야 할 중요한 선택'**으로 다시 정의하고, 무한한 공간에서도 빠르고 정확하게 답을 찾을 수 있는 새로운 알고리즘 S-BFS를 개발했습니다.

이해하기 쉽게 세 가지 핵심 비유로 설명해 드릴게요.

---

1. 문제 상황: "무한한 레시피"와 "시간 부족"

상상해 보세요. 당신이 거대한 요정 식당을 운영한다고 칩시다.

• 기존 방식 (기존 AI): 요리를 할 때 "소금 1g, 2g, 3g..."처럼 정해진 숫자만 넣는 레시피만 따릅니다. 만약 "소금 1.53g"이 필요하면, 그걸 미리 정해둔 리스트에 없으면 못 찾습니다.
• 새로운 문제: 하지만 손님이 "소금 1.5342g"을 원한다면? 소금의 양은 무한히 세분화될 수 있습니다. 모든 가능한 양 (0.0001g, 0.0002g...) 을 다 시도해 보는 건 우주 나이만큼 걸려서 불가능합니다.

2. 해결책: "미리 다 먹어보지 않는" 전략 (지연된 부분 확장)

저자들이 제안한 S-BFS 알고리즘은 이 문제를 이렇게 해결합니다.

비유: "맛있는 요리를 찾기 위해 모든 재료를 다 섞어보지 않는 요리사"

일반적인 검색 알고리즘은 한 단계에서 가능한 모든 경우 (소금 1g, 1.1g, 1.2g...) 를 다 만들어서 비교합니다. 하지만 무한한 경우의 수라면 이 방식은 멈춰버립니다.

이 새로운 알고리즘은 두 가지 마법을 사용합니다.

마법 1: "샘플링 (Sampling)" - 무작위 시식

"모든 소금 양을 다 섞어볼 순 없으니, 가장 유망해 보이는 몇 가지만 먼저 시식해 보자!"라고 생각합니다.

• 예를 들어, 소금 양을 결정할 때 0.5g, 1.0g, 1.5g 처럼 임의의 몇 가지만 뽑아봅니다.
• 이걸 샘플링이라고 합니다. 모든 것을 다 보지 않고, 대표성 있는 몇 가지만 골라보는 거죠.

마법 2: "지연된 부분 확장" - 다시 돌아오기

이게 핵심입니다.

1. 요리를 하나 시식해 봤습니다 (예: 소금 1.0g).
2. 그 결과가 나쁘지 않아서 바로 다음 단계로 넘어가지 않습니다.
3. 대신, 그 요리를 다시 테이블에 올려두고, "아직 다른 소금 양 (예: 1.1g) 도 시도해 볼 가치가 있나?"라고 다시 생각합니다.
4. 나중에 다른 요리 (다른 소금 양) 를 시식해 봤는데, 그 결과가 더 좋다면 다시 돌아와서 그 요리를 더 자세히 파고듭니다.

이 방식은 "한 번에 모든 길을 다 열어두지 않고, promising(유망한) 길만 조금씩 열어보고, 나중에 다시 돌아와서 더 깊이 파는" 전략입니다. 이를 **'지연된 부분 확장 (Delayed Partial Expansions)'**이라고 합니다.

3. 왜 이 방식이 좋은가요? (완전성과 효율성)

• 완전성 (Completeness): "무한한데 어떻게 다 찾을 수 있죠?"라고 물으실 수 있습니다. 이 알고리즘은 **확률적으로 완전 (Probabilistic Completeness)**합니다.
  • 비유: "우주에 있는 모든 별을 한 번에 다 볼 순 없지만, 무한한 시간이 주어진다면, 어떤 별이든 결국 한 번은 보게 될 것"이라는 원리입니다. 시간이 무한히 흐르면, 우리가 원하는 정답 (최적의 소금 양) 을 100% 찾을 수 있다는 보장을 수학적으로 증명했습니다.
• 효율성: 모든 경우의 수를 다 보지 않기 때문에, 시간과 메모리를 아껴서 더 빠르게 답을 찾습니다.

4. 실험 결과: 기존 방법보다 낫다

저자들은 이 알고리즘을 실제 테스트해 보았습니다.

• 비교 대상: 기존에 쓰이던 방법 (NextFLAP) 과 무작위 탐색 (MCTS) 이었습니다.
• 결과:
  • NextFLAP은 작은 문제에서는 잘 작동하지만, 문제가 복잡해지면 답을 못 찾거나 시간이 너무 오래 걸렸습니다. (규칙에 너무 얽매임)
  • MCTS는 무작위 탐색이라서 답을 거의 찾지 못했습니다.
  • 새로운 S-BFS는 더 많은 문제를 해결했고, 특히 복잡한 상황에서 기존 방법들보다 훨씬 강력했습니다.

요약

이 논문은 **"무한한 선택지가 있는 세상에서 AI 가 어떻게 효율적으로 결정을 내릴까?"**에 대한 해답을 제시합니다.

"모든 가능성을 한 번에 다 확인하려 하지 말고, 유망한 것들을 조금씩 뽑아보고 (샘플링), 나중에 다시 돌아와서 더 깊이 파고드는 (지연된 부분 확장) 전략을 쓰면, 무한한 세상에서도 정답을 찾을 수 있다."

이 방법은 로봇이 물건을 잡을 때 힘의 세기를 조절하거나, 드론이 비행 경로를 미세하게 조정할 때처럼, 숫자가 무한히 변할 수 있는 현실적인 문제를 해결하는 데 큰 도움이 될 것으로 기대됩니다.

기술 요약

이 논문은 자동 계획 (Automated Planning) 분야에서 **무한한 도메인 (Infinite Domain)**을 가진 제어 매개변수 (Control Parameters) 를 효율적으로 처리하기 위한 새로운 탐색 알고리즘을 제안합니다. 기존 방법론들이 제어 매개변수를 제약 조건으로 간주하여 암묵적으로 처리한 반면, 이 연구는 이를 명시적인 **결정 지점 (Decision Points)**으로 취급하여 체계적인 탐색을 수행하는 방식을 제시합니다.

주요 내용은 다음과 같습니다.

1. 문제 정의 (Problem Definition)

• 배경: 전통적인 자동 계획은 유한한 객체 집합을 기반으로 하지만, PDDL2.1 이후 시간과 수치 변수 (Numeric Fluents) 가 도입되었습니다. 최근에는 연속적인 수치 결정 변수인 '제어 매개변수' (예: 로봇의 이동 거리, 가변적인 힘의 크기 등) 를 포함하는 계획 문제가 등장했습니다.
• 기존 접근법의 한계: 기존 최첨단 계획기 (POPCORN, NextFLAP 등) 는 제어 매개변수를 선형 계획법 (Linear Programming) 이나 SMT (Satisfiability Modulo Theories) 솔버를 통해 제약 조건으로 처리합니다. 즉, 탐색 공간에서 결정 지점으로 명시적으로 다루지 않고, 제약 충족 문제로 환원하여 해결합니다.
• 제안하는 문제: 제어 매개변수를 상태 전이 시스템의 명시적인 결정 변수로 정의하고, 이를 포함한 무한한 결정 공간 (Infinite Decision Space) 에서 체계적인 탐색을 수행하는 알고리즘이 필요합니다.

2. 방법론: 샘플링 기반 최우선 탐색 (Sampling Best-First Search, S-BFS)

저자들은 무한한 후계 상태 (Successors) 를 가진 노드를 완전히 확장할 수 없다는 문제점을 해결하기 위해 지연된 부분 확장 (Delayed Partial Expansions) 개념을 도입한 S-BFS 알고리즘을 제안합니다.

• 핵심 메커니즘:
  1. 샘플링 함수 ($\phi$): 각 상태의 무한한 결정 공간 (행동과 제어 변수 값의 쌍) 에서 후계 상태를 샘플링하여 부분적으로 확장합니다.
  2. 지연된 부분 확장: 노드가 완전히 확장되지 않고, 샘플링된 일부 후계 상태만 생성하여 오픈 리스트 (Open List) 에 추가합니다.
  3. 재확장 및 보정 (Rectification): 부분적으로 확장된 노드는 닫히지 않고, **보정 함수 ($r_h$)**에 의해 평가 값 (NEC, Node Evaluation Criterion) 이 조정된 후 오픈 리스트에 다시 삽입됩니다. 이는 탐색이 특정 경로에 갇히는 것을 방지하고, 시간이 지남에 따라 모든 가능한 후계 상태를 탐색할 기회를 보장합니다.
• 알고리즘 변형:
  • S-G: 휴리스틱 값 ($h$) 만을 기반으로 평가.
  • S-A: 누적 비용 ($g$) 과 휴리스틱 ($h$) 을 모두 고려 ($g + r_h$).

3. 주요 기여 및 이론적 성질 (Key Contributions & Properties)

• 확률적 완전성 (Probabilistic Completeness):
  • 무한한 공간에서 유한한 단계로 해를 찾는 것은 불가능하므로, 저자들은 확률적 완전성을 정의합니다. (즉, $n \to \infty$일 때 해를 찾을 확률이 1 이 됨).
  • 정리 1: 샘플링 함수가 모든 가능한 후계 상태를 양의 확률로 샘플링할 수 있고 ($\text{supp}(\phi(s)) = D(s)$), 보정 함수가 적절히 설계되어 (단조 증가) 노드가 무한히 우선순위를 차지하지 않도록 하면, S-BFS 는 확률적으로 완전함을 증명했습니다.
• 해의 품질 보장 (Solution Quality Bound):
  • 정리 2: S-A 알고리즘이 해를 찾을 때, 그 비용은 초기 상태의 보정된 평가 값 ($r_h(n, s_0)$) 에 의해 상한이 보장됨을 보였습니다. 이는 최적성을 보장하지는 않지만, 해의 품질에 대한 이론적 한계를 제공합니다.
• 새로운 탐색 패러다임: 제어 매개변수를 제약이 아닌 '결정'으로 취급하여, 제약 기반 솔버에 의존하지 않는 순수 탐색 기반 접근법을 정립했습니다.

4. 실험 결과 (Experimental Results)

• 비교 대상: NextFLAP (제약 기반 계획기), MCTS (Monte-Carlo Tree Search, Progressive Widening 사용).
• 테스트 도메인: POPCORN 및 최신 수치 IPC 도메인의 확장 버전 (CASHPOINT, PROCUREMENT, DRONE 등) 총 7 개 도메인, 140 개 문제.
• 성능 분석:
  • 보정 함수: 로그arithmic 성장 ($r_{log}$) 을 사용하는 보정 함수가 가장 높은 커버리지 (문제 해결 수) 를 보였습니다. 이는 휴리스틱의 기여도를 높이고 과도한 페널티를 줄이는 것이 효과적이었음을 시사합니다.
  • 샘플링 전략: 체계적 샘플링 (Systematic) 과 균일 샘플링 (Uniform) 이 휴리스틱 가이드 샘플링보다 성능이 좋았습니다. (휴리스틱이 평탄한 지역을 많이 가져 샘플링 효율이 떨어졌음).
  • NextFLAP 대비: S-BFS (특히 S-G) 는 NextFLAP 보다 훨씬 더 많은 문제를 해결했습니다. NextFLAP 은 해결한 문제의 경우 계획 길이 (Action count) 가 더 짧았으나, S-BFS 는 해결 가능한 문제의 범위가 훨씬 넓었습니다.
  • MCTS 대비: MCTS 는 매우 적은 수의 문제만 해결하여 S-BFS 의 우월성을 입증했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 의의: 이 연구는 제어 매개변수를 가진 계획 문제를 제약 충족 문제가 아닌 체계적인 탐색 문제로 재정의했습니다. 지연된 부분 확장을 통해 무한한 결정 공간을 효율적으로 탐색할 수 있는 이론적 기반과 실용적 알고리즘을 제공했습니다.
• 결론: 제안된 S-BFS 알고리즘은 기존 제약 기반 접근법보다 더 넓은 범위의 문제를 해결할 수 있으며, 무한 도메인 계획에 대한 새로운 연구 방향을 제시합니다.
• 향후 작업: 시간 계획 (Temporal Planning) 및 PDDL+ 의 연속 시간 행동으로의 확장, 무한 결정 공간을 고려한 새로운 휴리스틱 개발 등을 계획하고 있습니다.

요약하자면, 이 논문은 무한한 제어 매개변수를 가진 계획 문제를 해결하기 위해 샘플링 기반의 지연 부분 확장 전략을 도입한 S-BFS 알고리즘을 제안하고, 이를 통해 기존 방법론보다 **더 높은 문제 해결 능력 (Coverage)**을 달성했음을 입증했습니다.