Multi-agent robot systems as distributed autonomous systems

https://doi.org/10.1016/j.aei.2005.06.002Get rights and content

Abstract

In the numerous existing studies dealing with multi-agent robot systems, the systems are positioned on the crossover area of robotics and distributed autonomous systems. Multi-agent robots perform many tasks, which are classified into six types according to the dimension of the goal state and the number of iterations of the tasks. This paper surveys earlier studies on multi-agent robots for each type, such as multi-robot motion-planning algorithms and exploration algorithms of multiple robots. The tasks that multi-agent robots can perform are becoming increasingly more complex as they move from single, one-time tasks to those involving many iterations. This study is an investigation of the current trends and the potentials for multi-agent robot 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)

  • A. Agah

    Robot teams, human workgroups, and animal sociobiology: a review of research on natural and artificial multi-agent autonomous systems

    Adv Robotics

    (1996)
  • Y.U. Cao et al.

    Cooperative mobile robotics: antecedents and directions

    Autonomous Robots

    (1997)
  • D. Kurabayashi

    Toward realization of collective intelligence and emergent robotics (survey)

    Proc IEEE Int Conf Syst Man Cybern

    (1999)
  • J.C. Latombe

    Robot Motion Planning

    (1991)
  • M. Hashimoto et al.

    Dynamic control approach for motion coordination of multiple wheeled mobile robots transporting a single object

    Proc IEEE/RSJ Int Conf Intell Robots Syst

    (1993)
  • D.J. Stilwell et al.

    Towards the development of a material transport system using swarms of ant-like robots

    Proc IEEE Int Conf Robotics Automat

    (1993)
  • C.R. Kube et al.

    Collective robotics: from social insects to robots

    Adaptive Behav

    (1994)
  • J. Sasaki et al.

    Cooperating grasping of a large object by multiple mobile robots

    Proc IEEE Int Conf Robotics Automat

    (1995)
  • B.R. Donald et al.

    Information invariants for distributed manipulation

    J Robotics Res

    (1997)
  • Y. Hirata et al.

    Coordinated transportation of a single object by multiple mobile robots without position information of each robot

    Proc IEEE/RSJ Int Conf Intell Robots Syst

    (2000)
  • M.N. Ahmadabadi et al.

    A. “constrain and move” approach to distributed object manipulation

    IEEE Trans Robotics Automat

    (2001)
  • T.G. Sugar et al.

    Control of cooperating mobile manipulators

    IEEE Trans Robotics Automat

    (2002)
  • H.G. Tanner et al.

    Nonholonomic navigation and control of cooperating mobile manipulators

    IEEE Trans Robotics Automat

    (2003)
  • L. Chaimowics et al.

    A paradigm for dynamic coordination of multiple robots

    Autonomous Robots

    (2004)
  • T. Fukuda et al.

    Cellular robotic system (CEBOT) as one of the realization of self-organizing intelligent universal manipulators

    Proc IEEE Int Conf Robotics Automat

    (1990)
  • K. Tomita et al.

    Self-assembly and self-repair method for a distributed mechanical system

    IEEE Trans Robotics Automation

    (1999)
  • S. Murata et al.

    Self-repairing mechanical systems

    Autonomous Robots

    (2001)
  • D. Rus et al.

    Crystalline robots: self-reconfiguration with compressible unit modules

    Autonomous Robots

    (2001)
  • M. Yim et al.

    Modular robots

    IEEE Spectrum

    (2002)
  • W.M. Shen et al.

    Hormone-inspired adaptive communication and distributed control for CONRO self-reconfigurable robots,

    IEEE Trans Robotics Automat

    (2002)
  • R. Kurazume et al.

    Cooperative positioning with multiple robots

    Proc IEEE Int Conf Robotics Automat

    (1994)
  • D. Fox et al.

    A probabilistic approach to collaborative multi-robot localization

    Autonomous Robots

    (2000)
  • R. Grabowski et al.

    Heterogeneous teams of modular robots for mapping and exploration

    Autonomous Robots

    (2000)
  • S. Thrun

    A probabilistic online mapping algorithm for teams of mobile robots

    Int J Robotics Res

    (2001)
  • T. Schmitt et al.

    Cooperative probabilistic state estimation for vision-based autonomous mobile robots

    IEEE Trans Robotics Automat

    (2002)
  • S.I. Roumeliotis et al.

    Distributed multi-robot localization

    IEEE Trans Robotics Automat

    (2002)
  • M. Di Marco et al.

    Simultaneous localization and map building for a team of cooperating robots: a set membership approach

    IEEE Trans Robotics Automat

    (2003)
  • M.W.M.G. Dissanayake et al.

    A solution to the simultaneous localization and map building (SLAM) problem

    IEEE Trans Robotics Automat

    (2001)
  • V.R. Lesser

    Multi-agent systems: an emerging subdiscipline of AI

    ACM Computing Surveys

    (1995)
  • P. Stone et al.

    Multiagent systems: a survey from a machine learning perspective

    Autonomous Robots

    (2000)
  • M. Erdmann et al.

    On multiple moving objects

    Algorithmica

    (1987)
  • N.J. Nilsson

    A mobile automaton: an application of artificial intelligence techniques

    Proc 1st Int Joint Conf Artif Intel

    (1969)
  • K. Fujimura

    Motion planning in dynamic environments

    (1991)
  • M. Saptharishi et al.

    Distributed surveillance and reconnaissance using multiple autonomous ATVs: CyberScout

    IEEE Trans Robotics Automat

    (2002)
  • K. Azarm et al.

    A decentralized approach for the conflict-free motion of multiple mobile robots

    Adv Robotics

    (1997)
  • R. Alami et al.

    Multi-robot cooperation in the MARTHA project

    IEEE Robotics Automat Mag

    (1998)
  • S. Zilberstein et al.

    Anytime sensing, planning and action: a practical model for robot control

    Proc 13th Int Joint Conf Artif Intel

    (1993)
  • S.M. Lavalle et al.

    Optimal motion planning for multiple robots having independent goals

    IEEE Trans Robotics Automat

    (1998)
  • T. Siméon et al.

    Path coordination for multiple mobile robots: a resolution-complete algorithm

    IEEE Trans Robotics Automat

    (2002)
  • T. Yoshioka et al.

    Sensor-based traffic rules for multiple automata based on a geometric deadlock-free characteristic

    J Robotics Mechatronics

    (1996)
  • Cited by (137)

    View all citing articles on Scopus
    View full text