Por que a programação com planejadores é surpreendente

 (hillelwayne.com)
2 pontos por GN⁺ 2024-02-22 | 1 comentários | Compartilhar no WhatsApp
  • O módulo planner do Picat vai além da programação lógica que encontra atribuições de valores e expressa o problema como uma sequência de mudanças de estado até chegar ao estado objetivo
  • Ao definir o estado inicial Start, as regras de transição action(From, To, Action, Cost) e a condição de término final(S), best_plan(Start, Plan) encontra o plano de menor custo até o estado final
  • No exemplo de caminho em grade, movimentação, limites de borda, desvio de obstáculos e visita a vários objetivos são tratados apenas alterando action e final, e a ordem de visita dos objetivos também pode ser fixa ou livre
  • O recurso de planejamento pode ser combinado com resolução de restrições, permitindo expressar problemas como encontrar a maior sublista que pode ser dividida em somas iguais removendo elementos no partition problem
  • O Picat é uma linguagem de pesquisa, então faltam documentação e mensagens de erro melhores, mas como linguagem-ferramenta para resolver rapidamente certos problemas computacionais, pode oferecer soluções mais concisas do que linguagens gerais

A ideia básica de Picat e da programação com planejadores

  • Picat é uma linguagem de pesquisa que busca combinar programação lógica, programação imperativa e resolução de restrições
  • Na programação imperativa e funcional comum, escreve-se um algoritmo que produz saídas a partir de entradas; já a programação lógica e a resolução de restrições encontram atribuições de valores que satisfazem relações
  • No Picat, identificadores não funcionais que começam com minúscula são atoms como a, b, c, e identificadores que começam com maiúscula são variáveis
  • Mesmo em expressões com uma variável ainda não definida Y, como member(Y, Arr), o Picat pode encontrar e atribuir valores que tornem a expressão verdadeira
    • Se Arr = [a, b, c, a], então Y pode ser um entre a, b e c
    • Em seguida, ao adicionar uma condição como X != Y, os valores possíveis ficam mais restritos
    • Mesmo quando a própria lista ainda é desconhecida, como em member(a, Z), é possível instanciar Z como uma lista

Planejamento encontra mudanças de estado, não atribuições de valor

  • Em vez de encontrar valores de variáveis que satisfaçam equações, o planejamento busca uma sequência de mudanças de variáveis que alcance um estado final específico
  • Um problema de planejamento no Picat precisa de três elementos
    • O estado inicial Start
    • Funções action que representam transições de estado
    • final(S) para decidir se um estado é final
  • As funções action do Picat devem todas se chamar action e recebem quatro parâmetros
    • Estado atual
    • Próximo estado
    • Nome da ação
    • Custo
  • best_plan(Start, Plan) atribui a Plan o plano de menor número de etapas ou menor custo necessário para chegar ao estado final
    • Se todos os custos forem 1, o custo do plano passa a ser o número total de movimentos
    • Se qualquer plano servir, independentemente do tamanho, pode-se usar plan(Start, Plan)

Exemplo de busca de caminho em grade

  • O problema de exemplo consiste em um marcador sobre uma grade que parte da origem (0, 0) e deve chegar a uma coordenada alvo
    • Em cada etapa, ele pode se mover uma casa para cima, baixo, esquerda ou direita
    • Não pode sair dos limites da grade
    • Ao chegar à coordenada alvo, obtém sucesso
  • O estado inicial armazena juntos a posição atual e o objetivo, como em {Origin, Goal}
    • Em Picat, {a, b} é sintaxe de array, mas na prática é usada como uma tupla
  • A condição de término pode ser expressa com pattern matching, como em final({Pos, Goal}) => Pos = Goal.
    • Para escrever a mesma coisa sem pattern matching, seria preciso primeiro decompor o estado em {Pos, Goal}
    • Se houver várias condições final, o plano terá sucesso quando qualquer uma delas for verdadeira
  • A ação de movimento escolhe uma entre quatro direções {-1,0}, {1,0}, {0,-1}, {0,1} e verifica se a nova coordenada está no intervalo 0..10
    • member({Dx, Dy}, Dir) é usado para encontrar valores de direção possíveis
    • member(Tx, 0..10) e member(Ty, 0..10) são usados para verificar se a coordenada está dentro dos limites
    • Para um predicado de verificação sem atribuição de valor, também existe membchk
  • O plano resultante é exibido como uma lista de ações de movimento e novas coordenadas, como {move,{1,0}}, {move,{2,0}}
    • Um script em Raku pode ser usado para visualizar o caminho
    • Ao adicionar uma condição como {Tx, Ty} != {2, 1}, também é possível fazer desvio de obstáculos para evitar coordenadas específicas

Vários objetivos e minimização de custo

  • Para visitar vários objetivos, Goal deixa de ser uma única coordenada e passa a ser uma fila de objetivos, como [{2, 2}, {3, 4}]
  • Adiciona-se uma nova action que remove o item correspondente da lista de objetivos quando se chega a um objetivo
    • [Head|Tail] divide uma lista entre o primeiro elemento e o restante
    • Goal = [Pos|Rest] só é verdadeiro quando a posição atual Pos coincide com o primeiro item da lista de objetivos
    • Se o novo estado for {Pos, Rest}, o objetivo alcançado é removido
  • O critério para saber se todos os objetivos foram visitados passa a ser final({Pos, Goal}) => Goal = [].
    • A condição de término deixa de ser se a posição atual coincide com um objetivo específico e passa a ser se a lista de objetivos está vazia
  • Visitar os objetivos em uma ordem fixa nem sempre produz o caminho global mais curto
  • Para ignorar a ordem dos objetivos e minimizar o caminho total, a ação mark é alterada
    • Em vez de Goal = [Pos|Rest], usa-se member(Pos, Goal) para verificar se a posição atual aparece em qualquer lugar da lista de objetivos
    • To = {Pos, delete(Goal, Pos)} remove da lista o objetivo visitado
    • Nesse modelo, o Picat pode escolher qual objetivo visitar em seguida para minimizar o comprimento total do caminho

Combinação de planejamento e resolução de restrições

  • O recurso de planejamento do Picat é integrado a outras funcionalidades da linguagem, permitindo usar planejamento junto com resolução de restrições
  • O partition problem usado como exemplo é um problema NP-completo em que uma lista de números deve ser dividida em dois grupos com a mesma soma
  • Esse programa remove elementos da lista de números para encontrar a maior sublista que pode ser particionada em somas iguais
    • Remover elementos da lista de entrada é tratado como uma ação de planejamento
    • final(Numbers) verifica se existe uma solução de partition válida para aquela lista de números
    • Com as restrições do módulo cp, cada elemento é representado por uma variável 0..1 indicando se entra no grupo da esquerda ou da direita
    • A restrição exige que a soma total seja o dobro da soma de um dos lados
  • Na saída de exemplo, após remover [5,17], a lista restante pode ser dividida em dois grupos que somam 1108 cada
    • 32+99+977=1108
    • 122+77+86+59+47+154+141+172+49+62+109+30=1108
  • Essa abordagem não para em resolver diretamente uma restrição válida: ela também expressa em forma de planejamento as mudanças necessárias para chegar a um estado com restrições válidas

Limitações e usos adequados do Picat

  • Como o Picat é uma linguagem de pesquisa, seu uso em produção não é recomendado
  • Ela não tem muitos recursos de conveniência e também carece de boa documentação e mensagens de erro claras
    • Quando não existe um plano solucionável, o erro aparece como *** error(failed,main/0)
  • O fato de rodar no Windows é visto como uma vantagem em relação a muitas linguagens de pesquisa
  • O Picat se parece menos com uma linguagem para escrever código que será mantido ou compartilhado e mais com uma linguagem de toolkit voltada a resolver certos tipos de problemas computacionais
  • Alguns problemas que eram difíceis de tratar com linguagens de programação gerais e resolvedores de restrições podem ser resolvidos de forma bastante elegante com Picat

Outras linguagens de planejamento e conceitos relacionados

  • O planejamento foi originalmente desenvolvido em robótica e IA, mas hoje aparece com frequência em IA para videogames sob o nome Goal Oriented Action Planning (GOAP)
  • PDDL é uma linguagem de descrição de planejamento usada como entrada por planejadores independentes
    • Ela cumpre um papel semelhante ao do DIMACS no SAT como formato de descrição

Leituras relacionadas

1 comentários

 
GN⁺ 2024-02-22
Comentários do Hacker News

  • Já usei o modo de planejamento do Picat em trabalho real
    Fiz um protótipo de um sistema para coordenar a manutenção de conjuntos de vários equipamentos, e o modelo era inserir “o que você quer”, “quais ações são possíveis” e “quais restrições precisam ser respeitadas”, não “como fazer”
    Em exemplos pequenos ele criava bem planos ótimos, mas, quando cresceu para uma escala real, desmoronou como esperado; problemas de planejamento acabam sendo EXPTIME, então os limites eram grandes
    O Picat tem uma válvula de escape para definir heurísticas, então fiz um random forest de predicados de estado e um classificador Naive Bayes preverem caminhos promissores, mas, mesmo com restrições de quebra de simetria e planejamento hierárquico, dava trabalho demais
    Parece que ainda há um inverno da IA no domínio clássico da GOFAI
    Talvez não, se o problema de planejamento for reformulado para retornar um “gerador em tempo polinomial que produz planos potencialmente exponencialmente longos”

    • Solvers comerciais têm desempenho muito melhor que os open source e também esvaziam sua carteira muito mais rápido
      CPLEX, Xpress, GUROBI e Hexaly me vêm à mente, e o Hexaly é especialmente bom para problemas de escalonamento ou roteamento de veículos
      Em geral, você acessa isso por APIs para linguagens muito usadas na indústria; acho que essa abordagem faz muito mais sentido do que linguagens dedicadas de solvers, que são fracas para tarefas gerais
      Chamar o GUROBI a partir de Python é muito fácil, e você também pode usar normalmente os recursos gerais do Python
      O Mosek é muito mais barato que o GUROBI, mas as APIs de ambos são de nível bem baixo, e o desempenho também não chega ao do GUROBI
    • Nesse caso, algo como CP-SAT(https://developers.google.com/optimization/cp) provavelmente teria escalado bem
      Esse solver lida facilmente com uma quantidade absurda de variáveis e restrições, e as heurísticas embutidas também são excelentes
    • Planejadores antigos reduziam o espaço de busca incluindo metarregras ou heurísticas para decidir quais regras aplicar
      Alguns sistemas dividiam o problema em representações diferentes e acoplavam solvers automáticos especializados
      Jahob Analysis System e Cyc me vêm à mente
      Do ponto de vista de uso real, o design mais limpo da IA clássica foi o Procedural Reasoning System, e eu gostaria de ver uma versão refeita que compensasse seus pontos fracos com métodos modernos
      https://en.wikipedia.org/wiki/Procedural_reasoning_system
    • Fico me perguntando por que não existem solvers open source de alta qualidade
      Em outras áreas de computação numérica, muitas vezes o estado da arte é open source, então sempre me perguntei por que a área de otimização é diferente
    • Em termos de resultado ou desempenho, fico com a impressão de que talvez não seja muito diferente de uma busca em profundidade escrita de qualquer jeito, com uma lembrança vaga de Prolog

  • Há um site do hakank, usuário ativo do HN na comunidade de programação por restrições, ou seja, Hakan Kjellerstrand, com muitos materiais e exemplos de Picat: http://www.hakank.org/picat/

  • Como de costume, eu recomendaria Prolog
    É elegante, fácil de entender e mais maduro; se você quer resolução de restrições em domínios finitos, a configuração básica já é suficiente
    Além disso, o MiniZinc é uma ótima interface para acessar vários solvers especializados em diferentes finalidades, então, se você não for especialista, é provável que chegue mais perto do resultado desejado
    Prolog tem muitas vantagens, mas o “faro mecânico” necessário para obter bom desempenho pode crescer bastante rapidamente
    Se você escreveu algo em Picat, vale pensar também em como escreveria a mesma coisa em outras linguagens
    Esses problemas de brinquedo também são fáceis em outras linguagens, e, na maioria das linguagens funcionais, Dijkstra ou A* cabem em poucas linhas; no fim das contas, muitas vezes tudo se resume a definir o espaço de estados do algoritmo de busca

  • Fiquei feliz, mas ao mesmo tempo nem um pouco surpreso, ao ver Predrag como revisor
    O Firebase technical screen teria sido muito mais fácil com uma ferramenta dessas, e no fim era só mais um problema de otimização
    Dá até vontade de resolver de novo em Picat
    Ele também faz coisas interessantes na área de linguagens de programação: https://github.com/obi1kenobi/trustfall

  • Meu primeiro pensamento foi: “parece um sistema de tipos que você precisa resolver manualmente”
    Tentei expressar isso ingenuamente em TypeScript, mas a, b e c podiam ser todos iguais, então nada era resolvido
    Ao tentar expressar corretamente, cheguei a uma forma que parecia utilizável até certo ponto, mas ainda precisava usar assertions e também não conseguia representar direito o tipo de Y
    Esse processo, na verdade, mostra o quanto programas no estilo de planejadores são poderosos em termos de simplicidade e concisão
    TypeScript não parece poderoso o bastante para expressar esse tipo de restrição
    Link do experimento no TS Playground: http://tinyurl.com/3p2pzdtn

  • É bom ver GOAP sendo mencionado de novo
    Era o ingrediente secreto que tornava os inimigos de F.E.A.R. tão interessantes, e o artigo de Jeff Orkin sobre como ele funciona também é fácil e divertido de ler

  • Uso Prolog e um pouco de CLPFD em trabalho real, e é realmente ótimo
    Gostaria que estivesse em todos os lugares; mais exatamente, gostaria de manter um núcleo lógico que enfatizasse pureza e empurrar o comportamento imperativo para as bordas
    É uma pena que a indústria pareça presa a ferramentas tão ruins

  • Parece parecido com Prolog e é interessante

  • Esse estilo de programação em si não é totalmente novo
    Aprendi Prolog na universidade e parece bem parecido, mas Prolog não tinha recurso de planejador
    Ainda assim, um planejador é uma forma muito elegante e simples de resolver problemas
    A parte sobre videogames no fim do texto me deixou curioso
    O recurso de planejador permite resolver problemas com muita facilidade em poucas linhas de código claro, mas como será o desempenho em comparação com um algoritmo escrito de forma imperativa?
    O Picat parece bastante eficiente em comparação com linguagens semelhantes [1], mas não encontrei uma comparação com linguagens “padrão”
    [1]: https://arxiv.org/abs/1405.2538

  • Eu também tenho o sonho de simplesmente dizer ao computador qual estado ele precisa alcançar
    Não conheço bem a comunidade de planejamento nem os solvers, e só brinquei ingenuamente com ortools, mas já tentei gerar código para ir de um estado a um estado-alvo usando A*
    Ele gerava instruções assembly para se mover entre estados e até descobria transições de estado ocultas em chamadas de função para chegar ao objetivo
    Para acelerar a busca, também rodei em paralelo com Python multiprocessing, e usei geração dinâmica de vizinhos porque cada thread gerava vizinhos de modo diferente
    Na tentativa original, paralelizar A* era difícil, então foi preciso fazer sharding
    O sonho do meu experimento é informar ao computador “o que tenho agora” e “o que quero” para que ele encontre sozinho o caminho correto de movimentação
    Pessoalmente, vejo programação mais como logística, tipo Factorio ou uma fábrica
    Por isso chamo de “sliding puzzle”, porque é um quebra-cabeça em que você precisa mover coisas de um lado para o outro para ver a imagem correta
    Repositório no GitHub e anotações: https://github.com/samsquire/sliding-puzzle-codegen-memory
    Replit: https://replit.com/@Chronological/SlidingPuzzle3