Resumo Técnico: KnowPlan

Declaração do Problema

O planejamento de trajetórias de graduação acadêmica é um problema de decisão orientado por restrições que exige que os alunos sequenciem cursos para satisfazer a lógica de pré-requisitos, requisitos de graduação, limites de unidades e ofertas de períodos letivos. Embora trabalhos anteriores tenham abordado a recomendação de cursos e a otimização de currículos, essas abordagens assumem amplamente que uma representação de currículo suficientemente completa já está disponível.

A construção dessa representação a partir de fontes universitárias públicas é inerentemente difícil. Os currículos institucionais estão distribuídos em formatos heterogêneos (páginas web, endpoints JSON, PDFs) sem um esquema compartilhado, contendo cláusulas lógicas aninhadas, sobreposições de requisitos e exceções de políticas. Uma lacuna crítica e não abordada na literatura existente é a circularidade aquisição–planejamento: se um planejador personalizado controla a aquisição da fonte, o objetivo atual do estudante determina quais páginas são abertas. Consequentemente, o grafo parcial resultante determina quais planos parecem viáveis, e o mesmo grafo incompleto é usado para validar o plano. Regras ausentes permanecem invisíveis porque nunca foram adquiridas.

Metodologia

Os autores apresentam o KnowPlan, um framework de extração prioritária que separa a reconstrução do currículo do planejamento de graduação personalizado para quebrar essa circularidade. O sistema opera em dois estágios distintos:

1. CatalogBrowse: Extração Independente de Perfil

O CatalogBrowse é um agente de exploração web projetado para adquirir dados curriculares sem acesso a qualquer perfil de estudante.

• Estado e Observabilidade: O agente mantém um grafo de páginas dinâmico e uma fronteira de links não abertos. Crucialmente, o conteúdo da página é revelado apenas após uma ação ser pré-comprometida e paga, impedindo que o agente inspecione o conteúdo para decidir se deve acessá-lo.
• Obrigações Atômicas: Em vez de depender de sinais de conclusão ponderados que incentivam vitórias fáceis, o agente visa um conjunto finito de obrigações atômicas ($O$), como descobrir entradas de índice, instanciar entidades, preencher campos obrigatórios e resolver referências.
• Política: O agente seleciona ações usando um limite inferior de confiança (LCB) sobre o ganho marginal de obrigação esperado por unidade de acesso à fonte. Esta política conservadora prioriza evidências já validadas e garante que ações desconhecidas sejam apenas perseguidas se a própria obrigação gerar um ganho esperado positivo.
• Parsing e Fallback: O sistema utiliza adaptadores determinísticos para APIs, DOMs e PDFs. Para cláusulas lógicas complexas, emprega um modelo de cláusula-para-AST com restrição de intervalo (span-constrained). O modelo é restrito a tokens literalmente presentes no intervalo visível e não pode emitir URLs ou identificadores arbitrários; as saídas são relocalizadas no texto da página antes da aceitação.
• Terminação: O agente para apenas quando um certificado de fechamento é válido. Este certificado verifica que cada entrada de índice descoberta está vinculada a uma entidade ou registrada como explicitamente falha, que cada campo exigido pelo esquema está vinculado ou explicitamente não resolvido, e que cada deslocamento de proveniência está dentro dos limites de uma página que o agente abriu. O certificado localiza evidências, mas não adjudica os fatos em si; ele é relativo ao snapshot e não faz afirmações sobre a Web viva.
• Saída: O estágio emite exatamente três documentos JSON com rastreabilidade de proveniência: cursos/pré-requisitos, requisitos de programa e estruturas de educação geral.

2. DegreeMap: Planejamento Personalizado

O DegreeMap consome apenas os três documentos JSON produzidos pelo CatalogBrowse e a solicitação específica do estudante.

• Hipergrafo de Requisitos Tipados: O compilador mapeia os documentos JSON em um hipergrafo de requisitos tipados. Ele preserva estruturas lógicas complexas (ex: CHOOSE_N, ALL_OF) como hiperarestas em vez de expandi-las em cláusulas de pares, garantindo a aplicação exata de restrições como "escolha 3 de 9".
• Utilidade Personalizada: O sistema calcula uma pontuação $S(c)$ para cada curso baseada em:
  • Interesse semântico direto ($I_0$).
  • Difusão de grafo tipado ($I_D$), propagando interesse através de arestas de cumprimento e de listagem cruzada, mas não através de arestas de pré-requisito.
  • Valor de desbloqueio de pré-requisito ($U$), propagando interesse para trás ao longo dos caminhos de dependência.
  • Ganhos de Major/Educação Geral, valor de opção futura, carga de trabalho, risco e aversão.
• Otimização Lexicográfica CP-SAT: O planejador resolve para um conjunto ranqueado de planos usando uma ordem lexicográfica:
  1. Viabilidade Rígida (satisfazendo todas as restrições).
  2. Horizonte de conclusão mínimo.
  3. Carga de trabalho e risco de agendamento.
  4. Utilidade personalizada.
  5. Valor de opção futura.
     Cada estágio fixa o ótimo comprovado do estágio anterior como uma restrição rígida, preservando a certificabilidade dentro de um orçamento fixo do solver.
• Esclarecimento: Se o plano ideal variar entre as hipóteses de preferência restantes, o sistema faz perguntas direcionadas para reduzir o arrependimento esperado.

Principais Contribuições

1. Formulação: O artigo formula o planejamento de graduação a partir de fontes públicas como um problema de dois estágios de aquisição e otimização, tornando a circularidade aquisição–planejamento diretamente mensurável.
2. CatalogBrowse: Introduz um agente de exploração independente de perfil, apresentando exploração orientada por obrigações, extração vinculada à proveniência e uma regra de parada baseada em certificado que garante a completude da saída em relação a um snapshot congelado, verificando que todas as entradas descobertas foram processadas ou explicitamente falhas.
3. DegreeMap: Apresenta um planejador que combina um hipergrafo de requisitos tipados com otimização lexicográfica exata, avaliado através de trilhas de fonte mascarada e de ouro-versus-extraído pareadas.

Resultados

O sistema foi avaliado em uma trilha Broad-100 (100 universidades) e uma trilha Dense-6 (6 universidades com diversos formatos de fonte).

• Desempenho de Extração (CatalogBrowse):
  • Alcançou 96,2% de recall de inventário e 88,7% de recuperação de fonte mascarada (recuperando entidades atrás de páginas ocultas).
  • Utilizou 47% menos acessos à fonte do que um crawler exaustivo, superando baselines como agentes Static BFS e do tipo Go-Browse.
  • Manteve alto Typed F1 (79,4) e equivalência semântica de AST (77,8) na trilha broad.
• Desempenho de Planejamento (DegreeMap):
  • Manteve 100,0% de viabilidade rígida na trilha Dense-6.
  • Melhorou a utilidade personalizada em +0,066 sobre o baseline mais forte (MSGS do tipo LLMAP).
  • Reduziu o horizonte de conclusão de 6,7 para 6,3 períodos.
• Desempenho End-to-End:
  • O pipeline completo certificou 99,5% das solicitações de planejamento.
  • A lacuna de utilidade em relação ao planejamento sobre um grafo de currículo "ouro" privilegiado foi de apenas 0,015.
  • Estudos de ablação confirmaram que remover o certificado de ponto fixo reduziu o recall em 4,4 pontos, e usar um objetivo de soma ponderada em vez de otimização lexicográfica reduziu a viabilidade certificada em 4,0 pontos.

Significância

O artigo afirma que o KnowPlan remove a circularidade aquisição–planejamento por construção. Ao separar a aquisição do currículo (independente dos objetivos do estudante) da otimização do plano, o sistema torna a interface entre a aquisição de dados e o uso mensurável em vez de assumida. Os autores enfatizam que esta abordagem converte uma suposição de modelagem (que o currículo é conhecido) em uma quantidade medida, demonstrando que o planejamento de graduação confiável requer a aquisição de currículo independente de perfil antes da otimização específica do estudante. O framework é generalizável para qualquer domínio onde um agente deva adquirir um modelo de mundo para pontuar contra um objetivo posterior, desde que o alvo da aquisição seja fixo antes que o objetivo seja conhecido.