Distributed Approaches for Solving Constraint-based Multiagent Scheduling Problems

This dissertation focuses on building scheduling algorithms for computational agents that assist people in managing their activities in environments in which tempo and complexity outstrip people's cognitive capacity, such as in helping people with dementia manage their everyday lives. The critical challenge is that, as individuals decide how to act on their scheduling goals, scheduling agents should answer queries regarding the timings of and relationships between events in their interacting schedules, such as between patients and caregivers in an assisted-living facility, while respecting individual privacy and autonomy.
I formally define both the Multiagent Simple Temporal Problem (MaSTP) and Multiagent Dis- junctive Temporal Problem (MaDTP) for naturally capturing and reasoning over the distributed but interconnected scheduling problems of multiple individuals. My hypothesis is that combining a bottom-up approach, where an agent externalizes constraints that compactly summarize how its local subproblem affects other agents' subproblems, with a top-down approach, where an agent proac- tively constructs and internalizes new local constraints that decouple its subproblem from others', will lead to effective solution techniques.
In the MaSTP domain, I confirm my hypothesized approach leads to distributed algorithms whose concurrent execution lead to orders-of-magnitude speedup and increased privacy and independence over previous art as problem structure grows more loosely-coupled. Despite the combinatorially-large and unwieldy nature of the MaDTP solution space, I further confirm my hypothesis by showing that influence spaces, which I demonstrate are much more tractable to compute and represent, exploit independence between agents, when it exists, to compactly summarize spaces of interacting sched- ules. Finally, I apply the same basic principle to the Hybrid Scheduling Problem and show that my new Hybrid Constraint Tightening approach can improve the propagation of information be- tween planning and scheduling subproblems, leading to significant search space pruning and solve time reduction. In summary, this dissertation's contributions include calculating distributed repre- sentations of the joint solution space for multiagent, constraint-based scheduling problems without centralizing or otherwise redistributing the problem while achieving computational speedup over current art.