Algorithms for Solving the Multiagent Simple Temporal Problem

author: James C. Boerkoel Jr., University of Michigan
published: Nov. 15, 2010,   recorded: May 2010,   views: 4196


Related Open Educational Resources

Related content

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.
Lecture popularity: You need to login to cast your vote.


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.

See Also:

Download slides icon Download slides: icaps2010_boerkoel_asmstp_01.pdf (757.3┬áKB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: