Artificial Intelligence – Comprehensive Bullet Notes (Ch 1–3 Overview)

INTRODUCTION – WHY STUDY AI?

• Humanity (Homo sapiens) deeply values INTELLIGENCE, recognizing it as the ability to perceive, understand, predict, and effectively manipulate a complex world. AI seeks to replicate or enhance this capability in machines.

• AI is the scientific study and engineering discipline of building artificial artifacts that exhibit intelligence, mirroring human cognitive functions or performing tasks typically requiring human intelligence.

  • The term "Artificial Intelligence" was coined in 1956 at the Dartmouth workshop, marking the formal birth of the field. Its arrival was comparable in excitement and intellectual challenge to the discovery of molecular biology.

  • It remains an open and rapidly evolving field, offering significant opportunities for innovation and discovery, much like the early days that gave rise to figures akin to "Einsteins & Edisons."

• Broad applicability: AI's influence spans numerous domains, from strategic games like chess and Go, to complex tasks like automated theorem-proving, creative endeavors such as poetry generation, practical applications like self-driving vehicles, advanced medical diagnosis, and many more.

FOUR TRADITIONS OF DEFINITION

• AI definitions can be categorized along two primary axes (as illustrated in Figure 1.1):

  • Thinking vs. Acting: Focus on what AI does (acting) or what AI thinks (thinking).

  • Human-oriented vs. Rational-ideal: Focus on replicating human performance (human-oriented) or achieving optimal, logical correctness (rational-ideal).

1. Acting Humanly

   • Turing Test: Proposed by Alan Turing in 1950, this test evaluates a machine's ability to exhibit intelligent behavior equivalent to, or indistinguishable from, that of a human. It involves a text-only interrogation whereby a human judge converses with both a human and a computer, passing if the judge cannot reliably tell which is which.

   • Passing the Turing Test requires several core AI capabilities:

     • Natural Language Processing (NLP): To enable communication in human languages.

     • Knowledge Representation (KR): To store and retrieve information about the world.

     • Automated Reasoning: To use stored information to answer questions and draw new conclusions.

     • Machine Learning (ML): To adapt to new circumstances and detect patterns.

   • The Total Turing Test extends this by adding physical interaction, requiring the machine to also have Computer Vision (to perceive objects) and Robotics (to manipulate objects).

2. Thinking Humanly

   • This approach focuses on cognitive modeling, aiming to build AI programs that think like humans. It involves gathering empirical data through various methods such as introspection (humans describing their own thought processes), psychological experiments (observing human behavior in controlled settings), and brain-imaging (studying brain activity during cognitive tasks).

   • An early example is the General Problem Solver (GPS) by Newell & Simon, which attempted to compare its machine reasoning traces directly to human problem-solving traces, seeking a match between the steps taken by the AI and those taken by a person.

   • The interdisciplinary field dedicated to this study is Cognitive Science, combining AI with psychology, linguistics, and philosophy.

3. Thinking Rationally

   • This tradition is rooted in the "Laws of Thought," a field initiated by Aristotle with his syllogisms, which provided structures for valid arguments. The goal is to build AI systems that can reason logically.

   • Key concepts derive from formal logic (e.g., propositional logic, first-order logic) developed by mathematicians like George Boole and Gottlob Frege.

   • Obstacles include: accurately translating uncertain knowledge from the real world into formal logical statements, and the inherent computational explosion that can occur when attempting to solve complex problems through exhaustive logical deduction.

4. Acting Rationally (Rational Agent Approach)

   • This paradigm defines AI as the study of designing rational agents—systems that act to maximize their expected outcome. This means selecting the action that is expected to achieve the best result given the available information.

   • It is broader and more encompassing than pure logic, embracing practical considerations like reflexes, learning from experience, and decision-making under uncertainty, allowing for effective action even when complete knowledge is unavailable.

   • This approach is mathematically crisp and provides a quantifiable framework for evaluating AI performance, forming the core of modern AI textbooks and research.

RATIONAL AGENTS & KEY TERMS

• Agent: An entity that perceives its environment through sensors (e.g., cameras, microphones, keyboards) and acts upon that environment through actuators (e.g., motors, speakers, screen displays).

• Percept sequence = The complete chronological history of everything the agent has ever perceived. This sequence forms the basis for the agent's decisions.

• Agent Function: An abstract, mathematical mapping from every possible percept sequence to an action. It defines what the agent should do for any given perceptual history.

• Agent Program: A concrete, computational implementation of the agent function that runs on a physical Architecture (the computing device and its hardware).

• Performance Measure: A criterion that defines the degree of success for an agent's behavior. For example, for a vacuum cleaner, it might be the amount of dirt collected per hour, penalized by noise or power consumption.

• Rationality: The property of selecting an action that maximizes the agent's expected performance measure, given its current percept sequence, any prior knowledge it possesses, the set of possible actions, and the known (or estimated) dynamics of the environment. This implies making the best decision under uncertainty and imperfect information.

• PEAS description (Performance, Environment, Actuators, Sensors) is a crucial framework for formally defining and formulating any AI problem, ensuring all relevant aspects are considered.

  • Example: For an Autonomous Taxi:

    • Performance: Safety (minimal accidents), maximizing profit (reaching destination efficiently, minimizing fuel), legality, comfort, reaching the correct destination.

    • Environment: Roads, traffic, pedestrians, customers, other vehicles, weather, road signs/markings.

    • Actuators: Steering wheel, accelerator, brake, signal lights, horn, display messages to passengers, speaking (for navigation/interaction).

    • Sensors: GPS, camera, lidar, radar, speedometer, odometer, engine sensors, keyboard (for destination input), microphone (for voice commands).

ENVIRONMENT TYPES (7 DIMENSIONS)

Environments can be classified along several independent dimensions, which significantly impact the design of the rational agent:

• Fully vs. Partially Observable: Is the agent's sensors sufficient to perceive the entire state of the environment at all times? Partially observable means some aspects are hidden or unknown (e.g., an autonomous taxi can't see around a corner).

• Single vs. Multi-Agent: Does the agent operate alone, or are there other agents in the environment? Multi-agent environments can be Competitive (e.g., chess) or Cooperative (e.g., joint robotic task).

• Deterministic vs. Stochastic (→ Uncertain): Will the next state of the environment be completely determined by the current state and the agent's action (deterministic)? Or does it involve randomness or unpredictable outcomes (stochastic)? Uncertain environments often require probabilistic reasoning.

• Episodic vs. Sequential: Is the agent's experience divided into atomic, independent episodes where each perception and action is unrelated to the next (episodic, e.g., image classification)? Or does the current action affect future perceptions and actions (sequential, e.g., driving)?

• Static vs. Dynamic (or Semi-dynamic): Does the environment change while the agent is deliberating or not? Static environments don't change. Dynamic environments change constantly. Semi-dynamic environments don't change by the agent's actions, but change outside of its control.

• Discrete vs. Continuous: Is the state, action, and percept space discrete (finite number of distinct states/actions, e.g., chess) or continuous (infinite range of values, e.g., real numbers for speed or position)?

• Known vs. Unknown laws: Are the rules governing the environment's behavior known to the agent (known) or does the agent need to learn them through experience (unknown)?

• The hardest environments for AI agents are typically: partially observable, multiagent, stochastic, sequential, dynamic, continuous, and unknown.

AGENT STRUCTURES

These structures represent different ways to implement the agent program, varying in complexity and capability:

1. Simple Reflex Agents

   • Operate based on Condition–Action rules: If the current percept matches a specific condition, then perform a predefined action. For example, if car in front is braking then initiate braking.

   • They work effectively only in fully observable environments because they act solely on the current percept and have no memory of past states.

   • They may get stuck in infinite loops if a condition leads to an action that restores the environment to a state that triggers the same condition. Randomization can sometimes help break these loops.

2. Model-Based Reflex Agents

   • These agents maintain an internal state that tracks the unobserved aspects of the environment. This internal state is updated based on the history of percepts and the agent's actions.

   • They use an internal model of how the world evolves independently of the agent and how the agent's actions affect the world. This allows them to function in partially observable environments by keeping track of what they can't see presently but know based on past information.

3. Goal-Based Agents

   • Beyond just maintaining a model of the world, these agents have explicit goals that they aim to achieve (e.g., reaching a specific destination, winning a game).

   • They use their goals to evaluate the desirability of different states and choose actions that lead towards goal states. This often requires search (finding a sequence of actions) or planning (creating a detailed strategy) to determine the best path to reach the goal.

4. Utility-Based Agents

   • These are the most general and sophisticated agents. While goal-based agents only distinguish between goal and non-goal states, utility-based agents have a utility function $U(s)$, which provides a numerical measure of the desirability (or preference) of each state or sequence of states.

   • This allows for fine-grained decision-making, enabling the agent to handle multiple conflicting goals, make trade-offs between different factors (e.g., speed vs. safety), and make decisions under uncertainty by maximizing expected utility (the average utility of possible outcomes, weighted by their probabilities).

5. Learning Agents (4 components)

   • These agents can learn and improve their performance over time. They consist of:

     • Performance Element: This is the agent itself, responsible for selecting actions. It is what we might call the "solver" or "learner" which takes the current percept and decides what to do.

     • Learning Element: Responsible for making improvements to the performance element. It analyzes feedback from the critic and suggests modifications to the agent's knowledge or action selection strategy.

     • Critic: Provides feedback to the learning element on how well the agent is doing with respect to a fixed performance standard.

     • Problem Generator: Responsible for suggesting actions that will lead to new and informative experiences, enabling the agent to explore the environment and discover new ways to improve its performance. This encourages active learning rather than just reacting to given situations.

REPRESENTATION AXIS

AI systems represent information about the world in different ways, affecting how reasoning and learning are performed:

• Atomic: The simplest representation where a state is treated as a single, indivisible entity, without any internal structure. For example, a location might simply be represented by a name like "RoomA" without breaking it down into attributes.

• Factored: A state is represented as a vector or collection of attribute-value pairs, where each attribute (or variable) has a specific value. For example, a state might be {Location: "RoomA", Light: "On", Temperature: "22C"}.

• Structured: The most expressive representation, where objects exist and have explicit relations to each other. This is typically achieved using formal logics like first-order logic, allowing for complex knowledge representation and reasoning about relationships (e.g., "(Is_In John RoomA)", "(Contains RoomA Chair1)").

FOUNDATIONS & HISTORY SNAPSHOT

AI draws heavily from various disciplines:

• Philosophy: Explored fundamental questions about knowledge, mind, and reasoning. Key ideas include: Aristotle's logic, Descartes' dualism (separation of mind and body), Lock & Hume's empiricism (knowledge from experience), and Carnap's logical positivism (scientific knowledge from observation and logic).

• Mathematics: Provided the formal tools for AI. This includes: Logic (George Boole's symbolic logic, Gottlob Frege's predicate logic), Computability (Alan Turing's Turing Machine and Church–Turing Thesis defining what is computable), Incompleteness theorems (Kurt Gödel showing limits of formal systems), and Complexity theory (Edmonds, Cobham, Cook, Karp's work on NP-completeness, defining hard problems).

• Economics/Decision Theory: Contributed frameworks for rational decision-making. Key concepts are: Utility theory (von Neumann & Morgenstern's expected utility theory for decisions under uncertainty), and Game Theory (strategic interaction between rational agents).

• Neuroscience: Inspired by the structure and function of the brain. Concepts include: the basic unit of the brain, the Neuron, and Donald Hebb's Hebbian learning rule ("neurons that fire together wire together"). Comparisons between brain computational power and supercomputers (Fig 1.3) highlight the scale and efficiency differences.

• Psychology: Investigated human cognition and behavior. The shift from Behaviorism (focus on observable stimulus-response) to Cognitive psychology (focus on internal mental processes, memory, problem-solving).

• Control Theory/Cybernetics: Deals with designing systems that regulate themselves. Norbert Wiener's Cybernetics introduced concepts like feedback and homeostasis (maintaining stable internal conditions), crucial for agent control.

• Linguistics: Explored the structure and meaning of language. Noam Chomsky's critique of Skinner's behaviorist view of language led to more sophisticated computational linguistics models.

Important Milestones:

• 1950: Alan Turing publishes "Computing Machinery and Intelligence," introducing the Turing Test.

• 1956: The Dartmouth conference is held, officially coining the term "Artificial Intelligence" and marking its birth as a field.

• Early Programs: Significant early AI programs include:

  • Logic Theorist (1956): Considered the first AI program, co-authored by Newell, Simon, and Shaw, capable of proving mathematical theorems.

  • General Problem Solver (GPS): A more general problem-solving architecture by Newell and Simon that attempted to mimic human problem-solving steps.

  • DENDRAL (1965): An early expert system that inferred molecular structure from mass spectrometry data.

  • SHRDLU (1971): A natural language understanding program that operated in a "blocks world" environment, demonstrating understanding of commands, questions, and statements.

• Winters & Revivals: AI has experienced periods of funding cuts and renewed interest:

  • 1966–73: The "AI Winter" due to over-promising, limited computational power, and difficulty with scaling early methods.

  • 1980s: Boom of expert systems, specific AI programs that use knowledge bases to provide expert-level advice.

  • 1986: Resurgence of neural networks with the discovery of the back-propagation algorithm.

  • 1990s: Resurgence of probabilistic reasoning and Bayesian networks, better handling uncertainty.

• 2005+: Era of Big Data, powerful computing, and the rise of Internet agents. Notable events include the DARPA Grand Challenge for autonomous vehicles, significantly advancing self-driving technology.

PROBLEM-SOLVING AGENTS (Chapter 3 intro)

Problem-solving agents often achieve their goals by performing Search in an abstract State Space (a simplified model of the world relevant to the problem) until a goal state is reached.

Components of a Well-Defined Problem:

1. Initial state: The starting point of the agent in the problem space. E.g., for routing, it's the current city.

2. Actions $ACTIONS(s)$: A function that returns the set of all possible actions that can be executed from a given state $s$. E.g., for routing, $ACTIONS( ext{Arad})$ might return {"Go to Sibiu", "Go to Timisoara", "Go to Zerind"}.

3. Transition model $RESULT(s,a)$: A function that describes the state reached after executing action $a$ in state $s$. E.g., $RESULT( ext{Arad}, ext{Go to Sibiu})= ext{Sibiu}$.

4. Goal test: A function that determines whether a given state is a goal state. E.g., $GoalTest( ext{Bucharest})$ is true, otherwise false.

5. Path cost $g(n)=\sum c(s,a,s')$: A function that assigns a numerical cost to a path (sequence of actions). This is typically the sum of individual step costs $c(s,a,s')$ for each action taken to transition from state $s$ to $s'$. E.g., distance in km or time taken.

• A Solution is a sequence of actions that transforms the initial state into a goal state. An Optimal solution is one that minimizes the path cost among all possible solutions.

• Search Tree vs. State Space Graph: A search tree is generated by starting at the initial state and systematically expanding nodes (possible states) by applying actions. It can have redundant paths to the same state if not managed. A state space graph shows all states and their connections, representing the underlying problem structure without necessarily showing the search process or redundancies.

• Nodes in the search tree typically store crucial information: {STATE (the actual state in the problem space), PARENT (the node from which this node was generated), ACTION (the action taken to reach this node from the parent), PATH-COST (the total cost from the initial state to this node, $g(n)$).

• Frontier / Open list: This is a data structure storing all the leaf nodes that have been generated but not yet expanded (i.e., their successors have not yet been evaluated). It is often managed via different types of queues: FIFO (First-In, First-Out for Breadth-First), LIFO (Last-In, First-Out for Depth-First), or Priority Queue (for Uniform-Cost or A* search).

• Explored set / Closed list: This data structure stores all previously expanded nodes. Its purpose is to prevent the search algorithm from re-expanding states that have already been visited and processed, thereby avoiding redundant computations and infinite loops in cyclic graphs.

Uninformed (Blind) Search Strategies

These strategies operate with no knowledge about the suitability of a non-goal state for reaching the goal, hence they are "blind." Performance criteria include:

• Completeness: Is the strategy guaranteed to find a solution if one exists?

• Optimality: Is the strategy guaranteed to find the optimal (lowest cost) solution?

• Time Complexity $O(\cdot)$: How long does it take to find a solution (measured in terms of nodes expanded)?

• Space Complexity $O(\cdot)$: How much memory does it require (measured in terms of nodes stored)?

1. Breadth-First Search (BFS)

   • Expands the shallowest (closest to the root) unexpanded node first, using a FIFO queue for the frontier.

   • Complete (if branching factor is finite) and optimal if all step costs are equal (or constant and non-negative).

   • Time & Space Complexity: $O(b^d)$, where $b$ is the branching factor and $d$ is the depth of the shallowest goal. This can be very large for deep solutions.

2. Uniform-Cost Search (UCS)

   • Expands the node with the lowest path cost $g(n)$ first, using a priority queue.

   • Complete (if step costs are non-negative and greater than or equal to a small positive constant $\epsilon>0$) and optimal, even for varying step costs.

   • Time/Space Complexity: $O(b^{1+\lfloor C^<em>/\epsilon \rfloor})$, where $C^</em>$ is the cost of the optimal solution. It is similar to BFS but explores nodes in increasing order of path cost.

3. Depth-First Search (DFS)

   • Expands the deepest unexpanded node first, using a LIFO stack for the frontier.

   • Time Complexity: $O(b^m)$, where $m$ is the maximum depth of the search space. Can be very long if the deepest path is irrelevant.

   • Space Complexity: $O(bm)$ (for remembering the current path in the stack). For graph search with a closed list, it needs $O(m)$ if using recursive implementation.

   • Not complete in infinite search spaces (gets stuck exploring one deep path) and non-optimal (may find a sub-optimal solution first).

4. Depth-Limited Search (DLS) with limit $\ell$

   • DFS with a predefined depth limit $\ell$ to avoid infinite paths. Nodes at depth $\ell$ are treated as if they have no successors.

   • Completeness and optimality depend critically on the choice of $\ell$ relative to the actual solution depth $d$. If \elld, it's not optimal.

5. Iterative Deepening Search (IDS)

   • Repeatedly runs Depth-Limited Search (DLS) for increasing depth limits: $\ell=0, 1, 2, \dots, d$. This combines the benefits of DFS's low space complexity with BFS's completeness and optimality.

   • Complete and optimal (if step costs are unit or equal).

   • Time Complexity: $O(b^d)$, surprisingly efficient despite re-exploring nodes. Most nodes are at deeper levels, so re-exploring shallower ones contributes little to total time.

   • Space Complexity: $O(bd)$, which is optimal among complete search strategies.

6. Bidirectional Search

   • Simultaneously runs two BFS searches: one forward from the start node and one backward from the goal node. The search terminates when the two frontiers meet in the middle.

   • Requires the ability to generate predecessors for the backward search (i.e., know which actions lead to a given state).

   • Time & Space Complexity: $O(b^{d/2})$, a significant advantage over single-direction search for deep problems as $b^{d/2}+b^{d/2}$ is much less than $b^d$.

(A table summarizing these strategies' properties is typically found in textbooks, e.g., Fig 3.21.)

KEY EQUATIONS & DEFINITIONS

• Expected utility: $EU(a)=\sum_{s'}P(s'\mid a,\text{percepts})\,U(s')$. This equation defines the expected utility of an action $a$ as the sum over all possible next states $s'$ of the probability of reaching that state (given action $a$ and current percepts) multiplied by the utility of that state. Rational agents choose the action with the maximum expected utility.

• Optimal path cost $C^*$: The lowest possible cost to reach a goal state.

• Branching factor $b$: The average number of successors for any given node in the search tree.

• Depth of optimal solution $d$: The number of steps from the initial state to the shallowest goal state.

• Maximum depth $m$: The maximum depth of any path in the state space.

ETHICAL & PRACTICAL IMPLICATIONS

• Rational ≠ Human: A rational agent acts optimally according to its design, which doesn't necessarily mean it acts like a human. Human rationality is often "bounded rationality" (Chapter 17), meaning decisions are made with limited computational resources and imperfect information. This distinction is crucial in AI design.

• Consider “Friendly AI”: A critical area of ethical AI research focused on ensuring that advanced AI systems, especially those capable of learning and adapting, have learned utility functions that align perfectly with human values and well-being, to prevent unintended harmful outcomes.

• Big-data-driven learning raises significant concerns regarding privacy (how personal data is collected, stored, and used) and bias (if the training data reflects societal biases, the AI system will likely perpetuate or amplify them, leading to unfair or discriminatory outcomes).

REAL-WORLD APPLICATIONS (state of the art)

• Self-driving vehicles: Progress largely driven by challenges like the DARPA Urban Challenge, leading to widespread research and development in autonomous navigation using AI.

• Speech interfaces: Enabled by advanced NLP and speech recognition, used in various applications like airline booking systems, smart assistants (Siri, Alexa), and customer service.

• NASA Remote Agent & MAPGEN on Mars: AI systems used for autonomous spacecraft control and automated planning for Martian rover operations, demonstrating AI's capability in complex, remote environments.

• IBM Deep Blue: A chess-playing computer that famously defeated world champion Garry Kasparov in 1997, marking a significant milestone in AI's ability to tackle complex strategic games.

• AlphaGo: Developed by DeepMind, this AI program defeated the world's top Go players, a feat considered much harder than chess due to the enormous branching factor and intuitive nature of Go.

• Spam filtering with ML: Machine learning algorithms effectively classify and filter unwanted emails, adapting to new spam techniques.

• Web search & recommender systems: AI powers major search engines (like Google) and content recommendation platforms (like Netflix, Amazon), personalizing results and suggestions based on user behavior and preferences.

STUDY TIPS FOR EXAM

• Be able to classify an environment along all 7 dimensions with precise reasoning.

• For each uninformed search strategy: clearly state its queue type, explain its completeness, optimality, and typical time & space complexity implications.

• Write a complete PEAS description for any novel task provided.

• Translate an English problem description into the formal components of a well-defined problem: $\langle S_0, A, RESULT, Goal, c \rangle$.

• Clearly explain the difference between an agent function, an agent program, and the underlying architecture.

• Illustrate the functionality of simple reflex, model-based, goal-based, and utility-based agents with your own concrete examples.

• Practice converting path cost units (e.g., converting kilometers to milliseconds for an autonomous vehicle based on fuel consumption and speed limits).