Scalable Temporal Plan Merging. Marcon dos Santos, G. and Adams, J. A. In review, 2020.
abstract   bibtex   
Agents can individually devise plans and coordinate to achieve common goals. Methods exist to factor planning problems into separate tasks and distribute the plan synthesis process, while reducing the overall planning complexity. However, merging distributedly generated plans becomes computationally costly when task plans are tightly coupled, and conflicts arise due to dependencies between plan actions. Existing methods either scale poorly as the number of agents and tasks increases, or do not minimize makespan, the overall time necessary to execute all tasks. A new family of plan coordination and conflict resolution algorithms is introduced to merge independently generated plans, minimize the resulting makespan, and scale to a large number of tasks and agents in complex problems. A thorough algorithmic analysis and empirical evaluation demonstrates how the new conflict identification and resolution models can impact the resulting plan quality and computational cost across two heterogeneous multiagent domains and outperform the baseline algorithms.
@article{MarcondosSantos2020c,
  abstract = {Agents can individually devise plans and coordinate to achieve common goals. Methods exist to factor planning problems into separate tasks and distribute the plan synthesis process, while reducing the overall planning complexity. However, merging distributedly generated plans becomes computationally costly when task plans are tightly coupled, and conflicts arise due to dependencies between plan actions. Existing methods either scale poorly as the number of agents and tasks increases, or do not minimize makespan, the overall time necessary to execute all tasks. A new family of plan coordination and conflict resolution algorithms is introduced to merge independently generated plans, minimize the resulting makespan, and scale to a large number of tasks and agents in complex problems. A thorough algorithmic analysis and empirical evaluation demonstrates how the new conflict identification and resolution models can impact the resulting plan quality and computational cost across two heterogeneous multiagent domains and outperform the baseline algorithms. },
  added-at = {2020-05-24T20:36:48.000+0200},
  author = {Marcon dos Santos, Gilberto and Adams, Julie A.},
  biburl = {https://www.bibsonomy.org/bibtex/2907f8c7d42a23f90c5345fe0a9f2f39f/marcondg},
  interhash = {773af77bb3fe68fa669772dbf013b5e5},
  intrahash = {907f8c7d42a23f90c5345fe0a9f2f39f},
  journal = {In review},
  keywords = {mine},
  timestamp = {2020-05-24T20:36:48.000+0200},
  title = {Scalable Temporal Plan Merging},
  year = 2020
}
Downloads: 0