CMPUT 366 F20: Representational Dimensions
James Wright & Vadim Bulitko
September 3, 2020
CMPUT 366 F20: Representational Dimensions
1
Lecture Outline
Lecture recordings
Tutorials
Representational dimensions
PM Chapter 1
CMPUT 366 F20: Representational Dimensions 2
Lecture Recordings
About ¨% of the students are attending from outside of Canada, from substantially different time zones
To include the students, I will record the lectures and make the recordings available to them:
the recordings will be available by request only; email me a justification for it attending lectures live and participating in in-class exercises is still the best way to get the most out of the course
do not record the lectures on your side unless you have my permission for it
CMPUT 366 F20: Representational Dimensions 3
Tutorials
Tutorials in the on-line labs
Tentative topics:
a refresher on Python basics
a crash course on Python libraries (e.g., NumPy) a crash course on machine learning with Python
Follow along and attend in-lab problem-solving segments use Google Colaboratory
or use your own hardware with Python 3 and (extra) libraries installed labs start on-line on Monday, September 14th, 5-7:50pm
details to be posted on eClass beforehand
CMPUT 366 F20: Representational Dimensions 4
Rational Agents: Caveats to Ponder On Until Next Class
A rational agent is an entity that acts in an environment to its achieve goals or optimize its preferences
Where is the boundary between an agent and an environment?
Where does the I end and not-I begin? What about agent¡¯s thinking?
Is it acting?
What are the agent¡¯s goals?
in the eye of an observer?
What are the agent¡¯s preferences?
inverse reinforcement learning
https://artint.info/2e/html/ArtInt2e.Ch1.S3.html
CMPUT 366 F20: Representational Dimensions 5
In-class Exercise
Assigned to a break-out room ¡ª that is your team
Consider human society (e.g., a nation or the entire Earth population) as a single rational agent
Collectively discuss:
What is the agent¡¯s environment?
What are the agent¡¯s goals?
What are the agent¡¯s preferences?
You can use audio/video within your break-out room
I will visit (some) break-out rooms and briefly talk to the teams you can talk to me via audio/video in your break-out room
CMPUT 366 F20: Representational Dimensions 6
Representations
Knowledge: Information about a domain useful for solving problems in that domain
To use knowledge, a computational agent needs to encode it into a set of data structures called a representation
Representations are about the environment:
What kinds of states can the world be in? How should we denote them?
What kind of information do we get about the current and past states? How certain can our beliefs be?
Dynamics: How does the environment change based on our actions? Are the changes deterministic or stochastic?
https://artint.info/2e/html/ArtInt2e.Ch1.S3.html
CMPUT 366 F20: Representational Dimensions 7
Representations: A Wish List
Rich enough to express all of the knowledge necessary for solving the task As close to the problem as possible: compact, natural, maintainable,
transparent
Tractable: amenable to efficient computation
Learnable: should be able to acquire new knowledge from data, past experiences, people
Able to trade off accuracy and computation time
CMPUT 366 F20: Representational Dimensions 8
In-class Exercise
Consider a pathfinding agent operating on a grid
In your team, come up with its representation of a pathfinding problem
Explain how the agent can: Use it to solve the problem
Why it is rich enough to encode all such knowledge
Why it allows for an efficient computation How would agent learn it?
How can it trade off accuracy and computation time?
https://www.growingwiththeweb.com/2012/06/ a- pathfinding- algorithm.html
CMPUT 366 F20: Representational Dimensions
9
Primary Dimensions
We will classify domains by three main dimensions: Uncertainty: deterministic vs. stochastic settings Interaction: online vs. offline interaction
Number of agents: single vs. multiple agents
CMPUT 366 F20: Representational Dimensions 10
Uncertainty
Multiple aspects of an environment may be deterministic (no randomness) or stochastic (some randomness)
Observations and state (¡°sensing uncertainty¡±)
Fully observable: observations directly determine state
Partially observable: many possible states for same observations; or observations are misleading
Dynamics (¡°effect uncertainty¡±)
Deterministic dynamics: state completely determined by action and prior state Stochastic dynamics: probability distribution over possible states from an action
CMPUT 366 F20: Representational Dimensions 11
Interaction
When does the agent decide what to do?
Offline
Agent determines what to do before interacting with the environment
Online
Agent determines what to do while interacting with the environment
CMPUT 366 F20: Representational Dimensions 12
Number of Agents
Does the agent (need to) explicitly consider other agents?
Single agent
No other agents in the environment
Behaviour of other agents is fixed (part of nature)
Multiple agents
Other agents in the environment, with distinct goals/preferences
Must reason about other agent¡¯s behaviour and reasoning
Other agents¡¯ actions affect agents goals/preferences, and vice versa
CMPUT 366 F20: Representational Dimensions 13
Other Dimensions
Static vs. sequential action
Goal states vs. complex preferences Episodic vs. continuing
State representation scheme Perfect vs. bounded rationality
CMPUT 366 F20: Representational Dimensions 14
Static vs. Sequential Action
How many actions does the agent need to select?
Static: the agent selects a single action Classify an image
Diagnose a disease based on symptoms Recommend a driving route
Sequential: the agent needs to take a sequence of actions Participate in an automated negotiation
Choose a series of tests to diagnose a patient Navigate through an environment
Can we convert sequential to static?
CMPUT 366 F20: Representational Dimensions 15
Goals vs. Preferences
How complicated a goal is the agent trying to achieve?
Goal: A simple desired condition
Maintenance goal: Keep some already-true condition true in all visited states Achievement goal: Condition should be true in final state
Robot trying to deliver banana to Sam without hurting anyone or making a mess
Preferences: Varying desirability of different outcomes, trade-offs Ordinal preferences: Only the ordering of outcomes is important Cardinal preferences: Magnitude of preference also matters
CMPUT 366 F20: Representational Dimensions 16
Knowledge Given vs. Knowledge Learned
How much does the agent know about the world in advance?
The agent has a model of the world before it acts received from the user
innate/built-in
The agent must learn how the world works from data
from experience
often still starts with some prior knowledge
CMPUT 366 F20: Representational Dimensions 17
State Representation
How does the agent describe the world?
Enumerate every possible state of the world
pathfinding? chess?
Factor each state into features may or may not be observable
2¨ binary features can represent over a million states features in pathfinding?
features in chess?
CMPUT 366 F20: Representational Dimensions 18
Episodic vs. Continuing
Is the task ever done?
Episodic: The agent eventually reaches a final state
pathfinding?
chess?
history of human kind?
Continuing: The agent keeps acting forever
pathfinding?
chess?
history of human kind?
Conversion
Future discounting Planning horizon
CMPUT 366 F20: Representational Dimensions 19
Perfect Rationality vs. Bounded Rationality
Does the agent have bounds on its cognitive ability?
Perfect rationality: The agent can derive the best course of action without accounting for computational limitations
pathfinding?
chess?
history of human kind?
Bounded rationality: Agent decides on best action that it can find within its computational limitations
pathfinding?
chess?
history of human kind?
Does perfect rationality really exist?
Anytime algorithm: Solution quality improves with time
CMPUT 366 F20: Representational Dimensions 20
Recap and In-class Exercise: Dimensions
In your team fill out this table:
Dimension
Static vs. sequential action Goals vs. complex preferences Episodic vs. continuing
State representation scheme Perfect vs. bounded rationality Uncertainty: states/dynamics Interaction: offline vs online Number of agents
I will talk to teams
Grid pathfinding
Chess
History of human kind
CMPUT 366 F20: Representational Dimensions
21
Summary
Formal representation of an environment is essential for building agents Many representations are possible for the same environment
Different representations are useful for different solutions
We can usefully classify environments and representations according to a number of dimensions
Certain properties call for certain AI techniques
CMPUT 366 F20: Representational Dimensions 22