Artificial Intelligence Foundations and Intelligent Agents Syllabus

What four things does rationality at any given time depend on?

1) The performance measure defining success, 2) the agent's prior knowledge of the environment, 3) the actions the agent can perform, 4) the agent's percept sequence to date.

Distinguish rationality from omniscience.

An omniscient agent knows the actual outcome of its actions in advance (impossible in reality). Rationality maximizes EXPECTED performance given available information, so a rational agent can still have a bad outcome without being irrational.

What is the acronym PEAS, used to specify a task environment?

PEAS = Performance measure, Environment, Actuators, Sensors — the specification framework used to fully describe a task environment when designing an agent.

Give the PEAS description for an automated taxi driver.

Performance: safe, fast, legal, comfortable, maximize profits. Environment: roads, traffic, pedestrians, customers. Actuators: steering, accelerator, brake, signal, horn, display. Sensors: cameras, radar, speedometer, GPS, engine sensors.

Compare fully observable vs. partially observable environments.

Fully observable: sensors give access to the complete state of the environment relevant to the choice of action at each point. Partially observable: noisy/inaccurate sensors or missing state data mean parts of the state are unavailable.

Compare deterministic vs. stochastic environments.

Deterministic: the next state is completely determined by the current state and the agent's action. Stochastic: outcomes involve uncertainty/probabilities. (If uncertain but no probabilities are quantified, it is called nondeterministic.)

Compare episodic vs. sequential environments.

Episodic: the agent's experience is divided into atomic episodes where each action depends only on the current episode (no effect on future ones). Sequential: current decisions affect all future decisions (short-term actions have long-term consequences).

Compare static, dynamic, and semidynamic environments.

Static: the environment does not change while the agent is deliberating. Dynamic: it can change while the agent deliberates. Semidynamic: the environment itself does not change with time, but the agent's performance score does.

Compare discrete vs. continuous environments.

Discrete: a finite number of distinct, clearly defined percepts, actions, states, and time steps (e.g., chess). Continuous: state, time, percepts, or actions vary smoothly over a range of values (e.g., taxi driving).

Compare single-agent vs. multi-agent environments, and cooperative vs. competitive.

Single-agent: one agent operates alone. Multi-agent: multiple agents interact. Multi-agent can be competitive (agents maximize opposing measures, e.g., chess) or cooperative (agents share/partly share a goal, e.g., taxis avoiding collisions).

Which type of task environment is generally the hardest, and why?

Partially observable, stochastic, sequential, dynamic, continuous, and multi-agent — because uncertainty, long-term consequences, changing conditions, and other agents all compound the difficulty of choosing rational actions.

Name the four basic types of agent programs in order of increasing generality/capability.

1) Simple reflex agents, 2) Model-based reflex agents, 3) Goal-based agents, 4) Utility-based agents. (Plus learning agents as an orthogonal enhancement.)

How does a simple reflex agent choose actions, and what is its key limitation?

It selects actions using condition-action (if-then) rules based only on the CURRENT percept, ignoring history. Its key limitation: it fails in partially observable environments and can get stuck in infinite loops.

What does a model-based reflex agent add over a simple reflex agent?

It maintains an internal state (a model of the world) reflecting the unobserved parts of the environment, using knowledge of how the world evolves and how the agent's actions affect the world — handling partial observability.

How does a goal-based agent differ from a reflex agent?

A goal-based agent uses goal information describing desirable situations and combines it with the world model to choose actions that achieve the goal — considering the future ('what will happen if I do this?'), enabling flexibility.

When are utility-based agents needed instead of goal-based agents?

When goals alone are insufficient — e.g., when there are conflicting goals (trade-offs) or several uncertain goals. A utility function maps a state to a real number measuring degree of 'happiness,' allowing rational trade-offs and maximization of expected utility.

What are the four conceptual components of a learning agent?

1) Learning element (makes improvements), 2) Performance element (selects external actions), 3) Critic (gives feedback on how the agent is doing against a fixed standard), 4) Problem generator (suggests exploratory actions).

What is the role of the critic in a learning agent?

The critic tells the learning element how well the agent is doing with respect to a fixed performance standard, since the percepts themselves provide no indication of success. It provides the feedback signal for improvement.

Explain the distinction between atomic, factored, and structured state representations.

Atomic: each state is a black box with no internal structure. Factored: each state is split into a fixed set of variables/attributes with values. Structured: states include objects and relationships between them (most expressive).

What is a problem-solving agent, and what representation does it typically use?

A goal-based agent that decides what to do by finding sequences of actions leading to desirable states. It typically uses an atomic representation of states and searches for a solution.

List the four phases of the problem-solving process for a problem-solving agent.

1) Goal formulation (define objective), 2) Problem formulation (define states and actions), 3) Search (find an action sequence / solution), 4) Execution (carry out the recommended actions).

Name the five components that formally define a search problem.

1) Initial state, 2) Actions available in each state, 3) Transition model (RESULT(s,a) = successor state), 4) Goal test, 5) Path cost function. (State space is derived from initial state, actions, and transition model.)

Define the state space of a search problem.

The state space is the set of all states reachable from the initial state by any sequence of actions; it forms a directed graph where nodes are states and edges (links) are actions.

Define path cost and step cost, and give the notation for step cost.

Path cost is a function assigning a numeric cost to a path (typically the sum of step costs). Step cost of taking action $a$ in state $s$ to reach state $s'$ is denoted $c(s, a, s')$.

What defines an optimal solution to a search problem?

A solution is a sequence of actions leading from the initial state to a goal state. An optimal solution is a solution that has the lowest path cost among all solutions.

Describe the 8-puzzle as a formal search problem (states, actions, goal, path cost).

States: locations of the eight tiles and the blank in the 3×3 grid. Actions: move the blank Left, Right, Up, Down. Goal test: matches the goal configuration. Path cost: number of moves (each step costs 1). It is an NP-hard sliding-tile problem.

Describe the 8-queens problem and the difference between its two formulations.

Goal: place 8 queens on a chessboard so no two attack each other. Incremental formulation: add one queen at a time (states = partial arrangements). Complete-state formulation: start with all 8 on the board and move them. The incremental formulation drastically reduces the state space.

How does the general TREE-SEARCH / GRAPH-SEARCH algorithm work, and what is the frontier?

Starting from the initial state, it repeatedly expands the current node by generating successors, adding them to the frontier (the set of leaf nodes available for expansion, a.k.a. open list). GRAPH-SEARCH additionally keeps an explored set to avoid revisiting states and prevent redundant paths/loops.

What are the four criteria used to evaluate a search algorithm's performance?

1) Completeness (guaranteed to find a solution if one exists), 2) Optimality (finds the least-cost solution), 3) Time complexity, 4) Space complexity — the latter two typically measured by the number of nodes generated/stored.

Define the parameters b, d, and m used in analyzing search complexity, and give the worst-case time complexity of breadth-first search.

$b$ = branching factor (max successors per node), $d$ = depth of the shallowest goal, $m$ = maximum length of any path in the state space. Breadth-first search has worst-case time and space complexity of $O(b^{d})$.