Planejamento e agendamento automatizado

O planejamento e o planejamento automáticos, às vezes denotados simplesmente como Planejamento da IA, são 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 no 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. Estes incluem programação dinâmica, aprendizado por reforço e otimização combinatória. Os idiomas usados ​​para descrever o planejamento e o planejamento geralmente são chamados de idiomas de ação.

visão global
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 contenha os objetivos desejados (tal estado é chamado de estado de meta).

A dificuldade de planejamento depende das suposições simplificadoras empregadas. Várias 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 deterministas 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 eles são discretos, eles têm apenas um número finito de valores possíveis?
O estado atual pode ser observado sem ambigüidade? Pode haver observabilidade total e observação 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 somente uma ação é possível de cada vez?
O objetivo de um plano é alcançar um objetivo designado 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 o Problema de Planejamento Clássico, é determinado por:

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

Como o estado inicial é conhecido sem ambigüidade, 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 exatidã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 conhecido de antemão 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.

Processos de decisão de Markov em tempo discreto (MDP) estão planejando problemas 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 completa é substituída pela observação parcial, o planejamento corresponde ao processo de decisão Markov parcialmente observável (POMDP).

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

Planejamento Independente de Domínio
No Planejamento da 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 “Independente de domínio” para enfatizar o fato de que podem resolver problemas de planejamento de uma ampla gama de domínios. Exemplos típicos de domínios são o empilhamento de blocos, a logística, o gerenciamento do fluxo de trabalho e o planejamento de tarefas do robô. Assim, um único planejador independente de domínio pode ser usado para resolver problemas de planejamento em todos esses domínios. Por outro lado, um planejador de rotas é típico de um planejador específico de domínio.

Planejando Idiomas de Modelagem de Domínio
As linguagens mais 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 para as variáveis ​​de estado e as ações determinam como os valores das variáveis ​​de estado mudam quando essa ação é executada. Como um conjunto de variáveis ​​de estado induz um espaço de estados que tem um tamanho exponencial no conjunto, o planejamento, assim como muitos outros problemas computacionais, sofre com a maldição da dimensionalidade e com a explosão combinatória.

Uma linguagem alternativa para descrever problemas de planejamento é a das redes de tarefas hierárquicas, nas quais um conjunto de tarefas é dado, 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 variáveis ​​de estado de aplicativos mais realistas simplifiquem a descrição de redes de tarefas.

Algoritmos para planejamento
Planejamento clássico
busca de espaço de estado de encadeamento direto, possivelmente aprimorada com heurística
pesquisa de encadeamento reverso, possivelmente aprimorada pelo uso de restrições de estado (consulte STRIPS, graphplan)
planejamento de ordem parcial

Planejamento clássico
O planejamento tradicional é baseado em duas suposições:

o determinismo das ações. Por exemplo, a ação “colocar um cubo na mesa” é determinística. Ao executá-lo, passamos de um estado para outro. Pelo contrário, “jogue um dado” não é determinista porque existem valores possíveis. A ação “role um dado” não se enquadra no escopo do planejamento tradicional.
a perfeita observação. O agente (o robô, o programa, etc.) conhece o estado do mundo completamente.

No planejamento clássico, é uma questão de procurar por uma sequência de ações (por exemplo, “pegar uma panela”, “colocar água”, “colocar massa”, “acender uma fogueira”, “alcançar”, “apagar” fogo”). O algoritmo A * é um exemplo típico de um algoritmo de planejamento clássico, geralmente usado em cursos introdutórios por sua simplicidade. Aqui estão algumas técnicas algorítmicas usadas em planejadores clássicos:

a pesquisa direta em um espaço de estados: algoritmo de planejamento de pesquisa heurística (HSP), algoritmo Fast-Forward (FF),
a busca de volta em um espaço de estado,
a pesquisa antes em um espaço de planos, graphplan
relaxamento de um problema de planejamento: calcular um problema relaxado para o qual é mais fácil saber se existe um plano que ajude a resolver o problema inicial
a transformação para um problema de satisfabilidade de uma fórmula de lógica proposicional.

Bylander demonstrou em 1994 que o planejamento convencional é PSPACE-complete.

Redução para outros problemas
redução do problema de satisfabilidade proposicional (satplan).
Redução para verificação de modelos – ambos são essencialmente problemas de atravessar espaços de estado, 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 é que, devido à possibilidade de várias ações temporalmente sobrepostas com uma duração simultânea, 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 ocorreu. Além disso, no planejamento com tempo racional ou real, o espaço de estados pode ser infinito, diferentemente do planejamento clássico ou do planejamento com tempo inteiro. O planejamento temporal está intimamente relacionado a problemas de agendamento. 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 estados é suficientemente pequeno. Com a observabilidade parcial, o planejamento probabilístico é similarmente resolvido 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 recompensas mais comum, por exemplo, correspondente aos 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. Nomes de ação são ordenados em uma sequência e esse é 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 não há loops 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 programas, o que significa que um planejador gera um código-fonte que pode ser executado por um intérprete.

Um dos primeiros exemplos de um planejador condicional é o “Warplan-C”, que foi introduzido em meados da década de 1970. Até agora, a questão não foi respondida qual é a diferença entre uma sequência normal e um plano complicado, que contém instruções if-then. Tem a ver com a incerteza em 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 com antecedência. Por exemplo, se um objeto foi detectado, a ação A será executada, se um objeto estiver faltando, a ação B será executada. Uma grande vantagem do planejamento condicional é a capacidade de lidar com planos parciais. Um agente não é obrigado 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.

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.

Outros tipos de planejamento
Na prática, só verifica raramente as hipóteses do planejamento clássico. É por isso que muitas extensões surgiram.

Related Post

Planejamento em conformidade
Falamos sobre planejamento em conformidade (cronograma de conformidade) em que o sistema está em um estado incerto, mas nenhuma observação é possível. O agente então tem crenças sobre o mundo real. Esses problemas são resolvidos por técnicas semelhantes às do planejamento tradicional, mas onde o espaço de estados é exponencial no tamanho do problema, devido à incerteza sobre o status atual. Uma solução para um problema de programação conforme é uma seqüência de ações.

Planejamento de contingência
Planejamento de contingência (planejamento contingente) em que o ambiente é observável por meio de sensores, que podem estar com defeito. 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 estágio do plano é representado por um conjunto de estados, em vez de um único estado perfeitamente observável, como no caso do planejamento clássico.

Rintanen demonstrou em 2004 que, se a ramificação é adicionada (planejamento contingente), o problema de planejamento torna-se EXPTIME -completo. Um caso particular de planejamento contíguo é representado pelos problemas FOND – por “totalmente observável e não determinista”. Se a meta for especificada em LTLf (lógica temporal linear sobre traço finito), o problema é sempre EXPTIME-complete 16 e 2EXPTIME-complete para uma especificação de propósito em LDLf.

Se, além disso, se adicionar incerteza ao planejamento tradicional (isto é, planejamento conforme), ele se tornará EXPSPACE -completo. Se adicionarmos ramificação e incerteza (planejando tanto compliant quanto contingent), ela se torna 2EXPTIME-complete.

Planejamento probabilístico
Kushmerick et al. introduziu o planejamento probabilístico. Em seu trabalho, o efeito das ações é descrito com os probabilistas. Ele dá o exemplo da ação ‘o robô pega um bloco’ descrito da seguinte maneira: se a garra do robô estiver seca, o robô segura o bloco com uma probabilidade de 0,95; Se o grampo estiver molhado, o robô segura o bloco com uma probabilidade de 0,5.

Isso leva ao problema de geração de política (ou estratégia) para um Processo de Decisão de Markov (MDP) ou (no caso geral) um Processo de Decisão de Markov Parcialmente Observável (POMDP).

Planejamento Não Linear
O planejamento clássico resolve sub-metas em uma determinada ordem. O problema é que às vezes leva a destruir o que já foi construído. Esse fenômeno é conhecido como a anomalia de Sussman.

Suponha que um indivíduo descalço esteja na mesma condição em que está usando o sapato direito, o sapato esquerdo, a meia direita e a meia esquerda. Se ele procura alcançar os objetivos na ordem do enunciado, ele falhará.

Para resolver este tipo de problema, pode-se passar para planos parcialmente ordenados nos quais a ordem entre as ações é fixada apenas quando for necessário (compromisso no último ou no mínimo planejamento de compromisso).

No exemplo anterior, coloque o sapato esquerdo deve ser feito depois de colocar a meia esquerda. O mesmo para a direita. Por outro lado, a execução do plano para a esquerda é independente da execução para a direita. O plano global é, portanto, parcialmente ordenado.

Os planejadores capazes de lidar com essa categoria de problema são considerados de ordem parcial (POP, NOAH, etc.).

Planejamento hierárquico
Geralmente, ao planejar, pode-se ter uma informação hierárquica sobre as ações, isto é, uma descrição de como ações complexas são decompostas. Por exemplo, uma ação complexa como “servir um café” pode ser dividida na sequência de duas ações complexas “fazendo um café” e depois “trazendo café”. Assim, existem planejadores, como o ABSTRIPS, que além da descrição das ações, tomam como entrada a descrição hierárquica das ações. Pode-se, por exemplo, começar a planejar em alto nível e depois descer nos detalhes, se necessário (como ABSTRIPS, por exemplo). O objetivo é então descrito usando uma rede hierárquica de tarefas (HTN).

Planejamento Temporal
O planejamento de tempo permite expressar tempos de ação, condições no início, no final e durante a ação e efeitos no início e no final das ações. O PDDL 2.1 inclui planejamento de tempo. O método TLP-GP 1 constrói um gráfico e depois resolve as restrições temporais usando um solucionador SMT. Um backtracke em caso de inconsistência. Rintanen demonstrou que o planejamento de tempo simultâneo (várias instâncias da mesma ação paralela é possível) é EXPSPACE-complete. Por outro lado, se relaxarmos essas condições, poderemos nos reduzir ao planejamento convencional e, portanto, o planejamento temporal com essas restrições se tornará PSPACE completo.

Planejamento geral
O planejamento geral consiste em produzir um plano que funcione para vários ambientes iniciais.

Planejamento Multiagente
O agendamento multiagente estuda a conclusão de uma tarefa por vários agentes, por exemplo, vários robôs. A geração do plano e sua execução é então frequentemente distribuída / descentralizada. Um aspecto importante nos planos é a cooperação entre os agentes. Há também um algoritmo de escalonamento centralizado, que se baseia em uma generalização do STRIPS para o framework multi-agente, chamado MA-STRIPS. A renderização do algoritmo foi então distribuída, utilizando um solucionador CSP distribuído para gerenciar a coordenação entre os agentes. Os autores, Nissim, Brafman e Domshlak, verificaram experimentalmente que seu algoritmo é melhor que o agendamento centralizado quando os agentes têm pouca interação entre si.

Uma grande dificuldade no planejamento multiagente é a explosão combinatória de todas as ações, que é exponencial no número de agentes. Em 2011, Jonsson e Rovatsos oferecem uma solução para neutralizar este problema, reduzindo-o ao planejamento clássico de agente único. Há também um uso renovado de técnicas de paralelização para o planejamento de algoritmos para escalonamento.

Planejamento epistêmico
O problema do planejamento epistêmico é levar em conta o conhecimento dos agentes na descrição dos estados e ações. Tipicamente, o objetivo é uma fórmula da lógica modal epistêmica, tal como “o agente sabe que o agente b que o bloco C está no bloco A” e as ações são representadas com modelos de ações da dinâmica epistêmica lógica. O problema do planejamento é indecidível em toda a sua generalidade.

Objetivo :

Acima (A, B) Λ Acima (B, C)
Estado inicial :

[Acima (A, Tabela) Acima (B, Tabela) Acima (C, A) Trava (A) Trava (B) Trava (C) Divulgação (B) Divulgação (C)
Ações disponíveis:

Mover (b, x, y)
PRÉ-CONDIÇÕES: Acima (b, x) Λ Descoberto (b) Λ Descoberto (y) Λ Bloqueio (b) Λ Bloqueio (y) Λ (b ≠ x) Λ (b ≠ y) Λ (x ≠ y)
ADICIONAL: Acima (b, y) Λ Descoberto (x)
CANCELAMENTOS: Acima (b, x) Λ Descoberto (y)
Move_tool (b, x)
PRECONDIÇÕES: Acima (b, x) Λ Descoberto (b) Λ Descoberto (y) Λ Bloqueio (b) Λ (b ≠ x)
ADICIONAL: Acima (b, Tabela) Λ Descoberto (x)
CANCELAMENTOS: Acima (b, x)

Exemplo

Exemplo informal de planejamento.

Alvo
Tem algumas frutas e legumes na geladeira

Estado inicial
[geladeira vazia, em casa, com chinelos]

Ações disponíveis (lista não ordenada)
saia para casa
usar sapatos,
pegue as chaves do carro,
chegar à loja de carro,
chegar à loja a pé,
volto para casa,
fazer compras na geladeira,
entrar na loja,
pegue frutas,
tome vegetais,
pagar.

Solução possível (lista ordenada)
[1- usar sapatos, 2- pegar as chaves do carro, 3- sair da casa, 4- ir à loja de carro, 5- entrar na loja, 6- colher frutas, 7- colher legumes, 8- pagar, 9- voltar para casa, 10- compras na geladeira

Outra solução possível (lista ordenada):
[1- usar sapatos, 2- sair, 3- ir à loja a pé, 4- entrar na loja, 5- comer legumes, 6- colher frutas, 7- pagar, 8- ir para casa, 9- fazer compras na geladeira]

Conclusões
Do exemplo podemos ver como:

as soluções podem ser múltiplas,
podem estar presentes ações que devem ser realizadas, inevitavelmente, depois de outras (não consigo chegar à loja de carro se eu não levei as chaves antes),
pode haver ações que são reversíveis (tomar frutas e legumes),
não é necessário que o plano final contenha todas as ações no caso de múltiplas ações ou seqüências de ações intercambiáveis ​​(chegar à loja a pé ou de carro).

Share