Mostrar código-fonte de Planejamento automatizado

<!-- *****************************************************************************************
Não retirem este comentário, porque ajuda no controlo e manutenção das [[Special:Shortpages]].
****************************************************************************************** -->

'''Planeamento Automatizado''' é uma área da [[Inteligência Artificial]] (IA) que estuda este processo de deliberação por meio da [[computação]].<ref name="Book_Automated_Planning">Ghallab, M., Nau, D. S., and Traverso, P. (2004). Automated Planning: Theory and Practice. ISBN 1-55860-856-7</ref> O [[planejamento|planeamento]] é 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.

<!--
Algumas das ações humanas necessitam de planejamento. Em suas atividades diárias o ser [[humano]] está
sempre antecipando os resultados de suas ações, mesmo que não esteja completamente ciente dessa antecipação. Entretanto freqüentemente ele age sem planejar tais ações: poucas vezes tem consciência de estar executando um
processo de deliberação antes da ação. Isso pode acontecer com sucesso em duas situações:
# Quando executa comportamentos bem treinados para os quais possui planos previamente armazenados, ou
# Quando o curso de uma ação pode ser livremente adaptada enquanto ela estiver sendo executada.

Deste modo geralmente o homem age e adapta suas ações sem planejá-las com muita antecedência.

Quando novas situações ou tarefas são diagnosticadas, uma atividade premeditada é necessaria. Deste modo, o planejamento também é necessário nos casos em que a adaptação das ações é coagida, por exemplo, por um [[ambiente crítico]] envolvendo alto risco ou alto custo, ou por uma atividade que necessite estar sincronizada com um sistema dinâmico. Entretanto, como o planejamento é um processo complexo, que consome muito tempo e recursos (como por exemplo dinheiro), recorre-se a ele apenas quando realmente for necessário ou quando a relação entre custo e benefício obriga a planejar.
-->

== Motivações ==
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 autônomas|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élite artificial|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.<ref>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.</ref>

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

* [[Planejamento de caminho e movimento]],<ref>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.</ref>
* [[Planejamento de percepção]],
* [[Planejamento de navegação]],<ref>Matthew T. Mason (1993). Kicking the Sensing Habit. AI Magazine.</ref>
* [[Planejamento de manipulação]],<ref>Dana S. Nau and Satyandra K. Gupta and William C. Regli (1995). AI Planning Versus Manufacturing-Operation Planning: A Case Study - IJCAI.</ref>
* [[Planejamento de comunicação]],
* [[planejamento econômico]],
* [[Planejamento urbano]],
* [[Planejamento familiar]],
* Planejamento estratégico,
* Planejamento integrado,
* entre outros.

== Mundo dos blocos ==
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.<ref>Naresh Gupta and Dana S. (1992). Artificial Intelligence: [http://www.cs.pdx.edu/~bart/archive/cs510sps/hw/blocks-long.ps.gz On The Complexity of Blocks-Word Planning]</ref>

== Planejamento independente do domínio ==
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 [[Estação da Força Aérea de Cabo Canaveral|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.<ref name="ASPEN">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</ref>

== Modelo restrito ==
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.<ref name="Book_Automated_Planning" />

* '''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 <math>\Sigma</math>. Neste caso, a função observação <math>\eta</math> é 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 ==
O ''planejamento clássico'' se refere genericamente a um planejamento para sistemas restritos de transição de estado.<ref name="Book_Automated_Planning" />

=== Algoritmo STRIPS ===
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) <ref name="STRIPS">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.</ref>

== Replanejamento ==
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.<ref name="dissertação_reparo_plano_refinamento_reverso">David Robert Camargo de Campos (2008), [http://www.teses.usp.br/teses/disponiveis/45/45134/tde-06082008-164027/ Reparo de plano por refinamento reverso].</ref>

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.<ref name="AIMA">Russell, S. J. and Norvig, P. (2002). Artificial Intelligence: A Modern Approach. Prentice Hall. ISBN 0-13-103805-2</ref>

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.<ref>Wilkins, D. E. (1988). Pratical planning: Extending the ai planning paradigm.</ref>

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}}

== Ver também ==
* [[Automação]]
* [[Engenharia de base]]
* [[Inteligência Artificial]] ([[IA]])
* [[Planejamento]]
* [[Problema]]

{{esboço}}

{{DEFAULTSORT:Planejamento Automatizado}}
[[Categoria:Planejamento]]