Project: Game-Theoretic Agent Programming
supported by the Austrian Science Fund (FWF) under project number P18146 (see also TUWIS++)
Contents
Project Team
Goal of the Project
The main goal of the project is to develop high-level formalisms and techniques for programming systems of multiple agents in uncertain and partially observable environments. We want to develop such agent programming languages by combining formalisms from reasoning about actions (which have nice software engineering features), planning under uncertainty (for modeling uncertainty and partial observability), and game theory (for modeling cooperation and competition in multi-agent systems). More precisely, we aim at an approach where the logic-oriented languages for reasoning about actions around Golog and around the action language C+ are combined with multi-agent variants of POMDPs and with partially observable Markov games, for cooperation and competition, respectively (in which planning under uncertainty and partial observability is combined with game theory). We plan to design algorithms that are based on reductions to answer set programming, and to develop implementations on top of existing answer set programming technology, such as DLV and SMODELS.
Results of the Project
The most important results of the project concentrate around the agent programming languages POGTGolog and TeamGolog, which are the first approaches in the literature to combine agent programming in Golog (on top of the situation calculus) with planning under uncertainty and game theory (in partially observable stochastic games). Another important result is the adaptive agent programming language AGTGolog, which is the first approach in the literature to combine agent programming in Golog with planning under uncertainty, game theory, and reinforcement learning. More specifically, our results on POGTGolog, TeamGolog, and AGTGolog are briefly summarized as follows:
In [4,5,7,18], we present the agent programming language POGTGolog (Partially Observable Game-Theoretic Golog), which integrates explicit agent programming in Golog with game-theoretic multi-agent planning in partially observable stochastic games. In this framework, we assume one team of cooperative agents acting under partial observability, where the agents may also have different initial belief states and not necessarily the same rewards. POGTGolog allows for specifying a partial control program in a high-level logical language, which is then completed by an interpreter in an optimal way. To this end, we define a formal semantics of POGTGolog programs in terms of Nash equilibria, and we then specify a POGTGolog interpreter that computes one of these Nash equilibria. We illustrate the usefulness of POGTGolog along several examples.
In [10,21], we present and explore the agent programming language TeamGolog, which is a novel approach to programming a team of cooperative agents under partial observability. Every agent is associated with a partial control program in Golog, which is completed by the TeamGolog interpreter in an optimal way by assuming a decision-theoretic semantics. The approach is based on the key concepts of a synchronization state and a communication state, which allow the agents to passively resp. actively coordinate their behavior, while keeping their belief states, observations, and activities invisible to the other agents. We show the practical usefulness of the TeamGolog approach in a rescue simulated domain. We describe the algorithms behind the TeamGolog interpreter and provide a prototype implementation. We also show through experimental results that the TeamGolog approach outperforms a standard greedy one in the rescue simulated domain.
In [8,9,22], we present and explore a novel approach to adaptive multi-agent programming, which is based on an integration of the agent programming language GTGolog with adaptive dynamic programming techniques. GTGolog combines explicit agent programming in Golog with multi-agent planning in stochastic games. A drawback of this framework, however, is that the transition probabilities and immediate rewards of the domain must be known in advance and then cannot change anymore. But such data is often not available in advance and may also change over time. The adaptive generalization of GTGolog in this paper is directed towards letting the agents themselves explore and adapt these data, which is more useful for realistic applications. We present an algorithm for learning policies and show that under suitable conditions it converges and produces optimal policies. This multi-agent learning algorithm includes as a special case a single-agent learning algorithm for DTGolog. We use high-level programs for generating both abstract states and optimal policies, which benefits from the deep integration between action theory and high-level programs in the Golog framework.
Other innovative results of the project are (1) the combination of the language for reasoning about actions C+ with partially observable stochastic games, and (2) an exploration of applications of game-theoretic agent programming in e-commerce and in the Semantic Web, which are briefly summarized as follows:
In [6,19], we introduce the action language GC+ for reasoning about actions in multi-agent systems under probabilistic uncertainty and partial observability, which is an extension of the action language C that is inspired by partially observable stochastic games. We provide a finite-horizon value iteration for this framework and show that it characterizes finite-horizon Nash equilibria. We also describe how the framework can be implemented on top of nonmonotonic causal theories. Furthermore, we present acyclic action descriptions in GC+ as an important special case where transitions are computable in polynomial time.
In [15,23], we explore the application of game-theoretic agent programming in e-commerce, namely, in multi-attribute negotiation, which has recently been extensively studied from a game-theoretic viewpoint. Towards automated multi-attribute negotiation in the Semantic Web, we introduce Boolean description logic games, which are a combination of Boolean games with ontological background knowledge, formulated in expressive description logics. We discuss several generalizations, and show how a travel and a service negotiation scenario can be formulated in Boolean description logic games, which gives evidence of their practical usefulness.
In [11-14], towards an application of game-theoretic agent programming in the Semantic Web, which is heavily based on ontologies, we present an integration of Poole's independent choice logic with the expressive description logics standing behind the standard web ontology languages OWL Lite and OWL DL. Note that the independent choice logic is a formalism for reasoning about actions in multi-agent systems, which also allows for representing games.
Refereed Conference Papers
| [1] |
Alberto Finzi and Thomas Lukasiewicz Structure-Based Causes and Explanations in the Independent Choice Logic In C. Meek and U. Kjaerulff, editors, Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence (UAI 2003), pp. 225-232, Acapulco, Mexico, August 2003. Morgan Kaufmann, 2003. |
| [2] |
Alberto Finzi and Thomas Lukasiewicz Game-Theoretic Agent Programming in Golog In R. López de Mántaras and L. Saitta, editors, Proceedings of the 16th biennial European Conference on Artificial Intelligence (ECAI 2004), pp. 23-27, Valencia, Spain, August 2004. IOS Press, 2004. |
| [3] |
Alberto Finzi and Thomas Lukasiewicz Relational Markov Games In J. Alferes and J. Leite, editors, Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004), pp. 320-333, Lisbon, Portugal, September 2004. Volume 3229 of Lecture Notes in Computer Science, Springer, 2004. |
| [4] |
Alberto Finzi and Thomas Lukasiewicz Game-Theoretic Agent Programming in Golog under Partial Observability In P. Gmytrasiewicz and S. Parsons, editors, Proceedings of the IJCAI-2005 Workshop on Game-Theoretic and Decision-Theoretic Agents (GTDT 2005), July 2005. |
| [5] |
Alberto Finzi and Thomas Lukasiewicz Game-Theoretic Golog under Partial Observability In F. Dignum, V. Dignum, S. Koenig, S. Kraus, M. Pechoucek, M. Singh, D. Steiner, S. Thompson, and M. Wooldridge, editors, Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2005), pp. 1301-1302, Utrecht, The Netherlands, July 2005. ACM Press, 2005. |
| [6] |
Alberto Finzi and Thomas Lukasiewicz Game-Theoretic Reasoning about Actions in Nonmonotonic Causal Theories In C. Baral, G. Greco, N. Leone, and G. Terracina, editors, Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2005), pp. 185-197, Diamante, Cosenza, Italy, September 2005. Volume 3662 of Lecture Notes in Computer Science, Springer, 2005. |
| [7] |
Alberto Finzi and Thomas Lukasiewicz Game-Theoretic Agent Programming in Golog under Partial Observability In C. Freksa, M. Kohlhase, and K. Schill, editors, Proceedings of the 29th Annual German Conference on Artificial Intelligence (KI 2006), pp. 113-127, Bremen, Germany, June 2006. Volume 4314 of Lecture Notes in Computer Science, Springer, 2007. |
| [8] |
Alberto Finzi and Thomas Lukasiewicz Adaptive Multi-Agent Programming in GTGolog In C. Freksa, M. Kohlhase, and K. Schill, editors, Proceedings of the 29th Annual German Conference on Artificial Intelligence (KI 2006), pp. 389-403, Bremen, Germany, June 2006. Volume 4314 of Lecture Notes in Computer Science, Springer, 2007. |
| [9] |
Alberto Finzi and Thomas Lukasiewicz Adaptive Multi-Agent Programming in GTGolog In G. Brewka, S. Coradeschi, A. Perini, and P. Traverso, editors, Proceedings of the 17th biennial European Conference on Artificial Intelligence (ECAI 2006), pp. 753-754, Riva del Garda, Italy, August/September 2006. IOS Press, 2006. |
| [10] |
Alessandro Farinelli, Alberto Finzi, and Thomas
Lukasiewicz Team Programming in Golog under Partial Observability In M. M. Veloso, editor, Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 2097-2102, Hyderabad, India, January 2007. AAAI Press / IJCAI, 2007. |
| [11] |
Andrea Calì and Thomas Lukasiewicz Tightly Integrated Probabilistic Description Logic Programs for the Semantic Web In V. Dahl and I. Niemelä, editors, Proceedings of the 23rd International Conference on Logic Programming (ICLP 2007), pp. 428-429, Porto, Portugal, September 2007. Volume 4670 of Lecture Notes in Computer Science, Springer, 2007. |
| [12] |
Thomas Lukasiewicz Tractable Probabilistic Description Logic Programs In H. Prade and V.S. Subrahmanian, editors, Proceedings of the 1st International Conference on Scalable Uncertainty Management (SUM 2007), pp. 143-156, Washington DC, USA, October 2007. Volume 4772 of Lecture Notes in Computer Science, Springer, 2007. |
| [13] |
Andrea Calì, Thomas Lukasiewicz, Livia Predoiu, and Heiner Stuckenschmidt A Framework for Representing Ontology Mappings under Probabilities and Inconsistency In F. Bobillo, P. Costa, C. d'Amato, N. Fanizzi, F. Fung, T. Lukasiewicz, T. Martin, M. Nickles, Y. Peng, M. Pool, P. Smrž, and P. Vojtáš, editors, Proceedings of the ISWC-2007 Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2007), Busan, Korea, November 2007. Volume 327 of CEUR Workshop Proceedings, CEUR-WS.org, 2008. |
| [14] |
Andrea
Calì, Thomas Lukasiewicz, Livia Predoiu, and Heiner
Stuckenschmidt Tightly Integrated Probabilistic Description Logic Programs for Representing Ontology Mappings In S. Hartmann and G. Kern-Isberner, editors, Proceedings of the 5th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2008), pp. 178-198, Pisa, Italy, February 2008. Volume 4932 of Lecture Notes in Computer Science, Springer, 2008. |
| [15] |
Thomas Lukasiewicz and Azzurra Ragone Combining Boolean Games with the Power of Ontologies for Automated Multi-Attribute Negotiation in the Semantic Web Accepted for publication in Proceedings of the 2nd International Workshop on Service Matchmaking and Resource Retrieval in the Semantic Web (SMRR 2008), Karlsruhe, Germany, October 2008. |
Technical Reports
| [16] |
Alberto Finzi and Thomas Lukasiewicz Structure-Based Causes and Explanations in the Independent Choice Logic Technical Report Nr. 1843-03-06, Institut für Informationssysteme, Technische Universität Wien, April 2003. |
| [17] |
Alberto Finzi and Thomas Lukasiewicz Game-Theoretic Agent Programming in Golog Technical Report Nr. 1843-04-02, Institut für Informationssysteme, Technische Universität Wien, April 2007. |
| [18] |
Alberto Finzi and Thomas Lukasiewicz Game-Theoretic Golog under Partial Observability Technical Report Nr. 1843-05-02, Institut für Informationssysteme, Technische Universität Wien, December 2006. |
| [19] |
Alberto Finzi and Thomas Lukasiewicz Game-Theoretic Reasoning about Actions in Nonmonotonic Causal Theories Technical Report Nr. 1843-05-04, Institut für Informationssysteme, Technische Universität Wien, June 2005. |
| [20] |
Andrea Calì and Thomas Lukasiewicz Tightly Integrated Probabilistic Description Logic Programs Technical Report Nr. 1843-07-05, Institut für Informationssysteme, Technische Universität Wien, March 2007. |
| [21] |
Alessandro Farinelli, Alberto Finzi, and Thomas Lukasiewicz Team Programming in Golog under Partial Observability Technical Report Nr. 1843-08-04, Institut für Informationssysteme, Technische Universität Wien, May 2008. |
| [22] |
Alberto Finzi and Thomas Lukasiewicz Adaptive Game-Theoretic Agent Programming in Golog Technical Report Nr. 1843-08-07, Institut für Informationssysteme, Technische Universität Wien, August 2008. |
| [23] |
Thomas Lukasiewicz and Azzurra Ragone Combining Boolean Games with the Power of Ontologies for Automated Multi-Attribute Negotiation in the Semantic Web Technical Report Nr. 1843-08-08, Institut für Informationssysteme, Technische Universität Wien, August 2008. |