Student Investigators: Jason Sleight, James C. Boerkoel, Jr., Alexander GutierrezUniversity of Michigan durfee at umich dot edu http://ai.eecs.umich.edu/people/durfee
Project sponsor: National Science Foundation
Grant Number: IIS-0964512
Grant Period: 6/10-12/14
This has been a collaborative project between the University of Michigan and the University of Massachusetts. For more information on the particular investigations at the University of Massachusetts, see their corresponding project’s website here.
Human organizations have inspired the encoding of a variety of approaches for coordinating computational agents that need to work together as a cohesive group in order to achieve their goals. Computational approaches to organization have largely taken what we would refer to as a problem-driven view, where an organizational designer starts with a complex problem to solve, and decomposes the problem into a set of roles (e.g., marketing, manufacturing, etc.) that can contribute to solving the problem and relationships among those roles. Numerous specification languages have been developed for defining such organizations. With such an organization specified, agents capable of playing particular roles are enlisted, and the organization is instantiated. A particular strength of this kind of approach is that the organization can persist as long as the problem persists, where agents playing roles can come and go, and thus a multiagent system constructed in this manner can be robust and long-lasting. But because agents have no inherent incentive for being part of an organization, there cannot be any realistic expectations about agent participation in the management and evolution of the organization.
In contrast, this project explores an agent-driven view of organizations, where an organization is built specifically to benefit a group of agents that want to cooperate. In other words, this project is looking at systems where agents are trying to work together but discovering that they are either miscoordinating (e.g., interfering with each other or taking redundant actions) or are spending much of their effort coordinating rather than focusing on useful work. In colloquial terms, the agents can decide that they “need to get organized.” The power of an agent-centric approach is that the agents can be expected to understand the purpose of the organization, and to be able to recognize and respond appropriately when, due to incorrect assumptions or changing circumstances, the organizational structure they have adopted is misaligned with what should be transpiring.
We refer to such agents as Organizationally-Adept Agents (OAAs) . An OAA does not execute its role blindly, like an assembly-line robot going through motions of picking up and packing parts even when the conveyor belt is empty. Instead, an OAA is not only capable of translating its assigned organizational responsibilities into operational decisions, but is also aware of how its responsibilities relate to the environment in which it operates and the responsibilities of the other agents in the organization. When expectations are not met, it can take action, which could simply be alerting some higher-level manager with responsibility to modify the organization. More generally, though, the OAAs can make changes to the boundaries of their responsibilities and expectations, ranging from temporary changes (tasking out a responsibility that cannot currently be fulfilled) to permanent changes (redefining the boundaries of responsibilities and expectations). OAAs thus adapt their behaviors to better match with the spirit and purpose of the organizational design, as opposed to rote following of the organizational directives unconditionally.
The fundamental challenges we have pursued in developing OAAs are (1) formulating a specification of organizational designs that can be directly used by the agents to guide their operational decisions; (2) developing principles and algorithms for automating the construction of organizational designs within the design space of the specification language; (3) providing agents with principled criteria to reason about the suitability of their current organizational structure; and (4) creating techniques that agents can use among themselves for revising boundaries between their activities that delineate responsibilities and expectations more effectively under their current circumstances.
Organizational Design Specification Language
The organizational design specification language is the bridge between the intent of the designer and the execution of the organization participants. Many languages concentrate on trying to capture concepts and terminology from the organization-theory literature in a language, with the assumption that ultimately agents will be implemented to correctly translate those concepts/terms into their decision-making machinery. Our approach goes in the opposite direction, by first considering all the ways in which external guidance could influence the decisions of our target agents, and then formulating the organizational design language so as to cover those influences unambiguously. To model and encoding organizational guidelines into an operational form, therefore, we use the principled foundation provided by decision theory as embodied in Decentralized Partially-Observable Markov Decision Processes (Dec-POMDPs). Considerable research has been devoted to solution techniques for finding optimal or approximately optimal joint policies for Dec-POMDPs. In this project, however, our emphasis has been on identifying how the various components of the Dec-POMDP framework (such as the agents’ reward functions, transition models, action spaces, and state representations) can be manipulated as part of an organizational design, and the ramifications of doing so. Our work has shown that each of the components of the agents’ decision-theoretic model provides a different lever for influencing behavior, often with impacts not only on the quality of the agents’ joint decisions, but also with the reasoning costs that the agents must invest in making their decisions [2,3].
Principles and Algorithms for Automating Organization Design
We have also shown the benefits of a factored version of this organizational specification language for decision-theoretic agents, and connected the notion of factoring to common concepts such as “micromanagement.” We have shown empirically that the flexibility of selectively influencing only some aspects of a component of an agent’s decision model outperforms our initial “overwriting” strategy. However, the factored language is richer, making the design process more complicated. We have addressed this challenge in two ways. First, we have proposed a general principle for organizational design that states that the only influences the organization should have on agents are those stemming from interactions. We codified this principle in terms of specifications of reward and transition dependencies between agents, and demonstrated empirically that following this principle provides superior performance. Our second strategy for addressing this challenge has been to automate the organizational design process. In a nutshell, we’ve shown that using an “options” framework to abstract actions and solving randomly-drawn example problems at the abstract level reveals important interaction patterns in the agents’ state-action occupancy measures. We’ve shown how these can be mapped to influences that shape agents’ transition and reward behaviors, hence imposing an organization. Our experiments showed that these computer-generated organizational structures could often outperform handcrafted designs, and in fact would reveal patterns of interaction (or means of organizationally fostering such patterns) overlooked in the handcrafted designs [4, 5].
Agent Reasoning About Organizational Structures
For the challenge of reasoning about the suitability of organizational structures, a fundamental aspect of addressing this challenge is to recognize that not only should agents be able to reason about adjusting their behaviors to meet the spirit of the organizational design, but also that the organizational design should be constructed in the first place with an eye toward giving agents the right amount of latitude for adjusting their behaviors. In our earlier work , this co-design was explicitly captured in that agents were provided with multiple organizational designs along with criteria under which each would be preferred. Our empirical investigations focused on questions about how reactive agents should be in moving among organizational designs given inherent randomness in their environments. That is, how much confidence should agents have that the environmental conditions have shifted before moving to a different organizational structure, given that changing structures itself incurs overhead costs. In subsequent work, we have used the factored representation of organizational influences to permit the organizational design to explicitly leave some influences “unsaid” and therefore to decide exactly where the agents are themselves expected to “fill in the blanks” in the organization’s behaviors .
We have also formalized the relationship between an organizational structure and its impact on the amount of reasoning that an agent must do. We have developed preliminary metrics for measuring reasoning cost as well as operational performance, so that an organization can be evaluated in terms of how well it encourages agents to behave in coordinated ways while shielding the agents from reasoning about behaviors that are unlikely to be beneficial. A key innovation in this work has been developing algorithmic techniques for searching the organizational design space that can incrementally estimate the benefits (to coordination) and costs (to agent computation) of introducing a candidate influence into an organizational design that is being constructed. As was witnessed in our earlier work on automated organization design, this work reveals yet other opportunities in the organizational design space for unexpected design choices, such as prohibiting agents from considering reversing actions that they have taken, which focuses agents on reasoning about fewer focused trajectories of action [5,6].
Abstraction plays a key role in both the articulation of an organizational structure and in the search process for designing such a structure. Increasing abstraction over organizational influences allows fewer, broadly-applicable behavioral roles and guidelines to be specified, thereby streamlining the organizational design process (fewer combinations of influences to consider) and leaving agents more room to tailor their actions to evolving circumstances. Too much abstraction, however, can provide too little guidance towards fruitful joint activities and burden agents with solving complex coordination problems. We have engaged in the first in-depth study of the impacts of alternative abstraction choices both on the organizational design process and on the performance of a multiagent system using the designed organizations. Our work has identified dimensions of abstraction pertinent to organization design processes and outcomes, and by mapping these to an example domain we have evaluated organizational designs at different points of the abstraction space. A key innovation of this work has been the development of an analytical framework for understanding the impact of abstraction in organizational design, which we have used to identify a general-purpose organizing heuristic of preferring influence abstractions that are “task-delineated,” which we have shown empirically to be effective .
Techniques for Establishing/Revising Agent Boundaries and Relationships
For identifying different or new boundaries between agents’ activities, our efforts have centered on defining and utilizing the concept of “abstract influence” between individual agents . Our prior work in multiagent planning for stochastic domains demonstrated the power of coordinating over the space of different ways that agents can influence each other rather than over the space of different possible joint plans, exploiting in a principled way that intuition that, in many multiagent problems, an agent might have many detailed local plans whose impacts on other agents all look the same. We have built on our previous strategies for making commitments to future events despite uncertainty about intervening opportunities that modify an agent’s potential goals and rewards. Our work has situated these probabilistic strategies in the space of commitment techniques adopted by the community, which focus on modal logical formulations .
We have also developed techniques for using abstract influences to discover and institute decoupling decisions over disjunctive scheduling problems, which included the design of metrics for assessing the loss of flexibility agents incur by voluntarily imposing boundaries on their actions to resolve potential negative interactions. In scheduling applications involving multiple agents, the challenge is to avoid either of two extremes: we don’t want agents to commit to overly-specific times because such schedules are brittle to uncontrollable events, and yet if agents try to leave all of their options open then they need to stay in constant contact to whittle down options as time progresses. We showed how reasonably compact and computable representations of spaces of schedules can be realized for STPs [10, 11, 12]. Meanwhile, we have been extending these ideas to the much harder DTP class of problems. Most recently, we have developed an algorithm for decoupling (imposing local constraints that obviate inter-agent constraints) for the DTP. We have empirically found that this process can be done orders of magnitude faster than finding complete spaces of joint schedules, but at the cost of flexibility. We have also found that traditional measures of flexibility are insufficient for capturing tradeoffs with DTPs, and have extended such measures accordingly [13, 14].
Collaborations with the University of Massachusetts
Our other research activities included collaborating with our teammates at the University of Massachusetts to assist them in identifying simulation testbeds, and scenarios to run in those simulations. We found complementary niches with those teammates. For example, in their work they had been stretching the boundaries of organizational adaptation in complex disaster-response scenarios assuming that different facets of an organizational specification can be adapted independently. Our work has instead been looking the overall design process for an organization, starting from the ground up rather than repairing imperfections in a predefined structure.
1. Daniel D. Corkill, Edmund H. Durfee, Victor R. Lesser, Huzaifa Zafar, and Chongjie Zhang. “Organizationally Adept Agents.” In Working Notes of the AAMAS-11 Workshop on Coordination, Organizations, Institutions, and Norms in Multiagent Systems (COIN), May 2011.
2. Jason Sleight and Edmund H. Durfee. “A Decision-Theoretic Characterization of Organizational Influences.” In Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS-12), pages 323-330, June 2012.
3. Jason Sleight and Edmund H. Durfee. “Selectively Injecting Organizational Influences into Decision-Theoretic Agents.” In Working Notes of the AAMAS-12 Workshop on Coordination, Organizations, Institutions, and Norms, pages 181-195, June 2012.
4. Jason Sleight and Edmund H. Durfee. “Organizational Design Principles and Techniques for Decision-Theoretic Agents.” In Proceedings of the Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-13), pages 463-470, May 2013.
5. Jason Sleight and Edmund H. Durfee. “Multiagent Metareasoning Through Organizational Design (Extended Abstract).” In Proceedings of the Thirteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-14), May 2014.
6. Jason Sleight and Edmund H. Durfee. “Multiagent Metareasoning Through Organizational Design.” In Proceedings of the Twenty-Eighth Conference on Artificial Intelligence (AAAI-14), pages 1478-1484, July 2014.
7. Jason Sleight and Edmund H. Durfee. “Effective Influence Abstractions for Organizational Design.” In Proceedings of the Fourteenth International Conference on Autonomous Agents and Mulitagent Systems (AAMAS-15), May 2015.
8. Stefan J. Witwicki and Edmund H. Durfee. “Towards a Unifying Characterization for Quantifying Weak Coupling in Dec-POMDPs.” In Proceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-11), pages 29-36, May 2011. (One of three nominees for the Best Student Paper Award.)
9. Stefan Witwicki, Inn-Tung Chen, Edmund Durfee, and Satinder Singh. “Planning and Evaluating Multiagent Influences Under Reward Uncertainty (Extended Abstract).” In Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2012), pages 1277-1278, Valencia, Spain, 2012.
10. James C. Boerkoel Jr. and Edmund H. Durfee. “Distributed Reasoning for Multiagent Simple Temporal Problems.” Journal of Artificial Intelligence Research (JAIR), volume 47, pages 95-156, May 2013.
11. James C. Boerkoel Jr. and Edmund H. Durfee. “Distributed Algorithms for Solving the Multiagent Temporal Decoupling Problem.” In Proceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-11), pages 141-148, May 2011.
12. James C. Boerkoel, Jr. and Edmund H. Durfee. “A Distributed Approach to Summarizing Spaces of Multiagent Schedules.” In Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI-12), pages 1742-1748, July 2012.
13. James C. Boerkoel, Jr. and Edmund H. Durfee. “Decoupling the Multiagent Disjunctive Temporal Problem.” In Proceedings of the Twenty-Seventh Conference on Artificial Intelligence (AAAI-13), pages 123-129, July 2013.
14. James C. Boerkoel, Jr. and Edmund H. Durfee. “Decoupling the Multiagent Disjunctive Temporal Problem (Extended Abstract).” In Proceedings of the Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2013), pages 1145-1146, July 2013.
Other Research Products:
Data files corresponding to results reported in Sleight/Durfee AAMAS2015 paper.
Data files corresponding to results reported in Sleight/Durfee AAMAS2014 paper.
Data files corresponding to results reported in Sleight/Durfee AAMAS2013 paper.
Data files corresponding to results reported in Sleight/Durfee AAMAS2012 paper.