CSE 3521: Agent Design

[Many slides are adapted from the UC Berkeley. CS188 Intro to AI at UC Berkeley and previous CSE 3521 course at OSU.]

Recap: What is AI?

The science of making machines that:

Think like people

Act like people

Think rationally

Act rationally

maximizes some goal achievement (expressed by the expected utility/performance of outcomes)

Utility, Performance, Reward

Pre-defined utility

Learned utility

[OpenAI, https://openai.com/blog/chatgpt]

Recap: Turn a real-world problem into an AI solution

• AI agents (perceive through sensors 🡪act through actuators) operator in/interact with the environment.
• PEAS:
• Performance
• Environment
• Actuator
• Sensor

​

Environment

Agent

perception

action

• Performance – cleanness, efficiency, distance traveled
• Environment – room with 4 squares
• Actuators – wheels, brushes, vacuum extractor
• Sensors – dirt detection

​

Environments can change!

Today

• Agent design (continued)
• (rational) AI agents
• Types of agents
• Types of environments

​

• Search problems

​

​

​

Sample agents

Pacman

• Percepts – squares around Pacman
• Actions – move U/D/L/R
• Environment – map with walls, dots,� and ghosts

​

Spam Detector

• Percepts – sender, subject line, body � of current email
• Actions – mark Spam/Not Spam
• Environment – your email inbox

​

Other sample agents

Navigation agent

[Kil et al., 20224]

[Song et al., CVPR 2022]

What makes an AI agent

• Agent – an entity that perceives its environment through sensors, � and acts on it with effectors (actuators).�

​

Sensors

​

​

​

​

​

​

Actuators

Percepts

​

​

​

​

​

​

​

​

Actions

Agent

Environment

• Percepts are constrained by Sensors + Environment

​

​

​

• Actions are constrained by Actuators + Environment

What makes an AI agent

• Agent – an entity that perceives its environment through sensors, � and acts on it with effectors (actuators).�

​

Sensors

​

​

​

​

​

​

Actuators

Percepts

​

​

​

​

​

​

​

​

Actions

Agent

Environment

• Percepts are constrained by Sensors + Environment

​

​

​

• Actions are constrained by Actuators + Environment

​

Agent Function (policy) – how does it choose the action?

​

?

What is a rational AI agent?

• A rational agent always acts to maximize its expected performance measure, given current percept/state

​

• Rationality ≠ omniscience
• There is “uncertainty” in the environment.
• That is why we emphasize “expected”.

​

​

​

​

​

​

​

Types of agents

• Reflex agent

​

• Planning agent

​

• Goal-based agent

​

• Learning agents, Utility-based agents, logical agents, …

​

​

Reflex agent

• Choose action based on current percept (and maybe memory)
• May have memory or a model of the world’s current state
• Do not consider the future consequences of their actions
• There might be no effects to the future.
• Consider how the world IS

Days

Buy or not?

percept

Stock price

Reflex agent

• Choose action based on current percept (and maybe memory)
• May have memory or a model of the world’s current state
• Do not consider the future consequences of their actions
• There might be no effects to the future.
• Consider how the world IS

Buy or not?

Days

percept

memory

Stock price

Percepts vs. states

• State: a representation of the environment (where are the ghosts, dots, etc.) that is relevant to the problem

• Percept: what the “agent” can perceive from the environment

• percept vs. state
• May be the same
• May be different (according to the definition or observability)

Planning agent

• Ask “What if”
• Decisions based on (hypothesized) consequences of actions
• Must have a model of how the world evolves in response to actions
• Must formulate a (long-term) goal
• Consider how the world WOULD BE

​

Real world

Model of the world

Example

Planning-oriented Autonomous Driving [Hu et al., CVPR 2023]

Goal-based agent

• Chooses action (sequence) to get from current state to some goals

​

Goal-based agent

• Chooses action (sequence) to get from current state to some goals

​

Pacman

• Percepts – squares around Pacman
• Actions – move U/D/L/R
• Environment – map with walls, dots, and ghosts
• Goal:

​

​

Spam Detector

• Percepts – sender, subject line, body � of current email
• Actions – mark Spam/Not Spam
• Environment – your email inbox
• Goal:

​

​

Goal-based agent

• Chooses action (sequence) to get from current state to some goals

​

Pacman

• Percepts – squares around Pacman
• Actions – move U/D/L/R
• Environment – map with walls, dots, and ghosts
• Goal:

​

​

Spam Detector

• Percepts – sender, subject line, body � of current email
• Actions – mark Spam/Not Spam
• Environment – your email inbox
• Goal:

​

​

…in as short a path as possible

Detect as many spam emails as possible!

Goal-based agent

• Chooses action (sequence) to get from current state to some goals

​

Pacman

• Percepts – squares around Pacman
• Actions – move U/D/L/R
• Environment – map with walls, dots, and ghosts
• Goal:

​

​

Spam Detector

• Percepts – sender, subject line, body � of current email
• Actions – mark Spam/Not Spam
• Environment – your email inbox
• Goal:

​

​

…in as short a path as possible

Can also have a learning agent!

​

We’ll learn it later in the course!

Detect as many spam emails as possible!

Example: navigation agent

[Song et al., CVPR 2022]

Example: large language model (LLM)

​

​

​

[Bi et al., 2020]

Evaluation

Recap: AI – agents and environments

• Much (though not all) of AI is concerned with agents operating in environments.
• Environment – the problem setting
• Agent – an entity that perceives its environment through sensors and acts upon that environment through effectors (actuators)

​

​

​

Questions?

Types of environments

• Six common properties to distinguish environments (not exhaustive)
• Fully observable vs. Partially observable
• Single agent vs. Multiagent
• Deterministic vs. Stochastic
• Episodic vs. Sequential
• Static vs. Dynamic
• Discrete vs. Continuous

​

Fully observable vs. Partially observable

• Fully observable
• Agent is able to sense everything (the complete state) in the environment

​

​

�

• Partially observable
• noisy, inaccurate, or incomplete sensors

​

​

Single Agent vs. Multiagent

• Single Agent
• Self-explanatory

​

• Multiagent
• Task involves more than one agent
• Each with its own performance measure
• May be competitive (measures are opposed) or cooperative (measures are aligned)

​

​

​

[Credit: Jiaoyang Li’s website]

Deterministic vs. Stochastic

• Deterministic
• Next state of the world is fully determined by the current state + agent action

​

�

• Stochastic
• it’s not deterministic

​

https://2048game.com/

Episodic vs. Sequential

• Episodic
• Each step’s state (and/or decision) is independent of the previous ones

​

​

​

​

​

• Sequential
• Each step’s state (and/or decision) affects later ones

Static vs. Dynamic

• Static
• world doesn’t change while agent is choosing an action

​

​

​

• Dynamic
• decision time matters!

[credits: Deva Ramanan et al., 2020;

Yan Wang et al., 2019]

Discreet vs. Continuous

• Discrete
• Possible states/actions are distinct; world changes discretely

​

​

​

​

​

• Continuous
• states/actions take on continuous values

These help to find how to approach a problem

• Static: focus on getting high accuracy/utility
• Dynamic: trade some utility for higher efficiency (speed!)
• Episodic: reflex agent
• Sequential: need a goal-based/planning agent
• Stochastic: need robustness to uncertainty/failure (robots!)
• Deterministic: can focus on efficiency and exactness (Internet crawler)

​

• Reflex agents can be rational in episodic environments!

​

• Discussion: fully-observable + deterministic vs. partially-observable + stochastic

​

Exercise

Summary

• Types of agents
• Reflex agent
• Planning agent
• Goal-Based agent
• Learning agents, utility-based agents, logical agents, …
• They are not “mutually” exclusive!

​

• Six types of environments

​

• Appropriate agent design depends on the environment type

​

Next

• Search problems: a systematic way to choose the right action sequence

​

• We will focus on fully-observable, deterministic, and static environments.

Questions?

CSE 3521: Search

[Many slides are adapted from the UC Berkeley. CS188 Intro to AI at UC Berkeley and previous CSE 3521 course at OSU.]

Agents that plan ahead

• Planning agents:
• Ask “what if”
• Decisions based on hypothesized consequences of actions
• Must have a model of how the world evolves in response to actions
• Must formulate a goal test
• Consider how the world WOULD BE

​

• Optimal vs. complete planning

Agents that plan ahead

• Before taking real actions in the real environment, formulate an off-line problem in a simulated/imaginary environment (model).

​

• The off-line problem:
• Has a goal test/desired state(s): not necessary the same as the real problem
• To find a sequence of actions that can achieve the goal, better with optimal cost/performance measure/utility

​

• Execute the action sequence in the real environment
• Execute the first action in the sequence, see how to state changes, and may re-plan!

Search problems

• A systematic way to looking for the (optimal) action sequence to reach goal
• Not the only way

Search problems

• A search problem consists of:

​

• A state space

​

​

• A successor function

(with actions, costs)

​

​

• A start state and a goal test

​

• A solution is a sequence of actions (a plan) which transforms the start state to a goal state

​

Start:

Goal(s): or or ……

Example: traveling in Romania

• State space:
• Cities
• Successor function:
• Roads: Go to adjacent city with cost = distance
• Start state:
• Arad
• Goal test:
• Is state == Bucharest?

​

• Solution?
• If there exists one, it is a sequence of cities from Arad to Bucharest

​

​

​

What’s in a state space?

• Problem: Pathing
• States: (x, y) location
• Actions: NSEW
• Successor: update location only
• Goal test: is (x, y)=END

• Problem: Eat-All-Dots
• States: {(x, y), dot Booleans}
• Actions: NSEW
• Successor: update location and dot Booleans
• Goal test: dots all false

The world state includes every detail of the environment

A search state keeps only the details needed for planning (abstraction)

State space sizes? How many possible states?

• World state:
• Agent positions: 120 (i.e., 10 x 12)
• Food count: 30 (i.e., 5 x 6)
• Ghost positions: 12
• Agent facing: NSEW�
• How many
• World states?

120 x (2³⁰) x (12²) x 4

• States for pathing?

120

• States for eat-all-dots?

120 x (2³⁰)

​

Summary

• Planning agents
• Solve off-line problems and execute the solution in real environment

​

• Search problem
• State spaces, successors (actions, next states, costs), start state, goal (test)

Questions to you

• Do you think “how to search faster and accurately” has anything to do with intelligence?