access icon free Concurrent multi-agent systems with temporal logic objectives: game theoretic analysis and planning through negotiation

This study examines equilibrium behaviour and negotiation protocol design for a class of systems composed of multiple, non-cooperative, agents. The agents modelled as finite-state transition systems, are autonomous, and are interacting ‘concurrently’ aiming at achieving individual tasks specified in temporal logic. Each agent has its own preferences over outcomes of its interaction with others. The agents’ goals and preferences are neither perfectly aligned nor necessarily opposing. The authors reason about agent behaviours in such a system, by formulating a concurrent multi-agent game with infinitely many stages. To enable the synthesis of strategies, they develop a negotiation protocol which ensures that under a proper design of preferences and tasks, the mutually accepted plan is a Pareto optimal pure Nash equilibrium.

Inspec keywords: multi-agent systems; planning; temporal logic; game theory

Other keywords: planning; finite-state transition systems; Pareto optimal pure Nash equilibrium; concurrent multiagent systems; temporal logic objectives; game theoretic analysis; negotiation protocol; multiagent game

Subjects: Formal logic; Artificial intelligence (theory); Game theory

References

    1. 1)
      • 22. Arnold, A.: ‘Synchronized products of transition systems and their analysis’, in Desel, J., Silva, M. (Eds.): ‘Application and theory of Petri nets(LNCS, 1420) (Springer, Berlin, Heidelberg, 1998), pp. 2627.
    2. 2)
    3. 3)
      • 17. Alur, R., La Torre, S.: ‘Deterministic generators and games for ltl fragments’. 2001 Proc. 16th Annual IEEE Symp. on Logic in Computer Science, 2001, pp. 291300.
    4. 4)
      • 14. Perrin, D., Pin, J.É.: ‘Infinite words: automata, semigroups, logic and games’ (Elsevier, 2004).
    5. 5)
    6. 6)
      • 8. Tabuada, P.: ‘Approximate simulation relations and finite abstractions of quantized control systems’, in Bemporad, A., Bicchi, A., Buttazzo, G. (Eds.): ‘Hybrid systems: computation and control, (LNCS, 4416) (Springer-Verlag, 2007), pp. 529542.
    7. 7)
      • 2. Mukund, M.: ‘From global specifications to distributed implementations’ (Kluwer Academic Publishers, 2002), pp. 1934.
    8. 8)
      • 11. Fisman, D., Kupferman, O., Lustig, Y.: ‘Rational synthesis’, in Esparza, J., , Majumdar, R. (Eds) ‘Tools and algorithms for the construction and analysis of systems’ (Cyprus, Springer Berlin Heidelberg, 2010), pp. 190204.
    9. 9)
    10. 10)
      • 6. Ulusoy, A., Smith, S.L., Ding, X.C., Belta, C.: ‘Robust multi-robot optimal path planning with temporal logic constraints’. IEEE Int. Conf. on Robotics and Automation, May 2012, pp. 46934698.
    11. 11)
    12. 12)
      • 12. Bouyer, P., Brenguier, R., Markey, N., Ummels, M.: ‘Concurrent games with ordered objectives’, in Birkedal, L. (Ed.): ‘Foundations of software science and computational structures(LNCS, 7213), (Springer, Berlin, Heidelberg, 2012), pp. 301315.
    13. 13)
      • 5. Chen, Y., Ding, X.C., Belta, C.: ‘Synthesis of distributed control and communication schemes synthesis of distributed control and communication schemes from global LTL specifications’. IEEE Conf. on Decision and Control, Orlando, FL, 2011, pp. 27182723.
    14. 14)
      • 19. Bouyer, P., Brenguier, R., Markey, N., Ummels, M.: ‘Nash equilibria in concurrent games with Büchi objectives’. IARCS Annual Conf. on Foundations of Software Technology and Theoretical Computer Science’, 2011, vol. 13, pp. 375386.
    15. 15)
      • 10. Apt, K.R., Grädel, E.: ‘Lectures in game theory for computer scientists’ (Cambridge University Press, 2011).
    16. 16)
    17. 17)
      • 18. Piterman, N., Pnueli, A., Sa’ar, Y.: ‘Synthesis of reactive (1) designs’, in Emerson, E. Allen, , Namjoshi, Kedar S. (eds) ‘Verification, model checking, and abstract interpretation’ (Springer, 2006), pp. 364380.
    18. 18)
      • 15. Thomas, W.: ‘Infinite games and verification’. Proc. 14th Int. Conf. on Computer Aided Verification (Springer-Verlag, London, UK, 2002), pp. 5864.
    19. 19)
      • 21. Shoham, Y., Leyton-Brown, K.: ‘Multiagent systems – algorithmic, game-theoretic, and logical foundations’ (Cambridge University Press, 2009).
    20. 20)
      • 3. Seboui, M.-A.B., Hadj-Alouane, N.B., Delaval, G., Rutten, E., Yeddes, M.: ‘A decentralized supervisory control approach for distributed adaptive systems’. Proc. of the Fourth Int. Conf. on Verification and Evaluation of Computer and Communication Systems, British Computer Society, 2010, pp. 1323.
    21. 21)
      • 13. Murray, C., Gordon, G.: ‘Multi-robot negotiation: approximating the set of subgame perfect equilibria in general-sum stochastic games’ (Carnegie Mellon University, School of Computer Science, Machine Learning Department, 2006).
    22. 22)
      • 20. Reiter, R.: ‘Knowledge in action: logical foundations for specifying and implementing dynamical systems’ (MIT Press, 2001).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cta.2014.0611
Loading

Related content

content/journals/10.1049/iet-cta.2014.0611
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading