Fuzzy Inferencing
The process of fuzzy reasoning is incorporated into what is called a Fuzzy Inferencing System. It is comprised of three steps that process the system inputs to the appropriate system outputs. These steps are 1) Fuzzification, 2) Rule Evaluation, and 3) Defuzzification. The system is illustrated in the following figure.
1Fuzzification
is the first step in the fuzzy inferencing process. This involves a domain formation where crisp inputs are transformed into fuzzy inputs. Crisp inputs are exact inputs measured by sensors and passed into the control system for processing, such as temperature, pressure, rpm's, etc.. Each crisp input that is to be processed by the FIU has its own group of membership functions or sets to which they are transformed. This group of membership functions exists within a universe of discourse that holds all relevant values that the crisp input can possess. The following shows the structure of membership functions within a universe of discourse for a crisp input.
2 Degree of membership:
degree to which a crisp value is compatible to a membership function, value from 0 to 1, also known as truth value or fuzzy input.membership function, MF: defines a fuzzy set by mapping crisp values from its domain to the sets associated degree of membership.
3.crisp inputs: distinct or exact inputs to a certain system variable, usually measured
4.parameters external from the control system, e.g. 6 Volts.
5.label: descriptive name used to identify a membership function.
6.scope: or domain, the width of the membership function, the range of concepts, usually numbers, over which a membership function is mapped.
7.universe of discourse: range of all possible values, or concepts, applicable to a system variable. When designing the number of membership functions for an input variable, labels must initially be determined for the membership functions. The number of labels correspond to the number of regions that the universe should be divided, such that each label describes a region of behavior. A scope must be assigned to each membership function that numerically identifies the range of input values that correspond to a label. The shape of the membership function should be representative of the variable. However this shape is also restricted by the computing resources available. Complicated shapes require more complex descriptive equations or large lookup tables. The next figure shows examples of possible shapes for membership functions.
Learn every thing about Artificial Intelligence, Here from a Subject Expert. Dr. G Veera Raghavaiah., Associate Professor /HOD., MCA Department., The Pedanandipadu College of Arts & Sciences., Pedanandipadu-522235. Guntur-Dt., Andhrapradesh., India. Ph.9441503757.
Tuesday, November 30, 2010
Classical Planners use the STRIPS (Stanford Research Institute Problem Solver)
language to describe states and operators. It is an efficient way to represent
planning algorithms.
language to describe states and operators. It is an efficient way to represent
planning algorithms.
Fuzzy Concepts. Hedges
Another important feature of fuzzy systems is the ability to define "hedges," or
modifier of fuzzy values. These operations are provided in an effort to maintain
close ties to natural language, and to allow for the generation of fuzzy statements
through mathematical calculations. As such, the initial definition of hedges and
operations upon them will be quite a subjective process and may vary from one
project to another. Nonetheless, the system ultimately derived operates with the
same formality as classic logic. The simplest example is in which one transforms
the statement "Jane is old" to "Jane is very old." The hedge "very" is usually
defined as follows:
m"very"A(x) = mA(x)^2 Thus, if mOLD(Jane) = 0.8, then mVERYOLD(Jane) = 0.64.
Other common hedges are "more or less" [typically SQRT(mA(x))], "somewhat,"
"rather," "sort of," and so on. Again, their definition is entirely subjective, but
their operation is consistent: they serve to transform membership/truth values in a
systematic manner according to standard mathematical functions.
A more involved approach to hedges is best shown through the work of Wenstop
in his attempt to model organizational behavior. For his study, he constructed
arrays of values for various terms, either as vectors or matrices. Each term and
hedge was represented as a 7-element vector or 7x7 matrix. He ten intuitively
assigned each element of every vector and matrix a value between 0.0 and 1.0,
inclusive, in what he hoped was intuitively a consistent manner. For example, the
term "high" was assigned the vector 0.0 0.0 0.1 0.3 0.7 1.0 1.0
and "low" was set equal to the reverse of "high," or 1.0 1.0 0.7 0.3 0.1 0.0 0.0
Wenstop was then able to combine groupings of fuzzy statements to create new
fuzzy statements, using the APL function of Max-Min matrix multiplication.
These values were then translated back into natural language statements, so as to
allow fuzzy statements as both input to and output from his simulator. For
example, when the program was asked to generate a label "lower than sortof
low," it returned "very low;" "(slightly higher) than low" yielded "rather low,"
etc. The point of this example is to note that algorithmic procedures can be
devised which translate "fuzzy" terminology into numeric values, perform
reliable operations upon those values, and then return natural language statements
in a reliable manner.
Fuzzy Concepts.
The notion central to fuzzy systems is that truth values (in fuzzy logic) or membership values (in fuzzy sets) are indicated by a value on the range [0.0, 1.0], with 0.0 representing absolute Falseness and 1.0 representing absolute Truth. For example, let us take the statement: "Jane is old."
If Jane's age was 75, we might assign the statement the truth value of 0.80. The statement could be translated into set terminology as follows:
"Jane is a member of the set of old people."
This statement would be rendered symbolically with fuzzy sets as:
mOLD(Jane) = 0.80
where m is the membership function, operating in this case on the fuzzy set of old people, which returns a value between 0.0 and 1.0.
At this juncture it is important to point out the distinction between fuzzy systems and probability. Both operate over the same numeric range, and at first glance both have similar values: 0.0 representing False (or non- membership), and 1.0 representing True (or membership). However, there is a distinction to be made between the two statements:
The probabilistic approach yields the natural-language statement, "There is an 80% chance that Jane is old," while the fuzzy terminology corresponds to "Jane's degree of membership within the set of old people is 0.80." The semantic difference is significant:
the first view supposes that Jane is or is not old (still caught in the Law of the Excluded Middle); it is just that we only have an 80% chance of knowing which set she is in. By contrast, fuzzy terminology supposes that Jane is "more or less" old, or some other term corresponding to the value of 0.80. Further distinctions arising out of the operations will be noted below.
The next step in establishing a complete system of fuzzy logic is to define the operations of EMPTY, EQUAL, COMPLEMENT (NOT), CONTAINMENT, UNION (OR), and INTERSECTION (AND). Before we can do this rigorously, we must state some formal definitions:
Definition 1
: Let X be some set of objects, with elements noted as x. Thus,
X = {x}.
Definition 2
: A fuzzy set A in X is characterized by a membership function mA(x) which maps each point in X onto the real interval [0.0, 1.0]. As mA(x) approaches 1.0, the "grade of membership" of x in A increases.
Definition 3
: A is EMPTY iff for all x, mA(x) = 0.0.
Definition 4
: A = B iff for all x: mA(x) = mB(x) [or, mA = mB].
Definition 5
: mA' = 1 - mA.
Definition 6
: A is CONTAINED in B iff mA <= mB.
Definition 7
: C = A UNION B, where: mC(x) = MAX(mA(x), mB(x)).
Definition 8:
C = A INTERSECTION B where: mC(x) = MIN(mA(x), mB(x)).
It is important to note the last two operations, UNION (OR) and INTERSECTION
(AND), which represent the clearest point of departure from a probabilistic theory for sets to fuzzy sets. Operationally, the differences are as follows:
For independent events, the probabilistic operation for AND is multiplication,
which (it can be argued) is counterintuitive for fuzzy systems. For example, let us
presume that x = Bob, S is the fuzzy set of smart people, and T is the fuzzy set of
tall people. Then, if mS(x) = 0.90 and uT(x) = 0.90, the probabilistic result would
be: mS(x) * mT(x) = 0.81 whereas the fuzzy result would be:
MIN(uS(x), uT(x)) = 0.90
The probabilistic calculation yields a result that is lower than either of the two
initial values, which when viewed as "the chance of knowing" makes good sense.
However, in fuzzy terms the two membership functions would read something
like "Bob is very smart" and "Bob is very tall." If we presume for the sake of
argument that "very" is a stronger term than "quite," and that we would correlate
"quite" with the value 0.81, then the semantic difference becomes obvious. The
probabilistic calculation would yield the statement If Bob is very smart, and Bob
is very tall, then Bob is a quite tall, smart person.The fuzzy calculation, however,
would yield If Bob is very smart, and Bob is very tall, then Bob is a very tall,
smart person.Another problem arises as we incorporate more factors into our
equations (such as the fuzzy set of heavy people, etc.). We find that the ultimate
result of a series of AND's approaches 0.0, even if all factors are initially high.
Fuzzy theorists argue that this is wrong: that five factors of the value 0.90 (let us
say, "very") AND'ed together, should yield a value of 0.90 (again, "very"), not
0.59 (perhaps equivalent to "somewhat").
Similarly, the probabilistic version of A OR B is (A+B - A*B), which approaches
1.0 as additional factors are considered. Fuzzy theorists argue that a sting of low
membership grades should not produce a high membership grade instead, the limit
of the resulting membership grade should be the strongest membership value in
the collection. The skeptical observer will note that the assignment of values to
linguistic meanings (such as 0.90 to "very") and vice versa, is a most imprecise
operation. Fuzzy systems, it should be noted, lay no claim to establishing a formal
procedure for assignments at this level; in fact, the only argument for a particular
assignment is its intuitive strength. What fuzzy logic does propose is to establish a
formal method of operating on these values, once the primitives have been
established.
Planning as Search
Planning as Search:
There are two main approaches to solving planning problems, depending on the kind of search space that is explored:
1. Situation-space search
2. Planning-space searchIn situation space search
In Situation-Space search
• the search space is the space of all possible states or situations of the world
• initial state defines one node
• a goal node is a state where all goals in the goal state are satisfied
• a solution plan is the sequence of actions (e.g. operator instances) in the path
from the start node to a goal node.
In Plan-Space Search
• the search space is the space of all possible plans
• a node corresponds to a partial plan
• initially we will specify an "initial plan" which is one node in this space
• a goal node is a node containing a plan which is complete, satisfying all of the
goals in the goal state
• the node itself contains all of the information for determining a solution plan
(e.g.sequence of actions)
Goal Interaction
Most planning algorithms assume that the goals to be achieved are independent or nearly independent in the sense that each can be solved separately and then the solutions concatenated together. If the order of solving a set of goals (either the original goals or a set of sub-goals which are the preconditions of an operator) fails because solving a latter goal undoes an earlier goal, then this version of the STRIPS algorithm fails. Hence, situation-space planners do not allow for interleaving of steps in any solution it finds.
Principle of Least Commitment:The principle of least commitment is the idea of never making a choice unless required to do so. The advantage of using this principle is you won't have to backtrack later! In planning, one application of this principle is to never order plan steps unless it's necessary for some reason. So, partial-order planners exhibit this property because constraint ordering steps will only be inserted when necessary. On the other hand, situation-space progression planners make commitments about the order of steps as they try to find a solution and therefore may make mistakes from poor guesses about the right order of steps.
Monday, November 29, 2010
Situation Calculus
Situation Calculus
Situation calculus is a version of first-order-logic (FOL) that is augmented so that it can reason about actions in time.
• Add situation variables to specify time. A situation is a snapshot of the world at
an interval of time when nothing changes
• Add a special predicate holds(f,s) that means "f is true in situation s"
• Add a function result(a,s) that maps the current situations into a new situation as
a result of performing action a.
Situation calculus is a version of first-order-logic (FOL) that is augmented so that it can reason about actions in time.
• Add situation variables to specify time. A situation is a snapshot of the world at
an interval of time when nothing changes
• Add a special predicate holds(f,s) that means "f is true in situation s"
• Add a function result(a,s) that maps the current situations into a new situation as
a result of performing action a.
Saturday, November 27, 2010
Planning Systems
Classical Planners use the STRIPS (Stanford Research Institute Problem Solver)
language to describe states and operators. It is an efficient way to represent planning
algorithms.
Representation of States and Goals
States are represented by conjunctions of function-free ground literals, that is, predicates
applied to constant symbols, possibly negated.
An example of an initial state is:
At(Home)
/\ -
Have(Milk)
/\ -
Have(Bananas)
/\ -
Have(Drill)
/\ ...
A state description does not have to be complete. We just want to obtain a successful plan
to a set of possible complete states. But if it does not mention a given positive literal, then
the literal can be assumed to be false.
Goals are a conjunction of literals. Therefore the goal is
language to describe states and operators. It is an efficient way to represent planning
algorithms.
Representation of States and Goals
States are represented by conjunctions of function-free ground literals, that is, predicates
applied to constant symbols, possibly negated.
An example of an initial state is:
At(Home)
/\ -
Have(Milk)
/\ -
Have(Bananas)
/\ -
Have(Drill)
/\ ...
A state description does not have to be complete. We just want to obtain a successful plan
to a set of possible complete states. But if it does not mention a given positive literal, then
the literal can be assumed to be false.
Goals are a conjunction of literals. Therefore the goal is
Algorithm of a simple planning agent:
1. Generate a goal to achieve
2. Construct a plan to achieve goal from current state
3. Execute plan until finished
4. Begin again with new goal
1. Generate a goal to achieve
2. Construct a plan to achieve goal from current state
3. Execute plan until finished
4. Begin again with new goal
Friday, November 26, 2010
ProblemSolving Vs Planning.
Problem Solving vs. Planning
A simple planning agent is very similar to problem-solving agents in that it constructs
plans that achieve its goals, and then executes them. The limitations of the problem-
solving approach motivates the design of planning systems.
To solve a planning problem using a state-space search approach we would let the:
• initial state = initial situation
• goal-test predicate = goal state description
• successor function computed from the set of operators
• once a goal is found, solution plan is the sequence of operators in the path from
the start node to the goal node In searches, operators are used simply to generate successor states and we
can not look "inside" an operator to see how it’s defined. The goal-test predicate also is used as a
"black box" to test if a state is a goal or not. The search cannot use properties of how a
goal is defined in order to reason about finding path to that goal.
Hence this approach is all algorithm and representation weak.
Planning is considered different from problem solving because of the difference in the
way they represent states, goals, actions, and the differences in the way they construct
action sequences. Remember the search-based problem solver had four basic elements:
• Representations of actions: programs that develop successor state descriptions which
represent actions.
• Representation of state: every state description is complete. This is because a
complete description of the initial state is given, and actions are represented by a program
that creates complete state descriptions.
• Representation of goals: a problem solving agent has only information about it's
goal, which is in terms of a goal test and the heuristic function.
• Representation of plans: in problem solving, the solution is a sequence of actions.
In a simple problem:
"Get a quart of milk and a bunch of bananas and a variable speed
cordless drill" for a problem solving exercise we need to specify:
Initial State: the agent is at home without any objects that he is wanting.
Operator Set: everything the agent can do.
Heuristic function: the # of things that have not yet been acquired.
Problems with Problem solving agent: It is evident from the above figure that the actual branching factor
would be in the thousands or millions. The heuristic evaluation function can only choose states to
determine which one is closer to the goal. It cannot eliminate actions from
consideration. The agent makes guesses by considering actions and the evaluation
function ranks those guesses. The agent picks the best guess, but then has no idea
what to try next and therefore starts guessing again. It considers sequences of actions beginning from the
initial state. The agent is
forced to decide what to do in the initial state first, where possible choices are to
go to any of the next places. Until the agent decides how to acquire the objects, it
can't decide where to go.Planning emphasizes what is in operator and goal representations. There are three
key ideas behind planning:to "open up" the representations
of state, goals, and operators so that a reasoner
can more intelligently select actions when they are needed
the planner is free to add actions to the plan
wherever they are needed, rather
than in an incremental sequence starting at the initial state
most parts of the world are independent of most other parts
which makes it feasible to take a conjunctive goal and solve it with a divide-and-conquer strategy
A simple planning agent is very similar to problem-solving agents in that it constructs
plans that achieve its goals, and then executes them. The limitations of the problem-
solving approach motivates the design of planning systems.
To solve a planning problem using a state-space search approach we would let the:
• initial state = initial situation
• goal-test predicate = goal state description
• successor function computed from the set of operators
• once a goal is found, solution plan is the sequence of operators in the path from
the start node to the goal node In searches, operators are used simply to generate successor states and we
can not look "inside" an operator to see how it’s defined. The goal-test predicate also is used as a
"black box" to test if a state is a goal or not. The search cannot use properties of how a
goal is defined in order to reason about finding path to that goal.
Hence this approach is all algorithm and representation weak.
Planning is considered different from problem solving because of the difference in the
way they represent states, goals, actions, and the differences in the way they construct
action sequences. Remember the search-based problem solver had four basic elements:
• Representations of actions: programs that develop successor state descriptions which
represent actions.
• Representation of state: every state description is complete. This is because a
complete description of the initial state is given, and actions are represented by a program
that creates complete state descriptions.
• Representation of goals: a problem solving agent has only information about it's
goal, which is in terms of a goal test and the heuristic function.
• Representation of plans: in problem solving, the solution is a sequence of actions.
In a simple problem:
"Get a quart of milk and a bunch of bananas and a variable speed
cordless drill" for a problem solving exercise we need to specify:
Initial State: the agent is at home without any objects that he is wanting.
Operator Set: everything the agent can do.
Heuristic function: the # of things that have not yet been acquired.
Problems with Problem solving agent: It is evident from the above figure that the actual branching factor
would be in the thousands or millions. The heuristic evaluation function can only choose states to
determine which one is closer to the goal. It cannot eliminate actions from
consideration. The agent makes guesses by considering actions and the evaluation
function ranks those guesses. The agent picks the best guess, but then has no idea
what to try next and therefore starts guessing again. It considers sequences of actions beginning from the
initial state. The agent is
forced to decide what to do in the initial state first, where possible choices are to
go to any of the next places. Until the agent decides how to acquire the objects, it
can't decide where to go.Planning emphasizes what is in operator and goal representations. There are three
key ideas behind planning:to "open up" the representations
of state, goals, and operators so that a reasoner
can more intelligently select actions when they are needed
the planner is free to add actions to the plan
wherever they are needed, rather
than in an incremental sequence starting at the initial state
most parts of the world are independent of most other parts
which makes it feasible to take a conjunctive goal and solve it with a divide-and-conquer strategy
Algorithem simple Planning Agent.
1. Generate a goal to achieve
2. Construct a plan to achieve goal from current state
3. Execute plan until finished
4. Begin again with new goal
The agent first generates a goal to achieve, and then constructs a plan to achieve it from
the current state. Once it has a plan, it keeps executing it until the plan is finished, then
begins again with a new goal.
Assumptions:
A simple planning agent create and use plans based on the following assumptions:
Atomic time :each action is indivisible
No concurrent actions : allowed
Deterministic actions : result of each actions is completely determined by the
definition of the action, and there is no uncertainty in performing it in the world.
Agent is the sole cause of change: in the world.
Agent is omniscient : has complete knowledge of the state of the world
2. Construct a plan to achieve goal from current state
3. Execute plan until finished
4. Begin again with new goal
The agent first generates a goal to achieve, and then constructs a plan to achieve it from
the current state. Once it has a plan, it keeps executing it until the plan is finished, then
begins again with a new goal.
Assumptions:
A simple planning agent create and use plans based on the following assumptions:
Atomic time :each action is indivisible
No concurrent actions : allowed
Deterministic actions : result of each actions is completely determined by the
definition of the action, and there is no uncertainty in performing it in the world.
Agent is the sole cause of change: in the world.
Agent is omniscient : has complete knowledge of the state of the world
LogicBasedPlanning.
Introduction to Planning
The purpose of planning is to find a sequence of actions that achieves a given goal when
performed starting in a given state. In other words, given a set of operator instances
(defining the possible primitive actions by the agent), an initial state description, and a
goal state description or predicate, the planning agent computes a plan.
What is a plan?
A sequence of operator instances, such that "executing" them in the
initial state will change the world to a state satisfying the goal state description. Goals
are usually specified as a conjunction of goals to be achieved.
Simple Planning Agent:
Earlier we saw that
problem-solving agents
are able to plan ahead - to consider the
consequences of sequences
of actions - before acting. We also saw that a knowledge-based agents can select actions based on explicit, logical representations of the current state and the effects of actions. This allows the agent to succeed in complex, inaccessible environments that are too difficult for a problem-solving agent
Problem Solving Agents + Knowledge-based Agents = Planning Agents
In this module, we put these two ideas together to build
planning agents.
At the most abstract level, the task of planning is the same as problem solving. Planning can be
viewed as a type of problem solving in which the agent uses beliefs about actions and
their consequences to search for a solution over the more abstract space of plans, rather than over the space of situations
Planning.!
The students should understand the formulation of planning problems
The student should understand the difference between problem solving and planning
and the need for knowledge representation in large scale problem solving
Students should understand the STRIPS planning language
Students should be able to represent a real life planning problem using STRIPS
operators
Students should understand planning using situation calculus and the related frame
problems
Students should understand the formulation of planning as a search problem
Students should learn the following planning algorithms
Situation space planning
Plan space planning
Progression planning
Regression planning
The student should understand the difficulties of full commitment planning
Students should understand the necessity of least commitment
Students should learn partial order planning algorithms
At the end of this lesson the student should be able to do the following:
Represent a planning problem in STRIPS language
Use a suitable planning algorithm to solve the problem.
The student should understand the difference between problem solving and planning
and the need for knowledge representation in large scale problem solving
Students should understand the STRIPS planning language
Students should be able to represent a real life planning problem using STRIPS
operators
Students should understand planning using situation calculus and the related frame
problems
Students should understand the formulation of planning as a search problem
Students should learn the following planning algorithms
Situation space planning
Plan space planning
Progression planning
Regression planning
The student should understand the difficulties of full commitment planning
Students should understand the necessity of least commitment
Students should learn partial order planning algorithms
At the end of this lesson the student should be able to do the following:
Represent a planning problem in STRIPS language
Use a suitable planning algorithm to solve the problem.
Subscribe to:
Posts (Atom)