Distributed Reasoning for Multiagent Simple Temporal Problems

TitleDistributed Reasoning for Multiagent Simple Temporal Problems
Publication TypeJournal Article
Year of Publication2013
AuthorsBoerkoel, J. C., and E. H. Durfee
JournalJournal of Artificial Intelligence Research (JAIR)
Start Page95
Date Published05/2013
KeywordsDistributed Scheduling, Multiagent Simple Temporal Problem, Temporal Decoupling

This research focuses on building foundational algorithms for scheduling agents that assist people in managing their activities in environments where tempo and complex activity interdependencies outstrip people's cognitive capacity. We address the critical challenge of reasoning over individuals' interacting schedules to efficiently answer queries about how to meet scheduling goals while respecting individual privacy and autonomy to the extent possible. We formally define the Multiagent Simple Temporal Problem for naturally capturing and reasoning over the distributed but interconnected scheduling problems of multiple individuals. Our hypothesis is that combining bottom-up and top-down approaches will lead to effective solution techniques. In our bottom-up phase, an agent externalizes constraints that compactly summarize how its local subproblem affects other agents' subproblems, whereas in our top-down phase an agent proactively constructs and internalizes new local constraints that decouple its subproblem from others'. We confirm this hypothesis by devising distributed algorithms that calculate summaries of the joint solution space for multiagent scheduling problems, without centralizing or otherwise redistributing the problems. The distributed algorithms permit concurrent execution to achieve significant speedup over the current art and also increase the level of privacy and independence in individual agent reasoning. These algorithms are most advantageous for problems where interactions between the agents are sparse compared to the complexity of agents' individual problems.

Refereed DesignationRefereed