Swarm robotics: a review from the swarm engineering perspective <s> Automatic design methods <s> This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning. <s> BIB001 </s> Swarm robotics: a review from the swarm engineering perspective <s> Automatic design methods <s> Abstract. This paper attempts to bridge the fields of machine learning, robotics, and distributed AI. It discusses the use of communication in reducing the undesirable effects of locality in fully distributed multi-agent systems with multiple agents robots learning in parallel while interacting with each other. Two key problems, hidden state and credit assignment, are addressed by applying local undirected broadcast communication in a dual role: as sensing and as reinforcement. The methodology is demonstrated on two multi-robot learning experiments. The first describes learning a tightly-coupled coordination task with two robots, the second a loosely-coupled task with four robots learning social rules. Communication is used to (1) share sensory data to overcome hidden state and (2) share reinforcement to overcome the credit assignment problem between the agents and bridge the gap between local individual and global group pay-off. <s> BIB002 </s> Swarm robotics: a review from the swarm engineering perspective <s> Automatic design methods <s> This paper describes a formulation of reinforcement learning that enables learning in noisy, dynamic environments such as in the complex concurrent multi-robot learning domain. The methodology involves minimizing the learning space through the use of behaviors and conditions, and dealing with the credit assignment problem through shaped reinforcement in the form of heterogeneous reinforcement functions and progress estimators. We experimentally validate the approach on a group of four mobile robots learning a foraging task. <s> BIB003 </s> Swarm robotics: a review from the swarm engineering perspective <s> Automatic design methods <s> In this paper, we bring techniques from operations research to bear on the problem of choosing optimal actions in partially observable stochastic domains. We begin by introducing the theory of Markov decision processes (mdps) and partially observable MDPs (pomdps). We then outline a novel algorithm for solving pomdps off line and show how, in some cases, a finite-memory controller can be extracted from the solution to a POMDP. We conclude with a discussion of how our approach relates to previous work, the complexity of finding exact solutions to pomdps, and of some possibilities for finding approximate solutions. <s> BIB004 </s> Swarm robotics: a review from the swarm engineering perspective <s> Automatic design methods <s> This paper surveys the emerging science of how to design a “COllective INtelligence” (COIN). A COIN is a large multi-agent system where: i) There is little to no centralized communication or control. ii) There is a provided world utility function that rates the possible histories of the full system. In particular, we are interested in COINs in which each agent runs a reinforcement learning (RL) algorithm. The conventional approach to designing large distributed systems to optimize a world utility does not use agents running RL algorithms. Rather, that approach begins with explicit modeling of the dynamics of the overall system, followed by detailed hand-tuning of the interactions between the components to ensure that they “cooperate” as far as the world utility is concerned. This approach is labor-intensive, often results in highly nonrobust systems, and usually results in design techniques that have limited applicability. In contrast, we wish to solve the COIN design problem implicitly, via the “adaptive” character of the RL algorithms of each of the agents. This approach introduces an entirely new, profound design problem: Assuming the RL algorithms are able to achieve high rewards, what reward functions for the individual agents will, when pursued by those agents, result in high world utility? In other words, what reward functions will best ensure that we do not have phenomena like the tragedy of the commons, Braess’s paradox, or the liquidity trap? Although still very young, research specifically concentrating on the COIN design problem has already resulted in successes in artificial domains, in particular in packet-routing, the leader-follower problem, and in variants of Arthur’s El Farol bar problem. It is expected that as it matures and draws upon other disciplines related to COINs, this research will greatly expand the range of tasks addressable by human engineers. Moreover, in addition to drawing on them, such a fully developed science of COIN design may provide much insight into other already established scientific fields, such as economics, game theory, and population biology. <s> BIB005 </s> Swarm robotics: a review from the swarm engineering perspective <s> Automatic design methods <s> Cooperative multi-agent systems (MAS) are ones in which several agents attempt, through their interaction, to jointly solve tasks or to maximize utility. Due to the interactions among the agents, multi-agent problem complexity can rise rapidly with the number of agents or their behavioral sophistication. The challenge this presents to the task of programming solutions to MAS problems has spawned increasing interest in machine learning techniques to automate the search and optimization process. We provide a broad survey of the cooperative multi-agent learning literature. Previous surveys of this area have largely focused on issues common to specific subareas (for example, reinforcement learning, RL or robotics). In this survey we attempt to draw from multi-agent learning work in a spectrum of areas, including RL, evolutionary computation, game theory, complex systems, agent modeling, and robotics. We find that this broad view leads to a division of the work into two categories, each with its own special issues: applying a single learner to discover joint solutions to multi-agent problems (team learning), or using multiple simultaneous learners, often one per agent (concurrent learning). Additionally, we discuss direct and indirect communication in connection with learning, plus open issues in task decomposition, scalability, and adaptive dynamics. We conclude with a presentation of multi-agent learning problem domains, and a list of multi-agent learning resources. <s> BIB006 </s> Swarm robotics: a review from the swarm engineering perspective <s> Automatic design methods <s> Multiagent reinforcement learning for multirobot systems is a challenging issue in both robotics and artificial intelligence. With the ever increasing interests in theoretical research and practical applications, currently there have been a lot of efforts towards providing some solutions to this challenge. However, there are still many difficulties in scaling up multiagent reinforcement learning to multi-robot systems. The main objective of this paper is to provide a survey on multiagent reinforcement learning in multi-robot systems, based on the literature the authors collected. After reviewing some important advances in this field, some challenging problems are analyzed. A concluding remark is made from the perspectives of the authors. <s> BIB007 </s> Swarm robotics: a review from the swarm engineering perspective <s> Automatic design methods <s> Temporal difference reinforcement learning algorithms are perfectly suited to autonomous agents because they learn directly from an agent's experience based on sequential actions in the environment. However, their most common algorithmic variants are relatively inefficient in their use of experience data, which in many agent-based settings can be scarce. In particular, they make just one learning "update" for each atomic experience. Batch reinforcement learning algorithms, on the other hand, aim to achieve greater data efficiency by saving experience data and using it in aggregate to make updates to the learned policy. Their success has been demonstrated in the past on simple domains like grid worlds and low-dimensional control applications like pole balancing. In this paper, we compare and contrast batch reinforcement learning algorithms with on-line algorithms based on their empirical performance in a complex, continuous, noisy, multiagent domain, namely RoboCup soccer Keepaway. We find that the two batch methods we consider, Experience Replay and Fitted Q Iteration, both yield significant gains in sample complexity, while achieving high asymptotic performance. <s> BIB008 </s> Swarm robotics: a review from the swarm engineering perspective <s> Automatic design methods <s> Batch reinforcement learning methods provide a powerful framework for learning efficiently and effectively in autonomous robots. The paper reviews some recent work of the authors aiming at the successful application of reinforcement learning in a challenging and complex domain. It discusses several variants of the general batch learning framework, particularly tailored to the use of multilayer perceptrons to approximate value functions over continuous state spaces. The batch learning framework is successfully used to learn crucial skills in our soccer-playing robots participating in the RoboCup competitions. This is demonstrated on three different case studies. <s> BIB009
The use of automatic design methods allows the automatic generation of behaviors without the explicit intervention of the developer. Automatic design methods for swarm robotics systems can be divided in two main subdomains: reinforcement learning and evolutionary robotics. BIB006 conducted an extensive review of the state of the art of automatic design methods for multiagent and multi-robot systems. Differently from BIB006 , in this review we focus on understanding the obtained results and the challenges of applying automatic design methods in swarm robotics. The section is organized as follows. We first introduce reinforcement learning BIB001  and we identify the key challenges in the application of the methods developed for reinforcement learning to swarm robotics. We then present evolutionary robotics  , the application of evolutionary computation techniques to single and multi-robot systems. Finally, we present some individual works on automatic design methods that do not belong to either of the above two categories. Reinforcement learning A set of methods to automatically design individual behaviors for robots in a swarm can be found in the reinforcement learning (RL) literature. RL traditionally refers to a class of learning problems: an agent learns a behavior through trial-and-error interactions with an environment and by receiving positive and negative feedback for its actions. In this section, we do not go into the details of RL: our goal is to discuss to what extent the methods developed for RL are or can be applied to swarm robotics. For a more formal introduction and more details about RL, the interested reader can refer to BIB001 . In RL, the robot receives a reward for its actions. The goal of the robot is to learn automatically an optimal policy, that is, the optimal behavior mapping robot states to robot actions. The behavior is optimal in the sense that it maximizes the rewards received from the environment. RL has been intensively studied in the single robot case where an elegant and unified mathematical framework has been developed BIB001  . In the multi-robot case, only few works with limited scope exist. A review of such works was conducted by BIB006 , BIB007 , and  . A swarm robotics problem can hardly be seen as a RL problem. In fact, the swarm engineer tackles the task at the collective level, but learning typically takes place at the individual level. Thus, in applying methods developed for RL to swarm robotics, the main issue is the decomposition of the global reward into individual rewards BIB005 . This challenging problem is called spatial credit assignment. BIB003 BIB002 addressed this issue by performing experiments with few robots (2 to 4), using communication or signaling to share the reward BIB003 BIB002 . In addition to the spatial credit assignment, there are also other open problems: (i) The size of the state space faced in RL problems is huge. The reason behind this problem is the high complexity of the robots hardware and the complexity of the robot-to-robot interactions. Examples of techniques to reduce the state space dimension have been used by BIB009 . In this work, the authors applied neural networks as function approximators together with fast learning algorithms BIB008 . (ii) The environment perception is incomplete. This makes the search of the behavior even more complex BIB004 ). Matarić and her colleagues addressed this problem using communication BIB002 or behavioral decomposition BIB003 . (iii) The environment, as seen from the individual robot perspective, is non-stationary due to the fact that each robot's action is influenced by the actions performed by other robots in the same environment or by changes in the environment itself. We do not know of any work in multirobot learning addressing this problem.  (henceforth ER) is an automatic design method that applies evolutionary computation techniques   ) to single and multi-robot systems. Evolutionary computation is inspired by the Darwinian principle of natural selection and evolution. As such, it uses a vocabulary borrowed from biology.