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