Using multi-agent systems for learning optimal policies for complex problems

ABSTRACT

The automatic computation of an optimal solution for a complex problem is a challenging task if no additional knowledge is available. For bounded sized problems there are universally applicable algorithms (e.g. genetic algorithms, branch and bound, reinforcement learning). The disadvantage of these algorithms is their high computational complexity so that real world problems can only be solved efficiently, if the search space is reduced dramatically.

In this paper we present an approach that enables the automatic computation of the parameter dependencies of a complex problem without any additional information. The basic idea is to apply reinforcement learning and to incrementally acquire knowledge about the implicit parameters dependencies. Based on the obtained data an optimal strategy is learned. For speeding up the learning process a multiagent architecture is applied, that supports the simultaneous analysis of alternative strategies. We prove the advantages of our approach by successfully learning a control strategy for a model helicopter.

REFERENCES

• 1: Mark Iwen , Amol Dattatraya Mali, Interaction graphs for planning problem decomposition, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544969]
• 2: E. N. Johnson and S. Kannan. Adaptive flight control for an autonomous unmanned helicopter. In gnc, number AIAA-2002-4439, Monterey, CA, aug 2002.
• 3: J. Leishman. Principles of Helicopter Aerodynamics. Cambridge University Press, Cambridge, MA, 2000.
• 4: M. Musial, G. Hommel, U. W. Brandenburg, E. Berg, M. Christmann, C. Fleischer, C. Reinicke, V. Remuß, S. Rönneke, and A. Wege. MARVIN - Technische Universität Berlin's Flying Robot Competing at the IARC'99.
• 5: A. Y. Ng, A. Coates, and e. a. Mark Diel. Inverted autonomous helicopter flight via reinforcement learning. In International Symposium on Experimental Robotics, 2004.
• 6: A. Y. Ng, H. J. Kim, M. I. Jordan, and S. Sastry. Autonomous helicopter flight via reinforcement learning. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.
• 7: Sahin Albayrak , Silvan Kaiser , Jan Stender, Advanced Grid Management Software for Seamless Services, Multiagent and Grid Systems, v.1 n.4, p.263-270, December 2005
• 8: Ralf Sesseler, Building agents for service provisioning out of components, Proceedings of the fifth international conference on Autonomous agents, p.218-219, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376121]
• 9: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 10: 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

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Experimentation

Keywords:
coordination, learning, multi-agent systems