Unit 2: Search and Knowledge Representation

I. Orientation — Intelligent Search and Symbolic Knowledge

Artificial intelligence solves problems by searching through possible states and representing knowledge in forms that support inference. A search algorithm explores alternatives from an initial state toward a goal, while a knowledge-representation scheme encodes facts, relationships, rules, and uncertainty.

• Problem formulation: A search problem specifies an initial state, available actions, a transition model, a goal test, and optionally a path-cost function.
• State space: The set of all states reachable through valid actions; it is commonly modeled as a graph or tree.
• Search node: A data structure containing a state, parent node, generating action, path cost, and depth.
• Solution quality: Algorithms are evaluated by completeness, optimality, time complexity, and space complexity.
• Knowledge and inference: A knowledge base stores statements, while an inference mechanism derives conclusions from them.
• Uncertainty: When facts are incomplete or noisy, probabilistic reasoning assigns degrees of belief instead of only true or false values.

II. Uninformed Search — Exploration Without Domain Guidance

A. Uninformed search: Breadth First Search and Depth First Search

Uninformed search uses only the problem definition and does not estimate how close a state is to the goal.

1. Breadth First Search (BFS) explores nodes in increasing order of depth.
   • Frontier: BFS uses a first-in, first-out queue.
   • Procedure: Remove the shallowest node, test it, and enqueue its unvisited successors.
   • Completeness: It finds a solution if the branching factor (b) is finite and a solution exists at finite depth (d).
   • Optimality: It is optimal when every action has the same cost.
   • Complexity: Time and space are approximately (O(b^d)); storing the broad frontier makes memory its main limitation.
   • Application: It suits shortest-path problems with unit costs, such as finding the fewest moves in a simple puzzle.

BFS(initial):
    frontier = FIFO queue containing initial
    explored = empty set
    while frontier is not empty:
        node = frontier.dequeue()
        if goal(node): return solution(node)
        add node.state to explored
        enqueue every unexplored successor
    return failure

2. Depth First Search (DFS) follows one branch as deeply as possible before backtracking.
   • Frontier: DFS uses a last-in, first-out stack or recursion.
   • Completeness: It is not complete in infinite-depth spaces or spaces containing cycles unless depth and repeated states are controlled.
   • Optimality: It may return a longer or more expensive solution before a better one.
   • Complexity: For maximum depth (m), time is (O(b^m)), but space is only (O(bm)).
   • Application: It is useful for backtracking, maze exploration, and constraint problems where solutions may lie deep in the state space.

III. Informed Search — Exploration Guided by Estimates

A. Informed search: Best First Search, Hill Climbing and A* Search

Informed algorithms use heuristic information to prioritize states that appear more promising.

1. Best First Search expands the node with the most favorable evaluation value.

   • Selection rule: A priority queue orders nodes by an evaluation function (f(n)).
   • Greedy form: Greedy Best First Search uses (f(n)=h(n)), where (h(n)) estimates the remaining cost.
   • Strength: A good heuristic can direct exploration rapidly toward a goal.
   • Limitation: Greedy selection ignores the cost already incurred, so it is generally neither optimal nor guaranteed to perform efficiently.

2. Hill Climbing repeatedly moves from the current state to the locally best neighboring state.

   • Memory use: It retains only the current state and therefore requires little memory.
   • Variants: Simple hill climbing accepts the first improvement; steepest-ascent chooses the greatest improvement.
   • Local maximum: Every neighboring state may be worse even though the global optimum has not been reached.
   • Plateau and ridge: Equal-valued states or narrow improvement paths can halt or misdirect progress.
   • Remedies: Random restarts, limited sideways moves, or stochastic neighbor selection can improve results.
   • Application: It is suitable for optimization tasks such as scheduling and parameter tuning when an approximate solution is acceptable.

3. A* Search balances the cost already paid against the estimated cost remaining.

f(n) = g(n) + h(n)

• Symbols: (g(n)) is the exact path cost from the initial state to node (n); (h(n)) estimates the cheapest cost from (n) to a goal; (f(n)) estimates total solution cost through (n).
• Completeness: A* is complete under standard conditions, including positive step costs and finite branching.
• Optimality: Tree-search A* is optimal with an admissible heuristic; graph-search A* is optimal when the heuristic is consistent.
• Limitation: It may store exponentially many nodes, making memory consumption substantial.

IV. Heuristic Functions — Estimating Distance to a Goal

A. Heuristic functions

A heuristic function (h(n)) estimates the cost of reaching a goal from node (n) using problem-specific knowledge.

• Goal value: Conventionally, (h(n)=0) when (n) is a goal state.
• Admissibility: A heuristic is admissible if it never overestimates the true remaining cost (h^*(n)).

0 <= h(n) <= h*(n)

• Consistency: For every successor (n') reached with step cost (c(n,n')), a consistent heuristic satisfies:

h(n) <= c(n,n') + h(n')

• Dominance: If admissible (h_2(n)\geq h_1(n)) for every node, then (h_2) dominates (h_1) and usually causes A* to expand fewer nodes.
• Construction: Heuristics may come from relaxed problems, abstraction, stored pattern databases, or domain expertise.
• Concrete example: In grid navigation without diagonal movement, Manhattan distance is (h=|x_g-x_n|+|y_g-y_n|). From ((2,3)) to ((7,5)), (h=5+2=7).

V. Algorithm Comparison — Selecting an Appropriate Strategy

A. Comparison and applications of search algorithms

Search algorithms differ in guarantees, resource requirements, and dependence on domain knowledge.

• Fewest-step routing: BFS is appropriate when every edge represents one equal-cost step.
• Memory-limited exploration: DFS is suitable when memory is scarce and solution depth may be large.
• Rapid approximate optimization: Hill climbing fits large configuration spaces where exact optimality is unnecessary.
• Weighted pathfinding: A* is preferred for maps, robotics, and games when a reliable distance estimate exists.
• Effective branching factor: Better heuristics reduce the number of nodes expanded, though computing them may itself require time.

VI. Knowledge Representation — Encoding Information for Reasoning

A. Knowledge representation

Knowledge representation organizes information so an AI system can store it, retrieve it, and infer new conclusions.

• Representational adequacy: The scheme must express relevant objects, properties, events, relations, and constraints.
• Inferential adequacy: It must permit conclusions to be derived from stored facts.
• Inferential efficiency: Its organization should guide reasoning without examining every stored statement.
• Acquisitional efficiency: Knowledge should be addable and modifiable without rebuilding the entire system.
• Types of knowledge:
  • Declarative: Facts such as “Delhi is the capital of India.”
  • Procedural: Methods describing how to perform a task.
  • Heuristic: Experience-based guidance, such as a diagnostic rule.
  • Meta-knowledge: Knowledge about which rules or strategies to use.
• Open-world distinction: In many knowledge systems, absence of a fact does not prove that the fact is false.

VII. Structured Representations — Concepts, Relations, and Defaults

A. Semantic networks and frames

Semantic networks and frames represent structured knowledge through relationships and attribute-value descriptions.

1. Semantic networks model knowledge as labeled graphs.

   • Nodes: Represent entities or concepts, such as Canary and Bird.
   • Edges: Represent relations such as IS-A, PART-OF, or HAS.
   • Inheritance: If Canary IS-A Bird and Bird HAS Wings, the canary inherits wings.
   • Limitation: Informal networks may leave relation meanings and inference rules ambiguous.

2. Frames represent stereotyped objects or situations using named slots.

   • Frame structure: A Bird frame might contain covering = feathers, legs = 2, and canFly = normally true.
   • Defaults: Typical values apply unless overridden; a Penguin frame can inherit from Bird while setting canFly = false.
   • Facets: Slots may specify value types, constraints, default values, or procedures triggered when values change.
   • Application: Frames support object-centered modeling, natural-language understanding, and common-sense reasoning.

VIII. Rule-Based Intelligence — From Conditions to Actions

A. Production systems and expert systems

Production systems apply condition-action rules, while expert systems use such reasoning to emulate specialized human decision-making.

• Production rule: A rule commonly has the form IF condition THEN action/conclusion.
• Working memory: It stores facts describing the current problem state.
• Inference engine: It matches facts against rule conditions and fires applicable rules.
• Conflict resolution: When several rules match, priority, specificity, or recency determines which rule fires.
• Forward chaining: Data-driven reasoning begins with known facts and repeatedly derives new facts.
• Backward chaining: Goal-driven reasoning starts with a proposed conclusion and seeks rules and evidence that support it.
• Expert-system components: A knowledge base, inference engine, user interface, explanation facility, and knowledge-acquisition mechanism form the typical architecture.
• Limitations: Rule acquisition is costly; systems may be brittle outside their encoded domain and require maintenance when expertise changes.

IX. Formal Logic — Representing Facts and Relations

A. Propositional logic and first-order predicate logic

Formal logic represents knowledge through precisely defined statements and truth-preserving inference.

1. Propositional logic treats complete statements as indivisible propositions.

   • Connectives: Negation (\neg), conjunction (\land), disjunction (\lor), implication (\rightarrow), and biconditional (\leftrightarrow) construct compound formulas.
   • Example: From (P\rightarrow Q) and (P), modus ponens derives (Q).
   • Limitation: It cannot directly express objects, properties, relations, or quantified generalizations.

2. First-order predicate logic (FOL) describes objects and relationships within a domain.

   • Predicates: Human(x) expresses a property; Parent(x,y) expresses a relation.
   • Quantifiers: (\forall x) means “for every (x),” while (\exists x) means “there exists an (x).”
   • Example:

forall x (Human(x) -> Mortal(x))
Human(Socrates)
therefore Mortal(Socrates)

• Expressiveness: FOL compactly represents general rules and individual facts.
• Constraint: General FOL inference is computationally demanding and may not terminate for every knowledge base.

X. Probabilistic Reasoning — Updating Beliefs from Evidence

A. Reasoning under uncertainty using Bayes' theorem

Bayes’ theorem updates the probability of a hypothesis after evidence is observed.

P(H | E) = [P(E | H) P(H)] / P(E)

• Symbols: (H) is a hypothesis; (E) is evidence; (P(H)) is the prior; (P(E\mid H)) is the likelihood; (P(H\mid E)) is the posterior; (P(E)) normalizes the result.
• Total evidence probability: For alternatives (H) and (\neg H),

P(E) = P(E | H)P(H) + P(E | not H)P(not H)

• Worked example: Suppose a disease has prior probability (0.01), a test has sensitivity (P(+\mid D)=0.90), and false-positive rate (P(+\mid\neg D)=0.05).

P(D | +) = (0.90 x 0.01) /
           [(0.90 x 0.01) + (0.05 x 0.99)]
         = 0.009 / 0.0585
         ≈ 0.154

• Interpretation: Despite a positive test, the posterior disease probability is about (15.4\%) because the disease is rare.
• Applications: Bayesian reasoning supports diagnosis, classification, forecasting, sensor fusion, and spam filtering.
• Limitation: Reliable results depend on appropriate priors, likelihood estimates, and justified independence assumptions.