Planejamento automatizado
Origem: Wikipédia, a enciclopédia livre.
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Índice |
[editar] Introdução
[editar] Primeiras intuições sobre planejamento
Planejamento é o lado racional da ação. Trata-se de um processo de deliberação abstrato e explícito 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. Planejamento automatizado (ou planejamento automático) é uma área da Inteligência Artificial (IA) que estuda este processo de deliberação por meio da computação.
Algumas de nossas ações necessitam de planejamento, mas muitas não. Em nossas atividades diárias, estamos sempre agindo, e antecipamos os resultados de nossas ações, mesmo que não estejamos completamente cientes dessa antecipação. Mas agimos com muito mais freqüência do que planejamos, explicitamente, nossas ações: poucas vezes temos consciência de estarmos executando um processo de deliberação antes da ação. Assim que tomamos conhecimento de uma ação, ou quando executamos comportamentos bem treinados para os quais possuímos planos previamente armazenados, ou quando o curso de uma ação pode ser livremente adaptado enquanto ela estiver sendo executada, então, geralmente agimos e adaptamos nossas ações sem planejá-las explicitamente.
Uma atividade premeditada exige deliberação quando se volta para novas situações ou tarefas e objetivos complexos ou quando conta com ações menos familiares. O planejamento também é necessário quando a adaptação das ações é coagida, por exemplo, por um ambiente crítico envolvendo alto risco ou alto custo, por uma atividade em parceria com mais alguém, ou por uma atividade que necessite estar sincronizada com um sistema dinâmico. Uma vez que o planejamento é um processo muito complicado, que consome muito tempo e dinheiro, recorremos ao planejamento apenas quando é realmente necessário ou quando a relação custo X benefício nos obriga a planejar. Além disso, geralmente, procuramos somente planos bons e viáveis ao invés de planos ótimos.
Uma das motivações para o planejamento automático:
projeto de ferramentas de processo de informação que forneça acesso as fontes de planejamentos produtivas e eficientes. Alguns profissionais enfrentam tarefas complexas e variadas que envolvem necessidade de segurança e/ou eficiência. Imagine, por exemplo, uma operação de resgate após um desastre natural como um terremoto ou uma enchente, esta operação pode 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 tributação de vários planos alternativos. Mas o tempo também é restrito e necessita de decisões imediatas que devem ser apoiadas por uma ferramenta de planejamento. A necessidade de tal ferramenta também é sentida por organizadores de tarefas mais simples ou rotineiras como a organização de um encontro social ou viagem profissional para um grupo de pessoas. No campo individual, uma fonte de planejamento que seja completamente integrada com organizadores eletrônicos ou serviços via web pode ser muito benéfica no manejamento das restrições, oferecendo planos alternativos ainda não considerados, e salientando ações críticas e o que poderá ser necessário para facilitá-las.
Outra motivação para o planejamento automático é mais teórica. O planejamento é um componente importante do comportamento racional. Se um dos objetivos da I.A. é controlar os aspectos computacionais da inteligência, então certamente, como lado racional da ação, planejamento é o elemento-chave em tal objetivo. O desafio aqui é estudar o planejamento não como um processo abstrato independente, mas como um componente completamente integrado do comportamento deliberativo. Uma combinação importante de motivações práticas e teóricas para o planejamento automático é o estudo e o projeto de máquinas inteligentes autônomas. Tal estudo diz respeito à prática, pois alguns de nossos artefatos complexos tais como satélites e naves espaciais exigem comportamentos autônomos e deliberativos. Estes artefatos não podem ser sempre teleoperados devido a limites operacionais ou por casa de uma interação necessária com humanos.
Uma combinação importante das motivações práticas e teóricas para planejamento automatizado é o estudo e projeto de máquinas autônomas inteligentes. Tal estudo é de interesse prático porque alguns de nossos artefatos complexos como satélites e espaçonaves requerem autonomia e comportamento deliberativo. Estes artefatos nem sempre podem ser tele-operados devido a restrições operacionais ou por causa de uma trabalhosa interação com humanos não specialistas que é mais natural no nível de tarefas que no baixo nível de sinais de controle. O estudo de máquinas autônomas inteligentes é também de interesse teórico pois planejamento como um componente totalmente integrado do comportamento deliberativo requer implantação em uma máquina que possa sensoriar e atuar assim como raciocina sobre suas ações.
[editar] 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, planejamento de percepção e obtenção de informação, planejamento de navegação, planejamento de manipulação, planejamento de comunicação e várias outras formas de planejamento social e econômico.
Planejamento de caminho e movimento está relacionado com a síntese de um caminho geométrico de uma posição inicial no espaço a um objetivo e de uma trajetória de controle ao longo deste caminho que especifica as variáveis de estados no espaço de configuração de um sistema móvel como um caminhão, um braço mecânico, um robô ou um personagem virtual. O planejamento de movimento leva em consideração o modelo do ambiente e as limitações da cinemática e da dinamicidade de um sistema móvel.
O planejamento de movimento pode ser visto como um caso particular dentro de um problema geral das ações de planejamento de controle para sistemas dinâmicos. Enquanto planejamentos de movimento buscam uma trajetória no espaço da configuração de um sistema móvel, o problema geral do planejamento está relacionado com espaços de estados mais abstratos. Considere, por exemplo, o problema do controle de um aparelho de cerâmica ou um forno de fundição de seu estado atual a um estado desejado. Quando estes dois estados estão suficientemente perto, uma ação de controle corretiva poderá ser computada a partir de suas diferenças. Se o desejado estiver muito distante do atual (por exemplo, por ter levado o forno a um estado de interrupção), então, uma seqüência de ações de controle que encontram algumas limitações e critérios deve ser planejada.
O planejamento de percepção está relacionado com planos que envolvem ações sensíveis no acúmulo de informação. Ele se manifesta em tarefas como modelagem de ambientes ou objetos, identificação de objetos, localização através de um sistema móvel, ou mais comumente, identificação do estado atual no ambiente. Um exemplo destas tarefas é o projeto de um modelo virtual preciso de uma cena urbana a partir de um conjunto de imagens. O planejamento de percepção direciona questões como, quais informações são necessárias e quando serão necessárias, onde procurá-las, que sensores são mais adequados para esta tarefa específica, e como usá-los. Ele requer modelos de sensores disponíveis e suas habilidades e limites. Conta com decisão teórica para problemas relacionados a como e quando a informação é necessária, com programação matemática e limitações de satisfação para a seleção do ponto de vista e as modalidades do sensor.
O planejamento de navegação combina os dois problemas anteriores de planejamento de movimento e percepção a fim de alcançar um objetivo ou explorar uma área. O propósito do planejamento de navegação é sintetizar um plano de ação que combina localizações primitivas e movimentos primitivos baseados em sensores, por exemplo, seguir visualmente uma estrada até alcançar algum marco divisório, afastando-se de algo que está à frente enquanto desvia de obstáculos, e assim por diante.
Planejamento de manipulação está relacionado com o manuseio de objetos, por exemplo, construção. As ações incluem primitivas senso-motoras que envolve forças, toque, visão, amplitude, e outras informações sensoriais. Um plano poderá envolver/apanhar um objeto em seus lados marcados, devolvê-lo caso seja necessário, inseri-lo, e empurrá-lo levemente até que se prenda mecanicamente na posição.
O planejamento de comunicação manifesta-se no diálogo e em problemas de cooperação entre vários agentes, humanos ou artificiais. Levanta questões como, quando e como solicitar informações necessárias, e qual feedback deverá ser fornecido.
Há uma ampla variedade de outros tipos de problemas de planejamento, principalmente na esfera social e econômica. Por exemplo, o planejamento urbano envolve a distribuição e organização de uma infra-estrutura urbana (como, transporte público, escolas, hospitais) a fim de encontrar as necessidades de uma comunidade, o planejamento familiar lida com a demografia, e o planejamento financeiro enfoca a otimização financeira estreita.
[editar] Planejamento independente do domínio
Uma abordagem natural para estas diversas formas de planejamento é criar técnicas específicas para cada problema. Sendo desenvolvido modelos preditivos para o tipo de ação que será planejada e para os estados específicos do sistema. 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 automático 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 automático 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 automático é 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 independente do domínio conta com modelos de ações gerais e abstratos. Estes modelos variam de alguns muitos simples, que permitem apenas formas limitadas de raciocínio, a modelos com habilidades de prognóstico mais ricas. Há, em especial, as seguintes formas de modelos e habilidades de planejamento.
- Planejamento de projeto, no qual modelos de ações são reduzidos principalmente a limitações temporais e de precedência, por exemplo, as mais antigas e as mais recentes, inícios de uma ação ou a latência em relação à outra ação. O planejamento de projeto é usado para a edição e verificação de planos interativos. Um plano possível é dado pelo usuário como incentivo a uma ferramenta de planejamento de projeto que verifica a praticabilidade das limitações e computa vários atributos úteis do plano dado como os caminhos críticos. Aqui, os modelos de ação no plano (isto é, seus efeitos e interações) permanecem, normalmente, na mente do usuário.
- Escalonamento de recursos, nos quais os modelos de ação incluem os tipos e as limitações nos recursos que serão usados em cada ação. Uma ferramenta de escalonamento toma como impulso as ações que serão realizadas juntamente com as limitações de recurso e os critérios de otimização. A ferramenta devolve uma organização temporal e a atribuição de recurso para as ações dadas a fim de encontrar todas as limitações e otimizar os critérios.
- Síntese de plano, na qual os modelos de ação melhoram os modelos anteriores com as condições necessárias para a aplicabilidade de uma ação e os efeitos das ações no estado do mundo. Uma ferramenta de síntese de plano toma como impulso os modelos de todas as ações conhecidas, uma descrição do estado do mundo, e um objetivo. A ferramenta devolve uma coleção organizada de ações das quais o efeito global, se for completo e executada conforme o modelo, atinge o objetivo.
O planejamento automático está relacionado com as formas gerais de síntese de plano. Embora teoricamente, esteja ainda em seus estágios iniciais, o planejamento automático já está avançado o suficiente para ser útil na prática.
O planejamento automático 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.
[editar] Modelo conceitual de planejamento
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.
Uma vez que o planejamento está relacionado na escolha e organização das ações para mudar o estado de um sistema, um modelo conceitual para planejamento necessita de um modelo geral para um sistema dinâmico.
A abordagem de planejamento descrita conta com o modelo de sistema de transição de estado (também chamado sistema evento discretos).
Formalmente, um sistema de transição de estado é um 4-tupla 
, onde:
é um conjunto de estados finito ou recursivamente numerável;
é um conjunto de ações finito e recursivamente numerável;
é um conjunto de eventos finito e recursivamente numerável; e
é uma função de transição de estado.
Um sistema de transição de estado pode ser representado por um grafo direto cujos nós são os estados em S. Se 
, onde u é um par (a,e), 
e 
, então o gráfo contém um arco de s a s' que é classificado com u. Cada um desses arcos é chamado transição de estado. É conveniente introduzir um evento neutro ε para dar a razão de transições que são causadas apenas por ações e, simetricamente, uma ação neutra não-operacional (no-op) por transições denotativas causadas exclusivamente por um evento. Escrevemos γ(s,a,ε) como γ(s,a) e γ(s,no-op,e) como γ(s,e).
[editar] Modelo restrito
Este modelo conceitual não pretende ser diretamente operacional. Pelo contrário, será usado como uma referência para as representações. Vamos considerá-lo como um ponto inicial para avaliação de propriedade restritiva, particularmente as seguintes.
- Propriedade A0 (Σ finito). O sistema Σ tem um conjunto finito de estados.
- Propriedade A1 (Σ completamente observável). 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 (Σ determinístico). O sistema Σ é determinístico, isto é, para cada estado s e para cada evento ou ação
. Se uma ação é aplicável a um estado, sua aplicação leva um sistema determinístico a um outro estado único; igual à ocorrência de um possível evento.
- Propriedade A3(Σ estático). O sistema Σ está estático, isto é, o conjunto de eventos E é vazio. Σ não tem dinâmica interna; fica no mesmo estado até que o controlador aplique alguma ação.
- Propriedade A4 (objetivos restritos). O planejador manipula apenas objetivos restritos que são especificados como um estado objetivo explícito sg ou conjunto de estados objetivo Sg; o objetivo é qualquer seqüência de transições de estado que termina em um dos estados-objetivo. Objetivos ampliados como estados que devem ser evitados e limitações nas trajetórias dos estados ou funções de utilidade não são manipuladas sob esta propriedade restrita.
- Propriedade A5 (planejamento seqüencial). Um plano solução para um problema de planejamento é uma seqüência de ações finita linearmente ordenada.
- Propriedade A6 (Tempo implícito). 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 (planejamento offline). O planejador não está relacionado com qualquer mudança que possa ocorrer em Σ enquanto estiver planejando; planeja-se para o estado inicial e o objetivo independente da dinâmica atual, se houver.
