Transcript Algorithms of Artificial Intelligence

Algorithms of Artificial
Intelligence
Lecture 9: Intelligent agents
E. Tyugu
Spring 2003
© Enn Tyugu
1
Intelligent agents
Intelligent agents are software components. They possess some features of
intelligent behavior:
• proactiveness
• understanding of agent communication language (ACL)
• reactivity (ability to make some decisions and to act)
and they may have properties like
• planning ablity
• mobility
• reflection
• perception of environment etc.
In the software engineering community they are also called software agents
and are considered to be objects with proactiveness and ACL.
(Compare agents and objects.)
© Enn Tyugu
2
Proactiveness
Proactiveness is the ability to act without external stimuli. It
can be realized by means of a separate thread performing
the following simple algorithm, and a knowledge base of
proactive actions.
A9.1: while true do
wait(givenInterval);
lookAtClock;
consultKB;
act;
od
© Enn Tyugu
3
How to act in an open world?
•
•
•
•
perceiving the world
affecting the world
having a (rational) model of behavior
having motivations to be fulfilled by implementing corresponding
goals
© Enn Tyugu
4
Basic concepts: Agents
•
•
•
•
•
•
act on behalf of another entities
autonomy
proactiveness
reactivity
decentralized data and control
negotiation, communication, coordination
© Enn Tyugu
5
More definitions
• Distributed Problem Solving (DPS) -considers how the task of solving
a particular problem can be divided among a number of cooperating
modules
• Multi-Agent Systems (MAS) - concerned with behavior of a collection
of autonomous agents aiming in solving a given problem
© Enn Tyugu
6
Simple reactive agent
reactiveAgent() {
while (true) do
state := perceive();
rule :=selectRule(KB,state);
rule.action();
}
}
KB
perceive
Environment
select
act
© Enn Tyugu
7
Agent with internal state
reactiveAgent() {
while (true) do
input := perceive();
rule := selectRule(KB,input,state);
state := update(state,input);
rule.action();
}
}
update
perceive
Environment
state
KB
select
act
© Enn Tyugu
8
Goal-driven agent
planner
KB2
update
perceive
goal
Environment
state
KB1
select
act
© Enn Tyugu
9
BDI
BDI = Beliefs, Desires, Intentions
ACL communication
BDI
?
intentions
planner
KB2
update
perceive
goal
Environment
state
KB1
select
act
© Enn Tyugu
10
Knowledge processing within an agent
Goal
activation
Execution
Planning
Scheduling
Skills
Tasks
Goals
Plans
World
state
© Enn Tyugu
Resources
11
Generic Agent Interpreter - an agent shell
(Y. Shoham)
Initialize mental
state and capabilities
Define rules for making
new commitments
clock
Update mental
state
Representation of
mental state and capability
Execute commitments for
current time
Outgoing messages
© Enn Tyugu
12
Agent finite state machine
SENDING
INACTIVE
ACTIVE
WAITING
RECEIVING
© Enn Tyugu
13
Agent machinery
Event Event
Agent engine
…
Event
EventType1
Handler1
EventType2
Handler2
…
…
Event list
Event description list
(including Event types
and references to
Event handlers)
EventTypeN HandlerN
Event handlers
Handler1
Agent interface
….
HandlerN
A CL port
Models
Sensors/
affectors
Data
© Enn Tyugu
Agent memory
14
Agent Shell Functional Structure
Procedural reflection
manager
Executor
ACL
Communication
block
Goals analyser/synthesiser
Reactive block
Planner
Declarative reflection
manager
Low-level communication
Sensing
Models
Affection
© Enn Tyugu
15
Agent communication languages
(ACL)
There are several ACL-s, the best known are:
– KQML
– FIPA.
The KQML language is based on the speech act theory:
– it gives a message format and message handling protocol
– it has primitives with fixed meaning, called performatives
– it is assumed that the environment for using KQML provides
facilitators - special agents supporting the communication process,
e.g. supporting a name service etc.
© Enn Tyugu
16
KQML statement (message)
A KQML message consists of
• a performative
• its arguments, if any
• message content (not understood in KQML)
• communication (transport and context( information.
Example:
(Ask-one
- performative
:sender customer1
- communication
:content (PRICE VCR ?price)
- content
:reply-with VCR-price
:langugae LPROLOG
- parameters
:ontology USD)
© Enn Tyugu
17
KQML performatives
KQML performatives have the role of commands.
Some KQML performatives are:
– tell, deny, cancel, untell
– evaluate, reply, ask-if, ask-one, ask-about, ask-all
– achieve, advertise, subscribe, monitor, register, unregister
© Enn Tyugu
18
Reflection in agents
• Procedural
• Parametric
• Declarative
© Enn Tyugu
19
Declarative reflection schema 1
Oracle
(planner)
self
daemon
Model of the self and
of the environment
daemon
daemon
© Enn Tyugu
20
Declarative reflection schema 2
Oracle
(planner)
self
Modeling language
daemon
Reflection
manager
Model of the self and
of the environment
daemon
© Enn Tyugu
21
Concept specification language
•
•
•
•
•
Superclass declaration
super C;
- C is a superclass
Component declaration
var A : C;
- A is a new component of class C
Method declaration
rel R : <axiom> <program>; - R is a new method (the name R may be
omitted.)
Equivalence declaration
rel A = B;
- A and B are components with the
same value
Equation declaration
rel e1 = e2;
- e1, e2 are arithmetic expressions which define
a constraint on the variables occurring in them
© Enn Tyugu
22
Translation of specifications
We use a function Sem´ in an expression Sem´(D,w) denoting the set of
formulas (axioms) representing the semantics of a declaration D with
respect to the object w.
Sem(class C : D) =
(
" w. C(w)  Sem´(D,w))  <structural axioms>
- semantics of the class is a set of axioms of the form C(w)  F, where each F
is included into axioms of one of its declarations, plus axioms representing
the structure of the class.
© Enn Tyugu
23
Translation of specifications continued
• Sem´(super C, w) = C(w) – axioms of a superclass are taken without
changes.
• Sem´(var A : C, w) = C(w.A) – a component A of an object w obtains
the name w.A and keeps the properties of the class C given in its
declaration.
• Sem´(rel <axiom> <program> , w) = <axiom instantiated by w> semantics of a method is given by its axiom.
• Sem´(rel X = Y, w) = w.X = w.Y – equality of components is encoded
in the proper way.
© Enn Tyugu
24
Exhibition/shopping center example
•
•
•
class Visitor:
super
var
class Guide:
super
var
class Team:
var
Person;
affiliation : text;
Agent;
id : text;
param : text;
visitor : Visitor;
guide : Guide;
planOfVisit, parameters, state : text;
level, priority : num;
© Enn Tyugu
25
Exhibition/shopping center example
•
•
•
class FirstMeet:
var
guide : any;
visitor : any;
team : Team;
rel intro: guide, visitor -> team.planOfVisit, team.level, team.param {…};
team.guide = guide;
team.visitor = visitor;
class Guide:
super
Agent;
var
id, param : text;
class Team:
var
visitor : Visitor;
guide : Guide;
level, priority : num;
planOfVisit , parameters ,state ,nextstate : text;
© Enn Tyugu
26
Exhibition/shopping center example
•
•
class FirstMeet:
var
guide : any;
visitor : any;
team : Team;
rel
intro: guide, visitor ->
team.planOfVisit, team.level, team.param {…};
team.guide = guide;
team.visitor = visitor;
class Move:
var
team : Team;
exhibitionInfo : any;
nextPlace : any;
rel
next : exhibitionInfo, team.planOfVisit -> nextPlace {…};
init
exhibitionInfo := Expo2XXX();
© Enn Tyugu
27
Exhibition/shopping center example
•
class AtBooth:
super
Agora;
var
booth : any;
time : num;
team : Team;
ready, bye : bool;
alias
state = (time, all.state);
nextstate = (time, all.nextstate);
rel
intro : team, booth -> state {…};
discourse : (state -> nextstate) -> ready {…};
farewell : ready -> bye {…};
© Enn Tyugu
28
Declarations for the PC example
Class
DiscrepancyExist :
var
ListOfPCmemebers: any;
resolveConflict: bool;
paper: Paper;
rel
Conflict: ListOfPCmemebers, paper ->
resolveConflict {…};
© Enn Tyugu
29
Managing reflection
(Exhibition/Shopping center)
Tommy9 : Guide type = Tommy;
MrSmith :Visitor name = ´John´;
act1 : FirstMeet guide = Tommy9, visitor = MrSmith;
team1024 = act1.team;
act2 : Move
team = team1024 ;
act3 : AtBooth booth = act2.nextPlace;
act4 : Move
team = team1024;
act6 : AtBooth booth = Nokia;
…
© Enn Tyugu
30
References
• G. M. O’Hare, N. R. Jennings, eds. (1996) Foundations of Distributed
Artificial Intelligence. John Wiley & Sons.
• Norvig, Russell (2000) Artificial Intelligence: Modern Approach
• P. Maes. (1987). Concepts and Experiments in Computational
Reflection. Proc. ACM Conf. On OOP, Systems, Languages and
Applications, Orlando, p. 147 – 156.
• Y. Shoham. (1997). An Overview of Agent-Oriented Programming. In:
J. M. Bradshaw, ed. Software Agents. AAAI Press/The MIT Press, p.
271 - 290.
• M. Addibpour, E. Tyugu. Declarative reflection tools for agent shells.
Future Generation Computer Systems. July 1996, p. 1 - 12.
© Enn Tyugu
31