verificação de restrições temporais com tempo contínuo em
Transcrição
verificação de restrições temporais com tempo contínuo em
UNIVERSIDADE FEDERAL DO ESTADO DO RIO DE JANEIRO DEPARTAMENTO DE INFORMÁTICA APLICADA PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA VERIFICAÇÃO DE RESTRIÇÕES TEMPORAIS COM TEMPO CONTÍNUO EM STORYTELLING NÃO-DETERMINÍSTICO Eric Teixeira Araujo Orientador Prof. Dr. Angelo Ernani Maia Ciarlini RIO DE JANEIRO, RJ – BRASIL Setembro de 2011 VERIFICA<;AO DE RESTRI<;OES COM TEMPO CONTINUO EM STORYTELLING NAO-DETERMINISTICO Eric Teixeira Araujo DISSERTA<;AO APRESENTADA COMO REQUISITO PARCIAL PARA OBTEN<;AO DO TITULO DE MESTRE PELO PROGRAMA DE POSGRADUA<;AO EM INFORMATICA DA UNIVERSIDADE FEDERAL DO ESTADO DO RIO DE JANEIRO (UNIRIO). APROVADA PELA COMISSAO EXAMINADORA ABAIXO ASSINADA. Aprovada por: Prof~ngelo Ernani Maia Ciarlini, D. Sc. - UNIRIO Prof. Sean Wolfgand Matsui Siqueira, D.Sc. - UNIRIO Prof Marco~~lJJgasQ.Ph.D. -PUC-RIO !Lfe-:··~ Prof. Bru o FJtt Ph.D. -PUC-RIO RIO DE JANEIRO, RJ - BRASIL SETEMBRO DE 2011 A663 Araujo, Eric Teixeira. Verificação de restrições temporais com tempo contínuo em storytelling não-determinístico / Eric Teixeira Araujo, 2011. 124f. Orientador: Angelo Ernani Maia Ciarlini. Dissertação (Mestrado em Informática) – Universidade Federal do Estado do Rio de Janeiro, Rio de Janeiro, 2011. 1. Storytelling interativo. 2. Programação em lógica com restrições. 3. Inteligência artificial. 4. Tempo ramificado e contínuo. 5. Não-determinismo. 6. Lógica temporal. I. Ciarlini, Angelo Ernani Maia. II. Universidade Federal do Estado do Rio de Janeiro (2003-). Centro de Ciências Exatas e Tecnologia. Curso de Mestrado em Informática. III. Título. CDD – 006.7 AGRADECIMENTOS • Aos meus pais, que foram as pessoas mais importantes na construção deste trabalho. • À minha namorada pelo apoio e compreensão. • Ao meu orientador pela oportunidade e por ter acreditado no meu potencial, além de toda a ajuda e tempo dispensado para que este trabalho pudesse ser realizado. • A todos os professores com os quais tive contato no decorrer do processo, em especial aos professores Sean e Flávia que em muito acrescentaram à esta pesquisa no decorrer dos seminários de acompanhamento. • Aos colegas com os quais mantive contato nesse tempo de mestrado. • Aos meus verdadeiros amigos por toda a força nos momentos difíceis. • Aos colegas da CMQ pela força e ajuda durante o processo de desenvolvimento desta pesquisa. • Aos servidores técnicos-administrativos da UniRio pela dedicação no atendimento às necessidades dos alunos, principalmente à Alessandra que está sempre à disposição para ajudar os alunos. • E a todas as outras pessoas que de alguma forma, mesmo que minimamente, ajudaram a me manter focado na conclusão deste trabalho. ARAUJO, Eric Teixeira. Verificação de Restrições Temporais de Tempo Contínuo em Histórias Não-Determinísticas. UNIRIO, 2011. 124 páginas. Dissertação de Mestrado. Departamento de Informática Aplicada, UNIRIO. RESUMO Em um contexto de Storytelling Interativo, as histórias são essencialmente não lineares, isto é, correspondem a múltiplas alternativas de seqüências de eventos e cada evento pode, usualmente, terminar de diversas maneiras diferentes. Nesse contexto, trabalhar com lógicas de tempo ramificado tende a ser uma opção interessante para lidar com os possíveis estados de uma história interativa. Além disso, propriedades importantes das histórias, como as emoções geradas por elas, variam continuamente ao longo do tempo. Nesta dissertação descrevemos um método implementado para checar se histórias interativas (ou partes delas) satisfazem restrições de tempo contínuo. Restrições são especificadas por meio de uma lógica temporal modal, que assume que o tempo é ramificado e contínuo. Devido à suposição de que o tempo é contínuo, o nosso método tem de lidar com um número infinito de estados. A fim de lidar com isso, usamos técnicas de Programação em Lógica com Restrições e modelamos nossas propriedades contínuas como funções linearizadas aos pedaços. O método foi aplicado a um contexto de história, com variações, do conto de fadas da Chapeuzinho Vermelho e os resultados dos testes mostraram que a sua aplicação em tempo real, enquanto a história é gerada e contada, é viável. Palavras-chave: Storytelling Interativo; Programação em Lógica com Restrições; Inteligência Artificial; Tempo Ramificado e Contínuo; Não-determinismo; Lógica Temporal ABSTRACT Within an interactive storytelling context, stories are essentially nonlinear, i.e., they correspond to multiple alternative sequences of events and each event can usually have multiple different outcomes. In this context, branching-time logics tend to be a coherent option to handle the possible states of an interactive story. In addition, important properties of the stories, such as the emotions they generate, continuously vary over time. In this paper, we describe an implemented method to check whether (parts of) interactive stories satisfy continuous-time constraints. Constraints are specified by means of a temporal modal logic, assuming that the time is continuous and branched. Due to the continuous-time assumption, our method has to deal with an infinite number of states. In order to cope with that, we use constraint logic programming and model our continuous-time properties as piecewise-linear functions. The method was applied to a story context with variants of the Little Red Riding Hood fairy tale and the results so far have shown that its application at real-time, while a story is generated and told, is viable. Keywords: Interactive Storytelling; Constraint Logic Programming; Artificial Intelligence; Branching and Continuous Time; Nondeterminism; Temporal Modal Logic Sumário 1 Introdução.................................................................................................................... 10 1.1 Motivação............................................................................................................... 10 1.2 Proposta.................................................................................................................. 11 1.3 Estrutura..................................................................................................................12 2 Fundamentação Teórica............................................................................................... 14 2.1 Storytelling Interativo............................................................................................. 15 2.1.1 Plot-Based x Character-Based.................................................................. 16 2.1.2 Formas de Interação................................................................................... 18 2.1.3 Modelagem de Usuário.............................................................................. 19 2.1.4 Logtell........................................................................................................ 21 2.2 Lógica Temporal Modal......................................................................................... 23 2.3 Verificação de Restrições em Sistemas Híbridos................................................... 24 2.3.1 Exemplo de um Autômato Híbrido............................................................25 2.3.2 Definição Formal de um Autômato Híbrido.............................................. 27 2.4 Programação em Lógica com Restrições................................................................29 3 Modelo de Verificação Temporal................................................................................ 32 3.1 Requisitos............................................................................................................... 33 3.2 Modelo de Emoções............................................................................................... 34 3.3 Especificação de Eventos....................................................................................... 37 3.4 Uma Lógica Para Falar Sobre Propriedades Contínuas de Histórias Interativas... 39 3.4.1 Simplificação de fórmulas compostas....................................................... 41 3.4.2 Demonstração de Algumas Simplificações............................................... 42 3.5 Processo de Verificação Baseado em CLP............................................................. 46 4 Algoritmo de Verificação............................................................................................ 48 4.1 Estruturas de dados................................................................................................. 48 4.1.1 Eventos...................................................................................................... 48 4.1.2 Histórias (ou capítulos de uma história).................................................... 49 4.1.3 Fórmulas.................................................................................................... 50 4.2 Algoritmo básico.................................................................................................... 51 4.3 Verificação de fórmulas quantificadas................................................................... 54 4.4 Verificação de estados ao longo de um caminho ................................................... 56 4.5 Adicionando restrições aos intervalos.................................................................... 59 4.6 Processamento de alternativas................................................................................ 63 5 Exemplo de Aplicação do Método.............................................................................. 65 5.1 Chapeuzinho Vermelho.......................................................................................... 65 5.2 Modelagem Emocional........................................................................................... 67 5.3 Avaliação................................................................................................................ 71 5.4 Atendimento aos requisitos.................................................................................... 77 6 5.4.1 Análise de Eficiência................................................................................. 78 5.4.2 Análise de Expressividade......................................................................... 78 5.4.3 Análise da Facilidade de Representação das Propriedades Contínuas...... 79 Conclusão.....................................................................................................................81 6.1 Principais Contribuições......................................................................................... 82 6.2 Trabalhos Futuros................................................................................................... 84 7 Referências Bibliográficas........................................................................................... 87 ANEXO I – Simplificações da Lógica Baseada em CTL................................................... 93 ANEXO II – Algoritmos de Validação dos Operadores de Estado...................................108 8 Lista de Figuras 2.1 Autômato representando um esquema de um termostato (Adaptado de [Henzinger, 1997]). 3.1 Estrutura de n-Eixos de famílias de emoções opostas. 3.2 Estrutura de n-Eixos de famílias de emoções opostas, simplificada. 3.3 Exemplo de especificação das derivadas de uma função linearizada aos pedaços. 3.4 Gráfico de uma função linearizada aos pedaços representando uma propriedade continua versus tempo (porcentagem). 3.5 Significado da combinação de quantificadores de operadores de estado. 3.6 Representação gráfica de possibilidades de uma fórmula do tipo EF EG α ser válida. 3.7 Representação gráfica de possibilidades de uma fórmula do tipo E (EG α U β) ser válida. 3.8 Representação gráfica de possibilidades de uma fórmula do tipo A (EG α U β) ser válida. 3.9 Representação gráfica de possibilidades de uma fórmula do tipo E (AG α U β) ser válida. 3.10 Representação gráfica de possibilidades de uma fórmula do tipo A (AG α U β) ser válida. 4.1 Algoritmo para verificação de fórmulas temporais modais em histórias não-determinísticas. 4.2 Algoritmo para validação das fórmulas temporais. 4.3 Algoritmo não-determinístico de verificação de caminhos. 4.4 Quebrando eventos em intervalos de derivadas constantes. 4.5 Algoritmo para validação das fórmulas a partir de um evento. 4.6 Impondo restrições nos eventos. 4.7 Algoritmo que impõe e verifica as restrições para uma fórmula existencialmente quantificada. 4.8 Algoritmo que verifica a validade de uma subfórmula com o operador ‘G’. 4.9 Algoritmo que impõe e verifica as restrições para uma fórmula globalmente quantificada. 4.10 Algoritmo de verificação de alternativas. 4.11 Algoritmo que impõe e verifica as restrições para uma fórmula no fim de um caminho. 5.1 Eventos na história da Chapeuzinho Vermelho. 5.2 Árvore de Eventos (História I). 5.3 Emoções envolvidas em cada evento da história. 5.4 Desenvolvimento das emoções ao longo da história original. 5.5 Desenvolvimento das emoções ao longo de uma alternativa para a história. 5.6 Desenvolvimento das emoções ao longo de uma alternativa para a história. 5.7 Desenvolvimento das emoções ao longo de uma alternativa para a história. 5.8 Desenvolvimento das emoções ao longo de uma alternativa para a história. 5.9 Desenvolvimento das emoções ao longo de uma alternativa para a história. 5.10 Desenvolvimento das emoções ao longo de uma alternativa para a história. 5.11 Desenvolvimento das emoções ao longo de uma alternativa para a história. 5.12 Árvore de Eventos (História II). 1 Introdução 1.1 Motivação Sistemas de Storytelling Interativo são aplicações em que histórias são geradas e contadas de acordo com interferências do usuário. Guardadas as devidas proporções, eles podem ser comparados a RPGs (Roleplaying Games), onde os jogadores são, ao mesmo tempo, personagens e autores da história [Cupertino, 2008]. Sistemas desse tipo foram desenvolvidos para diversos propósitos e, na maioria dos casos, existem propriedades relevantes, que variam continuamente ao longo do tempo. A intensidade das emoções, os níveis de violência e suspense são exemplos desse tipo de propriedade. É possível observar, por exemplo, picos na intensidade das emoções e uma tensão geral acumulada que leva ao clímax da história antes que ela acabe. Esse conhecimento é essencial para despertar e manter a atenção do público na história [Zagalo et al, 2004]. Além disso, cada gênero narrativo impõe restrições próprias para as emoções, que são causadas por seqüências de eventos que ocorrem durante a narrativa. Em contos de fada, por exemplo, as histórias tendem a ter um final feliz, enquanto que, em um suspense, um determinado nível de tensão é mantido ao longo de toda a narrativa. Nesse sentido, a satisfação das restrições impostas pelo gênero de uma determinada história é um importante tema para a área de Storytelling Interativo. Além das restrições impostas pelo gênero, podemos ter restrições relacionadas com as preferências do usuário. Nos últimos anos, Sistemas de Storytelling Interativo, como o PaSSAGE [Thue et al, 2007] e o Mirage [El-Nasr, 2007], têm lançado mão de técnicas de modelagem de usuário no processo de geração de histórias. Ao usar essa técnica, as histórias são adaptadas de acordo com modelos de usuário, que são detectados mediante interações prévias. Se um modelo de usuário incorpora restrições emocionais, se faz necessário criar formas de reforçar essas restrições. 10 Quando um autor está escrevendo uma história linear, tanto as restrições impostas pelo gênero quanto as impostas pela audiência da história são levadas em consideração. Se as histórias são não-lineares e geradas em tempo real, como em muitos sistemas de Storytelling Interativo, a tarefa tende a ser bem mais complicada. Muitas soluções para esse tipo de sistema têm utilizado técnicas de planejamento para gerar histórias ou partes delas. Algumas técnicas, como as descritas em [Riedl, 2009; Porteous et al, 2010; Ciarlini et al, 2010], incorporam técnicas de satisfação de restrições temporais durante a narrativa. Ao utilizar planejamento em sistemas de Storytelling Interativo assume-se, normalmente, que o tempo é discreto. Isso faz sentido, pois não se faz necessário assumir que o tempo é contínuo para manipular a maior parte das características das narrativas. Além disso, utilizar técnicas de planejamento considerando que o tempo é contínuo tende a ter um nível de complexidade muito maior do que quando se considera o tempo discreto. Esse fato, no entanto, não quer dizer que considerar que o tempo é continuo não é uma situação relevante dentro das histórias, principalmente quando se deseja estabelecer restrições para o nível das emoções. Nosso foco principal não é a geração dos enredos, estamos preocupados com a seleção de alternativas em histórias não determinísticas com base na verificação de propriedades que mudam continuamente. A idéia principal é que, dada uma árvore de eventos com as possibilidades de uma história (ou partes de uma história), devemos ser capazes de impor restrições sobre as propriedades de tempo contínuo e verificar se a árvore as satifaz. Como podemos querer dizer que uma condição deve ser válida em todos os caminhos ou em pelo menos um caminho, estamos lidando com tempo ramificado. Lógicas temporais modais como o CTL (Computation Tree Logic) [Konur, 2010] são utilizadas normalmente quando é necessário lidar isso. A motivação desse trabalho é a proposição de um modelo temporal para lidar com tempo ramificado e contínuo, incorporando as necessidades específicas de um contexto de Storytellig Interativo, e a proposição de um algoritmo que permita verificar a satisfação de fórmulas em lógica temporal por histórias interativas. 1.2 Proposta No decorrer desta dissertação, propõe-se uma extensão do CTL para lidar com tempo ramificado e contínuo, incorporando as necessidades específicas de um contexto 11 storytelling interativo. Para verificar as restrições especificadas com esta lógica, nós implementamos um método de verificação. Assumimos que as histórias, ou partes delas, a serem verificadas já foram geradas por um processo de planejamento em tempo real. O método de verificação foi desenvolvido para ser incorporado como uma extensão do sistema de Storytelling Interativo Logtell 3 [Silva et al, 2010], que gera capítulos de histórias por meio de planejamento não-determinístico em tempo real. Os capítulos correspondem a árvores de eventos, em que cada caminho corresponde a uma seqüência diferente de eventos. A idéia principal é verificar a satisfação de propriedades que variam continuamente ao longo do tempo por essas árvores. Se uma árvore não satisfaz as restrições especificadas, o capítulo correspondente é descartado e outro tem que ser fornecido pelo módulo de planejamento. Apesar de ter sido implementado para ser incorporado ao Logtell, o método pode também ser incorporado a outros sistemas. Alternativamente, pode ser usado para selecionar histórias interativas em uma biblioteca. O principal desafio do procedimento de verificação é que, com tempo contínuo, temos que lidar com um número infinito de estados. A fim de fazer isso, recorremos a técnicas de programação em lógica com restrições [Marriot & Stuckey, 2010] e assumimos que as propriedades de tempo contínuo podem ser modeladas como funções linearizadas aos pedaços. Para a validação do método de verificação e da lógica proposta apresentamos um exemplo de contexto com variações para o conto de fadas da Chapeuzinho Vermelho. 1.3 Estrutura No Capítulo 2 é apresentada a fundamentação teórica deste trabalho. Como o principal contexto de aplicação desta pesquisa são os Sistemas de Storytelling Interativo, é apresentada uma visão geral sobre o tema descrevendo-se as principais questões envolvidas e os enfoques adotados em diferentes sistemas. Então, é apresentada uma visão geral sobre o funcionamento do Logtell 3. Além disso, como trabalhamos com técnicas de lógica temporal modal, de programação em lógica com restrições e de sistemas de verificação em tempo real fez-se necessário discorrer também sobre esses temas, de forma a posicionar esta pesquisa no contexto desses temas. 12 No Capítulo 3, é apresentada uma proposta de modelo de verificação temporal baseado em CTL para a especificação de restrições temporais sobre propriedades contínuas em histórias interativas. O Capítulo 4 descreve os principais aspectos relativos ao algoritmo que permite a verificação segundo o modelo proposto no Capítulo 3 e à sua implementação. Já no capítulo 5, é realizada uma análise dos testes realizados para verificar o atendimento aos requisitos desse modelo. O Capítulo 6 contém as conclusões da pesquisa com a descrição de suas principais contribuições e dos trabalhos futuros potenciais, os quais foram identificados ao longo da elaboração do modelo e dos testes realizados com o protótipo. 13 2 Fundamentação Teórica Este trabalho trata da verificação de restrições sobre propriedades que variam continuamente ao longo do tempo em histórias não-determinísticas interativas (daqui para frente simplesmente mencionadas como propriedades contínuas), considerando que o tempo é ramificado e contínuo. Este capítulo apresenta o contexto da pesquisa de que trata esta dissertação e as principais técnicas utilizadas para fazer a verificação nas histórias dinamicamente, enquanto elas são geradas e apresentadas. A pesquisa se enquadra dentro do contexto de sistemas de Storytelling Interativo. Sistemas desse tipo são, resumidamente, aplicações que servem para contar histórias com o auxílio de mecanismos automatizados, procurando adaptar as histórias de acordo com as interações que têm com o usuário. Diferentemente de jogos, que são focados nos jogadores, suas estratégias e desafios pontuais a serem vencidos, esse tipo de sistema é focado nas histórias e no seu conteúdo dramático. O método de verificação de propriedades que se almeja visa conferir meios para garantir que as histórias sejam capazes de entreter e engajar os usuários de sistemas de storytelling interativo, em particular em um ambiente de TV interativa. Dada uma história não-linear interativa, com vários caminhos possíveis, ou parte dessa história, deseja-se averiguar, antes de adotá-la, se, por exemplo, a tensão e as emoções despertadas em quem assiste à história variam conforme o desejado pelo autor do contexto da história. O método proposto, embora possa ser adotado de forma independente, foi pensado para ser incorporado dentro de um módulo do sistema de storytelling para TV interativa Logtell 3. No Logtell 3, capítulos de histórias são gerados e apresentados em paralelo, enquanto os usuários interagem com as histórias. Desse modo, o método deve ser baseado em uma lógica suficientemente expressiva para garantir que as restrições importantes para uma boa história sejam especificadas e, por outro lado, possam ser verificadas dinamicamente, sem atrapalhar o processo de storytelling. Na seção 2.1 são apresentadas as principais características de sistemas de 14 Storytelling Interativo de modo a se ter uma idéia do contexto onde a pesquisa está sendo aplicada. Como se deseja especificar restrições sobre histórias levando em conta que o tempo é ramificado e contínuo, a compreensão dos conceitos de lógica temporal modal é necessária. A seção 2.2 tem o objetivo de apresentar esses conceitos, apresentando uma revisão de (Computation Tree Logic) [Konur, 2008], que é usada como base para a lógica proposta nesta dissertação para especificar restrições sobre histórias. A verificação de modelos de sistemas de software e hardware para se certificar de que eles atendem às suas especificações é o objeto de estudo da área de Computação conhecida como Verificação de Modelos (Model Checking) [McMillan, 1993]. Tal atividade é fundamental para garantir que os sistemas funcionem como desejado. Normalmente, o processo de verificação é aplicado a sistemas com um conjunto finito de estados discretos. Mesmo nesse caso, a explosão no número de estados a tratar demanda o uso de técnicas específicas, como algoritmos simbólicos [Bertoli et al, 2001] que evitam a construção do grafo de estados total ou métodos que limitam a verificação a um certo limite no número de passos da execução [Biere et al, 2003]. Quando os sistemas possuem variáveis contínuas (que possivelmente variam continuamente ao longo do tempo), o problema de verificação torna-se bem mais complexo, tendo em vista que se passa a tratar de um conjunto infinito de estados. Tal tipo de verificação é, contudo, de fundamental importância para garantir a correção sistemas complexos, tais como sistemas com requisitos de tempo real. A verificação de modelos de sistemas híbridos (com variáveis discretas e contínuas), tal como proposto em [Alur et al, 1993; Henzinger et al, 1997], é feita estendendo as técnicas de verificação de modelos com estados discretos. Tal abordagem tem relação direta com o método proposto nesta dissertação para a verificação de histórias, cabendo portanto discutir as similaridades e diferenças. Desse modo, a verificação de modelos em sistemas híbridos é discutida na seção 2.3. Por fim, o método proposto nesta dissertação apóia-se na Programação em Lógica com Restrições, cujos conceitos principais são apresentados na seção 2.4. 2.1 Storytelling Interativo 15 Sistemas desse tipo vêm sendo pesquisados para diferentes aplicações e implementados de diferentes modos. Podem ser aplicados, por exemplo, a jogos, à Educação, no auxílio à autoria de histórias e a entretenimento em geral. As diferenças entre os sistemas decorrem, em geral, do tipo de aplicação e do gênero de histórias com que se deseja trabalhar. Algumas abordagens têm foco na estrutura da trama (plot-based) ou na modelagem de personagens (character-based) [Cai et al, 2007]. Os sistemas também podem diferir no posicionamento dos usuários com relação à narrativa, na capacidade de realmente gerar dinamicamente histórias novas (ou apenas controlar a escolha de alternativas previamente criadas), no nível de interação do usuário e no meio através do qual as histórias são criadas e contadas. Apesar das diferenças, na maior parte das abordagens as histórias contêm propriedades que variam continuamente, as quais podem estar diretamente relacionadas à lógica do enredo, às emoções de personagens, às emoções do usuário ou à tensão dramática. Tais propriedades normalmente têm que ser levadas em conta para a obtenção de um bom resultado. A modelagem dos usuários é outro aspecto relevante adotado em alguns sistemas. De modo a se tentar criar e contar histórias que automaticamente se ajustem a preferências dos usuários, modelos dos usuários também podem ser úteis. Esses modelos podem eventualmente envolver preferências sobre como propriedades contínuas das histórias variam. Nesta seção, as diferentes abordagens e a questão da modelagem de usuários em storytelling interativo são discutidas e relacionadas à variação de propriedades contínuas das histórias. Por fim, são apresentados mais detalhes sobre o sistema de storytelling para TV interativa Logtell, o qual deverá incorporar o mecanismo de verificação de restrições proposto nesta dissertação. 2.1.1 Plot-based x Character-based Na abordagem plot-based, como em [Grasbon et al, 2001; Paiva et al, 2001], o usuário não tem permissão de, a qualquer momento, intervir na história. Há um controle rígido sobre a história que está sendo apresentada, com o objetivo de evitar que haja uma fuga do contexto inicial que foi previamente definido pelo autor. A estrutura geral da história é gerada inicialmente, podendo-se definir um início, um meio e um fim. O usuário pode fazer pequenas interferências que apenas têm o objetivo de guiar o andamento para chegar a pontos predefinidos. Devido à rigidez, torna-se mais fácil a 16 manutenção da coerência e a autoria das histórias, porém, restringe-se o potencial de intervenção do usuário. Em uma abordagem plot-based, é importante que o autor procure garantir que as alternativas de enredo apresentadas sejam atrativas e variadas e, para tal, é preciso levar em conta, mesmo que de forma implícita, a variação da tensão dramática durante a narrativa. Em abordagens character-based, a interação ocorre em mais baixo nível. Há uma possibilidade maior de se fazer alterações de atributos que influenciam no desenvolvimento do enredo. Em sistemas como os descritos em [Cavazza et al, 2002; Charles et al, 2001], a história surge da interação em tempo real entre agentes autônomos, cada um com objetivos e comportamentos próprios. Isto facilita a participação do usuário, pois, em geral, as ações de qualquer personagem da história podem ser influenciadas por alterações que o usuário faz diretamente nos atributos mundo a qualquer momento. Nesta abordagem, no entanto, pode-se tornar mais difícil garantir que situações novas permaneçam coerentes com o gênero e que sejam, também, suficientemente interessantes. Em uma abordagem character-based, pode-se querer controlar níveis de emoção tanto de personagens quanto dos usuários que assistem a história, os quais podem variar continuamente, de modo a tornar a história interessante. Há algumas abordagens que integram características das duas abordagens anteriores. O sistema Façade [Mateas et al, 2005], uma das mais bem sucedidas experiências de storytelling interativo, adota essa estratégia. A autonomia dos personagens é mantida na maioria das vezes, mas seus objetivos e seu comportamento podem ser alterados por um gerenciador de história (drama manager) de forma a mover a trama adiante. O sistema permite intervenções do usuário num ambiente 3D onde ele pode manipular alguns objetos e conversar com os personagens através de linguagem natural, influenciando assim os rumos da história. Pode-se destacar também o S-MADE [Cai et al, 2007] onde o processo de storytelling é visto como a execução de objetivos de agentes (i.e. o agente diretor e os agentes personagens), aqui foi construída uma ferramenta de modelagem de objetivos chamada FCGN (Fuzzy Cognitive Goal Net) que é usada para modelar os planos da história para o diretor (gerenciador da história) e o comportamento para os personagens. A FCGN é composta de metas e transições, as metas são usadas para representar o que um agente precisa possuir para que possa alcançar o objetivo final e as transições conectam duas metas. Cada transição é 17 associada a uma lista de tarefas que define o que um agente precisa fazer para transitar entre uma meta de entrada e uma meta de saída. A ferramenta permite que metas compostas (com várias tarefas a serem realizadas) possam ser decompostas em metas conectadas por transições. O agente diretor utiliza a decomposição para atribuir o comportamento aos atores virtuais de forma autônoma e dinâmica, levando sempre em consideração a rede de objetivos e as interações dos usuários com o sistema. Dessa forma, a geração dinâmica das histórias e as características comportamentais são geradas simultaneamente, o que em abordagens tradicionais é mais difícil de ser alcançado. Em abordagens híbridas, é necessário lidar tanto com a variação de emoções dos personagens quanto com a variação da tensão dramática e das emoções transmitidas aos usuários. Esses elementos, que variam continuamente, precisam ser adequadamente coordenados para que as histórias sejam coerentes e interessantes. 2.1.2 Formas de Interação Sistemas de storytelling interativo podem ser classificados ainda de acordo com a posição do usuário em relação à história [Charles et al, 2009]. Em muitos sistemas, a perspectiva de primeira pessoa é adotada. O usuário é um membro do elenco e interage com o ambiente como um dos personagens, como no sistema chamado PaSSAGE [Thue et al, 2007], onde os objetos são diretamente manipulados pelo usuário. Em outras abordagens, a perspectiva de terceira pessoa é adotada e as interferências do usuário são mais indiretas. A coerência e a diversidade das histórias geradas também são fatores importantes para que a experiência com esse tipo de sistemas seja prazerosa. Assim, os enredos precisam ser factíveis e coerentes em relação ao gênero, senão o usuário pode perder o interesse na narrativa. Sistemas como o Logtell utilizam técnicas de planejamento para poder gerar histórias diversas e coerentes com o gênero escolhido, permitindo certo controle do usuário sobre o desenvolvimento da trama. O grupo Liquid Narrative Group, da Universidade do Estado da Carolina do Norte (EUA), propôs uma forma para balancear a coerência da narrativa com o controle do usuário na geração de narrativas interativas através da mediação de narrativa, que é uma técnica baseada no enredo, na qual um agente-autor tem o controle sobre as ações dos personagens [Riedl & Young 2006]. O sistema gera, previamente, uma narrativa linear que servirá como guia para a história, as intervenções do usuário são analisadas e, caso seja necessário, alternativas são 18 geradas e apresentadas ao usuário. O controle de mediação atua impedindo que usuário adicione incoerências à história. A verificação de propriedades contínuas sobre as histórias geradas pode auxiliar nessa tarefa. Com o advento da TV interativa (iTV), seja por meio da rede aberta ou de outros ambientes torna-se possível a aplicação de técnicas de storytelling interativo, que podem ser usadas como forma de dar mais poder ao telespectador, fazendo com que a experiência de assistir televisão seja muito mais interessante. Nesse tipo de ambiente, o usuário deve ser capaz de interagir facilmente com a história, sem que a experiência se torne enfadonha para ele, da mesma forma que ocorre na TV convencional [Dória, 2009]. Nesse sentido, é preciso lidar com usuários que desejam ter níveis de interação diferentes, alguns podem querer interagir ativamente e outros podem desejar apenas assistir a histórias interativas. Quanto maior o nível de interatividade, mais difícil é de manter a coerência e o nível de responsividade (a capacidade de atender às expectativas do usuário no tempo adequado) [Camanho, 2009]. Assim, é possível adotar um controle de qualidade para as histórias, para que não se fuja do contexto adotado inicialmente. A verificação de propriedades sobre as histórias geradas parece ser um meio interessante de resolver essa questão. Além disso, pode-se trabalhar com o conhecimento sobre as necessidades dos usuários, adaptando as histórias de acordo com o perfil de quem interage com o sistema. Nesse sentido pode ser necessário verificar padrões existentes nas histórias, levando em conta modelos de usuários, conforme detalhado na seção a seguir. Se pensarmos no contexto de iTV, podemos ter vários usuários interagindo com o sistema ao mesmo tempo, logo vários modelos de usuários diferentes, o que torna a conciliação de requisitos de coerência e responsividade uma tarefa mais complicada. Mecanismos de verificação sobre a adequação de histórias aos modelos podem ser úteis na realização dessa tarefa. 2.1.3 Modelagem de Usuário Para determinar as preferências do público de forma automática pode-se lançar mão de técnicas de modelagem de usuário. No contexto do entretenimento digital esse é um caminho interessante a ser seguido, pois, com a adaptação dos sistemas ao perfil do usuário podem-se construir aplicações cada vez mais interessantes de serem utilizadas, já que a forma de apresentação delas varia de acordo com o perfil do(s) utilizador(es). Modelos de usuário são coleções de informações e suposições sobre usuários individuais (ou grupos de usuários) que são necessárias no processo de adaptação de 19 sistemas. Se a adaptação é feita manualmente, o resultado tende a ser satisfatório, pois o desenvolvedor programa o sistema de acordo com as necessidades já conhecidas inicialmente. No entanto, é mais interessante que o sistema possa se adaptar automaticamente a qualquer usuário que o esteja utilizando [Kobsa, 1995]. A adaptação manual a cada tipo de usuário é muito custosa. Além disso, quando usada em ambientes interativos, conduz a experiências inflexíveis [El-Nasr, 2007]. A automatização do processo é, portanto, desejável. Diversas técnicas já foram desenvolvidas para representar vários tipos de informação e suposições sobre o usuário, como por exemplo: a adaptação de ambientes virtuais [Aquino et al, 2006], visitas guiadas a museus adaptadas ao visitante [Zimmermann et al, 2008; Stock et al, 2007], adaptação de sistemas de aprendizagem [Tsiriga et al, 2002; Kay, 2000], ou ainda a adaptação de sistemas de storytelling interativo [Thue et al, 2007; El-Nasr, 2004; El-Nasr, 2007]. Apesar do desenvolvimento de sistemas adaptáveis ao usuário não ser um campo de pesquisa novo, há poucas pesquisas que aliem modelagem de usuário a técnicas de storytelling interativo para criar novas formas de entretenimento digital. No PaSSAGE [Thue et al, 2007], é utilizado um modelo de usuário para determinar o estilo de jogo preferido do jogador atual, fazendo com que o conteúdo da história interativa seja alterado dinamicamente. A idéia central do sistema é fazer com que o jogo seja mais atrativo para determinados tipos de jogadores. Os tipos de jogadores são: Fighters – que preferem o combate, Power Gamers – que preferem ganhar itens especiais e riquezas, Tacticians – que preferem pensar criativamente, Storytellers – que preferem tramas complexas e Method Actors – que preferem tomar decisões dramáticas. Durante o jogo, o PaSSAGE aprende o modelo de jogador expresso em pesos para cada um desses cinco estilos de jogo. Quanto maior o peso, maior é a crença de que esse estilo de jogo é o preferido. O cenário é adaptado e atualizado em tempo de execução de acordo com as ações do jogador. Já o Mirage [El-Nasr, 2004; El-Nasr, 2007] objetiva aumentar o envolvimento e a qualidade dramática em uma narrativa interativa empregando técnicas dramáticas que foram obtidas e amadurecidas ao longo de algum tempo de pesquisa. A arquitetura foi construída com o auxílio de profissionais de cinema e teatro. O trabalho inicial de ElNasr foi estender o trabalho de Mateas e Stern [Mateas et al, 2005] incorporando uma estratégia de modelagem de usuário, similar ao projeto PaSSAGE, descrito acima. O sistema de El-Nasr, porém, é focado nas características do usuário, e os estereótipos são 20 representados por um vetor de traços que determina as características do usuário (herói, violento, covarde, egocêntrico e caçador da verdade). A partir de uma ação do usuário, o sistema manipula o modelo baseado no estado da história e no histórico de interação do usuário com o sistema para definir suas características. O sistema usa regras simples para realizar as operações. Se, por exemplo, o usuário ataca um personagem desarmado, o grau de violência no modelo de usuário é aumentado. O sistema calcula, ainda, o grau de confiança do novo modelo do usuário, considerando a ação realizada, o tempo que ele levou para decidir realizá-la e o momento em que a história se encontra. Isso é baseado no pressuposto que o tempo indica indecisão. Sistemas desse tipo partem do pressuposto que haverá uma interação explícita do usuário com o sistema. O usuário pode, porém querer apenas assistir a uma história, que possua determinadas características (violenta, romântica, etc.) e/ou propriedades (níveis de violência, trilha sonora, etc.), eventualmente interagindo com ela. Usando apenas esse tipo de técnica não será possível adaptar a história, sendo necessário muitas vezes que os modelos contenham informações prévias sobre o público e suas preferências. Pesquisas referentes à modelagem de usuários em ambientes de storytelling interativo ainda estão em um estado muito incipiente. De qualquer modo, as propriedades de histórias que estão sujeitas a preferências dos usuários muitas vezes variam continuamente. Pode-se imaginar, portanto, que com a associação de padrões de variação desejáveis a tipos de usuários diferentes, e com a disponibilidade de métodos para a verificação de restrições sobre as propriedades ao longo do tempo, é possível gerar histórias que satisfaçam públicos específicos de forma mais satisfatória. 2.1.4 Logtell Com o advento da TV interativa, abriram-se novas oportunidades para a aplicação de técnicas de storytelling interativo. Torna-se possível dar mais poder ao telespectador, fazendo com que a experiência de assistir televisão seja muito mais interessante. O Logtell 2 [Ciarlini et al, 2008; Camanho, 2009; Camanho et al, 2009] é uma extensão do Logtell [Ciarlini, 1999; Ciarlini et al, 2005] que foi proposto para atender aos requisitos da TV interativa. O sistema procura conciliar requisitos de coerência e diversidade de histórias com requisitos de responsividade e escalabilidade, que são típicos de um ambiente de TV. As histórias são dividas em capítulos. Enquanto o capítulo corrente é apresentado através de uma dramatização 3D, o próximo capítulo é gerado através de 21 um processo de simulação que combina a inferência de objetivos a serem atingidos pela história com o planejamento para atingir esses objetivos. A interação do usuário com o sistema durante a apresentação do capítulo corrente influencia a geração do próximo capítulo. Os capítulos são gerados continuamente e apresentados em paralelo. As interações do usuário ocorrem por meio de um modo de terceira pessoa onde os usuários podem sugerir eventos e situações que devem ocorrer no próximo capítulo, que são incorporados à história apenas se não causarem uma inconsistência lógica. O Logtell adota uma abordagem que pode ser classificada essencialmente como plot-based, pois é focado na coerência das histórias, mas, ao invés das histórias criadas serem baseadas apenas em variações de uma história básica, como em sistemas puramente plot-based, as histórias emergem da especificação lógica de um gênero e de uma simulação baseada em planejamento. A inferência de objetivos ocorre através de regras, definidas em lógica temporal para o contexto da história. As regras especificam objetivos a serem perseguidos quando determinadas situações são observadas na história gerada até o momento. Como as regras de inferência são especificadas para, dinamicamente, inferir objetivos que devem ser alcançados pelos personagens, a abordagem acaba por incorporar características de sistemas character-based. Um modelo não-determinístico para gerar [Silva et al, 2010, Silva, 2010] os enredos está sendo incorporado na nova versão do Logtell (Logtell 3), aumentando a diversidade de enredos, as oportunidades de interação do usuário e a duração dos eventos. Cada evento poderá ter efeitos distintos, condicionando a continuidade da história. A dramatização se baseia na extensão de um modelo de controle de autômatos não-determinísticos [Doria et al, 2008]. Esse modelo propunha inicialmente que a dramatização poderia variar conforme houvesse conveniência de estender ou encurtar a dramatização, mas havia apenas um único estado final para cada evento, de modo a não comprometer a lógica do enredo. No Logtell 3, assume-se que eventos podem ter efeitos diferentes e a própria geração dos enredos leva as diferentes contingências em consideração. Nessa nova versão, um capítulo não é mais uma combinação simples de eventos que devem ser dramatizados essencialmente de uma única forma. Os eventos podem ter mais de uma possibilidade de final e a simulação baseada em planejamento gera agora uma árvore onde cada nó representa um evento e cada arco para um evento seguinte corresponde a uma condição para que o evento correspondente possa ser executado. Como nas versões anteriores do Logtell, as metas são inferidas para serem alcançadas 22 durante o capítulo, mas agora metas mais fracas podem também ser especificadas (representando tentativas para chegar a uma determinada situação, que podem ser bem sucedidas ou não). Assim, os capítulos podem terminar em situações muito diferentes. Durante a dramatização do capítulo atual, além de serem capazes de sugerir eventos e situações que devem ser incorporadas em outro capítulo, os usuários também podem interferir nos eventos a serem dramatizados, na tentativa de favorecer um ou outro final para o capítulo atual. Em paralelo com a dramatização do capítulo atual, uma versão do capítulo futuro é gerada para cada fim do capítulo atual, de modo que a dramatização do enredo possa ocorrer de forma contínua. Neste trabalho, é proposto um modelo para verificar se um capítulo satisfaz a restrições sobre propriedades contínuas. Os capítulos possíveis que são gerados podem ser escolhidos para serem dramatizados ou descartados, dependendo da satisfação de restrições impostas pelo gênero e/ou pela preferência do público. 2.2 Lógica Temporal Modal Lógicas temporais modais têm uma forte relação com a especificação e a verificação de sistemas de tempo real. Sistemas desse tipo devem ser definidos com base em métodos matemáticos confiáveis. Lógicas temporais modais têm sido usadas com esse propósito ao longo dos anos, pois elas permitem a especificação do comportamento de um sistema em termos de fórmulas lógicas, que descrevem restrições sobre as propriedades que variam ao longo do tempo, tais restrições são geralmente verificadas por meio de métodos de Model Checking [McMillan, 1993]. Sistemas de lógica temporal modal podem ser classificados em diversas dimensões, tais como: proposicional versus primeira ordem, baseada em pontos versus baseada em intervalos, tempo linear versus tempo ramificado, tempo discreto versus tempo continuo, etc [Emerson, 1995; Venema, 1998]. A lógica temporal precisa tratar tempo ramificado quando há várias possibilidades (vários caminhos) para a sucessão de estados futuros do mundo que está sendo modelado. Computation Tree Logic (CTL) [Konur, 2008] é o formalismo usual adotado quando é necessário falar sobre proposições com tempo discreto e ramificado. Em CTL existem os conectivos lógicos usuais (¬, ∧,∨, → e ↔), quantificadores de caminho e operadores para falar dos estados ao longo de um caminho. 23 Os quantificadores de caminho são: • A que significa “válido em todos os caminhos”; • E que significa “válido em pelo menos um caminho”. Os operadores para falar dos estados ao longo de um caminho são: • X que significa “válido no próximo estado”; • G que significa “válido em todos os estados futuros”; • F que significa “válido em algum estado futuro”; • U que significa “um fato antecessor é necessariamente válido em todos os estados até que outro fato que o sucede o seja”. Em CTL os quantificadores precisam ser combinados aos pares, com os quantificadores de caminho antecedendo os operadores de estados do caminho. Combinações usuais de CTL são as seguintes, onde ρ e µ podem proposições ou fórmulas temporais modais complexas (ex.: µ = EF EG ρ): • AF ρ: ρ é necessariamente válida no futuro; • AG ρ: ρ é sempre válida em todos os estados; • AX ρ: ρ é sempre válida no próximo estado; • A ρ U µ: ρ é sempre válida em todos os caminhos até que µ seja; • EF ρ: ρ é possivelmente válida no futuro; • EG ρ: ρ é válida em todos os estados de pelo menos um caminho; • EX ρ: ρ é possivelmente válida no próximo estado; • E ρ U µ: ρ é sempre válida em pelo menos um caminho até que µ seja; CTL não é diretamente aplicável quando é necessário lidar com fórmulas de lógica de primeira ordem ou para tratamento de tempo contínuo. Neste caso, no entanto, é possível especificar uma lógica temporal modal com quantificadores e operadores semelhantes. No Capítulo 3, propomos uma lógica, baseada em CTL, para especificar restrições em tempo contínuo e ramificado sobre histórias em um contexto de storytelling interativo. 2.3 Verificação de restrições em sistemas híbridos Conforme mencionado anteriormente, a existência de um conjunto potencialmente infinito de estados torna a verificação de restrições em sistemas híbridos bem mais complexa. Há dificuldade tanto na modelagem quanto na implementação de 24 métodos eficientes, corretos e completos para a verificação. No entanto, esse tipo de verificação é de extrema importância, pois em muitas situações do mundo real, existem propriedades que variam continuamente ao longo do tempo. A utilização de sistemas que fazem esse tipo de verificação não implica que o tempo de resposta seja imediato. A verificação de atendimento de restrições em sistemas de tempo real exige aproximações na modelagem da variação das propriedades e nos procedimentos de verificação propriamente ditos e, ainda sim, pode ser uma tarefa que não chegue ao seu final ou demore muito para fornecer a resposta [Carvalho, 2009]. Com os avanços tecnológicos na área de verificação de sistemas de tempo real, surgiram diferentes ferramentas computacionais para a verificação de modelos de sistemas híbridos. O HyTech [Alur et al, 1993; Henzinger et al, 1997] é provavelmente a ferramenta mais famosa nessa área e adota uma abordagem onde os componentes de um sistema híbrido são modelados como autômatos híbridos temporizados. No HyTech há dois sistemas dinâmicos: sistema contínuo (ex.: euclidiano) e sistema discreto (ex.: booleano). 2.3.1 Exemplo de um autômato híbrido Um sistema dinâmico euclidiano ilustra como um conjunto de variáveis reais estão associadas com o tempo. Um estado do sistema é um ponto em Rn (onde n é o número de variáveis) e uma trajetória do sistema é uma curva em Rn (chamado de fluxo). A evolução determinística dos valores das variáveis reais é fixada por uma condição inicial e equações diferenciais. A temperatura x ∈ R , de um aquecedor, por exemplo, tem uma condição inicial x=2 e uma equação diferencial igual a x’= – x +5. A evolução não determinística das variáveis reais pode ser fixada usando desigualdades diferenciais, como por exemplo x'∈ [3,4] . Um sistema dinâmico booleano ilustra como um conjunto de variáveis booleanas estão associadas com o tempo. Um estado do sistema é um ponto em Bm (onde m é o número de variáveis) e uma trajetória do sistema é uma sequência de estados (cada par de estados consecutivos é chamado de salto). A evolução não determinística das variáveis booleanas é naturalmente fixada por uma condição inicial e uma relação de transição que indica para cada estado um conjunto de possíveis estados sucessores. Exemplo: o status y ∈ {on, off } de um aquecedor onde se observa a condição inicial y = on e a relação de transição {(on, off ), (off , on)} , ou seja, o aquecedor pode estar ligado ou desligado. Um sistema booleano dinâmico pode ser 25 considerado como um autômato finito. Um estado desse sistema é um ponto em Bm X Rn, e uma trajetória do sistema é uma sequência de fluxos e saltos: durante fluxos a parte booleana permanece constante e a parte real do estado muda continuamente ao longo do tempo, durante saltos todo o estado do sistema muda instantaneamente. Se combinarmos a temperatura x ∈ R com o aquecedor y ∈ {on, off } teremos um termostato. A figura 2.1 ilustra um autômato híbrido representando um termostato simples. Figura 2.1 Autômato representando um esquema de um termostato (Adaptado de [Henzinger, 1997]). Esse autômato possui dois modos de operação: ou o aquecedor está ligado (modo on) ou o aquecedor está desligado (modo off). Inicialmente o aquecedor está ligado e a temperatura está em 2 graus. Quando o aquecedor está ligado a temperatura aumenta a uma taxa de x’ = – x + 5 graus por minuto e quando o aquecedor está desligado a temperatura diminui a uma taxa de x’ = – x. O aquecedor é desligado quando a temperatura chega a 3 graus e é ligado quando a temperatura chega a 1 grau. Isso é feito pelas condições de ponte x = 3 e x = 1, que indicam quando o modo de operação do termostato precisa ser alterado. Para forçar que o aquecedor mude para o estado desligado quando a temperatura chegar a 3 graus, os modos de operação são especializados com as chamadas condições invariantes: o sistema permanece em um único modo apenas enquanto a condição invariante é satisfeita. Assim, como a mesma condição invariante precisa ser satisfeita em ambos os modos de operação, força-se que o interruptor troque o modo de operação do aquecedor antes que a temperatura deixe o intervalo [1,3] graus. Aqui há a necessidade de se trabalhar com funções lineares. Parte-se do princípio que, apesar de, na maioria das vezes, as funções que tratam das propriedades de sistemas dinâmicos não serem lineares, é possível obter uma aproximação linear aos pedaços dessas funções. Apesar dessa restrição esse tipo de formalismo se mostrou bastante eficiente na resolução de problemas do mundo real. 26 2.3.2 Definição formal de um autômato híbrido Um autômato híbrido é um sistema A=(X, V, fluxo, inv, init, E, salto, D, syn), onde temos: Variáveis: é um conjunto ordenado X={x1,...,xn} de n variáveis de valores reais. Modos de Controle: Um conjunto finito de V de modos de controle. Em um termostato há dois modos de controle on e off. Condições de Fluxo: O predicado fluxo(v) é um predicado sobre as variáveis do conjunto X U X’, onde uma variável de X’ representa a derivada primeira de uma variável de X em relação do tempo. Enquanto o controle do autômato híbrido A está no modo v, para todas as variáveis de X que estão ao longo de uma curva diferenciável, todos os pontos da curva, os valores das variáveis e suas derivadas satisfazem a condição de fluxo. Por exemplo, o modo de controle on do termostato possui a condição de fluxo x’ = – x + 5 e o modo de controle off possui a condições de fluxo x’ = – x. Condições Invariantes: Uma função inv que associa uma condição invariante a cada modo de controle v de V. A condição invariante inv(v) é um predicado sobre as variáveis de X. Enquanto o autômato híbrido A está no modo v, as variáveis de X precisam satisfazer a condição invariante inv(v). O termostato do exemplo possui, em ambos os modos de controle, a seguinte condição invariante 1 ≤ x ≤ 3. Condição Inicial: Uma função init que estabelece uma condição inicial para cada modo de controle v de V. A condição inicial init(v) é um predicado sobre as variáveis de X. O controle do autômato híbrido A começa no modo de controle v quando a condição inicial init(v) é verdadeira. O modo de controle on do exemplo do termostato tem a condição inicial x = 2 e o modo de controle off tem a condição inicial igual a falso. Controle de Troca: Um conjunto finito múltiplo E de controles de troca, onde cada controle de troca (v, v’) é uma ponte direta entre um modo v de V e um modo destino v’ de V. No exemplo do termostato há dois controles de troca: (on,off) e (off,on). Condições de Salto: Uma função salto que estabelece uma condição de mudança a cada controle de troca em E. O predicado salto(e) é um predicado sobre as variáveis de X U X’. Ele faz referência aos valores das variáveis antes e depois da troca de controle. No exemplo do termostato o controle de troca (on,off) possui a seguinte 27 condição de salto: x = 3 e o controle de troca (off,on) possui o seguinte controle de salto: x = 1. Eventos: Um conjunto D de eventos e uma função syn que relaciona um evento de D a cada controle de troca e de E. O controle de troca (on,off) do exemplo do termostato corresponde a evento Desligar e o controle de troca (off,on) corresponde ao evento Ligar. O sistema trabalha com uma coleção de autômatos concorrentes, que possuem variáveis que se influenciam mutuamente criando um autômato geral cuja trajetória é uma seqüência finita de estados admissíveis, onde o primeiro estado da seqüência é a condição inicial A e cada par de estados subseqüentes na seqüência é um fluxo de A ou um salto de A. Um estado de A é alcançável se ele é o último estado de uma trajetória. O HyTech trabalha ainda com requisitos de segurança que estabelecem que algo ruim não deve acontecer durante a evolução do sistema. Um sistema satisfaz os requisitos de segurança se todos os estados alcançáveis atendem a esses requisitos. Em alguns casos, os modos de controle ou as variáveis não são suficientes para estabelecer requisitos de segurança. Assim, a descrição do sistema precisa ser aumentada com variáveis e modos de controle adicionais, chamados de monitores do autômato, que são executados juntamente com o sistema e retornam um estado de erro quando um estado inseguro é alcançado. Esses monitores, no caso do HyTech são clocks (computam o tempo máximo de execução por exemplo) e cronômetros (funcionam como acumuladores). A especificação das propriedades no Hytech é feita usando uma lógica derivada de CTL, que estende a CTL com variáveis de clock. A utilização do HyTech parece funcionar melhor, na maior parte dos casos, em sistema que possuem a maior parte das seguintes características [Henzinger et al, 2001]: Pequeno número de variáveis: para que a dimensão do sistema não excede as capacidades computacionais o sistema deve ser abstraído com o menor número possível de variáveis contínuas. Além disso, as variáveis discretas devem ser colocadas como modos de controle. Pequeno número de parâmetros: a análise com um único parâmetro é bem sucedida na maioria das vezes, mas sistemas com relações complexas entre vários parâmetros e constantes de tempo pode levar rapidamente a um overflow aritmético. Dinâmica constante: erros aritméticos são mais difíceis de ocorrer se as transformações nos valores das variáveis contínuas ocorrerem da mesma maneira. 28 Dinâmica com variação pequena: é difícil de obter aproximações quando as trajetórias mudam rapidamente. Quanto menos aproximações precisarem ser feitas maior será a possibilidade de a verificação ser bem sucedida. Baixa precisão: a probabilidade de overflow aritmético é menor se o autômato for definido com taxas e constantes com precisão relativamente baixa. O HyTech é mais adequado para descrições de alto nível do sistema, onde as variáveis têm uma dinâmica simples. O procedimento de verificação do HyTech utiliza técnicas de Model-Checking [McMillan, 1993] que podem levar muito tempo para chegarem ao fim, além de aproximações aritméticas. Ao trabalhar com ciclos e a necessidade de juntar autômatos, é necessário trabalhar com aproximações, que podem levar a estados inconsistentes. Além disso, os autômatos do HyTech são determinísticos, mas influenciados por variáveis cujos valores podem ser deixados em aberto, daí vem a necessidade de uma análise com tempo ramificado, por isso a utilização de uma lógica derivada de CTL, especializada para atender as necessidades específicas da ferramenta. 2.4 Programação em lógica com restrições Programação em lógica com restrições (CLP) é um dos desenvolvimentos mais interessantes em linguagem de programação das últimas 2 décadas. Tem grande fundamentação teórica e diversas aplicações de interesse comercial. CLP combina a natureza declarativa da programação em lógica com a eficiência dos métodos de resolução de problemas que recorrem a restrições. Ao longo dos anos, essa tecnologia tem mostrado ser eficiente na resolução de problemas que são intratáveis quando se recorre a outras técnicas. Entre esses problemas encontram-se diversas classes de problemas de natureza combinatória, tais como os problemas de escalonamento, de planejamento e de otimização. Uma das vantagens mais significativas deste modelo está presente no fato de oferecer menor tempo de desenvolvimento de programas e grande eficiência. Na programação com restrições, a especificação de relacionamentos é mais fácil, diferente de outras linguagens, como as orientadas a objetos que, devido ao pouco suporte a isso, fazem com que o programador precise explicitar todos os relacionamentos, para obter os resultados esperados. Em muitas áreas da atividade humana existem problemas que têm seu comportamento condicionado pela existência de restrições. São formas naturais para formalizar 29 as regularidades e dependências que estão presentes no mundo real. No contexto da atividade humana, podemos entender as restrições como pontos chave que constituem o senso comum na condução do raciocínio. Frases como “terei aula quarta-feira entre oito e dez horas da manhã” é uma restrição típica usada para o planejamento do tempo. Mudando para outros domínios, é possível encontrar outros exemplos de restrições: “a soma dos ângulos internos de um triângulo é 180 graus”; e “uma resistência num circuito elétrico obedece à lei de Ohm”. Restrições matemáticas especificam de forma clara e precisa as relações entre parâmetros desconhecidos (variáveis), cada um tomando um dado valor no domínio que está sendo considerado. Elas restringem os valores possíveis que as variáveis podem tomar e representam alguma informação (parcial) sobre as variáveis que estão sendo consideradas. Se considerarmos, por exemplo, a Lei de Ohm, que relaciona a diferença de potencial elétrico (V) com a intensidade da corrente elétrica (I) e a resistência elétrica (R) de um circuito e é dada pela fórmula: V=IxR Nas linguagens de programação tradicionais, cada relacionamento precisaria ser explicitado no código para que os cálculos pudessem ser feitos, em CLP basta usar a lei como se apresenta que os cálculos serão realizados, independente do que se quer encontrar, seja a voltagem, a corrente ou a resistência, dados dois valores é possível encontrar o outro. CLP pode ser usada para modelar programas complexos, envolvendo um grande número de equações, relacionamentos e restrições, por essa razão pode ser usada em diversas áreas do conhecimento. A área de Engenharia é onde foram verificados os maiores sucessos na aplicação da programação em lógica com restrições. Isso é devido ao fato de que muitos dos seus problemas têm composição hierárquica de sistemas complexos, matemáticos ou booleanos, e – especialmente no caso de diagnósticos e design – regras baseadas em raciocínio [Marriot & Stuckey, 1998]. Entretanto discute-se que a aplicação mais importante para a CLP é em problemas de ordem combinatória. Esse tipo de problema é extremamente difícil de ser modelado nas linguagens de programação tradicionais, pois o espaço de busca é exponencial, tornando inviável encontrar uma solução boa ou ótima em um tempo aceitável. A programação em lógica com restrições pode ser usada para podar o espaço de busca. As primeiras linguagens com suporte a CLP são extensões das linguagens de programação em lógica. Essas linguagens de programação são chamadas de linguagens de programa30 ção em lógica com restrições e estendem as linguagens de programação em lógica, como o Prolog, através da troca da operação de substituição por um teste de satisfação de restrições usando um constraint solver dedicado. O tratamento das relações numéricas é próxima das relações explicitadas por predicados normais em Prolog, só que sem o uso de constraint solvers as relações numéricas só pode ser testadas com os valores devidamente instanciados. Diferentes solvers e diferentes domínios de aplicação escritos em diferentes linguagens oferecem os mesmos mecanismos de avaliação. O aspecto chave da CLP é a integração entre um processo determinístico, avaliação das restrições, e um processo não-determinístico, a busca. Durante a execução do programa, o programa envia restrições para o constraint solver, que tenta resolver essas restrições. O resultado proveniente do solver, em princípio, diminui o número de alternativas a serem testadas na árvore de busca aumentando o número de regras do programa. Quando uma restrição não pode ser satisfeita a árvore que está sendo testada pode ser abandonada, reduzindo o número de alternativas, isto é, diminuindo o número de escolhas possíveis a serem exploradas via backtracking. Ao usar esse tipo de técnica é fácil trabalhar com restrições numéricas. Muitas linguagens de programação em lógica com restrições possuem constraint solvers para os domínios dos números reais e dos números racionais. A principal limitação desses solvers é que eles, em geral, trabalham apenas com equações e inequações lineares, por que o custo de trabalhar com restrições não lineares, em geral, é muito grande, em termos computacionais. Apesar dessa limitação, esse tipo de técnica mostrou ser eficiente na resolução de muitos problemas combinatórios. CLP abre também a possibilidade de falar abstratamente sobre instantes durante a ocorrência de eventos e relacioná-los a valores de propriedades contínuas, deixando que o constraint solver garanta, dinamicamente, a coerência lógica dos conjuntos de restrições estabelecidos sobre esses valores. 31 3 Modelo de Verificação Temporal No contexto de Storytelling Interativo, é importante que as histórias sejam suficientemente interessantes para envolver o usuário no processo de storytelling, onde ele assiste às histórias enquanto tem a oportunidade de interagir com elas. Como o envolvimento depende dos níveis de tensão dramática e das emoções despertadas pela narrativa, os quais variam continuamente, torna-se desejável prover meios para garantir que as narrativas são satisfatórias em termos da variação desses níveis. Note-se ainda que outros atributos das histórias como as emoções de personagens específicos, atributos da trilha sonora ou atributos de iluminação também podem variar continuamente e pode ser interessante fazer com que obedeçam a padrões desejáveis. Tendo em vista que as histórias são criadas com base em processos automáticos, duas alternativas podem ser pensadas. Uma primeira seria o autor do contexto, de modo “artesanal”, garantir que qualquer história criada atenderá aos requisitos. Tal alternativa, contudo, tende a ser tão mais difícil quanto mais capaz de gerar histórias diversificadas for o sistema. Uma segunda alternativa, que motivou o trabalho descrito nesta dissertação, é incorporar ao sistema meios para garantir automaticamente que as histórias geradas obedecem a padrões desejados. Para esse fim, modelos formais para a variação das propriedades contínuas durante os eventos devem ser especificados. A idéia básica é ser capaz de verificar o quão triste ou alegre uma história (ou parte de uma história) é. Além disso, podemos querer verificar padrões mais complexos, querendo saber, por exemplo, se um determinado capítulo gera um nível desejado de suspense, em qualquer uma das situações decorrentes da interação com o usuário. A história, por exemplo, pode ter um capítulo em que um vilão tenta seqüestrar uma vítima, com diferentes resultados possíveis. O vilão pode ter êxito, mas a vítima também pode fugir ou morrer. Se o nível desejado de suspense é atingido em qualquer situação, o capítulo pode ser considerado válido. Se não for alcançado, o capítulo pode ser descartado. 32 O modelo especificado para esse fim precisa obedecer a requisitos para que o processo global de Storytelling Interativo não seja prejudicado e que a incorporação do modelo de verificação resulte em uma melhor qualidade no conteúdo das histórias geradas. Assim, na seção 3.1, fazemos o levantamento esses requisitos, tendo em mente o objetivo de utilização do modelo dentro de um sistema de Storytelling Interativo para TV digital. Como as emoções correspondem às principais propriedades a serem consideradas, um modelo matemático para a sua representação precisa ser definido. A seção 3.2 descreve um modelo inicial proposto, o qual não tem a pretensão de ser definitivo, mas que permite a realização de experimentos. Com o tempo contínuo, o número de estados dentro de qualquer intervalo é infinito. Desta forma, é impossível enumerar todos os estados e testá-los. Uma alternativa para lidar com tal complexidade é a simplificação da forma como as propriedades podem ser representadas. A fim de ser capaz de verificar as restrições sobre os estados, criamos um modelo para a especificação de propriedades contínuas como funções do tempo de execução, conforme descrito na seção 3.3. Para falarmos das possibilidades de variação de propriedades contínuas ao longo do tempo propomos uma lógica que pretende ser expressiva o suficiente para descrever restrições relevantes, a serem satisfeitas por um capítulo de uma história com tempo ramificado e contínuo. Assim, na seção 3.4 apresentamos uma lógica que estende CTL, para permitir que esse tipo de verificação seja possível. As definições do modelo de representação das propriedades contínuas e a expressividade da lógica foram pensadas de modo a tornar viável o processo de verificação baseado em Programação em Lógica com Restrições (CLP), conforme descrito na seção 3.5. Maiores detalhes sobre a implementação do método são apresentados no Capítulo 4. 3.1 Requisitos Deseja-se verificar a satisfação de restrições dinamicamente em um ambiente de Storytelling Interativo, onde capítulos de histórias são criados e apresentados continuamente. Para que a verificação não provoque interrupções no processo, é necessário que ela ocorra em uma fração de tempo pequena quando comparada ao tempo de geração e apresentação de um capítulo. Obviamente, esses tempos podem 33 variar muito dependendo da complexidade das histórias. No entanto, se o processo de verificação puder ser executado em tempo inferior a 1s para capítulos com a complexidade dos que deverão ser gerados atualmente no Logtell 3.0 (árvores com no máximo 4 níveis e 20 eventos), pode-se garantir a viabilidade de incorporação da verificação automática no processo. É preciso definir uma lógica expressiva o suficiente para a verificação das histórias, já que consideramos que o tempo é ramificado e contínuo, o que torna o processo muito mais complexo. Essa lógica precisa ser capaz de comparar valores de diferentes propriedades em cada um dos instantes dos eventos, incluindo-se aqui o fim da história, já que pode ser interessante, por exemplo, forçar um final feliz ou triste, além de poder expressar condições mais complexas que envolvam seqüências de fatos, como no caso de se querer forçar que o nível de suspense atinja determinado nível, e após esse fato, forçar que o nível de alegria se mantenha em determinado nível. Essa demanda de expressividade exige uma lógica com definições recursivas para as fórmulas bem formadas. Além disso, a especificação da variação das propriedades deve ser natural. O autor deve poder, indicar facilmente como determinadas propriedades irão variar ao longo de cada evento, independente da história em que se encontra o evento. Desse modo, o mapeamento entre os eventos e a variação das propriedades poderá ser feito uma vez para ser reutilizado muitas vezes. No caso de propriedades correspondentes a emoções, mais do que falar sobre níveis absolutos de emoção, cabe indicar como o evento gera estímulos, ao longo de sua duração, para a variação dos níveis. Pode-se querer definir, para um certo evento, que, por exemplo, na sua primeira metade, o suspense cresce drasticamente e, na segunda metade o suspense se mantém constante enquanto o nível de medo aumenta. 3.2 Modelo de Emoções Podemos entender histórias como um conjunto finito de eventos que são logicamente conectados para que objetivos sejam atingidos. Esses eventos devem gerar picos de intensidades de emoções, com o objetivo de manter a audiência interessada na história. A seqüência de eventos também deve gerar uma tensão global durante a narrativa, que normalmente atinge um clímax que leva ao fim da história [Zagalo et al, 2004]. 34 No contexto desse trabalho, não há a pretensão de identificar a real natureza das emoções, apenas simular os seus efeitos sobre histórias. Diversos pesquisadores têm investigado as formas, os tipos e a maneira como se manifestam as emoções. Dentre diversos trabalhos, destacamos o modelo de “emoções básicas” proposto em [Plutchik, 1962; Plutchik, 1980]. A Teoria Psicoevolucionária Integrativa das Emoções é uma das mais influentes abordagens classificatórias para respostas emocionais em geral. Esse modelo considera que existem oito emoções primárias: Alegria, Antecipação, Confiança, Medo, Desgosto, Raiva, Surpresa e Tristeza. Nesse trabalho, consideramos que a combinação das emoções básicas é a abordagem mais adequada, pois é possível adaptar o modelo de Plutchik dentro de uma estrutura de n-Eixos de famílias de emoções opostas (Figura 3.1), semelhante ao que foi adotado em [Rodrigues, 2007]. Figura 3.1: Estrutura de n-Eixos de famílias de emoções opostas. Cada setor circular representa um nível de intensidade de cada emoção básica, o primeiro representa intensidade baixa, o segundo representa intensidade normal e o terceiro representa intensidade alta, para cada emoção básica. Em cada um desses 35 níveis, há nomes específicos, a Alegria em baixa intensidade é um Encanto, por exemplo. Plutchik afirma ainda que as emoções básicas podem ser combinadas em pares para que sejam formadas outras emoções que são colocadas em 4 grupos: Díades Primárias (sentidas muitas vezes), Díades Secundárias (sentidas algumas vezes), Díades Terciárias (sentidas raríssimas vezes) e Díades Opostas (não podem ser combinadas). As Díades Primárias são obtidas combinando emoções imediatamente vizinhas, por exemplo, Alegria + Antecipação = Amor. As Díades Secundárias são obtidas combinando emoções que estão distantes em dois eixos, por exemplo, Alegria + Medo = Excitação. As Díades Terciárias são obtidas combinando emoções que estão distantes em três eixos, por exemplo, Alegria + Surpresa = Perdição. E as Díades Opostas estão no mesmo eixo, porém em lados opostos, por exemplo, Alegria e Tristeza não podem ser combinadas, ou seja, não podem ocorrer ao mesmo tempo. Segundo Plutchik, as emoções básicas estão presentes nos animais inferiores, mas as emoções não-básicas costumam ser unicamente humanas, visto que a mistura de emoções básicas em emoções superiores são uma operação cognitiva. No contexto deste trabalho, porém, utilizamos um modelo simplificado, desconsiderando classificações correspondentes à intensidade das emoções básicas e ao tratamento de díades primárias, secundárias e terciárias. Assume-se que existem funções do tempo associadas a cada par de díade oposta: Alegria/Tristeza, Confiança/Desgosto, Medo/Raiva e Antecipação/Surpresa. Cada evento especifica como essas funções podem variar ao longo do evento. A estrutura de n-Eixos adotada no contexto deste trabalho está ilustrada na Figura 3.2. 36 Figura 3.2: Estrutura de n-Eixos de famílias de emoções opostas, simplificada. 3.3 Especificação dos Eventos Sabemos que existem diversas propriedades de histórias que variam continuamente ao longo do tempo de desenvolvimento da história, como os níveis de suspense, níveis de violência, níveis de tensão, emoções e etc. Obviamente, propriedades de histórias que variam ao longo do tempo, podem ser funções nãolineares do tempo. Na maioria das vezes, é, no entanto, razoável aproximá-las por meio de pedaços em que a variação é considerada linear. Essa abordagem simplifica a verificação, já que cada pedaço é representado por uma função linear e a transição de um pedaço para outro ocorre instantaneamente. Esse técnica foi aplicada com sucesso no HyTech [Alur et al, 1993; Henzinger et al, 1997] para verificar a satisfação de fórmulas temporais em tempo contínuo em autômatos híbridos temporizados. Para a verificação por meio de CLP, essa técnica também é fundamental, pois os constraint solvers para números reais ou racionais são capazes de lidar com sistemas de equações e inequações lineares, mas não com equações e inequações não-lineares. 37 Assim, para cada evento, especificamos explicitamente a derivada de cada propriedade contínua. A derivada pode variar durante o evento, mas apenas como uma seqüência de valores constantes. Cada valor constante é atribuído a uma porcentagem do tempo de execução do evento. Optamos por definir as derivadas com tempo relativo (percentual do evento) para dar flexibilidade à dramatização para alongar ou diminuir o tempo de dramatização de cada evento, essa possibilidade está presente no Logtell [Dória, 2008]. Como eventos podem ser não-determinísticos, pode existir um conjunto de curvas para as derivadas correspondentes a cada alternativa nãodeterminística. No entanto, para efeito de verificação, as alternativas nãodeterminísticas podem ser tratadas como eventos alternativos. Desse modo, no restante desta dissertação trabalharemos com apenas uma curva de derivada para cada propriedade em cada evento. Figura 3.3: Exemplo de especificação das derivadas de uma função Derivada (unidade de emoção) X Tempo (porcentagem) linearizada aos pedaços. Na Figura 3.3, cada retângulo cinza representa a área de um pedaço de um evento, que são adicionados para calcular a integral. Para calcular o nível de uma propriedade em um determinado momento, podemos integrar a derivada a partir do início da história até aquele momento, considerando a especificação da derivada para cada evento. Como conseqüência, o valor da propriedade durante a história varia como uma função linearizada aos pedaços (Figura 3.4), ou seja, temos uma função continua que foi dividida em partes lineares. 38 Figura 3.4: Gráfico de uma função linearizada aos pedaços representando uma propriedade continua versus tempo (porcentagem). Se assumirmos que o valor inicial da propriedade contínua começa com zero, o valor varia linearmente até a primeira metade do evento, quando atinge o valor 1.5. Na segunda metade, varia, também de forma linear, de 1.5 até -1.5. Desta forma, somos capazes de usar CLP no processo de verificação, pois as restrições a serem impostas sobre os valores são sempre lineares. Para que seja possível estabelecer restrições ao longo das funções de todas as propriedades a serem analisadas é preciso que os pedaços do tempo a serem analisados de ambas as funções sejam contínuos, sem pontos de inflexão, para que possamos lidar apenas com equações diferenciais simples, em que as derivadas das funções sejam valores constantes, dessa maneira o processo de verificação é facilitado, pois todas as funções analisadas serão lineares. 3.4 Um Lógica para Falar sobre Propriedades Contínuas de Histórias Interativas A lógica a ser utilizada na especificação de restrições tem que ser expressiva o suficiente para descrever restrições relevantes que devem ser satisfeitas por uma história (ou capítulos de uma história) com tempo contínuo e ramificado. Dessa forma, nossa lógica utiliza os quantificadores de caminho A e E. E os operadores de estados de um caminho G, F e U. A diferença principal de nossa lógica para CTL é que o tempo a ser considerado é contínuo, logo o número de estados é infinito, então não é possível falar sobre o próximo estado, por conseguinte não é possível utilizar o operador X. Contudo, podemos querer impor restrições sobre o fim da história (ou fim do capítulo da história). Então adicionamos o operador “end” que fala sobre a satisfação de fórmulas nesse momento específico. Esse operador é importante dentro de um contexto de Storytelling 39 Interativo, pois é típico da necessidade de restringir a forma como uma história termina (por exemplo, podemos querer forçar um final feliz). Uma fórmula temporal modal bem formada é definida recursivamente por meio da seguinte gramática (onde a e b representam combinações lineares de propriedades continuas, que possuem valores específicos a cada momento da história, e α e β representam fórmulas temporais modais): α , β → basic _ constr | AF α | AG α | EF α | EG α | A α U β (1) E α U β | A end α | E end α | α ∧ β | α ∨ β | α ⇒ β | ¬α basic _ constr → a = b | a ≠ b | a > b | a < b | a ≤ b | a ≥ b (2) A semântica para a satisfação de restrições básicas e fórmulas com os conectivos lógicos (∧,∨,¬, é ⇒) é definida da maneira usual. A semântica das fórmulas quantificadas é a mesma de CTL, mas ampliada para incorporar a noção de que estamos falando de intervalos de tempo com seqüências infinitas de estados. A Figura 3.5 apresenta graficamente o significado da combinação de quantificadores de caminho e operadores de estados do caminho. Figura 3.5: Significado da combinação de quantificadores de operadores de estado. Uma fórmula do tipo EG α significa que há pelo menos um caminho em que α será válida em todos os instantes, uma fórmula do tipo AG α significa que em todos os instantes de todos os caminhos α deverá ser válida. Uma fórmula do tipo E α U β significa que em pelo menos um caminho α será sempre válida até que β seja válida, já uma fórmula do tipo A α U β significa que em todos os caminhos α será sempre válida até que β seja válida. Uma fórmula do tipo EF α significa que há pelo menos um 40 instante em que α é válida, uma fórmula do tipo AF α significa que em todos os caminhos há pelo menos um instante em que α é válida. Uma fórmula do tipo E end α significa que há pelo menos um caminho em que α é válida no fim, uma fórmula do tipo A end α significa que α é sempre válida no fim. É possível garantir a validade dessas combinações, pois, no contexto desta dissertação, consideramos que as histórias (ou capítulos de uma história) são representadas por as árvores finitas de eventos. Considerando que α e β representam fórmulas temporais modais, é possível fazer simplificações de fórmulas compostas, reescrevendo-as como fórmulas equivalentes mais simples. Essas simplificações, listadas a seguir, são importantes para garantir a eficiência do método de verificação. 3.4.1 Simplificação de Fórmulas Compostas Quantificadores de caminho sempre antecedem operadores de estados de um caminho. Quando um par quantificador de caminho/operador de estado é aplicado sobre uma fórmula também quantificada com um par, em geral ela pode ser simplificada em (conjunções ou disjunções) de fórmulas mais simples, que podem ser mais facilmente verificadas. No processo de verificação, assume-se que, após o fim da história ou capítulo, os valores das propriedades permanecem inalterados. Isso é importante na definição da equivalência entre fórmulas, por exemplo, quando se impõe alguma restrição sobre o fim da história que fala sobre estados futuros. A Tabela 3.1 a seguir mostra um conjunto de combinações que foram estudadas e cujas simplificações, quando existem, são adotadas no método de verificação, de modo a torná-lo mais eficiente. Tabela 3.1 Tabela de equivalência de fórmulas compostas na lógica temporal ORIGINAIS FÓRMULAS EQUIVALENTES ORIGINAIS EQUIVALENTES 1. EF EG α E end α 33. EG EF α E end α 2. EF AG α E end α 34. EG AF α – 3. EF AF α – 35. EG AG α AG α 4. EF EF α EF α 36. EG EG α EG α 5. EF (E end α) E end α 37. EG (E end α) E end α 6. EF (A end α) E end α 38. EG (A end α) A end α 7. EF (E (α α U β)) – 39. EG (E (α α U β)) – 8. EF (A (α α U β)) – 40. EG (A (α α U β)) – 9. AF EG α – 41. AG EF α A end α 41 10. AF AG α A end α 42. AG AF α A end α 11. AF EF α EF α 43. AG EG α AG α 12. AF AF α AF α 44. AG AG α AG α 13. AF (E end α) E end α 45. AG (E end α) A end α 14. AF (A end α) A end α 46. AG (A end α) A end α 15. AF (E (α α U β)) – 47. AG (E (α α U β)) – 16. AF (A (α α U β)) – 48. AG (A (α α U β)) – 17. E end (EF α) E end α 49. A end (EF α) A end α 18. E end (AF α) E end α 50. A end (AF α) A end α 19. E end (EG α) E end α 51. A end (EG α) A end α 20. E end (AG α) E end α 52. A end (AG α) A end α 21. E end (E (α α U β)) E end (α α˄β) 53. A end (E (α α U β)) A end (α α˄β) 22. E end (A (α α U β)) E end (α α˄β) 54. A end (A (α α U β)) A end (α α˄β) 23. E end (E end (α) α)) α) E end α 55. A end (E end (α) α)) α) A end α 24. E end (A end (α) α)) α) E end α 56. A end (A end (α) α)) α) A end α 25. E (EF α U β) EF (β ˄ EF α) 57. A (EF α U β) AF (β ˄ EF α) 26. E (AF α U β) EF (β ˄ AF α) ˄ AF α 58. A (AF α U β) AF (β ˄ AF α) 27. E (EG α U β) EG (α α ˄ EF β) 59. A (EG α U β) – 28. E (AG α U β) (AG α) ˄ (EF β) 60. A (AG α U β) (AG α) ˄ (AF β) 29. E (E end α U β) EF (β ˄ E end α) 61. A (E end α U β) AF (β ˄ E end α) 30. E (A end α U β) (EF β) ˄ (A end α) 62. A (A end α U β) AF (β ˄ A end α) 31. E (E (α α U β) u θ) – 63. A (E (α α U β) u θ) – 32. E (A (α α U β) u θ) – 64. A (A (α α U β) u θ) – A tabela 3.1 mostra as 64 combinações possíveis de fórmulas temporais no modelo adotado no contexto desta dissertação. Algumas fórmulas não foram simplificadas por não termos conseguido obter fórmulas equivalentes mais simples ou, por não serem triviais, não chegaram a ser estudadas. Há, no entanto, casos triviais, como as fórmulas 4, 11, 12, 36, 43 e 44 que a simples observação permite que se chegue às fórmulas simplificadas. No caso das fórmulas em que o operador “end” é o mais externo, simplificações não são necessárias, pois basta que as fórmulas básicas presentes nas fórmulas compostas sejam válidas no último instante. Na seção a seguir mostraremos a explicação de algumas das simplificações listadas, as demais estão anexas à esta dissertação. 3.4.2 Demonstração de Algumas Simplificações A Figura 3.6 ilustra algumas possibilidades de ocorrência da fórmula EF EG α. 42 Figura 3.6: Representação gráfica de possibilidades de uma fórmula do tipo EF EG α ser válida Sempre que há uma fórmula do tipo EF EG α é preciso estabelecer um ponto onde α começa a valer, pois dali para frente ela precisará valer em todos os pontos de pelo menos um caminho para que a fórmula toda seja válida. Assim, esse ponto pode estar no início, no meio, ou no fim de um caminho. Se estiver no início, é preciso verificar todos os pontos dali por diante, porém pode haver um ponto entre o início e o fim do caminho onde a fórmula não seja válida. Nesse caso, um ponto mais à frente deve ser escolhido e o processo reiniciado (aumentando o tempo total de busca). No entanto, pode-se observar que a fórmula EF EG α é satisfeita se e somente se α é satisfeita no fim de um caminho, pois o ponto a partir do qual α passa a valer pode ser o último de um caminho. Desse modo, verificar uma fórmula desse tipo é equivalente a verificar uma fórmula do tipo E end α (que é bem mais simples). No caso em que a fórmula a ser verificada for EF AG α, pelos mesmos fatos expostos anteriormente, ela também pode ser simplificada para E end α. Isso ocorre porque, considerando o último ponto de um caminho, uma quantificação em todos os caminhos se confunde com a quantificação existencial. Observe, contudo, que, ao verificar uma formula do tipo EF( (x>y) ∧ EG(y>z)) a simplificação não se aplica. É necessário encontrar um instante em que (x>y) é válida e verificar desse instante em diante se existe um caminho onde (y>z) é válida em todos os estados. 43 Em uma fórmula do tipo E (EG α U β), é preciso garantir que a fórmula α seja válida em todos os estados de pelo menos um caminho e que exista pelo menos um estado, desse mesmo caminho, em que a fórmula β seja válida. Assim, uma fórmula do tipo E (EG α U β) é equivalente a uma fórmula do tipo EG (α α ˄ EF β). A Figura 3.7 ilustra possibilidades de ocorrência desse fato. Figura 3.7: Representação gráfica de possibilidades de uma fórmula do tipo E (EG α U β) ser válida Em uma fórmula do tipo A (EG α U β) é preciso garantir que a fórmula α seja válida em todos os estados de todos os caminhos até que a fórmula β seja válida Desse momento em diante, é preciso garantir que a fórmula α seja válida em todos os estados de pelo menos um caminho. Assim, não é possível encontrar uma fórmula mais simples que seja equivalente a uma fórmula do tipo A (EG α U β). A Figura 3.8 ilustra possibilidades de ocorrência desse fato. 44 Figura 3.8: Representação gráfica de possibilidades de uma fórmula do tipo A (EG α U β) ser válida Em uma fórmula do tipo E (AG α U β) é preciso garantir que a fórmula α seja válida em todos os estados de todos os caminhos e que exista pelo menos um estado em que a fórmula β seja válida. Assim, uma fórmula do tipo E (AG α U β) é equivalente a uma fórmula do tipo (AG α) ˄ (EF β). A Figura 3.9 ilustra possibilidades de ocorrência desse fato. Figura 3.9: Representação gráfica de possibilidades de uma fórmula do tipo E (AG α U β) ser válida Em uma fórmula do tipo A (AG α U β), é preciso garantir que a fórmula α seja válida em todos os estados de todos os caminhos e que exista pelo menos um estado em todos os caminhos em que a fórmula β seja válida. Assim, uma fórmula do tipo A (AG 45 α U β) é equivalente a uma fórmula do tipo (AG α) ˄ (AF β). A Figura 3.10 ilustra possibilidades de ocorrência desse fato. Figura 3.10: Representação gráfica de possibilidades de uma fórmula do tipo A (AG α U β) ser válida 3.5 Processo de Verificação Baseado em CLP Em nosso processo de verificação, os eventos são divididos em intervalos, nos quais a derivada de todas as propriedades contínuas é constante. As fórmulas devem ser transformadas para eliminar negações e condicionais utilizando a Lei De Morgan e o fato de que a negação de uma restrição básica é também uma restrição básica (ex.: a negação de A>B é A≤B). Considerando a execução de uma seqüência de eventos, é necessário impor restrições sobre os valores de cada propriedade em vários pontos durante o evento, e estabelecer a relação entre eles de acordo com as derivadas correspondentes. O processo deve ser dividido em duas partes: a verificação de caminhos e a verificação de estados de um caminho. Sempre que uma fórmula a ser verificada é universalmente quantificada em todos os caminhos (quantificador ‘A’), é necessário testar todos os caminhos a serem seguidos e, sempre que uma fórmula a ser verificada é existencialmente quantificada sobre os caminhos (quantificador ‘E’), é necessário testar os caminhos possíveis até que um deles satisfaça a fórmula ou até que todas as alternativas tenham sido testadas. 46 Sempre que uma formula é existencialmente quantificada ao longo dos estados futuros de um caminho (operador ‘F’) deve-se verificar, para cada parte do evento, duas possibilidades: a fórmula é válida em um ponto específico no intervalo ou após esse intervalo. No primeiro caso, as fórmulas a serem verificadas após essa parte devem ser identificadas e o processo precisa continuar verificando essas fórmulas. O mesmo ocorre se for identificado que as fórmulas têm que ser verificadas nos eventos subseqüentes. Sempre que uma fórmula é universalmente quantificada sobre os estados futuros de um caminho (operador ’G’) é necessário impor restrições sobre as extremidades de cada intervalo. Sempre que uma fórmula do tipo α U β tem que ser verificada, é necessário verificar se α é sempre válida em todos os estados até que β seja válida. Fórmulas com operador “end” precisam ser verificadas apenas após a execução do último evento. Durante a verificação dos estados de um caminho, o uso de CLP é importante, pois permite o estabelecimento de restrições abstratamente Além disso, o próprio sistema se encarrega de verificar se o conjunto de restrições pode ser satisfeito. Mostraremos nas seções a seguir que o procedimento descrito é eficaz para verificar restrições dinamicamente, sem prejudicar o processo de Storytelling Interativo. 47 4 Algoritmo de Verificação Este capítulo descreve um algoritmo não-determinístico para a verificação da satisfação de fórmulas em histórias não-determinísticas, de acordo com o modelo apresentado no Capítulo 3. São apresentados também os principais pontos relativos à implementação determinística desse algoritmo utilizando programação em lógica com restrições no domínio dos reais (Constraint Logic Programming over Reals - CLPR). Há versões rodando tanto no SICStus Prolog [SICStus] quanto no SWI Prolog [SWI]. Inicialmente serão descritas as principais estruturas de dados correspondentes à especificação de eventos, histórias e fórmulas. Em seguida, será apresentado o algoritmo em pseudocódigo. A tradução das execuções não-determinísticas de procedimentos para CLP foi feita usando backtracking cronológico. 4.1 Estruturas de Dados 4.1.1 Eventos Como visto anteriormente, as histórias são modeladas como árvores finitas de eventos, cada evento é modelado através do predicado Prolog event/5 que possui os seguintes dados: • Nome: cada evento possui um único nome. • Listas para as propriedades emocionais formadas por pares onde o primeiro elemento do par representa a porcentagem do tempo e o segundo elemento do par representa o nível da emoção naquele instante (obrigatoriamente o primeiro elemento da lista representa o início do evento, 0%, e o último elemento da lista representa o fim do evento, 100%): o Alegria/Tristeza. o Medo/Raiva. 48 o Confiança/Desgosto. o Antecipação/Surpresa O evento Lobo Mata o Caçador, por exemplo, está no banco de dados do exemplo apresentado no capítulo 5 da seguinte forma: event(wolf_kills_hunter, [(0,-50),(35,-70),(40,-100),(50,-80),(60,-85),(80,-95),(100,0)], [(0,0),(100,0)],[(0,0),(100,0)],[(0,-100),(100,0)]). Os eventos podem ter mais de uma modelagem para as suas emoções, com várias cláusulas correspondentes ao mesmo evento, mas com valores diferentes para as derivadas. Nos testes realizados, por simplicidade, foi considerada a existência de apenas uma modelagem para cada evento. 4.1.2 Histórias (ou Capítulos de uma História) As histórias são modeladas pelo predicado Prolog story/2, onde o primeiro elemento do par representa o nome da história (ou um identificador de capítulo) e o segundo elemento representa a árvore de eventos. A árvore de eventos é uma tripla, onde o primeiro elemento é um conjunto de pré-condições que devem ser satisfeitas para que uma árvore (ou subárvore) seja válida, por exemplo, para que o mocinho salve a mocinha ela precisa estar em perigo. Há a possibilidade de existirem várias árvores, com diferentes pré-condições, para uma mesma história (ou capítulo) assim, no momento da verificação é necessário considerar essas diferentes possibilidades (as précondições não são consideradas no contexto deste trabalho, apesar de previstas no Logtell [Silva, 2010]). O segundo elemento é a raiz da árvore e o terceiro é uma subárvore. No contexto deste trabalho, as histórias foram modeladas manualmente, porém, dentro de um sistema de storytelling interativo elas serão adicionadas ao banco de dados de fatos dinamicamente após serem geradas. Havendo várias alternativas para a mesma história (ou capítulo) é possível selecionar uma que satisfaça a fórmula. Uma história simples pode ser modelada da seguinte maneira: story(story1,(COND1,event1,[(COND21,(event21,SUBARV21)),..., (COND2n,(event2n,SUBARV2n))])). 49 Usamos a notação Prolog “lista vazia” ([]) para árvores (ou subárvores) que não possuem folhas, ou seja, possuem apenas raiz. 4.1.3 Fórmulas No contexto deste trabalho, dentro de uma fórmula podem ser identificados três tipos de subfórmulas, de acordo com a lógica apresentada no Capítulo 3: • Básica: Restrição simples colocada entre chaves “{}” que representa uma equação ou uma inequação linear. Ex.: {X ≥ 0.0}. • Quantificada: Uma fórmula α (composta, básica ou quantificada) é dita quantificada quando é precedida de um quantificador de caminho. Ex.: EF α. • Composta: Quando uma fórmula é formada por duas ou mais fórmulas unidas por conectivos lógicos (˄, ˅ ou ⇒) dizemos que ela é composta. Ex.: EF α ˄ AF β. No contexto deste trabalho as fórmulas precisam ser normalizadas. O primeiro passo do processo consiste na remoção de implicações em todas as partes das fórmulas utilizando a Lei De Morgan. Ex.: EF {X = 0.0} ⇒ AG {X < 0.0} é equivalente a ¬ EF {X = 0.0} ˅ AG {X < 0.0} O passo seguinte consiste na remoção de negações, movendo-as para dentro das fórmulas básicas. Ex.: ¬ EF {X = 0.0} ˅ AG {X < 0.0} é equivalente a AG {X ≠ 0.0} ˅ AG {X < 0.0} No último passo, fórmulas compostas e quantificadas são levadas para uma forma normal onde, em cada nível de quantificação, as fórmulas são sempre disjunções de conjunções. Durante o processo de normalização, também são feitas as simplificações lógicas descritas no capítulo 3. Essa fórmula final recebe o nome de fórmula normalizada. Há duas exceções no processo de normalização: 50 • Fórmulas dos tipos AG α ou EG α, sendo α uma disjunção de fórmulas (básicas ou quantificadas) ou uma fórmula do tipo v1≠v2, são sinalizadas para serem verificadas, por negação como falha, como ¬EF ¬α e ¬AF ¬α, respectivamente. • As negações de fórmulas dos tipos A α U β ou E α U β são sinalizadas para serem verificadas, por negação como falha, como ¬A ¬(α U β) e ¬E ¬(α U β), respectivamente. 4.2 Algoritmo Básico A Figura 4.1 mostra o algoritmo utilizado para satisfazer fórmulas temporais modais em histórias não-determinísticas, que pode ser usado de duas maneiras: (i) para verificar se uma determinada história atende às restrições impostas por uma fórmula ou (ii) para selecionar histórias (ou capítulos) que atendam a essas restrições. Os dados de entrada são: • fórmula: conjunto de restrições lógicas (conforme sintaxe descrita no Capítulo 3 desta dissertação) que se deseja satisfazer o ex.: EF {ALEGRIA > 0.0}, que significa: existe um ponto no futuro em que a alegria é maior que zero. Por conta da especificação de CLP para o conjunto dos números reais, as restrições numéricas devem ser colocadas entre chaves. • variáveis: lista contendo as variáveis presentes na fórmula o Variáveis são utilizadas para representar o valor das propriedades nos intervalos de tempo. • propriedades: lista contendo as propriedades que serão atribuídas a cada uma das variáveis o ex.: PROPRIEDADES = [joy, fear], ou seja, apenas as curvas da propriedade alegria e da propriedade medo de cada evento deverão ser consideradas. • história: história a ser verificada. As histórias são representadas sob a forma de uma árvore de contingências, em que cada nó corresponde a um evento e cujos ramos correspondem às alternativas de continuidade da história. Eventos determinísticos possuem apenas um ramo e levam a outro nó (associado a outro evento); caso haja efeitos não-determinísticos, os ramos 51 correspondentes levam a novos nós que corresponderão a eventos a serem verificados. Eventos sem sucessores são associados a nós terminais, ou seja, aqueles que não possuem ramos. Caso o usuário indique a história, presente no banco de dados do sistema, que deseja verificar, é retornado se a história (árvore) atende às restrições da fórmula ou não. Caso o usuário não forneça a história que deseja verificar, o sistema verificará, por backtracking, quais histórias armazenadas na base satisfazem a fórmula e as retornará instanciando o parâmetro correspondente à história. Na seqüência deste capítulo, utilizaremos a seguinte notação na descrição dos algoritmos: o símbolo “+” antes de um parâmetro indica que ele é um dado de entrada, o símbolo “–” antes de uma variável indica que ele é um dado de saída e o símbolo “?” que é um dado que pode ser de entrada ou de saída. Verifica(+FÓRMULA,+VARIÁVEIS,+PROPRIEDADES,?HISTÓRIA) // Variáveis locais: // VALOR_INICIAL: lista de valores iniciais para as propriedades // RET: resultado de validação de história específica // Valor de retorno: sucesso/falha FORMULA_NORM=normaliza(FORMULA) // Simplificações possíveis são feitas aqui Para cada propriedade P em PROPRIEDADES VALOR_INICIAL[posição(P)]=0.0 Anotar como atributo da VARIÁVEL[posicao(P)] que ela está associada à propriedade P SE HITÓRIA está instanciada Retorne Validar_formula(FORMULA_NORM,VARIÁVEIS,VALOR_INICIAL,HISTÓRIA) SENÃO Para cada história H armazenada na base de dados RET=Validar_formula(FORMULA_NORM,VARIÁVEIS,VALOR_INICIAL,H) SE (RET<>falha) HISTORIA=H Retorne Sucesso Retorne falha Fim Verifica Figura 4.1: Algoritmo para verificação de fórmulas temporais modais em histórias não-determinísticas. Nosso algoritmo principal, apresentado na Figura 4.1, recebe uma fórmula especificada de acordo com a gramática apresentada no capítulo anterior desta dissertação. A fórmula é transformada inicialmente, eliminando condicionais e formas negativas. Isso é possível usando a regra do condicional, as leis de De Morgan e o fato 52 de que negação de uma restrição básica é também uma restrição básica (ex.: a negação de a ≥ b é a < b). Durante o processo de normalização, as simplificações indicadas no Capítulo 3 também são feitas. Após essa etapa inicial, é preciso validar a fórmula que será verificada. Para isso, é necessário identificar se a fórmula é uma disjunção ou uma conjunção de fórmulas, ou se é uma fórmula temporal já quantificada (ex.: EF {ALEGRIA>0.0}). Na Figura 4.2, está ilustrado o algoritmo responsável por essa etapa. Validar_formula(+FORMULA_NORM,+VARIÁVEIS,+VALOR_ACUM,+HISTÓRIA) // Variáveis locais: RET e RET1: valores de retorno correspondentes à verificação de subfórmulas // Valores de retorno: sucesso/falha SE quantificada(FORMULA_NORM) Retorne Validar_quantificada(SUBFORMULA,QUANT_CAM, OP_EST,VARIAVEIS,VALOR_ACUM,HISTÓRIA) SENÃO SE FORMULA_NORM= F1 ˅ F2 RET=Validar_formula(FORMULA_NORM,VARIÁVEIS, VALOR_ACUM,HISTÓRIA) SE (RET<>falha) Retorne Sucesso SENÃO RET1=Validar_formula(F2,VARIÁVEIS,VALOR_ACUM,HISTÓRIA) SE (RET1<>falha) Retorne Sucesso SENÃO Retorne Falha SE FORMULA_NORM= F1 ˄ F2 RET=Validar_formula(F1,VARIÁVEIS,VALOR_ACUM,HISTÓRIA) SE (RET<>falha) RET1=Validar_formula(F2,VARIÁVEIS,VALOR_ACUM,HISTÓRIA) SE (RET1<>falha) Retorne Sucesso SENÃO Retorne Falha Fim Validar_formula Figura 4.2: Algoritmo para validação das fórmulas temporais. Para a verificação de uma história, duas tarefas precisam ser adequadamente combinadas: (i) a verificação de caminhos alternativos e (ii) a verificação de estados ao 53 longo de um caminho. Na seção a seguir, é apresentada a função que trata da verificação de fórmulas quantificadas. 4.3 Verificação de fórmulas quantificadas A verificação nesse ponto é feita para uma árvore que tem um primeiro evento e diferentes possibilidades de continuação. A fórmula a ser verificada possui uma única quantificação mais externa, combinando quantificador de caminhos e operador de estados. Como um evento pode ter mais de uma definição para as derivadas de suas propriedades contínuas, o quantificador de caminho precisa ser levado em conta nesse ponto. Ele será levado em conta também mais à frente para decidir como alternativas de continuação devem ser verificadas. Sempre que uma fórmula a ser verificada é existencialmente quantificada sobre os caminhos (quantificador ‘E’), testamos se há uma atribuição de derivadas que satisfaz a fórmula. Neste caso, quando a satisfação é verificada para uma atribuição, as demais não são verificadas, porque não é mais necessário já que a fórmula é satisfeita. Sempre que uma fórmula a ser verificada é universalmente quantificada em todos os caminhos (quantificador ‘A’), testamos todas as possíveis atribuições de derivadas às propriedades. Se, para uma dada atribuição, não for válida, então a fórmula não é satisfeita. A Figura 4.3 ilustra o algoritmo. A chamada para validar a partir do primeiro evento, com a curva de derivadas escolhida, cuidará de todo o processamento dos eventos e das alternativas de continuação após o evento. 54 Validar_quantificada(+FORMULA, VARIAVEIS,+VALOR_ACUM,+HISTÓRIA) // Variáveis Locais: // EVENTO= primeiro_evento da HISTÓRIA: Cada evento pode ter mais de uma modelagem para as curvas e // DERIV: para cada evento há um (ou mais) conjunto(s) de lista(s) de propriedades, DERIV é uma lista que cada modelagem tem a seguinte estrutura -> event(NAME,P1,...,Pn), onde cada P representa uma propriedade. contém as listas de propriedades. // INTERV_DERIV: lista de pares, onde o primeiro elemento do par representa a porcentagem do tempo e o segundo elemento é uma lista que possui o valor da derivada de cada uma das propriedades que estão sendo analisadas entre aquele tempo e o próximo. A variável possui a seguinte estrutura: [(T1,[Derivada_P1,...,Derivada_Pn]),..., (Ti,[Derivada_P1,...,Derivada_Pn]),...]. // ALTS= alternativas_de continuação da HISTORIA: cada alternativa é uma subárvore com respectivos eventos e possibilidades de continuaçãodois elementos (RAIZ,SUBARVORE). // Valor de retorno: sucesso/falha QUANT_CAM= quantif_caminho(FORMULA) OP_EST = operador_estado(FORMULA) EVENTO=primeiro_evento(HISTORIA) ALTS=alternativas_continuacao(HISTORIA) SUBFORMULA = subformula(FORMULA) SE QUANT_CAM="E" De forma não-determinística escolha uma alternativa de derivadas DERIV associada a EVENTO Quebra_em_partes(DERIV, INTERV_DERIV) Retorne Validar_a_partir_de_evento(SUBFORMULA,QUANT_CAM,OP_EST, VARIÁVEIS,VALOR_ACUM,INTERV_DERIV,ALTS) SE QUANT_CAM="A" Para cada alternativa de derivadas DERIV associada a EVENTO Quebra_em_partes(DERIV, INTERV_DERIV) SE (Validar_a_partir_de_evento(SUBFORMULA,QUANT_CAM,OP_EST,VÁRIAVEIS, VALOR_ACUM,INTERV_DERIV,ALTS)=falha) Retorne falha Retorne sucesso Fim Validar_quantificada Figura 4.3: Algoritmo não-determinístico de verificação de caminhos Antes de entrar no processo de verificação dos estados em si, é necessário quebrar os eventos em intervalos onde os valores de todas as derivadas das propriedades contínuas que estão sendo verificadas são constantes. Na Figura 4.4, suponha que um evento ocorre entre os tempos T0 e T3. O tempo T1 é o momento em que a derivada da propriedade P1 muda de valor e o tempo T2 é o momento em que a derivada da propriedade P2 muda de valor. Os pedaços do evento a serem analisados, em seqüência, correspondem aos intervalos [T0,T1], [T1,T2] e [T2,T3]. 55 Figura 4.4: Quebrando eventos em intervalos de derivadas constantes Durante o processo, o valor de cada propriedade nas extremidades de cada pedaço é representado por uma variável, e tais variáveis estão relacionadas entre si por meio de restrições que calculam os valores de acordo com as derivadas. A execução simbólica é então realizada, calculando os valores ao longo dos ramos. Para calcular a variação no valor de uma propriedade em um intervalo de tempo particular, nós apenas integramos suas derivadas, adicionando os valores de cada intervalo, de acordo com a seguinte fórmula: T −T Li = Di × i +1 i 100 (3) Na fórmula acima, Ti representa a porcentagem do tempo correspondente e Di representa a derivada constante associada ao intervalo entre Ti e Ti+1. Li representa a variação do nível da propriedade entre Ti e Ti+1. No algoritmo da Figura 4.3, a chamada ao procedimento Quebra_em_partes é que cuida desta divisão do evento em intervalos. Note que no algoritmo da Figura 4.3 também é identificado o operador de estado da fórmula corrente (‘F’, ‘G’, ‘U’ ou “end”) para que o processamento adequado seja feito para o evento. 4.4 Verificação de estados ao longo de um caminho Para realizar a verificação dentro do primeiro evento é necessário verificar o operador de estados de um caminho associado à fórmula. As funções Validar_F, Validar_G, Validar_U e Validar_END cuidam da acumulação dos valores das propriedades ao longo do intervalo e do estabelecimento de restrições correspondentes à 56 fórmula de acordo com o respectivo operador de estado. Quando, após o evento, é necessário continuar o processo de verificação ao longo do caminho, a fórmula que precisa ser verificada na continuação é calculada e retornada para ser repassada à função Validar_alts que trata da verificação levando em conta as alternativas de continuação. A Figura 4.5 ilustra o algoritmo responsável por essa tarefa. Validar_a_partir_de_evento(+SUBFORMULA, +QUANT_CAM, +OP_EST, +VARIÁVEIS, +VALOR_ACUM, +INTERV_DERIV, +ALTS) // Variáveis_locais: // A variável possui a seguinte estrutura: [P1,...,Pn], onde cada variável P é uma lista formada por pares (porcentagem_do_tempo,derivada) que indica o valor da derivada de cada propriedade considerada daquele tempo até o próximo, onde o último elemento é sempre (100,0). // FORMULA_CONT: Fórmula a ser verificada após o evento corrente. // VALOR_ACUM2: Lista com valor acumulado das propriedades ao final do evento // Valores de retorno: sucesso/falha SE (OP_EST="F") SE Validar_F(SUBFORMULA, VARIÁVEIS, VALOR_ACUM, INTERV_DERIV, FORMULA_CONT, VALOR_ACUM2) SE (FORMULA_CONT='true') Retorne Sucesso SENÃO FORMULA = compõe_quantificada(SUBFORMULA, QUANT_CAM, OP_EST) SE (SUBFORMULA=FORMULA_CONT) FORMULA_CONT1 = FORMULA SENÃO FORMULA_CONT1=FORMULA_CONT Retorne Validar_alts(FORMULA_CONT1, VARIÁVEIS, VALOR_ACUM2, ALTS) SE (OP_EST="G") FORMULA_ADIC=true SE Validar_G(SUBFORMULA, VARIÁVEIS, VALOR_ACUM, INTERV_DERIV, FORMULA_ADIC, FORMULA_CONT,VALOR_ACUM2) FORMULA = compõe_quantificada(SUBFORMULA, QUANT_CAM, OP_EST) SE (FORMULA_CONT= ‘true’) FORMULA_CONT1 = FORMULA SENÃO FORMULA_CONT1=FORMULA ˄ FORMULA_CONT Retorne Validar_alts(FORMULA_CONT1, VARIÁVEIS,VALOR_ACUM2,ALTS) SENÃO Retorne falha SE (OP_EST="U") Retorne Validar_U(SUBFORMULA,QUANT_CAM,VARIÁVEIS,VALOR_ACUM,INTERV_DERIV, ALTS) 57 SE (OP_EST="END") SE Validar_END(VALOR_ACUM,INTERV_DERIV,VALOR_ACUM2) Retorne Validar_alts(FORMULA, VALOR_ACUM2,ALTS) SENÃO Retorne falha Fim Validar_a_partir_de_evento Figura 4.5: Algoritmo para validação das fórmulas a partir de um evento. Para cada operador há uma forma de realizar o processo de validação, que se deve à própria especificação dos operadores. Quando é necessário lidar com o operador ‘F’ é chamada a função Validar_F que recebe uma fórmula sem quantificadores e tenta descobrir se há algum momento dentro do evento atual em que a fórmula é válida, essa função sempre retorna algum valor para a variável FORMULA_CONT (fórmula a ser verificada nos eventos subseqüentes), caso o valor dessa variável seja ‘true’ a busca termina e é retornado sucesso, caso contrário é necessário verificar se FORMULA_CONT quantificada com o quantificador de caminho atual e o operador de estado ‘F’ (compõe_quantificada realiza essa tarefa) é igual à fórmula que foi passada para ser validada pela função Validar_F (SUBFORMULA), caso positivo, a fórmula de continuação (FORMULA_CONT1) será a própria fórmula inicial (FORMULA_CONT1 = FORMULA), caso contrário FORMULA_CONT1 = FORMULA_CONT e então é chamado o processamento das alternativas (Valida_alts). Quando é necessário lidar com o operador ‘G’ é chamada a função Validar_G que recebe SUBFORMULA e a variável FORMULA_ADIC que funciona como uma variável auxiliar e recebe fórmulas geradas pelo processo de verificação devido a peculiaridades da lógica, como por exemplo quando se está lidando com uma fórmula do tipo EG AF α onde a fórmula AF α deverá ser verificada para todos os caminhos. Após o processo de verificação, caso não seja retornado falha analisa-se o valor de FORMULA_CONT, caso o valor seja ‘true’ a fórmula original precisa ser quantificada e passada para ser verificada nos eventos subseqüentes, já que uma fórmula com o operador ‘G’ precisa ser reforçada a cada instante, caso contrário FORMULA_CONT1 = FORMULA ˄ FORMULA_CONT, pois, além de reforçar a validade da fórmula original é preciso verificar a validade da fórmula gerada pelo processo de verificação. Quando é necessário lidar com o operador ‘U’ é chamada a função Validar_U que não retorna fórmulas para serem verificadas nesse nível já que as fórmulas que são geradas pelo processamento de fórmulas desse tipo é essencialmente diferente, pois o processo de verificação para os próximos eventos pode ser para uma fórmula com o 58 operador ‘U’ ou com outro tipo de fórmula e essa análise precisa ser feita em separado, assim o Validar_U trata dentro dele todas as possibilidades. Quando é necessário lidar com o operador ‘end’ é chamada a função Validar_END que apenas acumula os valores das variações dos intervalos de cada evento e repassa a fórmula para os eventos subseqüentes até que não hajam mais alternativas a serem verificadas e, nesse momento, a fórmula é verificada. No processamento dos eventos é necessário verificar a validade das fórmulas a cada intervalo que os compõem, esse processo envia fórmulas para o constraint solver para que ele verifique se o conjunto de fórmulas é satisfatível. Maiores detalhes sobre os algoritmo e a implementação das funções mencionas neste capítulo funções estão detalhados no Anexo II desta dissertação. 4.5 Adicionando restrições aos intervalos Devido ao fato de que as propriedades de tempo contínuo têm derivada constante durante o intervalo, uma restrição do tipo a>b (onde a e b representam combinações lineares de propriedades contínuas) é válida ao longo de um intervalo se e somente se ela for válida nas extremidades do intervalo. A fim de impor a satisfação da fórmula, as restrições sobre as extremidades dos intervalos, representada pelos círculos na Figura 4.6, são então enviadas para o constraint solver. Figura 4.6: Impondo restrições nos eventos Quando como o processo está sendo verificado dentro de um operador ‘F’, é preciso verificar a validade da fórmula apenas a partir de um ponto genérico T (quadrados na figura 4.6) até o fim do intervalo. Na figura 4.7 está ilustrado o algoritmo que estabelece essas restrições. 59 Adiciona_restricoes_intervalo_F(+FORMULA, +VARIÁVEIS, +VARIACAO, +VALOR_ACUM, +T1, +T2, -T_VALID, -PERC) copia_restricoes(VARIÁVEIS,CÓPIA_VARIÁVEIS,FORMULA,CÓPIA_FORMULA) SE (adiciona_restricao(PERC>=0.0 and PERC<=1.0)= falha) Retorne falha PARA CADA Propriedade P SE (adiciona_restricao(CÓPIA_VARIÁVEIS[posicao(P)]= VALOR_ACUM[posicao(P)] + PERC * VARIACAO[posicao(P)])=falha) Retorne falha SE (adiciona_restricao(T_VALID=T1+(T2-T1)*PERC)=falha) Retorne falha SE (adiciona_restricao(CÓPIA_FORMULA)=falha) Retorne falha Retorne sucesso Fim adiciona_restricoes_intervalo_F Figura 4.7: Algoritmo que impõe e verifica as restrições para uma fórmula existencialmente quantificada. A Figura 4.7 apresenta a adição de restrições correspondentes a uma fórmula quantificada com o operador de estado ‘F’ em um tempo genérico T_VALID entre o tempo de início do intervalo T1 e o tempo final T2. A variável PERC indica o percentual da diferença entre T1 e T2 correspondente ao tempo T_VALID e deve ser restringida a assumir um valor entre 0% e 100%. Variáveis Prolog novas são usadas para representar os valores das propriedades contínuas. Uma cópia da fórmula, definida em termos dessas variáveis, é gerada. Restrições correspondentes ao cálculo dos valores das propriedades contínuas em T_VALID são enviadas para o constraint solver (note que essas restrições podem ser descritas por equações lineares, uma vez que todas as derivadas são constantes dentro de um intervalo). Além disso, as restrições da fórmula correspondentes ao tempo T_VALID também são enviadas para o constraint solver. Os quadrados no meio dos intervalos na Figura 4.6 representam a imposição de restrições correspondentes ao instante T_VALID. Essas restrições são tratadas pelo constraint solver e uma falha ocorre se e somente se o conjunto de restrições não pode ser satisfeito. É importante deixar claro que as variáveis PERC e T_VALID não estão instanciadas, mas têm os seus valores restringidos para atender à satisfação da fórmula. Note, por exemplo, que, se uma fórmula do tipo AF((x>y) ∧ EG(y>z)) está sendo verificada, é necessário encontrar um instante em que (x>y) vale e verificar desse momento em diante se há um caminho em que (y>z) sempre vale. E quando temos uma fórmula do tipo AF((x>y) ˅ EG(y>z)) é necessário verificar a validade de (x>y) e de EG (y>z) em paralelo, pois qualquer uma das duas pode ser válida em determinado intervalo, além disso, a verificação de fórmulas básicas do tipo a≠b é feita de forma 60 indireta, forçando a falha na verificação de a=b. Esses fatos são apresentados pelo algoritmo da Figura 4.8. Adiciona_restricoes_intervalo_FG(+FORMULA, +VARIÁVEIS, +VARIACAO, +VALOR_ACUM, +T1, +T2, −T_VALID, −PERC) copia_restricoes(VARIÁVEIS,CÓPIA_VARIÁVEIS,FORMULA,CÓPIA_FORMULA) copia_restricoes(VARIÁVEIS,CÓPIA_VARIÁVEIS1,FORMULA,CÓPIA_FORMULA1) SE (CÓPIA_FORMULA = {A <> B}) CÓPIA_FORMULA2 = {A = B} // essa atribuição tem q falhar SE (adiciona_restricao(PERC>=0.0 and PERC<=1.0)= falha) Retorne sucesso PARA CADA Propriedade P SE (adiciona_restricao(CÓPIA_VARIÁVEIS[posicao(P)]= VALOR_ACUM[posicao(P)] + PERC * VARIACAO[posicao(P)])=falha) Retorne sucesso SE (adiciona_restricao(T_VALID=T1+(T2-T1)*PERC)=falha) Retorne sucesso SE (adiciona_restricao(CÓPIA_FORMULA)=falha) Retorne sucesso Retorne falha SE (CÓPIA_FORMULA <> {A <> B}) SE (adiciona_restricao(PERC>=0.0 and PERC<=1.0)= falha) Retorne falha PARA CADA Propriedade P SE (adiciona_restricao(COPIA_VARIÁVEIS[posicao(P)]= VALOR_ACUM[posicao(P)] + PERC * VARIACAO[posicao(P)])=falha) Retorne falha SE (adiciona_restricao(COPIA_VARIÁVEIS1[posicao(P)]= VALOR_ACUM[posicao(P)] + VARIACAO[posicao(P)])=falha) Retorne falha SE (adiciona_restricao(T_VALID=T1+(T2-T1)*PERC)=falha) Retorne falha SE (adiciona_restricao(CÓPIA_FORMULA)=falha) Retorne falha SE (adiciona_restricao(CÓPIA_FORMULA1)=falha) Retorne falha Retorne sucesso Fim adiciona_restricoes_intervalo_FG Figura 4.8: Algoritmo que verifica a validade de uma subfórmula com o operador ‘G’. No caso de uma fórmula com um operador ‘G’ sendo testada dentro de uma fórmula com o operador ‘F’ tem um tratamento especial, pois a fórmula com o operador ‘G’ precisam valer apenas a partir do tempo indicado pela variável T_VALID até o fim do intervalo representado pela variável T2, a representação desses fatos é feita 61 abstratamente. Como já pode existir um conjunto de restrições para o T_VALID no constraint solver, ao receber novas restrições impostas pelo algoritmo da Figura 4.8 há a verificação de validade desse conjunto, note que aqui são criadas duas cópias da fórmula, uma para cada extremo do intervalo, todo o conjunto é enviado ao constraint solver que verifica a validade em sendo válido o conjunto é retornado sucesso se houver alguma inconsistência no conjunto o sistema retorna falha. A figura 4.9 ilustra o algoritmo responsável pelo estabelecimento de restrições à fórmula quando se está trabalhando com o operador ‘G’. Adiciona_restricoes_intervalo_G(+FORMULA,+VARIÁVEIS,+VARIACAO,+VALOR_ACUM) // Variável Local: PERCENT: É utilizada aqui apenas para forçar que a fórmula ocorra no intervalo copia_restricoes(VARIÁVEIS,CÓPIA_VARIÁVEIS,FORMULA,CÓPIA_FORMULA) copia_restricoes(VARIÁVEIS,CÓPIA_VARIÁVEIS1,FORMULA,CÓPIA_FORMULA1) SE (CÓPIA_FORMULA = {A <> B}) CÓPIA_FORMULA2 = {A = B} // essa atribuição tem q falhar SE (adiciona_restricao(PERCENT>=0.0 and PERCENT<=1.0)= falha) Retorne sucesso PARA CADA Propriedade P SE (adiciona_restricao(CÓPIA_VARIÁVEIS[posicao(P)]= VALOR_ACUM[posicao(P)] + PERC * VARIACAO[posicao(P)])=falha) Retorne sucesso SE (adiciona_restricao(CÓPIA_FORMULA)=falha) Retorne sucesso Retorne falha SE (CÓPIA_FORMULA <> {A <> B}) PARA CADA Propriedade P SE (adiciona_restricao(COPIA_VARIÁVEIS[posicao(P)]=VALOR_ACUM[posicao(P)])=falha) Retorne falha SE (adiciona_restricao(COPIA_VARIÁVEIS1[posicao(P)]=VALOR_ACUM[posicao(P)] + VARIACAO[posicao(P)])=falha) Retorne falha SE (adiciona_restricao(CÓPIA_FORMULA)=falha) Retorne falha SE (adiciona_restricao(CÓPIA_FORMULA1)=falha) Retorne falha Retorne sucesso Fim Adiciona_restricoes_intervalo_G Figura 4.9: Algoritmo que impõe e verifica as restrições para uma fórmula globalmente quantificada. Após a verificação das fórmulas em um evento, se houver fórmulas a verificar é necessário realizar o processo nos eventos subseqüentes, esse procedimento é chamado de processamento de alternativas e está detalhado a seguir. 62 4.6 Processamento de Alternativas A Figura 4.10 ilustra o algoritmo que realiza o processamento das alternativas. Validar_alts(+FORMULA,+VARIÁVEIS,+VALOR_ACUM,+ALTS) SE ALTS <> Ø SE FORMULA = 'true' Retorne sucesso SE quantificada(FORMULA) QUANT_CAM= quantif_caminho(FORMULA) SE QUANT_CAM="E" De forma não-determinística escolha uma das alternativas ALT em ALTS Retorne Validar_quantificada(FORMULA, VARIÁVEIS, VALOR_ACUM, ALT) SE QUANT_CAM="A" Para todas as alternativas ALT de ALTS SE (Validar_quantificada(FORMULA, VARIAVEIS, VALOR_ACUM, ALT)=falha) Retorne falha SE ALTS = Ø SE FORMULA = 'true' Retorne sucesso SE quantificada(FORMULA) QUANT_CAM= quantif_caminho(FORMULA) OP_EST = operador_estado(FORMULA) SUBFORMULA = subformula(FORMULA) SE (QUANT_CAM = 'F') Retorne falha SE (QUANT_CAM = 'G') Retorne sucesso SE (QUANT_CAM = 'U') Retorne falha SE QUANT_CAM = 'END' SE (Força_validade_END(SUBFORMULA,VARIÁVEIS,VALOR_ACUM) = falha) Retorne falha Retorne sucesso Fim Validar_alts Figura 4.10: Algoritmo de verificação de alternativas. No processamento de alternativas, há sempre duas possibilidades que devem ser consideradas: (i) há alternativas e (ii) não há alternativas. No primeiro caso se ainda houver alternativas e a fórmula for diferente de 'true' o processo segue para os eventos subseqüentes, caso contrário a busca termina. No segundo caso é preciso analisar o operador da fórmula que precisa ser verificada, se o operador for do tipo ‘F’ ou do tipo 63 'U' significa que a fórmula não foi válida naquele caminho, se o operador for do tipo 'G' significa que a fórmula foi válida ao longo de todos os estados daquele caminho, assim a busca termina com sucesso, se o operador for do tipo 'END' é necessário realizar a verificação das fórmulas para esse instante final, na Figura 4.11 está ilustrado o algoritmo que realiza esse procedimento. Força_validade_END (FORMULA,VARIÁVEIS, VALOR_ACUM) SE básica(FORMULA) copia_restricoes(VARIÁVEIS,CÓPIA_VARIÁVEIS,FORMULA,CÓPIA_FORMULA) PARA CADA Propriedade P SE (adiciona_restricao(COPIA_VARIÁVEIS[posicao(P)]=VALOR_ACUM[posicao(P)])=falha) Retorne falha SE (adiciona_restricao(CÓPIA_FORMULA)=falha) Retorne falha Retorne sucesso SE (FORMULA = F1 ˄ F2) SE (Força_validade_END(F1,VARIÁVEIS,VALOR_ACUM) = falha) Retorne falha SE (Força_validade_END(F2,VARIÁVEIS,VALOR_ACUM) = falha) Retorne falha Retorne sucesso Fim Força_validade_END Figura 4.11: Algoritmo que impõe e verifica as restrições para uma fórmula no fim de um caminho. No caso de fórmulas com o operador “end”, há dois casos possíveis: (i) a fórmula a ser testada é básica ou (ii) a fórmula a ser testada é uma conjunção de fórmulas. No primeiro caso basta enviar as restrições impostas pela fórmula, sobre o valor acumulado para o constraint solver. No segundo caso é necessário que as duas fórmulas da conjunção sejam válidas para que o processo retorne sucesso. No próximo capítulo apresentamos uma aplicação prática, dentro do contexto de Storytelling Interativo, dos formalismos até aqui apresentados, expondo os resultados obtidos no contexto desta pesquisa. 64 5 Exemplo de Aplicação do Método Em nosso protótipo, as restrições são especificadas por meio da lógica temporal modal descrita no Capítulo 3. O protótipo implementa o algoritmo descrito no Capítulo 4. Como explicado anteriormente, as histórias não-determinísticas (ou seus capítulos) são modeladas na forma de árvores de eventos. A dramatização final é sempre um dos caminhos da raiz até uma folha e depende da interação com o usuário ou de seleções que ocorrem de forma aleatória. Para avaliar o modelo proposto e o algoritmo, foram realizados testes em um contexto correspondente a variações do conto de fadas Chapeuzinho Vermelho. Em nosso exemplo, nós modelamos as emoções que são provocadas pelos acontecimentos da história usando os 4 eixos de emoções opostas (alegria e tristeza; antecipação e surpresa; raiva e medo; desgosto e confiança), conforme descrito no capítulo 3. Especificamos as seqüências de derivadas para as emoções em cada evento da história. Este modelo de emoções, embora ainda muito simples, foi útil para a validação do nosso procedimento. As experiências aqui descritas foram realizadas em um PC executando uma versão do SWI Prolog para Windows com um processador Core 2 Duo de 1,6 Ghz. 5.1 Chapeuzinho Vermelho O conto de fadas Chapeuzinho Vermelho faz parte da cultura popular mundial e conta a história de uma menina cuja mãe lhe pede que leve uma cesta de frutas para a sua avó que está muito doente, mas a mãe a orienta a ter cuidado, não entrar na floresta e não parar para falar com estranhos, pois há um lobo muito mal pelas redondezas. No caminho, ela encontrando o lobo que a engana e consegue tirar dela informações preciosas. Enquanto a menina está distraída na floresta, o Lobo se dirige para a casa da avó e a engole, disfarçando-se de vovozinha até a chegada da menina. Daí a menina 65 conversa com a vovozinha (lobo) e, após algum tempo, o lobo a ataca e ela foge, encontrando um caçador que mata o lobo e resgata a vovozinha de suas entranhas. Os eventos da história e algumas alternativas são apresentados na Figura 5.1. A Figura 5.2 apresenta uma árvore de eventos correspondente a uma história não-linear baseada no conto de fadas Chapéuzinho Vermelho. EV 1 – A mãe alerta a menina EV 2 – Menina sai de casa EV 3 – Menina na floresta EV 4 – Menina encontra o Lobo na floresta EV 5 – O Lobo engana a Menina EV 6 – O Lobo ataca a Menina EV 7 – O Lobo vai para a casa da Vovó EV 8 – O Lobo engole a Vovó EV 9 – A Menina chega à casa da Vovó EV 10 – A Menina fala com o Lobo EV 11 – A Menina escapa EV 12 – O Lobo devora a Menina EV 13 – A Menina encontra o Caçador EV 14 – O Lobo pega a Menina EV 15 – O Caçador mata o Lobo e salva a Vovó EV 16 – O Lobo mata o Caçador EV 17 – O Lobo ataca a menina na casa da Vovó EV 18 – O Lobo devora a garota após sua fuga EV 19 – O Lobo devora a Menina na casa da Vovó EV 20 – O Lobo devora a Menina na Floresta Figura 5.1: Eventos na história da Chapeuzinho Vermelho. Figura 5.2: Árvore de Eventos (História I). 66 A trama original é representada pela seguinte seqüência grifada de eventos: EV 1, EV 2, EV 3, EV 4, EV 5, EV 7, EV 8, EV 9, EV 10, EV 17, EV 11, EV 13 e EV 15 . Em alguns momentos da história, há possibilidades de ramificações, tais como o momento em que a menina encontra o lobo na floresta. 5.2 Modelagem Emocional Cada evento possui quatro propriedades que variam continuamente, uma para cada dupla de emoções opostas. Seqüências de valores para a derivada de cada uma das propriedades representam como as propriedades variam ao longo do tempo. Valores positivos para as derivadas representam incrementos nos níveis das seguintes emoções: Alegria, Confiança, Antecipação e Medo, e valores negativos representam incrementos nos níveis de suas respectivas emoções opostas: Tristeza, Desgosto, Surpresa e Raiva. O valor zero indica a ausência de variação para aquela emoção. A associação das emoções a cada evento foi feita de forma intuitiva e os valores das derivadas foram obtidos de forma arbitrária. A Figura 5.3 ilustra as emoções envolvidas em cada um dos 20 eventos presentes na história. EV 1 – Alegria + Surpresa EV 2 – Alegria + Antecipação EV 3 – Confiança + Surpresa EV 4 – Medo + Surpresa EV 5 – Medo + Confiança EV 6 – Raiva + Antecipação EV 7 – Tristeza + Antecipação EV 8 – Raiva + Surpresa EV 9 – Alegria + Medo EV 10 – Confiança + Surpresa EV 11 – Alegria + Antecipação EV 12 – Tristeza + Raiva EV 13 – Alegria + Antecipação EV 14 – Raiva + Desgosto EV 15 – Alegria + Raiva EV 16 – Tristeza + Surpresa EV 17 – Raiva + Antecipação EV 18 – Tristeza + Raiva EV 19 – Tristeza + Raiva EV 20 – Tristeza + Raiva Figura 5.3: Emoções envolvidas em cada evento da história. A Figura 5.4 ilustra o desenvolvimento das emoções ao longo do tempo na história original. As Figuras 5.5, 5.6, 5.7, 5.8, 5.9, 5.10 e 5.11 ilustram o desenvolvimento das emoções ao longo de alternativas para a história. Nos gráficos, cada curva representa uma emoção, onde: J = Alegria, F = Medo, T = Confiança e A = Antecipação. 67 Figura 5.4: Desenvolvimento das emoções ao longo da história original. Figura 5.5: Desenvolvimento das emoções ao longo de uma alternativa para a história. 68 Figura 5.6: Desenvolvimento das emoções ao longo de uma alternativa para a história. Figura 5.7: Desenvolvimento das emoções ao longo de uma alternativa para a história. 69 Figura 5.8: Desenvolvimento das emoções ao longo de uma alternativa para a história. Figura 5.9: Desenvolvimento das emoções ao longo de uma alternativa para a história. 70 Figura 5.10: Desenvolvimento das emoções ao longo de uma alternativa para a história. Figura 5.11: Desenvolvimento das emoções ao longo de uma alternativa para a história. 5.3 Avaliação 71 Para avaliar a abordagem foram feitas chamadas Prolog, passando como argumentos: • A fórmula a ser testada: que possui operadores Prolog definidos para representar os operadores de estados e os quantificadores de caminho de nossa lógica, além disso, as fórmulas básicas são colocadas entre chaves, segundo sintaxe de CLPR (CLP para o conjunto dos números reais). Há um caso específico da chamada para fórmulas com o operador “end” que é feita utilizando o functor mod(QUANT_CAM,OP_EST,FORMULA); • Uma lista contendo as variáveis que representam as emoções presentes na fórmula: segundo técnicas de CLP; • Uma lista com as emoções a serem testadas: a lista é composta por átomos, cada emoção tem um átomo que a representa – Alegria = joy, Medo = fear, Confiança = trust e Antecipação = anticipation; • A história a ser testada (Chapeuzinho Vermelho). Os tempos médios mencionados na seqüência deste capítulo foram extraídos de 20 execuções de cada teste em questão. A fórmula mais simples que se pode verificar é se existe um momento em que determinada emoção é igual a zero como, por exemplo, a Alegria. Os parâmetros de entrada para a verificação desse fato ficariam assim: Fórmula → ef {JOY = 0.0} Variáveis → [JOY] Emoções → [joy] História → little_red_riding_hood Essa busca no nosso protótipo consumiu um tempo médio de 0,00415s, com tempo mínimo de 0,004s e tempo máximo de 0,005s. Essa busca é quase instantânea, pois, no instante inicial, todas as emoções têm valor igual a zero.A partir da observação dos gráficos das histórias é fácil chegar a essa conclusão. Para o contexto de Storytelling Interativo é importante que se possam estabelecer restrições sobre o fim de um capítulo de uma história (ou sobre o fim da história), querendo forçar, por exemplo, um final feliz ou triste. A partir da observação dos gráficos da seção anterior pode-se notar que a história pode ter um final feliz (JOY>0) 72 ou um final triste (JOY<0). Esses fatos em termos de nossa lógica temporal podem ser descritos da seguinte forma: (E end (JOY > 0)) e (E end (JOY < 0)), respectivamente. Para a verificação desses fatos os parâmetros de entrada ficariam assim: Fórmula → mod(e, end,{JOY > 0.0}) Variáveis → [JOY] Emoções → [joy] História → little_red_riding_hood Fórmula → mod(e, end,{JOY < 0.0}) Variáveis → [JOY] Emoções → [joy] História → little_red_riding_hood A primeira busca (JOY>0.0), no nosso protótipo, consumiu um tempo médio de 0,0178s, com tempo mínimo de 0,017s e tempo máximo de 0,018s. A segunda (JOY<0.0) consumiu um tempo médio de 0,02245s, com tempo mínimo de 0,022s e tempo máximo de 0,024s. A partir daí é fácil concluir que buscas do tipo: (A end (JOY>0)) e (A end (JOY<0)) devem falhar. Para a verificação desses fatos os parâmetros de entrada ficariam assim: Fórmula → mod(a, end,{JOY > 0.0}) Variáveis → [JOY] Emoções → [joy] História → little_red_riding_hood Fórmula → mod(a, end,{JOY < 0.0}) Variáveis → [JOY] Emoções → [joy] História → little_red_riding_hood A primeira busca (JOY>0.0), no nosso protótipo, consumiu um tempo médio de 0,0275s, com tempo mínimo de 0,026s e tempo máximo de 0,03s. A segunda (JOY<0.0) 73 consumiu um tempo médio de 0,0217s, com tempo mínimo de 0,018s e tempo máximo de 0,03s. Uma situação mais complexa ocorre quando se deseja encontrar um caminho em que há um momento no qual o nível de Antecipação é maior do que o nível da Alegria e maior do que 60.0. A partir desse momento, deve haver um caminho em que, no fim, o nível da Alegria é positivo. Para a verificação desses fatos os parâmetros de entrada ficariam assim: Fórmula → ef ({ANTICIPATION > JOY} and {ANTICIPATION > 60.0} and mod(e,end,{Joy > 0})) Variáveis → [JOY , ANTICIPATION] Emoções → [joy , anticipation] História → little_red_riding_hood Nesse caso, o método tenta encontrar um caminho e um momento T nesse caminho quando a condição {ANTICIPATION > JOY} and {ANTICIPATION > 60.0} é válida. Quando a condição é verificada, o método precisa continuar o processo para verificar a validade da condição que resta: mod(e,end,{Joy > 0}). Assim, a condição passa ser a verificada na árvore que tem como ponto inicial o ponto T. Backtracking cronológico é utilizado para explorar todas as possíveis alternativas. Essa verificação consumiu um tempo médio de 0,1768s, com tempo mínimo de 0,175s e tempo máximo de 0,187s. Como ilustrado nas Figuras 5.4 e 5.8 a condição {ANTICIPATION > JOY} and {ANTICIPATION > 60.0} é válida em um momento durante o Evento 13 e no fim do Evento 15 a condição {Joy > 0} é válida. O mesmo não ocorre nas demais alternativas. Outra situação com um nível de complexidade ainda maior ocorre quando é preciso estabelecer restrições em vários pontos do tempo. Esse fato ocorre quando se deseja testar, por exemplo, a fórmula a seguir: AF ((JOY>FEAR) and (ANTICIPATION>TRUST) and AG (JOY=<100.0 and JOY>= -100.0) and A (end (ANTICIPATION=TRUST and FEAR =\= JOY))). Nesse caso, pretende-se garantir que, em todos os caminhos, haverá um momento em que o nível de Alegria seja maior que o nível de Medo e o nível de Antecipação seja maior que o nível de Confiança e, a partir desse momento, o nível de Alegria permaneça sempre entre -100.0 e +100.0. Além disso, no fim, o nível de Antecipação sempre deverá ser igual ao nível de Confiança e o 74 nível de Medo deverá ser sempre diferente do nível de Alegria. Para a verificação desses fatos os parâmetros de entrada ficariam assim: Fórmula → af (({JOY>FEAR}) and ({ANTICIPATION>TRUST}) and ag ({JOY=<100.0} and {JOY>= -100.0}) and mod(a,end,({ANTICIPATION=TRUST} and {FEAR=\= JOY}))) Variáveis → [JOY , ANTICIPATION , FEAR , TRUST] Emoções → [joy , anticipation , fear , trust] História → little_red_riding_hood Nesse caso, o método tenta encontrar o momento T em que a condição ({JOY>FEAR}) and ({ANTICIPATION>TRUST}) and ag({JOY≤100.0} and {JOY ≥ – 100.0}) é valida. Quando a condição é verificada, o método precisa continuar o processo para verificar se a condição ag({JOY≤100.0} and {JOY≥ –100.0}) and mod(a,end,({ANTICIPATION=TRUST} and {FEAR ≠ JOY})) é válida. Assim a condição passa ser a verificada na árvore que tem como ponto inicial o ponto T. Backtracking cronológico é utilizado para explorar todas as possíveis alternativas. Essa verificação consumiu um tempo médio de 0,4919s, com tempo mínimo de 0,488s e tempo máximo de 0,514s. Note que, nesse caso o tempo de execução foi maior que das fórmulas anteriores. Assim, é fácil concluir que o número (e a complexidade) das restrições influenciam muito o tempo de execução da verificação da validade da fórmula. A quantidade de alternativas a serem analisadas quando se verifica uma fórmula contendo o operador ‘F’, em geral, é maior do que quando se deseja verificar uma fórmula contendo o operador ‘G’. Isso se deve à necessidade de se definir abstratamente um ponto T no tempo no qual a validade de ‘F’ se confirma, e, a partir dali, verificar as demais restrições. Diferentemente de uma fórmula contendo o operador ‘G’ que precisa ter sua validade reforçada em todos os instantes, o que diminui o espaço de busca. O usuário pode, por exemplo, verificar se existe um caminho em que o nível de Confiança e o nível de Alegria são sempre positivos. Para a verificação desses fatos os parâmetros de entrada ficariam da seguinte forma: Fórmula → eg ({TRUST>=0.0} and {JOY>= 0.0}) Variáveis → [JOY , TRUST] 75 Emoções → [joy , trust] História → little_red_riding_hood Nesse caso, as restrições são reforçadas a cada instante durante a execução da busca e quando um estado de falha é encontrado, toda a árvore após o ponto de falha é abandonada, podando o espaço de busca. Essa verificação consumiu um tempo médio de 0,1555s, com tempo mínimo de 0,128s e tempo máximo de 0,176s. As verificações aqui apresentadas se concentraram em uma única história nãolinear. Em um caso mais geral, pode haver várias árvores, representando várias histórias (ou capítulos) e se desejar identificar uma árvore onde uma certa fórmula temporal vale. Para aplicar o protótipo também com esse propósito, elaboramos outra versão não-linear (árvore) para a história da Chapeuzinho Vermelho, como ilustra a Figura 5.12 (História II). A diferença dessa versão para a presente na Figura 5.2 (História I) é a ausência dos Eventos 16 e 12 no fim de dois caminhos onde eles ocorrem na História I. Figura 5.12: Árvore de Eventos (História II). A partir daí podemos executar buscas que selecionem uma das duas histórias. Suponhamos, por exemplo, que desejamos encontrar uma história na qual o nível de Antecipação é igual a 50.0 e maior que o nível de Alegria e, desse momento em diante, 76 a Alegria é sempre maior ou igual a zero em todos os caminhos. Para a verificação desses fatos, os parâmetros de entrada ficariam assim: Fórmula → ef ({ANTICIPATION = 50.0} and {ANTICIPATION > JOY} and ag {JOY >= 0.0}) Variáveis → [JOY , ANTICIPATION] Emoções → [joy , anticipation] História → ? Nesse caso, como desejamos encontrar uma história que satisfaça a fórmula, deixamos a variável destinada à história livre, para que ela seja instanciada com a história que satisfizer a restrição. Aqui é usado backtracking cronológico para percorrer o banco de dados de histórias. A partir da observação das árvores das histórias I e II, nota-se que ambas são idênticas, exceto pelo fato de a História I apresentar bifurcações após as duas ocorrências do Evento 13, nas quais há a possibilidade desse evento ser seguido pelos eventos 16 e 12. Conforme pode ser verificado nas figuras 5.4 a 5.11, o nível de Antecipação atinge o nível 50.0 apenas na história original e nas alternativas 1, 4 e 5. Isso ocorre no fim do Evento 11, (que coincide com o início do Evento 13) e, nesse mesmo momento, o nível de Antecipação é maior que o nível de Alegria. Como os eventos 16 e 12 ocorrem após o Evento 13 e o nível de Alegria não se mantém maior ou igual a zero em todos os estados ao longo dos eventos 16 e 12 nas alternativas 1 (Figura 5.5) e 5 (Figura 5.9), a História I não satisfaz a fórmula. Com a exclusão dos eventos 16 e 12 na História II, a fórmula é satisfeita. A verificação da fórmula que não é satisfeita pela primeira árvore consumiu um tempo médio de 0,34185s com tempo mínimo de 0,338s e tempo máximo de 0,352s. A verificação da satisfação da fórmula satisfeita na segunda árvore consumiu um tempo médio de 0,2782s com tempo mínimo de 0,275s e tempo máximo de 0,290s. 5.4 Atendimento aos Requisitos No contexto de Storytelling Interativo, as histórias são criadas com base em processos automáticos. Ao incorporar meios para garantir automaticamente que as histórias geradas obedecem a padrões desejados é necessário atender determinados requisitos (listados no Capítulo 3 desta dissertação). Tais requisitos provêm em especial 77 do objetivo de se possibilitar experiências de Storytelling Interativo através da TV digital, como se pretende através do sistema Logtell. A seguir fazemos uma análise dos resultados aqui apresentados à luz desses requisitos. 5.4.1 Análise de Eficiência A eficiência do processo de verificação é requisito de fundamental importância para que o sistema de storytelling seja capaz de verificar restrições sobre propriedades contínuas enquanto a geração e a dramatização dos capítulos ocorre em paralelo. Além disso, em histórias não-determinísticas, há uma complexidade maior na geração dos planos. Assim, o tempo de execução das atividades do processo deve ser compatível. Os capítulos gerados pelo Logtell têm um número relativamente pequeno de eventos, e o planejamento não-determinístico consome cerca de 5s, no pior caso. A história da Chapeuzinho Vermelho modelada contém um número de eventos e alternativas compatível com o imaginado para um dos capítulos. Como, em todos os nossos testes, o tempo de verificação não foi superior a 1s, ao adicionarmos a verificação de propriedades contínuas o tempo geral para que uma versão de capítulo seja gerada e verificada antes de ser enviada para a dramatização não tenderá a crescer mais do que 20%, se comparado à alternativa de enviar o capítulo sem o processo de verificação. A dramatização de um capítulo na versão 2.0 do Logtell, com planejamento determinístico, contém capítulos com menos de 6 eventos que duram tipicamente de 1 a 2min, que é o tempo disponível para gerar o capítulo seguinte incorporando interações com usuários. Os capítulos na versão com planejamento não-determinístico poderão ter duração consideravelmente maior. Desse modo, várias alternativas de capítulo podem ser geradas e testadas enquanto o capítulo corrente é apresentado, havendo espaço também para que verificações com fórmulas ainda mais complexas que as apresentadas nos exemplos deste capítulo sejam feitas. Desse modo, capítulos poderão então ser apresentados sem interrupção, já garantindo a obediência a restrições impostas pelo gênero, pelo autor do contexto ou por perfis de usuários. 5.4.2 Análise da Expressividade Na aplicação ao exemplo das variações do conto da Chapeuzinho Vermelho, o protótipo permitiu o estabelecimento de restrições sobre valores contínuos em vários 78 instantes ao longo da história, além do estabelecimento de restrições sobre os caminhos alternativos. Além disso, é possível forçar a forma como uma história termina, estabelecendo, restrições que são ser verificadas apenas no fim de um ou de todos os caminhos. É possível também comparar a variação de propriedades, podendo, por exemplo, forçar que o nível de determinada propriedade se mantenha sempre maior que o nível de outra. As fórmulas podem ser muito complexas, pois há suporte a vários níveis de endentação e à mistura de quantificadores de caminho e operadores de estado diferentes. A formulação de CTL herdada e estendida por nossa lógica, provê uma boa gama de recursos para a especificação de restrições sobre as histórias que podem ser usadas para controlar a tensão dramática e assim manter o interesse dos usuários. 5.4.3 Análise da Facilidade de Representação das Propriedades Contínuas Estimar a variação de propriedades em histórias não chega a ser um trabalho complexo quando é possível imaginar a forma como os eventos acontecem dentro da história. Na modelagem da história da Chapeuzinho Vermelho, a intuição foi determinante para que obtivéssemos um modelo coerente para a variação das emoções durante os eventos. Se olharmos, por exemplo, para o primeiro evento da história (A mãe alerta a menina), podemos imaginar a seguinte situação que deve ocorrer nesse evento: a mãe fala para a menina que sua avó está muito doente e a pede que leve frutas para ela. Além disso, a mãe alerta a menina para que evite a floresta, pois lá há um lobo malvado. Como temos 8 possíveis emoções envolvidas na situação descrita, podemos supor que ela ficou alegre pois iria visitar a avó, surpresa devido ao fato de a avó estar doente, triste pela doença da avó, com medo por causa da presença de um lobo em seu caminho, etc. No caso deste evento, escolhemos que as emoções escolhidas seriam alegria e surpresa, o que não impede que uma alternativa para esse evento envolva estímulos para outras emoções, dependendo da percepção de quem modela os eventos da história. Essa análise foi feita para cada um dos 20 eventos presentes na história sem maiores dificuldades, atribuindo-se derivadas negativas ou positivas conforme se interprete que o nível de uma certa emoção deva aumentar ou diminuir durante o evento. Esse processo foi facilitado porque se optou pela definição de derivadas e não de valores absolutos para as emoções. Neste trabalho a modelagem foi essencialmente manual, o que demandou grande esforço autoral, mas é possível imaginar interfaces 79 onde o autor desenharia uma curva padrão correspondente a determinada propriedade e as seqüências de derivadas seriam extraídas automaticamente. No que tange à especificação de restrições temporais, também é razoavelmente simples falar com nossa lógica sobre vários tipos de padrões a serem obedecido por uma história não-linear. Apesar disso, pode-se ainda pensar em interfaces gráficas que, com o auxílio de linguagem natural, por exemplo, poderiam ajudar os usuários a estabelecer restrições sem que necessitem de um conhecimento prévio de lógica temporal ou de detalhes do modelo proposto. 80 6 Conclusão A pesquisa descrita nesta dissertação apresentou um modelo temporal para lidar com tempo ramificado e contínuo, incorporando as necessidades específicas de um contexto de Storytellig Interativo. O modelo foi proposto de forma a ser incorporado ao sistema de storytelling para TV interativa Logtell. A utilização de técnicas de programação em lógica com restrições permitiu que pudéssemos lidar com o tempo contínuo, tratando abstratamente os tempos e valores das propriedades dentro dos intervalos por meio de variáveis, equações e inequações. Tendo em vista a limitação dos constraint solvers de lidarem apenas com equações e inequações lineares,modelamos as propriedades como funções do tempo linearizadas aos pedaços. Propusemos também uma extensão de CTL para tratar com tempo ramificado e contínuo dentro do contexto de storytelling interativo, visando a especificação das restrições sobre as histórias. Um algoritmo de verificação foi então especificado para permitir a verificação de restrições definidas de acordo com o modelo. Para permitir a avaliação do modelo e do algoritmo, foi implementado um protótipo, a ser integrado ao Logtell, que foi testado com base em um exemplo de contexto com variações para o conto de fadas da Chapeuzinho Vermelho. A aplicação do protótipo ao exemplo permitiu avaliar o atendimento dos requisitos do modelo. No que tange à eficiência, foi demonstrado pelos testes realizados, que o processo de verificação ocorre em tempo razoável em relação ao tempo de geração e apresentação de um capítulo. Sendo assim, pode-se garantir que é viável incorporar a verificação automática de restrições sobre propriedades contínuas no processo de Storytelling interativo. No que tange à expressividade, o modelo permite o estabelecimento de restrições sobre valores contínuos em vários instantes ao longo da história (incluindo o último instante, podendo estabelecer diretamente restrições sobre esse momento específico), além do tratamento de possibilidades alternativas em histórias nãodeterminísticas, fornecendo meios para tentar garantir que a história interativa seja 81 capaz de entreter e engajar o público. Além disso, a modelagem da variação das propriedades ao longo dos eventos e de fórmulas interessantes para serem obedecidas pelas histórias mostrou-se razoavelmente intuitiva, podendo ser auxiliada com o desenvolvimento de interfaces gráficas que apóiem esta tarefa. Apesar de ter sido proposto para ser incorporado ao Logtell, nossa abordagem pode ser utilizada para verificar propriedades contínuas em outros tipos de histórias interativas, incluindo RPGs eletrônicos. A técnica pode ser utilizada, por exemplo, para procurar por histórias em uma biblioteca, utilizando a lógica aqui descrita para especificar as preferências do(s) usuário(s). Além disso, os formalismos aqui propostos podem ser úteis em outros sistemas que requerem a verificação de propriedades que variam continuamente ao longo do tempo. Durante o desenvolvimento desta dissertação, foram elaborados dois artigos relatando os resultados parciais obtidos. O primeiro foi aceito pela 10th International Conference on Entertainment Computing – ICEC 2011 [Araujo & Ciarlini, 2011] e o segundo pela 4th International Conference on Interactive Digital Storytelling – ICIDS 2011 [Araujo et al, 2011]. A seguir, a seção 6.1 faz um relato mais detalhado das principais contribuições decorrentes da pesquisa desenvolvida. Por fim, a seção 6.2 destaca as principais possibilidades de trabalhos. 6.1 Principais Contribuições As contribuições do trabalho desenvolvido nesta dissertação correspondem essencialmente aos seguintes pontos: • Um modelo de verificação de propriedades contínuas para Storytelling Interativo: Nossa proposta de extensão da CTL se mostrou suficientemente expressiva para o contexto de Storytelling Interativo, pois permite a especificação de restrições em vários momentos de uma história nãodeterminística, inclusive permitindo que se estabeleçam restrições sobre o fim de histórias (ou capítulos), sobre os estados ao longo de um caminho e sobre estados alternativos. 82 Durante a especificação da lógica temporal, também foram investigadas várias simplificações de fórmulas que têm importância para a implementação de algoritmos de verificação,como o apresentado no Capítulo 5. Um sistema de Storytelling que adote o modelo apresentado nesta dissertação pode dar mais poder aos autores para modelar os contextos, garantindo a geração de histórias interessantes. Novas formas de interação com o usuário podem também ser implementadas, já que este pode influenciar os rumos da história de acordo com padrões que deseje controlar, como o nível das emoções. O controle pode se dar de forma explícita com a especificação de restrições diretamente pelos usuários ou de forma implícita com base em modelos de usuários adotados. Embora proposto com vistas às necessidades de um ambiente de Storytelling Interativo, o modelo não está restrito a ambientes desse tipo, sendo eventualmente aplicável em outros contextos onde se deseje estudar a variação de propriedades contínuas ao longo de seqüências alternativas de eventos. • Algoritmo baseado em Programação em Lógica com Restrições: O algoritmo apresentado no Capítulo 4 trata a verificação de todos os tipos de fórmulas descritas no Capítulo 3. Nessa verificação, procura-se analisar cada evento contido em algum caminho um número mínimo de vezes e usam-se simplificações de fórmulas de modo a buscar maior eficiência. O algoritmo nãodeterminístico apresentado é suficientemente geral para permitir extensões. • Protótipo implementado: Nosso protótipo, com mais de duas mil linhas de código, foi implementado com base nos algoritmos apresentados no Capítulo 4 e encontra-se funcional, tendo sido usado nos testes apresentados no Capítulo 5. A eficiência demonstrada no processo de verificação permitirá sua integração ao Logtell. Apesar de ter sido pensado para ser parte integrante do Logtell, há a possibilidade de ser utilizado em outros ambientes, como, por exemplo, para selecionar histórias em uma biblioteca de histórias com base em restrições temporais. • Base para estudos sobre especificação de restrições temporais com tempo ramificado e contínuo: o modelo, o algoritmo e o protótipo implementado poderão servir como base para diversos estudos sobre a especificação de restrições temporais com tempo ramificado e contínuo. O modelo e o algoritmo 83 foram definidos com base na idéia de representar os tempos e os valores de propriedades contínuas ao longo dos eventos por variáveis, submetidas a restrições, o que permite o tratamento automático de restrições por constraint solvers. Diversos trabalhos futuros, envolvendo restrições mais complexas, mas utilizando a base desenvolvida nesta dissertação, são discutidos a seguir. 6.2 Trabalhos Futuros Diversos trabalhos futuros merecem ser investigados como continuação dos trabalhos desenvolvidos nesta dissertação. Compensa destacar as seguintes frentes de pesquisa a serem investigadas: • Otimização e correção do algoritmo: O algoritmo proposto nesta dissertação pode ser otimizado para obter melhores resultados quando se trabalha com fórmulas muito grandes, pois estas tendem a levar mais tempo de execução com a implementação proposta. Uma forma de fazer isso seria propor uma forma de realizar as simplificações das fórmulas em passos intermediários ao invés de serem feitas apenas no início da busca. Além disso, é possível um estudo sobre a corretude do procedimento. • Prova matemática da lógica: No contexto desta dissertação não houve um estudo sobre a validade matemática da lógica proposta, apesar de ser um passo no processo de validação da lógica. Estudos nesse sentido, no entanto, são custosos o suficiente para justificar um tema de pesquisa. • Incorporação do mecanismo de verificação dentro da geração de histórias com planejamento: No modelo corrente, histórias ou capítulos são gerados com planejamento, assumindo-se a duração nula dos eventos. Em seguida, é feita a verificação sobre a variação de propriedades contínuas. Compensa investigar até que ponto a substituição desse mecanismo de gerar e testar pela incorporação de mecanismos de verificação durante o próprio planejamento poderia acelerar ou não o processo. Outra possibilidade mais ambiciosa seria gerar histórias usando a fórmula temporal como um objetivo a ser cumprido pela história, o qual influenciaria diretamente na escolha dos eventos a serem incorporados. • Estender a lógica: Utilizar técnicas de lógica fuzzy, por exemplo, para poder estabelecer restrições subjetivas, como por exemplo, poder estabelecer que uma 84 propriedade mantenha-se em uma determinada média, ou que um capítulo termine “um pouco” triste ou “muito” feliz. Isso pode ajudar a estender o modelo emocional, permitindo a utilização do modelo emocional completo proposto por Plutchik. • Adição de modelos de usuário: Uma forma de estabelecer as restrições automaticamente é com a utilização de modelos de usuário que podem ser usados para inferir o que o usuário gostaria de assistir e descartar capítulos a serem enviados para a dramatização de forma automatizada. • Restrições falando sobre tempo absoluto: No contexto deste trabalho não consideramos o estabelecimento de um tempo exato para a verificação das restrições. Pode ser interessante, por exemplo, forçar que após os 5 primeiros minutos de execução da história algo terrível deve acontecer. Isso pode aumentar sistematicamente a expressividade da nossa lógica. • Trabalhar com variação não-linear: Devido às limitações da técnica escolhida para trabalhar com tempo contínuo, optamos por trabalhar apenas com funções que variem linearmente, porém, como já mencionamos, propriedades contínuas tendem a variar de forma não-linear, assim, poder-se-ia investigar técnicas que permitam trabalhar com esse tipo de fórmula, aplicando as idéias aplicadas nesta dissertação para restrições não-lineares. Uma alternativa é a implementação de constraint solvers dedicados, usando, por exemplo, bibliotecas como CHR (Constraint Handling Rules) [Frühwirth, 1998; Sneyers et al, 2009]. Com CHR, torna-se viável programar o tratamento de um conjunto específico de equações e inequações não-lineares típicas de um domínio. • Estudos mais aprofundados sobre a variação das emoções: As emoções tendem a variar de forma não-linear. Tipicamente o nível de uma determinada emoção diminui de forma não-linear quando não há estímulos. O tratamento de restrições não-lineares abre a possibilidade de se criar modelos mais precisos para a variação das emoções. Estudos nessa área, porém, ainda estão em estado insipiente. Há a possibilidade ainda de se investigar a relação entre as emoções dos personagens e a emoção geral sobre as histórias de modo a se construir modelos mais eficientes que ajudem inclusive na produção de melhores dramatizações. 85 • Reduzir a carga de trabalho do autor: Hoje a modelagem dos eventos e a especificação das propriedades sobre os eventos são tarefas manuais e exigem conhecimento sobre a teoria emocional utilizada no contexto deste trabalho e técnicas de programação em Prolog. Assim, é possível pensar em interfaces gráficas que poderiam ajudar o autor a realizar essa tarefa de forma lúdica e intuitiva, sem a necessidade de um conhecimento maior sobre a especificação do modelo de verificação. 86 7 Referências Bibliográficas ALUR, R.; HENZINGER, T.A.; HO, P.-H.: Automatic Symbolic Verification of Embedded Systems. In: Proceedings of the 14th Annual Real-Time Systems Symposium (RTSS). IEEE Computer Society Press, 1993, p. 2-11 (1993) AQUINO, M. S.; DE SOUZA, F. F.; FRERY, A. C.; NETO, L. G. A.; ALBUQUERQUE, M. V. A.; ALMEIDA, R. M. G.: Adaptação de conteúdos pelo perfil do usuário para personalização de ambientes virtuais com X3D. In: Anais do Simpósio Brasileiro de Realidade Virtual. Belém, PA, p. 2-5. (2006) ARAUJO, E. T.; CIARLINI, A. E. M.: Verification of Temporal Constraints in Continuous Time on Nondeterministic Stories. In: ICEC 2011 - International Conference on Entertainment Computing, 2011, Vancouver. Proc. ICEC 2011 - International Conference on Entertainment Computing. (2011) ARAUJO, E. T.; CIARLINI, A. E. M.; POZZER, C. T.; FEIJÓ, B.: A Method to Check the Satisfaction of Continuous-Time Constraints by Nonlinear Stories. In: ICIDS 2011 - International Conference on Interactive Digital Storytelling, 2011, Vancouver. Proc. ICIDS 2011 - International Conference on Interactive Digital Storytelling. (2011) BERTOLI, P.; CIMATTI, A.; ROVERI, M.; TRAVERSO, P.: Planning in nondeterministic domains under partial observability via symbolic model checking. In: Proceedings of IJCAI 2001: p. 473-478 (2001). BIERE, A.; CIMATTI, A.; CLARKE, E.M.; STRICHMAN, O.; ZHU, Y.: Bounded model checking. Advances In Computers 58: p. 118-149 (2003). CAI, Y.; MIAO, C.; SHEN, Z.; TAN, A.: S-MADE: Interactive Storytelling Architecture Through Goal Execution and Decomposing, AAAI Fall Symposium on Intelligent Narrative Technologies (2007) 87 CAMANHO, M. M.: Conciliando coerência e responsividade em storytelling interativo para TV digital. Dissertação de Mestrado, Departamento de Informática Aplicada, UNIRIO, Rio de Janeiro (2009); CAMANHO, M.M.; CIARLINI, A.E.M.; FURTADO, A.L.; POZZER, C.T.; FEIJO, B.: A model for interactive TV Storytelling. In: VIII Brazilian Symposium on Games and Digital Entertainment, Rio de Janeiro, Brazil, p. 197-206. (2009) CARVALHO, J. S.: Verificação automatizada de sistemas de tempo real críticos. Dissertação de Mestrado, Departamento de Informática, Universidade da Beira Interior, Portugal (2009) CAVAZZA, M.; CHARLES, F.; MEAD, S.: Character-based interactive storytelling. IEEE Intel-ligent Systems, special issue on AI in Interactive Entertainment, 17(4): p. 17-24 (2002) CHARLES, F.; PIZZI, D.; CAVAZZA, M.; VOGT, T.; ANDRE, E.: EmoEmma: emotional speech input for interactive storytelling. In: Proc. 8th international Conference on Autonomous Agents and Multiagent Systems - Volume 2 (Budapest, Hungary, May 10 - 15, 2009) (2009) CIARLINI, A.E.M.: Geração interativa de enredos, DSc. Thesis, Departamento de Informática, PUC-Rio, Rio de Janeiro (1999) CIARLINI, A. E. M.; POZZER, C. T.; FURTADO, A. L.; FEIJÓ, B.: A Logic-Based Tool for Interactive Generation and Dramatization of Stories. In: Proceedings of the ACM SIGCHI International Conference on Advances in Computer Entertainment Technology (ACE 2005), Valencia, p.133-140, June 2005 (2005) CIARLINI, A. E. M.; CAMANHO, M. M.; DORIA, T. R.; FURTADO, A. L.; POZZER, C.T.; FEIJÓ, B.: Planning and Interaction Levels for TV Storytelling. In: Proceedings of the First Joint International Conference on Interactive Digital Storytelling, ICIDS 2008, 2008, Erfurt - Alemanha. p. 198-209. (2008) CIARLINI, A. E. M.; CASANOVA, M. A.; FURTADO, A. L.; VELOSO, P. A. S.: Modeling interactive storytelling genres as application domains. Journal of Intelligent Information Systems, 35(3): p. 347-381 (2010) CUPERTINO, E. R.: Vamos Jogar RPG? Diálogos com a literatura, o leitor e a autoria. Dissertação de Mestrado, USP, São Paulo (2008) 88 DORIA, T. R.; CIARLINI, A. E. M.; ANDREATTA, A.: A Nondeterministic Model for Controlling the Dramatization of Interactive Stories. In: Proceedings of the ACM Multimedia 2008 - 2nd ACM Workshop on Story Representation, Mechanism and Context - SRMC08, Vancouver, Canada, p. 21-26. (2008) DÓRIA, T. R.: Dramatização não-determinística de enredos em storytelling para TV interativa. Dissertação de Mestrado, Centro de Ciências Exatas e Tecnologia, Programa de Pós-Graduação em Informática, UNIRIO, Rio de Janeiro. (2009) EL-NASR, M. S.: A User-Centric Adaptive Story Architecture – Borrowing from Acting Theories. International Conference on Advances in Computer Entertainment Technology (ACE 2004). (2004) EL-NASR, M. S.: Interaction, Narrative, and Drama Creating an Adaptive Interactive Narrative using Performance Arts Theories. Interaction Studies, Vol. 8, Nº 2. (2007) EMERSON, E. A.: Temporal and modal logic. In: Handbook of Theoretical Computer Science, North-Holland Pub. Co. (1995) FRÜHWIRTH, T.: Theory and Practice of Constraint Handling Rules. Special Issue on Constraint Logic Programming (P. Stuckey and K. Marriott, Eds.), Journal of Logic Programming, Vol 37 (p. 1-3), October 1998. doi:10.1016/S07431066(98)10005-5 (1998) GRASBON, D.; BRASUN, N.: A morphological approach to interactive storytelling. In: Proceedings CAST01, Living in Mixed Realities. Special Issue of Netzspannung.org/journal, the Magazine for Media Production and Inter-Media Research, p. 337-340, Sankt Augustin, Germany. (2001) HENZINGER, T.A.; HO, P.-H.; WONG-TOI, H.: HYTECH: A Model Checker for Hybrid Systems. In: O. Grumberg, editor, CAV, volume 1254 of LNCS, p. 460– 463. Springer-Verlag (1997) HENZINGER, T.A.; PREUSSIG, J.; WONG-TOI, H.: Some lessons from the HyTech experience. In: Proceedings of the 40th Annual Conference on Decision and Control (CDC), IEEE Press, p. 2887-2892. (2001) KAY, J.: Stereotypes, student models and scrutability. In: Lecture Notes in Computer Science, vol. 1839, G. Gauthier, C. Frasson, and K. VanLehn, Eds., p. 19-30. (2000) 89 KOBSA, A.: Supporting User Interfaces for All Through User Modeling. In: Proceedings of the 6th international Conference on Human-Computer Interaction, HCI, Yokohama, Japão, p. 155-157. (1995) KONUR, S.: Real-time and Probabilistic Temporal Logics: An Overview. Department of Computer Science, University of Liverpool (2008) KONUR, S.: Real-time and probabilistic temporal logics: An overview. Cornell University Library. May 2010. [Online]. Available: http://arxiv.org/abs/1005.3200 (2010) MARRIOT, K.; STUCKEY, P.: Programming with Constraints. MIT Press. (1998) MATEAS, M.; STERN, A.: Structuring content in the Façade interactive drama architecture. In: Proceedings of Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE 2005) (2005) MCMILLAN, K. L.: Symbolic Model Checking. Kluwer Academic Publishers, USA (1993) MCDERMOTT, D.: A Temporal Logic for Reasoning About Processes and Plans. Cognitive Science, Vol. 6, Issue 2, April-June 1982, p. 101-155 (1982) PAIVA, A.; Machado, I.; Prada, R.: Heroes, villains and magicians: Dramatis personage in a virtual story creation environment. In: Proceedings of Intelligent User Interfaces. (2001) PLUTCHIK, R.: The emotions: Facts, theories, and a new model. New York, Random House (1962) PLUTCHIK, R.: A general psychoevolutionary theory of emotions. In: R. Plutchik & H. Kellerman (Eds.), Emotion: Theory, research, and experience: Vol. 1. Theories of emotion. New York: Academic (1980) PORTEOUS, J.; CAVAZZA, M.; CHARLES, F.: Applying Planning to Interactive Storytelling: Narrative Control using State Constraints. ACM Transactions on Intelligent Systems and Technology (ACM TIST). (2010) POZZER, C. T.: Um Sistema para Geração, Interação e Visualização Tridimensional de Histórias para TV Interativa. DSc. Thesis, Departamento de Informática, PUC-Rio (2005) 90 RIEDL, M.; YOUNG, R. M.: From Linear Story Generation to Branching Story Graphs. IEEE Computer Graphics and Applications, v. 26, n. 3, p. 23-31, May/June 2006, doi:10.1109/MCG.2006.56. (2006) RIEDL, M. O.: Incorporating authorial intent into generative narrative systems. In: Proceedings of AAAI Spring Symposium on Intelligent Narrative Technologies II, Palo Alto, California. (2009) RODRIGUES, P. S. L.: Um Sistema de Geração de Expressões Faciais Dinâmicas em Animações Faciais 3D com Processamento de Fala. Tese de Doutorado, Departamento de Informática, PUC-Rio, Rio de Janeiro, RJ, Brasil. SILVA, F. A. G.: Geração de enredos com planejamento não-determinístico em storytelling para TV interativa. Dissertação de Mestrado, Departamento de Informática Aplicada, UNIRIO, Rio de Janeiro (2010); SILVA, F.A.G.: CIARLINI, A. E. M.; SIQUEIRA, S.W.M.: Nondeterministic Planning for Generating Interactive Plots. In: IBERAMIA - 2010 12th. Ibero-American Conference on Artificial Intelligence, 2010, Bahía Blanca, Proc. IBERAMIA - 2010 12th, Ibero-American Conference on Artificial Intelligence (2010) SNEYERS, J; SCHRIJVERS, T.; DEMOEN, B.: The computational power and complexity of constraint handling rules. ACM Trans. Program. Lang. Syst. 31(2): (2009). STOCK, O.; ZANCANARO, M.; BUSETTA, P.; CALLAWAY, C.; KRÜGER, A.; KRUPPA, M.; KUFLIK, T.; NOT, E.; ROCCHI, C.: Adaptive, intelligent presentation of information for the museum visitor in PEACH. Volume 17(3): p. 257304. (2007) THUE, D.; BULITKO, V.; SPETCH, M.; WASYLISHNEN, E., 2007. Interactive storytelling: A player modelling approach. In: Proceedings of the 4th Artificial Intelligence and Interactive Digital Entertainment Conference – AIIDE’07, Stanford, California. (2007) TSIRIGA, V.; VIRVOU, M.: Initializing the Student Model using Stereotypes and Machine Learning. IEEE International Conference on Systems, Man, and Cybernetics. IEEE Press. (2002) VENEMA, Y.: Temporal Logic. Blackwell Guide to Philosophical Logic, Blacwell Publishers (1998) 91 ZAGALO, N.; BRANCO, V.; BARKER, A.: Emoção e Suspense no Storytelling Interactivo. In: Actas, Games2004 - Workshop Entretenimento Digital e Jogos Interactivos, Lisboa, Portugal, p.75-84. (2004) ZIMMERMANN, A.; LORENZ, A.: LISTEN: a user-adaptive audio-augmented museum guide. User Modeling and User-Adapted Interaction. Volume 18(5): p. 389-416. (2008) SICStus Prolog website: http://www.sics.se/isl/sicstuswww/site/index.html SWI Prolog website: http://www.swi-prolog.org/ 92 ANEXO I Simplificações da Lógica Baseada em CTL I.I EF EG α / EF AG α / EF (E end α) / EF (A end α) A Figura I.1 ilustra possibilidades de ocorrência da fórmula EF EG α. Figura I.1: Representação gráfica de possibilidades de uma fórmula do tipo EF EG α ser válida Sempre que há uma fórmula do tipo EF EG α é preciso estabelecer um ponto onde α começa a valer, pois dali para frente ela precisará valer em todos os pontos de pelo menos um caminho para que a fórmula toda seja válida. Assim, esse ponto pode estar no início, no meio, ou no fim de um caminho. Se estiver no início, é preciso verificar todos os pontos dali por diante, porém pode haver um ponto entre o início e o fim do caminho onde a fórmula não seja válida. Nesse caso, um ponto mais à frente deve ser escolhido e o processo reiniciado (aumentando o tempo total de busca). No entanto, pode-se observar que a fórmula EF EG α é satisfeita se e somente se α é satisfeita no fim de um caminho, pois o ponto a partir do qual α passa a valer pode ser o 93 último de um caminho. Desse modo, verificar uma fórmula desse tipo é equivalente a verificar uma fórmula do tipo E end α (que é bem mais simples). No caso em que a fórmula a ser verificada for EF AG α, pelos mesmos fatos expostos anteriormente, ela também pode ser simplificada para E end α. Isso ocorre porque, considerando o último ponto de um caminho, uma quantificação em todos os caminhos se confunde com a quantificação existencial. Observe, contudo, que, ao verificar uma formula do tipo EF( (x>y) ∧ EG(y>z)) a simplificação não se aplica. É necessário encontrar um instante em que (x>y) é válida e verificar desse instante em diante se existe um caminho onde (y>z) é válida em todos os estados. No caso de fórmulas do tipo EF (E end α) e EF (A end α), obriga-se que haja pelo menos um caminho em que no fim α seja válida, isso pode ser traduzido facilmente para E end α. I.II AF AG α / AF EG α / EG AF α A Figura I.2 ilustra possibilidades de ocorrência da fórmula AF AG α. Figura I.2: Representação gráfica de possibilidades de uma fórmula do tipo AF AG α ser válida A semântica de uma fórmula do tipo AF AG α é semelhante à de uma fórmula do tipo EF EG α, só que aqui é preciso que a fórmula α seja válida em todos os caminhos a partir de um ponto. Assim sendo, α deverá valer em todos os finais. 94 Analogamente, se valer em todos os finais, a fórmula AF AG α valerá. E então, verificar uma fórmula do tipo AF AG α é equivalente a verificar uma fórmula do tipo A end α. O mesmo não ocorre para uma fórmula do tipo AF EG α, como ilustra a Figura I.3. Figura I.3: Representação gráfica de possibilidades de uma fórmula do tipo AF EG α ser válida Cumpre destacar que nesse caso não é possível obter uma fórmula equivalente mais simples que contenha o operador “end”, pois α poderá valer em alguns finais e não valer em outros. No caso de uma fórmula do tipo EG AF α, exige-se e que AF α valha em todos os estados ao longo de um caminho. Isso faz com que E end α tenha que valer, pois AF α precisa valer para o último ponto do caminho. No entanto, nos pontos de ramificação anteriores ao longo do caminho, AF α também precisa valer, o que faz com que essa fórmula não seja simplificável. I.III EG EF α / AG EF α / AG AF α Sempre que há uma fórmula do tipo EG EF α, é preciso reforçar, a cada instante, a ocorrência de EF α ao longo de pelo menos um caminho. Assim, como α deverá obrigatoriamente ser válida no fim, e esse fato garante a validade de EF α nos estados anteriores (por conta da especificação do F – vide Capítulo 2 desta dissertação), 95 verificar a validade de uma fórmula do tipo EG EF α é equivalente a verificar a validade de uma fórmula do tipo E end α. Verificar fórmulas do tipo AG EF α ou do tipo AG AF α é equivalente a verificar uma fórmula do tipo A end α, pois, a cada instante de todos os caminhos, é preciso reforçar a ocorrência de EF α ou AF α, respectivamente, logo α deverá obrigatoriamente ser válida no fim de todos os caminhos. Por outro lado, quando isso ocorre, ambas as fórmulas são válidas. I.IV EF AF α / AF EF α / EF EF α / AF AF α A Figura I.4 ilustra possibilidades de ocorrência da fórmula EF AF α. Figura I.4: Representação gráfica de possibilidades de uma fórmula do tipo EF AF α ser válida Em uma fórmula do tipo EF AF α, exige-se que, a partir de algum estado no futuro, α valha em algum estado futuro de todos os caminhos. Na Figura I.4, vemos que não é possível obter uma fórmula equivalente que seja mais fácil de verificar a partir de uma fórmula do tipo EF AF α. Em uma fórmula do tipo AF EF α, é preciso garantir que, em todos os caminhos, haja um ponto no futuro onde, daquele momento em diante, em pelo menos um caminho, a fórmula α é válida em um momento. Se α é válida em um momento de algum caminho qualquer (ou seja EF α vale), o momento de início (que pertence a todos os caminhos) justificará o fato de que AF EF α seja considerada válida. Por outro 96 lado, se AF EF α vale então EF α vale. Desse modo, uma fórmula do tipo AF EF α é equivalente a uma fórmula do tipo EF α. A obtenção de fórmulas equivalentes a fórmulas do tipo EF EF α ou AF AF α é trivial, ou seja, conclui-se que EF EF α é equivalente a EF α e AF AF α é equivalente a AF α. I.V AF (E end α) / AF (A end α) Em fórmulas do tipo AF (E end α) é necessário que o E end α seja válido para todos os caminhos a partir da raiz, só que se considerarmos isso basta que α seja válida em um dos finais, assim AF (E end α) é equivalente a E end α. Em fórmulas do tipo AF (A end α) é necessário que o A end α seja válido para todos os caminhos a partir da raiz, isso significa que é necessário garantir que α vale no fim de todos os caminhos, assim AF (A end α) é equivalente a A end α. I.VI EG AG α / AG EG α / EG EG α / AG AG α Em uma fórmula do tipo EG AG α há a obrigatoriedade de que a fórmula AG α seja válida em todos os estados de pelo menos um caminho, como todos os caminhos têm o mesmo ponto de partida, ou seja, as árvores possuem a mesma raiz, a fórmula α precisará ser válida em todos os estados a partir da raiz, logo AG α também terá que ser válida na raiz, isso força que α seja válida em todos os caminhos e em todos os estados. Assim, verificar uma fórmula do tipo EG AG α é equivalente a verificar uma fórmula do tipo AG α. Em uma fórmula do tipo AG EG α há a obrigatoriedade de que a fórmula EG α seja válida em todos os estados de todos os caminhos, assim, uma fórmula desse tipo é também equivalente a uma fórmula do tipo AG α. A obtenção de fórmulas equivalentes a fórmulas do tipo EG EG α ou AG AG α é trivial, ou seja, EG EG α é equivalente a EG α e AG AG α é equivalente a AG α. I.VII EG (E end α) / EG (A end α) / AG (E end α) / AG (A end α) Em fórmulas do tipo EG (E end α) a obtenção de uma fórmula equivalente é trivial, assim dizemos que ela é equivalente a EG (E end α). Em fórmulas do tipo EG A 97 end α é necessário garantir que existe um caminho em que A end α é sempre válida, se considerarmos o início da história, ou seja, o primeiro segundo do primeiro evento, A end α tem que ser sempre válida, o que significa dizer que α deverá ser válida em todos os finais, logo EG (A end α) é equivalente a A end α. A simplificação de fórmulas dos tipos AG (E end α) e AG (A end α) é feita de maneira trivial, ou seja, ambas são iguais a A end α, pois o AG força que α tenha que ser sempre válida no fim de todos os caminhos. I.VIII E (EF α U β) / A (EF α U β) Em uma fórmula do tipo E (EF α U β) há a obrigatoriedade de que a fórmula β seja válida em pelo menos um caminho Ao longo desse caminho, no entanto, é preciso garantir que α valha no futuro para todos os estados que antecedem o momento em que β vale. Isso implica que se encontre o caminho em que β vale e daquele momento em diante é preciso garantir a validade de α em pelo menos um caminho. Assim, uma fórmula do tipo E (EF α U β) é equivalente a uma fórmula do tipo EF (β ˄ EF α). A Figura I.5 ilustra possibilidades de ocorrência desse fato. Figura I.5: Representação gráfica de possibilidades de uma fórmula do tipo E (EF α U β) ser válida Em uma fórmula do tipo A (EF α U β) é preciso garantir que a fórmula β seja válida em algum estado de todos os caminhos. Além disso, é necessário encontrar pelo menos um estado em que a fórmula α seja válida em algum caminho depois do estado 98 em que β vale. Assim, uma fórmula do tipo A (EF α U β) é equivalente a uma fórmula do tipo AF (β ˄ EF α). A Figura I.6 ilustra possibilidades de ocorrência desse fato. Figura I.6: Representação gráfica de possibilidades de uma fórmula do tipo A (EF α U β) ser válida I.IX E (AF α U β) / A (AF α U β) Em uma fórmula do tipo E (AF α U β), é preciso garantir que a fórmula β seja válida em pelo menos um caminho, além disso, α precisa ser válida em todos os caminhos após β e em todos os caminhos em que β não é válida. Assim, uma fórmula do tipo E (AF α U β) é equivalente a uma fórmula do tipo EF (β ˄ AF α) ˄ AF α. A Figura I.7 ilustra possibilidades de ocorrência desse fato. 99 Figura I.7: Representação gráfica de possibilidades de uma fórmula do tipo E (AF α U β) ser válida Em uma fórmula do tipo A (AF α U β) é preciso garantir que a fórmula β seja válida em todos os caminhos, além disso, α precisa ser válida em todos os caminhos após β. Assim, uma fórmula do tipo A (AF α U β) é equivalente a uma fórmula do tipo AF (β ˄ AF α). A Figura I.8 ilustra possibilidades de ocorrência desse fato. Figura I.8: Representação gráfica de possibilidades de uma fórmula do tipo A (AF α U β) ser válida I.X E (EG α U β) / A (EG α U β) 100 Em uma fórmula do tipo E (EG α U β), é preciso garantir que a fórmula α seja válida em todos os estados de pelo menos um caminho e que exista pelo menos um estado, desse mesmo caminho, em que a fórmula β seja válida. Assim, uma fórmula do tipo E (EG α U β) é equivalente a uma fórmula do tipo EG (α ˄ EF β). A Figura I.9 ilustra possibilidades de ocorrência desse fato. Figura I.9: Representação gráfica de possibilidades de uma fórmula do tipo E (EG α U β) ser válida Em uma fórmula do tipo A (EG α U β) é preciso garantir que a fórmula α seja válida em todos os estados de todos os caminhos até que a fórmula β seja válida Desse momento em diante, é preciso garantir que a fórmula α seja válida em todos os estados de pelo menos um caminho. Assim, não é possível encontrar uma fórmula mais simples que seja equivalente a uma fórmula do tipo A (EG α U β). A Figura I.10 ilustra possibilidades de ocorrência desse fato. 101 Figura I.10: Representação gráfica de possibilidades de uma fórmula do tipo A (EG α U β) ser válida I.XI E (AG α U β) / A (AG α U β) Em uma fórmula do tipo E (AG α U β) é preciso garantir que a fórmula α seja válida em todos os estados de todos os caminhos e que exista pelo menos um estado em que a fórmula β seja válida. Assim, uma fórmula do tipo E (AG α U β) é equivalente a uma fórmula do tipo (AG α) ˄ (EF β). A Figura I.11 ilustra possibilidades de ocorrência desse fato. Figura I.11: Representação gráfica de possibilidades de uma fórmula do tipo E (AG α U β) ser válida 102 Em uma fórmula do tipo A (AG α U β), é preciso garantir que a fórmula α seja válida em todos os estados de todos os caminhos e que exista pelo menos um estado em todos os caminhos em que a fórmula β seja válida. Assim, uma fórmula do tipo A (AG α U β) é equivalente a uma fórmula do tipo (AG α) ˄ (AF β). A Figura I.12 ilustra possibilidades de ocorrência desse fato. Figura I.12: Representação gráfica de possibilidades de uma fórmula do tipo A (AG α U β) ser válida I.XII E (E end α U β) / A (E end α U β) Em uma fórmula do tipo E (E end α U β) é preciso garantir que a fórmula α seja válida no estado terminal de pelo menos um caminho e que exista pelo menos um estado antes desse fim em que a fórmula β seja válida. Assim, uma fórmula do tipo E (E end α U β) é equivalente a uma fórmula do tipo EF (β ˄ E end α). A Figura I.13 ilustra possibilidades de ocorrência desse fato. 103 Figura I.13: Representação gráfica de possibilidades de uma fórmula do tipo E (E end α U β) ser válida Em uma fórmula do tipo A (E end α U β) é preciso garantir que a fórmula β seja válida em pelo menos um estado de todos os caminhos e que pelo menos em um estado terminal, a partir da ocorrência de β, a fórmula α seja válida. Assim, uma fórmula do tipo A (E end α U β) é equivalente a uma fórmula do tipo AF (β ˄ E end α). A Figura I.14 ilustra possibilidades de ocorrência desse fato. Figura I.14: Representação gráfica de possibilidades de uma fórmula do tipo A (E end α U β) ser válida I.XIII E (A end α U β) / A (A end α U β) 104 Em uma fórmula do tipo E (A end α U β) é preciso garantir que a fórmula β seja válida em pelo menos um estado e que, em todos os estados terminais de todos os caminhos, a fórmula α seja válida. Assim, uma fórmula do tipo E (A end α U β) é equivalente a uma fórmula do tipo (EF β) ˄ (A end α). A Figura I.15 ilustra possibilidades de ocorrência desse fato. Figura I.15: Representação gráfica de possibilidades de uma fórmula do tipo E (A end α U β) ser válida Em uma fórmula do tipo A (A end α U β) é preciso garantir que a fórmula β seja válida em pelo menos um estado de todos os caminhos e que, em todos os estados terminais de todos os caminhos, a fórmula α seja válida. Assim, uma fórmula do tipo A (A end α U β) é equivalente a uma fórmula do tipo AF (β ˄ A end α). A Figura I.16 ilustra possibilidades de ocorrência desse fato. 105 Figura I.16: Representação gráfica de possibilidades de uma fórmula do tipo A (A end α U β) ser válida I.XIV E end (EF α) / E end (AF α) / E end (EG α) / E end (AG α) Em todas as fórmulas desse tipo α será obrigatoriamente válida no fim e, como o operador “end” força que a verificação de validade seja feita apenas no fim do caminho não há mais que se testar caminhos alternativos, logo a simples validade de α no fim do caminho garante a validade da fórmula como um todo, assim todas as fórmulas listadas no título são equivalentes a E end α. I.XV A end (EF α) / A end (AF α) / A end (EG α) / A end (AG α) Em todas as fórmulas desse tipo α será obrigatoriamente válida no fim de todos os caminhos e, como o operador “end” força que a verificação de validade seja feita apenas no fim de cada caminho não há a necessidade de testar caminhos alternativos, assim todas as fórmulas listadas no título são equivalentes a A end α. I.XVI E end (E (α α U β)) / E end (A (α α U β)) / E end (E end α) / E end (A end α) No caso de fórmulas do tipo E end (E (α U β)) e E end (A (α U β)) há a obrigação de que α e β sejam válidas no fim do caminho, como não há mais ramos alternativos a serem verificados basta que a conjunção das duas fórmulas (α ˄ β) seja 106 válida no fim, dessa forma E end (E (α U β)) e E end (A (α U β)) são equivalentes a E end (α ˄ β). No caso de fórmulas do tipo E end (E end α) e E end (A end α) há a obrigação de que α seja válida no fim do caminho, então, é fácil concluir que elas são equivalentes a E end α. I.XVII A end (E (α α U β)) / A end (A (α α U β)) / A end (E end α) / A end (A end α) No caso de fórmulas do tipo A end (E (α U β)) e A end (A (α U β)) há a obrigação de que α e β sejam válidas no fim de todos os caminhos, como não há mais ramos alternativos a serem verificados basta que a conjunção das duas fórmulas (α ˄ β) seja válida no fim de cada caminho, assim, A end (E (α U β)) e A end (A (α U β)) são equivalentes a A end (α ˄ β). No caso de fórmulas do tipo A end (E end α) e A end (A end α) é fácil concluir que são equivalentes a A end α. I.XVIII Fórmulas cujas possíveis simplificações não chegaram a ser estudadas • EF (E (α U β)) • EF (A (α U β)) • AF (E (α U β)) • AF (A (α U β)) • EG (E (α U β)) • EG (A (α U β)) • AG (E (α U β)) • AG (A (α U β)) • E (E (α U β) U θ) • E (A (α U β) U θ) • A (E (α U β) U θ) • A (A (α U β) U θ) 107 ANEXO II Algoritmos de Validação dos Operadores de Estado II.I Operador F Sempre que uma formula α qualquer é existencialmente quantificada ao longo dos estados futuros de um caminho (operador ‘F’), é necessário encontrar um estado em que a fórmula α é válida. A Figura II.1 ilustra o algoritmo que realiza esse passo da verificação para fórmulas existencialmente quantificadas ao longo dos estados. Para indicar a validade da subfórmula em um tempo durante o evento é criada uma variável que representa este tempo (T_VALID). Validar_F(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +INTERV_DERIV, −FORMULA_CONT, −VALOR_ACUM2) // Variáveis locais: // T_VALID: Variável criada para representar o tempo em que a fórmula é válida // T1,T2: tempos (porcentagens) correspondentes ao primeiro intervalo a ser tratado // PERC: Porcentagem do tempo do intervalo em que a fórmula valeu // DERIV1,DERIV2: valores das derivadas após T1 e após T2, respectivamente // FORMULA_CONT1: fórmula a ser verificada nos intervalos restantes // Valores de retorno: sucesso/falha SE (comprimento(INTERV_DERIV)<2)) VALOR_ACUM2=VALOR_ACUM FORMULA_CONT=FORMULA Retorne sucesso SE (comprimento(INTERV_DERIV)>=2) traz_basicas_para_frente(FORMULA,FORMULA1) (T1,DERIV1)=cabeca(INTERV_DERIV) (T2,DERIV2)=cabeca(cauda(INTERV_DERIV)) Calcula_variacao(T1,T2,DERIV1,VARIACAO) De forma não-determinística trate as das 2 possibilidades 108 1. SE Força_validade_intervalo_F(FORMULA1, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO,FORMULA_CONT1,VALOR_ACUM1, T_VALID, PERC)= falha Retorne falha SE (FORMULA_CONT1=’true’) Retorne sucesso 2. Soma_variacao(VALOR_ACUM,VARIACAO,VALOR_ACUM1) FORMULA_CONT1=FORMULA Retorne Validar_F(FORMULA_CONT1, VARIÁVEIS, VALOR_ACUM1, cauda(INTERV_DERIV), FORMULA_CONT, VALOR_ACUM) Fim Validar_F Figura II.1: Algoritmo não determinístico que verifica de que forma é preciso caminhar pela árvore da história quando uma fórmula é existencialmente quantificada. Essa função recursiva percorre todos os intervalos em que um evento é quebrado. A condição de parada da recursão corresponde ao fim da lista de intervalos ou à identificação de um instante onde a fórmula é válida e nada mais precisa ser verificado adiante. Quando há intervalos a processar, a fórmula a ser verificada é primeiro trabalhada de modo que as subfórmulas básicas sejam analisadas antes das subfórmulas quantificadas. Isso é feito dentro de cada elemento da disjunção (lembre-se que, na fórmula normalizada, as disjunções ficam externas às conjunções). A transferência de fórmulas básicas para frente é importante porque, em uma quantificação com o operador de estado ‘F’, ao se indicar um instante para a validade de uma subfórmula que seja uma conjunção, as componentes básicas devem valer nesse instante e as componentes quantificadas levam à necessidade de verificação na continuidade do caminho. Além da preparação da fórmula para ser processada, é feito, para cada intervalo, o cálculo da variação de cada propriedade de acordo com a respectiva derivada. Se a subfórmula valer em determinado momento do intervalo, o valor da variação até esse momento é uma percentagem da variação no intervalo e uma variável é criada para representar essa percentagem em restrições a serem enviadas ao constraint solver. Para cada intervalo, duas possibilidades são verificadas: α é válida em um ponto específico dentro do intervalo ou é valida após o intervalo. No primeiro caso, a verificação pode ser interrompida com sucesso se não houver fórmula a ser verificada na continuação. No segundo caso, os valores das propriedades são apenas acumulados de acordo com as respectivas derivadas. Esses casos são tratados não109 deterministicamente (através de backtracking cronológico na implementação). Se a satisfação é verificada para o primeiro caso, o segundo caso não precisa ser testado. No segundo caso e no primeiro, quando há fórmula a ser testada na continuação, é feita chamada para verificação a partir do próximo intervalo. O processo segue para o estabelecimento das restrições dentro do intervalo corrente. A função Força_validade_intervalo_F é chamada para dar início a esse procedimento. II.I.I Validade de fórmulas em intervalos em quantificações com operador F É necessário estabelecer as restrições impostas pela fórmula a cada intervalo que forma o evento. Isso é feito então verificando o tipo da subfórmula (básica, quantificada ou composta) com o qual se está trabalhando, verificando sua validade e retornando a fórmula que precisa ser válida no próximo intervalo, conforme ilustrado na Figura 4.7. Note que o processo é recursivo: a função da Figura II.2 é chamada diversas vezes até encontrar sucesso ou falha. Força_validade_intervalo_F(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM, −T_VALID, −PERC) SE basica(FORMULA) Retorne (Força_validade_intervalo_F_basica(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM, T_VALID, PERC) = falha) SE quantificada(FORMULA) Retorne (Força_validade_intervalo_F_quantificada(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM, T_VALID, PERC) = falha) SE composta(FORMULA) Retorne (Força_validade_intervalo_F_composta(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM, T_VALID, PERC) = falha) Fim Força_validade_intervalo_F Figura II.2: Algoritmo que verifica o tipo de fórmula a ser verificada no intervalo corrente. A figura II.3 ilustra o algoritmo que realiza a verificação quando a subfórmula é básica. Nesse caso, tentamos estabelecer as restrições dela no intervalo atual. Quando detectamos que a fórmula é válida em determinado instante, a satisfação da subfórmula 110 não precisa ser imposta nos intervalos remanescentes nem no evento corrente, nem nos eventos seguintes. Força_validade_intervalo_F_basica(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) SE (Adiciona_restricoes_intervalo_F(FORMULA, VARIÁVEIS, VARIACAO, VALOR_ACUM, T1, T2, T_VALID, PERC) = falha) Retorne falha soma_variacao(VALOR_ACUM,VARIACAO,VALOR_ACUM1) FORMULA_CONT = 'true' Retorne sucesso Fim Força_validade_intervalo_F_basica Figura II.3: Algoritmo que verifica a validade de uma fórmula básica para uma fórmula existencialmente quantificada. Quando se deseja forçar a validade de uma subfórmula quantificada em um tempo genérico do intervalo, é necessário identificar o operador de estado associado a ela e continuar o processo de acordo com esse quantificador. Essa situação é tratada pelo algoritmo apresentado na Figura II.4. Força_validade_intervalo_F_quantificada(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) SUBFORMULA=subformula(FORMULA) OP_EST = operador_estado(SUBFORMULA) SE OP_EST = 'F' SE (Forca_validade_intervalo_F(SUBFORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE OP_EST = 'END' FORMULA_CONT = FORMULA soma_variacao(VALOR_ACUM,VARIACAO,VALOR_ACUM1) Retorne sucesso SE OP_EST = 'G' SE (Reforca_validade_intervalo_F(SUBFORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE OP_EST = 'U' SUBFORMULA = F1 U F2 SE (Reforca_validade_intervalo_F(F1, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT1, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha 111 SE (Forca_validade_intervalo_F(F2, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT2, VALOR_ACUM1, T_VALID, PERC) = falha) FORMULA_CONT = FORMULA ∧ FORMULA_CONT1 Retorne sucesso SE FORMULA_CONT2 = 'true' FORMULA_CONT=FORMULA_CONT1 SENÃO FORMULA_CONT = FORMULA_CONT1 ∧ FORMULA_CONT2 Retorne sucesso Fim Forca_validade_ intervalo_F Figura II.4: Algoritmo que verifica a validade de uma fórmula quantificada. Pode-se verificar, nesse algoritmo, que, ao identificar um operador do tipo F, o sistema chama novamente a função que vai tentar estabelecer a validade de uma fórmula básica. Quando o sistema identificar um operador do tipo “end” a mesma fórmula é passada para ser verificada nos estados subseqüentes e apenas a variação dos valores dos níveis das propriedades é somada ao valor corrente. Já quando o sistema identificar um operador do tipo ‘G’, é executado o algoritmo apresentado na Figura 4.10. Ao identificar um operador do tipo F1 U F2, o processo é dividido em dois, verificando-se a validade de F1 e F2. F1 é verificada de forma análoga a uma fórmula quantificada como operador ‘G’ e F2 a uma quantificada com o operador ‘F’. Devido a simplificações feitas durante a normalização, sabe-se que uma fórmula F1 dentro de um operador F1 U F2 contém obrigatoriamente um operador ‘G’, o que obriga a sua validade durante todo o intervalo. Por outro lado, a fórmula F2 pode ou não valer no intervalo. Se não valer, na continuidade do caminho a verificação deverá continuar para uma fórmula com o operador U. Caso F2 valha, deverá ser verificada desse ponto em diante uma fórmula composta pela conjunção entre a fórmula de continuação resultante da verificação de F1 e a resultante da verificação de F2. Quando se deseja forçar a validade de uma subfórmula composta em um tempo genérico do intervalo, é necessário identificar qual o tipo de composição dela (disjunção ou conjunção) e continuar o processo de acordo com o conectivo. Essa situação é tratada pelo algoritmo apresentado na Figura II.5. 112 Forca_validade_intervalo_F_composta(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) SE conjunção(FORMULA) SE (Força_validade_intervalo_F_Conj(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE disjunção(FORMULA) SE (Força_validade_intervalo_F_Disj(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha Retorne sucesso Fim Forca_validade_intervalo_F_composta Figura II.5: Algoritmo que verifica a validade de fórmula composta. Após verificar a maneira como a fórmula está composta o procedimento segue para validar uma conjunção (Força_validade_intervalo_F_Conj) ou uma disjunção (Força_validade_intervalo_F_Disj) de fórmulas. Cada tipo de conectivo tem sua forma específica de avaliação. 113 Na Figura II.6 está ilustrado o algoritmo que realiza a verificação para fórmulas formadas por uma conjunção de subfórmulas. Forca_validade_intervalo_F_Conj(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) FORMULA = F1 ˄ F2 SE (Forca_validade_intervalo_F(F1, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMU- LA_CONT1, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE (Forca_validade_intervalo_F(F2, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMU- LA_CONT2, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE (FORMULA_CONT1 <> 'true') SE (FORMULA_CONT2 <> 'true') FORMULA_CONT = FORMULA_CONT1 ˄ FORMULA_CONT2 FORMULA_CONT = FORMULA_CONT1 SE (FORMULA_CONT1 = 'true') SE (FORMULA_CONT2 <> 'true') FORMULA_CONT = FORMULA_CONT2 FORMULA_CONT = 'true' Retorne Sucesso Fim Forca_validade_intervalo_F_Conj Figura II.6: Algoritmo que verifica a validade de uma conjunção. Quando se está trabalhando com uma conjunção de fórmulas F1 e F2 dentro de um F é necessário que ambas sejam válidas no mesmo tempo T_VALID, assim a verificação de F1 e F2 precisa ser bem-sucedida. Após a verificação é necessário analisar as fórmulas de continuação resultantes do processamento de F1 (FORMULA_CONT1) e do processamento de F2 (FORMULA_CONT2). Se ambas forem iguais a 'true' não há mais nada a ser verificado, logo o sistema retorna sucesso. Caso apenas FORMULA_CONT1 seja igual a 'true' a busca deve continuar para FORMULA_CONT2. Caso apenas FORMULA_CONT2 seja igual a 'true' a busca deve continuar para FORMULA_CONT1. E no último caso se ambas forem diferentes de 'true' o processo continua para a fórmula composta FORMULA_CONT1˄FORMULA_CONT2. 114 Na Figura II.7 está ilustrado o algoritmo que realiza a verificação para fórmulas formadas por uma disjunção de subfórmulas. Forca_validade_intervalo_F_Disj(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) FORMULA = F1 ˅ F2 SE (Forca_validade_intervalo_F(F1, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMU- LA_CONT1, VALOR_ACUM1, T_VALID, PERC) = falha) SE (Forca_validade_intervalo_F(F2, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT2, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE (FORMULA_CONT2 <> 'true') SE (FORMULA_CONT2 <> F1) FORMULA_CONT = FORMULA_CONT2 ˅ F1 Retorne sucesso SENÃO FORMULA_CONT = F1 SENÃO FORMULA_CONT = 'true' Retorne sucesso SE (FORMULA_CONT1 <> 'true') SE (Forca_validade_intervalo_F(F2, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT2, VALOR_ACUM1, T_VALID, PERC) = falha) FORMULA_CONT = FORMULA_CONT1 ˅ F2 Retorne sucesso SE (FORMULA_CONT2 <> ‘true’) SE (FORMULA_CONT1 <> FORMULA_CONT2) FORMULA_CONT = FORMULA_CONT1 ˅ FORMULA_CONT2 Retorne sucesso SENÃO FORMULA_CONT = FORMULA_CONT1 Retorne sucesso SENÃO FORMULA_CONT = 'true' Retorne sucesso SE FORMULA_CONT = 'true' FORMULA_CONT = 'true' Retorne sucesso Fim Forca_validade_intervalo_F_Disj Figura II.7: Algoritmo que verifica a validade de uma disjunção. Em uma fórmula do tipo F1 ˅ F2, basta que uma das fórmulas (F1 ou F2) seja válida. Primeiro testamos a validade de F1 que gera duas situações possíveis: (i) F1 é válida ou (ii) F1 não é valida. 115 No primeiro caso (i) verificamos se a fórmula de continuação (FORMULA_CONT1) retornada é igual a ‘true’, se for a busca termina, senão devemos verificar a validade de F2 que também gera duas situações possíveis: (1) F2 é válida ou (2) F2 não é valida. (1) Quando F2 é válida verificamos se a fórmula de continuação (FORMULA_CONT2) retornada é igual a ‘true’ se for a busca termina, senão é preciso verificar se FORMULA_CONT1 é diferente de FORMULA_CONT2, se for a fórmula de continuação (FORMULA_CONT) FORMULA_CONT1˅FORMULA_CONT2, FORMULA_CONT1. (2) Quando F2 será senão não é igual FORMULA_CONT válida FORMULA_CONT a = = FORMULA_CONT1 ˅ F2. No segundo caso (ii) passamos direto para a verificação da validade de F2. Caso seja bem-sucedida (1) verificamos se FORMULA_CONT2 é diferente de ‘true’ se for a busca termina, senão verificamos se FORMULA_CONT2 é diferente de F1 se for FORMULA_CONT = FORMULA_CONT2 ˅ F1, senão FORMULA_CONT = F1. No caso em que a verificação de F2 falha (2) o sistema retorna falha, pois nenhuma das duas fórmulas foi válida naquele momento específico. Quando é necessário lidar com uma fórmula quantificada com o operador ‘G’ é preciso realizar um procedimento específico, que, em muitos momentos é análogo a processos de verificação já apresentados anteriormente, assim, deste momento em diante sempre indicaremos quando isso acontecer. A Figura II.8 mostra a função que trata as fórmulas quantificadas com o operador ‘G’. Reforca_validade_intervalo_F(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) SE basica(FORMULA) Retorne Reforça_validade_intervalo_F_basica(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VA- RIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) SE quantificada(FORMULA) Retorne Reforça_validade_intervalo_F_quantificada(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) SE composta(FORMULA) Retorne Reforça_validade_intervalo_F_composta(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) Fim Reforça_validade_intervalo_F Figura II.8: Algoritmo que verifica uma subfórmula com quantificador G dentro de um quantificador F 116 Note que o algoritmo da Figura II.8 é análogo ao da Figura II.2. O algoritmo que trata uma fórmula básica dentro de um ‘F’ com o operador ‘G’ está ilustrado na Figura II.9. Reforça_validade_intervalo_F_basica (+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) SE (Adiciona_restricoes_intervalo_FG(FORMULA, VARIÁVEIS, VARIACAO, VALOR_ACUM, T1, T2, T_VALID, PERC) = falha) Retorne falha soma_variacao(VALOR_ACUM,VARIACAO,VALOR_ACUM1) FORMULA_CONT = FORMULA Fim Reforça_validade_intervalo_F_basica Figura II.9: Algoritmo que verifica a validade de uma subfórmula básica com operador G dentro de um operador F. Como o operador é do tipo ‘G’ a fórmula deverá ser reforçada nos instantes e eventos subseqüentes, por isso ela é retornada pelo algoritmo. Quando a função Reforca_validade_intervalo_F identifica uma fórmula quantificada é chamada a fórmula Forca_validade_intervalo_F para realizar o tratamento dessa situação, já quando ela encontra uma fórmula composta é chamada a função Reforca_validade_intervalo_F_composta, cujo algoritmo está ilustrado na Figura II.10. 117 Reforça_validade_intervalo_F_composta(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) SE FORMULA = F1 ˅ F2 SE (Força_validade_intervalo_F(not(FORMULA), VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT1, VALOR_ACUM1, T_VALID, PERC) <> falha) SE FORMULA_CONT1 = 'true' Retorne Falha SENÃO FORMULA_CONT = FORMULA ˄ not(FORMULA_CONT1) SENÃO FORMULA_CONT = FORMULA Retorne sucesso SE FORMULA = F1 ˄ F2 SE (Reforça_validade_intervalo_F(F1, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT1, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE (Reforca_validade_intervalo_F(F2, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT2, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha FORMULA_CONT = FORMULA CONT1 ˄ FORMULA_CONT2 soma_variacao(VALOR_ACUM,VARIACAO,VALOR_ACUM1) Retorne sucesso Reforca_validade_intervalo_F_composta Figura II.10: Algoritmo que verifica a validade de uma fórmula composta dentro de um G. Quando a fórmula composta é do tipo FORMULA = F1 ˅ F2 a negação dela não pode ser válida dentro de nenhum intervalo, caso seja o sistema retorna falha e a busca termina. Quando a fórmula composta é do tipo FORMULA = F1 ˄ F2 ambas precisam valer ao longo de todo o intervalo, se a verificação retorna falha para qualquer uma das duas o sistema retorna falha e a busca termina. II.II Operador G Sempre que uma fórmula α qualquer é globalmente quantificada ao longo dos estados futuros de um caminho (operador ‘G’), o processo de verificação é similar ao processo de verificação para a quantificação existencial (operador ‘F’). A diferença principal é que α precisa ser válida em todos os instantes de todos os intervalos dos eventos. Devido ao fato de que as propriedades de tempo contínuo têm derivada constante durante o intervalo, a tarefa é facilitada. Assim como no caso do operador ‘F’, 118 o processo de verificação é feito por partes. A figura II.11 ilustra o algoritmo geral que realiza a verificação para fórmulas globalmente quantificadas ao longo dos estados. Validar_G(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +INTERV_DERIV, +FORMULA_ADIC, −FORMULA_CONT, −VALOR_ACUM2) // Variáveis locais: // T_VALID: Variável criada para reforçar o tempo em que a fórmula foi válida // PERC: Porcentagem do intervalo em que a fórmula valeu // Valores de retorno: sucesso/falha SE (comprimento(INTERV_DERIV)<2) VALOR_ACUM2=VALOR_ACUM FORMULA_CONT=FORMULA_ADIC Retorne sucesso SE (comprimento(INTERV_DERIV)>=2) (T1,DERIV1)=cabeca(INTERV_DERIV) (T2,DERIV2)=cabeca(cauda(INTERV_DERIV)) Calcula_variacao(T1,T2,DERIV1,VARIACAO) SE Forca_validade_intervalo_G(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT1, VALOR_ACUM1, T_VALID, PERC)= falha Retorne falha SE (FORMULA_ADIC<>true) SE Forca_validade_intervalo_G(FORMULA_ADIC, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT2, VALOR_ACUM1, T_VALID, PERC)= falha Retorne falha SENÃO FORMULA_CONT2=true FORMULA_ADIC2=simplifica_formula(FORMULA_CONT1∧ ∧FORMULA_CONT2) // Olha duas fórmulas, se uma delas for ‘true’ FORMULA_ADIC2 recebe apenas a outra, se elas forem FORMULA_ADIC2 recebe apenas uma delas Retorne Validar_G(FORMULA_CONT1, VARIÁVEIS, VALOR_ACUM1, cauda(INTERV_DERIV), FORMULA_ADIC2, FORMULA_CONT, VALOR_ACUM) Fim Validar_G Figura II.11: Algoritmo de verificação de fórmulas globalmente quantificadas ao longo dos estados de um caminho. O próximo passo no processo de verificação para fórmulas com o operador ‘G’ é semelhante ao processo de verificação para fórmulas com o operador ‘F’. Faz-se chamada para verificar a validade a partir do primeiro evento. Para tal, é necessário verificar o tipo de fórmula com o qual será preciso lidar. O processo aqui também é recursivo. 119 Forca_validade_intervalo_G(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) SE basica(FORMULA) Retorne Força_validade_intervalo_G_basica(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) SE quantificada(FORMULA) Retorne Força_validade_intervalo_G_quantificada(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) SE composta(FORMULA) Retorne Força_validade_intervalo_G_composta(FORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) Fim Força_validade_intervalo_G Figura II.12: Algoritmo que verifica o tipo de fórmula globalmente quantificada Note que o algoritmo da Figura II.12 é análogo ao da Figura II.8. A figura II.13 ilustra o algoritmo que realiza a verificação quando a subfórmula é básica. Forca_validade_intervalo_G_basica(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) SE (Adiciona_restricoes_intervalo_G(FORMULA, VARIÁVEIS, VARIACAO, VALOR_ACUM, T1, T2, T_VALID, PERC) = falha) Retorne falha soma_variacao(VALOR_ACUM,VARIACAO,VALOR_ACUM1) FORMULA_CONT = ‘true’ Retorne sucesso Fim Forca_validade_intervalo_G_basica Figura II.13: Algoritmo de verificação de fórmulas básicas globalmente quantificadas. Se a subfórmula que está sendo verificada for básica, o processo tenta estabelecer as restrições dela no intervalo atual. Se for possível, ela precisa ainda ser imposta nos intervalos remanescentes tanto do evento corrente quanto dos eventos seguintes. Caso não seja possível estabelecê-la no intervalo, o sistema retorna falha. Uma restrição do tipo a>b precisa ser válida nas extremidades do intervalo. A fim de impor a satisfação de uma fórmula, as restrições sobre as extremidades dos intervalos são então enviadas para o constraint solver. A estratégia descrita para lidar com quantificadores sobre todos os estados de um caminho não funciona quando a fórmula é uma disjunção ou uma restrição básica do tipo a≠b, porque as restrições sobre 120 as extremidades dos intervalos não implicam a satisfação ao longo do intervalo. Nesses casos, a verificação de AG α e EG α são feitas indiretamente e ocorrem pelo meio da verificação de que EF ¬α e AF ¬α não são válidos, respectivamente. Na figura II.14 apresentamos o algoritmo que verifica fórmulas compostas, onde esse fato está representado. Forca_validade_intervalo_G_composta(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) SE (FORMULA = F1 ˅ F2) SE (Forca_validade_intervalo_F(not(FORMULA), VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT1, VALOR_ACUM1, T_VALID, PERC) <> falha) SE FORMULA_CONT1 = 'true' Retorne Falha SENÃO FORMULA_CONT = not(FORMULA_CONT1) SENÃO FORMULA_CONT = 'true' Retorne sucesso SE (FORMULA = F1 ˄ F2) SE (Forca_validade_intervalo_G(F1, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT1, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE (Forca_validade_intervalo_G(F2, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT2, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE SUBFORMULA = FORMULA_CONT1 ˄ FORMULA_CONT2 FORMULA_CONT = 'true' SENÃO FORMULA_CONT = FORMULA_CONT1 ˄ FORMULA_CONT2 Fim Forca_validade_intervalo_G_composta Figura II.14: Algoritmo que verifica fórmulas compostas que são globalmente quantificadas. 121 As fórmulas quantificadas também precisam ter sua validade reforçada ao longo dos estados do caminho. A Figura II.15 ilustra o algoritmo que realiza essa tarefa. Força_validade_intervalo_G_quantificada(+FORMULA, +VARIÁVEIS, +VALOR_ACUM, +T1, +T2, +VARIACAO, −FORMULA_CONT, −VALOR_ACUM1, −T_VALID, −PERC) SUBFORMULA=subformula(FORMULA) OP_EST = operador_estado(SUBFORMULA) SE OP_EST = 'F' SE (Forca_validade_intervalo_F(SUBFORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE OP_EST = 'END' FORMULA_CONT = FORMULA soma_variacao(VALOR_ACUM,VARIACAO,VALOR_ACUM1) Retorne sucesso SE OP_EST = 'G' SE (Forca_validade_intervalo_G(SUBFORMULA, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE OP_EST = 'U' SUBFORMULA = F1 U F2 SE (Forca_validade_intervalo_G(F1, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT1, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SE (Forca_validade_intervalo_F(F2, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT2, VALOR_ACUM1, T_VALID, PERC) = falha) FORMULA_CONT = FORMULA_CONT1 Retorne sucesso SE FORMULA_CONT2 = 'true' FORMULA_CONT=FORMULA_CONT1 SENÃO FORMULA_CONT = FORMULA_CONT1 ∧ FORMULA_CONT2 Retorne sucesso Fim Forca_validade_intervalo_G_quantificada Figura II.15: Algoritmo globalmente quantificado que verifica a validade de uma fórmula quantificada. Note que o algoritmo ilustrado pela Figura II.15 é análogo ao algoritmo ilustrado pela Figura II.4. II.III Operador U Sempre que temos uma fórmula do tipo α U β para verificar, é necessário verificar se α é sempre válida em todos os estados até que β seja válida. A fim de fazer isso, nós misturamos as estratégias utilizadas para a verificação de fórmulas com os 122 operadores ‘G’ e ‘F’ (conforme ilustrado na figura II.16). Restrições são impostas nas extremidades dos intervalos para forçar a satisfação de α, mas também consideramos (através da imposição de restrições) que β pode ser válida em um ponto específico do intervalo, o que torna a verificação da satisfação de α desnecessária no restante do caminho. Validar_U(+FORMULA, +QUANT_CAM, +VARIÁVEIS, +VALOR_ACUM, +INTERV_DERIV, +ALTS) // Variáveis locais: // T_VALID: Variável criada para reforçar o tempo em que a fórmula foi válida // PERC: Porcentagem do intervalo em que a fórmula valeu // Valores de retorno: sucesso/falha SE (comprimento(INTERV_DERIV)<2) FORMULA_PROX_EVENTOS = compõe_formula(FORMULA, QUANT_CAM, ‘U’) Retorne Validar_alts(FORMULA_PROX_EVENTOS,VARIÁVEIS,VALOR_ACUM,ALTS) SE (comprimento(INTERV_DERIV)>=2) (T1,DERIV1)=cabeca(INTERV_DERIV) (T2,DERIV2)=cabeca(cauda(INTERV_DERIV)) Calcula_variacao(T1,T2,DERIV1,VARIACAO) FORMULA = F1 U F2 SE (Forca_validade_intervalo_F(F2, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT2, VALOR_ACUM1, T_VALID, PERC) = falha) SE (Forca_validade_intervalo_G(F1, VARIÁVEIS, VALOR_ACUM, T1, T2, VARIACAO, FORMULA_CONT1, VALOR_ACUM1, T_VALID, PERC) = falha) Retorne falha SENÃO SE (FORMULA_CONT1 = ‘true’) FORMULA_CONT_AUX = F1 U F2 SENÃO FORMULA_CONT_AUX = (F1 U F2) ∧ FORMULA_CONT1 SENÃO SE (Forca_validade_intervalo_G(F1, VARIÁVEIS, VALOR_ACUM, T1, T_VALID, VARIACAO, FORMULA_CONT1, VALOR_ACUM1, T_VALID1, PERC) = falha) Retorne falha SE (FORMULA_CONT2 = 'true') SE (FORMULA_CONT1 = ‘true’) Retorne sucesso SENÃO FORMULA_CONT_AUX = FORMULA_CONT1 SENÃO FORMULA_CONT_AUX=FORMULA_CONT1 ˄ FORMULA_CONT2 SE (FORMULA_CONT_AUX = F3 ∧ F4) 123 OP_EST1=operador_estado(F3) OP_EST2=operador_estado(F4) SE (Validar_a_partir_de_evento(F3, QUANT_CAM, OP_EST1, VARIÁVEIS, VALOR_ACUM1, cauda(INTERV_DERIV), ALTS) = falha) Retorne falha SE (Validar_a_partir_de_evento(F4, QUANT_CAM, OP_EST2, VARIÁVEIS, VALOR_ACUM1, cauda(INTERV_DERIV), ALTS) = falha) Retorne falha Retorne sucesso SENÃO OP_EST3=operador_estado(FORMULA_CONT_AUX) Retorne Validar_a_partir_de_evento(FORMULA_CONT_AUX, QUANT_CAM, OP_EST3, VARIÁVEIS, VALOR_ACUM1, cauda(INTERV_DERIV), ALTS) Fim Validar_U Figura II.16: Algoritmo que verifica fórmulas compostas que são condicionalmente quantificadas. Observe que primeiro é necessário testar o comprimento do intervalo, assim como nas demais funções que validam operadores, depois é necessário verificar as fórmulas que precisam ser verificadas para os próximos intervalos que pode ser uma fórmula quantificada com o U ou uma conjunção de fórmulas quantificadas que devem ser verificadas nos eventos subseqüentes. II.IV Operador END Fórmulas com o operador “end” são verificadas apenas após a execução do último evento de um caminho. A Figura II.17 ilustra o algoritmo de verificação quando o operador “end” está sendo considerado. Nesse caso, apenas a variação é acumulada e passada para os eventos subseqüentes até que não haja mais alternativas para serem testadas. Validar_END(+VALOR_ACUM, +INTERV_DERIV, −VALOR_ACUM2) SE (comprimento(INTERV_DERIV)<2) VALOR_ACUM2=VALOR_ACUM Retorne sucesso SE (comprimento(INTERV_DERIV)>=2) (T1,DERIV1)=cabeca(INTERV_DERIV) (T2,DERIV2)=cabeca(cauda(INTERV_DERIV)) Calcula_variacao(T1,T2,DERIV1,VARIACAO) Soma_variacao(VALOR_ACUM,VARIACAO,VALOR_ACUM1) Retorne Validar_END(VALOR_ACUM1,cauda(INTERV_DERIV),VALOR_ACUM) Fim Validar_END Figura II.17: Algoritmo de verificação de fórmulas com o operador “end”. 124