Solving the Multiagent Selection and Scheduling Problem

1 Introduction

My work focuses on building computational agents that assist people in managing their activities in environments in which tempo and complexity outstrip people's cognitive capacity, such as in coordinating rescue teams in the aftermath of a disaster, or in helping people with dementia manage their everyday lives. A critical challenge faced in such environments is not only that individuals must factor complicated constraints into deciding how and when to act on their own goals, but also that their decisions are further constrained by choices made by others with whom they interact, such as between cooperating teams in disaster relief or between patients and caregivers in an assisted-living facility. An additional challenge in such situations is that the interests of individuals, such as privacy and autonomy, along with slow, costly, uncertain, or otherwise problematic communication may further limit individuals' abilities to work together. My work assumes that a computational agent is associated with each individual, and that these agents will work together efficiently to manage individual and joint activities, while maintaining autonomy and privacy to the extent possible.

2 Significance

My thesis focuses on providing scalable, multiagent algorithms for solving rich, complex multiagent activity scheduling and selection problems, while retaining as much privacy as possible on behalf of the human users. While there have been many approaches for solving distributed, finitedomain/discrete versions of these types of problem representations in the past (e.g., [Yokoo et al., 1998]), due to limiting assumptions over problem structure and a narrow focus on computational efficiency, this work has largely failed to gain traction in practical applications. My work, on the other hand, in addition to computational efficiency, also considers more strategic issues, like privacy and autonomy, over problems with more general structure, such as where agent subproblems are non-trivial. My approach is distinct from other recent multiagent scheduling approaches (e.g., [Smith et al., 2007]) because it is capable of not only scheduling activities, but also selecting which activities to schedule and how to schedule them. Additionally, my work represents the first time that ideas such as constraint summarization and decoupling (described in Section 4), have been unified into a distributed approach that more ef-

Solving the Multiagent Selection and Scheduling Problem

James Boerkoel

Computer Science and Engineering University of Michigan, Ann Arbor boerkoel@umich.edu

ficiently solves general classes of real-world, multiagent selection and scheduling problems. This work not only makes significant efficiency gains over previous state-of-the-art solution approaches, but also incentivizes individuals to adopt this technology in practice by contributing algorithms that protect an individual's privacy and autonomy [Boerkoel and Durfee, 2011; 2010]. My novel problem representation and solution approaches could also be applied in hospital scheduling, military coordination, supply-chain logistics, and allocation of community services, among others. I proceed by introducing the Multiagent Selection and Scheduling Problem (MASSP), explaining my approach and presenting preliminary results for solving the MASSP, and concluding with a summary of expected contributions.

3 Problem Statement

In this section, I introduce a novel problem representation, the Multiagent Selection and Scheduling Problem (MASSP), which generalizes Schwartz's (2007) Hybrid Scheduling Problem (HSP) representation to a multiagent setting. As background, the HSP formulation combines the typical finitedomain Constraint Satisfaction Problem (CSP) formulation with the Disjunctive Temporal Problem (DTP) formulation using hybrid constraints. Informally, the MASSP is a set of n local HSP subproblems, one for each of n agents, and a set of external constraints that relates and mutually constrains agents' local subproblems. The problem that this thesis addresses is that of developing efficient, decentralized algorithms that solve the MASSP, while to the maximum extent possible, protecting users' privacy and autonomy.

4 Approach

My high-level approach is to decompose problems into n locally-independent subproblems that each agent can solve concurrently and privately, and one shared subproblem for which agents must work together to solve. This decomposition divides variables based on whether or not they are involved in external constraints and so exploits the natural, loosely-coupled problem structure of many real-world problems, when it exists. I describe this partitioning in much greater detail for the Multiagent Simple Temporal Problem (MaSTP) and use it to prove important privacy properties for my algorithms and empirically demonstrate how this structure influences algorithm performance [Boerkoel and Durfee, 2010; 2011]. Solving the MaSTP is an important precursor for solving the multiagent versions of more complicated scheduling formulations such as DTPs and HSPs, which often require quickly evaluating partial, candidate assignments in the form of component STPs. I next describe my approach for designing algorithms that utilize this decomposition.

First an agent exploits otherwise idle time to summarize how its local subproblem affects the subproblems of other agents, thus elucidating the interface between subproblems. Generally, agents accomplish this using constraint compilation - deriving new constraints that capture otherwise implicit constraint information. The adaptive consistency algorithm [Dechter and Pearl, 1987] is an example of a constraint compilation algorithm that uses a variable elimination procedure to create backtrack-free representations of a CSP. My algorithm to solve the MaSTP [Boerkoel and Durfee, 2010] is a variant of this basic variable elimination procedure where each agent privately and concurrently eliminates its local variables first, and then coordinates with other agents to eliminate its externally constrained variables. The algorithm then performs a reverse pass that calculates the full set of possible joint solutions. This distributed algorithm demonstrates impressive levels of speedup over comparable centralized approaches, especially on loosely-coupled problems.

Second, agents perform a decoupling search - a search where each agent heuristically makes search decisions that decouples itself from the subproblems of other agents. Informally, a decoupling (e.g., a temporal decoupling [Hunsberger, 2002]) is defined in terms of locally independent sets of solutions that, when combined, form a solution to the original multiagent constraint problem. Thus, the goal for each agent is to make search decisions (e.g., impose local constraints) that render external constraints moot. My most recent result [Boerkoel and Durfee, 2011] augments my previous MaSTP solution algorithm so that, during the reverse phase of execution, agents introduce new constraints that temporally decouple their local subproblems. Calculating a temporal decoupling allows agents to avoid continually revising a set of consistent joint schedules as new constraints arise, since persistent coordination may not be a viable option in environments where communication is uncertain, costly, or otherwise problematic. I empirically demonstrate that it is more efficient to calculate a temporal decoupling than the full set of possible solutions. I also introduce and perform an empirical cost/benefit analysis of new techniques and heuristics for selecting a maximally flexible temporal decoupling.

Overall, local constraint summarization promotes privacy, independence, and concurrency by limiting agent coordination to a small subset of mutually known aspects of the joint problem. The decoupling search, then, complements local constraint summarization by attempting to shrink the size of the shared problem, thus increasing the amount of computation that can be done locally, concurrently, and privately.

As a highlight of the generality of this approach, my Hybrid Constraint Tightening (HCT) preprocessing algorithm [Boerkoel and Durfee, 2008; 2009] uses constraint summarization principles to reformulate hybrid constraints by lifting information from the structure of an HSP instance. These reformulated constraints elucidate implied constraints between the CSP and DTP subproblems of an HSP earlier in the search process, leading to significant search space pruning. HCT leads to orders of magnitude speedup when used in conjunction with off-the-shelf, state-of-the-art solvers. Additionally, I have explored properties of HSPs that influence HCT's efficacy, quantifying the influence empirically. HCT will play a critical role in merging multiagent versions of the DTP and CSP to solve the more general MASSP.

5 Expected Contributions

To summarize, in addition to the contributions mentioned in the preliminary results, I expect to contribute the following: 1) the constraint-based MASSP formulation for representing multiagent problems involving both activity selection and scheduling; 2) a local constraint summarization approach for establishing the joint consistency of the MASSP (and also multiagent versions of the CSP and DTP); 3) a decoupling search strategy for solving the MASSP (and also multiagent versions of the CSP and DTP ); and finally 4) an evaluation of algorithms that implement and synthesize these techniques.