Lernalgorithmen für kooperative Multi-Agenten Systeme

• Applicant: Professor Dr. Martin Riedmiller
• Subject Area: Theoretical Computer Science
• Term: from 2005 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5446214

• Final Report Year: 2010

Final Report Abstract

In verteilten Systemen ist die gezielte Zusammenarbeit individuell handelnder Agenten nötig, um ein vorgegebenes Ziel zu erreichen. Dazu müssen die Handlungsstrategien der einzelnen Agenten optimal aufeinander abgestimmt sein. In praktischen Anwendungen ist es typischerweise der Fall, dass jeder Agent nur über seinen eigenen Zustand, nicht jedoch über den Zustand der anderen Agenten informiert ist. Diese Uninformiertheit resultiert darin, dass die Komplexität zum Finden eines optimalen Verhaltens für alle Agenten erheblich anwächst. Ziel des Forschungsprojekts war die Entwicklung und Untersuchung autonomer Lernverfahren, die das Erlernen kooperativer Strategien allein aus der Spezifikation des gewünschten Gesamtverhaltens des Systems realisieren (Multi-Agent Reinforcement Learning, MARL). Im Rahmen des Projekts haben wir mehrere neuartige modellfreie MARL-Algorithmen entwickelt, ihre Eigenschaften theoretisch analysiert und ihre Leistungsfähigkeit empirisch evaluiert. Anwendungsbeispiele verteilter Agenten sind im Ressourcenmanagement, Scheduling, Energieverteilungsaufgaben, Netzwerk-Routing oder der Robotik zu finden. Im anwendungsorientierten Teil des Projektes haben wir Job-Shop Scheduling Probleme als verteilte Entscheidungsprobleme modelliert und die von uns entwickelten Algorithmen bzw. deren Varianten an ausgewählten Benchmark-Problemen aus dem Bereich Job-Shop Scheduling auf ihre Praxistauglichkeit hin getestet. Die verteilt erlernten kooperative Handlungsstrategien erbrachten Resultate, die mit konventionellen Ansätzen aus dem Bereich Scheduling mithalten können und diese teilweise übertreffen. Die wichtigsten im Projekt erzielten wissenschaftlichen Ergebnisse umfassen • die Identifikation einer praxisrelevanten und komplexitätsbeschränkten Teilklasse von verteilten Lernproblemen, • die Entwicklung von robusten und generalisierungsfähigen Algorithmen für Reinforcement Lernen in Multi-Agenten-Systemen, • die Entwicklung von verteilten Lernalgorithmen, die die Handlungsstrategien der Agenten direkt modifizieren, • die theoretische Analyse der Eigenschaften der vorgeschlagenen Algorithmen, • den gezielten Einsatz von Kommunikation zum Erlernen optimaler Handlungsstrategien sowie • die erfolgreiche Evaluation der entwickelten Verfahren anhand von Benchmark-Problemen aus dem Bereich Job-Shop Scheduling.

Publications

• Neural Fitted Q Iteration – First Experiences with a Data Efficient Neural Reinforcement Learning Method. In Machine Learning: ECML 2005, 16th European Conference on Machine Learning, pages 317–328, Porto, Portugal, 2005
  M. Riedmiller
  
• Multi-Agent Case-Based Reasoning for Cooperative Reinforcement Learners. In Proceedings of the 8th European Conference on Case- Based Reasoning (ECCBR 2006), pages 32–46, Fethiye, Turkey, 2006. Springer
  T. Gabel and M. Riedmiller
  
• Reducing Policy Degradation in Neuro-Dynamic Programming. In Proceedings of the 11th European Symposium on Artificial Neural Networks (ESANN 2006), pages 653–658, Bruges, Belgium, 2006
  T. Gabel and M. Riedmiller
  
• Adaptive Reactive Job-Shop Scheduling with Learning Agents. International Journal of Information Technology and Intelligent Computing, 2(4), 2007
  T. Gabel and M. Riedmiller
  
• Evaluation of Policy Gradient Methods and Variants on the Cart-Pole Benchmark. In Proceedings of the IEEE Symposium on Approximate Dynamic Programming and Reinforcement Learning (ADPRL 2007), pages 254–261, Honolulu, USA, 2007. IEEE Press
  M. Riedmiller, J. Peters, and S. Schaal
  
• Learning to Drive a Real Car in 20 Minutes. In Proceedings of Frontiers in the Convergence of Bioscience and Information Technologies (FBIT 2008), Jeju, South Korea, 2007
  M. Riedmiller, M. Montemerlo, and H. Dahlkamp
  
• On a Successful Application of Multi-Agent Reinforcement Learning to Operations Research Benchmarks. In Proceedings of the IEEE Symposium on Approximate Dynamic Programming and Reinforcement Learning (ADPRL 2007), pages 68–75, Honolulu, USA, 2007. IEEE Press
  T. Gabel and M. Riedmiller
  
• Scaling Adaptive Agent-Based Reactive Job-Shop Scheduling to Large-Scale Problems. In Proceedings of the IEEE Symposium on Computational Intelligence in Scheduling (CI-Sched 2007), pages 259–266, Honolulu, USA, 2007. IEEE Press
  T. Gabel and M. Riedmiller
  
• Evaluation of Batch-Mode Reinforcement Learning Methods for Solving DEC-MDPs with Changing Action Sets. In Proceedings of the 8th European Workshop on Reinforcement Learning (EWRL 2008), pages 82–95, Lille, France, 2008. Springer
  T. Gabel and M. Riedmiller
  
• Gradient Descent Policy Search for Distributed Job-Shop Scheduling Problems. In Online Proceedings of the 18th International Conference on Planning and Scheduling (ICAPS 2008), Sydney, Australia, 2008. AAAI Press
  T. Gabel and M. Riedmiller
  
• Joint Equilibrium Policy Search for Multi-Agent Scheduling Problems. In Proceedings of the 6th Conference on Multiagent System Technologies (MATES 2008), pages 61–72, Kaiserslautern, Germany, 2008. Springer
  T. Gabel and M. Riedmiller
  
• Reinforcement Learning for DEC-MDPs with Changing Action Sets and Partially Ordered Dependencies. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), pages 1333–1336, Estoril, Portugal, 2008. IFAAMA
  T. Gabel and M. Riedmiller
  
• Learning in Cooperative Multi-Agent Systems. ISBN 978-3838110363, Südwestdeutscher Verlag für Hochschulschriften, Saarbrücken, Germany, 2009
  T. Gabel
  
• Multi-Agent Reinforcement Learning Approaches for Distributed Job-Shop Scheduling Problems. Dissertation Thesis, University of Osnabrück, 2009
  T. Gabel