Planejamento automatizado

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


Planejamento Automatizado é uma área da Inteligência Artificial (IA) que estuda este processo de deliberação por meio da computação.[1] O planejamento é um processo de deliberação que escolhe e organiza ações, antecipando os resultados esperados. Esta deliberação busca alcançar, da melhor forma possível, alguns objetivos pré-definidos.


Motivações[editar | editar código-fonte]

Uma das motivações para o planejamento automatizado é estritamente prática. Imaginando-se, por exemplo, uma operação de resgate após um desastre natural como um terremoto ou uma enchente, esta operação poderá envolver um grande número de participantes e exigir a distribuição de uma infra-estrutura de comunicação e transporte. Ela contará com um planejamento cuidadoso e a avaliação de custos dos planos alternativos. O tempo também é restrito e necessitar-se-á de decisões imediatas que deverão ser apoiadas por uma ferramenta de planejamento. A necessidade do uso de tal ferramenta também é sentida por organizadores de tarefas mais simples ou rotineiras, como a coordenação de um encontro social ou de uma viagem profissional para um grupo de pessoas.

Uma combinação importante de motivações para o planejamento automatizado é o estudo e projeto de máquinas inteligentes autônomas. Tal estudo diz respeito não só à teoria como a prática também, pois alguns de nossos artefatos complexos, como satélites e naves espaciais exigem comportamentos autônomos e deliberativos. Estes artefatos não podem ser sempre tele-operados devido a limites operacionais ou por causa de uma interação necessária com humanos não-especialistas, que agem mais naturalmente no nível da tarefa do que no baixo nível.[2]

Formas de planejamento[editar | editar código-fonte]

Uma vez que existem vários tipos de ações, há também várias formas de planejamento, por exemplo:

Mundo dos blocos[editar | editar código-fonte]

O Mundo dos blocos é um problema clássico para o fácil entendimento inicial sobre Planejamento Automatizado. O problema consiste, basicamente, de alguns blocos sobre uma mesa e um braço mecânico para o movimento dos blocos. O objetivo é determinar um plano a partir de um estado inicial e um estado final.[6]

Planejamento independente do domínio[editar | editar código-fonte]

Uma abordagem natural para estas diversas formas de planejamento é criar técnicas específicas para cada problema. Ferramentas computacionais para executar estes modelos, a fim de prognosticar e avaliar os efeitos de ações e planos alternativos em várias situações, exploram as especificidades do domínio. Por exemplo, geometria, cinemática e dinâmica são as ferramentas necessárias para o planejamento de movimento e de manipulação. Programação matemática e técnicas de otimização são as ferramentas amplamente usadas em várias formas de planejamento econômico. Estes domínios próximos a formas específicas de planejamento são certamente bem justificados. São muito bem sucedidos na maioria das áreas de aplicação mencionadas. Entretanto, são frustrantes por várias razões.

  • Algumas semelhanças em todas estas formas de planejamento não são levantadas em abordagens especificas do domínio. O estudo destas semelhanças é necessário para a compreensão do processo de planejamento; podendo ajudar a melhorar as abordagens especificas do domínio.
  • É mais caro levantar cada problema novamente ao invés de adaptar algumas ferramentas gerais.
  • Abordagens específicas do domínio não são satisfatórias para o estudo e para o projeto de uma máquina inteligente autônoma. Suas capacidades deliberativas serão limitadas a áreas para as quais tiver planejadores específicos do domínio, a menos que possam desenvolver sozinhas novas abordagens a partir de suas interações com o ambiente.

Por todas estas razões, o planejamento automatizado se interessa por abordagens gerais independente do domínio para planejamento. Para resolver um problema específico, um planejador independente do domínio toma como impulso as especificações do problema e os conhecimentos sobre o domínio. O planejamento automatizado não pretende ser oposto as técnicas de planejamento específico de domínio, assim como o raciocínio automático não pretende substituir todo processador aritmético e de cálculo de ponto-flutuante e outras técnicas de raciocínio especializadas num computador. Devido ao planejamento ser o lado racional da ação, o objetivo do planejamento automatizado é desenvolver abordagens gerais para esta forma específica de raciocínio que possam edificar e ser bem integradas com ferramentas de planejamento de domínio.

O planejamento automatizado está relacionado com as formas gerais de síntese de plano. Embora teoricamente, esteja ainda em seus estágios iniciais, ele já está avançado o suficiente para ser útil na prática.

O planejamento automatizado já possui vários casos de sucesso; um deles é o controle da espaço-nave Deep space 1. Esta nave foi lançada do Cabo Canaveral em 24 de outubro de 1998, e foi retirado de circulação em 18 de dezembro de 2001, após completar sua missão com êxito, encontrando o cometa Borrelly e trazendo as melhores imagens e outros dados científicos. A missão Deep space 1 testou com êxito inúmeras tecnologias avançadas. Entre elas estava o software do sistema de Agente Remoto Autônomo. O agente remoto autônomo, era baseado nas técnicas de planejamento automático, e operou com sucesso a Deep Space 1 entre 17 de maio e 21 de maio de 1999.[7]

Modelo restrito[editar | editar código-fonte]

Um modelo conceitual é um dispositivo teórico simples para descrever os principais elementos de um problema. Pode divergir significativamente dos conceitos computacionais e das abordagens aritméticas para a solução do problema. Entretanto, pode ser muito útil para explicar conceitos básicos, esclarecer suposições restritivas, analisar exigências acerca de representações e trocas, e para provar propriedades semânticas.

Para o planejamento automatizado o modelo conceitual não pretende ser diretamente operacional. Pelo contrário, será usado como uma referência para as representações. Considerando como um ponto inicial para avaliação de propriedade restritiva.[1]

  • Propriedade A0 . O sistema tem um conjunto finito de estados.
  • Propriedade A1 . O sistema é completamente observável, isto é, sabe-se completamente sobre o estado de \Sigma. Neste caso, a função observação \eta é a função identidade.
  • Propriedade A2 . O sistema é determinístico, isto é, se uma ação (ou evento) é aplicável a um estado, sua aplicação leva um sistema determinístico a um outro estado único;
  • Propriedade A3 . O sistema é estático, isto é, o conjunto de eventos possíveis é vazio. O sistema não tem dinâmica interna; fica no mesmo estado até que o controlador aplique alguma ação.
  • Propriedade A4 . O planejador manipula apenas objetivos restritos que são especificados como um estado objetivo explícito ou conjunto de estados objetivo; o objetivo é qualquer seqüência de ações que termina em um dos estados-objetivo.
  • Propriedade A5 . Um plano solução para um problema de planejamento é uma seqüência de ações finita linearmente ordenada.
  • Propriedade A6 . Ações e eventos não têm duração; são transições de estado instantâneas. Esta suposição está embutida num sistema de transição de estado, um modelo que não representa tempo explicitamente.
  • Propriedade A7 . O planejador não está relacionado com qualquer mudança que possa ocorrer no sistema enquanto estiver planejando; planeja-se para o estado inicial e o objetivo independente da dinâmica atual, se houver.

Planejamento Clássico[editar | editar código-fonte]

O planejamento clássico se refere genericamente a um planejamento para sistemas restritos de transição de estado.[1]

Algoritmo STRIPS[editar | editar código-fonte]

A representação de problemas de planejamento − estados, ações e objetivos − deve ser feita por meio de uma linguagem que seja suficientemente expressiva para descrever uma ampla variedade de problemas, mas restritiva o bastante para permitir que algoritmos eficientes operem sobre ela. A maioria das abordagens de planejamento adotam uma representa são baseadas em lógica para descrever estados, ações e para definir e computar facilmente o próximo estado. A linguagem básica para representação adotada por planejadores clássicos é conhecida como STRIPS (Stanford Research Institute Planning System) [8]

Replanejamento[editar | editar código-fonte]

Na teoria, modificar um plano existente não é mais eficaz do que um replanejamento completo (a partir do estado atual) no pior caso. Porém, na prática, o reparo do plano pode ser mais eficaz, uma vez que uma grande parte do plano geralmente ainda é válida. Além disso, em muitos domínios pode ser mais caro mudar todo o plano por causa de compromissos com outros agentes baseados no plano original.[9]

Um agente de replanejamento observa o ambiente para ver se tudo está funcionando de acordo com o plano. Este tipo de planejamento se faz em ambientes realistas, onde sempre surgirá alguma circunstância inesperada para a qual as descrições de ações do agente serão incorretas — indeterminismo ilimitado. Existem dois tipos de monitoramento de execução: uma forma simples, embora fraca, chamada monitoramento de ação, por meio da qual o agente verifica o ambiente para saber se a próxima ação funcionará, e uma forma mais complexa, ainda que mais efetiva, chamada monitoramento de plano, em que o agente verifica todo o plano restante.[10]

Um agente de replanejamento sabe o que fazer quando acontece algo inesperado: chama novamente um planejador para apresentar um novo plano que irá atingir o objetivo a partir de um novo estado inicial. Para evitar gastar tempo, em geral, o planejador tenta reparar o plano previamente gerado — a fim de encontrar um caminho do estado inesperado atual de volta para a seqüência normal do plano.[11]

Juntos, o monitoramento de execução e o replanejamento formam uma estratégia geral que pode ser aplicada a ambientes completamente observáveis e a ambientes parcialmente observáveis, além de uma variedade de representações de tipos de planejamento.

Referências

  1. a b c Ghallab, M., Nau, D. S., and Traverso, P. (2004). Automated Planning: Theory and Practice. ISBN 1-55860-856-7
  2. Smith, B., Millar, W., Wen, Y. J. D., Nayak, P., and Clark, M. (1999). Validation and verification of the remote agent for space-craft autonomy. In IEEE Aerospace Conference.
  3. Koenig, S., Goodwin, R., and Simmons, R. G. (1995). Robot navigation with markov models: A framework for path planning and learning with limited computational resources. In Reasoning with Uncertainty in Robotics, pages 322–337.
  4. Matthew T. Mason (1993). Kicking the Sensing Habit. AI Magazine.
  5. Dana S. Nau and Satyandra K. Gupta and William C. Regli (1995). AI Planning Versus Manufacturing-Operation Planning: A Case Study - IJCAI.
  6. Naresh Gupta and Dana S. (1992). Artificial Intelligence: On The Complexity of Blocks-Word Planning
  7. Rabideau, G., Knight, R., Chien, S., Fukunaga, A., & Govindjee, A. - Iterative Repair Planning for Spacecraft Operations Using the ASPEN System - Artificial Intelligence, Robotics and Automation in Space, Proceedings of the Fifth International Symposium, ISAIRAS '99, held 1-3 June, 1999 in ESTEC, Noordwijk, the Netherlands. Edited by M. Perry. ESA SP-440. Paris: European Space Agency, 1999., p.99
  8. Fikes, R. and Nilsson, N. J. (1971). Strips: A new approach to the application of theorem proving to problem solving. In IJCAI, pages 608–620.
  9. David Robert Camargo de Campos (2008), Reparo de plano por refinamento reverso.
  10. Russell, S. J. and Norvig, P. (2002). Artificial Intelligence: A Modern Approach. Prentice Hall. ISBN 0-13-103805-2
  11. Wilkins, D. E. (1988). Pratical planning: Extending the ai planning paradigm.

Ver também[editar | editar código-fonte]

Wiki letter w.svg Este artigo é um esboço. Você pode ajudar a Wikipédia expandindo-o. Editor: considere marcar com um esboço mais específico.