Transcript Intro to Multi-Agent Systems - Computer Science & Engineering

Computer Science & Engineering, University of Nevada, Reno
CS483/683 - AI Programming
Multi-Agent Systems:
Algorithmic, Game-theoretic and Logical Foundations
Lecture 1:
Introduction to
Multi-Agent Systems
19 January 2010
Instructor: Kostas Bekris
MAS
What are multi-agent systems
Very vague definition:
A system composed of multiple interacting intelligent agents
Multiple?
Intelligent Agent?
Interacting?
MAS
Intelligent Agents
How can we fully describe an AI problem?
MAS
Multiple Interacting Agents
MAS
Forms of Interaction
Treat other agents similarly to the environment:
• Sensing and observing the behavior of other agents
• Acting upon other agents
Aspects of interaction in the field of multi-agent systems:
• Reason about the decision-making process of other agents
• Communication
• Respect predefined “social laws” and protocols of interaction
- how can a team of agents make fair decisions (e.g., voting schemes)
MAS
Agent Relations
Multi-Agent System
Cooperative Agents
(optimize a
common utility)
Non-cooperative Agents
(separate utilities)
Coalitional Agents
(e.g. opposing teams
of agents)
Competing Agents
(e.g., opposing utilities)
Agents with
diverging interests
MAS
Types of Problems
Agent Design
• How to design an agent that collaborates with other agents to solve a
common task?
• How to design an agent that competes with other agents so as to be the
winner?
• How to design an agent that operates efficiently in an environment where
multiple other agents operate with divergent interests?
Mechanism Design
• How to design the entire system so that a common utility function is
optimized even when each agent is “strategic” (i.e., aims to optimize its
own utility?)
MAS
Topics of Research in MAS
Agent-oriented Software Engineering
Beliefs, Desired and Intentions (BDI)
Cooperation and Coordination
Organization
Communication
Negotiation
Distributed Problem Solving
Multi-Agent Learning
Scientific Communities
Dependability and Fault-Tolerance
MAS
Example Applications
Autonomous Physical Devices
• Multi-robot teams
• Coordinated Defense / Space Exploration Systems
• Sensor Networks
• Transportation and Traffic
Simulation Environments
• Computer Games
• Scientific Simulation
Networking, Mobile Technologies and the Internet
• Automatic and Dynamic Load Balancing
• Self-healing networks
Financial / Economics problems
• Pricing, accounting and logistics
• Bidding mechanisms, negotiations, e-commerce, electricity/energy
MAS
Why do we need MAS?
Ubiquity
• Send sensors and robots everywhere
Fault-tolerance
• Make many small, cheap devices, instead of one large, expensive one
• If a single device fails, the system may continue operating
The real world is a huge Multi-Agent System
• We might have to simulate real-world MAS
• Or we might desire to exercise some control over them
For fun
• Computer games and games in general
For profit
• You have to compete to succeed
• And you have to understand the underlying MAS to be a good competitor
MAS
Objections to MAS
Isn’t it all just Distributed Systems / Networking?
• Systems can be self-interested
Isn’t is all just Artificial Intelligence?
• Communication and social aspects were typically ignored in classical AI
Isn’t it all just Economics / Game Theory?
• We must also come with algorithmic solutions to game theoretic
problems
• Not all assumptions in Game Theory are always true (e.g., “perfect
market”)
Isn’t it all Social Science?
• Artificial societies do not have to be built exactly like human and
biological societies
MAS
Class Overview
∞
a
Intro to Multi-Agent Systems
Distributed Path Planning
∞
2
d
1
∞ s
Distributed Constraint Satisfaction
2
1
3
1
3
c
b
∞
t 0
1
2
∞
Distributed Constraint Optimization
• Belief Propagation
• ADOPT
• Auctions
{red, blue, green}
≠
Coordination through Social Laws
and protocols
≠
≠
{red, blue, green} {red, blue, green}
MAS
Class Overview
Husband
Games in Normal Form
• Two-player, zero-sum games
• General-sum games
• Nash equilibria and strategies
Wife
Games in Extensive Form
• Perfect-Information Games
• Imperfect Information
• Behavioral Strategies
Richer representations of games
• Bayesian games
• Communication and Signaling games
Multi-agent Resource Allocation
• Auctions
Lethal
Weapon
Wondrous
Love
Lethal
Weapon
2, 1
0, 0
Wondrous
Love
0, 0
1, 2
Early March:
Proposal Presentation
and Report
Late April:
Final Presentation
and Report