Skip to main content
Springer Nature Link
Log in

Towards Team Formation via Automated Planning

  • Conference paper
  • First Online:
Coordination, Organizations, Institutions, and Norms in Agent Systems XI (COIN 2015)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 9628))

  • 705 Accesses

Abstract

Cooperative problem solving involves four key phases: (1) finding potential members to form a team, (2) forming the team, (3) formulating a plan for the team, and (4) executing the plan. We extend recent work on multi-agent epistemic planning and apply it to the problem of team formation in a blocksworld scenario. We provide an encoding of the first three phases of team formation from the perspective of an initiator, and show how automated planning efficiently yields conditional plans that guarantee certain collective intentions will be achieved. The expressiveness of the epistemic planning formalism, which supports modelling with the nested beliefs of agents, opens the prospect of broad applicability to the operationalisation of collective intention.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 52.74
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    http://www.haz.ca/research/tw-as-ap.

  2. 2.

    Note that, as with most blocksworld encodings, the fluent \(in\_b1\_room\) is false whenever an agent is holding block b1.

References

  1. Agmon, N., Stone, P.: Leading ad hoc agents in joint action settings with multiple teammates. In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, vol. 1, pp. 341–348. IFAAMAS (2012)

    Google Scholar 

  2. Amgoud, L.: An argumentation-based model for reasoning about coalition structures. In: Parsons, S., Maudet, N., Moraitis, P., Rahwan, I. (eds.) ArgMAS 2005. LNCS (LNAI), vol. 4049, pp. 217–228. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  3. Barrett, S., Agmon, N., Hazon, N., Kraus, S., Stone, P.: Communicating with unknown teammates. In: Proceedings of the Twenty-First European Conference on Artificial Intelligence, August 2014. http://www.cs.utexas.edu/users/ai-lab/?barrett:ecai14

  4. Cimatti, A., Pistore, M., Roveri, M., Traverso, P.: Weak, strong, and strong cyclic planning via symbolic model checking. Artif. Intell. 147(1), 35–84 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  5. Decker, K.S., Lesser, V.R.: Designing a family of coordination algorithms. In: Proceedings of the First International Conference on Multi-Agent Systems, pp. 73–80. AAAI Press (1995)

    Google Scholar 

  6. Dignum, F., Dunin-Keplicz, B., Verbrugge, R.: Creating collective intention through dialogue. Log. J. IGPL 9(2), 289–304 (2001)

    Article  MATH  Google Scholar 

  7. Dunin-KÈ©plicz, B., Verbrugge, R.: Teamwork in Multi-Agent Systems: A Formal Approach. Wiley, Ltd (2010)

    Book  MATH  Google Scholar 

  8. Grant, J., Kraus, S., Perlis, D.: Formal approaches to teamwork. In: Artëmov, S.N., et al. (ed.) We Will Show Them! Essays in Honour of Dov Gabbay, vol. 2, pp. 39–68. College Publications (2005)

    Google Scholar 

  9. Grosz, B., Kraus, S.: Collaborative plans for complex group actions. Artif. Intell. 86, 269–358 (1996)

    Article  MathSciNet  Google Scholar 

  10. Hoang, H., Lee-Urban, S., Muñoz-Avila, H.: Hierarchical plan representations for encoding strategic game AI. In: Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference, pp. 63–68, Marina del Rey, California, USA, 1–5 June 2005 (2005)

    Google Scholar 

  11. Hoffmann, J.: Everything you always wanted to know about planning. In: Bach, J., Edelkamp, S. (eds.) KI 2011. LNCS, vol. 7006, pp. 1–13. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  12. Johnson, M., Bradshaw, J., Duran, D., Vignati, M., Feltovich, P., Jonker, C., van Riemsdijk, M.B.: RT4T: a reconfigurable testbed for joint human-agent-robot teamwork. In: Workshop on Human-Robot Teaming, Proceedings of the Tenth Annual ACM/IEEE International Conference on Human-Robot Interaction (2015)

    Google Scholar 

  13. Johnson, M., Jonker, C., van Riemsdijk, B., Feltovich, P.J., Bradshaw, J.M.: Joint activity testbed: blocks world for teams (BW4T). In: Aldewereld, H., Dignum, V., Picard, G. (eds.) ESAW 2009. LNCS, vol. 5881, pp. 254–256. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  14. Jonker, C.M., van Riemsdijk, M.B., van de Kieft, I.C., Gini, M.: Compositionality of team mental models in relation to sharedness and team performance. In: Jiang, H., Ding, W., Ali, M., Wu, X. (eds.) IEA/AIE 2012. LNCS, vol. 7345, pp. 242–251. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  15. Kinny, D., Sonenberg, E., Ljungberg, M., Tidhar, G., Rao, A., Werner, E.: Planned team activity. In: Castelfranchi, C., Werner, E. (eds.) MAAMAW 1992. LNCS, vol. 830, pp. 227–256. Springer, Heidelberg (1994)

    Chapter  Google Scholar 

  16. Li, S., Sun, W., Miller, T.: Communication in human-agent teams for tasks with joint action. In: COIN 2015: The XIX International Workshop on Coordination, Organizations, Institutions and Norms in Multiagent Systems, pp. 111–126 (2015)

    Google Scholar 

  17. Marcolino, L.S., Zhang, C., Jiang, A.X., Tambe, M.: A detailed analysis of a multi-agent diverse team. In: Balke, T., Dignum, F., van Riemsdijk, M.B., Chopra, A.K. (eds.) COIN 2013. LNCS, vol. 8386, pp. 3–24. Springer, Heidelberg (2014)

    Chapter  Google Scholar 

  18. Muise, C., Miller, T., Felli, P., Pearce, A., Sonenberg, L.: Efficient reasoning with consistent proper epistemic knowledge bases. In: Proceedings of the 14th International Conference on Autonomous Agents and Multi-Agent Systems (2015)

    Google Scholar 

  19. Muise, C.: Planner for Relevant Policies: Bitbucket repository. https://bitbucket.org/haz/pdkb-planning/. Accessed 26 Jan 2015 (2015)

  20. Muise, C., Belle, V., Felli, P., McIlraith, S., Miller, T., Pearce, A., Sonenberg, L.: Planning over multi-agent epistemic states: A classical planning approach. In: The 29th AAAI Conference on Artificial Intelligence (2015)

    Google Scholar 

  21. Muise, C., Felli, P., Miller, T., Pearce, A.R., Sonenberg, L.: Leveraging FOND planning technology to solve multi-agent planning problems. In: Workshop on Distributed and Multi-Agent Planning, DMAP 2015 (2015)

    Google Scholar 

  22. Muise, C., McIlraith, S.A., Beck, J.C.: Improved non-deterministic planning by exploiting state relevance. In: The 22nd International Conference on Automated Planning and Scheduling (2012)

    Google Scholar 

  23. Nair, R., Tambe, M.: Hybrid BDI-POMDP framework for multiagent teaming. J. Artif. Intell. Res. (JAIR) 23, 367–420 (2005)

    MATH  Google Scholar 

  24. Rahwan, T., Michalak, T.P., Elkind, E., Faliszewski, P., Sroka, J., Wooldridge, M., Jennings, N.R.: Constrained coalition formation. In: AAAI, vol. 11, pp. 719–725 (2011)

    Google Scholar 

  25. Rao, A.S., Georgeff, M.P.: BDI agents: from theory to practice. In: Proceedings of the First International Conference on Multi-Agent Systems, ICMAS 1995, pp. 312–319 (1995)

    Google Scholar 

  26. Sandholm, T., Lesser, V.: Coalitions among computationally bounded agents. Artif. Intell. Spec. Issue Econ. Principles Multi-Agent Syst. 94(1), 99–137 (1997)

    MathSciNet  MATH  Google Scholar 

  27. Shehory, O., Kraus, S.: Methods for task allocation via agent coalition formation. Artif. Intell. 10(12), 165–200 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  28. Sierhuis, M., Jonker, C., van Riemsdijk, B., Feltovich, P.J., Bradshaw, J.M., Johnson, M.: Autonomy and interdependence in human-agent-robot teams. IEEE Intell. Syst. 27(2), 43–51 (2012)

    Article  Google Scholar 

  29. Tidhar, G., Rao, A.S., Sonenberg, E.A.: Guided team selection. In: Proceedings of the Second International Conference on Multi-Agent Systems, pp. 369–376. AAAI Press (1996)

    Google Scholar 

  30. Wooldridge, M., Jennings, N.R.: The cooperative problem-solving process. J. Log. Comput. 9(4), 563–592 (1999)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This research is partially funded by Australian Research Council Discovery Grant DP130102825, Foundations of Human-Agent Collaboration: Situation-Relevant Information Sharing.

Author information

Authors and Affiliations

  1. Department of Computing and Information Systems, University of Melbourne, Melbourne, Australia

    Christian Muise, Paolo Felli, Tim Miller, Adrian R. Pearce & Liz Sonenberg

  2. Department of Information and Computing Sciences, Universiteit Utrecht, Utrecht, The Netherlands

    Frank Dignum

Authors
  1. Christian Muise
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Frank Dignum
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Paolo Felli
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tim Miller
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Adrian R. Pearce
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Liz Sonenberg
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christian Muise .

Editor information

Editors and Affiliations

  1. Delft University of Technology , Delft, The Netherlands

    Virginia Dignum

  2. IIIA-CSIC , Barcelona, Spain

    Pablo Noriega

  3. Ozyegin University , Istanbul, Turkey

    Murat Sensoy

  4. University of Sao Paulo , Sao Paulo, São Paulo, Brazil

    Jaime Simão Sichman

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Muise, C., Dignum, F., Felli, P., Miller, T., Pearce, A.R., Sonenberg, L. (2016). Towards Team Formation via Automated Planning. In: Dignum, V., Noriega, P., Sensoy, M., Sichman, J. (eds) Coordination, Organizations, Institutions, and Norms in Agent Systems XI. COIN 2015. Lecture Notes in Computer Science(), vol 9628. Springer, Cham. https://doi.org/10.1007/978-3-319-42691-4_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-42691-4_16

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-42690-7

  • Online ISBN: 978-3-319-42691-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation