Planejamento e programação automatizados - Automated planning and scheduling

O planejamento e programação automatizados , às vezes denotados simplesmente como planejamento de IA , é um ramo da inteligência artificial que diz respeito à realização de estratégias ou sequências de ação, normalmente para execução por agentes inteligentes , robôs autônomos e veículos não tripulados . Ao contrário dos problemas clássicos de controle e classificação , as soluções são complexas e devem ser descobertas e otimizadas em um espaço multidimensional. O planejamento também está relacionado à teoria da decisão .

Em ambientes conhecidos com modelos disponíveis, o planejamento pode ser feito offline. As soluções podem ser encontradas e avaliadas antes da execução. Em ambientes dinamicamente desconhecidos, a estratégia geralmente precisa ser revisada online. Modelos e políticas devem ser adaptados. As soluções geralmente recorrem a processos iterativos de tentativa e erro comumente vistos na inteligência artificial . Isso inclui programação dinâmica , aprendizado por reforço e otimização combinatória . As linguagens usadas para descrever o planejamento e a programação são freqüentemente chamadas de linguagens de ação .

Visão geral

Dada uma descrição dos possíveis estados iniciais do mundo, uma descrição dos objetivos desejados e uma descrição de um conjunto de ações possíveis, o problema de planejamento é sintetizar um plano que é garantido (quando aplicado a qualquer um dos estados iniciais) para gerar um estado que contém as metas desejadas (tal estado é chamado de estado de meta).

A dificuldade de planejamento depende das premissas simplificadoras empregadas. Diversas classes de problemas de planejamento podem ser identificadas, dependendo das propriedades que os problemas possuem em várias dimensões.

As ações são determinísticas ou não determinísticas? Para ações não determinísticas, as probabilidades associadas estão disponíveis?
As variáveis de estado são discretas ou contínuas? Se forem discretos, eles têm apenas um número finito de valores possíveis?
O estado atual pode ser observado de forma inequívoca? Pode haver observabilidade total e observabilidade parcial.
Quantos estados iniciais existem, finitos ou arbitrariamente muitos?
As ações têm duração?
Várias ações podem ser executadas simultaneamente ou apenas uma ação é possível por vez?
O objetivo de um plano é atingir um determinado estado de meta ou maximizar uma função de recompensa ?
Existe apenas um agente ou existem vários agentes? Os agentes são cooperativos ou egoístas? Todos os agentes constroem seus próprios planos separadamente ou os planos são construídos centralmente para todos os agentes?

O problema de planejamento mais simples possível, conhecido como Problema de Planejamento Clássico, é determinado por:

um único estado inicial conhecido,
ações sem duração,
ações determinísticas,
que pode ser feito apenas um de cada vez,
e um único agente.

Como o estado inicial é conhecido sem ambigüidades e todas as ações são determinísticas, o estado do mundo após qualquer sequência de ações pode ser previsto com precisão, e a questão da observabilidade é irrelevante para o planejamento clássico.

Além disso, os planos podem ser definidos como sequências de ações, porque sempre se sabe com antecedência quais ações serão necessárias.

Com ações não determinísticas ou outros eventos fora do controle do agente, as possíveis execuções formam uma árvore, e os planos devem determinar as ações apropriadas para cada nó da árvore.

Os processos de decisão de Markov em tempo discreto (MDP) são problemas de planejamento com:

ações sem duração,
ações não determinísticas com probabilidades,
observabilidade total,
maximização de uma função de recompensa,
e um único agente.

Quando a observabilidade total é substituída pela observabilidade parcial, o planejamento corresponde ao processo de decisão de Markov parcialmente observável (POMDP).

Se houver mais de um agente, temos o planejamento multiagente , que está intimamente relacionado à teoria dos jogos .

Planejamento independente de domínio

No planejamento de IA, os planejadores normalmente inserem um modelo de domínio (uma descrição de um conjunto de ações possíveis que modelam o domínio), bem como o problema específico a ser resolvido especificado pelo estado inicial e objetivo, em contraste com aqueles em que não há domínio de entrada especificado. Esses planejadores são chamados de "independentes de domínio" para enfatizar o fato de que podem resolver problemas de planejamento em uma ampla gama de domínios. Exemplos típicos de domínios são empilhamento de blocos, logística, gerenciamento de fluxo de trabalho e planejamento de tarefas do robô. Portanto, um único planejador independente de domínio pode ser usado para resolver problemas de planejamento em todos esses vários domínios. Por outro lado, um planejador de rotas é típico de um planejador específico de domínio.

Linguagens de modelagem de domínio de planejamento

As linguagens mais comumente usadas para representar domínios de planejamento e problemas de planejamento específicos, como STRIPS e PDDL para Planejamento Clássico, são baseadas em variáveis de estado. Cada estado possível do mundo é uma atribuição de valores às variáveis de estado, e as ações determinam como os valores das variáveis de estado mudam quando essa ação é executada. Uma vez que um conjunto de variáveis de estado induz um espaço de estado que tem um tamanho exponencial no conjunto, o planejamento, assim como muitos outros problemas computacionais, sofre com a maldição da dimensionalidade e da explosão combinatória .

Uma linguagem alternativa para descrever problemas de planejamento é a das redes hierárquicas de tarefas , nas quais um conjunto de tarefas é fornecido, e cada tarefa pode ser realizada por uma ação primitiva ou decomposta em um conjunto de outras tarefas. Isso não envolve necessariamente variáveis de estado, embora em aplicativos mais realistas as variáveis de estado simplifiquem a descrição de redes de tarefas.

Algoritmos para planejamento

Planejamento clássico

pesquisa de espaço de estado com encadeamento direto , possivelmente aprimorada com heurísticas
pesquisa de encadeamento reverso , possivelmente aprimorada pelo uso de restrições de estado (consulte STRIPS , graphplan )
planejamento de pedido parcial

Redução a outros problemas

redução ao problema de satisfazibilidade proposicional ( satplan ).
redução à verificação de modelo - ambos são essencialmente problemas de atravessar espaços de estados, e o problema de planejamento clássico corresponde a uma subclasse de problemas de verificação de modelo.

Planejamento temporal

O planejamento temporal pode ser resolvido com métodos semelhantes ao planejamento clássico. A principal diferença é, devido à possibilidade de várias ações temporariamente sobrepostas com uma duração serem executadas simultaneamente, que a definição de um estado deve incluir informações sobre o tempo absoluto atual e até que ponto a execução de cada ação ativa avançou. Além disso, no planejamento com tempo racional ou real, o espaço de estados pode ser infinito, ao contrário do planejamento clássico ou do planejamento com tempo inteiro. O planejamento temporal está intimamente relacionado a problemas de programação . O planejamento temporal também pode ser entendido em termos de autômatos cronometrados .

Planejamento probabilístico

O planejamento probabilístico pode ser resolvido com métodos iterativos, como iteração de valor e iteração de política , quando o espaço de estado é suficientemente pequeno. Com a observabilidade parcial, o planejamento probabilístico é resolvido de forma semelhante com métodos iterativos, mas usando uma representação das funções de valor definidas para o espaço de crenças em vez de estados.

Planejamento baseado em preferências

No planejamento baseado em preferências, o objetivo não é apenas produzir um plano, mas também satisfazer as preferências especificadas pelo usuário . Uma diferença para o planejamento baseado em recompensa mais comum, por exemplo, correspondendo a MDPs, as preferências não têm necessariamente um valor numérico preciso.

Planejamento condicional

O planejamento determinístico foi introduzido com o sistema de planejamento STRIPS , que é um planejador hierárquico. Os nomes das ações são ordenados em uma sequência e este é um plano para o robô. O planejamento hierárquico pode ser comparado a uma árvore de comportamento gerada automaticamente . A desvantagem é que uma árvore de comportamento normal não é tão expressiva como um programa de computador. Isso significa que a notação de um gráfico de comportamento contém comandos de ação, mas nenhum loop ou instruções if-then. O planejamento condicional supera o gargalo e introduz uma notação elaborada que é semelhante a um fluxo de controle , conhecido de outras linguagens de programação como Pascal . É muito semelhante à síntese de programa , o que significa que um planejador gera código-fonte que pode ser executado por um interpretador.

Um dos primeiros exemplos de planejador condicional é o “Warplan-C”, que foi introduzido em meados dos anos 1970. Qual é a diferença entre uma sequência normal e um plano complicado, que contém declarações se-então? Tem a ver com a incerteza no tempo de execução de um plano. A ideia é que um plano pode reagir a sinais de sensores que são desconhecidos para o planejador. O planejador gera duas opções antecipadamente. Por exemplo, se um objeto foi detectado, a ação A é executada; se um objeto estiver ausente, a ação B é executada. Uma grande vantagem do planejamento condicional é a capacidade de lidar com planos parciais . Um agente não é forçado a planejar tudo do início ao fim, mas pode dividir o problema em partes . Isso ajuda a reduzir o espaço de estado e resolve problemas muito mais complexos.

Planejamento contingente

Falamos de "planejamento contingente" quando o ambiente é observável por meio de sensores, que podem ser defeituosos. É, portanto, uma situação em que o agente de planejamento atua sob informações incompletas. Para um problema de planejamento contingente, um plano não é mais uma sequência de ações, mas uma árvore de decisão, porque cada etapa do plano é representada por um conjunto de estados em vez de um único estado perfeitamente observável, como no caso do planejamento clássico. As ações selecionadas dependem do estado do sistema. Por exemplo, se chover, o agente opta por levar o guarda-chuva e, caso não chova, pode optar por não o levar.

Michael L. Littman mostrou em 1998 que com ações de ramificação, o problema de planejamento torna-se EXPTIME -completo. Um caso particular de planejamento contíguo é representado por problemas FOND - para "totalmente observável e não determinístico". Se a meta for especificada em LTLf (lógica de tempo linear em rastreio finito), o problema será sempre EXPTIME-complete e 2EXPTIME-complete se a meta for especificada com LDLf.

Planejamento em conformidade

O planejamento em conformidade é quando o agente está incerto sobre o estado do sistema e não pode fazer nenhuma observação. O agente então tem crenças sobre o mundo real, mas não pode verificá-las com ações sensoriais, por exemplo. Esses problemas são resolvidos por técnicas semelhantes às do planejamento clássico, mas onde o espaço de estados é exponencial no tamanho do problema, devido à incerteza sobre o estado atual. Uma solução para um problema de planejamento em conformidade é uma sequência de ações. Haslum e Jonsson demonstraram que o problema de planejamento em conformidade é EXPSPACE -completo e 2EXPTIME-completo quando a situação inicial é incerta e há não-determinismo nos resultados das ações.

Implantação de sistemas de planejamento

O Telescópio Espacial Hubble usa um sistema de curto prazo chamado SPSS e um sistema de planejamento de longo prazo chamado Spike .

Veja também

Listas

Referências

Leitura adicional

Vlahavas, I. "Planejamento e Programação" . EETN . Arquivado do original em 22/12/2013.

links externos

Conferência Internacional sobre Planejamento e Programação Automatizada

Languages

In other projects