Multi-Agent Systems - Summary
Lecture 1 - Introduction
Intelligent Agent Paradigm
● An agent is anything that can be viewed as perceiving its environment through sensors and
acting upon that environment through effectors, but we are interested in automated agents
● Internally, an agent is: agent = architecture + program
● Core business of AI: designing agent architectures & programs
Natural agents
● Animals are agents
○ Can perceive their environment using their eyes, ears, skin (touch), tongue (taste), nose
(smell)
○ Can act upon their environment by their muscle motor systems (moving), mouth
(sounds)
○ Cognitive skills: perception, attention, memory, language, learning, and problem solving
● Human agents
○ Can perceive their environment using their eyes, ears, skin (touch), tongue (taste), nose
(smell)
○ Can act upon their environment by their muscle motor systems (moving), mouth
(sounds)
○ Are very versatile (ability to adapt): can survive in almost any environment on earth
○ Advanced cognitive skills: perception, attention, memory, language, learning, and
problem-solving skills
Robotic Agents
● Can perceive their environment using their cameras, microphones, touch sensors,...
● Can act upon their environment by their motor and sound systems, displays,...
● Are currently not yet versatile: can function in specific contexts
● Do currently not yet have advanced cognitive skills, limited perception, attention, memory,
language, learning and problem-solving skills
Intelligent Agents
● Reactive: ability to receive information and respond
● Pro-active: ability to take the initiative
● Social: ability to communicate and cooperate
● Autonomous: agents control their own processes
Cognitive (-Affective) Agents
● An agent is anything that can be (usefully) viewed as a system that has
○ Beliefs, desires, goals, intentions, plans, expectations, hopes, fears, joy…
Intentional Systems
● First-order:
○ bel(p): the agent believes that p
○ goal(p): the agent has a goal (or wants) that p
1
,Multi-Agent Systems - Summary
● Second-order:
○ bel(a; bel(b,p)): a believes that b believes that p
○ bel(a; goal(b,p)): a believes that b wants that p
○ goal(a; bel(b,p)): a wants that b believes that p
○ goal(a; goal(b,p)): a wants that b wants that p
Notion of Cognitive Agent
● Agents with the following basic capabilities:
1. Event processing: process events like percepts and messages
2. Knowledge representation: process events like percepts and messages. It allows to
maintain a model of the environment and other agents. (e.g. use propositional or FOL, or
Prolog)
3. Decision-making: agent is able to select an action based on its belief, knowledge, and
goals.
● We are not concerned about how to transform observations into symbolic representation. We
abstract from this.
Cognitive state
● The internal state of a cognitive agent is called a cognitive state
● Typically, it includes:
○ Event component
■ Percepts
■ Messages
○ Informational component
■ Knowledge (static)
■ Beliefs (dynamic)
○ Motivational component (what the agent wants to achieve)
■ goals
Environments
● It is very important to emphasize that agents are situated in an environment
● Percepts: agents usually don’t see the real state of the environment but only receive percepts
● Designer: the designer has to process percepts and possibly store them within the agent’s
memory
● Environment-properties: as such it is very important to know the characteristics of an
environment before designing an agents
Properties of environments
● Fully/partially observable: if the environment is not completely observable the agent will need
internal states
● Deterministic/stochastic: deterministic if completely determined by the agent’s action. If the
environment is only partially observable, then it may appear stochastic (while it is
deterministic)
● Static/dynamic: the environment can change while an agent is deliberating
2
,Multi-Agent Systems - Summary
● Discrete/concrete: if there is a limited number of percepts and action the environment is
discrete
● Single/multi-agents: is there just one agent or are there several interacting with each other
Cognitive agents & environments
● For cognitive agents, we take the view that an environment offers controllable entities that are
connected to cognitive agents.
● Possible view:
○ Cognitive agent is the mind
○ Controllable entity is the body
● An action specification designs which actions are available to an agent and when. It is defined
by the environment.
Interaction with environment & agents
● Observation: how can the agent observe its environment?
○ Passive: the agent receives the results of observations without taking any initiative or
control to observe
○ Active: the agent actively initiates and controls which observations it want to perform
● Execution of Actions: The agent is capable of making changes to the state of its environment by
initiating and executing actions.
● Communication with other agents: two directions of communications are distinguished, which
can occur together:
○ Outgoing: is the agent capable of communicating with another agent?
○ Incoming: is the agent capable of receiving communication from another agent?
Cognitive agent programming
● Cognitive agent language: programming language with events, beliefs, goals, actions, plans, …
as first-class citizens
● Key language elements
○ Events received from environment (& agents)
○ Beliefs and goals to represent the environment
○ Actions to
1. Update beliefs, adopt goals,
2. Send messages,
3. Act in environment
○ Plans to structure action
○ Rules to select actions/plans/modules
○ Modules to structure rules & action selections
○ Support for multi-agent systems
● Cognitive stats used for:
○ Representing and reasoning about the environment
○ Deriving a choice of action from beliefs and goals
3
, Multi-Agent Systems - Summary
Prolog
● A logic-based programming language, focused on the description of a problem (and thus not
on how to solve it)
○ Declarative programming vs. imperative/procedural programming
● Prolog is based on a different programming paradigm, and thus requires a different way of
thinking
Imperative vs. Declarative
● Imperative: uses statements that change a program’s state.
○ E.g., all the steps you have to take before ordering a coffee (enter shop, wait in line etc.)
● Declarative: expresses the logic of a computation without describing its control flow.
○ E.g., “A large latte for takeaway, please”
Propositional logic
● A declarative sentence (or proposition) is a statement that is true or false
● Propositional variables p, q, r, …
● Connectives
● Propositional formulas
1. Every propositional variable p, q, r, … is a formula
2. (a) If ϕ is a formula, then so is (￢ϕ)
(b) If ϕ and ψ are formulas, then so are (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ ⊕ ψ), (ϕ → ψ) and
(ϕ ↔ ψ)
● A valuation corresponds to one line in the truth table of a formula.
First-order logic
● Logical structures are indicated as L = (U, S, I), where L is the name of the structure, U is a
universe, S is its signature ad I is an interpretation.
● Universe: the universe of objects about which a first-order logic is formulated. Also called the
domain of discourse
● Signature: the set of non-logical symbols with which expressions about the domain can be
composed.
○ Predicate symbols: per universe you can define your own predicate symbols, e.g., Pk,
Qk, would be k-ary predicate symbols. Propositions are 0-ary predicate symbols.
○ Function symbols: fk, gk are k-ary function symbols. Constants are 0-ary function
symbols.
○ Variables: x,y,...
● Interpretation: how non-logical expressions should be interpreted in the universe
4
Lecture 1 - Introduction
Intelligent Agent Paradigm
● An agent is anything that can be viewed as perceiving its environment through sensors and
acting upon that environment through effectors, but we are interested in automated agents
● Internally, an agent is: agent = architecture + program
● Core business of AI: designing agent architectures & programs
Natural agents
● Animals are agents
○ Can perceive their environment using their eyes, ears, skin (touch), tongue (taste), nose
(smell)
○ Can act upon their environment by their muscle motor systems (moving), mouth
(sounds)
○ Cognitive skills: perception, attention, memory, language, learning, and problem solving
● Human agents
○ Can perceive their environment using their eyes, ears, skin (touch), tongue (taste), nose
(smell)
○ Can act upon their environment by their muscle motor systems (moving), mouth
(sounds)
○ Are very versatile (ability to adapt): can survive in almost any environment on earth
○ Advanced cognitive skills: perception, attention, memory, language, learning, and
problem-solving skills
Robotic Agents
● Can perceive their environment using their cameras, microphones, touch sensors,...
● Can act upon their environment by their motor and sound systems, displays,...
● Are currently not yet versatile: can function in specific contexts
● Do currently not yet have advanced cognitive skills, limited perception, attention, memory,
language, learning and problem-solving skills
Intelligent Agents
● Reactive: ability to receive information and respond
● Pro-active: ability to take the initiative
● Social: ability to communicate and cooperate
● Autonomous: agents control their own processes
Cognitive (-Affective) Agents
● An agent is anything that can be (usefully) viewed as a system that has
○ Beliefs, desires, goals, intentions, plans, expectations, hopes, fears, joy…
Intentional Systems
● First-order:
○ bel(p): the agent believes that p
○ goal(p): the agent has a goal (or wants) that p
1
,Multi-Agent Systems - Summary
● Second-order:
○ bel(a; bel(b,p)): a believes that b believes that p
○ bel(a; goal(b,p)): a believes that b wants that p
○ goal(a; bel(b,p)): a wants that b believes that p
○ goal(a; goal(b,p)): a wants that b wants that p
Notion of Cognitive Agent
● Agents with the following basic capabilities:
1. Event processing: process events like percepts and messages
2. Knowledge representation: process events like percepts and messages. It allows to
maintain a model of the environment and other agents. (e.g. use propositional or FOL, or
Prolog)
3. Decision-making: agent is able to select an action based on its belief, knowledge, and
goals.
● We are not concerned about how to transform observations into symbolic representation. We
abstract from this.
Cognitive state
● The internal state of a cognitive agent is called a cognitive state
● Typically, it includes:
○ Event component
■ Percepts
■ Messages
○ Informational component
■ Knowledge (static)
■ Beliefs (dynamic)
○ Motivational component (what the agent wants to achieve)
■ goals
Environments
● It is very important to emphasize that agents are situated in an environment
● Percepts: agents usually don’t see the real state of the environment but only receive percepts
● Designer: the designer has to process percepts and possibly store them within the agent’s
memory
● Environment-properties: as such it is very important to know the characteristics of an
environment before designing an agents
Properties of environments
● Fully/partially observable: if the environment is not completely observable the agent will need
internal states
● Deterministic/stochastic: deterministic if completely determined by the agent’s action. If the
environment is only partially observable, then it may appear stochastic (while it is
deterministic)
● Static/dynamic: the environment can change while an agent is deliberating
2
,Multi-Agent Systems - Summary
● Discrete/concrete: if there is a limited number of percepts and action the environment is
discrete
● Single/multi-agents: is there just one agent or are there several interacting with each other
Cognitive agents & environments
● For cognitive agents, we take the view that an environment offers controllable entities that are
connected to cognitive agents.
● Possible view:
○ Cognitive agent is the mind
○ Controllable entity is the body
● An action specification designs which actions are available to an agent and when. It is defined
by the environment.
Interaction with environment & agents
● Observation: how can the agent observe its environment?
○ Passive: the agent receives the results of observations without taking any initiative or
control to observe
○ Active: the agent actively initiates and controls which observations it want to perform
● Execution of Actions: The agent is capable of making changes to the state of its environment by
initiating and executing actions.
● Communication with other agents: two directions of communications are distinguished, which
can occur together:
○ Outgoing: is the agent capable of communicating with another agent?
○ Incoming: is the agent capable of receiving communication from another agent?
Cognitive agent programming
● Cognitive agent language: programming language with events, beliefs, goals, actions, plans, …
as first-class citizens
● Key language elements
○ Events received from environment (& agents)
○ Beliefs and goals to represent the environment
○ Actions to
1. Update beliefs, adopt goals,
2. Send messages,
3. Act in environment
○ Plans to structure action
○ Rules to select actions/plans/modules
○ Modules to structure rules & action selections
○ Support for multi-agent systems
● Cognitive stats used for:
○ Representing and reasoning about the environment
○ Deriving a choice of action from beliefs and goals
3
, Multi-Agent Systems - Summary
Prolog
● A logic-based programming language, focused on the description of a problem (and thus not
on how to solve it)
○ Declarative programming vs. imperative/procedural programming
● Prolog is based on a different programming paradigm, and thus requires a different way of
thinking
Imperative vs. Declarative
● Imperative: uses statements that change a program’s state.
○ E.g., all the steps you have to take before ordering a coffee (enter shop, wait in line etc.)
● Declarative: expresses the logic of a computation without describing its control flow.
○ E.g., “A large latte for takeaway, please”
Propositional logic
● A declarative sentence (or proposition) is a statement that is true or false
● Propositional variables p, q, r, …
● Connectives
● Propositional formulas
1. Every propositional variable p, q, r, … is a formula
2. (a) If ϕ is a formula, then so is (￢ϕ)
(b) If ϕ and ψ are formulas, then so are (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ ⊕ ψ), (ϕ → ψ) and
(ϕ ↔ ψ)
● A valuation corresponds to one line in the truth table of a formula.
First-order logic
● Logical structures are indicated as L = (U, S, I), where L is the name of the structure, U is a
universe, S is its signature ad I is an interpretation.
● Universe: the universe of objects about which a first-order logic is formulated. Also called the
domain of discourse
● Signature: the set of non-logical symbols with which expressions about the domain can be
composed.
○ Predicate symbols: per universe you can define your own predicate symbols, e.g., Pk,
Qk, would be k-ary predicate symbols. Propositions are 0-ary predicate symbols.
○ Function symbols: fk, gk are k-ary function symbols. Constants are 0-ary function
symbols.
○ Variables: x,y,...
● Interpretation: how non-logical expressions should be interpreted in the universe
4
