Proceedings

Flexibility and Decoupling in the Simple Temporal Problem

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2422-2427.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

In this paper we concentrate on finding a suitable metric to determine the flexibility of a Simple Temporal Problem (STP). After reviewing some flexibility metrics that have been proposed, we conclude that these metrics fail to capture the correlation between events specified in the STP, resulting in an overestimation of the available flexibility in the system. We propose to use an intuitively more acceptable flexibility metric based upon uncorrelated time-intervals for the allowed starting times of events in an STP. This metric is shown to be computable in low-polynomial time. As a byproduct of the flexibility computation, we get a decomposition of the STN almost for free: for every possible k-partitioning of the event space, a decomposition can be computed in O(k)-time. Even more importantly, we show that contrary to popular belief, such a decomposition does not affect the flexibility of the original STP.

  1. [Boerkoel and Durfee, 2011] J.C. Boerkoel and E.H. Durfee. Distributed algorithms for solving the multiagent temporal decoupling problem. In Proceedings AAMAS, 2011.
  2. [Boerkoel and Durfee, 2012] J.C. Boerkoel and E.H. Durfee. A distributed approach to summarizing spaces of multia- gent schedules. In Proceedings AAAI, 2012.
  3. [Boerkoel, 2012] J.C. Boerkoel. Distributed Approaches for Solving Constraint-based Multiagent Scheduling Prob- lems. PhD thesis, University of Michigan, 2012.
  4. [Brambilla, 2010] A. Brambilla. Artificial Intelligence in Space Systems: Coordination Through Problem Decou- pling in Multi Agent Planning for Space Systems. Lambert Academic Publishing, 2010.
  5. [Dechter et al., 1991] R. Dechter, I. Meiri, and J. Pearl. Tem- poral constraint networks. Artificial Intelligence, 49:61- 95, 1991.
  6. [Dechter, 2003] R. Dechter. Constraint processing. Morgan Kaufmann, 2003.
  7. [Floyd, 1962] R.W. Floyd. Algorithm 97: Shortest path. Communications of the ACM, 5(6):345, 1962.
  8. [Hunsberger, 2002] L. Hunsberger. Algorithms for a tempo- ral decoupling problem in multi-agent planning. In Pro- ceedings AAAI, 2002.
  9. [Morris et al., 2001] Paul H. Morris, Nicola Muscettola, and Thierry Vidal. Dynamic control of plans with temporal uncertainty. In Proceedings IJCAI, pages 494-502, 2001. IJCAI
  10. [Planken et al., 2010] L. Planken, M. de Weerdt, and C. Wit- teveen. Optimal temporal decoupling in multiagent sys- tems. In Proceedings AAMAS, 2010.
  11. [Policella et al., 2007] N. Policella, A. Cesta, A. Oddi, and S.F. Smith. From precedence constraint posting to partial order schedules: A CSP approach to robust scheduling. AI Communications, 20:163-180, 2007.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards