Part 2: Intelligent Agents

Intelligent Agents (IA) - Concept

IA Types

Environment types

IA Behavior

IA Structure
 Mission


To design/create computer programs that have
some intelligence/ can do some intelligent tasks/ or
can do tasks that require some intelligence.

CISY 422_BBIT 333 2

Mars Rover

Autonomous device:
 Exploring Mars, sending pictures to earth, camera, obstacle
sensor, wheels, steering, turning,..

CISY 422_BBIT 333 3

What is an (Intelligent) Agent?

An over-used, over-loaded, and misused term.


Anything that can be viewed as perceiving its environment
through sensors and acting upon that environment through its
effectors to maximize progress towards its goals.


PAGE (Percepts, Actions, Goals, Environment)


Task-specific & specialized: well-defined goals and
environment


The notion of an agent is meant to be a tool for analyzing
systems, not an absolute characterization that divides the
world into agents and non-agents. Much like, e.g., object-
oriented vs. imperative program design approaches.
CISY 422_BBIT 333 4
 Intelligent Agents


Agents interact with environments through sensors
and effectors

CISY 422_BBIT 333 5

Agent Function

a = F(p)
where p is the current percept, a is the action carried
out, and F is the agent function
F maps percepts to actions
F: P  A
where P is the set of all percepts, and A is the set of
all actions
In general, an action may depend on all
percepts observed so far, not just the current
percept, so…
6
Agent Function Refined

ak = F(p0 p1 p2 …pk)
where p0 p1 p2 …pk is the sequence of percepts
observed to date, ak is the resulting action carried
out
F now maps percept sequences to actions
F: P*  A

7
Structure of Agents

Agent = architecture + program

architecture
device with sensors and actuators
e.g., A robotic car, a camera, a PC, …
program
implements the agent function on the architecture

8
Intelligent Agents and Artificial Intelligence

Human mind as network of thousands or millions of agents all
working in parallel. To produce real artificial intelligence, this
school holds, we should build computer systems that also
contain many agents and systems for arbitrating among the
agents' competing results.
Agency

Distributed decision-making
and control

sensors

effectors

Challenges:
 Action selection: What next action
to choose
 Conflict resolution

CISY 422_BBIT 333 9

Agent Research Areas
We can split agent research into two main strands:


Distributed Artificial Intelligence (DAI) – Multi-Agent Systems
(MAS) (1980 – 1990)


Much broader notion of "agent" (1990’s – present)
 interface, reactive, mobile, information

CISY 422_BBIT 333 10

A Windscreen Agent
How do we design a agent that can wipe the
windscreens when needed?


Goals?

Percepts ?

Sensors?

Effectors ?

Actions ?

Environment ?

CISY 422_BBIT 333 11

A Windshield Wiper Agent (Cont’d)

Goals: To keep windscreens clean and maintain
good visibility

Percepts: Raining, Dirty, Clear

Sensors: Camera (moist sensor)

Effectors: Wipers (left, right, back)

Actions: Off, Slow, Medium, Fast

Environment: Nairobi city, pot-holed roads,
highways, bundus, weather …

CISY 422_BBIT 333 12

Towards Autonomous Vehicles

CISY 422_BBIT 333 13

Interacting Agents
Collision Avoidance Agent (CAA)

Goals: Avoid running into obstacles

Percepts ?

Sensors?

Effectors ?

Actions ?

Environment: River Road, Nairobi

Lane Keeping Agent (LKA)

• Goals: Stay in current lane
• Percepts ?
• Sensors?
• Effectors ?
• Actions ?
• Environment: Highway
CISY 422_BBIT 333 14
Interacting Agents

Collision Avoidance Agent (CAA)


Goals: Avoid running into obstacles

Percepts: Obstacle distance, velocity, trajectory

Sensors: Vision, proximity sensing

Effectors: Steering Wheel, Accelerator, Brakes, Horn, Headlights

Actions: Steer, speed up, brake, blow horn, signal (headlights)

Environment: River Road, Nairobi

Lane Keeping Agent (LKA)

• Goals: Stay in current lane
• Percepts: Lane center, lane boundaries
• Sensors: Vision
• Effectors: Steering Wheel, Accelerator, Brakes
• Actions: Steer, speed up, brake
• Environment: Highway
CISY 422_BBIT 333 15
The Right Thing = The Rational Action

Rational Action: The action that maximizes the expected
value of the performance measure given the percept sequence
to date

 Rational = Best ?
 Rational = Optimal ?
 Rational = Omniscience ?
 Rational = Successful ?

CISY 422_BBIT 333 16

The Right Thing = The Rational Action

Rational Action: The action that maximizes the expected
value of the performance measure given the percept
sequence to date

 Rational = Best Yes, to the best of its knowledge

 Rational = Optimal Yes, to the best of its abilities (incl. its
constraints)
 Rational  Omniscience
 Rational  Successful

CISY 422_BBIT 333 17

Behavior and performance of IAs

Perception (sequence) to Action Mapping: f : P*  A
 Ideal mapping: specifies which actions an agent ought to
take at any point in time
 Description: Look-Up-Table,..


Performance measure: a subjective measure to characterize
how successful an agent is (e.g., speed, power usage,
accuracy, money, etc.)


(degree of) Autonomy: to what extent is the agent able to
make decisions and actions on its own?

CISY 422_BBIT 333 18

Look up table

Distance Action

10 No action obstacle
sensor
5 Turn left 30 agent
degrees

2 Stop
How is an Agent different from other software?


Agents are autonomous, that is, they act on behalf of
the user


Agents contain some level of intelligence, from fixed
rules to learning engines that allow them to adapt to
changes in the environment


Agents don't only act reactively, but sometimes also
pro-actively
How is an Agent different from other software?


Agents have social ability, that is, they communicate
with the user, the system, and other agents as required


Agents may also cooperate with other agents to carry
out more complex tasks than they themselves can handle


Agents may migrate from one system to another to
access remote resources or even to meet other agents
Specifying the Task Environment

PEAS
Performance Measure: captures agent’s aspiration
Environment: context, restrictions
Actuators: indicates what the agent can carry out
Sensors: indicates what the agent can perceive

22
 Environment Types

Characteristics
 Accessible vs. inaccessible

An environment is accessible if the sensors detect all aspects
that are relevant to the choice of action.
 Deterministic vs. non-deterministic

If the next state of the environment is completely determined
by the current state and the actions selected by the agents,
then we say the environment is deterministic.
 Episodic vs. non-episodic

In an episodic environment, the agent’s experience is divided
into “episodes.” Each episode consists of the agent perceiving
and then acting.
 Static vs. dynamic

If the environment can change while an agent is deliberating,
then we say the environment is dynamic for that agent;
otherwise it is static.
CISY 422_BBIT 333 23
Environment Types

Characteristics
 Discrete vs. continuous

If there are a limited number of distinct, clearly defined
percepts and actions we say that the environment is discrete.
 Hostile vs. friendly

This depends on the agent perception.

CISY 422_BBIT 333 24

 Environment types

Environment Accessibl Deterministi Episodic Static Discrete

e c
Operating
System

Virtual
Reality
Office
Environment

Mars

CISY 422_BBIT 333 25

 Environment types

Environment Accessibl Determinis Episodic Static Discrete

e tic
Operating Yes Yes No No Yes
System
Virtual
Reality
Office
Environment
Mars
 Environment types

Environment Accessibl Determinis Episodic Static Discrete

e tic
Operating Yes Yes No No Yes
System
Virtual Yes Yes Yes/no No Yes/no
Reality
Office
Environment
Mars
 Environment types

Environment Accessibl Determinis Episodic Static Discrete

e tic
Operating Yes Yes No No Yes
System
Virtual Yes Yes Yes/no No Yes/no
Reality
Office No No No No No
Environment
Mars
 Environment types

Environment Accessib Deterministi Episodic Static Discrete

le c
Operating Yes Yes No No Yes
System
Virtual Yes Yes Yes/No No Yes/No
Reality
Office No No No No No
Environment
Mars No Semi No Semi No

•The environment types largely determine the agent design.

CISY 422_BBIT 333 29

Structure of Intelligent Agents

Agent = architecture + program


Agent program: the implementation of f : P*  A, the agent’s
perception-action mapping

function: Skeleton-Agent(Percept) returns Action

memory  UpdateMemory(memory, Percept)
Action  ChooseBestAction(memory)
memory  UpdateMemory(memory, Action)
return Action


Architecture: a device that can execute the agent program
(e.g., general-purpose computer, specialized device,
specialized, hardware/software, beobot, etc.)

CISY 422_BBIT 333 30

 Using a look-up-table to encode f : P*  A

Example: Collision Avoidance

obstacle
Sensors: 3 proximity sensors
 Effectors: Steering wheel, Brakes sensors

How to generate?

How large? agent

How to select action?

CISY 422_BBIT 333 31

Using a look-up-table to encode f : P*  A

Example: Collision Avoidance obstacle
 Sensors: 3 proximity sensors sensors
 Effectors: Steering wheel, Brakes


How to generate: for each p  Pl  Pm  Pr agent
generate an appropriate action, a  S  B


How large: size of table = #possible percepts times # possible actions
= |Pl | |Pm| |Pr| |S| |B|

E.g., P = {close, medium, far}3

A = {left, straight, right}  {on, off}
then size of table = 27*3*2 = 162


How to select action? Search.

CISY 422_BBIT 333 32

Agent types

Reflex agents

Reflex agents with internal states

Goal-based agents

Utility-based agents

Learning agents

CISY 422_BBIT 333 33

Agent types


Reflex agents

Reactive: No memory


Reflex agents with internal states

W/o previous state, may not be able to make
decision

E.g. brake lights at night.


Goal-based agents

Goal information needed to make decision
Agent types


Utility-based agents

How well can the goal be achieved (degree of
happiness)


What to do if there are conflicting goals?

Speed and safety


Which goal should be selected if several can be
achieved?
Reflex agents

CISY 422_BBIT 333 36

 Reactive agents

Reactive agents do not have internal symbolic models.

Act by stimulus-response to the current state of the environment.

Each reactive agent is simple and interacts with others in a basic
way.

Complex patterns of behavior emerge from their interaction.


Benefits: robustness, fast response time

Challenges: scalability, how intelligent?
and how do you debug them?

CISY 422_BBIT 333 37

Reflex agents with state

CISY 422_BBIT 333 38

State Management

Reflex agent with state

Incorporates a model of the world

Current state of its world depends on percept
history

Rule to be applied next depends on resulting
state

state’  next-state( state, percept )
action  select-action( state’, rules )

39
Goal-based agents

CISY 422_BBIT 333 40

Incorporating Goals


Rules and “foresight”

Essentially, the agent’s rule set is determined
by its goals

Requires knowledge of future consequences
given possible actions

Can also be viewed as an agent with more complex
state management

Goals provide for a more sophisticated
next-state function

41
Utility-based Agent

42
 Incorporating Performance


May have multiple action sequences that arrive at a
goal

Choose action that provides the best level of
“happiness” for the agent

Utility function maps states to a measure

May include trade offs

May incorporate likelihood measures

43
Learning Agent

44
Incorporating Learning

Can be applied to any of the previous agent types

Agent <-> Performance Element

Learning Element

Causes improvements on agent/ performance
element

Uses feedback from critic

Provides goals to problem generator

45
 Mobile agents

Programs that can migrate from one machine to another.

Execute in a platform-independent execution environment.

Require agent execution environment (places).

Mobility not necessary or sufficient condition for agent hood

Practical but non-functional advantages:
 Reduced communication cost (e.g., from PDA)
 Asynchronous computing (when you are not connected)

Two types:
 One-hop mobile agents (migrate to one other place)
 Multi-hop mobile agents (roam the network from place to
place)

Applications:
 Distributed information retrieval.
 Telecommunication network routing.
CISY 422_BBIT 333 46
 Information agents

Manage the explosive growth of information.

Manipulate or collate information from many distributed
sources.

Information agents can be mobile or static.

Examples:
 BargainFinder comparison shops among Internet stores for CDs
 FIDO the Shopping Doggie (out of service)
 Internet Softbot infers which internet facilities (finger, ftp, gopher)
to use and when from high-level search requests.

Challenge: ontologies for annotating Web pages (e.g., SHOE).

CISY 422_BBIT 333 47

Summary

Intelligent Agents:
 Anything that can be viewed as perceiving its
environment through sensors and acting upon that
environment through its effectors to maximize progress
towards its goals.
 PAGE (Percepts, Actions, Goals, Environment)
 Described as a Perception (sequence) to Action Mapping:
f : P*  A
 Using look-up-table, closed form, etc.


Agent Types: Reflex, state-based, goal-based, utility-based


Rational Action: The action that maximizes the expected
value of the performance measure given the percept sequence
to date

CISY 422_BBIT 333 48