Intelligent agents and problem formulation notes — Unit 1

Artificial Intelligence (AI) is the study of how to build or program computers to do things that, if done by humans, would require intelligence.

⇒1.1 The Four Definitions of AI

Stuart Russell and Peter Norvig classify AI into four historical categories:

Modern AI focuses almost exclusively on Category 4: Acting rationally (doing the right thing to achieve the best outcome).

Proposed by Alan Turing in 1950, it was designed to provide a satisfactory operational definition of intelligence.

⇒2.1 The Setup

A human interrogator communicates via text with a human and a computer, hidden in different rooms. If the interrogator cannot reliably tell which one is the computer, the computer passes the test.

⇒2.2 Requirements to Pass

• Natural Language Processing: To communicate effectively.
• Knowledge Representation: To store what it knows.
• Automated Reasoning: To use stored information to answer questions.
• Machine Learning: To adapt to new circumstances.

An Agent is anything that can perceive its environment through sensors and act upon that environment through actuators.

⇒3.1 The Agent Function

Mathematically, an agent's behavior is described by the agent function that maps any given percept sequence to an action. `f: P* -> A`.

⇒3.2 Rationality

A rational agent is one that does the right thing. What is right is defined by a Performance Measure. Rationality is distinct from Omniscience (knowing the actual outcome). Rationality maximizes expected performance based on the percept sequence to date.

Before designing an agent, we must specify the task environment as fully as possible. We use the PEAS description.

• P - Performance Measure: The criteria for success (e.g., safety, speed, profit).
• E - Environment: The physical or virtual world the agent operates in (e.g., roads, pedestrians, chess board).
• A - Actuators: The hardware/software the agent uses to change the environment (e.g., steering wheel, brakes, display screen).
• S - Sensors: The hardware/software the agent uses to perceive the environment (e.g., cameras, lidar, keyboard input).

The complexity of the AI required depends entirely on the properties of its environment.

• Fully Observable vs Partially Observable: Can the sensors see the entire state of the world? (Chess is fully observable; Poker is partially observable).
• Deterministic vs Stochastic: Does the current state and action uniquely determine the next state? (Chess is deterministic; driving a car is stochastic because tires slip and humans act unpredictably).
• Episodic vs Sequential: Is the agent's experience divided into atomic, independent episodes? (Image classification is episodic; Chess is sequential).
• Static vs Dynamic: Does the environment change while the agent is deliberating? (Crosswords are static; driving is dynamic).
• Discrete vs Continuous: Are the states, time, and actions limited? (Chess is discrete; flying a drone is continuous).

Agents can be categorized by their internal complexity.

⇒6.1 Simple Reflex Agents

These agents select actions based strictly on the current percept, ignoring the rest of the percept history. They use Condition-Action rules (If car-in-front-is-braking Then apply-brakes). They only work in Fully Observable environments.

⇒6.2 Model-Based Reflex Agents

Used in Partially Observable environments. The agent maintains an internal state (a model of the world) that tracks the parts of the environment it cannot currently see.

⇒7.1 Goal-Based Agents

Knowing the current state is not always enough. The agent needs goal information that describes situations that are desirable. It uses Search and Planning to find a sequence of actions that reach the goal. (e.g., A GPS navigator).

⇒7.2 Utility-Based Agents

Goals just provide a binary 'Happy' or 'Unhappy' state. What if there are multiple paths to a goal? (e.g., one is safe but slow, one is fast but risky). A utility function maps a state onto a real number representing the degree of 'happiness'. The agent acts to maximize expected utility.

Problem-solving agents are a type of goal-based agent that use atomic representations (states are indivisible black boxes with no internal structure).

⇒8.1 The Formulation Process

Before an agent can search for a solution, it must formulate the problem mathematically. A problem consists of 5 components:

• 1. Initial State: Where the agent starts. (e.g., `In(Arad)`).
• 2. Actions: A function `ACTIONS(s)` returning the set of valid actions in state `s`.
• 3. Transition Model: `RESULT(s, a)` returns the state resulting from doing action `a` in state `s`.
• 4. Goal Test: A condition that determines if state `s` is the goal.
• 5. Path Cost: A function assigning a numeric cost to each path. We assume step costs are `c(s, a, s') >= 0`.

The Initial State, Actions, and Transition Model implicitly define the State Space of the problem: a directed graph in which nodes are states and links are actions.

⇒9.1 Searching the Graph

A solution is a path from the initial state to a goal state. The agent's algorithm will explore the state space by generating successors of already-explored states (expanding nodes) until a goal is found.

AI researchers use 'toy problems' to illustrate algorithms, as their state spaces are exact.

⇒10.1 The 8-Puzzle

A 3x3 grid with 8 numbered tiles and one blank space.

• States: Integer locations of tiles.
• Actions: Move blank Left, Right, Up, Down.
• Goal: Tiles in numerical order.
• Cost: 1 per move.

Other classic toy problems include the Vacuum World, Missionaries and Cannibals, and the N-Queens problem.