Improving Execution Concurrency in Partial-Order Plans via Block-Substitution

이 논문은 부분 순서 계획 (POP) 의 실행 동시성을 향상시키기 위해 블록 역순서화 (block deordering) 를 통해 일관된 행동들을 캡슐화하고, 이를 기반으로 자원 활용을 최적화하는 하위 계획 치환 알고리즘을 제안하며 국제 계획 대회 (IPC) 벤치마크를 통해 그 효과를 입증했습니다.

핵심

🏗️ 1. 배경: "순서대로" vs "함께" 하기

상상해 보세요. 여러분이 거대한 파티를 준비하고 있다고 칩시다.

• 기존 방식 (순차적 계획): AI 는 "먼저 케이크를 구워야 하고, 그 다음에 초를 꽂아야 하며, 그다음에 선물을 포장해야 한다"는 식으로 엄격한 순서를 정해줍니다. 한 가지가 끝나야 다음 걸 시작할 수 있죠.
• 문제점: 하지만 "케이크를 굽는 동안"에 "선물 포장"을 해도 아무 문제없지 않나요? 기존 방식은 이런 **동시 작업 (병렬 처리)**의 기회를 놓쳐서 시간이 더 오래 걸립니다.

이 논문은 AI 가 만든 계획서에서 **"이건 꼭 순서대로 해야 해"**라는 규칙을 최대한 없애고, **"이건 동시에 해도 돼"**라는 기회를 늘리는 방법을 연구했습니다.

🧱 2. 핵심 아이디어: "블록"과 "대체"

논문의 핵심은 두 가지 단계로 이루어져 있습니다.

1 단계: "블록" 만들기 (조립식 블록)

기존의 복잡한 작업 목록을 **작은 블록 (Block)**으로 묶습니다.

• 비유: 레고 블록을 생각하세요. 개별 레고 조각 (작업) 들을 묶어서 하나의 큰 블록 (예: '케이크 완성 블록', '선물 포장 블록') 으로 만듭니다.
• 효과: 이렇게 묶으면, '케이크 블록'과 '선물 포장 블록'은 서로 순서가 상관없을 수 있습니다. 하지만 여기서 하나의 치명적인 문제가 생깁니다.

2 단계: "자원 충돌" 해결하기 (블록 교체)

여기서 중요한 건 **자원 (Resource)**입니다.

• 상황: '케이크 블록'과 '선물 포장 블록'을 동시에 하려고 해도, 두 블록이 같은 '오븐'을 사용해야 한다면 동시에 할 수 없습니다. (이걸 논문에서는 '비동시성 제약'이라고 부릅니다.)
• 해결책 (블록 교체): 논문의 새로운 알고리즘은 **"아, 오븐이 하나뿐이니까 동시에 못 하네? 그럼 다른 방법을 찾아보자!"**라고 생각합니다.
  • 예를 들어, '케이크를 오븐에 굽는 블록' 대신 **'마이크로파로 데우는 블록'**이나 **'다른 오븐을 쓰는 블록'**으로 대체해버립니다.
  • 이렇게 자원을 바꾸면, 두 작업을 진짜로 동시에 진행할 수 있게 됩니다.

🚀 3. 이 방법이 왜 특별한가요?

기존 연구들은 주로 "순서를 어떻게 바꾸면 더 유연해질까?"만 고민했습니다. 하지만 이 논문은 **"순서를 바꾸는 것만으로는 부족할 때, 아예 작업 내용 (블록) 자체를 다른 것으로 갈아치워라"**라고 제안합니다.

• 예시 (엘리베이터 문제):
  • 상황: 엘리베이터 1 대가 2 층에서 3 층으로 사람을 태우고, 다시 1 층으로 내려가 3 번을 태워야 합니다.
  • 기존: 엘리베이터가 움직이는 동안 다른 일은 못 합니다.
  • 이 논문의 방법: "아, 엘리베이터 1 대만 쓰는 게 아니라, 엘리베이터 2 대를 불러와서 한 명은 1 대, 다른 한 명은 2 대를 태우면 어떨까?"라고 작업 블록을 교체합니다.
  • 결과: 두 엘리베이터가 동시에 움직이므로 전체 시간이 반으로 줄어듭니다.

📊 4. 실험 결과: 실제로 효과가 있을까?

저자들은 국제 AI 계획 대회 (IPC) 의 수천 개의 문제들을 가지고 실험했습니다.

• 결과: 제안한 방법 (CIBS 알고리즘) 을 쓰면, 작업들이 동시에 이루어질 수 있는 비율 (cflex) 이 크게 향상되었습니다.
• 의미: 작업들이 동시에 더 많이 이루어질수록, 전체 완료 시간이 짧아집니다. 마치 교통 체증이 해결되어 차들이 한꺼번에 지나가는 것과 같습니다.

💡 5. 한 줄 요약

"AI 가 만든 계획서를 볼 때, '순서'만 바꾸는 게 아니라, '자원을 쓰는 방법'을 clever하게 바꾸어 (예: 엘리베이터 1 대 → 2 대), 작업들을 동시에 처리하게 만들어 시간을 아끼자!"

이 논문은 인공지능이 더 똑똑하고 빠르게 일할 수 있도록, 작업의 유연성을 극대화하는 새로운 지혜를 제시한 것입니다.

기술 요약

1. 문제 정의 (Problem Statement)

• 배경: 부분 순서 계획 (POP) 은 작업 간의 순서 제약을 최소화하여 실행 유연성 (Flexibility) 을 제공합니다. 그러나 POP 내의 순서 없는 작업들이 반드시 병렬 실행 (Concurrency) 이 가능한 것은 아닙니다.
• 핵심 문제: 두 작업 (또는 하위 계획) 이 동일한 자원 (예: 같은 엘리베이터, 로봇 등) 을 사용하거나 상태 변수의 값이 상충될 경우, 순서가 없더라도 병렬 실행이 불가능합니다. 이를 **비동시성 제약 (Non-concurrency constraints)**이라고 합니다.
• 한계: 기존 연구들은 주로 불필요한 순서 제약을 제거하는 '계획 순서 제거 (Deordering)'에 집중했습니다. 하지만 순서 제약이 제거되어도 자원 충돌로 인한 비동시성 제약이 남아있으면 병렬 실행 효율 (Concurrency) 은 개선되지 않습니다.
• 목표: 계획의 전체 실행 시간을 단축하기 위해, 자원 충돌을 해결하여 비동시성 제약을 최소화하고 병렬 실행 가능성을 극대화하는 방법론을 개발하는 것.

2. 방법론 (Methodology)

이 연구는 **병렬 블록 분해 계획 (Parallel Block Decomposed, PBD)**을 기반으로 하며, CIBS (Concurrency Improvement via Block-Substitution) 알고리즘을 제안합니다.

2.1 기본 개념 및 정의

• 비동시성 제약 조건 (Non-concurrency Constraints): 두 작업 $o_i, o_j$가 병렬 실행될 수 없는 조건을 상태 변수 (State Variables) 관점에서 정의했습니다.
  • 두 작업의 전제 조건 (Precondition) 이 같은 변수에 대해 서로 다른 값을 요구할 때.
  • 두 작업의 효과 (Effect) 가 같은 변수에 대해 서로 다른 값을 생성할 때.
  • 한 작업의 전제 조건과 다른 작업의 효과가 같은 변수에서 충돌할 때.
• PBD 계획: 블록 분해 부분 순서 계획 (BDPO) 에 비동시성 제약 관계 (#) 를 명시적으로 포함시킨 형태의 계획입니다.

2.2 CIBS 알고리즘의 3 단계 프로세스

제안된 알고리즘은 다음 세 단계를 거쳐 계획의 병렬성을 향상시킵니다.

1. EOG (Explanation-based Order Generalization):

   • 순차적 계획을 부분 순서 계획 (POP) 으로 변환합니다.
   • 인과적 링크 (Causal links) 와 위협 (Threats) 을 분석하여 필수적인 순서만 남기고 불필요한 순서 제약을 제거합니다.
   • 이 단계에서 비동시성 제약 관계를 초기화합니다.

2. BD (Block Deordering):

   • 일관된 작업 집합을 '블록 (Block)'으로 캡슐화합니다.
   • 블록 간의 순서 제약을 제거하여 계층적 구조 (BDPO) 를 생성합니다.
   • 이 단계에서는 블록 간의 순서는 제거되지만, 여전히 자원 충돌로 인한 비동시성 제약 (#) 이 존재할 수 있습니다.

3. SC (Substitution for Concurrency) - 핵심 기여:

   • 블록 확장 (Block Extension): 비동시성 제약을 가진 두 블록 중 하나를 대체하기 위해, 해당 블록의 선행/후행 작업을 포함하여 블록을 확장합니다. 이는 하위 작업 (Subtask) 을 독립적으로 해결할 수 있도록 범위를 넓히는 과정입니다.
   • 하위 계획 생성: 확장된 블록에 해당하는 새로운 하위 계획 (Subtask) 을 생성하고, 이를 해결하는 대체 가능한 하위 계획 (Candidate Subplan) 을 탐색합니다.
   • 블록 대체 (Block Substitution): 기존 블록을 대체할 수 있는 새로운 하위 계획을 찾았을 때, 새로운 계획이 기존 블록과 비동시성 제약이 없으며 (자원 충돌 없음), 비용은 유지하거나 감소하는지 확인합니다.
   • 조건을 만족하면 기존 블록을 새로운 블록으로 교체하여 비동시성 제약을 제거하고 병렬성을 높입니다.

3. 주요 기여 (Key Contributions)

1. 비동시성 제약의 필요충분 조건 정립: FDR (Finite Domain Representation) 기반의 상태 변수를 사용하여 두 작업 또는 두 하위 계획 간의 비동시성 제약이 발생하는 필요충분 조건을 수학적으로 증명했습니다.
2. PBD (Parallel Block Decomposed) 계획의 정의: 블록 간의 병렬 실행을 가능하게 하는 의미론 (Semantics) 과 비동시성 제약을 명시적으로 포함하는 PBD 계획 모델을 제안했습니다.
3. 블록 대체를 통한 병렬성 향상 알고리즘 (CIBS):
   • 블록을 하위 계획의 후보로 활용하여 자원을 재할당하거나 다른 자원을 사용하는 대체 계획을 찾는 알고리즘을 개발했습니다.
   • 기존 순서 제거 기법만으로는 해결되지 않는 자원 충돌 문제를 해결하여 병렬성을 극대화합니다.
4. cflex 지표 도입: 계획의 병렬성을 정량화하기 위해 cflex (동시 실행 가능한 작업 쌍의 비율) 를 도입하고, 이 값이 계획의 최소 실행 시간과 강한 음의 상관관계가 있음을 실험적으로 증명했습니다.

4. 실험 결과 (Experimental Results)

• 데이터셋: 국제 계획 대회 (IPC) 의 다양한 도메인 (Elevator, Logistics, Blocks 등) 에서 3,303 개의 계획에 대해 실험을 수행했습니다.
• 성능 향상:
  • cflex 증가: EOG 단계 (0.237) 에서 BD 단계 (0.241), 그리고 SC 단계 (0.242) 로 진행될수록 평균 cflex 값이 유의미하게 증가했습니다.
  • 도메인별 효과: Elevator, Logistics, Parking 등 자원이 제한적이거나 대체 가능한 자원이 있는 도메인에서 병렬성 개선 효과가 두드러졌습니다.
  • 통계적 유의성: Wilcoxon 부호 순위 검정을 통해 BD 와 SC 단계가 EOG 대비 통계적으로 유의미한 개선을 가져왔음을 확인했습니다.
• 실행 시간과 크기:
  • CIBS 알고리즘은 중간 크기 (50~300 개 작업) 의 계획에서 가장 큰 개선을 보였습니다.
  • 매우 큰 계획 (350 개 이상) 에서는 계산 복잡도와 시간 제한으로 인해 개선 효과가 감소하는 경향이 있었습니다.
• 기타 알고리즘 비교: MaxSAT 기반의 최적 순서 재배열 (MR, MRR) 기법과 비교했을 때, CIBS 는 더 빠른 초기 수렴 속도와 높은 커버리지 (Coverage) 를 보여주었습니다.

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

• 실용적 가치: 이 연구는 단순히 계획을 유연하게 만드는 것을 넘어, 실제 병렬 하드웨어 환경에서 계획의 실행 시간 (Makespan) 을 단축할 수 있는 실질적인 방법을 제공합니다.
• 자원 관리의 혁신: 기존에는 자원 충돌을 순서 제약을 통해 해결했다면, 이 연구는 **대체 계획 (Substitution)**을 통해 자원을 우회하거나 다른 자원을 활용함으로써 병렬 실행의 기회를 창출합니다.
• 미래 전망: 블록 분해 기법이 포착하지 못하는 일관된 작업 집합을 발견하기 위한 방법론 개발과, 상호작용하는 작업이 포함된 복잡한 병렬 계획으로의 확장이 향후 연구 과제로 제시되었습니다.

요약하자면, 이 논문은 블록 대체 (Block-Substitution) 기법을 통해 자원 충돌을 해결함으로써 부분 순서 계획의 병렬 실행 능력을 획기적으로 향상시켰으며, 이는 AI 계획 시스템의 효율성과 실행 속도를 높이는 중요한 진전입니다.