Scribd
Upload
4 views

Algorithms, Pseudocode, or Code

The document outlines algorithms and pseudocode for backtracking search, arc consistency, and knowledge-based agents. It details the processes of sensing, reasoning, and acting in agents, along with inference methods such as enumeration and forward chaining. Examples illustrate how these algorithms operate in practice, including the steps taken to derive conclusions from a knowledge base.

Uploaded by

basmala yasser
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views

Algorithms, Pseudocode, or Code

The document outlines algorithms and pseudocode for backtracking search, arc consistency, and knowledge-based agents. It details the processes of sensing, reasoning, and acting in agents, along with inference methods such as enumeration and forward chaining. Examples illustrate how these algorithms operate in practice, including the steps taken to derive conclusions from a knowledge base.

Uploaded by

basmala yasser
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 10

Algorithms, Pseudocode, or Code

Ch 5:

1-BackTracking Pseudocode(slide 13) :

function Backtracking-Search(csp):
return Recursive-Backtrack({}, csp)

function Recursive-Backtrack(assignment, csp):


if all variables are assigned:
return assignment
var = select an unassigned variable
for each value in the variable's domain:
if value is consistent with the assignment:
assign value to var
result = Recursive-Backtrack(assignment, csp)
if result is not failure:
return result
undo the assignment (backtrack)
return failure
2- Arc consistency:

function AC3(constraints):
queue = all arcs (A, B) in the problem # Start with all pairs (A, B) that
have constraints

while queue is not empty:


(A, B) = queue.remove() # Take one arc (A, B) from the queue

if remove_inconsistent_values(A, B): # If A's domain is reduced


for each neighbor C of A (except B): # Check all variables related to A
queue.add((C, A)) # Add these arcs back to the queue

return "Domains reduced and consistent"

function remove_inconsistent_values(A, B):


removed = false
for each value in domain[A]: # Loop through A's possible values
if no value in domain[B] satisfies the constraint (A, B): # If A's value is
invalid
domain[A].remove(value) # Remove it from A's domain
removed = true

return removed # Return whether we removed anything


Ch 7:
1- Simple KB agent:

function KB-Agent(percept) ​ returns an action


static: KB, a knowledge base # A database storing knowledge about the
world
t, a counter, initially 0 # Keeps track of time steps

Tell(KB, Make-Percept-Sentence(percept, t)) # Add the percept to the


KB
action ← Ask(KB, Make-Action-Query(t)) # Query KB for the best
action
Tell(KB, Make-Action-Sentence(action, t)) # Add the chosen action to
the KB
t ← t + 1 # Increment the time step
return action # Return the action to be performed

What Does the Agent Do?

The agent is a loop of sensing, thinking, and acting:

1.​ Sense: Perceives something from the environment (e.g., light, sound).
2.​ Think: Updates its knowledge base with the new information and
queries it for the best action.
3.​ Act: Executes the chosen action and records it for future reasoning.
Example

Scenario:

●​ Agent’s Job: Turn on the light if it’s dark.


●​ Percept: "It’s dark."
●​ Knowledge Base: Contains:
○​ Rule: "If it’s dark, turn on the light."

Steps:

1.​ Perceive:
○​ The agent receives the percept "It’s dark."
○​ Tell(KB, "It’s dark at time t").
2.​ Reason:
○​ The agent queries the KB: "What action should I take at time ttt?"
○​ KB applies the rule and answers: "Turn on the light."
3.​ Act:
○​ The agent records: "I turned on the light at time ttt."
○​ Then performs the action: Turn on the light.
4.​ Repeat:
○​ Next percept, next reasoning, next action.
2-Inference By Enumeration (slide 38):

function TT-Entails(KB, α):


symbols = all symbols in KB and α
return Check-All(KB, α, symbols, {})

function Check-All(KB, α, symbols, model):


if symbols is empty:
if KB is true in the model:
return α is true in the model
else:
return true
else:
P = first symbol in symbols
rest = remaining symbols
return Check-All(KB, α, rest, model + {P: true}) and
Check-All(KB, α, rest, model + {P: false})
Explanation

1. TT-Entails Function

●​ This is the main function. It checks if KB⊨αKB \models αKB⊨α (if the
knowledge base entails the query).
●​ Input:
1.​ KB: The knowledge base.
2.​ α: The query (proposition to check if it follows from the KB).
●​ Steps:
1.​ Extract all the symbols (propositions) from KB and α
2.​ Call the recursive function Check-All to evaluate all possible
models (truth assignments).

2. Check-All Function

●​ This function performs recursive enumeration of all possible truth


assignments (models).
●​ Parameters:
○​ KB: The knowledge base.
○​ α: The query.
○​ symbols: The list of remaining symbols to assign truth values to.
○​ model: The current truth assignment (e.g., {P: true, Q: false}).
Steps in Check-All

1.​ Base Case (symbols is empty):


○​ If there are no more symbols to assign:
■​ Check if KB is true in the current model:
■​ If KB is false, skip this model (return true because we
only care about models where KB is true).
■​ If KB is true, check if α is also true:
■​ If α is false, return false (this model disproves
KB⊨α).
○​ If all models where KB is true also make α true, return true.
2.​ Recursive Case:
○​ Pick the first symbol (P) from symbols.
○​ Assign P=true and recursively evaluate the rest of the symbols.
○​ Assign P=false and recursively assess the rest of the symbols.
○​ Combine results using and: both branches must confirm KB⊨α.
3- Forward Chaining algorithm:

function Forward-Chaining(KB, q):

agenda = facts from KB

inferred = {} # Track which facts have already been processed

count = {rule: number of premises in rule for each rule in KB} # Count
remaining premises for each rule

while agenda: # Keep processing as long as there are facts to check

p = Pop(agenda) # Get the next fact from the agenda

if not inferred.get(p, False): # If the fact has not been processed yet

inferred[p] = True # Mark the fact as processed

for rule in KB where p is a premise: # Check all rules where this fact is a
premise

count[rule] -= 1 # Reduce the number of unsatisfied premises for the rule

if count[rule] == 0: # If all premises for the rule are satisfied

conclusion = result of the rule # Get the conclusion of the rule

if conclusion == q: # If the conclusion matches the query

return True # The query is proven

agenda.append(conclusion) # Add the conclusion to the agenda for


further processing

return False # If no proof is found, return False


Example:

Knowledge Base (KB):

1.​ A∧B→C: "If A and B are true, then C is true."


2.​ C→D: "If C is true, then D is true."
3.​ A=true: "A is true."
4.​ B=true: "B is true."

Query (Q):

●​ Is D true?

Step-by-Step Execution

1.​ Initialization:
○​ agenda = [A, B] (facts from KB).
○​ inferred = {} (nothing processed yet).
○​ count = { (A ∧ B → C): 2, (C → D): 1 }
(premises left to satisfy for each rule).

2.​ Process A:
○​ p=A, remove A from agenda.
○​ Mark A as processed: inferred = {A: true}.
○​ Rule A ∧ B→C: Reduce count from 2 to 1.
3.​ Process B:
○​ p=B, remove B from agenda.
○​ Mark B as processed: inferred = {A: true, B:
true}.
○​ Rule A∧B→C: Reduce count from 1 to 0 (all premises
satisfied).
○​ Infer C: Add C to agenda.

4.​ Process C:
○​ p=C, remove C from agenda.
○​ Mark C as processed: inferred = {A: true, B: true,
C: true}.
○​ Rule C→D Reduce count from 1 to 0 (all premises satisfied).
○​ Infer D: Add D to agenda.

5.​ Process D:
○​ p=D, remove D from agenda.
○​ D=q: The query is proven true.

Final Result:

●​ The query (D) is true.

Key Steps Summary

1.​ Start with known facts (A, B).


2.​ Use rules to infer new facts (C, then D).
3.​ Stop when the query (q=D) is proven.

You might also like