Core Concepts in Artificial Intelligence: Search Algorithms and Knowledge Systems

Heuristic Search Techniques Explained

Heuristic search techniques use intelligent estimations to find solutions efficiently. These methods help in decision-making by prioritizing the most promising paths.

1. Greedy Best-First Search (GBFS)

• Always chooses the next step that appears closest to the goal.
• Ignores the cost already traveled.

Example:

A person finding the exit of a maze by always taking the path that looks shortest.

⚠ Risk: May lead to dead ends.

2. A* Search Algorithm

• Balances actual cost and estimated cost to reach the goal.
• Ensures the shortest and most efficient path.

Example:

Google Maps finds the best route by considering both distance already covered and the remaining estimated distance.

✅ Optimal and efficient.

3. Hill Climbing Algorithm

• Moves towards the highest value (best choice at each step).
• Can get stuck in local maxima (a peak that isn’t the highest).

Example:

A hiker always climbing uphill but stopping at a smaller peak, thinking it’s the highest.

⚠ Risk: Can miss the best solution.

4. Simulated Annealing

• Similar to hill climbing but allows some downward moves to escape local maxima.
• Helps find a better overall solution.

Example:

A mountain climber sometimes goes downhill temporarily to find a higher peak later.

✅ Avoids local maxima but takes longer.

5. Genetic Algorithm

• Inspired by evolution (mutation, selection, crossover).
• Generates multiple solutions and improves them over generations.

Example:

Designing the best-performing car by testing different models and evolving the best ones.

✅ Good for complex optimization problems.

Comparison of Heuristic Search Techniques

AI Agents, PEAS Framework, and Components

Types of Agents in Artificial Intelligence

An agent in AI is an entity that perceives its environment through sensors and acts upon it using actuators.

1. Simple Reflex Agent

• Acts only on current perceptions (ignores history).
• Example: A thermostat turning on heating when the temperature is low.

2. Model-Based Reflex Agent

• Maintains some internal state to track past events.
• Example: A self-driving car remembering previous lane positions.

3. Goal-Based Agent

• Chooses actions to achieve a specific goal.
• Example: A chess-playing AI planning moves to checkmate an opponent.

4. Utility-Based Agent

• Chooses actions based on a utility function (best possible outcome).
• Example: A recommendation system suggesting movies based on user preference.

5. Learning Agent

• Continuously improves its performance by learning from experience.
• Example: A chatbot improving its responses over time.

PEAS Representation for a Driverless Vehicle

PEAS stands for Performance measure, Environment, Actuators, and Sensors.

Difference Between Sensors and Actuators

PEAS Representation for a Smart Washing Machine

Hill Climbing Algorithm: Problems and Prevention

Problems in Hill Climbing and Solutions

1. Local Maxima: Stuck at a suboptimal peak.
   ✅ Solution: Random Restarts (try different starting points).

2. Plateau: Flat area with no improvement.
   ✅ Solution: Random Walk (make random moves).

3. Ridges: Requires sideways moves before going up.
   ✅ Solution: Simulated Annealing (allow occasional downward moves).

Steps in Hill Climbing Algorithm

1. Start with an initial state (e.g., a hiker at the base of a mountain).
2. Evaluate the current state (check elevation).
3. Select the best neighbor (choose the highest step).
4. Move to the new state (climb up if it's better).
5. Repeat until termination (stop at a peak).

Example: Delivery Drone Optimization

A delivery drone finds the shortest route. It moves toward the best estimated path but may get stuck in traffic (local maxima). Random restarts help find a better route.

Propositional Logic vs. Predicate Logic (FOL)

Predicate Logic vs. Propositional Logic

✅ Predicate logic is more expressive as it defines relationships.

Inference Rules in First-Order Logic (FOL)

1. Modus Ponens: If P→Q and P is true, then Q is true.

   • Example: "If it rains, the road is wet." It rains → The road is wet.

2. Modus Tollens: If P→Q and Q is false, then P is false.

   • Example: "If I study, I pass." I didn't pass → I didn't study.

3. Universal Instantiation (UI): From ∀x P(x), infer P(A) for a specific A.

   • Example: "All humans are mortal." → "Socrates is mortal."

4. Universal Generalization (UG): From P(A), infer ∀x P(x).

5. Existential Instantiation (EI): From ∃x P(x), infer P(A) for some A.

6. Existential Generalization (EG): From P(A), infer ∃x P(x).

Knowledge Representation: Instances and Chaining

Representing Instances and the IS-A Relationship

• Instances represent specific objects in a system (e.g., "Sparky is a dog").
• IS-A Relationship shows hierarchy, where one entity is a subtype of another (e.g., "Dog IS-A Animal").

✅ Example:

• General rule: "Dogs are mammals." → Dog IS-A Mammal
• Instance: "Sparky is a dog." → Sparky IS-A Dog
• Inference: Since Sparky IS-A Dog and Dogs ARE Mammals, Sparky is also a Mammal.

Forward vs. Backward Chaining

✅ Example: Diagnosing a disease

• Forward Chaining: From symptoms → Infer possible disease.
• Backward Chaining: Given a disease → Check symptoms to confirm.

Necessity of Knowledge Representation and Unification

Why Knowledge Representation is Necessary

Knowledge representation (KR) is crucial because it allows machines to store, process, and reason about information in a structured way. Without KR, AI systems wouldn’t be able to understand or manipulate knowledge in a human-like manner.

Example:

In a medical expert system, KR allows the system to store facts like "Humans have a heart" and "People with heart disease need treatment." It enables the system to reason about conditions (e.g., if a person has heart disease, they need treatment) and provide helpful advice.

Unification in AI

Unification is a process in logic and AI where two logical expressions are made identical by finding a suitable substitution for their variables. It is fundamental in predicate logic and automated reasoning.

Example:

Given two expressions:

• Likes(John, X)
• Likes(Y, IceCream)

Unification would find that X = IceCream and Y = John to make both expressions identical.

Unification is essential for reasoning, pattern matching, and query processing in AI systems.

Approaches and Properties of Knowledge Representation Systems

Different Approaches to Knowledge Representation

1. Logical Representation

   • Uses formal logic (e.g., propositional or predicate logic).
   • Example: "All dogs are mammals" → ∀x(Dog(x)→Mammal(x)).
   • Difference: Precise, but can be computationally expensive.

2. Semantic Networks

   • Uses nodes (concepts) and edges (relationships).
   • Example: "Dog" IS-A "Mammal".
   • Difference: Visual and intuitive but less expressive than logic.

3. Frames

   • Represents knowledge as structured objects with attributes.
   • Example: "Dog" frame with attributes like "Breed", "Size".
   • Difference: Flexible, but complex with many attributes.

4. Production Rules

   • Uses "If-then" rules.
   • Example: "If temperature > 30°C, turn on AC."
   • Difference: Useful for decision-making, but complex with many rules.

5. Ontologies

   • Formal representation of relationships within a domain.
   • Example: "Dog" related to "Animal" and "Mammal".
   • Difference: Detailed and formal, but complex to build.

Properties of an Efficient Knowledge Representation System

1. Expressiveness: Can represent all necessary knowledge.
2. Efficiency: Allows fast retrieval and reasoning.
3. Reusability: Knowledge can be reused in different contexts.
4. Scalability: Can handle large amounts of knowledge.
5. Modularity: Divides knowledge into manageable parts.
6. Clarity: Easy for humans to understand.
7. Consistency: Avoids contradictory information.

An efficient system should be expressive, efficient, scalable, and consistent.

Detailed Explanation of A* and Hill Climbing Search

1. A* Search Algorithm

A* is a pathfinding algorithm that finds the shortest path by considering both the actual cost so far (g(n)) and the estimated cost to the goal (h(n)). It selects nodes based on:

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

Example:

Imagine navigating a city using a map app. The app calculates the best route based on actual distance traveled and estimated remaining distance.

Key Features:

✅ Guarantees the shortest path
✅ Uses heuristics for efficiency

2. Hill Climbing Algorithm

Hill climbing is an optimization algorithm that moves toward the highest value (best heuristic) without considering the overall path. It continuously selects the best neighbor until no better option is available.

Example:

Climbing a hill in the fog, always choosing the steepest upward path. If you reach a peak that isn't the highest, you're stuck.

Key Features:

⚠ Can get stuck in local maxima
⚠ No backtracking or memory of previous states
✅ Works well for problems like function optimization

Comparison of A* and Hill Climbing