- -

A Better-response Strategy for Self-interested Planning Agents

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

A Better-response Strategy for Self-interested Planning Agents

Show simple item record

Files in this item

dc.contributor.author Jordán, Jaume es_ES
dc.contributor.author Torreño Lerma, Alejandro es_ES
dc.contributor.author de Weerdt, M. es_ES
dc.contributor.author Onaindia De La Rivaherrera, Eva es_ES
dc.date.accessioned 2019-05-31T20:43:20Z
dc.date.available 2019-05-31T20:43:20Z
dc.date.issued 2018 es_ES
dc.identifier.issn 0924-669X es_ES
dc.identifier.uri http://hdl.handle.net/10251/121362
dc.description.abstract [EN] When self-interested agents plan individually, interactions that prevent them from executing their actions as planned may arise. In these coordination problems, game-theoretic planning can be used to enhance the agents¿ strategic behavior considering the interactions as part of the agents¿ utility. In this work, we define a general-sum game in which interactions such as conflicts and congestions are reflected in the agents¿ utility. We propose a better-response planning strategy that guarantees convergence to an equilibrium joint plan by imposing a tax to agents involved in conflicts. We apply our approach to a real-world problem in which agents are Electric Autonomous Vehicles (EAVs). The EAVs intend to find a joint plan that ensures their individual goals are achievable in a transportation scenario where congestion and conflicting situations may arise. Although the task is computationally hard, as we theoretically prove, the experimental results show that our approach outperforms similar approaches in both performance and solution quality. es_ES
dc.description.sponsorship This work is supported by the GLASS project TIN2014-55637-C2-2-R of the Spanish MINECO and the Prometeo project II/2013/019 funded by the Valencian Government. es_ES
dc.language Inglés es_ES
dc.publisher Springer-Verlag es_ES
dc.relation MINECO/TIN2011-27652-C03-01 es_ES
dc.relation MINECO/TIN2014-55637-C2-2-R-AR es_ES
dc.relation GV/PROMETEOII/2013/019 es_ES
dc.relation.ispartof Applied Intelligence es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Planning es_ES
dc.subject Game theory es_ES
dc.subject Best-response es_ES
dc.subject Better-response es_ES
dc.subject Nash equilibrium es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.title A Better-response Strategy for Self-interested Planning Agents es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s10489-017-1046-5 es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Jordán, J.; Torreño Lerma, A.; De Weerdt, M.; Onaindia De La Rivaherrera, E. (2018). A Better-response Strategy for Self-interested Planning Agents. Applied Intelligence. 48(4):1020-1040. https://doi.org/10.1007/s10489-017-1046-5 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion http://doi.org/10.1007/s10489-017-1046-5 es_ES
dc.description.upvformatpinicio 1020 es_ES
dc.description.upvformatpfin 1040 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 48 es_ES
dc.description.issue 4 es_ES
dc.relation.pasarela S\342987 es_ES
dc.contributor.funder Generalitat Valenciana es_ES
dc.contributor.funder Ministerio de Economía y Competitividad es_ES
dc.relation.references Aghighi M, Bäckström C (2016) A multi-parameter complexity analysis of cost-optimal and net-benefit planning. In: Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling. AAAI Press, London, pp 2–10 es_ES
dc.relation.references Bercher P, Mattmüller R (2008) A planning graph heuristic for forward-chaining adversarial planning. In: ECAI, vol 8, pp 921–922 es_ES
dc.relation.references Brafman RI, Domshlak C, Engel Y, Tennenholtz M (2009) Planning games. In: IJCAI 2009, Proceedings of the 21st international joint conference on artificial intelligence, pp 73–78 es_ES
dc.relation.references Bylander T (1994) The computational complexity of propositional strips planning. Artif Intell 69(1):165–204 es_ES
dc.relation.references Chen X, Deng X (2006) Settling the complexity of two-player nash equilibrium. In: 47th annual IEEE symposium on foundations of computer science, 2006. FOCS’06. IEEE, pp 261–272 es_ES
dc.relation.references Chien S, Sinclair A (2011) Convergence to approximate nash equilibria in congestion games. Games and Economic Behavior 71(2):315–327 es_ES
dc.relation.references de Cote EM, Chapman A, Sykulski AM, Jennings N (2010) Automated planning in repeated adversarial games. In: 26th conference on uncertainty in artificial intelligence (UAI 2010), pp 376–383 es_ES
dc.relation.references Dunne PE, Kraus S, Manisterski E, Wooldridge M (2010) Solving coalitional resource games. Artif Intell 174(1):20–50 es_ES
dc.relation.references Fabrikant A, Papadimitriou C, Talwar K (2004) The complexity of pure nash equilibria. In: Proceedings of the thirty-sixth annual ACM symposium on theory of computing, STOC ’04, pp 604–612 es_ES
dc.relation.references Friedman JW, Mezzetti C (2001) Learning in games by random sampling. J Econ Theory 98(1):55–84 es_ES
dc.relation.references Ghallab M, Nau D, Traverso P (2004) Automated planning: theory & practice. Elsevier es_ES
dc.relation.references Goemans M, Mirrokni V, Vetta A (2005) Sink equilibria and convergence. In: Proceedings of the 46th annual IEEE symposium on foundations of computer science, FOCS ’05, pp 142–154 es_ES
dc.relation.references Hadad M, Kraus S, Hartman IBA, Rosenfeld A (2013) Group planning with time constraints. Ann Math Artif Intell 69(3):243–291 es_ES
dc.relation.references Hart S, Mansour Y (2010) How long to equilibrium? the communication complexity of uncoupled equilibrium procedures. Games and Economic Behavior 69(1):107–126 es_ES
dc.relation.references Helmert M (2003) Complexity results for standard benchmark domains in planning. Artif Intell 143(2):219–262 es_ES
dc.relation.references Helmert M (2006) The fast downward planning system. J Artif Intell Res 26(1):191–246 es_ES
dc.relation.references Jennings N, Faratin P, Lomuscio A, Parsons S, Wooldrige M, Sierra C (2001) Automated negotiation: prospects, methods and challenges. Group Decis Negot 10(2):199–215 es_ES
dc.relation.references Johnson DS, Papadimtriou CH, Yannakakis M (1988) How easy is local search? J Comput Syst Sci 37 (1):79–100 es_ES
dc.relation.references Jonsson A, Rovatsos M (2011) Scaling up multiagent planning: a best-response approach. In: Proceedings of the 21st international conference on automated planning and scheduling, ICAPS es_ES
dc.relation.references Jordán J, Onaindía E (2015) Game-theoretic approach for non-cooperative planning. In: 29th AAAI conference on artificial intelligence (AAAI-15), pp 1357–1363 es_ES
dc.relation.references McDermott D, Ghallab M, Howe A, Knoblock C, Ram A, Veloso M, Weld D, Wilkins D (1998) PDDL: the planning domain definition language. Yale Center for Computational Vision and Control, New Haven es_ES
dc.relation.references Milchtaich I (1996) Congestion games with player-specific payoff functions. Games and Economic Behavior 13(1):111–124 es_ES
dc.relation.references Monderer D, Shapley LS (1996) Potential games. Games and Economic Behavior 14(1):124–143 es_ES
dc.relation.references Nigro N, Welch D, Peace J (2015) Strategic planning to implement publicly available ev charching stations: a guide for business and policy makers. Tech rep, Center for Climate and Energy Solutions es_ES
dc.relation.references Nisan N, Ronen A (2007) Computationally feasible vcg mechanisms. J Artif Intell Res 29(1):19–47 es_ES
dc.relation.references Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic game theory. Cambridge University Press, New York es_ES
dc.relation.references Papadimitriou CH (1994) On the complexity of the parity argument and other inefficient proofs of existence. J Comput Syst Sci 48(3):498–532 es_ES
dc.relation.references Richter S, Westphal M (2010) The LAMA planner: guiding cost-based anytime planning with landmarks. J Artif Intell Res 39(1):127–177 es_ES
dc.relation.references Rosenthal RW (1973) A class of games possessing pure-strategy nash equilibria. Int J Game Theory 2(1):65–67 es_ES
dc.relation.references Shoham Y, Leyton-Brown K (2009) Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge University Press es_ES
dc.relation.references Torreño A, Onaindia E, Sapena Ó (2014) A flexible coupling approach to multi-agent planning under incomplete information. Knowl Inf Syst 38(1):141–178 es_ES
dc.relation.references Torreño A, Onaindia E, Sapena Ó (2014) FMAP: distributed cooperative multi-agent planning. Appl Intell 41(2):606– 626 es_ES
dc.relation.references Torreño A, Sapena Ó, Onaindia E (2015) Global heuristics for distributed cooperative multi-agent planning. In: ICAPS 2015. 25th international conference on automated planning and scheduling. AAAI Press, pp 225–233 es_ES
dc.relation.references Von Neumann J, Morgenstern O (2007) Theory of games and economic behavior. Princeton University Press es_ES
dc.relation.references de Weerdt M, Bos A, Tonino H, Witteveen C (2003) A resource logic for multi-agent plan merging. Ann Math Artif Intell 37(1):93–130 es_ES
dc.relation.references Wooldridge M, Endriss U, Kraus S, Lang J (2013) Incentive engineering for boolean games. Artif Intell 195:418–439 es_ES


This item appears in the following Collection(s)

Show simple item record