AI Agents, Planning, Logic, and Search - Lecture Notes

Vocabulary flashcards covering AI agents, planning, search, logic, and planning formalisms from the notes.

Standard Model (AI)

The idea that AI research aims to build agents that act rationally to achieve the given objective, limitations of computation to find optimal solution and value alignment.

Limited rationality

Optimal solution may be computationally intractable in complex environments, so agents settle for good enough options.

Value Alignment Problem

Challenge of aligning an agent's objective with human values so it acts in humans best interests.

Agent

Entity that perceives the environment via sensors and acts through actuators, capable of autonomy over time.

Rational/Intelligent Agent

Agent whose actions aim to maximize expected performance given evidence and knowledge.

Agent function

Abstract mapping from percepts to actions that supports the agent objective.

Agent program

Concrete implementation of the agent function in software.

Simple reflex agent

Agent that acts only on the current perception without history.

Model based reflex agent

Agent that uses internal state plus a transition model and sensor model to act.

Internal state

Perception history kept to infer the current state of the environment.

Transition model

Model of how actions change the world and how the world evolves independently.

Sensor model

Model of how sensors interpret the state of the world.

Goal based agent

Agent that reasons about future outcomes with respect to a goal.

Utility based agent

An agent that chooses actions to maximise a performance metric describing how desirable a state is.

Utility function

Internal performance measure assigning a value to states to reflect desirability.

Learning Agent

Agent that improves its performance over time by learning from experiences.

Learning element

Component responsible for making improvements based on experience.

Performance Measure

Numeric measure of how desirable the outcome of actions is.

Performance element

The part of an agent that decides which actions to take based on its perceptions, in order to achieve its goals or objectives.

Critic

Module that judges the learning element against a fixed performance standard.

Problem generator

Module that suggests exploratory actions to gain informative experiences.

Problem solving agent

Agent that plans ahead by considering a sequence of actions to reach a goal.

Planning agents

Agents that use structured representations to plan actions.

Agent architecture

The computing device on which the agent program runs.

Autonomy

Ability to act based on perception and learning rather than only prior knowledge.

PEAS framework

Performance, Environment, Actuators, Sensors used to define a task environment.

Observable environment

Environment fully observable by the agent senses.

Partially observable environment

Agent cannot observe the entire environment at once.

Multiagent

Environments with multiple agents with competitive or cooperative goals.

Deterministic

Next state is completely predictable base on current state and actions.

Sequential

Decisions affect future states (opposite of Episodic).

Static

Environment does not change while making a decision (opposite of dynamic)

Semi dynamic

Environment unchanged but performance score can change (chess clock decreases)

Discrete

Finite states (opposite of continuous)

Known

Action outcomes are known to the agent.

Informed search

Search strategies that use domain knowledge to guide exploration.

Problem formulation

Defining states and actions needed to solve the goal.

State space

Set of all possible states the environment can be in.

State

Representation of the environment at a point in time.

Initial state

The starting point of the search.

Transition model

Specification of how actions change states.

Goal test

Criterion to determine if a state satisfies the goal.

Goal state

A state that satisfies the goal condition.

Active cost function

Cost of applying an action used to evaluate paths.

Touring problems

Problems where a set of locations must be visited rather than a single goal.

Search tree

Structure representing possible action sequences from initial state to goal.

Search Node

Node containing state, parent, action, path cost, and depth.

Frontier

Set of nodes that can be expanded in the next step.

Queue types

Types include priority queue, FIFO queue, and LIFO queue.

Reached

Nodes that have been generated in the search.

Best-first search

Expands the frontier node with the best evaluation function value.

Graph search

Must avoids revisiting states

Uninformed search

blind search strategies without domain knowledge.

Breadth-first search

Expands the shallowest nodes first using a FIFO frontier.

Complete

The algorithm finds a solution when one exists

Time/space complexity

Measures of the resources required by a search algorithm.

Uniform-cost search / Dijkstra’s

Best first by path cost; complete and optimal with nonnegative costs.

Depth-first search

Expands deep paths using a stack; not cost-optimal and not complete in infinite spaces.

Bidirectional search

Search from both start and goal, aiming to meet in the middle.

Heuristic

Estimated cost to reach a goal used to guide informed search.

Greedy Best-First Search

Expands node with lowest heuristic value; not guaranteed optimal.

A* search

Uses f(n) = g(n) + h(n); can be optimal if h is admissible and consistent.

Admissible heuristic

Never overestimates the true cost to reach the goal.

Consistent heuristic

h(n) is no greater than the cost to move to a neighbor plus its h value.

Weighted A*

A* with h weighted to favor faster solution at the cost of optimality.

Effective branching factor (b*)

Average number of branches per node that yields the same node count as a perfectly balanced tree.

Relaxed problem

Easier version of a problem used to derive an admissible heuristic.

Adversarial search

Search in competitive environments where opponents have conflicting goals.

Deterministic games

Games with perfect information and zero-sum payoffs.

MAX and MIN

Opponents in adversarial search where MAX seeks maximum and MIN seeks minimum.

Minimax

Recursive strategy that backs up values from leaves to decide the root move.

Alpha-beta pruning

Prunes branches that cannot yield better outcomes than already explored paths.

Transposition table

Cache that stores evaluated game states to avoid re-searching identical positions.

Type A vs Type B strategies

Type A searches wide but shallow; Type B searches deep but narrow.

Heuristic evaluation function EVAL(s,p)

Estimates the expected utility of a position for a player.

Expectimax search

Models average case by introducing EXPECT nodes instead of MIN nodes.

Expectiminimax

Extends expectimax to stochastic two player games with MIN, MAX and EXPECT nodes.

Monte Carlo tree search

Estimates state value by averaging results of many simulated playouts.

Playout policy

Policy used to simulate moves in Monte Carlo search.

Selection policy

Strategy to focus computation on important parts of the game tree.

Knowledge based agents

Agents that use reasoning over a knowledge base to make decisions.

Knowledge Base (KB)

Set of sentences in a knowledge representation language.

Knowledge Representation Language

Formal language to encode knowledge, such as propositional or first order logic.

Axiom

Sentence accepted as true without proof within the KB.

TELL / ASK operations

TELL adds sentences to the KB; ASK queries what the KB knows.

Syntax and Semantics

Syntax is sentence structure; semantics is truth conditions for sentences.

Inference

Deriving new sentences from existing ones in the KB.

Declarative vs Procedural

Declarative tells what is true; procedural specifies how to act.

Wumpus World

A grid world with Wumpus, pits, gold; sensor cues and actions shape a planning problem.

Propositional Logic

Logic without variables where sentences are built from propositional symbols.

Model, satisfiability, entailment

Models assign truth values; satisfiable means some model makes a formula true; entailment means one sentence follows from another.

Entailment α |= β

Sentence α semantically entails β if every model of α is also a model of β.

Grounding

Link between logical reasoning and real world perception and action.

Propositional atoms, literals, clauses

Atoms are basic symbols; literals are atoms or their negation; clauses are disjunctions of literals.

CNF (Conjunctive Normal Form)

Formula expressed as a conjunction of disjunctions of literals.

Resolution

Inference rule that derives new clauses by eliminating a complementary literal pair.

Definite clause

Disjunction with exactly one positive literal used in forward chaining.

Horn clause

Disjunction with at most one positive literal; supports efficient forward chaining.

Forward chaining

Data-driven inference that adds conclusions as rules fire, linear time in KB size.

Backward chaining

Goal-driven inference that works back from a query to find supporting facts.