Artificial Intelligence I
Artificial Intellegence
What is artificial Intellegence?
"It is the exciting new effort to make computers think . . . machines with minds, in the full and literal sense"
(Haugeland, 1985)
"The study of mental faculties through the use of computational models"
(Charniak and McDermott, 1985)
"[The automation of] activities that we associate with human thinking, activities such as decision-making, problem solving, learning..."
(Bellman, 1978)
"The study of the computations that make it possible to perceive, reason, and act"
(Winston, 1992)
"The art of creating machines that perform functions that require intelligence when performed by people"
(Kurzweil, 1990)
"A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes"
(Schalkoff, 1 990)
"The branch of computer science that is concerned with the automation of intelligent behavior"
(Luger and Stubblefield, 1993)
"The study of how to make computers do things at which, at the moment, people are better"
(Rich and Knight, 1 99 1 )
AI systems can be organized into four categories:
- Systems that think like humans. Systems that think rationally.
- Systems that act like humans.
- Systems that act rationally.
- Acting humanly: The Turing Test approach
The requirements of an Arificially intellegent computer
- Natural language processing to enable it to communicate successfully in English (or some other human language);
- Knowledge representation to store information provided before or during the interrogation;
- Automated reasoning to use the stored information to answer questions and to draw new conclusions;
- Machine learning to adapt to new circumstances and to detect and extrapolate patterns.
To pass the total Turing Test, the computer will need
- Computer vision to perceive objects, and
- Robotics to move them about.
History of AI
Presence of AI in Real World
Case I
HITECH is the first computer program to defeat a grandmaster(Arnold Denker) in a game of chess.
Case II
"I want to go from Bangalore to Delhi," the traveller says into the microphone. "What date will you be travelling on?" is the reply. The traveller explains she wants to go July 10th, nonstop, on the cheapest available fare, returning on Monday. A speech understanding program named PEGASUS handles the whole transaction, which results in a confirmed reservation that saves the traveller 990$ over the regular coach fare. Even though the speech recognizer gets one out of ten words wrong, it is able to recover from these errors because of its understanding of how dialogs are put together.
What is an Intelligent Agents?
An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through effectors. An agent always acts rationally.
Autonomy of an Agent
If the agent's actions are based completely on built-in knowledge, such that it need not pay any attention to its percepts, then we say that the agent lacks autonomy. For example, if the clock manufacturer was prescient enough to know that the clock's owner would be going to America at some particular date, then a mechanism could be built in to adjust the hands automatically by five hours at just the right time. This would certainly be successful behavior, but the intelligence seems to belong to the clock's designer rather than to the clock itself.
STRUCTURE OF INTELLIGENT AGENTS
The job of AI is to design the agent program:
A function that implements the agent mapping from percepts to actions. We assume this program will run on some sort of computing device, which we will call the architecture.
agent = architecture + program
A sample Agent program
A skeleton agent. On each invocation, the agent's memory is updated to reflect the new percept, the best action is chosen, and the fact that the action was taken is also stored in memory. The memory persists from one invocation to the next.
function SKELETON-AGENT[(percept) returns action
static: memory, the agent's memory of the world
memory — UPDATE-MEMORY(memory, percept)
action <— CHOOSE-BEST-ACTION(memory)
memory — UPDATE-MEMORY(memorv, action)
return action
Example of Car driver agent :
Disadvantages of Table driven agent
- The table needed for something as simple as an agent that can only play chess would be about 3510° entries.
- It would take quite a long time for the designer to build the table.
- The agent has no autonomy at all, because the calculation of best actions is entirely builtin.
So if the environment changed in some unexpected way, the agent would be lost. - Even if we gave the agent a learning mechanism as well, so that it could have a degree of
autonomy, it would take forever to learn the right value for all the table entries.
An agent based on a prespecified lookup table
function TABLE-DRIVEN-AGENT(percepf) returns action
static: percepts, a sequence, initially empty
table, a table, indexed by percept sequences,
initially fully specified
append percept to the end of percepts
action <— LookUp(percepts, table)
return action
Different types of agent programs:
1 ) Simple reflex agents
functionSIMPLE-REFLEX-AGENT(percept) returns action
static: rules, a set of condition-action rules
state <— lNTERPRET-INPUT(percept)
rule <- RULE-MATCH(state, rules)
action <- RULE-ACTION[rule]
return action
2 ) Agents that keep track of the world
The simple reflex agent described before will work only if the correct decision can be made on the basis of the current percept. If the car in front is a recent model, and has the centrally mounted brake system, then it is to be possible to tell if it is braking from a single image agent will have to maintain some sort of internal state in order to choose an action.
3 ) Goal-based agents
a goal based reflex agent:
function REFLEX-AGENT-WiTH-STATE(percepts) returns action; static: state, a description of the current world state rules, a set of condition-action rules state <— UPDATE-STATE(state, percept) rule — RULE-MATCH(state, rules) action — RULE-ACTION[state] state <- UPDATE-STATE (state, action) return action
4 ) Utility-based agents :
The agents which are developed having their end uses as their building blocks are called utility based agents..
Classifications of enviornment can be based on :
- Accessible vs. Inaccessible.
- Deterministic vs. Nondeterministic.
- Episodic vs. Nonepisodic.
- Static vs. Dynamic
- Discrete vs. Continuous
Environment programs
The basic environment simulator program. It gives each agent its percept, gets an action from each agent, and then updates the environment.
procedure RUN-ENVIRONMENT(state, UPDATE-FN, agents, termination)
inputs: state, the initial state of the environment
UPDATE-FN, function to modify the environment
agents, a set of agents
termination, a predicate to test when we are done
repeat
for each agent in agents do
PERCEPT[agent] <— GEY-PERCEPT(agent, state)
end
for each agent in agents do
ACTION[agent] — PROGRAM[agent](PERCEPT[agent])
end
state <— UPDATE-FN(actions, agents, state)
until termination(state)
An environment simulator is a program that keeps track of the performance measure for each agent.
function RUN-EVAL-ENVIRONMENT(state, UPDATE-FN, agents, termination,
PERFORMANCE-FN)
returns scores
local variables: scores, a vector the same size as agents, all 0
repeat
for each agent in agents do
PERCEPT[agent] <- GET-PERCEPT(agent, state)
end
for each agent in agents do
ACTTON[agent] <- PROGRAM[agent](PERCEPT[agent])
end
state = UPDATE-FN(actions, agents, state)
scores= PERFORMANCE-FN(scores, agents, state)
untill termination(states)
return scores;
Problem solving agent
Problem-solving agents decide what to do by finding sequences of actions that lead to desirable state.
simple example :
A simple problem-solving agent.
function SIMPLE-PROBLEM-SOLVING-AGENT(P) returns an action
inputs: p, a percept
static: s, an action sequence, initially empty
state, some description of the current world state
g, a goal, initially null
problem, a problem formulation
state <— UPDATE-STATE(state, p)
if s is empty then
g — FORMULATE-GOAL(state)
problem <— FORMULATE-PROBLEM(state, g)
s r- SEARCH( problem)
action — RECOMMENDATION(s,state)
s <— REMAINDER(s, state)
return action
Problem formulation based on different states of agent :
Suppose that the agent's sensors give it enough information to tell exactly which state it is in (i.e., the world is accessible); and suppose that it knows exactly what each of its actions does. Then it can calculate exactly which state it will be in after any sequence of actions. This is the simplest case, which we call a single-state problem.
When the world is not fully accessible, the agent must reason about sets of states that it might
get to, rather than single states. We call this a multiple-state problem.
Components of a Well defined problems and solutions
- Datatype PROBLEM
- Components: INITIAL-STATE, OPERATORS, GOAL-TEST, PATH-COST-FUNCTION
- A Problem is really a collection of information that the agent will use to decide what to do. The initial state that the agent knows itself to be in
- The term Operator is used to denote the description of an action in terms of which state will be reached by carrying out the action in a particular state.
- The Goal Test is a test which the agent can apply to a single state description to determine if it is a goal state.
- A Path Cost function is a function that assigns a cost to a path
Measuring problem solving Preformance
The effectiveness of a search technique can be measured in at least three ways.
1) Does it find a solution?
2) Is it a good solution (one with a low path cost)?
3) What is the search cost associated with the time and memory required to find a solution?
Example for problem formulation
8 Queens Problem
Goal test: 8 queens on board: placing 8 queens on chess board so that no queen attacks each other.
Path cost: zero.
There are also different possible states and operators. Consider the following simple-minded formulation:
States: any arrangement of 0 to 8 queens on board.
Operators: add a queen to any square.
example 2
Route finding: it is used in a variety of applications, suchas routing in computer networks, automated travel advisory systems, and airline travel planning systems. Touring and travelling salesperson problems, VLSI layout,Robot navigation,Assembly sequencing.
Searching for solutions:
An informal description of the general search algorithm.
function GENERAL-SEARCH(problem strategy) returns a solution,
or failure
initialize the search tree using the initial state of problem
loop do
if there are no candidates for expansion then return failure
choose a leaf node for expansion according to strategy
if the node contains a goal state then return the
corresponding solution
else expand the node and add the resulting nodes to the search tree
end
Data structures for search trees
data type node
components: STATE, PARENT-NODE, OPERATOR, DEPTH, PATH-COST
the state in the state space to which the node corresponds;
the node in the search tree that generated this node (this is called the parent node);
the operator that was applied to generate the node;
the number of nodes on the path from the root to this node (the depth of the node);
the path cost of the path from the initial state to the node.
Different Search strategies:
The search algorithm's optimality is based on following factors:
Completeness: is the strategy guaranteed to find a solution when there is one?
Time complexity: how long does it take to find a solution?
Space complexity: how much memory does it need to perform the search?
Optimality: does the strategy find the highest-quality solution when there are several different solutions?
Breadth-first search
One simple search strategy is a breadth-first search. In this strategy, the root node is expanded first, then all the nodes generated by the root node are expanded next, and then their successors, and so on.
Uniform cost search
Breadth-first search finds the shallowest goal state, but this may not always be the least-cost solution for a general path cost function. Uniform cost search modifies the breadth-first strategy by always expanding the lowest-cost node on the fringe (as measured by the path cost g(n)), rather than the lowest-depth node.
Depth-first search
Depth-first search always expands one of the nodes at the deepest level of the tree. Only when the search hits a dead end (a nongoal node with no expansion) does the search go back and expand nodes at shallower levels.
Depth-limited search
Depth-limited search avoids the pitfalls of depth-first search by imposing a cutoff on the maximum depth of a path.
Iterative deepening search
Iterative deepening search is a strategy that sidesteps the issue of choosing the best depth limit by trying all possible depth limits: first depth 0, then depth 1, then depth 2, and so on.
Bidirectional search
The idea behind bidirectional search is to simultaneously search both forward from the initial state and backward from the goal, and stop when the two searches meet in the middle .
Comparing search strategies
Evaluation of search strategies, b is the branching factor; d is the depth of solution; m is the maximum depth of the search tree; l is the depth limit.
How to avoid repeated states
Three ways to deal with repeated states
1- Do not return to the state you just came from.
2- Do not create paths with cycles in them.
3- Do not generate any state that was ever generated before
Constraint satisfaction search
A constraint satisfaction problem (or CSP) is a special kind of problem that satisfies some additional structural properties beyond the basic requirements for problems in general.
Informed search method
Best first search:When the nodes are ordered so that the one with the best evaluation is expanded first, the resulting strategy is called best-first search.
OPEN = initial state
while OPEN != null
do
1. Pick the best node on open.
2. Create open's successors
3. For each successor do:
a. If it has not been generated before: evaluate it,
add it to OPEN, and record its parent
b. Otherwise: change the parent if this new path is
better than previous one.
done
Greedy search:
The node whose state is judged to be closest to the goal state is always expanded first.
Minimizing the total path cost: A* search
Greedy search minimizes the estimated cost to the goal, h(n).
Uniform-cost search, on the other hand, minimizes the cost of the path so far, g(n);
f(n) = g(n) + h(n).
If h is admissible, f(n) never overestimates the actual cost of the best solution through n. Bestfirst
search using as the evaluation function and an admissible h function is known as A*
search.
The behavior of A* search
Proof of the optimality of A*
Proof of the completeness of A*
Complexity of A*
|h(n) -A*(n)|<0(log h*(n))|
Computation time is not, however, A*'s main drawback. Because it keeps all generated
nodes in memory, A* usually runs out of space long before it runs out of time.
Memory Bounded Search
Iterative deepening A* search (IDA*)
IDA* is a variant of the A* search algorithm which uses iterative deepening to keep the memory usage lower than in A*. It is an informed search based on the idea of the uninformed iterative deepening search.
def IDA_star():
cost_limit = heuristics[rootNode]
while True:
(solution, cost_limit) = DFS(0, rootNode,
cost_limit, [rootNode])
if solution != None: return (solution, cost_limit)
if cost_limit == ∞: return None
# returns (solution-sequence or None, new cost limit)
def DFS(start_cost, node, cost_limit, path_so_far):
minimum_cost = start_cost + heuristics[node]
if minimum_cost > cost_limit: return (None, minimum_cost)
if node in goalNodes: return (path_so_far, cost_limit)
next_cost_limit = ∞
for succNode in successors[node]:
newStartCost = start_cost + edgeCosts[(node,succNode)]
(solution, new_cost_limit) = DFS(newStartCost, succNode,
cost_limit, path_so_far + [succNode])
if solution != None: return (solution, new_cost_limit)
next_cost_limit = min(next_cost_limit, new_cost_limit)
return (None, next_cost_limit)
SMA* search
Sketch of the SMA* algorithm. Note that numerous details have been omitted in the interests of clarity.
function SMA*(probem) returns a solution sequence
inputs: problem, a problem
static: Queue, a queue of nodes ordered by-cost
Queue — MAKE-QUEUE({MAKE-NODE(lNITIAL-STATE[problem])})
loop do
if Queue is empty then return failure
n — deepest least-f-cost node in Queue
if GoAL-TEST(n) then return success
S — NEXT-SUCCESSOR(rc)
if s is not a goal and is at maximum depth then
f(.v) - oc
else
f(s) <- MAX(f(n), g(i)+h(j))
if all of j's successors have been generated then
update n's/-cost and those of its ancestors if necessary
if SUCCESSORS(n) all in memory then remove n from Queue
if memory is full then
delete shallowest, highest-f-cost node in Queue
remove it from its parent's successor list
insert its parent on Queue if necessary
insert s on Queue
end
Iterative Improvement Algorithms
The general idea is to start with a complete configuration and to make modifications to improve its quality interatively.
Hill-climbing search
Discrete Space Hill Climbing Algorithm
currentNode = startNode;
loop do
L = NEIGHBORS(currentNode);
nextEval = -INF;
nextNode = NULL;
for all x in L
if (EVAL(x) > nextEval)
nextNode = x;
nextEval = EVAL(x);
if nextEval <= EVAL(currentNode)
//Return current node since no better neighbors exist
return currentNode;
currentNode = nextNode;
Simulated annealing
The simulated annealing search algorithm.
s ← s0; e ← E(s)
// Initial state, energy.
sbest ← s; ebest ← e
// Initial "best" solution
k ← 0
// Energy evaluation count.
while k < kmax and e > emax
// While time left & not good enough:
snew ← neighbour(s)
// Pick some neighbour.
enew ← E(snew)
// Compute its energy.
if enew < ebest then
// Is this a new best?
sbest ← snew; ebest ← enew
// Save 'new neighbour' to 'best found'.
if P(e, enew, temp(k/kmax)) > random() then
// Should we move to it?
s ← snew; e ← enew
// Yes, change state.
k ← k + 1
// One more evaluation done
return sbest
// Return the best solution found.
Applications in constraint satisfaction problems
A two-step solution for an 8-queens problem using min-conflicts. At each stage, a queen is chosen for reassignment in its column. The number of conflicts (in this case, the number of attacking queens) is shown in each square. The algorithm moves the queen to the min-conflict square, breaking ties randomly.
Game Playing
Games as Search Problem
A game can be formally defined as a kind of search problem with the following components:
The initial state, which includes the board position and an indication of whose move it is , A set of operators, which define the legal moves that a player can make. A terminal test, which determines when the game is over. States where the game has ended are called terminal states.
A utility function (also called a payoff function), which gives a numeric value for the outcome of a game. In chess, the outcome is a win, loss, or draw, which we can represent by the values +1, -1, or 0. Some games have a wider variety of possible outcomes.
Perfect decision in two person games
An algorithm for calculating minimax decisions. It returns the operator that corresponding to the best possible move, that is, the move that leads to the outcome with the best utility, under the assumption that the opponent plays to minimize utility.
The function MINIMAX-VALUE goes through the whole game tree, all the way to the leaves,
to determine the backed-up value of a state.
function MINlMAX-DECISION(game) returns an operator for each op in OPERATORS[game] do VALUE[op] — MINIMAX-VALUE(APPLY(op, game), game) end return the op with the highest VALUE[op]
function MiNlMAX-VALUE(state, game) returns a
utility value
if TERMiNAL-TEST[gamel(state) then
return UTILITY[game](state)
else if MAX is to move in state then
return the highest MINI MAX-VALUE of
Successors(state)
else
return the lowest MINIMAX-VALUE of
Succesors(state)
ALPHA-BETA PRUNING
The process of eliminating a branch of the search tree from consideration without examining it is called pruning the search tree. The particular technique we will examine is called alpha-beta pruning. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.
Effectiveness of alpha-beta pruning algorithm
The effectiveness of alpha-beta depends on the ordering in which the successors are examined.
The alpha-beta search algorithm, It does the same computation as a normal minimax, but prunes the search tree.
function MAX-VAULVE(state, game, a, ft) returns the minimax
value of state
inputs: state, current state in game
game, game description
a, the best score for MAX along the path to state
ft, the best score for MIN along the path to state
if CUTOFF-TEST(state) then return EvAL(state)
for each s in Successors(state) do
a <— MAX(Q , MlN-VALUE(s, game, a, ft))
if a > ft then return ft
end
return a
function MIN-VALUE(.vfate, game, a, ft) returns the minimax
value of state
if CUTOFF-TEST(state) then return Eval(state)
for each s in Successors(state) do
ft — MIN( ft, MAX -VALUER, game, a, ft))
if ft < a then return a
end
return ft
Agents That Reason Logically
A Knowledge Based Agent
The central component of a knowledge-based agent is its knowledge base, a knowledge base is a set of representations of facts about the world.
We can describe a knowledge-based agent at three levels
The knowledge level or epistemological level is the most abstract For example, an automated taxi might be said to know that the Golden Gate Bridge links San Francisco and Marin County. If TELL and ASK work correctly, then most of the time we canwork at the knowledge level and not worry about lower levels.
The logical level is the level at which the knowledge is encoded into sentences. For example the taxi might be described as having the logical sentence Links(GGBridge, SF, Marin) in its knowledge base.
The implementation level is the level that runs on the agent architecture. By a complex set of pointers connecting machine addresses corresponding to the individual symbols. The choice of implementation is very important to the efficient performance of the agent, but it is irrelevant to the logical level and the knowledge level.
What are Inference in computers?
Logics : consists of synatx, symantics and proof theory.
Propositional logic, symbols represent whole propositions (facts);
Ontological commitments have to do with the nature of reality
Temporal logic assumes that the world is ordered by a set of time points or intervals, and includes built-in mechanisms for reasoning about time.
fuzzy logic can have degrees of belief in a sentence, and also allow degrees of truth:
a fact need not be true or false in the world, but can be true to a certain degree.
Representation, Reasoning and Logic of reasoning agents
The syntax of a language describes the possible configurations that can constitute sentences.
The semantics determines the facts in the world to which the sentences refer.
Because sentences are physical configurations of parts of the agent, reasoning must be a process of constructing new physical configurations from old ones. Proper reasoning should ensure that the new configurations represent facts that actually follow from the facts that the old configurations represent. The connection between sentences and facts is provided by the semantics of the language
Propositional Logic
A BNF (Backus-Naur Form) grammar of sentences in propositional logic.
Sentence — AtomicSentence |ComplexSentence
AtomicSentence --- True | False |P Q R ...
ComplexSentence — ( Sentence )
|Sentence Connective Sentence
|~Sentence
Connective — A | V
Semantics
Rules of inference for propositional logic
Complexity of prepositional inference
The use of inference rules to draw conclusions from a knowledge base relies implicitly on a general property of certain logics (including prepositional and first-order logic) called monotonicity.
First Order Logic
First-order logic makes a stronger set of ontological commitments. The main one is that the world consists of objects, that is, things with individual identities and properties that distinguish them from other objects.Among these objects, various relations hold. Some..Of these relations are functions - relations in which there is only one "value" for a given "input."
It is easy to start listing examples of objects, properties, relations, and functions:
Objects: people, houses, numbers, theories, Ronald McDonald, colors, baseball games, wars, centuries . . .
Relations: brother of, bigger than, inside, part of, has color, occurred after, owns . . .
Properties: red, round, bogus, prime, multistoried...
Functions: father of, best friend, third inning of, one more than ...
Syntax and Symantics
Constant symbols: A, B, C, John ...
Predicate symbols: Round, Brother,...
Function symbols: Cosine. FatherOf, LeftLegOf...
Terms : A term is a logical expression that refers to an object. Atomic sentences
An atomic sentence is formed from a predicate symbol followed by a parenthesized list of terms. For example,
Brother(Richard, John)
Complex sentences : We can use logical connectives to construct more complex sentences.
Example
Brother(Richard,John) A Brother(John, Richard) is true just when John is the brother of
Richard and Richard is the brother of John.
Quantifier : Used to express properties of entire collections of objects, rather than having to enumerate the objects by name.
Universal quantification (V)
Cat(Spot) => Mammal(Spot) A
Cat(Rebecca) =>• Mammal(Rebecca) A
Cat(Felix) => Mammal(Felix) A
Cat(Richard) => Mammal(Richard) A
Cat(John) => Mammal(John) A
Thus, it is true if and only if all these sentences are true, that is, if P is true for all objects x in
the universe. Hence V is called a universal quantifier.
Ground Term
A term with no variables is called a ground term.
Existential quantification
We can make a statement about some object in the universe without naming it, by using an existential quantifier.
Nested quantifiers
We will often want to express more complex sentences using multiple quantifiers.
Equality
We can use the equality symbol to make statements to the effect that two terms refer to the same object. For example,
Father(John) = Henry
Extensions and Notational Variations of first order logic
Higher-order logic
Higher-order logic allows us to quantify over relations and functions as well as over objects. For example, in higher-order logic we,can say that two objects are equal if and only if all properties
applied to them are equivalent:
Vx,y (x = y) & (Vp p(x) O p(y)) ........(V stands "for every")
Using First Order Logic
DomainIn knowledge representation, a domain is a section of the world about which we wish to
express some knowledge.
The kinship domain
we consider is the domain of family relationships, or kinship.
Axioms, definitions, and theorems
Mathematicians write axioms to capture the basic facts about a domain, define other concepts in terms of those basic facts, and then use the axioms and definitions to prove theorems.
The domain of sets
Special notations for sets, lists and arithmetic
A Simple Reflex Agent
The simplest possible kind of agent has rules directly connecting percepts to actions. These rules resemble reflexes or instincts. For example, if the agent sees a glitter, it should do a grab in order to pick up the gold.
Limitations of simple reflex agents
consider climb problem: A pure reflex agent cannot know for sure when to Climb, because neither having the goal nor being in the start is part of the percept; they are things the agent knows by forming a representation of the world.
Reflex agents are also unable to avoid infinite loops
Towards a Goal based agent:
The presence of an explicit goal allows the agent to work out a sequence of actions that will achieve the goal. There are at least three ways to find such a sequence:
- Inference: It is not hard to write axioms that will allow us to ASK the KB for a sequence of actions that is guaranteed to achieve the goal safely.
- Search: We can use a best-first search procedure to find a path to the goal.
- Planning: This involves the use of special-purpose reasoning systems designed to reason about actions.
Building A Knowledge Base
The process of building a knowledge base is called knowledge engineering. The knowledge engineer will usually interview the real experts to become educated about the domain and to elicit the required knowledge, in a process called knowledge acquisition. Representing these very general concepts is sometimes called ontological engineering.
Knowledge engineering versus programming
| Knowledge Enginering | Programming |
| Choosing a Logic | Choosing a programming logic |
| Building a Knowledge base | Writing a programme |
| Implementing the proof theory | Choosing or writing a compiler |
| Inferring New Facts | Running the programme |
What is Knowledge engineering?
The knowledge engineer must understand enough about the domain in question to represent the important objects and relationships, representation language, implementation of the inference procedure.
development of a knowledge base:
1) Decide what to talk about.
2) Decide on a vocabulary of predicates, functions, and constants.
3) Encode general knowledge about the domain.
4) Encode a description of the specific problem instance.
5) Pose queries to the inference procedure and get answers.
THE ELECTRONIC CIRCUITS DOMAIN
based on above 5 steps.
A digital circuit C1 , with three inputs and two outputs, containing two XOR gates, two AND
gates and one OR gate. The inputs are bit values to be added, and the outputs are the sum bit and
the carry bit.
General Ontology
There are two major characteristics of general-purpose ontologies that distinguish them from collections of special-purpose ontologies
1) A general-purpose ontology should be applicable in more or less any special-purpose
domain (with the addition of domain-specific axioms).
2) In any sufficiently demanding domain, different areas of knowledge must be unified because reasoning and problem solving may involve several areas simultaneously.
Discussion of the general-purpose ontology
- Categories: Rather than being an entirely random collection of objects, the world exhibits a good deal of regularity. For example, there are many cases in which several objects have a number of properties in common.
- Measures: Many useful properties such as mass, age, and price relate objects to quantities of particular types, which we call measures.
- Composite objects: It is very common for objects to belong to categories by virtue of their constituent structure. For example, cars have wheels, an engine, and so on, arranged in particular ways;
- Time, Space, and Change: In order to allow for actions and events that have different durations and can occur simultaneously, we enlarge our ontology of time. The basic picture is of a universe that is continuous in both temporal and spatial dimensions. Times, places, and objects will be parts of this universe.
- Events and Processes: Events such as the purchase of a tomato will also become individuals in our ontology. Like tomatoes, they are usually grouped into categories.
- Physical Objects: We are already familiar with the representation of ordinary objects such as AND-gates and wumpuses. As things that are extended in both time and space, physical objects have much in common with events.
- Substances: Whereas objects such as tomatoes are relatively easy to pin down, substance such as tomato juice are a little slippery. Natural language usage seems to provide conflicting intuitions.
- Mental Objects and Beliefs: An agent will often need to reason about its own beliefs, for example, when trying to decide why it thought that anchovies were on sale. It will also need to reason about the beliefs of others, for example, in order to decide whom to ask about the right aisle to find the tomatoes.
Inference rules involving quantifiers
Universal Elimination:For example, from Victim Likes(x,IceCream), we can use the substitution {x/Ben} and infer Likes(Ben, IceCream).
Existential Elimination: For example, from 3x Kill(x, Victim), we can infer Kill(Murderer, Victim), as long as Murderer does not appear elsewhere in the knowledge base.
Existential Introduction: For example, from Likes(Jerry, IceCream) we can infer 3 x Likes(x, IceCream).
Generalized Modus Ponens
Generalized Modus Ponens is an efficient inference :
1 . It takes bigger steps
2. It takes sensible steps using unification algorithm.
3. It makes use of a precompilation step that converts all the sentences in the knowledge base into a canonical form.
Completeness
Godel has put forth his completeness theorem and showed that, for first-order logic, any sentence that is entailed by another set of sentences can be proved from that set.
Dealing with equality
The demodulation rule takes an equality statement x=y and any sentence with a nested term that unifies with x and derives the same sentence with y substituted for the nested term. A more powerful rule called paramodulation deals with the case where we do not know x-y, but we do know,
say, x = y V P(x).
Resolution strategies
Unit preference This strategy prefers to do resolutions where one of the sentences is a single literal (also known as a unit clause).
SET OF SUPPORT It starts by identifying a subset of the sentences called the set of support.
Input resolution In the input resolution strategy, every resolution combines one of the input sentences (from the KB or the query) with some other sentence.
The linear resolution strategy is a slight generalization that allows P and Q to be resolved together if either P is in the original KB or if P is an ancestor of Q in the proof tree. Linear resolution is complete.
Subsumption The subsumption method eliminates all sentences that are subsumed by (i.e., more specific than) an existing sentence in the KB.
The Completenes of resolution
Different Logical Reasoning Systems
Four main categories of logic systems:
- Theorem provers and logic programming languages
- Production systems
- Frame systems and semantic networks
- Description logic systems
Indexing
Table-based indexing
The keys to the table will be predicate symbols, and the value stored under each key will have four components:
- A list of positive literals for that predicate symbol.
- A list of negative literals.
- A list of sentences in which the predicate is in the conclusion.
- A list of sentences in which the predicate is in the premise.
Tree-based indexing
Tree-based indexing is one form of combined indexing, in that it essentially makes a combined key out of the sequence of predicate and argument symbols in the query. The cross-indexing strategy indexes entries in several places, and when faced with a query chooses the most promising place for retrieval.
Logic Programming Systems
Logic programming tries to extend these advantages to all programming tasks. Any computation can be viewed as a process of making explicit the consequences of choosing a particular program for a particular machine and providing particular inputs
Algorithm = Logic + Control
The Prolog language
A program consists of a sequence of sentences, implicitly conjoined. All variables have implicit universal quantification, and variables in different sentences are considered distinct. Only Horn clause sentences are acceptable. Terms can be constant symbols, variables, or functional terms
Queries can include conjunctions, disjunctions, variables, and functional terms. Prolog uses a negation as failure operator.
All syntactically distinct terms are assumed to refer to distinct objects. There is a large set of built-in predicates for arithmetic, input/output, and various system and knowledge base functions.
Implementation
All inferences are done by backward chaining, with depth-first search. The order of search through the conjuncts of an antecedent is strictly left to right, and clauses in the knowledge base are applied in first-to-last order. The occur-check is omitted from the unification routine.
Compilation of logic programs
Pseudocode representing the result of compiling the Member predicate
procedure MEMBER(item, list, continuation)
trail <— GLOBAL-TRAIL-POINTER()
if UNTFY([item I NEW-VARIABLE()], list) then
CALL(continuation)
RESET-TRAIL(trail)
res<— NEW-VARIABLE()
if UNIFY(list, [NEW-VARIABLE rest]) then
MEMBER(item, rest, continuation)
Theorem Provers
Sketch of the OTTER theorem prover. Heuristic control is applied in the selection of the "lightest" clause, and in the FILTER function that eliminates uninteresting clauses from consideration.
procedure OTTER(sos, usable)
inputs: sos, a set of support—clauses defining the
problem (a global variable)
usable, background knowledge potentially relevant
to the problem
repeat
clause <— the lightest member of sos
move clause from sos to usable
PROCESS(INFER(clause, usable), sos)
until sos - [ ] or a refutation has been found
function lNFER(clause, usable) returns clauses
resolve clause with each member of usable
return the resulting clauses after applying FILTER
procedure PROCESS(clauses, sos)
for each clause in clauses do
clause r- SlMPLIFY(clause)
merge identical literals
discard clause if it is a tautology
sos'— [clause I sos]
if clause has no literals then a refutation has
been found
if clause has one literal then look for unit
refutation
end
Extending Prolog
An alternative way to build a theorem prover is to start with a Prolog compiler and extend it to get a sound and complete reasoner for full first-order logic.
Theorem provers as assistants
A theorem prover can also act as a proof-checker, where the proof is given by a human as a
series of fairly large steps;
A Socratic reasoner is a theorem prover whose input dreiving function is incomplete, but which can
always arrive at a solution if asked the right series of questions.
Conflict resolution phase
- No duplication. Do not execute the same rule on the same arguments twice.
- Recency. Prefer rules that refer to recently created working memory elements.
- Specificity. Prefer rules that are more specific.5
- Operation priority. Prefer actions with higher priority, as specified by some ranking.
Description Logics
The principal inference tasks are subsumption :: checking if one category is a subset of another based on their definitions— and classification :: checking if an object belongs to a category. In some description logics, objects are also viewed as categories defined by the object's description and (presumably) containing only one member.
Managing Retractions, Assumptions and Explanations
The process of keeping track of which additional propositions need to be retracted when we retract P is called truth maintenance. A truth maintenance system or TMS is a program that keeps track of dependencies between sentences so that retraction (and some other operations) will be more efficient. The simplest is the justification-based truth maintenance system or JTMS. the most popular type is the ATMS or assumption-based truth maintenance system
