Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> The Domain Space of Distributed Intelligence <s> An autonomous and decentralized robot system, ACTRESS, is being developed as an intelligent robot system which is composed of multiple robotic agents. The basic concept and strategy for path planning in a dynamically changing environment with multiple autonomous mobile robots are introduced. Collision avoidance with dynamic path planning according to the complexity of the situations is also discussed. A method for collision avoidance based on rules and negotiation by communication is presented. Finally, this method is applied to a developed prototype system consisting of two mobile robots, and the result of experiments operating on real robots is given. > <s> BIB001 </s> Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> The Domain Space of Distributed Intelligence <s> A model for studying fully distributed traffic control strategies for many-AGV systems in an operating field of a network of stations and passages is proposed. As a basic operating primitive, distributed mutual exclusion on a resource of capacity M (0 > <s> BIB002 </s> Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> The Domain Space of Distributed Intelligence <s> Achieving tasks with multiple robots will require a control system that is both simple and scalable as the number of robots increases. Collective behavior as demonstrated by social insects is a form of decentralized control that may prove useful in controlling multiple robots. Nature's several examples of collective behavior have motivated our approach to controlling a multiple robot system using a group behavior. Our mechanisms, used to invoke the group behavior, allow the system of robots to perform tasks without centralized control or explicit communication. We have constructed a system of five mobile robots capable of achieving simple collective tasks to verify the results obtained in simulation. The results suggest that decentralized control without explicit communication can be used to perform cooperative tasks requiring a collective behavior. <s> BIB003 </s> Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> The Domain Space of Distributed Intelligence <s> The problem of synthesizing and analyzing collective autonomous agents has only recently begun to be practically studied by the robotics community. This paper overviews the most prominent directions of research, defines key terms, and summarizes the main issues. Finally, it briefly describes our approach to controlling group behavior and its relation to the field as a whole. <s> BIB004 </s> Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> The Domain Space of Distributed Intelligence <s> We propose a distributed and optimal motion planning algorithm for multiple robots. The computationally expensive problem is decomposed into two modules: path planning and velocity planning. The D* search method is applied in both modules, based on either geometric formulation or schedule formulation. Optimization is achieved at the individual robot level by defining cost functions, and also at the team level by a global measurement function reflecting performance indices of interest as a team. Contrary to our knowledge of previous results on multi-robot motion planning that either obtain optimal solutions through centralized and exhaustive computing, or achieve distributed implementations without considering any optimization issues, our approach combines these two features and explicitly optimizes performance functions through a distributed implementation. It is also one of the few that is capable of handling outdoor rough terrain environments and real time replanning. Simulations are shown on a Mars-like rough terrain using a 3D vehicle planner and control simulator. The algorithm was also implemented and successfully run on a group of Nomad 200 indoor robots. <s> BIB005 </s> Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> The Domain Space of Distributed Intelligence <s> A lawn watering system utilizes water formed by condensation taken out of the air by an air conditioning system. The water is stored in a holding tank and at a predetermined level in the tank, a pump is switched on for delivering the water to a hose system in the lawn. <s> BIB006 </s> Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> The Domain Space of Distributed Intelligence <s> In an adversarial multi-robot task, such as playing robot soccer, decisions for team and single-robot behaviour must be made quickly to take advantage of short-term fortuitous events. When no such opportunities exist, the team must execute sequences of coordinated team action that increases the likelihood of future opportunities. A hierarchical architecture, called STP, has been developed to control an autonomous team of robots operating in an adversarial environment. STP consists of skills for executing the low-level actions that make up robot behaviour, tactics for deter- mining what skills to execute, and plays for coordinating synchronized activity among team members. The STP architecture combines each of these components to achieve autonomous team control. Moreover, the STP hierarchy allows for fast team response in adversarial environments while carrying out actions with longer goals. This article presents the STP architecture for controlling an autonomous robot team in a dynamic adversarial task that allows for coordinated team activity towards long- term goals, with the ability to respond rapidly to dynamic events. Secondly, the subcomponent of skills and tactics is presented as a generalized single-robot control hierarchy for hierarchical problem decomposition with flexible control policy implementation and reuse. Thirdly, the play techniques contribute as a generalized method for encoding and synchronizing team behaviour, providing multiple competing team responses, and for supporting effective strategy adaptation against opponent teams. STP has been fully implemented on a robot platform and thoroughly tested against a variety of unknown opponent teams in a number of RoboCup robot soccer competitions. These competition results are presented as a mechanism to analyse the performance of STP in a real setting. <s> BIB007 </s> Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> The Domain Space of Distributed Intelligence <s> Robotic Construction Crew (RCC) is a heterogeneous multi-robot system for autonomous acquisition, transport, and precision mating of components in construction tasks. RCC minimizes use of resources constrained by a space environment such as computation, power, communication, and sensing. A behavior-based architecture provides adaptability and robustness despite low computational requirements. RCC successfully performs several construction related tasks in an emulated outdoor environment despite high levels of uncertainty in motions and sensing. This paper provides quantitative results for formation keeping in component transport, precision instrument placement, and construction tasks. <s> BIB008 </s> Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> The Domain Space of Distributed Intelligence <s> As the community strives towards autonomous multi-robot systems, there is a need for these systems to autonomously form coalitions to complete assigned missions. Numerous coalition formation algorithms have been proposed in the software agent literature. Algorithms exist that form agent coalitions in both super additive and non-super additive environments. The algorithmic techniques vary from negotiation-based protocols in multi-agent system (MAS) environments to those based on computation in distributed problem solving (DPS) environments. Coalition formation behaviors have also been discussed in relation to game theory. Despite the plethora of MAS coalition formation literature, to the best of our knowledge none of the proposed algorithms have been demonstrated with an actual multi-robot system. There exists a discrepancy between the multi-agent algorithms and their applicability to the multi-robot domain. This paper aims to bridge that discrepancy by unearthing the issues that arise while attempting to tailor these algorithms to the multi-robot domain. A well-known multi-agent coalition formation algorithm has been studied in order to identify the necessary modifications to facilitate its application to the multi-robot domain. This paper reports multi-robot coalition formation results based upon simulation and actual robot experiments. A multi-agent coalition formation algorithm has been demonstrated on an actual robot system <s> BIB009 </s> Distributed Intelligence : Overview of the Field and its Application in Multi-Robot Systems <s> The Domain Space of Distributed Intelligence <s> In this paper we demonstrate path planning for our formation space that represents permutation-invariant multi-robot formations. Earlier methods generally pre-assign roles for each individual robot, rely on local planning and behaviors to build emergent behaviors, or give robots implicit constraints to meet. Our method first directly plans the formation as a set, and only afterwards determines which robot takes which role. To build our representation of this formation space, we make use of a property of complex polynomials: they are unchanged by permutations of their roots. Thus we build a characteristic polynomial whose roots are the robot locations, and use its coefficients as a representation of the formation. Mappings between work spaces and formation spaces amount to building and solving polynomials. In this paper, we construct an efficient obstacle collision detector, and use it in a local planner. From this we construct a basic roadmap planner. We thus demonstrate that our polynomial based representation can be used for effective permutation invariant formation planning. <s> BIB010
As researchers are discovering, there are many possible solution strategies, or paradigms, for achieving distributed intelligence. Not all of these paradigms are appropriate for all types of distributed intelligence. Thus, it is important to understand the various types of distributed intelligence that can occur in different application settings. One important way to view the domain space in distributed intelligence is by understanding the types of interactions that can take place between the entities in the system. As illustrated in Figure 2 , we find it instructive to view the types of interactions along three different axes -the types of goals, whether entities have awareness of others on the team, and whether an entity's actions advance the goals of others on the team. In terms of types of goals, we classify systems into two types -those in which each entity has individual goals, and those in which the entities have shared goals. For the awareness of others axis, we divide the systems into those that are aware and those that are not aware. By aware in this context, we refer to whether entities reason about the actions and intentions of their teammates. Robots that are not aware may sense the presence of local entities and move so as to maintain a certain distance, for example, but otherwise perform no other reasoning to understand the intent or future plans of the teammates. Often, these "unaware" systems operate based on the principle of stigmergy, in which communication between entities is not direct, but rather through changes made in the environment. Finally, we segment systems into those in which an entity's actions do advance the goals of others on the team (yes) and those that do not (no). An example of an entity advancing the goals of others with its actions is a floor cleaning robot, as a member of a floor cleaning robot team. Each robot's actions of cleaning a bit of the floor are helpful to the other teammates, who do not have to repeat the floor cleaning in that particular spot. Obviously, these segmentations of the domain space are approximate, yet we believe they are helpful in understanding the primary types of interactions that can occur in typical applications. Different areas of this subspace represent common types of interactions seen in systems of distributed intelligence. These common forms of interaction are: In the following paragraphs we describe these types of interactions in more detail. Perhaps the simplest type of interaction is the collective interaction, in which entities are not aware of other entities on the team, yet they do share goals, and their actions are beneficial to their teammates. An example of this type of interaction in multi-robot systems is the swarm robotics work of many researchers (e.g., BIB006 BIB004  Figure 2: Categorization of types of interactions in systems of distributed intelligence. BIB003 ). This work focuses on creating systems of robots that can perform biologically-relevant tasks, such as foraging, swarming, flocking, herding, formationkeeping, and so forth. Robots in these systems typically perform relatively simple local control laws which, when combined with larger numbers of robots, result in the global goal being achieved, often as an emergent property of the local interactions. The second type of interaction is the cooperative interaction, in which entities are aware of other entities, they share goals, and their actions are beneficial to their teammates. In multi-robot systems, an example of this type of interaction is multiple robots working together and reasoning about each other's capabilities in order to accomplish a joint task, such as pushing a box (e.g.,  ), cleaning up a worksite (e.g.,  ), performing search and rescue (e.g.,  ), or extra-planetary exploration (e.g., BIB008 ). In these systems, robots may at times be working on different parts of the higher level goal, and thus may at times have to ensure that they share the workspace without interfering with each other. However, the majority of the work of the robots is focused on working together to achieve a common goal. A third type of interaction in systems of distributed intelligence occurs when robots have individual goals, they are aware of their teammates, and their actions do help advance the goals of others. This part of the domain space is typically called collaborative, and is characterized by entities helping each other to achieve their individual, yet compatible, goals. While closely associated to the cooperative domain space, we make a distinction here to focus on the ability of entities to work together to help others better achieve their individual goals. In human research teams, we are familiar with the concept of collaboration, in which each person brings unique expertise that helps the team as a whole achieve a broader objective. Each team member has his/her own goal of performing his/her own aspect of the research, but by working together with others with complementary expertise, each can help the other members better achieve their individual goals. Of course, most of these collaborations are also cooperative, and it is possible to turn a collaborative team into a cooperative team by simply viewing the team goals from a higher perspective. A multi-robot example of a collaborative team is a group of robots that each must reach specified goal positions that are unique to each member. If robots are unable to reach their goal positions independently, due to sensor limitations, they could work together with other robots by sharing sensory capabilities to help all team members reach their individual goal locations. This type of collaboration is sometimes called coalition formation, and has been illustrated in  BIB009 . Finally, the fourth type of interaction relevant to distributed intelligence is what we call coordinative. In these systems, entities are aware of each other, but they do not share a common goal, and their actions are not helpful to other team members. In multi-robot systems, these situations often occur when robots share a common workspace. The robots must work to coordinate their actions to minimize the amount of interference between themselves and other robots. Multi-robot path planning techniques (e.g., BIB010 BIB005 ) or traffic control techniques (e.g., BIB001  BIB002 ) are commonly used in these domains. As a side note, we could have extended the third axis of our domain space to categorize systems based on whether they (1) positively affect the goals of other entities, (2) have no effect on the goals of other entities, or (3) negatively effect the goals of other entities. Then, we could create a new type of interaction in which entities have individual goals, they are aware of each other, but their actions have a negative effect on others' goals. This defines the adversarial domain, in which entities actively work against each other. In multirobot systems, this topic is studied extensively in the multirobot soccer application domain (e.g.,  BIB007  ). This form of interaction also has clear relevance for many military applications.