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?