skip to main content
10.5555/1402821.1402872acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Adaptive Kanerva-based function approximation for multi-agent systems

Published: 12 May 2008 Publication History

Abstract

In this paper, we show how adaptive prototype optimization can be used to improve the performance of function approximation based on Kanerva Coding when solving largescale instances of classic multi-agent problems. We apply our techniques to the predator-prey pursuit problem. We first demonstrate that Kanerva Coding applied within a reinforcement learner does not give good results. We then describe our new adaptive Kanerva-based function approximation algorithm, based on prototype deletion and generation. We show that probabilistic prototype deletion with random prototype generation increases the fraction of test instances that are solved from 45% to 90%, and that prototype splitting increases that fraction to 94%. We also show that optimizing prototypes reduces the number of prototypes, and therefore the number of features, needed to achieve a 90% solution rate by up to 87%. These results demonstrate that our approach can dramatically improve the quality of the results obtained and reduce the number of prototypes required. We conclude that adaptive prototype optimization can greatly improve a Kanerva-based reinforcement learner's ability to solve large-scale multi-agent problems.

References

[1]
M. Adler, H. Racke, N. Sivadasan, C. Sohler, and B. Vocking. Randomized pursuit-evasion in graphs. In Proc. of the Intl. Colloq. on Automata, Languages and Programming, 2002.
[2]
J. Albus. Brains, Behaviour, and Robotics. McGraw-Hill, 1981.
[3]
L. Baird. Residual algorithms: Reinforcement learning with function approximation. In Proc. of the 12th Intl. Conf. on Machine Learning. Morgan Kaufmann, 1995.
[4]
M. Benda, V. Jagannathan, and R. Rodhiawalla. On optimal cooperation of knowledge sources. Technical Report, Boeing Computer Services, 1985.
[5]
T. Haynes and S. Sen. The evolution of multiagent coordination strategies. Adaptive Behavior, 1997.
[6]
G. Hinton. Distributed representations. Technical Report, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, 1984.
[7]
V. Isler, S. Kannan, and S. Khanna. Randomized pursuit-evasion with local visibility. SIAM Journal on Discrete Mathematics, 20(1):26--41, 2006.
[8]
P. Kanerva. Sparse Distributed Memory. MIT Press, 1988.
[9]
K. Kostiadis and H. Hu. KaBaGe-RL: Kanerva-based generalisation and reinforcement learning for possession football. In Proc. of IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems, 2001.
[10]
B. Ratitch and D. Precup. Sparse distributed memories for on-line value-based reinforcement learning. In Proc. of the European Conf. on Machine Learning, 2004.
[11]
R. Sutton and A. Barto. Reinforcement Learning: An Introduction. Bradford Books, 1998.
[12]
M. Tan. Multi-agent reinforcement learning: Independent vs. cooperative learning. In M. N. Huhns and M. P. Singh, editors, Readings in Agents, pages 487--494. Morgan Kaufmann, CA, 1997.
[13]
C. Watkins and P. Dayan. Q-learning. Machine Learning, 8:279--292, 1989.

Cited By

View all
  • (2017)Dynamic Generalization Kanerva Coding in Reinforcement Learning for TCP Congestion Control DesignProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091375(1598-1600)Online publication date: 8-May-2017
  • (2009)Fuzzy Kanerva-based function approximation for reinforcement learningProceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 210.5555/1558109.1558240(1257-1258)Online publication date: 10-May-2009
  • (2009)Adaptive Fuzzy Function Approximation for Multi-agent Reinforcement LearningProceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology - Volume 0210.1109/WI-IAT.2009.147(169-176)Online publication date: 15-Sep-2009

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 3
May 2008
503 pages
ISBN:9780981738123

Sponsors

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 12 May 2008

Check for updates

Author Tags

  1. Kanerva Coding
  2. function approximation
  3. pursuit
  4. reinforcement learning

Qualifiers

  • Research-article

Conference

AAMAS08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Dynamic Generalization Kanerva Coding in Reinforcement Learning for TCP Congestion Control DesignProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091375(1598-1600)Online publication date: 8-May-2017
  • (2009)Fuzzy Kanerva-based function approximation for reinforcement learningProceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 210.5555/1558109.1558240(1257-1258)Online publication date: 10-May-2009
  • (2009)Adaptive Fuzzy Function Approximation for Multi-agent Reinforcement LearningProceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology - Volume 0210.1109/WI-IAT.2009.147(169-176)Online publication date: 15-Sep-2009

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media