Adaptive Kanerva-based function approximation for multi-agent systems

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: Micah Adler , Harald Räcke , Naveen Sivadasan , Christian Sohler , Berthold Vöcking, Randomized Pursuit-Evasion in Graphs, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.901-912, July 08-13, 2002
• 2: James Sacra Albus, Brains, Behavior and Robotics, McGraw-Hill, Inc., New York, NY, 1981
• 3: Hajime Kimura , Kazuteru Miyazaki , Shigenobu Kobayashi, Reinforcement Learning in POMDPs with Function Approximation, Proceedings of the Fourteenth International Conference on Machine Learning, p.152-160, July 08-12, 1997
• 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: Volkan Isler , Sampath Kannan , Sanjeev Khanna, Randomized Pursuit-Evasion with Local Visibility, SIAM Journal on Discrete Mathematics, v.20 n.1, p.26-41, 2006 [doi>10.1137/S0895480104442169]
• 8: Pentti Kanerva, Sparse Distributed Memory, MIT Press, Cambridge, MA, 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: Richard S. Sutton, Reinforcement Learning, Kluwer Academic Publishers, Norwell, MA, 1992
• 12: Ming Tan, Multi-agent reinforcement learning: independent vs. cooperative agents, Readings in agents, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 13: Christopher J. C. H. Watkins , Peter Dayan, Technical Note: $\backslash cal\; Q$-Learning, Machine Learning, v.8 n.3-4, p.279-292, May 1992 [doi>10.1007/BF00992698]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Experimentation

Keywords:
Kanerva Coding, function approximation, pursuit, reinforcement learning