1 of 39

Intelligent Agents

​

CHAPTER 2

Oliver Schulte

Summer2011

2 of 39

�Course structure

Artificial Intelligence a modern approach

2

3 of 39

�Course structure

Artificial Intelligence a modern approach

3

​

Types of Work

​

​

%

​

Semester

50%

Independent assignments (1 time )

10%

Practical sessions

20%

Mid-term assessment (1 time)

20%

Final examination

50%

4 of 39

Outline

  • Agents and environments
  • Rationality
  • PEAS (Performance measure, Environment, Actuators, Sensors)
  • Environment types
  • Agent types

Artificial Intelligence a modern approach

4

5 of 39

Agents

  • An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators

​

  • Human agent:
    • eyes, ears, and other organs for sensors;
    • hands, legs, mouth, and other body parts for actuators

​

  • Robotic agent:
    • cameras and infrared range finders for sensors
    • various motors for actuators

Artificial Intelligence a modern approach

5

6 of 39

Agents and environments

​

​

​

  • The agent function maps from percept histories to actions:

[f: P* 🡪 A]�

  • The agent program runs on the physical architecture to produce f
  • agent = architecture + program

Artificial Intelligence a modern approach

6

7 of 39

Vacuum-cleaner world

​

  • Percepts: location and contents, e.g., [A,Dirty]
  • Actions: Left, Right, Suck, NoOp
  • Agent’s function 🡪 look-up table
    • For many agents this is a very large table

Artificial Intelligence a modern approach

7

Demo: http://www.ai.sri.com/~oreilly/aima3ejava/aima3ejavademos.html

8 of 39

Rational agents

  • Rationality
    • Performance measuring success
    • Agents prior knowledge of environment
    • Actions that agent can perform
    • Agent’s percept sequence to date

​

  • Rational Agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.�

Artificial Intelligence a modern approach

8

9 of 39

Rationality

  • Rational is different from omniscience
    • Percepts may not supply all relevant information
    • E.g., in card game, don’t know cards of others.

​

  • Rational is different from being perfect
    • Rationality maximizes expected outcome while perfection maximizes actual outcome.

​

Artificial Intelligence a modern approach

9

10 of 39

Autonomy in Agents

  • Extremes
    • No autonomy – ignores environment/data
    • Complete autonomy – must act randomly/no program
  • Example: baby learning to crawl
  • Ideal: design agents to have some autonomy
    • Possibly become more autonomous with experience

The autonomy of an agent is the extent to which its

behaviour is determined by its own experience,

rather than knowledge of designer.

11 of 39

PEAS

  • PEAS: Performance measure, Environment, Actuators, Sensors

​

  • Must first specify the setting for intelligent agent design

​

  • Consider, e.g., the task of designing an automated taxi driver:
    • Performance measure: Safe, fast, legal, comfortable trip, maximize profits

​

    • Environment: Roads, other traffic, pedestrians, customers

​

    • Actuators: Steering wheel, accelerator, brake, signal, horn

​

    • Sensors: Cameras, sonar, speedometer, GPS, odometer, engine sensors, keyboard

Artificial Intelligence a modern approach

11

12 of 39

PEAS

  • Agent: Part-picking robot
  • Performance measure: Percentage of parts in correct bins
  • Environment: Conveyor belt with parts, bins
  • Actuators: Jointed arm and hand
  • Sensors: Camera, joint angle sensors

Artificial Intelligence a modern approach

12

13 of 39

PEAS

  • Agent: Interactive English tutor
  • Performance measure: Maximize student's score on test
  • Environment: Set of students
  • Actuators: Screen display (exercises, suggestions, corrections)
  • Sensors: Keyboard

Artificial Intelligence a modern approach

13

14 of 39

Environment types

  • Fully observable (vs. partially observable)
  • Deterministic (vs. stochastic)
  • Episodic (vs. sequential)
  • Static (vs. dynamic)
  • Discrete (vs. continuous)
  • Single agent (vs. multiagent):

Artificial Intelligence a modern approach

14

15 of 39

Fully observable (vs. partially observable)

  • Is everything an agent requires to choose its actions available to it via its sensors? Perfect or Full information.
    • If so, the environment is fully accessible
  • If not, parts of the environment are inaccessible
    • Agent must make informed guesses about world.
  • In decision theory: perfect information vs. imperfect information.

​

Artificial Intelligence a modern approach

15

Cross Word

Backgammon

Taxi driver

Part picking robot

Poker

Image analysis

Fully

Fully

Fully

Partially

Partially

Partially

16 of 39

Deterministic (vs. stochastic)

  • Does the change in world state
    • Depend only on current state and agent’s action?
  • Non-deterministic environments
    • Have aspects beyond the control of the agent
    • Utility functions have to guess at changes in world

​

Artificial Intelligence a modern approach

16

Cross Word

Backgammon

Taxi driver

Part picking robot

Poker

Image analysis

Cross Word

Backgammon

Taxi driver

Part

Poker

Image analysis

Deterministic

Deterministic

Stochastic

Stochastic

Stochastic

Stochastic

17 of 39

Episodic (vs. sequential):

  • Is the choice of current action
    • Dependent on previous actions?
    • If not, then the environment is episodic
  • In non-episodic environments:
    • Agent has to plan ahead:
      • Current choice will affect future actions

​

Artificial Intelligence a modern approach

17

Cross Word

Backgammon

Taxi driver

Part picking robot

Poker

Image analysis

Sequential

Sequential

Sequential

Sequential

Episodic

Episodic

18 of 39

Static (vs. dynamic):

  • Static environments don’t change
    • While the agent is deliberating over what to do
  • Dynamic environments do change
    • So agent should/could consult the world when choosing actions
    • Alternatively: anticipate the change during deliberation OR make decision very fast
  • Semidynamic: If the environment itself does not change with the passage of time but the agent's performance score does.

​

Artificial Intelligence a modern approach

18

Cross Word

Backgammon

Taxi driver

Part picking robot

Poker

Image analysis

Static

Static

Static

Dynamic

Dynamic

Semi

Another example: off-line route planning vs. on-board navigation system

19 of 39

Discrete (vs. continuous)

  • A limited number of distinct, clearly defined percepts and actions vs. a range of values (continuous)

Artificial Intelligence a modern approach

19

Cross Word

Backgammon

Taxi driver

Part picking robot

Poker

Image analysis

Discrete

Discrete

Discrete

Conti

Conti

Conti

20 of 39

Single agent (vs. multiagent):

  • An agent operating by itself in an environment or there are many agents working together

Artificial Intelligence a modern approach

20

Cross Word

Backgammon

Taxi driver

Part picking robot

Poker

Image analysis

Single

Single

Single

Multi

Multi

Multi

21 of 39

Summary.

Artificial Intelligence a modern approach

Observable

Deterministic

Static

Episodic

Agents

Discrete

Cross Word

Backgammon

Taxi driver

Part picking robot

Poker

Image analysis

Deterministic

Stochastic

Deterministic

Stochastic

Stochastic

Stochastic

Sequential

Sequential

Sequential

Sequential

Episodic

Episodic

Static

Static

Static

Dynamic

Dynamic

Semi

Discrete

Discrete

Discrete

Conti

Conti

Conti

Single

Single

Single

Multi

Multi

Multi

Fully

Fully

Fully

Partially

Partially

Partially

22 of 39

Choice under (Un)certainty

Artificial Intelligence a modern approach

22

Fully Observable

Deterministic

Certainty: Search

Uncertainty

no

yes

yes

no

23 of 39

Agent types

  • Four basic types in order of increasing generality:
    • Simple reflex agents
    • Reflex agents with state/model
    • Goal-based agents
    • Utility-based agents
    • All these can be turned into learning agents
    • http://www.ai.sri.com/~oreilly/aima3ejava/aima3ejavademos.html

Artificial Intelligence a modern approach

23

24 of 39

Simple reflex agents

Artificial Intelligence a modern approach

24

25 of 39

Simple reflex agents

  • Simple but very limited intelligence.
  • Action does not depend on percept history, only on current percept.
  • Therefore no memory requirements.
  • Infinite loops
    • Suppose vacuum cleaner does not observe location. What do you do given location = clean? Left of A or right on B -> infinite loop.
    • Fly buzzing around window or light.
    • Possible Solution: Randomize action.
    • Thermostat.
  • Chess – openings, endings
    • Lookup table (not a good idea in general)
      • 35100 entries required for the entire game

​

Artificial Intelligence a modern approach

25

26 of 39

States: Beyond Reflexes

  • Recall the agent function that maps from percept histories to actions:

[f: P* 🡪 A]

  • An agent program can implement an agent function by maintaining an internal state.
  • The internal state can contain information about the state of the external environment.
  • The state depends on the history of percepts and on the history of actions taken:

[f: P*, A*🡪 S 🡪A] where S is the set of states.

  • If each internal state includes all information relevant to information making, the state space is Markovian.

​

Artificial Intelligence a modern approach

26

27 of 39

States and Memory: Game Theory

  • If each state includes the information about the percepts and actions that led to it, the state space has perfect recall.
  • Perfect Information = Perfect Recall + Full Observability + Deterministic Actions.

Artificial Intelligence a modern approach

27

28 of 39

Model-based reflex agents

Artificial Intelligence a modern approach

28

  • Know how world evolves
    • Overtaking car gets closer from behind
  • How agents actions affect the world
    • Wheel turned clockwise takes you right

​

  • Model base agents update their state

29 of 39

Goal-based agents

  • knowing state and environment? Enough?
    • Taxi can go left, right, straight
  • Have a goal
    • A destination to get to
  • Uses knowledge about a goal to guide its actions
    • E.g., Search, planning

​

​

Artificial Intelligence a modern approach

29

30 of 39

Goal-based agents

Artificial Intelligence a modern approach

30

​

​

  • Reflex agent breaks when it sees brake lights. Goal based agent reasons
    • Brake light -> car in front is stopping -> I should stop -> I should use brake

31 of 39

Utility-based agents

  • Goals are not always enough
    • Many action sequences get taxi to destination
    • Consider other things. How fast, how safe…..
  • A utility function maps a state onto a real number which describes the associated degree of “happiness”, “goodness”, “success”.
  • Where does the utility measure come from?
    • Economics: money.
    • Biology: number of offspring.
    • Your life?

Artificial Intelligence a modern approach

31

32 of 39

Utility-based agents

Artificial Intelligence a modern approach

32

33 of 39

Learning agents

Artificial Intelligence a modern approach

33

  • Performance element is what was previously the whole agent
    • Input sensor
    • Output action
  • Learning element
    • Modifies performance element.

34 of 39

Learning agents

Artificial Intelligence a modern approach

34

  • Critic: how the agent is doing
    • Input: checkmate?
    • Fixed

​

  • Problem generator
    • Tries to solve the problem differently instead of optimizing.
    • Suggests exploring new actions -> new problems.

​

​

​

35 of 39

Learning agents(Taxi driver)

    • Performance element
      • How it currently drives
    • Taxi driver Makes quick left turn across 3 lanes
      • Critics observe shocking language by passenger and other drivers and informs bad action
      • Learning element tries to modify performance elements for future
      • Problem generator suggests experiment out something called Brakes on different Road conditions
    • Exploration vs. Exploitation
      • Learning experience can be costly in the short run
      • shocking language from other drivers
      • Less tip
      • Fewer passengers

​

​

Artificial Intelligence a modern approach

35

36 of 39

The Big Picture: AI for Model-Based Agents

Action

Artificial Intelligence a modern approach

36

Learning

Knowledge

Logic

Probability

Heuristics

Inference

Planning

Decision Theory

Game Theory

Reinforcement Learning

Machine Learning

Statistics

37 of 39

The Picture for Reflex-Based Agents

Action

Artificial Intelligence a modern approach

37

Learning

Reinforcement Learning

  • Studied in AI, Cybernetics, Control Theory, Biology, Psychology.

38 of 39

Discussion Question

  • Model-based behaviour has a large overhead.
  • Our large brains are very expensive from an evolutionary point of view.
  • Why would it be worthwhile to base behaviour on a model rather than “hard-code” it?
  • For what types of organisms in what type of environments?

​

Artificial Intelligence a modern approach

38

39 of 39

Summary

  • Agents can be described by their PEAS.
  • Environments can be described by several key properties: 64 Environment Types.
  • A rational agent maximizes the performance measure for their PEAS.
  • The performance measure depends on the agent function.
  • The agent program implements the agent function.
  • 3 main architectures for agent programs.
  • In this course we will look at some of the common and useful combinations of environment/agent architecture.

Artificial Intelligence a modern approach

39