The article investigates different approaches to the problem of autonomous robots' self-learning. The knowledge, which a priori is introduced into the on-board control system of an intelligent autonomous robot for control of its expedient behavior in certain situations, should, in general, be supplemented with the results of the self-learning based on the analysis of the accumulated experience. A variety of the autonomous robots' applications in combination with the diversity of the environmental uncertainty types makes possible several options for augmentation of knowledge. The authors employ the construction methods of the classification trees and the decision forests to find the hidden patterns in the arrays of the sensory data, which accumulate the experience, gathered by the robots operating in a complex environment. The prospects of the decision forests construction method were demonstrated for organization of the self-learning processes in the multi-robot systems (MRS). A new approach to MRS self-learning was developed based on a combination of the decision forests and evolutionary computation methods. It was proved that the method of the evolutionary decision forests can serve as a constructive basis for development of the intelligent self-learning autonomous robots operating together within a multi-robot system. The authors demonstrated that the role of the robotic agents was not confined to accumulation of their own sensory data, but that they were also capable of a knowledge exchange and its incorporation into their personal experience. The results of the model simulation are presented, confirming the effectiveness of the proposed approach.