Resumo Técnico: Da Viabilidade à Desejabilidade: Estrutura Plan, Learn, Adapt (PLA)

1. Declaração do Problema

O artigo aborda o desafio de gerar itinerários de viagem personalizados e de vários dias em dispositivos móveis. Esta tarefa é definida por uma tensão fundamental entre viabilidade combinatória rígida e desejabilidade latente subjetiva:

• Viabilidade: Os itinerários devem aderir estritamente às restrições espaço-temporais, incluindo horários de funcionamento de POIs (Pontos de Interesse), tempos de deslocação, orçamentos de tempo diários e limites de custo.
• Desejabilidade: Os itinerários devem satisfazer preferências subjetivas do utilizador relativas ao ritmo, coerência geográfica e diversidade de categorias, que são difíceis de capturar com funções de objetivo estáticas e manuais.
• Viabilidade Operacional: As soluções devem ser implementáveis em dispositivos de utilizadores finais (especificamente ambientes iOS offline-first) com requisitos rigorosos de latência (velocidade interativa) e restrições de privacidade, o que exclui LLMs dependentes da nuvem.

As abordagens existentes falham em satisfazer simultaneamente todos estes três requisitos: os otimizadores clássicos garantem a viabilidade, mas carecem de um modelo de preferências matizado; os métodos baseados em aprendizagem capturam preferências, mas frequentemente violam restrições rígidas; e os LLMs, embora capazes de geração de linguagem natural, produzem frequentemente cronogramas inválidos (0% de viabilidade no benchmark dos autores) e são incompatíveis com a implementação móvel offline e de baixa latência.

2. Metodologia: A Estrutura PLA

Os autores propõem o Plan, Learn, Adapt (PLA), uma estrutura de três estágios concebida para abordar conjuntamente a viabilidade, a desejabilidade e a viabilidade operacional.

Fase 1: PLAN (Geração de Planos Diversos e Viáveis)

A fase Plan gera um conjunto estruturalmente diverso de itinerários candidatos viáveis utilizando um ensemble heterogéneo de cinco algoritmos de planeamento leves, todos partilhando uma camada de viabilidade unificada:

• Algoritmos: Greedy (construtivo), Programação Dinâmica (DP), Beam Search, A* Search e Simulated Annealing (SA).
• Camada de Viabilidade: Um módulo de lógica partilhado que impõe restrições rígidas (horas de visita, consistência de tempo de viagem, orçamentos de tempo/custo, sem repetições) e calcula os tempos de chegada mais cedo e viáveis.
• Objetivo: Embora todos os planeadores otimizem uma pontuação composta partilhada (equilibrando eficiência de viagem, tempo de espera, urgência, diversidade de categorias e popularidade de POI), os seus distintos paradigmas de pesquisa resultam em itinerários estruturalmente diferentes. Esta diversidade é crucial porque nenhum algoritmo único domina em todos os contextos de viagem.

Fase 2: LEARN (Modelagem de Preferências Humanas)

A fase Learn ajusta um modelo de recompensa compacto para capturar a satisfação latente do utilizador ao nível do itinerário, em vez de depender de pontuações por POI.

• Recolha de Dados: Foram recolhidas 2.519 comparações pareadas humanas de itinerários completos em mais de 100 cidades dos EUA. Os anotadores escolheram entre itinerários gerados por diferentes planeadores sem conhecer a sua origem.
• Arquitetura do Modelo: Um modelo de recompensa Bradley-Terry é treinado em aproximadamente 20 características interpretáveis ao nível do itinerário (ex: tempo total de viagem, entropia de categoria, equilíbrio de carga diária, folga de horário).
  • O modelo utiliza uma formulação baseada na diferença: $P(x_a \succ x_b) = \sigma(R_\theta(x_a) - R_\theta(x_b))$.
  • Restrições de Monotonicidade: O modelo impõe o conhecimento de domínio (ex: o aumento do tempo de viagem não deve aumentar a recompensa) diretamente durante a otimização.
• Seleção: O modelo de recompensa atua como um seletor, escolhendo o itinerário com a pontuação mais alta do conjunto diverso gerado na fase Plan.

Fase 3: ADAPT (Refinamento no Dispositivo)

A fase Adapt realiza o refinamento local guiado pela recompensa no itinerário semente selecionado, dentro de um orçamento de computação rigoroso e consciente do dispositivo.

• Edições que Preservam a Viabilidade: O sistema aplica operadores atómicos (Drop, Insert, Replace, Swap, Relocate, MoveDay) ao itinerário. Crucialmente, cada edição é seguida por um procedimento de re-temporização incremental que valida as restrições. Se uma edição violar uma restrição, ela é descartada. Isto garante que cada estado intermédio permanece viável, ao contrário dos métodos de reparação post-hoc.
• Estratégia de Pesquisa: Uma abordagem de hill-climbing com amostragem de vizinhança estocástica seleciona movimentos que melhoram a pontuação de recompensa.
• Consciência de Recursos: O processo de refinamento é limitado por um orçamento de tempo dinâmico (tipicamente ~200–500 ms) ajustado com base nos sinais do dispositivo (número de núcleos, memória, modo de energia) para garantir latência interativa.

3. Principais Contribuições

1. Ensemble de Planeadores Heterogéneos: Os autores demonstram empiricamente que nenhum algoritmo de planeamento único domina. Ao combinar cinco algoritmos distintos, alcançam uma taxa de vitória de 67,8% em comparações pareadas, uma melhoria de 11,2 pontos percentuais sobre o melhor planeador individual (DP).
2. Modelagem de Preferência ao Nível do Itinerário: Indo além da pontuação por POI, o artigo introduz um modelo Bradley-Terry compacto treinado em comparações de itinerários completos. Este modelo captura propriedades emergentes (ritmo, equilíbrio de dias) e alcança 6 de 67,6% de precisão em validação cruzada leave-one-city-out.
3. Refinamento no Dispositivo que Preserva a Viabilidade: A fase Adapt melhora a desejabilidade enquanto garante 100% de viabilidade por construção. Alcança uma latência média no dispositivo de 109,9 ms, permitindo execução totalmente offline e interativa.

4. Resultados Experimentais

• Viabilidade vs. LLMs: Num benchmark contra três LLMs de fronteira (GPT-5, Claude Opus 4.5, Gemini 3 Pro) em 294 itinerários, os LLMs atingiram 0% de viabilidade estrita, violando restrições como tempo de viagem e horas de visita. Em contraste, o PLA manteve 100% de viabilidade.
• Desempenho do Ensemble: O ensemble guiado por recompensa superou o melhor planeador individual em 11,2 pontos (67,8% vs. 56,6% de taxa de vitória). A distribuição de seleção mostrou alta entropia (97,6% do máximo), confirmando que diferentes algoritmos contribuem de forma única dependendo do contexto.
• Melhoria pelo Refinamento: A fase Adapt proporcionou melhorias de pontuação estatisticamente significativas em todos os algoritmos semente. Por exemplo, as sementes A* tiveram um aumento de 11,7%, enquanto as sementes do ensemble, já de alta pontuação, melhoraram 3,9%.
• Impacto na Produção: Implementado na aplicação iOS FlyEnJoy, o PLA aumentou as taxas de conclusão de itinerários em 91% e as iniciações em 83% comparativamente a uma base de heurística única, reduzindo simultaneamente o tempo médio de sessão por utilizador em 38%.

5. Significância e Alegações

O artigo alega que o PLA fornece um plano viável para o planeamento alinhado com humanos sob restrições de implementação do mundo real. A sua significância reside na resolução do compromisso entre viabilidade e desejabilidade sem depender de IA na nuvem:

• Robustez: Ao separar a viabilidade (Plan) da aprendizagem de preferências (Learn) e utilizar o refinamento que preserva a viabilidade (Adapt), o sistema evita o problema do "cronograma inválido" comum em abordagens de aprendizagem e IA generativa.
• Portabilidade: O uso de um modelo de recompensa compacto e interpretável e de operadores de pesquisa leves permite que o sistema corra inteiramente no dispositivo, suportando casos de uso offline (aeroportos, voos) onde as APIs de nuvem não estão disponíveis ou são demasiado dispendiosas.
• Praticidade: O framework demonstra que o planeamento complexo de vários dias pode ser executado com latência interativa (<300 ms) enquanto adere estritamente a restrições rígidas, uma capacidade que os atuais LLMs de fronteira não possuem neste domínio específico.

Os autores concluem que, embora os LLMs tenham dificuldade com restrições rígidas, uma abordagem híbrida estruturada, combinando otimização clássica, aprendizagem de preferências e pesquisa local com restrições, pode entregar resultados superiores e prontos para produção para a geração de itinerários personalizados.