Multi-agent robot systems as distributed autonomous systems
Introduction
The environments in which robots operate include factories, offices, and homes. Because various tasks are required of robots, cooperation becomes important. Currently, various studies have been undertaken on the issue of the accomplishment of tasks by multi-agent robots.
The characteristics of distributed autonomous systems or multi-agent systems were described as follows in Ref. [1]: (1) incomplete information or capabilities for solving the problem in each agent, (2) no system global control, (3) decentralized data, and (4) asynchronous computation. One more important aspect to be added to the above list is that, although systems are evaluated according to the performance of multi-agents, group performance cannot be programmed directly. Designs are limited to the individual performance of each agent. The performance of multi-agents emerges from that of individual agents. The gap between the evaluated object (the behavior of multi-agents) and the designed object (the behavior of an individual agent) makes it difficult to design a multi-agent system. Because multi-agent robot systems are part of multi-agent systems (distributed autonomous systems), the above-mentioned characteristics can also apply to multi-agent robot systems.
However, multi-agent robot systems have the following special characteristics: (s1) since a robot has its own physical parts, including sensors, processors, actuators, and communication devices, its limitations must be considered, such as those related to calculation power, sensing errors, and errors in actuating and communicating devices; and (s2) robots move in actual environments; therefore, geometry must be considered. In other words, physical interaction, such as collision avoidance and the manipulation of physical objects by the cooperation of robots, must be taken into account.
Several reviews on these issues are currently available. For example, Ref. [2] presents a review of artificial systems, multi-agent robot systems, and software agents as well as natural systems, such as human and animal groups. In Ref. [3], in order to clarify the mechanism of cooperation among multiple robots, five key research areas applying to all of the reviewed papers were examined. They included group architecture, resource conflict, origin of cooperation, learning, and geometry problems. Ref. [4] focused on three topics as he surveyed existing studies: arbitration among agents, communication, and dynamic configurable architecture.
In this review, the focus is on the task assigned to the robots. Multi-agent robots deal with many kinds of tasks. The task specification determines the level and kind of intelligence that robots need. Although many methodologies have been proposed for some specific tasks or general task frameworks, an overall definition of robotic tasks is still lacking. It has not been determined what types of tasks multiple robots should perform or what is appropriate for robots. In order to overcome the current deficiency, in this paper, we (a) classify tasks from two viewpoints and (b) survey previous studies on the basis of the classification obtained in (a), describing what kind of knowledge robots need to create to realize these tasks, and (c) we discuss future trends for multi-agent robot systems.
It is natural to consider that behavior is essential for robots. Here, the robot tasks are categorized according to the various dimensions of the tasks and the numbers of tasks that are to be performed.
Point-reaching tasks are those in which the target is expressed with a specific goal configuration of the robot. The goal configuration is expressed as a specific point in the configuration space of the robots. Here, the configuration of the robot is a specification of the position of every point in the robot in a certain coordinate system. The configuration space is the space of the entire configuration of the robot [5]. Standard motion-planning tasks of multi-agent robots are grouped into this category. Here, the word ‘dimension’ is used to compare the expressive form of the goal, that is, the goal point (which is zero-dimensional in the configuration space). In the point-reaching task, the robot's trajectory is generated by connecting the robot's start and goal configurations. In general, a robot's trajectory is expressed with a space curve and parameterized with an arc length (one parameter). Hence, we can regard the dimension of a robot's trajectory as one. The point-reaching task is to generate a one-dimensional solution (the robot's trajectory) to accomplish the zero-dimensional goal.
Region-sweeping tasks are those in which the target is expressed with a specific goal region. The target is to generate the trajectory of the robot covering the required region with the robot's sensing area, i.e. to generate a one-dimensional solution (trajectory) to complete a multi-dimensional goal. The term ‘multi-dimensional goal’ indicates that the goal is expressed as a certain region that has more than one-dimension. Sweeping or exploring tasks are included in the second category. For a sweeping task of a flat region, the dimension is two.
It is noteworthy that, when the dimension of the target is equal to one, the problem becomes a control problem rather than the task realization problems addressed here. An example of a control problem is a tracking task on a given trajectory by a mobile robot. This type of task will not be discussed in this paper.
Compound tasks are those in which the two types of tasks referred to above are combined.
Ordinary tasks should be performed once only. Some tasks, however, must be performed many-times. Here, ‘many-times’ means that we expect the effect of adaptation, learning, and self-organization to occur as a result of several trials.
Tasks can be classified into six (=3×2) by a combination of the two categories given above. Examples of tasks are shown in Table 1. Most multi-agent robotic tasks are included in this table. Tasks in the same class are similar in that the same behavior is required of the robots. Former studies in this field are surveyed on the basis of these classes.
Many studies have researched the multi-agent robotic tasks in Table 1. For example, there are studies on cooperative manipulation and transportation, such as those by Refs. [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18]. An example is shown in Fig. 1, in which four circular robots are tasked with transporting one large rectangle-shaped object cooperatively. The main topic in this field is how to achieve stable and robust transportation in environments that involve errors in sensing, actuating, and communication. Other important topics are the development of self-reconfigurable robots [19], [20], [21], [22], [23], [24], in which many small robotic units gather and connect dynamically depending on the demands, and the achievement of cooperative localization [25], [26], [27], [28], [29], [30], [31], in which several robots maintain formation to know their location within their environment without the use of landmarks. The last two papers mentioned above deal with the multi-robot Simultaneous Localization and Mapping (SLAM) problem. The standard SLAM problem asks if it is possible for a mobile robot to start in an unknown location in an unknown environment and then incrementally build a map of this environment while simultaneously using this map to compute absolute vehicle location [32]. The structure of multi-agent robot systems is similar to that used in Distributed Artificial Intelligence (for example, [33], [34]) because it deals with the intelligence of many agents interacting in the same domain.
Section snippets
‘One-time’ and ‘point-reaching’ tasks
There are many studies of one-time and point-reaching tasks. One of the most fundamental topics is ‘motion-planning of multi-agent robots’, in which individual robots reach goal configurations from initial configurations while avoiding each other. Some examples are shown in Fig. 2. In Fig. 2, four robots try to move to their destinations as quickly as possible while avoiding other robots and static obstacles.
Several approaches exist to solve the motion-planning problem. Erdmann et al.
‘Many-time’ and ‘point-reaching’ tasks
When a certain task has to be executed many-times, it becomes important to generate a group formation of robots based on the learning capacity of individual robots. Several studies have been conducted on this topic. Hand-to-hand delivery motion was introduced to avoid deadlocks [69]. This motion is compatible with object transportation and mutual avoidance of two robots. Yoshimura et al. settled an iterative transportation task, as shown in Fig. 6, in which the target of the task is to
‘One-time’ and ‘region-sweeping’ tasks
The region-sweeping (covering) task finishes when the region produced by integrating the sensing area of the robots along the robots' trajectories becomes identical to that of the target region (Fig. 7). Here, the robots are assumed to have their own sensing areas. The tasks are realized by covering a multi-dimensional area with one-dimensional trajectories of robots, as described in Section 1. This is fundamentally different from point-reaching tasks, in which trajectories are made to reach
‘Many-time’ and ‘region-sweeping’ tasks
An example in this class is the patrolling of a dynamically changing environment. This problem can be modeled as a Multiple Traveling Salesmen Problem (MTSP) [87] by considering observation points as nodes in graph theory. We can calculate the observation points by utilizing the method of Ref. [77] or other methodologies. There are very few studies that have examined this method.
Trevai et al. advanced a method to generate an exploration path in a restricted working environment [88]. The
‘One-time’ and ‘compound’ tasks
When the task is to (a) find a specific object whose initial location is unknown to the robots and (b) transport it to a desired position, it is categorized as a compound task. This is because it includes a region-sweeping task (searching the object in the working environment) and a point-reaching task (transporting an object to a target position). More generally, compound tasks consist of several subtasks, such as a searching subtask or a transporting subtask. Multi-agent robots share the role
‘Many-time’ and ‘compound’ tasks
As previously reported, learning or adaptive ability becomes important in this task class.
The task of collecting samples scattered in the working environments by many robots in unknown environments has been thoroughly studied. The task is popular in the field of swarm intelligence, where there is no explicit communication among robots and very simple behavior is expected of the robots. In order to complete the task efficiently, an adequate formation of robots is necessary. Such a task could
Conclusion
In this paper, we classified tasks performed by multiple robots based on the dimension of the goal state and the number of iterations they perform. This classification is made by considering how a motion-planning problem, which is one of the most fundamental tasks, can be extended. The dimension of the goal state is an extension of the geometric dimension. The number of iterations is an extension of the time dimension.
The results of the review, according to the classifications listed above,
References (128)
- et al.
Transfer control of a large object by a group of mobile robots
Robotics Autonomous Syst
(1999) Mobile Manipulation: the robotic assistant
Robotics Autonomous Syst
(1999)- et al.
Cooperative transportation by two four-legged robots with implicit communication
Robotics Autonomous Syst
(1999) - et al.
Multi-robot motion coordination in space and time
Robotics Autonomous Syst
(1998) - et al.
A distributed control scheme for multiple robotic vehicles to make group formations
Robotics Autonomous Syst
(2001) Decentralized coordination for multi-robot exploration
Robotics Autonomous Syst
(1999)- et al.
Compound behaviors in pheromone robotics
Robotics Autonomous Syst
(2003) Situated agents can have goals
Robotics Autonomous Syst
(1990)- et al.
An architecture for distributed cooperative planning in a behavior-based multi-robot system
Robotics Autonomous Systems
(1999) Multi-agent systems
AI Mag
(1998)
Robot teams, human workgroups, and animal sociobiology: a review of research on natural and artificial multi-agent autonomous systems
Adv Robotics
Cooperative mobile robotics: antecedents and directions
Autonomous Robots
Toward realization of collective intelligence and emergent robotics (survey)
Proc IEEE Int Conf Syst Man Cybern
Robot Motion Planning
Dynamic control approach for motion coordination of multiple wheeled mobile robots transporting a single object
Proc IEEE/RSJ Int Conf Intell Robots Syst
Towards the development of a material transport system using swarms of ant-like robots
Proc IEEE Int Conf Robotics Automat
Collective robotics: from social insects to robots
Adaptive Behav
Cooperating grasping of a large object by multiple mobile robots
Proc IEEE Int Conf Robotics Automat
Information invariants for distributed manipulation
J Robotics Res
Coordinated transportation of a single object by multiple mobile robots without position information of each robot
Proc IEEE/RSJ Int Conf Intell Robots Syst
A. “constrain and move” approach to distributed object manipulation
IEEE Trans Robotics Automat
Control of cooperating mobile manipulators
IEEE Trans Robotics Automat
Nonholonomic navigation and control of cooperating mobile manipulators
IEEE Trans Robotics Automat
A paradigm for dynamic coordination of multiple robots
Autonomous Robots
Cellular robotic system (CEBOT) as one of the realization of self-organizing intelligent universal manipulators
Proc IEEE Int Conf Robotics Automat
Self-assembly and self-repair method for a distributed mechanical system
IEEE Trans Robotics Automation
Self-repairing mechanical systems
Autonomous Robots
Crystalline robots: self-reconfiguration with compressible unit modules
Autonomous Robots
Modular robots
IEEE Spectrum
Hormone-inspired adaptive communication and distributed control for CONRO self-reconfigurable robots,
IEEE Trans Robotics Automat
Cooperative positioning with multiple robots
Proc IEEE Int Conf Robotics Automat
A probabilistic approach to collaborative multi-robot localization
Autonomous Robots
Heterogeneous teams of modular robots for mapping and exploration
Autonomous Robots
A probabilistic online mapping algorithm for teams of mobile robots
Int J Robotics Res
Cooperative probabilistic state estimation for vision-based autonomous mobile robots
IEEE Trans Robotics Automat
Distributed multi-robot localization
IEEE Trans Robotics Automat
Simultaneous localization and map building for a team of cooperating robots: a set membership approach
IEEE Trans Robotics Automat
A solution to the simultaneous localization and map building (SLAM) problem
IEEE Trans Robotics Automat
Multi-agent systems: an emerging subdiscipline of AI
ACM Computing Surveys
Multiagent systems: a survey from a machine learning perspective
Autonomous Robots
On multiple moving objects
Algorithmica
A mobile automaton: an application of artificial intelligence techniques
Proc 1st Int Joint Conf Artif Intel
Motion planning in dynamic environments
Distributed surveillance and reconnaissance using multiple autonomous ATVs: CyberScout
IEEE Trans Robotics Automat
A decentralized approach for the conflict-free motion of multiple mobile robots
Adv Robotics
Multi-robot cooperation in the MARTHA project
IEEE Robotics Automat Mag
Anytime sensing, planning and action: a practical model for robot control
Proc 13th Int Joint Conf Artif Intel
Optimal motion planning for multiple robots having independent goals
IEEE Trans Robotics Automat
Path coordination for multiple mobile robots: a resolution-complete algorithm
IEEE Trans Robotics Automat
Sensor-based traffic rules for multiple automata based on a geometric deadlock-free characteristic
J Robotics Mechatronics
Cited by (137)
Distributed fault-tolerant control for heterogeneous multiagent systems and application in wireless power transfer grid
2023, Journal of the Franklin InstituteDistributed extended state observer-based fault-tolerant control for nonlinear multi-agent systems with switching topologies
2024, International Journal of Robust and Nonlinear Control