Dissertação Gottin

Universidade Federal do Estado do Rio de Janeiro
Departamento de Informática Aplicada
Programa de Pós-Graduação em Informática
VERIFICAÇÃO ABSTRATA DE PROPRIEDADES DRAMÁTICAS CONTÍNUAS
EM EVENTOS NÃO DETERMINÍSTICOS
Vinícius Michel Gottin
Orientador
Prof. Dr. Angelo Ernani Maia Ciarlini
Rio de Janeiro
2013
VERIFICAÇÃO ABSTRATA DE PROPRIEDADES DRAMÁTICAS CONTÍNUAS
EM EVENTOS NÃO DETERMINÍSTICOS
Vinícius Michel Gottin
DISSERTAÇÃO APRESENTADA COMO REQUISITO PARCIAL PARA
OBTENÇÃO DO TÍTULO DE MESTRE PELO PROGRAMA DE PÓSGRADUAÇÃO EM INFORMÁTICA DA UNIVERSIDADE FEDERAL DO ESTADO
DO RIO DE JANEIRO (UNIRIO). APROVADA PELA COMISSÃO
EXAMINADORA ABAIXO ASSINADA.
Aprovada por:
_______________________________________________
Prof. Angelo Ernani Maia Ciarlini, D.Sc. – UNIRIO
_______________________________________________
Prof. Sean Wolfgand Matsui Siqueira, D.Sc. – UNIRIO
_______________________________________________
Prof. Antonio Luz Furtado, Ph.D. – PUC-RIO
_______________________________________________
Prof. Bruno Feijó, Ph.D. – PUC-RIO
RIO DE JANEIRO, RJ - BRASIL
OUTUBRO DE 2013
ii
Gottin, Vinícius Michel.
G686
Verificação abstrata de propriedades dramáticas contínuas em eventos
não determinísticos / Vinícius Michel Gottin, 2013.
85 f. ; 30 cm
Orientador: Angelo Ernani Maia Ciarlini.
Dissertação (Mestrado em Informática) - Universidade Federal do
Estado do Rio de Janeiro, Rio de Janeiro, 2013.
1. Inteligência artificial. 2. Storytelling interativo. 3. Dramatização.
4.Interação homem- máquina. 4. Programação lógica (Computação). I.
Ciarlini, Angelo Ernani Maia. II. Universidade Federal do Estado do Rio
de Janeiro. Centro de Ciências Exatas e Tecnológicas. Curso de Mestrado
em Informática. III. Título.
CDD – 006.3
iii
Dedicado a meus pais.
iv
Agradecimentos
Agradeço ao professor e orientador Angelo Ciarlini, que tornou todo o trabalho possível
e interessante. Também ao colega Paulo Abelha, por ter compartilhado as horas de
trabalho. É um privilégio poder trabalhar ao lado de quem gosta de resolver problemas
complexos.
Agradeço a todos que me acompanharam ao longo do período do mestrado. Aos colegas
e professores, pela parceria e apoio. Aos amigos e colegas de república que me
receberam no Rio de Janeiro.
Aos amigos distantes, que ainda mantêm contato.
Agradeço a minha família por me apoiar e pela paciência com a falta de visitas.
Agradeço à Luíza, por ter me acompanhado, me inspirado e compartilhado a minha
vontade de prosseguir estudando longe de casa.
Por fim, agradeço à CAPES pelo financiamento e incentivos.
v
GOTTIN, Vinícius Michel. Verificação Abstrata de Propriedades Dramáticas
Contínuas em Eventos Não Determinísticos. UNIRIO, 2013. 85 páginas. Dissertação
de Mestrado. Departamento de Informática Aplicada, UNIRIO.
RESUMO
Em sistemas de Storytelling Interativo, uma narrativa é gerada e dramatizada sob a
influência da interação com um ou mais usuários. O uso de técnicas de planejamento
automatizado para a geração de enredos em sistemas de Storytelling Interativo provê a
garantia de coerência com diversidade, em particular quando considera o não
determinismo dos eventos. Para possibilitar que o processo de geração de enredos atue
em paralelo com a dramatização, evitando pausas na experiência do usuário, é
necessário que o planejamento seja realizado no menor tempo possível. A consideração
de restrições sobre propriedades dramáticas relevantes aumentaria o poder expressivo
conferido ao autor e a qualidade estética da história. Considerar que essas propriedades
variam continuamente ao longo dos eventos, de forma que possam representar aspectos
dramatizáveis, tornaria o processo de planejamento mais complexo. Para evitar que a
complexidade adicional torne o paralelismo entre a geração e dramatização inviáveis,
propomos um modelo no qual uma pré-verificação exaustiva das restrições sobre
propriedades dramáticas em eventos não determinísticos provê resultados indexados ao
planejamento. Para tanto, trabalhamo com uma lógica de tempo contínuo ramificado
proposta para o contexto de Storytelling, e utiliza-se programação em lógica com
restrições para verificar a satisfação de restrições sobre a variação linear de
propriedades contínuas ao longo de eventos narrativos abstratos e não determinísticos.
Palavras-chave: Storytelling Interativo; Propriedades Dramáticas, Arco Dramático;
Verificação de Modelos; Execução Simbólica, Inteligência Artificial; Não determinismo
vi
ABSTRACT
In Interactive Storytelling systems, a narrative is generated and dramatized under the
influence of one or more user`s interaction. Applying automated planning techniques
for the generation of plots guarantees coherence and the necessary diversity for a good
variability, in particular when nondeterministic events are considered. In order to enable
the plot generation process to act in parallel with the dramatization, avoiding breaks in
user experience, it is necessary for the planning to be accomplished in reasonable time.
The consideration of restrictions over dramatic properties would enhance the author’s
expressive power and the story’s aesthetic quality. Considering that these properties
vary continuously during events, in order to represent dramatizable aspects, would add
complexity to the planning process. To avoid this additional complexity turning the
parallelism between generation and dramatization impracticable, we propose a model in
which an exhaustive offline verification of restrictions over dramatic properties in
nondeterministic events generates indexed results to the planning process. To do so, we
work with continuous ramified time logic, proposed for the Storytelling context, and
apply constraint logic programming in order to verify the satisfaction of restrictions
over continuous properties during abstract narrative nondeterministic events.
Keywords: Interactive Storytelling; Dramatic properties; Model checking; Symbollic
execution; Artificial Intelligence; Nondeterminism
vii
SUMÁRIO
1
Introdução .......................................................................................................................................... 1
1.1
1.2
1.3
1.4
1.5
2
Motivação ................................................................................................................................... 1
Definição do problema ................................................................................................................ 3
Proposta ...................................................................................................................................... 6
Hipótese ...................................................................................................................................... 6
Estrutura ...................................................................................................................................... 7
Fundamentação Teórica .................................................................................................................... 8
2.1
Storytelling Interativo ................................................................................................................. 8
2.1.1 Planejamento em Storytelling ............................................................................................... 10
2.1.2 Arcos dramáticos .................................................................................................................. 12
2.1.3 Tempo contínuo em Storytelling ........................................................................................... 13
2.1.4 Logtell ................................................................................................................................... 14
2.2
Verificação de Proriedades ....................................................................................................... 14
2.2.1 Model checking ..................................................................................................................... 15
2.2.2 Sistemas de transição de estados .......................................................................................... 16
2.2.3 Execução Simbólica .............................................................................................................. 18
2.3
Contraint Logic Programming .................................................................................................. 19
2.4
CTL ........................................................................................................................................... 21
2.4.1 CTL-estendida ...................................................................................................................... 22
3
Modelo .............................................................................................................................................. 24
3.1
Modelo de conteúdo .................................................................................................................. 24
3.1.1 Propriedades dramáticas ..................................................................................................... 25
3.1.2 Fórmulas típicas em CTL-estendida ..................................................................................... 26
3.1.3 Eventos ................................................................................................................................. 26
3.2
Modelo de verificação e consulta .............................................................................................. 30
4
Algoritmos de Verificação Abstrata ............................................................................................... 36
Processamento exaustivo .......................................................................................................... 36
4.1
4.1.1 Verify_Formulae_Events ...................................................................................................... 37
4.1.2 Gen_Tree .............................................................................................................................. 39
4.2
Algoritmo de verificação .......................................................................................................... 42
4.2.1 Tratamento das situações ..................................................................................................... 45
4.3
Satisfação .................................................................................................................................. 48
4.4
Consulta .................................................................................................................................... 64
5
Resultados e avaliação ..................................................................................................................... 67
6
Conclusões e Trabalhos Futuros .................................................................................................... 74
6.1
6.2
6.3
7
Considerações Gerais ................................................................................................................ 74
Principais Contribuições ........................................................................................................... 75
Trabalhos Futuros ..................................................................................................................... 76
Referências ....................................................................................................................................... 79
viii
LISTA DE FIGURAS
Figura 1.1. Representação do ciclo contínuo de geração-dramatização, com os capítulos dramatizados
tendo sua continuação gerada em paralelo........................................................................................... 2
Figura 1.2. Comparação da consideração de um evento no processo de planejamento quando não é (esq.)
e quando é (dir.) necessário considerar a variação de propriedades dramáticas. Os quadrados
representam estados internos do evento, do inicial (mais à esquerda) aos finais (mais à direita). ....... 3
Figura 1.3. Abordagem de geração e teste, com etapa de verificação intercalada. Os planos desperdiçados
causam a demora excessiva na geração de um capítulo, quebrando o ciclo de geração-dramatização
em paralelo. ......................................................................................................................................... 4
Figura 1.4. Aumento no número de alternativas a serem consideradas causando uma diferença
exponencialmente maior no tempo necessário para o planejamento; e a subsequente quebra no ciclo
contínuo de geração/dramatização. ...................................................................................................... 5
Figura 3.1. Modelo de conteúdo representando os conjuntos de Eventos, de Fórmulas típicas e
Propriedades dramáticas em cada instância de Gênero. ................................................................... 25
Figura 3.2. Autômato não determinístico associado ao evento Try to Kidnap. ......................................... 27
Figura 3.3. Variação linear das propriedades dramáticas associada aos estados do autômato Try to
Kidnap. .............................................................................................................................................. 29
Figura 4.1. Chamada, pelo algoritmo de verificação, ao algoritmo de satisfação para fórmula com
expressão interna básica. ................................................................................................................... 52
Figura 4.2. Variação da propriedade Joy ao longo de uma transição na qual dobra de valor, em relação a
uma variável que representa o tempo transcorrido. ........................................................................... 53
Figura 4.3. Resultado da chamada ao algoritmo de satistafação de fórmula sobre transição. ................... 54
Figura 4.4. No tratamento de fórmulas aninhadas, a expressão interna é dividida. Uma chamada recursiva
ao algoritmo de satisfação é realizada sobre a fórmula contendo a primeira parcela de conjunção
original, resultando em uma lista de alternativas parciais.................................................................. 61
Figura 4.5. Tratamento de fórmula interna de fórmula aninhada. As alternativas geradas na satisfação do
primeiro termo da fórmula são recebidas como L_Above, e são utilizadas para gerar a satisfação da
fórmula interna de forma hierarquicamente dependente. ................................................................... 62
Figura 5.1. Autômato descrevendo as possíveis execuções de dramatização do evento Fight to the Death.
........................................................................................................................................................... 69
Figura 5.2. Árvore de execução gerada a partir do autômato do evento Fight to the Death. ...................... 70
ix
LISTA DE TABELAS
Tabela 1. Exemplos semânticos de consulta. ............................................................................................. 31
Tabela 2. Exemplo resultado condicionados à restrições sobre propriedades de contexto. ....................... 32
Tabela 3. Tratamento de alternativas de acordo com operadores de estado. ............................................. 56
Tabela 4. Tabela de composição de alternativas por operador no caso da satisfação básica. .................... 58
Tabela 5. Tabela de composições de resultados de alternativas hierárquicas. ........................................... 63
Tabela 6. Exemplos de restrições e fórmulas equivalentes representadas no modelo. .............................. 67
Tabela 7. Resultados da verificação de AF ({Joy ≥ 50} and EG {Fear ≥ Joy }) sobre o evento Fight to
the Death............................................................................................................................................ 71
x
LISTA DE ALGORITMOS
Algoritmo 4-1. VERIFY_FORMULAE_EVENTS. ........................................................................................... 38
Algoritmo 4-2. GEN_TREE. ........................................................................................................................ 40
Algoritmo 4-3. VERIFY. ............................................................................................................................. 42
Algoritmo 4-4. ENDPATHRESIDS. .............................................................................................................. 45
Algoritmo 4-5. DISTRIBUTERESIDS. ........................................................................................................... 47
Algoritmo 4-6. COMBINESITUATIONS. ....................................................................................................... 48
Algoritmo 4-7. SATISFACTION. .................................................................................................................. 49
Algoritmo 4-8. SATISFACTION_BASIC. ....................................................................................................... 51
Algoritmo 4-9. SATISFACTION_DEPEND. ................................................................................................... 59
Algoritmo 4-10. CONSULT. ........................................................................................................................ 66
xi
1 Introdução
1.1 Motivação
Storytelling Interativo é o nome dado às aplicações nas quais uma narrativa é
gerada e contada sob a influência da interação do usuário. Sistemas de Storytelling
Interativo encontram uso em aplicações educativas, de entretenimento e simulação; e o
seu desenvolvimento é tópico de pesquisa recente e atual em diversas disciplinas.
As métricas de avaliação da qualidade da experiência do usuário em sistema de
Storytelling Interativo são diversas (ROBERTS e ISBELL, 2008): além de quesitos
como a velocidade (o usuário não deve perceber pausas no desenrolar da ação) e
adaptabilidade (as histórias devem ser adequadas ao gosto particular do usuário); há o
quesito da rejogabilidade (a variabilidade, capacidade do sistema de oferecer
experiências diversas em múltiplas execuções). A coerência dos enredos gerados
também é apontada como uma característica desejável (KARLSSON et al., 2006), e
conciliar esses aspectos por vezes conflitantes é um dos desafios que esses sistemas
enfrentam.
No presente trabalho, considera-se o paradigma de Storytelling Interativo no
qual a narrativa é gerada através de planejamento automatizado. Essa técnica, oriunda
da área da inteligência artificial, é utilizada por sistema de Storytelling Interativo devido
à semelhança natural entre um plano (como uma sequência de ações) e um enredo
(como uma sequência de eventos) (PORTEOUS et al., 2010). Em especial, assume-se a
aplicação de planejamento não determinístico pelo suporte dessa técnica à geração de
histórias diversas, com possibilidades flexíveis de interação do usuário (promovendo a
rejogabilidade), mas ainda garantindo a coerência na narrativa (SILVA, 2010). Em
especial, o tratamento de alternativas não determinísticas nos eventos gera um grande
aumento da variabilidade por permitir que histórias se desenrolem de meios diversos
nas mesmas condições. O tratamento de não determinismo, no entanto, implica em uma
maior complexidade computacional no problema de planejamento.
1
A qualidade dramática dos enredos gerados por um sistema de Storytelling
Interativo é determinante para a boa experiência do usuário. Alguns dos aspectos
estéticos explorados na literatura são a representação da psicologia de personagens
(PIZZI, 2011) e a adequação da história a um arco de tensão desejado, à intenção
autoral ou a preferências do usuário (promovendo a adaptabilidade). No presente
trabalho, busca-se conciliar a expressão desses aspectos estéticos com os requisitos de
coerência e rejogabilidade.
Como uma exigência adicional, assume-se a necessidade de um ciclo de
geração-dramatização em paralelo, no qual o sistema dramatiza uma porção (capítulo)
da história enquanto as alternativas possíveis de continuação são geradas – garantindo a
velocidade do sistema. Esse modelo garante uma maior flexibilidade no tratamento da
interação do usuário, e é particularmente interessante para a aplicação de sistemas de
Storytelling Interativo para a TV Digital (CAMANHO, 2009) e em arquiteturas para
jogos multi-usuário (VIDAL e NAREYEK, 2011). Estabelece, porém, requisitos mais
estritos de eficiência no processo de geração: as alternativas de continuação devem estar
prontas quando a dramatização do capítulo atual se encerra. Na Figura 1.1, o ciclo é
representado conceitualmente.
Figura 1.1. Representação do ciclo contínuo de geração-dramatização, com os capítulos
dramatizados tendo sua continuação gerada em paralelo.
Na figura, tem-se que o eixo horizontal representa o tempo. O ponto o representa o
ponto no qual o processo de planejamento inicia a geração do enredo. Assim que um
primeiro capítulo é gerado, ele passa a ser dramatizado. O ponto i no tempo representa o
início da dramatização – a partir de então, a dramatização dos capítulos subsequentes
deve ser contínua. Isso implica em um limite estrito de tempo para que o planejamento
gere o capítulo seguinte. Nota-se, ainda, que sendo necessário considerar eventos não
determínistico, cada capítulo pode ter múltiplos finais diferentes. Isso implica na
necesside de gerar diversas continuações: uma para cada possível final do capítulo.
Assim, as restrições de tempo para a geração de capítulos na continuação é ainda maior
2
– de fato, divide-se o tempo disponível para a geração da continuação pelo número de
finais possíveis do capítulo anterior.
1.2 Definição do problema
Dado o objetivo de representar propriedades dramáticas e garantir requisitos
sobre suas variações nas histórias geradas, surge o problema da complexidade adicional
que a verificação desses requisitos adiciona ao processo de planejamento. A origem
dessa complexidade é demonstrada na Figura 1.2.
Figura 1.2. Comparação da consideração de um evento no processo de planejamento
quando não é (esq.) e quando é (dir.) necessário considerar a variação de propriedades
dramáticas. Os quadrados representam estados internos do evento, do inicial (mais à
esquerda) aos finais (mais à direita).
Na Figura 1.2 o elemento da esquerda representa um evento não determinístico
selecionado pelo planejamento para compor o enredo quando não é necessário
considerar a variação de propriedades contínuas. Nesse caso, o desenrolar interno do
evento é abstraído, sendo necessário considerar continuações a partir de cada final. Os
quadrados azuis representam estados internos do evento ‘sem propriedades’.
Ainda na mesma figura, o elemento da direita representa o mesmo evento não
determinístico, mas agora quando é necessário considerar a variação de propriedades
dramáticas internas ao evento. Os estados internos com o número 1 apresentam um
nível de tensão baixo; os estados com o número 2, nível médio; e o estado com o
número 3 apresenta um nível de tensão alto. Diferentes ‘caminhos’ internos para o
mesmo final geram diferentes variações da tensão da história: é possível, por exemplo,
atingir qualquer um dos três finais gerando alta tensão. Se o planejamento precisa
obrigar, por exemplo, que não há a possibilidade de um alto nível de tensão na história,
o evento não satisfaz a restrição. Para descobrir que o evento deve ser descartado, é
preciso analisá-lo internamente e considerar cada possível execução como uma
3
alternativa distinta.
Duas abordagens iniciais são possíveis para resolver esse problema: primeiro,
um processo de “geração e teste”. Nesse caso, o planejamento gera um capítulo
normalmente – sem considerar propriedades dramáticas - e posteriormente verifica se as
restrições em tempo contínuo são satisfeitas no capítulo gerado, aplicando um algoritmo
como o desenvolvido por (ARAÚJO, 2011). Se sim, o processo prossegue normalmente.
Se não, o capítulo é descartado e um capítulo alternativo deve ser gerado. O problema
que essa abordagem apresenta é ilustrado na Figura 1.3.
Figura 1.3. Abordagem de geração e teste, com etapa de verificação intercalada. Os
planos desperdiçados causam a demora excessiva na geração de um capítulo, quebrando
o ciclo de geração-dramatização em paralelo.
Nessa figura, o processo de planejamento gera um capítulo inicial sem
problemas (a verificação de restrições sobre propriedades dramáticas nesse capítulo
inicial é abstraída no exemplo). Ao gerar a sequência desse “Capítulo 1”, no entanto, o
planejamento enfrenta problemas: a primeira alternativa considerada não satisfaz as
restrições necessárias. Uma capítulo alternativo é gerado e verificado a tempo,
satisfazendo as restrições. Esse capítulo é então dramatizado como o “Capítulo 2”. A
geração da sequência, no entanto, enfrenta ainda mais problemas: duas alternativas são
geradas e nenhuma delas satisfaz as restrições impostas, de forma que a dramatização
encerra enquanto o planejamento ainda procura uma alternativa viável de continuação.
Essa quebra do ciclo é indesejada, por causar uma pausa artificial na experiência do
usuário.
A segunda abordagem inicial possível para resolver o problema é aplicar o
planejamento no nível interno dos eventos, encadeando os estados internos como
4
alternativas. O problema dessa abordagem é que o planejamento automatizado é um
processo naturalmente combinatório, e o aumento de alternativas causa um aumento
exponencial do tempo necessário para a geração do enredo. A Figura 1.4 ilustra o
problema.
Figura 1.4. Aumento no número de alternativas a serem consideradas causando uma
diferença exponencialmente maior no tempo necessário para o planejamento; e a
subsequente quebra no ciclo contínuo de geração/dramatização.
O exemplo recapitula o evento mostrado na Figura 1.2, onde há 3 estados finais,
e 10 execuções distintas. Na Figura 1.4, é representado o aumento do número de
alternativas causado quando se passa a considerar as execuções distintas como
alternativas de planejamento. Se for necessário encadear seis eventos com essas
características, o planejamento que não considera arcos dramáticos só precisa combinar
finais, ou seja 36 possibilidade (totalizando 729). O planejamento no nível interno ao
evento, no entanto, precisa considera 106, totalizando 1.000.000, possibilidades a gerar e
analisar. Em uma história mais longa, composta por 10 eventos, a diferença fica ainda
maior: de 310 (59.049) possibilidades, um número ainda realisticamente tratável, para
1010, um número exorbitante.
Dada a inviabilidade das alternativas inicialmente consideradas, o problema de
pesquisa do presente trabalho é: como prover mecanismos para a expressão e garantia
de requisitos sobre propriedades dramáticas que variam continuamente ao longo de
cada evento sem incorrer em custos computacionais que inviabilizem o ciclo de
geração-dramatização.
5
1.3 Proposta
Propõe-se um modelo para a representação de propriedades dramáticas em
narrativas geradas por sistemas de Storytelling Interativo. Almeja-se que essas
propriedades permitam a adequação da história às preferências do autor; ou às restrições
do gênero ou, ainda, impostas pela audiência. Adota-se a representação de propriedades
que variam continuamente ao longo dos eventos, já que aspectos estéticos como a
intensidade da trilha sonora, emoções dos personagens, e os níveis de tensão e violência
da trama são melhor representados dessa forma.
Dada a necessidade de manter o processo de geração de enredos em tempo hábil,
o modelo proposto define uma etapa de verificação offline para evitar carga
computacional adicional nesse processo. A pré-verificação considera exaustivamente
todas as possíveis restrições sobre propriedades dramáticas em relação a todos os
eventos de um gênero, gerando resultados que podem ser consultados pelo
planejamento em uma fração do tempo que seria necessário para realizar a verificação
online.
Representa-se as restrições sobre as propriedade dramáticas utilizando uma
lógica temporal estendida para Storytelling (ARAÚJO e CIARLINI, 2011). Dado que a
pré-verificação é realizada sem o conhecimento dos valores das propriedades – que
serão conhecidos apenas durante o planejamento - utiliza-se técnicas de programação
em lógica com restrições (constraint logic programming) (MARRIOT e STUCKEY,
1998) para realizar a execução abstrata dos eventos.
O modelo e os algoritmos desenvolvidos são aplicados como uma extensão a um
sistema de Storytelling Interativo existente. Apesar da implementação para essa
incorporação, os resultados são independentes desse sistema e podem ser reutilizados
tanto em outros sistemas de Storytelling como em aplicações de outros domínios nas
quais condições similares se apresentem – eventos que podem ser modelados como
autômatos não determinísticos e com propriedades que variam continuamente ao longo
de sua execução.
1.4 Hipótese
Se forem conhecidos de antemão:
•
A especificação dos eventos possíveis, e como esses modificam as
propriedades dramáticas; e
6
•
As restrições típicas do gênero, sobre as propriedades dramáticas;
Então, consegue-se mapear cada par (especificação abstrata de evento, restrição
dramática) às restrições que devem ser satisfeitas após o evento.
1.5 Estrutura
No capítulo 2, é apresentada a fundamentação teórica do trabalho. Apresenta-se
uma visão geral sobre o tema de storytelling e descreve-se as técnicas de geração de
narrativa, em especial a utilização de planejamento automatizado. Explora-se ainda a
questão da modelagem de arcos dramáticos e de te tempo contínuo em sistemas de
Storytelling Interativo. Além de tópicos específicos sobre storytelling, aborda-se alguns
dos temas relevantes para os modelos e algoritmos desenvolvidos nessa dissertação:
model checking; programação em lógica com restrições; e a lógica de tempo ramificado
CTL, detalhando a sua extensão para aplicação em tempo contínuo em domínios de
stortelling.
No Capítulo 3, apresenta-se o modelo de conteúdo, que define um gênero que
contém as propriedades dramáticas, as restrições típicas sobre elas e as definições dos
eventos que compõem esse gênero. Este capítulo também descreve de maneira geral o
modelo proposto de verificação e consulta. O capítulo 4 apresenta a implementação dos
algoritmos referentes a esse modelo de verificação e consulta, utilizando estruturas de
dados que refletem o modelo de conteúdo; e contendo exemplos do processo.
O capítulo 5 contém a discussão sobre os resultados obtidos, referente à expressão
de propriedades dramáticas e restrições típicas; e também aos custos computacionais
para a verificação e para a consulta de resultados. Por fim, o capítulo 6 contém as
conclusões do trabalho, recapitulando as contribuições da dissertação. Também contém
uma análise sobre os possíveis desenvolvimentos futuros do trabalho e sua aplicação em
domínios diversos.
7
2
Fundamentação Teórica
Neste capítulo são apresentados os tópicos relacionados à pesquisa. Explorase o tópico de Storytelling Interativo, dado o foco da solução para aplicação em
sistemas nesse contexto. Além disso, são explorados assuntos referentes às principais
técnicas utilizadas na modelagem e implementação dos algoritmos produzidos.
2.1 Storytelling Interativo
Storytelling Interativo é na qual uma narrativa é composta e contada sob a
influência da interação de um ou mais usuários. A geração e dramatização
computacional de histórias interativas têm sido objeto de estudo em diversas disciplinas,
com influências e inspirações advindas de áreas como a produção cinematográfica, a
interação humano-computador, o design de jogos e a inteligência artificial (SPIERLING,
2005). Sistemas de Storytelling Interativo têm sido desenvolvidos para aplicação em
educação, treinamento e simulação (SPIERLING et al., 2002; SILVA et al., 2011;
RIEDL e STERN, 2006); e principalmente entretenimento, seja ligado ao
desenvolvimento de jogos (HARTSOOK et al., 2011) ou em aplicações destinadas à
televisão interativa (CAMANHO et al., 2009).
De modo geral, as diversas abordagens de geração de enredo em sistemas de
Storytelling Interativo podem ser classificadas em um eixo, contrapondo aquelas
baseadas em personagens (character-based) àquelas baseadas na estrutura do enredo
(plot-based). Em abordagens do primeiro tipo, os personagens são modelados como
agentes autônomos e a história emerge da interação entre estes agentes (cooperantes ou
conflitantes). Nas abordagens do segundo tipo, o foco é a estrutura da trama e o enredo
é produzido pela combinação de eventos narrativos.
Abordagens character-based têm como origem os jogos eletrônicos com
geração de histórias emergentes (DÓRIA et al., 2008), e facilitam a interação direta. O
8
usuário pode interagir com a trama: tomando o controle de um dos personagens;
restringindo e guiando as ações de múltiplos personagens; e influenciando o ambiente
no qual a história se desenrola. É difícil, no entanto, garantir a coerência e interesse
dramáticos da trama, pois a livre interação de agentes pode não gerar um enredo
interessante. RIEDL e STERN (2006) classificam essa abordagem como “strong
autonomy” (autonomia forte).
Por outro lado, abordagens plot-based surgiram com base na constatação, a
partir de estudos de narratologia e linguística estruturalista, de que há padrões típicos
nos eventos de histórias de um mesmo gênero. Em seu trabalho seminal de 1928, Propp
(PROPP, 2003) identifica, por exemplo, os eventos comuns (e a ordem típica entre esses
eventos) em histórias de contos de fada.
Assim, a abordagem plot-based consiste na composição de histórias através da
combinação de eventos típicos; sendo chamada, na classificação de Riedl e Stern, de
“strong story” (história forte), pois oferece um maior controle sobre a coerência interna
da trama e facilita a geração de histórias interessantes. No entanto, essa abordagem
tende a limitar as possibilidades de interação, dado que existe um número finito de
eventos que podem ser combinados, e considerar os efeitos da interação do usuário pode
tornar a combinação de eventos um problema muito complexo.
Um exemplo de sistema de Storytelling Interativo prominente na literatura é o
sistema Façade, que aplica técnicas de Inteligência Artificial (em uma abordagem mista,
com elementos de plot e character-based) para “responder às influências do usuário
dadas interações em tempo de execução”, na “construção de uma performance
dramática”(MATEAS e STERN, 2005). Outro sistema que aplica uma abordagem mista
é o IN-TALE, utilizado para simulação e treinamento (RIEDL e STERN, 2006).
O sistema FatiMA é categorizado como character-based. Esse sistema aplica
uma abordagem de ‘composição e teste’; através de ‘ensaios’, onde o usuário define
uma cena a ser dramatizada (utilizando um módulo de composição apropriado) e ‘dirige’
o comportamento dos personagens-agentes, justificando as decisões tomadas por eles.
Dessa forma, o sistema pode usar essas decisões e justificativas como refêrencias
futuras; e com elas guiar o comportamento dos personagens-agentes em execuções
futuras (KRIEGEL et al.).
Como exemplo de sistema plot-based, há o DINAH. Nesse sistema, o autor
preenche uma base de dados com muitas partes básicas de narrativa (story clips); que
9
são então compostas, em tempo de execução, em uma narrativa completa por algoritmo
combinatório que leva em conta restrições de combinações entre esses story clips
(VENTURA e BROGAN, 2002).
Outros exemplos de sistemas de Storytelling Interativo, com aplicações em áreas
diversas, podem ser encontrados na literatura. ROBERTS e ISBELL (2008) realizaram
um survey, classificando sistemas de sistemas de Storytelling Interativo (e drama
managers) de acordo com as técnicas utilizadas, abordagem e métricas de qualidade de
experiência do usuário. MAGERKO (2007) também categoriza e compara sistemas de
narração interativa segundos suas capacidades como geradores, gerenciadores e
dramatizadores de histórias.
URSU et al. (2008) analisam sistema de Storytelling Interativo especificamente
em relação à narratividade em televisão interativa, constrastando sistemas que geram
narrativas baseadas em interação (foco em emergência, equivalente à “strong
autonomy”) àqueles que focam na exploração de uma história através de interação
mediada (foco em controle, equivalente a “strong story”). Em suas conclusões,
argumentam que sistemas do segundo tipo são mais apropriadas para o paradigma de
narrativas em TV interativa, e que experiências adquiridas na construção de sistemas de
Storytelling Interativo gerativos não são diretamente aplicáveis em implementações
nesse paradigma.
2.1.1 Planejamento em Storytelling
Uma das técnicas comumente utilizadas por sistemas de Storytelling Interativo
para a geração de enredos é o planejamento automatizado (SILVA et al., 2010; RIEDL
e YOUNG, 2004; PORTEOUS e CAVAZZA, 2009), tanto em abordagens character
based como plot based (CHARLES et al., 2003). O planejamento automatizado trata do
chamado planning problem, ou problema de planejamento: encontrar uma sequência de
ações para atingir um objetivo a partir de um estado inicial definido. Dado um domínio
de planejamento definido por uma linguagem L e uma coleção O de operadores, o
planning problem P é declarado na forma P = (Σ,s0,Sg), onde:
•
s0 é o estado inicial;
•
Sg é o conjunto (não-vazio) de estados objetivo ;
•
Σ é um sistema de transição de estados na forma (S,A,γ):
o S define o conjunto de estados possíveis;
10
o A é o conjunto de ações aplicáveis (de instanciação dos
operadores em O);
o γ é a função de transição parcial que mapeia ações e estados a
estados, na forma s’= γ (a,s) onde a ϵ A, e s,s’ ϵ S.
Uma solução para o problema de planejamento é dada como uma sequência de
ações (a0, a1, ..., an ); que gera a sequencia de estados (s0, s1, ..., sn+1) quando ai é
aplicada em si, gerando si+1. O último estado, sn+1, é o estado objetivo (i.e. , sn+1ϵ Sg).
No caso de abordagens character based, o planejamento pode ser utilizado para
dirigir personagens (no sentido teatral), ou seja: guiar seu comportamento (PIZZI, 2011).
Um exemplo é o Façade (MATEAS e STERN, 2005), que utiliza a linguagem de
planejamento reativo ABL para controlar agentes autônomos emotivos. O sistema INTALE também utiliza a linguagem ABL para gerar o comportamento de personagens
com objetivos individuais (RIEDL e STERN, 2006).
No caso de abordagens plot based, explora-se a semelhança natural entre um
enredo e um plano (PORTEOUS e CAVAZZA, 2009) para compor enredos como
sequências de eventos narrativos. Além disso, técnicas de planejamento podem ser
utilizadas para coordenar a interação do usuário com agentes virtuais (GILROY, 2012).
Diversas técnicas de planejamento são utilizadas em sistemas de Storytelling
Interativo para esses fins: planejamento de ordem parcial (RIEDL e YOUNG, 2004;
AYLETT et al., 2006), planejamento por heurística de busca (PIZZI et al, 2006), e
planejamento em rede hierárquica de tarefas (HTN) (SILVA et al, 2010). A aplicação
de planejamento não determinístico para gerar maior variabilidade em abordagens plot
based é proposta por (SILVA, 2010); possibilitando ainda o tratamento de tentativas
fracassadas gerando maior qualidade dramática. Planejamento temporal tem sido
recentemetne explorado nessa área para o controle da experiência e interação do usuário
(BENFORD e GIANNACHI, 2008), e para promover a sincronização de ações de
agentes virtuais (PORTEOUS et al., 2011).
O presente trabalhalho relaciona-se à aplicação de planejamento automatizado
em sistemas de Storytelling Interativo, pois busca permitir que uma tal aplicação possa
considerar informação temporal contínua sem prejuízo computacional. No entanto, os
algoritmos desenvolvidos para a pré-verificação de fórmulas não aplicam técnicas deste
tipo.
11
2.1.2 Arcos dramáticos
Aspectos estéticos podem ser impostos em uma narrativa pelo autor ou pelo
gênero. Contos de fada, por exemplo, normalmente exigem um final feliz; enquanto
histórias de aventura impõem que o nível de tensão deve atingir seu nível mais alto
imediatamente antes da resolução da trama. Esse conceito, a variação do impacto
emocional da estrutura da história sobre a audiência, é chamado de arco dramático e
tem origem em Aristóteles (BUTCHER, 2011), sendo objeto de estudo até a época
contemporânea na área da Narratologia (BRANIGAN, 1992).
Em relação a sistemas de Storytelling Interativo, o tratamento de arcos
dramáticos é de especial interesse para garantir a qualidade da narrativa, que por sua vez
é crucial para garantir uma boa experiência do usuário. É de importância, nesse sentido,
a distinção de E.M. Foster (apontada por (BRANIGAN, 1992)): embora “O rei morreu e
então a rainha morreu” e “Mary comeu uma maçã” não se qualifiquem como narrativas;
as versões alternativas “O rei morreu e então a rainha morreu de tristeza” e “Shirley era
boa e então foi levada a uma vida de crime” o fazem. Não há narrativa sem
complicações e resoluções, e essas são melhor modeladas como mudanças contínuas, e
não abruptas, ao longo da história.
Há diversas maneiras possiveis de representar e controlar arcos dramáticos em
sistemas de Storytelling Interativo. A produção de suspense, por exemplo, tem sido
objeto de estudo nas abordagens de (CHEONG, 2007) e (O’NEIL e RIEDL, 2011).
BARROS e MUSSE (2008) aplicam técnicas de planejamento com resolução de
conflitos para gerar narrativas que se adequam a um arco dramático - desenhado por um
autor como uma função em valor do tempo de dramatização – que representa o
conhecimento do protagonista em relação a um mistério estabelecido.
A abordagem de WARE e YOUNG (2010) é formalizar a variação, baseada em
conceitos de narratologia, dos níveis de conflito (tensão) entre os personagens da
história.
Já Zagalo et al. (2004) exploram a modelagem de “áreas” de emoção e
suspense no enredo. A relação entre essas áreas é controlada para gerar interesses no
usuário (curiosidade, surpresa e suspense, na terminologia dos autores. Também em
relação a arcos dramáticos considerando emoções, ARAÚJO e CIARLINI (2011)
modelam a variação das ‘emoções básicas’, segundo o modelo de PLUTCHIK (1962),
ao longo de eventos.
12
2.1.3 Tempo contínuo em Storytelling
Tempo é um elemento básico de histórias. Como afirma GERVAS (2009), o tipo
mais elementar de história envolve uma série de eventos contados em ordem
cronológica; enquanto histórias complexas formam “uma nuvem de eventos tomando
parte em um contínuo de tempo e espaço”.
Embora sistemas de Storytelling Interativo com enredos gerados como
sequências de eventos sejam capazes de apresentar diversidade e despertar interesse, há
algums problemas relacionados à essa representação implícita do tempo. Primeiramente,
como apontam PORTEOUS et al. (2011), a história (os acontecimentos no mundo da
narrativa) e o discurso (a representação desses acontecimentos) não compartilham
princípios dramáticos. O tempo explícito que o processo de geração de enredos
desconsidera é necessário para a dramatização em tempo real: é preciso posicionar
atores, controlar diálogos, enquadramento da câmera, intensidade da trilha sonora, entre
outros aspectos que dependem de uma representação explícita de tempo ao longo dos
eventos.
PORTEOUS et al. (2011) defendem que a aplicação de técnicas de tratamento
de tempo contínuo podem conferir maior poder de expressão a sistemas de Storytelling
Interativo. Assim, propõem o uso de planejamento temporal para considerar tempo
contínuo; buscando tanto coordenar aspectos de dramatização como aumentar o poder
gerativo do sistema.
Além de PORTEOUS et al., ARAÚJO (2011) também propõe que o tratamento
de tempo contínuo no nível da geração do enredo provê maior coerência entre a geração
e dramatização da história. A coordenação de aspectos visuais e de agentes virtuais, por
exemplo, pode ser então realizada com base em informação presente na história que foi
planejada.
Outro problema do tratamento implícito do tempo é a dificuldade de
representação de arcos dramáticos. Embora possam ser representados por valores
discretos associados aos eventos, descritos no próprio formalismo do planejamento, há
certas propriedades melhor representadas por variação contínua ao longo da
dramatização, como os níveis de suspense, as emoções dos personagens, os níveis de
violência; entre outros.
13
2.1.4 Logtell
O sistema Logtell é um sistema de geração semi-automatizada de histórias com
dramatização em ambiente virtual tridimensional, fruto de um projeto de pesquisa com
foco na produção de conteúdo para o sistema de televisão digital brasileiro (CIARLINI
et al., 2010). Com a característica de conciliar um alto nível de interatividade com
coerência lógica e variabilidade das histórias geradas (CAMANHO, 2009), o Logtell
atua com base em uma formalização lógica de contexto para planejar as possíveis
conseqüências e desenrolares da história (CIARLINI et al., 2008).
No Logtell, as histórias são dividas em capítulos. Como o sistema busca atender
requisitos do ambiente de televisão interativa, adota-se um processo de geração de
enredo em ciclo contínuo de paralelismo com a dramatização; de forma a não gerar
pausas artificiais na experiência dos usuários. Assim, enquanto um capítulo é
dramatizado, o processo de geração de enredos gera as alternativas de continuação
possíveis considerando as influências oriundas da interação dos usuários com o capítulo
que está sendo dramatizado.
O modelo de conteúdo proposto nesta dissertação é uma extensão compatível
com o utilizado pela versão atual do Logtell (CAMANHO et al., 2009), considerando
ainda a adoção de técnicas para o tratamento de eventos não determinísticos (SILVA,
2011). O modelo de conteúdo proposto permite a expressão da variação de propriedades
dramáticas ao longo dos eventos; e de restrições sobre essa variação, baseando-se na
lógica temporal CTL-estendida definida por ARAUJO (2011), descrita na seção 2.4.1.
O modelo de conteúdo proposto nesta dissertação é descrito no capítulo 3.
2.2 Verificação de Proriedades
Dado o objetivo de representar arcos dramáticos em histórias geradas por
sistemas de Storytelling Interativo, é necessário considerar a variação de propriedades
continuamente ao longo do tempo. Nesta seção, trata-se dos tópicos relacionados à
verificação de propriedades, com paralelos entre as técnicas descritas e sua utilização
em sistemas de Storytelling Interativo.
O modelo proposto opera verificando a satisfação de restrições sobre um evento
modelado como um autômato não determinístico. Dessa forma, o presente trabalho
relaciona-se intimamente ao tema de verificação de modelos em sistemas formais. Além
disso, como o processo é offline, e opera sem o conhecimento dos valores concretos das
14
propriedades, é necessário que a verificação seja abstrata. Assim, o trabalho também se
relaciona com técnicas de execução simbólica.
2.2.1 Model checking
Verificação de modelos (model checking) é uma técnica utilizada para
determinar se uma propriedade existe em um sistema especificado formalmente como
um sistema de transições – em geral, como um autômato finito ou uma estrutura de
Kripke (MCMILLIAN, 1993). As propriedades a serem verificadas sobre esse sistema
são expressas em lógica temporal, ou seja, em um formalismo que permite raciocinar
sobre a ordem dos eventos no tempo. Tradicionalmente, admite-se que uma lógica
temporal é uma extensão da lógica proposicional, com operadores que se referem ao
comportamento de um sistema ao longo do tempo. Isso deve-se ao fato de que, para que
a verificação possa ser rigorosa, propriedades do sistema (e restrições sobre essas
propriedades) devem ser expressas de forma precisa e não ambígua (CHRISTEL e
KATOEN, 2008).
Algoritmos de model checking exploram o espaço de estados determinado pela
especificação do sistema para determinar se ele satisfaz requisitos e obedece às
restrições lógicas. A exploração é sistemática e completa, no sentido de que todas as
possibilidades de desenvolvimento do sistema são consideradas. Um dos problemas
principais enfrentados por essas técnicas é a explosão do espaço de estados, o chamado
state-space explosion problem: “O tamanho da representação de sistemas de transição
cresce exponencialmente em vários compoentes, tais como o número de variáveis no
grafo de um programa ou o número de componentes em um sistema concorrente. Esse
problema é conhecido com o problema da explosão do espaço de estados” (CHRISTEL
e KATOEN, 2008, p.80, em tradução livre).
Apesar dos problemas relacionados à essa alta complexidade computacioanl,
model checking é uma técnica amplamente utilizada em diversos domínios. Além de
aplicações relacionadas ao planejamento automatizado, especialmente em domínios
parcialmente observáveis (DÓRIA et al., 2008), model checking é muito utilizado para
a verificação de propriedades em software (verificação formal) e hardware (simulação
simbólica), com diversas heurísticas especializadas para esses domínios, evitando
problemas de explosão combinatorial no espaço de estados.
A aplicação de lógicas temporais como um formalismo para descrever o
15
comportamento de sistemas é considerada um dos fatores mais importantes para o
sucesso de algoritmos de model checking (GRUMBER e VEITH, 2006). As
propriedades da lógica temporal aplicada determinam os tipos de propriedades
temporais que podem ser garantidas pelos algoritmos de verificação. Destacam-se, na
literatura, o Mu-calculus, uma classe de lógicas proposicionais baseadas em operadores
de ponto-fixo (KOZEN, 1983); as lógicas de tempo ramificado; e as lógicas temporais
lineares. Assim como lógicas de tempo ramificado podem ser consideradas extensões de
lógicas temporais lineares; o Mu-calculus é uma extensão das lógicas de tempo
ramificado.
Abordagens primordiais de model checking consideravam apenas sistemas de
transição discretos – isto é, com um número contável de estados. Mais recentemente,
foram desenvolvidas diversas aplicações de model checking sobre sistemas híbridos,
com característidas tanto discretas como contínuas. Um dos principais sistemas de
verificação de modelos sobre autômatos híbridos destacados na literatura é o HyTech
(ALUR et al., 1993).
Aplicações de algoritmos de model checking em SI são raras. DÓRIA et al.
(2008) utilizam planejamento baseado em verificação de modelos para a geração de
políticas de dramatização para eventos modelados como autômatos não determinísticos.
Já (ARAÚJO, 2011) apresenta um algoritmo de verificação de propriedades contínuas
sobre eventos modelados como autômatos híbridos.
Na secao 2.2.2, descreve-se sistemas de transição de estados utilizados por
sistemas de model checking; em especial os automatos híbridos não determinísticos
utilizados por ARAÚJO (2011), dada a sua semelhança ao modelo proposto. Na seção
2.2.3, descreve-se o conceito de execução simbólica, relacionado ao trabalho de
verificação abstrata de propriedades contínuas realizado no presente trabalho. Não são
discutidas em detalhe lógicas temporais aplicadas em algoritmos de model checking,
que são profusamente detalhadas na biblografia (BOUYER, 2009). A seção 2.4, no
entanto, descreve a lógica de tempo ramificado CTL e sua extensão, proposta por
ARAÚJO (2011) para aplicação no domínio de storytelling interativo; já que esta é
utilizada no modelo proposto.
2.2.2 Sistemas de transição de estados
Sistemas de transição de estados são utilizados para modelar formalmente o
16
funcionamento de sistemas reais. O comportamento e as características de um sistema
são implicitamente definidos a partir do conjunto de estados atingíveis pelas transições
determinadas. Um estado, nessa concepção, descreve quais são as propriedades do
sistema em um determinado instante de seu comportamento (MCMILLAN, 1993); e
uma transição leva o sistema de um estado a outro.
Há duas maneiras principais de representar um sistema desta maneira, para
facilitar a representação: abstraindo-se os estados (foco em transições); ou abstraindo-se
as transições (foco nos estados). Esses modos de representação são, em geral,
diretamente intercambiáveis. Há abordagens de representação mista apropriadas para
domínios específicos, embora estas adicionem complexidade extra na descrição do
sistema (SCHOREN, 2011). O modelo mais utilizado para abordagens baseadas em
estados (“labeled states”) é o de estruturas de Kripke. Já para abordagens baseadas em
transições, o modelo mais utilizado é o LTS (Labeled Transition Systems).
Aqui, apresenta-se o formalismo que define sistemas de transição de estados
com labeled transitions. Um sistema de transição de estados TS é definido pela tupla (S,
Act, T, s0,F, AP, L), na qual:
•
S é um conjunto de estados;
•
I é um conjunto de estados iniciais, subconjunto de S;
•
Act é um conjunto de ações;
•
T é uma função parcial que mapeia estados e ações a conjuntos de
estados: S × AP → 2S;
•
s0 é o estado inicial, um elemento de S;
•
F é um conjunto de estados finais, subconjunto de S;
•
AP é um conjunto de proposições atômicas, e ;
•
L : S → 2AP é a labeling function; que relaciona a cada estado s todas as
proposições atômicas p ∈ AP que são satisfeitas naquele estado.
Semanticamente, o sistema parte de um estado s0 ∈ I e se desenvolve de acordo
com a função de transições T. A partir de cada estado atual s, uma das transições que
parte de s e leva a s’ é selecionada não deterministicamente dentre os elementos de T(s).
Isto equivale a uma ação a ∈ Act ter sido executada no estado s, levando o estado do
sistema a tornar-se s’. As sequências de ações consideradas válidas são apenas aquelas
que terminam em um dos estados de F.
Os sistemas de transição correspondem a autômatos determinísticos, onde a
17
função de transição T leva cada par <estado,ação> a no máximo um estado, ou não
determinísticos que não têm esta limitação. Neste trabalho, utiliza-se autômatos não
determinísticos e assume-se ainda que nenhuma transição parte de um estado final.
Além disso, o modelo proposto nesta dissertação considera a variação contínua de
propriedades ao longo da execução dos eventos, o que torna o sistema híbrido - isto é,
com a representação de comportamento tanto discreto como contínuo. Um meio de
representação de sistemas híbridos difundido na literatura são os autômatos híbridos. O
modelo apresentado aqui, no entanto, adota uma representação particular descrita no
capítulo 3.
2.2.3 Execução Simbólica
O termo execução simbólica refere-se principalmente à verificação de
programas (KING, 1976); um tipo específico de verificação de modelos no qual um
artefato de software é analisado em busca de informações sobre suas condições, limites
e possíveis problemas de execução. Este conceito relaciona-se intimamente à simulação
simbólica; que refere-se à verificação de propriedades em hardware e sistemas
concretos. No que diz respeito ao presente trabalho, a característica de algoritmos de
execução simbólica de principal interesse é a consideração abstrata dos dados de
entrada; já que o modelo proposto assume que é necessário verificar as fórmulas
temporais que descrevem os arcos dramáticos em tempo offline. Portanto, os valores
concretos das propriedades dramáticas – que variam continuamente ao longo dos
eventos – são desconhecidos em tempo de verificação.
Em seu artigo seminal, KING (1976) define os conceitos de teste, prova formal
e execução simbólica de um programa. Define o teste de um programa como uma
sequência de inputs concretos e a verificação dos resultados. Portanto, embora o sucesso
no teste de um programa garanta que ele opera corretamente em relação aos dados
exemplares fornecidos como input, ele não não garante a corretude em relação aos
demais possíveis valores para os dados de entrada.
Define, no outro extremo do espectro, a prova formal. A prova de um programa
provê informação sobre todos os possíveis dados de entrada, mas depende de uma
especificação detalhada (e completamente correta) do comportamento do programa;
além de ser necessário construir a prova lógica de que o programa e suas especificações
são consistentes. KING (1976) nota que a confiança neste método “depende do cuidado
18
empregado na criação da especificação e na construção dos passos da prova”; e que é
ainda “necessário considerar questões práticas, dependentes de máquina, como overflow,
representação numérica, etc.”.
Por fim, define a execução simbólica de um programa como o meio termo
aplicável entre essas duas abordagens extremas. Ao invés de executar o programa em
relação a um conjunto de dados de entrada; ou realizar o trabalho de prova formal de
funcionamento; executa-se simbolicamente o programa. Ou seja, o programa é
executado em relação a conjuntos de classes de dados de entrada.
Embora essa abordagem seja particularmente aplicável a domínios discretos
devido ao problema de explosão do espaço de estados; há, na literatura, diversas
aplicações e heurísticas para a sua aplicação em domínios contínuos. No entanto,
mesmo técnicas mais radicais e especializadas a domínios específicos não proprocionam
escalabilidade suficiente para o tratamento de valores contínuos a partir de certa escala
de dados (EMERSON, 2009).
Neste trabalho, explora-se a execução simbólica considerando a dramatização de
eventos não determinísticos em storytelling interativo como um ‘programa’; buscando
gerar todos os possíveis ‘casos de teste’. Busca-se especialmente aproveitar a nãoexploração de caminhos inviáveis no espaço de estados; e evitar caminhos infinitos
gerados por ciclos de execução, utilizando conhecimento específico do domínio.
No modelo proposto, utiliza-se técnicas de programação em lógica com
restrições (constraint logic programming) para realizar uma execução simbólica de cada
evento na qual todos os possíveis valores de entrada para as propriedades dramáticas
são classificados em relação à fórmula residual que geram para cada estado final do
evento. A seção 2.3 trata do tópico de constraint logic programming em detalhe. A
solução proposta é inovadora na aplicação de técnicas de verificação abstrata no
domínio de storytelling interativo; não constando na biblografia especializada outras
iniciativas similares.
2.3 Contraint Logic Programming
Constraint programming é o nome dado ao conjunto de técnicas utilizadas para
raciocinar programaticamente sobre relações entre entidades. Ao contrário do
paradigma de programação imperativo, no qual é necessário tornar as relações entre
objetos explícitas, linguagens de contraint programming permitem que o programador
19
declare relações entre objetos. A linguagem então se encarrega de garantir que as
relações definidas (as constraints) são mantidas ao longo do processamento
(MARRIOT e STUCKEY, 1998).
Estas linguagens implementam a solução do problema de satisfação de
constraints (constraint solving problem). Esse problema é definido como consistindo de
um conjunto de variáveis; um domínio não-vazio para cada um das variáveis; e um
conjunto de constraints restringindo os valores possíveis dessas variáveis, considerando
dependências de uma variável em relação a outras (YUAN et al., 1999). A satisfação de
constraints é o processo de encontrar uma atribuição para todas as variáveis que
simultaneamente satisfaz todas as constraints; ou determinar que tal atribuição é
impossível.
Diversas linguagem de programação implementam esta técnica; algumas
especilizadas em relação ao domínio das variáveis consideradas. Nesta dissertação,
foca-se no formalismo CLP (constraint logic programming), que combina as
características de constraint solving com programação lógica. Ferramentas de CLP são
apropriadas para o tratamento de constraints de diversos tipos, incluindo restrições
lineares, não-lineares; de lógica temporal; em domínios reais, finitos e booleanos.
A aplicação de ferramentas de CLP provê diversas vantagens. Uma delas é a
facilidade da representação de certas regularidades e dependências do mundo real como
restrições computacionais. No planejamento de sistemas elétricos, por exemplo, é muito
mais natural determinar que ‘a resistência em um circuito obedece à lei de Ohm (R =
V/I : a resistência R é igual ao potencial V divido pela intensidade da corrente I )’ do
que explicitar essa relação para cada objeto, em relação a valores concretos de potencial
e intensidada da corrente elétrica.
É graças à facilidade na representação de restrições como essa que técnicas de
CLP são aplicadas em problemas de diversas áreas do conhecimento. Discute-se, no
entanto, a idéia de que a aplicação mais importante de CLP é em problemas
combinatórios; pois esses problemas são difícies de ser modelados de outra forma, e
apresentam um espaço de busca exponencial. Nesse caso, a aplicação de CLP pode
podar o espaço de busca, tornando mais viável encontrar soluções em tempo aceitável.
Nesta dissertação, aplica-se técnicas de CLP em um domínio de números reais.
Limita-se a variação das propriedades tratadas à expressões lineares dado que
implementações de CLP (que estendem linguagens de programação em lógica) são
20
incapazes de lidar com expressões de mais alta ordem em tempo razoável; e por
considerarmos que esse tipo de variação provê poder expressivo suficiente para a
aplicação no contexto de storytelling interativo.
Há muitas aplicações de técnicas de CLP em relação a lógicas temporais,
incluindo CTL, bem como na verificação de propriedades em autômatos e sistemas
híbridos. Em relação a storytelling interativo, no entanto, apenas ARAÚJO (2011)
aplica técnicas de CLP para a verificação de propriedades temporais em histórias. Nossa
aplicação difere-se da de ARAÚJO (2011) pois, segundo nosso modelo proposto, a
verificação de propriedades utilizando CLP é realizada em tempo offline de
planejamento; sem os valores das variáveis e, portanto, de forma abstrata –
considerando todos os possíveis valores de entrada em paralelo. Mais detalhes sobre o
processo de verificação e o modelo proposto são dados no capítulo 3.
2.4 CTL
A representação do tempo é um fator crucial em diversos campos do
conhecimento, das ciências naturais à ciência da computação, retórica, lógica, ética até a
literatura (ØHRSTRØM e HASLE, 1995). A representação formal do tempo, como uma
abstração matemática e lógica, é muito necessária, em especial, em aplicações
computacionais que consideram a passagem do tempo. Algoritmos de model checking
(seção 2.2.1) e execução simbólica utilizam-se de formalizações lógicas do tempo que,
tradicionalmente, são extensões da lógica de primeira ordem.
Uma destas formalizações é computation tree logic (CTL); uma lógica temporal
proposta por (CLARKE e EMERSON, 1981) para a representação e raciocínio sobre
propriedades em sistemas computacionais em tempo ramificado. Isto é, a lógica CTL
permite expressar fatos sobre a evolução de um sistema no tempo, considerando
diversas ‘linhas do tempo’ como possibilidades de desdobramento (EMERSON, 1995).
Essa lógica permite expressar, por exemplo, que uma certa propriedade não é
válida no presente, mas que pode se tornar válida no futuro; ou ainda, que uma certa
propriedade é válida no presente e sempre será no futuro. A lógica CTL estende a lógica
proposicional com operadores de quantificação de caminho e de estado (CLARKE e
EMERSON, 1986) e tem sua semântica definida em relação a um sistema de transição
de estados – i.e. considera um tempo discretizado, no qual seus operadores temporais
discorrem sobre ‘estados futuros’ do sistema (e não instantes absolutos de tempo). No
21
presente trabalho, utiliza-se uma extenção da lógica CTL para a aplicação no domínio
de storytelling interativo. Essa lógica CTL-estendida considera a variação de
propriedades em tempo contínuo, e é definida na seção a seguir.
2.4.1 CTL-estendida
Conforme descrito anteriormente, CTL é uma lógica temporal que permite
raciocinar sobre a ordem dos eventos no tempo; e considera diferentes desenrolares de
um sistema a partir de um certo estado. No entanto, como visto, na definição da lógica
CTL o tempo é considerado apenas em relação ao estados, implicitamente – não há
valoração explícita do tempo.
Para a aplicação de técnicas de verificação de modelos (especificamente, de
execução simbólica) no domínio de storytelling interativo, é interessante tratar de tempo
contínuo. Para tanto, ARAÚJO (2011) define uma extensão da lógica CTL para o
tratamento de tempo contínuo ramificado, na qual uma fórmula bem formada é definida
recursivamente pela seguinte gramática (adaptada de (ARAÚJO, 2011)):
α ,β → aritm_expr | AF α | AG α | EF α | EG α | A α U β
E α U | A end α | E end α |α ∧β |α ∨ β |α →β |¬α | true | false
Na qual aritm_expr é uma expressão aritmética (uma equação ou inequação) na
qual os termos são propriedades que variam ao longo da história ou valores numéricos;
α e β são fórmulas bem formadas; e a semântica dos conectivos lógicos ∧, ∨, ¬, e → é
definida da maneira usual. Fórmulas na lógica CTL-estendida aplicam quantificadores
de caminho (A e E) combinados com operadores de estado (F, G, U, e end) aos pares,
segundo a seguinte semântica, equivalente à da lógica CTL:
•
Quantificador de camminho A significa todos os caminhos futuros;
•
Quantificador de caminho E significa pelo menos um caminho futuro;
•
Operador de estado F significa válido em um instante futuro;
•
Operador de estado G significa válido em todos os instantes futuros;
•
Operador de estado U significa que um fato antecessor é válido até que
seja válido um fato sucessor.
•
Operador de estado end significa válido no último instante.
Nota-se, no entanto, que na lógica CTL-estendida os operadores de estado
referem-se a instantes de tempo, já que a lógica trata de tempo contínuo, e não apenas
22
estados futuros de um sistema de transição de estados.
Além disso, a lógica CTL-estendida não possui o operador X, que na lógica
CTL define válido no próximo estado. Isto deve-se ao fato de, no tratamento de tempo
contínuo, não é possível falar de um ‘próximo estado’, já que o número de instantes em
qualquer intervalo é infinito.
Por fim, a lógica CTL-estendida possui ainda o operador de estado end, que
inexiste na lógica CTL. Isto deve-se ao fato de que, no domínio de storytelling
interativo, trata-se de um tempo com final (o final da história ou capítulo). Portanto, é
necessário um operador para descrever este momento específico. É típico de histórias
possuir características definidas pelo seu final (p.ex. ‘todos os contos de fadas têm final
feliz’).
23
3
Modelo
Neste capítulo é apresentado o modelo de conteúdo proposto. Este modelo
considera a existência de dados relativos ao nível de planejamento (geração dos
enredos), interação e dramatização (representação da história); baseando-se num
formalismo já aplicado em um sistema de Storytelling Interativo. O foco deste trabalho,
no que diz respeito ao modelo de conteúdo, é a representação das propriedades
dramáticas e das restrições sobre elas a serem verificadas nos eventos.
Além do modelo de conteúdo, este capítulo descreve o modelo proposto de
verificação das restrições sobre propriedades dramáticas. A consulta de resultados pelo
planejamento também é abordada. Os algoritmos referentes à etapa de verificação e à
consulta utilizam estruturas de dados que refletem o modelo de conteúdo e são descritos
em detalhe no próximo capítulo.
3.1 Modelo de conteúdo
O modelo proposto assume a aplicação num sistema de Storytelling Interativo
independente de contexto, i.e., capaz de gerar enredos pertencentes a múltiplos gêneros
dramáticos. Para tanto, baseamo-nos no formalismo desenvolvido por (CIARLINI et al.,
2010), aplicado ao sistema Logtell (seção 2.1.4). Neste formalismo, um gênero é um
repertório de enredos possíveis – sua definição permite gerar todos os enredos daquele
gênero, bem como identificar se um enredo em particular pertence a ele.
24
Figura 3.1. Modelo de conteúdo representando os conjuntos de Eventos, de Fórmulas
típicas e Propriedades dramáticas em cada instância de Gênero.
Para a representação de propriedades dramáticas, o modelo é definido da
seguinte forma, conforme ilustrado na Figura 3.1. Cada instância de gênero encerra um
conjunto de Eventos diretamente dramatizáveis; um conjunto de Fórmulas típicas,
representando restrições sobre propriedades dramáticas (na lógica temporal CTLestendida descrita na seção 2.4.1); e o conjunto de Propriedades dramáticas que os
eventos desse gênero consideram (sobre as quais as fórmulas típicas versam). As seções
seguintes descrevem em detalhes cada um destes conjuntos.
3.1.1 Propriedades dramáticas
As propriedades dramáticas representam atributos estéticos relevantes para as
histórias pertencentes ao gênero. A variação contínua dessas propriedades provê
informação para que a dramatização expresse esses aspectos com maior fidelidade. O
processo de composição de enredos leva em consideração restrições sobre essas
propriedades para gerar apenas histórias que satisfaçam os desejos do autor, as
necessidades e preferências da audiência, ou requisitos próprios do gênero.
O processo de verificação desenvolvido nesta dissertação não é dependente do
domínio ao qual as propriedades contínuas pertencem. Diversos aspectos estéticos
relevantes para o storytelling interativo podem ser representados. ARAÚJO (2011)
utiliza o modelo descrito em (RODRIGUES, 2008), baseado em (PLUTCHIK, 1962),
para representar as emoções evocadas ao longo da história. No exemplo da Figura 3.1,
25
utiliza-se essa representação para definir Joy e Fear como os níveis de felicidade e
temor, respectivamente, despertados pela narrativa. Nesse modelo, as propriedades
assumem valores não-negativos com valor inicial (no começo do primeiro evento)
atribuído pelo gênero.
Além da representação de atributos da narrativa, seria possível modelar e
representar as emoções pessoais dos personagens ao longo dos eventos; ou ainda
atributos práticos como a intensidade desejada da trilha sonora, atributos de iluminação
das cenas, etc. Nesta dissertação não avalia-se qualitativamente os possíveis modelos e
domínios das propriedades dramáticas. Assume-se apenas que representam qualidades
estéticas da narrativa sobre as quais certas restrições devem ser obrigadas.
3.1.2 Fórmulas típicas em CTL-estendida
Representa-se as restrições sobre as propriedades dramáticas através de fórmulas
na lógica CTL-estendida apresentada na seção 2.4.1. Assim como em relação às
propriedades dramáticas, também não avalia-se as restrições típicas sob a ótica da
narratologia ou cinematografia. Assume-se apenas que restrições sobre as propriedades
dramáticas existem como definição prévia, para que seja possível realizar a préverificação.
Na lógica CTL-estendida as fórmulas representam algo que deve valer a partir
do momento em que a fórmula é afirmada. As fórmulas que pertencem ao conjunto de
fórmulas típicas de um gênero não representam restrições que devem valer apenas a
partir do ponto inicial da história; mas sim todas as restrições que podem ser
estabelecidas para valer em uma parte da história – tipicamente, um capítulo.
3.1.3 Eventos
No formalismo original no qual o modelo proposto é baseado, os eventos são
descritos como operadores parametrizáveis de planejamento, com uma assinatura
única. Baseando-se em (DÓRIA et al., 2008), adota-se a representação dos eventos
dramatizáveis como autômatos não-determinísticos. Não é adotado, porém, o controle
do tempo de dramatização a partir de políticas pré-geradas por um processo de model
checking.
No modelo proposto, o autor define o tempo máximo e mínimo de
dramatização; e as transições entre os estados internos de um evento são compostas
por micro-ações diretamente dramatizáveis e com tempo definido; condicionadas por
26
restrições sobre propriedades de contexto. Propriedades de contexto são referentes ao
nível do operador de planejamento, e as restrições sobre elas são dadas como
expressões lógicas. A Figura 3.2 mostra a modelagem do evento dado pelo operador
try_to_kidnap(VILLAIN,VICTIM), que descreve o evento no qual há a tentativa de
rapto de uma vítima por um vilão.
Figura 3.2. Autômato não determinístico associado ao evento Try to Kidnap.
A Figura 3.2 mostra um exemplo simples de um autômato representando o
evento Try to Kidnap. Cabe notar que o nível de detalhe e sofisticação dos autômatos
em uma aplicação real pode ser muito maior, dependendo apenas do esforço autoral.
Para o fim de demonstrar os algoritmos desenvolvidos nesse trabalho, a simplicidade
do exemplo apresentado é suficiente. No autômato da Figura 3.2:
•
O estado inicial s0 representa Vilão espreitando a vítima;
•
Os estados finais s1 e s2 representam, respectivamente, Vilão foragido e
Vítima raptada;
•
Os hexágonos representam as micro-ações que compõem as transições:
o A transição que leva de s0 para s0 representa o vilão ficando à
espreita. A condição a é true, representando que não há restrição
para que a transição aconteça. É composta pelas micro-ações:
Esperar, com duração de dramatização definida em 2
segundos; e
Observar, 4 segundos.
o A transição que leva de s0 para s1 representa o vilão atacando a
vítima, mas fugindo sem sucesso. Ambas as condições b e b1
27
também são true. A condição b2 é dada pela expressão lógica
“at(VICTIM,VICTIM_PLACE),
protection(VICTIM_PLACE,PROTLVL), PROTLVL > 50”, que
determina que essa transição só pode acontecer caso haja algum
tipo de proteção da vítima no local. Composta pelas micro-ações:
Ir, 1 segundo;
Esperar, 2 segundos; e
Ir, 1 segundo.
o A transição que leva de s0 para s2 representa o vilão atacando a
vítima e tendo sucesso no rapto. Composta pelas micro-ações:
Ir, 1 segundo;
Esperar, 2 segundos;
Bater, 4 segundos; e
Pegar, 2 segundos.
A variação das propriedades dramáticas ao longo do evento é representada nos
estados. A cada estado, é associada uma expressão linear sobre os valores das
propriedades no estado inicial para cada propriedade. A Figura 3.3 mostra a variação
das propridades dramáticas no mesmo autômato do evento Try to Kidnap. Limita-se a
variação de propriedades dramáticas a expressões lineares para evitar os custos
computacionais excessivos no algoritmo de verificação, que aplicam técnicas de
programação em lógica com restrições que não lidam com expressões de mais alta
ordem em tempo razoável (MARRIOT e STUCKEY, 1998).
28
S2
S0
S1
Figura 3.3. Variação linear das propriedades dramáticas associada aos estados do
autômato Try to Kidnap.
No autômato representado na Figura 3.3 a variável X representa a propriedade
dramática fear e Y representa a propriedade joy. Os valores de joy nos estados s0, s1 e
s2, portanto, são representados respectivamente por X0, X1 e X2. De forma similar, os
valores da propriedade fear são dados por Y0, Y1 e Y2. No estado inicial, os valores são
os próprios iniciais. No estado s2 – quando o vilão tem sucesso e rapta a vítima – a
propriedade fear aumenta, significando que aumenta o nível de medo na história. A
propriedade joy, nesse estado, sofre um decréscimo, representando que a felicidade
diminuiu. Já no estado s1 – quando o vilão falha e é obrigado a fugir, deixando a vítima
em segurança – o medo da história aumenta marginalmente devido à tentativa de rapto.
Nota-se que os valores das propriedades em um certo momento podem depender dos
valores iniciais de outras propriedades, se o autor julgar que há razão semântica para tal:
o nível de felicidade da história, no caso do estado s2 do exemplo corrente, aumenta
proporcionalmente ao medo inicial no evento, dada a resolução da tensão dramática.
Tradicionalmente, sistemas de transição de estados para problemas de
verificação de modelos abstraem as ações, ou os estados. Isto é comum para evitar
definições e conceitos redundantes. Nossa abordagem mista é apropriada, no entanto,
para sistemas de Storytelling Interativo, pois associar informação tanto aos estados
como às transicoes é útil para a expressão de conteúdo autoral. De qualquer forma, as
29
modelagens são intercambiáveis e no modelo de verificação adota-se uma visão
centrada nas ações (abstraindo a existência de estados).
3.2 Modelo de verificação e consulta
O modelo proposto assume que são conhecidos de antemão a especificação
abstrata dos eventos possíveis (e como esses modificam as propriedades dramáticas); e
também as restrições típicas sobre essas propriedades que podem ser exigidas pelo
gênero, pelo autor ou pela audiência. Assim, o processo de verificação pode ser
realizado de forma offline, isto é, em tempo prévio e sobre as estruturas de dados
abstratas.
No momento da verificação, não se conhecem os valores para as propriedades
dramáticas ou de contexto (referentes ao estado do mundo que é o domínio do
planejamento). Semanticamente, o processo de verificação busca associar a cada
possível instância de evento do gênero, em cada possível estado do mundo, uma lista de
possíveis satisfações para cada restrição típica.
A consulta, por sua vez, é realizada sobre os resultados da verificação, em tempo
de planejamento – conhecendo-se os valores das propriedades dramáticas no momento
inicial do evento. Busca-se permitir que o planejamento, ao encadear eventos, possa
realizar consultas da forma geral: “Dado o estado atual do mundo S, o que é necessário
para que α valha a partir do evento Ev?”; e que obtenha resultados na forma “É
necessário que β1 valha no evento que sucede Ev acabando no final sf1; e que β2 valha
no evento que sucede Ev acabando no final sf2”.
Nesse exemplo, α é uma fórmula, Ev é um evento, sfi é um estado final de Ev, e
βi é uma fórmula, dita fórmula residual da verificação, que precisa ser verificada a partir
de um estado final. Cada fórmula residual βi pode ser true significando que não há
restrição a ser garantida, ou false, se não há maneira de α ser satisfeita em Ev acabando
naquele estado. Além disso, βi pode ser uma conjunção ou disjunção de fórmulas CTLestendidas.
São dados alguns exemplos semânticos na Tabela 1. Em todos os exemplos,
considera-se o estado atual do mundo S no qual a história que já está triste (no momento
da consulta) e que o evento Ev considerado é o Try to Kidnap. Relembra-se o autômato
do evento definido na Figura 3.2, e que os estados finais s1 e s2 representam,
respectivamente, Vilão foragido e Vítima raptada.
30
Restrição
α
Expressão de
Significado
resultado
“Há algum momento
triste?”
EF{joy<30}
(S1,true) ou (S2, true)
“Há a possibilidade da
história ser sempre
triste?”
EG{joy<30}
(S1,EG{joy<30}) ou
(S2,EG{joy<30})
“Todas as histórias
possíveis são sempre
tristes?”
AG{joy<30}
(S1, AG{joy<30}) e
(S2, AG{joy<30})
“Todas as histórias
possíveis são muito
tristes?”
AG{joy<10}
(S1,false) e
(S2, AG{joy<10})
“Sim, isso é
garantido pelo
estado do mundo.”
“Sim, desde que haja
a possibilidade da
história continuar
sempre triste, na
sequência a partir de
um dos finais.”
“Sim, desde que a
sequência a partir de
ambos os finais seja
sempre triste.”
“Não, pois essa
condição não vale
em uma das histórias
possíveis”
Tabela 1. Exemplos semânticos de consulta.
O modelo assume que a fórmula α é dada sob uma gramática restrita: contém
apenas um quantificador mais geral. A razão para tal é que isso simplifica
consideravelmente o algoritmo de verificação de fórmulas em eventos abstratos, já que
é possível tratar fórmulas aninhadas em chamadas puramente recursivas; e que assumese que as conjunções e disjunções de fórmulas podem ser tratadas sem prejuízo de custo
computacional excessivo no nível do planejamento.
O modelo considera que as restrições sobre propriedades de contexto invalidam
transições. Se uma restrição de contexto não é satisfeita, considera-se que aquela
transição não pode ser executada e, portanto, as histórias que dependem da sua
execução não são consideradas como “histórias possíveis”.
Como a verificação é offline e esse estado do mundo é desconhecido, essas
restrições também são coletadas abstratamente, sendo associadas aos resultados.
Expande-se na Tabela 2 um dos exemplos anteriores, demonstrando que cada expressão
de um resultado é associado a um conjunto de restrições sobre propriedades de contexto,
tornando-se um termo (sfi, rX, βi).
31
Expressão de
Restrição
resultado
α
Significado
condicional
“Há algum
momento
triste?”
EF{joy<30}
(S1,rA,true) ou
(S2,rB true)
“Sim, isso é garantido pelo
estado do mundo.”
“Há a
possibilidade da
história ser
sempre triste?”
EG{joy<30}
(S1,rC,EG{joy<30})
ou
(S2,rD,EG{joy<30})
“Sim, desde que haja a
possibilidade
da
história
continuar sempre triste, na
sequência a partir de um dos
finais atingíveis.”
“Todas as
histórias
possíveis são
sempre tristes?”
AG{joy<30}
(S1,rE, AG{joy<30})
e
(S2,rF, AG{joy<30})
“Sim, desde que a sequência a
partir de todos os finais
atingíveis seja sempre triste.”
(S1,rG,false) e
(S2,rH,AG{joy<10})
“Não, se a condição não vale em
uma das histórias possíveis;
caso, contrário, apenas se todas
as histórias possíveis a partir do
final atingível forem sempre
muito tristes.”
“Todas as
histórias
possíveis são
muito tristes?”
AG{joy<10}
Tabela 2. Exemplo resultado condicionados à restrições sobre propriedades de contexto.
Na Tabela 2, os termos rA, rB, ..., rH representam os conjuntos de restrições sobre
propriedades dramáticas coletados. Cada um desses conjuntos determina se é possível
atingir o final correspondente na tripla, e se é necessário verificar a fórmula residual
respectiva.
No momento da consulta, tenta-se validar cada um desses conjuntos no estado
corrente do mundo. Se o conjunto não é validado, o caminho no evento que leva até o
final associado ao conjunto não é possível, e portanto não é necessário considerar a
fórmula residual associada àquele final. Efetivamente, quando um conjunto rX não é
validado, o termo da expressão do resultado ao qual ele pertence é eliminado. Se
nenhum dos termos for satisfeito, nenhum dos finais do evento é atingível nesse
contexto. O processo de consulta trata estes casos de forma especializada, conforme
descrito na seção 4.4.
Observa-se, na Tabela 2, em destaque em negrito, as mudanças semânticas nos
significados desses resultados em relação à Tabela 1:
•
Na segunda restrição:
o se rC não for validada, é necessário verificar apenas EG {joy<30}
a partir do final S2;
32
o se rD não for validada, é necessário verificar apenas EG {joy<30}
a partir do final S1;
o se tanto rC como rD forem validadas, é necessário verificar EG
{joy<30} a partir do final S1; ou EG {joy<30} a partir do final S2.
•
Na terceira restrição:
o se rE não for validada, é necessário verificar apenas AG {joy<30}
a partir do final S2;
o se rF não for validada, é necessário verificar apenas AG {joy<30}
a partir do final S1;
o se tanto rE como rF forem validadas, é necessário verificar tanto
AG {joy<30} a partir do final S1; como AG {joy<30} a partir do
final S2.
•
Na quarta restrição:
o se rG não for validada, é necessário verificar apenas AG {joy<10}
a partir do final S2;
o se rH não for validada, a restrição não é satisfeita nesse evento;
o se tanto rG como rH forem validadas, a restrição não é satisfeita
nesse evento.
Mais formalmente, o objetivo do processo de verificação é mapear cada dupla
(Ev, α) a um conjunto de resultados, doravante denominado R:
•
Ev é a especificação abstrata de um evento, associada tanto ao operador
de planejamento como ao autômato não determinístico de controle de
dramatização para esse evento;
•
α é uma fórmula CTL-estendida com apenas um quantificador mais geral,
representando uma restrição típica sobre propriedades dramáticas neste
gênero, ou gerada a partir do resultado de uma outra verificação neste
gênero;
Cada elemento em R é um resultado. Um resultado é composto por uma
restrição e uma expressão. O resultado é dado pela dupla (CtrDram, ConditionalResid):
•
CtrDram é a restrição do resultado: um conjunto de restrições sobre
propriedades dramáticas, que mapeia diversos estados do mundo para a
expressão residual ConditionalResid. Estas restrições referem-se aos
33
valores das propriedades dramáticas no momento inicial do evento Ev;
•
ConditionalResid é a expressão do resultado, dada como uma conjunção
ou disjunção de triplas (Sf,RCtx,ResidFormula):
o Sf é um estado final do evento Ev;
o RCtx é um conjunto de restrições sobre propriedades de contexto
necessárias para que esse final seja atingível quando é necessário
verificar ResidFormula a partir de Sf;
o ResidFormula é uma formula CTL-Estendida no mesmo formato
de α; representando uma possível restrição sobre propriedades
dramáticas que deve valer no evento que segue Ev a partir de Sf.
Relembra-se que a variação das propriedades dramáticas é definida em
autômatos de perspectiva mista (ações e estados). Para simplificar o processo de
verificação, é gerada para cada evento uma árvore de execução a partir de seu autômato
e da assinatura de seu operador lógico. Essa estrutura de dados apresenta duas vantagens
principais:
•
finita: valendo-se da informação dos tempos necessários para cada
transição e do tempo máximo de execução do autômato, a árvore gerada
é finita. Assim, evita-se um dos problemas relacionados à verificação de
propriedades em sistemas de transição de estados – a verificação infinita.
•
centrada em ações: todas as informações da árvore de execução
representam as ações internas que tomam parte no evento. As variações
das propriedades dramáticas, as restrições sobre propriedades de
contexto, etc. são todas dadas em relação às sequências de transições,
abstraindo-se a existência de estados.
O processo de consulta, por sua vez, utiliza os resultados gravados pelo processo
de verificação. A consulta é realizada passando-se como parâmetro uma dupla (Ev, α) e
o estado atual do mundo – que contém os valores tanto das propriedades dramáticas
quanto de contexto – para obter-se o conjunto R de resultados da verificação dessa
fórmula sobre esse evento.
A consulta percorre essa estrutura R coletando uma lista dos ConditionalResid
que tiveram o conjunto ConstrDram satisfeito pelo estado do mundo. Lembrando que
cada ConditionalResid é uma conjunção ou disjunção de triplas (Sf,RCtx,ResidFormula),
34
obtém-se uma conjunção ou disjunção de duplas (Sf,ResidFormula) eliminando-se os
termos de ConditionalResid que tem o conjunto RCtx insatisfeito. A expressão
resultando contém todas as fórmulas residuais ResidFormula que devem ser verificadas
a partir de Ev acabando em um estado Sf específico.
Outra observação necessária é a de que, adotando o modelo proposto, o
planejamento torna-se dependente do processo de pré-verificação no que diz respeito à
consideração de restrições sobre propriedades dramáticas. Isto é, o planejamento só é
capaz de tratar a satisfação de fórmulas que foram pré-verificadas. Assim, é necessário
que o processo de verificação trate cada fórmula βi como uma nova fórmula típica,
mesmo que ela não seja explicitamente listada no gênero como tal, e que gere resultados
para a sua verificação.
O processo de verificação é, como uma técnica de verificação de modelos,
exaustivo, sendo realizado em relação a cada possível restrição típica aplicada a cada
evento do gênero. Assim, os resultados são completos – não há fórmula possível no
gênero sem resultados indexados em relação a cada final de cada evento.
Os resultados de cada rodada de pré-verificação são reutilizáveis, e servem para
todas as gerações de enredos futuras naquele gênero. O gênero pode ser atualizado com
novas fórmulas típicas (por exemplo, por nova inferência de preferências de usuários); e
apenas as novas fórmulas (e suas possíveis subfórmulas) precisam ser verificadas em
nova rodada do algoritmo. A atualização de eventos, com a modificação da variação das
propriedades contínuas, no entanto, implica na necessidade de re-verificar todas as
fórmulas em relação ao evento modificado. Além de reutilizáveis, os resultados do
processo de verificação podem ser utilizados em paralelo. Isso quer dizer que duas
instâncias diferentes do mesmo sistema de Storytelling Interativo podem consultar os
mesmos dados pré-verificados concomitantemente sem interferência.
Conforme descrito na seção 2.4.1, a lógica temporal ramificada aplicada ao
domínio de storytelling assume um tempo finito – isto é, que há um ponto final da
história. Como o trabalho de verificação realizado nesta dissertação trata dos eventos
em forma abstrata, é impossível distinguir se um evento possui ou não possui
continuação. Assim, o tratamento especializado para a satisfação de fórmulas em
estados finais de eventos finais da história é deixado a cargo do planejamento. Os
algoritmos referentes aos processos de verificação e consulta descritos aqui são dados
no capítulo seguinte.
35
4
Algoritmos de Verificação Abstrata
Esta seção descreve os algoritmos implementados para realizar a pré-verificação
das restrições sobre propriedades dramáticas em eventos abstratos de um gênero. A
descrição dos algoritmos é feita segundo uma notação em pseudo-código na qual os
nomes destacados em VERSALETE indicam chamadas a algoritmos; e termos com a
primeira letra maiúscula em Itálico indicam variáveis. O símbolo “//” indica comentário
de código (a partir do símbolo até o final da linha corrente). Ao longo das descrições
dos algoritmos, os quantificadores de caminho (A e E) e operadores de estado (F, G,
end ou U) da lógica CTL-estendida são destacados em negrito para não serem
confundidos com variáveis.
Relembra-se que a verificação de uma fórmula é feita sobre a definição abstrata
de um evento, já que os valores concretos do estado do mundo e das propriedades
dramáticas não são conhecidos – só serão conhecidos durante o processo de
planejamento. Para tal, são utilizadas restrições (constraints) em constraint logic
programming (CLP) que, combinadas, definem as diversas situações diferentes a serem
tratadas. O uso de constraints em CLP é essencial para expressar e verificar a
consistência dessas restrições sobre propriedades dramáticas.
4.1 Processamento exaustivo
O modelo prevê a verificação exaustiva das fórmulas em todos os eventos do
gênero. Isto é, para cada fórmula, em relação a cada evento, são gerados resultados
mapeando todos os estados possíveis do mundo a uma fórmula que deve ser verificada
na sequência. Estes estados do mundo não são enumerados, no entanto, mas
classificados de acordo com a restrições sobre as propriedades de contexto e dramáticas.
O algoritmo VERIFY_FORMULAE_EVENTS controla o processo de verificação
em seu nível mais alto, gerenciando os resultados da verificação sobre cada par evento fórmula típica. Nas próximas seções são descritos os algoritmos referentes a esse
processo de alto nível.
36
4.1.1 Verify_Formulae_Events
O algoritmo VERIFY_FORMULAE_EVENTS é descrito no item Algoritmo 4-1.
Este algoritmo é responsável por invocar o algoritmo VERIFY para cada par evento,
fórmula típica e por verificar fórmulas residuais não-típicas, mantendo a completude
dos resultados.
O modo de operação do algoritmo é: primeiro, são geradas as árvores de
execução de todos os eventos do gênero. Depois, todas as fórmulas típicas são
iterativamente verificadas sobre todas as árvores. Ao longo do processo, cada fórmula
residual encontrada que ainda não foi verificada é adicionada ao conjunto de fórmulas
a verificar.
O motivo para esse tratamento de fórmulas residuais (conforme descrito na
seção 3.2) é que, no modelo proposto, o processo de planejamento se torna dependente
da pré-verificação para lidar com fórmulas temporais sobre propriedades dramáticas.
Se o processo de planejamento consulta a satisfação de uma fórmula f1 sobre um evento
qualquer, e recebe como resposta que é necessário verificar uma fórmula f2 no evento
seguinte; então é preciso que f2 também tenha sido pré-verificada – mesmo que não seja
uma fórmula típica explícita no gênero – já que, sem o processo de pré-verificação, o
planejamento não pode distinguir se uma fórmula é válida ou não em um evento.
37
1. VERIFY_FORMULAE_EVENTS(GEN)
2.
DP = conjunto de propriedades dramáticas de GEN,
3.
FT = conjunto de fórmulas típicas de GEN,
4.
EVS = conjunto de eventos de GEN,
5.
L_TREES = [ ]
6.
para cada evento E em EVS:
7.
TR = GEN_TREE (E, GEN),
8.
L_TREES = UNION(L_TREES,TR)
9.
L_VERIFIED = [ true, false ]
10.
R=[]
11.
enquanto FT ≠ [ ]
//fórmulas a verificar
//fórmulas já verificadas
//Resultados
12.
L_RESIDS = [ ]
13.
remove-se a primeira fórmula F de FT
14.
UNION (F, L_VERIFIED)
15.
para cada par evento-árvore TR=(E,TREE) em L_TREES
16.
RF = VERIFY(E, {true}, DP, F, TREE)
17.
para cada fórmula residual Resid em RF
18.
se Resid ∉ L_VERIFIED
19.
L_RESIDS += Resid
20.
RECORD(E,FT,RF)
21.
UNION (FT, L_RESIDS)
Algoritmo 4-1. Verify_Formulae_Events.
O algoritmo recebe como parâmetro de entrada um identificador de um dos
gêneros presente na base de conteúdo. A partir desse identificador, são obtidos os
conjuntos:
•
DP, de propriedades dramáticas (linha 2);
•
FT, de fórmulas típicas a verificar (linha 3);
•
EVS, de eventos (linha 4).
O algoritmo começa coletando todas as árvores de execução (linhas 5-8). É
gerado um elemento TR para cada evento E em EVS através de chamada ao algoritmo
GEN_TREE, descrito na seção 4.1.2. Esse elemento TR é uma dupla (E,TREE),
associando um evento a uma árvore de execução.
38
É definida uma lista L_VERIFIED de fórmulas já testadas sobre todas as
árvores (linha 9). Esta lista é inicializada contendo os valores true e false, pois essas
fórmulas não são consultadas pelo planejamento, e não é necessário verificá-las.
O algoritmo prossegue selecionando uma das fórmulas em FT para verificar
sobre todas árvores em L_TREE. Essa fórmula F é removida do conjunto FT e é
adicionada ao conjunto L_VERIFIED (linhas 13-14).
A verificação da fórmula F é realizada invocando-se o algoritmo VERIFY,
descrito na seção 4.2. O conjunto RF de resultados (linha 16) da verificação dessa
fórmula sobre esse evento é dado por esse algoritmo. Nas linhas 17 a 19, todas as
fórmulas residuais geradas pelo processo de verificação que ainda não foram testadas
são adicionadas ao conjunto L_RESIDS de fórmulas a testar. A aplicação do algoritmo
de união (linha 21) garante a não duplicidade das fórmulas na geração do novo conjunto
FT. A chamada ao procedimento RECORD na linha 20 representa a gravação dos
resultados para a verificação da fórmula F sobre o evento E em uma estrutura global.
Essa estrutura indexa cada par (E,F) em relação a um resultado RF.
4.1.2 Gen_Tree
Como a variação das propriedades dramáticas é definida nos autômatos não
determinísticos associados aos eventos, é preciso limitar os possíveis ciclos na execução
desses autômatos de forma a evitar que o processo de verificação seja infinito. Para
tanto, o algoritmo GEN_TREE faz uso da informação contida no gênero para gerar uma
árvore de execução: uma estrutura de dados finita que contém toda a informação
necessária para a execução do evento.
A árvore gerada é finita, pois é utilizada informação contida no gênero para
limitar o tempo de execução. Para gerar a estrutura, o algoritmo GEN_TREE, descrito
no item Algoritmo 4-2, considera as seguintes informações:
•
Cada transição é composta por uma seqüência de micro-ações;
•
Cada micro-ação tem tempo de dramatização definido;
•
Cada evento tem tempo máximo e mínimo de dramatização.
O algoritmo utiliza o algoritmo auxiliar GEN_SEQUENCES, que recursivamente
gera sub-árvores dado um estado inicial S, um tempo já percorrido no evento e os
limites máximo e mínimo de tempo de execução para o restante da árvore.
39
1. GEN_TREE(E, GEN)
2.
LowB = tempo mínimo para a execução de E em GEN,
//Lower Bound
3.
HiB = tempo máximo para a execução de E em GEN,
//Higher Bound
4.
S = estado inicial de E,
//State
5.
TS = conjunto de transições possíveis a partir de S,
//Transition Set
6.
(EndPaths,Subtrees) = GEN_SEQUENCES(E, S, TS, LowB, HiB, [ ], 0),
7.
se Subtrees ≠ nil
8.
9.
10.
11.
TREE = (nil, S, 0, [ ], EndPaths, Subtrees)
senão
TREE = nil
retorna TREE
Algoritmo 4-2. Gen_Tree.
O algoritmo recebe como parâmetros de entrada os identificadores únicos do
evento e do gênero, para obter a informação sobre o tempo máximo e mínimo possível
de dramatização desse evento nesse gênero. Gera-se como retorno uma estrutura de
dados que representa a árvore. Essa estrutura é recursivamente definida na forma (SIni,
SEnd, D, CtxAcc, EndPaths, Subtrees):
•
SIni é o estado inicial da transição;
•
SEnd é o estado final da transição;
•
D é a duração, em segundos, da transição;
•
CtxAcc é o conjunto de restrições sobre propriedades de contexto
acumulado até a transição atual (inclusive);
•
EndPaths é um conjunto de duplas (Fin,LCtx); nas quais:
o Fin é o identificador de um estado final do evento; e
o LCtx é um conjunto de restrições sobre propriedades de contexto
acumulado até atingir Fin;
•
Subtrees é uma lista de árvores de transição a partir de SEnd. Transições
terminais têm SEnd como um estado terminal do autômato e a lista
Subtrees vazia.
Uma árvore de execução é tal, portanto, que sempre contém apenas uma
transição inicial, i.e., apenas uma aresta partindo do seu nó raiz. A árvore inicial possui
um nó raiz nil, duração zero, e um caminho percorrido vazio, sem restrições sobre
40
propriedades de contexto. Essa transição identifica a origem da execução do evento.
Formalmente, a transição inicial é dada na forma especial (nil, Sini, 0, [ ], SRCtx,
EndPaths, Subtrees), sendo Sini o estado inicial do autômato e [ ] a representação de uma
lista vazia.
A árvore de execução também guarda em todas as transições a informação sobre
os finais possíveis, e as sequências de transições necessárias para atingi-los. Essa
informação é contida no conjunto EndPaths. Semanticamente, o conjunto EndPaths de
uma árvore provê informação sobre todos os caminhos possíveis para todos os finais a
partir daquele ponto na árvore. Essa informação é necessária para a gravação de
resultados sem que seja necessário percorrer a árvore até o final.
Nota-se que a informação sobre a variação das propriedades dramáticas está
contida, na árvore de execução, apenas implicitamente. Através dos identificadores dos
estados é possível consultar o banco de dados que contém as definições do gênero e
recuperar a informação sobre como as propriedades variam.
41
4.2 Algoritmo de verificação
1. VERIFY(E, ConstrAcc, DP, Expr, Tree)
2.
TREE = (IniS, EndS, D, CtxAcc, EndPaths, L_SubTrees)
3.
Transition = (IniS,EndS,D)
4.
(L_Elems, ExprElems) ← EXPRELEMS(Expr)
5.
L_Result = [ ({true}, ExprElems) ]
6.
para cada Elem em L_Elems
7.
Elem = (ElemF, ElemVar)
8.
L_RespAllSit = [ ]
9.
L_Sit ← SATISFACTION(E, ConstrAcc, DP, ElemF,Transition)
10.
para cada Sit em L_Sit
11.
Sit = (SitCtr, SitResid)
12.
se SitResid = true ou SitResid = false
13.
14.
15.
L_RespSit ← ENDPATHRESIDS(SitCtr,EndPaths,SitResid, ElemF)
senão
se L_SubTree = [ ]
16.
L_RespSit ← DISTRIBUTERESIDS(SitCtr, CtxAcc,p
EndS, SitResid)
17.
senão
18.
L_RespSit = [ ]
19.
para cada SubTree em L_SubTrees
20.
L_RespSitPartial ← VERIFY(E, SitCtr, DP,
SitResid, SubTree)
21.
L_RespSit ← COMBINESITUATIONS(L_RespSit,
L_RespSitPartial, ElemF)
22.
23.
L_RespAllSit ← UNION(L_RespAllSit,L_RespSit)
L_Result ← COMBINERESULT(L_Result, L_RespAllSit, ElemVar)
24. retorna L_Result
Algoritmo 4-3. Verify.
O processo de verificação é mostrado no Algoritmo 4-3. Ele opera
recursivamente, gerando o resultado da verificação de uma expressão sobre uma árvore
de execução. Recebe como parâmetros:
42
•
O identificador do evento E, utilizado no algoritmo de satisfação para
poder recuperar os valores das propriedades nos estados desse evento;
•
O conjunto ConstrAcc
de restrições sobre propriedades dramáticas
acumuladas até esse ponto;
•
O conjunto DP de variáveis, representando os valores das propriedades
dramáticas no instante inicial do evento. As restrições acumuladas ao
longo da verificação são afirmadas sobre essas variáveis;
•
A expressão Expr, uma conjunção ou disjunção de fórmulas CTLestendidas, cada uma delas com apenas um quantificador mais geral;
•
A árvore de execução Tree, no formato descrito na seção 4.1.2.
A expressão de entrada Expr contém a fórmula a ser verificada na árvore Tree.
Como Expr pode ser uma disjunção ou conjunção de fórmulas CTL-estendidas com
apenas um quantificador mais geral, cada elemento em Expr é tratado em separado. Os
resultados gerados pelo tratamento de cada um desses elementos são combinados
incrementalmente.
A expressão Expr é ‘separada’ em elementos na chamada ao algoritmo auxiliar
EXPRELEMS. Essa chamada (linha 4) recebe Expr e produz uma dupla (L_Elems,
ExprElems), na qual:
•
L_Elems é uma lista de duplas (Elem,Var), na qual:
o Elem é um dos elementos da expressão original;
o Var é uma variável placeholder (identificadora de posição)
associada a Elem;
•
ExprElems é uma cópia da expressão original, na qual cada elemento é
substituído pela variável Var associada ao Elem correspondente.
ExprElems é utilizada para compor o valor inicial dos resultados em
L_Result. Ao longo do processamento, os resultados produzidos nas
chamadas recursivas substituem essas variáveis - assim, se a expressão
original recebida é uma disjunção/conjunção, o resultado final contém a
disjunção/conjunção, respectivamente, dos resultados das chamadas
recursivas.
A qualquer momento, a lista L_Result guarda a combinação dos resultados
gerados para cada elemento da expressão já tratado. Ela é um conjunto de resultados
43
dados na forma descrita na seção 3.2. Ou seja, cada membro de L_Results é uma dupla
(CtrDram, ConditionalResid), onde:
•
CtrDram são as restrições do resultado;
•
ConditionalResid é a expressão do resultado, uma conjunção ou disjunção
de triplas (Sf,RCtx,ResidFormula):
o Sf é um estado final do evento;
o RCtx um conjunto de restrições sobre propriedades de contexto;
o ResidFormula uma fórmula CTL-estendida com apenas um
quantificador mais geral.
A princípio, a lista L_Result contém apenas a dupla ({true},ExprElems) (linha 5).
Conforme cada elemento Elem da expressão original é tratado (no ciclo que começa na
linha 6), é gerada uma lista de resultados L_RespAllSit para esse elemento.
Cada dupla na lista L_Result é combinada com cada um dos elementos em
L_RespAllSit através de uma chamada a COMBINERESULTS (linha 23). Essa combinação
corresponde à criação das diferentes situações referentes às fórmulas já tratadas com as
situações relacionadas à nova fórmula. Cada combinação que gera uma nova situação
que não seja consistente será desconsiderada no resultado final. Assim, ao final do
processo, L_Result é retornado contendo as combinações dos resultados gerados pelo
tratamento de cada um dos elementos Elem na expressão original Expr. Note que, na
chamada de COMBINERESULTS, é passada como parâmetro a variável ElemVar que
representa os resultados de ElemF. O algoritmo cuida de instanciar essa variável com os
repectivos resultados que aparecem em L_RespAllSit para cada situação, bem como de
fazer simplificações de fórmulas sempre que possível.
Cada elemento Elem na expressão original Expr é uma fórmula a ser satisfeita na
primeira transição Transition da árvore atual Tree. Essa análise de satisfação (linha 9)
gera uma lista de situações alternativas para esta fórmula, L_Sit. Cada uma destas
situações mapeia um conjunto distinto de estados do mundo a fórmulas que precisam
ser verificadas nas sequências da transição inicial da árvore (linha 11).
Uma situação Sit é uma dupla (SitCtr,SitResid) (linha11). O conjunto de estados
do mundo ao qual a situação se aplica é dado por um conjunto de restrições sobre
propriedades dramáticas SitCtr. A expressão (conjunção e/ou disjunção de fórmulas)
que é preciso verificar nas continuações nessa situação é dada por SitResid.
44
O ciclo que começa na linha 10 trata cada situação, gerando uma lista L_RespSit
de resultados para essa situação que possivelmente se desdobra em várias situações de
acordo com as próximas transições em cada uma das subárvores. Esse tratamento
distingue três casos diferentes, discutidos a seguir. L_RespSit contém o resultado
incremental das combinações das situações resultantes do tratamento de cada uma das
subárvores para a situação (SitCtr, SitResid). Quando a situação acaba de ser tratada, os
seus resultados em L_RespSit são iterativamente adicionados à lista L_RespAllSit. A
princípio, essa lista é vazia (linha 8), mas ao final do ciclo deve conter os resultados
combinados de todas as situações tratadas sobre todas as sub-árvores para um dado
elemento Elem da fórmula Expr que está sendo verificada.
4.2.1 Tratamento das situações
Uma situação pode ser tratada de três modos distintos. Nessa seção, descreve-se
os algoritmos que geram a lista de respostas para uma dada situação, em cada um desses
casos.
4.2.1.1
Situação com fórmula residual true ou false
Primeiro, considera-se o caso no qual uma situação mapeia um estado do mundo
a uma falha ou sucesso incondicional (isto é, quando SitResid é false ou true,
respectivamente). Nesse caso, utiliza-se a informação sobre os caminhos completos até
os finais da árvore para compor-se um resultado. Esse processo é tratado pelo algoritmo
ENDPATHRESIDS (linha 13), descrito no Algoritmo 4-4.
1. ENDPATHRESIDS(SitCtr, EndPaths, SitResid,ElemF)
2.
ElemF = (PQ, _, _),
3.
ResExpr = true
4.
para cada dupla Path em EndPaths
5.
Path = (Sf, RCtx)
6.
se PQ = A
7.
ResExpr ← MAKECONJ (ResExpr,(Sf,RCtx,SitResid))
8.
senão, se PQ = E
9.
ResExpr ← MAKEDISJ(ResExpr,(Sf,RCtx,SitResid))
10. retorna [ (SitCtr,ResExpr) ]
Algoritmo 4-4. EndPathResids.
Esse algoritmo recebe:
45
•
SitCtr, o conjunto de restrições sobre propriedades dramáticas da
situação, a ser inserido no resultado;
•
EndPaths, uma lista de duplas (Sf,RCtx), onde Sf é o estado final do
autômato atingido ao final de um caminho da árvore e RCtx é o conjunto
de restrições sobre propriedades de contexto necessárias para que Sf seja
alcançado. Cada elemento de EndPaths forma uma tripla na expressão do
resultado;
•
SitResid que nesse caso tem o valor true ou o valor false; é a fórmula
residual em cada termo da expressão do resultado.
•
ElemF é a fórmula que gerou a situação que está sendo analisada para as
folhas da árvore. O quantificador de caminho dessa fórmula, PQ,
determina se a expressão do resultado é uma conjunção ou disjunção de
termos. Os algoritmos MAKECONJ e MAKEDISJ são aplicados caso o
quantificador seja A ou E, respectivamente.
O algoritmo ENDPATHRESIDS retorna um conjunto com um único resultado
(SitCtr,ResExpr); onde ResExpr é uma conjunção ou disjunção de triplas, cada uma
formada pelo estado final Sf e pelas restriçõs de contexto RCtx que formam cada
elemento de EndPaths, juntamente o valor true ou false de SitResid, replicado em todas
as triplas. No algoritmo VERIFY, esse resultado é recebido como L_RespSit (Algoritmo
4-3, linha 13).
Esse algoritmo é usado para marcar registrar que para todos os finais que podem
ser alcançados em uma árvore, a fórmula que estava sendo verificada tem valor true ou
false, evitando-se chamadas recursivas ao algoritmo VERIFY, uma vez que a satisfação
ou não da fórmula terá sido detectada.
4.2.1.2 Situação gerada em transição final da árvore
O segundo caso para o tratamento de uma situação é quando não há sub-árvores;
isto é, a transição Transition (Algoritmo 4-3, linha 3) leva a um estado final EndS que é
um estado final do evento. Nesse caso, uma chamada ao algoritmo DISTRIBUTERESIDS
(Algoritmo 4-3, linha 16) gera um resultado referente a esse final do evento. O
algoritmo DISTRIBUTERESIDS é dado no item Algoritmo 4-5.
46
1. DISTRIBUTERESIDS(SitCtr,CtxAcc,EndS,SitResid)
2.
(ResidElems, ResExpr) ← EXPRELEMS(SitResid)
3.
para cada Elem em ResidElems
4.
Elem = (ElemF, ElemVar)
5.
Resp = (EndS,CtxAcc,ElemF)
6.
ResExpr ← SUBSTITUTE(ResExpr,ElemVar,Resp)
7.
retorna [ (SitCtr,ResExpr) ]
Algoritmo 4-5. DistributeResids.
Esse algoritmo recebe:
•
SitCtr, o conjunto de restrições a ser associado ao resultado para esse
final da árvore;
•
CtxAcc, as restrições sobre propriedades de contexto acumuladas até o
final da árvore nesse caminho. Cada tripla na expressão do resultado
contém CtxAcc;
•
EndS é o final atingido nesse caminho da árvore. Cada tripla na
expressão do resultado é dada em relação à EndS;
•
SitResid, a residual da situação; que pode ser uma disjunção ou
conjunção de fórmulas CTL-estendidas.
Se SitResid é apenas uma fórmula (e não uma conjunção ou disjunção de
fórmulas), o resultado é a dupla (SitCtr,(EndS,CtxAcc, SitResid)). Caso SitResid seja
uma conjunção ou disjunção de fórmulas, o resultado retornado terá como expressão
uma conjunção ou disjunção de triplas, respectivamente.
O algoritmo EXPRELEMS é utilizado para gerar uma expressão no mesmo
formato de SitResid com variáveis placeholder. Conforme os elementos de SitResid são
processados, as variáveis placeholder em ResExpr são substituídas por triplas formadas
por EndS, CtxAcc e o termo em SitResid equivalente àquela variável.
Esse algoritmo é usado para registrar o que precisa valer quando se encontra um
estado final do autômato, sendo a condição de parada normal do algoritmo recursivo
VERIFY.
4.2.1.3
Situação verificada sobre todas as sub-árvores
Por fim, o terceiro caso para o tratamento de uma situação é aquele no qual há
sub-árvores. A expressão dada por SitResid (Algoritmo 4-3, linha 11) é passada a uma
chamada recursiva ao algoritmo de verificação para cada uma das sub-árvores
(Algoritmo 4-3, linha 21), gerando uma lista de resultados parcial L_RespSitPartial. A
47
lista L_RespSit é iterativamente combinada com cada L_RespSitPartial através do
algoritmo COMBINESITUATIONS, dado no Algoritmo 4-6.
1. COMBINESITUATIONS(L_Current, L_Add, ElemF)
2. ElemF = (PQ, _, _),
3. L_RespNew = [ ]
4. para cada RespC em L_Current
5.
RespC = (CtrC, ExprC)
6.
para cada ElemAdd em L_Add
7.
RespAdd = (CtrA, ExprA)
8.
CtrN = CtrC and CtrA
9.
se CtrN é consistente
10.
se PQ = A
11.
ExprN = ExprC and ExprA
12 .
senão, se PQ = E
13.
ExprN = ExprC or ExprA
14.
L_RespN = (CtrN,ExprN)
15.
L_RespNew ← UNION(L_RespNew, L_RespN)
16. retorna L_RespNew
Algoritmo 4-6. CombineSituations.
O algoritmo COMBINESITUATIONS gera uma lista de resultados que combina
cada resultado já coletado (L_Current) com cada novo resultado (L_Add). O algoritmo
efetivamente gera todas as possíveis m x n combinações de situações, gerando um novo
resultado para cada possível par (m,n); no qual m é uma situação (RespC) em L_Current
e n é uma situação (CtrA) em L_Add. Combinações de estados que não são consistentes
são descartadas.
As expressões nos resultados m e n são combinadas levando-se em consideração
o quantificador de caminhos da fórmula ElemF. Caso o operador seja E, os resultados
são combinados em uma disjunção, e caso o operador seja A, a combinação é feita em
uma conjunção. Neste processo, conjunções e disjunções de um mesmo elemento são
simplificadas e simplificações são também feitas quando a fórmula a ser combinada é
true ou false.
4.3 Satisfação
O algoritmo SATISFACTION é descrito no Algoritmo 4-7.
48
1. SATISFACTION(E, CtrIn, DP,F,T)
2.
F = (PQ, SOp, Expr),
3.
se SOp == end
4.
L_ALTS = [(true, F) ]
//a própria fórmula, sem restrição
5.
senão
6.
se ARITHCONJ(Expr)
7.
L_ALTS ← SATISFACTION_BASIC(E, CtrIn, DP,F, T)
8.
senão
9.
(Alpha, Beta) ← SEPARATE_SUBFORMULA(Expr)
10.
NF = (PQ,SOp,Alpha)
11.
L_Partial ← SATISFACTION(E, CtrIn, DP, NF, T)
12.
L_ALTS ← SATISFACTION_DEPEND(E, F, Beta,
DP, T, L_Partial)
13. retorna L_ALTS
Algoritmo 4-7. Satisfaction.
O algoritmo recebe como parâmetros de entrada:
•
O identificador do evento E, para poder recuperar os valores das
propriedades nos estados desse evento;
•
O conjunto de restrições sobre as propriedades dramáticas acumuladas
até o momento em CtrIn;
•
O conjunto de variáveis representativas de propriedades dramáticas DP;
•
A fórmula F sobre a qual é preciso gerar as situações alternativas de
verificação a partir da transição atual;
•
A transição atual T.
O algoritmo de satisfação de uma fórmula é responsável por gerar uma lista de
situações alternativas a serem verificadas após uma transição da árvore de execução.
Todos os casos possíveis devem ser cobertos como alternativas distintas.
A saída do algoritmo é um único parâmetro L_ALTS, uma lista de alternativas.
Pode-se perceber que há dois modos principais de tratamento: quando a expressão
interna da fórmula é uma conjunção de relações aritméticas básicas, é invocado o
algoritmo SATISFACTION_BASIC (linhas 6-7). Relações aritméticas básicas são
definidas neste trabalho como equações e inequações que relacionam combinações
lineares dos valores das propriedades dramáticas.
Caso contrário é realizada uma chamada recursiva ao algoritmo SATISFACTION
e
uma
composição
de
alternativas
através
da
chamada
ao
algoritmo
SATISFACTION_DEPEND (linhas 8-12). Relembra-se que o processo de verificação trata
apenas de fórmulas com um quantificador mais geral, na forma F = (QC, SOp, Expr),
49
onde QC é o quantificador de caminho (A ou E); SOp é o operador de estado (F, G,
end ou U), e Expr é a expressão interna da forma ((ar0 and ar1 and ... arn) and SubF),
na qual:
•
cada termo ari é uma relação aritmética básica;
•
SubF é uma subfórmula, dada na mesma forma de F.
Essa restrição sobre SubF - de que deve ser dada na mesma forma de F e
possuir apenas um quantificador mais geral - é admitida para que o algoritmo
SATISFACTION possa operar recursivamente. Essa restrição é, portanto, introduzida pela
implementação do algoritmo (e não pelo modelo de pré-verificação proposto).
O algoritmo opera com um caso especial para o operador end, que define uma
restrição sobre o último instante da história ou capítulo. Como a verificação é abstrata,
não se conhece o contexto da aplicação do evento E na história, e não se sabe se esse
evento é capaz de satisfazer uma restrição que fala sobre o fim da história ou capítulo.
Portanto, fórmulas com o operador end são simplesmente repassadas como fórmulas
residuais nas alternativas – sem restrições – e gravadas nos resultados no final da
verificação; cabendo seu tratamento ao planejamento de enredos.
Também relembra-se que os valores das propriedades dramáticas contínuas são
abstratamente definidos para cada estado do autômato do evento, em função dos valores
de entrada, ou seja, os valores do estado inicial. Durante o planejamento, esses valores
são instanciados de acordo com valores que são calculados de acordo com o estado final
do evento que antecedeu o evento corrente.
No caso da primeira transição de um evento, que parte de um estado nil, a
geração de alternativas sempre é dada em relação ao valores pontuais de entrada. Isto é:
na transição inicial da primeira árvore, as constraints ligadas às alternativas simbolizam
restrições sobre as propriedades dramáticas no instante inicial do evento. No caso das
demais transições, as constraints representam restrições que devem valer em algum
ponto ou em algum intervalo da transição – possivelmente a transição inteira.
Define-se uma chamada de exemplo na qual o algoritmo de satisfação é
chamado sobre a transição t1 passando-se como parâmetro a fórmula β1. Para
exemplificar o funcionamento do algoritmo SATISFACTION, demonstra-se o caso no
qual β1 é a fórmula EF ({Joy ≥ 50}, de modo a explorar o tratamento da satisfação de
fórmulas com expressão interna básica. Isto é descrito na seção 4.3.1.1. Depois,
demonstra-se essa chamada com β1 sendo a fórmula EF ({Joy ≥ 50} and AG {Joy ≥ 50}),
50
para exemplificar o tratamento de fórmulas aninhadas. Este exemplo é descrito na seção
4.3.1.2. Em ambos os exemplos, assume-se que a propriedade Joy dobra ao longo da
transição entre os estados s0 e s2.
4.3.1.1 Satisfação de expressões básicas
Para os casos mais básicos de satisfação – fórmulas nas quais a expressão
interna é uma relação aritmética básica, é chamado o algoritmo SATISFACTION_BASIC.
Esse algoritmo é descrito no Algoritmo 4-8.
1. SATISFACTION_BASIC(E, CtrIn, DP,Formula,T)
2.
Formula = (PQ, SOp, Expr),
3.
T = (ORIG, DEST, D),
4.
(OrigVal, DestVals) ← COLLECT_ABSTRACT_VALUES(E, DP, ORIG, DEST)
5.
(VariationsCtrs,VarsInterval ) ← DEFINE_VARIATIONS (OrigVals,DestVals,D)
6.
L_ALTS ← COMPOSE_ALTERNATIVES(SOp, AltExpr,NAltExpr )
7.
retorna L_ALTS
Algoritmo 4-8. Satisfaction_Basic.
Nessa processo, são dados como parâmetros de entrada:
•
E, o identificador do evento;
•
CtrIn, as constraints acumuladas até o momento inicial da transição sobre a
qual a satisfação da fórmula corrente é analisada;
•
DP, o conjunto de variáveis representando as propriedades dramáticas;
•
Formula, a fórmula cuja satisafação é analisada na transição corrente;
•
T, a transição corrente.
A fórmula Formula é composta por um quantificador de caminhos PQ, um
operador de estados SOp e uma relação aritmética básica Expr. A transição T é definida
por um estado inicial ORIG, um estado terminal DEST e uma duração D.
Apresenta-se um exemplo de execução do algoritmo, e, na sequência, uma
explicação detalhada do código. Assume-se, no exemplo, a fórmula de entrada EF {Joy
≥ 50} sendo verificada sobre uma das subárvores geradas para um evento “Donate”.
Essa fórmula representa a restrição: “há algum caminho no qual, em algum instante, Joy
é maior ou igual a 50”. A Figura 4.1 mostra graficamente a chamada realizada.
51
Figura 4.1. Chamada, pelo algoritmo de verificação, ao algoritmo de satisfação para
fórmula com expressão interna básica.
Nessa chamada, já se está tratando a restrição de que o valor da propriedade
dramática Joy, no momento inicial do evento, representado pela variável Joy0, é menor
do que 50. Essa restrição foi adicionada pela verificação na transição anterior, que gerou
como residual a fórmula que está sendo verificada em nosso exemplo. A verificação que
está sendo feita deve tratar as situações diferentes que podem decorrer desse fato.
O primeiro passo do algoritmo de satisfação, quando está tratando de uma
fórmula
básica,
é
consultar
a
base
de
dados.
Essa
consulta
(COLLECT_ABSTRACT_VALUES) obtém os valores abstratos das propriedades
dramáticas nos estados da transição atual. A consulta, no exemplo corrente, retorna as
seguintes expressões:
•
em s0, o valor da propriedade Joy, representado pela variável nova
JoyOrig, é igual ao valor de entrada, representado por Joy0;
•
em s2, o valor de Joy, representado por JoyDest é igual a duas vezes o
valor de entrada (isto é, 2*Joy0).
Além de usar variáveis para representar os valores nos extremos dos intervalos,
é necessário criar variável para representar o valor em momentos ao longo do intervalo,
assumindo a variação linear com o tempo. Este valor depende dos valores de origem e
de destino e de um tempo proporcional à duração do intervalo. Este tratamento é
realizado pelo algoritmo DEFINE_VARIATIONS.
No exemplo corrente, a variável produzida para representar este instante genérico
é JoyMid. Sobre ela é gerada a constraint
{JoyMid = JoyOrig + (JoyDest- JoyOrig)
52
*Time/D}que é simplificada para {JoyMid = Joy0 + Joy0*Time/D}, onde Time é uma
variável que representa o tempo transcorrido e D é a duração da transição.
A Figura 4.2 mostra semanticamente como JoyMid representa o valor de Joy ao
longo da transição do estado s0 para s2. Quando o tempo é zero, JoyMid ainda não sofreu
variação em relação a JoyOrig e tem valor Joy0. Conforme o tempo passa (e o valor de
Time aumenta), JoyMid torna-se progressivamente mais próxima do valor final, até
tornar-se exatamente igual a JoyDest (no exemplo, 2*Joy0) quando o tempo é igual a
duração da transição.
Figura 4.2. Variação da propriedade Joy ao longo de uma transição na qual dobra de
valor, em relação a uma variável que representa o tempo transcorrido.
Nota-se, na Figura 4.2, que sobre a variável Time são geradas constraints que
descrevem o intervalo no qual a transição acontece. As constraints, na figura, ainda não
estão na forma simplifica a ser provida pelo constraint solver. Todas as situações a
serem consideradas para a satisfação da fórmula deverão satisfazer a essas restrições e a
restrições específicas de cada situação.
Uma vez tratada a variação das propriedades na transição, com variáveis para
representar seus valores ao longo dessa transição, pode-se agora tratar as alternativas
de satisfação da fórmula Formula de acordo com a fórmula que está sendo verificada.
Este tratamento, tipicamente implica em adicionar restrições em cima dessas variáveis.
Alternativas são então compostas juntando, na constraint store, as restrições de
entrada CtrIn com as restrições relativas à variação linear das propriedades VariationCtrs
e as restrições de cada alternativa. O constraint solver verifica a consistência da
alternativa e simplifica o conjunto de restrições em uma expressão que representa a
situação. A fórmula residual da alternativa é dada segundo o operador de estados da
53
fórmula. Sempre que a alternativa for consistente, ela deve ser considerada. No caso do
exemplo, como a fórmula tem operador F, expressando que a subfórmula deve valer em
algum momento, as alternativas compostas são:
•
({CtrIn and CtrVars and JoyMid ≥ 50}, true);
Representando que em algum momento da transição o ‘novo valor’ de
Joy deve ser maior ou igual a 50, e que, nesse caso, a fórmula é satisfeita
sem precisar verificar nada nas sequências.
•
({{CtrIn and CtrVars and JoyOrig < 50 and JoyDest <50}, EF {Joy ≥ 50});
Representando que, durante toda a transição, o ‘novo valor’ de Joy deve
ser menor que 50, devido ao fato de ser menor do que 50 nos extremos, e
que, nesse caso, ainda é preciso encontrar, no futuro, um instante no qual
Joy≥ 50.
O resultado da chamada ao algoritmo de satisfação nesse exemplo é mostrado na
Figura 4.3. Nesta figura, as constraints já se encontram simplificadas, em sua forma
final. As alternativas resultante são o retorno do algoritmo.
Figura 4.3. Resultado da chamada ao algoritmo de satistafação de fórmula sobre
transição.
Detalha-se o funcionamento do algoritmo de acordo com o código. Primeiro, o
algoritmo obtém os valores abstratos das propriedades dramáticas no estado de origem
54
(OrigVals) e no estado destino (DestVals) da transição T (linha 3), as quais são
combinações lineares dos valores das propriedades dramáticas no estado inicial do
autômato. Para tanto, é aplicado o algoritmo COLLECT_ABSTRACT_VALUES, que
consulta a base utilizando o identificador único do evento E, o estado de origem ORIG e
o estado destino DEST.
Depois (linha 4), o algoritmo DEFINE_VARIATIONS calcula a variação abstrata
sofrida por cada propriedade dramática ao longo da transição. São construídas então
restrições representando essas variações, que são armazenadas em VariationCtrs. Essas
restrições referem-se a variáveis novas criadas para representar os valores no estado de
origem, no estado de destino e no meio do intervalo. Tais variáveis, definidas para todas
as propriedades dramáticas, são listadas em IntervalVars, de modo que possam ser
referenciadas pelas restrições das diferentes situações.
Por fim (Algoritmo 4-8, linha 6), as alternativas são compostas de acordo com a
semântica do operador de estados. Esta etapa é dependente do operador de estados SOp
da fórmula Formula. A Tabela 3 mostra o tratamento dependente de operador. As
alternativas de satisfação para cada operador são testadas e simplificadas juntamente
com as restrições de entrada CtrIn e de variação ao longo do intervalo, VariationCtrs.
Todas as alternativas consistentes geram situações cujas fórmulas residuais devem ser
verificadas nas transições seguintes.
55
SOp
Alternativas
Expressão
Residual
Descrição
true
Fórmula satisfeita na transição. Expr deve valer
em algum instante do intervalo. Nada mais vai
precisar ser verificado em seguida.
Formula
Fórmula não satisfeita na transição. Expr não
deve valer em momento algum do intervalo, o
que é garantindo ao se forçar que a negação de
Expr valha no estado de origem e de destino;
nesse caso, a própria fórmula deve ser verificada
no futuro.
Formula
Fórmula vale por toda a transição sem falhar, o
que é garantindo ao se forçar que a Expr valha
no estado de origem e de destino; Expr deve
valer em todo o intervalo e é necessário
continuar verificando a própria fórmula.
false
Fórmula não vale em algum momento da
transição. Residual indica verificação de que
fórmula não é válida.
Before[orig] and
Before[dest] and
(NotAfter)[mid]
Formula
Before foi válida ao longo da transição; mas After
não foi satisfeita. É necessário continuar
verificando a própria fórmula.
Before[orig] and
Before[mid] and
After[mid]
true
Before foi válida do início até algum instante da
transição; e After valeu nesse instante. Nada mais
precisa ser verificado em seguida.
false
Before não valeu em algum instante; e After não
valeu no intervalo definido pelo início da
transição e esse instante. Residual indica
verificação de que fórmula não é válida.
Expr[mid]
F
(NotExpr)[orig]
and
(NotExpr)[dest]
Expr[orig]
Expr[dest]
and
G
(NotExpr)[mid]
U
(NotBefore)[mid]
and
(NotAfter[orig])
and
(NotAfter)[mid]
Tabela 4 Tabela 3. Tratamento de alternativas de acordo com operadores de estado.
Na tabela, é utilizada a notação Expr[orig], Expr[dest] e Expr[mid] para
designar, respectivamente, a expressão aplicada ao estado de origem, de destino ou a um
determinado momento genérico ao longo do intervalo. Lembra-se que o operador U é
56
acompanhado de uma expressão Expr na forma (Before,After), descrevendo a
necessidade de garantir que a restrição antecedente Before seja válida até o momento em
que After valha. Desse modo, a classificação das situações analisa a validade de Before e
de After. A notação Not Expr é usada para designar a negação da expressão Expr (e.g. a
negação de Joy≥50 é Joy<50).
57
SOp
Alternativas
Expressão
Residual
Descrição
true
Fórmula satisfeita na transição. Expr deve valer
em algum instante do intervalo. Nada mais vai
precisar ser verificado em seguida.
Formula
Fórmula não satisfeita na transição. Expr não
deve valer em momento algum do intervalo, o
que é garantindo ao se forçar que a negação de
Expr valha no estado de origem e de destino;
nesse caso, a própria fórmula deve ser verificada
no futuro.
Formula
Fórmula vale por toda a transição sem falhar, o
que é garantindo ao se forçar que a Expr valha
no estado de origem e de destino; Expr deve
valer em todo o intervalo e é necessário
continuar verificando a própria fórmula.
false
Fórmula não vale em algum momento da
transição. Residual indica verificação de que
fórmula não é válida.
Before[orig] and
Before[dest] and
(NotAfter)[mid]
Formula
Before foi válida ao longo da transição; mas After
não foi satisfeita. É necessário continuar
verificando a própria fórmula.
Before[orig] and
Before[mid] and
After[mid]
true
Before foi válida do início até algum instante da
transição; e After valeu nesse instante. Nada mais
precisa ser verificado em seguida.
false
Before não valeu em algum instante; e After não
valeu no intervalo definido pelo início da
transição e esse instante. Residual indica
verificação de que fórmula não é válida.
Expr[mid]
F
(NotExpr)[orig]
and
(NotExpr)[dest]
Expr[orig]
Expr[dest]
and
G
(NotExpr)[mid]
U
(NotBefore)[mid]
and
(NotAfter[orig])
and
(NotAfter)[mid]
Tabela 4. Tabela de composição de alternativas por operador no caso da satisfação
básica.
4.3.1.2 Satisfação de fórmulas aninhadas
58
Se a expressão interna é uma conjunção de restrições aritméticas com uma subfórmula quantificada, é necessário tratamento diferenciado. No momento, o único tipo
de forma aninhada que está sendo tratado se refere a conjunções de relações aritméticas
básicas com uma única sub-fórmula quantificada. Além disso, são tratadas subfórmulas
aninhadas apenas quando o operador de estados é F ou G. Apresenta-se agora o
algoritmo SATISFACTION_DEPEND. Esse algoritmo é descrito no Algoritmo 4-9.
1. SATISFACTION_DEPEND (E, OF, F, DP, T, L_Above)
2.
OF= (QC,_,_),
3.
para cada AltAbove em L_Above
4.
AltAbove = (CtrAbove,ResidAbove)
5.
se QC = F
6.
se é possível definir uma sub-transição T’ de T
com as restrições em CtrAbove
7.
NT = T’
8.
senão
9.
seja NAlt a alternativa AltAbove com a fórmula residual
substituída por OF
10.
L_ALTS+= [NAlt]
11.
escape
12.
senão, se QC = G
13.
NT = T
14.
L_Local ← SATISFACTION(E, CtrAbove, DP, F, NT)
15.
L_Comb ← COMBINE_HIERARCHICAL_ALTERNATIVES(AltAbove,L_Local)
16
L_ALTS += L_Comb
17. retorna L_ALTS
Algoritmo 4-9. Satisfaction_Depend.
O objetivo desse tratamento é gerar as combinações de possibilidades: para cada
alternativa da fórmula no nível superior, é gerada a satisfação da fórmula interna. Assim,
a satisfação de uma fórmula aninhada gera todos os casos possíveis.
Assume-se, no exemplo para este caso, a fórmula EF ({Joy ≥ 50} and AG {Joy ≥
50}). Essa fórmula significa a restrição: “Há algum caminho no qual Joy é maior ou
igual a 50 em algum instante, e a partir daquele instante, em todas as histórias possíveis
a partir desse momento, Joy mantém-se maior ou igual a 50”. O resultado desejado pra
esse exemplo é o seguinte:
•
Se há algum ponto ao longo da transição no qual Joy se torna maior ou
igual a 50;
o E se Joy se mantém maior ou igual a 50 até o fim da transição:
59
é necessário continuar verificando que, em todas as histórias
possíveis, Joy não se torna menor que 50.
Também é necessário considerar que, mesmo que a restrição
seja satisfeita sobre essa transição, ela pode falhar no futuro.
Assim, é necessário procurar outro ponto no futuro que
satisfaça a fórmula original.
o E Joy se torna menor que 50: a porção interna da fórmula não é
satisfeita, e é necessário encontrar outro ponto no futuro que
satisfaça a fórmula original.
•
Se não há algum ponto ao longo da transição no qual Joy se torna maior
ou igual a 50, é necessário continuar procurando, nas transições futuras,
um ponto que satisfaça a fórmula.
O algoritmo SATISFACTION realiza um tratamento para a fórmula aninhada.
Primeiro, a fórmula tem a expressão interna separada (Algoritmo 4-7, linha 9), e são
compostas:
•
A fórmula superior, composta pelo quantificador mais geral e as
restrições aritméticas diretamente relacionadas a ele. No exemplo: EF
{Joy ≥ 50}.
•
A fórmula interna, relativa às restrições de um quantificador interno,
possivelmente outra fórmula aninhada. No exemplo: AG {Joy ≥ 50}.
A fórmula superior é usada em uma chamada recursiva ao algoritmo
SATISFACTION. A Figura 4.4 mostra esse processo.
60
Figura 4.4. No tratamento de fórmulas aninhadas, a expressão interna é dividida. Uma
chamada recursiva ao algoritmo de satisfação é realizada sobre a fórmula contendo a
primeira parcela de conjunção original, resultando em uma lista de alternativas parciais.
O resultado dessa chamada é uma lista de alternativas parciais, denominada
L_Partial.
Essa
lista
é
então
passada
como
parâmetro
ao
algoritmo
SATISFACTION_DEPEND, que trata da satisfação da fórmula aninhada.
A satisfação da fórmula interna é gerada em relação às alternativas da lista
recebida como parâmetro. Ou seja, são coletadas as constraints necessárias para que a
fórmula interna seja satisfeita (insatisfeita, não-satisfeita, etc.) em relação a cada
possibilidade de resolução da fórmula superior.
A Figura 4.5 mostra o funcionamento do algoritmo SATISFACTION_DEPEND,
com o tratamento da primeira e segunda alternativas recebidas. A lista L_Partial é
recebida pelo algoritmo SATISFACTION_DEPEND como L_Above. São realizadas novas
chamadas ao algoritmo SATISFACTION para o tratamento de cada alternativa AltAbove
recebida nessa lista.
61
Figura 4.5. Tratamento de fórmula interna de fórmula aninhada. As alternativas geradas
na satisfação do primeiro termo da fórmula são recebidas como L_Above, e são
utilizadas para gerar a satisfação da fórmula interna de forma hierarquicamente
dependente.
No exemplo da Figura 4.5, a transição t1 gera a transição t1.p1, representando a
transição a partir de um ponto arbitrário p1 no qual Joy já foi maior ou igual a 50.
Efetivamente, as restrições de tempo ‘herdadas’ pelas chamadas nesse nível definem
uma parcela da transição na qual a fórmula interna deve ser satisfeita.
Se a relação entre a fórmula e a parcela da transição for incoerente, a alternativa
não é combinada. Por exemplo, no tratamento da segunda alternativa da Figura 4.5 –
que representa que Joy foi menor que 50 ao longo de todo o intervalo - não há subintervalo sobre o qual testar AG {Joy ≥ 50}.
Cada chamada nesse nível gera uma lista L_Local de alternativas de satisfação
da fórmula interna, incluindo as próprias constraints. O algoritmo combina esta lista
L_Local com a alternativa AltAbove sendo tratada e adiciona as alternativas resultantes
L_Comb à lista final L_ALTS de alternativas. A combinação de alternativas é realizada
pelo algoritmo COMBINE_HIERARCHICAL_ALTERNATIVES, que combina as constraints
em conjunções e as residuais de acordo com o operador de estados da fórmula superior.
As regras de composição aplicadas para a geração dessa lista L_Comb são dadas
na Tabela 5. Nessa tabela, o símbolo Formula representa uma fórmula qualquer
62
diferente de true e false; e Original representa a fórmula original do algoritmo de
satisfação (a fórmula aninhada completa).
Residual da
alternativa
Residual resultante:
Residual da
Operador de estados mais geral
alternativa local
superior
F
G
false
Formula
-
false
Formula
false
Original
false
true
Formula
Formula or Original
-
Formula
true
Formula or Original
Original
Formula
Formula
-
Original
Tabela 5. Tabela de composições de resultados de alternativas hierárquicas.
As regras de composição demonstradas na tabela consideram as seguintes
exigências:
•
Fórmulas com o operador mais geral F não podem falhar: ou a fórmula
foi satisfeita em algum ponto ou ainda pode ser satisfeita no futuro.
Assim, substitem-se nas alternativas finais as fórmulas residuais false
pela fórmula original.
•
Fórmulas com o operador mais geral F podem precisar ser verificadas no
futuro, mesmo que as restrições pontuais já tenham valido. Essa
alternativa representa o caso no qual a restrição pontual (associada ao
operador F) vale ao longo da transição atual, mas falha em algum ponto
posterior, durante a transição ou posteriormente. Nesse caso, é necessário
procurar um novo ponto no qual a restrição pontual vale. A cada
alternativa é adicionada na fórmula residual a fórmula original em
disjunção.
•
Fórmulas com o operador mais geral G podem falhar ou precisar ser
garantidas no futuro, não podendo ser satisfeitas absolutamente:
substituem-se nas alternativas finais todas as fórmulas residuais que não
são false pela fórmula original.
A segunda alternativa em L_Above não gera uma lista local. Essa alternativa é
então incluída diretamente na lista L_ALTS, tendo sua fórmula residual substituída pela
fórmula original.
63
As alternativas em L_Partial correspondem às possibilidades de continuação
desejadas. Nota-se que estas alternativas correspondem às continuações desejadas
listadas anteriormente.
Descreve-se agora o algoritmo em relação ao código. O algoritmo recebe como
parâmetros de entrada:
•
o identificador do evento E;
•
a fórmula superior AboveF;
•
a fórmula interna F, a ser satisfeita de forma dependente às alternativas
de satisfação da fórmula superior;
•
o conjunto de variáveis representando as propriedades dramáticas DP;
•
a transição atual T;
•
a lista de alternativas L_Above, geradas pela satisfação de AboveF na
transição T.
O algoritmo retorna uma lista de alternativas L_ALTS que define todas as
possibilidades de satisfação da fórmula aninhada. Na linha 2, o algoritmo inicia o ciclo
de tratamento de todas as alternativas AltAbove em L_Above.
Caso a alternativa AltAbove selecionada não defina uma transição T’ válida sobre
a qual verificar a fórmula interna F (linha 8), essa alternativa é adicionada aos
resultados tendo sua fórmula residual substituída pela fórmula superior (linhas 9 e 10).
Caso contrário (linha 4), é feita uma chamada interna ao algoritmo
SATISFACTION passando-se a fórmula F e a transição T’ como parâmetros. Essa
chamada resulta em uma lista de alternativas L_Local, que é parâmetro de entrada para
o algoritmo COMBINE_HIERARCHICAL_ALTERNATIVES.
O algoritmo COMBINE_HIERARCHICAL_ALTERNATIVES (linha 6) combina a
alternativa AltAbove da fórmula superior com as alternativas no nível atual L_Local. As
restrições das alternativas são compostas em uma conjunção, e as residuais são
combinadas segundo regras de composição. O resultado desse processo é uma lista
L_Comb de alternativas, que é adicionada à lista final L_Partial.
4.4 Consulta
Cada verificação de fórmula para um certo tipo de evento gera um conjunto de
resultados R indexado por uma dupla (Ev, α), onde Ev é a especificação abstrata de um
64
evento e α é uma fórmula CTL-estendida com apenas um quantificador mais geral. Em
tempo de planejamento, é preciso consultar esses resultados diante do valor das
propriedades dramáticas e de contexto. Desse modo, neste trabalho foi implementado
também o mecanismo de consulta que fornece as fórmulas residuais para uma dada
situação.
O processo de consulta recebe o estado do mundo, o valor corrente das
propriedades dramáticas a serem consideradas, a indicação do evento instanciado e uma
fórmula temporal sobre as propriedades dramáticas a ser verificada. Com base nessas
informações, são recuperadas na estrutura os pares (Situação, Residual) que foram
gerados pelo preprocessamento para o evento e a fórmula informada.
Com base no valor corrente das propriedades dramáticas, é selecionada a
fórmula residual. Tal fórmula, é uma conjunção de triplas (Sf, RCtx, Expr), onde Sf
identifica um dos estados finais do evento, RCtx contém um conjunto de restrições
sobre as propriedades de contexto que devem ser verificadas para que a tripla seja
considerada, e Expr é uma fórmula estendida a ser verificada a partir do estado final Sf
identificado.
Com base no estado do mundo, a fórmula residual é inspecionada para se saber
quais triplas têm as restrições de contexto atendidas. Quando não são atendidas, a tripla
é desconsiderada, não influenciando o resultado de conjunções e disjunções. Após esse
processamento, sabem-se os estados finais do eventos que podem ser atingidos. Além
disso, simplificações adicionais são feitas na expressão, uma vez que, com a avaliação
das restrições sobre propriedades de contexto, novas simplificações de fórmula tornamse possíveis. A expressão final a ser verificada a partir do evento é retornada como a
fórmula com conjunções e disjunções de duplas (Sf, Expr), indicando o que precisa
valer a partir de cada estado final para que a fórmula de entrada seja satisfeita. O
Algoritmo 4-10 descreve o processamento
65
1. CONSULT(Ev, F, S, Result)
2.
F = (PQ,_,_)
3.
R ← INDEX(Ev,F)
4.
DPVal ← DRAMPROPVALUES(S)
5.
para cada resultado Res em R
6.
Res = (Ctr,Expr)
7.
se Ctr é satisfeito em relação a DPVal
8.
(L_Elems, ExprElems) ← EXPRELEMS(Expr)
9.
para cada elemento Elem em L_Elems
10.
Elem = ((Sf,RCtx,Resid), ElemVar)
11.
se RCtx é satisfeito em relação a S
12.
ExprElems ← SUBSTITUTE(ExprElems,ElemVar,(Sf,Resid))
13.
senão
14.
se PQ = A
15.
ExprElems ← SUBSTITUTE(ExprElems,ElemVar,true)
16.
se PQ = E
17.
ExprElems ← SUBSTITUTE(ExprElems,ElemVar,false)
18.
retorna ExprElems
19. retorna false
Algoritmo 4-10. Consult.
66
5
Resultados e avaliação
Neste capítulo apresentam-se os resultados gerados pela implementação do
modelo e dos algoritmos expostos no capítulo anterior. Avalia-se os resultados em
relação a dois quesitos principais. São eles: a capacidade de expressão provida pelo
modelo; e a análise dos tempos computacionais para a verificação e consulta de
resultados.
Em relação à expressão provida pelo modelo, é tratada a lógica temporal
proposta por (ARAÚJO, 2011), apresentada na seção 2.4.1. A Tabela 6 mostra algumas
restrições que podem ser expressas em fórmulas consideradas na implementação.
Restrição
Fórmula
Existe a possibilidade de haver um ponto EF{Joy≥100 }
com a felicidade muito alta ao longo da
história.
Em todas as histórias possíveis, não há A{Romance =0}U{Joy≥60 }
romance até que a felicidade seja alta.
Existe a possibilidade de que a história EF({Romance=0}and
tenha,
em
algum
ponto,
nenhum (A {Romance<30}U{Joy ≥60 }))
romance; e que, a partir desse ponto, o
romance é sempre baixo até que a
felicidade seja alta.
Há a possibilidade de que haja felicidade EF({Joy>50 and Romance<30} and
sem romance em algum momento, e um (EF{Romance≥50} and
momento posterio no qual há romance e, (AG{Romance≥Tension} and
a partir de então o romance seja sempre (A end{Joy>50}))))
maior que a tensão, que é sempre alta, até
que seja alcançado um final feliz.
Tabela 6. Exemplos de restrições e fórmulas equivalentes representadas no modelo.
67
Cabe notar que o modelo de conteúdo permite ainda que a variação abstrata das
propriedades dramáticas seja dada por expressões lineares envolvendo os valores de
outras propriedades. Ou seja, o modelo permite que o valor de uma propriedade
dependa também dos valores de uma ou mais propriedades diferentes (seção 3.1.3).
Assim, é possível expressar interdependência entre as propriedades dramáticas.
Relembra-se o exemplo do evento Try to Kidnap, apresentado na seção 3.1.3: no final
no qual o vilão não consegue raptar a vítima, o valor da felicidade da história é
incrementado de acordo com o o valor inicial da tensão, representando a resolução ‘feliz’
da tensão dramática acumulada.
Para efeito de implementação, assume-se a limitação de que as fórmulas internas
(aninhadas) também devem possuir apenas um quantificador mais geral. Uma fórmula
interna nesse formato pode conter uma conjunção de restrições aritméticas sobre
propriedades dramáticas em conjunção com uma única fórmula com um quantificador
mais geral. Isso permitiu uma implementação recursiva (seção 4.3), conforme explicado
na descrição do algoritmo de satisfação (Algoritmo 4-7). Essa restrição não é, no
entanto, obrigatória no modelo.
Apesar da limitação imposta, considera-se que as fórmulas que podem ser
expressas nesse formato provêm um bom poder de expressão para aplicação no contexto
de Storytelling interativo. Os exemplos na Tabela 6 demonstram restrições que podem
ser expressas nesse formato. Nota-se que a limitação a apenas um quantificador mais
geral por nível não interfere na capacidade da lógica de expressar restrições sequenciais
(nas quais algo deve valer em um momento, e outra restrição deve valer a partir daquele
ponto).
Além disso, cabe salientar que a implementação não admite fórmulas com
disjunção interna entre as restrições aritméticas sobre propriedades dramáticas.
Relembra-se que o tratamento de restrições que devem valer ao longo de um intervalo é
realizado aplicando-se a restrição aos limites desse intervalo. Ou seja, considerando que,
dado que as variações das propriedades dramáticas são lineares, algo que vale em um
intervalo deve obrigatoriamente valer no começo e no fim daquele intervalo.
Restrições representadas com fórmulas com disjunção interna, no entanto, tais
como fórmulas do tipo AG(α or β), não podem ser tratadas desta maneira. Uma
alternativa para tratar esse tipo de fórmula seriam mecanismos de dupla negação, ou
68
seja, verificar, por exemplo, o que é necessário para que AG(α or β) valha através da
verificação do que é necessário para que EF(¬α and ¬ β) não valha. A implementação
de mecanismos de verificação abstrata para tal não chegou, no entanto, a ser investigada.
Para demonstrar o poder de expressão do modelo implementado, é apresentado
um exemplo, com os respectivos resultados gerados. Demonstra-se o resultado da
verificação de fórmulas sobre um evento específico não determinístico do gênero
Swords and Dragons: Fight to the Death.
Figura 5.1. Autômato descrevendo as possíveis execuções de dramatização do evento
Fight to the Death.
69
Demonstra-se no autômato a variação das propriedades Joy (a felicidade da
história) e Fear (o nível de medo). No evento, há três estados finais possíveis: s2, s3 e
s4. Além disso, devido à restrição na transição que leva de s1 para s2, o caminho até
um final pode ser condicionado a restrições sobre propriedades de contexto1.
A árvore de execução TFight to the Death gerada a partir do autômato do evento Fight
to the Death é dada na Figura 5.2. As durações das transições são suprimidas, bem como
informações sobre os caminhos até as folhas (o componente EndPaths de cada transição
da árvore). Esta árvore assume uma duração máxima para o evento de 60 segundos.
Figura 5.2 Árvore de execução gerada a partir do autômato do evento Fight to the Death.
1
A restrição, representada na Figura 5.1 pelo termo [a], representa que o personagem defensor B não
gosta do personagem A, e portanto não evita matá-lo. Essa restrição existe pois, nas histórias de Swords
and Dragons, um personagem pode atacar outro que não lhe deseja mal. Por exemplo: caso um bom
cavaleiro A ataque (por estar amaldiçoado, ou ter sido enganado, etc.) um outro cavaleiro B, o cavaleiro
defensor B tenta vencer a luta sem matá-lo (e, tragicamente, invariavelmente acaba morto).
70
Os resultados para essa verificação são dados na Tabela 7.
Situação
Expressão:
(Ctr)
(RCtx, Sf, Resid)
{Joy0≥50.0,
([a],s2,EG{Fear>Joy}) or
Fear0 > Joy0}
([],s3,EG{Fear>Joy}) or
([],s4,EG{Fear>Joy}) or
(
([a], s2, AF({Joy≥50.0} and EG{Fear>Joy})) and
([], s3, AF({Joy≥50.0} and EG{Fear>Joy})) and
([], s4, AF({Joy≥50.0} and EG{Fear>Joy}))
)
{Joy0≥50.0,
([a],s2,EG{Fear>Joy}) or
Fear0 ≤ Joy0,
([],s3,EG{Fear>Joy}) or
Fear0+10>Joy0}
([],s4,EG{Fear>Joy})
{Joy0≥50.0,
([a], s2, AF({Joy≥50.0} and EG{Fear>Joy})) and
Fear0≤0.68*Joy0+18.18}
([], s3, AF({Joy≥50.0} and EG{Fear>Joy})) and
([], s4, AF({Joy≥50.0} and EG{Fear>Joy}))
{Joy0 < 50.0}
([a], s2, AF({Joy≥50.0} and EG{Fear>Joy})) and
([], s3, AF({Joy≥50.0} and EG{Fear>Joy})) and
([], s4, AF({Joy≥50.0} and EG{Fear>Joy}))
Tabela 7. Resultados da verificação de AF ({Joy ≥ 50} and EG {Fear ≥ Joy }) sobre o
evento Fight to the Death.
A implementação dos algoritmos foi gerada na linguagem programação em
lógica Prolog; utilizando-se o interpretador SWI-Prolog (para o processo de verificação)
e o interpretador SICStus Prolog (para a consulta). Em ambos os casos, utilizou-se a
biblioteca de programação em lógica com restrições CLP(R) (que possui versões para
ambas as distribuições Prolog utilizadas) para o tratamento da variação abstrata das
propriedades dramáticas. Todos os testes foram realizados em um computador pessoal
HP Pavilion dv6 Notebook PC, com processador Intel(R) Core(TM) i7-2670QM
2.20GHz e 8GB de memória RAM. Como os tempos de execução para o algoritmo de
verificação são consideráveis, o algoritmo do processo exaustivo de verificação
(Algoritmo 4-1) foi modificado para realizar a contagem do tempo.
Foi gerado o preprocessamento para o gênero Swords and Dragons que é uma
extensão do proposto por (SILVA, 2011), tendo sido criados autômatos específicos para
71
a dramatização de cada um dos eventos. Sobre os eventos desse gênero foram
verificadas as seguintes restrições típicas:
•
Há a possibilidade da história ser feliz em algum instante; representada
pela fórmula EF {Joy ≥ 70};
•
O nível de tensão, em todas as histórias possíveis, nunca é muito baixo;
representada pela fórmula AG {Tension > 40};
•
O nível de tensão, em todas as histórias possíveis, nunca é muito alto;
representada pela fórmula AG {Tension < 80};
•
Existe pelo menos uma história na qual a alegria se torna alta e, a partir
de então, em pelo menos uma história, não fica nunca muito baixa;
representada pela fórmula EF ({Joy ≥ 60 } and EG {Joy ≥ 35}).
O tempo de verificação para esse conjunto de quinze eventos foi de 4 horas e 20
minutos, com alta variação no tempo necessário para a geração dos resultados para um
evento. A demora do processo se deve à explosão combinatorial intrínseca ao processo
de verificação abstrata: para cada árvore de execução, em cada transição, são geradas
múltiplas alternativas de continuação (que dividem as situações). Fórmulas mais
complexas (com maior aninhamento) geram mais alternativas, e portanto são mais
custosas.
O tempo para a verificação de um evento aumenta de acordo com a
profundidade da árvore devido ao aumento da constraint store. Conforme a constraint
store se torna carregada, as operações sobre as constraints e sobre os resultados que as
contêm se tornam mais custosos. O tempo para esse geração poderia ser ainda maior,
em domínios nos quais os eventos são mais numerosos, complexos, ou longos (com
árvores mais profundas). Esse alto custo computacional é mitigado, no modelo, dada a
natureza offline do processo de verificação. Além disso, o problema é inerentemente
paralelizável: além de verificar cada restrição típica sobre cada evento em uma chamada
em paralelo, também seria possível verificar cada alternativa sobre cada sub-árvore em
um processo em separado.
O objetivo do modelo é permitir que o planejamento possa compor enredos
utilizando eventos nos quais há variação contínua de propriedades dramáticas,
considerando restrições sobre essas variações. Com o preprocessamento gerado pela
verificação offline, os resultados gravados podem ser consultados em tempo de
processamento. Relembra-se os resultados exemplo da Tabela 7. Considerando uma
72
base que contém estes resultados, as consultas são realizadas em tempo igual ou inferior
a 1 milisegundo.
Os resultados do processo de verificação para o gênero de Swords and Dragons
foram utilizados com sucesso em uma implementação especializada do planejador mais
atual do Logtell (FERREIRA, 2013). Nos testes de planejamento utilizando os
resultados para o gênero Swords and Dragons, são realizadas múltiplas consultas ao
conjunto de resultados, com tempo médio para cada consulta de 0,01s. Os resultados
indicam que a aplicação do modelo é viável no planejamento de histórias para
Storytelling interativo. Assim, constata-se que é viável o tratamento de variação
contínua de propriedades dramáticas, utilizando os resultados preprocessados
produzidos pelos algoritmos implementados neste trabalho.
73
6
Conclusões e Trabalhos Futuros
6.1 Considerações Gerais
Esta dissertação trata da verificação de propriedades sobre eventos de
storytelling interativo modelados como autômatos não determinísticos. O objetivo do
modelo proposto é possibilitar que um processo de planejamento automatizado
considere a variação contínua de propriedades ao longo de eventos sem precisar analisálos internamente.
Os algoritmos para a validação do modelo de conteúdo e de verificação foram
implementados para aplicação no sistema Logtell. Os resultados da dissertação, no
entanto, são independentes, podendo ser aplicados em outros sistema de Storytelling
Interativo dado que os pontos principais da hipótese sejam garantidos. São eles:
•
conhecimento do conjunto de eventos que podem ser utilizados para
compor a história;
•
conhecimento da variação das propriedades dramáticas ao longo desses
eventos, definidas como expressões lineares sobre valores iniciais;
conhecimento das restrições típicas sobre essas propriedades, expressas
em fórmula temporal CTL-estendida; e, por fim
•
a possibilidade de realizar o processo (computacionalmente custoso) de
verificação de modo offline.
O modelo proposto e os algoritmos implementados são, portanto, independentes
de contexto, podendo ser aplicados em quaisquer sistemas de storytelling que
representem as propriedades dramáticas e suas restrições na lógica CTL-estendida. O
modelo é capaz de representar e raciocinar sobre quaisquer conjuntos de propriedades,
desde que os eventos contenham a informação sobre sua variação; e desde que sejam
conhecidas as restrições típicas para as histórias daquele gênero.
A verificação realizada pelo modelo é exaustiva, no sentido de que garante que o
74
planejamento não necessitará de resultados que não foram previamente gerados. O
modelo e os algoritmos implementados garantem, portanto, a coêrencia entre o conjunto
de restrições típicas e as possíveis consultas. Isso é garantido pelo tratamento que
adiciona as fórmulas residuais de uma verificação ao conjunto de fórmulas a verificar,
durante o processo de verificação em alto nível.
O alto custo computacional para o processo de verificação é mitigado pela sua
natureza offline. Os resultados da verificação sobre um gênero são reutilizáveis,
servindo para todas as gerações de enredos futuras naquele gênero. O gênero pode ser
atualizado com novas fórmulas típicas (por exemplo, por nova inferência de
preferências de usuários); e apenas as novas fórmulas (e suas possíveis residuais)
precisam ser verificadas, em nova rodada do algoritmo, tendo os resultados adicionados
ao conjunto de resultados para aquele gênero. A atualização de eventos, no entanto, com
a modificação da variação das propriedades contínuas, implica na necessidade de reverificar novamente todas as fórmulas em relação ao evento modificado.
Os resultados gerados pelo processo de verificação são então utilizados pelo
planejamento, para composição de enredos. Os resultados indicam que a consideração
de restrições sobre a variação contínua de propriedades dramáticas em eventos não
determinísticos é possível, nesse modelo. O tempo necessário para realizar o processo
de consulta não impacta significativamente no tempo necessário para o planejamento de
enredos.
6.2 Principais Contribuições
Os resultados obtidos indicam a viabilidade de um tratamento offline para
possibilitar que o planejamento de enredos considere restrições sobre propriedades
dramáticas, que variam continuamente, ao longo de eventos não determinísticos.
Como principal contribuição do trabalho, tem-se o modelo e os algoritmos
desenvolvidos. O modelo de conteúdo permite a representação de propriedades
dramáticas com variação contínua ao longo de eventos não determinísticos, a expressão
de restrições típicas sobre estas propriedades em histórias de um gênero, e fundamenta
tanto o processo de verificação quanto a dramatização.
Os algoritmos desenvolvidos realizam a verificação abstrata das propriedaes
dramáticas com variação contínua, produzindo resultados a serem utilizados pelo
processo de planejamento para viabilizar a consideração de restrições temporais sobre
75
essas propriedades. Dada a natureza genérica do modelo, os algoritmos podem ser
aplicados em domínios diversos. Desde que sejam garantidos os pontos principais da
hipótese, os algoritmos podem ser utilizados para gerar a verificação exaustiva de
restrições conhecidas sobre um conjunto de eventos nos quais propriedades variam
continuamente.
Foi implementado um protótipo, para aplicação no domínio de Storytelling
Interativo, associado ao sistema de Storytelling Interativo independente de contexto
Logtell. A utilização do protótipo demonstra a viabilidade da geração de enredos não
determinísticos, respeitando os limites de tempo impostos pelo ciclo de geraçãodramatização em paralelo.
Com o uso do protótipo associado ao planejador mais atual do sistema Logtell
(FERREIRA, 2013), o processo de geração produz histórias satisfazendo restrições
complexas sobre a variação de propriedades dramáticas, utilizando os resultados da
verificação offline. Este protótipo serve de base de testes e indica possíveis
aprimoramentos a serem aplicados no modelo, descritos na seção a seguir.
6.3 Trabalhos Futuros
O
trabalho
pode
ser
complementado,
em
diversos
aspectos,
por
desenvolvimentos futuros adicionais. O primeiro ponto a ser explorado deve ser a
completude da gramática da lógica CTL-estendida, buscando prover maior poder de
expressão autoral.
Para tanto, é necesário definir um algoritmo de satisfação que permita o
tratamento de fórmulas com mais de um quantificador mais geral por nível. A resolução
deste problema relaciona-se a outra restrição assumida neste trabalho, que também pode
ser futuramente eliminada: o tratamento de disjunções internas nas restrições de
fórmulas. Para tanto, é necessário que esse tratamento não incorra em custos
computacionais adicionais significativos que inviabilizem o processo.
Também relacionado ao poder de expressão provido pelo modelo, a gramática
da lógica CTL-estendida pode ser incrementada com novos operadores. Aproveitandose da característica de tratamento de tempo contínuo, propõe-se a definição de
operadores de estado que tratam de restrições concomitantes e ‘janelas de tempo’:
76
•
W: operador while, aplicado sobre os termos (α,β) na forma (α W β).
Definindo que a restrição α deve ser garantida sempre que se verifica β,
como uma forma alternativa de expressar relações until sem a
necessidade de negação;
•
D: operador during, aplicado sobre os termos (α, n) na forma (α D n).
Define que a restrição α deve ser garantida por n segundos.
O processo de verificação pode ser otimizado através da aplicação de
simplificações nas constraints adicionadas à constraint store. Como o tamanho da
constraint store acarreta em um maior tempo de processamento, as chamadas ao
algoritmo de verificação em árvores de execução mais profundas acabam por tomar um
tempo muito maior do que em árvores menores. O mecanismo para essa simplificação
seria a verificação de consequências lógicas: se um conjunto de constraints é
consequência lógica de um outro, apenas o primeiro precisa ser afirmado.
A simplificação de constraints pode também otimizar os processos de
composição, diminuindo o número de resultados distintos. As combinações multiplicam
o número de resultados, o que pode fazer com que composições de grandes conjuntos
tomem um tempo significativo.
Essa simplificação pode ser realizada quando situações distintas, dadas por
conjuntos de constraints distintas, resultam na mesma expressão de resultado (mesmas
fórmulas residuais a serem verificadas a partir dos mesmos finais). Para tanto, podem
ser aplicadas técnicas de regras de manipulação de constraints (constraint handling
rules) para agrupar os resultados em um mesmo intervalo quando possível. Essa
simplificação implicaria também em uma potencial melhora no processo de consulta, já
que, havendo menos resultados a considerar, o tempo médio para determinar qual é a
situação aplicável potencialmente diminui.
Outra otimização que pode ser aplicada referente ao processo de consulta é a
composição dos resultados em uma estrutura que facilita a busca do resultado aplicável
no estado corrente do mundo. Relembra-se que as alternativas geradas a cada etapa do
algoritmo de verificação representam situações mutuamente exclusivas, e diferentes
resultados gerados a partir de uma mesma alternativa compartilham parte das restrições
associadas a eles.
Assim, o processo de consulta pode ter de afirmar diversas vezes o mesmo
conjunto de restrições até encontrar o resultado aplicável no estado do mundo corrente.
77
A organização dos resultados em relação às constraints que compartilham, de forma
hierarárquica (como em uma árvore de decisões), potencialmente diminuiria o número
de constraints a serem afirmadas em cada resultado; e assim também diminuiria o
tempo médio para a realização das consultas.
O protótipo implementado pode ser aprimorado em relação ao seu uso,
promovendo maior coêrencia entre os níveis lógico e de dramatização. A utilização do
modelo proposto pode fornecer informação sobre a variação das propriedades
dramáticas aos módulo de dramatização do Logtell, de forma que elementos gráficos e
sonoros (posição da câmera, iluminação, música) possam ser adaptados de acordo com
essa variação, de acordos com modelos sugeridos em (LIMA et al., 2009a; LIMA et al.,
2009b; LIMA et al., 2010; LIMA et al., 2011; LIMA et al., 2012a; e LIMA et al.,
2012b).
Por fim, aproveitando-se da abordagem genérica do modelo, pode-se pensar na
aplicação do modelo de verificação offline de restrições sobre propriedades com
variação contínua em domínios diversos. Quaisquer sistemas nos quais eventos não
determinísticos precisam ser combinados através de planejamento automatizado,
considerando a variação contínua de propriedades, podem aproveitar-se do modelo e
dos algoritmos propostos. Exemplos de contextos onde isso ocorre são sistemas que
envolvem processos físicos com variáveis contínuas que precisam ser devidamente
controladas.
78
7
Referências
ALUR, R.; HENZINGER, T.A.; HO, P.-H., 1993, “Automatic Symbolic Verification of
Embedded Systems”. In: Proceedings of the 14th Annual Real-Time Systems Symposium
(RTSS). IEEE Computer Society Press, 1993, pp. 2-11 (1993).
ARAÚJO, E.T., CIARLINI, A.E.M., 2011, “Verification of Temporal Constraints in
Continuous Time on Nondeterministic Stories”. In: Proceedings of the 10th
International Conference on Entertainment Computing, pp. 28-34, Vancouver, Oct.
ARAÚJO, E.T., 2011, Verificação de Restrições Temporais com Tempo Contínuo em
Histórias Não-Determinísticas. Dissertação de M.Sc., Departamento de Informática,
Universidade Federal do Estado do Rio de Janeiro, RJ, Brasil.
ARISTÓTELES., BUTCHER, S.H., 2011, The Poetics. 1 ed. Seattle, CreateSpace
Independent Publishing Platform.
AYLETT, R., DIAS, J., PAIVA, A., 2006, “An Affectively Driven Planner for
Synthetic Characters”. In: ICAPS, Cumbria, UK, p.2-10, AAAI.
BARROS, L.M., MUSSE, S.R., 2008, “Towards consistency in interactive storytelling:
Tensão arcs and dead-ends”, Computers in Entertainment, v. 6, n. 3 (Oct), article n. 43.
BENFORD, S., GIANNACHI, G., 2008, “Temporal trajectories in shared interactive
narratives”. In: Proceedings of the SIGCHI Conference on Human Factors in
Computing Systems, Florence, Italy, pages 73--82, ACM.
BOUYER, P., 2009, “Model-Cheking Timed Temporal Logics”. Electron. Notes
Theoretical Computer Science, 231:323-341.
BRANIGAN, E., 1992, Narrative Comprehension and Film. 1 ed. New York,
Routledge.
CAMANHO, M. M., 2009, “Conciliando coerência e responsividade em storytelling
interativo
79
para TV digital.”. Dissertação de M.Sc., Departamento de Informática, Universidade
Federal do Estado do Rio de Janeiro, RJ, Brasil.
CAMANHO, M.M., CIARLINI, A.E.M., FURTADO, A.L., et al., 2009, “A model for
Interactive TV Storytelling”. In: Proceedings of the 7th Brazilian Symposium on Games
and Digital Entertainment. Rio de Janeiro, Brasil.
CATALDI, M., DAMIANO, R., LOMBARDO, V., et al., 2011, “Representing
Dramatic Features of Stories through an Ontological Model”. In: Proceedings of the
Fourth International Conference on Interactive Digital Storytelling, pp. 122-127,
Vancouver, Nov.
CHARLES, F., IBÁÑEZ, M.L., MEAD, S. J., et al., 2003, “Planning formalisms and
authoring in Interactive Storytelling”. In: Proceedings of TIDSE’03: Technologies for
Interactive Digital Storytelling and Entertainment, Darmstadt, Alemanha.
CHEONG, Y.G., YOUNG, R.M., 2008, “Narrative Generation for Suspense: Modeling
and Evaluation”. In: Proceedings of the 1st Joint International Conference on
Interactive Digital Storytelling, pp. 144-155, Erfurt, Nov.
CHEONG, Y.G., 2007, A Computational Model Of Narrative Generation For Suspense.
Ph.D. thesis, Department of Computer Science, North Carolina State University,
Raleigh, North Carolina, USA.
CHRISTEL, B., KATOEN, J., 2008, “Principles of Model Checking”. MIT Press.
CIARLINI, A.E.M, CASANOVA, M.A., FURTADO, A.L., et al., 2010, “Modeling
interactive storytelling genres as application domains”, Journal of Intelligent
Information Systems, v. 35, n. 3 (Dec), pp. 347-381.
CIARLINI, A.E.M., CAMANHO, M.M., DÓRIA, T.R., et al., 2008, “Planning and
Interaction Levels for TV Storytelling”. In: Proceedings of the 1st Joint International
Conference on Interactive Digital Storytelling, pp. 198-209, Erfurt, Nov.
CIARLINI, A.E.M., POZZER, C.T., FURTADO, A.L., et al., 2005, “A logic-based tool
for interactive generation and dramatization of stories”. In: Proceedings of the 2nd
International Conference on Advances in Computer Entertainment Technology, pp.
133-140, Valencia, Jun.
CIARLINI, A.E.M., 1999, Geração Interativa De Enredos. Tese de D.Sc.,
Departamento de Informática, Pontifícia Universidade Católica, RJ, Brasil.
80
CLARKE, E. M., EMERSON, E. A., 1981, “Design and Synthesis of Synchronization
Skeletons Using Branching Time Temporal Logic”. In: IBM Logics of Programs
Workshop, Springer LNCS #131, pp.5-71.
CLARKE, E. M., EMERSON, E. A., 1986. “Automatic Verification of finite-state
concurrent systems using temporal logic specifications”. In: ACM Transactions on
Programming Languages and Systems 8:244-263.
DÓRIA, T.R., CIARLINI, A.E.M., ANDREATTA, A., 2008, “A nondeterministic
model for controlling the dramatization of interactive stories”. In: Proceedings of the
2nd ACM Workshop on Story Representation, Mechanism and Context, pp. 21-26,
Vancouver, Oct.
EMERSON, E. A., 2009, “Model Checking: Progress and problems”. In: VMCAI –
Verification, Model Checking and Abstract Interpretation.
EMERSON, E. A., 1995, “Temporal and Modal Logic”. In: Handbook of Theoretical
Computer Science. Elsevier.
FERREIRA, P., 2013, “Planejamento de Histórias não Determinísticas com
Propriedades Dramáticas em mudança contínua”. Dissertação de M.Sc., Departamento
de Informática, Universidade Federal do Estado do Rio de Janeiro, RJ, Brasil.
FERREIRA, P., GOTTIN, V.M., CIARLINI, A.E.M., et al., 2013, “A Nondeterministic
Temporal Planning Model for Generating Narratives with Continuous Change in
Interactive Storytelling”. In: Proceedings of the 9th AAAI Conference on Artificial
Intelligence and Interactive Digital Entertainment. No prelo.
GERVÁS, P., 2009, “Computational Approaches to Storytelling and Creativity”, AI
Magazine, v. 30, n. 3 (Sep), pp. 49-62.
GILROY, S., PORTEOUS, J., CHARLES, F., et al., 2012, “Exploring Passive User
Interaction for Adaptive Narratives”. In: Proceedings of the Proceedings of the 17th
International Conference on Intelligent User Interfaces, pp. 119-128, New York, Feb.
GRUMBER, O., VEITH, H. (org)., 2006, “25 Years of Model Checking”, Symposium.
Federated Logic Conference, Seattle.
HARTSOOK, K., ZOOK, A., DAS, S., et al., 2011, “Toward Supporting Stories with
Procedurally Generated Game Worlds”. In: Proceedings of the IEEE Conference on
Computational Intelligence and Games, pp. 297-304, New York, Sep.
81
KARLSSON, B., CIARLINI, A. E. M., FEIJÓ, B., FURTADO, A. L., 2006. “Applying
a plan-recognition/plan-generation paradigm to interactive storytelling”. In: ICAPS
2006 - Workshop on AI Planning for Computer Games ans Synthetic Characters.
KING, J. C., 1976, “Symbolic execution and program testing”. In: Communications of
the ACM 19, 7:385-394.
KOZEN, D., 1983, “Results on the propositional µ-calculus”. In: Thoretical Computer
Science, v.27, 3:333-354.
KONUR, S., 2008, “Real-time and Probabilistic Temporal Logics: An Overview”.
Department of Computer Science, University of Liverpool.
KRIEGEL, M., AYLETT, R., DIAS, J, et al., 2007, “An Authoring Tool for an
Emergent Narrative Storytelling System”. Heriot-Watt University, Edinburgh; and
INESCID IST, Taguspark, Porto Salvo, Portugal.
LIMA, E. S, POZZER, C. T., D’ORNELLAS, M. C., et al., 2009, “Support Vector
Machines
for
Cinematography
Real-Time
Camera
Control
in
Storytelling
Environments”. In: VIII Brazilian Symposium on Games and Digital Entertainment
(SBGAMES 2009), Rio de Janeiro, Brazil, p. 44-51.
LIMA, E. S., POZZER, C. T., D’ORNELLAS, M. C., et al., 2009, “Virtual
Cinematography Director for Interactive Storytelling”. In: Proceedings of the
International Conference on Advances in Computer Entertainment Technology (ACE
2009), Athens, Greece, p. 263-270.
LIMA, E. S., POZZER, C. T., FEIJÓ, B., et al, 2010, “Director of Photography and
Music Director for Interactive Storytelling”. In: IX Brazilian Symposium on Games and
Digital Entertainment (SBGAMES 2010), Florianópolis, Brazil, p. 122-131.
LIMA, E.S., FEIJO, B., BARBOSA, S., et al., 2011, “Draw Your Own Story: Paper and
Pencil Interactive Storytelling”. In: 10th International Conference on Entertainment
Computing (ICEC 2011), Vancouver, Canada. p. 1-12.
LIMA, E.S., FEIJO, B., POZZER, C.T., et al., 2012, “Social Interaction for Interactive
Storytelling”. In: Proceedings of the 11th International Conference on Entertainment
Computing, pp. 1-15, Bremen, Sep.
LIMA, E.S., FEIJO, B., FURTADO, et al., 2012, “Automatic Video Editing For VideoBased Interactive Storytelling”. In: Proceedings of the 2012 IEEE International
Conference on Multimedia and Expo (ICME 2012), Melbourne, Australia, p. 806-811.
82
LIMBERGER, R., POZZER, C. T., FEIJÓ, B., et al., 2010. “Um Modelo de Diretor
para Personagens Figurantes em Narrativa Interativa”. In: IX Brazilian Symposium on
Games and Digital Entertainment (SBGAMES 2010), Florianópolis, Brazil, p. 141-144.
MAGERKO, B., 2007, “Measuring Dramatic Believability”. In: Proceedings of the
AAAI Fall Symposium, pp. 79-82, Menlo Park, Nov.
MARRIOT, K., STUCKEY, P.J., 1998, Programming with Constraints. 1 ed.
Cambridge, The MIT Press.
MATEAS, M., STERN, A., 2005, “Structuring Content in The Façade Interactive
Drama Architecture”. In: Proceedings of the 1st AAAI Conference on Artificial
Intelligence and Interactive Digital Entertainment.
MCMILLAN, K.L., 1993, Symbolic Model Checking. 1 ed. Dordrecht, Kluwer
Academic.
O’NEIL, B., RIEDL, M., 2011, “Toward a computational framework of suspense and
dramatic arc”. In: Proceedings of the International Conference on Affective Computing
and Intelligent Interaction, pp. 246-255, Memphis, Oct.
ØHRSTRØM, O., HASLE, P. F. V., 1995, “Temporal logic: from ancient ideas to
artificial intelligence”. Springer.
PETTA, P. IRIS publication database on Interactive Storytelling. Disponível em:
<http://iris.ofai.at:7777/iris_db/index.php/>. Acesso em: 21 setembro 2013.
PIZZI, D., 2011, Emotional Planning for Character-based Interactive Storytelling.
Ph.D. dissertation, School of Computing, Teesside University, Middlesborough, UK.
PIZZI, D, CAVAZZA, M., WHITTAKER, A., et al., 2006, “Automatic Generation of
Game Level Solutions as Storyboards”. In: AIIDE, Stanford, California, USA, pages
96-101, The AAAI Press.
PLUTCHIK, R., 1962, “The emotions: Facts, theories, and a new model”. New York,
Random. House.
PORTEOUS, J., TEUTENBERG, J., CHARLES, F., et al., 2011, “Controlling
Narrative Time in Interactive Storytelling”, In: Proceedings of the 10th International
Conference on Autonomous Agents and Multiagent Systems, pp. 449-456, Taipei, May.
PORTEOUS, J., CAVAZZA, M., CHARLES, F., 2010, “Applying planning to
interactive storytelling: Narrative control using state constraints”, ACM Transactions on
Intelligent Systems and Technology, v. 1, n. 2 (Dec), pp. 10:1-10:21.
83
PORTEOUS, J., CAVAZZA, M., 2009, “Controlling Narrative Generation with
Planning Trajectories: The Role of Constraints”. In: Proceedings of the 2nd Joint
International Conference on Interactive Digital Storytelling, pp. 234-245, Guimarães,
Dec.
PROPP, V., 2003, Morphology of the Folktale. 2 ed. Austin, University of Texas Press.
RAMAKRISHNAN, C. R., “Model Checking with Tabled Logic Programming”. DCS
SUNY, Stony Brook, NY.
RIEDL, M., Young, R.M., 2004, “An Intent-Driven Planner for Multi-Agent Story
Generation”. In: Proceedings of the 3rd International Joint Conference on Autonomous
Agents and Multiagent Systems, pp. 186-193, New York, Jul.
RIEDL, M. STERN, A., 2006, “Believable agents and intelligent story adaptation for
Interactive Storytelling”. In: Proceedings of the Third International Conference on
Technologias for Interactive Digital Storytelling and Entertainment (TIDE’06).
Springer-Verlag, Berlin, 1-12.
ROBERTS, D.L., ISBELL, C.L., 2008, “A Survey and Qualitative Analysis of Recent
Advances in Drama Management”, International Transactions on Systems Science and
Applications, v. 4, n. 1 (May), pp. 61-75.
RODRIGUES, P. S. L., 2008: “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.
SICSTUS. SICStus Prolog. Disponível em: < http://sicstus.sics.se/ >. Acesso em: 26
setembro 2013.
SILVA, M.A.R., LIMA, D.C., SILVA, J.C.A., et al., 2011, “A Narrative Game as an
Educational Entertainment Resource to Teach Words to Children with Learning
Deficits: A Feasibility Study”. In: Proceedings of the 10th International Conference on
Entertainment Computing, pp. 222-227, New York, Oct.
SILVA, F.A.G., CIARLINI, A. E. M., SIQUEIRA, S.W.M., 2010, “Nondeterministic
Planning for Generating Interactive Plots”. In: Proceedings of the 12th Ibero-American
Conference on Artificial Intelligence, pp. 133-143, Bahía Blanca, Nov.
SILVA, F.A.G., 2010, Geração de Enredos com Planejamento Não-Determinístico em
Storytelling para TV Interativa. Dissertação de M.Sc., Departamento de Informática,
Universidade Federal do Estado do Rio de Janeiro, RJ, Brasil.
84
SPIERLING, U., 2005. Interactive Digital Storytelling: Towards a Hybrid Conceptual
Approach. In: Conference Proceedings, Selected Papers of DIGRA 2005, Vancouver,
BC, Canada
SPIERLING, U., GRASBON, D., BRAUN, N., et al., 2002, “Setting the Scene: Playing
Digital Director in Interactive Storytelling and Creation”. In: Computers and Graphics,
26:1(31-44).
URSU, M.F., THOMAS, M., KEGEL, I. et al., 2008, “Interactive TV narratives:
Opportunities, progress and challenges”. In: ACM Transactions in Multimedia
Computing, Communications and Applications, 4:4(25:1-125:39).
VIDAL, E. C. E., NAREYEK, A., 2011, “A Real-Time Concurrent Planning and
Execution Framework for Automated Story Planning for Games”. In: Proceedings of
the AIIDE Workshop on Narrative Technologies IV (INT IV).
VENTURA, D., BROGAN. D.C., 2002, “Digital Storytelling with DINAH: dynamic,
interactive, narrative authoring heuristic”. In: IWEC, Makuhari, Japão, p.91-99.
WARE, S.G., YOUNG, R.M., 2011, “CPOCL: A Narrative Planner Supporting
Conflict”. In: Proceedings of the 7th AAAI Conference on Artificial Intelligence and
Interactive Digital Entertainment, pp. 97-102, Stanford, Oct.
WARE, S.G., YOUNG, R.M., 2010, “Modeling Narrative Conflict to Generate
Interesting Stories”. In: Proceedings of the 6th AAAI Conference on Artificial
Intelligence and Interactive Digital Entertainment, pp. 277-298, Stanford, Oct.
YUAN, J., SCHULTZ, K., PIXLEY, C. et al., 1999, “Modelling Design Constraints and
Biasing in Simulation Using BDDS”.
ZAGALO, N., BARKER, A., BRANCO, V., 2004, “Story reaction structures to
emotion detection”. In: Proceedings of the 1st ACM workshop on Story representation,
mechanism and context, pp. 33-38, New York, Oct.
85