Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Hybrid POMDP-BDI Agent Architecture with Online Stochastic Planning and Desires with Changing Intensity Levels Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Speeding up Planning in Multiagent Settings Using CPU-GPU Architectures

Authors : Fadel Adoe, Yingke Chen, Prashant Doshi

Published in: Agents and Artificial Intelligence

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Planning under uncertainty in multiagent settings is highly intractable because of history and plan space complexities. Probabilistic graphical models exploit the structure of the problem domain to mitigate the computational burden. In this article, we introduce the first parallelization of planning in multiagent settings on a CPU-GPU heterogeneous system. In particular, we focus on the algorithm for exactly solving interactive dynamic influence diagrams, which is a recognized graphical models for multiagent planning. Beyond parallelizing the standard Bayesian inference and the computation of decisions’ expected utilities, we also solve the other agents behavioral models in a parallel manner. The GPU-based approach provides significant speedup on two benchmark problems.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Using Process Calculi for Plan Verification in Multiagent Planning
next chapter LSC - A Platform for Norm Controlled Social Computers
Footnotes
1
A GUI-based software application called Netus is freely available from http://​tinyurl.​com/​mwrtlvg for designing I-DIDs.
 
Literature
1.
Bernstein, D.S., Givan, R., Immerman, N., Zilberstein, S.: The complexity of decentralized control of markov decision processes. Math. Oper. Res. 27(4), 819–840 (2002)MathSciNetCrossRefMATH
2.
Berstein, D.S., Hansen, E.A., Zilberstein, S.: Bounded policy iteration for decentralized POMDPs. In: IJCAI, pp. 1287–1292 (2005)
3.
Chandrasekaran, M., Doshi, P., Zeng, Y., Chen, Y.: Team behavior in interactive dynamic influence diagrams with applications to ad hoc teams. In: AAMAS, pp. 1559–1560 (2014)
4.
Chen, Y., Hong, J., Liu, W., Godo, L., Sierra, C., Loughlin, M.: Incorporating PGMs into a BDI architecture. In: Boella, G., Elkind, E., Savarimuthu, B.T.R., Dignum, F., Purvis, M.K. (eds.) PRIMA 2013. LNCS, vol. 8291, pp. 54–69. Springer, Heidelberg (2013) CrossRef
5.
Doshi, P., Zeng, Y., Chen, Q.: Graphical models for interactive POMDPs: representations and solutions. JAAMAS 18(3), 376–416 (2009)
6.
Gal, K., Pfeffer, A.: Networks of influence diagrams: a formalism for representing agents’ beliefs and decision-making processes. JAIR 33, 109–147 (2008)MathSciNetMATH
7.
Gmytrasiewicz, P.J., Doshi, P.: A framework for sequential planning in multiagent settings. JAIR 24, 49–79 (2005)MATH
8.
Howard, R.A., Matheson, J.E.: Influence diagrams. In: Howard, R.A., Matheson, J.E. (eds.) The Principles and Applications of Decision Analysis. Strategic Decisions Group, Menlo Park (1984)
9.
Jeon, H., Xia, Y., Prasanna, K.V.: Parallel exact inference on a cpu-gpgpu heterogenous system. In: ICPP, pp. 61–70 (2010)
10.
Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge (2009)MATH
11.
Koller, D., Milch, B.: Multi-agent influence diagrams for representing and solving games. In: IJCAI, pp. 1027–1034 (2001)
12.
Luo, J., Yin, H., Li, B., Wu, C.: Path planning for automated guided vehicles system via I-DIDs with communication. In: ICCA, pp. 755–759 (2011)
13.
Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, Berlin (1998)MATH
14.
Sano, Y., Kadono, Y., Fukuta, N.: A performance optimization support framework for gpu-based traffic simulations with negotiating agents. In: ACAN (2014)
15.
Smallwood, R., Sondik, E.: The optimal control of partially observable markov decision processes over a finite horizon. Oper. Res. 21, 1071–1088 (1973)CrossRefMATH
16.
Søndberg-Jeppesen, N., Jensen, F. V., Zeng, Y.: Opponent modeling in a PGM framework. In: AAMAS, pp. 1149–1150 (2013)
17.
Kozlov, A.V., Singh, J.P.: A parallel Lauritzen-Spiegelhalter algorithm for probabilistic inference. In: Supercomputing, pp. 320–329 (1994)
18.
Xia, Y., Prasanna, K.V.: Parallel exact inference on the cell broadband engine processor. In: SC, pp. 1–12 (2008)
19.
Zeng, Y., Doshi, P.: Exploiting model equivalences for solving interactive dynamic influence diagrams. JAIR 43, 211–255 (2012)MathSciNetMATH
20.
Zheng, L., Mengshoel, O.J., Chong, J.: Belief propagation by message passing in junction trees: computing each message faster using gpu parallelization. In: UAI (2011)
Metadata
Title
Speeding up Planning in Multiagent Settings Using CPU-GPU Architectures
Authors
Fadel Adoe
Yingke Chen
Prashant Doshi
Copyright Year
2015
Book
Agents and Artificial Intelligence

Print ISBN: 978-3-319-27946-6

Electronic ISBN: 978-3-319-27947-3

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-27947-3_14

Premium Partner

    Image Credits