KNOWPLAN: Knowledge-Driven AI Agents for Smart Degree Pathway Planning

기술 요약: KnowPlan

문제 정의

학위 경로 계획(degree pathway planning)은 학생들이 선수 과목 논리, 학위 요구 사항, 이수 단위 제한, 학기별 개설 여부를 충족하도록 과목을 배치해야 하는 제약 기반의 의사 결정 문제입니다. 기존 연구들이 과목 추천 및 커리큘럼 최적화를 다루어 왔으나, 이러한 접근 방식들은 대개 충분히 완전한 커리큘럼 표현이 이미 가용하다는 가정을 전제로 합니다.

공공 대학 소스로부터 이러한 표현을 구축하는 것은 본질적으로 어렵습니다. 기관의 커리큘럼은 이질적인 형식(웹페이지, JSON 엔드포인트, PDF)으로 분산되어 있으며, 공유된 스키마가 없고, 중첩된 논리 절, 요구 사항 중복, 정책 예외 사항을 포함하고 있습니다. 기존 문헌에서 다뤄지지 않은 핵심적인 공백은 **획득-계획의 순환성(acquisition–planning circularity)**입니다. 만약 개인화된 플래너가 소스 획득을 제어한다면, 현재 학생의 목표가 어떤 페이지를 열 것인지를 결정하게 됩니다. 결과적으로, 이렇게 생성된 부분적인 그래프는 어떤 계획이 실행 가능한지를 결정하며, 동일한 불완전한 그래프가 계획을 검증하는 데 사용됩니다. 누락된 규칙은 획득되지 않았기 때문에 보이지 않는 상태로 남게 됩니다.

방법론

저자들은 이 순환성을 깨기 위해 커리큘럼 재구성과 개인화된 학위 계획을 분리하는 추출 우선 프레임워크인 KnowPlan을 제시합니다. 시스템은 두 가지 별개의 단계로 작동합니다.

1. CatalogBrowse: 프로필 독립적 추출

CatalogBrowse는 학생 프로필에 접근하지 않고 커리큘럼 데이터를 획득하도록 설계된 웹 탐색 에이전트입니다.

• 상태 및 관측 가능성: 에이전트는 동적인 페이지 그래프와 열리지 않은 링크의 프런티어를 유지합니다. 결정적으로, 페이지 콘텐츠는 액션이 사전 약정(precommitted)되고 비용이 지불된 후에만 공개되므로, 에이전트가 콘텐츠를 검사하여 접근 여부를 결정하는 것을 방지합니다.
• 원자적 의무(Atomic Obligations): 쉬운 성공을 장려하는 가중치 완료 신호에 의존하는 대신, 에이전트는 인덱스 항목 발견, 엔티티 인스턴스화, 필수 필드 채우기, 참조 해결과 같은 유한한 원자적 의무($O$)를 목표로 합니다.
• 정책: 에이전트는 소스 접근 단위당 기대되는 한계 의무 이득에 대한 하한값(lower-confidence bound, LCB)을 사용하여 액션을 선택합니다. 이 보수적인 정책은 이미 검증된 증거를 우선시하며, 익숙하지 않은 액션은 해당 의무 자체가 양(+)의 기대 이득을 생성할 때만 수행되도록 보장합니다.
• 파싱 및 폴백(Fallback): 시스템은 API, DOM, PDF를 위한 결정론적 플랫폼 어댑터를 사용합니다. 복잡한 논리 절의 경우, span-제약 조건이 있는 clause-to-AST 모델을 사용합니다. 이 모델은 가시적인 span 내에 실제로 존재하는 토큰으로 제한되며, 임의의 URL이나 식별자를 생성할 수 없습니다. 출력값은 수락 전 페이지 텍스트 내에서 재위치(re-located)됩니다.
• 종료: 에이전트는 **폐쇄 인증서(closure certificate)**가 성립할 때만 정지합니다. 이 인증서는 발견된 모든 인덱스 항목이 엔티티에 바인딩되었거나 명시적으로 실패한 것으로 기록되었는지, 모든 스키마 필수 필드가 바인딩되었거나 명시적으로 미해결 상태인지, 그리고 모든 출처 오프셋(provenance offset)이 에이전트가 연 페이지의 범위 내에 있는지를 검증합니다. 인증서는 증거를 찾아내지만 사실 자체를 판정하지는 않습니다. 이는 스냅샷 상대적이며 실제 웹(Live Web)에 대한 주장을 하지 않습니다.
• 출력: 이 단계는 출처가 연결된 세 가지 JSON 문서(과목/선수 과목, 프로그램 요구 사항, 일반 교육 프레임워크)를 정확히 생성합니다.

2. DegreeMap: 개인화된 계획

DegreeMap은 CatalogBrowse에서 생성된 세 개의 JSON 문서와 학생의 특정 요청만을 소비합니다.

• 타입화된 요구사항 하이퍼그래프: 컴파일러는 JSON 문서를 타입화된 요구사항 하이퍼그래프로 매핑합니다. 이는 복잡한 논리 구조(예: CHOOSE_N, ALL_OF)를 쌍 단위의 절로 확장하지 않고 하이퍼엣지로 보존하여, "9개 중 3개 선택"과 같은 제약 조건을 정확하게 강제합니다.
• 개인화된 효용: 시스템은 다음을 기반으로 각 과목에 대한 점수 $S(c)$를 계산합니다:
  • 직접적인 의미론적 관심($I_0$).
  • 타입화된 그래프 확산($I_D$): 충족 및 교차 리스팅 엣지를 통해 관심을 전파하되, 선수 과목 엣지를 통해서는 전파하지 않음.
  • 선수 과목 잠금 해제 가치($U$): 의존성 경로를 따라 역방향으로 관심을 전파함.
  • 전공/교양 이득, 미래 옵션 가치, 학습량, 리스크 및 기피 요인.
• 사전적(Lexicographic) CP-SAT 최적화: 플래너는 다음과 같은 사전적 순서에 따라 순위가 매겨진 계획 세트를 해결합니다:
  1. 하드 실행 가능성 (모든 제약 조건 충족).
  2. 최소 완료 기간.
  3. 학습량 및 스케줄링 리스크.
  4. 개인화된 효용.
  5. 미래 옵션 가치.
     각 단계는 이전 단계의 증명된 최적값을 하드 제약 조건으로 고정하여, 고정된 솔버 예산 내에서 인증 가능성을 보존합니다.
• 명확화: 남은 선호도 가설 전반에 걸쳐 최적의 계획이 달라지는 경우, 시스템은 예상 후회(regret)를 줄이기 위해 표적 질문을 던집니다.

주요 기여

1. 정식화: 본 논문은 공공 소스로부터의 학위 계획을 획득 및 최적화라는 2단계 문제로 정식화하여, 획득-계획의 순환성을 직접 측정 가능하게 만들었습니다.
2. CatalogBrowse: 의무 기반 탐색, 출처 연결 추출, 그리고 모든 발견된 항목이 처리되었거나 명시적으로 실패했음을 검증함으로써 스냅샷 대비 출력의 완전성을 보장하는 인증 기반 정지 규칙을 갖춘 프로필 독립적 에이전트를 도입했습니다.
3. DegreeMap: 타입화된 요구사항 하이퍼그래프와 정확한 사전적 최적화를 결합한 플래너를 제시하며, 이를 마스킹된 소스(masked-source) 및 골드(gold) 대 추출(extracted) 쌍 비교 트랙을 통해 평가했습니다.

결과

시스템은 Broad-100 트랙(100개 대학)과 Dense-6 트랙(다양한 소스 형식을 가진 6개 대학)에서 평가되었습니다.

• 추출 성능 (CatalogBrowse):
  • **96.2%**의 인벤토리 재현율(recall)과 **88.7%**의 마스킹된 소스 복구율(숨겨진 페이지 뒤의 엔티티 복구)을 달 achieved 했습니다.
  • 철저한 크롤러보다 47% 적은 소스 접근을 사용하면서도 Static BFS 및 Go-Browse 스타일의 에이전트와 같은 베이스라인을 능가했습니다.
  • Broad 트랙에서 높은 Typed F1(79.4) 및 AST 의미론적 동등성(77.8)을 유지했습니다.
• 계획 성능 (DegreeMap):
  • Dense-6 트랙에서 **100.0%**의 하드 실행 가능성을 유지했습니다.
  • 가장 강력한 베이스라인(LLMAP 스타일 MSGS) 대비 개인화된 효용을 +0.066 개선했습니다.
  • 완료 기간을 6.7학기에서 6.3학기로 단축했습니다.
• 엔드 투 엔드 성능:
  • 전체 파이프라인은 계획 요청의 **99.5%**를 인증했습니다.
  • 특권적인 골드 커리큘럼 그래프를 통한 계획 대비 효용 격차는 단 0.015였습니다.
  • 절제 연구(Ablation studies) 결과, 고정점 인증(fixed-point certificate)을 제거하면 재현율이 4.4포인트 감소하고, 가중 합산 목적 함수를 사용하면 인증된 실행 가능성이 4.0포인트 감소함을 확인했습니다.

의의

본 논문은 구성상(by construction) KnowPlan이 획득-계획의 순환성을 제거한다고 주장합니다. 커리큘럼의 획득(학생 목표와 무관)을 학생 특화 최적화로부터 분리함으로써, 데이터 획득과 사용 사이의 인터페이스를 가정된 것이 아닌 측정 가능한 것으로 만듭니다. 저자들은 이 접근 방식이 모델링 가정(커리큘럼이 알려져 있다는 가정)을 측정된 양으로 변환하며, 신뢰할 수 있는 학위 계획을 위해서는 학생 특화 최적화 이전에 프로필 독립적인 커리큘럼 획득이 필요함을 입증한다고 강조합니다. 이 프레임워크는 에이전트가 나중에 결정될 목적에 대응하기 위해 세계 모델을 획득해야 하는 모든 도메인에 일반화될 수 있습니다.