Foraging Robots

Definition of the Subject

Foraging robots are mobile robots capable of searching for and, when found, transporting objects to one or more collection points. Foraging robotsmay be single robots operating individually, or multiple robots operating collectively. Single foraging robots may be remotely tele‐operated orsemi‐autonomous; multiple foraging robots are more likely to be fully autonomous systems. In robotics foraging is important for several reasons:firstly, it is a metaphor for a broad class of problems integrating exploration, navigation and object identification, manipulation andtransport; secondly, in multi‐robot systems foraging is a canonical problem for the study of robot‐robot cooperation, and thirdly, manyactual or potential real‐world applications for robotics are instances of foraging robots, for instance cleaning , harvesting , search and rescue ,land‐mine clearance or planetary exploration .

Introduction

Foraging is a benchmark problem for robotics, especially for multi‐robot systems. It is a powerful benchmark problem for severalreasons: (1) sophisticated foraging observed in social insects, recently becoming well understood, provides both inspiration and system level models forartificial systems. (2) Foraging is a complex task involving the coordination of several – each also difficult – tasks includingefficient exploration (searching) for food or prey, physical collection (harvesting ) of food or prey almost certainly requiring physical manipulation,transport of the food or prey, homing or navigation whilst carrying the food or prey back to a nest site, and deposition of the food item in the nestbefore returning to foraging. (3) Effective foraging requires cooperation between individuals involving either communication to signal to others wherefood or prey may be found (e. g. pheromone trails, or direction giving) and/or cooperative transport of food items too large for a singleindividual to transport.

There are, at the time of writing, very few types of foraging robots successfully employed in real‐world applications. Most foraging robotsare to be found in research laboratories or, if they are aimed at real‐world applications, are at the stage of prototype orproof‐of‐concept. The reason for this is that foraging is a complex task which requires a range of competencies to be tightlyintegrated within the physical robot and, although the principles of robot foraging are now becoming established, many of the sub‐systemtechnologies required for foraging robots remain very challenging. In particular, sensing and situational awareness; power and energy autonomy; actuation,locomotion and safe navigation in unknown physical environments and proof of safety and dependability all remain difficult problems in robotics.

This article therefore focuses on describing and defining the principles of robot foraging. The majority of examples will necessarily be oflaboratory systems not aimed at solving real‐world applications but designed to model, illuminate and demonstrate those principles. The articleproceeds as follows. Section “An Abstract Model of Robot Foraging” describes an abstractmodel of robot foraging, using a finite state machine (FSM) description to define the discrete sub‐tasks, or states, that constituteforaging. The FSM method will be used throughout this article. The section then develops a taxonomy of robotforaging. Section “Single Robot Foraging” describes the essential design features that area requirement of any foraging robot, whether operating singly or in a multi‐robot team, and the technologies currently available toimplement those features; the section then outlines a number of examples of single‐robot foraging, including robots that are commerciallyavailable. Section “Multi-Robot (Collective) Foraging” then describes the development andstate‐of‐the‐art in multi‐robot (collective) foraging; strategies for cooperation are described including information sharing,cooperative transport and division of labor (task allocation), the section then reviews approaches to the mathematical modeling of multi‐robotforaging. The article concludes in Sect. “Future Directions” with a discussion offuture directions in robot foraging and an outline of the technical challenges that remain to be solved.

An Abstract Model of Robot Foraging

Foraging, by humans or animals, is the act of searching (widely) for and collecting (or capturing) food for storage or consumption. Robot foragingis defined more broadly as searching for and collecting any objects, then returning those objects to a collectionpoint. Of course if the robot(s) are searching for energy resources for themselves then robot foraging will have precisely the same meaning as human oranimal foraging. In their definitive review paper on cooperative mobile robotics Cao et al. state simply “In foraging, a group of robots mustpick up objects scattered in the environment” [14]. Østergaard et al. define foraging as“a two‐step repetitive process in which (1) robots search a designated region of space for certain objects, and (2) once found theseobjects are brought to a goal region using some form of navigation” [54].

Figure 1 shows a Finite State Machine (FSM) representation of a foraging robot (orrobots). In the model the robot is in always in one of four states: searching, grabbing, homing or depositing. Implied in this model is,firstly, that the environment or search space contains more than one of the target objects; secondly, that there is a single collection point (hencethis model is sometimes referred to as central‐place foraging), and thirdly, that the process continues indefinitely. The four states are defined asfollows.

Figure 1

Finite State Machine for Basic Foraging

• 1. Searching. In this state the robot is physically moving through the search space using its sensors to locate and recognize the target items. At this level of abstraction we do not need to state how the robot searches: it could, for instance, wander at random, or it could employ a systematic strategy such as moving alternately left and right in a search pattern. The fact that the robot has to search at all follows from the pragmatic real‐world assumptions that either the robot's sensors are of short range and/or the items are hidden (behind occluding obstacles for instance); in either event we must assume that the robot cannot find items simply by staying in one place and scanning the whole environment with its sensors. Object identification or recognition could require one of a wide range of sensors and techniques. When the robot finds an item it changes state from searching to grabbing. If the robot fails to find the target item then it remains in the searching state forever; searching is therefore the ‘default’ state.

• 2. Grabbing. In this state the robot physically captures and grabs the item ready to transport it back to the home region. Here we assume that the item is capable of being grabbed and conveyed by a single robot (the case of larger items that require cooperative transport by more than one robot will be covered later in this article). As soon as the item has been grabbed the robot will change state to homing.

• 3. Homing. In this state the robot must move, with its collected object, to a home or nest region. Homing clearly requires a number of stages, firstly, determination of the position of the home region relative to where the robot is now, secondly, orientation toward that position and, thirdly, navigation to the home region. Again there are a number of strategies for homing: one would be to re‐trace the robot's path back to the home region using, for instance, odometry or by following a marker trail; another would be to home in on a beacon with a long range beacon sensor. When the robot has successfully reached the home region it will change state to depositing.

• 4. Depositing. In this state the robot deposits or delivers the item in the home region, and then immediately changes state to searching and hence resumes its search.

There are clearly numerous variations on this basic foraging model. Some are simplifications: for instance if a robot is searching for one ora known fixed number of objects then the process will not loop indefinitely. Real robots do not have infinite energy and so a model of practicalforaging would need to take account of energy management. However, many variations entail either complexity within one or more of the four basic states(consider, for instance, objects that actively evade capture – a predator‐prey model of foraging), or complexity in the interaction orcooperation between robots in multi‐robot foraging. Thus the basic model stands as a powerful top‐level abstraction.

A Taxonomy of Robot Foraging

Oster and Wilson classify the foraging strategies of social insects into five types, summarized in Table 1 [53]. Hölldobler and Wilson describe a more comprehensive taxonomy of insect foraging as a combination of strategies for (1) hunting, (2) retrieval and (3) defense [30]. However, since we will not be concerned in this article with defensive robot(s), then Oster and Wilson's classification is more than sufficient as a basis for consideration of robot foraging.

Table 1 Oster and Wilson's classification of insect foraging

In robotics several taxonomies have been proposed for multi‐robot systems. Dudek et al. define seven taxonomic axes: collective size; communications [range, topology and bandwidth]; collective reconfigurability; processing ability and collective composition [21]. Here collective size may be: single robot, pair of robots, limited (in relation to the size of the environment) or infinite (number of robots ${ N_r \gg 1 }$); communications range may be: none (i. e. robots do not communicate directly), near (robots have limited range communication) or infinite (any robot may communicate with any other). Collective reconfigurability refers to spatial organization and may be: static (robots are in a fixed formation); coordinated (robots may coordinate to alter their formation) or dynamic (spatial organization may change arbitrarily). Processing ability refers to the computational model of individuals, here Dudek et al. make the distinction between the general purpose computer which most practical robots will have, or simpler models including the finite state machine. Collective composition may be: identical (robots are both physically and functionally identical), homogeneous or heterogeneous. Dudek et al. makes the distinction – highly relevant to foraging robots – between tasks that are traditionally single‐agent, tasks that are traditionally multi‐agent, tasks that require multiple agents, or tasks that may benefit from multiple agents.

In contrast to Dudek's taxonomy which is based upon the characteristics of the robot(s), Balch characterizes tasks and rewards [3]. Balch's task taxonomy is particularly relevant to robot foraging because it leads naturally to the definition of performance metrics. Balch articulates six task axes: time; criteria; subject of action; resource limits; group movement and platform capabilities. Time and criteria are linked; time may be: limited (task performance is determined by how much can be achieved in the fixed time); minimum (task performance is measured as time taken to complete the task); unlimited time, or synchronized (robots must synchronize their actions). Criteria refers to how performance is optimized over time; it may be finite (performance is summed over a finite number of time steps); average (performance is averaged over all time) or discounted (future performance is discounted geometrically). Subject of action may be: object- or robot-based, depending upon whether the movement or positioning of objects or robots, respectively, is important. Balch's fourth criterion is again relevant to foraging: resource limits which may be: limited (external resources, i. e. objects to be foraged, are limited); energy (energy consumption must be minimized); internally competitive (one robot's success reduces the likelihood of success of another), or externally competitive (if, for instance, one robot team competes against another). See also [24] for a formal analysis and taxonomy of task allocation.

Østergaard et al. [54] develop a simple taxonomy of foraging by defining eight characteristics each of which has two values:

• 1. number of robots: single or multiple;

• 2. number of sinks (collection points for foraged items): single or multiple;

• 3. number of source areas (of objects to be collected): single or multiple;

• 4. search space: unbounded or constrained;

• 5. number of types of object to be collected: single or multiple;

• 6. object placement: in fixed areas or randomly scattered;

• 7. robots: homogeneous or heterogeneous and

• 8. communication: none or with.

This taxonomy maps more closely (but not fully) onto the insect foraging taxonomy of Table 1, but fails to capture task performance criteria, nor does it specify the strategy for either searching for, physically collecting or retrieving objects. Tables 2 and 3 propose a more comprehensive taxonomy for robot foraging that incorporates the robot‐centric and task/performance oriented features of Dudek et al. and Balch, respectively, with the environmental features of Østergaard et al., whilst mapping onto the insect foraging classification of Oster and Wilson. The four major axes are Environment, Robot(s), Performance and Strategy. Each major axis has several minor axes and each of these can take the values enumerated in the third column of Tables 2 and 3. The majority of the values are self‐explanatory, those that are not are annotated. Table 3 suggests a mapping of Oster and Wilson's classification onto robot foraging strategies.

Table 2 A taxonomy of robot foraging, part A

Table 3 A taxonomy of robot foraging, part B

Following Balch [3], we can formalize successful object collection and retrieval as follows:

$$ F(O_i,t) = \begin{cases} 1 & \text{if object } O_i \text{ is in a sink at time } t \\ 0 & \text{otherwise}\:. \end{cases} $$

(1)

If the foraging task is performance time limited (Performance time = fixed) and the objective is to maximize the number of objects foraged within fixed time T, then we may define a performance metric for the number of objects collected in time T,

$$ P = \sum_{i=1}^{N_o} F(O_i, t_0 + T) $$

(2)

where N _o is the number of objects available for collection and t ₀ is the start time. A metric for the number of objects foraged per second is clearly, ${ P_t = P/T }$. P as defined here is independent of the number of robots. In order to measure the performance improvement of multi‐robot foraging, for example the benefit gained by search or homing with trail following, recruitment or coordination (assuming the task can be completed by a single robot, grabbing = single and transport = single), then we may define the performance of a single robot P _s as defined in Eq. 2 and use this a baseline for the normalized performance P _m of a multi‐robot system,

$$ P_m = \frac{P}{N_r} $$

(3)

where N _r is the total number of robots. The efficiency of multi‐robot foraging is then the ratio ${ {P_m}/{P_s} }$.

Consider now that we wish instead to minimize the energy cost of foraging (Performance energy = minimum). If the energy cost of foraging object i is E _i , then we may define a performance metric for the number of objects foraged per Joule of energy,

$$ P_{e} = \frac{N_o}{\sum_{i=1}^{N_o}E_i} $$

(4)

then seek the foraging strategy that achieves the highest value for P _e .

Single Robot Foraging

The design of any foraging robot, whether operating alone or as part of a multi‐robot team, will necessarily follow a similar basicpattern. The robot will require one or more sensors, with which it can both sense its environment for safe navigationand detect the objects or food‐items it seeks; actuators for both locomotion through the environment and forphysically collecting, holding then depositing its prey, and a control system to provide the robot with – atthe very least – a set of basic reflex behaviors. Since robots are machines that perform work, which requires energy, then power management is important; if, for instance, the robot is foraging for its own energy then balancing its energy needs withthe energy cost of foraging is clearly critical. Normally, a communication transceiver is also a requirement,either to allow remote tele‐operation or monitoring or, in the case of multi‐robot collective foraging, for robot‐robotcommunications. A foraging robot is therefore a complex set of interconnected sub‐systems and, although its system‐level structuremay follow a standard pattern, the shape and form of the robot will vary significantly depending upon its intended environment andapplication.

This section will review approaches and techniques for sensing, actuation, communications and control, within the context of robot foraging and withreference to research which focuses on advancing specific capabilities within each of these domains of interest. Then a number of examples of singlerobot foraging are given, including real‐world applications.

Sensing

Obstacle Avoidance and Path Planning

There are many sensors available to designers of foraging robots and a comprehensive review can be found in [22]. A foraging robot will typically require short or medium range proximity sensors for obstacle avoidance, such as infra‐red return‐signal‐intensity or ultrasonic‐ or laser‐based time‐of‐flight systems. The most versatile and widely used device is the 2D or 3D scanning laser range finder which can provide the robot with a set of radial distance measurements and hence allow the robot to plan a safe path through obstacles [64].

Localization

All but the simplest foraging robots will also require sensors for localization, that is to enable the robot to estimate its own position in the environment. If external reference signals are available such as fixed beacons so that a robot can use radio trilateration to fix its position relative to those beacons, or a satellite navigation system such as the Global Positioning System (GPS) , then localization is relatively straightforward. If no external infrastructure is available then a robot will typically make use of several sensors including odometry , an inertial measurement unit (IMU) and a magnetic compass, often combining the data from all of these sensors, including laser scanning data, to form an estimate of its position. Simultaneous Localization and Mapping (SLAM) is a well‐known stochastic approach which typically employs Kalman filters to allow a robot (or a team of robots) to both fix their position relative to observed landmarks and map those landmarks with increasing confidence as the robot(s) move through the environment [18].

Object Detection

Vision is often the sensor of choice for object detection in laboratory experiments in foraging robots. If, for instance, the object of interest has a distinct color which stands out in the environment then standard image processing techniques can be used to detect then steer towards the object [31]. However, if the environment is visually cluttered, unknown or poorly illuminated then vision becomes problematical. Alternative approaches to object detection include, for instance, artificial odor sensors: Hayes et al. demonstrated a multi‐robot approach to localization of an odor source [28]. An artificial whisker modeled on the Rat mystacial vibrissae has recently been demonstrated [56], such a sensor could be of particular value in dusty or smoky environments.

Actuation

Locomotion

The means of physical locomotion for a foraging robot can take many forms and clearly depends on the environment in which the robot is intended to operate. Ground robots typically use wheels, tracks or legs, although wheels are predominantly employed in proof‐of‐concept or demonstrator foraging robots. An introduction to the technology of robot mobility can be found in [63]. Flying robots (unmanned air vehicles – UAVs ) are either fixed- or rotary‐wing; for recent examples of work towards teams of flying robots see [13] (fixed‐wing) and [51] (rotary‐wing). Underwater robots (unmanned underwater vehicles – UUVs ) generally use the same principles for propulsion as submersible remotely operated vehicles (ROVs) , [70]. Whatever the means of locomotion important principles which apply to all foraging robots are that robot(s) must be able to (1) move with sufficient stability for the object detection sensors to be able to operate effectively and (2) position themselves with sufficient precision and stability to allow the object to be physically grabbed. These factors place high demands on a foraging robot's physical locomotion system, especially if the robot is required to operate in soft or unstable terrain.

Object Manipulation

The manipulation required of a foraging robot is clearly dependent on the form of the object and the way the object presents itself to the robot as it approaches. The majority of foraging experiments or demonstrations have simplified the problem of object manipulation by using objects that are, for instance, always the right way up (metal pucks or wooden sticks protruding from holes) so that a simple gripper mounted on the front of the robot is able to grasp the objects with reasonable reliability. However, in general a foraging robot would require the versatility of a robot arm (multi‐axis manipulator) and general purpose gripper (hand) such that – with appropriate vision sensing – the robot can pick up the object regardless of its shape and orientation. This technology is well developed in tele‐operated robots used for remote inspection and handling of dangerous materials or devices, see [62,66].

Communications

Communications is of fundamental importance to robot foraging. Only in the simplest case of a single robot foraging autonomously would communications be unnecessary. For single robot teleoperation radio communication between operator and robot is clearly an essential requirement. In multi-robot foraging robot-robot communication is frequently employed to improve multi‐robot performance; all six axes of strategy in the taxonomy of Table 3: search, grabbing, transport, homing, recruitment and coordination may require some form of robot‐robot communication. Arai et al. point out the important distinction between explicit and implicit communication [1].

Explicit Communication

Explicit communication applies when robots need to exchange information directly. The physical medium of communication is frequently (but not necessarily) radio, and wireless local area network (WLAN) technology is highly appropriate to terrestrial multi‐robot systems, not least because a spatially distributed team of wireless networked robots naturally forms an ad‐hoc network, which – providing the team maintains sufficient connectivity – allows any robot to communicate with any other via multiple hops, [69]. A method for linking wireless connectivity to locomotion in order to maintain connectivity is described in [52]; work that falls within the framework of situated communications proposed by Støy. Situated communication pertains when “both the physical properties of the signal that transfers the message and the content of the message contribute to its meaning” [65].

Implicit Communication

Implicit communication applies when robots communicate not directly but via the environment, also known as stigmergic communications. Thus one robot changes the environment and another senses the change and alters its behavior accordingly. Beckers et al., in one of the first demonstrations of self‐organized multi‐robot puck clustering, show that stigmergic communication alone can give rise to the desired overall group behavior [6]. However, in their study on multi‐robot communication, Balch and Arkin show that while stigmergy may be sufficient to complete the task, direct communication can increase efficiency [4]. Trail following, in which a robot follows a short‐lived trail left by other(s), is an example of implicit communication [59,60].

Control

From a control perspective the simplicity of the finite state machine for basic foraging, in Fig. 1, is deceptive. In principle, a very simple foraging robot could be built with basic hard‐wired reflex actions such as obstacle avoidance and taxis toward the attractor object; such a robot is known as a Braitenberg vehicle , after his landmark work [11]. However, even simple foraging requires a complex set of competencies that would be impractical to implement except as a program on one or more embedded computers (microprocessors) in the robot. There are clearly many ways of building such a control program, but in the field of mobile robotics a number of robot control architectures have been defined. Such architectures mean that robot designers can approach the design of the control system in a principled way.

A widely adopted robot control architecture, first proposed and developed by Brooks, is the layered subsumption architecture known generically as behavior‐based control  [12]. Behavior‐based control is particularly relevant to foraging robots since, like foraging, it is biologically inspired. In particular, as Arkin describes in [2], the principles of behavior‐based control draw upon ethology – the study of animal behavior in the natural environment. Essentially behavior‐based control replaces the functional modularity of earlier robot control architectures with task achieving modules, or behaviors. Matarić uses Brooks' behavior language (BL) to implement a set of basic behaviors for multi‐robot foraging, as described in more detail below in Sect. Multi-Robot (Collective) Foraging, [46,47]. Refer to [14] for a comprehensive review of group control architectures for multi‐robot systems.

Figure 2

Subsumption control architecture for basic foraging

Figure 2 shows the subsumption architecture for basic foraging (from Fig. 1), with the addition of avoidance for safely avoiding obstacles (including other robots in the case of multi‐robot foraging). Each behavior runs in parallel and, when activated suppresses the output of the layer(s) below to take control of the robot's actuators.

Examples of Single Robot Foraging

A Soda-Can Collecting Robot

Possibly the first demonstration of autonomous single‐robot foraging is Connell's soda‐can collecting robot Herbert , [15]. Herbert's task was to wander safely through an office environment while searching for empty soda‐cans; upon finding a soda‐can Herbert would need to carefully grab the can with its hand and 2 degrees‐of‐freedom arm, then return to a waste basket to deposit it before resuming the search. Herbert therefore represents an implementation of exactly the basic foraging model of Fig. 1 and 2. However, two of the behaviors are not so straightforward. Both searching and homing require the robot to be able to navigate safely through a cluttered and unstructured ‘real‐world’ environment, while grabbing is equally complex given the precision required to safely reach and grab the soda‐can. Thus Herbert's control system required around 40 low‐level behaviors in order to realize foraging.

A Robot Predator

Arguably the first attempt to build a robot capable of actively predating for its own energy is the Slugbot of Holland and co‐workers, [26,33]. The Slugbot (Fig. 3) solved the difficult problems of finding and collecting slugs in an energy efficient manner by means of, firstly, a long but light articulated arm which allows the robot to scan (in spiral fashion) a large area of ground for slugs without having to physically move the whole robot (which is much more costly in energy). Secondly, the special purpose gripper at the end of the arm is equipped with a camera which, by means of reflected red light and appropriate vision processing, is able to reliably detect and collect the slugs. An evolution of the Slugbot, the Ecobot , uses microbial fuel cell (MFC) technology to generate electrical energy directly from unrefined biomass [49].

Figure 3

The Slugbot : a proof‐of‐concept robot predator

Real-World Foraging Robots

Autonomous crop harvesting is an obvious real‐world application of single‐robot foraging. The Demeter system [57] has successfully demonstrated automated harvesting of cereal crops. Demeter uses a combination of GPS for coarse navigation and vision to sense the crop‐line and hence fine‐tune the harvester's steering to achieve a straight and even cut of the crop. The vision processing is challenging because it has to cope with a wide range of lighting conditions including – in conditions of bright sunlight – shadows cast onto the crop line by the harvester itself. In the field of automated agriculture a number of proof‐of‐concept robot harvesters have been demonstrated for cucumber, tomato and other fruits [34,35].

Robot lawn mowers and vacuum cleaners can similarly be regarded as simple forms of foraging robot and are notable because they are the only form of autonomous foraging robot in commercial production; in both cases the search task is simple because the grass, or dirt are not discrete objects to be found. The search problem for robot lawn movers and vacuum cleaners thus becomes the problem of energy efficient strategies for (1) safely covering the whole search space while avoiding obstacles and (2) homing and docking to a re‐charging station. Robot lawn mowers typically require a wire to be installed at the perimeter of the lawn, thus delimiting the robot's working area, see [29] for a survey of commercial robot lawn mowers. A short account of the development of a vacuum cleaning robot is given in [58].

Although technically an off‐world application, the planetary rover may be regarded as an instance of single‐robot foraging in which the objects of interest (geological samples) are collected and analyzed within the robot. Autonomous sample‐return robots would be true foragers [61]. The proof‐of‐concept robot astrobiologist Zoë forages – in effect – for evidence of life [67].

Multi-Robot (Collective) Foraging

Foraging is clearly a task that lends itself to multi‐robot systems and, even if the task can be accomplished by a single robot,foraging should – with careful design of strategies for cooperation – benefit from multiple robots. Swarm intelligence is the study of naturaland artificial systems of multiple agents in which there is no centralized or hierarchical command or control. Instead, global swarm behaviors emerge asa result of local interactions between the agents and each other, and between agents and the environment, [8]. Swarm robotics is concerned with the design of artificial robot swarms based upon the principles of swarmintelligence, thus control is completely distributed and robots, typically, must choose actions on the basis only of local sensing andcommunications, [7,16]. Swarm robotics is thusa sub‐set of multi‐robot systems and, in the taxonomy of Table 2 the strategy: coordination = self‐organized.

Foraging is therefore a benchmark problem within swarm robotics, not least because of the strong cross‐over between the study ofself‐organization in social insects and their artificial counterparts within swarm intelligence [19]. This section will therefore focus on examples of multi‐robot foraging from within the field of swarmrobotics. Three strategies for cooperation will be outlined: information sharing, physical cooperation and division of labor . The section will concludewith an outline of the problem of mathematical modeling of swarms of foraging robots.

Without Cooperation

Balch and co‐workers describe the winners of the ‘Office Cleanup Event’ of the 1994 AAAI Mobile Robot Competition : a multi‐robot trash‐collecting team [5]. The robots were equipped with a vision system for recognition and distance estimation of trash items (primarily soda cans) and differentiation between trash items, wastebaskets and other robots. The robots did not communicate, but employed a collective strategy in which robots generate a strong repulsive force if they see each other while searching, and a weaker (but sufficient for avoidance) repulsive force while in other states; this had the effect of causing the robots to spread‐out and hence search the environment more efficiently. Interestingly, Balch et al. found that the high density of trash in the competition favored a ‘sit‐and‐spin’ strategy to scan for trash items rather than the random wander approach of the original design. The FSM was essentially the same schema as shown in Fig. 1 except that since there could be a number of wastebaskets at unknown locations then ‘homing’ becomes ‘search for nearest wastebasket’.

Strategies for Cooperation

Information Sharing

Matarić and Marjanovic provide what is believed to be the first description of a multi‐robot foraging experiment using real (laboratory) robots in which there is no centralized control [47]. They describe a system of 20 identical 12″ 4‑wheeled robots, equipped with: a two‐pronged forklift for picking up, carrying and stacking metal pucks; proximity and bump sensors; radio transceivers for data communication and a sonar‐based global positioning system. Matarić and Marjanovic extend the basic five state foraging model (wandering, grabbing, homing, dropping and avoiding), to introduce information sharing as follows. If a robot finds a puck it will grab it but also broadcast a radio message to tell other robots it has found a puck. Meanwhile, if another robot in the locale hears this message it will first enter state tracking to home in on the source of the message, then state searching – a more localized form of wandering. The robot will return to wandering if it finds no puck within some time out period. Furthermore, while in state tracking a robot will also transmit a radio signal. If nearby robots hear this signal they will switch from wandering into following to pursue the tracking robot. Thus the tracking robot actively recruits additional robots as it seeks the original successful robot (a form of secondary swarming, [48]); when the tracking robot switches to searching its recruits will do the same. Figure 4 shows a simplified FSM . Within the taxonomy of Table 3 Strategy : recruitment = direct and indirect.

Physical Cooperation

Figure 4

Finite State Machine for multi‐robot foraging with recruitment – adapted from [47]

Figure 5

Cooperative grabbing : Khephera robots engaged in collective stick‐pulling . With kind permission of A. Martinoli

Cooperative Grabbing

Consider the case of multi‐robot foraging in which the object to be collected cannot be grabbed by a single robot working alone, in Table 3 this is Strategy: grabbing = cooperative. Ijspeert et al. describe an experiment in collaborative stick‐pulling in which two robots must work together to pull a stick out of a hole [32,44]. Each Khephera robot is equipped with a gripper capable of grabbing and lifting the stick, but the hole containing the stick is too deep for one robot to be able to pull the stick out alone; one robot must pull the stick half‐way then wait for another robot to grab the stick and lift it clear of the hole, see Fig. 5. Ijspeert and co‐workers describe an elegant minimalist strategy which requires no direct communication between robots. If one robot finds a stick it will lift it and wait. If another finds the same stick it will also lift it, on sensing the force on the stick from the second robot the first robot will let go, hence allowing the second to complete the operation.

Figure 6

Cooperative transport by s‐bots . (Left) s‐bots approach the attractor object, (middle) s‐bots start to grab the object, (right) s‐bots collectively drag the object toward a beacon. With kind permission of M. Dorigo

Cooperative Transport

Now consider the the situation in which the object to be collected is too large to be transported by a single robot, in Table 3 Strategy: transport = cooperative. Parker describes the ALLIANCE group control architecture applied to an example of cooperative box‐pushing by two robots [55].

Arguably the most accomplished demonstration of cooperative multi‐robot foraging to date is within the swarm‐bot project of Dorigo and co‐workers [20]. The s‐bot is a modular robot equipped with both a gripper and a gripping ring, which allows one robot to grip another [50]. Importantly, the robot is able to rotate its wheelbase independently of the gripping ring so that robots can grip each other at any arbitrary point on the circumference of the grip ring but then rotate and align their wheels in order to be able to move as a single unit (a swarm‐bot). Groß et al. describe cooperative transport which uses visual signaling [27]. s‐bots are attracted to the (large) object to be collected by its ring of red LEDs. The s‐bot's LEDs are blue, but when an s‐bot finds and grabs the attractor object it switches its LEDs to red. This increases the red light intensity to attract further s‐bots which may grab either the object, or arbitrarily a robot already holding the object. The s‐bots are then able to align and collectively move the object.

Division of Labor

In multi‐robot foraging it is well know that overall performance (measured, for instance, as the number of objects foraged per robot in a given time interval), does not increase monotonically with increasing team size because of interference between robots (overcrowding), [4,25,38]. Division of labor in ant colonies has been well studied and in particular a response threshold model is described in [9] and [10]; in essence a threshold model means that an individual will engage in a task when the level of some task‐associated stimulus exceeds its threshold.

For threshold‐based multi‐robot foraging with division of labor Fig. 7 shows a generalized finite state machine for each robot. In this foraging model the robot will not search endlessly. If the robot fails to find a food‐item because, for instance, its searching time exceeds a maximum search time threshold T _s , or its energy level falls below a minimum energy threshold, then it will abandon its search and return home without food, shown as failure. Conversely success means food was found, grabbed and deposited. Note, however, that a robot might see a food‐item but fail to grab it because, for instance, of competition with another robot for the same food‐item. The robot now also has a resting state during which time it remains in the nest conserving energy. The robot will stop resting and leave home which might be according to some threshold criterion, such as its resting time exceeding the maximum rest time threshold T _r , or the overall nest energy falling below a given threshold.

Figure 7

Finite State Machine for foraging with division of labor

Let us consider the special case of multi‐robot foraging in which robots are foraging for their own energy. For an individual robot foraging costs energy, whereas resting conserves energy. We can formally express this as follows. Each robot consumes energy at A units per second while searching or retrieving and B units per second while resting, where ${ A > B }$. Each discrete food item collected by a robot provides C units of energy to the swarm. The average food item retrieval time, is a function of the number of foraging robots x, and the density of food items in the environment, ρ, thus ${ t = f(x,\rho) }$.

If there are N robots in the swarm, E _c is the energy consumed and E _r the energy retrieved, per second, by the swarm then

$$ E_c = Ax + B(N-x) $$

(5)

$$ E_r = Cx/t = \frac{Cx}{f(x,\rho)}\:. $$

(6)

The average energy income to the swarm, per second, is clearly the difference between the energy retrieved and the energy consumed,

$$ E = E_r - E_c = \left(\frac{C}{f(x,\rho)} - (A-B)\right) x - BN $$

(7)

Equation 7 shows that maximizing the energy income to the swarm requires either increasing the number of foragers x or decreasing the average retrieval time ${ f(x,\rho) }$. However, if we assume that the density of robots in the foraging area is high enough that interference between robots will occur then, for constant ρ, increasing x will increase ${ f(x,\rho) }$. Therefore, for a given food density ρ there must be an optimal number of foragers ${ x^* }$.

Krieger ad Billeter adopt a threshold‐based approach to the allocation of robots to either foraging or resting; in their scheme each robot is allocated a fixed but randomly chosen activation threshold [36]. While waiting in the nest each robot listens to a periodic radio broadcast indicating the nest‐energy level E; when the nest‐energy level falls below the robot's personal activation threshold then it leaves the nest and searches for food. It will continue to search until either its search is successful, or it runs out of energy and returns home; if its search is successful and it finds another food‐item the robot will record its position (using odometry ). On returning home the robot will radio its energy consumption thus allowing the nest to update its overall net energy. Krieger and Billeter show that team sizes of 3 or 6 robots perform better than 1 robot foraging alone, but larger teams of 9 or 12 robots perform less well. Additionally, they test a recruitment mechanism in which a robot signals to another robot waiting in the nest to follow it to the food source, in tandem. Krieger's approach is, strictly speaking, not fully distributed in that the nest is continuously tracking the average energy income E; the nest is – in effect – acting as a central coordinator.

Based upon the work of [17] on individual adaptation and division of labor in ants, Labella et al. describe a fully distributed approach that allows the swarm to self‐organize to automatically find the optimal value ${ x^* }$ [37]. They propose a simple adaptive mechanism to change the ratio of foragers to resters by adjusting the probability of leaving home based upon successful retrieval of food. With reference to Fig. 7 the mechanism works as follows. Each robot will leave home, i. e. change state from resting to searching, with probability P _l . Each time the robot makes the success transition from deposit to resting, it increments its P _l value by a constant Δ multiplied by the number of consecutive successes, up to a maximum value P _max. Conversely, if the robot's searching time is up, the transition failure in Fig. 7, it will decrement its P _l by Δ times the number of consecutive failures, down to minimum P _min. Interestingly, trials with laboratory robots show that the same robots self‐select as foragers or resters – the algorithm exploits minor mechanical differences that mean that some robots are better suited as foragers.

Recently Liu et al. have extended this fully distributed approach by introducing two additional adaptation rules [43]. As in the case of Labella et al. individual robots use internal cues (successful object retrieval), but Liu adds environmental cues (collisions with team mates while searching), and social cues (team mate success in object retrieval), to dynamically vary the time spent foraging or resting. Furthermore, Liu investigates the performance of a number of different adaptation strategies based on combinations of these three cues. The three cues increment or decrement the searching time and resting time thresholds T _s and T _r as follows (note that adjusting T _r is equivalent to changing the probability of leaving the nest P _l ):

• 1. Internal cues. If a robot successfully finds food it will reduce its own rest time T _r ; conversely if the robot fails to find food it will increase its own rest time T _r .

• 2. Environment cues. If a robot collides with another robot while searching, it will reduce its T _s and increase its T _r times.

• 3. Social cues. When a robot returns to the nest it will communicate its food retrieval success or failure to the other robots in the nest. A successful retrieval will cause the other robots in the nest to increase their T _s and reduce their T _r times. Conversely failure will cause the other robots in the nest to reduce their T _s and increase their T _r times.

In order to evaluate the relative effect of these cues three different strategies are tested, against a baseline strategy of no cooperation. The strategy/cue combinations are detailed in Table 4.

Table 4 Foraging swarm strategy – cue combinations

Figures 8 and 9, from [43], show the number of active foragers and the instantaneous net swarm energy, respectively, for a swarm of eight robots. In both plots the food density in the environment is changed at time ${ t=5000 }$ and again at time ${ t=10000 }$ seconds. Figure 8 shows the swarm's ability to automatically adapt the number of active foragers in response to each of the step changes in food density. The baseline strategy S ₁ shows of course that all eight robots are actively foraging continuously; S ₂–S ₄ however require fewer active foragers and strategies with social and environmental cues, S ₃ and S ₄, clearly show the best performance. Notice, firstly that the additional of social cues – communication between robots – significantly improves the rate at which the system can adapt the ratio of foragers to resters and, secondly, that the addition of environmental cues – collisions with other robots – brings only a marginal improvement. The rates of change of net swarm energy in Fig. 9 tell a similar story. Interestingly, however, we see very similar gradients for S ₂–S ₄ when the food density is high (on the RHS of the plot), but when the food density is medium or poor the rate of increase in net energy of strategies S ₃ and S ₄ is significantly better than S ₂. This result interestingly suggests that foraging robots benefit more from cooperation when food is scarce, than when food is plentiful.

Figure 8

Number of foraging robots x in a foraging swarm of ${ N=8 }$ robots with self‐organized division of labor . S ₁ is the baseline (no cooperation strategy); S ₂, S ₃ and S ₄ are three different cooperation strategies (see Table 4). Food density changes from 0.03 (medium) to 0.015 (poor) at ${ t=5000 }$, then from 0.015 (poor) to 0.045 (rich) at ${ t=10000 }$. Each plot is the average of 10 runs

Figure 9

Instantaneous net energy E of a foraging swarm with self‐organized division of labor. S ₁ is the baseline (no cooperation strategy); S ₂, S ₃ and S ₄ are three different cooperation strategies (see Table 4). Food density changes from 0.03 (medium) to 0.015 (poor) at ${ t=5000 }$, then from 0.015 (poor) to 0.045 (rich) at ${ t=10000 }$. Each plot is the average of 10 runs

Mathematical Modeling

A multi‐robot system of foraging robots is typically a stochastic non‐linear dynamical system and therefore challenging to mathematically model, but without such models any claims about the correctness of foraging algorithms are weak. Experiments in computer simulation or with real‐robots (which provide in effect an ‘embodied’ simulation) allow limited exploration of the parameter space and can at best only provide weak inductive proof of correctness. Mathematical models on the other hand, allow analysis of the whole parameter space and discovery of optimal parameters. Ultimately, in real‐world applications, validation of a foraging robot system for safety and dependability will require a range of formal approaches including mathematical modeling.

Martinoli and coworkers proposeda  microscopic approach to study collective behavior of a swarm of robots engaged in cluster aggregation [45] and collaborative stick‐pulling  [32], in which a robot's interactions with other robots and the environment are modeled as a series of stochastic events, with probabilities determined by simple geometric considerations and systematic experiments with one or two real robots.

Lerman, Martinoli and co‐workers have alsodeveloped the macroscopic approach, as widely used in physics, chemistry, biology and the social sciences, to directly describe the collective behavior of the robotic swarm. A class of macroscopic models have been used to study the effect of interference in a swarm of foraging robots [38] and collaborative stick‐pulling [39,44]. A review of macroscopic models is given in [41]. More recently, Lerman et al. [40] successfully expanded the macroscopic probabilistic model to study dynamic task allocation in a group of robots engaged in a puck collecting task, in which the robots need to decide whether to pick up red or green pucks based on observed local information.

A Macroscopic Mathematical Model of Multi‐Robot Foraging with Division of Labor

Recently Liu et al. have applied the macroscopic approach to develop a mathematical model for foraging with division of labor (as described above in Section “Division of Labor”), [42]. The finite state machine of Fig. 7 is extended in order to describe the probabilistic behavior of the whole swarm, resulting in a probabilistic finite state machine (PFSM). In Fig. 10 each state represents the average number of robots in that state. The five basic states are S for searching, H for homing, G for grabbing, D for depositing and R for resting, and the average number of robots in each of these states is respectively N _S , N _H , N _G , N _D and N _R . ${ \tau_S }$, ${ \tau_H }$, ${ \tau_G }$, ${ \tau_D }$ and ${ \tau_R }$ represent the average times a robot will spend in each state before moving to the next state.

Figure 10

Probabilistic Finite State Machine (PFSM) for foraging with division of labor

In each time step a robot in state S has probability ${ \gamma_f }$ of finding a food‐item and moving to state G, in which it will move towards the target food‐item until it is close enough to grab it using the gripper. Once the robot successfully grabs the food‐item it will move to state D, in which the robot moves back to the ‘nest’ carrying the food‐item and deposits it. After the robot has unloaded the food‐item it will rest in state R, for ${ \tau_R }$ seconds and then move to S to resume searching. Meanwhile, if the robot in state S fails to find a food‐item within time ${ \tau_S }$, it will move to state H, and return to the ‘nest’ to save energy or minimize interference with other robots. Because of competition among robots more than one robot may see the same food‐item and thus move towards it at the same time; clearly only one of them can grab it, a robot in state G therefore has probability ${ \gamma_l }$ to lose sight of the food‐item if it has already been grabbed by another robot, which in turn drives the robot back to state S to resume its search.

In foraging interference between robots because of overcrowding, competition for food‐items or simply random collisions is a key aspect of the dynamics of foraging. Thus collision avoidance is modeled as follows. Robots in states S, G, D and H will move to avoidance states A, A _G , A _D and A _H respectively with probability ${ \gamma_r }$, as shown in Fig. 10. The avoidance behavior then takes ${ \tau_A }$ seconds to complete before the robot moves back to its previous state.

Constructing the mathematical model requires two further steps. Firstly, writing down a set of difference equations (DEs) describing the change in the average number of robots in each state from one time step to the next and, secondly, estimating the state transition probabilities . Expressing the PFSM as a set of DEs is relatively straightforward. For instance, the change in the average number of robots N _A in state A from time step k to ${ k+1 }$ is given as:

$$ N_A(k+1) = N_A(k) + \gamma_rN_S(k) - \gamma_rN_S(k - T_A) $$

(8)

where ${ \gamma_rN_S(k) }$ is the number of robots that move from the search to the avoidance state A and ${ \gamma_rN_S(k - T_A) }$ is the number of robots that return to S from state A after time T _A (note T _A is ${ \tau_A }$ discretized for time step duration ${ \Delta t }$). The full set of DEs is given in [42]. Clearly, the total number of robots in the swarm remains constant from one time step to the next,

$$ \begin{aligned} N= & N_S(k) + N_R(k) + N_G(k) + N_D(k) + N_H(k) \\ & + N_{A}(k) + N_{A_H}(k)+ N_{A_G}(k)+ N_{A_D}(k) \end{aligned} $$

(9)

Estimating state transition probabilities can be challenging but if we simplify the environment by placing the ‘nest’ region at the center of a circular environment in which the food growing area is bounded by two concentric rings in a bounded arena, as shown in Fig. 11, then a purely geometrical approach can be used to estimate ${ \gamma_f }$, ${ \gamma_r }$ and ${ \gamma_l }$ together with the average times for grabbing, depositing and homing ${ \tau_G }$, ${ \tau_D }$ and ${ \tau_H }$. Clearly ${ \tau_R }$ and ${ \tau_S }$ are the design parameters we seek to optimize, while ${ \tau_A }$ is determined by the physical design of the robot and its sensors.

Figure 11

Foraging environment showing 8 robots labeled ${ A-H }$. The nest region is the grey circle with radius R _h at the center. Robot A is shown with its arc of vision in which it can sense food items; robots C, E and F have grabbed food items and are in the process of returning to the nest to deposit these. Food items, shown as small squares, ‘grow’ in order to maintain uniform density within the annular region between circles with radius R _inner and R _outer

Figure 12, from [42], plots the average number of robots, from both simulation and the mathematical model, in states searching, resting and homing for the swarm with ${ \tau_r=80 }$. The average number of robots in each state predicted by the probabilistic model quickly settles to a constant value. In contrast, but as one would expect, the average number of robots from simulation oscillates over time but stays near the value predicted by the model.

Figure 12

The number of robots in states searching, resting and homing for the swarm with ${ \tau_r=80 }$ seconds. The horizontal black dashed lines are predicted by the mathematical model; colored graphs show the instantaneous number of robots measured from simulation

Figure 13 compares the predicted value of net swarm energy from the mathematical model , with the measured value from simulation, for resting time parameter ${ \tau_r }$ increasing from 0 to 200s. The two curves show, firstly a good match between measured and predicted curves therefore validating the mathematical model and, secondly, that there is indeed an optimal value for ${ \tau_r }$ (at about 160 seconds). We thus have confirmation that a mathematical model can be used to analyze the effect of individual parameters on the overall performance of collective foraging.

Figure 13

The net energy of the swarm for different values of the resting time parameter ${ \tau_r }$. The black curve is the prediction of the mathematical model; the dashed curve with error bars is measured from simulation

Future Directions

This article has defined robot foraging, set out a taxonomy and described both the development and state‐of‐the‐art in robotforaging. Although the principles of robot foraging are well understood, the engineering realization of those principles remains a researchproblem. Consider multi‐robot cooperative robot foraging. Separate aspects have been thoroughly researched and demonstrated, and a number ofexemplars have been described in this article. However, to date there has been no demonstration of autonomous multi‐robot foraging which integratesself‐organized cooperative search, object manipulation and transport in unknown or unstructured real‐world environments. Sucha demonstration would be a precursor to a number of compelling real‐world applications including search and rescue , toxic wastecleanup or foraging for recycling of materials.

The future directions for foraging robots lie along two separate axes. One axis is the continuing investigation and discovery of foraging algorithms – especially those which seek to mimic biologically inspired principles of self‐organization. The other axis is the real‐worldapplication of foraging robots and it is here that many key challenges and future directions are to be found. Foraging robot teams are complex systems andthe key challenges are in systems integration and engineering, which would need to address:

• 1. Principled design and test methodologies for self‐organized multi‐robot foraging robot systems.

• 2. Rigorous methodologies and tools for the specification, analysis and modeling of multi‐robot foraging robot systems.

• 3. Agreed metrics and quantitative benchmarks to allow comparative evaluation of different approaches and systems.

• 4. Tools and methodologies for provable multi‐robot foraging stability, safety and dependability [23,68].