Abstract
Embedding planning systems in real-world domains has led to the necessity of Distributed Continual Planning (DCP) systems where planning activities are distributed across multiple agents and plan generation may occur concurrently with plan execution. A key challenge in DCP systems is how to coordinate activities for a group of planning agents. This problem is compounded when these agents are situated in a real-world dynamic domain where the agents often encounter differing, incomplete, and possibly inconsistent views of their environment. To date, DCP systems have only focused on cases where agents’ behavior is designed to optimize a global plan. In contrast, this paper presents a temporal reasoning mechanism for self-interested planning agents. To do so, we model agents’ behavior based on the Belief-Desire-Intention (BDI) theoretical model of cooperation, while modeling dynamic joint plans with group time constraints through creating hierarchical abstraction plans integrated with temporal constraints network. The contribution of this paper is threefold: (i) the BDI model specifies a behavior for self interested agents working in a group, permitting an individual agent to schedule its activities in an autonomous fashion, while taking into consideration temporal constraints of its group members; (ii) abstract plans allow the group to plan a joint action without explicitly describing all possible states in advance, making it possible to reduce the number of states which need to be considered in a BDI-based approach; and (iii) a temporal constraints network enables each agent to reason by itself about the best time for scheduling activities, making it possible to reduce coordination messages among a group. The mechanism ensures temporal consistency of a cooperative plan, enables the interleaving of planning and execution at both individual and group levels. We report on how the mechanism was implemented within a commercial training and simulation application, and present empirical evidence of its effectiveness in real-life scenarios and in reducing communication to coordinate group members’ activities.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Allen, J.F.: Maintaining knowledge about temporal intervals. Communications of the ACM 26, 832–843 (1983)
Allen, J.F.: Towards a general theory of action and time. Artificial Intelligence Journal 23(2), 123–144 (1984)
Barbulescu, L., Rubinstein, Z.B., Smith, S.F., Zimmerman, T.L.: Distributed coordination of mobile agent teams: the advantage of planning ahead. In: AAMAS, pp. 1331–1338 (2010)
van Beek, P.: Reasoning about qualitative temporal information. Artificial Intelligence Journal 58(1):297–326 (1992)
Boerkoel, J.C. Jr., Durfee, E.H.: Evaluating hybrid constraint tightening for scheduling agents. In: AAMAS, pp. 673–680 (2009)
Boerkoel, J.C. Jr., Durfee, E.H.: Distributed algorithms for solving the multiagent temporal decoupling problem. In: AAMAS, pp. 141–148 (2011)
Boerkoel, J.C. Jr., Durfee, E.H.: A distributed approach to summarizing spaces of multiagent schedules. In: AAAI, pp. 1742–1748 (2012)
Chen, Y., Wah, B.W., Hsu, C.W.: Temporal planning using subgoal partitioning and resolution in SGPlan. Journal of Artificial Intelligence Research 26, 323–369 (2006)
Chien, S., Rabideau, G., Willis, J., Mann, T.: Automating planning and scheduling of shuttle payload operations. Artificial Intelligence Journal 114(1), 239–255 (1999)
Chien, S., Rabideau, G., Knight, R., Sherwood, R., Engelhardt, B., Mutz, D., Estlin, T., Smith, B., Fisher, F., Barrett, T., Stebbins, G., Tran, D.: ASPEN—automating space mission operations using automated planning and scheduling. In: Space Ops, pp. 1–10 (2000)
Clement, B.J., Barrett, A.C.: Continual coordination through shared activities. In: AAMAS, pp. 57–64 (2003)
Corkill, D.: Hierarchical planning in a distributed environment. In: IJCAI, pp. 168–175 (1979)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, London (2001)
Currie, K., Tate, A.: O-Plan: the open planning architecture. Artificial Intelligence Journal 52(1), 49–86 (1991)
Dean, T.L., McDermott, D.V.: Temporal data base management. Artificial Intelligence Journal 32(1), 1–55 (1987)
Dechter, R., Meiri, I., Pearl, J.: Temporal constraint networks. Artificial Intelligence Journal 49(1), 61–95 (1991)
Demetrescu, C., Italiano, G.F.: Experimental analysis of dynamic all pairs shortest path algorithms. ACM Trans. Algor. 2(4), 578–601 (2006)
desJardins, M., Durfee, E.H., Ortiz, C., Wolverton, M.: A survey of research in distributed continual planning. AI Mag 1(4), 13–22 (1999)
Dudek, G., Jenkin, M.R.M., Milios, E., Wilkes, D.: A taxonomy for multi-agent robotics. Auton. Robot. 3(4), 375–397 (1996)
Durfee, E.H., Lesser, V.R.: Partial global planning: a coordination framework for distributed hypothesis formation. IEEE Trans. Syst. Man Cybern. 21(5), 1167–1183 (1991)
Durfee, E.H.: Distributed problem solving and planning. In: Weiss, G. (ed.) Multiagent Systems: a Modern Approach to Distributed Artificial Intelligence, pp. 121–164. MIT Press, Cambridge, MA (1999)
El-Kholy, A., Richards, B.: Temporal and resource reasoning in planning: the parcPlan approach. In: ECAI, pp. 614–618 (1996)
Erol, K., Nau, D., Hendler, J.: HTN planning: complexity and expressivity. In: AAAI, pp. 1123–1128 (1994)
Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, CA (1979)
Ghallab, M., Nau, D., Traverso, P.: Automated Planning: Theory & Practice. Morgan Kaufmann, San Francisco, CA (2004)
Grosz, B.J., Kraus, S.: Collaborative plans for complex group action. Artificial Intelligence Journal 86(2), 269–357 (1996)
Grosz, B.J., Kraus, S.: The evolution of SharedPlans. In: Rao, A., Wooldridge, M. (eds.) Foundations and Theories of Rational Agency, pp. 227–262. Academic, Boston, MA (1999)
Grosz, B.J., Hunsberger, L., Kraus, S.: Planning and acting together. AI Mag 20(4), 23–34 (1999)
Hadad, M., Kraus, S.: Sharedplans in electronic commerce. In: Klusch, M. (ed.) Intelligent Information Agents, pp. 204–231. Springer, New York (1999)
Hadad, M., Kraus, S.: A mechanism for temporal reasoning by collaborative agents. In: CIA, pp. 229–234 (2001)
Hadad, M., Kraus, S.: Exchanging and combining temporal information by collaborative agents. In: CIA, pp. 279–286 (2002)
Hadad, M., Rosenfeld, A.: Adapt: abstraction hierarchies to better simulate teamwork under dynamics. In: Agents for Educational Games and Simulations, pp. 166–182 (2012)
Hadad, M., Kraus, S., Gal, Y., Lin, R.: Time reasoning for a collaborative planning agent in a dynamic environment. Ann. Math. Artif. Intell. 37(4), 331–380 (2003)
Harbers, T., Maheswaran, R.T., Szekely, P.: Centralized, distributed or something else? making timely decisions in multi-agent systems. In: AAAI, p. 738 (2007)
Hirayama, K., Yokoo, M.: Distributed partial constraint satisfaction problem. In: Principles and Practice of Constraint Programming, pp. 222–236 (1997)
Hirayama, K., Yokoo, M.: An approach to over-constrained distributed constraint satisfaction problems: distributed hierarchical constraint satisfaction. In: AAMAS, pp. 135–142 (2000)
Horling, B., Lesser, V., Vincent, R., Wagner, T., Raja, A., Zhang, S., Decker, K., Garvey, A.: The TAEMS White Paper. Multi-Agent Systems Lab University of Massachusetts (1999)
Hunsberger, L.: Distributing the control of a temporal network among multiple agents. In: AAMAS, pp. 899–906 (2003)
Jennings, N.R.: Controlling cooperative problem solving in industrial multi-agent systems using joint intentions. Artificial Intelligence Journal 75(2), 1–46 (1995)
Kamar, E., Gal, Y., Grosz, B.: Incorporating helpful behavior into collaborative planning. In: AAMAS, pp. 875–882 (2009)
Kaminka, G.A., Frenkel, I.: Integration of coordination mechanisms in the BITE multi-robot architecture. In: ICRA, pp. 2859–2866 (2007)
Karacapilidis, N.I.: Planning under uncertainty: a qualitative approach. In: EPIA, pp. 285–296 (1995)
Kim, Y., Krainin, M., Lesser, V.: Effective variants of the max-sum algorithm for radar coordination and scheduling. In: Proceedings of the 2011 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, pp. 357–364 (2011)
Kitano, H.: Robocup rescue: A grand challenge for multi-agent systems. In: ICMAS, Boston, MA, pp. 5–12 (2000)
Kohout, B.: The DARPA COORDINATORS program: a retrospective. In: CTS, pp. 342–342 (2011)
Lansky, A., Getoor, L.: Scope and abstraction: two criteria for localized planning. In: IJCAI, pp. 1612–1619 (1995)
Lesser, V., Decker, K., Wagner, T., Carver, N., Garvey, A., Horling, B., Neiman, D., Podorozhny, R., Nagendra Prasad, M., Raja, A., Vincent, R., Xuan, P., Zhang, X.Q.: Evolution of the GPGP/TEAMS domain independent coordination framework. In: AAMAS, pp. 87–143 (2004)
Lever, J., Richards, B.: parcPlan: a planning architecture with parallel actions, resources and constraints. In: Methodologies for Intelligent Systems, pp. 213–222 (1994)
Liu, J.S., Sycara, K.: Exploiting problem structure for distributed constraint optimization. In: ICMAS, pp. 246–253 (1995)
Maheswaran, R.T., Szekely, P.: Criticality metrics for distributed plan and schedule management. In: ICAPS, vol. 2, p. 2 (2008)
Maheswaran, R., Rogers, C.M., Sanchez, R., Szekely, P., Gati, G., Smyth, K., VanBuskirk, C.: Multi-agent systems for the real world. In: AAMAS, pp. 1281–1282 (2009)
Mailler, R., Lesser, V.: Solving distributed constraint optimization problems using cooperative mediation. In: AAMAS, pp. 438–445 (2004)
Mailler, R., Lesser, V.: Using cooperative mediation to solve distributed constraint satisfaction problems. In: AAMAS, pp. 446–453 (2004)
Miller, D.P., Gat, E.: Exploiting known topologies to navigate with low-computation sensing. In: Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, vol. 1383, pp. 425–435 (1991)
Modi, P.J., Shen, W.M., Tambe, M., Yokoo, M.: Adopt: asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence Journal 161(1), 149–180 (2005)
Mohr, R., Henderson, T.C.: Arc and path consistency revisited. Artificial Intelligence Journal 28(2), 225–233 (1986)
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic ‘phase transitions’. Nature 400(6740), 133–137 (1999)
Montanari, U.: Networks of constraints: fundamental properties and applications to picture processing. Inf. Sci. 7, 95–132 (1974)
Morris, P., Muscettola, N., Vidal, T., et al.: Dynamic control of plans with temporal uncertainty. In: IJCAI, pp. 494–502 (2001)
Musliner, D.J., Dufree, E.H., Shin, K.G.: CIRCA: a cooperative intelligent real-time control architecture. IEEE Trans. Comput. 23(6), 1561–1574 (1993)
Musliner, D.J., Dufree, E.H., Shin, K.G.: World modeling for dynamic construction of real-time control plans. Artificial Intelligence Journal 74(1), 83–127 (1995)
Nareyek, A.: A planning model for agents in dynamic and uncertain real-time environments. In: AIPS Workshop on Integrating Planning, pp. 7–14 (1998)
Nareyek, A.: Open world planning as scsp. In: AAAI Workshop on Constraints and AI Planning, pp. 35–46 (2000)
Nau, D., Cao, Y., Lotem, A., Muñoz-Avila, H.: SHOP and M-SHOP: planning with ordered task decomposition. Technical report, University of Maryland (2000)
Nau, D.S., Au, T.C., Ilghami, O., Kuter, U., Murdock, J.W., Wu, D., Yaman, F.: SHOP2: an HTN planning system. Journal of Artificial Intelligence Research 20, 379–404 (2003)
Penberthy, J.S., Weld, D.: Temporal planning with continuous change. In: AAAI, pp. 1010–1015 (1994)
Petcu, A.: A class of algorithms for distributed constraint optimization. Phd. thesis no. 3942, Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland (2007)
Planken, L., De Weerdt, M., van der Krogt, R., Rintanen, J., Nebel, B., Beck, J.C., Hansen, E.: P3c: a new algorithm for the simple temporal problem. In: ICAPS, pp. 256–263 (2008)
Planken, L.R., de Weerdt, M.M., Yorke-Smith, N.: Incrementally solving stns by enforcing partial path consistency. In: ICAPS, pp. 129–136 (2010)
Pynadath, D.V., Tambe, M.: The communicative multiagent team decision problem: analyzing teamwork theories and models. Journal of Artificial Intelligence Research 16, 389–423 (2002)
Rochlin, I., Sarne, D., Laifenfeld, M.: Coordinated exploration with a shared goal in costly environments. In: ECAI, pp. 690–695 (2012)
Sarne, D., Grosz, B.J.: Determining the value of information for collaborative multi-agent planning. Auton. Agent. Multi-Agent Syst. 26(3), 456–496 (2013)
Shah, J.A., Williams, B.C.: Fast dynamic scheduling of disjunctive temporal constraint networks through incremental compilation. In: ICAPS, pp. 322–329 (2008)
Shah, J.A., Conrad, P.R., Williams, B.C.: Fast distributed multi-agent plan execution with dynamic task assignment and scheduling. In: ICAPS, pp. 289–296 (2009)
Shu, I., Effinger, R., Williams, B.: Enabling fast flexible planning through incremental temporal reasoning with conflict extraction. In: ICAPS, pp. 252–261 (2005)
Simmons, R.: An architecture for coordinating planning, sensing, and action. In: Procs. DARPA Workshop on Innovative Approaches to Planning, Scheduling and Control, pp. 292–297 (1990)
Smith, S.F., Gallagher, A., Zimmerman, T.: Distributed management of flexible times schedules. In: AAMAS, p. 74 (2007)
Sonenberg, E., Tidhar, G., Werner, E., Kinny, D., Ljungberg, M., Rao, A.: Planned team activity. Technical Report 26, Australian Artificial Intelligence Institute, Australia (1992)
Stefanovich, N., Farinelli, A., Rogers, A., Jennings, N.R.: Resource-aware junction trees for efficient multi-agent coordination. In: AAMAS, pp. 363–370 (2011)
Stergiou, K., Koubarakis, M.: Backtracking algorithms for disjunctions of temporal constraints. Artificial Intelligence Journal 120(1), 81–117 (2000)
Sultanik, E., Modi, P.J., Regli, W.C.: On modeling multiagent task scheduling as a distributed constraint optimization problem. In: IJCAI, pp. 1531–1536 (2007)
Tambe, M.: Toward flexible teamwork. Journal of Artificial Intelligence Research 7, 83–124 (1997)
Vidal, T., Fargier, H.: Handling contingency in temporal constraint networks: from consistency to controllabilities. J. Exp. Theor. Artif. Intell. 11, 23–45 (1999)
Vidal, T., Ghallab, M.: Dealing with uncertain durations in temporal constraint networks dedicated to planning. In: ECAI, pp. 48–52 (1996)
Vilain, M., Kautz, H.A.: Constraint propagation algorithms for temporal reasoning. In: AAAI, pp. 132–144 (1986)
Wehowsky, A., Block, S., Williams, B.: Robust distributed coordination of heterogeneous robots through temporal plan networks. In: ICAPS Workshop on Multiagent Planning and Scheduling, pp. 67–72 (2005)
Weld, D., Anderson, C., Smith, D.: Extending graphplan to handle uncertainty and sensing actions. In: AAAI, pp. 897–904 (1998)
Wilkins, D.E., Myers, K.L., Lowrance, J.D., Wesley, L.P.: Planning and reacting in uncertain and dynamic environments. J. Exp. Theor. Artif. Intell. 7(1), 197–227 (1995)
Wolverton, M., desJardins, M.: Controlling communication in distributed planning using irrelevance reasoning. In: AAAI, pp. 868–874 (1998)
Xu, L., Choueiry, B.: Improving backtrack search for solving the tcsp. In: Principles and Practice of Constraint Programming, pp. 754–768 (2003)
Yokoo, M.: Distributed Constraint Statification. Springer, Germany (2001)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hadad, M., Kraus, S., Ben-Arroyo Hartman, I. et al. Group planning with time constraints. Ann Math Artif Intell 69, 243–291 (2013). https://doi.org/10.1007/s10472-013-9363-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-013-9363-9