Principal Investigators: Edmund H. Durfee and Martha Pollack
Student Investigators: James C. Boerkoel, Jr., Erin Rhode, Keith Purrington
Project sponsor: National Science Foundation
Grant Number: IIS-0534280
Grant Period: 11/05-4/10
The research and education activities of this project focused on making advances in the representations and algorithms needed for modeling cognitively-impaired users’ scheduling constraints and preferences, for efficiently converging on feasible and preferable activity schedules while managing privacy, and on using these motivations and challenging problems to teach students about technology development and about the research process. In the below, we summarize these activities in terms of the particular research thrusts of the work, along with the educational efforts.
Simultaneously Solving Selection and Scheduling Problems
Providing cognitive support for people that encourages social interaction involves both scheduling and selection problems. Selection problems involve deciding from among alternative ways of satisfying a particular objective, such as deciding whether to go for a walk or a swim for one’s daily exercise. Scheduling problems involve deciding when to do these things. These decisions are coupled due to hybrid constraints that connect them: for example, if the decision is to swim, then the timing of the exercise activity is limited to the open swim hours at the pool. A central thrust in this project has been to formalize representations of such hybrid scheduling problems (HSPs), to develop efficient algorithms for solving them, and to extend these concepts to coordinate decisions across multiple entities (such as promoting convergence across multiple people to choose to walk, and to schedule walks at the same time, so as to have an opportunity to socialize while exercising).
Prior to this project, the state of the art for solving HSPs was to decompose a problem into its constituent components—a Finite-domain Constraint Satisfaction Problem (FdCSP) and a Disjunctive Temporal Problem (DTP)—and then to apply solution techniques tailored to each of these types of problems separately. Heuristic decisions were made about when to solve the FdCSP first, versus the DTP first. Our findings suggest that such techniques can be inefficient and prone to error in deciding where to invest computation time next.
We have found that HSPs can be formulated in ways that allow efficient, off-the-shelf constraint processing systems to solve them effectively, if the formulation emphasizes the right aspects of the problem. Toward this end, our Hybrid Constraint Tightening (HCT) approach reformulates standard hybrid constraints in HSPs so as to “lift” the shared aspects of multiple constraints, and thereby create a series of increasingly tight constraints that can be applied preemptively during the constraint search. Because the our hybrid-constraint tightening (HCT) approach only involves a preprocessing step rather than changing the search process itself, it can be applied in tandem with state of the art solvers. Our publications on this topic include a paper at AAAI-08 that showed analytically that HCT was a sound and efficient transformation of the problem, and a paper at AAMAS-09 that describes a battery of empirical studies to evaluate the efficacy of this approach. Our empirical studies applied HCT to a space of randomly-generated problems where we varied problem properties such as constraint tightness and number of features. We demonstrated that, for all but the simplest problems, the preprocessing overhead of HCT is more than recouped in speeding up the solution process, by orders of magnitude as problems grew in size, difficulty, or generality along several dimensions. We have since been able to apply this machinery to solve problems involving hundreds of variables and tens of thousands of constraints in a matter of seconds.
Publications:
James C. Boerkoel Jr. and Edmund H. Durfee. “Hybrid Constraint Tightening for Solving Hybrid Scheduling Problems.” In Proceedings of 23rd AAAI Conference on Artificial Intelligence (AAAI-08), pages 1446-1449, July 2008.
James C. Boerkoel, JJr. and Edmund H. Durfee. “Evaluating Hybrid Constraint Tightening for Scheduling Agents.” Proceedings of the 2009 Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS-09), pages 673-680, May 2009.
James C. Boerkoel, Jr. “A Multiagent System for Solving the Activity Selection and Scheduling Coordination Problem.” Proceedings of the AAAI/SIGART Doctoral Consortium, Pasadena, CA, 2009.
Edmund H. Durfee, James C. Boerkoel Jr., and Jason Sleight. “Using hybrid scheduling for the semi-autonomous formation of expert teams,” Future Generation Computer Systems, 31:200-212, 2014.
Decentralized Temporal Reasoning
Techniques for solving scheduling problems, including our Hybrid Constraint Tightening work, have generally relied on having access to all pertinent information in a single, centralized place. A complementary thrust of our work has been to explore the potential to solve such scheduling problems in a distributed, decentralized manner. Decentralization can have many benefits, especially for scheduling problems involving the coordination of multiple actors’ schedules, because it can improve privacy (individuals’ scheduling details that don’t materially affect coordination can be withheld), and can exploit parallel processing (where individuals contribute concurrently to finding a coordinated schedule rather than waiting for a centralized system to solve everyone’s problems).
Our activities on this front have drawn on the latest ideas for solving temporal constraint problems in centralized ways, and for solving selection (finite-domain constraint satisfaction) problems decentrally, to synthesize a novel approach that integrates ideas from these fields. We have carefully analyzed our resulting decentralized algorithms to prove correctness and termination properties, and have performed empirical studies to evaluate how well they can perform in practice in terms of maintaining privacy and increasing concurrent computation to converge on solutions more quickly. We have also been extending these ideas to embrace notions of temporal plan decoupling, where the judicious selection of up-front scheduling commitments for interactions across individuals enables even more parallelism and decoupling across individuals’ scheduling problems, not only further speeding up the process of finding coordinated solutions, but also providing greater amounts of latitude for individuals to adjust their schedules on the fly as activities last longer or shorter than expected, or as new events or objectives emerge.
We have found that decentralizing the process of temporal reasoning provides potential benefits to not only computation speed, but also to user privacy. We have developed distributed versions of a cutting-edge algorithm for solving temporal constraint problems based on partial path consistency, and have proven that our algorithms can allow a user to retain privacy and hence autonomy over his or her personal schedule. However, we have also proven that an agent cannot maintain privacy over local information that is also constrained by others’ schedules, such is when scheduling a meeting between users. Our empirical results suggest that our distributed approach not only has privacy advantages but speed advantages as well; the agents’ ability to solve their private problems independently and concurrently can lead to significant reductions in computation time for loosely-coupled problems, and computational effort grows sublinearly when agents share the burden of solving the non-private aspects of their schedules.
Publications:
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, 2013.
James C. Boerkoel Jr. and Edmund H. Durfee. “A Comparison of Algorithms for Solving the Multiagent Simple Temporal Problem.” In Proceedings of the 2010 International Conference on Automated Planning and Scheduling (ICAPS-10), pages 26-33, May 2010.
James C. Boerkoel Jr. and Edmund H. Durfee. “Partitioning the Multiagent Simple Temporal Problem For Concurrency and Privacy (Extended Abstract).” In Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2010), Toronto, pages 1421-2, May 2010.
Christopher Portway and Edmund H. Durfee. “The Multi Variable Multi Constrained Distributed Constraint Optimization Framework.” In Proceedings of the 2010 IEEE/WIC/ACM International Conference on Intelligent Agent Technologies (IAT-10), Toronto, August 2010.
Christopher Portway and Edmund H. Durfee. “The Multi Variable Multi Constrained Distributed Constraint Optimization Framework (Extended Abstract).” In Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2010), Toronto, pages 1385-6, May 2010.
Social Preferences
Whereas the activities described so far focused on finding one or more solutions that satisfy problem constraints, a companion issue for solving selection and scheduling problems across multiple participants is in ranking candidate solutions. That is, in many cases there could be multiple solutions that satisfy the hard constraints of the problem, so then the challenge is in picking one. Because multiple individuals are involved, it is unlikely that any candidate would be the top choice of everyone, so instead some compromise needs to be found.
A variety of social choice mechanisms have been developed over the years involving processes such as voting, bidding, negotiating, etc. The emphasis of our thrust in this area was on mechanisms that handle qualitative (rather than quantitative) preference specifications. Our motivation was that the class of users we are interested in, people with cognitive impairments, should not be expected to be able to express complex quantitative value judgments over complicated alternatives. Hence, our work adopted a model of preferences that is simple to express and to elicit from users. The model, called a CP-net, was developed by others to summarize a user’s preferences for some feature of the world, conditioned on other features of the world, all else being equal, such as preferring red wine if the meal is red meat, and white wine with fish.
Algorithms with provable properties had been developed for using CP-nets for efficiently determining preferred outcomes for individuals. However, expanding these techniques to finding preferred social outcomes is difficult without enumerating the exponentially many (in the number of features considered) outcomes and comparing them all. Our research activities focused on finding multiagent variations to the efficient single-agent algorithms for finding preferential social outcomes, and on the relationships between such approaches and established voting mechanisms.
We have developed a way to compare outcomes across agents based on each outcome’s relative standing in the individuals’ spaces of possible outcomes. We have shown how this formulation can guide the search through the outcome preference graphs that are induced by the agents’ CP-nets to find the optimal social outcome. However, because these induced preference graphs are exponential in the number of features, this approach can be infeasible for large problems. To address this, we have found that there are conditions under which the agents can search for approximately-optimal social outcomes directly using their CP-nets, and our empirical evaluations show that our approach yields near-optimal social outcomes in exponentially less time.
Based on these results, our investigations have delved more deeply into understanding the conditions for which these techniques work, uncovering implicit semantics in the CP representation about the importance of different preferences. We have proven that the additional complication of explicitly introducing indifference into the CP-net leads in general to an intractable optimization problem. Whereas prior work on this topic argued that a linear-time (in the number of features for describing an outcome) algorithm existed, our work showed that in the general case where some of the features might be set outside of the control of the algorithm, optimizing the outcome based on the controllable features involves search exponential in the number of such features. However, our empirical findings show that our new algorithm, which sweeps through portions of the feature space linearly in three phases, can reach good approximations of the optimal outcomes in linear time, and in fact under some restrictions on the topology of the CP-net the algorithm is guaranteed to find an optimal outcome.
Publications:
Keith Purrington and Edmund H. Durfee. “Agreeing on Social Outcomes Using Individual CP-Nets,” Multiagent and Grid Systems 5(4): 409-425, 2009. (Special Issue on Coordinating Agents’ Plans and Schedules).
Keith Purrington and Edmund H. Durfee. “NP-Completeness of Outcome Optimization for Partial CP-nets.” (student abstract track) In Proceedings of the 23rd AAAI Conference on Artificial Intelligence, pages 1826-1827, July 2008.
Keith Purrington and Edmund H. Durfee. “NP-Completeness of Outcome Optimization for Partial CP-nets.” Working Notes of the AAAI-08 4th Multidisciplinary Workshop on Advances in Preference Handling, July 2008.
Keith Purrington and Edmund H. Durfee. “Making Social Choices from Individuals’ CP-nets.” (short paper) In Proceedings of the Fifth International Conference on Autonomous Agents and MultiAgent Systems (AAMAS-07), pages 1114-1116, May 2007.
Keith Purrington and Edmund H. Durfee. “Joint Goal-Setting for Self-Interested Agents Using CP-nets.” In Working Notes of the AAMAS-07 Workshop on Coordinating Agents’ Plans and Schedules, pages 9-16, May 2007.
Decoupled Constraint and Preference Reasoning
Given our thrusts on constraint reasoning and preference reasoning, one of our culminating activities was to bring these thrusts together, to develop algorithms that interleave constraint and preference reasoning to converge more efficiently on schedules that are both feasible and desirable. Rather than following the more common path of expressing preferences as a form of “weak” constraints, we have pursued an approach in which preferences remain separately specified in CP-nets. This, for example, supports different participants in an endeavor having their own representations: where a resident in a facility, for example, has his or her own preferences over healthcare activities, while caregivers have sophisticated models of the facilities’ constraints that impact the feasible scheduling of appointments, tests, and procedures.
We have conducted empirical studies on strategies for interleaving preferential and constraint reasoning, including developing techniques for finding approximately optimal solutions that can be tuned to strike a desired tradeoff between how close to optimal the solution is and how much time the algorithm needs to run. Our efforts to combine the search for preferred outcomes and for feasible outcomes have provided a wealth of empirical data that has deepened our understanding about the complexity of such constrained optimization problems. We have generalized previous algorithms for finding solutions to constrained preferential optimization problems such that we can parametrically represent a family of algorithms, and specialize the parameterization to best meet the needs of a particular domain. With this parametric formulation, we have empirically verified that a particular interleaving between preferential and constraint reasoning (an interleaving that others had previously conjectured would likely work well but had not been experimentally tested) indeed outperforms a set of variations on that theme. Further, we have found that, even when there is a correlation between preferences and constraints (such that, for example, more preferred values for variables tend to lead more often to constraint violations), interleaving preferential reasoning with constraint propagation leads to more rapid convergence than reasoning sequentially about constraints and preferences (or vice versa). Furthermore, we have clarified why the different parametric flavors of the generalized algorithm behave as they do, and how the parameterized approach we have developed lets a user judiciously trade off the degree of solution optimality to get a much faster response.
Publications:
James C. Boerkoel Jr., Edmund H. Durfee, and Keith Purrington. “Generalized Solution Techniques for Preference-Based Constrained Optimization with CP-nets.” In Proceedings of the Eighth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-10), pages 291-298, May 2010.
Keith M. Purrington, James C. Boerkoel, Jr. and Edmund H. Durfee. “Solving Decoupled Constraint Optimization Problems for Online Cognitive Orthotic Scheduling Agents.” Working Notes of the IJCAI 2009 Workshop on Intelligent Systems for Assisted Cognition, July 2009.
Products
A related thrust of our work has been to design and implement test environments for evaluating our approaches. In our early efforts along these lines, we collected data from people (ourselves) to characterize scheduling decision-making behavior, and explored the possibilities of using actual instrumented living environments for evaluating prototype implementations. As the project progressed, we focused more on designing and developing a simulation testbed for testing and evaluating our solution strategies under fully controllable conditions. In this testbed, cognitive assistants are instantiated for each simulated human in need of cognitive support, where each assistant solves a hybrid scheduling problem with preferential information. The resulting scheduling decisions are enacted (or not) by the simulated humans who can choose to act against suggestions to varying degrees. As activities and interactions play out, the actual events are tracked and reported to the assistant processes, which in turn dynamically adapt the scheduling suggestions for subsequent activities to adjust to unexpected eventualities in ways to satisfy preferences. This simulation environment has provided a basic touchstone for confirming the technologies developed. The simulation testbed is in a prototype form for our internal use for empirical studies of preferential activity scheduling in stochastic environments, but we are attempting to put a portion of the testbed into a sharable form.
Over the course of this project, we have also implemented prototype algorithms that manifest the research concepts developed. For the most part, these software products have not been tested and packaged for use by others outside of knowledgeable members of the research community. In the case of the Hybrid Constraint Tightening techniques, we have shared portions of this code with partners looking at applications of this work to other joint scheduling domains, and it is available for use of others, though again with limited documentation and support. For example, an annotated file formulating a Hybrid Scheduling Problem that our software solves, as reported in our 2014 Future Generation Computing Systems paper cited above, is available.
Education
The educational thrust associated with this project involved graduate students and also undergraduates. The emphasis from this standpoint has largely been on teaching students about the fundamental concepts behind the science, engineering, and evaluation of computationally intelligent systems, and has also used the project’s objectives and research ideas to motivate student learning. The project has supported on average two graduate students per term, one of whom has focused on issues of efficiently solving (distributed) hybrid scheduling problems, and the other of whom has focused on modeling and using qualitative preferential information. At various times, other graduate students have also participated in the project to inject and evaluate related technologies for distributed constraint reasoning, model approximation, and efficient simulation. These graduate students received training from the faculty not only in the range of science and engineering topics brought to bear on the problem, but also in the art of formulating research problems, conducting research, and reporting results in oral and written form.
This project also supported the participation of undergraduate students, to support their education and in some cases graduate education. For example, the project involved a third-year undergraduate student in developing the simulation testbed, where the student closely collaborated with one of the project’s graduate students, providing both a mentoring opportunity to the graduate student and a research experience to the undergraduate. Further, the aims and approaches associated with the project attracted a first-year student to work on the project for a summer to gain some research experience in computational technologies to help automate aspects of decision making. While, as an African-American woman, this student had other sources of support (through the University’s Minority Engineering Program Office), this NSF project was critical for providing a context and foundation for this student’s experiences.
Contributions
Within the Discipline:
Our principal contributions within the discipline have been in devising new representations, algorithms, and evaluation methodologies for reasoning over preferences, constraints, and combinations of preferences and constraints. These contributions support the development of systems for managing large-scale, distributed, preferential scheduling problems, by reducing computational time to solve hybrid scheduling problems by orders of magnitude, achieving similar speedups for approximate preference reasoning compared to complete algorithms for preference optimization, and improving privacy and flexibility for distributed users.
Contributions to Other Disciplines:
The research conducted in this project borders on and informs research in neighboring fields, including: developing new temporal reasoning algorithms for solving scheduling problems, which are of interest to communities such as operations research; developing efficient new mechanisms for solving social choice problems, which are of interest to researchers in economics and political science; and providing new techniques for providing recommendations during computer-human interaction, which is a topic of interest to the user interface community.
Contributions Beyond Science and Engineering:
We have worked with a company to transition some some of the techniques we have developed into tools for coordinating networks of human experts who are assembled into teams for emergent problem-solving episodes.