Simple Temporal Networks for Improvisational Teamwork

Authors

  • Malia Morgan Harvey Mudd College, Claremont, CA
  • Julianna Schalkwyk Harvey Mudd College, Claremont, CA
  • Huaxiaoyue Wang Harvey Mudd College, Claremont, CA
  • Hannah Davalos Harvey Mudd College, Claremont, CA
  • Ryan Martinez Harvey Mudd College, Claremont, CA
  • Vibha Rohilla Harvey Mudd College, Claremont, CA
  • James Boerkoel Harvey Mudd College, Claremont, CA

Keywords:

Simple Temporal Networks, Improvisational Teamwork, Strong Controllability, Scheduling Under Uncertainty

Abstract

When communication between teammates is limited to observations of each other's actions, agents may need to improvise to stay coordinated. Unfortunately, current methods inadequately capture the uncertainty introduced by a lack of direct communication. This paper augments existing frameworks to introduce Simple Temporal Networks for Improvisational Teamwork (STN-IT)—a formulation that captures both the temporal dependencies and uncertainties between agents who need to coordinate but lack reliable communication. We define the notion of strong controllability for STN-ITs, which establishes a static scheduling strategy for controllable agents that produces a consistent team schedule, as long as non-communicative teammates act within known problem constraints. We provide both an exact and approximate approach for finding strongly controllable schedules, empirically demonstrate the trade-offs between these approaches on benchmarks of STN-ITs, and show analytically that the exact method is correct.

Downloads

Published

2022-06-13

How to Cite

Morgan, M., Schalkwyk, J., Wang, H., Davalos, H., Martinez, R., Rohilla, V., & Boerkoel, J. (2022). Simple Temporal Networks for Improvisational Teamwork. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 261-269. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19809