Workshop on
Multiagent Planning and Scheduling

To be held in conjunction with
The 15th International Conference on Automated Planning & Scheduling
(ICAPS 2005)
Monterey, California, USA

June 6, 2005

Discussion Notes
Tentative Schedule
Proceedings (PDF)

Call for papers (text)

Multiagent planning is concerned with planning by (and for) multiple agents. It can involve agents planning for a common goal, an agent coordinating the plans (plan merging) or planning of others, or agents refining their own plans while negotiating over tasks or resources. The topic also involves how agents can do this in real time while executing plans (distributed continual planning). Multiagent scheduling differs from multiagent planning the same way planning and scheduling differ: in scheduling often the tasks that need to be performed are already decided, and in practice, scheduling tends to focus on algorithms for specific problem domains. Because of the overlap in the fields, we will not distinguish them and will use "planning" to refer to both planning and scheduling.

More than ever industry, space, and the military are seeking systems that can solve multiagent planning problems, such as those in supply chain management, coordinating space missions, and commanding mixtures of vehicles and troops. For many real-world problems it is hard to motivate multiple agents because centralized decision-making is often most efficient. One goal of this workshop is to identify methods for discerning how and when systems should be decentralized.

Multiagent planning and scheduling seems to fall in the intersection of the fields of planning and scheduling, distributed systems, parallel computing/algorithms, and multiagent systems. However, much of the research appears to build on ideas from either planning or multiagent systems (and usually not both). From the viewpoint of planning, planning for multiple agents means supporting concurrent action, and planning by multiple agents means parallelizing a planning algorithm. One might argue that the former has been done and the latter should be solved using parallel computing techniques and is dependent on hardware. On the other hand, from a multiagent systems perspective, multiagent planning is not about just solving planning problems but also how agents should behave and interact given that they have plans or planning capabilities.

From any point of view, there are many open issues in multiagent planning. While many planners can handle some notion of concurrency, and many plan merging algorithms have been proposed, there has been little work on decentralized planning, competitive planning systems, evaluation of communication costs, and distributed continual planning. We aim for this workshop to foster ideas addressing these issues and suggest other important research questions.

The workshop will be one full day. We solicited papers and position statements for presentation on topics including (but not limited to)

We plan to have one or two invited speakers and a panel on applications where we hope to spur discussions among participants. In addition, we will set aside time after groups of related paper presentations to raise discussions pertinent to the talks.

Accepted Papers
Extended Abstract: Honeywell' COORDINATORs Project
David J. Musliner and John Phelps
Managing Communication Limitations in Partially Controllable Multi-Agent Plans
John Stedl and Brian Williams
Computing the Communication Costs of Item Allocation
Timothy W. Rauenbusch, Stuart M. Shieber, and Barbara J. Grosz
Coordinating Agile Systems Through the Model-based Execution of Temporal Plans
Thomas Léauté and Brian Williams
Execution Monitoring and Replanning with Incremental and Collaborative Scheduling
David E. Wilkins, Stephen F. Smith, Laurence A. Kramer, Thomas J. Lee and Timothy W. Rauenbusch
Self-interested Planning Agents using Plan Repair
Roman van der Krogt and Mathijs deWeerdt
Exploiting Interaction Structure in Networked Distributed POMDPs
R. Nair, P. Varakantham, M. Tambe, and M. Yokoo
Bounded Policy Iteration for Decentralized POMDPs
Daniel S. Bernstein, Eric A. Hansen, and Shlomo Zilberstein
ASET: a Multi-Agent Planning Language with Nondeterministic Durative Tasks for BDD-Based Fault Tolerant Planning
Rune M. Jensen and Manuela M. Veloso
Robust Distributed Coordination of Heterogeneous Robots through Temporal Plan Networks
Andreas F.Wehowsky, Stephen A. Block, and Brian C. Williams
Determining Task Valuations for Task Allocation
David C. Han and K. Suzanne Barber
Planning for Multiagent Environments: From Individual Perceptions to Coordinated Execution
Michael Brenner
From Multiagent Plan to Individual Agent Plans
Olivier Bonnet-Torrès and Catherine Tessier

Program Committee