Reasoning
Fuzzy Logic and
The Rule Application
Andrew Diniz da Costa
Fábio de Azevedo
Sérgio Ciglione
[email protected]
[email protected]
[email protected]
Roadmap
• Introduction
• Fuzzy Logic
• The Rule Application
• Simulations
• Final Considerations
© LES/PUC-Rio
Introdução
• Aristóteles, filósofo grego, foi o fundador da ciência da
lógica.
• Estabeleceu um conjunto de regras rígidas para que
conclusões pudessem ser consideradas logicamente válidas.
• Linha de raciocínio lógico baseado em premissas e
conclusões.
• Exemplo
• Premise 1: All humans are mortal.
• Premise 2: Socrates is a human.
• Conclusion: Socrates is mortal.
© LES/PUC-Rio
Introdução
• Desde então, a lógica Ocidental, assim chamada, tem sido
binária, isto é, uma declaração é falsa ou verdadeira,
• Não podendo ser ao mesmo tempo parcialmente verdadeira
e parcialmente falsa.
• Esta suposição e a lei da não contradição, que coloca que "U
e não U" cobrem todas as possibilidades, formam a base do
pensamento lógico Ocidental.
© LES/PUC-Rio
Lógica Fuzzy
• A Lógica Difusa (Fuzzy Logic) viola estas suposições.
• O conceito de dualidade, estabelecendo que algo pode e
deve coexistir com o seu oposto, faz a lógica difusa parecer
natural, até mesmo inevitável.
• A lógica de Aristóteles classifica como verdade ou falsidade.
• Experiências humanas não podem ser classificadas
simplesmente como verdadeiras ou falsas, sim ou não,
branco ou preto.
• Ao trabalhar com a lógica fuzzy é comum chamar a lógica
booleana de lógica nítida.
© LES/PUC-Rio
Lógica Fuzzy
• Exemplos:
– Aquele homem é alto ou baixo?
– A taxa de risco para aquele empreendimento é grande ou
pequena?
• Um Sim ou Não, na maioria das vezes, é incompleta.
• Na verdade, entre a certeza de ser e a certeza de não ser,
existem infinitos graus de incerteza.
• Tratada matematicamente no passado com o uso da teoria
das probabilidades.
© LES/PUC-Rio
Lógica Fuzzy
• Lógica Difusa, com base na teoria dos Conjuntos
Nebulosos (Fuzzy Set), tem se mostrado mais adequada
para tratar imperfeições da informação do que a Teoria das
Probabilidades.
• Lógica Difusa: “Uma ferramenta capaz de capturar
informações vagas, em geral descritas em uma linguagem
natural e convertê-las para um formato numérico, de fácil
manipulação pelos computadores de hoje em dia.”
© LES/PUC-Rio
Lógica Fuzzy
• Conjunto nebuloso estende o conceito de conjunto
permitindo que um elemento passa a ter um grau de
pertinência variando entre 0 e 1, ao invés de pertencer ou
não ao conjunto como na teoria de conjuntos tradicional.
• Permitem que estados indeterminados possam ser tratados
por dispositivos de controle, como por exemplo avaliar
conceitos como morno, médio...
© LES/PUC-Rio
Lógica Fuzzy
• O raciocínio fuzzy também é conhecido como raciocínio aproximado
e pode ser dividido em 5 etapas.
1. Transformação das variáveis do problema em valores fuzzy, ou
fuzzificação
2. Aplicação dos operadores fuzzy
3. Aplicação da implicação
4. Combinação de todas as saídas fuzzy possíveis
5. Transformação do resultado fuzzy em um resultado nítido, a
defuzzificação.
© LES/PUC-Rio
Lógica Fuzzy
• Passo 1: Transformação das variáveis do problema em
valores fuzzy, ou fuzzificação
– para cada valor de entrada associamos uma função de
pertinência, que permite obter o grau de verdade da
proposição.
– Determinar o grau de pertinência de cada conjunto
(proposição);
– Limitar o valor da entrada entre 0 e 1.
•
Passo 2: Aplicação dos operadores fuzzy
– aplicar os operadores fuzzy, assim como os operadores da
lógica nítida: AND e OR, conhecidos como operadores de
relação.
© LES/PUC-Rio
Lógica Fuzzy
• Passo 3: Aplicação da implicação
– Aplicar o operador de implicação, usado para definir o peso no
resultado e remodelar a função, ou seja, criar a hipótese de
implicação.
– Exemplo: Serviço é excelente OU atendimento é rápido ENTÃO
pagamento é alto
• Passo 4: Combinação de todas as saídas fuzzy possíveis
– Combinação de todas as saídas em um único conjunto fuzzy,
algo semelhante ao processo de união e intersecção, na teoria
dos conjuntos abruptos.
© LES/PUC-Rio
Lógica Fuzzy
• Passo 5: Defuzzificação
– Consiste em retornar os valores;
– Obter um valor numérico dentro da faixa estipulada pela lógica
fuzzy.
© LES/PUC-Rio
The Rule Application
• Java application that implements both Boolean and fuzzy
logic-based inferencing and demostrates the two major
types of reasoning algorithms used with rule-based
systems:
– Forward chaining
– Backward chaining
• Main classes
– Rule
– Clause
– Boolean Rule Base
© LES/PUC-Rio
Rule
• It is used to define a single rule and also contains methods
that support the inferencing process.
• Properties
– A name data member
– A reference to the owning BooleanRuleBase object
– A array of antecedent Clauses
– A single consequent Clause
– Rule’s truth value is stored in the Boolean object. This allows us
to move a null value to indicate that the rule’s truth cannot be
determined
– The fired boolean member indicates whether this rule has been
fired or not.
© LES/PUC-Rio
Clause
• Clauses are used both in the antecedent and consequent
parts of a Rule.
• A Clause is composed by
– a RuleVariable on the left-hand size;
– a Condition, which testes equality, greater than, or less than;
– the right-hand size, which can be a String;
– a truth Boolean which indicates whether the clause is true,
false, or unknown (null);
– A vector of the Rules which contain this Clause;
– A consequent boolean which indicates whether the clause
appears in the antecendet or the consequent of the rule.
© LES/PUC-Rio
Clause
• Automobile: IF num_wheels=4
AND motor=yes
THEN vehicleType=automobile
• Clause num_wheels=4
– Rule Variable: “num_wheels”
– Condition: “=”
– String: “4”
© LES/PUC-Rio
Boolean Rule Base
• Boolean Rule Base defines
– A set of Rule Variables
– Rules
© LES/PUC-Rio
The Rule Application – Fuzzy Classes
• The FuzzyRuleBase implementation is made up of several
classes that roughly parallel the BooleanRuleBase design.
These include:
– FuzzyRule
– FuzzyClause
– FuzzyRuleVariable
– FuzzySet
– FuzzyRuleBase
• Main Algorithm
– Forward chaining
© LES/PUC-Rio
FuzzyRule
• It is used to define a single rule and also contains methods
that support the inferencing process.
• Properties
– A name data member
– A reference to the owning FuzzyRuleBase object
– A array of antecedent Clauses
– A single consequent Clause
– A firedFlag boolean
– Each FuzzyVariable has a unique integer ID
© LES/PUC-Rio
FuzzyClauses
• Clauses are used both in the antecedent and consequent
parts of a FuzzyRule.
• A Clause is composed by
– a FuzzyRuleVariable on the left-hand size
– a FuzzyOperator, which implements fuzzy comparison or
assignment
– the right-hand size, which is a FuzzySet
• Ex:
– VeryFastRule: IF temp is very hot AND humidity is very sticky
THEN motor is very fast
© LES/PUC-Rio
ContinuousFuzzyRuleVariable
• For fuzzy rule processing, we define the base
FuzzyRuleVariable class and the ContinuousFuzzyRuleVariable
subclass that supports the use of FuzzySets in inferencing.
• A ContinuousFuzzyRuleVariable is composed by
– Name of the variable
– Minimum and maximum values of the domain (called discourse)
– Hashtable that holds all of the fuzzy sets and linguistic edges
defined for the variable
– Two WorkingFuzzySet instances. One valFzy holds the current
fuzzy value, while the other one is used as a temporary fuzzy set
during inferencing
© LES/PUC-Rio
FuzzySet
• The FuzzySet class is the base class for the sets
implamentations like triangle, trapezoid, and shoulder.
• A FuzzySet is composed by
– Int setType
– String setName
– String alphaCut
– String DomainLo
– String DomainHi
– Array of Doubles called truthVector that defines the shape of
FuzzySet at 256 points
© LES/PUC-Rio
Membership
FuzzySet - Layouts
Discourse
© LES/PUC-Rio
FuzzySet Classes
• All the FuzzySets define fuzzy memberships functions whose
shape resembles:
– Trapezoid: This Fuzzy set takes four parameters, ptLeft,
ptLeftCore, ptRightCore, and ptRight to describe the base (left
and right) and top (left and right) of the fuzzy set.
– Triangle: This Fuzzy set takes three parameters, ptLeft,
ptLeftCenter, and ptRight to describe the base (left and right) and
top (center) of the fuzzy set.
– Shoulder (one half of a trapezoid): This Fuzzy set takes three
parameters, ptBeg, ptEnd, and the direction of the shoulder,
either right or left.
• There’s also the WorkingFuzzySet, one of the major classes in
the FuzzyRulesBase. It is used to combine fuzzy sets as we
are inferencing with the correlateWith() and implicateWith()
methods.
© LES/PUC-Rio
Fuzzy Rule Base
• The FuzzyRuleBase class implements the RuleBase interface
and contains:
– A name;
– A set of FuzzyRuleVariables and FuzzyRules, along with the
high-level methods for foward chaining.
• The key parameter that control inferencing are the
aplhaCut, inferenceMethod, correlationMethod, and
defuzzificationMethod members
© LES/PUC-Rio
Fuzzy Forward-Chaining Implementation
• Automatically resets the rules, but not the variables wich
may have had their values set by the user.
• The factBase is initialized to a BitSet with all bits clear. It´s
used to keep track of variables that have been computed.
• Unconditional rules are procesed.
• Fuzzy forward inferencing logic is performed in the
processConditionalRules() method
© LES/PUC-Rio
Fuzzy Forward-Chaining Implementation
public void forwardChain() {
Enumeration enum = ruleList.elements();
while(enum.hasMoreElements()){
((FuzzyRule) (enum.nextElement())).reset();
}
BitSet factbase = (BitSet) fbinitial.clone();
factBase.set(0);
processAssertionRules(factBase);
processConditionalRules(factBase);
}
© LES/PUC-Rio
Fuzzy Forward-Chaining Implementation
processAssertionRules()
• Simply walks through the unconditonal rules lists and fires each
rule;
• Since each rule has no antecedent clause, the effect of firing each
rule is to perform them;
© LES/PUC-Rio
Fuzzy Forward-Chaining Implementation
private void processAssertionRules(BitSet factBase) {
trace (“\nProcessing unconditional fuzzy rules “);
Enumeration enum = uncRuleList.elements.elements();
while (enum.hasMoreElements()) {
FuzzyRule rule = (FuzzyRule) (enum.nextElement());
rule.fire(alphacut, factBase);
}
}
© LES/PUC-Rio
Fuzzy Forward-Chaining Implementation
process ConditionalRules()
• Grabbing of Enummeration of all the conditional rules in the rule
base
• For each rule that has not yet fired, the Id bit is extracted and
placed into two working BitSets
• Logically and the set of currently know variables with the variables
required by the rule:
– If result equals the same bits required by the rule, then the rule is
added to the list of rules to be processed.
© LES/PUC-Rio
Fuzzy Forward-Chaining Implementation
process ConditionalRules()
• If there is no more rule to be processed, set moreRules to false
and exits loop.
• Loop over the list, and fire() each rule.
• As soon as rules are fired, their fired flags are set.
© LES/PUC-Rio
Fuzzy Forward-Chaining Implementation
process ConditionalRules()
private void processConditionalRules(BitSet factBase) {
boolean moreRules = true;
Vector tmpRuleSet = new Vector();
trace("\nProcessing conditional fuzzy rules ");
while (moreRules) {
// Create a rule set:
// Examine all conditional rules.
// If a rule has fired, ignore it.
// If a rule has not fired, and if it can be fired given
// the current fact base, add it to the rule set.
Enumeration enum = cndRuleList.elements();
while (enum.hasMoreElements()) {
FuzzyRule rule = (FuzzyRule) (enum.nextElement());
© LES/PUC-Rio
Fuzzy Forward-Chaining Implementation
process ConditionalRules()
if (!rule.isFired()) {
// The rule has not fired; check the rule's antecedents reference
BitSet tmpRuleFacts = rule.getRdReferences();
BitSet tempFacts = rule.getRdReferences();
tempFacts.and(factBase);
// If the antecedents reference variables whose values have been
// determined, the rule can fire, so add it to the rule set.
if (tempFacts.equals(tmpRuleFacts)) {
tmpRuleSet.addElement(rule);
}
}
}
// If the rule set is empty, no rules can be fired; exit the loop.
if (tmpRuleSet.isEmpty()) {
moreRules = false;
break;
}
© LES/PUC-Rio
Fuzzy Forward-Chaining Implementation
process ConditionalRules()
// Okay, we have some rules in the generated rule set;
// Attempt to fire them all. Rules that fire successfully
// update the fact base directly.
for (int i = 0; i < tmpRuleSet.size(); i++) {
FuzzyRule rule = (FuzzyRule) tmpRuleSet.elementAt(i);
trace("\nFiring fuzzy rule: " + rule.getName());
rule.fire(alphaCut, factBase);
}
// We may or may not have fired all the rules in the rule set;
// In any event, do a purge of the rule set to get ready for the
// next iteration of the while loop.
tmpRuleSet.removeAllElements();
}
}
© LES/PUC-Rio
Planning
•
Uma das tarefas mais complexas que IA tenta solucionar.
•
Basicamente:
•
–
Sequência ordenada de tarefas
–
Variedade enorme de técnicas
Técnicas de solução:
–
Decomposição de um grande problema em pequenos problemas
–
Consideração de restrições de precedência
© LES/PUC-Rio
Planning
•
Planejamento não é Busca !
•
Busca x Planejamento
•
•
–
Espaço de soluções em problemas de planejamento é enorme.
–
Restrições de precedência em planejamento impõem dificuldades ainda
maiores
Basicamente:
–
Sequência ordenada de tarefas
–
Variedade enorme de técnicas
Técnicas de solução:
–
Decomposição de um grande problema em pequenos problemas
–
Consideração de restrições de precedência
© LES/PUC-Rio
Planning
Três abordagens para solucionar problemas de planejamento:
• Pilha de objetivos
• Método não linear
• Algoritmo de planejamento hierárquico
© LES/PUC-Rio
Planning
Pilha de Objetivos
• Tentativa de solucionar problemas através do seu
particionamento:
– 1 problema grande = n problemas pequenos
• Baseado no problema de empilhamento de blocos em uma
determinada ordem.
© LES/PUC-Rio
Planning
Pilha de Objetivos
• Dada uma configuração inicial de blocos (tarefas) e
operadores possíveis, deseja-se alcançar o estado final.
• O objetivo é desenvolver uma seqüência de operações que
levem ao objetivo final.
• Usa uma pilha de objetivos que será armazenada até que
objetivos anteriores sejam alcançados.
© LES/PUC-Rio
Planning
Pilha de Objetivos
• Problemas:
– Perda de boas soluções iniciais para solucionar subproblemas
de maior precedência e com isso prejudicar os subproblemas
de menor precedência.
– Tenta encontrar uma solução linear, e não leva em
consideração como isto pode impactar na solução final.
© LES/PUC-Rio
Planning
Método não linear
• Constrói um plano onde dois ou mais objetivos podem
proceder simultaneamente.
• Consegue encontrar boas soluções em problemas que
possuem restrições de precedência mais rígidas, pois,
aborda a prática de executar problemas que podem ser
resolvidos simultaneamente.
• Aplica múltiplos operadores e somente após testar as
restrições atualiza o espaço de soluções.
© LES/PUC-Rio
Planning
Método não linear
• Sistemas de Planejamento não lineares:
– NOAH
– MOLGEN
© LES/PUC-Rio
Planning
Algoritmo de planejamento hierárquico
• Permite o planejamento em maior nível de abstração, para
conseguir soluções globais melhores.
• Mapeia a solução como um todo, para então buscar resolver
os detalhes.
© LES/PUC-Rio
Planning
Algoritmo de planejamento hierárquico
• ABSTRIPS:
– Soluciona o problema levando em consideração as tarefas de
maiores níveis de urgência.
– Em seguida, prossegue para solucionar os problemas de
menores granularidades, adicionando operadores que
satisfaçam as precondições de todos eles.
© LES/PUC-Rio
The Rule Application - Vehicle
• Simulation
– Forward Chaining
– Backward Chaining
© LES/PUC-Rio
Forward Chaining
© LES/PUC-Rio
Backward Chaining
© LES/PUC-Rio
The Rule Application - Motor
• Simulation
– Forward Chaining
© LES/PUC-Rio
The Motor Rule Base Implementation
© LES/PUC-Rio
The Motor Rule Base Implementation
To see if adding more rules would help, a new rule base was created that
covered all possible temperature - humidity combinations. The following table
shows the motor speed for each of the 25 climate scenarios.
© LES/PUC-Rio
The Motor Rule Base Implementation
© LES/PUC-Rio
Final Considerations
• Three types of algorithms
– Forward Chaining
– Backward Chaining
– Fuzzy Logic
• Boolean Logic vs Fuzzy Logic
• The code source will be available.
© LES/PUC-Rio
Bibliography
•
Bigus, Joseph P.; Bigus, Jennifer, Constructing Intelligent Agents Using Java
– Second Edition.
•
Fuzzy Logic – An Introduction (2007)
http://www.seattlerobotics.org/encoder/mar98/fuz/flindex.html, August
•
http://www.zabaronick.com/CO/susan/csc5814/Assignment1/index.html
•
Forward chaining - Wikipedia (2007),
http://en.wikipedia.org/wiki/Forward_chaining, August.
•
Forward chaining of Rules (2007), http://msdn2.microsoft.com/enus/library/aa349441.aspx, August.
•
Reasoning – Wikipedia (2007), http://en.wikipedia.org/wiki/Reasoning,
August
© LES/PUC-Rio
Bibliography
• Backward chaining – Wikipedia (2007)
http://en.wikipedia.org/wiki/Backward_chaining, August.
• API JTP Web site (2007), http://wwwksl.stanford.edu/software/jtp/, August.
© LES/PUC-Rio
Questions?
The End.