## Algorithms for Solving the Multiagent Simple Temporal Problem

author: James C. Boerkoel Jr., University of Michigan
published: Nov. 15, 2010,   recorded: May 2010,   views: 238
Categories
You might be experiencing some problems with Your Video player.

# Slides

0:00 Slides A Comparison of Algorithms for Solving the Multiagent Simple Temporal Problem Motivation - 1 Motivation - 2 Talk Summary Background: Simple Temporal Problem (STP) Extending to Multiagent STP (MaSTP) Example MaSTP Establishing Decomposability Our Approach Multiagent STP Partitioning Privacy Properties of our Multiagent STP Algorithms Three Candidate Algorithms Partially Centralized: Private1 Partially Centralized: Shared Partially Centralized: Private2 Solving a Multiagent STP: Summary Empirical Evaluation Computation: Non-concurrency - 1 Computation: Non-concurrency - 2 Computation: Non-concurrency - 3 Computation: Non-concurrency - 4 Conclusion Thanks!

# Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

# Description

The Simple Temporal Problem (STP) is a popular representation for solving centralized scheduling and planning problems. When scheduling agents are associated with different users who need to coordinate some of their activities, however, considerations such as privacy and scalability suggest solving the joint STP in a more distributed manner. Building on recent advances in STP algorithms that exploit loosely-coupled problem structure, this paper develops and evaluates algorithms for solving the multiagent STP. We define a partitioning of the multiagent STP with provable privacy guarantees, and show that our algorithms can exploit this partitioning while still finding the tightest consistent bounds on timepoints that must be coordinated across agents. We also demonstrate empirically that our algorithms can exploit concurrent computation, leading to solution time speed-ups over state-of-the-art centralized approaches, and enabling scalability to problems involving larger numbers of loosely-coupled agents.