Home

Formato PDF - mtc-m17:80

1. ou seja se o Planejador teve ou n o sucesso ao gerar um plano que atenda solicita o O plano gerado deve ser enviado em resposta a um telecomando espec fico para an lise por parte dos operadores da miss o em solo Caber aos operadores gerar manualmente planos de opera o para atender a solicita o do experimento Os planos dos operadores dever o ent o ser comparados com aqueles enviados pelo RASSO Se for constatado que o RASSO gerou um plano que atenderia solicita o do experimento mantendo ainda a opera o normal do sat lite isso ser computado como um sucesso do servi o Caso contr rio o algoritmo de planejamento e o modelo do sistema dever o ser revistos e uma nova vers o enviada ao sat lite Havendo um n mero considerado suficiente de sucessos consecutivos o servi o poder ser colocado em modo atuando passando a estar completamente operacional O pr ximo Cap tulo detalha a implementa o do prot tipo do servi o de replanejamento embarcado aqui proposto 108 CAP TULO 6 IMPLEMENTA O DE UM PROT TIPO DO SERVI O DE REPLANEJAMENTO EMBARCADO O Cap tulo anterior apresentou a proposta para um servi o de replanejamento embarcado chamado de RASSO e as abordagens escolhidas para a representa o do conhecimento para o processo de planejamento e para uma implementa o gradual Este Cap tulo traz a implementa o de um prot tipo do servi o RASSO Primeiramente
2. 106 Assim foi escolhida a representa o do problema de realoca o de recursos como um CSP a ser resolvido por um algoritmo de busca local guiado por restri es de escalonamento item 3 6 3 deste trabalho e auxiliado por heur sticas espec ficas para o dominio de sat lites O plano corrente do sat lite enviado rotineiramente a partir de solo deve ser a entrada para o processo de replanejamento e a solicita o por mais recursos respons vel por inserir no plano as perturba es que levar o viola o das restri es T cnicas para a fuga de m nimos locais e plat s no espa o de estados tamb m devem ser implementadas 5 4 Ganhando a Confian a do Pessoal de Miss o fato que h uma grande resist ncia justificada quanto ao aumento da autonomia de sat lites O custo e o volume de trabalho em uma miss o espacial em geral considerado muito grande para confiar ao sat lite a tomada de mais decis es do que as de rotina como a corre o de atitude e rbita Esta resist ncia tende a ser ainda maior quando o aumento de autonomia propiciado por uma t cnica proveniente da rea de Intelig ncia Artificial Para lidar com isso e tornar poss vel uma implementa o gradual do servi o em uma miss o real ganhando assim pouco a pouco a confian a da equipe de opera es o RASSO deve trazer duas caracter sticas 1 As modifica es no plano efetuadas pelo RASSO devem ter escopo reduzido 2 D
3. cc ccccsssccssssesecsesccessesseceessseesesseneees 88 4 3 1 As Experi ncias Realizadas com Planejamento Embarcado 90 4 3 2 O Futuro do Planejamento Embarcado ccccnococcnonoocnnononnnnnnononnnnonnnnnnncnoncnnonnnnoss 94 CAP TULO 5 PROPOSTA PARA UM SERVI O DE REPLANEJAMENTO EMBARCADO pinta iii rr iii 97 5 1 Contexto Definido para o Prot tipo do Servi o de Replanejamento 97 5 1 1 O Projeto do Computador Avan ado COMAY cccccssesseccsesstseesesaeeeesseeeenes 98 5 1 2 O Sat lite Cient fico EQUARS como Aplica o Alvo ccoooooccnnooocccononncncnonanononnns 99 5 2 Caracter sticas do Problema Escolhido oooococononoccnonononnnononnnncnananononanannnnono 101 5 3 A Arquitetura do Servi o de Replanejamento ooooocccnoooncnonnnonnnononnnncnconcnnnnnnnos 102 5 3 1 A Abordagem para a Representa o do Conhecimento cooooooccnnooncncnoonnnnnnonnss 104 5 3 2 A Abordagem para o Processo de Replanejamento ooooonncccncnonocncnnonnnnononononos 106 5 4 Ganhando a Confian a do Pessoal de MISSa0 scccccesesssscceceeeseenssnseeeeeecees 107 CAP TULO 6 IMPLEMENTA O DE UM PROT TIPO DO SERVI O DE REPLANEJAMENTO EMBARCADO seem 109 6 1 Estrutura para a Representa o do Conhecimento no RASSO 109 6 2 A Linguagem de Representa o do Conhecimento 110 6 2 1 A Descri o Est tica do Modelo coin ic cevasedeusesasens 112
4. high level Spacecraft Command Language spacecraft state commands low level e a e e te o e a N Conventional Flight Software sensor telemetry i control signals very H low level Spacecraft Hardware FIGURA 4 3 A Arquitetura do ASE Fonte adaptado de Chien et al 2003 p 2 Para possibilitar a resposta aut noma o ASE emprega algoritmos de an lise de dados de imagens obtidas pelas c meras do sat lite que identificam a ocorr ncia dos eventos Quando da detec o de um evento uma solicita o de observa o enviada ao CASPER para que novas imagens sejam feitas da mesma rea nas pr ximas passagens sobre ela O CASPER ent o consolida os dados de previs o de passagens com os dados do estado do sat lite e do plano de opera es atual para efetuar o replanejamento Assim como o RAX PS o CASPER tamb m faz uso de um modelo do sat lite para inferir seu comportamento durante a gera o do plano Uma vez que o novo plano tenha sido gerado ele convertido em comandos para o sat lite e colocado em execu o Tudo isso realizado sem a interven o da equipe de opera es em solo o CASPER capaz de gerar uma resposta em algumas dezenas de minutos tempo suficiente para colocar o plano em execu o na pr xima passagem sobre o alvo Os primeiros testes em v o foram realizados em outubro de 2003 Testes incrementais foram realizados desde ent o at que o sistema foi
5. ionex nao pode ser desligado apenas seu modo de operacao alterado condition get current state by id Experiment exp name jonex force state if needed by id Experiment exp on true efeitos descritos a partir daqui set current state by id Experiment exp on false consume resource by id Experiment exp Power 0 consume resource by id Experiment exp Mass Memory 0 when running printf Turn Off experiment Si n exp action success Aplicavel apenas ao IONEX RASSO Action Change Mode action parameters parameter exp parameter new mode when planning condition get current state by id Experiment exp name ionex condition get current state IONEX on true condition get current state IONEX mode new mode force state if needed IONEX on true efeitos descritos a partir daqui set current state IONEX mode new mode if new mode full consume resource by id Experiment exp Power 5 4 consume resource by id Experiment exp Mass Memory 189 16 per min else new_mode partial consume resource by id Experiment exp Power 3 consume_resource by id Experiment exp Mass Memory 95 29 per min when running printf Changing IONEX to mode i n new mode 161 action_success Aplicavel apenas ao CERTO e MLTM Recebe new sr como valores discretos 1 2 ou 3 RASSO Acti
6. rg o que mant m relacionamento constante com a ESA Este grupo formalizou o problema e prop s o desenvolvimento de uma ferramenta de planejamento com IA para a gera o automatizada de planos aptos a trat lo Uma primeira vers o desta ferramenta chamada Mars EXpress Architecture MEXAR Cesta et al 2004 come ou a ser implantada apenas tr s meses ap s ser proposta O MEXAR foi testado no ambiente operacional da miss o e passou a ser utilizado rotineiramente a partir de fevereiro de 2005 em uma nova vers o MEXAR2 O MEXAR2 assim como o MAPGEN parte da id ia de planejamento cooperativo O usu rio e o sistema planejador interagem at que um plano satisfat rio seja alcan ado A modelagem tem como elementos apenas os recursos e as atividades e o problema assim como em outros planejadores tratado como um CSP utilizado um conjunto de algoritmos executados em s rie para se atingir a solu o O primeiro algoritmo aplicado de busca gulosa guiada por heur sticas que apenas atribui valores iniciais s vari veis do problema sem tratar as viola es de restri es que estejam ocorrendo A seguir algoritmos de busca rand mica e de busca tabu s o utilizados de forma combinada para tratar as viola es ao t rmino da primeira execu o destes 86 algoritmos que uma primeira vers o do plano apresentada ao usu rio A cada conjunto de altera es sugeridas pelo usu rio os algoritmos de busca r
7. 37 Como o aumento das quotas para um experimento novamente implica na redu o das quotas dos demais estas altera es devem ser previstas com anteced ncia suficiente para permitir a an lise de seu impacto sobre o funcionamento do sat lite e em alguns casos uma nova rodada de negocia es entre os cientistas A Figura 2 2 ilustra o processo normal de planejamento da opera o de sat lites cient ficos no INPE Flight Domains Pass Plan Orbit Events System Activities Schedule W W 1 FEA SCC Working Plan GS Working Plan FIGURA 2 2 O Processo Normal de Planejamento de Sat lites Cient ficos do INPE Fonte Carvalho 2001 O processo normal de planejamento se inicia com o levantamento por parte do centro de controle de sat lites SCC na Figura 2 2 e do controle da miss o MC de informa es sobre os dom nios de v o plano de passagens eventos orbitais e o escalonamento de atividades do sistema S o ent o obtidas as solicita es dos usu rios da miss o que no caso dos sat lites cientificos s o os cientistas respons veis pelos experimentos e dos respons veis pela opera o do sat lite gerando dois planos um para a carga til os experimentos e 38 outro para a plataforma Estes dois planos s o ent o unidos em um plano operacional que enviado ao sat lite e colocado em execu o Nota se na Figura 2 2 que o processo normal de planejamento iniciado numa quarta
8. HANSEN E ORTIVIZ A WILKLOW C WICHMAN S Onboard autonomy on the Three Corner Sat mission In INTERNATIONAL SYMPOSIUM ON ARTIFICIAL INTELLIGENCE ROBOTICS AND AUTOMATION IN SPACE I SAIRAS 6 2001 Montreal Canada Proceedings Montreal CSA 2001 150 CHIEN S SHERWOOD R TRAN D CASTANO R CICHY B DAVIES A RABIDEAU G TANG N BURL M MANDL D FRYE S HENGEMIHLE J D AGOSTINO J BOTE R TROUT B SHULMAN S UNGAR S VAN GAASBECK J BOYER D GRIFFIN M BURKE H GREELEY R DOGGETT T WILLIAMS K BAKER V DOHM J Autonomous science on the EO 1 mission In INTERNATIONAL SYMPOSIUM ON ARTIFICIAL INTELLIGENCE ROBOTICS AND AUTOMATION IN SPACE I SAIRAS 7 2003 Nara Japan Proceedings Nara JAXA 2003 CHIEN S SHERWOOD R TRAN D CICHY B RABIDEAU G CASTANO R DAVIES A LEE R MANDL D FRYE S TROUT B D AGOSTINO J SHULMAN S BOYER D HAYDEN S SWEET A CHRISTA S Lessons learned from Autonomous Sciencecraft Experiment In INTERNATIONAL JOINT CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS AAMAS 05 4 2005 Utrecht Netherlands Proceedings Utrecht ACM Press 2005 CONSULTATIVE COMMITTEE FOR SPACE DATA SYSTEMS CCSDS Telemetry summary of concept and rationale Washington D C USA December 1987 Report Concerning Space Data Systems Standards CCSDS 100 0 G 1 Green Book Issue 1 CONSULTATIVE COMMITTEE FOR
9. es action para a es pontuais e durative action para a es com dura o associada Cada a o possui descritos seus par metros pr condi es para execu o e efeitos sobre o dominio no arquivo de especifica es do problema que o dom nio instanciado atrav s da cria o de objetos a partir dos tipos definidos e da defini o dos estados inicial e objetivo A Figura 3 7 apresenta um arquivo de problema para o dom nio apresentado na Figura 3 6 define problem sat examplej domain satellite i objects satellite satellite instrumento instrument imagel mode Bpectrographe mode thermographo mode Ground tations direction Phenomenon4 direction init 7 Defini o do valor da fun o slew time Phenomenon4 GroundStationg 39 73 Slew time GroundStatione Phenomenond 40 00 Estado inicial do ambiente supports instrumento thermographo ton board instrumento satellited power avail satellited pointing satelliteO cround tationg goal and have image Phenomenon thermographoO i FIGURA 3 7 Arquivo de Problema em PDDL para 0 Dominio do Sat lite Fonte adaptada de Cardoso 2006 p 67 A descri o do problema cont m objetos objects que s o instancia es dos tipos definidos no dom nio e as descri es dos estados inicial init e objetivo goal do dom nio Para uma an lise detalhada deste dom nio consulte Cardoso 2006 58 3 3 4
10. es s o posicionadas nas linhas do tempo como tokens Cada token possui um momento de in cio e de fim sendo que qualquer um destes pode ser colocado como uma de egos a janela de tempo Isso permite por exemplo descrever o in cio de um token uma a o tanto como inicia s 12 03 quanto como inicia entre 12 00 e 12 05 76 A busca parcialmente ordenada ou seja a ordem das a es n o totalmente fixa O planejador explora o espa o de estados sem se comprometer com uma seq ncia totalmente ordenada de a es Isso reduz consideravelmente o tempo de busca uma vez que as restri es est o relaxadas e gera planos flex veis Entretanto esta abordagem depende de um executor inteligente capaz de selecionar dentro das op es dispon veis no plano a ordem e momento exato da execu o de cada a o Apesar de desenvolvido inicialmente para o Hubble o HSTS foi aplicado s miss es EUVE e Cassini foi usado como base para um planejador embarcado e deu origem ao motor de planejamento EUROPA que ser descrito adiante neste Capitulo 4 2 3 Planejamento nas Opera es dos Space Shuttles Outro projeto espacial extremamente complexo que motivou o desenvolvimento de sistemas planejadores com IA foram os space shuttles tamb m da NASA Entre suas miss es cada shuttle passa por uma etapa de processamento em solo Esta etapa envolve a inspe o manuten o e reparos da espa onave na pr
11. o ao planejador que ele mantenha pelo menos a quantidade de recursos solicitada pelo experimento durante o per odo entre h1 e h2 9 S o aplicadas as instru es guarantee resource contidas nos comportamentos Assim como a solicita o por recursos elas imp em restri es que devem ser respeitadas A diferen a que a solicita o por recursos informa apenas uma quantidade m nima a ser mantida para o experimento enquanto guarantee resource pode impor que os recursos garantidos se mantenham entre determinados valores m nimo e m ximo Ao finalizar as etapas descritas acima o Compositor de Problemas encaminha ao m dulo Planejador o problema na forma de um esbo o de plano de opera es com objetivos a atingir conflitos a resolver e restri es a respeitar 124 6 4 O Planejador Conforme apresentado no Cap tulo anterior foi definido que o problema de planejamento deve ser representado como um CSP e que deve ser aplicada busca local para encontrar a solu o O esbo o de plano encaminhado pelo Compositor de Problemas possui associadas a ele estruturas de dados que permitem o seu tratamento como um problema de satisfa o de restri es Ao receber o esbo o de plano o Planejador entra em um Joop em busca da solu o dos conflitos detectados Para cada conflito diversas op es para a solu o s o testadas e avaliadas e a melhor entre elas selecionada Este processo segue at que n o haja mais con
12. o do replanejamento obtidos a partir da simula o da solicita o por mais recursos disparada por um dos experimentos S o ent o descritos o processo de replanejamento e as escolhas feitas pelo planejador com os conflitos resolvidos e inseridos durante o processo A seguir apresenta se o tempo gasto com a composi o do problema e com o planejamento bem como o tamanho da aplica o compilada mostrando que ela est adequada para execu o a bordo de sat lites com o computador COMAV 7 1 O Modelo do Sat lite EQUARS Este item apresenta o modelo criado para o sat lite EQUARS composto de suas descri es est tica e din mica O modelo em RASSO ml correspondente descri o aqui colocada encontra se no Ap ndice A deste trabalho A descri o est tica do sat lite EQUARS em RASSO ml compreende e Duas classes Experiment e Antenna e Cinco objetos da classe Experiment CERTO GROM IONEX MLTM e TIP e um da classe Antenna Comm System e Dois recursos Power do tipo reservable e Mass Memory do tipo depletable Objetos da classe Experiment possuem atributos para nome status ligado desligado modo de opera o taxa de aquisi o de dados precis o dos dados coletados e 131 prioridade de execu o com rela o aos demais A classe Antenna possui apenas um atributo que indica se o sistema de comunica o est ligado ou desligado O recurso Power representa a bateria do sat lite e
13. 3 3 3 PDDL Um Padr o Para a Descri o de Modelos A aus ncia de um padr o para a descri o de modelos em planejamento tornava muito dif cil comparar a efic cia de sistemas planejadores quando aplicados a um mesmo problema Tendo isso em mente Mcdermott 1998 e o comit organizador da primeira edi o da International Planning Competition IPC desenvolveram uma linguagem a ser utilizada por todos os sistemas planejadores participantes da competi o de forma a permitir uma compara o emp rica entre seus desempenhos Esta linguagem era baseada na STRIPS e na ADL e recebeu o nome de Planning Domain Definition Language PDDL A cria o da PDDL melhorou a comunica o de resultados de pesquisa e disparou um aumento no desempenho expressividade e robustez de sistemas de planejamento Desde a vers o inicial algumas extens es para problemas de planejamento mais realistas foram propostos A PDDL 2 1 usada para a edi o de 2002 do IPC trouxe algum avan o na representa o do tempo com a es que possu am dura o em oposi o as a es pontuais existentes at ent o A vers o 2 2 implementou literais que permitem a representa o de eventos ex genos determin sticos Eventos ex genos s o eventos fora do controle do planejador mas que afetam o estado do modelo Em um plano para controlar um carro com o objetivo de levar seus passageiros de um ponto a outro em uma cidade por exemplo a abertura e o
14. baseado nos dados ambientais e agir Um agente de solu o de problemas capaz de considerar os efeitos de sequ ncias de a es antes de agir J um agente baseado em conhecimento pode selecionar a es 43 baseadas em representa es l gicas e expl citas do estado corrente e dos efeitos das a es Um sistema planejador une estes dois tipos de agentes em um agente de planejamento Ainda de acordo com Russell e Norvig um agente de planejamento difere de um agente de solu o de problemas na sua forma de representa o de estados objetivos e a es A id ia b sica do processo de planejamento simular o comportamento de um ambiente ao qual aplicada uma sequ ncia de a es tamb m chamadas na literatura existente de tarefas atividades ou operadores As caracter sticas do ambiente s o representadas de forma l gica por um conjunto de estados e cada a o aplicada ao ambiente pode modificar um ou mais de seus estados A meta encontrar a seqti ncia correta de a es que leve o ambiente de seu estado inicial a um estado desejado ou estado objetivo Para isso o planejador deve possuir um modelo do ambiente com representa es de seus estados um conjunto de a es aplic veis ao modelo cada uma possuindo suas pr condi es para execu o e a descri o de seus efeitos e os estados inicial e objetivo O processo de planejamento come a quando a partir de um estado inicial o sistema plane
15. durante a rbita ou mesmo per odos de tempo n o relacionados incid ncia solar Existem diversos fatores que restringem os experimentos Entre eles destacam se a quantidade de recursos dispon veis no sat lite o quanto uma bateria pode fornecer de energia por exemplo as restri es de comunica o taxas de transmiss o de telemetria dura o e frequ ncia das passagens sobre a esta o terrena e as restri es impostas pelas caracter sticas orbitais como a exposi o de experimentos luz solar objetivas de c meras e espelhos de telesc pios por exemplo n o devem ser expostos diretamente a ela Finalmente h um processo de negocia o entre os engenheiros da miss o e os cientistas respons veis pelos experimentos que ser o seus usu rios Como os recursos dispon veis s o limitados cada quantidade de recurso alocado a um experimento significa menos recursos dispon veis aos demais O resultado deste processo de negocia o um conjunto de quotas de recursos definidas para cada experimento Uma vez lan ado o sat lite seus experimentos passam a operar da forma previamente definida Entretanto as prioridades dos experimentos podem mudar durante a miss o e tamb m as quotas de recursos associadas a eles Por exemplo determinado experimento voltado an lise de part culas emitidas pelo Sol pode dispor de maior quantidade de recursos durante um per odo onde prevista maior atividade solar
16. espacial a ASPEN Modeling Language AML que ser descrita no pr ximo Cap tulo 3 4 Conceitos de Escalonamento em IA Scheduling De acordo com Smith et al 2000 o conceito comum de escalonamento dentro da rea de Intelig ncia Artificial de que se trata de um caso especial de planejamento no qual as a es j foram escolhidas restando apenas selecionar sua ordem e momentos de execu o Segundo eles esta uma simplifica o infeliz de escalonamento Um problema de escalonamento envolve a atribui o de recursos limitados em quantidade para tarefas distintas durante determinado per odo de tempo de forma a otimizar um ou mais objetivos Smith et al 2000 trazem tamb m algumas considera es sobre esta defini o 60 e Racioc nio sobre tempo e recursos o que comp e o n cleo do escalonamento Estes temas receberam at o final da d cada passada pouca aten o da comunidade de planejamento em IA e Problemas de escalonamento s o quase sempre problemas de otimiza o Embora seja f cil encontrar um conjunto de atribui es legais simplesmente aumentando o intervalo entre a execu o de tarefas encontrar um bom conjunto de atribui es muito mais dificil e Problemas de escalonamento tamb m envolvem escolhas Estas escolhas n o est o relacionadas apenas ordena o de tarefas mas tamb m sele o de quais recursos consumir Para uma determinada tarefa diversos recursos alte
17. estado intermedi rio 1 recursos j realocados estado intemedi rio 2 inicia a devolu o de recursos i I I i I 1 i i i estado objetivo tudo de volta ao normal linha do tempo t0 h0 h1 h2 h3 A A FIGURA 6 9 Horizontes de Planejamento e Objetivos O momento de in cio do per odo com mais recursos alocados para o experimento solicitante chamado de horizonte h1 ou simplesmente hl O momento de t rmino do per odo com mais recursos h2 Os horizontes hl e h2 indicam os momentos em que est o os estados objetivo intermedi rios do processo de planejamento O horizonte h1 indica o momento em que a quantidade solicitada dos recursos ja deve estar realocada para o experimento J h2 indica at quando estes recursos devem ser mantidos Em fun o destes h mais dois horizontes o horizonte inicial h0 e o horizonte final h3 O horizonte inicial h0 definido como sendo hl Al onde Al o tempo necess rio para a execu o de comandos de realoca o de recursos para o experimento solicitante Se um experimento houver solicitado mais energia a partir de hl por exemplo o planejador pode come ar a inserir comandos de realoca o a partir do momento ho De forma similar h3 determinado por h2 A2 onde A2 o tempo necess rio para devolver os recursos aos experimentos que os cederam Seguindo ainda o exemplo anterior se o experimento solicitou que
18. o call action tamb m poss vel descrever o consumo de recursos como ocorre com as a es e tamb m a sua gera o Na Figura 6 5 a primeira instru o generate resource indica que a mem ria de massa est sendo liberada taxa de 13800 unidades por minuto enquanto o sat lite encontra se na janela de comunica o com solo ou seja enquanto est sendo feita a transmiss o dos dados de experimentos para solo Ao t rmino da janela generate resource Mass Memory 0 indica que a transmiss o de dados se encerrou Al m de descrever os efeitos dos eventos ex genos comportamentos tamb m s o utilizados para impor restri es ao planejador durante o per odo de ocorr ncia das janelas de tempo s quais est o associados A instru o guarantee resource faz com que seja garantida uma determinada quantidade de recurso para um objeto durante certo per odo dentro da janela de tempo no exemplo da Figura 6 5 imposta a manuten o de pelo menos 5 4 unidades de energia para o experimento IONEX nos primeiros 12 minutos da janela de tempo Night 6 2 3 Lidando com o Tempo As a es e comportamentos modificam o estado do sat lite medida que s o executados no decorrer do tempo Para que o planejador consiga lidar com as mudan as no sat lite modelado ele deve n o apenas gerenciar objetos e recursos mas todos os estados que eles assumem no decorrer do plano ou seja todos os seus momentos Assim ao se c
19. this subsystem Reservation hydraulic lift usage i resource hydraulic lift usage i duration O 5 requires state prevalve purged TRUE requires state prevalve illuminated TRUE Resource hydraulic lift type non depletable quantity 1 FIGURA 4 1 Um Exemplo de Descri o de Modelo em AML Fonte Fukunaga et al 1997 p 6 Assim como seus precursores o ASPEN representa o problema de planejamento escalonamento como um CSP Para resolv lo o ASPEN n o conta com um algoritmo de busca espec fico Ao inv s disso ele suporta uma vasta gama de algoritmos inclusive algoritmos com backtracking de busca construtiva e de busca local Este ltimo considerado pelos autores como o mais importante e chamado por eles de algoritmo baseado em reparos basicamente o mesmo que foi desenvolvido para o DCAPS inclusive no uso de heur sticas para auxiliar na tomada de decis es O processo de gera o do plano possui um tempo limite timeout Caso um plano satisfat rio tenha sido alcan ado antes de atingir este limite o planejador utiliza o restante do tempo tentando otimizar o plano Os crit rios utilizados para determinar o n vel de otimiza o de um plano s o definidos previamente pelo usu rio Nesta etapa al m de tentar melhorar o plano atingido o ASPEN tenta atingir um conjunto de objetivos opcionais caso tenham sido especificados no problema Cada varia o vi vel do primeiro plano gerado com
20. 6 2 2 A Desericio Din mica do Modelo condon coi dcir 113 6 23 Lidando com o Tempe ccccc tecececcsccscissledecessscssaseecnecesaedcersteensdeessuesedesscoees 117 6 3 O Compositor de Problemas canina direis 120 6 3 1 Horizontes de Plate panic naco ici 121 6 3 2 Compondo um Problema Bem Definido occcoooccnonononcnnonnnnononanncnnnononononnn ono 123 6 4 Crane iaads 125 6 4 1 Os Momentos Chave na Linha do Tempo do Plano 126 642 A Identifica o dos Comflitos ccccccccccccsocsesccecedssvoveesecs cose secdecesedodessvorecsevecs 127 6 4 3 O Teste e a Aplica o de Mudan as no Esbo o de Plano oooooononoccncnononnnnons 128 CAP TULO 7 CEN RIO DE TESTES E RESULTADOS OBTIDOS 131 7 1 O Modelo de Satelite EQUARS coil ie decos 131 7 2 A A e RE TI ve geradas E 133 7 3 O Processo de Replanejamento e as Escolhas do Planejador 136 7 4 An lise do Processo de Replanejamento ooooocccnnoooccnoononononnnnnnnnnonnnncncononcnnnnnos 138 7 5 Adequa o do RASSO ao COMAY cccccccsssscesssesseceseneesesesseeeeesseaeescesseeseneegs 139 CAP TULO 8 CONCLUS O a SL RS 141 8 1 Ponciano ETA A 141 8 2 Trabalhos FOS AA sii sesnvanatenatcesiecuesvisdeedecvedets 143 8 3 So PAO essere orago Seco series GEES IN 144 REFER NCIAS BIBLIOGR FICAS ccccccesessessesescescessscescscescaccsesscseeseaecaeescseeseseseereees 147 AP NDICE A MODELO DO SAT LITE E EXPERIMENTOS EM
21. C ligue o subsistema de aquecimento Isso tem a desvantagem de que cada nova situa o a ser tratada demanda a inser o de uma nova regra a ser verificada J ferramentas que usam modelos representam sistemas num n vel maior de abstra o quando comparados com regras simples Isso permite a manipula o das informa es contidas no modelo e resulta na capacidade de inferir o comportamento do sistema em resposta a novas situa es que lhes forem apresentadas A forma de representa o do conhecimento utilizada para descrever um modelo pode definir o sucesso ou o fracasso de um sistema planejador Entre as abordagens para a representa o do conhecimento descritas nos Cap tulos 3 e 4 a grande maioria utiliza a representa o baseada em predicados herdada do STRIPS Mesmo a PDDL e a OCL linguagens modernas de planejamento em IA s o fundamentadas nos mesmos conceitos b sicos Estas formas de representa o possuem algumas limita es que dificultam seu uso em dom nios complexos como o espacial dentre as quais se destacam e A car ncia no que se refere representa o de recursos e de seu consumo e A forma limitada de descri o de pr condi es e efeitos n o h estruturas de loops ou sele es de casos e nem todas as linguagens baseadas em predicados possuem condicionais ifs e O fato de que modelos descritos nestas linguagens devem ser interpretados por um analisador parser e convertidos em e
22. Detec o de Fen menos Cient ficos de Curta Dura o 39 CAP TULO 3 PLANEJAMENTO E ESCALONAMENTO EM INTELIG NCIA A A RIR DR DD ER RD TR 43 3 1 Concerto de Pineamine aoe RU nile 43 3 2 Hist rico e Abordagens de Planejamento ooccccooocccooonnncnnoncnnnnnononononnnncncnnnnnonos 45 3 2 1 O Primeiro Plangjador E Seus BUSES cl Deca digest aed aaa 45 3 2 2 As Confer ncias na rea de Planejamento 47 3 2 3 Planejamento Baseado em Satisfatibilidade ooonococononoccccononncnononnnncnnononnoss 48 3 2 4 Planejamento Baseado em Grafos erre eerererenerereerrerenenereraranneo 50 3 2 5 Combinando Grafos e Saltisfatibilidade 6 55 cccccscsscessepnceisoceerddnsnerposcdererosensaneveee 52 3 2 6 Planejamento Baseado em Heuristicas de BUSCA coooococcnooocnnnononnnnononnnncnnnnnonoss 53 3 3 Formas de Representa o do Conhecimento Usadas em Planejamento 54 3 3 1 STRIPS o Paradigma Ainda Vigenite c cccssccccssesescesesesecessesteeeederseeeesenes 54 3 3 2 Relaxando as Restri es do STRIPS occ 0s s escccccccsseveevancssevssesscevessdsdessvorecevecsss 55 3 3 3 PDDL Um Padr o Para a Descri o de Modelos ccccccnnonononnncnnnnonnnnnnnnononons 56 3 3 4 OCL Uma Representa o Centrada em ObjetoS oooocccooconcnononnnnnnonnnncninnnonoss 59 3 3 5 Outras Formas de Representa o do Conhecimento ccoooocccnnnononcnononnnncnonananonnno 60 3 4 Conc
23. Enquanto uma a o deve possuir um ou mais comandos relacionados a ela na fila de telecomandos temporizados o comportamento RASSO Behavior descreve eventos que ocorrem ao in cio e t rmino de uma janela de tempo independente do plano de opera es corrente Em outras palavras os comportamentos descrevem os efeitos da ocorr ncia de eventos ex genos durante a execu o do plano A Figura 6 5 traz dois exemplos de comportamentos Night Behavior e Communicating Behavior RASSO Behavior Night Behavior behavior parameters at_start call action Turn On certo garante os 5 4 Watts p IONEX nos primeiros 12 min da janela guarantee resource IONEX Power 5 4 0 0 12 60 at_end call_action Turn_Off certo RASSO Behavior Communicating Behavior behavior parameters at_start taxa de transferencia para solo 230 kbits s ou 13 8 Mbits min generate resource Mass Memory 13600 per min ff o sistema de comunicacao consome 10W consume resource Comm System Power 10 at_end para de liberar memoria e de consumir energia generate resource Mass Memory 0 consume resource Comm System Power 0 FIGURA 6 5 Exemplos de Comportamentos em RASSO ml 116 Os blocos at start e at end em cada comportamento indicam quais efeitos est o relacionados ao in cio e ao t rmino da janela de tempo E poss vel inclusive efetuar chamadas a a es atrav s da instru
24. N Aloca o din mica de recursos computacionais para experimentos cient ficos com replanejamento automatizado a bordo de sat lites Fabr cio de Novaes Kucinskis S o Jos dos Campos INPE 2007 165 p INPE 14798 TDI 1241 1 Intelig ncia artificial 2 Planejamento 3 Escalonamento 4 Representa o do conhecimento 5 Autonomia I Titulo Dr Dr Dr Dra Dra Aprovado a pela Banca Examinadora em cumprimento ao requisito exigido para obten o do T tulo de Mestre em Computa o Aplicada Jos Demisio Sim es da Silva Presidente INPE SiCampfs SP Mauricio Gongalves Vieira Ferreira Orientador a INPE SJCampos SP Solon Venancio de Carvalho Membro da Banca INPE SJCampos SP Ana Maria Ambrosio A e x tre l ease Membro da Banca INPE S o Jos dos Campos SP Selma Shin Shimizu Melnikoff Coiividado a USP S o Paulo SP Aluno a Fabr cio de Novaes Kucinskis S o Jos dos Campos 30 de Mar o de 2007 Podemos avistar apenas uma curta dist ncia frente mas ali j vemos muito do que precisa ser feito Alan Turing ao encerrar seu Computing Machinery and Intelligence As mulheres da minha vida Olga e M riam AGRADECIMENTOS Poetas seresteiros namorados correi E chegada a hora de escrever e cantar talvez as derradeiras noites de luar Com os primeiros versos da letra de Lunik 9 Gilber
25. NCIA ARTIFICIAL De acordo com Fukunaga et al 1997 planejamento em IA a sele o e sequenciamento de atividades de forma que elas atinjam um ou mais objetivos e satisfa am um conjunto de restri es do dom nio Escalonamento definido por Zweben et al 1993 como o processo de atribuir tempo e recursos a tarefas em um plano satisfazendo ainda uma s rie de restri es de dom nio Uma defini o menos formal mas certamente mais esclarecedora foi dada por Myers e Smith 1999 por planejamento n s geralmente nos referimos ao processo de decidir o que fazer n s usamos o termo escalonamento geralmente para designar o processo de decidir quando e como fazer Este Cap tulo apresenta os conceitos de planejamento e escalonamento um breve hist rico das reas e as principais abordagens para a solu o de problemas de cada uma delas E ent o mostrado como estas t cnicas s o complementares e como elas v m sendo integradas nos ltimos anos 3 1 Conceitos de Planejamento A rea de pesquisa em planejamento se originou de uma melhor estrutura o das t cnicas cl ssicas de IA de busca pela solu o de problemas e da uni o destas t cnicas com os sistemas baseados em conhecimento que atualmente s o baseados no conceito de agentes Segundo Russell e Norvig 2004 um agente um sistema computacional com a capacidade de sentir seu ambiente tomar decis es a respeito do que fazer
26. O crit rio para determinar o n vel de otimiza o num plano o n mero de observa es cient ficas realizadas e a quantidade de dados enviados para solo Nos primeiros cinco dias da miss o o Data Chaser foi operado atrav s de planos gerados manualmente pelos especialistas de miss o Nos sete dias seguintes a gera o dos planos passou para o DCAPS De acordo com Chien et al 1998 o uso do DCAPS reduziu em 80 o esfor o nas opera es relacionadas gera o de planos em compara o queles gerados manualmente e aumentou o retorno cient fico em 40 79 4 2 4 Sistemas Planejadores de Uso Geral em Miss es Espaciais Talvez o mais bem sucedido sistema planejador na rea espacial o Automated Scheduling and Planning Environment ASPEN Fukunaga et al 1997 uma evolu o do DCAPS que foi criado pelo JPL para ser um ambiente para o desenvolvimento de aplica es de planejamento e escalonamento de prop sito geral Com caracter sticas herdadas tamb m dos planejadores GERRY e HSTS e desenvolvido por pessoal que estivera envolvido nestes projetos pode se considerar o ASPEN como uma consolida o dos conhecimentos adquiridos pelo JPL nas aplica es de planejamento anteriores da NASA O ASPEN um framework um conjunto reus vel de componentes de software que prov as funcionalidades comumente encontradas em sistemas complexos de planejamento e escalonamento S o elas e Uma linguagem expressiva de
27. Pode se facilmente notar que a integra o entre planejamento e escalonamento pequena neste caso e que o desempenho pode n o ser satisfat rio Uma forma de se tentar melhorar a efici ncia de um sistema em cascata aumentar a troca de informa es entre o planejador e o escalonador Ao inv s de apenas informar que n o conseguiu efetuar as atribui es o escalonador pode devolver ao planejador dados sobre o que n o foi poss vel atribuir para que esta informa o guie o processo de gera o de um novo plano 3 6 2 Verifica o de Viabilidade A verifica o de viabilidade utilizada para aumentar as chances de que planos gerados sejam vi veis com rela o ao escalonamento Isso envolve o uso das restri es impostas ao escalonador para filtrar ainda durante o planejamento as op es de a o a selecionar Resumidamente o escalonador chamado em pontos intermedi rios do plano para prover estimativas da viabilidade de diferentes alternativas de planejamento Esta forma de integra o especialmente adequada para o uso com planejadores hier rquicos que resolvem o problema em um n vel alto de abstra o para ent o partir 67 para a busca da solu o no n vel imediatamente mais baixo Neste caso o escalonador pode ser acionado ao obter um plano com sucesso em determinado n vel e antes de partir para o n vel inferior de abstra o Se o plano for escalon vel o planejador recebe permiss o para ir
28. action parameters parameter exp parameter new precision double new memory 0 when planning condition get current state by id Experiment exp on true condition get current state by id Experiment exp precision new precision hs condition get current state by id Experiment exp name certo get current state by id Experiment exp name grom force state if needed by id Experiment exp on true efeitos descritos a partir daqui set current state by id Experiment exp precision new precision switch get current state by id Experiment exp name case certo new memory 420 98 new precision break case grom new memory 711 12 new precision break default break apenas para nao disparar warning consume resource by id Experiment exp Mass Memory new memory per min when running printf Changing precision to i n new precision 163 action success DEFINICAO DAS JANELAS DE TEMPO E COMPORTAMENTOS DO MODELO x create time window Day create time window Night create time window Communicating RASSO Behavior When Day behavior parameters at_start call_action Turn_On mltm garante de 264 54 a 300 kbits m p MLTM nos primeiros 15 m da janela guarantee resource MLTM Mass Memory 264 54 per min 300 per min 0 15 8 60 at_end call action Turn
29. feira resulta em um plano operacional que colocado em execu o apenas na sexta feira da semana seguinte Embora o processo normal de planejamento n o seja o mesmo que seria seguido no caso da necessidade de se modificar o plano de opera es em resposta detec o de fen menos cient ficos de curta dura o ele d uma boa id ia do tempo despendido e do volume de trabalho envolvido no planejamento de uma miss o espacial 2 4 Resposta Detec o de Fen menos Cient ficos de Curta Dura o A forma de opera o dos experimentos descrita no item anterior perfeitamente adequada ao controle de experimentos de longa dura o ou seja aqueles que coletam informa es sobre determinado objeto de estudo por longos per odos de tempo e de forma repetitiva Entretanto existem fen menos de interesse cient fico que ser o chamados aqui apenas de fen menos cient ficos cuja ocorr ncia e dura o s o aleat rias uma perturba o ionosf rica por exemplo pode ocorrer a qualquer momento e se manifestar por poucos minutos ou por algumas horas Um experimento que detecte este tipo de fen meno pode precisar aumentar sua taxa de aquisi o ou a precis o dos dados coletados para fazer uma melhor observa o ou pode precisar simplesmente manter se operando por mais alguns minutos caso o seu desligamento esteja pr ximo de ocorrer Em qualquer um destes casos ele ir precisar de mais recursos do que as quo
30. o encaminhado ao m dulo Planejador seta 6 Cabe ao Planejador trabalhar para a solu o dos conflitos respeitando uma s rie de restri es que lhe foram impostas e buscando os objetivos que lhe foram passados Entre as restri es impostas est o as quantidades m nima e m xima de recursos dispon veis estados de experimentos que devem ser mantidos em certos momentos e outros Em suma os objetivos do planejador ser o 1 Realocar temporariamente os recursos solicitados pelo experimento 2 Devolver o sistema ao estado normal ap s a execu o do plano alterado em bordo 3 Fazer isso respeitando todas as restri es de estados e recursos impostas Ao obter um novo plano de opera es que consiga cumprir todos estes requisitos o RASSO o encaminha para a fila de telecomandos temporizados seta 7 substituindo o plano anterior e tornando o o novo plano de opera es corrente do sat lite Deve se lembrar que o programa SCE do INPE utiliza o conceito de experimentos inteligentes onde cada experimento possui software e processador pr prios 103 5 3 1 A Abordagem para a Representa o do Conhecimento Atualmente as decis es tomadas pelos sat lites do INPE s o geradas com base em regras colocadas como instru es l gicas Estas instru es geralmente se apresentam na forma de cl usulas condicionais simples tais como se a mensagem A chegar envie a mensagem B ou se a temperatura for menor que 10
31. o n o exista e Otimiza o dif cil efetuar otimiza o dentro de um sistema de busca local Pode se apenas combinar o crit rio de otimiza o com a fun o de avalia o de novos vizinhos ou impor restri es mais rigorosas ao problema Isso entretanto tem como custo uma maior dificuldade em encontrar solu es n o timas mas v lidas Deve se encontrar um meio termo entre uma solu o v lida e uma solu o tima para n o penalizar excessivamente o processo de busca 65 3 6 Unindo Planejamento e Escalonamento em IA Muitos problemas complexos do mundo real apresentam caracter sticas tanto de problemas de planejamento quanto de escalonamento Para estes n o suficiente encontrar uma sequ ncia de a es correta a executar Estas a es devem ser iniciadas em seus devidos momentos devem respeitar restri es de ordena o e intervalos de tempo entre outras a es do plano e devem ter sido escolhidas de forma a consumir recursos compartilhados da melhor forma poss vel Se a d cada de 1990 foi marcada pelo surgimento de novas abordagens para o planejamento a tend ncia da d cada de 2000 vem sendo a uni o das reas de planejamento e escalonamento em JA O melhor exemplo disso a mudan a em 2003 do nome da International Conference on Artificial Intelligence Planning Systems AIPS para International Conference on Automated Planning and Scheduling ICAPS Alguns exemplos de sistemas que integra
32. o para bordo do planejador ASPEN Devido s limita es do ambiente embarcado diversas funcionalidades presentes no ASPEN tiveram que ser removidas do CASPER Entre elas est o o planejamento hier rquico backtracking objetivos opcionais e a otimiza o de planos O CASPER seria utilizado no sat lite TechSat 21 da For a A rea Norte Americana Chien et al 1999 e na constela o de nanosat lites universit rios Three Corner Sat 3CS Chien et al 2001 mas a primeira miss o foi cancelada pelos militares e a segunda perdida durante o lan amento 91 Foi apenas com o sat lite de sensoriamento remoto Earth Observing One EO 1 que j utilizava o ASPEN em solo que o CASPER p de ser executado com sucesso Assim como a sonda DS 1 o sat lite EO 1 faz parte do programa New Millennium enquanto o objetivo da DS 1 era validar novas tecnologias para uso em sondas no espa o profundo o objetivo do EO 1 era fazer o mesmo para sat lites de observa o da Terra No EO 1 o CASPER faz parte do Autonomous Sciencecraft Experiment ASE Chien et al 2003 um experimento que envolve a detec o e a resposta aut nomas a eventos de interesse cient fico como inunda es e erup es vulc nicas A Figura 4 3 apresenta a arquitetura do ASE image Observation Onboard Planner Science EN overflight times observation goals e CASPER Planner high level spacecraft i plans of activities state information
33. Pelo RASSO cccc rei 137 7 4 Consumo Total de Energia e Mem ria Ap s o Replanejamento 138 3CS ABSTRIPS ADL AEB AIPS AML AOMPS ASE ASPEN BIRD CASPER CAST CBERS CCSDS CLARAty CNES COMAV CSP DCAPS DEA LISTA DE SIGLAS E ABREVIATURAS Three Corner Sat Abstraction Based STRIPS Action Description Language Ag ncia Espacial Brasileira International Conference on Artificial Intelligence Planning Systems ASPEN Modeling Language Autonomous On board Mission Planning Software Autonomous Sciencecraft Experiment Automated Scheduling and Planning Environment Bispectral InfraRed Detection Continuous Activity Scheduling Planning Execution and Replanning Chinese Academy of Space Technology China Brazil Earth Resources Satellites Consultative Committee for Space Data Systems Coupled Layer Architecture for Robotic Autonomy Centre National d Etudes Spatiales Computador Avan ado Constraint Satisfaction Problem Data Chaser Automated Planning System Divis o de Eletr nica Aeroespacial DLR DS 1 ECP EO 1 EQUARS ESA EUROPA EUVE FBM FNC GCC GPL GPSS HSP HSTS IA ICAPS INPE IPC JPL MAGA MAPGEN Deutsches Zentrum fiir Luft und Raumfahrt Deep Space One European Conference on Planning Earth Observing One Equatorial Atmosphere Research Satellite European Space Agency Extensible Universal Remote Operations Planning Architecture Extreme Ultraviolet Explore
34. RASSO ML 159 LISTA DE FIGURAS 2 1 Intera o entre os Segmentos Solo e Espacial e os Usu rios da Miss o 34 2 2 O Processo Normal de Planejamento de Sat lites Cient ficos do INPE 38 2 3 Diferentes Respostas Detec o de Fen menos Cient ficos 40 3 1 Aplica o de A es no Modelo At a Obten o do Estado Objetivo 44 3 2 Descri o de um Problema em STRIPS ooooonnccoccccncccnononoannnnnnoconnnnanonanococonanano nos 46 3 3 Estrutura da Gera o de Planos por Satisfatibilidade oooonocccnnnnocccnnoncnnonons 49 3 4 Grafo de Planejamento para o Mundo de Blocos 51 3 5 Busca Heur stica Aplicada ao Problema do Mundo de Blocos 53 3 6 Exemplo de um Arquivo de Dominio de um Sat lite em PDDL 57 3 7 Arquivo de Problema em PDDL para o Dominio do Sat lite 58 3 8 Exemplo de Descri o de Dominio Para o Mundo de Blocos em OCL 59 3 9 Algoritmo para a Solu o de CSPs por Busca Construtiva 62 3 10 Algoritmo para a Solu o de CSPs por Busca Local 64 3 11 Planejamento e Escalonamento em Cascata coooooocccnooooncncononcnonoonnnncnonnnncnnoncnnonnns 67 4 1 Um Exemplo de Descri o de Modelo em AML 82 4 2 A Arquitetura do RAX PS coococooooocccccoooonocoononononoonnnncnnononnnnnnn ono ncnnnnnncnnnn nn ncnnn cnn 90 4 3 A Arquitetura do A
35. SPACE DATA SYSTEMS CCSDS Telecommand summary of concept and rationale Washington D C USA December 1987 Report Concerning Space Data Systems Standards CCSDS 200 0 G 6 Green Book Issue 6 COOK S A MITCHELL D G Finding hard instances of the satisfiability problem a survey In Satisfiability Problem Theory and Applications DIMACS Series in Discrete Mathematics and Theoretical Computer Science American Mathematical Society 1997 151 CURRIE K TATE A O Plan the open planning architecture Artificial Intelligence v 52 n 1 pp 49 86 Elsevier Nov 1991 DAMIANI S VERFAILLIE G CHARMEAU M C An Earth watching satellite constellation how to manage a team of watching agents with limited communications In INTERNATIONAL JOINT CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS AAMAS 05 4 2005 Utrecht The Netherlands Proceedings Utrecht ACM Press 2005 DRABBLE B Mission scheduling for spacecraft the diaries of T SCHED In INTERNATIONAL EXPERT PLANNING SYSTEMS CONFERENCE 1 1990 London England Proceedings Brighton Institute of Electrical Engineers 1990 EROL K NAU D S SUBRAHMANIAN V S Complexity decidability and undecidability results for domain independent planning Artificial Intelligence v 76 n 1 2 pp 75 88 Elsevier Science Jul 1995 ESTLIN T GAINES D CHOUINARD C FISHER F CASTANO R JUDD M ANDERSON R NESNAS I Enabling autonom
36. a es relacionadas aos comandos na fila s o aplicadas ao modelo conforme suas tags temporais do momento atual at o horizonte h0 4 A Tabela de Janelas de Tempo lida S o verificadas as janelas que iniciam ou terminam at h0 Os comportamentos vinculados a estas janelas de tempo s o aplicados ao modelo do momento atual at h0 Com isso obt m se o estado inicial O Compositor do Problema passa ent o obten o do plano de opera es corrente e de seus efeitos sobre o modelo 123 5 Repete se o passo 3 desta vez obtendo e aplicando os comandos entre os horizontes h0 e h3 Todas as altera es nos estados dos objetos e recursos linhas de tempo e perfis s o armazenadas 6 Repete se o passo 4 agora obtendo os comportamentos entre h0 e h3 As instru es guarantee resource descritas nos comportamentos n o s o aplicadas neste momento Novamente as altera es nas linhas do tempo e perfis s o armazenadas Tendo o plano de opera es corrente do sat lite e seus efeitos aplica se as restri es ao planejador 7 O estado do sat lite ao t rmino do per odo de execu o do plano horizonte h3 marcado como objetivo final Isso faz com que o planejador respeite este estado e procure a es que levem o sat lite a eles durante o processo de planejamento 8 aplicada ao esbo o de plano a solicita o por mais recursos enviada pelo experimento Isso feito impondo como restri
37. a energia alocada seja mantida para ale at o momento h2 o planejador ter a partir de h2 at o momento h3 para inserir comandos no plano que realoquem novamente os recursos e assim colocar o sat lite em modo normal de opera es 122 preciso definir o que significa modo normal de opera es aqui como o RASSO se prop e a alterar temporariamente o modo de opera es do sat lite o plano gerado por ele deve garantir que ao atingir o horizonte h3 todos os objetos modelados estejam no mesmo estado que se encontrariam caso tivesse sido executado o plano original e que a quantidade de recursos dispon vel seja pelo menos igual quela que seria deixada pela execu o do plano original 6 3 2 Compondo um Problema Bem Definido A composi o do problema passa por tr s etapas principais a obten o do estado inicial do modelo no horizonte h0 a obten o do plano de opera es corrente do sat lite e o levantamento dos efeitos de sua execu o sobre o modelo entre h0 e h3 e a imposi o de restri es e estados objetivo intermedi rios e final ao planejador incluindo os conflitos a serem resolvidos Estas etapas s o detalhadas a seguir Obten o do estado inicial do modelo em h0 1 O modelo inicializado 2 O estado atual dos objetos do modelo obtido atrav s de chamadas a outros processos aplicativos do software de bordo do sat lite 3 A fila de telecomandos temporizados lida Todas as
38. agregado ou seja devem permitir que a miss o fa a mais do que poderia fazer de outra maneira sem amea a ao sucesso da miss o ao retorno cient fico ou seguran a da espa onave O problema escolhido neste trabalho de disserta o que a realoca o de recursos para experimentos cient ficos em bordo segue esta defini o A realoca o caso seja bem sucedida quando de uma solicita o por mais recursos agrega valor miss o pois permite uma melhor observa o dos fen menos Caso a realoca o n o seja poss vel os experimentos seguem operando conforme o originalmente programado sem qualquer tipo de perda Al m disso o servi o de replanejamento embarcado n o vital opera o do sat lite se ele for retirado ou desabilitado a qualquer momento nada acontecer ao restante do sistema 101 5 3 A Arquitetura do Servi o de Replanejamento A partir do estudo das arquiteturas dos sistemas planejadores descritos no Cap tulo 4 em especial dos sistemas de planejamento embarcado RAX PS e CASPER Figuras 4 2 e 4 3 foram identificados os seguintes componentes b sicos necess rios ao servi o de replanejamento e Um modelo do sistema com a descri o das caracter sticas e comportamento e Um m dulo para a gera o do problema de planejamento e Um m dulo que implemente o processo de planejamento A identifica o destes m dulos e a defini o de suas intera es deram origem arquit
39. apresentada a estrutura que foi definida para representar o conhecimento A seguir s o listadas as principais caracter sticas da linguagem de representa o do conhecimento criada para o prot tipo e utilizada para descrever o modelo do sat lite Descreve se ent o a implementa o dos outros m dulos do prot tipo o Compositor de Problemas e o Planejador com nfase na forma como cada um manipula o modelo 6 1 Estrutura para a Representa o do Conhecimento no RASSO Conforme descrito no item 3 3 deste trabalho um modelo de dom nio ou apenas modelo uma base de conhecimento que um sistema planejador pode utilizar para efetuar decis es racionais sobre o dom nio representado Para o RASSO foi definido que o modelo do sat lite deve ser composto por duas descri es complementares a descri o est tica e a descri o din mica A descri o est tica de um modelo cont m a estrutura do modelo ou seja os objetos que comp em o sat lite ou a parte dele que se encontra representada no modelo as classes a que estes objetos pertencem e os recursos dispon veis para consumo por estes objetos A descri o din mica de um modelo cont m os operadores que modificam o estado do modelo Estes operadores s o de dois tipos as a es e os comportamentos 109 Uma a o corresponde a um ou mais comandos internos do sat lite e descreve como o modelo afetado por sua execu o J um comportamento
40. comandos gerados e validados em solo que s o ent o enviados para o sat lite e agendados para execu o futura Ao conjunto de telecomandos temporizados dado o nome de plano de opera es J4 Qualquer anomalia relacionada opera o dos experimentos relatada pelo sat lite para a equipe de opera o em solo via telemetria Ap s analisar os dados sobre a anomalia e sobre o estado do sat lite a equipe junto aos respons veis pelos experimentos e outros envolvidos na miss o pode ou n o modificar o plano de opera es corrente Como a comunica o ocorre apenas quando o sat lite passa sobre sua esta o terrena de rastreio o tempo transcorrido entre a detec o da anomalia e a recep o e execu o de um novo plano de opera es para lidar com ela pode ser de dezenas de horas Esta forma de opera o dos experimentos perfeitamente adequada para observa es cient ficas de longa dura o Existem entretanto fen menos de curta dura o cuja ocorr ncia aleat ria uma perturba o ionosf rica por exemplo pode ocorrer a qualquer momento e se manifestar por poucos minutos ou por algumas horas Para analisar melhor estes fen menos pode ser importante aumentar a taxa de aquisi o ou a precis o dos dados coletados por um experimento Isso aumenta o consumo de recursos como energia e mem ria de armazenamento para al m do originalmente previsto Devido curta dura o e dificuldade em
41. considerado totalmente operacional em abril de 2005 O uso do CASPER gerou at o momento uma economia de cerca de um milh o de d lares na opera o do EO 1 Um relato detalhado do processo gradual de implanta o pode ser encontrado em Chien et al 2005 A Figura 4 4 apresenta uma linha do tempo com todos os sistemas planejadores com Intelig ncia Artificial aplicados a miss es espaciais descritos neste Cap tulo RAX PS CASPER NASA bordo DEVISER SPIKE GERRY HSTS DCAPS EUROPA MAPGEN ASPEN NASA solo 1993 1994 1995 1997 1999 2003 2004 2 v e T SCHED 4 Surrey 3 ui PLAN ERS1 OPTIMUM AIV MEXAR MEXAR2 FIGURA 4 4 Sum rio dos Planejadores com IA Aplicados a Miss es Espaciais 93 Os ret ngulos em cinza destacam as linhagens de planejadores O RAX PS e o CASPER que representam o estado da arte em planejamento com IA para a rea espacial s o como se pode notar as vers es embarcadas das duas mais utilizadas linhagens de planejadores em miss es espaciais O ENSEMBLE e o OMPS n o est o representados aqui por se tratarem de sistemas ainda em desenvolvimento 4 3 2 O Futuro do Planejamento Embarcado O uso de planejamento com IA executado em solo que foi iniciado com o desenvolvimento de sistemas aplic veis a uma nica miss o como exemplos temos o DEVISER SPIKE GERRY e DCAPS passou a ter como foco a partir da segunda metade da d cada de 1990 a busca po
42. e de bordo Isso se d quando ele se encontra sobre a esta o terrena A este per odo de visibilidade e comunica o entre o sat lite e a esta o terrena dado o nome de passagem O tempo de passagem varia de uma rbita para outra podendo mesmo n o ocorrer em alguns casos Nos sat lites operados pelo INPE todos categorizados como de rbita baixa os SCDs orbitam a cerca de 750 km de altitude e os CBERS a 778 km e com dura o m dia de cerca de 100 minutos o tempo m dio de passagem gira em torno de 10 minutos ou seja 10 do seu tempo em rbita Para lidar com esta limita o e monitorar o sat lite durante toda a sua rbita existem dois tipos de telemetria a telemetria de tempo real e a armazenada A telemetria de tempo real utilizada para monitorar durante o per odo da passagem o status dos principais subsistemas do sat lite como a bateria e o computador de bordo Assim caso seja detectada qualquer anomalia comandos podem ser enviados para tentar corrigi la ainda durante a passagem A telemetria armazenada pode conter dados sobre os estados dos equipamentos relatos da execu o de comandos alertas mensagens de erro e dados da carga til Estes dados s o gerados durante a rbita e armazenados para envio em passagens futuras Os pacotes de telecomandos s o enviados da esta o terrena para o sat lite Eles cont m comandos gerados pela equipe de opera es para serem executados pelo sa
43. em IA na rea espacial a linguagem desenvolvida para o prot tipo traz uma nova forma de representar o consumo de recursos especialmente adequada para uso no segmento espacial por estar mais pr xima forma de opera o real de sat lites e espa onaves em geral Para a comunidade de planejamento e escalonamento em IA este trabalho representa uma contribui o significativa para a representa o de problemas de planejamento O fato de n o ser poss vel utilizar PDDL ou qualquer outra linguagem de representa o do conhecimento no ambiente de execu o do RASSO levou cria o da RASSO ml que possui uma s rie de caracter sticas bastante diferentes do que comumente visto em sistemas baseados nos conceitos da STRIPS e da PDDL e A integra o do modelo ao c digo fonte e O uso dos recursos da linguagem de programa o para aumentar a representatividade do modelo e A forma de descrever a es e eventos ex genos e as instru es para manipula o de objetos no tempo e A aplica o de structs para a descri o de objetos o que leva o modelo mais pr ximo Orienta o a Objetos do que por exemplo a OCL que conforme mostrado no Cap tulo 3 toma por objeto um agrupamento de predicados O uso de OO para descrever modelos de dom nio para planejamento algo que vem sendo perseguido pela comunidade nos ltimos anos A aceita o de artigos relacionados a este trabalho em confer ncias internacio
44. integra o entre o processo de planejamento e o restante do software do sat lite A linguagem de representa o do conhecimento traz uma forma mais pr xima de modelar a opera o e o comportamento de sat lites do que outras linguagens existentes n o voltadas rea espacial Os resultados obtidos mostram que o prot tipo desenvolvido adequado para execu o no ambiente embarcado e que este trabalho pode ser considerado um primeiro passo no sentido de aumentar a autonomia do software embarcado nos futuros sat lites do INPE DYNAMIC ALLOCATION OF COMPUTATIONAL RESOURCES FOR SCIENTIFIC EXPERIMENTS WITH AUTONOMOUS REPLANNING ABOARD SATELLITES ABSTRACT The experiments aboard the Brazilian scientific satellites are currently thought to execute its tasks in a repetitive way collecting storing and sending data in a cycle that does not suffer great alterations This way of dealing with the experiments operation fits perfectly to long term scientific observation There are however short duration scientific phenomena of which occurrence although predictable are random To better analyze these phenomena it may be important to increase the acquisition rate or the precision of the data collected This increases the consumption of resources such as memory and power beyond the originally predicted Due to the short duration and the difficulty to specify exactly when a phenomenon of this kind will occur it is not enough to leave the ground
45. integration of scheduling and planning In INTERNATIONAL CONFERENCE ON AUTOMATED PLANNING AND SCHEDULING ICAPS04 2004 Whisler Canada Proceedings Whisler AIAA 2004 INSTITUTO NACIONAL DE PESQUISAS ESPACIAIS INPE Homepage da MECB miss o espacial completa brasileira S o Jos dos Campos 1999 Dispon vel em lt http www inpe br programas mecb default htm gt Acesso em 17 de janeiro de 2007 INSTITUTO NACIONAL DE PESQUISAS ESPACIAIS INPE Homepage do CBERS sat lite sino brasileiro de recursos terrestres S o Jos dos Campos 2003 2006 Dispon vel em lt http www cbers inpe br pt index pt htm gt Acesso em 15 de fevereiro de 2007 INSTITUTO NACIONAL DE PESQUISAS ESPACIAIS INPE Equatorial atmosphere research satellite home page S o Jos dos Campos 2005 Dispon vel em lt http www laser inpe br equars gt Acesso em 12 de janeiro de 2007 153 INSTITUTO NACIONAL DE PESQUISAS ESPACIAIS INPE Homepage do programa de sat lites cient ficos do INPE S o Jos dos Campos 2006 Dispon vel em lt http www cea inpe br satelites php gt Acesso em 20 de dezembro de 2006 JOHNSTON M SPIKE AI scheduling for NASA s Hubble space telescope In IEEE CONFERENCE ON AI APPLICATIONS CAIA 90 6 1990 Santa Barbara CA USA Proceedings Santa Barbara IEEE 1990 pp 184 190 JOHNSTON M MILLER G SPIKE intelligent scheduling of Hubble space telescope observations Intelligent Scheduling
46. it was also necessary to develop a knowledge representation language and a planning system specific for this domain The prototype created is based on the idea of guaranteeing a greater integration between the planning process and the rest of the satellite software The knowledge representation language brings a form of modeling closer to the operation and behavior of satellites than other existing languages which are not directed to the space area The results gotten show that the prototype is adequate for execution in the onboard environment and that this work can be considered a first step in the direction of increasing the autonomy of the software aboard future INPE s satellites SUM RIO LISTA DE FIGURAS LISTA DE SIGLAS E ABREVIATURAS CAP TULO 1 INTRODU O sssiccinnin e 25 1 1 Motiva o do Trabalho de Pesquisa cscesentesrenristesserelossnnas icortstabecsevestsent c nisoueceb 28 1 2 Objetivos de Trabalho de PESQUIAA sas c isciasscescisosccssssusenaseraceassiessssabesaniedaccesssnanees 29 1 3 Metodologia de Trabalho e Organiza o Desta Disserta o oooooocccioncncnnoonanos 30 CAP TULO 2 CONTROLE E OPERA O DE SAT LITES CIENT FICOS 33 21 Defini o de Miss o Espacial Sistema Espacial e Seus Segmentos 33 22 Pacotes de Telemetria e de Telecomandos ccc cccccc0cccecccccseseseeesesetececeseneees 34 23 Modos de Opera o de Experimentos Cient ficos ese 36 2 4 Resposta
47. limitado ao fornecimento de 50 Watts de energia enquanto que Mass Memory representa a mem ria de massa para os dados dos experimentos e disponibiliza 120 Mbits a serem compartilhados entre todos eles A descri o din mica do modelo composta por e Cinco a es Turn On Turn Off Change Mode Change Sample Rate e Change Precision e Tr s janelas de tempo Day Night e Communicating e Tr s comportamentos um associado a cada janela de tempo When Day When Night e When Communicating As a es n o s o aplic veis a todos os objetos Turn One Turn Off por exemplo n o podem ser executadas para o experimento IONEX Este experimento n o pode ser desligado pode se apenas alternar seus modos de opera o entre full e partial pela a o Change Mode O IONEX est plenamente ativo durante a fase em eclipse da rbita e parcialmente ativo durante a fase iluminado Change Sample Rate e Change Precision alteram respectivamente a taxa de amostragem e a precis o dos dados coletados por um experimento e aumentam o consumo de mem ria e energia para o experimento As janelas de tempo representam as fases iluminada e em eclipse de uma rbita e o per odo de comunica o com a esta o de rastreio em solo As duas primeiras janelas s o consecutivas e a terceira pode ocorrer a qualquer momento sobrepondo se s anteriores O comportamento associado janela Day indica que o experimento MLTM ligado automaticame
48. modelagem de restri es que permite ao usu rio definir naturalmente o dom nio da aplica o e Um sistema de gerenciamento de restri es para a representa o da operabilidade da espa onave e das restri es de recursos bem como dos requisitos das atividades e Um sistema de racioc nio temporal para a express o e tratamento de restri es temporais e Uma interface gr fica para a visualiza o dos planos A linguagem de modelagem criada para o ASPEN a ASPEN Modeling Language AML Um modelo descrito em AML possui sete componentes b sicos par metros depend ncias entre par metros restri es temporais recursos vari veis de estado reservas e atividades Um par metro simplesmente uma vari vel com um dom nio restrito e bem definido Este dom nio pode ser um subconjunto dos inteiros por exemplo Outros tipos de 80 par metros aceitos incluem n meros de ponto flutuante valores booleanos e strings Uma depend ncia entre par metros um relacionamento funcional entre dois par metros Um momento de t rmino de uma atividade por exemplo uma fun o soma do momento de in cio e da dura o da atividade Uma restri o temporal o relacionamento entre o momento de in cio de uma atividade e o momento de t rmino de uma outra qualquer Pode se especificar por exemplo que uma atividade de prepara o de um instrumento deva ser encerrada entre um e cinco segundos antes de uma ativ
49. no qual um sistema gerenciador global atua em coopera o com planejadores embarcados para efetuar observa es de forma coordenada Damiani et al 2005 Este entretanto apenas um exerc cio conceitual Na DLR a ag ncia espacial alem um artigo Axmann e Wickler 2006 relata o desenvolvimento de um sistema em C com planejamento e escalonamento embarcados a ser aplicado ao sat lite Bispectral InfraRed Detection BIRD Segundo os autores este sistema batizado de Autonomous On board Mission Planning Software 95 AOMPS permite a automatiza o das opera es de carga til do sat lite Infelizmente o artigo vago demais para permitir qualquer an lise mais aprofundada O INPE como apresentado no item 4 2 6 deste Cap tulo j possui uma linha de pesquisa de planejamento com Intelig ncia Artificial para o suporte s opera es de controle de sat lite em solo A proposta deste trabalho de disserta o a ser detalhada no pr ximo Cap tulo dar um passo inicial para os estudos de planejamento a bordo de sat lites do INPE visando o aumento de sua autonomia a partir do desenvolvimento de um prot tipo de servi o de replanejamento embarcado 96 CAP TULO 5 PROPOSTA PARA UM SERVI O DE REPLANEJAMENTO EMBARCADO Este Cap tulo apresenta uma proposta para a implementa o de um servi o de replanejamento embarcado em sat lites do INPE Primeiramente mostrado o contexto no qual o servi o de
50. o deste conjunto de cl usulas por um algoritmo chamado GSAT apresentou um 48 desempenho superior ao dos demais planejadores da poca A Figura 3 3 apresenta as etapas do processo de planejamento baseado em Satisfatibilidade Proposicional Descri o do Problema e estado inicial i Simplificador e estado objetivo a es ta I tabela de s mbolos A FIGURA 3 3 Estrutura da Gera o de Planos por Satisfatibilidade Um Compilador recebe a descri o do problema e gera uma F rmula Normal Conjuntiva FNC proposicional equivalente a um plano de tamanho n A FNC uma conjun o de cl usulas booleanas no formato estadol OR estado2 AND estado3 A FNC gerada ent o enviada ao Simplificador Cabe a ele reduzir o tamanho da f rmula atrav s de t cnicas de otimiza o em tempo polinomial elimina o de literais e propaga o de cl usula nica O Gerador tenta ent o encontrar um conjunto de atribui es para os elementos da FNC que resulte numa express o verdadeira Caso nenhum conjunto de atribui es torne a express o verdadeira o processamento retorna ao Compilador que aumenta o tamanho estimado do plano e gera uma nova f rmula O processo segue at que o Gerador seja capaz de encontrar os valores para tornar a FNC verdadeira Quando isso ocorre o Decodificador traduz a f rmula em um plano aplic vel ao estado inicial do problema e o encaminha para exe
51. o na vizinhan a A 3 4 Se nenhuma restri o violada ent o retornar A 5 6 4tribua A A FIGURA 3 10 Algoritmo para a Solu o de CSPs por Busca Local Fonte adaptada de Smith et al 2000 p 17 Um vizinho uma atribui o que esta pr xima da atribui o existente em geral uma atribui o que difere no valor de apenas uma das vari veis embora existam outras vers es desta abordagem O processo de gera o da vizinhan a varia em termos de quantos e quais vizinhos s o gerados Uma solu o selecionar uma vari vel que est relacionada a uma restri o violada pode se dizer que ela contribui para a viola o da restri o e ent o gerar um conjunto de atribui es que mude apenas o valor da vari vel selecionada Uma abordagem mais completa embora mais custosa consiste em gerar vizinhos para todas as vari veis que contribuem para a restri o violada Uma vez que os novos conjuntos de atribui es as novas vizinhan as tenham sido gerados eles s o analisados e elencados Tipicamente isso baseado no n mero de restri es satisfeitas mas as restri es podem tamb m ser priorizadas de acordo com o 64 qu o importante satisfaz las Seleciona se ent o um dos conjuntos de atribui es e repete se todo o processo at se eliminar todas as viola es Algoritmos de busca local podem sofrer de problemas de plat s e de m nimos locais Plat s s o
52. observa es normalmente para um per odo de poucas semanas Ele ent o traduz este plano detalhado em sequ ncias de comandos a serem enviados para o Hubble O SPIKE desenvolvido em Common Lisp representa o problema de escalonamento como um CSP e utiliza uma t cnica chamada por Johnston e Miller 1994 de reparo estoc stico de m ltiplos in cios que baseado em busca local auxiliada por heuristicas Al m do Hubble o SPIKE foi utilizado em outras miss es de observa o do espa o como os sat lites Extreme Ultraviolet Explorer EUVE e o Chandra X Ray Observatory entre outros Outro planejador desenvolvido originalmente para o telesc pio espacial foi o Heuristic Scheduling Testbed System HSTS Muscettola et al 1995 um projeto conjunto entre o Jet Propulsion Laboratory JPL e o Ames Research Center ambos da NASA O HSTS usa decomposi o hier rquica e uma forma de busca local batizada como reparo iterativo al m de permitir o uso de heur sticas espec ficas para cada dominio Ele possui um conjunto rico de restri es temporais e de recursos o que torna a representa o de seus modelos muito expressiva mas ao custo de uma maior complexidade do planejamento O HSTS utiliza vari veis de estado para descrever os componentes do sistema e as representa como linhas do tempo Estas linhas do tempo indicam o estado corrente e a evolu o no tempo dos valores atribu dos s vari veis A
53. precisar quando um fen meno deste tipo ir ocorrer n o suficiente deixar a cargo da equipe de opera es em solo a gera o de um novo plano de opera es que reconfigure o sistema O tempo necess rio para que o 26 fen meno seja relatado e para que a equipe de opera es gere e envie um novo plano ao sat lite em geral muito maior que a dura o do fen meno Neste caso a oportunidade cient fica para analis lo adequadamente ter sido perdida Surge ent o a necessidade de se permitir que os experimentos ao detectarem a ocorr ncia de fen menos de curta dura o solicitem diretamente ao computador de bordo do sat lite a modifica o do plano de opera es corrente de forma a realocar temporariamente os recursos necess rios para que sejam capazes de realizar uma an lise mais detalhada Entretanto esta realoca o deve ocorrer de tal forma que afete o m nimo poss vel a opera o dos outros experimentos e do pr prio sat lite Como o n mero de estados em que o sistema pode estar no momento da detec o do fen meno enorme torna se dif cil o uso de t cnicas cl ssicas de programa o para trat los Neste contexto as t cnicas de Planejamento e Escalonamento da rea de Intelig ncia Artificial IA apresentam se como uma solu o em potencial a ser explorada e uma das mais promissoras tecnologias aptas a aumentar a autonomia dos sat lites O Planejamento tem como base a simula o da execu o
54. regi es no espa o de busca nas quais nenhuma atribui o aumenta o valor da fun o objetivo M nimos locais s o regi es onde todas as atribui es vizinhas s o piores que a atual Nestas regi es a busca local pela sua caracter stica de busca nas vizinhan as ineficiente Estes s o os principais motivos da gera o de um novo conjunto inicial de atribui es a cada tentativa A comunidade de TA desenvolveu algumas t cnicas para lidar com estes problemas Um m todo para escapar de plat s e m nimos locais a perturba o aleat ria Ao inv s de sempre selecionar a melhor atribui o vizinha um vizinho aleat rio selecionado ocasionalmente Isso permite eventualmente escapar de plat s e m nimos locais explorando outras reas do espa o de busca Segundo Smith et al 2000 estudos emp ricos demonstraram que os m todos de busca local frequentemente resolvem problemas mais rapidamente que a busca construtiva Por esta raz o estes m todos v m sendo usados para resolver um grande n mero de problemas pr ticos ou seja problemas do mundo real Existem entretanto dois pontos fracos a se considerar com rela o ao uso da busca local e Completeza com a busca construtiva se houver uma solu o ela ser eventualmente encontrada Esta garantia n o existe para a busca local Adicionalmente o procedimento de busca local pode apenas falhar ao encontrar uma solu o ele n o pode concluir que tal solu
55. remoto ERS 1 O segundo sistema desenvolvido foi o Optimum AIV Aarup et al 1994 utilizado para auxiliar no processo de montagem integra o e verifica o de lan adores de sat lites Ariane IV Ambos os planejadores foram baseados na arquitetura O Plan O O Plan uma arquitetura aberta de planejamento desenvolvida em Common Lisp por Currie e Tate 1991 Ele trabalha com decomposi o hier rquica al m de aceitar heuristicas para auxiliar o processo de busca Sua linguagem de descri o bastante rica permitindo a representa o de restri es de recursos de consumo discreto cont nuo e renov veis Al m disso tamb m estavam presentes a representa o de tempo e operadores de ordena o after before etc Outra demonstra o de planejador com IA em uma aplica o espacial que tamb m foi baseada em O Plan foi o T SCHED Drabble 1990 desenvolvido para o sat lite UOSAT I da Universidade de Surrey Foi gerada uma seqii ncia de vinte e quatro horas de comandos que foram enviados ao sat lite e executados com sucesso 4 2 2 Escalonamento de Observa es para o Telesc pio Espacial Hubble O telesc pio espacial Hubble um dos maiores e mais complexos sistemas espaciais j desenvolvidos Ele efetua dezenas de milhares de observa es astron micas a cada ano propiciando grandes descobertas cient ficas e imagens espetaculares do Universo Qualquer astr nomo de qualquer nacionalidade pode solicitar
56. replanejamento embarcado foi inserido e as caracter sticas do problema a ser tratado A seguir dada uma vis o geral da arquitetura proposta para o servi o e as abordagens escolhidas para a forma de representa o do conhecimento e para o processo de replanejamento O Cap tulo encerra descrevendo a forma prevista para a implanta o do servi o em uma miss o real atrav s de uma abordagem gradual e baseada na an lise dos planos modificados em rbita por parte dos operadores em solo 5 1 Contexto Definido para o Prot tipo do Servi o de Replanejamento Houve a preocupa o neste trabalho de Disserta o de se contextualizar o desenvolvimento de um prot tipo do servi o de replanejamento embarcado dentro dos projetos do INPE Foram identificados dois projetos no Instituto que poderiam ser relacionados a um esfor o para o aumento da autonomia do segmento espacial O primeiro o projeto de um novo computador de bordo para sat lites escolhido como ambiente de execu o e desenvolvimento de software O segundo o projeto do pr ximo sat lite cient fico do programa SCE escolhido para ser utilizado como base para o estudo da modelagem da aplica o Ambos s o apresentados a seguir 97 5 1 1 O Projeto do Computador Avan ado COMAV O INPE possui diversos projetos de desenvolvimento cient fico e tecnol gico geridos por diferentes grupos de trabalho espalhados pelo Instituto Entre estes projetos encon
57. representa o estudadas a que mais se assemelha ao que se pretende obter neste trabalho a AML utilizada pelo planejador ASPEN A AML possui uma sintaxe baseada na linguagem de programa o C veja a Figura 4 1 uma vez que o modelo compilado junto ao planejador que foi desenvolvido em C Na cria o de uma aplica o com o ASPEN um parser desenvolvido em Java respons vel por substituir as instru es ao planejador por c digo C transformando um arquivo de modelo em um arquivo fonte compil vel Esta etapa de pr processamento poderia ser evitada caso as instru es ao planejador fossem implementadas por macros da linguagem de programa o Assim o respons vel pela interpreta o do modelo passaria a ser o pr compilador da linguagem de programa o 105 Foi decidido ent o pelo uso da pr pria linguagem de programa o para descrever o modelo de planejamento Macros devem ser utilizadas para implementar as instru es da linguagem de modelagem e os recursos da linguagem de programa o devem ser aproveitados para aumentar a capacidade de representa o do dom nio 5 3 2 A Abordagem para o Processo de Replanejamento A abordagem mais comum para a representa o de problemas de planejamento com IA utilizada na rea espacial trat los como Constraint Satisfaction Problems CSPs como foi apresentado no Cap tulo 4 deste trabalho Um esbo o de plano gerado normalmente a partir do plano de oper
58. sistema aut nomo certo que uma vez superada a dificuldade inicial em se desenvolver validar e implementar sistemas com maior autonomia seus 28 benef cios ser o consider veis ser poss vel haver uma melhoria na execu o de tarefas rotineiras a execu o de novas aplica es n o previstas atualmente e uma potencial redu o de custos na opera o de sat lites A tecnologia escolhida para este estudo do aumento da autonomia em sat lites a de Planejamento e Escalonamento em JA que vem sendo estudada e aplicada gradualmente no controle de miss es espaciais notadamente da NASA e da ESA Embora a maioria dos projetos seja para a gera o de planos de opera o em solo h casos relatados de planejamento embarcado em espa onaves da NASA 1 2 Objetivos do Trabalho de Pesquisa Este trabalho de pesquisa visa o estudo e a defini o de uma arquitetura que permita a altera o do plano de opera es ou replanejamento de um sat lite cient fico quando da detec o da ocorr ncia de um fen meno cient fico em rbita de forma a reconfigurar o sat lite para fazer uma melhor observa o do fen meno Deve ser desenvolvido um prot tipo que implemente as funcionalidades da arquitetura total ou parcialmente Foi escolhido um problema que devido s suas caracter sticas de ocorr ncia aleat ria e curta dura o dificilmente seria resolvido sem o replanejamento embarcado r E necess rio ainda que o pr
59. testado pelo Planejador Esta modifica o resolveu os conflitos de consumo total de energia e mem ria deixando apenas o conflito de estado imposto ao TIP para ser resolvido Em uma nova busca por modifica es que resolvam este conflito o Planejador n o encontrou op es aplic veis Ele inseriu ent o uma perturba o no plano para tentar solucionar o conflito Como j explicado a perturba o consiste da adi o de uma a o que resolva o conflito mas cujos pr requisitos n o sejam verdadeiros no momento em que ela foi inserida A a o adicionada como perturba o no plano foi a Change Sample Rate tip 1 inserida aos 12000s Apesar de esta a o devolver a taxa de amostragem do TIP ao seu normal ap s o per odo de observa o do fen meno ela tem como pr requisito que o TIP esteja ligado o que era falso aos 12000s havia uma a o Turn Off imediatamente 136 antes Um novo conflito de estado imposto foi inserido TIP deveria estar ligado aos 12000s e o Planejador buscou uma a o para ligar o TIP Ap s inserir Turn Ont tip e resolver mais este conflito um ltimo conflito foi inserido TIP deveria estar novamente desligado ap s os 12000s A adi o de um novo comando Turn_Off tip tamb m aos 12000s solucionou o problema sem adicionar novos conflitos O plano modificado para atender solicita o de TIP apresentado na Figura 7 3 Os comandos inseridos pelo RASSO est o em negr
60. 2 Pacotes de Telemetria e de Telecomandos O monitoramento o controle e a comunica o com o sat lite s o feitos atrav s de sistemas de telemetria e de telecomandos Um sistema de telemetria tem como prop sito transportar de forma transparente e confi vel informa es de medi o de uma origem de dados remotamente localizada para usu rios distantes desta origem CCSDS 1987 a Um sistema de telecomandos deve transportar informa es de controle de um ponto de origem como um operador humano para um equipamento remotamente localizado CCSDS 1987 b As unidades de telemetria e telecomandos s o chamadas de pacotes ou mensagens Os pacotes de telemetria s o enviados do sat lite para a esta o terrena Eles podem conter dados sobre o estado do sat lite como temperatura n veis de tens o el trica situa o de seus subsistemas se est o ligados ou n o seus modos de opera o e par metros de funcionamento atuais ou dados de carga til como dados brutos de imagens valores lidos por sensores de experimentos etc Pacotes de telemetria 34 carregam ainda relatos sobre o sucesso ou falha na execu o de comandos mensagens de erro e alertas sobre anomalias detectadas Durante sua rbita o sat lite s pode receber comandos e transmitir dados durante o per odo em que h visibilidade entre sua antena e a da esta o terrena ou seja no per odo em que poss vel a comunica o entre as antenas de solo
61. 997 a ESA patrocinou a adapta o do kernel do RTEMS para o ERC32 como parte de sua estrat gia para a obten o de independ ncia tecnol gica em sistemas espaciais Atualmente a vers o para ERC32 do RTEMS homologada para uso em aplica es espaciais Por ser um projeto de desenvolvimento tecnol gico que propicia maior poder computacional e por se colocar como um poss vel computador de bordo para as futuras miss es espaciais do INPE o COMAV apresenta se como uma oportunidade para que sejam iniciados estudos com planejamento embarcado Assim foi definido que o prot tipo do servi o de replanejamento embarcado deve ser desenvolvido como um software aplicativo do Computador Avan ado 5 1 2 O Sat lite Cient fico EQUARS como Aplica o Alvo De acordo com o Plano Nacional de Atividades Espaciais AEB 2005 os pr ximos sat lites cient ficos do programa SCE ser o o Equatorial Atmosphere Research Satellite EQUARS e o Monitor e Imageador de Raios X MIRAX Por ser o sat lite em 99 est gio mais adiantado de projeto entre os dois o EQUARS foi selecionado como a aplica o alvo para o estudo da modelagem e an lise de cen rios do servi o de replanejamento embarcado O EQUARS Figura 5 1 um projeto de parceria com institui es de diversos pa ses Os experimentos a serem embarcados ser o provenientes de institui es do Brasil Estados Unidos Canad e Jap o O objetivo dos experimentos realizar o monit
62. ACE TECHNOLOGY CONFERENCE AND EXPOSITION 1999 Albuquerque NM USA Proceedings Albuquerque AIAA 1999 BIANCHO A C AQUINO A C FERREIRA M G V SILVA J D S CARDOSO L A multi agent ground operations automation architecture In INTERNATIONAL CONFERENCE ON SPACE OPERATIONS SPACEOPS 9 2006 Rome Italy Proceedings Rome ATAA 2006 BIUNDO S AYLETT R BEETZ M BORRAJO D CESTA A GRANT T MCCLUSKEY L MILANI A AND VERFAILLE G Ed Technological roadmap on Al planning and scheduling PLANET II The European Network of Excellence in Al Planning IST 2000 29656 2003 Dispon vel em lt http planet dfki de service Resources Roadmap Roadmap2 pdf gt BLANQUART P FLEURY S HERNEK M HONVAULT C INGRAND F PONCET J C POWELL D STRADY L CUBIN N TH VENOD FOSSE P Software safety supervision on board autonomous spacecraft In EUROPEAN CONGRESS ON EMBEDDED REAL TIME SOFTWARE ERTS 2 2004 Toulouse France Proceedings s n 2004 11p BLUM A FURST M Fast planning through planning graph analysis In INTERNATIONAL JOINT CONFERENCES ON ARTIFICIAL INTELLIGENCE IJCAI 95 1995 Montreal Canada Proceedings Montreal Morgan Kaufmann 1995 p 1636 1642 BONET B LOERINCS G GEFFNER H A robust and fast action selection mechanism for planning In NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AAAI 97 14 1997 Providence RI USA Proceedings Provid
63. As macros ocultam a cria o e a alimenta o das estruturas vetores fun es e outros elementos utilizados pelo planejador e fazem com que a descri o do dom nio seja mais leg vel e pr xima linguagens de planejamento como a AML A este conjunto de instru es foi dado o nome de RASSO modeling language ou apenas RASSO ml A Figura 6 2 traz exemplos simplificados de instru es ao planejador implementadas na RASSO ml atrav s de macros As instru es sublinhadas s o utilizadas na descri o do modelo enquanto que os trechos destacados nas caixas gerados a partir destas instru es ficam ocultos do modelador create class Experiment Exp Name name bool on int priority typedef struct s Experiment Exp Name name bool on int priority Experiment typedef struct s2 Experiment i int plan_id Experiment object timeline Experiment typedef struct s3 Experiment int morent Experiment object imposed Experiment int catalog Experiment create object Experiment IONEX object indexer object indexer IONEX timeline Experiment timeline IONEX X imposed Exper iment imposed states IONEX Y FIGURA 6 2 Exemplos de Instru es ao Planejador Implementadas por Macros J4 O modelo do dom nio editado junto ao c digo fonte do software Ele deve estar presente em um arquivo chamado model h que vinculado uma biblioteca RASSO ml na etapa de pr com
64. D UCPOP UFO 1 Programa de Sat lites Cient ficos e Experimentos Systematic Nonlinear Planning Science Planning Intelligent Knowledge Environment Science Planning and Scheduling System Stanford Research Institute Problem Solver Space Telescope Science Institute Grupo de Supervis o de Bordo Universal Conditional Partial Order Planner UHF Follow On One CAP TULO 1 INTRODU O O Instituto Nacional de Pesquisas Espaciais INPE vem desenvolvendo a tecnologia de sat lites h quase tr s d cadas desde a aprova o da Miss o Espacial Completa Brasileira INPE 1999 em 1979 Dividida em tr s grandes ramos a MECB previa o desenvolvimento de pequenos sat lites de aplica es de um ve culo lan ador compat vel com estes sat lites e a implanta o de toda a infra estrutura necess ria para estes projetos O processo de desenvolvimento tecnol gico ent o iniciado culminou no bem sucedido lan amento do primeiro sat lite brasileiro o Sat lite de Coleta de Dados SCD 1 em fevereiro de 1993 O xito alcan ado pelo SCD 1 e posteriormente pelo SCD 2 ambos tendo ultrapassado em muito a vida til estimada trouxe ao Brasil o reconhecimento de sua capacita o na rea espacial Visando aumentar esta capacita o com miss es mais complexas e de maior valor agregado o INPE iniciou um programa de parceria internacional com a Chinese Academy of Space Technology CAST para o desenvolvimento de sat lites avan ado
65. El E El HEI i Ele ji to estado inicial E we wo FIGURA 3 5 Busca Heuristica Aplicada ao Problema do Mundo de Blocos Fonte Silva 2003 p 40 Na Figura 3 5 o estado inicial definido como sobre C A sobre A mesa sobre B mesa enquanto que o estado objetivo sobre A B sobre B C sobre C mesa Os estados destacados s o aqueles que possuem o menor valor definido por uma fun o heur stica h s em cada passo do processo de planejamento ou seja aqueles que aparentemente est o mais pr ximos do objetivo 53 Os planejadores aqui apresentados deram origem a diversos novos sistemas implementando varia es ou combina es das abordagens descritas neste Cap tulo Cabe aqui destacar algumas outras reas de pesquisa em planejamento como o planejamento probabil stico Erol et al 1995 t cnicas baseadas em Redes de Petri Silva et al 2000 e programa o por restri o Beek e Chen 1999 3 3 Formas de Representa o do Conhecimento Usadas em Planejamento Biundo et al 2003 define Engenharia do Conhecimento em planejamento como o processo que envolve e A aquisi o valida o e verifica o do conhecimento sobre o dom nio bem como a manuten o de modelos de dom nios para planejamento e A sele o de ferramentas de planejamento apropriadas e sua integra o ao modelo do dom nio para compor uma aplica o de planejamento O mod
66. FIGURA 3 9 Algoritmo para a Solu o de CSPs por Busca Construtiva Fonte adaptada de Smith et al 2000 p 14 62 Este procedimento cont m um conjunto de t cnicas cuja implementa o tem enorme impacto no desempenho S o elas Ordena o de vari veis a sele o de qual deve ser a pr xima vari vel a selecionar para a atribui o de valores e Ordena o de valores a sele o da pr xima atribui o de valor a testar para uma determinada vari vel e Estrat gia de propaga o a propaga o o mecanismo de esbo ar conclus es a partir de novas atribui es de valores a vari veis Estrat gias de propaga o podem variar de simples regras de verifica o de consist ncia at estrat gias poderosas mas custosas em termos computacionais de infer ncia do novo n mero de restri es entre as vari veis restantes e Estrat gia de backtracking backtracking o ato de voltar um ou mais passos em um plano em constru o para tomar um novo caminho na busca pela solu o Isso geralmente ocorre quando o planejador encontra um ponto a partir do qual n o h mais op es de a o a escolher ou simplesmente quando as ltimas a es selecionadas n o o levaram a um estado mais pr ximo do estado objetivo 3 5 2 Busca Local A busca local come a com todas as vari veis do CSP inicializadas com algum valor sem considerar as restri es impostas ao problema ou seja alguns dos valores a
67. L 1999 San Diego CA USA Proceedings s n 1999 155 PAVLOVIC V GARG A KASIF S Where we were and where to next Summary of the workshop on machine learning technologies for autonomous space applications Washington D C USA August 2003 20th International Conference on Machine Learning ICML 2003 PEDERSEN L SMITH D DEANS M SARGENT R KUNZ C LEES D RAJAGOPALAN S Mission planning and target tracking for autonomous instrument placement In IEEE AEROSPACE CONFERENCE 2005 Big Sky MT USA Proceedings Big Sky IEEE 2005 PEDNAULT E ADL exploring the middle ground between STRIPS and the situation calculus In INTERNATIONAL CONFERENCE ON PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING KR 89 1 1989 Toronto Canada Proceedings San Francisco Morgan Kaufmann Publishers Inc 1989 pp 324 332 PENBERTHY J S WELD D S UCPOP A sound complete partial order planner for ADL In INTERNATIONAL CONFERENCE ON PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING KR 92 3 1992 Cambridge MA USA Proceedings San Francisco Morgan Kaufmann Publishers Inc 1992 RABIDEAU G CHIEN S MANN T WILLIS J SIEWERT S STONE P Interactive repair based planning and scheduling for shuttle payload operations In IEEE AEROSPACE CONFERENCE 1997 Aspen CO USA Proceedings Aspen IEEE 1997 RABIDEAU G KNIGHT R CHIEN S FUKUNAGA A GOVINDJEE A Iterative repair pla
68. LO eee KKK create domain Exp Name certo create domain Mode full grom ionex mltm tip partial CRIACAO DAS CLASSES DE OBJETOS DO MODELO kkk kkk kd kt create class Antenna bool on Iy create_class Experiment Exp_Name bool Mode int int int name on mode sample rate precision priority CRIACAO DOS OBJETOS E RECURSOS DO MODELO kkk kkk kd kt create object CERTO Experiment create object GROM Experiment create object IONEX Experiment create object MLTM Experiment create object TIP Experiment create object create resource Power create resource Mass Memory resource is consumed by Power resource is consumed by Power resource is consumed by Power resource is consumed by Power resource is consumed by Power resource is consumed by Power Comm System Antenna CERTO GROM IONEX MLTM TIP Comm System CERTO resource is consumed by Mass Memory resource is consumed by Mass Memory resource is consumed by Mass Memory resource is consumed by Mass Memory resource is consumed by Mass Memory GROM IONEX MLTM TL 159 DEFINICAO DAS ACOES DO MODELO KA Ak A A AAA ARA Turn On nao eh aplicavel apenas ao experimento IONEX RASSO_Action Turn_On action_parameters parameter exp when planning condition get current state
69. M Zweben ed Morgan Kaufman pp 391 422 1994 JONSSON A MORRIS P MUSCETTOLA N RAJAN K Planning in interplanetary space theory and practice In 2000 INTERNATIONAL CONFERENCE ON AI PLANNING AND SCHEDULING AIPS 2000 Breckenridge CO USA Proceedings s n 2000 pp 177 186 KAUTZ H SELMAN B Planning as satisfiability In EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE ECAI92 10 1992 Vienna Austria Proceedings Chichester John Wiley and Sons 1992 pp 359 363 KAUTZ H SELMAN B BLACKBOX a new approach to the application of theorem proving to problem solving In 1998 INTERNATIONAL CONFERENCE ON AI PLANNING AND SCHEDULING AIPS 4 1998 Pittsburgh USA Proceedings s n 1998 pp 58 60 KAUTZ H Deconstructing planning as satisfiability In NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AAAI 06 21 2006 Boston MA USA Proceedings Boston AAAI Press 2006 KUCINSKIS F N FERREIRA M G V Dynamic allocation of resources to improve scientific return with onboard automated planning In INTERNATIONAL CONFERENCE ON SPACE OPERATIONS SPACEOPS 9 2006 Rome Italy Proceedings Rome AIAA 2006 154 KUCINSKIS F N FERREIRA M G V ARIAS R Increasing the autonomy of scientific satellites to deal with short duration phenomena In IEEE AEROSPACE CONFERENCE 2007 Big Sky MT USA Proceedings Big Sky IEEE 2007 LIU D MCCLUSKEY T L The OCL langu
70. MINIST RIO DA CI NCIA TECNOLOGIA INSTITUTO NACIONAL DE PESQUISAS ESPACIAIS E INPE 14798 TDI 1241 ALOCA O DIN MICA DE RECURSOS COMPUTACIONAIS PARA EXPERIMENTOS CIENT FICOS COM REPLANEJAMENTO AUTOMATIZADO A BORDO DE SAT LITES Fabr cio de Novaes Kucinskis Disserta o de Mestrado do Curso de P s Gradua o em Computa o Aplicada orientada pelo Dr Maur cio Gon alves Vieira Ferreira aprovada em 30 de mar o de 2007 INPE S o Jos dos Campos 2007 Publicado por esta p gina responsabilidade do SID Instituto Nacional de Pesquisas Espaciais INPE Gabinete do Diretor GB Servi o de Informa o e Documenta o SID Caixa Postal 515 CEP 12 245 970 S o Jos dos Campos SP Brasil Tel 012 3945 6911 Fax 012 3945 6919 E mail pubtc sid inpe br Solicita se interc mbio We ask for exchange Publica o Externa permitida sua reprodu o para interessados MINIST RIO DA CI NCIA TECNOLOGIA INSTITUTO NACIONAL DE PESQUISAS ESPACIAIS E INPE 14798 TDI 1241 ALOCA O DIN MICA DE RECURSOS COMPUTACIONAIS PARA EXPERIMENTOS CIENT FICOS COM REPLANEJAMENTO AUTOMATIZADO A BORDO DE SAT LITES Fabr cio de Novaes Kucinskis Disserta o de Mestrado do Curso de P s Gradua o em Computa o Aplicada orientada pelo Dr Maur cio Gon alves Vieira Ferreira aprovada em 30 de mar o de 2007 INPE S o Jos dos Campos 2007 681 3 019 Kucinskis F
71. O CLARATy um dos sistemas citados no Cap tulo 4 deste trabalho se prop e a realizar isso Maiores informa es s o encontradas em Bresina et al 2002 O prot tipo do RASSO tamb m traz muitas possibilidades de melhorias em trabalhos futuros A aplica o de heur sticas espec ficas para o dom nio pode melhorar consideravelmente o desempenho do sistema A linguagem RASSO ml tamb m possui diversas melhorias poss veis Outra possibilidade o desenvolvimento de ferramentas de software a serem utilizadas em solo pelos operadores da miss o para auxiliar na an lise dos planos modificados em bordo e transmitidos pelo sat lite 143 Finalmente uma migra o do RASSO para C possibilitaria o uso de objetos ao inv s de structs na modelagem do dom nio Isso permitiria o uso real de Orienta o a Objetos na linguagem de representa o do conhecimento Apesar da aplica o escolhida para este trabalho ter sido a resposta detec o de fen menos de curta dura o em sat lites cient ficos h um grande n mero de outras aplica es para as t cnicas aqui implementadas Entre elas destacam se duas de especial interesse para o INPE e O uso de replanejamento em sat lites de sensoriamento remoto Um sat lite capaz de efetuar replanejamento embarcado pode em tempo real modificar seu plano para obter mais e melhores imagens de uma queimada detectada na Amaz nia por exemplo e A descoberta de novas formas de o
72. OCL Uma Representa o Centrada em Objetos Proposta por Liu e McCluskey 2000 e implementada em PROLOG a Object Centered Language OCL parte da id ia de se representar modelos de dom nios como um conjunto de objetos sujeitos v rias restri es A id ia de representa o baseada em objetos est claramente alinhada com uma abordagem baseada em modelos Entretanto a OCL e sua vers o hier rquica OCLh s o totalmente sentenciais elas ainda descrevem o modelo como um conjunto de predicados basicamente os agrupando e chamando estes grupos de objetos Um modelo em OCL composto por objetos din micos ou est ticos agrupados em sorts Isso o que se chama em Orienta o a Objetos OO de classes ou na PDDL de types Cada objeto din mico existe em um de seus conjuntos de estados chamados substates caracterizados por predicados A aplica o de um operador ir mover os objetos de um conjunto de estados para outro A OCLh adiciona a estes conceitos o relacionamento hier rquico entre sorts permitindo criar objetos a partir da composi o de outros como ocorre em OO A Figura 3 8 traz um trecho de uma descri o do dom nio do mundo de blocos em OCL sortsCprimitive sorts bloco objectsQ hioco blocol blocoz bloco3 bloco4 blocos bloco amp blocor predicates sobre blocolbloco bloco sobre mesatblocoi o ivrechlocos substate classes bloco B sobre_bloco B El b
73. Off mltm RASSO Behavior When Night behavior parameters at_start garante 5 4Watts p IONEX modo full nos primeiros 12 m da janela guarantee resource IONEX Power 5 4 0 0 12 60 call_action Turn_On certo at_end call_action Turn_Off certo RASSO Behavior When_Communicating behavior parameters at_start taxa de transferencia para solo 230 kbits s set current state Comm System on true liga a antena libera 13 8 Mbits por minuto da memoria de massa generate resource Mass Memory 13800 per min o sistema de comunicacao consome 10W consume resource Comm System Power 10 at_end para de liberar memoria e de consumir energia generate resource Mass Memory 0 consume resource Comm System Power 0 164 INICIALIZACAO DO MOD void Initialize Model Inicializa o con tialize class tialize class An ini ini ini ini set_current_state Comm_ System on false desliga a antena tialize object GROM tialize object MLTM Experime Experime ELO FA AAA AA trole de classes Experiment tenna nt nt a bateria pode fornecer 50W quando plena ini ini ini ini ini beh beh beh beh avior occurs tialize resource Power at time tialize time window Day tialize time window Night tialize time window Communica window avior occurs at time win
74. Os par metros das a es seus tipos e valores poss veis s o informados ao planejador em uma rotina parte onde estruturas de controle das a es s o inicializadas Cada a o possui dois blocos de execu o when planning e when running O primeiro chamado durante o processo de planejamento ao aplicar a a o sobre o modelo de dom nio O segundo bloco deve conter o c digo que implementa a a o no software regular do sat lite Assim planejamento e execu o ficam descritos em um nico local 114 possibilitando uma maior integra o entre o software normal e o planejador Dentro do bloco when planning s o descritas as pr condi es necess rias execu o da a o instru es condition e quais efeitos a a o ter sobre o modelo set current state by id e consume resource by id caso todas as pr condi es sejam verdadeiras 6 2 2 2 As Janelas de Tempo e os Comportamentos As a es permitem descrever os efeitos da execu o de comandos de software sobre o estado do sat lite Entretanto nem todas as altera es no estado ocorrem em fun o de comandos Alguns dos experimentos do EQUARS t m seu funcionamento vinculado incid ncia solar ou falta dela O experimento TIP por exemplo faz observa es de rel mpagos e sprites enquanto se encontra em eclipse de noite durante uma rbita o que n o poss vel quando o sat lite est iluminado de dia Estes ex
75. Pr publica es PRE Todos os artigos publicados em peri dicos anais e como cap tulos de livros Manuais T cnicos MAN S o publica es de car ter t cnico que incluem normas procedimentos instru es e orienta es Relat rios de Pesquisa RPQ Reportam resultados ou progressos de pesquisas tanto de natureza t cnica quanto cient fica cujo n vel seja compat vel com o de uma publica o em peri dico nacional ou internacional Publica es Did ticas PUD Incluem apostilas notas de aula e manuais did ticos Programas de Computador PDC S o a sequ ncia de instru es ou c digos expressos em uma linguagem de programa o compilada ou inter pretada a ser executada por um computador para alcan ar um determi nado objetivo S o aceitos tanto programas fonte quanto execut veis
76. SE ici 92 4 4 Sum rio dos Planejadores com IA Aplicados a Miss es Espaciais 93 5 1 0 Sat lite Cient fico EQUA RS rainei e a a ndice 100 5 2 A Arquitetura do RASSO c0ooooccooocccccconcnncnononnonoonnnnonononnnncnnonnnncnnnn nro cnn nn noncnnnnnnnns 102 6 1 Estrutura de um Modelo no RASSO coccconooccccooconooncnconononnnnonnnnnronnncnonn conan nnrannc nn 110 6 2 Exemplos de Instru es ao Planejador Implementadas por Macros 111 6 3 Cria o de Dominios Classes Objetos e Recursos em RASSO ml 113 6 4 Uma A o em RASSO Ml ooo ccecccceeseseeceeesseeecesseceeeceseeeeeseeseesesseseeeeeeeaeees 114 6 5 Exemplos de Comportamentos em RASSO ml erre 116 6 6 Exemplo de um timeline no RASSO uuu eeecccccecesssceceeseceeeceeceeeceseeesesseseeeeseseaeees 118 6 7 Exemplo de Perfil de Consumo de Recurso ccooooocccconocncnconnncnnnnoncnnnnonnnncninncnnoss 119 6 8 Consolida o de Dados para a Composi o do Problema 121 6 9 Horizontes de Planejamento e Objetivos cccoooocccnnonccncononnnncnononncnnnnnnnnnononnnnnns 122 6 10 O Algoritmo de Planejamento 0 0 eee ceceeseeceeesseeceeseceeecesseeeeseseeseeseeeeeeeeeeees 125 7 1 Comandos Iniciais e Janelas de Tempo Definidos para o Cen rio 134 7 2 Consumo de Energia e Mem ria em Modo Normal e em Sobrecarga 135 7 3 O Plano de Opera es Modificado
77. a es corrente da espa onave A seguir as modifica es solicitadas para atingir os novos objetivos s o aplicadas inserindo conflitos neste esbo o devido viola o das restri es impostas de tempo e recursos Aplicam se algoritmos de busca local chamados em alguns casos de algoritmos de reparo iterativo para corrigir o plano e satisfazer as restri es violadas uma a uma Este processo geralmente incrementado com o uso de heur sticas espec ficas para o dom nio e de t cnicas para escapar de m nimos locais e plat s definidos no item 3 5 2 deste trabalho no espa o de busca A op o dos desenvolvedores de sistemas planejadores espaciais por esta solu o torna se clara quando se analisa as outras alternativas Tanto algoritmos baseados em satisfatibilidade quanto aqueles baseados em grafos dependem de uma etapa de pr processamento onde o espa o de busca reduzido Nesta etapa todas as vari veis do modelo s o inicializadas e t m seus valores avaliados em cada momento do tempo ap s a aplica o de cada a o poss vel Isso demanda uma grande quantidade de mem ria que um recurso bastante limitado em sistemas embarcados Al m disso n o h implementa es de algoritmos de satisfatibilidade ou grafos que gerenciem recursos de forma t o completa quanto os planejadores da rea espacial desenvolvidos na ltima d cada embora seus autores argumentem que isso seja poss vel Kautz 2006
78. a Olga que me deu todo o suporte que precisei e muitas vezes mais do que mereci antes e durante a realiza o deste trabalho Tamb m minha m e M riam por compreender a aus ncia dos ltimos meses e por ter criado este seu filho atrav s de bons ensinamentos e de um grande exemplo de vida RESUMO Os experimentos a bordo dos sat lites cient ficos do INPE s o atualmente pensados para executar suas tarefas de forma repetitiva coletando armazenando e enviando dados em um ciclo que n o sofre grandes altera es Esta forma de lidar com a opera o de experimentos perfeitamente adequada para a observa o cient fica de longo prazo Existem entretanto fen menos cient ficos de curta dura o cuja ocorr ncia embora previs vel aleat ria Para analisar melhor estes fen menos pode ser importante aumentar a taxa de aquisi o ou a precis o dos dados coletados Isso aumenta o consumo de recursos como mem ria e energia para al m do originalmente previsto Devido curta dura o e dificuldade em precisar quando um fen meno deste tipo ir ocorrer n o suficiente deixar a cargo da equipe de opera es em solo a reconfigura o do sat lite O tempo necess rio para que o fen meno seja relatado e para que a equipe de opera es crie e envie um novo plano ao sat lite em geral muito maior que a dura o do fen meno Surge ent o a necessidade de se permitir que os experimentos ao detectarem a ocorr ncia de
79. ada no Cap tulo 3 Foram ent o estudados sistemas planejadores que aplicam IA utilizados em miss es espaciais Foram analisados tanto sistemas planejadores executados em solo quanto planejadores embarcados em espa onaves O Cap tulo 4 descreve brevemente estes sistemas com suas principais caracter sticas miss es em que foram aplicados seus objetivos e resultados obtidos O pr ximo passo foi analisar a estrutura dos softwares embarcados em sat lites do INPE e determinar onde um sistema de replanejamento se encaixaria e como se comunicaria com o restante do software embarcado Isso aliado a uma an lise da arquitetura dos poucos sistemas planejadores embarcados existentes permitiu a defini o de uma arquitetura para replanejamento dos sat lites do INPE Esta arquitetura e os conceitos relacionados a ela s o apresentados no Cap tulo 5 Com uma arquitetura definida passou se implementa o de um prot tipo que envolveu tamb m o desenvolvimento de uma linguagem de representa o do conhecimento pr pria para o dom nio de sat lites e de um sistema planejador espec fico O Cap tulo 6 detalha a etapa de implementa o 30 Para validar o prot tipo foi criado um cen rio de testes composto por um modelo do sat lite planos de opera o e previs es de passagens para algumas rbitas que simula a opera o de um sat lite cient fico e dispara o processo de replanejamento embarcado Este cen rio e os resultad
80. age manual version 1 2 Huddersfield UK 2000 Technical Report Department of Computing and Mathematical Sciences University of Huddersfield MCALLESTER D ROSENBLITT D Systematic nonlinear planning In NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AAAI 91 9 1991 Anaheim CA USA Proceedings Anaheim AAAI Press 1991 pp 634 639 MCDERMOTT D PDDL the planning domain definition language Yale CT USA 1998 Technical Report CVC TR 98 003 DCS Yale Center for Computational Vision and Control MINTON S KNOBLOCK C KUOKKA D GIL Y JOSEPH R CARBONELL J Prodigy 2 0 the manual and tutorial Pittsburg PA USA 1989 Technical Report CMU CS 89 146 University of Carnegie Mellon MUSCETTOLA N PELL B HANSSON O MOHAN S Automating mission scheduling for space based observatories In Robotic Telescopes Current Capabilities Present Developments and Future Prospects for Automated Astronomy G W Henry and J A Eaton eds Astronomical Society of the Pacific Provo UT USA 1995 MUSCETTOLA N DORAIS G A FRY C LEVINSON R PLAUNT C IDEA planning at the core of autonomous reactive agents In 2002 INTERNATIONAL CONFERENCE ON AI PLANNING AND SCHEDULING AIPS 6 2002 Toulouse France Proceedings s n 2002 pp 58 60 MYERS K L SMITH S F Issues in the integration of planning and scheduling for enterprise control In DARPA JFACC SYMPOSIUM ON ADVANCES IN ENTERPRISE CONTRO
81. and mica e tabu s o novamente executados De acordo com Cesta et al 2006 o uso do MEXAR2 trouxe um aumento de cerca de 50 na quantidade de dados cient ficos obtidos da Mars Express A abordagem de desenvolvimento do MEXAR e MEXAR2 foi focada especificamente para a solu o do problema da Mars Express fazendo com que este planejador n o seja facilmente aplic vel a outras miss es Devido a isso a equipe do PST est atualmente desenvolvendo um planejador de uso geral chamado Open Multi CSP Planner and Scheduler OMPS Fratini e Cesta 2006 Embora n o seja voltado especificamente para miss es espaciais os autores pretendem aplicar o OMPS a problemas desta rea e sua experi ncia pr via com o MEXAR os qualifica para isso O OMPS baseado em restri es e traz conceitos de modelagem e algoritmos de busca bastante semelhantes aos do ASPEN 4 2 6 Estudos em Planejamento Automatizado Realizados no INPE Existem poucos trabalhos publicados a respeito de t cnicas de planejamento em IA na rea espacial fora do eixo NASA ESA No INPE estudos iniciados recentemente buscam o desenvolvimento de ferramentas capazes de automatizar as tarefas de controle em solo de seus sat lites A arquitetura Multi Agent Ground operation Automation MAGA Biancho et al 2006 tem como objetivo gerenciar a aloca o dos recursos em solo para o rastreio e controle da opera o de m ltiplos sat lites por uma mesma esta o terrena d
82. ao n vel inferior caso contr rio ele dever gerar um plano alternativo no n vel atual importante notar que neste caso o escalonador deve ser capaz de efetuar estimativas de tempo e consumo de recursos em diferentes n veis de abstra o 3 6 3 Planejamento Guiado por Restri es de Escalonamento Esta a abordagem onde maior a integra o entre planejamento e escalonamento Aqui as decis es do planejador sobre quais a es ser o selecionadas para o plano s o guiadas n o apenas pelas pr condi es das a es mas tamb m pelas considera es sobre consumo de recursos e tempo provenientes do escalonador Torna se muito mais dif cil distinguir o planejador do escalonador e passa a ser mais importante a utiliza o de uma representa o nica do conhecimento do dominio para o planejador e o escalonador Com rela o a isso a PDDL apresentou at o momento poucos avan os Sua vers o 2 1 trouxe uma representa o temporal ainda limitada atrav s do conceito de a es com dura o Nelas pode se especificar um tempo de dura o e efeitos ocorridos ao in cio ou ao t rmino da a o Nada h na PDDL com rela o ao gerenciamento de recursos De fato poucas linguagens utilizadas em planejamento permitem a descri o de tempo e de consumo de recursos e isso pode ser em parte um efeito adverso do sucesso da IPC e da PDDL se por um lado elas trouxeram uma padroniza o na representa o do conheci
83. by id Experiment exp on false ionex nao pode ser ligado apenas seu modo de operacao alterado condition get current state by id force state if needed by id Experiment efeitos descritos a partir daqui set current state by id Experiment exp on switch get current state by id Experiment case certo consume resource by id Experiment consume resource by id Experiment break case grom consume resource by id Experiment consume resource by id Experiment break case mltm consume resource by id Experiment consume resource by id Experiment break case tip consume resource by id Experiment consume resource by id Experiment break default break when running action_success printf Turn On experiment Si n exp 160 Experiment exp exp name on false true exp name exp exp exp exp exp exp exp exp Power 3 6 Mass Memory Power 12 Mass Memory Power 14 Mass Memory Power 7 Mass Memory apenas para evitar warning l ionex 420 98 per min i ie th T2 per min 264 54 per min 568 89 per min Turn Off nao eh aplicavel apenas ao experimento IONEX RASSO Action Turn Off action parameters parameter exp when planning condition get current state by id Experiment exp on true
84. comportamentos e as instru es ao planejador que cada um pode conter 6 2 2 1 As A es Uma a o RASSO Action em RASSO ml corresponde a um ou mais comandos internos do sat lite presentes na fila de telecomandos temporizados e descreve como o modelo afetado por sua execu o A Figura 6 4 traz um exemplo de uma a o que liga Turn On um experimento passado a ela por par metro A estrutura da a o e suas instru es s o detalhadas a seguir 113 RASSO Action Turn On action parameters parameter exp when planning pre condicoes para a acao instrucao ao planejador efeitos descritos a partir daqui case grom consume_resource_by_id Experiment consume_resource_by_id Experiment break case mltm i consume_resource_by_id Experiment consume_resource_by_id Experiment break when_running printf Turn On experiment n action_success set current state by id Experiment exp on switch get current state by id Experiment exp exp exp exp condition get current state by id Experiment exp on false force state 1f needed by id Experiment exp on false true exp name Power 12 Mass Memory 100 per min Power 14 Mass Memory 264 per min FIGURA 6 4 Uma A o em RASSO ml A a o Turn On recebe como par metro um objeto do tipo Experiment representado pela vari vel exp
85. cu o 49 3 2 4 Planejamento Baseado em Grafos Os planejadores baseados em STRIPS constitu ram o tipo de sistema de planejamento mais comum at o come o da d cada de 1990 Mas na primeira edi o do IPC em 1998 dos cinco planejadores concorrentes tr s adotavam um novo tipo de planejamento apresentado tr s anos antes o planejamento baseado em grafos Este tipo de planejamento foi proposto por Blum e Furst 1995 e implementado em um sistema batizado de GRAPHPLAN O GRAPHPLAN possui duas etapas para a gera o de planos a primeira consiste da gera o de um grafo de planejamento com representa es das a es e estados A segunda de um algoritmo simples de busca exaustiva no grafo gerado O que o torna especial justamente a cria o do grafo que reduz consideravelmente o espa o de busca para o algoritmo O grafo de planejamento constitu do por n veis cada um representando um instante no tempo e possui dois tipos de n s os que representam estados e os que representam a es Os n s que representam os estados encontram se nos n veis pares do grafo O conjunto de n s de um mesmo n vel par representa o conhecimento do mundo em determinado instante O primeiro n vel do grafo o n vel zero representa o estado inicial do dom nio e o ltimo n o estado objetivo Nos n veis impares est o representadas as a es cujas pr condi es em termos de estados est o presentes no n vel imediata
86. cursos por objetos Um conflito de estados inconsistentes diz respeito a estados impostos ao planejador nos horizontes hl h2 e h3 Quando a execu o das a es em um plano e dos comportamentos n o leva aos estados impostos nestes momentos h um conflito a resolver Os conflitos de estados s o verificados pela compara o simples entre os estados atingidos pela execu o do plano at o momento com aqueles que s o esperados impostos para este momento Um conflito de viola o em uma restri o de consumo total de recurso diz respeito ao uso excessivo do recurso pela soma dos objetos consumindo al m de sua quantidade dispon vel m xima O ltimo tipo de conflito o de viola o em uma restri o de consumo de recurso por um objeto ocorre quando algum objeto consome uma quantidade de recurso fora das faixas impostas seja pela solicita o por recursos do experimento ou pelas instru es guarantee resource Os conflitos de consumo de recursos s o verificados de duas formas diferentes de acordo com o tipo de recurso Recursos do tipo reservavel s o verificados apenas somando todos os consumos por todos os objetos no momento chave Recursos do tipo consumivel s o tratados de forma diferente devido abordagem da RASSO ml para a modelagem de seu consumo O c lculo da quantidade de recursos consumidos feito multiplicando se cada taxa de consumo pelo tempo decorrido desde que a taxa foi defini
87. da por exemplo no momento da execu o de uma a o Turn On 127 A partir da os consumos s o somados e verificados da mesma forma que ocorre com OS recursos reserv veis Um conflito no consumo de um recurso consum vel detectado em um momento chave n o necessariamente surgiu naquele momento Como o consumo informado em termos de taxas o estouro na quantidade consumida pode ter ocorrido em qualquer instante entre o momento chave atual e o momento chave imediatamente anterior a ele E necess rio ent o determinar o momento exato do estouro do consumo Para isso aplicado um algoritmo baseado em busca bin ria ao per odo entre os dois momentos chave o anterior quando ainda n o havia conflito e o atual quando o conflito foi detectado O instante exato do estouro do consumo importante para que o planejador possa deslocar temporalmente de forma mais eficaz as a es no esbo o do plano Sabendo quais conflitos ocorrem seus tipos e em que instantes o algoritmo identifica quais a es contribuem para o conflito Para conflitos de estados os contribuintes s o todas as a es que modificam aquele estado antes do momento chave que est sendo verificado Para conflitos de recursos os contribuintes s o todas as a es que modificam o perfil de consumo do recurso antes do momento chave 6 4 3 O Teste e a Aplica o de Mudan as no Esbo o de Plano O pr ximo passo do algoritmo de planejamento tentar mo
88. de recursos que ao trabalhar com atividades caso o planejador precise modificar a execu o de Experimento Operando para alocar 20 Mb de mem ria para outra atividade suas nicas op es ser o deslocar a atividade temporalmente ou simplesmente remov la do plano Na abordagem da RASSO ml onde uma a o n o possui dura o mas seus efeitos sim o planejador poderia manter inalterada a a o Ligar Experimento e adiantar a execu o de Desligar Experimento em dez minutos garantindo a mem ria necess ria Isso maximiza o tempo de opera o do experimento sem deixar de garantir os recursos necess rios para outro Esta abordagem tamb m mais pr xima forma de opera o real do sat lite do que as demais 6 3 O Compositor de Problemas Cada experimento que puder detectar fen menos de curta dura o dever possuir pelo menos uma Condi o de Disparo em seu software que quando verdadeira ir enviar uma solicita o por mais recursos ao RASSO Esta solicita o deve informar e Quais recursos o experimento precisa e As quantidades necess rias de cada recurso e A partir de que momento os recursos devem estar dispon veis 120 e Por quanto tempo os recursos alocados devem ser mantidos A solicita o por recursos ser recebida pelo Compositor de Problemas que respons vel por reunir informa es de diversas fontes e fornecer ao Planejador um problema a ser resolvido conforme
89. de a es sobre determinado ambiente e a avalia o do efeito destas a es sobre o mesmo de forma que possa ser encontrado um conjunto de a es um plano que leve o ambiente de um estado inicial a um estado desejado ou estado objetivo O Escalonamento diz respeito atribui o de tempo e recursos para cada a o de forma a satisfazer restri es impostas pelo ambiente Estes conceitos ser o descritos em maiores detalhes no pr ximo Cap tulo Mas apesar de seu poder a implementa o de replanejamento embarcado em sat lites encontra dois grandes obst culos a capacidade de processamento limitada dos computadores de bordo e a resist ncia de gerentes de miss o e engenheiros com rela o ao aumento da autonomia Esta resist ncia natural e at mesmo justificada uma vez que o custo e o volume de trabalho de uma miss o espacial s o em geral considerados muito grandes para confiar ao sat lite a tomada de mais decis es do que as de rotina como a corre o de atitude e rbita 27 O desafio reside em permitir o aumento da autonomia sem entretanto reduzir a confian a no comportamento do sat lite e em adequar a aplica o de Planejamento e Escalonamento ao poder de processamento dispon vel no computador de bordo 1 1 Motiva o do Trabalho de Pesquisa Ao longo dos anos vem aumentando a necessidade de que os sistemas espaciais dependam cada vez menos da interven o de operadores em solo e tornem se mais au
90. de satisfatibilidade na busca pela solu o do problema O BLACKBOX entrou na competi o IPC de 1998 e seu desempenho foi compar vel dos melhores competidores quase todos baseados no GRAPHPLAN Entretanto na edi o de 2000 da IPC seu desempenho foi muito abaixo do esperado Em 2002 n o havia nenhuma vers o competindo e em 2004 uma nova vers o do sistema chamado SATPLANOS foi considerado o melhor planejador na soma dos resultados A varia o de desempenho de uma competi o para outra foi atribu da s caracter sticas da solu o SAT em rela o s caracter sticas dos problemas apresentados nas diferentes edi es da competi o Uma an lise detalhada dos motivos desta varia o encontra se descrita em Kautz 2006 52 3 2 6 Planejamento Baseado em Heur sticas de Busca Bonet et al 1997 foram os primeiros a propor o uso de heuristicas de busca na gera o de planos A proposta consiste em realizar uma busca progressiva a partir do estado inicial ao estado objetivo utilizando uma fun o heur stica que estima a dist ncia custo em passos do estado atual intermedi rio ao estado objetivo A proposta foi implementada no planejador HSP de Heuristic Search Planner Bonet e Geffner 1998 que participou da primeira IPC com bons resultados A Figura 3 5 mostra um exemplo de planejamento com busca heur stica para o problema do mundo dos blocos E E Ele EE EE a i
91. de um plano possui uma linha principal a ser seguida e um conjunto de ramifica es poss veis para lidar com situa es de conting ncia Outro sistema em desenvolvimento que tem a MSL como objetivo o ENSEMBLE Bresina e Morris 2006 O ENSEMBLE a pr xima vers o do MAPGEN basicamente atualizando as ferramentas utilizadas e integrando as melhor O motor de planejamento utilizado passa a ser o EUROPA II e o ambiente de desenvolvimento de software Eclipse aplicado para melhorar a integra o gr fica entre os m dulos 85 Al m da NASA a ESA tamb m colabora no esfor o cient fico para aumentar o conhecimento sobre Marte Sua primeira miss o para l a sonda orbitadora Mars Express chegou ao planeta em 2004 Durante os primeiros seis meses de atividade da espa onave seus operadores encontraram um grave problema relacionado ao envio dos dados armazenados de carga til que em determinados per odos eram gerados em volume maior do que as janelas de visibilidade com a Terra permitiam transmitir o que acarretava a perda de dados cient ficos O problema estava sendo tratado manualmente atrav s da gera o de planos de opera o que lidavam com cada janela de visibilidade de forma diferente o que demandava enorme esfor o dos especialistas da miss o Para resolver este problema foi contatado o grupo Planning and Scheduling Team PST do Italian National Research Council Conselho Nacional de Pesquisas Italiano
92. descreve os efeitos sobre o modelo da ocorr ncia de um evento ex geno definido no item 3 3 3 deste trabalho A ocorr ncia dos eventos ex genos por sua vez representada por janelas de tempo A Figura 6 1 ilustra a estrutura de uma base de conhecimento no RASSO Modelo no RASSO Descri o Est tica Descri o Din mica e Classes e A es e Objetos e Comportamentos e Recursos e Janelas de Tempo FIGURA 6 1 Estrutura de um Modelo no RASSO Os pr ximos itens descrevem a forma de implementa o da linguagem de representa o do conhecimento no RASSO e detalha as descri es est tica e din mica de um modelo 6 2 A Linguagem de Representa o do Conhecimento O COMAY est sendo desenvolvido na linguagem C com o compilador GNU Cross Compiler GCC e seguindo a proposta apresentada no Cap tulo anterior esta a linguagem usada para a modelagem do EQUARS no RASSO As instru es ao planejador que fazem parte do modelo foram criadas de forma a permitir uma forte integra o entre a programa o do sistema e o processo de planejamento tornando a liga o entre o modelo o planejador e o restante do software mais natural Estas instru es foram implementadas atrav s de macros do C Neste trabalho o termo comando reservado para os comandos internos do sat lite enquanto que instru o se refere s instru es ao planejador que descrevem as caracter sticas do modelo 110
93. dificar o plano de forma a resolver os conflitos identificados em determinado momento chave Para cada conflito testado um conjunto de altera es no plano que possam resolv lo S o testadas modifica es para cada uma das a es que contribuem para o conflito Estas modifica es podem ser e Mover temporalmente no plano a a o que contribui para o conflito Esta a principal modifica o testada pois a que provavelmente ir gerar menor impacto no plano 128 e Adicionar outra a o no plano em um momento aleat rio antes da a o que contribui para o conflito e Excluir do plano a a o que contribui para o conflito Cada uma das modifica es testadas avaliada A modifica o considerada a melhor ent o aplicada ao esbo o de plano A melhor modifica o aquela que resolve o conflito que est sendo tratado e insere o menor n mero poss vel de conflitos no plano o ideal n o inserir novos conflitos Outros crit rios s o utilizados para desempate na sele o de modifica es como o tipo de conflitos adicionados e suas dura es Caso n o seja encontrada nenhuma mudan a no plano que resolva determinado conflito uma perturba o inserida no plano A perturba o consiste da adi o de uma a o que resolva o conflito se houver tal a o mas cujos pr requisitos n o sejam verdadeiros no momento em que ela foi inserida A falta dos pr requisitos da a o adicio
94. dow avior occurs at time window avior occurs at time W W W W window resource is consumed by Power G resource is consumed by Power MLTM reservable 0 50 120 Mbits dedicados aos experimentos tialize resource Mass Memory depletable 0 120 1024 ting hen Day Day hen Night Night hen Communicating Day hen Communicating Night ROM resource is consumed by Mass Memory GROM resource is consumed by Mass Memory MLTM 165 PUBLICA ES T CNICO CIENT FICAS EDITADAS PELO INPE Teses e Disserta es TDI Teses e Disserta es apresentadas nos Cursos de P s Gradua o do INPE Notas T cnico Cient ficas NTC Incluem resultados preliminares de pesquisa descri o de equipamentos descri o e ou documenta o de programa de computador descri o de sistemas e experimentos apresenta o de testes dados atlas e docu menta o de projetos de engenharia Propostas e Relat rios de Projetos PRP S o propostas de projetos t cnico cient ficos e relat rios de acompanha mento de projetos atividades e conv nios Publica es Seriadas S o os seriados t cnico cient ficos boletins peri dicos anu rios e anais de eventos simp sios e congressos Constam destas publica es o Internacional Standard Serial Number ISSN que um c digo nico e definitivo para identifica o de t tulos de seriados
95. duration slew time 2d prev 2d new condition and jat start pointing 73 d_prev effect and at end pointing is 2d new at start not pointing s 2d previ j1 durative action switch on parameters 21 instrument Ys satellite duration duration 2 condition and over all on board Fi 2314 at start power avail 5 effect jand fat end power on 71 lat start not power avail 73 durative action switch off parameters Yi instrument Ys satellite duration duration 1 condition and over all on board Fi 73 at start power on 71 effect jand fat start not power on ij fat end power avail 73 durative action take image parameters 5 satellite d direction i instrument m mode duration duration 7 condition and over all on board 7i P3 over all Supports i m over all power on i over all pointing dj fat end power on Zi1 effect land fat end have image 7d 10 111 FIGURA 3 6 Exemplo de um Arquivo de Dom nio de um Sat lite em PDDL Fonte adaptada de Cardoso 2006 p 65 57 O dom nio mant m toda a sem ntica do planejamento com tipos de entidades classes dos objetos que fazem parte do modelo definidas na instru o types da Figura 3 6 predicados sobre as entidades ou seja atributos que definem o estado da entidade listados em predicates fun es utilit rias functions e a
96. e suas taxas utilizada na RASSO ml difere de outras abordagens de planejamento O consumo de recursos em problemas de planejamento est sempre vinculado s a es As a es foram at hoje tratadas de duas formas distintas como a es pontuais de efeito imediato sobre estados e sem consumo de recursos ou como a es com dura o definida e consumo de recursos associado Exemplos deste segundo tipo s o as durative actions da PDDL e as activities da AML Chamaremos este tipo de a o de atividades para distingui las das a es sem dura o O ponto fraco do conceito de atividades que a modelagem do consumo de recursos discreta Fukunaga et al 1997 e reduz as possibilidades de manipula o pelo 119 planejador Para explicar a diferen a entre as abordagens tomemos como exemplo uma atividade Experimento Operando com uma dura o de 60 minutos e cuja execu o respons vel pelo consumo de 120 Mb de mem ria Em RASSO ml esta mesma atividade seria modelada como duas a es A primeira Ligar Experimento informa ao planejador que o consumo de mem ria por determinado objeto a partir daquele instante de 2 Mb por minuto A segunda que estaria posicionada no plano 60 minutos ap s a primeira seria Desligar Experimento Ela apenas informa ao planejador que o objeto n o consome mais mem ria x A diferen a b sica entre as abordagens com rela o modelagem do consumo
97. e algoritmo e seus elementos 6 4 1 Os Momentos Chave na Linha do Tempo do Plano O processo de busca por um plano v lido tem in cio com a identifica o de um conjunto de momentos chave na linha de tempo do plano e na verifica o da ocorr ncia de conflitos nestes momentos Os momentos chave s o e Os horizontes de planejamento h0 inicio do plano hl h2 e h3 t rmino do plano onde s o impostos estados e quantidades dispon veis de recursos a respeitar e Os momentos de execu o de a es no esbo o de plano recebido do Compositor de Problemas e Os momentos de in cio e t rmino de janelas de tempo que ocorram no per odo entre h0 e h3 e Os momentos de in cio e t rmino das restri es de recursos impostas pelas instru es guarantee resource e pela pr pria solicita o do experimento Tendo levantado estes momentos o planejador passa a verificar se existem conflitos em cada um deles de h0 at h3 Isso feito aplicando sobre o modelo as a es do esbo o de plano e dos comportamentos vinculados s janelas de tempo que ocorram entre h0 e h3 e verificando atrav s de seus efeitos se alguma restri o violada 126 6 4 2 A Identifica o dos Conflitos Mais de um conflito pode ocorrer a cada momento chave Os conflitos podem ser de tr s tipos e Estados inconsistentes e Viola o das restri es de consumo total de recursos e Viola o das restri es de consumo de re
98. e rastreio Para isso a arquitetura MAGA combina cinco tipos de agentes e Agente de Gera o do Problema e Agente de Planejamento do Rastreio de Sat lites e Agente para a Gera o do Plano de Opera es 87 e Agente para a Prioriza o de Objetivos e Agente para a Execu o dos Planos em Solo Outro trabalho em planejamento com IA no INPE teve como resultado o sistema de Planejamento Inteligente de Planos de Opera o de V o PlanIPOV Cardoso et al 2006 Este sistema utiliza o planejador temporal LPG TD e gera planos de opera o para o suporte s atividades de controle de sat lites em solo A linguagem de modelagem utilizada para a descri o do dom nio a PDDL 2 2 exemplos de arquivos de problema e de dom nio do PlanIPOV foram utilizados para os exemplos das Figuras 3 6 e 3 7 do Cap tulo anterior O PlanIPOV composto por m dulos de gera o do problema configura o planejamento e visualiza o Os m dulos de gera o do problema e de planejamento ser o integrados arquitetura MAGA implementando alguns de seus agentes 4 3 Aumento da Autonomia nas Espa onaves Todos os sistemas planejadores descritos at aqui aumentam o n vel de automatiza o na gera o de planos de opera o Isso reduz o esfor o da gera o manual de planos por parte dos especialistas e tem o potencial para reduzir os custos da miss o e aumentar o retorno da mesma Entretanto a automatiza o e
99. ecarga e respeitando as restri es impostas no modelo do EQUARS O pr ximo t pico apresenta passo a passo as escolhas feitas pelo Planejador durante o processo de replanejamento 135 7 3 O Processo de Replanejamento e as Escolhas do Planejador Ao receber o esbo o de plano do Compositor de Problemas o Planejador tinha como nicos conflitos presentes neste plano os de consumo de energia e mem ria pelo TIP no per odo indicado pela solicita o de recursos entre 9000s e 12000s Ao iniciar a busca o Planejador detectou que a melhor forma de resolver este conflito seria modificar a taxa de amostragem do experimento inserindo no plano uma a o Change Sample Rate tip 3 aos 9000s Esta a o multiplica em tr s vezes o consumo de energia e mem ria pelo TIP atendendo solicita o do experimento Entretanto conforme esperado a inser o desta a o levou a conflitos de consumo total de energia aos 10800s e de mem ria aos 15600s veja a Figura 7 2 Foi tamb m inserido um conflito de estado imposto pois TIP deveria ter sua taxa de amostragem igual a 1 ao t rmino do per odo do plano horizonte h3 e Change Sample Rate alterou esta taxa tornando a diferente do esperado em h3 O Planejador passou ent o a buscar mais uma modifica o no plano que solucionasse estes novos conflitos A modifica o encontrada foi inserir um comando para desligar o experimento GROM aos 10143s um momento aleat rio que foi
100. eitos de Escalonamento em TA Scheduling oooononcccnnnoocnnnnonncncnnaannnonnos 60 3 5 T cnicas Para a Solu o de Problemas de Satisfa o de Restri es CSPs 62 3 5 1 Busca Cons MVA sec errian ei a eaae ENERE EEEE EEEE RE E 62 3 52 do 63 3 6 Unindo Planejamento e Escalonamento em JA ccccccceesscceeseseceessseesesseneees 66 3 6 1 Planejamento e Escalonamento em Cascata ccccoooccnnnonnncnoonnnnnnonnnnononannnncnnnnnnnon 66 3 62 Venicaciode Vialidad cuina rl dabas 67 3 6 3 Planejamento Guiado por Restri es de Escalonamento cooocccnonocnnnonocncnnonnnnos 68 CAP TULO 4 APLICA ES ESPACIAIS COM PLANEJAMENTO E ESCALONAMENTO EM INTELIG NCIA ARTIFICIAL 71 4 1 Automatiza o de Opera es Versus Aumento da Autonomia c 72 4 2 Automatiza o de Opera es nas Miss es EspacialS cccoooccnnononnononananannnnnnonoss 73 4 2 1 Os Primeiros Planejadores com IA para Uso Espacial 73 4 2 2 Escalonamento de Observa es para o Telesc pio Espacial Hubble 74 4 2 3 Planejamento nas Opera es dos Space Shuttles cccccsccessccessceceeseceesueeeseeeeeaees 77 4 2 4 Sistemas Planejadores de Uso Geral em Miss es Espaciais 80 4 2 5 Planejamento em Miss es de Explora o de Marte cscs eeseeeseeseeeeseeeeeees 84 4 2 6 Estudos em Planejamento Automatizado Realizados no INPE 87 4 3 Aumento da Autonomia nas Espaconaves
101. elo de dominio tamb m chamado aqui apenas de modelo a base de conhecimento que um agente de planejamento pode utilizar para efetuar decis es racionais sobre o dom nio representado A forma de representa o do conhecimento existente sobre o dom nio dita o sucesso de qualquer sistema de planejamento em IA Classicamente esta representa o tamb m chamada de modelagem consiste da defini o de espa os de estados em que os componentes do dom nio possam se encontrar um conjunto de operadores ou a es capazes de alterar estes estados e um conjunto de regras associadas execu o dos operadores Os itens seguintes apresentam algumas das principais formas de representa o do conhecimento utilizadas em planejamento 3 3 1 STRIPS o Paradigma Ainda Vigente Mais de tr s d cadas depois de sua cria o a forma de representa o do conhecimento definida pelo STRIPS e apresentada no item 3 2 1 deste trabalho ainda o paradigma 54 vigente na rea de planejamento A esta forma de representa o foi dado o mesmo nome do sistema planejador que a implementou pela primeira vez A descri o em termos de literais que representam estados a es pr condi es e efeitos provou ser capaz de modelar os mais variados dom nios e problemas Diversas extens es surgiram com o passar dos anos e mesmo novas linguagens como a ADL e a PDDL mas estas continuam sendo baseadas nos mesmos conceitos fundamen
102. en M ed Morgan Kaufmann San Mateo CA USA 1994 AGENCIA ESPACIAL BRASILEIRA AEB PNAE programa nacional de atividades espaciais 2005 2014 Brasilia MCT AEB 2005 Disponivel em lt http www aeb gov br area download pnae web pdf gt Acesso em 14 mar de 2007 AI CHANG M BRESINA J CHAREST L CHASE A CHENG JUNG J JONSSON A KANEFSKY B MORRIS P RAJAN K YGLESIAS J CHAFIN B DIAS W MALDAGUE P MAPGEN mixed initiative planning and scheduling for the Mars Exploration Rover mission IEEE Intelligent Systems v 19 n 1 pp 8 12 Jan Feb 2004 ALONSO J D D PEREIRA JR A C O PESSOTTA F A Especifica o de requisitos do COMAV S o Jos dos Campos DEA INPE 2001 AXMANN R WICKLER M Development and verification of an autonomous on board mission planning system an example from the BIRD satellite In INTERNATIONAL CONFERENCE ON SPACE OPERATIONS SPACEOPS 9 2006 Rome Italy Proceedings Rome ATAA 2006 BEEK P CHEN X CPlan a constraint programming approach to planning In NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AAAI 99 16 1999 Orlando FL USA Proceedings Orlando AAAI Press 1999 p 585 590 147 BERNARD D DORAIS G GAMBLE E KANEFSKY B KURIEN J MAN G K MILLAR W MUSCETTOLA N NAYAK P RAJAN K ROUQUETTE N SMITH B TAYLOR W TUNG Y Spacecraft autonomy flight experience the DS1 Remote Agent Experiment In SP
103. ence AAAI MIT Press 1997 pp 714 719 148 BONET B GEFFNER H HSP planning as heuristic search In Entry at the AIPS 98 Planning Competition Pittsburgh USA Jun 1998 BRAT G DENNEY E FARELL K GILANNAKOPOULOU D JONSSON A FRANK J BODDY M CARPENTER T ESTLIN T PIVTORAIKO M A robust compositional architecture for autonomous systems In IEEE AEROSPACE CONFERENCE 2006 Big Sky MT USA Proceedings Big Sky IEEE 2006 BRESINA J DEARDEN R MEULEAU N RAMAKRISHNAN S SMITH D WASHINGTON R Planning under continuous time and resource uncertainty a challenge for AI In Conference on Uncertainty in AI UAT 18 2002 Edinburgh Scotland Proceedings s n 2002 BRESINA J JONSSON A MORRIS P RAJAN K Activity planning for the Mars Exploration Rovers In INTERNATIONAL CONFERENCE ON AUTOMATED PLANNING AND SCHEDULING ICAPS05 2005 Monterey CA USA Proceedings Monterey AIAA 2005 pp 40 49 BRESINA J L MORRIS P H Mission operations planning beyond MAPGEN In IEEE INTERNATIONAL CONFERENCE ON SPACE MISSION CHALLENGES FOR INFORMATION TECHNOLOGY 2 2006 Pasadena CA USA Proceedings Pasadena IEEE 2006 CARDOSO L S FERREIRA M G V ORLANDO V An intelligent system for generation of automatic flight operation plans for the satellite control activities at INPE In INTERNATIONAL CONFERENCE ON SPACE OPERATIONS SPACEOPS 9 2006 Rome Italy Proceeding
104. ento represent los como um Problema de Satisfa o de Restri es CSP do ingl s Constraint Satisfaction Problem e aplicar a eles t cnicas comuns de satisfa o de restri es Segundo Russell e Norvig 2004 em um CSP os estados s o definidos pelos valores atribu dos a um conjunto de vari veis para estes valores s o especificados um conjunto de restri es que devem ser respeitadas Os pr ximos itens apresentam as principais t cnicas utilizadas para a solu o de CSPs 3 5 T cnicas Para a Solu o de Problemas de Satisfa o de Restri es CSPs Existem diversos algoritmos para a solu o de CSPs mas a maioria deles cai em duas categorias a busca construtiva ou a busca local Ambas s o descritas brevemente a seguir 3 5 1 Busca Construtiva A busca construtiva baseia se na tentativa de se construir uma solu o ao efetuar atribui es a vari veis de forma incremental verificar as restri es e voltar atr s quando viola es nas restri es forem detectadas A Figura 3 9 traz um algoritmo simples para a resolu o de CSPs com busca construtiva Busca Construtiva CSP 1 Se qualquer restri o violada ent o falhar Sen o se todas as vari veis possuem valores atribu dos ent o retornar CSP Selecione uma vari vel sem valor atribu do w Escolha um valor v para w Atribua CSP propagar CSP UY v viy Busca Construtiva CSP no bw N
105. epara o para um novo lan amento Isso implica no planejamento de diversas tarefas como a aloca o de equipamentos equipes de t cnicos e a contrata o de empresas prestadoras de servi o O planejamento constantemente alterado seja pela indisponibilidade de pessoal especializado por atrasos inesperados ou pela necessidade de lidar com novos problemas descobertos no shuttle Como as tarefas est o fortemente vinculadas entre si qualquer altera o na execu o de uma tem impacto direto na realiza o das demais Os space shuttles s o espa onaves de manuten o extremamente custosa Qualquer redu o no tempo de processamento em solo mesmo que seja um pequeno percentual do tempo total representa uma economia de milh es de d lares Tendo como objetivo reduzir o tempo de processamento e consequentemente os custos das miss es dos shuttles o Ames Research Center da NASA desenvolveu o Ground 77 Processing Scheduling System GPSS cujo n cleo chamado de GERRY Zweben et al 1993 implementa escalonamento com t cnicas de IA Assim como o HSTS o GERRY representa o problema de escalonamento como um CSP e faz uso de reparo iterativo baseado em restri es para resolv lo A busca pela solu o guiada com o aux lio de heur sticas espec ficas para o problema O dom nio modelado com o uso de vari veis de estado e a entrada para o processo de busca um conjunto de tarefas a realizar cada qual co
106. ergia consumida da bateria n o alterada Se ao ser ligado um experimento consumir 10 watts ele continuar consumindo estes mesmos 10 watts at ser desligado Assim que isso ocorrer a bateria volta a ter os 10 watts dispon veis para serem consumidos por outro subsistema Por isso energia um recurso do tipo reserv vel Cabe esclarecer aqui que recursos s o mensurados em unidades n o importando ao RASSO se s o watts quilos ou bytes A Figura 6 3 apresenta um trecho de modelo em RASSO ml com instru es ao planejador para a cria o de dom nios de valores uma classe objetos e recursos A 112 cria o destes elementos complementada por uma rotina de inicializa o que se encontra listada ao fim do Ap ndice A deste trabalho create domain Exp Name certo grom ionex mltm tip create domain Mode full partial create class Experiment Exp Name name bool on Mode mode int sample rate int precision int priority create object MLTM Experiment create object GROM Experiment create resource Power create resource Mass Memory FIGURA 6 3 Cria o de Dominios Classes Objetos e Recursos em RASSO ml 6 2 2 A Descri o Din mica do Modelo Os principais elementos da parte din mica do modelo s o as a es e os comportamentos Ambos s o implementados como fun es em C mas tratados de forma diferente Este item descreve a estrutura das a es e dos
107. etura para o servi o de replanejamento embarcado que foi batizado de Resources Allocation Service for Scientific Opportunities RASSO Esta arquitetura apresentada na Figura 5 2 e descrita brevemente a seguir Na Figura o bloco destacado em amarelo corresponde ao servi o aqui proposto As setas numeradas indicam o fluxo de dados entre os m dulos em laranja durante o processo de planejamento Sat lite Carga til Computador de Bordo COMAV Experimento 1 RASSC Software de V o Sat lite mm Aplicativos Experimento n condi Fila de Telecomandos Temporizados GETS Plano Corrente FIGURA 5 2 A Arquitetura do RASSO 102 Cada experimento habilitado a solicitar mais recursos do computador de bordo deve ter implementada ao menos uma Condi o de Disparo As Condi es de Disparo indicam a detec o de um fen meno cient fico e disparam uma solicita o por mais recursos para o RASSO seta 1 da Figura 5 2 esquerda A forma de implementa o e o intervalo de w aes ns 4 verifica o das condi es ficam a cargo de cada experimento Ao receber a solicita o o m dulo Compositor de Problemas do RASSO gera um problema bem definido na forma de um esbo o de plano com conflitos Este esbo o criado ao se consolidar informa es de v rias fontes no software embarcado setas 2 a 5 Os conflitos s o inseridos devido aloca o dos recursos solicitados pelo experimento O esbo o de plano ent
108. eve ser poss vel equipe de opera es em solo efetuar a an lise dos planos gerados sem que estes sejam colocados em execu o A primeira caracter stica deve ser provida garantindo que qualquer altera o no plano tenha efeito tempor rio e que ap s o per odo de observa o do fen meno o sat lite volte ao seu modo de opera es normal ou seja forma de opera o programada em solo 107 A segunda caracter stica deve ser provida atrav s de modos de planejamento distintos que definam o destino dos planos gerados a bordo O RASSO deve possuir tr s modos de planejamento desabilitado sugerindo e atuando No modo desabilitado o servi o n o est dispon vel e os experimentos sempre t m suas solicita es negadas O modo sugerindo existe para permitir a an lise da confiabilidade do servi o Neste modo o servi o recebe as solicita es e sempre envia uma nega o aos experimentos em resposta Entretanto ele deve trabalhar num novo plano como se realmente fosse atender solicita o O plano resultante n o executado ao inv s disso ele disponibilizado para a equipe de opera es em solo via telemetria Toda vez que uma solicita o tiver sido enviada ao RASSO quando em modo sugerindo uma mensagem de alerta de que h planos armazenados para an lise deve ser enviada equipe de opera es independente se o plano obtido completo ou n o
109. ex e o controle destas a es a base da gera o de planos por an lise de grafos Duas a es s o consideradas mutex caso satisfa am os seguintes crit rios e Ffeitos inconsistentes o efeito de uma a o a nega o do efeito de outra a o e Interfer ncia uma a o elimina a pr condi o de outra a o 51 e Pr condi es inconsistentes duas a es do n vel 1 s o geradas a partir de pr condi es que s o mutuamente exclusivas no n vel 1 1 O grafo gerado comp e um espa o de busca bastante reduzido com rela o ao original O GRAPHPLAN ent o dispara um processo de busca exaustiva no grafo para encontrar o melhor plano que no exemplo da Figura 3 4 composto por duas a es mover A C B gt mover C mesa A Outros planejadores fizeram uso deste pr processamento do espa o de busca atrav s da cria o do grafo de planejamento e o combinaram com algoritmos de busca baseados em satisfatibilidade alcan abilidade e busca heur stica entre outros com a finalidade de obter melhores resultados 3 2 5 Combinando Grafos e Satisfatibilidade Um dos principais planejadores a combinar diferentes abordagens foi o BLACKBOX Kautz e Selman 1998 que uniu t cnicas de planejamento baseado em grafos e em satisfatibilidade O BLACKBOX usa o pr processamento e redu o do espa o de estados para a composi o de um grafo de planejamento e aplica a este grafo t cnicas
110. explos es solares e a passagem do telesc pio pela Anomalia do Atl ntico Sul for am o desligamento tempor rio de equipamentos Com tamanha complexidade a gera o de planos de observa o timos algo quase imposs vel de ser realizado manualmente Ciente disso o STScl iniciou antes mesmo do lan amento do telesc pio o desenvolvimento de dois sistemas escalonadores para automatizar a gera o de planos um para o planejamento de m dio longo prazo e outro para o planejamento de curto prazo O Science Planning Intelligent Knowledge Environment SPIKE Johnston 1990 respons vel pelo planejamento a m dio longo prazo Sua tarefa atribuir observa es a blocos de tempo alocando primeiramente observa es priorit rias para ent o preencher os intervalos com observa es de menor prioridade O resultado um plano com um ano de dura o mas com observa es atribu das aos blocos de tempo usualmente de uma semana ou seja h uma flexibilidade para ajustar cada observa o dentro de seu per odo 70 ponto de maior aproxima o do cintur o de Van Allen com a superficie da Terra onde a intensidade de radia o maior que em outras regi es da mesma altitude 75 O planejador de curto prazo Science Planning and Scheduling System SPSS Johnston 1990 ao contr rio do SPIKE n o implementa IA Ele recebe como entrada o plano gerado pelo SPIKE e atribui tempos espec ficos para as
111. fechamento dos sem foros encontrados pelo caminho s o eventos ex genos pois est o fora do controle do planejador A ltima vers o PDDL 3 0 permite a descri o de objetivos opcionais ou seja objetivos que um planejador deve tentar atingir ap s ter alcan ado todos os objetivos mandat rios Em geral nem todos os objetivos opcionais podem ser atingidos mas um plano que n o leve o sistema a estes estados ainda considerado um plano v lido A base de conhecimento da PDDL composta por duas partes presentes em arquivos distintos um para a descri o do dom nio e outro para as especifica es do problema A descri o do dom nio fixa para todos os problemas que s o compostos por descri es 56 do estado inicial e dos objetivos a serem atingidos A Figura 3 6 apresenta um exemplo de dom nio em PDDL representando estados e a es relativos opera o de um sat lite define domain satellite requirements strips cequality ityping fluents cdurative actions itypes satellite direction instrument mode predicates ton board Yi instrument 2s satellite supports Fi instrument fm mode pointing 78 satellite d direction power avail s satellite power on i instrument have_image d direction Y mode functions slew time a b direction i durative action turn to parameters 25 satellite 2d new direction d prev direction duration
112. fen menos de curta dura o solicitem diretamente ao computador de bordo do sat lite a realoca o tempor ria de recursos Esta realoca o deve ocorrer de tal forma que afete o m nimo poss vel a opera o dos outros experimentos e do pr prio sat lite Como o n mero de estados em que o sistema pode estar no momento da detec o do fen meno enorme torna se dif cil o uso de t cnicas cl ssicas de programa o para trat los Este trabalho prop e o uso de t cnicas de Planejamento e Escalonamento da rea de Intelig ncia Artificial para permitir o replanejamento embarcado de opera es quando da detec o de fen menos de curta dura o O objetivo propiciar ao sat lite maior autonomia e consequentemente maior capacidade de resposta a eventos externos Foi definida uma arquitetura para um servi o de replanejamento embarcado para os sat lites cient ficos do INPE Houve a preocupa o de se contextualizar esta arquitetura nos projetos atuais do Instituto para sat lites e computadores Foi ent o desenvolvido um prot tipo baseado nesta arquitetura implementado para execu o em um computador de bordo para sat lites que est sendo desenvolvido no INPE Devido falta de ferramentas de software para este tipo de computador foi preciso desenvolver tamb m uma linguagem de representa o do conhecimento e um sistema planejador espec ficos para este dom nio O prot tipo criado se baseia na id ia de garantir uma maior
113. flitos no plano O algoritmo apresentado em pseudo c digo na Figura 6 10 Plant I bter_Momentos_Chawe_no_Planot numero_conflitos obter conflitos no plano Enquanto Cnumero conflitos gt 0 l Para cada momento chawe no plano obter conflitos no MomentoCmomento Fara cada conflito neste momento obter cComtribuintesto Fara cada contribuinte deste conflito conflito resolvido Testar Mudancas momento conflito contribuinte se Cconflito resolvido false Inserir Perturbacao no Plano Escolher Melhor Mudanca os aplicar mudanca ao Planoj numero conflitos obter conflitos no plano Se modo_planejamernto sugerindo Disponibil1zar_Plano_Para_Telemetria senao modo atuando Enviar Plano Para a Fila TCs Temporizados FIGURA 6 10 O Algoritmo de Planejamento O algoritmo de planejamento criado procura solucionar o CSP atrav s de busca local guiada por restri es de escalonamento cuja defini o encontra se no item 3 6 3 deste 125 trabalho com a adi o de perturba es no plano quando necess rio para escapar de m nimos locais e plat s As perturba es consistem da inser o de a es que resolvam um conflito mas cujos pr requisitos ainda n o s o verdadeiros no plano Elas ser o melhor explicadas ainda neste Cap tulo Heur sticas para auxiliar no processo de planejamento n o foram inseridas neste prot tipo Os itens seguintes descrevem est
114. i es temporais entre as sub atividades J o conceito de recursos do DCAPS foi utilizado para descrever todos os componentes do sistema modelado Para isso foram definidos cinco tipos de recursos 78 e Recursos de estado que representam caracter sticas atributos do sistema que assumem valores discretos Um subsistema qualquer como um experimento pode ser modelado como um recurso de estado possuindo ao menos dois valores poss veis ligado e desligado e Recursos de concorr ncia que s o utilizados para modelar itens de uso exclusivo no sistema como um canal de comunica o de acesso nico e Recursos consum veis usados para modelar recursos com quantidade limitada como propelente e mem ria e Recursos n o consum veis que descrevem recursos com quantidade tamb m limitada mas que liberada imediatamente ap s o consumo como energia e E finalmente os recursos simples que representam dispositivos que s podem ser utilizados por uma atividade por vez O DCAPS gera um plano inicial com falhas e aplica a ele t cnicas de reparo iterativo de forma similar ao que ocorre no HSTS e no GERRY Heur sticas tamb m s o utilizadas para auxiliar na decis o de quais altera es devem ser aplicadas ao plano original Para cada per odo de opera o podem ser gerados mais de um plano todos atingindo os mesmos objetivos Estes planos s o comparados de acordo com o n vel de otimiza o de cada um
115. idade de uso do instrumento Ao contr rio do DCAPS que modelou todos os componentes em um modelo como recursos no ASPEN recursos representam apenas o perfil de consumo de um recurso f sico no tempo Os tipos de recursos dispon veis s o os consum veis e n o consum veis e suas defini es s o as mesmas do DCAPS O restante dos componentes modelado como vari veis de estado conceito herdado do HSTS assim como o uso de linhas do tempo para manipul las Reservas s o requisitos para a execu o de atividades com rela o a recursos ou vari veis de estado Por exemplo uma atividade pode ter uma reserva de dez watts de energia Isso significa que durante a atividade s o consumidos estes dez watts Pode se especificar se este consumo ser calculado no in cio ou no fim da atividade Finalmente a atividade a estrutura central no ASPEN Uma atividade representa uma a o ou um passo em um plano Ela possui um momento de in cio dura o e um momento de t rmino Atividades podem consumir um ou mais recursos e podem conter sub atividades o que permite o uso de planejamento hier rquico A Figura 4 1 apresenta um pequeno exemplo de modelo descrito em AML onde est o representadas uma atividade um recurso par metros restri es temporais e reservas 81 Activity prevalve removal duration 15 slot subsystem after prevalve prep with subsystem this subsystem hefore prevalve replace with subsystem
116. ido fisicamente dentro do experimento geralmente para a pesquisa do comportamento em ambiente de microgravidade de fen menos conhecidos e bem estudados na presen a de gravidade No segundo caso os experimentos carregam sensores que coletam dados sobre o ambiente espacial no qual o sat lite se encontra Alguns destes sensores podem detectar a passagem de part culas pelo sat lite outros podem efetuar medidas diversas das camadas superiores da atmosfera por exemplo A concep o atual dos experimentos no programa SCE do INPE o de experimentos inteligentes Estes experimentos possuem seu pr prio processador respons vel pelo funcionamento do experimento e pela comunica o com o computador de bordo Entretanto apesar de possu rem capacidade de processamento pr pria os experimentos 36 compartilham outros recursos providos pelo sat lite como mem ria para armazenamento de dados e energia Os experimentos cient ficos t m seus modos de opera o determinados ainda na etapa de projeto do sat lite Os modos de opera o s o definidos em termos das fases da rbita em que eles ficar o ligados do tempo em que permanecer o ligados de qual a quantidade de dados que ir o gerar e quanto ir o consumir de energia entre outros As fases da rbita podem ser o per odo em que o sat lite encontra se iluminado pelo Sol o per odo em que se encontra eclipsado pela Terra grosso modo os per odos de dia e noite
117. ilustrado na Figura 6 8 Modelo do Sistema Tabela de Janelas de Tempo solicita es problema de por recursos planejamento Compositor de Problemas Fila de Telecomandos Software Normal do Temporizados Computador de Bordo piano corrente chances para fibra oo estago alto FIGURA 6 8 Consolida o de Dados para a Composi o do Problema A cria o de um problema bem definido t o importante quanto o processo de busca pela solu o O problema consiste de um esbo o de plano de opera es com objetivos a serem atingidos restri es a serem respeitadas e conflitos a serem resolvidos Fazem parte do problema tamb m o estado inicial do sat lite os estados objetivo os telecomandos as a es na RASSO ml agendados para execu o e os eventos ex genos os comportamentos que ocorrem durante o per odo de execu o do plano 6 3 1 Horizontes de Planejamento A solicita o de recursos enviada pelo experimento carrega em seus par metros a informa o de dois momentos cruciais para o processo de planejamento o in cio e o t rmino do per odo em que o experimento precisa de mais recursos Estes momentos chave s o chamados de horizontes de planejamento e s o utilizados para determinar o estado inicial os estados intermedi rios e o estado objetivo Figura 6 9 121 Condi o de Disparo verdadeira envia solicita o por mais recursos estado inicial inicia a realoca o de recursos
118. ite a solicita o por mais recursos enviada pelo TIP faria com que o consumo tanto de mem ria quanto de energia ultrapassasse as quantidades dispon veis no sat lite O consumo de energia seria colocado em sobrecarga aos 10800s e o de mem ria aos 15600s A Figura 7 2 apresenta o consumo normal e em sobrecarga de cada recurso Nela as linhas vermelhas indicam a quantidade m xima dispon vel para consumo 134 Consumo Total de Energia do EQUARS em Modo Normal Consumo Total de Energia do EQUARS em Sobrecarga i E i En 50 50 45 45 40 40 H 3 35 o E 230 30 8 25 25 20 20 15 15 10 10 0 3000 6000 9000 12000 15000 18000 O 3000 6000 9000 12000 15000 18000 tempo seg tempo seg Consumo Total de Mem ria no EQUARS em Modo Normal Consumo Total de Mem ria no EQUARS em Sobrecarga 125000 A 180 ASAS 120000 120000 115000 115000 110000 110000 105000 105000 100000 100000 95000 95000 90000 90000 85000 85000 s000 80000 75000 75000 70000 70000 60000 60000 55000 55000 50000 50000 45000 45000 40000 40000 35000 35000 30000 30000 25000 25000 20000 20000 15000 15000 10000 10000 5000 5000 0 0 0 3000 6000 9000 12000 15000 18000 0 3000 6000 9000 12000 15000 18000 tempo seg tempo seg FIGURA 7 2 Consumo de Energia e Mem ria em Modo Normal e em Sobrecarga Cabe ao RASSO trabalhar no plano e encontrar altera es nele que permitam atender solicita o do TIP sem colocar os recursos em sobr
119. ito Fila de Teleco mandos Temporizados Momento Comando Ofchange Mode ionex partia 6oO Turm_Om grom 12000 Turn_On tip 12000 Change_Sample_Rate tip 1 12000 Turn_Off tip FIGURA 7 3 O Plano de Opera es Modificado Pelo RASSO 137 A Figura 7 4 apresenta o consumo total de mem ria e energia conforme definido no plano modificado pelo RASSO Consumo Total de Energia do EQUARS ap s Replanejamento Consumo Total de Mem ria no EQUARS ap s Replanejamento 55 qq gt gt gt 125000 lt u 120000 115000 E 4 gt gt 110000 105000 100000 95000 90000 40 85000 w m consumo watts q mem ria kbits 2 40000 A E ER EEE 20 25000 Say SEA 10 T T T T T 0 0 3000 6000 9000 12000 15000 18000 0 3000 6000 9000 12000 15000 18000 tempo seg tempo seg FIGURA 7 4 Consumo Total de Energia e Mem ria Ap s o Replanejamento Nota se que al m de evitar a sobrecarga no consumo de recursos o RASSO garantiu que ao t rmino do per odo do plano aos 18000s as quantidades em uso de recursos foram iguais energia ou menores mem ria do que no plano original Isso mais a imposi o dos estados em que os experimentos devem estar ao t rmino do per odo garantem que os efeitos da modifica o do plano sejam tempor rios e que ap s este per odo o sat lite volte a operar conforme originalmente planejado 7 4 An lise d
120. jador escolhe entre um conjunto de a es aplic veis qual a que parece levar o modelo para um estado mais pr ximo do objetivo As pr condi es para a execu o da a o s o avaliadas e caso sejam verdadeiras os efeitos da a o s o aplicados sobre o modelo verificado ent o o novo estado obtido Este processo segue iterativamente at que o estado objetivo seja atingido A seq ncia de a es que obteve sucesso em levar o modelo de seu estado inicial para o estado objetivo dado o nome de plano Estado Estado Estado Inicial Intermedi rio S S Objetivo S FIGURA 3 1 Aplica o de A es no Modelo At a Obten o do Estado Objetivo 44 Existem diversas t cnicas para guiar o processo de busca at uma seqii ncia de a es adequada Estas t cnicas v m evoluindo com o passar dos anos e tornando o planejamento em IA capaz de resolver problemas cada vez mais complexos Os pr ximos itens apresentam um breve hist rico da evolu o do planejamento em TA e de algumas das principais abordagens para a solu o de problemas de planejamento 3 2 Hist rico e Abordagens de Planejamento 3 2 1 O Primeiro Planejador e Seus Sucessores O primeiro software planejador foi o STRIPS Stanford Research Institute Problem Solver criado no in cio da d cada de 1970 Fikes e Nilsson 1971 O STRIPS trouxe um esquema de representa o de estados e a es baseado em literais tamb m chamada
121. loco Tivrece nece BL sobre bloco e Bl neces BL sobre mesa eB bloco Tivre eo sobre mesate Ji FIGURA 3 8 Exemplo de Descri o de Dom nio Para o Mundo de Blocos em OCL A instru o sorts define o tipo bloco Este tipo instanciado pela instru o objects onde s o criados os objetos blocol a bloco7 A instru o predicates traz os atributos 59 de um objeto do tipo bloco sobre bloco sobre mesa e bloco livre Finalmente a instru o substate classes define explicitamente todos os poss veis sub estados em que um objeto de determinado tipo pode se encontrar indicando quais combina es de predicados s o legais A OCL tem como grande contribui o permitir uma melhor estrutura o e maior representatividade do conhecimento sobre o mundo sendo modelado Mas por ainda se basear em descri o por predicados a linguagem dependente da representa o expl cita de qualquer mudan a nos estados do modelo exatamente como em STRIPS ou PDDL De qualquer forma a OCL representa um grande passo em dire o descri o de dom nios de forma totalmente orientada a objetos 3 3 5 Outras Formas de Representa o do Conhecimento Al m das linguagens STRIPS ADL PDDL OCL e suas variantes existem outras abordagens para a representa o do conhecimento em problemas de planejamento Boa parte delas foi criada tendo aplica es espec ficas em mente Um exemplo na rea
122. m IA ser referenciado com frequ ncia como planejamento ou planejamento em IA uma vez que estas t cnicas s o tratadas de forma unificada neste trabalho 71 planejadores com IA desenvolvidos at hoje suas caracter sticas e resultados colhidos de seu uso Estes sistemas est o categorizados conforme o tipo de automatiza o que eles proporcionam a automatiza o de opera es em solo ou o aumento da autonomia da espa onave O Cap tulo encerra com uma breve apresenta o das tend ncias atuais na rea de planejamento aplicado ao espa o 4 1 Automatizac o de Opera es Versus Aumento da Autonomia Existem tr s diferentes n veis de automatiza o poss veis em uma miss o espacial 1 Gera o de Planos de Opera o por Operadores Humanos 2 Gera o Automatizada de Planos de Opera o 3 Gera o Aut noma de Planos de Opera o O primeiro n vel onde ainda se encontram a maioria das miss es espaciais nas quais especialistas na miss o s o os respons veis pela gera o das sequ ncias de comandos Neste n vel mesmo que auxiliados por ferramentas computacionais s o os especialistas que tomam as decis es e fazem todas as considera es sobre os efeitos diretos e indiretos da execu o de comandos sobre o estado da espa onave No segundo n vel sistemas planejadores com IA s o utilizados para gerar os planos com base no comportamento simulado da espa onave a partir de modelos descriti
123. m planejamento e escalonamento foram apresentados por Myers e Smith 1999 para a opera o de grandes empresas Ruml e Fromherz 2004 controle de manufatura e Halsey et al 2004 planejador e escalonador de uso geral H tamb m iniciativas de integra o para aplica es na rea espacial que ser o apresentadas no pr ximo Cap tulo deste trabalho A seguir s o destacadas algumas das abordagens b sicas de integra o entre planejamento e escalonamento 3 6 1 Planejamento e Escalonamento em Cascata A forma mais simples de integra o entre Planejamento e Escalonamento o modelo iterativo em cascata Neste esquema o planejador e o escalonador operam de forma sequencial o planejador gera um conjunto completo de a es para atingir um conjunto de objetivos e ent o o encaminha para o escalonador que atribui tempo e recursos s a es 66 estado inicial plano candidato Planejador restri es temporais e estado de recursos objetivo falha ao atribuir recursos e tempo Escalonador crie um plano alternativo plano completo FIGURA 3 11 Planejamento e Escalonamento em Cascata Logicamente nem todos os planos s o escalon veis e caso o escalonador n o consiga efetuar suas atribui es ele chama novamente o planejador para gerar um plano alternativo Este processo se repete at que um plano seja totalmente escalon vel e possa ser encaminhado para execu o
124. m solo limitada em alguns aspectos importantes da opera o de espa onaves Em situa es de emerg ncia ou no caso da ocorr ncia de oportunidades cient ficas como descrito na Introdu o deste trabalho a equipe em solo pouco pode fazer Devido aos per odos fora de visibilidade ao atraso dos links de comunica o e ao pr prio tempo de rea o do pessoal da miss o para a an lise dos dados e tomada de decis o n o poss vel dar uma resposta satisfat ria a estas ocorr ncias At que um plano possa ser gerado em solo e colocado em execu o os estados do sistema e do ambiente externo a ele provavelmente ter o mudado significativamente 88 Al m disso a monitora o e o controle de uma espa onave sempre se baseiam numa vis o passada do estado dos subsistemas e do ambiente Os dados de telemetria contendo os estados podem ter sido coletados at horas antes de sua transmiss o e a quantidade de dados enviados em tempo real limitada Torna se dif cil replanejar de forma adequada em resposta a eventos n o previstos tendo disposi o informa o defasada sobre a situa o do sat lite Para que seja poss vel o replanejamento em resposta a ocorr ncias aleat rias necess rio manipular informa es obtidas em tempo real sobre o estado da espa onave e de seu ambiente e colocar o novo plano em execu o assim que estiver pronto A nica forma de se fazer isso transferir o processo de planejamento
125. m sua dura o restri es de tempo e de recursos requisitos de estados para permitir a execu o da tarefa e efeitos da tarefa sobre o modelo O GPSS recebeu pr mios por sua inova o tecnol gica como o NASA Space Act Award e o Technologies of the Year Award 1995 da revista Industry Week e seu uso trouxe uma economia de cerca de quatro milh es de d lares ano para as opera es de solo dos shuttles Mas o uso de sistemas planejadores nos space shuttles n o se restringiu s opera es de manuten o em solo A miss o STS 85 lan ada em agosto de 1997 carregou entre suas diversas cargas teis um conjunto de instrumentos cient ficos desenvolvidos pela Universidade do Colorado chamado de Data Chaser com a finalidade principal de efetuar observa es solares O Data Chaser possu a um sistema de planejamento automatizado em solo o Data Chaser Automated Planning System DCAPS Rabideau et al 1997 desenvolvido pela Universidade do Colorado em conjunto com o JPL No DCAPS o modelo de dom nio composto basicamente por atividades e recursos As atividades s o utilizadas para modelar tanto os eventos que afetam o estado do sistema quanto as a es que o Data Chaser pode executar Cada atividade possui uma dura o e um conjunto de par metros Al m disso cada atividade pode conter um conjunto de sub atividades o que permite ao DCAPS realizar planejamento hier rquico E poss vel ainda especificar restr
126. mente anterior A Figura 3 4 ilustra um grafo de planejamento simplificado para o problema do mundo de blocos na mesma configura o apresentada na Figura 3 2 50 sobre A B S1 sobre C mesa S1 sobre A B Sn sobre C A Sn sobre B mesa Sn mover B A mesa f retorna ao estado inicial livre C Sn mover C mesa A sobre B A S1 n vel O nivel 1 nivel 2 nivel 3 nivel 4 estado inicial a es 1 passo estado intermedi rio a es 2 passo estado objetivo FIGURA 3 4 Grafo de Planejamento para o Mundo de Blocos Para gerar este grafo a primeira etapa da execu o o GRAPHPLAN insere os n s com as literais que descrevem o estado inicial e em um nivel n par as literais do estado objetivo S o ent o verificadas todas as a es cujos operadores de pr condi o PRE para o estado inicial s o verdadeiros e estas s o inseridas no n vel um Os operadores ADD e DEL de cada a o s o aplicados e as literais resultantes s o colocadas no n vel seguinte do grafo n vel dois junto com as literais n o alteradas por a o alguma que s o transferidas para o pr ximo n vel Novamente s o selecionadas a es cujos operadores PRE sejam verdadeiros no n vel dois e inseridas no n vel tr s Este processo continua at que o grafo atinja as literais do estado objetivo Muitas das a es inseridas no grafo s o mutuamente exclusivas mut
127. mento e impulsionaram a rea de planejamento por outro elas parecem estar direcionando as pesquisas em planejamento apenas para a busca por algoritmos mais eficientes de solu o de problemas A pesquisa sobre formas alternativas e potencialmente mais poderosas de representa o do conhecimento para problemas de planejamento segue bastante restrita s extens es da PDDL Pode se notar na literatura 68 uma queda significativa ocorrida nos ltimos anos em publica es sobre formas de representa o n o relacionadas PDDL Uma exce o not vel regra vem justamente da rea de sistemas planejadores e escalonadores utilizados na rea espacial Como o gerenciamento dos recursos presentes no segmento espacial e o controle temporal da execu o de tarefas s o partes cruciais dos problemas da rea os criadores destes sistemas tiveram que desenvolver suas pr prias representa es de recursos e tempo que ser o apresentados no Cap tulo seguinte 69 70 CAP TULO 4 APLICA ES ESPACIAIS COM PLANEJAMENTO E ESCALONAMENTO EM INTELIG NCIA ARTIFICIAL O segmento espacial seja ele composto por sat lites cient ficos observat rios espaciais sondas ou jipes exploradores em Marte controlado atrav s de planos de opera o Isso ocorre de forma igual ou muito similar ao que foi apresentado no Cap tulo 2 deste trabalho Os planos s o compostos por sequ ncias de comandos de baixo n vel ordenados temporalme
128. mo mas permite lidar com situa es inesperadas em tempo real Outro framework que cont m planejamento embarcado atualmente em desenvolvimento na NASA em conjunto com outras institui es o Coupled Layer Architecture for Robotic Autonomy CLARAty Estlin et al 2005 O CLARAty um reposit rio de m dulos reutiliz veis de software que juntos compreendem todas as funcionalidades necess rias para espa onaves e rob s aut nomos Existem m dulos para opera o de sensores e aquisi o de dados para o controle motor coordenado para planejamento navega o inteligente entre outros Para o planejamento o CLARAty vinha integrando o CASPER ao sistema executor TDL Simmons e Apfelbaum 1998 mas um trabalho recente Brat et al 2006 mostra que esta solu o foi substitu da pelo EUROPA Pretende se que o CLARAty se torne um conjunto de bibliotecas de software a ser utilizado nos sistemas embarcados de miss es explorat rias a serem lan adas em m dio prazo as miss es atualmente em fase de desenvolvimento ainda n o abriram espa o para o replanejamento embarcado Nos ltimos dois anos come aram a surgir alguns trabalhos tratando de planejamento embarcado fora da NASA mostrando que outras ag ncias tamb m passam a se preocupar com o aumento da autonomia de suas futuras miss es O CNES franc s colaborou com um estudo sobre o problema de gerenciamento de constela es de sat lites de sensoriamento remoto
129. nada insere novos conflitos no plano Para determinar onde permitido ao planejador inserir uma perturba o utilizada na descri o do modelo a instru o force state if needed by id veja a Figura 6 4 Ap s a sele o e aplica o de uma modifica o no esbo o de plano um novo levantamento dos conflitos feito Este processo segue at que n o haja mais conflitos no plano Quando isso ocorrer o plano obtido enviado para a fila de telecomandos temporizados ou disponibilizado para telemetria de acordo com o modo de planejamento do RASSO conforme descrito no item 5 4 deste trabalho Cabe frisar aqui que ao contr rio do que era esperado no in cio deste trabalho n o foi o algoritmo de planejamento que demandou maior volume de trabalho e sim a defini o de uma forma adequada para a representa o do conhecimento do dom nio de sat lites que culminou na cria o da RASSO ml A representa o correta do modelo bem como do problema a ser resolvido tornou mais simples o processo de busca pela solu o no algoritmo de planejamento 129 O pr ximo Cap tulo apresenta o cen rio de testes criado para validar o sistema e os resultados obtidos de sua execu o 130 CAP TULO 7 CEN RIO DE TESTES E RESULTADOS OBTIDOS Este Cap tulo descreve o comportamento assumido para os experimentos embarcados no EQUARS o cen rio criado para os testes do prot tipo do RASSO e apresenta os resultados da execu
130. nais mostra o interesse da comunidade nas id ias aqui implementadas Um artigo apresentando uma vis o inicial deste trabalho foi publicado na 9th International 142 Conference on Space Operations SpaceOps 2006 Kucinskis and Ferreira 2006 e selecionado posteriormente entre os melhores trabalhos do congresso para publica o como cap tulo em uma edi o futura de um livro da s rie Progress in Astronautics and Aeronautics prevista para publica o no segundo semestre deste ano Outro artigo foi publicado e apresentado na 2007 IEEE Aerospace Conference Kucinskis et al 2007 no in cio de mar o deste ano Outros trabalhos foram submetidos para os journals Applied Artificial Intelligence Journal of Aerospace Computing Information and Communication JACIC e Engineering Applications of AI e se encontram atualmente em processo de revis o 8 2 Trabalhos Futuros H muito que ser feito com rela o a estudos e implementa o de t cnicas de planejamento e escalonamento em IA para o segmento espacial Em primeiro lugar destaca se a necessidade do desenvolvimento de t cnicas de verifica o e valida o para software aut nomo Discuss es a este respeito e algumas propostas interessantes podem ser vistas em Brat et al 2006 e Blanquart et al 2004 O gerenciamento da incerteza em sistemas aut nomos um t pico ainda pouco explorado e de vital import ncia para o futuro da autonomia em sistemas espaciais
131. ndo de um estado inicial e um conjunto de objetivos a serem atingidos inicializa o banco de dados do plano plan database que cont m um esbo o de plano a ser trabalhado O motor de busca search engine modifica o banco de dados do plano para gerar um plano v lido que ent o enviado para um sistema executor inteligente As heur sticas prov em guiagem para o processo de busca e os especialistas de planejamento planning experts permitem a comunica o com sistemas externos como os de controle de atitude cujas entradas o planejador deve levar em conta O objetivo do RAX PS foi gerar planos de opera o detalhados a partir de comandos de alto n vel enviados de solo Ele foi executado em duas ocasi es no m s de maio de 1999 totalizando cerca de vinte e seis horas de execu o Neste per odo o RAX PS gerou planos para tarefas de mudan a de atitude comunica o propuls o observa es e navega o entre outras O experimento foi considerado um enorme sucesso e atualmente refer ncia comum a qualquer trabalho de planejamento e escalonamento na rea espacial ou fora dela Bernard et al 1999 traz um relato e uma an lise sobre a execu o do experimento inclusive com os problemas ocorridos e as solu es aplicadas O segundo sistema planejador embarcado utilizado em uma miss o espacial e at o momento o nico outro foi o Continuous Activity Scheduling Planning Execution and Replanning CASPER uma vers
132. nning and scheduling Knowledge Engineering Review v 15 n 1 pp 47 83 2000 TATE A Generating project networks In INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE IJCAD 5 1977 Cambridge MA USA Proceedings Cambridge William Kaufmann 1977 pp 888 893 157 TESTON F CREASEY R BERMYN J MELLAB K PROBA ESA s autonomy and technology demonstration mission In INTERNATIONAL ASTRONAUTICAL CONGRESS IAC 48 1997 Turin Italy Proceedings Turin AIAA 1997 VERE S Planning in time windows and durations for activities and goals IEEE Transactions on Pattern Analysis and Machine Intelligence v 5 pp 246 267 1983 VERMA V JONSSON A SIMMONS R ESTLIN T LEVINSON R Survey of command execution systems for NASA robots and spacecrafts In INTERNATIONAL CONFERENCE ON AUTOMATED PLANNING AND SCHEDULING ICAPSOS 2005 Monterey CA USA Proceedings Monterey AIAA 2005 pp 40 49 WERTZ J LARSON W Ed Space mission analysis and design 3 ed Torrance CA Microcosm Inc and Kluwer Academic Publishers 1999 969 p ISBN 978 1881883104 ZWEBEN B DAVIS M DAUN E DEALE M Scheduling and rescheduling with iterative repair IEEE Transactions on Systems Man and Cybernetics v 23 n 6 Nov Dec 1993 158 AP NDICE A MODELO DO SAT LITE E EXPERIMENTOS EM RASSO ML include language h include config h CRIACAO DOS DOMINIOS A SEREM UTILIZADOS NO MODE
133. nning for spacecraft operations using the ASPEN system In INTERNATIONAL SYMPOSIUM ON ARTIFICIAL INTELLIGENCE ROBOTICS AND AUTOMATION IN SPACE I SAIRAS 5 1999 Noordwijk The Netherlands Proceedings Noordwijk ESA ESTEC 1999 156 RUML W FROMHERZ M P J On line planning and scheduling for high speed manufacturing In INTERNATIONAL CONFERENCE ON AUTOMATED PLANNING AND SCHEDULING ICAPS04 2004 Whisler Canada Proceedings Whisler AIAA 2004 RUSSELL S NORVIG P Intelig ncia Artificial 2 ed S o Paulo Editora Campus 2004 1040 p ISBN 8535211772 SACERDOTI E D Planning in a hierarchy of abstraction spaces Artificial Intelligence v 5 n 2 pp 115 135 1974 SILVA F CASTILHO M KUNZLE L PETRIPLAN a new algorithm for plan generation preliminary report In INTERNATIONAL JOINT CONFERENCE IBERAMIA SBIA IBERO AMERICAN CONFERENCE ON AI 7 BRAZILIAN SYMPOSIUM ON AL 15 2000 Atibaia SP Brasil Proceedings S o Paulo ICMS USP 2000 pp 86 95 SILVA F V Planejamento autom tico aplicado a problemas dependentes de recursos 2003 Disserta o Mestrado em Ci ncia da Computa o Universidade Federal do Cear Fortaleza 2003 SIMMONS R APFELBAUM D A task description language for robot control In Conference on Intelligent Robotics and Systems 1998 Vancouver Canada Proceedings s n 1998 SMITH D E FRANK J JONSSON A K Bridging the gap between pla
134. nte ao entrar na fase iluminada da rbita e desligado ao sair dela Da 132 mesma forma o comportamento para Night indica que CERTO ligado ao entrar na fase em eclipse e desligado ao t rmino desta fase O comportamento para a janela de comunica o com solo descreve a opera o do sistema de comunica o do sat lite Ao ser ligado este sistema passa a consumir energia e gerar mem ria Esta gera o deve se ao fato de que os dados coletados pelos experimentos est o sendo enviados para solo liberando assim a mem ria utilizada para seu armazenamento Ao t rmino da janela a gera o de mem ria e o consumo de energia pelo sistema de comunica o s o encerrados Como pode ser constatado no Ap ndice A foram adicionadas restri es ao planejador nos comportamentos atrav s de instru es guarantee resource Isso impede que o planejador modifique o plano de forma a retirar recursos de determinados experimentos durante a ocorr ncia das janelas de tempo 7 2 O Cen rio de Testes O cen rio criado para os testes do RASSO engloba um per odo de tr s rbitas Foi assumido que cada rbita tem a dura o de 6000 segundos 100 minutos com fases Dia e Noite de 3000s 50 minutos cada A dura o de cada janela de comunica o que ocorre uma vez a cada rbita de 540s 9 minutos O momento de in cio do cen rio o momento zero O experimento TIP conforme apresentado no item 5 1 2 des
135. nte de forma a executar determinadas atividades Para auxiliar no processo de gera o de planos diversas miss es empregam sistemas computacionais mas estes se limitam a automatizar tarefas simples e repetitivas Eles pouco ajudam no que se refere s considera es que devem ser feitas sobre as intera es entre subsistemas consumo de recursos restri es temporais e outros aspectos operacionais Por isso a gera o dos planos costuma ser um processo basicamente manual e realizado por pessoal altamente qualificado que deve considerar todas as implica es da execu o de cada comando no estado da espa onave Devido a isso existe o interesse de se aplicar t cnicas de planejamento e escalonamento em IA para automatizar a gera o de planos Um dos principais objetivos reduzir o trabalho dos especialistas e consequentemente os custos da miss o O Cap tulo anterior apresentou as principais t cnicas de planejamento e escalonamento em IA Entretanto estas t cnicas raramente s o empregadas de forma pura em aplica es do mundo real Na rea espacial elas costumam ser combinadas em sistemas h bridos para atender s necessidades de cada aplica o espec fica Este Cap tulo apresenta como o planejamento em IA vem sendo estudado e implantado por ag ncias espaciais e institui es a elas vinculadas S o descritos sistemas 2 A partir de agora pelo bem da clareza do texto planejamento e escalonamento e
136. o Processo de Replanejamento Embora tenha atingido todos os objetivos colocados no cen rio pode se ver pela Figura 7 3 que o plano de opera es modificado poderia ser melhor O comando para o desligamento de GROM aos 10143 segundos apenas adianta o desligamento do experimento originalmente previsto para os 10800 segundos Foi notado que apesar de dispor de op es para mover e excluir a es o Planejador sempre 138 decidiu que a inser o de a es teria melhor resultado No caso do desligamento de GROM teria sido mais inteligente mover a a o j existente no plano Outra melhoria poss vel diz respeito aos comandos inseridos aos 12000s para o ajuste de TIP ao estado que lhe foi imposto ao t rmino do plano O planejador n o conseguiu detectar que caso Change Sample Rate tip 1 fosse inserido antes do comando existente no plano original para desligar TIP aos 12000s n o teria sido necess rio inserir novos comandos para relig lo e deslig lo novamente neste mesmo segundo Estas limita es na solu o encontrada podem ser resolvidas futuramente com a inser o de heuristicas no Planejador 7 5 Adequa o do RASSO ao COMAV O cen rio apresentado no item anterior foi executado em uma placa de desenvolvimento com o processador ERC32 de propriedade do Grupo de Supervis o de Bordo SUBORD do INPE O processador foi configurado para trabalhar a uma velocidade de 12MHz pois esta provavelmente
137. o tratados pelo planejador O resultado apresentado novamente ao usu rio e este processo colaborativo segue at que o plano obtido seja considerado satisfat rio O planejamento automatizado provido pelo motor de planejamento EUROPA O MAPGEN utilizado al m do planejamento de opera es di rias para o teste de hip teses simula o de cen rios edi o de planos e an lise do status de recursos atrav s de sua interface gr fica O uso do MAPGEN na miss o MER teve um impacto significativo no tempo de aproveitamento dos jipes Segundo estimativas levantadas em Bresina et al 2005 houve um aumento do retorno cient fico de 20 a 40 em compara o com a miss o Mars Pathfinder Para sua pr xima miss o Marte a Mars Science Laboratory MSL a NASA j est desenvolvendo novos sistemas planejadores com mais recursos agregados Um deles ainda sem nome utiliza visualiza o 3D do terreno onde o jipe se encontra obtida atrav s do processamento de imagens est reo enviadas por ele e uma interface gr fica rica para facilitar a gera o de planos de opera o que envolvam a movimenta o e posicionamento de instrumentos sobre alvos a analisar como rochas por exemplo Pedersen et al 2005 Neste sistema o planejador utilizado o Planning Incrementally for Contingencies PICo que faz uso do motor de planejamento EUROPA II e realiza o que os autores chamam de planejamento de conting ncia on
138. objetivo e vice versa O SNLP Mcallester e Rosenblitt 1991 que definiu um plano como um conjunto de a es parcialmente ordenadas atrav s do uso de restri es de ordena o entre as a es e links causais E o UCPOP Penberthy e Weld 1992 uma extens o do SNLP que trouxe operadores condicionais e implementou satisfa o de restri es para provar a consist ncia dos planos obtidos Mas o grande legado do STRIPS foi a sua forma de descri o de estados e a es que a base para as principais formas de representa o do conhecimento em planejamento criadas at hoje 3 2 2 As Confer ncias na Area de Planejamento Durante as d cadas de 1970 e 1980 a rea de planejamento em IA experimentou uma evolu o lenta mas cont nua Cada novo planejador adicionava novos conceitos e ferramentas implementa o original do STRIPS e isso tornava poss vel sua aplica o a problemas maiores em dom nios mais complexos 47 O aumento do poder do planejamento atraiu um maior interesse para a rea o que levou realiza o em 1990 da International Conference on Expert Planning Systems que dois anos depois se tornou a bienal International Conference on Artificial Intelligence Planning Systems AIPS A partir de 1998 passou a ocorrer dentro da AIPS a International Planning Competition IPC O objetivo desta competi o promover o desenvolvimento de sistemas de planejamento avan ados e incentivar a
139. observa es a serem efetuadas pelo Hubble Estas solicita es s o enviadas ao Space Telescope Science Institute STScl rg o respons vel pelo gerenciamento das atividades do telesc pio Cabe ao STScI determinar quais das observa es solicitadas devem ser efetuadas aplicando crit rios como a import ncia do alvo a observar a reputa o do astr nomo instituto solicitante e a viabilidade da observa o entre outros Uma vez selecionadas as observa es elas devem ser escalonadas da melhor maneira poss vel 74 Cada observa o envolve o apontamento do telesc pio para o alvo e a manuten o deste apontamento por determinado per odo Para efetuar e manter o apontamento em rbita o telesc pio faz uso de seus propulsores cujo propelente um recurso limitado e de dif cil reposi o Logo necess rio encontrar a melhor segii ncia de observa es poss vel efetuando o m nimo de altera es no apontamento poupando assim a reserva de propelente e maximizando a vida til do telesc pio Mas o consumo de propelente n o o nico item a considerar Cada observa o possui uma prioridade atribu da e restri es temporais com rigidez variada Al m disso o uso de instrumentos diferentes altera constantemente o consumo de mem ria energia e aloca o dos links de comunica o com solo Fontes de luz intensa como o Sol a Lua e a pr pria Terra devem ser evitadas e restri es ambientais como a ocorr ncia de
140. on Change Sample Rate action parameters parameter exp parameter new sr double new power 0 new memory 0 when planning condition get current state by id Experiment exp on true condition get current state by id Experiment exp sample rate new sr force state if needed by id Experiment exp on true efeitos descritos a partir daqui set current state by id Experiment exp sample rate new sr switch get current state by id Experiment exp name case certo new power 3 6 new sr new memory 420 98 new sr break case grom new power 12 new sr new memory 711 12 new sr break case ionex if get_current_state IONEX mode full new power 5 4 new sr new memory 189 16 new sr else modo partial new power 3 new sr new memory 95 29 new sr break case mltm new power 14 new sr new memory 264 54 new sr break case tip new power 7 new sr new memory 568 89 new sr 162 break consume resource by id Experiment exp Power new power consume resource by id Experiment exp Mass Memory new memory per min when running printf Changing exp i sample rate to i n exp new sr action success Aplicavel ao CERTO E GROM Recebe new precision como valores discretos 1 2 ou 3 RASSO Action Change Precision
141. operations team in charge of the satellite reconfiguration The necessary time for the phenomenon to be reported and for the ground team to create and send a new operation plan to the satellite is in general much longer than the duration of the phenomenon There is then the need for allowing the experiments when detecting the occurrence of a short duration phenomenon to request from the onboard computer the temporary reallocation of resources This reallocation shall occur in a way that affects the least possible the operation of the other experiments and the satellite itself As the number of states in which the system can be is huge it becomes difficult the use of classical programming techniques to handle it This work proposes the use of Artificial Intelligence Planning and Scheduling techniques to allow the onboard replanning of operations when a short duration scientific phenomenon is detected The main goal is to provide more autonomy to the satellite and consequently more strength to respond to external events It was defined an architecture for an onboard replanning service to be used in INPE s scientific satellites There was the concern for context this architecture in the current INPE s projects for satellites and computers Thus it was developed a prototype based on this architecture implemented for execution in a satellite onboard computer which is being developed at INPE Due to the lack of software tools for this kind of computer
142. oramento global da atmosfera na regi o equatorial enfatizando processos din micos fotoquimicos e mecanismos de transporte de energia entre a baixa m dia e alta atmosfera e a ionosfera FIGURA 5 1 O Sat lite Cient fico EQUARS O conjunto de experimentos cient ficos previsto para o sat lite EQUARS o seguinte e JONEX um sensor de plasma para a medi o de densidade de plasma e temperatura eletr nica e GROM um instrumento baseado na recep o de sinais da constela o GPS para a medi o de umidade temperatura e conte do total eletr nico 100 e CERTO um transmissor de Beacon que ir fazer observa es de irregularidades na ionosfera conte do eletr nico e cintila es e TIP um imageador de luminesc ncia para rel mpagos e sprites e MLTM um imageador de temperatura mesosf rica Os dados a respeito do sat lite e de seus experimentos foram obtidos do website da miss o INPE 2005 e das apresenta es do Primeiro Workshop do EQUARS realizado em novembro de 2001 tamb m dispon veis no website 5 2 Caracter sticas do Problema Escolhido Nas considera es finais sobre o Workshop on Machine Learning Technologies for Autonomous Space Applications realizado durante a vig sima edi o do International Conference on Machine Learning Pavlovic et al 2003 descreve como consenso entre os participantes do workshop que aplica es iniciais com IA embarcada devem ser focadas no valor
143. os obtidos de sua execu o s o apresentados no Cap tulo 7 O Cap tulo 8 traz as conclus es contribui es e trabalhos futuros vislumbrados 31 32 CAP TULO 2 CONTROLE E OPERA O DE SAT LITES CIENT FICOS Neste Cap tulo s o apresentados os conceitos de miss o espacial sua divis o em segmento espacial e segmento solo e a forma de comunica o entre os segmentos A seguir descrita a forma atual de opera o de experimentos cient ficos O Cap tulo encerra apresentando os procedimentos de resposta detec o de fen menos cient ficos em rbita tanto na abordagem atual baseada em decis es tomadas pela equipe de opera es quanto numa abordagem aut noma proposta nesta Disserta o 2 1 Defini o de Miss o Espacial Sistema Espacial e Seus Segmentos De acordo com Wertz e Larson 1999 uma miss o espacial o esfor o para desenvolver e operar um sistema espacial com um objetivo espec fico Este objetivo pode ser o fornecimento de imagens de solo obtidas do espa o a realiza o de experimentos cient ficos em ambientes de microgravidade ou a retransmiss o de dados e voz em sistemas de telecomunica o Um sistema espacial dividido em dois segmentos o segmento espacial e o segmento solo O segmento espacial consiste da espa onave em si no caso do INPE do sat lite outros exemplos s o sondas space shuttles etc que por sua vez composta por plataforma e carga til Ainda conforme a
144. ot tipo forne a meios de aumentar gradativamente a confian a do pessoal da miss o com rela o ao incremento da autonomia Para isso ele deve possuir um conjunto de caracter sticas que visem auxiliar o processo de aceita o desta tecnologia em miss es reais e Alto n vel de integra o ao restante do software embarcado o replanejamento deve ser tratado como apenas mais um servi o provido pelo computador de bordo tal qual o processamento de telemetria ou tarefas de housekeeping e diagnose e Modos de execu o que permitam uma implanta o gradual do sistema baseada no aumento da confian a com rela o aos resultados obtidos 29 e Uma forma de representa o do conhecimento que facilite o entendimento por parte dos engenheiros de miss o do processo de decis o do sistema mesmo que eles n o possam prever com exatid o a resposta gerada para cada situa o apresentada ao sistema 1 3 Metodologia de Trabalho e Organiza o Desta Disserta o Este trabalho foi iniciado com o estudo da forma de opera o atual de sat lites do INPE em especial dos sat lites cient ficos O resultado deste estudo descrito no Cap tulo 2 desta Disserta o A seguir foi realizado um levantamento da bibliografia existente na rea de Planejamento e Escalonamento em IA e um estudo de diversos sistemas planejadores e das t cnicas que eles utilizam Uma vis o geral de planejamento e sistemas planejadores apresent
145. ous rover science through dynamic planning and scheduling In IEEE AEROSPACE CONFERENCE 2005 Big Sky MT USA Proceedings Big Sky IEEE 2005 FIKES R E NILSSON N J STRIPS a new approach to the application of theorem proving to problem solving Artificial Intelligence v 2 n 3 4 pp 189 208 1971 FRANK J JONSSON A K Constraint based attribute and interval planning Constraints v 8 n 4 pp 339 364 Oct 2003 FRATINI S CESTA A A planning and scheduling tool to automate and support mission planning In INTERNATIONAL CONFERENCE ON SPACE OPERATIONS SPACEOPS 9 2006 Rome Italy Proceedings Rome AIAA 2006 152 FUCHS J GULDBERG J OLALAINTY B DARROY J M CURRIE K Final report expert planning systems study Technical Report EP CRI FR 0001 1988 CRI 1988 FUCHS J J GASQUET A OLALAINTY B CURRIE K W PlanERS 1 an expert planning system for generating spacecraft mission plans In INTERNATIONAL EXPERT PLANNING SYSTEMS CONFERENCE 1 1990 London England Proceedings Brighton Institute of Electrical Engineers 1990 pp 70 75 FUKUNAGA A RABIDEAU G CHIEN S YAN D Towards an application framework for automated planning and scheduling In INTERNATIONAL SYMPOSIUM ON ARTIFICIAL INTELLIGENCE ROBOTICS AND AUTOMATION IN SPACE I SAIRAS 4 1997 Tokyo Japan Proceedings Tokyo NASDA 1997 HALSEY K LONG D FOX M CRIKEY a temporal planner looking at the
146. para o software embarcado na espa onave consenso entre os pesquisadores da rea que as espa onaves ser o cada vez mais aut nomas Um levantamento recente sobre os sistemas de execu o de comandos em espa onaves e rob s da NASA Verma et al 2005 destaca que medida que as miss es tornam se mais complexas a autonomia torna se cada vez mais importante para o sucesso destas miss es Em Teston et al 1997 argumenta se que esperado para um futuro pr ximo que atividades de opera o de miss es evoluam do controle baseado em solo para monitoramento e controle embarcado e que no futuro fun es mais complexas ser o gradualmente migradas para o computador embarcado As atividades baseadas em solo de opera o de espa onaves por humanos ser o limitadas essencialmente fase de inicializa o da miss o e suporte de emerg ncia Com o objetivo de aumentar a autonomia de suas futuras espa onaves a NASA realizou dois experimentos de planejamento embarcado nos ltimos anos Estes experimentos lhes deram subs dios para iniciar o desenvolvimento de sistemas ainda mais complexos com metas mais ambiciosas Os pr ximos itens apresentam o que foi realizado e o que vem sendo desenvolvido na rea de planejamento embarcado 89 4 3 1 As Experi ncias Realizadas com Planejamento Embarcado A primeira miss o a aplicar planejamento embarcado foi a sonda Deep Space One DS 1 da NASA em 1999 Jon
147. parada e ao t rmino do tempo de planejamento a melhor solu o encontrada apresentada 82 O ASPEN foi utilizado em diversas miss es Rabideau et al 1999 destaca o sat lite de comunica es navais UHF Follow On One UFO 1 o sat lite de sensoriamento remoto Earth Observing One EO 1 e o sat lite universit rio Citizen Explorer One CX 1 O ASPEN tamb m possui uma vers o embarcada a ser apresentada ainda neste Cap tulo Mas o ASPEN n o a nica iniciativa da NASA para desenvolver uma ferramenta de planejamento de uso geral O Ames Research Center desenvolveu seu pr prio sistema para atingir este objetivo o Extensible Universal Remote Operations Planning Architecture EUROPA Frank e Jonsson 2003 A id ia por tr s do EUROPA foi criar um sistema de planejamento plug amp play que pudesse ser facilmente integr vel a outros sistemas e encapsulasse toda a l gica de planejamento e escalonamento sem deixar de ser extens vel para cada miss o a que fosse aplicado Assim como o ASPEN herdou o legado de outras aplica es de planejamento do JPL o EUROPA foi desenvolvido sobre os planejadores HSTS e RAX PS que ser descrito ainda neste Cap tulo ambos do Ames Ele implementa planejamento e escalonamento baseado em restri es e integrado s aplica es como um conjunto de bibliotecas em C No EUROPA um dom nio modelado atrav s de atributos intervalos regras de intera o e re
148. pera o em modos degradados de funcionamento Com o passar do tempo os equipamentos dos sat lites apresentam falhas e a forma de oper los deve ser adaptada para lidar com estas falhas Um sistema de replanejamento embarcado em um sat lite que apresente falhas pode ajudar a equipe em solo a descobrir novas formas de operar o sat lite Para isso ele receberia como objetivos fazer o mesmo que faria se n o apresentasse falha alguma As falhas seriam ent o inseridas no problema como restri es impostas o que for aria o planejador a buscar formas alternativas para atingir seus objetivos 8 3 Considera es Finais dif cil mudar a vis o predominante na rea t cnica na qual se espera total previsibilidade dos sistemas embarcados para uma vis o que aceite o comportamento de um sistema aut nomo A realiza o de estudos e o desenvolvimento de prot tipos com o objetivo de aumentar a autonomia de sat lites permitem uma melhor compreens o das t cnicas utilizadas com seus pontos fortes e fracos 144 A melhor compreens o destas t cnicas leva a uma defini o clara dos limites a serem impostos para sistemas aut nomos e em que n vel a autonomia pode ser aplicada ao ambiente espacial 145 146 REFER NCIAS BIBLIOGR FICAS AARUP M ARENTOFT M M PARROD Y STADER J STOKES I Optimum AIV a knowledge based planning and scheduling system for spacecraft AIV Knowledge Based Scheduling Fox M and Zweb
149. perimentos podem ser ativados e desativados automaticamente por sensores solares sem que haja comandos liga desliga agendados para execu o Embora o software seja notificado de que o experimento foi ligado desligado a informa o de quando isso ocorrer futuramente n o se encontra a bordo do sat lite o que vital para o processo de planejamento Para lidar com eventos ex genos como os descritos acima o RASSO faz uso do conceito de janelas de tempo Janelas de tempo s o per odos nos quais o sat lite apresenta determinado comportamento caracter stico que n o pode ser modificado pelo planejador Por exemplo durante o per odo em que o sat lite se encontra em contato com uma esta o de rastreio em solo ele transmite os dados armazenados dos experimentos liberando assim mem ria de massa Tamb m consome mais energia pois seu sistema de comunica o est ativo Janelas de tempo podem ser consecutivas ou podem se sobrepor umas s outras nenhuma restri o quanto a isso feita pelo RASSO e n o h obrigatoriedade da ocorr ncia de uma janela de tempo em todas as rbitas O RASSO possui uma Tabela 115 de Janelas de Tempo que armazena os momentos de in cio e t rmino da ocorr ncia de cada janela para todas as rbitas nos pr ximos dias Estes dados devem ser atualizados regularmente pela equipe de opera es em solo Usando esta informa o a ocorr ncia das janelas vinculada aos comportamentos
150. pesquisa competitiva Na IPC os planejadores s o aplicados a problemas previamente definidos pelos organizadores da competi o e comparados em termos do n mero de problemas resolvidos do tempo total para a solu o dos problemas e do tamanho dos planos gerados A AIPS e a IPC trouxeram avan os significativos para a pesquisa em planejamento como uma maior troca de experi ncias entre grupos de pesquisa e a cria o da linguagem de representa o de dom nios Planning Domain Definition Language PDDL al m de terem aumentado ainda mais o interesse de pesquisadores de TA pela rea Prova disso foi a uni o do AIPS com a European Conference on Planning EPC que vinha sendo realizada tamb m bienalmente desde 1991 o que resultou na International Conference on Automated Planning and Scheduling ICAPS um evento ainda maior de realiza o anual a partir de 2003 3 2 3 Planejamento Baseado em Satisfatibilidade Satisfatibilidade Proposicional SAT o problema de se determinar para uma dada express o booleana composta por n elementos vari veis se existe algum conjunto de atribui es de verdadeiro e falso para os elementos que torne a express o verdadeira Cook e Mitchell 1997 Proposto por Kautz e Selman 1992 o planejamento baseado em satisfatibilidade implementado originalmente no planejador SATPLAN trouxe a formaliza o de problemas de planejamento como conjuntos de cl usulas proposicionais A satisfa
151. pila o do GCC 111 6 2 1 A Descri o Est tica do Modelo A parte est tica do modelo composta basicamente por objetos e recursos Objetos s o elementos instanciados a partir de classes que tamb m s o definidas no modelo e que possuem atributos de qualquer tipo aceito pelo C O conjunto de valores dos atributos de um objeto em dado instante chamado de estado do objeto Recursos s o os elementos consum veis do modelo Eles podem ser consumidos pelos objetos ou renovados em fun o do tempo sem v nculo a objetos H dois tipos de recursos no RASSO os consum veis chamados de depletable e os reserv veis reservable Ambos os tipos possuem quantidades m nima e m xima definidas em sua cria o e estas quantidades n o podem ser excedidas em momento algum A diferen a entre eles que enquanto os recursos consum veis acumulam seu gasto no tempo at serem esgotados e s s o renovados por instru es espec ficas os reserv veis s o controlados de forma moment nea sem ac mulo e s o repostos assim que um objeto p ra de os consumir Durante a opera o de um experimento por exemplo s o consumidos mem ria e energia A mem ria consumida aos poucos conforme o experimento coleta e armazena dados a cada minuto haver menos mem ria dispon vel at que os dados sejam transmitidos para solo e a mem ria seja liberada Mem ria um recurso do tipo consum vel J a en
152. r French Brazilian Microsatellite Formula Normal Conjuntiva GNU Cross Compiler GNU General Public License Ground Processing Scheduling System Heuristic Search Planner Heuristic Scheduling Testbed System Intelig ncia Artificial International Conference on Automated Planning and Scheduling Instituto Nacional de Pesquisas Espaciais International Planning Competition Jet Propulsion Laboratory Multi Agent Ground operation Automation Mixed initiative Activity Plan GENerator MECB MER MIRAX MSL NASA OAR OCL OMPS OO PDDL PICo PlanIPOV PNAE PO PST RASSO RASSO ml RAX PS RTEMS SACI SCD Miss o Espacial Completa Brasileira Mars Exploration Rovers Monitor e Imageador de Raios X Mars Science Laboratory National Aeronautics and Space Administration Online Applications Research Corporation Object Centered Language Open Multi CSP Planner and Scheduler Orienta o a Objetos Planning Domain Definition Language Planning Incrementally for Contingencies Planejamento Inteligente de Planos de Opera o de V o Programa Nacional de Atividades Espaciais Pesquisa Operacional Planning and Scheduling Team Resources Allocation Service for Scientific Opportunities RASSO modeling language Remote Agent Experiment RAX Planner Scheduler Real Time Executive for Multiprocessor Systems Sat lite de Aplica es Cient ficas Sat lite de Coleta de Dados SCE SNLP SPIKE SPSS STRIPS STScl SUBOR
153. r frameworks gen ricos de planejamento em solo que pudessem ser reaproveitados em diferentes miss es Os produtos disso foram o ASPEN e o EUROPA O mesmo vem acontecendo agora com o planejamento embarcado Ap s os bem sucedidos experimentos RAX e ASE a NASA vem trabalhando em frameworks embarcados que inserem os planejadores j existentes em pacotes de autonomia Estes pacotes concentram as funcionalidades necess rias detec o e resposta a eventos externos como a ocorr ncia de fen menos cient ficos em rbita ou o encontro com um obst culo inesperado durante a travessia de um terreno alien gena Um destes novos frameworks o Intelligent Distributed Execution Architecture IDEA Muscettola et al 2002 O IDEA uma re implementa o do RAX PS que emprega o EUROPA como motor de planejamento Ele tem como objetivo prover um ciclo completo para sentir planejar agir com resposta em tempo real na ordem de milissegundos para cada ciclo Isso possibilitado atrav s do conceito de planejamento reativo onde partes de um plano s o liberadas para execu o sem que o plano esteja completo O resultado do trecho do plano executado lido por sensores e realimentado no processo de planejamento que gera com isso um novo trecho do plano a executar Assim o 94 planejador reage aos efeitos das partes de seu plano j executadas adaptando se aos novos estados lidos Um plano gerado desta forma n o ti
154. ras devem ser respeitadas 1 Deve se mover apenas um bloco por vez 2 Podem ser movidos apenas blocos que n o estejam sob nenhum outro bloco A definig o de uma ac o aplic vel a este problema em STRIPS mover bloco de para PRE sobre bloco de livre bloco livre para ADD sobre bloco para livre de DEL sobre bloco de livre para O algoritmo do STRIPS seleciona um dos literais do objetivo e aplica sequ ncias de a es ao estado inicial at atingir um estado que contenha este literal Ent o seleciona o pr ximo literal do objetivo e repete o processo at encontrar um estado que contenha todos os literais do estado objetivo 46 Diversos outros planejadores foram baseados nos conceitos do STRIPS dentre os quais podem ser destacados O ABSTRIPS Sacerdoti 1974 que trouxe a primeira abordagem de planejamento hier rquico adicionando prioridades aos operadores de pr condi o das a es do STRIPS Estas prioridades eram usadas para gerar um esbo o de plano uma abstra o que resolvia todas as pr condi es de maior n vel Na seq ncia as prioridades do n vel imediatamente inferior eram resolvidas e o processo seguia at a obten o de um plano com todas as pr condi es resolvidas O PRODIGY Minton et al 1989 que adicionou a regress o encadeada de estados podendo assim realizar uma busca em profundidade em ambos os sentidos do estado inicial ao
155. re a esta o terrena ou em alguma outra passagem futura este alerta enviado para a equipe de opera es 4 a O sat lite segue operando da forma previamente estabelecida enquanto o pessoal da miss o encaminha o alerta para o cientista respons vel de forma rotineira junto aos dados de seu experimento Informado da ocorr ncia o cientista entra em contato com o pessoal de miss o e solicita modifica es no modo de opera o de seu experimento maior tempo ligado mais mem ria para armazenar dados coletados etc Esta solicita o ser analisada e caso seja aceita ser criado um novo plano de opera es com telecomandos para alterar a configura o do sat lite 5 a O novo plano ent o enviado para o sat lite e colocado em execu o 6 a O sat lite j reconfigurado inicia as observa es com maior quantidade de recursos dedicados ao experimento que fez a detec o inicial Entretanto devido ao tempo transcorrido desde o in cio do processo poss vel que o fen meno n o esteja mais se manifestando Nota se que este processo pode levar dias e seguro supor que o cientista ao receber o alerta da detec o do fen meno ir apenas lamentar a oportunidade perdida Um sistema aut nomo embarcado no sat lite com a capacidade de efetuar a reconfigura o necess ria estaria em condi es de dar uma resposta satisfat ria Trabalhando dentro de 41 uma margem de manobra aceit vel e por
156. recente s rie de miss es Marte a miss o Mars Pathfinder da NASA lan ou o jipe Sojourner sobre a superf cie do planeta em 1997 Apesar do grande feito que foi operar remotamente o jipe atrav s do terreno marciano um levantamento posterior destacou que o jipe gastava entre 40 e 75 de seu tempo sem realizar atividade alguma devido falhas nos planos que lhe eram enviados Bresina et at 2002 Para lidar com este problema a miss o seguinte da NASA para Marte a Mars Exploration Rovers MER que pousou em 2004 dois novos jipes batizados de Spirit e Opportunity analisou o uso da tecnologia de planejamento em IA Embora tenham considerado a tecnologia de planejamento embarcado que seria mais adequada a este tipo de miss o ainda n o madura o suficiente para uma miss o deste porte foi aberta uma oportunidade para o desenvolvimento de planejadores automatizados executados em solo Isto levou ao desenvolvimento de um sistema planejador de iniciativa mista chamado Mixed initiative Activity Plan GENerator MAPGEN Ai Chang et al 2004 Por iniciativa mista entenda se que o MAPGEN interage com os especialistas da miss o na cria o de planos de opera o para os jipes exploradores A partir de um esbo o de 84 plano o MAPGEN gera um plano v lido e o apresenta ao usu rio que pode efetuar quaisquer modifica es que julgar necess rias Estas modifica es podem inserir novos conflitos no plano que s
157. riar objetos e recursos na verdade est se criando hist ricos para eles Estes hist ricos s o implementados por vetores que armazenam as modifica es sofridas pelos objetos e recursos durante o decorrer do plano Os hist ricos s o chamados de linha do tempo timeline para objetos veja a macro para a instru o 117 create object na Figura 6 2 e perfis de consumo profiles para recursos e s o tratadas de forma diferente como ser visto nos pr ximos itens 6 2 3 1 Manipulando Objetos no Tempo Toda vez que uma a o ou comportamento modifica um atributo do objeto seu novo estado armazenado no timeline com uma refer ncia a o respons vel pela mudan a no estado A Figura 6 6 ilustra o timeline para um objeto MLTM que representa um dos experimentos do sat lite timeline MLTM name onex ionex on true false mode full sample rate precision 1 priority 1 2 objeto 1 a a o nr 2 no plano desligou MLTM FIGURA 6 6 Exemplo de um timeline no RASSO Na Figura 6 6 nota se que a a o identificada pelo plan id 2 teve como efeito o desligamento do experimento atributo on false em negrito Por serem armazenados em timelines necess rio que se informe com qual momento do objeto se deseja trabalhar ao obter ou modificar seus atributos Para isso foram criadas instru es espec ficas para a manipula o de objetos no tempo Alg
158. rnativos podem estar dispon veis cada qual trazendo diferente custo e ou dura o associadas Dado que problemas de escalonamento podem envolver escolhas entre recursos e mesmo entre processos alternativos o que os distingue dos problemas de planejamento A diferen a sutil enquanto h nos problemas de planejamento um grande n mero de a es a escolher e complexas intera es entre elas os problemas de escalonamento possuem poucas op es de a o mas trazem maiores restri es quanto ordena o das a es Em um problema de escalonamento dado um conjunto de tarefas definidas onde algumas delas podem ser opcionais e algumas podem permitir processos alternativos simples Em um problema de planejamento usualmente n o se sabe ao menos quantas tarefas ou a es s o necess rias para se atingir os objetivos A pesquisa em escalonamento se originou na rea de Pesquisa Operacional PO e vem sendo modificada e incorporada Intelig ncia Artificial notadamente na ltima d cada O que distingue a pesquisa em escalonamento da rea de PO daquela da rea de IA que em IA o foco tende a ser em formas gerais de representa o e em t cnicas que cubram diferentes tipos de problemas de escalonamento Em PO o foco encontra se geralmente no desenvolvimento de t cnicas para o processamento otimizado de classes espec ficas de problemas 61 Em IA a abordagem mais comum para a solu o de problemas de escalonam
159. s Rome ATAA 2006 CARDOSO L S Aplica o da tecnologia de agentes de planejamento em opera es de sat lites 2006 Disserta o Mestrado em Computa o Aplicada Instituto Nacional de Pesquisas Espaciais INPE S o Jos dos Campos 2006 CARVALHO H EQUARS system architecture S o Jos dos Campos INPE EQUARS Workshop Nov 2001 149 CESTA A CORTELLESSA G ODDI A POLICELLA N Studying decision support for MARS EXPRESS planning tasks a report from the MEXAR experience In INTERNATIONAL WORKSHOP ON PLANNING AND SCHEDULING FOR SPACE 4 2004 Darmstadt Germany Proceedings Darmstadt ESA ESOC 2004 CESTA A ODDI A CORTELLESSA G FRATINI S POLICELLA N AI based tools for continuous support to mission planning In INTERNATIONAL CONFERENCE ON SPACE OPERATIONS SPACEOPS 9 2006 Rome Italy Proceedings Rome AIAA 2006 CHIEN S MUSCETTOLA N RAJAN K SMITH B RABIDEAU G Automated planning and scheduling for goal based autonomous spacecraft IEEE Intelligent Systems v 13 n 5 pp 50 55 1998 CHIEN S KNIGHT R STECHERT A SHERWOOD R RABIDEAU G Using iterative repair to increase the responsiveness of planning and scheduling for autonomous spacecraft In INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE IJCAD 16 1999 Stockholm Sweden Proceedings Stockholm Morgan Kaufmann 1999 CHIEN S ENGELHARDT B KNIGHT R RABIDEAU G SHERWOOD R
160. s Isso d ao sat lite maior poder de resposta e possibilita o uso otimizado de seus recursos A seguir s o apresentadas as principais contribui es deste trabalho os trabalhos futuros vislumbrados e outras aplica es poss veis para esta tecnologia dentro do INPE 8 1 Principais Contribui es Diversas contribui es podem ser destacadas neste trabalho sendo que as principais seguem listadas abaixo Para o INPE este trabalho contribui trazendo um primeiro estudo da aplica o de t cnicas de Planejamento e Escalonamento em IA embarcadas em sat lites dentro do contexto espec fico do Instituto Isso possibilita a an lise da viabilidade do uso destas t cnicas seja para a aplica o em sat lites cient ficos seja para qualquer outra aplica o embarcada em sat lites Nas pesquisas realizadas para esta Disserta o n o foi encontrado na literatura nenhum trabalho que reunisse informa es sobre os sistemas planejadores com IA na rea espacial Todos os dados encontrados vieram de artigos descrevendo sistemas espec ficos contendo no m ximo compara es pontuais com um ou dois outros 141 planejadores Para aqueles interessados no estudo da automatiza o e autonomia de miss es espaciais com o uso de Planejamento e Escalonamento em IA o Cap tulo 4 apresenta uma revis o dos sistemas desenvolvidos e em desenvolvimento na rea assim como das atuais tend ncias Para os envolvidos com planejamento
161. s de sensoriamento remoto chamados China Brazil Earth Resources Satellites INPE 2003 Hoje os dados e imagens gerados pelos sat lites CBERS 1 e 2 s o consumidos diariamente por centenas de usu rios nas mais diversas reas de atua o dentro e fora do pa s Outros tr s sat lites da s rie CBERS encontram se atualmente em etapas diversas de desenvolvimento Al m dos programas de sat lites de coleta de dados e de sensoriamento remoto o INPE possui tamb m o programa de Sat lites Cient ficos e Experimentos INPE 2006 do qual fizeram parte os Sat lites de Aplica es Cient ficas SACI 1 e 2 e o French Brazilian Microsatellite FBM em parceria com o Centre National d Etudes Spatiales CNES franc s O objetivo destas miss es prover acesso freqiiente e de baixo custo 25 ao espa o para a comunidade cient fica brasileira bem como serem plataformas para testes de novas tecnologias e equipamentos para uso espacial que possam ser futuramente incorporadas em programas de maior vulto como o caso do CBERS Os pr ximos sat lites previstos para o SCE s o o Equatorial Atmosphere Research Satellite EQUARS e o Monitor e Imageador de Raios X MIRAX ambos atualmente em desenvolvimento Os sat lites do programa SCE possuem como carga til um conjunto de experimentos cient ficos e tecnol gicos cujo controle se baseia em modos de opera o pr definidos e na execu o de telecomandos temporizados Estes s o
162. s de predicados Em STRIPS uma a o definida em fun o dos operadores de pr condi o PRE de adi o ADD e de elimina o DEL Os operadores PRE s o um conjunto de literais que se estiverem presentes no estado atual permitem a aplica o da a o ao estado Os operadores ADD s o um conjunto de literais que s o adicionadas ao pr ximo estado ap s a aplica o da a o ao estado atual Finalmente os operadores DEL s o um conjunto de literais que devem ser removidas no pr ximo estado ap s a aplica o da a o ao estado atual Al m da representa o das a es STRIPS descreve o problema como conjuntos de predicados que definem seus estados inicial e objetivo A Figura 3 2 traz um exemplo da representa o em STRIPS para o problema do mundo dos blocos que definido a seguir 45 Estado Inicial S Estado Objetivo S C So sobre A A sobre C mesa Sp A sobre B mesa Sp livre A So livre B So 0 mesa FIGURA 3 2 Descri o de um Problema em STRIPS O problema do mundo dos blocos um problema cl ssico da rea de IA e ser utilizado como exemplo em alguns pontos deste trabalho Para o problema assume se uma mesa com blocos identificados de forma nica empilhados uns sobre os outros num determinado n mero de colunas O objetivo do problema rearranjar os blocos de forma a se obter determinada configurac o Para atingir este objetivo as seguintes reg
163. s defini es de Wertz e Larson a plataforma de um sat lite possui equipamentos que d o suporte opera o das cargas teis tais como estrutura energia computador de bordo e outros a plataforma a respons vel pelo monitoramento opera o e manuten o do sat lite em rbita e pela comunica o com as esta es terrenas de rastreio e com a carga til A carga til a parte dedicada aplica o ou seja ao motivo pelo qual o sat lite foi lan ado E ela que gera os dados da miss o Em um sat lite de sensoriamento remoto por exemplo a carga til composta por c meras e outros sensores Em um sat lite cient fico por experimentos cient ficos e tecnol gicos 33 O segmento solo composto pelas esta es terrenas bem como por toda a infra estrutura e pessoal envolvidos nas opera es de monitoramento e manuten o do sat lite e de disponibiliza o dos produtos do sat lite imagens dados cient ficos etc aos seus usu rios A Figura 2 1 ilustra os segmentos espacial solo os usu rios da miss o e suas intera es Ga pi Segmento Solo solicita es dos usu rios Suporte ao Sat lite comandos e Carga Util Segmento Espacial Recep o e satelite Disponibiliza o dos i Dados da Miss o i FIGURA 2 1 Intera o entre os Segmentos Solo e Espacial e os Usu rios da Miss o Usu rios da Miss o dados da miss o Fonte adaptada de Wertz e Larson 1999 p 623 2
164. ser a velocidade utilizada no COMAV O processo de replanejamento descrito nos itens anteriores levou 114 28 segundos para ser executado fazendo uso total do tempo do processador Deste per odo a inicializa o do sistema do modelo e a composi o do problema levaram apenas 0 07 segundo para serem completados O execut vel do prot tipo do RASSO com seu modelo e o sistema operacional RTEMS inclusos ocupa 182 68 kbytes em mem ria de programa Descontando o RTEMS que faz parte do COMAV o RASSO e seu modelo compilado possuem 79 96 kbytes de tamanho O tempo de replanejamento e o tamanho da aplica o mostram que o prot tipo do RASSO est adequado para execu o em computadores de bordo dos sat lites do INPE 139 A implementa o do prot tipo do RASSO gerou 3626 linhas de c digo fonte com coment rios descontadas as linhas em branco das quais 913 comp em a defini o da linguagem RASSO ml e 321 fazem parte do modelo do sat lite 140 CAP TULO 8 CONCLUS O O desenvolvimento de um prot tipo de servi o de replanejamento embarcado pode ser considerado um primeiro passo no sentido de aumentar a autonomia do software embarcado nos futuros sat lites do INPE O prot tipo desenvolvido neste trabalho traz os conceitos de planejamento e escalonamento da rea de IA para os sistemas embarcados em sat lites do INPE de forma a permitir o replanejamento aut nomo de opera es em resposta a eventos externo
165. sson et al 2000 Isso ocorreu como parte do Remote Agent Experiment RAX uma demonstra o de planejamento com execu o em ciclo fechado closed loop infer ncia de estados baseada em modelo e recupera o de falhas A sonda DS 1 fez parte do programa New Millennium de valida o tecnol gica para futuras aplica es espaciais da NASA Sua miss o era executar passagens sobre alguns alvos Marte um aster ide e um cometa e efetuar observa es durante elas A principal tecnologia validada pela DS 1 foi seu sistema de propuls o i nica mas diversas outras foram testadas como o RAX O experimento foi desenvolvido pelo Ames Research Center com colabora o do JPL e o planejador chamado RAX Planner Scheduler RAX PS basicamente uma vers o embarcada do HSTS Assim como o HSTS o RAX PS gera planos temporalmente flex veis deixando a cargo de um sistema executor inteligente selecionar os momentos exatos de execu o de cada tarefa A Figura 4 2 apresenta a arquitetura do RAX PS PE Planning Engine O Planning Search OT Heuristics Ep Engine de ee o Domain Model Knowledge base q Goals Plan Plan Database Initial state FIGURA 4 2 A Arquitetura do RAX PS Fonte Jonsson et al 2000 p 1 90 O modelo de dom nio domain model na Figura 4 2 descreve a din mica do sistema para o qual o planejador est sendo aplicado no caso da sonda DS 1 Uma solicita o de plano consisti
166. stri es de dom nio Um atributo descreve um componente do dom nio como um subsistema ou equipamento de um sat lite Cada atributo representa uma linha do tempo concorrente descrevendo sua hist ria atrav s de uma seq ncia de estados e atividades Este conceito similar ao das linhas do tempo aplicadas s vari veis de estado do HSTS Um intervalo descreve um per odo em que um atributo deve manter determinado valor As regras de intera o s o aplicadas s atividades e verificam atributos para definir como subsistemas interagem entre si As restri es de dom nio s o impostas manuten o de valores de atributos em determinados intervalos Ao contr rio do 83 ASPEN n o h uma forma de representar recursos explicitamente embora seja poss vel faz lo de forma indireta com o uso de atributos O EUROPA vem sendo usado em algumas aplica es de planejamento com sucesso e foi estendido em uma segunda vers o EUROPA II Pedersen et al 2005 Nestas aplica es ele comumente chamado de motor de planejamento planning engine 4 2 5 Planejamento em Miss es de Explora o de Marte Nos ltimos anos tem se observado um aumento nas miss es de explora o de Marte Estas miss es t m proporcionado diversas descobertas sobre a geologia e a hist ria do planeta vermelho seja atrav s de observa es realizadas por sondas orbitadoras ou de dados coletados por jipes exploradores Iniciando a
167. struturas de dados antes de serem utilizados pelo planejador No caso de um planejador embarcado as op es para lidar com a terceira limita o acima seriam converter o modelo antes de compilar a aplica o ou adicionar um parser 104 ao software do sat lite Tendo em vista que um dos objetivos deste trabalho buscar a integra o entre o planejamento embarcado e o restante do software do sat lite qualquer solu o que traga mais trabalho ao desenvolvedor como uma convers o do modelo antes da compila o do software deve ser evitada Torna se desej vel ent o o uso da pr pria linguagem de programa o para descrever o modelo do dom nio Alguns dos motivos para isso s o listados abaixo e Qualquer linguagem de programa o de alto n vel j possui recursos avan ados de condicionais sele o de casos e loops que faltam s linguagens de descri o de dom nios para planejamento como a PDDL e Outros recursos de linguagens de programa o como chamadas a fun es e o uso de ponteiros podem se bem utilizados prover ferramentas de grande valor para o processo de planejamento e O uso de estruturas de dados structs para descrever elementos do dom nio leva os modelos de planejamento mais pr ximos Orienta o a Objetos do que a linguagem OCL por exemplo permite Isso se deve ao fato de que os structs foram os precursores dos objetos tal qual eles s o conhecidos em OO Entre as formas de
168. t lite Estes comandos podem ser para ligar ou desligar equipamentos mudar modos de opera o de subsistemas carregar novos par metros de funcionamento etc Devido ao tempo limitado de comunica o com o sat lite necess rio prover meios de executar 35 comandos a qualquer momento durante sua rbita Para isso existem dois tipos de telecomandos os imediatos e os temporizados Os telecomandos imediatos devem ser executados assim que s o recebidos pelo sat lite Exemplos destes comandos s o a sincroniza o do rel gio interno do sat lite com o de solo o carregamento de novos programas ou comandos emergenciais para a corre o de anomalias ou recupera o de modos de erro Os telecomandos temporizados cont m um campo com uma refer ncia temporal indicando ao software do sat lite quando eles devem ser executados Ao serem recebidos eles s o armazenados numa estrutura de dados chamada fila de telecomandos temporizados Esta fila verificada regularmente e os comandos l contidos s o encaminhados para execu o nos seus devidos momentos O conjunto de telecomandos temporizados armazenados nesta fila comp e o plano de opera es corrente do sat lite 2 3 Modos de Opera o de Experimentos Cient ficos Os experimentos cient ficos podem ter como objetivo a observa o de fen menos internos ou externos ao sat lite No primeiro caso eles realizam an lises de seus objetos de estudo em ambiente cont
169. t nomos Os motivos para isso variam desde a necessidade de redu o do tempo de resposta de espa onaves a eventos externos at a dificuldade em manter equipes de operadores qualificados dispon veis em tempo integral o que encarece a opera o das miss es Entretanto o aumento da autonomia traz como custo uma demanda por maior poder computacional embarcado Apesar de ser tentador pensar que problemas de desempenho do software embarcado ser o resolvidos em um futuro pr ximo por processadores mais r pidos isso nem sempre verdade Uma an lise mais cuidadosa mostra que conforme o poder de processamento aumenta tamb m aumenta a demanda por seu consumo devido implementa o de novas aplica es e de melhorias nas aplica es existentes Outro problema com rela o ao aumento da autonomia vem da cren a de que todas as decis es tomadas pelos sistemas embarcados em sat lites devem ser absolutamente previs veis Saber exatamente como um sistema ir se comportar em cada uma das situa es que lhe forem apresentadas aumenta a seguran a com rela o sua robustez mas reduz o n mero de situa es s quais o sistema poder gerar uma resposta adequada A escolha deste trabalho de pesquisa foi motivada pela necessidade de se conciliar o aumento da autonomia de sat lites com as restri es de poder computacional embarcado garantindo ainda um n vel aceit vel de confiabilidade e previsibilidade quanto s respostas do
170. tais Entretanto recentemente a necessidade de se trabalhar com recursos e tempo em planejamento imp s um grande desafio para este tipo de representa o o que vem motivando o estudo de novas formas de modelagem como o uso de t cnicas inspiradas na Orienta o a Objetos item 3 3 4 deste trabalho 3 3 2 Relaxando as Restri es do STRIPS A Action Description Language ADL Pednault 1989 uma extens o ao STRIPS foi criada em 1989 com a id ia de tornar a forma de representa o do STRIPS menos r gida permitindo descrever modelos mais complexos Assim a ADL adicionou a disjun o em pr condi es condicionais em efeitos e quantifica o universal tanto nas pr condi es quanto nos efeitos Um exemplo do aumento da capacidade de modelagem dos novos recursos da ADL que passou a ser poss vel descrever express es como a localiza o de todas as caixas Es a w 1 em um caminh o muda quando a localiza o do caminh o mudar A ado o da ADL por diversos planejadores tornou a o mais pr ximo de um padr o para modelagem de dom nios que a rea de planejamento teve at ent o Um dos mais conhecidos planejadores a utilizar a ADL foi o UCPOP Penberthy e Weld 1992 que tamb m permitia o planejamento de ordem parcial onde h instru es sobre como as a es em um plano devem ser ordenadas Neste exemplo se usaria o recurso da quantifica o para representar todas as caixas 55
171. tas que lhe foram originalmente alocadas Seguindo a forma de opera o atual tudo o que o experimento pode fazer ao detectar o fen meno disparar um alerta para solo relatando a ocorr ncia e seguir operando em seu modo normal at que a equipe de opera es em solo envie uma resposta ao alerta que reconfigure o sat lite apropriadamente para sua observa o 39 Um sistema capaz de reconfigurar o sat lite sem interfer ncia de solo poderia dar uma resposta imediata detec o A Figura 2 3 ilustra as etapas da detec o sua resposta tanto da abordagem atual dependente das decis es do pessoal da miss o quanto de uma abordagem aut noma proposta nesta Disserta o Cada etapa identificada na figura e descrita a seguir a sat lite em rbita esta o terrena de rastreio GS fen meno detectado Reconfigurac o Reconfigura o Manual por solo Aut noma 3 a O O gt O 6 a FIGURA 2 3 Diferentes Respostas Detec o de Fen menos Cient ficos 40 Segue uma descri o detalhada de ambas as abordagens 1 O sat lite encontra se em rbita operando conforme o programado em modo normal de opera es 2 Um de seus experimentos detecta a ocorr ncia de um fen meno cient fico de curta dura o de interesse para a miss o Na abordagem atual o procedimento o seguinte 3 a O experimento gera um alerta sobre a detec o Na pr xima passagem sob
172. te trabalho um imageador de luminesc ncia para rel mpagos e sprites que s o fen menos que possuem como caracter stica a curta dura o e a aleatoriedade da ocorr ncia Por este motivo o TIP foi escolhido para enviar a solicita o por mais recursos ao RASSO Foi criado um processo do aplicativo do RTEMS para simular o disparo da solicita o por recursos A simula o da detec o da ocorr ncia do fen meno se d logo aos 3 segundos a partir do momento zero e s o solicitados mais energia e mem ria quantidades tr s vezes maiores do que em opera o normal para o TIP por um per odo de 3000s a partir dos 9000s do in cio do plano 133 Foi definido um plano de opera es inicial e uma tabela de ocorr ncias de janelas de tempo para o cen rio que s o apresentados na Figura 7 1 ight ommunicating ommunicating Fila de Telecomandos Temporizados Tabela de Janelas de Tempo OlChange Mode ionex partial Day 600 Turn_On grom Change Mode ionex full Day 3600 Turn_On grom Turn_Off grom 6600 Turn_On grom Turn_Off grom 9600 Turn_On grom 12600 Turn_On grorn Turn_Off grom todas as refer ncias temporais est o dii FIGURA 7 1 Comandos Iniciais e Janelas de Tempo Definidos para o Cen rio Na execu o do plano normal o consumo de recursos mant m se dentro dos limites impostos Entretanto caso fosse atendida sem nenhuma outra altera o na opera o do sat l
173. tempo limitado ele poderia propiciar uma observa o adequada e devolver o sat lite ao seu modo de opera es normal antes mesmo de enviar um alerta para solo Este procedimento aut nomo tamb m apresentado na Figura 2 3 descrito a seguir 3 b Ap s a detec o o experimento envia uma mensagem ao computador de bordo solicitando mais recursos para a observa o e informando por quanto tempo ir precisar destes recursos Um software de replanejamento aut nomo efetua diversas simula es analisando diferentes mudan as na configura o do sat lite a partir de seu estado atual e escolhe a que menos afete a opera o dos demais experimentos Um novo plano gerado em bordo e colocado em execu o J operando pelo novo plano o sat lite realoca os recursos solicitados e os mant m assim pelo tempo necess rio observa o Ao t rmino deste per odo os recursos s o devolvidos aos experimentos e outros subsistemas que os cederam e o sat lite volta a operar conforme o originalmente programado 4 b Numa pr xima passagem sobre a esta o terrena o sat lite envia o alerta da detec o do evento junto aos dados coletados durante sua observa o A tecnologia escolhida para propiciar ao sat lite o replanejamento aut nomo de sua opera o a de Planejamento e Escalonamento em IA O pr ximo Cap tulo apresenta uma vis o geral desta tecnologia 42 CAP TULO 3 PLANEJAMENTO E ESCALONAMENTO EM INTELIG
174. to Gil alertava aos incautos que estava chegando ao fim o tempo de contempla o rom ntica dos c us Os sovi ticos haviam acabado de chegar Lua com uma sonda Lunik em 1966 alcan ando o que at ent o era reservado poesia filosofia e literatura O encantamento com o espa o dava lugar pesquisa exatamente assim que me sinto ao terminar este trabalho N o raro me surpreendo pela naturalidade com que falo hoje em espa onaves rbitas intelig ncia artificial palavras comuns na inf ncia quando metido com meus brinquedos e minha imagina o mas que havia deixado de usar quando me tornei gente grande O encantamento de ent o deu lugar pesquisa de hoje E fico alegre ao constatar que a pesquisa trouxe o encantamento de volta H muitos a quem agradecer pelo apoio e ajuda na realiza o deste trabalho Em primeiro lugar agrade o ao meu orientador Maur cio n o apenas pelo timo relacionamento e pela orienta o segura e tranquila pelas dicas mineiras e pela confian a depositada mas tamb m por ter me apresentado o INPE alguns anos atr s e aberto com isso novas portas para mim Ao Dr M rio Selingardi chefe da Divis o de Eletr nica Aeroespacial do INPE pela oportunidade de estudos que me foi concedida Ao pessoal do Grupo de Supervis o de Bordo por todo o apoio pela paci ncia e pelos esclarecimentos em especial ao Ronaldo minha mais freq ente v tima Um agradecimento especial minha espos
175. to com IA a uma aplica o espacial ocorreu em 1983 quando o planejador DEVISER Vere 1983 baseado no NONLIN Tate 1977 gerou planos para a opera o de uma sonda Voyager da NASA O DEVISER foi tamb m o primeiro planejador a trabalhar com representa o temporal cont nua cada a o possuia um momento de in cio e fim ao inv s dos momentos sequenciais usados por outros sistemas onde a primeira a o ocorre no momento 1 a segunda no momento 2 e assim por diante Por ser apenas uma demonstra o os planos gerados n o foram enviados para a sonda O desempenho do planejador foi considerado insuficiente e n o se deu continuidade naquele momento pesquisa com planejamento em IA No final da d cada de 1980 estudos em planejamento e escalonamento em JA vinham sendo realizados pela ESA dentro de seu programa de pesquisas sobre Sistemas Especialistas Um dos trabalhos resultantes deste estudo Fuchs et al 1988 identificou cinco potenciais aplica es de planejamento e escalonamento em IA ao programa espacial europeu entre os quais estavam o planejamento de miss o para o sat lite ERS 1 e o planejamento da montagem integra o e verifica o de foguetes lan adores e espa onaves 73 Em resposta a isso a ESA patrocinou o desenvolvimento de dois planejadores O primeiro foi o planERS 1 Fuchs et al 1990 um prot tipo para an lise e planejamento de miss o para o sat lite de sensoriamento
176. tra se o do Computador Avan ado COMAV que vem sendo desenvolvido pelo Grupo de Supervis o de Bordo SUBORD da Divis o de Eletr nica Aeroespacial DEA O grupo SUBORD participou do projeto e desenvolvimento de todos os computadores embarcados nos sat lites do INPE desde o SCD 1 Sendo um projeto de desenvolvimento tecnol gico o COMAV Alonso et al 2001 tem entre seus objetivos a utiliza o de novas metodologias t cnicas e ferramentas a serem posteriormente aplicadas aos computadores de bordo das futuras miss es espaciais do INPE A proposta do COMAV seguindo uma tend ncia mundial unificar as tarefas de supervis o de bordo e o controle de atitude e rbita do sat lite que s o usualmente realizadas por computadores distintos Al m disso prevendo seu uso em miss es cient ficas o COMAV tamb m ir efetuar o controle e comunica o com experimentos O processador utilizado no COMAV o ERC32 RISC de 32 bits e arquitetura SPARC V7 que pode trabalhar a at 25MHz desenvolvido pela ESA especificamente para aplica es espaciais O uso do ERC32 representa um ganho significativo em termos de poder computacional para os sistemas embarcados em sat lites do INPE Como crit rio de compara o pode se destacar que o computador central do CBERS o mais complexo entre os sat lites do INPE baseado em um processador CISC 80c86 de 16 bits que atinge no maximo 4MHz Tais velocidades podem surpreender aqueles acos
177. tribu dos provavelmente estar o violando as restri es A viola o das restri es impostas ao problema tamb m conhecida como conflito A id ia b sica modificar gradualmente os valores atribu dos s vari veis envolvidas no conflito na tentativa de reparar as restri es violadas e levar o plano para mais pr ximo de uma solu o Isto feito gerando se repetidamente uma vizinhan a de novos valores atribu dos elencando estas atribui es e selecionando a melhor Cada etapa de cria o avalia o e r sele o de um conjunto vizinho de valores chamada de uma mudan a Como a 63 efic cia desta abordagem altamente dependente da atribui o inicial uma nova atribui o inicial sempre desconsiderando os poss veis conflitos para que sejam resolvidos no processo de cria o de vizinhan as gerada ap s um determinado n mero de mudan as terem sido executadas sem alcan ar uma solu o v lida A cada um destes ciclos desde a atribui o inicial at atingir o n mero m ximo de mudan as dado o nome de tentativa Ap s tentativas suficientes sem encontrar uma solu o o processo termina com uma indica o de falha A Figura 3 10 traz um algoritmo b sico de busca local Busca Local CsPi l Repetir por numero de tentativas Gerar uma atribui o inicial A para as vari veis no CSP Lepetir por movimentos Selecionar uma atribui
178. tumados aos GHz presentes nos atuais computadores do tipo IBM PC ou similares Esta defasagem de desempenho deve se ao fato de que processadores para aplica es espaciais passam por um rigoroso processo de qualifica o no qual seu pr prio projeto est sujeito a modifica es para permitir um menor consumo de energia e maior resist ncia s altas taxas de radia o do ambiente espacial entre outros Este processo pode levar anos para ser conclu do de forma que 98 os processadores utilizados em miss es espaciais nunca s o os modelos mais recentes dispon veis no mercado Com rela o ao software o COMAV ir utilizar pela primeira vez nos sat lites brasileiros um sistema operacional de tempo real gratuito e de c digo fonte aberto o Real Time Executive for Multiprocessor Systems RTEMS Os sat lites anteriores fizeram uso de sistemas operacionais dedicados desenvolvidos pelo INPE especificamente para cada miss o O RTEMS foi criado pela Online Applications Research Corporation OAR sob contrato com o Departamento de Defesa Norte Americano para ser um kernel de tempo real multitarefa para sistemas embarcados em m sseis O RTEMS foi posteriormente utilizado em outras aplica es militares e em 1994 foi aberto para uso em aplica es civis O RTEMS atualmente um sistema de c digo fonte aberto de uso livre e que pode ser distribu do e alterado sob os termos da GNU General Public License GPL Entre 1995 e 1
179. umas destas instru es s o get current state by id e set current state by id alguns exemplos se encontram na Figura 6 4 H tamb m instru es para a obten o do estado de um objeto no momento inicial do plano no momento imediatamente anterior ao atual e no estado objetivo 118 6 2 3 2 Manipulando o Consumo e a Gera o de Recursos no Tempo Em RASSO ml os recursos s o tratados em termos de taxas de consumo gera o Quando alguma a o ou comportamento modifica a taxa de consumo de um recurso por determinado objeto a nova taxa armazenada em um profile A Figura 6 7 apresenta um exemplo do perfil de consumo de energia pelo objeto MLTM profile MLTM Power 0 EXC ESCOCIA FIGURA 6 7 Exemplo de Perfil de Consumo de Recurso No exemplo da Figura 6 7 a a o de n mero 5 no plano teve como efeito o consumo de energia pelo objeto MLTM taxa de 3 unidades por segundo o segundo a unidade de tempo b sica do RASSO Esta pode ser por exemplo uma a o que ligue o experimento A a o de n mero 7 por sua vez tornou o consumo de energia igual a zero Esta pode ser uma a o do plano que desligue o experimento Estruturas similares da Figura 6 7 armazenam as taxas de gera o de recursos que diferentemente do consumo n o s o vinculadas a objetos veja a instru o generate resource na Figura 6 5 Cabe destacar aqui que a modelagem de consumo gera o de recursos em termos d
180. vos Neste tipo de automatiza o cabe aos especialistas monitorar o processo de gera o de planos corrigindo poss veis falhas ou efetuando melhorias pontuais Apesar de ainda pequeno o n mero de miss es que usam este tipo de planejamento vem crescendo nos ltimos anos especialmente na NASA O ltimo n vel de automatiza o ainda n o uma realidade para as miss es espaciais mas deve se tornar num futuro pr ximo Aqui a pr pria espa onave gera seus planos de opera o ou altera os que lhe haviam sido enviados de solo Isso permite uma maior capacidade de resposta a eventos externos otimiza o no consumo de recursos e tem o potencial para reduzir drasticamente os custos operacionais da miss o Com sistemas 72 embarcados de planejamento as espa onaves tomam suas decis es dentro de limites seguros pr estabelecidos e as relatam equipe de opera es em solo geralmente ap s a execu o Pouquissimas miss es utilizaram planejamento embarcado e o fizeram em car ter experimental O restante deste Cap tulo apresenta um hist rico da aplica o de planejamento com IA rea espacial descrevendo planejadores que foram ou est o sendo desenvolvidos para execu o tanto em solo quanto em bordo e o futuro do planejamento na rea 4 2 Automatizac o de Opera es nas Miss es Espaciais 4 2 1 Os Primeiros Planejadores com IA para Uso Espacial A primeira demonstra o do uso de planejamen

Formato PDF - mtc-m17:80

Contents

Download Pdf Manuals

Related Search

Related Contents