MO-KGMKS problemlerinin çözümünde evrimsel algoritmalar

The Decentralized Partially Observable Markov Decision Process (DEC-POMDP)model addresses the multiagent planning problem in partially observable environments.Due to its NEXP-complete complexity, only small size problems can be solved exactly.For this reason, many researchers concentrate on approximate solution algorithms that canhandle more complex cases and produce near optimal solutions. However, even the approximatesolution techniques developed so far can handle large size problems only for smallhorizons. One reason for this is the exponential memory requirements while representingthe agent policies and searching the policy space. In this thesis, we propose four newapproaches to solve finite horizon DEC-POMDP problems approximately. The first approach,called MAP, is based on modeling DEC-POMDP problems as a POMDP problemand then solving using an efficient POMDP solver. The other approaches, namely ES-BV,ES-OH and GA-FSC, are all based on the application of evolutionary algorithms. The ESBVmakes use of belief vectors as in the case of MAP and tries to find policy vectors usingevolution strategies (ES). The ES-OH proposes to use the observation history and input itinto a neural network to make a decision and it uses ES to train the neural networks. TheGA-FSC algorithm makes use of finite state controllers for representing the policies andsearch for the optimal policy using genetic algorithms (GA). All algorithms were tested onthe major well-known DEC-POMDP problems. We compared our results with the currentstate of the art methods and we also compared our algorithms with each other. We showedthat all the algorithms developed in this study, except MAP, have comparable performanceto that of the existing top algorithms and in the case of the GA-FSC, the solution horizonfor the problems are extended at least an order of magnitude.