Unit 2: Search and Knowledge Representation - Subjective Questions

Uninformed search explores a state space without using domain-specific information about the location of the goal. It relies only on the initial state, successor function, goal test, and path cost.

Working of BFS:

• BFS expands nodes level by level, beginning with the initial state.
• It stores generated nodes in a FIFO queue.
• The initial node is inserted into the queue and marked as visited.
• The node at the front is removed and tested for the goal.
• Its unvisited successors are added to the rear of the queue.
• This process continues until a goal is found or the queue becomes empty.

Properties:

• Complete: Yes, if the branching factor is finite.
• Optimal: Yes, when every step has the same cost.
• Time complexity: .
• Space complexity: .

Here, is the branching factor and is the depth of the shallowest goal. BFS is useful when the goal is expected to be close to the initial state.

Depth First Search (DFS) explores one branch of a search tree as deeply as possible before backtracking to explore another branch.

Algorithm:

• Place the initial state on a LIFO stack.
• Remove the top node and perform the goal test.
• If it is not the goal, generate its successors.
• Add the unvisited successors to the top of the stack.
• Continue until a goal is found or the stack becomes empty.

DFS can also be implemented recursively.

Advantages:

• Requires relatively little memory.
• Can reach deep solutions without expanding all shallower nodes.
• Is simple to implement using recursion or a stack.

Limitations:

• Is not complete in infinite-depth spaces or in the presence of uncontrolled cycles.
• Is not generally optimal because the first solution found may be expensive.
• May spend excessive time exploring an irrelevant deep branch.

For maximum depth and branching factor , its time complexity is and its space complexity is .

BFS and DFS are both uninformed search algorithms, but they differ in their exploration strategies.

• Exploration order: BFS explores the search tree level by level, whereas DFS explores one branch to its maximum depth before backtracking.
• Data structure: BFS uses a FIFO queue, whereas DFS uses a LIFO stack or recursion.
• Completeness: BFS is complete for a finite branching factor. DFS may fail in infinite-depth spaces or when cycles are not controlled.
• Optimality: BFS is optimal when all step costs are equal. DFS is not generally optimal.
• Time complexity: BFS requires , while DFS requires .
• Space complexity: BFS requires , while DFS requires only .
• Suitable applications: BFS is suitable for shortest-path problems with equal costs. DFS is useful for backtracking, maze traversal, topological exploration, and memory-constrained search.

Thus, BFS offers stronger solution guarantees, while DFS generally has a lower memory requirement.

Best First Search is an informed search strategy that expands the most promising node according to an evaluation function.

In Greedy Best First Search, the evaluation function is:

where estimates the cost from node to a goal.

Procedure:

• Insert the initial node into an OPEN priority queue.
• Select the node with the smallest evaluation value.
• If the selected node is a goal, return its solution path.
• Otherwise, generate its successors and calculate their heuristic values.
• Insert or update the successors in OPEN.
• Move the expanded node to a CLOSED set and repeat.

Characteristics:

• It often reaches a goal faster than uninformed search when the heuristic is useful.
• It focuses on estimated closeness to the goal rather than the cost already incurred.
• It is not generally optimal because a node that appears close to the goal may lie on an expensive path.
• Its completeness depends on the search space, repeated-state handling, and implementation.

For example, route finding may use straight-line distance to the destination as .

Hill Climbing is a local search technique that repeatedly moves from the current state to a neighboring state with a better heuristic value. It retains only the current state rather than an entire search tree.

Basic procedure:

• Start with an initial state.
• Evaluate the neighboring states.
• Select a neighbor that improves the evaluation value.
• Replace the current state with that neighbor.
• Stop when the goal is reached or no better neighbor exists.

Failure conditions:

• Local maximum: The current state is better than all nearby states but is not the global optimum.
• Plateau: Many neighboring states have the same value, giving no clear direction.
• Ridge: The best path requires a sequence of moves that individual local moves do not identify.
• Shoulder: A flat region may contain an improving path, but ordinary hill climbing stops too early.

Possible remedies:

• Random-restart hill climbing
• Allowing limited sideways moves
• Stochastic hill climbing
• Simulated annealing

Hill climbing uses very little memory, but it is neither complete nor guaranteed to find a globally optimal solution.

A* is an informed search algorithm that evaluates a node using both the path cost already incurred and an estimate of the remaining cost:

where:

• is the actual cost from the initial state to node .
• is the estimated cost from node to a goal.
• is the estimated total solution cost through .

Algorithm:

• Store the initial node in an OPEN priority queue ordered by .
• Remove the node with the smallest .
• Return the path if it is a goal.
• Otherwise, generate its successors and compute their , , and values.
• Add new states to OPEN or update a state when a less expensive path is found.
• Use a CLOSED set to manage expanded states.

Conditions:

• A* tree search is optimal when is admissible, meaning .
• A* graph search is optimal with the usual closed-node implementation when the heuristic is consistent.
• A* is complete when the branching factor is finite and every step cost is at least some positive constant.

Its main limitation is its potentially exponential memory consumption.

A heuristic function estimates the cost of the least expensive path from a state to a goal. It uses problem-specific knowledge to guide informed search.

Admissibility:
A heuristic is admissible if it never overestimates the true remaining cost:

where is the actual optimal cost from to a goal. An admissible heuristic is optimistic.

Consistency:
A heuristic is consistent if, for every transition from to with cost ,

and for a goal . Consistency is a triangle-inequality condition and implies admissibility.

Dominance:
If two admissible heuristics and satisfy

for every node, then dominates . It is usually more informed and causes A* to expand no more nodes than , assuming identical tie-breaking.

Good heuristics are often derived from relaxed versions of the original problem.

Comparison of search algorithms:

• BFS: Expands the shallowest node first. It is complete for a finite branching factor and optimal for equal step costs, but it requires exponential memory.
• DFS: Expands the deepest node first. It uses relatively little memory, but it is not generally complete in infinite spaces and is not optimal.
• Greedy Best First Search: Expands the node with the smallest . It may be fast with a good heuristic, but it ignores the cost already incurred and is not generally optimal.
• Hill Climbing: Moves to a locally better neighboring state and stores only the current state. Its memory use is very low, but it can become trapped at local maxima, plateaus, or ridges.
• *A Search:** Expands the node with the smallest . It is complete under standard positive-cost assumptions and optimal with a suitable heuristic, but it can consume large amounts of memory.

Selection guidelines:

• Use BFS for shallow, unweighted shortest paths.
• Use DFS for memory-limited traversal and backtracking.
• Use Greedy Best First Search when speed is more important than optimality.
• Use Hill Climbing for large optimization spaces where paths are unimportant.
• Use A* when an optimal path is required and a reliable heuristic is available.

Search algorithms are applied according to the structure of the problem and the quality of available domain knowledge.

Applications of uninformed search:

• BFS finds minimum-hop paths in unweighted networks.
• BFS supports social-network degree calculations and web crawling by levels.
• DFS is used in maze traversal and puzzle exploration.
• DFS supports cycle detection, topological sorting, and connected-component discovery.
• Depth-oriented search is useful in backtracking problems such as constraint satisfaction.

Applications of informed search:

• A* is used in robot navigation, map routing, and video-game pathfinding.
• Greedy Best First Search can quickly locate approximate routes or promising states.
• Hill Climbing is applied to scheduling, layout optimization, feature selection, and parameter tuning.
• Heuristic search is widely used in planning and game-playing systems.

Uninformed methods are appropriate when no useful estimate is available. Informed methods can reduce the number of expanded states by using domain knowledge, although their performance depends strongly on heuristic quality.

Knowledge representation (KR) is the process of encoding facts, concepts, relationships, rules, and constraints in a form that an artificial intelligence system can store, interpret, and use for reasoning.

An effective KR scheme should provide:

• Representational adequacy: It must represent all knowledge required by the application.
• Inferential adequacy: It must support the derivation of new knowledge from stored knowledge.
• Inferential efficiency: It should organize knowledge so useful conclusions can be reached efficiently.
• Acquisitional efficiency: It should allow knowledge to be added, modified, and maintained easily.
• Clarity: Its symbols and relationships should have well-defined meanings.
• Consistency: It should help detect or manage conflicting facts and rules.
• Modularity: Changes in one area should have limited impact on unrelated knowledge.
• Handling of uncertainty: Real systems may need to represent incomplete or probabilistic information.

Common KR methods include logic, semantic networks, frames, production rules, ontologies, and probabilistic models.

A semantic network represents knowledge as a labeled graph. Nodes represent objects, concepts, or values, while directed edges represent relationships between them.

Consider the following knowledge:

• A canary is a bird.
• A bird is an animal.
• Birds have wings.
• Canary-1 is a canary.
• Canary-1 has the color yellow.

This can be represented using nodes such as Animal, Bird, Canary, and Canary-1, connected by relations such as is-a, instance-of, has-part, and has-color.

Inheritance:

• Because Canary is linked to Bird by an is-a relation, it inherits general properties of Bird.
• Canary-1 inherits the properties of Canary and Bird.
• Therefore, the system can infer that Canary-1 has wings and is an animal even when these facts are not stored directly.
• A specific property can override an inherited default when exceptions are supported.

Advantages: Semantic networks are intuitive, visual, and effective for representing relationships.

Limitations: Their edge meanings may be informal, and inheritance conflicts or exceptions require carefully defined semantics.

A frame is a structured representation of a stereotyped object, concept, event, or situation. It resembles a record containing named attributes called slots.

For example, a frame for Vehicle may contain:

• wheels: default value 4
• power-source: engine
• purpose: transportation
• maximum-speed: a numerical filler

A Car frame can inherit from Vehicle and add slots such as number of doors and fuel type.

Key concepts:

• Slots: Named attributes or relations, such as color, owner, or number of wheels.
• Fillers: Values assigned to slots, such as red or 4.
• Default values: Assumed values used when no specific value is supplied.
• Inheritance: A specialized frame receives slots and default values from a more general frame.
• Facets: Additional information about a slot, such as its allowed values or method for computing it.
• Procedural attachments: Procedures triggered when a slot is read or changed.

Frames organize related information efficiently, but complex multiple inheritance and exceptions can create conflicts that require explicit resolution rules.

Semantic networks and frames both represent structured knowledge and support inheritance, but they emphasize different aspects.

• Basic structure: A semantic network is a graph of nodes and labeled links. A frame is a structured collection of slots and values.
• Primary strength: Semantic networks clearly display relationships among concepts. Frames provide detailed descriptions of individual concepts or situations.
• Inheritance: Semantic networks use links such as is-a and instance-of. Frames inherit slots and defaults from parent frames.
• Properties: In semantic networks, properties are often represented as links to other nodes. In frames, properties are stored directly in slots.
• Procedural knowledge: Traditional semantic networks mainly represent declarative relationships. Frames may include procedural attachments associated with slots.
• Visualization: Semantic networks are easier to visualize as graphs. Frames resemble records or object-oriented classes.
• Limitations: Semantic networks may lack precise formal semantics. Frames can become complex when dealing with multiple inheritance and many exceptions.

The two approaches can be combined: frames can represent concepts, while semantic links connect those frames into a broader knowledge graph.

A production system represents problem-solving knowledge as condition-action rules, commonly written as:

IF condition THEN action

Its main components are:

• Rule base: A collection of production rules.
• Working memory: Facts that describe the current problem state.
• Inference engine: Matches rules against facts and executes selected rules.
• Control strategy: Determines which applicable rule should fire.

Recognize-act cycle:

1. Match: Compare rule conditions with the facts in working memory.
2. Conflict set formation: Collect all rules whose conditions are satisfied.
3. Conflict resolution: Select one rule using priority, specificity, recency, or another policy.
4. Act: Fire the selected rule and modify working memory or produce an output.
5. Repeat until a goal is reached or no rule is applicable.

Production systems are modular because rules can often be added independently. However, a large rule base may produce matching inefficiency, conflicting rules, and difficult maintenance. Production rules form the reasoning foundation of many expert systems.

An expert system is an AI program that uses specialized knowledge and reasoning procedures to solve problems in a restricted domain.

Main components:

• Knowledge base: Stores domain facts, rules, and heuristics.
• Inference engine: Applies rules to facts to derive conclusions.
• Working memory: Holds case-specific facts and intermediate results.
• User interface: Supports interaction between the user and the system.
• Explanation facility: Explains how or why a conclusion was reached.
• Knowledge-acquisition facility: Helps experts or engineers update the knowledge base.

Forward chaining:

• Is data-driven.
• Begins with known facts.
• Fires applicable rules to derive new facts.
• Continues until a goal is reached or no more rules apply.
• Is suitable when all possible consequences of available data are required.

Backward chaining:

• Is goal-driven.
• Begins with a hypothesis or goal.
• Searches for rules that could establish that goal.
• Treats their conditions as subgoals.
• Is suitable for diagnosis and consultation where a specific conclusion must be tested.

Many practical systems combine both forms of reasoning.

Propositional logic represents knowledge using propositions that are either true or false.

Syntax:

• Atomic propositions are symbols such as , , and .
• Complex formulas are formed using logical connectives and parentheses.

Major connectives:

• Negation: means not .
• Conjunction: is true only when both propositions are true.
• Disjunction: is true when at least one proposition is true.
• Implication: is false only when is true and is false.
• Biconditional: is true when and have the same truth value.

Semantics assigns truth values to atomic propositions and determines the values of compound formulas using truth tables.

For example, let mean it is raining and mean the road is wet. The rule expresses that rain implies a wet road. If and are true, follows by modus ponens.

Propositional logic is precise and supports automated inference, but it cannot directly represent objects, variables, or quantified relationships.

First-order predicate logic (FOL) extends propositional logic by representing objects, their properties, and relationships among objects.

Elements of FOL:

• Constants: Particular objects, such as .
• Variables: Symbols such as and .
• Predicates: Properties or relations, such as or .
• Functions: Mappings from objects to objects.
• Quantifiers: means for all, and means there exists.
• Logical connectives: , , , , and .

Translations:

• All humans are mortal:
  
• Socrates is a human:
  
• Therefore, Socrates is mortal:
  
• Some student studies AI:
  
• Every student has a teacher:
  

FOL is more expressive than propositional logic, although inference in FOL is computationally more difficult.

Propositional logic and first-order predicate logic differ as follows:

• Basic unit: Propositional logic uses complete propositions. FOL uses predicates applied to terms.
• Internal structure: A proposition is treated as an indivisible symbol. FOL can represent objects, properties, functions, and relations.
• Variables: Propositional logic does not use object variables. FOL uses variables such as and .
• Quantification: Propositional logic has no quantifiers. FOL uses universal and existential quantifiers.
• Expressiveness: Propositional logic can state . FOL can express the general rule .
• Compactness: FOL can represent a general relationship in one formula, whereas propositional logic may require a separate formula for each object.
• Inference complexity: Propositional reasoning is usually simpler and decidable. General FOL validity is only semidecidable and may require unification and substitution.

Propositional logic is suitable for finite facts with no internal relational structure. FOL is preferable when a domain contains many objects and general relationships.

For events and , where , conditional probability gives:

Similarly,

Therefore,

Substituting this expression into the first equation gives Bayes' theorem:

Interpretation:

• is the prior probability, representing belief in hypothesis before observing evidence.
• is the likelihood, representing how probable evidence is if is true.
• is the evidence or marginal likelihood, which normalizes the result.
• is the posterior probability, representing the updated belief after observing .

If are mutually exclusive and exhaustive hypotheses, then:

Bayes' theorem provides a principled method for updating beliefs when uncertain evidence becomes available.

Let denote having the disease and denote a positive test.

Given:

• Prevalence:
• No disease:
• Sensitivity:
• False-positive rate:

By Bayes' theorem:

Substituting the values:

Therefore, the probability that a person who tests positive actually has the disease is approximately:

Although the test has high sensitivity, the posterior probability is relatively low because the disease is rare and false positives among healthy people are comparatively numerous. This illustrates the importance of the prior probability in reasoning under uncertainty.