ads:
CENTRO UNIVERSITÁRIO DA FEI
MARCEL LIRA GOMES
EXTRAÇÃO DE CONHECIMENTO DE DOMÍNIOS DE PLANEJAMENTO
DESCRITOS EM UML.P
São Bernardo do Campo
2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
1
MARCEL LIRA GOMES
EXTRAÇÃO DE CONHECIMENTO DE DOMÍNIOS DE PLANEJAMENTO
DESCRITOS EM UML.P
Dissertação de Mestrado apresentada a o
Centro Universitário da FEI para
obtenção do título de Mestre em
Engenharia Elétrica, orientado pelo Prof.
Dr. Flávio Tonidandel.
São Bernardo do Campo
2008
ads:
2
Marcel Lira Gomes
Extração de conhecimento de domínios de planejamento descritos em UML.P
Dissertação de Mestrado – Centro Universitário da FEI.
Comissão Julgadora
________________________________________________
Dr. Flávio Tonidandel
________________________________________________
Dr. José Reinaldo Silva
________________________________________________
Dr. Paulo Eduardo Santos
São Bernardo do Campo
2008
3
RESUMO
Neste trabalho desenvolveu-se um método que permite a inferência de conhecimento de
domínios para planejamento automático em Inteligência Artificial modelados nos Diagramas
de Classes e Objetos da UML.P. Para este desenvolvimento foi necessária a interpretação da
UML.P para uma linguagem formal, devido à característica de linguagem semi-formal
herdada da UML. Devido ao suporte a objetos, usou-se a F-Logic, que é uma lógica de 1ª.
Ordem baseada em frames, como a lógica de interpretação dos Diagramas de Classes e
Objetos. Dessa forma, se possibilitou a inferência de conhecimentos dos Diagramas de
Classes e de Objetos da UML.P. Dos diagramas são inferidas restrições através dos seguintes
elementos e propriedades: classes e suas hierarquias, propriedades de herança, associações,
mutabilidade e multiplicidade das associações e atributos. Estas restrições caracterizam-se por
permitir que sejam determinadas em que classes os objetos são membros e as características
que são herdadas das classes que eles descendem. Também é possível inferir restrições
simples quanto ao tipo dos objetos, além de determinar a igualdade de objetos através das
restrições inferidas da multiplicidade. Pela multiplicidade são definidas restrições quanto a
quantidade de ligações entre os objetos. A propriedade de mutabilidade fornece informações
adicionais ao domínio, quanto a forma que as ligações entre objetos podem ser alteradas
quando da aplicação da ação num domínio, o que possibilita a definição de restrições
baseadas nesta informação. Por fim são comparadas as restrições obtidas dos diagramas com
as restrições obtidas pelas ferramentas TIM e DISCOPLAN. O trabalho é concluído
discutindo os resultados obtidos e sugerindo os próximos passos para a geração de uma
ferramenta que permita a verificação interna de um modelo de domínio.
Palavras-chave: Inferência de Conhecimento. UML.P.
4
ABSTRACT
In this work a method was developed for knowledge inference from Artificial Intelligence
domains for automatic planning described in Class Diagram and Objects Diagrams of the
UML.P. For this development the interpretation of the UML.P for a formal language was
necessary, due to the semiformal language characteristic inherited from UML. On account of
the support of objects, it was used F-Logic, that is 1st. Order logic based on frames, as the
logic of interpretation for the Class Diagrams Objects. Therefore, it was made possible the
inference of knowledge from the Class Diagram and Objects Diagrams of the UML.P. From
the diagrams, the restrictions are inferred through the following elements and properties:
classes and its hierarchies, properties of inheritance, associations, mutability and multiplicity
of the associations and attributes. These restrictions are characterized for allowing the
determination of which classes the objects are members and the characteristics that are
inherited from classes that they descend. It is also possible to infer simple restrictions based
on the type of objects, beyond determining the object equality through the inferred restrictions
of the multiplicity. By the multiplicity, it is also defined restrictions of the amount of links
between objects. The mutability property supplies additional information to the domain, of the
form that the links between objects can be modified when an action is applied in a domain,
allowing the definition of restrictions based in this information. Finally, it is compared the
gotten restrictions from the diagrams with the restrictions gotten by the tools TIM and
DISCOPLAN. The work is concluded arguing the results and suggesting the next steps for the
generation of a tool that allows the internal verification of a domain model.
Key words: Knowledge inference. UML.P.
5
LISTA DE FIGURAS
Figura 1. Classificação dos diagramas da UML ................................................................. 34
Figura 2. Diagramas da UML.P ......................................................................................... 36
Figura 3. Diagrama de Classes de um domínio de Logística .............................................. 37
Figura 4. Símbolo de classe ............................................................................................... 37
Figura 5. Exemplo de classe .............................................................................................. 38
Figura 6. Exemplo de generalização .................................................................................. 39
Figura 7. Exemplo de associação ....................................................................................... 41
Figura 8. Exemplo de Diagrama de Estado de Máquinas ................................................... 42
Figura 9. Exemplo de estado ............................................................................................. 42
Figura 10. Exemplo da representação gráfica de uma transição ........................................ 43
Figura 11. Exemplo de estado inicial ............................................................................... 44
Figura 12. Exemplo de estado final .................................................................................. 44
Figura 13. Exemplo de diagrama de objetos ..................................................................... 44
Figura 14. Exemplo de instâncias..................................................................................... 45
Figura 15. Exemplo de generalização ............................................................................... 64
Figura 16. Exemplo UML.P de domínio de logística ........................................................ 71
Figura 17. Exemplo de estado de um domínio de logística ............................................... 80
Figura 18. Exemplo de tipos e hierarquias........................................................................ 81
Figura 19. Exemplo de objeto .......................................................................................... 84
Figura 20. Exemplo de propagação de atributos e associações ......................................... 87
Figura 21. Exemplo domínio de logística ......................................................................... 89
Figura 22. Exemplo de atributo com mesmo nome em classes distintas............................ 90
Figura 23. Exemplo de restrição pela multiplicidade ........................................................ 91
Figura 24. Exemplo de associação entre objetos............................................................... 92
Figura 25. Exemplo mundo dos blocos ............................................................................ 96
Figura 26. Exemplo de restrição por elemento diagramático ............................................ 98
Figura 27. Exemplo de associação com uma única classe ................................................. 99
6
LISTA DE TABELAS
Tabela 1. Formação da estrutura de relação de propriedades ........................................... 22
Tabela 2. Geração de regras de transição ........................................................................ 22
Tabela 3. Sementes do espaço de propriedades ............................................................... 23
Tabela 4. Geração de espaço de propriedades ................................................................. 24
Tabela 5. Determinação de propriedades do estado inicial .............................................. 24
Tabela 6. Exemplo de construção de tipos ...................................................................... 25
Tabela 7. Regras de inferência principais ....................................................................... 57
Tabela 8. Regras de inferência “é um” ............................................................................ 58
Tabela 9. Regras de inferência de tipos........................................................................... 58
Tabela 10. Outras regras de inferência .............................................................................. 59
Tabela 11. Assinaturas auxiliares ..................................................................................... 67
Tabela 12. Objetos auxiliares ........................................................................................... 68
Tabela 13. Interpretação de classes ................................................................................... 70
Tabela 14. Interpretação de atributos ................................................................................ 70
Tabela 15. Interpretação de operadores ............................................................................ 71
Tabela 16. Interpretação de associações ........................................................................... 73
Tabela 17. Interpretação de generalização ........................................................................ 75
Tabela 18. Interpretação de objetos .................................................................................. 79
Tabela 19. Interpretação de links ...................................................................................... 79
7
LISTA DE SÍMBOLOS
@ – Separador de método e parâmetros em F-Logic
; – Separador de atributos em F-Logic
: – Auxiliar de expressão “é-um” de objeto em F-Logic
:: – Auxiliar de expressão “é-um” de classe em F-Logic
-> – Auxiliar de expressão de dado escalar não herdável em F-Logic
->> – Auxiliar de expressão de conjunto de dados não herdável em F-Logic
*-> – Auxiliar de expressão de dado escalar herdável em F-Logic
*->> – Auxiliar de expressão de conjunto de dados herdável em F-Logic
=> – Define assinatura de dado escalar não herdável em F-Logic
=>> – Define assinatura de conjunto de dados não herdável em F-Logic
U – Domínio de uma F-Estrutura
U
– Relação irreflexível de ordem parcial que representa os relacionamentos em F-Logic
U
– Relação binária para modelar membros de uma classe em F-Logic
I
– Função de interpretação dos objetos em F-Logic
I
->
, I
*->
– Mapeamento de funções aos elementos de um domínio em F-Logic
I
->>
, I
*->>
– Mapeamento de funções aos elementos de um domínio em F-Logic
I
=>
, I
=>>
– Mapeamento das assinaturas dos métodos em F-Logic
id-terms – Termo usual de lógica de primeira ordem
mgu – Unificado Mais Geral
– Abreviação para -> e =>
– Abreviação para ->> e =>>
– Abreviação para *-> e =>
– Abreviação para *->> e =>>
nA_nCEO_nEOA – Abreviação para nome da Associação_nome da Classe da Extremidade
Oposta_nome da Extremidade Oposta da Associação
8
– Abreviação para os símbolos => ou =>>
– Abreviação para os símbolos -> ou ->>
// – Início de comentário de um F-Programa
– Função que determina as superclasses de uma classe
– Função que determina todas as subclasses de uma classe
– Função que determina as classes não pertencentes a uma hierarquia de classes
– Modelo de domínio passível de interpretação em F-Logic
c
– Recursos com definições dadas
– Modelo de domínio interpretável em F-Logic
– É super classe de
– É membro de
– Contém
9
SUMÁRIO
1 INTRODUÇÃO ............................................................................................................. 12
1.1 Motivação .................................................................................................................... 14
1.2 Objetivo ....................................................................................................................... 16
1.3 Organização do trabalho ............................................................................................ 16
2 ENGENHARIA DE CONHECIMENTO ..................................................................... 17
2.1 Processo de modelagem ............................................................................................... 17
2.2 Engenharia de conhecimento em planejamento......................................................... 18
3 EXTRAÇÃO DE CONHECIMENTO EM PLANEJAMENTO ................................. 20
3.1 TIM .............................................................................................................................. 21
3.1.1 Identificação dos tipos primitivos do domínio ........................................................... 21
3.1.2 Inferência da estrutura hierárquica dos tipos, baseado nos tipos primitivos................ 25
3.1.3 Inferência dos tipos de parâmetros dos operadores .................................................... 25
3.1.4 Inferência de estados invariantes ............................................................................... 26
3.2 DISCOPLAN ............................................................................................................... 27
3.2.1 Estados invariantes de tipo ........................................................................................ 28
3.2.2 Estados invariantes de estados do domínio ................................................................ 28
3.2.3 Modelo de suposição e teste...................................................................................... 29
3.2.4 Estados invariantes de implicação simples ................................................................ 29
3.2.5 Estados invariantes de valor único ............................................................................ 30
3.2.6 Estados invariantes de implicações de valor único .................................................... 30
3.2.7 Estados invariantes de anti-simetria .......................................................................... 31
3.2.8 Estados invariantes do tipo XOR .............................................................................. 31
3.3 Discussão ..................................................................................................................... 31
4 UML ............................................................................................................................... 33
4.1 UML.P ......................................................................................................................... 35
4.1.1 Diagrama de Classes ................................................................................................. 36
4.1.2 Classes ..................................................................................................................... 37
4.1.3 Generalização ........................................................................................................... 39
4.1.4 Associações .............................................................................................................. 39
4.1.5 Diagrama de Estados de Máquinas............................................................................ 41
4.1.6 Estado ...................................................................................................................... 42
4.1.7 Transição .................................................................................................................. 42
10
4.1.8 Estado Inicial ............................................................................................................ 43
4.1.9 Estado Final .............................................................................................................. 44
4.1.10 Diagrama de Objetos ................................................................................................ 44
4.1.11 Instância ................................................................................................................... 45
4.2 Discussão ..................................................................................................................... 45
5 F-Logic ........................................................................................................................... 48
5.1 Sintaxe ......................................................................................................................... 49
5.2 Semântica .................................................................................................................... 52
5.2.1 Satisfação das F-Moléculas pelas F-Estruturas .......................................................... 54
5.3 Regras de inferência .................................................................................................... 56
5.3.1 Regras de inferência principais ................................................................................. 57
5.3.2 Regras de inferência “é-um” ..................................................................................... 58
5.3.3 Regras de inferência de tipos .................................................................................... 58
5.3.4 Outras regras de inferência ....................................................................................... 59
5.4 Discussão ..................................................................................................................... 59
6 F-LOGIC E UML.P....................................................................................................... 63
6.1 Classes e assinaturas ................................................................................................... 63
6.2 Generalização .............................................................................................................. 64
6.3 Instâncias ..................................................................................................................... 65
7 INTERPRETAÇÃO DA UML.P EM F-LOGIC .......................................................... 66
7.1 Diagrama de classes .................................................................................................... 67
7.1.1 Classes ..................................................................................................................... 69
7.1.2 Associação ............................................................................................................... 71
7.1.3 Generalização ........................................................................................................... 75
7.1.4 Exemplo ................................................................................................................... 76
7.2 Diagrama de objetos ................................................................................................... 78
7.2.1 Objetos ..................................................................................................................... 78
7.2.2 Links ........................................................................................................................ 79
7.2.3 Exemplo ................................................................................................................... 79
8 EXTRAÇÃO DE CONHECIMENTO DO DIAGRAMA DE CLASSES DA UML.P 81
8.1 Conceitos fundamentais .............................................................................................. 81
8.2 Restrição por tipos ...................................................................................................... 83
8.2.1 Restrições pelas classes e hierarquias ........................................................................ 83
8.2.2 Restrições pela herança dos tipos .............................................................................. 87
11
8.3 Restrições por multiplicidade ..................................................................................... 91
8.4 Restrição pela mutabilidade do atributo e associação ............................................... 94
8.5 Discussão ..................................................................................................................... 95
8.5.1 Inferência de tipos (TIM e DISCOPLAN)................................................................. 95
8.5.2 Estado invariante de valor único ou identidade (TIM e DISCOPLAN) ...................... 96
8.5.3 Estado invariante de recurso fixo (TIM).................................................................... 96
8.5.4 Estado invariante de estado do membro (TIM) .......................................................... 97
8.5.5 Estado invariante de caracterização da unicidade do estado do membro e estado
invariante do tipo XOR (TIM e DISCOPLAN) .................................................................... 97
8.5.6 Estado invariante de estados do domínio (DISCOPLAN) .......................................... 98
8.5.7 Estado invariante de implicação simples (DISCOPLAN) .......................................... 98
8.5.8 Estado invariante de implicação de valor único (DISCOPLAN) ................................ 98
8.5.9 Estado invariante de anti-simetria ............................................................................. 99
9 CONCLUSÃO ............................................................................................................. 100
REFERÊNCIAS ............................................................................................................... 103
12
1 INTRODUÇÃO
O Planejamento Automático na Área de Inteligência Artificial (IA) envolve o
raciocínio automático de ações, eventos, objetivos, atividades, tempo e recursos
(MCCLUSKEY et al. 2003). Porém, para que um planejador seja capaz de efetuar um
planejamento, dado um problema, é necessário que um modelo da realidade em que o
problema está inserido seja fornecido. Este modelo da realidade é comumente chamado de
modelo do domínio. Um modelo do domínio de planejamento é composto principalmente
pelas ações e características do domínio, bem como um problema de planejamento é
composto pelos objetos e seus estados. Através do conhecimento de um modelo e da
manipulação do conhecimento das ações, um sistema planejador é capaz de determinar um
conjunto de ações para a solução de um problema. Existem vários sistemas de planejamento
que são capazes de desenvolver planos através da descrição de diversos tipos de domínios de
planejamento, tais como GraphPlan (BLUM; FURST, 1995), BlackBox (KAUTZ; SELMAN,
1998), STAN (LONG; FOX, 1999), FF (HOFFMAN; NEBEL, 2001), MARVIN (COLES;
SMITH, 2007) entre outros. Em sua maioria, os modelos são desenvolvidos sem o auxílio de
ferramentas de coleta de informações, o que pode dificultar o trabalho de seu
desenvolvimento.
A busca por uma ferramenta que ajude a coletar, verificar e manter as informações que
descrevem um domínio de planejamento é um dos principais objetivos atuais da comunidade
científica de Planejamento Automático. Para a descrição de um modelo e de seus problemas é
necessário que um especialista conhecedor dos detalhes do domínio o descreva em uma
linguagem apropriada ao planejador. Porém em sua maioria, as linguagens de modelagem em
planejamento são complexas e em muitos casos é necessária a ajuda de um especialista na
linguagem para a sua correta descrição.
Diversos fatores influenciam a modelagem de um domínio, partindo da compreensão
do engenheiro sobre a aplicação até a linguagem de descrição utilizada. Uma linguagem deve
ser simples, clara, com sintaxe precisa, mapeamento fácil entre o problema e a linguagem,
personalizável, reutilizável, com uma semântica bem pesquisada, expressividade adequada,
mecanismos claros de raciocínio, efeitos globais mínimos em manutenção, não ser propensa a
erros, possuir suporte de ferramentas, estruturada e com suporte aos aspectos operacionais
(MCCLUSKEY, 2003). Apesar da dificuldade de encontrar todas estas qualidades em uma
única linguagem, existem vários esforços para o seu desenvolvimento.
13
A PDDL – Planning Domain Description Language (MCDERMOTT et al., 1998),
que é atualmente utilizada como linguagem padrão de descrição de domínios, possui muita
das qualidades necessárias, tais como expressividade, possibilidade de personalização entre
outras. A PDDL expressa a dinâmica dos domínios informando quais são os seus predicados e
quais suas possíveis ações e seus efeitos. O principal intuito desta linguagem é determinar um
padrão que permita o compartilhamento de modelos entre os planejadores e que possibilite a
comparação das performances dos planejadores para a solução dos diferentes problemas
(MCDERMOTT et al., 1998). Por ter se tornado a linguagem padrão para a descrição de
domínios em planejamento, a PDDL tem sido desenvolvida para possibilitar a descrição de
modelos cada vez mais complexos o que conseqüentemente a torna igualmente complexa e
menos intuitiva para uso (BODDY, 2003). Ao mesmo tempo em que sua complexidade é
aumentada, o número de erros potenciais na modelagem também cresce, aumentando a carga
de trabalho dos modeladores devido à necessidade de verificação dos domínios quanto a sua
correta descrição.
Outra linguagem que se destaca em seu desenvolvimento é a UML.P– Unified
Modeling Language for Planning approach (VAQUERO, TONIDANDEL; BARROS;
SILVA, 2006), uma linguagem de modelagem orientada a objetos, que herda as características
da UML – Unified Modeling Language (OMG, 2007), sendo a UML uma linguagem de
modelagem bem difundida no mercado atualmente. Esta linguagem também mostra
características como simplicidade, clareza, sintaxe bem definida, mapeamento fácil do
domínio e problema para a linguagem, entre outras. Devido a sua simplicidade, facilidade de
aprendizagem e por ser amplamente difundida a UML.P se contrasta com a linguagem PDDL.
Porém, deve-se salientar que a PDDL apresenta recursos que permite a descrição de modelos
que atualmente não são possíveis de serem descritos em UML.P, tais como ações com
duração (durative actions), literais marcadas inicialmente (timed initial literals), entre outras.
Mas devido sua flexibilidade a UML.P é passível de novos desenvolvimentos para a inclusão
desta e outras características, o que a torna uma candidata potencial para o desenvolvimento
de modelos de domínio para a comunidade de Planejamento em IA.
Ferramentas como ItSIMPLE (VAQUERO, TONIDANDEL; SILVA, 2006)
(VAQUERO et al., 2007), GIPO - Graphical Interface for Planning with Objects (SIMPSON,
2005), ModPlan – Modern Action Planning (EDELKAMP; MEHLER, 2007) entre outras
estão sendo desenvolvidas com o objetivo de auxiliar o desenvolvimento de domínios. Estas
ferramentas são ambientes integrados com interface gráfica amigável e que facilitam o
processo de modelagem de domínios e problemas. O ItSIMPLE é baseado na UML.P com
14
quatro tipos de diagramas que permitem a descrição de um domínio por diferentes
abordagens. Baseado em uma abordagem orientada a objetos, o GIPO possui uma interface
com diversos recursos e é capaz de gerar domínios em PDDL, assim como o MODPLAN é
uma ferramenta que trabalha diretamente com a PDDL durante toda a modelagem, fornecendo
diversos recursos de aquisição de conhecimento.
1.1 Motivação
A descrição de problemas reais pode implicar na criação de descrições complexas de
domínio. Mesmo com a ajuda de um especialista na linguagem de modelagem, é de extrema
importância a utilização de uma ferramenta de suporte ao desenvolvimento de modelos de
domínios, pois o aumento da complexidade torna cada vez mais difícil a sua concepção e
verificação. Assim como o processo de aquisição se torna mais complexo, o processo de
planejamento automático também se torna dispendioso, pois o número de informações e ações
que podem ser executadas num domínio pode tornar este processo lento ou até mesmo sem
solução. Recursos como a inserção de estados invariantes podem beneficiar o processo de
planejamento permitindo um aumento de velocidade deste processo, bem como a redução do
espectro da busca de solução, com a extensão da descrição do domínio (RINTANEN, 2000).
Atualmente existem ferramentas que são capazes de inferir estados invariantes da
descrição dos domínios em PDDL, tais como TIM – Type Inference Module (FOX; LONG,
1998), DISCOPLAN – Discovering State Constraints for Planning (GEREVINI;
SCHUBERT, 2000), Algoritmo de Rintanen (RINTANEN, 2000) entre outros, que podem
auxiliar o planejador no processo de planejamento. Nestes trabalhos foram mostrados diversos
resultados que demonstram uma melhora expressiva no desempenho dos planejadores com a
inclusão de estados invariantes. O processo de inferência de estados invariantes destas
ferramentas é baseado na análise do estado inicial de um problema e nas ações disponíveis do
domínio. Das informações disponíveis são capturados os padrões de comportamento que as
ações mantêm, obtendo assim os estados que não variam no sistema.
Além da utilização dos estados invariantes para o melhora do processo de
planejamento os autores destas ferramentas também sugerem sua utilização para a verificação
de modelos, ou seja, pode-se descrever este processo como sendo a verificação efetuada pelo
modelador de cada estado invariante obtido pela ferramenta, validando sua pertinência ao
modelo do domínio. Qualquer erro na descrição de um domínio poderá gerar uma ou mais
inferências incorretas de estados invariantes, o que pode ser verificado, em alguns casos, de
forma fácil em domínios simples. Porém uma ou mais descrições incorretas em domínios com
15
complexidade elevada poderá gerar um número significativo de regras inferidas, incorretas e
corretas, tornando a complexidade de análise dos resultados inviável. Mesmo durante o
processo de análise das regras inferidas também poderá ocorrer erros provenientes da análise
do engenheiro do domínio, pois ainda não existe um procedimento que garanta a verificação
da consistência interna de um modelo.
Entende-se como verificação da consistência interna de um modelo o processo de
coleta de informações internas do domínio, inseridas claramente pelo modelador ou através de
qualquer mecanismo de inferência correto aplicado nas informações, que seja possível o
cruzamento destas informações para sua validação. Este processo exige que o modelo possua
informações redundantes sobre o domínio e possivelmente modeladas de formas diferentes,
sendo algumas delas intrínsecas e obtidas através de regras de inferência. Apesar de a PDDL
ser uma linguagem de modelagem evoluída, ela não fornece estrutura para sua verificação
interna, isto porque esta linguagem possui pouca ou nenhuma redundância de informação,
impossibilitando a aplicação de um sistema de validação interna nos modelos descritos nesta
linguagem.
Diferente da PDDL, a UML.P não é focada apenas na aquisição das ações de um
domínio, mas também oferece em sua estrutura outros diagramas que capturam visões
diferentes de um domínio. A UML.P é baseada em 4 diagramas principais, sendo o Diagrama
de Classes, Diagrama de Objetos, Diagrama de Estado de Máquinas e o Diagrama de Caso de
Uso (VAQUERO, TONIDANDEL; BARROS; SILVA, 2006). Porém, a UML.P é uma
linguagem semi-formal, isto é, não possui rigor matemático necessário para a realização de
inferência automática, e por este motivo as representações podem ser interpretadas de
maneiras diferentes, impossibilitando a extração automática de conhecimento. Portanto, para
que seja possível a extração automática de qualquer conhecimento desta linguagem será
necessária a sua interpretação para uma linguagem formal. Da sua interpretação será possível
a inferência de estados invariantes, não apenas das ações e do estado inicial como as
ferramentas de pré-processamento já conhecidas, mas dos demais diagramas.
Neste trabalho a atenção está focada na extração de conhecimento dos Diagramas de
Classes e de Objetos. Estes diagramas modelam informações estruturais de um domínio, que
carregam de forma intrínseca dados de estados invariantes que podem ser utilizados pelos
planejadores. Os estados invariantes obtidos por este método também poderão ser utilizados
para o processo de verificação interna de um modelo em um trabalho futuro, auxiliando o
modelador a verificar seus modelos ao fim do processo de modelagem.
16
1.2 Objetivo
O objetivo deste trabalho é definir uma interpretação em F-Logic, por ser uma
linguagem que oferece estrutura orientada a objetos, dos Diagramas de Classes e Objetos de
modelos de domínios descritos em UML.P, e a partir desta interpretação, inferir
conhecimentos.
Para que este processo seja possível serão utilizados alguns elementos do Diagrama de
Classes e o Diagrama de Objetos da UML de forma a possibilitar a definição da semântica
que será utilizada neste trabalho, porém sem ferir suas definições. Tendo os diagramas
interpretados em uma lógica que permita o raciocínio lógico automático, serão verificadas as
restrições que podem ser obtidas destes diagramas.
1.3 Organização do trabalho
No capítulo 2 é apresentada a engenharia de conhecimento, seguido da engenharia de
conhecimento em planejamento onde é discutida a necessidade de ferramentas que facilitem o
desenvolvimento de domínios. A seguir, no Capítulo 3, são apresentadas ferramentas de
extração de conhecimento de domínios de planejamento TIM e DISCOPLAN, que são
baseadas na análise das ações e do estado inicial de um problema.
A UML e a UML.P são apresentadas no Capítulo 4, onde é mostrada a estrutura que
será utilizada em planejamento e a semântica dos componentes dos Diagramas de Classes e
Objetos. No capítulo seguinte, é apresentada a Frame Logic (F-Logic) (KIFER, LAUSEN,
WU, 1995) que é uma lógica formal que permitirá a extração de conhecimento dos diagramas
da UML.P. Uma breve discussão sobre as características da UML.P e da F-Logic é
apresentada no Capítulo 6, mostrando a similaridades entre elas.
No Capítulo 7 é definida a interpretação dos elementos dos Diagramas de Classe e
Objetos em F-Logic, que possibilita a discussão da extração de conhecimento dada no
Capítulo 8. O Capítulo 9 apresenta a conclusão do trabalho e os trabalhos futuros.
17
2 ENGENHARIA DE CONHECIMENTO
As pesquisas para o desenvolvimento e operacionalização dos Sistemas Baseados em
Conhecimento (SBC) em IA concentravam esforços no desenvolvimento de formalização,
mecanismos de inferência e ferramentas para permitir a viabilidade destes sistemas em
diversas aplicações. Porém a transição inicial dos modelos acadêmicos para sistemas
comerciais se mostrou ineficiente e falhou em muitos casos (STUDER; BENHAMINS;
FENSEL, 1998). A necessidade do desenvolvimento de métodos e processos de extração de
conhecimento, especificação e modelagem, bem como de linguagens e ferramentas para o
desenvolvimento dos SBC levou o estabelecimento da Engenharia de Conhecimento (EC)
(STUDER; BENHAMINS; FENSEL, 1998).
A EC estuda os processos e métodos para o desenvolvimento e construção de SBC. De
maneira geral um SBC é composto de uma Base de Conhecimento (BC) e uma Máquina de
Inferência (MI). A BC tem por objetivo manter as informações e regras obtidas de um
especialista, que permitirá a resolução de problemas de sua especialidade através da utilização
da MI. A MI é responsável pelo raciocínio automático do sistema, sendo que normalmente
são utilizados mecanismos de inferência desenvolvidos pela IA. Portanto os SBC são sistemas
especialistas que são capazes de encontrar soluções e padrões para os problemas da
especialidade do sistema (STUDER; BENHAMINS; FENSEL, 1998).
2.1 Processo de modelagem
O processo de modelagem computacional de um domínio sugere que o engenheiro do
domínio modele todo o conhecimento do especialista, para que o sistema obtenha resultados
similares ao obtido pelo especialista na resolução de problemas. Neste processo os domínios
gerados são apenas aproximações do mundo real, sendo que esta modelagem é um processo
cíclico onde a cada nova análise novas características podem ser adicionadas ou aperfeiçoadas
para aproximar o modelo da realidade do domínio. Por ser uma visão particular do engenheiro
de domínio, o modelo deve ser constantemente analisado para que mantenha as características
adequadas para a construção do SBC.
Existem diversas ferramentas e métodos que auxiliam um Engenheiro de
Conhecimento a adquirir os dados para a inserção a uma BC, tal como CommonKADS -
Common Knowledge Acquisition Design System (SCHREIBER et al., 1994), MIKE – Model-
based Incremental Knowledge Engineering (ANGELE; FENSEL; STUDER, 1998),
18
PROTÉGÉ-II (ERIKSSON et al., 1995), entre outras que estão em constante desenvolvimento
((COMMONKADS, 2007), (GENNARI et. al., 2002)). As ferramentas oferecem diferentes
abordagens de aquisição de conhecimento, sendo cada qual com características que focam
objetivos diferentes. O CommonKADS tem como abordagem principal a distinção de três
tipos de conhecimento para a resolução de problemas, sendo eles o conhecimento estático, o
funcional e o dinâmico. Tendo como proposta a formação de um sistema completo, o MIKE
integra o processo de desenvolvimento de um sistema incremental e reversível com protótipo
e suporte. PROTÉGÉ-II tem como foco a utilização dos Métodos de Solução de Problemas
(MSP) e Ontologias (STUDER; BENHAMINS; FENSEL, 1998). Os MSP especificam a
seqüência de tarefas necessárias para resolver uma tarefa e o conhecimento necessário pelo
método, enquanto que a Ontologia na perspectiva da EC é usada como um sinônimo para as
terminologias em um domínio (KENDAL; CREEN, 2007).
2.2 Engenharia de conhecimento em planejamento
Engenharia de Conhecimento em Planejamento Automático é o processo que se dá
com a aquisição, verificação e manutenção de modelos de domínios de planejamento e a
seleção e otimização de agentes para trabalhar nestes domínios. Este processo é amplamente
baseado no conhecimento das ações e de como os objetos interagem entre si (MCCLUSKEY
et al. 2003). Diferentemente do que se encontra no desenvolvimento dos SBC, que possuem
ferramentas e métodos que auxiliam o seu desenvolvimento desde a aquisição de dados até a
concepção do sistema, verifica-se um desenvolvimento tímido na área de aquisição de
domínios pela comunidade de planejamento, com apenas alguns esforços isolados, tais como
o desenvolvimento de ferramentas de extração automática de conhecimento (TIM,
DISCOPLAN, Algoritmo de Rintenen entre outros) e ferramentas gráficas que auxiliam a
construção de modelos (GIPO, ItSIMPLE, ModPlan) entre outros esforços.
Uma ferramenta que auxilie o processo de aquisição e modelagem de domínios é de
grande importância para a continuidade no desenvolvimento da área de Planejamento
Automático em IA. Esta ferramenta deve fornecer um método para auxiliar a aquisição do
modelo de domínio de forma a facilitar a captura do maior número de informações do
domínio. Este método deve ser consistente e válido, assim como as ferramentas disponíveis
para o desenvolvimento de SBC são, com o intuito de obter domínios de alta qualidade e com
o menor número de inconsistências possíveis.
A validação de um domínio é o processo que promove sua qualidade em termos de
critérios internos e externos pela identificação e remoção dos erros do domínio. Os critérios
19
internos incluem propriedades como sintaxe correta e consistência lógica e os critérios
externos incluem propriedades como exatidão, completeza e correção para com o domínio a
ser modelado. Porém é importante ressaltar que devido a maioria dos domínios de
planejamento não serem objetos puramente matemáticos, nunca poderá ser provado que os
modelos destes domínios são corretos com relação ao domínio (MCCLUSKEY et al. 2003). O
processo que verifica a consistência interna de um modelo, chamado de validação estática,
verifica a completeza de um modelo no modo restrito do domínio mostrando as conseqüências
do modelo (MCCLUSKEY et al. 2003). Esta validação deve ser realizada da forma mais
automática possível, permitindo que o planejador receba um domínio verificado e consistente,
ou seja, sem informações ou ações que forneçam características conflitantes, permitindo a
redução na carga de processamento na geração de planos.
Um modelo de domínio deve ser caracterizado pela possibilidade de ser utilizado em
qualquer planejador, porém a linguagem de descrição deve ser clara, fácil e intuitiva,
permitindo não apenas a descrição do domínio e suas ações, mas também inserir
conhecimentos de controle que auxiliem no processo de planejamento.
Uma importante característica para o desenvolvimento de uma ferramenta que auxilie
o processo de aquisição e modelagem de domínios é a possibilidade de extração de
conhecimentos implícitos na descrição do domínio, bem como a classificação de domínios e
mecanismos para tirar proveito de sua codificação (MCCLUSKEY, PORTEOUS, 1997). Os
conhecimentos implícitos são informações que estão presentes na descrição do domínio,
porém não estão presentes de forma clara e direta. Atualmente estes conhecimentos são
extraídos para a aceleração do planejamento e para aumentar a qualidade do plano, porém
estas informações também podem auxiliar na validação estática do modelo.
Este trabalho se insere neste contexto, contribuindo na extração de conhecimentos de
modelos descritos em UML.P. Os conhecimentos extraídos poderão fazer parte dos elementos
de restrição dos domínios, porém seu maior objetivo é a viabilização de um futuro processo
de validação estática dos modelos em UML.P. Os conhecimentos que serão extraídos do
Diagramas de Classes e Objetos poderão ser utilizados no processo de validação das ações de
um domínio, contribuindo na geração de modelos com menor número de inconsistências.
20
3 EXTRAÇÃO DE CONHECIMENTO EM PLANEJAMENTO
Atualmente a extração de conhecimento em planejamento, que é o processo de análise
de um modelo de domínio através de métodos e algoritmos em busca de estruturas que não
foram declaradas explicitamente no modelo, tem sido utilizada em sua maioria para a
inferência de estados invariantes para a aceleração do processo de planejamento.
De uma maneira simples podemos exemplificar o processo de extração de
conhecimento através de um modelo do mundo dos blocos que é um exemplo clássico de
planejamento. Este domínio se caracteriza por ter um conjunto de blocos quadrados, todos de
mesmo tamanho, que podem ser empilhados sobre uma superfície ou uns sobre os outros. O
movimento dos blocos só pode ocorrer individualmente e quando não houver outro bloco
sobre ele, resultando no seu reposicionamento sobre a superfície ou sobre outro bloco. Neste
domínio não existem interferências externas sendo que todas as mudanças no domínio são
efetuadas por um único agente. As ações que podem ser efetuadas neste domínio são de
empilhar, desempilhar, pegar o bloco da mesa e colocar o bloco sobre a mesa. Portanto,
suponha a descrição simplificada da ação empilhar do mundo dos blocos em uma linguagem
qualquer, como no exemplo abaixo, onde G, B1 e B2 são variáveis definidas pelo seu tipo de
parâmetro e holding e clear são predicados do modelo do domínio:
Ação:: Stack
Parâmetros de Entrada:: G:Hand; B1, B2:Block.
Pré-Condição:: holding(G, B1), clear(B2), B1 ≠ B2.
Pós-Condição:: ¬holding(G, B1), ¬clear(B2), empty(G), on(B1,
B2), clear(B1).
Está claro na descrição acima que um bloco não pode estar sobre si mesmo, porém
esta informação está implícita no exemplo e é de conhecimento do modelador. Como
resultado da aplicação de uma ferramenta de inferência de estados invariantes no domínio do
mundo dos blocos pode-se obter restrições como:
B1,B2:Bloco. Sobre(B1, B2) → B1 ≠ B2.
Duas ferramentas de extração de conhecimento são muito conhecidas na comunidade
de planejamento, pois permitem a extração de estados invariantes que oferecem melhorias
significantes no processo de planejamento. TIM e DISCOPLAN são ferramentas de pré-
planejamento que oferecem recursos de extração de estados invariantes para auxiliar o
planejador no processo de busca. Estas ferramentas são capazes de inferir restrições corretas
21
de descrições de domínios corretos. Os autores destas ferramentas sugerem a sua utilização
para que o engenheiro de domínio verifique as regras extraídas para a validação do sistema,
porém a verificação destas regras em sistemas complexos e que gerem muitas regras pode se
tornar inviável. Abaixo são discutidos os processos utilizados para a extração dos estados
invariantes.
3.1 TIM
A ferramenta TIM (Type Inference Module) foi inicialmente desenvolvida como parte
integrante do planejador STAN (FOX; LONG, 1998), o qual é baseado no planejador
Graphplan. Apesar de ser parte integrante do planejador STAN, o módulo de inferência TIM é
independente do planejador e as regras por ele inferidas podem ser utilizadas por qualquer
planejador. Este módulo é apenas capaz de extrair restrições de operadores STRIPS (FIKES;
NILSSON, 1971), porém já existem extensões deste módulo para a extração de informações
de operadores descritos em ADL – Action Description Language (CRESSWELL; FOX;
LONG, 2002). Além dos estados invariantes que o TIM é capaz de extrair, esta ferramenta
também pode inferir os tipos de dados de um domínio, sendo este o processo inicial da
extração de estados invariantes (FOX; LONG, 1998).
O conceito de extração de conhecimento de um domínio adotado pelo TIM é baseado
nas Máquinas de Estados Finitos (MEF), onde dois objetos são funcionalmente equivalentes e
poderão ser identificados como sendo do mesmo tipo se ambos participarem de MEF
idênticas (FOX; LONG, 1998). O processo de obtenção dos estados invariantes é baseado em
quatro etapas principais: Identificação dos tipos primitivos do domínio, Inferência da estrutura
hierárquica dos tipos baseado nos tipos primitivos, Inferência dos tipos de parâmetros dos
operadores e Inferência de estados invariantes. A seguir têm-se os principais passos de cada
etapa para a inferência de estados invariantes.
3.1.1 Identificação dos tipos primitivos do domínio
Para iniciar o processo de identificação dos tipos primitivos o sistema analisa o
conjunto de operadores do domínio para a construção das regras de transição de estados das
MEFs. As regras de transição são formadas por propriedades, que são os predicados das ações
subscritos pela posição da variável em análise. A tabela 1 exemplifica as propriedades para
duas ações do mundo de blocos.
22
Para a construção das regras de transição são utilizadas as Estruturas de Relação de
Propriedades (ERP), que se caracterizam por uma coleção tripla de propriedades, formadas a
partir de cada parâmetro dos operadores. A primeira coleção de propriedades, chamada de
Prec, é dada pelos predicados que contenham o parâmetro em análise na pré-condição dos
operadores; a segunda coleção de propriedades, chamado de Del-Prec, é dada pelos
predicados que possuam o parâmetro em análise dado na lista de pré-condição e na lista de
remoção de um operador; a terceira coleção de propriedade, chamado de Add-Element, é dado
pelos predicados que contenham o parâmetro em análise na lista de adição do operador. A
tabela 1 exemplifica a construção dos ERPs de duas ações do mundo dos blocos.
Tabela 1. Formação da estrutura de relação de propriedades
Stack(X,Y,Z)
Pre-Condition: holding(Z, X),clear(Y)
Add: empty(Z),clear(X),on(X,Y)
Del: holding(Z,X),clear(Y)
Unstack(X,Y,Z)
Pre-Condition: empty(Z),clear(X),on(X,Y)
Add: holding(Z,X),clear(Y)
Del: empty(Z),on(X,Y),clear(X)
ERP1 – Considerando o parâmetro X
Prec: holding
2
Del-Prec: holding
2
Add-Element: clear
1
, on
1
ERP4 – Considerando o parâmetro X
Prec: clear
1
, on
1
Del-Prec: on
1
, clear
1
Add-Element: holding
2
ERP2 - Considerando o parâmetro Y
Prec: clear
1
Del-Prec: clear
1
Add-Element: on
2
ERP5 - Considerando o parâmetro Y
Prec: on
2
Del-Prec: on
2
Add-Element: clear
1
ERP3 - Considerando o parâmetro Z
Prec: holding
1
Del-Prec: holding
1
Add-Element: empty
1
ERP6 - Considerando o parâmetro Z
Prec: empty
1
Del-Prec: empty
1
Add-Element: holding
1
Cada ERP é baseada em uma variável do operador. As propriedades de cada ERP são formadas dos predicados
das ações subscrito pela posição da variável responsável pela formação da ERP.
Para a construção das regras de transição é utilizada a seguinte fórmula:
Prec Del-Prec Del-Prec → Add-Element
(1)
A fórmula mostra que a coleção de propriedades que facilitam a transição de estado de
um objeto é dada pela coleção das propriedades de Prec subtraída da coleção das
propriedades na Del-Prec. A transição faz com que o objeto perca as propriedades da lista de
Del-Prec e adquira as propriedades de Add-Element. Então para cada ERP serão obtidas as
seguintes Regras de Transição para as ações do exemplo do mundo de blocos:
Tabela 2. Geração de regras de transição
ERP1 – Considerando o parâmetro X
holding
2
→ clear
1
, on
1
ERP4 – Considerando o parâmetro X
on
1
, clear
1
→ holding
2
ERP2 - Considerando o parâmetro Y
clear
1
→ on
2
ERP5 - Considerando o parâmetro Y
on
2
→ clear
1
ERP3 - Considerando o parâmetro Z
holding
1
→ empty
1
ERP6 - Considerando o parâmetro Z
empty
1
→ holding
1
Resultado da geração das regras de transição do exemplo da tabela 1.
23
Da tabela 2, na ERP1 a instância do objeto X mudará de estado quando aplicado o
operador Stack, sendo que a propriedade holding será perdida para que o objeto receba as
novas propriedades clear e on. As outras ERPs seguem o mesmo raciocínio.
As ERPs que geram apenas regras onde não existem trocas de propriedades, ou seja,
não existem elementos de adição ou elementos de remoção, caracterizam-se como regras de
atributos. As regras que não possuem os elementos de adição e remoção são nomeadas de
regras de adição de atributos e de regras de remoção de atributos, respectivamente.
Definição 3.1.1 (FOX; LONG, 1998): Um espaço de propriedade é composto de quatro
componentes: um conjunto de propriedades, um conjunto de regras de transição, um conjunto
de estados e um conjunto de constantes do domínio.
Definição 3.1.2 (FOX; LONG, 1998): Um espaço de atributo é composto de três
componentes: um conjunto de propriedades, um conjunto de regras de transição e um
conjunto de constantes do domínio.
Tabela 3. Sementes do espaço de propriedades
[holding
2
, clear
1
, on
1
, on
2
]
[holding
1
, empty
1
]
A união das propriedades para a geração dos espaços de propriedades e atributos.
A construção dos Espaços de Propriedades e Atributos é necessária para a
identificação dos tipos do domínio. Para a sua construção são unidas as propriedades das
regras que possuem características em comum na coleção de propriedades que serão perdidas
(Del-Prec) ou na coleção de propriedades que serão adicionadas nas regras de transição (Add-
Element), observando que as propriedades que facilitam as transições (Prec Del-Prec) não
são utilizadas no processo de unificação. O objetivo da unificação é de formar coleções de
propriedades que semeiem os espaços de propriedades ou espaços de atributos formando
assim a base de construção de seus espaços (FOX; LONG, 1998). Para o exemplo do mundo
de blocos têm-se as sementes da tabela 3 que são compostas da coleção obtida da unificação
das propriedades das regras de transição da tabela 2.
Os espaços semeados são então preenchidos com as regras que se associam as
sementes geradas. Para efetuar esta associação basta pegar uma das propriedades, exceto a
propriedade que facilita a transição, e verificar a qual semente a regra pertence. As regras de
transição que se caracterizam como sendo atributos formarão espaços de atributos, mesmo
24
que em seu espaço existam regras que não se caracterizem como atributo (FOX; LONG,
1998).
Tabela 4. Geração de espaço de propriedades
Sementes
Regras
Espaço de
Propriedade 1
[holding
2
, clear
1
, on
1
, on
2
, ontable
1
]
holding
2
→ clear
1
, on
1
clear
1
→ on
2
on
1
, clear
1
→ holding
2
on
2
→ clear
1
Espaço de
Propriedade 2
[holding
1
, empty
1
]
holding
1
→ empty
1
empty
1
→ holding
1
Espaços de Propriedades gerados a partir das sementes obtidas da tabela 3.
Um vetor binário de tipo, com o tamanho do número de espaços encontrado no
domínio, é construído para a definição dos tipos de objetos. No exemplo do mundo dos blocos
2 espaços de propriedades foram obtidos, portanto seu vetor binário terá duas posições [XX].
Cada bit do vetor indicará se o objeto habita ou não um determinado Espaço de Propriedades
ou de Atributos. Para que um objeto habite um determinado Espaço de Propriedades ele deve
ter uma propriedade pertencente a este espaço. Para que um objeto pertença a um determinado
Espaço de Atributos ele deve ser capaz de potencializar as propriedades que facilitem a
transição de todas as regras que tenham características de adição de atributos naquele espaço
(FOX; LONG, 1998). Por exemplo, suponha que o estado inicial do domínio do mundo de
blocos seja clear(blockA) e holding(crane,blockB). Para os objetos blockX o
vetor é preenchido com [10], pois para blockX as propriedades clear
1
e holding
2
pertencem
ao primeiro Espaço de Propriedades. Para o objeto crane o vetor é preenchido com [01],
pois a propriedade holding
1
pertence apenas ao segundo Espaço de Propriedades. A tabela 4
exemplifica a distribuição dos objetos nos Espaços de Propriedades.
Tabela 5. Determinação de propriedades do estado inicial
Sementes
Regras
Objetos
Propriedades no
estado inicial
Propriedades
possíveis de
alcançar
[holding
2
, clear
1
, on
1
, on
2
]
holding
2
→ clear
1
, on
1
clear
1
→ on
2
on
1
, clear
1
→ holding
2
on
2
→ clear
1
blockA
blockB
clear
1
holding
2
on
1
on
2
[holding
1
, empty
1
]
holding
1
→ empty
1
empty
1
→ holding
1
crane
holding
1
empty
1
Identificação das propriedades dos objetos.
25
Através do espaço inicial são identificadas as propriedades dos objetos bem como as
propriedades em que os objetos podem alcançar. Para a determinação das propriedades que os
objetos podem alcançar são utilizadas as regras dos Espaços de Propriedades (FOX; LONG,
1998). O estado final não é utilizado para a obtenção de informações, pois não se sabe se o
estado é válido, o que poderia levar a extração de regras inválidas.
Dos Espaços de Propriedades se extraí os tipos primários do domínio, os quais podem
ser identificados pelo vetor de bits dos objetos do domínio. Portanto, no exemplo do mundo
de blocos há 2 tipos distintos de objetos, o tipo T
1
que possui o vetor [10] e o tipo T
2
que
possui o vetor [01].
3.1.2 Inferência da estrutura hierárquica dos tipos, baseado nos tipos primitivos.
A construção do vetor binário de tipo, utilizado anteriormente para a definição dos
tipos de objetos do domínio, tem como função distinguir os objetos de acordo com o seu
comportamento, agrupando-os de forma a manter as mesmas características entre eles. Porém
existem grupos de objetos que apresentam comportamentos similares, o que pode indicar que
ambos os tipos dos objetos são derivados de uma classe maior ou que possuem alguma
relação entre seus tipos. Através do vetor binário de tipo é possível inferir a estrutura
hierárquica dos tipos, sendo que qualquer vetor V
1
com uma determinada configuração de bits
e qualquer vetor V
2
com a mesma configuração de bits exceto por um bit, indicará que o tipo
associado a V
2
poderá ser um supertipo do tipo associado a V
1
(FOX; LONG, 1998).
Tabela 6. Exemplo de construção de tipos
Parâmetro
Propriedades
Vetor
Tipo
X
clear
1
, on
1
[10]
T
1
Y
on
2
[10]
T
1
Z
empty
1
[01]
T
2
Identificação dos tipos dos parâmetros dos predicados.
3.1.3 Inferência dos tipos de parâmetros dos operadores
Para a inferência dos tipos de parâmetros dos operadores os parâmetros da pré-
condição dos operadores são analisados, de forma a associar os tipos corretos para cada
parâmetro do operador a seu Espaço de Propriedades. Como exemplo suponha o operador
Unstack do domínio do mundo dos blocos da tabela 1. Atribuindo um vetor de bit para cada
parâmetro tem-se o resultado mostrado na tabela 6.
26
3.1.4 Inferência de estados invariantes
Para a inferência de estados invariantes que governam o comportamento do domínio e
de seus objetos a ferramenta utiliza os Espaços de Propriedades. O TIM é capaz de inferir
quatro tipos diferentes de estados invariantes, sendo eles (FOX; LONG, 1998):
1. Estados Invariantes de Identidade (Identity Invariants). Para cada propriedade P
K
,
derivada de um predicado P, que ocorre no máximo uma única vez num espaço de
propriedade, para P com aridade n > 1, pode-se obter invariantes do tipo
zyzxzPyxyPzyx
nkknkk
),,(),,(.(..
1..1..11..1..1
, onde x, y e z são variáveis.
Note que
y
e
z
são vetores contendo n – 1 valores. Esta regra pode ser generalizada
para propriedades que ocorrem mais de uma vez em um espaço de propriedade da
seguinte maneira:
mmmm
yyyyyyyxPyxPzyyx
1312111
...),(...),(.(.....
Onde k foi igualado a 1 por simplicidade. Do exemplo podem-se extrair os seguintes
estados invariantes:
zyzxHoldingyxHoldingzyx ),(),(.,,
zyzxOnyxOnzyx ),(),(.,,
2. Estados Invariantes de “Estado do Membro” (State Membership Invariants). São
estados invariantes do tipo
)...(
1 n
DisjunçãoDisjunçãox
sendo que cada
disjunção é construída de um único estado, para cada espaço de propriedades. Sendo
cada disjunto do tipo
),,(.
1..1..1
nkk
yxyPy
, sendo y uma variável. Note que caso a
aridade n do predicado for igual a 1 existirá apenas P(x), onde x é uma variável, na
disjunção. Do exemplo pode-se extrair o seguinte estado invariante,
)),(.),(.),(.)()(( xyonyyxonyxzholdingzxclearxontablex
))(),(.( xemptyzxholdingzx
.
3. Estados Invariantes de Caracterização de Unicidade do “Estado do Membro”
(Invariants characterizing uniqueness of state membership). São estados invariantes,
onde P
k
e Q
j
representam as n propriedades de um estado, para k variando de 1 a n e j
variando de 1 a m, são do tipo:
)))),(...),(.(...()),(...),(.(...((.
1
1
11
1
1 m
m
mn
n
n
yxQyxQyyyxPyxPyyx
.
Todos os pares de propriedades que são mutuamente exclusivos são identificados para
27
a geração dos estados invariantes, observe que para cada par é gerada uma regra
diferente. Do exemplo gera-se a seguinte regra,
)),(.),(.(. yxonyxzholdingzx
.
4. Estados Invariantes de Recurso Fixo (Fixed Resource Invariants). São estados
invariantes extraídos por meio da análise dos predicados da linguagem, onde é
verificado se os predicados são trocados igualmente das listas de ação e de remoção
dos operadores. Se o predicado é trocado igualmente em todos os operadores este é
considerado um recurso fixo. Do exemplo se extrai o estado invariante abaixo.
1),(: xzholdingx
.
Os três primeiros estados invariantes são adquiridos diretamente dos Espaços de
Propriedades, enquanto que o Estado Invariante de Recurso Fixo é obtido da estrutura dos
operadores e do estado inicial (FOX; LONG, 1998).
3.2 DISCOPLAN
O DISCOPLAN (DIscovering State COnstraints for PLANning) teve como motivação
a necessidade de encontrar uma ferramenta que permitisse inferir estados invariantes para a
aceleração de planejadores independentes de domínios (GEREVINI; SCHUBERT, 2000).
Baseado num conjunto de algoritmos capazes de inferir estados invariantes implícitos nos
operadores das ações dos domínios e das informações contidas nos estados iniciais, este é
capaz de utilizar operadores do tipo PDDL e UCPOP (GEREVINI; SCHUBERT, 2000).
Diferentemente do TIM o DISCOPLAN é capaz de inferir restrições de operadores com
efeitos condicionais, o que permite uma maior abrangência na análise de domínios onde
muitos já são descritos com estas características. Porém ele não é capaz de manipular
condições disjuntivas e quantificação universal (GEREVINI; SCHUBERT, 2000). O
DISCOPLAN é capaz de inferir os seguintes estados invariantes: estados invariantes de tipos,
estados invariantes de predicado do domínio, estados invariantes de implicação simples,
estados invariantes de valor único, estados invariantes de implicações de valor único, estados
invariantes de anti-simetria e estados invariantes do tipo XOR.
Deve-se salientar que exceto pelos Estados Invariantes de Tipos e os Estados
invariantes de Predicado do Domínio, os demais Estados Invariantes extraídos são obtidos
através de um modelo de suposições e testes (Hypothesize-and-Test Paradigm) (GEREVINI;
SCHUBERT, 2000).
28
3.2.1 Estados invariantes de tipo
A análise para a extração dos estados invariantes de tipos, que é obtida através do
estado inicial de um domínio, resulta em três listas distintas, sendo elas de predicados,
indicando os tipos dos objetos encontrados no domínio; de tipos universais e vazios,
indicando os tipos que todos os objetos do domínio satisfazem ou que nenhum deles satisfaz;
supertipos/subtipos e os tipos incompatíveis entre os predicados (GEREVINI; SCHUBERT,
2000).
Primeiramente o algoritmo encontra todos os predicados estáticos descritos no
domínio, ou seja, predicados que não ocorrem em nenhum efeito de operadores. Observando
que o sistema assume que todos os objetos do domínio são descritos no estado inicial. Após
encontrar todos os predicados estáticos e associar os conjuntos de constantes aos tipos
encontrados, o sistema analisa cada tipo, onde (GEREVINI; SCHUBERT, 2000):
a) se o tipo englobar todas as constantes, este será um supertipo;
b) se o tipo não englobar qualquer constante, este será um tipo vazio;
c) se dois tipos de predicados, A e B, sendo que
BA
então ter-se-á que A é um
subtipo de B e este será um supertipo;
d) se dois tipos de predicados, A e B, sendo que
{} BA
então eles são de tipos
incompatíveis e nenhum objeto pode ser dos dois tipos.
Através deste procedimento o sistema é capaz de inferir os tipos de todos os objetos do
domínio, determinando também a hierarquia deles, assim como o sistema TIM também é
capaz de inferir.
3.2.2 Estados invariantes de estados do domínio
Estados invariantes de estados dos domínios são obtidos por meio de uma versão
simplificada do Graphplan, onde não são consideradas as relações mutuamente exclusivas
entre os nós de ações e de fatos, este grafo é chamado de Forward Action Graph (GEREVINI;
SCHUBERT, 2000).
Através do Forward Action Graph é possível definir o número mínimo de ações
necessárias para que um predicado ocorra. Por exemplo, dado um estado inicial do mundo de
blocos
),(),(),( TableConCBonBAon
, através da construção do Forward Action Graph é
possível inferir que o predicado
),( ACon
apenas poderá ser verdadeiro depois de no mínimo
duas movimentações (GEREVINI; SCHUBERT, 2000).
29
3.2.3 Modelo de suposição e teste
A maioria dos algoritmos do DISCOPLAN utiliza o modelo de suposição e teste para
a obtenção de suas regras. Através da estrutura dos operadores este modelo é capaz de inferir
Estados Invariantes de um domínio. As regras inferidas são sugeridas a partir de pares de
efeitos ou por um par de efeitos e precondição persistente no operador, onde os pares
encontrados são testados em todos os operadores de forma a validar as regras. No caso da
falha da verificação da regra em algum dos operadores, pode ser possível adicionar uma
condição suplementar de forma a validar uma regra mais “fraca” (GEREVINI; SCHUBERT,
2000).
Os principais processos executados neste modelo são (GEREVINI; SCHUBERT,
2000):
a) supõe-se a restrição baseada na co-ocorrência de literais na estrutura do operador;
b) adiciona um conjunto de condições suplementares, as quais consistem de
precondições estáticas dos operadores;
c) testa a regra suposta em todos os operadores, encontrando formas de relaxar a
restrição, por meio do conjunto das condições suplementares, no caso de falha.
Caso a restrição não possa ser relaxada a mesma é abandonada;
d) encontra um conjunto mínimo de condições suplementares que permita a
utilização da restrição;
e) verifica a restrição em conjunto das condições suplementares no estado inicial do
problema e retorna a regra como uma regra testada.
Os estados invariantes extraídos a seguir são baseados no procedimento aqui descrito,
porém cada qual possuirá particularidades no seu processo de extração de regras. Nas seções
seguintes serão explicadas as regras inferidas de cada extração.
3.2.4 Estados invariantes de implicação simples
Através do modelo de suposição e testes, o sistema é capaz de inferir regras
verdadeiras em tempo polinomial. Os estados invariantes de implicação simples são regras no
formato
)..)((
1 n
, onde os componentes
, φ e σ
k
da regra são fórmulas atômicas
com argumentos constantes ou variáveis. As regras obtidas neste procedimento devem ser
interpretadas como “Para todos os estados e valores de variáveis, se
então φ, dado σ
1
,... e
σ
n
” (GEREVINI; SCHUBERT, 2000, p. 20).
30
Para a extração desta regra é assumido que
, que possui apenas predicados fluentes,
tenha todas as variáveis que ocorrem em φ e nas condições suplementares, que possuem
predicados estáticos ou fluentes no caso de φ. Porém se
tiver variáveis que não ocorrem em
φ, então φ necessariamente será monotônico e não poderá ter instâncias que possam torná-la
falsa. Caso esta condição não seja respeitada, a regra não será independente de outras
restrições, deixando de ser uma restrição de implicação simples (GEREVINI; SCHUBERT,
2000).
Num modelo do mundo de blocos, o sistema seria capaz de inferir regras como
)()(. xblockxclearx
,
)(),(., xblockyxonyx
e
)(),(., yblockyxonyx
das
ações, sendo x e y variáveis. Esse tipo de regra não é inferido pelo TIM, conforme se observa
na seção 3.1.4.
3.2.5 Estados invariantes de valor único
Os estados invariantes de valor único, chamadas de estados invariantes de identidade
pelo TIM, são restrições do tipo
zyzxPyxPzyx ),(),(.,,
, sendo x, y e z variáveis e
P a representação de um átomo. Esta mesma regra é descrita com variáveis “marcadas com
estrela” no formato Lisp da seguinte forma (P ?X ?*Y) pelo DISCOPLAN. O processo inicial
de suposição é realizado nos operadores onde exista como precondição um átomo P e que
possua ¬P como efeito, permitindo assim a suposição de estados invariantes de valor único, os
quais são submetidos a verificações para sua validação. Assim como a extração de estados
invariantes de implicações simples, este processo infere regras verdadeiras em tempo
polinomial (GEREVINI; SCHUBERT, 2000).
3.2.6 Estados invariantes de implicações de valor único
Assim como as implicações simples, as regras obtidas neste processo são do tipo
)..)((
1 n
. Apesar da extração de estados invariantes de implicações de valor único
ser baseada na extração de invariantes de implicação simples, duas das condições para a
extração de implicações simples são relaxadas. Sendo que não é mais assumido que
tenha
todas as variáveis que ocorrem em φ e, neste caso, φ pode não ser monotônico e pode possuir
instâncias que podem torná-lo falso (GEREVINI; SCHUBERT, 2000). Diferente do TIM,
num modelo do mundo dos blocos o sistema poderia inferir a regra
)()(),(),(.,, yclearzxytableyzonyxonzyx
, sendo x, y e z variáveis.
31
Dessa forma as implicações podem assumir a inclusão de estados invariantes de valor
único como parte do conjunto de predicados. Neste caso haverá a necessidade de uma
verificação diferenciada das restrições por haver interdependência de restrições na fórmula.
(GEREVINI; SCHUBERT, 2000)
3.2.7 Estados invariantes de anti-simetria
Os estados invariantes de anti-simetria são fórmulas do tipo
),(),(., xyPyxPyx
sendo x, y e z variáveis e P a representação de um átomo. Nota-se que este é um caso especial
da extração de invariantes de implicação simples, porém durante a análise dos domínios
existentes notou-se que em grande maioria as descrições dos mesmos não forneciam
explicitamente em sua precondição o predicado ¬P(y, x) o que inviabilizou a utilização do
algoritmo de implicação simples na extração desta regra. Portanto foi necessária a utilização
de um algoritmo específico para a extração deste tipo de restrição (GEREVINI; SCHUBERT,
2000).
3.2.8 Estados invariantes do tipo XOR
Os estados invariantes do tipo XOR são regras no formato
)..)((
1 n
xor
, sendo
que
e φ são fluentes positivos, das quais as variáveis compartilhadas entre
e φ não são
universalmente quantificadas, enquanto que as não compartilhadas são existencialmente
quantificadas. Os componentes suplementares são variáveis compartilhadas entre
e φ
(GEREVINI; SCHUBERT, 2000). No exemplo do mundo dos blocos, o sistema poderia
extrair regras como
)(),()(.. xclearxorxyonxtableyx
, sendo x e y variáveis.
3.3 Discussão
Cada ferramenta utiliza processos distintos para a extração de regras, sendo que o TIM
é capaz de inferir quatro tipos de estados invariantes diferentes: Estados Invariantes de
Identidade (Identity Invariants), Estados Invariantes de Estado de Membro (State Membership
Invariants), Estados Invariantes de Unicidade (Uniqueness Invariants) e Estados Invariantes
de Recursos Fixos (Fixed Resource Invariants). O DISCOPLAN é capaz de inferir 7 estados
invariantes sendo eles: Estados Invariantes de Tipos (Type Constraint), Estados Invariantes de
Predicado do Domínio (Predicate Domain Constraint), Estados Invariantes de Implicação
Simples (Simple Implicative Constraint), Estados Invariantes de Valor Único (Single
Valuedness Constraint), Estados Invariantes de Implicações de Valor Único (Implicative
32
Constraint + Single Valuedness Constraint), Estados Invariantes de Anti-Simetria
(Antisimmetry Constraint) e Estados Invariantes do Tipo XOR (XOR-Constraint).
Ambos os sistemas são capazes de inferir os tipos do domínio assim como as
restrições de valores únicos ou de unicidade. As ferramentas se complementam, permitindo
uma ampla gama de restrições de um domínio para o auxilio do planejamento automático.
Apesar das ferramentas utilizarem métodos distintos para a inferência dos estados
invariantes, a análise é efetuada na mesma origem, ou seja, nas ações e no estado inicial de
um modelo. Conforme será visto nas próximas seções, na linguagem UML.P as ações e o
estado inicial são modelados através dos Diagramas de Estado de Máquinas do Diagrama de
Objetos respectivamente. Porém, neste trabalho efetuaremos a análise dos Diagramas de
Classes e de Objetos, com o objetivo de obter uma nova origem de estados invariantes.
Para este trabalho utilizou-se como base os estados invariantes extraídos pelas
ferramentas TIM e DISCOPLAN para a obtenção dos mesmos estados invariantes da análise
dos Diagramas de Classes e de Objetos.
33
4 UML
De acordo com a OMG (2007), a UML é uma linguagem de modelagem gráfica com
um escopo amplo, permitindo a sua utilização em diversos domínios e aplicações. Isto se deve
a sua estrutura modular que permite que apenas os módulos de interesses da aplicação ou
domínio sejam utilizados durante a modelagem. A sua especificação está constantemente
sendo desenvolvida para atender os mais diversos aspectos de modelagem. No momento em
que desenvolvemos este trabalho a especificação oficial disponível pela OMG - Object
Management Group é a 2.1.1 (OMG, 2007) e será seguida esta especificação neste trabalho.
A UML é baseada no conceito de meta-modelos, ou seja, ela é um modelo de
linguagem que permite que seus usuários criem seus próprios modelos. Porém, a UML está
inserida em um contexto maior, definido pela OMG, para a padronização da criação de
modelos independentes de implementação conhecido como Arquitetura Ativada por Modelos
(MDA – Model-Driven Architecture) (OMG, 2007). A descrição do objetivo da MDA e de
suas especificações está além do escopo deste trabalho e será deixada a cargo do leitor a
imersão neste contexto. Aqui o foco será mantido na UML que é composta por duas
especificações, ou bibliotecas como é comumente chamado nos documentos da OMG: Infra-
Estrutura e Super-Estrutura, sendo que a especificação de Infra-Estrutura também faz parte do
coração das especificações da MDA. As especificações dadas nestas bibliotecas são descritas
pela linguagem da UML, ou seja, a UML define sua própria estrutura (OMG, 2007).
A biblioteca de Infra-Estrutura fornece o núcleo utilizado para definir a UML, além
dos outros componentes da MDA. Esta biblioteca define dois pacotes: o Core e o Profile. O
pacote Core aborda os conceitos para a criação de tipos de dados, elementos de modelagem e
características comuns dos elementos de modelagem. O pacote Profile contém os mecanismos
que permitem adaptar as meta-classes existentes para um fim específico. As meta-classes são
os elementos que definem a estrutura da UML, ou seja, são as meta-classes que caracterizam
todos os elementos da UML, assim como as classes são utilizadas para a modelagem de um
domínio. Este conceito ficará mais claro adiante, quando o conceito de classes será abordado.
A biblioteca Super-Structure define todos os elementos de diagramação da UML, organizado
em três conjuntos de Diagramas em que os elementos são admitidos: Estrutural,
Comportamental e Suplemento (OMG, 2007).
Os diversos diagramas disponíveis na UML permitem a descrição de várias
características de um domínio. Entre os diagramas há uma subdivisão que separa claramente
34
os diagramas estruturais dos diagramas comportamentais. A figura 1 permite a visualização da
classificação dos diagramas.
Figura 1. Classificação dos diagramas da UML
Fonte: Autor
Os diagramas estruturais mostram os aspectos estáticos dos objetos, que são todas as
características imutáveis dos objetos independentemente do comportamento dinâmico do
domínio. Abaixo segue uma breve descrição de cada diagrama estrutural:
a) Diagrama de Classes: descreve as classes e seus relacionamentos, sendo que uma
classe descreve um conjunto de objetos que compartilham as mesmas
características, restrições e semântica;
b) Diagrama de Estrutura de Composição: permite a modelagem dos elementos
interconectados de uma configuração, explicando os papéis de cada parte e de
como trabalham juntas;
c) Diagrama de Componente: define os módulos físicos e relacionamentos de um
sistema. Muito utilizado no desenvolvimento de software, onde são definidas
unidades modulares para o desenvolvimento de sistemas maiores;
d) Diagrama de Implantação: descreve o conjunto de hardware para a implementação
de um sistema;
e) Diagrama de Objetos: descreve fatos ou exemplos dos recursos do domínio;
f) Diagrama de Pacotes: utilizado para organizar e estruturar os artefatos de um
sistema.
Ao contrário dos diagramas estruturais, os diagramas comportamentais descrevem o
comportamento dinâmico e interações dos objetos de um domínio. Abaixo segue uma breve
descrição destes diagramas:
Diagramas
Diagramas
Estruturais
Diagrama de
Classes
Diagrama de
Estrutura de
Composição
Diagrama de
Componentes
Diagrama de
Implantação
Diagrama de
Objetos
Diagrama de
Pacotes
Diagramas
Comportamentais
Diagrama de
Atividades
Diagrama de
Interação
Diagrama de
Sequência
Diagrama de
Comunicação
Diagrama de
Visão Geral de
Interação
Diagrama de
Tempo
Diagrama de
Caso de Uso
Diagrama de
Estado de
Máquina
35
a) Diagrama de Atividades: descreve as seqüências e condições para a coordenação dos
comportamentos do sistema;
b) Diagramas de Interação: descreve os conceitos necessários que expressam as
interações do sistema dependendo de seus objetivos. São utilizados para obter uma
melhor compreensão das situações de interação dos elementos, sendo subdividido em
quatro diagramas que permitem capturar informações distintas dos elementos;
c) Diagrama de Caso de Uso: utilizado para capturar as necessidades funcionais do
sistema;
d) Diagrama de Estado de Máquina: utilizado para modelar o comportamento discreto
dos elementos do sistema, por meio de um sistema de transição de estados finitos.
A UML é bastante difundida pela comunidade de desenvolvimento de software devido
aos ricos recursos de modelagem, documentação e estruturação que a linguagem fornece.
Assim como estes recursos são utilizados por esta comunidade, nota-se que sua utilização
pode ser estendida para a modelagem de domínios para planejamento em IA. Conforme
mostrado no trabalho de Vaquero, Tonidandel e Silva (2006), a UML apresenta características
que permitem a modelagem de diversos domínios de planejamento de uma forma amigável e
de fácil interação.
4.1 UML.P
A UML.P é um subconjunto da UML que foca o desenvolvimento de domínios para
planejamento (VAQUERO; TONIDANDEL; SILVA, 2006). Apesar dos diversos recursos
disponíveis na UML para a descrição de domínios, a abordagem da UML.P ainda não utiliza
todos estes recursos que poderão ser utilizados posteriormente para enriquecer as descrições
dos domínios de planejamento. Conforme mencionado, a UML tem uma estrutura modular
que permite a utilização dos diagramas necessários para a modelagem de um domínio,
portanto, será utilizado apenas um conjunto de diagramas para a descrição dos domínios em
planejamento. A figura 2 mostra os diagramas que são utilizados na UML.P.
Conforme definido em Vaquero, Tonidandel e Silva (2006) quatro diagramas
constituem a UML.P, sendo dois estruturais e dois comportamentais. Dos diagramas
estruturais, o Diagrama de Classes fornece uma visão geral do domínio descrevendo as
características estáticas de seus elementos. Note que este diagrama não perderá as
características originais estabelecidas pela UML, porém nem todos os recursos disponíveis
neste diagrama serão utilizados pela UML.P. Os problemas de planejamento são modelados
pelo Diagrama de Objetos que utiliza as informações contidas no Diagrama de Classes para a
36
criação dos objetos participantes do modelo. O Diagrama de Estado de Máquina permite a
modelagem das ações de cada agente do domínio, enquanto que o diagrama de Caso de Uso
fornece uma estrutura para a documentação do modelo, onde são inseridas informações
descritivas das necessidades e objetivos que o modelo deve alcançar.
Figura 2. Diagramas da UML.P
Fonte: Autor
Os Diagramas de Classe, Diagrama de Estados de Máquina e o Diagrama de Objetos,
permitem a definição de modelos de domínios para planejamento de um modo simples e
claro. Estes diagramas formam o núcleo principal da UML.P. Abaixo, segue a descrição de
cada um dos diagramas na visão de planejamento.
4.1.1 Diagrama de Classes
O Diagrama de classes fornece uma visão geral da estrutura do domínio, sendo o
núcleo do processo de modelagem dos objetos de um domínio. Este diagrama modela os
recursos e mecanismos comuns de um domínio que serão utilizados durante o planejamento,
agrupando-os em conjuntos de classes que compartilham as mesmas características. Além dos
recursos, este diagrama modela os relacionamentos entre os recursos, definindo regras e
restrições dos relacionamentos entre os objetos. Como este diagrama é o centro que define os
recursos e usos de objetos de um modelo, todos os fatos modelados nos outros diagramas
devem respeitar as regras aqui definidas, caso contrário o Diagrama de Classes deve ser
ajustado para refletir as corretas características dos objetos modelados.
Diversos elementos compõem este diagrama, como as classes, associações e
generalizações. Nas seções a seguir serão explicadas as características de cada elemento que é
utilizado na UML.P e a semântica, descrita literalmente, que será utilizada em sua
modelagem. A semântica que se descreve foi obtida da semântica dada pela OMG com
Diagramas
Diagramas
Estruturais
Diagrama de
Classes
Diagrama de
Objetos
Diagramas
Comportamentais
Diagrama de
Caso de Uso
Diagrama de
Estado de
Máquina
37
limitações que adaptam este diagrama para a descrição de modelos para planejamento
automático.
Figura 3. Diagrama de Classes de um domínio de Logística
Fonte: Autor
4.1.2 Classes
A classe é o elemento principal do Diagrama de Classes. De acordo com a definição
da OMG (2007), as classes descrevem um conjunto de objetos que compartilham as mesmas
especificações de características, restrições e semântica. Pode-se exemplificar este conceito de
uma forma tradicional, por exemplo, na biologia os seres são classificados em classes, sendo
as classes dos mamíferos, aves, répteis, entre outros. Estas classes não definem um animal
específico, porém definem um conjunto de animais que possuem características em comum,
assim como as classes em UML.P definem conjuntos de objetos com características em
comum.
Figura 4. Símbolo de classe
Fonte: Autor
Sintaticamente as classes são representadas por um retângulo com três
compartimentos. O compartimento superior contém o nome da classe e em alguns casos
também acomoda o seu estereótipo. Um estereótipo permite informar a característica de uma
classe, por exemplo, as classes que efetuam ações em um modelo de domínio poderiam ter
seu estereótipo definido como Agente sendo obrigatório que todo agente possa executar ações
38
em um modelo de domínio. O compartimento central da representação contém os atributos de
uma classe e suas características. O compartimento inferior contém as ações que os objetos
das classes podem efetuar no modelo. A figura 4 exemplifica o símbolo de uma classe.
Os atributos que são modelados em uma classe possuem as seguintes características:
nome, tamanho, tipo, valor padrão e restrição. O valor padrão não é um parâmetro obrigatório
na modelagem, porém quando fornecidos todos os objetos derivados de uma classe que
possua atributos com valores padrões terão estes valores herdados para seus atributos. A
restrição poderá informar três situações distintas para os atributos, quando ausente o atributo
não tem qualquer restrição, quando Estático o atributo não poderá sofrer alterações por ações
do domínio e quando Somente Adiciona o atributo somente poderá sofrer incremento de
valores.
Operadores definem as ações que os objetos de uma classe executarão em um
domínio. Os operadores quando definidos em uma classe no Diagrama de Classes, ainda não
fornecem quais as condições e as alterações que os objetos farão em um domínio, esta
descrição é apenas um protótipo do operador sendo que sua completa descrição é dada nos
diagramas de estado de Máquina. Os operadores são dados com as seguintes características:
nome, parâmetros e valor de retorno caso seja necessário. Os parâmetros passados a um
operador possuem as mesmas características de um atributo, exceto pelo valor inicial,
restrição e tamanho. A figura 5 ilustra os atributos e operadores de uma classe, observando
que a quantidade de valores que um atributo pode armazenar é dada da forma [Vi...Vs], este
parâmetro também é comumente chamado de multiplicidade. A multiplicidade define que o
atributo é um vetor e possui um conjunto de valores de no mínimo Vi valores e no máximo Vs
valores. Nos casos onde não existem este parâmetro será assumido Vi = 0 e Vs = 1, ou seja,
serão atributos de valor unitário.
Figura 5. Exemplo de classe
Fonte: Autor
4.1.2.1 Semântica
De acordo com a semântica fornecida pelas definições da OMG (2007), e que se segue
neste trabalho, as classes devem possuir um nome único em um domínio e os objetos de uma
classe devem ter valores para cada atributo que faz parte de sua classe, em acordo com o tipo
e multiplicidade dos atributos. Quando um objeto for instanciado de uma classe, para cada
39
atributo da classe que tiver um valor inicial e se este valor não for especificado explicitamente
na instanciação, então o valor padrão será utilizado como o valor inicial do atributo do objeto.
Os operadores de uma classe podem ser invocados por um objeto, com a adequada
substituição de seus parâmetros. A execução de um operador poderá causar mudanças nos
atributos do objeto, observando as restrições impostas ao atributo, e poderá retornar um valor
como resultado, sendo o tipo do valor retornado definido pelo modelo da classe. A execução
de um operador também poderá causar mudança nos atributos de outros objetos e ainda causar
a criação ou destruição de um objeto.
4.1.3 Generalização
É possível também definir hierarquias em um Diagrama de Classes, que é chamada de
generalização. As hierarquias permitem que de uma classe mais geral ocorram especializações
de características pelos seus sucessores. A sintaxe de uma hierarquia é dada por uma reta e um
triângulo na extremidade da classe mais geral. A figura 6 exemplifica a sintaxe da hierarquia
entre classes, sendo que a Classe B é uma especialização da Classe A, ou seja, ela herdará os
atributos e operadores da Classe A, se somando as características da Classe B.
Figura 6. Exemplo de generalização
Fonte: Autor
4.1.3.1 Semântica
Uma generalização relaciona uma classe específica a uma classe mais geral, cada
instância da classe específica será igualmente uma instância da classe mais geral. Portanto,
características especificadas para instâncias de uma classe mais geral são implicitamente
especificadas para uma classe específica. Qualquer restrição que se aplique a uma classe mais
geral também se aplicará as instâncias das classes mais específicas.
4.1.4 Associações
As associações definem o relacionamento entre instâncias de classes, também
chamado de link, informando as características e restrições deste relacionamento. Uma
associação é representada por uma linha sólida conectando duas classes ou uma classe nela
mesma. A representação é incrementada com os seguintes itens:
40
a) Nome da Associação: O nome deverá ser posicionado próximo a linha, porém
longe das extremidades para não ser confundido com os nomes das extremidades.
Duas associações não poderão ter o mesmo nome quando interligarem as mesmas
classes;
b) Nome da Extremidade: Cada extremidade deverá ter um nome. Em uma
associação os nomes das extremidades deverão ser diferentes entre eles;
c) Multiplicidade: A multiplicidade de cada fim de associação restringe o número do
conjunto de links permitidos entre os objetos. A multiplicidade deve ser
informada nas extremidades da associação, próximo ao seu nome. A notação é
dada por dois valores naturais separados pelo símbolo “..”, que se tem “n
i
.. n
s
”
sendo n
i
≤ n
s
. Por exemplo, “1..10”, informa que deve existir no mínimo um link
entre objetos pertencentes às classes da associação e no máximo dez links entre
um objeto e outros objetos. Quando a multiplicidade não for informada, será
entendida a multiplicidade 0..1;
d) Mutabilidade: Existem duas restrições de associação que serão trabalhadas na
UML.P. A restrição somenteAdiciona e estático. Estas restrições serão utilizadas
quando o link entre dois objetos somente puder ser adicionado ou quando um link
não puder ser removido, ou seja, somenteAdiciona e estático respectivamente.
Quando a mutabilidade não for apresentada não haverá restrições quanto à adição
ou remoção dos links, exceto pela multiplicidade informada;
e) Navegabilidade: A navegabilidade determina como um objeto “enxerga” o outro
objeto. Sua representação é dada por uma seta na extremidade. Quando a seta não
é representada o objeto não “enxerga” o outro objeto. Na UML.P, pelo menos
uma das extremidades deverá ter a navegabilidade ativa;
f) Agregação: Existem dois tipos de agregação que serão utilizadas: Composição e
Compartilhada. A agregação compartilhada informa que um objeto faz parte de
outro objeto, mas caso o objeto agregado seja excluído não implicará na exclusão
do objeto agregado. Sua representação é dada nas extremidades sendo colocado
um “diamante” sem preenchimento. Uma composição informa que um objeto é
composto por outro e caso um deles seja excluído implicará na exclusão do outro
objeto. Uma composição limita sua multiplicidade em 1, ou seja, um objeto
deverá compor no máximo um objeto. Sua representação é dada da mesma
maneira que a agregação compartilhada exceto que o diamante é preenchido.
41
No exemplo da figura 7 tem-se a representação de uma associação com a maior parte
dos componentes possíveis representados.
Figura 7. Exemplo de associação
Fonte: Autor
4.1.4.1 Semântica
Parte da semântica já foi dada na descrição dos componentes permitidos a uma
associação, portanto aqui serão incluídas apenas as informações que não foram citadas
anteriormente.
Uma associação informa que podem existir links entre instâncias de classes. Um link é
uma tupla com um valor para cada fim da associação, respeitando o tipo da classe de cada
fim. Não poderá existir mais de um link entre um mesmo par de classes e pelo menos uma das
extremidades deve ser navegável.
4.1.5 Diagrama de Estados de Máquinas
O Diagrama de Estado de Máquinas, que é de maneira geral um grafo de máquinas de
estado, descreve a vida dos objetos em termos dos eventos e ações que ocorrem em um
modelo de um domínio. Os estados são representados pelos valores dos atributos dos objetos
e as mudanças dos estados, que são representados pelos arcos dos grafos (as ações), são
refletidas nas mudanças dos valores dos atributos que descrevem os objetos.
Toda classe capaz de executar uma ação ou que sofre uma ação no domínio tem seu
próprio Diagrama de Estado de Máquina. Um único Diagrama de Estado de Máquina não
especifica todas as mudanças que uma ação pode causar, mas especifica apenas os efeitos
locais sobre um objeto no domínio. Para uma completa visualização dos efeitos causados
pelas ações sobre o domínio é necessária a união de todos os Diagramas de Estado de
Máquina de um modelo.
As seções que seguem descreverão os componentes e suas funções do diagrama de
estado de máquina.
42
Figura 8. Exemplo de Diagrama de Estado de Máquinas
Fonte: Autor
4.1.6 Estado
Um estado modela uma situação quando um conjunto de condições estáticas são
verdadeiras. Uma situação estática é dada quando um objeto está aguardando uma ação ser
operada no domínio de modo a afetar seus atributos para a sua mudança de estado.
A representação de um estado é dada por um retângulo com dois compartimentos. O
compartimento superior contém o nome do estado, que deve ser único em um diagrama, e o
compartimento inferior contém os atributos e os respectivos valores que definem o estado.
Figura 9. Exemplo de estado
Fonte: Autor
4.1.6.1 Semântica
Um estado pode estar ativo ou inativo durante a execução de um modelo. Um estado
se torna ativo ou inativo após uma transição. Uma transição resulta na entrada ou na saída de
um estado.
4.1.7 Transição
Uma transição é uma relação direcional entre dois estados, sendo um estado de origem
e um estado de destino. Toda transição define uma ação num modelo, sendo constituída de
pré-condições e pós-condições para sua execução. A representação gráfica de uma transição é
dada por um arco com uma seta em uma das extremidades conectando os estados de origem e
43
de destino. Próximo ao arco são inseridas as condições de transição para a efetivação de uma
transição.
As condições são expressas pela formação BNF (Backus-Naur Form) abaixo:
<transição> ::= <ação> [[<pré-condição>] [‘/’ <pós-condição>]];
<ação> ::= ação que disparará a transição, deve respeitar o protótipo fornecido
as classes no Diagrama de Classes;
<pré-condição> ::= <atributo> ‘=’ <valor> [‘e’ <pré-condição>][‘ou’ <pré-
condição>];
< pós-condição> ::= <atributo> ‘=’ <valor> [‘e’ < pós-condição>][‘ou’ <pós-
condição>];
<atributo> ::= atributo de uma classe
<valor> ::= valor do atributo em acordo com o especificado no Diagrama de
Classes.
Figura 10. Exemplo da representação gráfica de uma transição
Fonte: Autor
O nome da ação que dispara uma transição deve estar de acordo com o protótipo
definido pelo Diagrama de Classes. As pré-condições fazem o papel de restrição para a
execução de uma ação, impedindo a execução de uma ação caso todos os atributos não
estejam de acordo com as restrições aqui impostas. As pós-condições são conseqüências da
execução da transição, inserindo, excluindo ou alterando valores de atributos ou novos objetos
em um modelo após a execução da ação.
4.1.7.1 Semântica
Havendo a solicitação da execução de uma ação, os objetos envolvidos deverão ter
seus estados de origem (atributos) e as pré-condições respeitados, caso contrário a transição
não será executada. Como conseqüência, se tem a mudança de estado dos objetos e a
validação das pós-condições da ação.
4.1.8 Estado Inicial
Um estado inicial é um pseudo-estado que indica qual a condição inicial que um
objeto inicia dentro de um modelo. A sua representação gráfica pode ser visualizada na figura
11.
<ação> [[<pré-condição>] [„/‟ <pós-condição>]]
44
Figura 11. Exemplo de estado inicial
Fonte: Autor
4.1.8.1 Semântica
Este pseudo-estado representa o estado padrão que é a origem de uma simples
transição. Poderá existir no máximo um estado inicial em um Diagrama de Estado de
Máquinas.
4.1.9 Estado Final
Um estado final é um tipo especial de estado, vide figura 12. Alcançando este estado o
objeto terá finalizado a execução de uma tarefa ou ação.
Figura 12. Exemplo de estado final
Fonte: Autor
4.1.9.1 Semântica
Quando um estado final é encontrado, significa que um ciclo de tarefas de um objeto
foi executado.
4.1.10 Diagrama de Objetos
Figura 13. Exemplo de diagrama de objetos
Fonte: Autor
O Diagrama de Objetos permite a definição de um ou mais problemas em
planejamento. Este diagrama permite que se descrevam todos os objetos e suas características
45
em seu estado inicial e estado final, sendo que o estado inicial e o estado final são descritos
em Diagramas de Objetos separados.
Os objetos destes diagramas mantêm as características definidas pelo Diagrama de
Classes. Caso seja necessária a adição ou remoção de alguma característica em um objeto
modelado, será necessária a correção do Diagrama de Classes.
4.1.11 Instância
Uma instância é uma entidade modelada de uma especificação, como as do Diagrama
de Classes. A instância respeita todas as características e restrições de sua especificação,
sendo chamada de objeto quando derivada de uma classe e de link quando derivada de uma
associação.
Os objetos são modelados de acordo com a sua apresentação de classe, exceto que
cada objeto deve receber um nome único no modelo. Seus atributos, também chamados de
slot na UML, receberão os devidos valores. O compartimento de operadores é suprimido na
modelagem.
Os links da mesma forma são modelados de acordo com a apresentação do Diagrama
de Classes, exceto que apenas seus nomes e os nomes das extremidades são apresentados.
Figura 14. Exemplo de instâncias
Fonte: Autor
4.1.11.1 Semântica
Uma instância especifica a existência de uma possível entidade em um instante fixo de
tempo num modelo, informando sua descrição completa. A entidade deve obedecer a
especificação de seu modelo incluindo as características de seus atributos. Caso uma instância
não possua atributos, não significará que não existem atributos definidos pela sua
especificação, mas que os valores padrões serão utilizados pelos atributos. Caso um atributo
não possua um valor padrão, será obrigatória sua definição na instância.
4.2 Discussão
Apesar de a UML ser bem difundida no mercado, sua semântica é dada de forma
descritiva e não completa. Ou seja, as descrições da semântica são de certa maneira claras,
porém deixam margem para a interpretação do leitor, podendo causar interpretações diversas
46
para um mesmo diagrama. Também se encontra no documento da OMG (2007), dentro da
descrição de alguns itens da linguagem, o tópico de “Pontos de Variação da Semântica”, ou
seja, pontos onde há entendimentos diferentes ou falta de definição sobre a semântica do item
em discussão. Note que a dificuldade de criar uma semântica completa para a UML é devido a
sua abrangência e flexibilidade, em muitas vezes a formalização de uma semântica completa e
concisa implica na parametrização total da linguagem, tornando-a inflexível. Essa
inflexibilidade vai de encontro ao objetivo da UML que é ser uma linguagem flexível e
dinâmica para a descrição de diversos tipos de domínios e aplicações.
Diversos trabalhos estudam a formalização da semântica da UML (BERARDI et al.,
2003) (EVANS et al., 1998) (BRUEL, FRANCE, 1998), porém falham em obter uma
abordagem abrangente que permita a inclusão de todas as funcionalidades da linguagem.
A falta de uma semântica precisa para a UML, e conseqüentemente para a UML.P,
impede de se efetuar raciocínio lógico automático sobre as descrições desenvolvidas nesta
linguagem. Como o desenvolvimento de uma semântica precisa e completa para a UML.P não
é parte do escopo deste trabalho, trabalhar-se-á com a interpretação da UML.P para uma
linguagem que tenha uma semântica que possibilite o raciocínio automático sobre os
domínios desenvolvidos.
À primeira vista podería-se interpretar os domínios desenvolvidos em UML para
PDDL, porém ela é uma linguagem descritiva não orientada a objetos e os diagramas
utilizados na descrição de domínios em UML.P possuem mais informações do que pode ser
descritas pela PDDL (TONIDANDEL, VAQUEIRO, SILVA, 2006). Como exemplo, pode-se
citar a multiplicidade do Diagrama de Classes que não pode ser codificada diretamente nas
descrições da PDDL.
A linguagem de interpretação deve possuir uma estrutura que permita a descrição de
todas as informações dos diagramas da UML.P e que forneça suporte de orientação a objetos.
Um modelo de representação orientado a objetos procura agrupar os dados em torno dos
objetos, ou seja, o usuário pode acessar toda a informação sobre um objeto tendo o seu
conhecimento. Essa filosofia é diferente do modelo relacional onde os dados são agrupados
em torno das propriedades, ou seja, as informações sobre um objeto são espalhadas entre
diferentes propriedades atribuídas ao objeto (KIFER, LAUSEN, WU, 1995). Note que o
modelo de representação orientado a objetos é mais próximo da representação dada pela
UML.P que é fundamentalmente baseada nos conceitos de orientação a objetos.
Em (RAMALHO, ROBIN, SCHIEL, 2004), foi proposto a utilização da Concurrent
Transaction Frame Logic (CTFL) para a formalização dos diagramas de atividades e classe da
47
UML. A CTFL é a combinação das lógicas Concurrent Transaction Logic (CTL), que é uma
lógica que modela o comportamento de atualização, transações, processos de comunicação e
restrições de execução temporal em banco de dados (RAMALHO, ROBIN, SCHIEL, 2004), e
F-Logic, que é uma lógica que modela conceitos de orientação a objeto. A utilização da CTFL
mostrou a possibilidade da utilização da F-Logic como uma linguagem de suporte a UML.P,
porém a proposta de interpretação apresentada não foi adequada para a proposta deste
trabalho, pois haveria a necessidade da criação de objetos desnecessários para a aplicação em
planejamento, criando a necessidade do desenvolvimento de uma nova interpretação da
UML.P para F-Logic.
A F-Logic é uma linguagem lógica que fornece a expressividade para se trabalhar com
a UML.P, fornecendo uma semântica bem estudada e que permite raciocínio lógico
automático. A F-Logic tem uma semântica com modelo teórico e uma prova teórica completa
e consistente, fornecendo suporte a tipos, hierarquia, herança não monotônica, polimorfismo,
entre outras características. Escolheu-se esta lógica neste trabalho por ser uma lógica que
permite extensão e por haver trabalhos que estendem sua lógica para trabalhar com a
dinâmica da base de conhecimento (KIFER, 1995) que não será abordado neste trabalho.
48
5 F-LOGIC
A F-Logic é uma lógica de 1ª ordem baseada em frames. De acordo com Minsky
(1974), frames são estruturas de dados que representam situações estereotipadas. Apesar da F-
Logic ter seu nome diretamente ligado às terminologias de IA, como frames, slots e outros, a
F-Logic tem em mente a abordagem da orientação a objetos e a nomenclatura feita por Kifer
(1995) será mantida neste trabalho.
Os modelos descritos em F-Logic mantêm as características e métodos condensados
em torno dos objetos, oferecendo uma estrutura organizacional diferente da oferecida pela
Lógica de 1ª Ordem tradicional, que organiza as informações em torno dos atributos. O
exemplo abaixo, extraído parcialmente de um modelo do mundo de blocos, permite visualizar
esta diferença de forma rápida.
Lógica de 1ª Ordem:
holds(hand, blockA)
on(blockB, table)
on(blockC, blockB)
F-Logic
hand[holds -> blockA]
blockB[on -> table]
blockC[on -> blockB]
No exemplo têm-se a descrição de uma situação simples em ambas as lógicas. Neste
modelo observa-se que hand segura blockA, blockB está sobre table e blockC está
sobre blockB. O símbolo ->, da F-Logic, denota que um atributo possui um valor, do
exemplo o objeto hand possui um atributo holds que tem o valor blockA. A sintaxe da
linguagem F-Logic será inteiramente explicada nas seções seguintes.
Além da estrutura focada nos objetos, a F-Logic também nomeia e agrupa os
conjuntos de objetos que compartilham características em comum através de assinaturas.
package[isAt => place; isIn => vehicle]
No exemplo acima, extraído de um modelo de logística, a assinatura em F-Logic
informa que os objetos do tipo package têm dois atributos, isAt e isIn, sendo que cada
atributo poderá conter um valor do tipo place e vehicle respectivamente. O símbolo =>
é o elemento que determina o tipo do atributo, este símbolo também indica que apenas um
único valor pode ser dado para o atributo. Porém quando um atributo puder armazenar mais
de um valor o símbolo de assinatura deverá ser dado por =>>.
49
A abordagem da F-Logic traz vantagens sob o prisma da UML.P em relação à Lógica
de 1ª Ordem, pois sua estrutura sintática e semântica é próxima a concepção da UML.P. A
sintaxe e semântica da F-Logic é correta e completa (KIFER, LAUSEN, WU, 1995),
fornecendo a estrutura necessária para o planejamento automático dos modelos desenvolvidos
em UML.P e interpretados em F-Logic. Estas e outras vantagens ficarão claras durante a
apresentação da F-Logic e dos próximos capítulos deste trabalho.
5.1 Sintaxe
Conforme o artigo de Kifer, Lausen e Wu (1995), a linguagem é constituída de um
alfabeto L, chamado de F-Linguagem, composto de:
a) um conjunto de construtores de objetos, F;
b) um conjunto infinito de variáveis, V;
c) símbolos auxiliares, tais como (, ), [, ], {, }, ->, =>, entre outros;
d) conectivos e quantificadores usuais da Lógica de 1ª. Ordem, , , ¬, e .
Os construtores de objetos são os símbolos de função da F-Logic que quando têm
aridade igual a 0 também são chamados de constantes, e quando têm aridade ≥ 1 são
utilizados para a construção de termos complexos. Um termo identidade (id-term) é um termo
usual de lógica de primeira ordem, composto de símbolo de funções e variáveis. Os id-terms
fundamentais, ou seja, livre de variáveis, tem o papel de identificador do objeto lógico
(KIFER, LAUSEN, WU, 1995). Portanto, num termo como package[isAt =>
place], tem-se que package, isAt e place são id-terms.
Através da utilização do alfabeto L pode-se construir fórmulas em F-Logic. As
fórmulas simples, ou seja, sem conectivos lógicos, são chamadas de F-Moléculas ou fórmulas
moleculares. Os termos package[isAt => place], pkg1[isAt->vhcl1] e
vhcl1:vehicle, são alguns exemplos de F-Moléculas que denotam respectivamente uma
assinatura, uma expressão de dados escalar e uma definição “é-um”. Nas seções seguintes
serão definidas a sintaxe e semântica destas construções.
Assim como adotado no trabalho de Kifer, Lausen e Wu (1995) será mantida a
convenção adotada inspirada no Prolog, onde um símbolo que inicia em letra minúscula
denota um id-term fundamental e o símbolo que inicia em letra maiúscula denota um id-term
que pode ser não fundamental.
50
Definição 5.1.1: Uma molécula em F-Logic (F-Molécula) é dada pelas seguintes afirmações
(KIFER, LAUSEN, WU, 1995):
1. Uma definição “é-um” é dada da forma C::D ou da forma O:C, onde C, D e O
são id-terms;
2. Uma molécula de objeto é dada na forma de O[uma lista separada por „;‟ de
expressões de métodos]. Uma expressão de método pode ser:
a. Expressão de dados não herdável:
i. Expressão escalar (k ≥ 0):
MétodoEscalar@Q
1
,...,Q
k
-> T
ii. Expressão de conjunto de valores (l, m ≥ 0):
MétodoConjunto@R
1
,...,R
l
->> {S
1
,...,S
m
}
b. Expressão de dados escalares e de conjunto de valores herdáveis. Essas
expressões são como as expressões de dados não herdáveis exceto que os
símbolos -> e ->> são substituídos por *-> e *->> respectivamente.
c. Expressão de Assinatura:
i. Assinatura escalar (n, r, ≥ 0):
MétodoEscalar@V
1
,...,V
n
=> {A
1
,...,A
r
}
ii. Assinatura de conjunto de valores (s, t, ≥ 0).
MétodoConjunto@W
1
,...,W
s
=>> {B
1
,...,B
t
}
A expressão C::D construirá estruturas de subclasses, onde C será uma subclasse de
D, enquanto que a expressão O:C construirá estruturas que informam que O é um membro da
classe C. No exemplo abaixo segue uma demonstração simples da construção destas
estruturas.
caminhão :: veículo
avião :: veículo
c1 : caminhão
a1 : avião
Do exemplo, tem-se que caminhão é uma subclasse de veículo, avião é uma
subclasse de veículo, c1 é um objeto de caminhão e a1 é um objeto de avião. Perceba
que a sintaxe desta definição é simples, permitindo a construção de cadeias de hierarquia de
classes.
As expressões de dados são construídas a partir de id-terms. A expressão „O‟
representa um objeto, sendo que o MétodoEscalar e o MétodoConjunto são métodos que são
invocados dos objetos. As setas ->, *-> e => indicam que o método correspondente é
51
escalar, enquanto que as setas ->>, *->> e =>> indicam que o método correspondente é uma
função que retorna um conjunto de valores. T e S
m
são id-terms que representam os valores de
saída das funções quando invocados pelos seus respectivos objetos com os valores de Q
k
e R
l
,
que também são id-terms.
Os símbolos *-> e *->> denotam expressões de dados herdáveis, conforme definição
5.1.1. Esses métodos são utilizados para que os objetos de uma classe herdem características
específicas para os métodos. Por exemplo, suponha que no exemplo anterior um veículo tenha
o seguinte método herdável rodas *-> 4, esse método será herdado pela classe caminhão
que resultará em caminhão[rodas *-> 4] e também pela classe avião. Porém, este
número de rodas não será verdadeiro para a maioria dos caminhões e, portanto, pode-se
alterar este método para caminhão[rodas *-> 10]. Essa alteração é permitida na F-
Logic e é conhecida como overriding. Quando um objeto é declarado como membro de uma
classe a propriedade de herança é retirada, do exemplo c1[rodas -> 10], porém o
método é herdado com o valor definido pelas classes superiores do objeto.
As assinaturas fornecem restrições de tipos quanto à classe, onde os valores de A
r
e B
t
são id-terms que representam os tipos dos resultados e seus respectivos métodos quando
solicitado de um objeto da classe, com argumentos do tipo V
n
e W
s
, que são id-terms. Observe
que existem simplificações que podem ser feitas quando da descrição dos métodos, ou seja,
quando não houver parâmetros para um método o símbolo „@‟ poderá ser omitido assim como
quando aparecer apenas um elemento em um conjunto os “{}” e “()” poderão ser omitidos
(KIFER, LAUSEN, WU, 1995). Abaixo seguem exemplos de assinaturas e objetos.
veículo[cargaMáxima => inteiro]
caminhão[pneuFurado@posição => booleano]
caminhão::veículo
t1:caminhão
t1[cargaMáxima -> 10]
t1[pneuFurado@esquerdo -> true]
O exemplo apresenta duas assinaturas, sendo a de um veículo, que contém o
atributo de cargaMaxima, e a assinatura de um caminhão com um método
pneuFurado que informa se o pneu passado como parâmetro está ou não furado. Os id-
terms cargaMaxima e pneuFurado denotam o parâmetro MétodoEscalar de uma
molécula da definição 5.1.1. Assim como os parâmetros inteiro e caminhão fazem o
52
papel do parâmetro A
1
da assinatura escalar, posição faz o papel de V
n
, 10 e true fazem
o papel T enquanto que esquerdo faz o papel de Q
n
do método escalar.
Note que devido ao caminhão ser um veículo, t1 herda os atributos e métodos do
veículo e do caminhão. A semântica destas funções ficará mais clara quando for definida a
semântica da linguagem.
Fórmulas complexas ou F-Fórmulas em F-Logic são construídas a partir de F-
Moléculas pela utilização de conectivos e quantificadores, portanto tem-se:
Definição 5.1.2: (KIFER, LAUSEN, WU, 1995)
a) F-Moléculas são F-Fórmulas;
b) ab, ab, ¬a são F-Fórmulas se a e b também forem;
c) Xa, Yb são F-Fórmulas se X e Y são variáveis e a e b são F-Fórmulas;
d) um literal é uma fórmula molecular ou sua negação;
e) o conectivo de implicação „←‟ é definido como na lógica clássica, ou seja, a ←
b é um atalho para a¬b.
As abreviações também serão utilizadas na constituição das fórmulas em F-Logic. Por
exemplo, a expressão A:K[ScMeth@Z -> (B:M); StMeth@W,Y ->> (C:N)] é
uma abreviação de A:K A[ScMeth@Z -> (B)] B:M A[StMeth@W,Y ->>
(C)] C:N.
5.2 Semântica
Conforme Kifer, Lausen e Wu (1995) a estrutura semântica da F-Logic é chamada de
F-Estrutura, onde dado uma F-Linguagem L, sua F-Estrutura é dada pela tupla I=(U,
U
,
U
,
I
, I
->
, I
->>
, I
*->
, I
*->>
, I
=>
, I
=>>
):
a) U: é o domínio de I;
b)
U
: esta é uma relação irreflexível de ordem parcial em U que é a representação
dos relacionamentos de subclasses em U, ou seja, a
U
b é interpretado como a é
uma subclasse de b. Quando a b ou a = b então a relação será dada por a
U
b,
a notação também é estendida para relacionar tuplas em U onde existe a relação
entre os componentes da seguinte forma
, sendo que ,
;
c)
U
: esta é uma relação binária em U que é utilizada para modelar os membros de
uma classe, ou seja, a
U
b é interpretado como a é um membro de b. Assim como
53
a notação foi estendida para relacionar tuplas em U, obtém-se
, sendo
que ,
;
Deve-se salientar que se a
U
b e b
U
c então a
U
c. Ou seja, esta relação diz que
qualquer membro de uma classe será membro de sua superclasse.
d) I
: →
=0
Total(U
i
, U). Esta função interpreta cada objeto construtor k em U, f
, por uma função total U
k
→ U. Para k=0, I(f) pode ser identificado com um
elemento de U. Este mapeamento é usado para associar um elemento de U a um
id-term;
Os id-terms de U também podem denotar métodos em F-Logic, sendo que um método
é uma função dada por um objeto que contém mais uma lista de parâmetros apropriados,
tendo seu mapeamento para outro objeto ou conjunto de objetos, dependendo se o método é
escalar ou de conjuntos. Os mapeamentos abaixo definem esta funcionalidade.
e) I
->, *->
: →
Parcial(U
i+1
, U)
=0
. Cada mapeamento associa uma tupla de
função parcial para todos os elementos de U. Para cada tupla existe uma função
parcial {f
k
: U
k+1
→U|k≥0}, para cada método com aridade ≥ 0. Este mapeamento
permite que os métodos de U, escalares, possam ser invocados com aridades
diferentes;
f) I
->>, *->>
: →
Parcial(U
i+1
, (U))
=0
. Este mapeamento difere do
mapeamento anterior por associar funções parciais de U
k+1
→P(U) para cada
elemento de U. Perceba que P(U) denota o super-conjunto de U, e, portanto, este
mapeamento é utilizado para métodos de conjuntos;
Os símbolos precedidos por * denota que as propriedades dos objetos são herdáveis
enquanto que os símbolos não precedidos por * não tem suas propriedades herdáveis.
Dos mapeamentos acima se entende que I
->
(m) é uma tupla infinita de funções
parametrizadas pela aridade k ≥ 0. Para referenciar uma função com k componentes escreve-
se
>
()
(m), sendo que esta função interpreta o método escalar não herdável m com k
parâmetros. A mesma simbologia é utilizada para os métodos de conjuntos e herdáveis, ou
seja,
>>
()
(m),
>
()
(m) e
>>
()
(m). Todos os mapeamentos são funções de k+1 argumentos,
isto porque o primeiro argumento do mapeamento é o objeto que possui o método e os outros
k argumentos são os parâmetros do método, portanto
>
()
(m)(obj, a
1
, …, a
k
) é uma solicitação
para que o objeto obj execute o método m com os parâmetros a
1
, …, a
k
.
54
Os mapeamentos I
=>
e I
=>>
expressam a assinatura dos métodos, definindo os tipos de
seus argumentos e o tipo de resultado retornado pelos métodos.
g) I
=>, =>>
: U →
ô
=1
(
+1
,
( )) .
( ) é o
conjunto V de todas as classes e superclasses de U, onde se v V este conjunto
contém todas as superclasses de v (upward-closure). A função
ParcialAntiMonotônico denota o conjunto de todas as funções parciais anti-
monotônicas de U
i+1
para
( ). Uma função parcial anti-monotônica é dada por,
se p:U
k
→
( ), ,
e
sendo p() definido, então p(
) também é
definida e p(
) p().
Assim como definido em I
->
(m), será utilizada a mesma notação com I
=>
e I
=>>
para
denotar uma assinatura de k componentes (I
=>
(k)
(m) e I
=>>
(k)
(m)). O significado de
=>
()
(m) é de
definir o tipo da função
>
()
(m), definindo o tipo da classe do objeto e a classe dos seus
argumentos. Similarmente o significado é o mesmo para
>>
()
(m) e
=>>
()
(m).
Pode-se expor agora a idéia de anti-monotonicidade e upward-closure de uma maneira
mais clara. Se um objeto
>
()
(m)(obj,
) é do tipo classe (
>
()
(m)(obj,
)
U
classe),
então este objeto será membro de todas as superclasses de classe (
>
()
(m)(obj,
)
U
classe’, para toda classe’ classe), que define a idéia de upward-closure. De forma similar,
se um método é definido em uma classe (
=>
(
,
)), todos os membros desta
classe e subclasses poderão invocar o método, sendo que o tipo do objeto e dos argumentos
do método poderão ser um elemento da classe ou subclasse definida pela assinatura resultando
em um valor membro da classe ou subclasse definida pela assinatura, que define a idéia de
anti-monotonicidade.
5.2.1 Satisfação das F-Moléculas pelas F-Estruturas
Uma atribuição de variáveis v é uma função de mapeamento do conjunto de variáveis
V para o domínio U, onde v(d)=I
(d) se d e tem aridade 0 e, recursivamente,
v(f(…,T,…))=I
(f)(…,v(T),…) (KIFER, LAUSEN, WU, 1995).
Dado uma F-Estrutura I e a função v, se pode afirmar que uma F-Molécula T[…] é
verdadeira em I, com respeito à atribuição de variáveis, se o objeto v(T) em I tem as
propriedades que a fórmula T[…] diz que tem. Essa afirmação será escrita como I
v
T[…].
Uma F-Molécula, P::Q ou P:Q é verdadeira se os objetos v(P) e v(Q) são relacionados entre
eles através de
U
ou
U
(KIFER, LAUSEN, WU, 1995).
55
Definição 5.2.1.1: (KIFER, LAUSEN, WU, 1995) Seja I uma F-Estrutura e G uma F-
Molécula, escreve-se que I
v
G se e somente se todas as afirmações abaixo forem
verdadeiras:
a) Quando G é uma expressão “é-um”, então:
i. v(Q)
U
v(P), se G = Q::P; ou
v(Q)
U
v(P), se G = Q:P.
b) Quando G é uma molécula de objeto da forma O[uma lista separada por „;‟ de
expressões de métodos], então para todas as expressões de métodos E em G, as
seguintes condições tem de ser verdadeiras:
ii. Se E é uma expressão escalar não herdável da forma ScalM@Q
1
,...,Q
k
-
>T, os elementos
>
()
(v(ScalM))(v(O), v(Q
1
), …, v(Q
k
)) precisam ser definido
e igual a v(T). Condições similares devem ser verdadeiras se E for uma
expressão escalar herdável, exceto que
>
()
deverá ser substituído por
>
()
;
iii. Se E é uma expressão de conjunto de valores não herdável da forma
SetM@R
1
,...,R
l
->>{S
1
,...,S
m
}, o conjunto
>>
()
(v(SetM))(v(O),
v(R
1
), …, v(R
l
)) precisa ser definido e conter o conjunto {v(S
1
), …, v(S
m
)}.
Condições similares devem ser verdadeiras se E for uma expressão de
conjunto de valores herdável, exceto que
>>
()
deverá ser substituído por
>>
()
;
iv. Se E é uma expressão de assinatura escalar ScalM@Q
1
,...,Q
n
=>{R
1
,…,
R
u
}, então o conjunto
=>
()
(v(ScalM))(v(O), v(Q
1
), …, v(Q
n
)) precisa ser
definido e conter {v(R
1
),..., v(R
u
)};
v. Se E é uma expressão de assinatura de conjunto de valores
SetM@V
1
,...,V
s
=>>{W
1
,...,W
v
}, então o conjunto
=>>
()
(v(SetM))(v(O), v(V
1
), …, v(V
s
)) precisa ser definido e conter {v(W
1
),...,
v(W
v
)}.
As formulas a b, c d, ¬e, ( e ( são definidas, respectivamente, como
(KIFER, LAUSEN, WU, 1995):
c) I
v
(a b) se e somente se I
v
a ou I
v
b;
d) I
v
(c d) se e somente se I
v
a e I
v
b;
e) I
v
(¬e) se e somente se I
v
e;
56
f) I
v
(X)g se e somente se I
μ
g para todo μ que concorda com v em qualquer lugar;
g) I
v
(Y)f se e somente se I
μ
f para algum μ que concorda com v em algum lugar.
Para uma fórmula fechada se pode deixar de mencionar v e escrever simplesmente
Ia, pois o significado da formula é independente da escolha da variável atribuída. Portanto,
uma F-Estrutura (I) é um modelo de fórmula fechada (a) se e somente se Ia. Se S é um
conjunto de formulas e a é uma fórmula, pode-se escrever que S
a se e somente se a é
verdadeiro em todos os modelos de S (KIFER, LAUSEN, WU, 1995).
5.3 Regras de inferência
Através da semântica apresentada, Kifer, Lausen e Wu (1995) mostram que a F-Logic
é composta de 12 regras de inferência e um axioma, agrupados em 4 conjuntos e organizados
por finalidade. De acordo com eles, esta grande quantidade de regras é conseqüência da
semântica rica dos sistemas orientados a objetos.
Antes da apresentação das regras de inferência da F-Logic, algumas observações serão
feitas quanto ao processo de unificação de id-terms e F-Moléculas devido algumas
características singulares desta lógica. O processo de unificação segue o mesmo padrão
adotado na lógica clássica, por exemplo: nas expressões “é-um” L
1
= carro::veículo e
L
2
= A::veículo, a unificação de L
2
em L
1
será {A\carro}. Porém, na F-logic as
moléculas de objetos podem não ser simétricas causando diferença no processo de unificação.
Por exemplo: sejam duas moléculas T
1
= X[K->W] e T
2
= A[B->C; D*->E], a
unificação de T
1
em T
2
será dada pelo conjunto {X\A, K\B, W\C}, porém a unificação de
T
2
em T
1
não será possível devido à impossibilidade de unificação do átomo A[D*->E] em
T
1
. Este conceito é obtido pela definição abaixo fornecida em (KIFER, LAUSEN, WU,
1995).
Definição 5.3.1 (Unificação assimétrica de Moléculas de Objetos). Sejam L
1
=S[...] e
L
2
=S[...] pares de moléculas de objetos com o mesmo identificador de objeto S. Dize-se
que L
1
é uma sub-molécula de L
2
, chamado de L
1
L
2
, se e somente se todos os membros
de L
1
também forem membros de L
2
. Portanto uma substituição φ será um unificador de L
1
em L
2
se e somente se φ(L
1
) φ(L
2
).
Está claro até o momento o conceito de unificação de id-terms, moléculas “é-um” e
moléculas de objetos, porém ainda é necessária a definição do conceito de unificador mais
geral (mgu) para a F-Logic. O conceito de mgu da lógica clássica não pode ser aplicado
57
diretamente na F-Logic devido aos objetos moleculares com expressões de conjunto de
valores, e.g. E
1
=m[att ->> {g, d}]. Dada a expressão E
2
=m[att ->> X], a
unificação de E
2
em E
1
resultará em duas possibilidades dadas por {X\g} e {X\d} que
poderão ser chamadas de mgu. Porém nenhuma delas é mais geral do que a outra, sendo
necessária a definição de conjuntos completos de unificares mais geral (KIFER, LAUSEN,
WU, 1995).
Definição 5.3.2: (Unificador Mais Geral) Sejam L
1
e L
2
pares de moléculas e α e β pares de
unificadores de L
1
em L
2
. Diz-se que α é geral a β, denotado por α β, se e somente se existir
uma substituição φ que faça β = φ α. Um unificador α de L
1
em L
2
é mais geral (mgu) se
para todo unificador β, β α implica que α β. Um conjunto Σ de unificadores mais gerais
de L
1
em L
2
é completo se para todo unificador µ de L
1
em L
2
exista α Σ que satisfaça α
µ.
Nas regras de inferência que serão apresentadas será utilizado o termo
1
,
2
para denotar um unificador mais geral de L
1
em L
2
, isto é necessário devido à assimetria entre
as moléculas de objetos na F-Logic (KIFER, LAUSEN, WU, 1995). Os símbolos que serão
utilizados nas regras de inferência seguirão o seguinte padrão: L e L` denotarão literais
positivas, C e C` denotarão cláusulas positivas e os demais termos denotarão id-terms.
5.3.1 Regras de inferência principais
Tabela 7. Regras de inferência principais
Resolução
¬ ,
, =
(, )
( )
Nesta regra e nas demais, deve-se ressaltar que se L e L` forem
moléculas de objetos, sua unificação poderá não ser simétrica,
podendo existir o
(, ), mas não existir o contrário.
Fatoração
, =
(, )
( )
¬ ¬
, =
(, )
(¬ )
Observe que a regra de fatoração tem resultado dependente da
polaridade do literal observado.
Paramodulação
, (
) , =
(, )
(
\
)
O símbolo denota uma relação congruente entre os predicados, ou
seja, se T` e T`` são id-terms, então ter-se-á que
se e
58
somente se v(
) = v() (KIFER, LAUSEN, WU, 1995). O termo
\
denota que a ocorrência de T é substituída por
.
Regras de Inferência principais da F-Logic.
5.3.2 Regras de inferência “é-um”
Tabela 8. Regras de inferência “é um”
(Axioma)
Refletividade
X::X
Toda Classe é subclasse de si mesma.
Aciclicidade
: :
, (
′
: : ′)
′
, =
(
,
,
′
, ′
)
(
′)
O mgu aqui denota que existe um unificador para tal que (P) =
(P') e (Q) = (Q'), essa forma de expressão será utilizada mais
adiante com o mesmo significado. Através desta regra podem-se
determinar classes iguais em um modelo.
Transitividade
: :
, (
′
: : ′)
′
, =
(, ′)
(
: : ′
′)
A regra de transitividade mostra que toda subclasse será membro
da classe mais superior de uma cadeia hierárquica de classes.
Inclusão de Subclasse
:
, (
′
: : ′)
′
, =
(, ′)
(
: ′
′)
Assim como a regra de transitividade mostra a hierarquia de
subclasses, esta regra mostra que um membro de uma classe
também será membro das classes superiores a que este objeto está
contido.
Regras de inferência que permitem a hierarquia das classes.
5.3.3 Regras de inferência de tipos
Tabela 9. Regras de inferência de tipos
Herança de
tipo
[@
,,
=> ] , (′: : ′)
′
, =
(, ′)
(′[@
, ,
=> ] ′)
[@
, ,
=>> ] , (′: : ′)
′
, =
(, ′)
(′[@
, ,
=>> ] ′)
Todas as subclasses herdam as propriedades das suas classes superiores. Essa
característica se aplica para as propriedades escalares e de conjuntos.
59
Restrição de
Entrada
[@
, ,
, ,
=> ] , (
′′
: :
′
)
′
, =
(
,
′
)
([@
, ,
′′
, ,
=> ] ′)
[@
, ,
, ,
=>> ] , (
′′
: :
′
)
′
, =
(
,
′
)
([@
, ,
′′
, ,
=>> ] ′)
Essa regra é conseqüência da regra de transitividade.
Relaxament
o de Saída
[@
, ,
=> ] , (′: : ′′)
′
, =
(, ′)
([@
, ,
=> ′′] ′)
[@
, ,
=>> ] , (′: : ′′)
′
, =
(, ′)
([@
, ,
=>> ′′] ′)
Essa regra é conseqüência da regra de transitividade.
Regras de inferência que efetivam a transferência das características das classes para suas herdeiras.
5.3.4 Outras regras de inferência
Tabela 10. Outras regras de inferência
Escalaridade
@
, ,
>
,
′
′
@
′
, ,
′
>
′
′
,
=
(
, ,
, ,
,
′
,
′
,
′
, ,
′
)
(
′
′)
@
, ,
>
,
′
′
@
′
, ,
′
>
′
′
,
=
(
, ,
, ,
,
′
,
′
,
′
, ,
′
)
(
′
′)
Através desta regra podem-se determinar objetos que são iguais num modelo.
Merging
,
′
′
, =
,
′
,
′′
= (
,
′
)
′′ ( ′)
A união de atributos de moléculas é dada por esta regra, sendo que L‟‟ será a
junção dos atributos da mesma F-Molécula.
Eliminação
¬[ ]
Conforme verificado em sua semântica qualquer F-Molécula da forma P[ ] é uma
tautologia, portanto sua negação terá como conseqüência as demais cláusulas do
modelo.
Regras de inferência diversas.
5.4 Discussão
A F-Logic mostra as características desejáveis de uma lógica, com uma sintaxe
poderosa e uma semântica concisa. Em seu trabalho, Kifer, Lausen e Wu (1995) mostram que
60
a F-Logic também permite a construção de programas em lógica, ou seja, Horn programs.
Sua expressão é dada por:
cabeça <- corpo
A cabeça da expressão é uma F-Molécula e o corpo pode ser constituído de uma
conjunção de F-Moléculas, sendo que todas as variáveis são implicitamente universalmente
quantificadas (KIFER, LAUSEN, WU, 1995).
No decorrer da explicação da F-Logic, observa-se que não existe uma ligação que
exija que um objeto tenha uma assinatura. Em seu trabalho, Kifer, Lausen e Wu (1995),
abordam este problema criando novas definições somando a F-Logic, chamando este conjunto
de definições de “programas bem tipado”, a qual ele nomeia de meta-teoria da lógica. Isso
porque a semântica e a teoria da prova da lógica são independentes das definições da ligação
das assinaturas com os objetos (KIFER, LAUSEN, WU, 1995). Serão apresentadas as
definições dadas, pois serão utilizadas nas seções seguintes para apoiar a extração de
conhecimento do Diagrama de Classes da UML.P.
As definições que validam os “programas bem tipados” são baseadas nas definições e
teoria das provas da F-Logic, sendo que foram utilizadas as definições das Estruturas de
Herbrand, chamada de H-Estrutura que é um subconjunto da Base de Herbrand da F-
Linguagem se ela for fechada sob a implicação lógica da definição 5.2.1.1, e o modelo de
Herbrand, chamado de H-Modelo. Não entraremos em detalhe nestas definições, pois está
além do escopo deste trabalho e as definições e provas podem ser obtidas claramente do
trabalho (KIFER, LAUSEN, WU, 1995).
A primeira definição trata das expressões não herdáveis da F-Logic, onde todas as
expressões não herdáveis devem ter uma assinatura.
Definição 5.4.1: (KIFER, LAUSEN, WU, 1995) Seja I uma H-Estrutura. Suponha que é
um átomo de dado não herdável da forma o[m@a
1
,...,a
k
v] I e é um átomo de
assinatura da forma d[m@b
1
,...,b
k
...]. Pode-se dizer que “cobre” se, para
cada i = 1, ..., k, tem-se o:d, a
i
:b
i
I. Os símbolos e denotam, respectivamente, para
-> e => ou para ->> e =>>. Diz-se que I é uma H-Estrutura tipada com respeito às
expressões de dados não herdáveis se as seguintes condições forem verdadeiras:
a) todo átomo de dado não herdável em I é coberto por um átomo de assinatura em I;
b) se um átomo de dado não herdável, o[m@a
1
,...,a
k
v] I, for coberto por
uma assinatura da forma d[m@b
1
,...,b
k
w] I, então v:w I.
61
O tratamento das expressões herdáveis é dada na definição abaixo. Note que a única
diferença entre a definição 5.4.1 e a definição 5.4.2 é o tratamento das expressões “é-um”.
Definição 5.4.2: (KIFER, LAUSEN, WU, 1995) Seja I uma H-Estrutura. Suponha que é
um átomo de dado herdável da forma c[m@a
1
,...,a
k
v] I e é um átomo de
assinatura da forma d[m@b
1
,...,b
k
...]. Pode-se afirmar que “cobre” se
c::d, a
i
:b
i
I. Os símbolos e denotam, respectivamente, para *-> e => ou para
*->> e =>>. Diz-se que I é uma H-Estrutura tipada com respeito as expressões de dados
herdáveis se as seguintes condições forem verdadeiras:
c) Todo átomo de dado herdável em I é coberto por um átomo de assinatura em I;
d) Se um átomo de dado herdável, c[m@a
1
,...,a
k
v] I, for coberto por uma
assinatura da forma d[m@b
1
,...,b
k
w] I, então v:w I.
Definição 5.4.3: (KIFER, LAUSEN, WU, 1995) As condições das definições 5.4.1 e 5.4.2
são chamadas de “condições de boa tipagem”. Uma H-Estrutura, I, é tipada se todas as
condições de boa tipagem forem satisfeitas.
As definições até aqui apenas definiram o que é um programa tipado, a noção de um
programa bem tipado é dada pelas definições 5.4.4 e 5.4.5 abaixo.
Definição 5.4.4: (KIFER, LAUSEN, WU, 1995) Um modelo canônico tipado de P é um
modelo para P que é uma H-Estrutura tipada e também um modelo canônico de P.
Definição 5.4.5: (KIFER, LAUSEN, WU, 1995) Um F-Programa P é bem tipado (ou tipado
corretamente) se todo H-Modelo canônico de P é um H-Modelo canônico tipado. Caso
contrário, P é dito ser tipado deficientemente.
As definições fecham a noção de um programa bem tipado, ou seja, todas as
expressões de dados deverão ter suas assinaturas explicitamente definidas. As definições aqui
mostradas são gerais e garantem que os programas não infiram fatos que sejam inconsistentes
com as assinaturas de um programa, porém não garantem que um programa em F-Logic esteja
sintaticamente correto (KIFER, LAUSEN, WU, 1995).
A sintaxe do programa deverá ser garantida pela ferramenta que interpretará os
diagramas da UML.P para a F-Logic. Conforme a semântica dada para a UML.P, os modelos
62
(Diagrama de Objetos) e assinaturas (Diagrama de Classes) deverão manter a sintaxe durante
toda a modelagem, isso garantirá que a interpretação também mantenha a sintaxe correta.
63
6 F-LOGIC E UML.P
A UML.P e a F-Logic possuem características que permitem o seu correlacionamento
por serem linguagens que permitem a descrição de domínios pelo conceito de orientação a
objetos. Aparte de como será feita a interpretação dos elementos dos diagramas da UML.P
para a F-Logic, os conceitos semânticos são próximos. Porém, novos conceitos são
adicionados aos modelos quando interpretados da UML.P para F-Logic. Essa adição de
conceitos ocorre devido à precisão da F-Logic que possui uma semântica que define
comportamentos que não são claramente definidos na UML.P.
Neste capítulo serão mostrados os principais conceitos que serão adicionados a
UML.P quando interpretada para a F-Logic e alguns conceitos que já são capturados por
ambas as linguagens. Não será discutido sobre o Diagrama de Estados de Máquina, pois a F-
Logic trata apenas dos aspectos estáticos da lógica e este diagrama deverá ser discutido em
um trabalho futuro que aborde os aspectos dinâmicos da interpretação.
6.1 Classes e assinaturas
As classes da UML.P fazem o mesmo papel das assinaturas da F-Logic. Esse papel
fica mais claro na descrição da semântica das instâncias da UML.P que afirma que ele deve
estar de acordo com as definições dos outros diagramas. Portanto, pode-se afirmar que um
objeto, de um Digrama de Objetos, é uma instância de uma classe definida no Diagrama de
Classes e que as características da classe são respeitadas. Na F-Logic este mesmo conceito foi
dado pela definição 5.4.1 e 5.4.2, que afirma que um objeto tem suas características
respeitadas de acordo com uma assinatura.
Assim como as classes definem os atributos e seus respectivos tipos, a F-logic também
os define. Portanto, durante a interpretação que será dada no próximo capítulo, os atributos e
as ações serão entendidos como métodos das assinaturas das classes.
A semântica da F-Logic adiciona os conceitos de upward-closure e anti-
monotonicidade ao Diagrama de Classe. O conceito de upward-closure será capturado pela
definição de Generalização da UML.P, que está descrita adiante, porém o conceito de anti-
monotonicidade não é claramente capturado pela semântica da UML.P. Portanto, o conceito
de anti-monotonicidade será adicionada à semântica da UML.P durante a interpretação,
implicando que todos os atributos e ações definidas nas classes superiores poderão ser
invocados pelos seus membros e os membros de suas subclasses, com os respectivos
64
argumentos sendo elementos da classe ou de suas subclasses. O conceito de anti-
monotonicidade da F-Logic dá a característica de herança simples a UML.P. Mas é
importante ressaltar que um atributo ou ação não poderá ser substituído numa definição,
sendo possível apenas a sua adição, conforme a definição de anti-monotonicidade. Por
exemplo, suponha que uma classe defina um atributo x do tipo k (cl[x=>k]) e que sua
subclasse defina um mesmo atributo x, porém do tipo w (cl’[x=>w]). Como resultado a
subclasse terá a seguinte assinatura cl’[x=>{k, w}], isto é, x deverá ter elementos que
sejam membros da classe k e w ao mesmo tempo.
6.2 Generalização
A generalização é capturada de forma clara no Diagrama de Classes. Através do
mapeamento
U
da F-Logic obtém-se a mesma semântica nas duas linguagens, exceto que na
F-Logic uma classe também é uma subclasse dela mesma e, portanto, esta característica
também deverá ser observada no Diagrama de Classes. Esta propriedade não acarretará em
grandes alterações nas características do Diagrama de Classes, porém permitirá que outras
características das definições de classe da F-Logic sejam pertinentes a UML.P quando da sua
interpretação. Por exemplo, o modelo da figura 15 não expressa um significado certo somente
com a semântica da UML.P, porém utilizando as características da F-Logic este modelo terá
um significado, ou seja, as classes Classe1 e Classe2 são iguais, e como elas são iguais uma
pode ser subclasse da outra e vice-versa. Esta propriedade é dada pela regra de inferência de
aciclicidade da seção 5.3.2.
Figura 15. Exemplo de generalização
Fonte: Autor
O conceito de upward-closure atende a semântica da UML.P que afirma que cada
instância de uma classe específica também é uma instância da classe mais geral da qual ela
deriva, e conseqüentemente um membro de uma classe também será membro das classes que
ele descende. Portanto, características e restrições especificadas para instâncias de classe mais
gerais são implicitamente especificadas para as classes específicas conforme as regras de
inferência de transitividade e inclusão de subclasse dadas na seção 5.3.2.
65
6.3 Instâncias
As instâncias são entidades que respeitam alguma assinatura dada no Diagrama de
Classes, estas instâncias associam os valores para seus atributos de forma gráfica que mantém
a organização dos Diagramas de Objetos. Obtém-se sua semântica em F-Logic pelos
mapeamentos
U
, que informa que um objeto, que é uma instância de uma assinatura, é
membro de uma classe, e pelos mapeamentos I
->, *->
e I
->>, *->>
, que associam os valores aos
seus respectivos objetos.
Os links do Diagrama de Objetos, que são instâncias das associações do Diagrama de
Classes, não são capturados diretamente pela F-Logic. Através da interpretação da UML.P
para a F-Logic, dada no próximo capítulo, este conceito será definido.
66
7 INTERPRETAÇÃO DA UML.P EM F-LOGIC
A estrutura da UML é fortemente baseada em objetos, sendo adequada a utilização de
uma linguagem lógica que seja capaz de capturar as informações disponibilizadas pelos
diagramas de forma simples e que mantenha os mesmos padrões fornecidos pelos diagramas.
Infelizmente não se encontram estas características na PDDL, sendo necessárias diversas
adaptações e até perda de informações para a interpretação dos diagramas nesta linguagem
(TONIDANDEL, VAQUERO, SILVA, 2006). Por este motivo e por ser uma lógica completa
e correta escolheu-se a F-Logic como a linguagem de modelagem mais adequada para a
interpretação dos diagramas.
A interpretação de uma linguagem formal é determinada pela formulação de uma interpretação das
sentenças atômicas da linguagem com respeito ao domínio dos objetos. Isto é, pela estipulação de quais
objetos do domínio são denotados por quais constantes da linguagem e quais relações e funções são
denotadas por quais letras de predicados e símbolos de funções. O valor verdade de todas as sentenças são
assim determinados de acordo com a interpretação padrão dos conectivos lógicos. Portanto, dado
qualquer interpretação de uma linguagem formal, um conceito formal de verdade é obtido.
(BRITANNICA, 2008).
O processo de interpretação tem como intuito principal fornecer um conceito formal
de verdade para as sentenças de uma linguagem. Desde que a UML.P é uma linguagem de
modelagem semi-formal, ou seja, não podemos concluir o conceito de verdade de todos os
modelos definidos pela linguagem, é necessário definir um processo que permita a definição
do conceito exato de verdade de seus modelos. Portanto, pode-se dizer que através da
interpretação da UML.P em F-Logic poder-se-á permitir a determinação do conceito formal
de verdade para todos os modelos que respeitarem as condições de interpretação.
Observando as definições semânticas da F-Logic e as definições da UML.P,
observamos que diversos conceitos e definições são comuns nestas linguagens. Baseado
nestes conceitos e definições em comum foi efetuada a interpretação dos Diagramas de
Classes e de Objetos da UML.P para a F-Logic. Deve ficar claro que diversos tipos de
interpretações poderiam ser feitas neste processo, porém a interpretação aqui apresentada foi a
que se apresentou mais adequada para a finalidade deste trabalho.
Neste capítulo será mostrado como serão interpretados os diagramas utilizados pela
UML.P utilizando a F-Logic como linguagem de suporte. Efetuar-se-á a interpretação dos
67
diagramas estruturais da UML.P e será seguido progressivamente nos itens utilizados nestes
diagramas até que todas as funcionalidades dos diagramas estáticos sejam apresentadas.
7.1 Diagrama de classes
O Diagrama de Classes fornece diversas informações que não são diretamente
codificadas em F-Logic, porém isso não limitará a interpretação, pois se podem ajustar os
termos da F-Logic para que todas as informações sejam capturadas
Abaixo será introduzido o conjunto de assinaturas necessárias para a interpretação,
chamadas de Assinaturas Auxiliares. Estes termos auxiliarão na estruturação das informações
que serão interpretadas em F-Logic mostrando todas as estruturas fundamentais que serão
utilizadas. A tabela abaixo é necessária, pois conforme verificado anteriormente, qualquer
termo P[] é uma tautologia em F-Logic e para que a interpretação mantenha apenas os tipos
definidos pelo Diagrama de Classes, todos os elementos deverão ter o atributo existe na sua
estrutura.
Tabela 11. Assinaturas auxiliares
Assinaturas Auxiliares
Descrição
tipoPrimDado[existe => booleano;
existe *-> verdadeiro]
Determina os tipos de dados primários que serão
utilizados na interpretação da UML.P. Os tipos de
dados serão: Inteiro, booleano, entre outros.
limConjunto [existe => booleano;
existe *-> verdadeiro]
Determina os limites de qualquer conjunto dado na
UML.P.
mutabilidade[existe => booleano;
existe *-> verdadeiro]
Determina a mutabilidade das associações.
assocTipoEx[existe => booleano;
existe *-> verdadeiro]
Determina o tipo da associação.
tipoEstereotipo[existe =>
booleano; existe *-> verdadeiro]
Determina o tipo do estereótipo das classes.
caracteristica[existe => booleano;
existe *-> verdadeiro]
Determina as características das associações.
classeFund[existe => booleano ;
estereotipo => tipoEstereotipo;
existe *-> verdadeiro]
Determina a classe fundamental que estruturará
todas as classes dos domínios.
Assinatura que auxiliarão na interpretação do Diagrama de Classes.
A definição 7.1 abaixo permitirá que nas próximas modelagens não seja necessária a
definição dos tipos primitivos, tais como nulos, inteiros, booleano e outros. Assumindo então
que todos os modelos tenham como informação prévia estas assinaturas.
68
Definição 7.1: Todo e qualquer tipo de dado primitivo, ou seja, nulo, inteiro, real, string,
booleano e outros, terá sua assinatura dada por tipo primitivo :: tipoPrimDado.
Exceto pelas assinaturas classeFund, as assinaturas serão utilizadas para definir
objetos fixos da interpretação. Da mesma maneira que foi definida as Assinaturas Auxiliares
para ajudar na estruturação da interpretação, será necessária a definição de expressões de
dados que terão a mesma funcionalidade, chamadas de Objetos Auxiliares.
Tabela 12. Objetos auxiliares
Objetos Auxiliares
Descrição
ester_nulo :
tipoEstereotipo
Determina um estereótipo vazio.
lim_Superior :
limConjunto
Determina um objeto de limite superior de um conjunto.
lim_Inferior :
limConjunto
Determina um objeto de limite inferior de um conjunto.
mut_Adiciona :
mutabilidade
Determina um objeto de mutabilidade que informa que as instâncias
de uma associação só podem ser adicionadas, ou seja, qualquer
instância definida ou criada não pode será excluída no decorrer da
dinâmica do domínio.
mut_Alteravel :
mutabilidade
Determina um objeto de mutabilidade que informa que as instâncias
de associações podem ser alteradas no decorrer da dinâmica do
domínio.
mut_Estatico :
mutabilidade
Determina um objeto de mutabilidade que informa que as instâncias
de associações são estáticas, ou seja, não podem ser adicionadas ou
excluídas no domínio no decorrer de sua dinâmica.
assoc_Simples :
assocTipoEx
Determina um objeto de tipo de associação que informa que as
instâncias de associações são simples.
assoc_Agregacao :
assocTipoEx
Determina um objeto de tipo de associação que informa que as
instâncias de associações são agregações compartilhadas.
assoc_Composicao :
assocTipoEx
Determina um objeto de tipo de associação que informa que as
instâncias de associações são composições.
assoc_TipoEx :
caracteristica
Determina um objeto de característica que definirá o tipo da
extremidade de uma associação.
69
atrib_carac :
característica
Determina um objeto que auxiliará a definição de característica de
restrição dos atributos de uma classe.
Os objetos auxiliares permitirão que algumas características do Diagrama de Classes sejam modeladas
facilmente. Porém seu papel principal será junto ao Diagrama de Objetos para a formação dos objetos de um
domínio.
As Assinaturas Auxiliares e Objetos Auxiliares serão utilizados adiante como suporte
a interpretação.
7.1.1 Classes
Conforme explicado no capítulo 4 as classes possuem diversas características que são
utilizadas na modelagem em UML.P. Nesta seção será mostrado como serão interpretadas as
classes e suas características em F-Logic.
Assim como foram definidas diversas assinaturas para capturar as características da
UML.P, as classes serão interpretadas como assinaturas dos elementos modelados. Estas
assinaturas serão descendentes da classe ClasseFund definida previamente na tabela 12, que
fornecerá a estrutura básica para a interpretação.
Definição 7.2: Toda classe não generalizada modelada no Diagrama de Classes da UML.P
será descendente da classe classeFund que tem como assinatura classeFund[existe =>
booleano ; estereotipo => tipoEstereotipo; existe *-> verdadeiro] em F-Logic.
A assinatura da definição 7.2 já tem embutida em sua estrutura a informação de
estereótipo da classe. Esta informação poderá identificar o estereótipo da classe como vazio,
agente, utilitário ou qualquer outro definido pelo modelado. Atualmente são utilizados apenas
os estereótipos agente e utilitário na modelagem de domínios de planejamento em UML.P,
porém nenhuma regra ou restrição é aplicada a estes estereótipos. A tabela 13 exemplifica
como os estereótipos serão capturados em F-Logic.
A assinatura mostra que o estereótipo é uma característica que será herdada por
qualquer objeto descendente da classe.
Adotou-se o padrão de manter o primeiro caractere em minúsculo para caracterizar um
termo em F-Logic e será utilizado o primeiro caractere em maiúsculo quando houver a
necessidade de caracterizar uma variável.
70
Tabela 13. Interpretação de classes
Simbologia UML.P
Estereótipo
Interpretação F-Logic
< >
classe::classeFund
classe[ estereotipo *-> ester_nulo]
<Agente>
classe::classeFund
ester_Agente : tipoEstereotipo
classe[ estereotipo *-> ester_Agente]
<Utilitário>
clClasse::classeFund
ester_Utilitario : tipoEstereotipo
classe[ estereotipo *-> ester_Utilitario]
Modelo de Interpretação da Classe.
A inclusão dos atributos das classes na assinatura interpretada é feita de forma
simples. A interpretação contempla desde atributos simples, ou seja, atributos que armazenam
apenas uma informação, até atributos parametrizáveis de múltiplos valores, ou seja, atributos
que agem como funções e armazenam múltiplos valores. A tabela abaixo mostra a
interpretação dos tipos de atributos.
Tabela 14. Interpretação de atributos
Simbologia UML.P
Interpretação F-Logic
clClasse[attr => A; attr@limConjunto => inteiro;
attr@lim_Inferior *-> 1; attr@lim_Superior *-> 1;
attr@caracteristica => mutabilidade; attr@atrib_carac *->
mut_Alteravel]
clClasse[attr@A
0
, …, A
n
=> B; attr@limConjunto => inteiro;
attr@lim_Inferior *-> 1; attr@lim_Superior *-> 1;
attr@caracteristica => mutabilidade; attr@atrib_carac *->
mut_Alteravel]
clClasse[attr =>> A; attr@limConjunto => inteiro;
attr@lim_Inferior *-> V
i
; attr@lim_Superior *-> V
s
;
attr@caracteristica => mutabilidade; attr@atrib_carac *->
mut_Alteravel]
(0 ≤ V
i
≤ V
s
e 1 ≤ V
s
)
clClasse[attr@A
0
, …, A
n
=>> B; attr@limConjunto => inteiro;
attr@lim_Inferior *-> V
i
; attr@lim_Superior *-> V
s
;
attr@caracteristica => mutabilidade; attr@atrib_carac *->
mut_Alteravel]
(0 ≤ V
i
≤ V
s
e 1 ≤ V
s
)
Modelo da interpretação dos atributos de uma classe.
A tabela também mostra que os atributos modelados em UML.P fornecem
informações de limitações que não são capturados pela simples interpretação para F-Logic.
Perceba que a modelagem em UML.P permite que seja definida a restrição de mutabilidade
do atributo e do limite superior e inferior do número de informações que podem ser
armazenadas, portanto teve-se a necessidade de adicionar a característica de mutabilidade e de
limite do atributo. Para manter a flexibilidade fornecida pela UML.P, quanto aos valores dos
limites, será assumido que o símbolo „*‟ é um valor válido para V
s
, que informará que não
71
existe um limite máximo de quantidade de informações que podem ser armazenadas no
atributo.
Os operadores, que serão utilizados principalmente como ações nos domínios de
planejamento automático, terão sua assinatura interpretada de acordo com a tabela 15.
Tabela 15. Interpretação de operadores
Simbologia UML.P
Interpretação F-Logic
clClasse[operador@A
0
, …, A
n
=> null]
Modelo da interpretação de operadores da classe.
Em sua maioria os operadores não retornam um valor após sua execução, porém esta
limitação na interpretação poderá ser facilmente superada através da adição de novas formas
de interpretação destes operadores ou funções.
7.1.2 Associação
Apesar das associações proverem informações de uma forma clara e simples em sua
modelagem em UML.P, sua interpretação em F-Logic exige atenção devido ao número de
informações que um modelo traz.
Figura 16. Exemplo UML.P de domínio de logística
Fonte: Autor
Uma solução de interpretação de associação foi sugerida em Ramalho, Robin (2004),
porém sua interpretação implicaria na criação de um objeto para cada associação utilizada no
modelo. A interpretação sugerida não foca a interpretação da UML para IA, portanto será
criada uma forma mais adequada de interpretação que atenda as necessidades da aplicação
deste trabalho.
72
Cada extremidade da associação será vinculada a classe que a contém, ou seja, a classe
da extremidade oposta da associação. Por exemplo, na figura 16 que é o Diagrama de Classes
de um modelo de logística, a associação PkgAt possui as extremidades isAt e has, sendo que a
extremidade isAt fará parte da classe Package enquanto que has fará parte de Place. De uma
maneira simplificada a interpretação desta associação ficaria com a seguinte estrutura
package[pkgAt@isAt=>place]. Porém, suponha que neste mesmo exemplo existisse a
possibilidade de um pacote estar em outro pacote, ou seja, poderia ser adicionada uma
associação com o mesmo nome PkgAt partindo e retornando para Package, para criar esta
condição. Porém isso causaria uma duplicidade na interpretação, ou seja,
package[pkgAt@isAt=>place; pkgAt@isAt=>package]. Essa interpretação
poderia ser automaticamente entendida como
package[pkgAt@isAt=>{place,package}] com a aplicação da propriedade de
merging da F-Logic. O significado deste resultado não condiz com a realidade desejada e,
portanto, não pode ser utilizado para esta interpretação.
Para efetuar a interpretação de uma associação será utilizado o formato nome da
Associação_nome da Classe da Extremidade Oposta_nome da Extremidade Oposta da
Associação que será abreviada por nA_nCEO_nEOA como referência. Esse formato permitirá
a superação do problema descrito anteriormente, mantendo a simplicidade da interpretação.
Portanto, a interpretação será estruturada da seguinte maneira:
nomeClasse[nA_nCEO => mutabilidade;
nA_nCEO_nEOA nomeClasseOposta;
nA_nCEO_nEOA@limConjunto => inteiro;
nA_nCEO_nEOA@caracteristica => assocTipoEx]
onde o símbolo denota o símbolo => ou =>>.
Por exemplo, da figura 16, pode-se obter a seguinte estrutura da associação isIn vista
pela classe package:
Package[isIn_Vehicle=>mutabilidade;
isIn_Vehicle_isIn=>vehicle;
isIn_Vehicle_isIn@limConjunto=>inteiro;
isIn_Vehicle_isIn@ caracteristica=>assocTipoEx]
Portanto, observe que no exemplo nA é o nome da associação isIn, nCEO é o nome da classe
oposta da classe pela qual a associação está sendo modelada Vehicle e nEOA é o nome da
extremidade oposta da associação isIn, formando o nome isIn_Vehicle_isIn.
A informação de mutabilidade de uma associação será obtida diretamente pelo método
nA_nCEO sem a utilização de parâmetros, neste caso não foi utilizado o nome da extremidade
73
da associação por se tratar de um atributo que caracteriza uma propriedade da associação em
geral. Por exemplo, a associação inCity da figura 16 interpretada para a classe place resultará
no termo place[inCity_City => mutabilidade; inCity_City *->
mut_Estatico], capturando a propriedade da mutabilidade estática do modelo.
As extremidades de uma associação possuem a propriedade de navegabilidade, esta
propriedade será expressa na F-Logic de maneira indireta, pois havendo a possibilidade de
navegação o método nA_nCEO_nEOA sem parâmetros será definido, caso contrário não. Por
exemplo, da figura 16 a associação isAt será interpretada da seguinte maneira:
truck[isAt_Place=>mutabilidade;
isAt_Place_at=>Place;
isAt_Place_at@limConjunto=>inteiro;
isAt_Place_at@caracteristica=>assocTipoEx]
place[isAt_Truck=>mutabilidade;
isAt_Truck_has@limConjunto=>inteiro;
isAt_Truck_has@caracteristica=>assocTipoEx]
Observe que a associação foi interpretada para truck, porém não foi interpretada para place.
Isso se pode verificar pela ausência do método isAt_Truck_has na classe package.
O símbolo “” representa os símbolos => e =>>, que será definido pelo limite
superior da multiplicidade da extremidade, ou seja, se o limite superior for igual a 1 o símbolo
será => caso contrário será =>>, sendo interpretado pelo método
nA_nCEO_nEOA@limConjunto. O tipo da extremidade da associação será capturado pelo
método nA_nCEO_nEOA@característica. Observe que esta estrutura permite obter todas as
características de uma associação, agregando à classe as informações necessárias. A tabela
abaixo exemplifica como será feita a interpretação das associações.
Tabela 16. Interpretação de associações
Simbologia UML.P
Interpretação F-Logic
P/ V
j,t
= 1
classeA[associação_classeB => mutabilidade;
associação_classeB *-> <mutabilidade>;
associação_classeB_fimB => classeB;
74
associação_classeB_fimB@limConjunto => inteiro;
associação_classeB_fimB@lim_Inferior *-> <V
s
>;
associação_classeB_fimB@lim_Superior *-> <V
t
>;
associação_classeB_fimB@caracteristica => assocTipoEx;
associação_classeB_fimB@assoc_TipoEx *-> < AssociaçãoTipo>]
classeB[associação_classeA => mutabilidade;
associação_classeA *-> <mutabilidade>;
associação_classeA_fimA => classeA;
associação_classeA_fimA@limConjunto => inteiro;
associação_classeA_fimA@lim_Inferior *-> <V
s
>;
associação_classeA_fimA@lim_Superior *-> <V
t
>;
associação_classeA_fimA@caracteristica => assocTipoEx;
associação_classeA_fimA@assoc_TipoEx *-> < AssociaçãoTipo>]
P/ V
j,t
> 1
As assinaturas serão idênticas as mostradas acima, porém o método
associação_classeX_fimX=>classeX terá o símbolo => substituído por =>>.
P/ V
t
= 1 e V
t
> 1
As assinaturas serão idênticas as mostradas anteriormente para a ClasseA, porém a assinatura
para a ClasseB deverá ser formada da seguinte maneira:
classeB[associação_classeA => mutabilidade;
associação_classeA *-> <mutabilidade>;
associação_classeA_fimA@limConjunto => inteiro;
associação_classeA_fimA@lim_Inferior *-> <V
s
>;
associação_classeA_fimA@lim_Superior *-> <V
t
>;
associação_classeA_fimA@caracteristica => assocTipoEx;
associação_classeA_fimA@assoc_TipoEx *-> < AssociaçãoTipo>]
Note que devido a ausência da navegabilidade, o método
associação_classeA@extAssoc=>classeB não foi inserido.
A multiplicidade de uma composição é limitada, conforme verificado nas definições da
UML.P. Portanto sua interpretação levará em conta esta limitação. A interpretação para a
ClasseA será idêntica ao primeiro e segundo exemplo desta tabela, observando a
navegabilidade da associação, e a ClasseB terá sua interpretação da seguinte maneira:
classeB[associação_classeA => mutabilidade;
associação_classeA *-> <mutabilidade>;
associação_classeA_fimA => classeA;
associação_classeA_fimA@limConjunto => inteiro;
75
associação_classeA_fimA@lim_Inferior *-> 1;
associação_classeA_fimA@lim_Superior *-> 1;
associação_classeA_fimA@caracteristica => assocTipoEx;
associação_classeA_fimA@assoc_TipoEx *-> assoc_Composicao]
As associações possuem diversos adornos que são modelados utilizando os parâmetros dos atributos.
Na interpretação da tabela 16, os métodos que mantém as propriedades de
mutabilidade, limite inferior e superior da multiplicidade e o tipo da associação obtêm os
dados diretamente do Diagrama de Classes. Porém, deve-se observar que o atributo
mutabilidade quando modelado em UML.P é dado por Alterável, Adiciona e Estático e estes
valores não são válidos para o atributo mutabilidade em F-Logic. Estes valores serão
respectivamente convertidos para mut_Alteravel, mut_Adiciona e mut_Estático validando os
valores conforme a tabela de Objetos Auxiliares. O mesmo ocorre com o atributo do tipo de
associação, que serão convertidos em assoc_Simples, assoc_Agregação e assoc_Composição
sendo que estes atributos serão obtidos conforme a indicação gráfica dadas pelas definições da
associação da seção 4.1.
As associações são interpretadas como métodos da F-Logic, porém estes métodos
estão relacionados entre as classes e conseqüentemente entre os objetos. Na tabela 16, isto
fica claro se observada a assinatura da classeA e a da classeB. O método
associacao_classeB_fimB da classeA e o método associacao_classeA_fimA da classeB estão
intimamente ligados, pois são derivados de uma mesma associação. Portanto qualquer
alteração que um dos métodos sofra, terá resultado direto ou indireto no outro método. Estes
métodos serão chamados de Atributos Complementares de Associação, portanto para
referenciar um método complementar será utilizada a função atrComplementar. Por exemplo,
o resultado da função atrComplementar(associação_classeB_fimB) resultará em
associacao_classeA_fimA.
7.1.3 Generalização
Tabela 17. Interpretação de generalização
Simbologia UML.P
Interpretação F-Logic
clClasseB :: clClasseA
A interpretação da generalização da UML.P tem representação direta na UML.P.
As generalizações são facilmente interpretadas em F-Logic, não apresentando
qualquer dificuldade na sua interpretação, conforme pode ser observado na tabela 17. Observe
que as classes generalizadas também herdarão as características da ClassFund após a
interpretação para F-Logic devido à propriedade de herança do operador “::”.
76
7.1.4 Exemplo
O modelo da figura 16 interpretado para a F-Logic, seguindo a interpretação, fornecerá
o modelo abaixo em F-Logic. Note que será utilizada a seqüência “//” como comentário e,
portanto as linhas precedidas por estes caracteres não farão parte do modelo.
//ASSINATURAS AUXILIARES (FIXO)
tipoPrimDado[existe => booleano; existe *-> verdadeiro]
limConjunto[existe => booleano; existe *-> verdadeiro]
mutabilidade[existe => booleano; existe *-> verdadeiro]
assocTipoEx[existe => booleano; existe *-> verdadeiro]
tipoEstereotipo[existe => booleano; existe *-> verdadeiro]
caracteristica[existe => booleano; existe *-> verdadeiro]
classeFund[existe => booleano ; estereotipo => tipoEstereotipo; existe *->
verdadeiro]
//OBJETOS AUXILIARES (FIXO)
lim_Superior : limConjunto
lim_Inferior : limConjunto
mut_Adiciona : mutabilidade
mut_Alteravel : mutabilidade
mut_Estatico : mutabilidade
assoc_Simples : assocTipo
assoc_Agregacao : assocTipo
assoc_Composicao : assocTipo
assoc_TipoEx : caracteristica
ester_Agente : tipoEstereotipo
ester_Utilitario : tipoEstereotipo
//GENERALIZAÇÕES CLASSES
city::classeFund
place::classeFund
package::classeFund
vehicle::classeFund
location::place
airport::place
truck::vehicle
airplane::vehicle
//ASSINATURA CLASSES
ester_agente : tipoEstereotipo
truck[estereotipo*->ester_Agente;
drive@clPlace,clPlace,clCity => nulo;
loadTruck@clPackage,clPlace => nulo;
unloadTruck@clPackage,clPlace => nulo]
vehicle[capacity => inteiro;
capacity@limConjunto => inteiro;
capacity@lim_Inferior *-> 1;
capacity@lim_Superior *-> 1;
capacity@caracteristica=>mutabilidade;
capacity@atrib_carac*->mut_Estatico;
77
currentLoad => inteiro
currentLoad@limConjunto => inteiro;
currentLoad@lim_Inferior *-> 1;
currentLoad@lim_Superior *-> 1;
currentLoad@caracteristica=>mutabilidade;
currentLoad@atrib_carac*->mut_Alteravel]
airplane[estereotipo*->ester_Agente;
fly@clAirport,clAirport => nulo;
loadAirplane@clPackage,clAirport => nulo;
unloadAirplane@clPackage,clAirport => nulo]
//ASSINATURA DAS ASSOCIAÇÕES
city[ inCity_Place=>mutabilidade;
inCity_Place_has@limConjunto=>inteiro;
inCity_Place_has@caracteristica=>assocTipoEx;
inCity_Place*->mut_Estatico;
inCity_Place_has@lim_Inferior*->1;
inCity_Place_has@lim_Superior*->*;
inCity_Place_has@assoc_TipoEx*->assoc_Simples]
place[inCity_City=>mutabilidade;
inCity_City_in=>city;
inCity_City_in@limConjunto=>interiro;
inCity_City_in@caracteristica=>assocTipoEx;
inCity_City*->mut_Estatico;
inCity_City_in@lim_Inferior*->1;
inCity_City_in@lim_Superior*->1;
inCity_City_in@assoc_TipoEx*->assoc_Composição;
pkgAt_Package=>mutabilidade;
pkgAt_Package_has@limConjunto=>inteiro;
pkgAt_Package_has@caracteristica=>assocTipoEx;
pkgAt_Package*->mut_Alteravel;
pkgAt_Package_has@lim_Inferior*->0;
pkgAt_Package_has@lim_Superior*->*;
pkgAt_Package_has@assoc_TipoEx*->assoc_Simples;
isAt_Truck=>mutabilidade;
isAt_Truck_has@limConjunto=>inteiro;
isAt_Truck_has@caracteristica=>assocTipoEx;
isAt_Truck*->mut_Alteravel;
isAt_Truck_has@lim_Inferior*->0;
isAt_Truck_has@lim_Superior*->*;
isAt_Truck_has@assoc_TipoEx*->assoc_Simples]
package[pkgAt_Place=>mutabilidade;
pkgAt_Place_isAt=>place;
pkgAt_Place_isAt@limConjunto=>inteiro;
pkgAt_Place_isAt@caracteristica=>assocTipoEx;
pkgAt_Place*->mut_Alteravel;
pkgAt_Place_isAt@lim_Inferior*->0;
pkgAt_Place_isAt@lim_Superior*->1;
pkgAt_Place_isAt@assoc_TipoEx*->assoc_Simples;
isIn_Vehicle=>mutabilidade;
isIn_Vehicle_isIn=>vehicle;
isIn_Vehicle_isIn@limConjunto=>inteiro;
isIn_Vehicle_isIn@ caracteristica=>assocTipoEx;
78
isIn_Vehicle*-> mut_Alteravel;
isIn_Vehicle_isIn@ lim_Inferior*->0;
isIn_Vehicle_isIn@ lim_Superior*->1;
isIn_Vehicle_isIn@ caracteristica*->assoc_Simples]
truck[isAt_Place=>mutabilidade;
isAt_Place_at=>Place;
isAt_Place_at@limConjunto=>inteiro;
isAt_Place_at@caracteristica=>assocTipoEx;
isAt_Place*->mut_Alteravel;
isAt_Place_at@lim_Inferior*->1;
isAt_Place_at@lim_Superior*->1;
isAt_Place_at@assoc_TipoEx*->assoc_Simples]
airport[parkedAt_Airplane=>mutabilidade;
parkedAt_Airplane_has@limConjunto=>inteiro;
parkedAt_Airplane_has@caracteristica=>assocTipoEx;
parkedAt_Airplane*->mut_Alteravel;
parkedAt_Airplane_has@lim_Inferior*->0;
parkedAt_Airplane_has@lim_Superior*->*;
parkedAt_Airplane_has@assoc_TipoEx*->assoc_Simples]
vehicle[isIn_Package=>mutabilidade;
isIn_Package_has@limConjunto=>inteiro;
isIn_Package_has@ caracteristica=>assocTipoEx;
isIn_Package*-> mut_Alteravel;
isIn_Package_has@ lim_Inferior*->0;
isIn_Package_has@ lim_Superior*->*;
isIn_Package_has@ caracteristica*->assoc_Simples]
airplane[parkedAt_Airport=>mutabilidade;
parkedAt_Airport_parkedAt=>airport;
parkedAt_Airport_parkedAt@limConjunto=>inteiro;
parkedAt_Airport_parkedAt@caracteristica=>assocTipoEx;
parkedAt_Airport*->mut_Alteravel;
parkedAt_Airport_parkedAt@lim_Inferior*->1;
parkedAt_Airport_parkedAt@lim_Superior*->1;
parkedAt_Airport_parkedAt@assoc_TipoEx*->assoc_Simples]
7.2 Diagrama de objetos
O diagrama de objetos permite a modelagem de um estado do domínio, sendo que
todos os objetos e links têm suas classes e associações definidas no Diagrama de Classes.
Conforme verificado, as classes definem as características dos objetos do domínio, portanto
no Diagrama de Objetos todas as instâncias terão apenas as características definidas no
Diagrama de Classes.
7.2.1 Objetos
Os objetos são dependentes das assinaturas definidas pelo Diagrama de Classes e,
portanto sua interpretação também dependerá das assinaturas em F-Logic. Os objetos deverão
79
respeitar as assinaturas obtidas do Diagrama de Classes incluindo os limites e atributos de
cada classe.
Os objetos do Diagrama de Objetos não apresentam dificuldades na sua interpretação
para F-Logic, que indicará qual a classe que o objeto pertence e os valores dos atributos que
são característicos do objeto. A tabela 18 exemplifica como será a interpretação de um objeto
para F-Logic. Note que havendo mais de um atributo para uma classe, estes atributos serão
separados por “;”, conforme definido na sintaxe da F-Logic.
Tabela 18. Interpretação de objetos
Simbologia UML.P
Interpretação F-Logic
objeto1 : classeA
objeto1[attr -> V
i
]
A interpretação dos atributos do objeto obtém os valores diretamente do modelo. Os valores devem respeitar a
assinatura definida no Diagrama de Classes.
7.2.2 Links
Assim como os objetos são dependentes de suas assinaturas, os links, que são os
relacionamentos entre os objetos, também respeitarão as assinaturas definidas no Diagrama de
Classes. A tabela abaixo exemplifica como será interpretado um link para F-Logic.
Tabela 19. Interpretação de links
Simbologia UML.P
Interpretação F-Logic
objeto1 : classeA
objeto2 : classeB
objeto1[associação_classeB_fimB -> objeto2]
Os links têm a sua interpretação similar a interpretação dos atributos de um objeto.
Observe que a interpretação será dependente da assinatura obtida do Diagrama de
Classes e terá relação direta com a interpretação obtida das associações.
7.2.3 Exemplo
Como a interpretação do Diagrama de Objetos está diretamente ligada a interpretação
do Diagrama de Classes, o processo ficará mais claro através do exemplo da figura 17 que é
um estado qualquer do modelo de logística utilizado no exemplo da figura 16.
80
Figura 17. Exemplo de estado de um domínio de logística
Fonte: Autor
pkg1:package[pkgAt_Place_isAt->locationSP1]
locationSP1:location[inCity_City_in -> saoPaulo]
truck1:truck[isAt_Place_at -> locationSP1; capacity -> 20; currentLoad -> 0]
saoPaulo:city
airportSP1:airport[inCity_City_in -> saoPaulo]
airplane1:airplane[parkedAt_Airport_parkedAt -> airportSP1; capacity -> 10;
currentLoad -> 0]
pkg2:package[pkgAt_Place_isAt->locationRJ1]
locationRJ1:location[inCity_City_in -> rioDeJaneiro]
truck2:truck[isAt_Place_at -> locationRJ1; capacity -> 20; currentLoad -> 0]
rioDeJaneiro:city
airportRJ1:airport[inCity_City_in -> rioDeJaneiro]
airplane2:airplane[parkedAt_Airport_parkedAt -> airportRJ1; capacity -> 10;
currentLoad -> 0]
Através do exemplo visualizam-se que as interpretações dos objetos se limitam as
características que são apresentadas no Diagrama de Objetos. Os outros atributos são
herdados pelos objetos conforme as propriedades presentes na F-Logic.
81
8 EXTRAÇÃO DE CONHECIMENTO DO DIAGRAMA DE CLASSES DA UML.P
O Diagrama de Classes da UML.P possui características inerentes de um modelo de
planejamento e que podem ser extraídas para fazer o papel de restrição de um domínio.
Dentre estas características podem ser citadas a multiplicidade, generalização, tipos entre
outras. A extração destes conhecimentos deve ser realizada após o completo processo de
modelagem do domínio, quando as informações deverão estar completas para análise.
Para que o conhecimento inserido no Diagrama de Classes seja útil é necessário que
ele seja o espelho de todas as características estáticas do modelo do domínio. Sendo que o
Diagrama de Objetos e os operadores não poderão possuir qualquer característica que não
tenha reflexo no Diagrama de Classes. Esta necessidade fica clara na semântica do Diagrama
de Classes definida para a UML.P.
Nas próximas seções será utilizada a nomenclatura utilizada na UML.P, ou seja,
classes, associações, atributos e outros, indistintamente. Porém deverá ficar claro que quando
for referida a linguagem F-Logic o termo classe deverá ser entendido como assinatura, assim
como o atributo e associações deverão ser entendidos como métodos. Os contextos dos termos
são similares, observando as interpretações definidas no capítulo 7.
8.1 Conceitos fundamentais
Figura 18. Exemplo de tipos e hierarquias
Fonte: Autor
Para demonstrar a obtenção das restrições da interpretação em F-Logic de um modelo
de domínio será necessária a definição de alguns conceitos que auxiliarão os processos.
Através das definições que seguem será possível a demonstração das extrações de forma
simplificada.
82
Definição 8.1.1: O conjunto de todas as superclasses de uma classe será obtido pela função
(), ou seja, essa função retornará o conjunto de todas as superclasses de que uma
classe descende.
Definição 8.1.2: O conjunto de todas as subclasses de uma classe será obtido pela função
(), ou seja, essa função retornará o conjunto de todas as subclasses que uma classe
define.
As definições 8.1.1 e 8.1.2 auxiliarão a obtenção das classes que uma classe descende
ou define, por exemplo, aplicando a função na classe ClasseH do exemplo da figura 18,
, resultará em { }, e
aplicando a função na classe ClasseA, do mesmo exemplo, resultará {
}.
Definição 8.1.3: O conjunto de todas as classes existente num diagrama de classes não
pertencente a uma estrutura hierárquica de uma determinada classe será obtido pela função
().
A definição 8.1.3 permitirá que sejam obtidas as classes que não pertencem a uma
hierarquia. Do exemplo da figura 18, () resultará nas classes {
}.
Definição 8.1.4: Um modelo de domínio em UML.P passível de interpretação em F-Logic,
será composto por um Diagrama de Classes C e um ou mais Diagramas de Objetos
, sendo
que todos os recursos utilizados em
deverão ter suas definições dadas em C, ou seja,
c
C. Todo modelo de domínio que respeite estas condições será denotado por
.
A definição 8.1.4 deixa claro que não será qualquer modelo de domínio em UML.P
que será passível de interpretação para F-Logic. O requerimento mínimo para sua
interpretação será a existência do Diagrama de Classes e de pelo menos um Diagrama de
Objetos.
83
Definição 8.1.5: Um modelo de domínio
pertencerá ao conjunto de modelos interpretáveis
em F-Logic,
, se e somente se sua interpretação resulte em um F-Programa bem tipado
nos moldes da definição 5.4.5.
Para garantir a validade das interpretações dos modelos UML.P para a extração de
conhecimento, o F-Programa resultante deverá respeitar a definição 5.4.5. Isso garantirá que
todos os objetos do Diagrama de Objetos tenham suas classes definidas no Diagrama de
Classes.
8.2 Restrição por tipos
Na UML.P os tipos dos objetos são obtidos diretamente das classes definidas no
Diagrama de Classes, bem como pelos tipos primários existentes, tais como inteiro, real,
booleano entre outros. A UML é uma linguagem tipada, ou seja, exige que um programa
tenha todos os tipos definidos para cada elemento utilizado no modelo. Esta característica é
derivada de sua forte ligação com o desenvolvimento de software e sistemas, que utilizam esta
característica em sua estrutura. Contudo, a completa especificação de tipo na programação
lógica é considerada uma tarefa dispendiosa. (KIFER, LAUSEN, WU, 1995). Porém, a
inferência total dos tipos de um modelo pode não ser adequada quando sua verificação fica a
cargo de um especialista que poderá cometer erros durante este processo. Com a definição dos
tipos no Diagrama de Classes, pode-se tirar vantagem desta informação para a obtenção da
estrutura hierárquica e de tipos de cada objeto que poderão ser utilizadas por um planejador
automático.
8.2.1 Restrições pelas classes e hierarquias
As classes, que determinam os tipos dos objetos, e suas hierarquias são descritas
explicitamente no Diagrama de Classes. Do Exemplo da figura 18, conclui-se que
, sendo que o
símbolo “” denota a hierarquia das classes, sendo “é super classe de”. Portanto, lê-se a
afirmação como “a ClasseA é superclasse das classes ClasseB, ClasseC, ClasseD, ClasseE,
ClasseF, ClasseG e ClasseH”. Essa conclusão é pertinente para as demais classes, ou seja,
, e sucessivamente de acordo com a
figura 18.
84
O teorema a seguir deixa claro que a estrutura de hierarquia da UML.P é valida
também na interpretação para F-Logic.
Teorema 8.2.1.1: Para um modelo
, sendo C o conjunto de classes definidas no
Diagrama de Classes, pode-se afirmar que , ().
Prova: Dado um modelo de domínio D qualquer, passível de interpretação para F-Logic
e bem tipado,
. Sejam Cl
j
, Cl
k
e Cl
t
classes pertencentes ao Diagrama de Classes
(C) deste domínio. A interpretação das estruturas hierárquicas da UML.P para F-Logic
resultará em termos como
: :
e
: :
, onde
são as superclasses de
e
são superclasses de
. Suponha que a afirmação
(
) seja falsa, ou seja,
a classe
não é superclasse das classes que descendem dela. Conseqüentemente a
afirmação
: :
também deverá ser falsa, pois este termo afirma que
é
superclasse de
. Aplicando a definição semântica 5.2.1.1 e a regra de inferência de
transitividade da seção 5.3.2, teremos
::
,(
::
)
::
, que afirma que
é subclasse de
e portanto
(
), validando o teorema. □
Figura 19. Exemplo de objeto
Fonte: Autor
Observado que a estrutura hierárquica também é valida na interpretação para F-Logic,
será verificado que também é possível determinar os tipos e subtipos a qual um objeto é
membro. Do exemplo do Diagrama de Classes da figura 18, suponha que fosse definido um
Objeto1 qualquer membro da ClasseH, conforme exemplo da figura 19. Pode-se afirmar que
este objeto também é membro das ClasseE, ClasseF, ClasseB, ClasseC e ClasseA de acordo
com as propriedades de herança dada pela semântica da UML.P. Portanto, pode-se escrever a
restrição .
. O símbolo “ ” denota
implicação simples, conforme definido na lógica de primeira ordem, e o símbolo “” denota
que um objeto é membro de uma classe, os outros conectivos e símbolos tem o significado
padrão utilizado na lógica de primeira ordem. Portanto, pode-se ler a afirmação como “para
todo objeto membro de classeH implicará que o objeto também é membro das classes
85
classeE, classeF, classeB, classeC e classeA”. Os símbolos “” e “” serão utilizados nas
definições e teoremas que seguem neste capítulo.
Aplicando este conceito no exemplo da figura 16, do mundo de logística, supondo um
objeto Obj qualquer do tipo Truck pode-se escrever: . ,
ou seja, todo objeto membro da classe truck também será membro da classe vehicle. De uma
forma mais simplificada pode-se reescrever esta restrição em lógica de primeira ordem, onde
é uma variável, como:
.
O mesmo processo pode ser aplicado ao exemplo da figura 18, obtendo:
.
.
.
.
.
Este tipo de restrição se aplica a qualquer estrutura hierárquica definida no Diagrama
de Classes da UML.P devido à propriedade de descendência das classes, portanto um objeto
pertencente a uma classe também pertencerá a todas as super classes da estrutura hierárquica.
Também é possível de obter estas restrições da interpretação da F-Logic, aplicando-se
as regras de inferência da lógica, conforme pode ser visto pelo teorema que segue.
Teorema 8.2.1.2: Para um modelo
, sendo C o conjunto de classes definidas no
Diagrama de Classes e O o conjunto de objetos pertencentes ao Diagramas de Objetos,
pode-se afirmar que , ().
Prova: Dado um modelo de domínio D qualquer, passível de interpretação para F-Logic
e bem tipado,
. Sejam
K
i
os objetos pertencentes ao Diagrama de Objetos (O) e
Cl
j
classes pertencentes ao Diagrama de Classes (C) deste domínio, sabe-se que
,
pela definição 8.1.1.4. A interpretação dos objetos para F-Logic
resultará em termos como
:
, assim como as estruturas hierárquicas resultarão em
termos como
,
: :
, onde
são as superclasses de
. Suponha
que a afirmação
(
) seja falsa, ou seja, o objeto
não é membro
das superclasses de
. Conseqüentemente a afirmação
:
também deverá ser
falsa, pois este termo afirma que
é membro de
. Aplicando a regra de inferência
86
de Inclusão de Subclasse da seção 5.3.2 na interpretação obtida, teremos
:
,(
::
)
:
, que afirma que todo
é membro de
e portanto
(
), validando o teorema. □
O teorema demonstra que se podem obter todas as classes que um objeto é membro através do
Diagrama de Classes e Objetos. Porém, um objeto membro de uma classe não poderá ser
membro de uma subclasse ou de uma classe que não pertença a hierarquia, conforme
verificamos pela semântica da UML.P. Do exemplo da figura 16, dado que
, sendo
X um objeto qualquer, resultará em regras como .
¬
. Pode-se
verificar o mesmo do exemplo das figuras 18 e 19, o 1 não será membro das classes
e ou de qualquer outra classe definida no domínio, resultando na restrição
. ¬
¬( ), ou descrito
em lógica de primeira ordem:
.
¬
.
¬
.
¬
.
¬
.
¬
Este conseqüência em F-Logic é obtida pelo teorema que se segue.
Teorema 8.2.1.3: Para um modelo
, sendo C o conjunto de classes definidas no
Diagrama de Classes e O o conjunto de objetos pertencentes ao Diagramas de Objetos,
pode-se afirmar que , ¬
¬
.
Prova: Dado um modelo de domínio D qualquer, passível de interpretação para F-Logic
e bem tipado,
. Sejam
K
i
os objetos pertencentes ao Diagrama de Objetos (O) e
Cl
j
classes pertencentes ao Diagrama de Classes (C) deste domínio, sabe-se que
,
pela definição 8.1.1.4. A interpretação dos objetos para F-Logic
resultará em termos como
:
, assim como as estruturas hierárquicas resultarão em
termos como
,
: :
, onde
são as superclasses de
. Suponha
que a afirmação
¬
¬
seja falsa, ou seja,
87
o objeto
é membro das subclasses de
e das demais classes do modelo. Seja
o
conjunto das classes que não pertençam à estrutura hierárquica de
e
o conjunto
das subclasses de
(
: :
), conseqüentemente as afirmações
:
e
:
deverão ser verdadeiras, pois estes termos afirmam que
é membro de
e
.
Observando a semântica da F-Logic dada na seção 5.2, a afirmação que um objeto é
membro de qualquer classe que ele não descendente é falsa, assim como não existe
qualquer regra de inferência ou definição que permita a validação da afirmação
:
,(
::
)
:
. Portanto pode-se concluir que o teorema é válido. □
Através dos teoremas 8.2.1.2 e 8.2.1.3 é possível obter estados invariantes de tipos.
Este conjunto de informações também é obtido pela inferência de tipos do TIM e
DISCOPLAN, conforme demonstrado nas seções 3.1 e 3.2. Diferente do método aplicado
pelo TIM e DISCOPLAN, que obtém estas regras das ações e do estado inicial, mostrou-se
que é possível obter estes estados invariantes diretamente do Diagrama de Classes da UML.P.
8.2.2 Restrições pela herança dos tipos
Conforme foi verificado, a hierarquia das classes permite que um membro de uma
classe também seja membro das superclasses que uma classe descende. Isso traz uma
conseqüência direta aos modelos em UML.P que implica na herança de atributos e
associações, conforme visto em sua semântica.
Figura 20. Exemplo de propagação de atributos e associações
Fonte: Autor
O exemplo da figura 20 traz diversos exemplos de herança. Analisando primeiramente
a herança de atributos, verifica-se que o attr1 será propagado para suas subclasses ClasseF e
ClasseC, assim como o atributo attr3 será propagado para suas subclasses ClasseD e ClasseE.
Da mesma maneira as associações podem ser analisadas, observe que os membros da classe
88
ClasseF poderão se relacionar através da associação assoc1 com os membros da classe
ClasseB. Os membros das classes ClasseD e ClasseE também são membros da classe
ClasseB, portanto os membros da classe ClasseF também poderão se relacionar pela
associação assoc1 com estes membros. A propagação do relacionamento já não ocorre das
classes inferiores para as classes superiores, portanto o atributo attr2 da classe ClasseF não
será propagado para qualquer outra classe, assim como a associação assoc2 também não o
será.
Aplicando-se este conceito no exemplo da figura 21 adiante, obtêm se que objetos do
tipo Truck e Airplane herdarão os atributos currentLoad e capacity da classe Vehicle, assim
como a associação isIn. No teorema 8.2.2.1 será utilizado o símbolo “” que denotará
“contém” e a função Atr que determina o conjunto de atributos e ações das classes, portanto
para a afirmação () () , pode-se ler “A classe Truck contém os
atributos e ações da classe Vehicle”.
Teorema 8.2.2.1: Para um modelo
, Sendo C o conjunto de classes definidas no
Diagrama de Classes, pode-se afirmar que , () (
).
Prova: Dado um modelo de domínio D qualquer, passível de interpretação para F-Logic
e bem tipado,
. Sejam Cl
j
as classes pertencentes ao Diagrama de Classes (C)
deste domínio. A interpretação das classes da UML.P para F-Logic resultará em termos
como
[@
0
, ,
0
, ,
], onde
representa o nome da classe,
representa o nome do atributo,
representa o tipo do parâmetro k obtido da
interpretação e
representa o tipo do valor do atributo. O símbolo denota => ou
=>>. Suponha que
,
: :
, ou seja, existe um
que é superclasse de
.
Suponha que a afirmação (
) (
) seja falsa, ou seja, os atributos da
superclasse de
não são herdados por
, portanto esta afirmação também deverá ser
falsa em F-Logic. Aplicando a regra de inferência de herança de tipo dada na seção
5.3.3, tem-se
@
0
,,
0
,,
,
::
@
0
,,
0
,,
, ou seja, os atributos são herdados das
superclasses pelas classes que contradiz a negação do teorema validando-o.□
Assim como o teorema 8.2.2.1 trata da herança dos atributos e ações, pode-se definir
um para tratar da herança das associações, mostrando o mesmo resultado.
89
Teorema 8.2.2.2: Para um modelo
, sendo C o conjunto de classes definidas no
Diagrama de Classes, pode-se afirmar que , () (
). Onde
a função Assoc determina o conjunto de associações das classes.
Prova: A prova é idêntica a prova do teorema 8.2.2.1, pois a interpretação das
associações da UML.P para F-Logic é similar a interpretação do atributo, podendo se
seguir a mesma prova utilizada anteriormente, porém utilizando as associações.□
Figura 21. Exemplo domínio de logística
Fonte: Autor
Os teoremas 8.2.2.1 e 8.2.2.2 mostram que a herança simples dos atributos e
associações são verdadeiras para a UML.P assim como para a F-Logic. As características
construtivas da UML.P e da herança permitem obter regras de restrição de implicação
simples, os termos abaixo exemplificam estas regras obtidas da figura 21 em lógica de
primeira ordem, onde e são variáveis:
, .
,
()
, .
,
()
, .
,
()
, .
,
()
, .
,
()
, .
,
()
, .
,
()
, .
,
()
90
Estas regras são similares aos estados invariantes de implicação simples obtidas pelo
DISCOPLAN, conforme se verificou na seção 3.2.4. Elas são formadas como
)..)((
1 n
, sendo
,
e
termos. De forma simplificada, . (, )
() () ou . (, ) () () , sendo X e Y
variáveis e pred, pred’ e pred’’ os predicados de um modelo. Porém como a abordagem
utilizada na interpretação é orientada ao objeto (F-Logic), pode-se reescrever um modelo
desta restrição em F-Logic da forma .
:
: , que
pode-se ler como “para todo e , dado que possui o atributo com valor igual a e
é membro da classe
implica que é membro da classe ”, e
. :
: , que pode-se ler como “para todo e , dado que
é membro da classe e possui o atributo com valor igual a implica que é
membro da classe
”, sendo que o símbolo “” é uma abreviação para os símbolos ->
e ->>.
Figura 22. Exemplo de atributo com mesmo nome em classes distintas
Fonte:Autor
A primeira afirmação reescrita para F-Logic não pode ser provada pelo simples fato de
que classes distintas podem ter atributos com mesmo nome e tipo de valores em comum. O
exemplo da figura 22 mostra duas classes distintas com atributos iguais que resultará na
interpretação simplificada para a F-Logic como: classe1[attr=>classeA] e
classe2[attr=>classeA], o que torna impraticável a afirmação .
:
: em F-Logic, pois poderá ser de qualquer tipo que tenha o
atributo do tipo definido pela assinatura.
O teorema a seguir permite a extração da regra de restrição de implicação simples,
observando a limitação para os casos onde existem atributos com o mesmo nome em classes
diferentes.
Teorema 8.2.2.3: Dado um modelo
, sendo X, Y e Cl variáveis e, P e V
componentes de atributos de um objeto, C o conjunto de classes definidas no Diagrama
de Classes e O o conjunto de objetos pertencentes ao Diagramas de Objetos (
). Será
chamado de O’ e C’ o conjunto de objetos e classes de um modelo UML.P interpretado
em F-Logic, então pode-se afirmar que:
,
. :
:
@
0
, ,
0
, ,
@
0
, ,
0
, ,
:
0
, ,
para 0 < < e 0 < < . O
91
símbolo “” denota => ou =>> e “” denota -> ou ->>, e atr é um atributo ou
associação interpretado em F-Logic.
Prova: Dado um modelo de domínio D qualquer, passível de interpretação para F-Logic
e bem tipado,
. Sejam Cl
j
as classes pertencentes ao Diagrama de Classes (C) e
K
i
os objetos pertencentes ao Diagrama de Objetos (O) deste domínio. A interpretação das
classes da UML.P para F-Logic resultará em termos como
[@
0
, ,
0
, ,
], onde
representa o nome da classe, representa o nome do método,
representa o tipo do parâmetro k obtido da interpretação e
representa o tipo do
valor do atributo. O símbolo denota => ou =>>. Suponha que a afirmação
:
:
@
0
, ,
0
, ,
: {
0
, ,
} , para 0 < < e
0 < < , seja falsa. Dado que
, sabe-se que todo objeto deste domínio possui
uma assinatura. Aplicando a definição 5.4.1 e 5.4.2 na afirmação
:
:
@
0
, ,
0
, ,
, teremos que
: {
0
, ,
}, o que contradiz a
falsidade e valida o teorema.□
O teorema 8.2.2.3 permite a extração de um estado invariante simples de um modelo
de planejamento em UML.P e interpretado para F-Logic.
8.3 Restrições por multiplicidade
Figura 23. Exemplo de restrição pela multiplicidade
Fonte: Autor
A multiplicidade impõe restrições ao modelo, limitando o número de relacionamentos
entre os objetos e o número de informações que um atributo pode manter. Pode-se visualizar
um exemplo de restrição dada pela multiplicidade de uma associação através da figura 23.
Neste exemplo, verifica-se que um membro da classe ClasseA pode se relacionar com no
máximo um membro da classe ClasseB, porém um membro da classe ClasseB poderá se
relacionar com até 10 membros da classe ClasseA.
Para o exemplo da associação da figura 23 com limite superior igual a 1, pode-se
verificar que dado dois objetos Obj1 e Obj2, membros da classe ClasseB, se relacionando
92
através da associação assoc com um objeto Obj3, membro da ClasseA, conforme figura 24,
pode-se obter a seguinte regra de restrição:
3, 1
3, 2
1 = 2, devido ao limite superior da associação ser igual a 1. Portanto um objeto do
tipo ClasseA apenas poder se relacionar com um único objeto do tipo ClasseB conforme
definido pelo Diagrama de Classes do exemplo da figura 23. Pode-se verificar a mesma
característica do exemplo da Figura 21, ou seja,
, 1
, 2
1 = 2, onde pckg é um objeto da classe Package e trck1 e trck2 são objetos da
classe Truck.
Figura 24. Exemplo de associação entre objetos
Fonte: Autor
Conforme mostrado na seção 7.1.2 a multiplicidade interfere diretamente na maneira
como uma associação ou um atributo é interpretado para F-Logic. Da mesma forma que foi
obtida a restrição em lógica de primeira ordem, também se pode obter da interpretação do
modelo em F-Logic e, portanto se tem: 3
> 1
3
> 2
1 2 do exemplo da figura 23 e
> 1
> 2
1 2 do exemplo da figura 21. Note que essa afirmação só é verdadeira em F-Logic
devido o limite superior de relacionamento ser igual a 1 e, portanto pode-se dizer que o Obj1
representa o mesmo objeto que Obj2, assim como trck1 representa o mesmo objeto que trck2.
Teorema 8.3.1: Dado um modelo
, sendo X, Y e Z variáveis, M e P
k
componentes
de atributos de um objeto, C o conjunto de classes definidas no Diagrama de Classes e
O o conjunto de objetos pertencentes ao Diagramas de Objetos (
). Será chamado de O’
e C’ o conjunto de objetos e classes de um modelo UML.P interpretado em F-Logic,
então pode-se afirmar que
,
. [@
1
, ,
> ] [@
1
, ,
> ] .
Prova: A prova segue diretamente da aplicação da regra de inferência de escalaridade
dada na seção 5.3.4.□
A conclusão obtida pela regra de inferência de escalaridade deve ser analisada com
critério no contexto da interpretação utilizada neste trabalho. Deve-se lembrar que a semântica
da UML.P exige um nome único para cada objeto e classe num modelo de domínio, portanto,
93
poderá ser caracterizado como erro se qualquer par de objetos de um Diagrama de Objetos
forem considerados iguais devido a migração da idéia de nome único para os objetos de um
modelo.
Para as multiplicidades superiores maiores que 1 a UML.P também permite obter
restrições, pois o seu valor é explicito o limite quando diferente de “*”. Por exemplo, da
figura 23 tem-se que o valor do limite superior de relacionamentos dos membros da classe
ClasseB para com os membros da classe ClasseA é de 10. Portanto, pode-se definir de forma
simplificada a restrição de estado invariante do exemplo 23 como , .
|
,
|
= 10 , esta restrição informa que para objetos do tipo
ClasseA e ClasseB pode-se ter no máximo 10 associações no domínio. Da mesma maneira
tem-se: , .
|
,
|
= 0, como restrição de limite
inferior.
Esta restrição não é capturada automaticamente pela semântica da F-Logic quando da
interpretação de um modelo UML.P. Do exemplo da figura 23 tem-se a interpretação
simplificada como classeB[assoc_classeA_ext1 =>> classeA], que não dá
qualquer informação quanto ao limite superior ou inferior do relacionamento, devido as
características da semântica da F-Logic. Para manter a informação de multiplicidade a
interpretação captura a informação pelo atributo nA_nCEO_nEOA@lim_Superior e
nA_nCEO_nEOA@lim_Inferior gerando de maneira simplificada a assinatura:
classeB[assoc_classeA_ext1 =>> classeA;
assoc_classeA_ext1@lim_Superior => integer;
assoc_classeA_ext1@lim_Superior -> 10;
assoc_classeA_ext1@lim_Inferior -> 0]
Apesar de a assinatura conter a informação de multiplicidade, não está claro como podemos
utilizar esta informação. Portanto, faz necessária a definição 8.2.1 que permite capturarmos
esta restrição.
Definição 8.3.1: Para um modelo de domínio
, sendo O o conjunto dos objetos de
interpretados em F-Logic. Para todo objeto Obj O que possuir limite inferior e superior para
um atributo Atr, Obj[Atr@lim_Inferior Val_Inferior] e
Obj[Atr@lim_Superior Val_Superior], será denominado de um modelo bem
delimitado os modelos onde a restrição Val_Inferior ≤
noAssociações(Obj[Atr Obj’]) ≤ Val_Superior e Obj’.
Val_Inferior ≤ SomaAssociações(Obj’[atrComplementar(Atr)
94
Obj]) ≤ Val_Superior, para os casos onde Obj[Atr Obj’] não é definido.
Sendo noAssociações uma função que retorna o número de elementos ativos de um atributo
num objeto, somaAssociações uma função que efetua a somatória do número de atributos que
fazem o papel do Atributo Complementar de Associação, definido na seção 7.1.2, e que
possua o valor Obj no atributo. O símbolo “” representa os símbolos -> e ->>.
A definição 8.3.1 é possível devido à aplicação da limitação da multiplicidade em F-
Logic. Dessa maneira será garantido que as informações de multiplicidade de um domínio
serão obedecidas, caso contrário o modelo será dito mal delimitado.
8.4 Restrição pela mutabilidade do atributo e associação
A modelagem pela UML.P também permite a inserção da mutabilidade dos atributos e
associações. Atualmente a UML.P contempla três tipos de mutabilidade: Alterável, Estática e
Somente Adiciona.
Estas restrições são obtidas diretamente pelo atributo interpretado para F-Logic
Mthd@mutabilidade de um objeto. A mutabilidade alterável, ou mut_Alteravel em F-Logic, é
o valor padrão para os atributos que não impõem qualquer restrição ao domínio. A
mutabilidade estática, ou mut_Estatico em F-Logic, informa que o atributo não pode sofrer
qualquer alteração durante sua vida num modelo e, portanto seu valor deve ser definido
quando da modelagem do estado inicial do problema. Destas restrições pode-se gerar a
seguinte definição:
Definição 8.4.1: Para um modelo de domínio
, sendo O o conjunto dos objetos de
interpretados em F-Logic. Para todo objeto Obj O que possuir restrição de mutabilidade
estática num atributo Atr, ou seja, Obj[Atr@mutabilidade -> mut_Estatico]
implicará que Obj[Atr Val] não poderá ser alterado no ciclo de vida do objeto. Sendo
que o símbolo “” representa os símbolos -> e ->>.
A mutabilidade Somente Adiciona, interpretada como mut_Adiciona em F-Logic,
informa que o atributo apenas pode sofrer inclusão de valores durante sua vida no modelo.
Portanto podemos gerar a seguinte definição:
95
Definição 8.4.2: Para um modelo de domínio
, sendo O o conjunto dos objetos de
interpretados em F-Logic. Para todo objeto Obj O que possuir restrição de mutabilidade
somente adiciona num atributo Atr, ou seja, Obj[Atr@mutabilidade ->
mut_Adiciona] implicará que Obj[Atr Val] não poderá ser decrementado de
valores durante seu ciclo de vida. Sendo que o símbolo “” representa os símbolos -> e
->>.
As definições 8.4.1 e 8.4.2 poderão ser aplicadas diretamente nas verificações das
ações, ou seja, para os atributos que contenham a mutabilidade Estática num domínio não
poderá haver qualquer alteração em seu valor após a aplicação de uma ação no domínio. Para
que ocorra alteração num atributo é necessário que ele participe da pós-condição de uma ação,
portanto para a verificação da mutabilidade estática de um atributo bastará que todas as pós-
condições das ações não acessem o atributo com esta restrição. Quanto aos atributos que
contenham mutabilidade Somente Adiciona, deverá ser verificado o a alteração que é efetuada
nestes atributos nas pós-condições das ações e, conforme definido, as pós-condições apenas
poderão incrementar os valores dos atributos com a restrição de mutabilidade Somente
Adiciona.
8.5 Discussão
Comparando as restrições obtidas do TIM e DISCOPLAN, verifica-se que a UML.P é
capaz de fornecer algumas das restrições de forma imediata, porém outras ainda não são
possíveis devido a limitação dos elementos de descrição do domínio. Nas subseções seguintes
será discutida as restrições obtidas pelas ferramentas em comparação com os recursos obtidos
pela UML.P.
8.5.1 Inferência de tipos (TIM e DISCOPLAN)
Diferente dos métodos utilizados pelo TIM e DISCOPLAN para obter os tipos dos
objetos, o Diagrama de Classes e Objetos permitem obter toda a hierarquia das classes e ainda
determinar todas as classes da qual um objeto descende de uma forma direta, conforme
demonstrado pelos teoremas 8.2.1.2 e 8.2.1.3.
96
8.5.2 Estado invariante de valor único ou identidade (TIM e DISCOPLAN)
As restrições de valor único, obtida pelo DISCOPLAN, e a restrição de identidade,
obtida pelo TIM, tem o mesmo significado, ou seja, eles inferem estados invariantes do tipo
ZYZXPYXPZeYX ),(),(.,
.
O teorema 8.3.1, que é uma conseqüência direta da regra de inferência de escalaridade,
demonstra que se pode obter a mesma regra do Diagrama de Classes e Objetos.
8.5.3 Estado invariante de recurso fixo (TIM)
Pela análise das ações, o TIM obtém os recursos fixos do domínio. A mesma
informação é determinada através da multiplicidade na UML.P e interpretado diretamente em
F-Logic por meio do atributo Mthd@multiplicidade. Por exemplo, do mundo dos
blocos o TIM obteria o estado invariante |x:holding(z, x)|=1 (FOX; LONG, 1998). Do
Diagrama de Classes de um modelo do mundo dos blocos da figura 25, é possível obter a
mesma informação na sua interpretação para F-Logic. A associação holding pode ser
interpretada de maneira simplificada como a listagem abaixo, note que o objeto Block e o
objeto Hand já possuem os limites da associação.
block[holding_hand_ishold@limConjunto => inteiro;
holding_hand_ishold@lim_Inferior *-> 0;
holding_hand_ishold@lim_Superior *-> 1]
hand[holding_block_holding@limConjunto => inteiro;
holding_block_holding@lim_Inferior *-> 0;
holding_block_holding@lim_Superior *-> 1]
Figura 25. Exemplo mundo dos blocos
Fonte Autor
97
Além de ter obtido os limites de um atributo, foi inserida a definição 8.2.1 que auxilia
na definição de um modelo bem delimitado, ou seja, que não tem qualquer limite.
8.5.4 Estado invariante de estado do membro (TIM)
A determinação do estado Invariante do Estado do Membro depende das
características das ações de um domínio. As associações de um Diagrama de Classes apenas
determinam que uma associação deve estar sempre ativa quando a sua multiplicidade inferior
é igual a 1, caso contrário não existem informações suficientes no Diagrama de Classes que
permitam determinar se um objeto deve ter uma ou mais associações sempre ativas. Por
exemplo, da figura 25 que modela um Diagrama de Classes do mundo dos blocos, e conforme
verificado nas explicações do TIM do capítulo 3, ele seria capaz de inferir das ações a
restrição
)),(.),(.),(.)()(( xyonyyxonyxzholdingzxclearxontablex
, porém sem
conhecer o significado semântico das associações em um Diagrama de Classes não é possível
obter a mesma conclusão, pois todas as multiplicidades do domínio têm valor inferior igual a
0 e, portanto, no caso da classe Block, ele poderia não ter nenhuma das associações ativas
após a aplicação de uma ação.
Portanto, conclui-se que o Diagrama de Classes ainda não possui informações
suficientes para que se possa extrair estados invariantes de estado do membro.
8.5.5 Estado invariante de caracterização da unicidade do estado do membro e estado
invariante do tipo XOR (TIM e DISCOPLAN)
Assim como o estado invariante de estado do membro, estas restrições também
dependem da análise das ações do domínio. O TIM e DISCOPLAN inferem os pares de
predicados que são mutuamente exclusivos para a determinação destas regras. Assim como
pode ser observado, as associações também não fornecem este tipo de informação, sendo
necessária a inclusão de novos recursos para possibilitar que essa mesma restrição seja obtida.
Atualmente já existe possibilidade de incluir restrições nos Diagramas de Classes da
UML, porém esse recurso ainda não foi completamente estudado para a sua aplicação na
UML.P. As restrições aceitas pela UML são inseridas de três maneiras: descritivamente, pela
Object Constraint Language (OCL) , que é a linguagem formal da UML para a inclusão de
restrição, e através de símbolos diagramáticos que expressam a restrição. Uma restrição
descritiva não poderia ser utilizada, pois é utilizada a linguagem natural e é necessária uma
linguagem formal para que seja efetuado raciocínio automático. A OCL poderia ser utilizada
98
para a determinação de restrições, isso poderá ser efetuado num trabalho futuro pois será
necessário um estudo sobre a linguagem para sua correta utilização no planejamento
automático. Os elementos diagramáticos poderão ser inseridos de uma forma simplificada se
for restringida a sua forma de expressão, pois este elemento permite a inclusão de texto
expressando a restrição. A figura 23 exemplifica uma restrição de exclusividade entre duas
associações. Para a utilização dos elementos diagramáticos disponíveis na UML, será
necessária sua análise e interpretação num trabalho futuro.
Figura 26. Exemplo de restrição por elemento diagramático
Fonte: OMG, 2007, p. 62.
8.5.6 Estado invariante de estados do domínio (DISCOPLAN)
Através da análise de um grafo simplificado do Graphplan o Discoplan é capaz de
obter restrições de Estados do Domínio, o Diagrama de Classes da UML.P não é capaz de
fornecer este tipo de informação pois sua característica é de obter as informações das
características dos elementos do domínio. Para a construção do grafo é necessária a utilização
das informações das ações o que torna necessária a utilização das análises das ações para sua
obtenção.
8.5.7 Estado invariante de implicação simples (DISCOPLAN)
Os estados invariantes de implicação simples utilizam as informações dos tipos para
sua determinação. Através do teorema 8.2.2.3, obtêm-se estados invariantes de implicação
simples, porém com limitação devido a construção da F-Logic e da UML.P, conforme
discutido na seção 8.2.2.
8.5.8 Estado invariante de implicação de valor único (DISCOPLAN)
Para a determinação dos estados invariantes de implicação de valor único, utilizam-se
as informações de tipo combinado com características das ações. Assim como as invariantes
de Estado do Membro obtido pelo TIM, sua determinação depende das características das
99
ações do domínio e não pode ser determinada com as informações disponíveis no Diagrama
de Classes.
8.5.9 Estado invariante de anti-simetria
Figura 27. Exemplo de associação com uma única classe
Fonte: Autor
A anti-simetria obtida pelo DISCOPLAN não pode ser obtida pela UML.P, pois não
existem informações suficientes no Diagrama de Classes para inferir esta condição. De
maneira geral, a regra obtida pelo DISCOPLAN poderia ser descrita por , . [> ]
¬[> ] em F-Logic. A assinatura de uma classe que poderia resultar neste tipo de
restrição seria derivada de um diagrama como o observado na figura 27. Note que não existe
qualquer elemento que permita a inferência desta restrição pela assinatura da classe, sendo
necessária a análise das ações para obter tal restrição.
100
9 CONCLUSÃO
A UML é uma linguagem de modelagem abrangente que permite a sua utilização em
diversos tipos de domínios e aplicações. Devido a sua característica modular, é possível a sua
aplicação em domínios de planejamento automático em IA utilizando apenas os diagramas e
elementos relevantes para o planejamento automático (VAQUERO, TONIDANDEL;
BARROS; SILVA, 2006). Este subconjunto de diagramas e elementos da UML aplicados ao
planejamento automático é denominado de UML.P (VAQUERO; TONIDANDEL; SILVA,
2006). Neste trabalho, verificaram-se os elementos da linguagem que são utilizados pelos
Diagramas de Classes e de Objetos, definindo as semânticas de maneira descritiva, conforme
as definições da UML, e limitando seus elementos diagramáticos ao escopo da interpretação
aqui desenvolvida. Essa necessidade surgiu devido a riqueza de possibilidades de modelagem
que a UML fornece.
A aplicação de ferramentas de inferência de estados invariantes nos modelos de
planejamento automático descritos em PDDL, tais como TIM, DISCOPLAN e Rintanen, são
bem conhecidas pela comunidade de planejamento automático em IA e seus trabalhos
demonstram diversos resultados que reconhecem o valor destas informações para a aceleração
do processo do planejamento automático. Dos diagramas da UML.P, é notável que também
pode-se obter estados invariantes. Porém, apesar de sua semântica permitir a modelagem de
maneira clara, a UML.P é uma linguagem de modelagem semi-formal, o que impede a
extração de conhecimento automático de seus diagramas por deixar inexata a sua
interpretação semântica, sendo necessária a sua interpretação a uma linguagem formal que
ofereça suporte ao raciocínio automático.
Com a introdução da F-Logic como linguagem formal de interpretação da UML.P
estudada neste trabalho, possibilitou-se a inferência automática de restrições dos modelos de
domínio de planejamento. A F-Logic foi adotada por ser uma linguagem que mantém os
conceitos da orientação a objetos, que são nativas a modelagem em UML.P. O método
desenvolvido foi restrito aos Diagramas de Classes e de Objetos e notou-se que ainda existe a
necessidade da extensão dos elementos de diagramação da UML.P, e conseqüentemente de
sua interpretação para F-Logic, para que possibilitem a inferência automática de um conjunto
maior de restrições, assim como as ferramentas TIM e DISCOPLAN são capazes de inferir.
Além da aceleração do processo de planejamento, os autores das ferramentas TIM e
DISCOPLAN sugerem a utilização dos estados invariantes como um item da verificação
interna do modelo. Este processo é possível, pois caso algum estado invariante inferido não
101
seja pertinente ao domínio descrito será necessário uma completa revisão nas descrições das
ações e no estado inicial do problema devido aos processos de inferência destas ferramentas
serem baseados nestes componentes da descrição. Contudo, poucos esforços têm sido feitos
para a utilização destes conhecimentos para a verificação e validação interna automática dos
modelos de domínios de planejamento devido à falta de redundância em suas descrições.
A extração de conhecimento de domínios de planejamento pode auxiliar, além da
melhora do processo de planejamento, o desenvolvimento de descrições de domínios de alta
qualidade. Para que ocorra o processo de validação interna automática de um modelo de
domínio em planejamento é necessário que sua descrição ofereça redundância de informações
para que, por meio de comparações, se possam verificar a consistência destas informações e
validar internamente o domínio de planejamento. Dos diagramas utilizados pela UML.P nota-
se a existência de informações que se complementam e outras que são redundantes,
potencializando o desenvolvimento de uma ferramenta que efetue o processo de validação
interna de um domínio através da inferência e o cruzamento destas informações na UML.P.
Conforme foi estudado neste trabalho, dos Diagramas de Classes e Objetos pode-se
verificar que é possível inferir estados invariantes. Um processo de inferência de estados
invariantes também poderá ser desenvolvido para ser aplicado nos Diagramas de Máquinas da
UML.P. Estes diagramas são compostos das ações que podem ser executadas em um domínio,
sendo possível verificar a validade de se adaptar os algoritmos do TIM e DISCOPLAN para
inferência de estados invariantes destes diagramas.
Entretanto, ainda é necessária a interpretação dos Diagramas de Estado de Máquinas
para uma lógica que permita a utilização da F-Logic junto com a execução das ações. Para a
formalização das ações, a F-Logic pode ser estendida através da Lógica de Transação
(BONNER, KIFER, 1995). A Lógica de Transações especifica formalmente transações em
base de dados, caminhos de execução e procedimentos de transições seqüenciais
(TONIDANDEL, 2003). Tonidandel (2003) discutiu em seu trabalho a aplicação da Lógica de
Transações em planejamento e foi verificado que é uma lógica que possui as características
necessárias para sua aplicação no planejamento automático. Contudo, após a correta
interpretação dos Diagramas de Estados de Máquinas para uma lógica que permita a
utilização de um mecanismo de inferência, será possível aplicar algoritmos tal como TIM e
DISCOPLAN para efetuar a inferência das restrições implícitas nas ações.
Com a utilização das regras inferidas, poderá se iniciar o processo de validação interna
de um domínio, pois haverá as informações redundantes necessárias para este processo.
Portanto podem-se resumir os próximos passos em:
102
1- extensão da UML.P para obter mais informações nos Diagrama de Classes. Incluindo
restrições inseridas explicitamente por uma linguagem formal, como a OCL;
2- interpretação dos Diagramas de Estados de Máquinas para uma lógica que permita a
inferência das restrições de um domínio;
3- cruzamento das restrições obtidas nos processos anteriores para a validação interna do
modelo. Mesmo neste ponto poderá não haver informações para uma completa validação
interna, porém as informações poderão ser utilizadas pelo modelador para a verificação
do domínio. Note que o trabalho será menor do que se usado apenas as informações
obtidas pelas ações, pois parte da verificação será feita automaticamente.
Portanto verificamos que a UML.P é uma linguagem gráfica que permite uma
modelagem mais intuitiva e que permite a sua expansão para atender as mais diversas
características.
103
REFERÊNCIAS
ANGELE, J.; FENSEL, D.; STUDER, R. Developing Knowledge-Based Systems with
MIKE, Journal of Automated Software Engineering, v. 5, n. 4, p. 389-418, 1998.
BERARDI, D.; CAL A.; CALVANESE D.; GIACOMO G. De. Reasoning with UML
Class Diagrams. Technical Report 11-03, 2003. Disponível em: <
citeseer.ist.psu.edu/article/berardi03reasoning.html >. Acesso em: 22 dez. 2007.
BLUM, A.; FURST, M. L. Fast planning through planning graph analysis, In
Proceedings of the 14th International Joint Conference of the American Association for
Artificial Intelligence (AJCAI - 95), p. 1636 – 1642, 1995.
BODDY, M. Imperfect Match: PDDL 2.1 and Real Applications. Journal of Artificial
Intelligence Research , v. 20, p. 123-137, 2003.
BONNER A.J.; KIFER M. Transaction Logic Programming, Toronto: University of
Toronto, 1995. (Technical Report CSRI-323).
BRITANNICA. Metalogic. Britannica Encyclopaedia. 2008. Disponível em: <
http://www.britannica.com/EBchecked/topic/377696/metalogic >. Acesso em: 13 jul.
2008.
BRUEL, JM.; FRANCE, R. Transforming UML Models to Formal Specifications,
Proceedings of International Conference on the Unified Modelling Language, n. 1618,
1998.
COLES, A.; SMITH, A. MARVIN. A heuristic search planner with online macro-
action learning. Journal of Artificial Intelligence Research. v. 28, p. 119–156. 2007.
COMMONKADS. What is CommonKADS?. Disponível em:
<http://www.commonkads.uva.nl/frameset-commonkads.html>. Acesso em 23 out. 2007.
CRESSWELL, S.; FOX, M.; LONG, D. Extending TIM domain analysis to handle
ADL constructs. AIPS‟02 Workshop, 2002.
EDELKAMP, S.; MEHLER T. MODPLAN – Modern Action Planning. Disponivel em:
<http://ls5-www.cs.uni-dortmund.de/~edelkamp/modplan/>. Acesso em 12 mar. 2007.
ERIKSSON, H.; SHAHAR, Y.; TU, S.W.; PUERTA, A.R.; MUSEN, M.A. Task
Modelling with Reusable Problem-Solving Methods, Artificial Intelligence 79 (1995),
293-326.
EVANS, A.; FRANCE R.; LANO, K.; RUMPE, B. The UML as a Formal Modelling
Notation, Lecture Notes In Computer Science, v. 1618, p. 336-348, 1998.
FIKES, R.; NILSSON, N. STRIPS: A New Approach to the Application of Theorem-
Proving to Problem-Solving, IJCAI, p. 608–620, 1971.
FOX, M.; LONG, D. The automatic inference of state invariants in TIM. Journal of
Artificial Intelligence, r. 9, p.367–421, 1998.
104
GEREVINI, A.; SCHUBERT, L. Discovering state constraints in DISCOPLAN: Some
new results. In Proceedings of the 17th National Conference on Artificial Intelligence
(AAAI–2000), ed. AAAI Press, CA., p. 761–767, 2000.
HOFFMAN, J.; NEBEL, B. The FF planning system: Fast plan generation through
heuristic search. Fast plan generation through heuristic search. JAIR. v 14, p. 253-302.
2001.
KAUTZ, H.; SELMAN, B. BLACKBOX: A new Approach to the application of
theorem proving to problem solving, In Proceedings of the AIPS-98 Workshop on
Planning as Combinatorial Search, p. 58-60, 1998.
KENDAL, S.; CREEN, M. An Introduction to Knowledge Engineering. Springer,
2007.
KIFER, M.; LAUSEN, G.; WU, J. Logical Foundations of Object Oriented and Frame
Based Languages. Journal of the ACM, v. 42, i. 4, p. 741-843, 1995.
KIFER, M. Deductive and Object Data Languages: A quest for Integration. Lecture
Notes in Computer Science, v. 1013, p. 187-212, 1995.
LONG, D.; FOX, M. The efficient implementation of the Graph Plan in STAN,
Journal of Artificial Intelligence Research , v. 10, p. 87-115, 1999.
MCCLUSKEY, T. L. PDDL: A Language with a Purpose? , ICAPS 2003 Workshop,
2003.
MCCLUSKEY, T. L.; BARROJO, D.; HASLUM, P.; JARVIS, P.; SCHOLZ, U.
Knowledge Engineering for Planning ROADMAP, 2003. Disponível em:
<http://scom.hud.ac.uk/planet/>. Acesso em: 10 fev. 2007.
MCCLUSKEY, T. L.; PORTEOUS J. M. Engineering and Compiling Planning
Domain Models to Promote Validity and Efficiency, Journal of Artificial Intelligence,
v. 95, n. 1, p. 1-65, 1997.
MCDERMOTT, D.; GHALLAB, M.; HOWE A.; KNOBLOCK, C.; RAM, A.; VELOSO,
M.; WELD, D.; WILKINS, D. The PDDL Planning Domain Definition Language,
AIPS-98 Planning Competition Committee, 1998.
MINSKY, M. A Framework for Representing Knowledge, MIT-AI Laboratory Memo
306, June, 1974. Disponível em: <
http://web.media.mit.edu/~minsky/papers/Frames/frames.html>. Acesso em: 12 abr. 2007.
OMG - Object Management Group. Unified Modelling Language: Superstructure,
2007. Disponível em: < http://www.omg.org/technology/documents/
modeling_spec_catalog.htm#UML> Acesso em: 01 jun. 2007.
GENNARI, J.; MUSEN, M. A.; FERGERSON, R. W.; GROSSO, W. E.; CRUBEZY, M.;
ERIKSSON, H.; NOY, N. F.; TU, S. W. The Evolution of Protégé: An Environment
for Knowledge-Based Systems Development. 2002. Disponível em:
<http://smi.stanford.edu/smi-web/reports/SMI-2002-0943.pdf>. Acesso em: 11 nov. 2007.
105
RAMALHO, F.; ROBIN, J.; SCHIEL, U. Concurrent Transaction Frame Logic
Formal Semantics for UML Activity and Class Diagrams. In. Electronic Notes in
Theoretical Computer Science, v. 95, p. 83-109, 2004.
RAMALHO, F.; ROBIN, J. Mapping UML Class Diagrams to Object-Oriented Logic
Programs for Formal Model-Driven Development, Proc. 3 rd UML Workshop in
Software Model Engineering, 2004.
RINTANEN, J. An Iterative Algorithm for Synthesizing Invariants, Proceedings of the
Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on
Innovative Applications of Artificial Intelligence table of contents, p. 806 – 811, 2000.
SCHREIBER, T; WIELINGA, B.; HOOG, R.; AKKERMANS, H.; VELDE, W.
CommonKADS: A Comprehensive Methodology for KBS Development, IEEE
Intelligent Systems, v. 9, n. 6, p. 28-37, 1994.
SIMPSON, R. N. GIPO Graphical Interface for Planning with Objects. ICAPS 2005
Competition on Knowledge Engineering for Planning and Scheduling, 2005
STUDER, R.; BENHAMINS, V.; FENSEL, D. Knowledge Engineering: Principles and
Methods. Data & Knowledge Engineering, v. 25, p. 161-197, 1998.
TONIDANDEL, F.; Desenvolvimento e Implementação de um Sistema de
Planejamento Baseado em Casos. 2003. Dissertação (Doutorado em Engenharia) –
Escola Politécnica da Universidade de São Paulo.
TONIDANDEL F.; VAQUERO T.; SILVA J. Reading PDDL, Writing an Object-
Oriented Model. In Lecture Notes in Computer Science. International Joint Conference
on AI IBERAMIA/SBIA. Springer-Verlag. 2006.
VAQUERO, T.; TONIDANDEL, F.; SILVA, J. The itSIMPLE tool for Modelling
Planning Domains, Technical Report, Brazil, 2006. Disponível em:
<http://www.pmr.poli.usp.br/d-lab/site>.
VAQUERO, T.; TONIDANDEL, F.; BARROS, L.; SILVA, J.; On the Use of UML.P
for Modelling a Real Application as a Planning Problem, In Proceedings or the 16th
International Conference on Automated planning and Scheduling (ICAPS), Cumbria, UK,
2006.
VAQUERO, T. S.; ROMERO, V. M. C.; SETTE, F.; TONIDANDEL, F.; SILVA, J. R.
itSIMPLE2.0 : An Integrated Tool for Designing Planning Domains. In: ICAPS 2007
- International Conference on Automated Planning and Scheduling, 2007, Providence,
Rhode Island. ICKEPS 2005 Competition on Knowledge Engineering for Planning and
Scheduling. Menlo Park, California, USA, 2007.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
