- This paper addresses the problem of foraging by a coordinated team of robots. This coordination is achieved by markers deposited by robots. In this paper, we present a novel decentralized behavioral model for multi robot foraging named cooperative c-marking agent model. In such model, each robot makes a decision according to the affluence of resource locations, either to spread information on a large scale in order to attract more agents or the opposite. Simulation results show that the proposed model outperforms the well-known c-marking agent model.
DIMES Via P. Bucci, cubo 41c 87036 - Rende (CS)
Italy g.fortino@unical.it
INTRODUCTION
Foraging is a benchmark problem for robotics, especially for multi-robot systems [1]. It is a “two-step repetitive process in which (1) robots search a designated region of space for certain objects, and (2) once found, these objects are brought to a goal region using some form of navigation” [2]. Distributed cooperative multi-robot systems are specifically adopted to achieve foraging missions when there is no a priori information about the environment, but communication mechanisms are needed for coordination. Pheromone deposits [3] is one of the approaches inspired from the study of the stigmergy process conducted in the early 90's on insect self-organized societies [4]. The foraging behavior of ants is an example of stigmergy where ants drop pheromones as they move in the environment. Most of studies in both artificial life and robotics carried out on synthetic pheromones use a large vocabularies linked to pheromone, coming from propagation and evaporation properties [5] [6]. These properties allow a group of agents to adapt to dynamic situations.
In this paper, we consider the problem of collective foraging in an unknown outdoor environment, with a homogeneous team of reactive agents that have no prior information about the environment. The objective is to retrieve and achieve all resource locations, while minimizing the time needed to complete the whole foraging. To this purpose, agents are based on a new behavioral model, where they can choose to
A wide range of approaches has been adopted to suggest
solutions to the foraging problem in unknown environments.
Most of them focus on examples of multi-robot foraging from
within the field of swarm robotics. The three main strategies
for cooperation in this field are: information sharing [8],
physical cooperation [9] [
An interesting approach named c-marking agents has been
proposed in [7] that allow reactive agents to build optimal
paths for foraging, which have limited information about their
environment. To keep track of found resource locations and to
build trails between them and the base, agents drop a quantity
of pheromones inside their environment. A first extension of
the c-marking agents model was proposed in [
III.
MODELING SYSTEM COMPONENTS
The different components of our reactive multi-agent system are: Environment, Pheromone and Agent (or Robot) models.
The environment is modeled as a squared grid with variable size that has resources in multiple locations. These locations are scattered randomly and are unknown by the agents. Each location has a given quantity of resources. Cells in the environment can:
Contain a resource (green color) of a limited quantity; Be the base station (red color), always positioned in the environment center, forming the starting point of all agents;
Contain an agent (blue color).
The pheromone is modeled as a piece that can be spread to the four neighboring cells, if the quantity of resources in a location is more or equal to a maximum reference quantity QRmax; or it is modeled as a static piece that takes effect just in the current cell, if the quantity of resources in a location is less than a minimum reference quantity QRmin. Pheromones are directly managed by agents.
Agents have limited information about their environment. Due to the pheromone model, agents directly manipulate real pieces and are then close to real robots. At each time step (or iteration), each agent can:
Move from a cell to another, which is not an obstacle in the four cardinal directions, like real robots. Perceive and read the values of the four neighboring cells. So agents can detect and load resources according to a maximum capacity Qmax.
Agents can read or write integer values that represent the Artificial Potential Field (APF) values [7], which represent the minimum distance between any cell and the base station cell. They are distributed to all agents, and can be modified to get the optimal values.
FINITE STATE MACHINE-BASED AGENT BEHAVIOR FOR
COLLECTIVE FORAGING
Figure 1 shows the finite state machine (FSM) diagram representing the behavior of an autonomous foraging robot (or agent). Such agent in its lifecycle goes through the following main states: 1) CLIMB; 2) LOAD; 3) DROP; 4) PICK_UP; 5) UNLOAD; and the following additional states: COLOR_MAX,
REMOVE_MIN. In all cases when the base station cell is reached, the agent executes the state UNLOAD and changes automatically to the CLIMB state when finished. The state details of the FSM, representing the proposed cooperative cmarking agents V2 model, are given below along with Algorithm 1 that provides further details.
Transitions: RF: Resource Found; RNE: Resource Not Exhausted; RE: Resource Exhausted; NT: No Trail exists; T: Trail exists; NRF : NoResource Found; Qres: Quantity of resources; QRmax: Maximum amount of resources; QRmin: Minimum amount of resources; BR: Base Reached.
CLIMB: it is the initial state for all agents, in which the highest priority task for an agent is to exploit a resource when it is detected or to climb a trail, by choosing a colored cell with max value of APF or finally to execute an exploration & APF construction [7].
LOAD: the agent in this state picks up a Qmax of resource. If the resource is exhausted, the agent goes to PICK_UP; otherwise it goes to DROP.
DROP: it is a transitory state towards one of the following four states (transitions are labeled by guards detailed in Figure 1):
COLOR_MAX: when the amount of resources is more than QRmax, agents drop diffusible pheromones; by such means, they create a max trail, within which colored cells with min values are not chosen in order to avoid common trails problem; COLOR_MIN: When the amount of resources is less than QRmin, agents drop non diffusible pheromones, so creating min trails. Colored cells with min values are not chosen in order to avoid common trails problem; REMOVE_MAX: if the amount of resources is equal to QRmin and there exists a max trail, agents remove such an amount; HOMING: if no trail exists and the resource is exhausted, agents just follow min values until the base is reached.
PICK_UP: it is a transitory state towards one of the following four states (transitions are labeled by guards detailed in Figure 1): DROP, COLOR_MAX, HOMING, and
REMOVE_MIN: it consists in removing the min trail in order to avoid attraction of agents to an exhausted resource.
UNLOAD: when the agent reaches the base station cell, it drops all resources and changes immediately its state to CLIMB.
CLIMB IF (Resource Found) goto LOAD ELSEIF (Trail Exists) Move to cell with highest value ELSE do exploration LOAD
Pick up Qmax IF (Resource Not Exhausted) goto DROP
ELSE goto PICK_UP DROP
IF (Qres> = QRmax & No Trail exists) goto COLOR_MAX ELSIF (Qres= QRmin & Trail exists) goto REMOVE_MAX ELSIF (Qres< QRmin & No Trail exists) goto COLOR_MIN ELSE goto HOMING PICK_UP
IF (Resource Found & No Trail exists) goto DROP ELSIF (No Resource Found & Trail exists)
goto REMOVE_MIN ELSE goto HOMING COLOR_MAX
IF (Base Reached) goto UNLOAD ELSE Move to a new neighboring, not colored cell with the least value; Color the current cell with dark gray color and the 4 neighboring cells with light gray color.
COLOR_MIN
IF (Base Reached) goto UNLOAD
ELSE REMOVE_MAX
IF (Base Reached) goto UNLOAD ELSE Move to a new neighboring, not colored cell with the least value; Color the current cell with dark gray color Move to a new neighboring colored cell with the least value; Reset the color of the 4 neighboring cells to the default color (white color); REMOVE_MIN
IF (Base Reached) goto UNLOAD ELSE IF (one colored cell exists in neighboring) Move to min colored cell in neighboring Reset the color to the default color (white color).
HOMING IF (Base Reached) goto UNLOAD ELSEIF (Trail Exists) Move to min colored cell in neighboring do update-value ELSE Move to min valued cell in neighboring do update-value UNLOAD Depose resources goto CLIMB exploration: IF (There exists a neighboring cell without value) Move randomly to such cell do update-value ELSE Move randomly to a free cell do update-value update-value: Write val = min (val, 1+ min (4 neighbor values)) in current cell
It is worth noting that the states CLIMB, HOMING and UNLOAD are the same as in [7]. Finally, the ELSE clause in the states COLOR_MAX, COLOR_MIN, REMOVE_MAX and REMOVE_MIN implies the return into the same state.
Two simulation scenarios have been defined by using the
JADE framework [
Scenario 1: The environment is composed of 40X40 cells with 30% obstacles; 20 cells are resources locations; each resource contains 1000 units of resources and each robot can load a maximum of 100 units. The number of robots is varying between 5-160 agents.
Scenario 2: The environment contains 5% obstacles; 20 cells are resource locations; each resource contains 2000 units of resources and the number of robots is 50. Each robot can carry a maximum of 100 units. The environment size varied from 12X12 to 100X100.
Table II show the simulation results of scenario 2; where the foraging time increases less by increasing the size of the environment, until 100X100, the foraging time increases dramatically.
We compared the proposed behavioral model (cooperative c-marking agent model V2) to the original c-marking agent model As one can see in Figure 2, increasing the level of cooperation between agents by the spread of a diffusible pheromones, allows agents to spend more time in exploitation rather than exploration, which means that resources will be exhausted rapidly and agents can spread out to exploration. When the quantity is less important, agents spread a nondiffusible pheromone that means that they did not need cooperation.
The preliminary results of scenario 2 in our previous work
(cooperative c-marking agents V1 model) [
CONCLUSION AND FUTURE WORK
In this paper, we proposed a new behavioral model for the foraging problem that aims to decrease the foraging time regarding the quantity of resources in locations. The new behavioral model based on resource affluence gives interesting results with respect to the original model (c-marking agent model). Agents in our system can perceive the environment, pick up resources, transport them to a storage point and manage the pheromone as a real piece, thus they are close to real robots. In perspective, we think that robot's behavior can be enhanced by introducing both new exploration approaches and solutions to problems such as the fast convergence of the Artificial Potential Field.