Multiagent Planning and Scheduling

Brad Clement

Summary:
Multiagent planning can involve agents planning for a common goal,  
an agent coordinating the plans or planning of others, or agents  
refining their own plans while negotiating over tasks or resources.
This tutorial will give researchers and practitioners an  
understanding of the motivations, design issues, applications, and  
history of work in multiagent planning up to present day.

Goal: 
More than ever industry, space, and the military are seeking to  
coordinate planning systems.  Because the demand outweighs the  
supply, we want to spread the word on the opportunities and tools  
available.  This tutorial will give researchers and practitioners an  
understanding of the motivations, applications, and history of work  
in multiagent planning up to present day.  After this tutorial, a  
graduate student could choose a thesis topic and know how to  situate 
it with prior work.  A research practitioner or systems  engineer 
would have references to relevant research and resources to  implement 
a multiagent planning system.

Outline (half-day tutorial):

 Tutorial outline:
   * What is multiagent planning?
     o Why multiple agents?
     o Role of Multiagent Planning
       - Multiagent problem solving
       - Multiagent system architecture
     o Planning + Multiple agents
   * Design Issues
     o Why coordinate?
     o Decentralized Decision-Making?
       - Why centralize?
       - Why decentralize?
     o Evaluation Criteria for Multiagent Planning
   * Applications
     o Industry
       - supply chain management
       - business-to-business
       - shipping logistics
       - factory management
       - workforce management
     o Military
       - distributed sensors
       - unmanned vehicles
       - troop/asset management
     o Space
       - multiple rovers
       - spacecraft constellation
       - Earth orbiters
       - Mars Network
       - DSN antenna allocation
     o Games
       - real-time strategy
       - massively multi-player online role playing
   * Multiagent planning problems and techniques
     o Planning for Multiple Agents
       - Markov Decision Processes (MDPs)
     o Planning by Multiple Agents
       - Distributed NOAH
       - COLLAGE
     o Coordinating Agents' Plans (Plan Merging)
     o Planning and Coordinating
       - Plan Combination Search
       - Multi-level Coordination & Planning
       - Generalized Partial Global Planning (GPGP)
       - DSIPE & CODA
       - Shared Plans
       - Game Theory
     o Distributed Continual Planning
       - Partial Global Planning (PGP)
       - Shared Activity Coordination (SHAC)
       - Market Mechanisms
   * Open Issues