CISC 887: Internet Information Gathering
ORGANIZATIONS
Sachin Kamboj
Outline
 Need for organizations
 What is an organization?
 Organizational structure
 Organizational paradigms
 Hierarchies
 Holarchies
 Coalitions
 Teams
 Societies
 Markets
 Case Study
Need for organizations
 Goal:
Design a multiagent system to solve a
problem
For example:
Information gathering
Biological workflow enactment
Distributed vehicle monitoring
Hospital scheduling
Insert your favorite application here
Need for organizations
 System needs to be designed at two levels:
 Micro-architecture (Internal architecture)
 Type of agents
 Simple reflex agents
 Model-based reflex agents
 Goal-based agents
 Utility-based agents
 Learning agents
 Type of reasoning
 Internal problem representation
 Macro-architecture
 Focus of rest of this talk!!!
Need for organizations
 Macro-architecture level:
 Task structure
 Breakup of problem into subgoals
 Dependencies between methods
 Number of agents needed
 Task and resource allocation
 Coordination mechanism
 Macro-architecture design involves:
 ORGANIZATION
 Creating an organizational structure
 Instantiating the structure
Example task structure
From Lesser et. al.: Evolution of TAEMS/GPGP
domain independent coordination framework
What is an organization?
 No universally accepted definition
 Organizations emerge whenever agents work together
in a shared environment. Organizations reflect the
structure of the interactions of the participating agents
and are engaged in tasks and goal oriented behavior.
 Singh.05
 Organizations are a consciously coordinated social
entity, with a relatively identifiable boundary, that
functions on a relatively continuous basis to achieve a
common goal or a set of goals.
 Robbins.89
What is an organization?
 A long-term commitment made by the
agents to a particular way of handling the
cooperative tasks.
 So and Durfee.93
 Something that binds agents together to
achieve effective coordination towards
some common goal.
Barber.01
What is an organization?
 Organizations (adapted from Carley and Gasser.99):
 are composed of cooperative agents working together towards
the achievement of some common goal
 goal directed
 engaged in one or more tasks/activities
 allow the effective coordination of agent activities towards the
achievement of their common goals
 are reasonably long term in duration:
 having knowledge, culture, memories, history, and capabilities
distinct from any single agent
 able to affect and be affected by the environment
 are characterized by an organizational structure
 having legal standing distinct from that of individual agents
Organizational structure
 Consists of:
 roles
 parts played by the agents in the solution to the problem
 reflect long term commitments made by the agents in
question to a certain course of action
 relationships
 coordination relationships between subparts of a problem
 Is used to:
 limit the scope of interactions
 reduce or manage uncertainty
 increase redundancy
 provide strength in numbers
Organizational design
 Is there a best way to organize?
 NO!!!
 All ways of organizing are not equally effective
 The organizational structure will depend on:
 The task structure
 The environmental conditions
 Resource availability
 Task deadlines
 Approaches to organization design
 Implicit
 emerges as a result of multiagent interaction
 Explicitly designed
 At design time
 At run-time
Organization paradigms
 Organizational paradigms
may be differentiated
based on:
 Type of multiagent system
 Open system
 Closed system
 Type of agents
 Cooperative
 Competitive
 Duration
 Short term
 Long term










Hierarchies
Holarchies
Coalitions
Teams
Congregations
Societies
Federations
Markets
Matrix
Compund
 (From Horling 05)
Organizational paradigms
 Hierarchies:
 Agents are organized in a tree




like structure
Data travels up.
Control and authority travels
down
Reflect natural task breakup
(HTNs)
Types:
 Simple
 Uniform
 Formation through various
means like contract net
Organizational paradigms
 Holarchies:
 Hierarchical nested structures
 Composed of holons
 groups of agents that can be
viewed as a single entity (agent)
 part of larger hierarchy
 characterized by partial autonomy
of members
 allows reasoning about individual
holons instead of agents
 easily applied to domains in which
goals can be broken up into
subgoals that can be assigned to
the individual holons
Organizational paradigms
 Coalitions:
 are subsets of agents
 are goal directed
 short-lived
 formed with a purpose in mind
 dissolves when need no longer exists
 characterized by a flat organizational
structure
 coalitions may overlap (agents may be
a member of two or more coalitions)
 agents are self-interested
 incentive for formation:
 value should be super-additive
 cost should be sub-additive
Organizational paradigms
 Teams:
 consist of cooperative agents
 that agree to work together
 attempt to maximize the utility of the
whole team
 as opposed to individual agents
 type and pattern of interactions is
arbitrary
 agents take on one or more roles as
required
 agents explicitly reason about and
represent team-level behavior:
 shared goals
 mutual beliefs
 team-level plans
 how actions affect team utility
Organizational paradigms
 Societies:
 long-term organizations
 inherently open
 agents have
 different goals
 varied levels of rationality
 heterogeneous capabilities
 provide a common domain through
which agents can act and interact
 impose constraints on the behavior of
agents
 by using social laws, norms and
conventions
 may themselves be made up of
different ‘organizations’
 allow flexible interactions between the
agents
Organizational paradigms
 Markets:
 Buying agents request/place bids
for a common set of items
 Sellers process bids and determine
the winner
 Multiagent system is a producerconsumer system modeled on realworld market economies.
 agents are competitive
 open systems
 as long as rules are followed
 Applications:
 To sell goods
 Factory Scheduling
 Query Processing
Case study
 A dynamically formed hierarchical agent
organization for a distributed content sharing
system
 Haizheng Zhang and Victor Lesser
University of Massachusetts, Amherst
 Published in proceedings of the International
Conference on Intelligent Agent Technology, 2004
 Investigates the role of an agent organization in a
large scale content retrieval system
Case study
 Each agent has its own collection of documents
 also include a local search engine
 Agents are cooperative
 Any agent may receive a query form the user:
 query is propagated to other agents
 agents perform local search
 agents return relevant documents
 results from multiple agents are merged together
 using some mechanism not discussed
 Unstructured/flat P2P agent network performs poorly
 Propose a multi-level topical hierarchical structure
 System consists of two parts:
 A mechanism for hierarchical organization formation
 A content aware search algorithm
Case study
 Agents have two roles:
 group-mediator
 whether a new agent should be added to the group
 when to reorganize the group
 selection of group members to process a query
 propagation of queries to non-group members
 query-processor
 performs a local search of its collection
 All non-leaf agents take on both roles
 Leaf agent only take on query processor roles
Case study
Case study
 Collection information
 collection
 actual stored documents
 collection model
 a statistical
signature/summary of a
collection
 is propagated to other
agents
 So that other agents
know what info is
available
 Local search engine
 searches for relevant
documents in the
collection
Case study
 Control unit
 accepts user queries
 decides whether queries
should be processed by one or
more group members
 determine order of other
agents/groups that the query
should be forwarded to
 Agent View
 contains information about
the existence and structure of
other agents in the network
 also contains collection
models of the other agents
Case study
 Topic-based hierarchical structure
 Content Group:
 A set of agents that store collections on the same topic
 Consist of:
 A mediator
 All agents which connect to the mediator, directly or indirectly
through upward links
Case study
Hierarchy Generation
Join?
Not Accept!
Join?
E
B
A
Not Accept!
D
Join?
C
Not Accept!
Scenario 1: Agent E joins the system as a top level mediator
Case study
Hierarchy Generation
Join?
Not Accept!
B
E
Join?
Group Invitation!
F
A
D
Join?
Not Accept!
C
F
Scenario 2: Agent F joins the group led by agent E
Case study
Hierarchy Generation
Join?
Join?
B
E
I
Group
Merge
Invitation!
Request
A
Join?
C
Merged
G
I
D
Join?
F
H
Group
Invitation!
G
Scenario 3: Agent joins a top-level mediator (E) that is fully loaded
Case study
Searching
A
B
E
C
D
F
G
H
Query
I
J
K
Phase 1: Propagation of query to top level mediators and similarity
calculation
Case study
Searching
A
B
E
C
D
F
G
H
I
J
Phase 2:Propagation of query to agents for local searching
K
References
 K. S. Barber and C. E. Martin. Dynamic reorganization of decision-making groups. In





AGENTS ‘01: Proceedings of the fifth international conference on Autonomous
agents, pages 513-520, New York, NY, USA, 2001. ACM Press.
Kathleen M. Carley and Les Gasser. Computational organization theory. In Gerhard
Wiess, editor, Multiagent Systems: A Modern Approach to Distributed Artificial
Intelligence, pages 299-330, Cambridge, MA, 1999. MIT Press.
Y. So and E. Durfee. An organizational self-design model for organizational change.
In AAAI-93 Workshop on AI and Theories of Groups and Organiza- tions: Conceptual
and Empirical Research, pages 8ミ15, Washington, D.C., July 1993
Bryan Horling and Victor Lesser. A survey of multi-agent organizational paradigms.
Knowledge Engineering Review, 2005.
S. Robbins. Organization Theory - Structure Design and Applications. Prentice-Hall,
Englewood Cliffs, 1989.
Haizheng Zhang and Victor Lesser. A Dynamically Formed Hierarchical Agent
Organization for a Distributed Content Sharing System . In Proceedings of the
International Conference on Intel ligent Agent Technology (IAT 2004), pages 169-175,
Beijing, September 2004. IEEE Computer Society.
Questions?
Descargar

Document