Managing dynamic multi-agent simple temporal network

Managing dynamic multi-agent simple temporal network

Guillaume Casanova Charles Lesire Cédric Pralet

Onera – The French Aerospace Lab F-31055, Toulouse, France

Corresponding Author Email:
30 April 2016
| Citation

The realization of plans of activities by several agents is usually subject to a set of temporal constraints, including synchronization constraints between agents. To represent the set of temporal constraints imposed on distributed plans, the framework of Multi-agent Simple Temporal Network (MaSTN) can be used. In this paper, we consider the problem of maintaining the temporal consistency of distributed plans during execution, when temporal constraints may be updated. We propose new incremental algorithms for managing dynamic MaSTNs, and we analyze the performance of these algorithms when communications are intermittent.


multi-agent planning, coordination, execution.

1. Introduction
2. Contexte
3. Algorithmes incrémentaux pour les MaSTN dynamiques
4. Analyse théorique
5. Expérimentations
6. Conclusion et perspectives

Bechon P., Barbier M., Infantes G., Lesire C., Vidal V. (2014). Hipop: Hierarchical partial-order planning. In European starting AI researcher symposium (stairs). Prague, Czech Republic.

Bechon P., Casanova G., Lesire C., Barbier M., Infantès G., Pralet C. et al. (2015). Multirobot planning and execution for surveillance missions. In Onera-dlr aerospace symposium (odas). Toulouse, France.

Boerkoel J. C., Planken L., Wilcox R., Shah J. A. (2013). Distributed algorithms for incrementally maintaining multiagent simple temporal networks. In Int. conf. on automated planning and scheduling (icaps). Rome, Italy.

Cervoni R., Cesta A., Oddi A. (1994). Managing dynamic temporal constraint networks. In Int. conf. on artificial intelligence planning systems (aips). Chicago, IL, USA.

Cesta A., Oddi A. (1996). Gaining efficiency and flexibility in the simple temporal problem. In Int. workshop on temporal representation and reasoning (time). Key West, FL, USA.

Davis E. (1987). Constraint propagation with interval labels. Artificial Intelligence, vol. 32, no 3, p. 281-331.

Dechter R., Meiri I., Pearl J. (1991). Temporal constraint networks. Artificial Intelligence, vol. 49, no 1-3, p. 61-95.

Di Rocco M., Pecora F., Saffiotti A. (2013). When robots are late: Configuration planning for multiple robots with dynamic goals. In Int. conf. on intelligent robots and systems (iros). Tokyo, Japan.

Lemai S., Ingrand F. (2004). Interleaving temporal planning and execution in robotics domains. In National conf. on artificial intelligence (aaai). San Jose, CA, USA.

McGann C., Py F., Rajan K., Thomas H., Henthorn R., McEwen R. (2008). A deliberative architecture for auv control. In Int. conf. on robotics and automation (icra). Pasadena, CA, USA.

Morris P. H., Muscettola N., Vidal T. (2001). Dynamic control of plans with temporal uncertainty. In Int. joint conf. on artificial intelligence (ijcai). Seattle, WA, USA.

Parker L. E. (2008). Distributed intelligence : Overview of the field and its application in multi-robot systems. Journal of Physical Agents, vol. 2.

Planken L.,Weerdt M. de, Yorke-Smith N. (2010). Incrementally solving stns by enforcing partial path consistency. In Int. conf. on automated planning and scheduling (icaps). Toronto, Canada.

Planken L. R., Weerdt M. M. de, Krogt R. P. van der. (2008). P3c: A new algorithm for the simple temporal problem. In Int. conf. on automated planning and scheduling (icaps). Sydney, Australia.

Pralet C., Lesire C. (2014). Deployment of mobile wireless sensor networks for crisis management: A constraint-based local search approach. In Int. conf. on principles and practice of constraint programming (cp). Lyon, France.

Xu L., Choueiry B. Y. (2003). A new efficient algorithm for solving the simple temporal problem. In Int. symposium on temporal representation and reasoning (time). Cairns, Queensland, Australia.