Unit 1: Foundations & Applications of AI / AI Problem Modeling & Search Concepts

1. Executive Summary & Overview of Artificial Intelligence

Artificial Intelligence (AI) is the engineering and scientific discipline dedicated to constructing computational systems capable of executing cognitive tasks traditionally associated with human intellect. These capabilities include reasoning, abstract knowledge representation, sensory perception, natural language comprehension, autonomous decision-making, and goal-directed planning.

Modern AI combines statistical learning, optimization, and cognitive modeling. The field has evolved through three primary historical epochs:

1. Symbolic AI (GOFAI - Good Old-Fashioned AI, 1950s–1980s): Knowledge-driven systems utilizing formal mathematical logic, production rules, expert systems, and combinatorial search.
2. Statistical Machine Learning (1990s–2010s): Data-driven probabilistic frameworks (SVMs, Bayesian networks, Random Forests) capable of generalizing patterns from empirical observations.
3. Deep Learning and Generative Foundation Models (2012–Present): Deep multi-layered representation learning (CNNs, Transformers, Diffusion models) pre-trained on vast multimodal corpuses.

2. Definitional Dimensions: The Four Perspectives on AI

In their seminal treatise Artificial Intelligence: A Modern Approach, Stuart Russell and Peter Norvig categorize AI definitions along two orthogonal dimensions:

• Human-Centric vs. Ideal Rationality (Fidelity to human behavior vs. normative ideal performance)
• Cognitive Process vs. Behavioral Action (Internal thought structures vs. external observable actions)

CODECopy Code
                       HUMAN-CENTRIC                 RATIONAL (IDEAL)
                 +-----------------------------+-----------------------------+
   THINKING      |  Cognitive Science          |  Laws of Thought            |
  (Internal)     |  Systems that think like    |  Systems that think         |
                 |  humans (Cognitive Models)  |  rationally (Formal Logic)  |
                 +-----------------------------+-----------------------------+
    ACTING       |  The Turing Test            |  Rational Agents            |
  (External)     |  Systems that act like      |  Systems that act           |
                 |  humans (Behaviorism)       |  rationally (Utility Max)   |
                 +-----------------------------+-----------------------------+

2.1 Acting Humanly: The Turing Test Approach (1950)

Alan Turing proposed an operational definition of intelligence via the Imitation Game. A computer passes the Turing Test if a human interrogator, communicating strictly through text terminals, cannot distinguish whether responses originate from a human or an automated machine.
To pass the Total Turing Test, an agent requires:

• Natural Language Processing (NLP): To communicate fluently in human languages.
• Knowledge Representation: To store contextual information, facts, and beliefs.
• Automated Reasoning: To answer queries and draw logical inferences.
• Machine Learning: To adapt to dynamic circumstances and extrapolate patterns.
• Computer Vision & Robotics (Total Test): To perceive physical objects and manipulate environments.

2.2 Thinking Humanly: The Cognitive Science Approach

To claim a program thinks like a human, one must determine how humans actually think. This relies on:

• Introspection: Catching one's own thoughts as they occur.
• Psychological Experimentation: Observing human subjects performing tasks.
• Neuroimaging: Scanning brain activity (fMRI, EEG) during cognitive functions.

2.3 Thinking Rationally: The "Laws of Thought" Approach

Pioneered by Aristotle's formal syllogisms: "Socrates is a man; all men are mortal; therefore, Socrates is mortal." This paradigm codifies correct thought into formal mathematical logic (First-Order Predicate Logic).

• Limitation: Transforming informal real-world knowledge into formal logical notation is difficult when uncertainty exists, and exhaustive logical deduction over large knowledge bases suffers from combinatorial explosion.

2.4 Acting Rationally: The Rational Agent Approach

A rational agent is an entity that acts so as to achieve the best expected outcome or, when there is uncertainty, the best expected utility.

• It subsumes logic: In many scenarios, logical inference is the correct mechanism to act rationally.
• It is more general than human behavior: Human actions are often constrained by cognitive biases, emotional impulses, or physical limitations. Rationality focuses on objective utility maximization.

3. Taxonomy of Artificial Intelligence

AI is categorized into distinct tiers based on operational capability and generality:

4. The PEAS Framework & Agent Environments

4.1 The PEAS Framework

To systematically design an intelligent agent, one must specify its PEAS description:

• P - Performance Measure: The objective criterion used to evaluate the agent's degree of success.
• E - Environment: The external world or task domain within which the agent operates.
• A - Actuators: The mechanisms through which the agent acts upon and alters the environment.
• S - Sensors: The input devices through which the agent perceives environmental states.

PEAS Design Examples:

4.2 Environmental Characteristics

Agent complexity is primarily dictated by the characteristics of its environment:

CODECopy Code
+---------------------------+--------------------------------------------------------------+
| Dimension                 | Contrast: Simple vs. Complex                                 |
+---------------------------+--------------------------------------------------------------+
| Observability             | Fully Observable (Chess) vs. Partially Observable (Poker)    |
| Determinism               | Deterministic (8-Puzzle) vs. Stochastic (Backgammon/Traffic) |
| Episodic vs. Sequential   | Episodic (Defect Inspection) vs. Sequential (Chess, Driving) |
| Static vs. Dynamic        | Static (Crossword) vs. Dynamic (Driving, Auction)            |
| Discrete vs. Continuous   | Discrete (Chess board) vs. Continuous (Autonomous Driving)   |
| Single vs. Multi-Agent    | Single-Agent (Solitaire) vs. Multi-Agent (Football, Markets) |
+---------------------------+--------------------------------------------------------------+

5. AI Problem Modeling as State Space Search

When an agent cannot immediately map perceptions to actions through reactive rules, it must search for a goal sequence within a formally defined state space.

5.1 Formal Formulation of a Search Problem

A search problem is formally defined by five atomic components:

1. State Space ($S$): The mathematical set of all conceivable states or world configurations reachable from the start.
2. Initial State ($s_0 \in S$): The specific state in which the agent begins.
3. Actions / Successor Function: Given state $s$, $\text{Actions}(s)$ returns the legal actions executable. The transition model $\text{Result}(s, a)$ defines the resultant state $s' = \text{Result}(s, a)$.
4. Goal Test: A Boolean predicate $\text{IsGoal}(s)$ determining whether a candidate state satisfies problem objectives.
5. Path Cost Function ($c(s, a, s')$): A numeric value assigning a cost to transitioning from $s$ to $s'$ via action $a$. Total path cost is $g(n) = \sum c(s_i, a_i, s_{i+1})$.

5.2 Classic State Space Examples

The 8-Puzzle Problem

• States: Any permutation of 8 numbered tiles and 1 blank space on a $3 \times 3$ grid ($9! / 2 = 181,440$ reachable states).
• Initial State: Any valid tile configuration.
• Actions: Move the blank space $\{\text{Left, Right, Up, Down}\}$.
• Goal Test: Matches target configuration (e.g., tiles 1–8 in row-major order with blank at center or bottom-right).
• Path Cost: Each step has a unit cost ($c = 1$).

The Travelling Salesperson Problem (TSP)

• States: The current city visited and the subset of all remaining unvisited cities.
• Initial State: Starting city with all other cities unvisited.
• Actions: Travel to any currently unvisited city.
• Goal Test: All $N$ cities visited and returned to starting city.
• Path Cost: Euclidean distance or travel time between consecutive cities.

CODECopy Code
       [State Space Graph]                       [Search Tree]
           (s0)                                      (s0)
          /    \                                    /           (A) <---> (B)                             (A)      (B)
        |         |                             /   \    /          (C) ----> (G)                          (C)   (B) (A)  (G*)
                                               |
                                              (G*)

5.3 State Space Graphs vs. Search Trees

• State Space Graph: A directed graph $G = (V, E)$ where vertices represent distinct problem states and directed edges represent valid transitions. It can contain cycles and multiple paths to the same state.
• Search Tree: A tree data structure generated dynamically by an agent exploring the graph. The root represents the initial state $s_0$, and branches represent candidate exploratory paths.
  • Distinction: A single physical state in the state space graph can appear multiple times as distinct nodes across different depths of the search tree!
  • Graph Search vs. Tree Search: Graph search maintains an explored set (closed list) to avoid re-expanding previously visited states, preventing infinite loops in cyclic graphs.

5.4 Search Performance Metrics

1. Completeness: Is the algorithm guaranteed to find a solution if one exists?
2. Optimality: Does the algorithm find the solution with the lowest total path cost among all possible solutions?
3. Time Complexity: Number of generated/expanded nodes before finding a goal.
4. Space Complexity: Maximum memory footprint (maximum nodes stored in the frontier).
   • Parameters: $b$ (branching factor), $d$ (depth of shallowest goal), $m$ (maximum depth of search tree).

6. Responsible, Trustworthy, and Ethical AI

As autonomous systems enter high-stakes socio-technical ecosystems (judiciary, credit scoring, healthcare triage), ethical governance frameworks become mandatory:

1. Algorithmic Fairness & Bias Mitigation:
   • Preventing models from encoding or magnifying historical societal prejudices (racial, gender, socio-economic biases).
   • Metrics: Demographic Parity ($P(\hat{Y}=1 | A=0) = P(\hat{Y}=1 | A=1)$), Equalized Odds ($P(\hat{Y}=1 | Y=y, A=0) = P(\hat{Y}=1 | Y=y, A=1)$).
2. Accountability & Auditability:
   • Traceability of decisions to engineers and organizations; maintaining data provenance logs.
3. Transparency & Explainability (XAI):
   • Ensuring deep model outputs can be interpreted by humans (SHAP, LIME, attention heatmaps) rather than remaining opaque black boxes.
4. Data Privacy & Governance:
   • Compliance with privacy regulations (GDPR, DPDP); differential privacy ($\epsilon$-DP); federated learning.
5. Safety, Robustness, and Adversarial Vulnerability:
   • Mitigating susceptibility to adversarial perturbations (Fast Gradient Sign Method) and distributional shift.

7. Comparative Framework: AI Paradigms

8. Practical Exam & Industry Tips

[!TIP]
Key Exam Heuristics for INT428 Unit 1:

• When asked to write a PEAS description, construct a clear 4-row markdown table covering Performance, Environment, Actuators, and Sensors explicitly.
• Remember the distinction between State and Node: A State is a representation of a physical configuration of the world; a Node is a bookkeeping data structure in a search tree containing state, parent pointer, action, path cost $g(n)$, and depth $d$.
• For environment taxonomy: Always remember that autonomous driving is the classic example of partially observable, stochastic, sequential, dynamic, continuous, and multi-agent.
• In Turing Test questions: State the components required for the standard test (NLP, Knowledge Representation, Automated Reasoning, Machine Learning) and the two additional ones for the Total Turing Test (Computer Vision, Robotics).