몇 번 해야 끝날지 몰라도, 반복 계획을 만들 수 있을까요?

도끼로 나무를 치는 행동을 chop, 도끼를 보관하는 행동을 store라고 하겠습니다. 나무가 정확히 세 번 뒤에 쓰러진다는 정보를 안다면 계획은 간단합니다. chop을 세 번 실행한 뒤 store를 실행하면 됩니다. 문제는 필요한 횟수가 알려지지 않았고 상한도 없을 때 생깁니다.

이 상황에서 고정된 chop 목록은 부족합니다. 두 번만 적은 계획은 세 번째 타격이 필요한 나무에서 멈추고, 백 번을 적은 계획도 백한 번째 타격이 필요한 경우를 다루지 못합니다. 계획은 남은 횟수의 값에 맞춰 길어져야 하므로 반복 구조가 필요합니다.

F는 계획 매개변수(planning parameter)입니다. 나무 사례에서는 나무를 쓰러뜨리는 데 필요한 타격 수를 뜻합니다. 계획을 만들 때 F의 실제 값과 상한을 모릅니다. F를 이미 알고 있다면 반복문 없이도 목표를 이룰 수 있다는 조건도 함께 둡니다.

이 조건은 반복이 필요한 까닭을 한 변수에 모읍니다. 도끼를 쓸 수 있는지, 나무가 서 있는지, 도끼를 보관했는지는 행동의 전제와 결과로 다룹니다. F만 값도 상한도 모르는 매개변수로 둡니다. 무엇을 고정하고 무엇을 바꾸는지 구별해야 생성 범위와 시험 범위를 정확히 말할 수 있습니다.

순차 계획은 행동을 한 줄로 실행합니다. F=3을 안다면 chop; chop; chop; store가 해당합니다. 조건 계획은 센서 결과에 따라 갈라집니다. F≤2라는 상한을 알면 look으로 나무 상태를 보고, up일 때만 chop을 이어 가는 두 층의 갈래를 만들 수 있습니다.

반복 계획은 갈래가 다시 앞 단계로 돌아갑니다. look 결과가 down이면 반복을 빠져나가고, up이면 chop 뒤에 다음 반복으로 갑니다. 끝나는 시점은 센서 결과가 결정합니다. 이 구조는 “언젠가 반복해서 치면 쓰러진다”라는 문제 조건과 맞물립니다.

look은 나무 상태를 down 또는 up으로 알려 주는 감각 행동입니다. 타격 횟수를 직접 말해 주지는 않습니다. 계획은 현재까지 몇 번 쳤는지와 look 결과를 함께 기록하고, up이면 chop을 합법적으로 실행할 수 있는지 확인합니다.

센서가 없다면 계획은 어느 순간 store로 넘어가야 할지 알 수 없습니다. 센서가 있으면 각 반복에서 종료 조건을 다시 확인합니다. down을 받으면 EXIT 뒤 store로 가고, up을 받으면 chop 뒤 NEXT로 돌아갑니다. 센서가 반복의 종료 판단을 맡습니다.

초기 상태에서 나무는 서 있고 도끼는 꺼내져 있습니다. 첫 look은 up을 돌려줍니다. 계획은 chop을 한 번 실행하고 다시 look으로 갑니다. 둘째와 셋째 반복도 같은 순서를 따릅니다. 세 번째 chop 뒤 나무가 쓰러졌다고 두면, 넷째 look이 down을 돌려줍니다.

down 갈래는 EXIT로 반복을 마치고 store를 실행합니다. 최종 상태는 tree=down, axe=stored입니다. 여기서 성공 근거는 “chop을 세 번 했기 때문”과 “down을 확인한 뒤 store로 갔기 때문”을 함께 포함합니다.

KPLANNER는 작은 생성 상한 N₁에서 순차·조건 계획을 먼저 찾습니다. 나무 사례에서 N₁=1이면 F≤1인 경우를 해결하는 작은 조건 계획을 만들 수 있습니다. 아직 반복문을 직접 열거하지 않습니다.

그 뒤 이미 만든 조건 계획이 어떤 반복문의 펼침(unwinding)과 같은 모양인지 찾습니다. 반복문을 한 차례 풀면 본문이 나오고, NEXT 자리에 반복문 자신이 다시 들어갑니다. 생성된 계획에 이 모양이 보이면 거꾸로 반복 구조를 감아 올립니다.

N₁은 계획을 찾는 범위입니다. 작은 값으로 두면 탐색 공간이 줄어듭니다. N₂는 찾아낸 계획을 시험하는 범위이며 N₁보다 크게 둡니다. 원문의 나무 명세는 생성에서 chops_max=1, 시험에서 chops_max=100을 사용합니다.

두 범위를 나눈 까닭은 계획 생성과 계획 검증의 난도가 다르기 때문입니다. 작은 범위에서 후보를 찾고, 큰 범위에서 가능한 센서 결과를 모두 따라가 목표가 성립하는지 확인합니다. 이 절차만으로 얻는 일반 보증은 F≤N₂입니다.

그 결론은 나오지 않습니다. 원문은 F≤2에서 맞는 조건 계획이 F≥3에서 실패할 수 있다고 분명히 설명합니다. N₂=2까지 시험했다면 확인된 범위는 F=1과 F=2입니다. F=3은 시험 바깥입니다.

반복 계획 TC는 나무 사례에서 더 큰 범위를 다루지만, 시험 범위를 넓혔다는 사실만으로 무한한 모든 F를 증명할 수는 없습니다. 전 범위 결론에는 §5의 “단순한 문제” 조건과 정리 1이 필요합니다.

시험기는 계획 P와 상한 N을 받은 뒤, 그 범위에서 가능한 모든 감각 결과를 따라갑니다. 행동의 전제조건이 현재 이력에서 성립하는지 확인하고, 감각 행동에서는 가능한 결과마다 후속 계획을 시험합니다. 계획이 끝나면 목표 식이 이력에서 참인지 확인합니다.

나무 사례에서 chop을 두 번 합법적으로 실행했고 F≤2라고 가정하면, 다음 look이 up을 돌려주는 갈래는 불가능합니다. 시험기는 행동과 감각 결과의 이력을 이용해 이런 갈래를 제외합니다. 가능한 갈래를 빠뜨리거나 불가능한 갈래를 성공 근거에 넣지 않습니다.

원문 구현은 반복 계획 P를 한 번 펼친 결과가 조건 계획 Q와 맞는지 검사하는 관계 unw(P,Q)를 프롤로그로 작성합니다. 보통은 P를 주고 Q를 계산하지만, 프롤로그의 변수와 역방향 패턴 맞추기를 이용하면 Q를 주고 P 후보를 돌려받을 수 있습니다.

나무 계획의 “상관없는 값(don’t care)” 자리에 seq(chop; TC)를 치환하면 생성된 조건 계획이 TC를 펼친 모양과 맞습니다. 이 관계를 이용해 가능한 모든 반복문을 처음부터 열거하지 않고도 작은 조건 계획에서 반복 후보를 얻습니다.

원문은 행동 A에 관해 “단순한 문제”를 세 조건으로 정의합니다. 첫째, 감각은 초기 F가 지금까지 실행한 A의 횟수와 같은지만 알려 줍니다. 둘째, 어떤 이력에서 행동이 합법이고 다른 이력에서는 불법이라면 그 차이가 생기기 전에 감각 결과도 달라져야 합니다.

셋째 조건은 더 큰 F에서도 같은 행동 조각 σ를 옮길 수 있다는 단조로운 확장 성질을 요구합니다. 작은 k에서 σ를 덧붙여 k+m을 해결했고, 더 큰 k′에서도 앞부분과 뒷부분이 각각 맞는다면 k′+m에서도 σ를 붙인 실행이 맞아야 합니다. 이 세 조건이 모두 있어야 정리 1을 사용할 수 있습니다.

정리 1은 단순한 문제와 로봇 프로그램 P를 전제로 합니다. P 안에 행동 A가 N번 나타나고, P가 모든 F≤N+2에서 올바르면 모든 F에서 올바르다는 결론을 냅니다. N은 프로그램 문법 안에 나타난 A의 발생 횟수입니다. 실행 중 반복되는 총횟수와 구별합니다.

나무 계획 TC의 반복 본문에는 chop이 한 번 나타납니다. 여기서 N=1로 읽으면 시험 경계는 N+2=3입니다. 나무 문제가 chop에 관해 단순하다는 세 조건을 별도로 확인한 뒤 F≤3에서 계획이 맞으면, 정리 1에 따라 모든 F로 결론을 넓힐 수 있습니다.

원문은 미지의 양의 정수 k와 두 누산기를 둡니다. 두 누산기는 0에서 시작합니다. 첫 누산기를 1로 만든 뒤, 첫 누산기가 입력 k와 같은지 감각 행동으로 검사합니다. 다르면 첫 누산기를 1 늘리고 둘째 누산기를 2 늘리며 반복합니다. 같으면 반복을 빠져나와 둘째 누산기를 마지막으로 1 늘립니다.

k=3으로 따라가면 첫 누산기는 1→2→3이고, 둘째 누산기는 반복 안에서 0→2→4, 반복 뒤에 5가 됩니다. 목표 2k−1=5와 일치합니다. 명세에 곱셈 계산법을 따로 넣지 않았지만, 목표식의 만족 여부는 평가할 수 있었기 때문에 계획을 찾습니다.

KPLANNER는 깊이 상한을 모르는 이진트리에서 목표 노드를 찾는 중첩 반복 계획도 생성합니다. 내부 노드에서는 왼쪽으로 내려가고, 잎에서 되돌아올 때는 스택에 저장된 방향을 읽어 아직 살펴보지 않은 오른쪽 갈래로 이동합니다. 목표를 만나면 바깥 반복을 빠져나옵니다.

이 사례에는 내부 스택과 중첩 반복, 여러 종류의 감각 결과가 들어갑니다. 원문은 이 문제가 단순한 문제 조건과 거리가 멀다고 밝힙니다. 계획을 생성했다는 사실과 정리 1로 전 범위를 증명했다는 사실을 분리해야 합니다.

첫째, 생성과 검증을 분리했다는 사실을 기록합니다. 둘째, 시험 상한까지의 성공과 모든 값에서의 성공을 구별합니다. 셋째, 정리 1을 쓸 때는 단순한 문제의 세 조건과 프로그램 안의 행동 발생 수 N을 실제로 확인합니다. 넷째, 계획 생성 시간이 입력 범위와 함께 빠르게 늘 수 있음을 감안합니다.

원문의 달걀 사례에서 풀어 쓴 계획 크기는 6, 9, 12, 15로 늘었고 실행 시간은 0.004초, 0.02초, 1.41초, 1681초로 증가했습니다. 크기 18은 3주가 지나도 끝나지 않았습니다. 반복 계획이 짧아 보여도 그 계획을 찾는 탐색은 매우 커질 수 있습니다. 이 방법은 작은 계획을 합성하는 데 초점을 둡니다.