Planejamento automatizado
Planeamento Automatizado é uma área da Inteligência Artificial (IA) que estuda este processo de deliberação por meio da computação.[1] O 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.
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:
- Planejamento de caminho e movimento,[3]
- Planejamento de percepção,
- Planejamento de navegação,[4]
- Planejamento de manipulação,[5]
- Planejamento de comunicação,
- planejamento econômico,
- Planejamento urbano,
- Planejamento familiar,
- Planejamento estratégico,
- Planejamento integrado,
- entre outros.
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 . Neste caso, a função observação é 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
- ↑ a b c Ghallab, M., Nau, D. S., and Traverso, P. (2004). Automated Planning: Theory and Practice. ISBN 1-55860-856-7
- ↑ 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.
- ↑ 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.
- ↑ Matthew T. Mason (1993). Kicking the Sensing Habit. AI Magazine.
- ↑ Dana S. Nau and Satyandra K. Gupta and William C. Regli (1995). AI Planning Versus Manufacturing-Operation Planning: A Case Study - IJCAI.
- ↑ Naresh Gupta and Dana S. (1992). Artificial Intelligence: On The Complexity of Blocks-Word Planning
- ↑ 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
- ↑ 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.
- ↑ David Robert Camargo de Campos (2008), Reparo de plano por refinamento reverso.
- ↑ Russell, S. J. and Norvig, P. (2002). Artificial Intelligence: A Modern Approach. Prentice Hall. ISBN 0-13-103805-2
- ↑ Wilkins, D. E. (1988). Pratical planning: Extending the ai planning paradigm.
