1. Introduction

1.1 Motivation

Control and communication methods for multiple-robot systems have been investigated by various researchers. Problems such as coordination of multiple manipulators, motion planning and coordination of multirobot systems are generally approached with a central (hierarchical) controller in mind. Until recently, most of the multirobot systems have been "fixed" systems without autonomously moving elements. They may consist of several types of robots or manipulators.

On the other hand, there is extensive research carried out on autonomous mobile robots. Many solutions to problems including path planning and obstacle avoidance were proposed and tested. However, most of the research on autonomous mobile robots was based on a single robot interacting with its environment.

Currently, there is an increasing interest in multiple autonomous mobile robot systems due to their applicability to various tasks such as space missions, operations in hazardous environments, and military operations. Such systems bring in the problems of both multiple robot coordination and autonomous navigation. Again, multiple mobile robots may be controlled by using a hierarchical (central) controller. However, tasks mentioned above obviously require many robots which are able to navigate autonomously. It is difficult to use a central controller or a hierarchical method, sometimes because of the large distances, sometimes due to robustness and versatility problems. The advantages of a decentralized system will be outlined in the next section where we introduce the Army-ant scenario.

1.2 Context

With a name like yours, you might be any shape, almost.
Through the Looking-Glass,
Chp.6, LEWIS CARROLL

The Army-ant scenario envisages a large population of identical mobile robots which are able to find and carry a relatively small number of palletized payloads from place to place. The locations of pallets are defined by beacons whose signals can be picked up by robots. Using the beacon signals, robots are able to group around a pallet and self organize to lift and carry it to its destination. After set-down, the robots will disperse to continue the operation.

Army-ant robots will be relatively small in size, and individually incapable of carrying the load; but they will be able to act cooperatively as a transporter, similar to ant colonies in foraging activity. We treat the Army-ant robots as a self-organizing system, because self-organization -an important characteristic of most insect societies- has many advantages, as we describe in depth in the next chapter. A self-organizing system can change its structure as a function of its experience with the environment, and may accomplish complex tasks with simple individual behavior. Changes in the individual characteristics can influence the overall behavior of the system. On the other hand, the environment may cause the system to generate a different task, without any effect on individual behavior.

Army-ant robots would also have the following characteristics:

• All robots are physically and functionally identical. Therefore, they can be manufactured inexpensively in large numbers, which would be the case.
• This homogeneous population of robots is a modular system. Any robot can replace any other robot. In case of failure, the absence of a hierarchical system would prevent total system failure. Furthermore, new agents can be added to the team whenever necessary.
• Army-ant robots are designed for a broad range of tasks, not for a specific task as is the case in current multirobot systems. They can be adapted to various tasks with minimal structural changes.
• Individually, robots have limited capabilities and limited knowledge of the environment. However, as a swarm, they can exhibit "intelligent behavior". Simple individual behavior will result in an intelligent swarm behavior provided that some type of direct or indirect communications between agents exists.
• Being a homogeneous and self-organizing population, Army-ant robots form a dynamic system. They are able to (cooperatively) adjust the team size to the size of the payload. The capabilities of a team (other than physical abilities such as lifting the pallet) do not depend on the number of agents since there are no hierarchical interactions between agents.

Obviously, most of the characteristics listed above cannot be achieved by using a central controller. The number of agents and the dynamic character of the teams make it impractical. Populations of mobile robots using decentralized control methods have many other applications. Mine sweeping, maintenance work in nuclear power plants, planetary surface missions and multisatellite defense systems are areas where teams of large numbers of autonomous agents are potentially advantageous. Some of the methods we describe for the Army-ant scenario in this thesis are also suitable for the above mentioned applications. The Army-ant approach differs from the ongoing research on multiple mobile robots in its design. We try to realize a complete system designed for a practical task, instead of creating a generic system to study the problems of multiple mobile robot populations.

Figure 1.1 Material transport using Army-ant robots

1.3 Scope and Structure of Thesis

We divide self-organization in Army-ant robots into two chapters: spatial and behavioral self-organizations. Spatial self-organization refers to a reactive method of treating the agents as a many-body system interacting according to specific laws of gravitation. By defining a set of gravitational rules, it is possible to force agents into geometric arrangements, or to divide them into groups/teams. On the other hand, in behavioral self-organization, Army-ant robots' behaviors are defined on a behavioral space, where the whole system's state consists of individual behavior modes of all agents. Changes in this space are due to the activation/inhibition forces generated by robot behaviors, beacons, and environmental conditions. State-space in behavioral self-organization can be "visualized" as a multidimensional space where the dimension is related to the number of behaviors, as opposed to the spatial self-organization dealing with two or three "physical" dimensions.

Chapter 3 deals with spatial self-organization, where geometric arrangement of agents, team formation in two- and three- dimensional spaces, and related assumptions on the knowledge and influence of robotic agents are investigated. A behavioral model of the robots, system-level analysis of the Army-ant problem and several aspects of team coordination are discussed in Chapter 4. As examples, several problems which may be encountered in the Army-ant scenario and solutions to some of these problems are outlined.

Chapter 5 is devoted to technical assessment; necessary devices for communication and sensing are briefly described. Feasibility of their application to our scenario is investigated. Chapter 6 draws conclusions from the work and makes suggestions for further research. Partial listings of the source code and screen snapshots of the simulation programs are given in the Appendix. The works we cited in the text are listed in the Bibliography (In this hypertext version of the thesis, double clicking on reference numbers will display the bibliographic information about the corresponding work).

To Chapter 2