UNIT 1: FOUNDATIONS OF ARTIFICIAL INTELLIGENCE & PROBLEM-SOLVING

I. INTRODUCTION TO AI & INTELLIGENT AGENTS

Definition and Goals of AI

AI is the science and engineering of creating intelligent machines, particularly intelligent computer programs. The four main approaches/definitions are:

1. Acting Humanly: The Turing Test approach; machine behavior is indistinguishable from human.

2. Thinking Humanly: Modeling human cognition; requires understanding human thought processes.

3. Thinking Rationally: Studying the principles that make "thinking" correct, i.e., logical reasoning.

4. Acting Rationally: The modern, engineering-focused goal. An agent acts to achieve the best outcome or best expected outcome.

Exam Tip: Current AI systems (like self-driving cars, recommendation systems) primarily align with "acting rationally"—making decisions that maximize utility based on available information, not necessarily mimicking human thought.

Characteristics of Intelligent Systems

Key traits enabling problem-solving:

• Reasoning & Inference: Drawing logical conclusions.

• Learning: Adapting from experience/data.

• Perception: Interpreting sensory input.

• Natural Language Understanding: Processing human language.

• Planning & Decision Making: Sequencing actions to achieve goals.

Intelligent Agents

An agent perceives its environment through sensors and acts through actuators.

• Agent Function: Maps a sequence of perceptions (percept history) to an action.

• Agent Program: Implements the agent function.

Types of Agents

Interaction with Environment

• Peephole (Partial Observability): Agent sees only a limited part of the environment at each step (e.g., a robot with a camera).

• Environment-Driven: The environment itself provides the next state after an action (most common in search problems).

Problem Characteristics for AI Suitability

A problem is suitable for AI techniques if it is:

1. Large state space: Too vast for exhaustive enumeration by humans.

2. Well-defined goal & operators: Clear initial state, goal test, and set of actions.

3. Requires heuristic search: No efficient algorithmic solution exists (NP-hard).

4. Benefits from domain knowledge: Can be improved with heuristics or rules.

Example Problem: Tic-Tac-Toe

• Representation as Search:

  • State: 3x3 grid with X, O, or blank.

  • Initial State: Empty grid.

  • Operators: Place X or O in an empty cell.

  • Goal Test: 3 X's/O's in a row, column, or diagonal.

  • Path Cost: Number of moves (or 1 per move).

• Significance: A simple adversarial search problem that perfectly illustrates core AI techniques: game trees, minimax, alpha-beta pruning, and heuristic evaluation functions. Its state space is small enough to solve completely but complex enough to teach fundamental concepts.

II. PROBLEM-SOLVING BY SEARCH

A. Uninformed (Blind) Search

No additional information about the goal beyond the problem definition.

Common Pitfall: DFS is not complete in infinite state spaces or very deep trees. BFS is often impractical for large $b$ and $d$ due to exponential space.

B. Informed (Heuristic) Search

Uses a heuristic function $h(n)$ estimating cost from node $n$ to goal.

Best-First Search

• General Framework: Selects the node with the best evaluation according to a problem-specific evaluation function $f(n)$.

• Comparison: More directed than uninformed search; can be optimal or not depending on $f(n)$. Greedy Best-First uses $$\displaystyle f(n)=h(n) $$ only (incomplete, not optimal).

A* Search Algorithm

The most popular optimal informed search.

• Evaluation Function:

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

*   $g(n)$: Actual cost from start to node $n$.

*   $h(n)$: **Heuristic** estimate from $n$ to goal.

• Properties:

  • Optimal: Always finds the least-cost path if $h(n)$ is admissible and consistent.

  • Admissible: $h(n)$ never overestimates the true cost to goal ($$\displaystyle h(n) \leq h^*(n) $$).

  • Consistent (Monotonic): For every node $n$ and successor $n'$, $h(n) \leq c(n,n') + h(n')$. Implies admissibility.

  • Complete & Optimal: With finite branching and step costs, and an admissible $h(n)$.

• Design of Admissible Heuristics: Often derived by relaxing the problem (removing constraints) to make it easier and solvable optimally (e.g., Manhattan distance for 8-puzzle, straight-line distance for map routing).

• Importance: Balances exploration ($g(n)$) and guidance ($h(n)$). Forms the basis for many real-world pathfinding and planning systems.

AO* Algorithm

• For AND/OR Graphs: Used when a problem can be decomposed into subproblems that must all be solved (AND branches) or where any one solution suffices (OR branches).

• Comparison with A:*

  | Feature | A* | AO* | | :--- | :--- | :--- | | Graph Type | OR graphs (standard state-space). | AND/OR graphs. | | Solution | Single path from start to goal. | Solution graph (tree) satisfying all AND arcs. | | Optimality | Optimal path cost. | Optimal solution graph (minimizes sum of costs along all branches). | | Complexity | Generally lower. | Higher due to handling AND branches. |

• Application: Task planning, theorem proving, parsing (where multiple subgoals must be met).

C. Local Search and Optimization

Used for optimization problems where the path to the solution doesn't matter, only the solution state itself.

Hill Climbing

• Algorithm: Iteratively move to a neighbor state with a better heuristic value.

• Variants:

  • Steepest-Ascent: Evaluate all neighbors, move to best.

  • First-Choice: Move to first better neighbor.

• Problems:

  1. Local Maxima: Peak higher than neighbors but not global maximum.

  2. Plateaus: Flat area where all neighbors have same value.

  3. Ridges: Sequence of local maxima.

• Mitigation: Use random restarts or switch to more advanced methods.

Other Local Search Methods (Brief)

• Simulated Annealing: Escapes local maxima by sometimes accepting worse moves with a probability that decreases over "temperature".

• Genetic Algorithms: Population-based search using selection, crossover, mutation.

D. Adversarial Search (Game Playing)

For two-player, zero-sum games (one's gain is other's loss).

Minimax Algorithm

• Procedure: Assumes opponent plays optimally. Maximizing player (MAX) chooses move leading to state with maximum utility value; minimizing player (MIN) chooses minimum.

• Game Tree: Nodes = game states, edges = moves. Terminal nodes have utility values (win=+1, loss=-1, draw=0).

• Application: Chess, Tic-Tac-Toe, Checkers.

• Advantages: Theoretically optimal against optimal opponent.

• Limitations: Exponential time $$\displaystyle O(b^m) $$; requires full game tree to depth of terminal states.

Alpha-Beta Pruning

• Optimization: Eliminates branches that cannot affect the final decision.

• Key Values:

  • $\alpha$: Best (highest) value that MAX can guarantee at that point or above.

  • $\beta$: Best (lowest) value that MIN can guarantee at that point or below.

• Cut-off Conditions:

  • If $\alpha \geq \beta$ at any node, prune remaining siblings (no need to explore).

• Impact: Can reduce effective branching factor from $b$ to roughly $\sqrt{b}$, making deeper search possible. Perfect ordering can yield $$\displaystyle O(\sqrt{b^m}) $$ complexity.

• Variations for Optimization: Iterative Deepening (used with alpha-beta), Transposition Tables (memoization), Move Ordering (search best moves first to maximize pruning).

E. Constraint Satisfaction Problems (CSP)

Formalism for problems where the goal is to find assignments to variables satisfying constraints.

• Formulation:

  • Variables: $$\displaystyle X = \{X_1, X_2, ..., X_n\} $$

  • Domains: $$\displaystyle D_i $$ = set of possible values for $$\displaystyle X_i $$.

  • Constraints: Relations among subsets of variables restricting allowable combinations (e.g., $$\displaystyle X_i \neq X_j $$, $$\displaystyle X_i + X_j < 5 $$).

• Example: Map coloring (variables=regions, domains=colors, constraints=adjacent regions ≠).

• Local Search for CSP:

  • Min-Conflicts Heuristic: For a randomly chosen conflicted variable, assign a value that minimizes the number of conflicts with other variables.

  • Highly effective for large-scale CSPs (e.g., scheduling).

III. KNOWLEDGE REPRESENTATION

A. Logical Representation

Propositional Logic

• Syntax: Atomic propositions ($P, Q, R$) combined with logical connectives: $\neg$ (not), $\land$ (and), $\lor$ (or), $$\displaystyle \rightarrow $$ (implies), $$\displaystyle \leftrightarrow $$ (iff).

• Semantics: Truth values assigned to propositions; truth of complex formulas determined by truth tables.

• Limitation: Cannot represent objects, relations, or quantifiers. Very limited expressiveness (e.g., cannot say "All men are mortal").

Predicate Logic (First-Order Logic - FOL)

• Syntax Elements:

  • Predicates: $P(x)$, $Loves(John, Mary)$ — represent relations/attributes.

  • Variables: $x, y, z$.

  • Constants: $John, 5, Siva$.

  • Functions: $mother(x)$, $plus(x,y)$.

  • Quantifiers: $\forall x$ (for all x), $\exists x$ (there exists x).

  • Equality: $$\displaystyle = $$.

• Translation Example:

  • "All courses in CSE are easy." → $$\displaystyle \forall x (CSE(x) \rightarrow Easy(x)) $$

  • "Steve likes some easy course." → $\exists x (Course(x) \land Easy(x) \land Likes(Steve, x))$

• Conversion to Clausal Form (CNF): Standard form for resolution.

  1. Eliminate $$\displaystyle \rightarrow, \leftrightarrow $$.

  2. Move $\neg$ inwards (Negation Normal Form).

  3. Standardize variables apart.

  4. Move quantifiers out (Skolemization for $\exists$).

  5. Distribute $\lor$ over $\land$.

  • Result: Conjunction of disjunctions (clauses). Each clause is a set of literals.

• Resolution Technique:

  • Rule: From $(A \lor L)$ and $(\neg L \lor B)$, infer $(A \lor B)$.

  • Refutation: To prove goal $G$, add $\neg G$ to knowledge base (KB). If resolution derives the empty clause $\Box$, then $G$ is entailed by KB. Sound and complete for FOL.

  • Example Proof: Given KB: $$\displaystyle \forall x (Man(x) \rightarrow Mortal(x)) $$, $Man(Socrates)$. Prove $Mortal(Socrates)$.

    1. Convert to clauses: $\{\neg Man(x) \lor Mortal(x)\}$, $\{Man(Socrates)\}$.

    2. Resolve with $$\displaystyle x = Socrates $$: $\{\neg Man(Socrates) \lor Mortal(Socrates)\}$ and $\{Man(Socrates)\}$ → $\{Mortal(Socrates)\}$.

    3. Goal $Mortal(Socrates)$ is a unit clause derived. QED.

Comparison: Propositional vs. Predicate Logic

B. Structured Representations

Alternatives to logic for organizing knowledge.

Semantic Networks

• Structure: Nodes represent objects/concepts; edges represent directed relationships (e.g., is-a, has-part).

• Reasoning: Via inheritance (subclass inherits properties from superclass) and path following.

• Example: [Bird] --is-a--> [Animal] implies a Sparrow (instance of Bird) inherits property breathes from Animal.

• Limitation: No standard syntax for complex constraints; reasoning can be ambiguous.

Frames

• Structure: A frame (template) for a stereotypical situation/object.

  • Frame Name: Student

  • Slots: Name, Age, Major, GPA

  • Facets: Value, Default, If-Added, If-Needed (procedural attachment).

• Use: Represents default knowledge and typical attributes. Inheritance works like semantic networks.

• Limitations: Difficult to represent dynamic changes, complex constraints, or procedural knowledge. Often enhanced with rules.

Scripts and Schemas

• Script: A temporal sequence of events in a stereotypical situation (e.g., Restaurant Script: Enter → Wait to be seated → Order → Eat → Pay → Exit).

• Schema: Broader cognitive structure for organizing knowledge about a concept or event (more abstract than a script).

• Application in NLP/Virtual Assistants: Understanding narratives, predicting next actions, filling in missing details (slot-filling).

• Difference: Scripts are a type of schema focused on event sequences.

Conceptual Dependency (CD)

• Goal: Represent meaning of natural language sentences in a language-independent primitive form.

• Primitives: A small set of universal conceptual primitives (e.g., ATRANS (transfer of abstract relationship), PTRANS (physical transfer), MOVE, INGEST).

• Relations: Actor, Object, Direction, Instrument.

• Comparison with Semantic Networks: CD is more formal and procedural, focusing on actions. Semantic networks are better for static relationships and taxonomy.

C. Probabilistic Reasoning

Bayes' Theorem

$$P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$$

• Statement: The probability of hypothesis $A$ given evidence $B$ is proportional to the likelihood $P(B|A)$ and prior probability $P(A)$.

• Significance: The cornerstone of Bayesian networks and probabilistic reasoning under uncertainty. Allows updating beliefs with new evidence.

• Comparison: Unlike pure logic (true/false), Bayes handles degrees of belief and combines prior knowledge with observed data. More robust to incomplete information than deterministic rule-based systems.

IV. REASONING METHODS

Forward Chaining (Data-Driven)

• Process:

  1. Match: Find all rules whose antecedents (IF part) are satisfied by current facts in working memory.

  2. Conflict Resolution: Choose one rule to fire (e.g., most specific, newest).

  3. Act: Execute rule's consequent (THEN part), add new facts to working memory. Repeat until goal is reached or no rules fire.

• Suitability: Monitoring & control systems, where data arrives continuously (e.g., fault diagnosis from sensor readings). Can be inefficient if goal is specific but data is vast.

Backward Chaining (Goal-Driven)

• Process:

  1. Start with goal to prove.

  2. Find rules whose consequent matches the goal.

  3. For each such rule, set its antecedents as new subgoals.

  4. Recursively try to prove subgoals (using facts or further rules).

  5. If all subgoals for a rule are proven, the original goal is proven.

• Suitability: Diagnostic & classification systems (e.g., medical diagnosis, MYCIN). Efficient when goal is known and the rule base is large, as it avoids considering irrelevant facts.

Comparison: Forward vs. Backward Chaining

Monotonic vs. Non-Monotonic Reasoning

• Monotonic Reasoning: Adding new knowledge never retracts old conclusions. If $KB \vdash \alpha$, then $KB \cup KB' \vdash \alpha$. Classical logic is monotonic.

• Non-Monotonic Reasoning: Adding new knowledge can retract old conclusions. Necessary for default reasoning and common sense.

  • Example (Default): "Birds typically fly." (Penguins are birds but don't fly). Initially infer flies(Tweety) from bird(Tweety). Upon learning penguin(Tweety), retract flies(Tweety).

  • Essential in: Diagnosis (new symptoms change hypothesis), planning (new information invalidates old plan), commonsense knowledge bases.

Role of Control Knowledge

• Definition: Knowledge that guides the search and inference process itself (e.g., "which rule to fire next?", "which node to expand?").

• How it Aids Problem-Solving:

  1. Reduces Search Space: Good control (e.g., heuristic $h(n)$ in A*, move ordering in alpha-beta) prunes irrelevant paths.

  2. Improves Efficiency: Chooses most promising actions first (e.g., conflict resolution strategies in forward chaining).

  3. Enables Learning: Meta-knowledge about how to solve problems can be learned and applied to new problems.

• In Expert Systems: The inference engine's strategy (forward/backward) and rule ordering are forms of control knowledge.

V. EXPERT SYSTEMS

Definition and Characteristics

An Expert System (ES) is a computer program that emulates the problem-solving ability of a human expert in a narrow, specific domain.

• Distinguishing Features from Conventional Programs:

  • High performance in a limited domain.

  • High cost of development (knowledge acquisition).

  • Separation of knowledge (KB) from inference (IE).

  • Ability to explain reasoning (explanation facility).

  • Handling uncertainty (often via certainty factors or probabilities).

Components of an Expert System

1. Knowledge Base (KB): Contains domain-specific facts and rules (e.g., IF symptom= fever AND rash THEN disease= measles [CF=0.9]).

2. Inference Engine (IE): The "reasoning processor." Applies rules to facts to derive new conclusions. Uses forward/backward chaining.

3. User Interface: Allows user to input facts and receive conclusions/advice.

4. Explanation Facility: Answers "how?" and "why?" questions about the reasoning process (crucial for user trust).

5. Knowledge Acquisition Module: Tools for experts/knowledge engineers to build/update the KB (often the bottleneck).

Inference Engines: Forward vs. Backward Chaining (Detailed)

Benefits of Expert Systems

• Consistency: Never tires, always applies rules uniformly.

• Documentation: KB is explicit and can be reviewed.

• Reproducibility: Same input yields same output.

• Availability: Can operate 24/7, in hazardous environments.

• Cost-Effective in Long Run: After high initial development cost.

Limitations and Challenges

1. Knowledge Acquisition Bottleneck: Difficulty and cost of extracting, structuring, and validating expert knowledge.

2. Brittleness: Fails on problems outside its narrow domain or with slight variations.

3. Lack of Common Sense: Cannot make reasonable assumptions about everyday world.

4. Explanation Adequacy: Explanations can be too technical or lengthy.

5. Maintenance & Updating: KB can become obsolete; updating is difficult.

6. No Learning: Traditional ES do not learn from experience (unlike ML).

Design and Development Considerations

• Ensuring Knowledge Currency:

  • Knowledge Engineer: Mediates between expert and system.

  • Modular KB Design: Easier to update specific rules/frames.

  • Explanation Facility: Helps experts verify and correct reasoning.

  • Integration with Databases: Link to up-to-date external data sources.

  • Periodic Review & Validation: By domain experts.

• Critical Factors for Effectiveness:

  • Clear, well-defined domain.

  • Availability of a human expert willing to collaborate.

  • Cost-benefit justification (high-stakes, frequent decisions).

  • User-friendly interface and robust explanation facility.

VI. NATURAL LANGUAGE PROCESSING (NLP)

Definition and Importance

NLP is the field of AI focused on enabling computers to understand, interpret, manipulate, and generate human language.

• Importance: Human-computer interaction (chatbots, Siri/Alexa), information extraction (search engines), translation, sentiment analysis, accessibility tools.

Key Components of NLP

1. Syntax: Grammatical structure.

   • Tasks: Parsing (syntactic analysis), part-of-speech tagging, grammar checking.

2. Semantics: Meaning.

   • Tasks: Word sense disambiguation, semantic role labeling, meaning representation (e.g., using frames/scripts).

3. Pragmatics: Context & intention.

   • Tasks: Anaphora resolution (what "it" refers to), discourse analysis, speech act recognition.

Applications in AI Systems

• Virtual Assistants & Chatbots: Integrate NLP (for understanding) with expert systems or knowledge graphs (for reasoning) and dialogue management.

• Information Retrieval: Query understanding, document summarization.

• Sentiment Analysis: Determining opinion from text (marketing, social monitoring).

Knowledge Representation in NLP

• Frames/Scripts: Ideal for representing stereotypical situations (e.g., a "restaurant script" with slots: Customer, Order, Food, Bill). Helps in expectation-based parsing and filling missing information.

• Semantic Networks: Represent word meanings and relationships (e.g., WordNet).

• Conceptual Dependency: Provides a primitive, language-independent meaning representation for sentences.

• Predicate Logic: Used for formal semantic interpretation (e.g., in a natural language interface to a database).

VII. ADDITIONAL TOPICS & APPLICATIONS (Brief)

Block World Problem

• Definition: A classic robotics/AI problem where a robot arm must rearrange blocks on a table from an initial configuration to a goal configuration.

• Significance: Tests planning, spatial reasoning, and knowledge representation (e.g., using predicate logic: ON(A,B), CLEAR(A)). It highlights the frame problem (what stays the same after an action).

• Recent Advancements: Modern robotics uses probabilistic roadmaps (PRM), task and motion planning (TAMP) combining symbolic planning with motion control, and deep learning for perception and grasp planning.

Production Systems

• Structure:

  • Production Rules (IF-THEN): IF <condition> THEN <action>.

  • Working Memory (WM): Global database of current facts/assertions.

  • Control System: Match rules against WM, resolve conflicts, fire rules.

• Characteristics: Modular, declarative (rules separate from control), good for rule-based expert systems.

• Comparison: More flexible than pure procedural code. Similar to forward-chaining inference engine. Differ from logic-based systems in their procedural semantics and often use certainty factors.

Interdisciplinary Nature of AI

AI draws from:

• Computer Science: Algorithms, data structures, complexity.

• Mathematics: Logic, probability, optimization, statistics.

• Psychology/Cognitive Science: Models of human learning and reasoning.

• Linguistics: Syntax, semantics, pragmatics for NLP.

• Neuroscience: Inspiration for neural network architectures.

• Philosophy: Ethics, consciousness, nature of intelligence.

Ethical and Societal Implications (Contextual)

• Heuristic Search Risks: In critical applications (autonomous vehicles, medical diagnosis), inadmissible heuristics or poorly tuned algorithms can lead to suboptimal or unsafe decisions.

• NLP in Surveillance: Mass surveillance using speech/text analysis raises privacy, consent, and bias concerns.

• Mitigation: Rigorous testing, transparency (explainable AI), bias audits, ethical guidelines, and regulatory frameworks.

Final Exam Strategy: For 7-mark questions, structure answers with Definition → Key Components/Algorithm → Example → Advantages/Limitations/Application. Always relate theory to the Tic-Tac-Toe or 8-puzzle examples where possible. For proof questions (resolution), show step-by-step unification and resolution.