Open access peer-reviewed chapter

A Distributed Approach for Autonomous Cooperative Transportation

Written By

Amar Nath and Rajdeep Niyogi

Submitted: 11 December 2020 Reviewed: 05 May 2021 Published: 23 July 2021

DOI: 10.5772/intechopen.98270

From the Edited Volume

Robotics Software Design and Engineering

Edited by Alejandro Rafael Garcia Ramirez and Augusto Loureiro da Costa

Chapter metrics overview

289 Chapter Downloads

View Full Metrics

Abstract

Autonomous mobile robots have now emerged as a means of transportation in several applications, such as warehouse, factory, space, and deep-sea where direct human intervention is impossible or impractical. Since explicit communication provides a better and reliable way of multi-robot coordination compared to implicit communication, so it is preferred in critical missions, such as search and rescue, where efficient and continuous coordination between robots is required. Cooperative object transportation is needed when the object is either heavy or too large or needs extra care to handle (e.g., shifting a glass table) or has a complex shape, which makes it difficult for a single robot to transport. All group members need no participation in the physical act of transport; cooperation can still be achieved when some robots transport the object, and others are involved in, say, coordination and navigation along the desired trajectory and/or clear obstacles along the path. A distributed approach for autonomous cooperative transportation in a dynamic multi-robot environment is discussed.

Keywords

  • cooperative transportation
  • distributed algorithm
  • dynamic environment
  • multi-agent coordination and cooperation

1. Introduction

Autonomous mobile robots are now used in several applications, such as warehouse, factory, space, and deep-sea, that may be inaccessible for humans. The main concern is to find an effective coordination mechanism among autonomous agents to perform tasks in order to achieve high quality overall performance. Although MAS research has received substantial attention, multi-robot coordination remains a challenging problem since the overall performance of the system is directly affected by the quality of coordination and control among the robots while executing cooperative tasks. Coordination in a multi-robot system can be achieved either by explicit or by implicit communication. Since explicit communication provides a better and reliable way of multi-robot coordination compared to implicit communication, so it is preferred in critical missions, such as search and rescue, where efficient and continuous coordination between robots is required.

A collaborative task cannot be executed by any single agent. It requires multiple agents at the task’s location. Execution of such tasks is quite challenging in a dynamic environment, as the time and location of a task arrival, required skills, and the number of robots required for its execution may not be known a priori. This necessitates the design of a distributed algorithm for collaborative task execution via runtime team/coalition formation. To form a team with a lack of global knowledge, the robots need to communicate with each other to acquire relevant information. Here, a distributed approach for collaborative task execution in a dynamic environment is discussed. We illustrate the applicability of the approach with urban search and rescue (USAR) domain and evaluate its performance with extensive experiments using ARGoS, a realistic multi-robot simulator.

We now illustrate an example scenario of the problem considered as shown in Figure 1. The environment, a grid world of size 4×3, consists of 12 locations marked as a,b,,l. Robots can move to its adjacent location. Boxes arrive at the locations at different points in time. The task is to move a box from its arrival location to the goal location, which is marked on the box.

Figure 1.

Snapshots of a dynamic environment.

The snapshots of the environment at different instants of time is shown in Figure 1. At time t1, two tasks τ1 and τ2 arrive at locations a and g respectively, 4 robots are present at the locations b, c, f and h. The robots r1 and r4 detect the tasks τ1 and τ2 respectively. At time t2, r1 and r4 move to locations a and g to attend the tasks. Now, r1 and r4 determine the team sizes to be 2 and 3, and the goal locations to be h and l for the tasks τ1 and τ2 respectively. At this time, r3 exits and r5 and r6 enter at locations k and j respectively.

At t2, r1 and r4 do not know the states and locations of other robots present in the environment, and thus with this insufficient information they cannot form their respective teams. Thus, in order to form their teams, they invoke the algorithm given in Section 4. At t3, r1 and r4 both form their teams successfully and the members reach the locations of the tasks as shown in the Figure. Finally, at time t4, execution of the tasks are completed and the team members for τ1 and τ2 reach their respective goal locations.

Advertisement

2. Related work

In the literature, several approaches have been suggested for solving the problem of cooperative object transportation [1, 2, 3, 4]. The work [1] is considered as the pioneering work, targeting a cooperative transport task by a homogeneous group of simple robots that can only push an object. The authors [1] demonstrate that coordinated effort is not possible without explicit communication.

The work [2] proposed direct (explicit) communication to improve the coordination of a homogeneous group of two six-legged robots required to transport a rectangular box towards a target cooperatively. The work [3] considered the problem of cooperative box pushing where the roles of the members are pre-defined; specifically one robot acts as a watcher and the others act as pusher. However, we consider a more complex scenario of cooperative object transportation scenario, where the role of each robot is not fixed in advance, rather decided at runtime. In [4], the robots are designed to push the object across the portion of its surface, where it occludes the direct line of sight to the goal. This simple behavior results in transporting the object towards the goal without using any form of direct communication.

The problem of cooperative transportation, considered in this paper, involves team formation of heterogeneous robots and gathering the robots to the location of the object to be transported. The number of robots required to transport the object is not known a priori and it is decided at runtime. For the same task, the team size is determined by the state of the environment. So, at some point in time an object may be transported by two robots while at some other moment in time three or more robots are required. Few works related to coalition formation strategies are discussed below.

Auction-based approaches for team formation (task allocation) are suggested in [3, 5]. A bidder agent has some resources (e.g., data center, CPU) [5], who may bid for multiple auctioneers concurrently. However, when we move to physical agents, a robot cannot be a member of multiple coalitions at any point of time simply because the tasks may be at different locations, and a robot cannot be at two different locations at the same time, even though a robot may have the capability to perform multiple tasks at a time.

In our work, a non-initiator robot (bidder) will not express its willingness to multiple initiators (auctioneers) concurrently; when more than one request message arrives, the robot stores the requests in its local queue. Having one or more resources specified in the auction is a sufficient condition for an agent to make a bid [5]. Having the required skills for a task is a necessary but not a sufficient condition for a robot to express its willingness to be part of a team, in our work. A robot’s behavior, in our work, is determined by its current state, whereas in [3, 5] states need not be taken into consideration.

In [6], the authors describe a framework for dynamic heterogeneous team formation for robotic urban search and rescue. The task discovery is made by a member of a team and it is sent to the team coordinator for assignment. The team coordinator performs the task assignment ensuring the task will be carried out by a robot with the necessary capabilities. However, in a distributed system, no robot knows the states, locations, and skills of other robots. Thus, the robots should communicate among themselves to acquire relevant information for task execution without the intervention of any central authority. This necessitates the design of a distributed algorithm for task execution in such a dynamic environment.

In our approach, unlike [6], every robot has a similar level of priority, and each of them can perform the task management activities, i.e., searching, team/coalition formation by acquiring the information from the robots available in the environment at that moment in time. In this paper, the arrival time and location of a task are not known a priori; hence, task searching and coalition formation activities are performed by a robot at runtime.

Advertisement

3. Problem formalization

A formal framework of a dynamic environment and some related concepts are presented below.

Definition 3.1. (Dynamic environment) A global view (snapshot) of an environment E, with a set of locations L, taken at time t, is given by a 3-tuple Et=RtTtf, where Rt is the set of robots present in the environment at time t, and Tt is the set of tasks that arrive in the environment at time t, f:Rt×NL, is a function that gives the location of a robot at a discrete instant of time represented by the set of natural numbers N.

A robot has a set of skills ψ (eg., gripper, camera), and at any instant of time it may be in any state from the set of states S=IdleReadyPromiseBusy. A robot can enter the environment E at any time, but can leave only if its state is Idle. When a robot attends a task, it can determine the information required to begin team formation, from the task specification, which is given below.

Definition 3.2. (Task (cooperative transportation)) A task τ is specified by a 5-tuple τ=νltkΨ where ν is the name of a task (e.g., move (carry) box B to location l, lift desk d), lL is the location where the task arrived, t is the time at which the task arrived, k>1 is the number of robots required to execute the task, and Ψ is the set of skills required to execute the task.

Definition 3.3. (Condition for single task execution) A task τ=νltkΨ can be executed, if there exists a set R of k available robots, such that for all rR, ψrΨ at some time t>t, and for all rR, location of r, locr=l at some time t>t.

The first condition in the if is for team formation, and the second condition is for ensuring that all the team members converge to the location of the task.

Definition 3.4. (Condition for multiple task execution) The tasks τ1=ν1l1tk1Ψ1 and τ2=ν2l2tk2Ψ2 can be executed if the following conditions hold:

  1. there exists a set R1 of k1 available robots, such that for all rR1, ψrΨ1 at some time t1>t, and for all rR1, locr=l1 at some time t1>t1.

  2. there exists a set R2 of k2 available robots, such that for all rR2, ψrΨ2 at some time t2>t, and for all rR2, locr=l2 at some time t2>t2.

  3. R1R2=.

Definition 3.5. (Utility of a team for task execution) Let Γ=x1xk be a team that can execute a task τ=νltkΨ where each member of the team was located at locxi. The utility of a team Γ for executing τ is UΓτ=costΓτ, where costΓτ=xiΓμxiτ and μxiτ=pxiτ×1αxi+dlocxil×βxi.

where αxi,βxi01 denote remaining battery coefficient and battery consumption rate respectively of (a robot) xi, pxiτ is the price of xi for τ, dl1l2 is the distance covered when moving from l1 to l2.

A robot with higher α value ensures that it will not fail due to its more remaining battery backup. A robot with lower β value ensures that it will last for a longer period of time.

Advertisement

4. Distributed algorithm for cooperative transportation

Following assumptions are made for the study. Multiple robots are required for any task execution. A robot can execute at most one task at a time. Each robot has a unique identifier (id). A wireless network that is lossless, message delay is finite, data is not corrupted during transmission is considered. Messages are delivered in a FIFO manner.

Informal description of the algorithm is given below. Let a robot i attend a task τ=νltkΨ where ψiτ.Ψ. To execute the task (cooperative transportation), initiator communicates with other robots in order to form a runtime team. Here, the i is named as an initiator, and the other robots as non-initiators.

After task detection, i broadcasts a Request message to know the current state of the other robots present in the environment at that moment in time and waits for some time, say Δ. The broadcast messages are delivered only to those robots who are present in the range. Now, on receipt of Request message, a non-initiator j takes the necessary actions. A non-initiator who has the desired skill will send a Willing and an Engaged message if its state is other then Idle.

The counter c of initiator is increased on receipt of Willing message. The parameter (ck1) is checked after Δ time has elapsed. Now, if the value of (ck1) is true then team formation that has maximum utility is possible and sends Confirm message to the members of the team and sends a Not-Required message to (ck1) robots, if any. However, if the value of the condition (ck1) is false, i sends a Not-Required message to all c robots who expressed their willingness to help. Also, i changes its state from state Ready to Idle The algorithm has the non-blocking property since a timer is used. If there was no timer, an initiator would have waited indefinitely and thereby forcing some non-initiators to wait indefinitely as well; thus the system would be blocked.

The receive function of a robot is given in Algorithm 2. The agents take the action based on the current state that may be Idle (line 17–21), Promise (line 22–39), Busy (line 12–16 and 41–45), and Ready (line 1–11). Within a state, the type of message is checked and appropriate actions are taken. For example, if an agent receives a Request message in Idle, the identifier of the sender is enqueued, and flag is set to true; if it has appropriate skills then it sends the Willing message to the sender (initiator) and flag is set to false.

The behavior of the agent is captured with communicating automata (CA) [7] as shown in Figures 2 and 3. Moreover, this communicating automata is helpful in understanding and designing the algorithm.

Figure 2.

Finite state machine for an initiator agent.

Figure 3.

Finite state machine for a non-initiator agent.

Transitions in CA are very general form χ:γ, where χ can either be an input a (send message !m, receive message ?m), or a state condition g, or ag, and γ can either be a sequence of actions seq, or a sequence of actions that is to be performed atomically seq, or empty. Similarly, semantics are defined.

4.1 Analysis of the algorithm

4.1.1 Message complexity

Let there be I initiators at some instant of time, say t. Each initiator broadcasts a Request message, which is sent to N1 robots, where N is the total number of robots present at time t. So, the total number of such messages would be N1I which is ONI. The total number of replies obtained from non-initiators would be at most N1I which is ONI. An initiator sends c number of Confirm and Not-Required messages, which is ON. Thus total messages send by all the initiators would be ONI. Thus the total number of messages would be the sum of these messages, and this becomes ONI+ONI+ONI, which is ONI. When the number of initiators is relatively small compared to the total number of robots present at time t, the message complexity would be ON.

4.1.2 Handling multiple initiators

Let us consider the snapshot of the environment at t2 in Figure 1, where r1,r4 invoke the send function (Algorithm 1) simultaneously; r1,r4 need one, two other robots respectively. The initiators r1,r4 broadcast Request messages corresponding to their respective tasks. Let all the other robots be in Idle state initially and they can satisfy the requirements of both the tasks. Eventually r2 becomes part of the team with r1 because it received the Request message from r1 before it received the Request message from r4. Similarly, eventually r5 and r6 become part of the team with r4.

The complete execution trace of algorithms 1,2 is shown in Figure 4 using message sequence chart (MSC).

Figure 4.

Execution trace of the algorithms for multiple initiators.

Advertisement

5. Implementation in ARGoS

We consider a road clearance scenario to illustrate the proposed distributed algorithm (Section 4), where a road may be blocked by several obstacles. A team of robots should jointly move each obstacle to one side of the road. The algorithm is implemented using ARGoS (Autonomous Robots Go Swarming) [8], a multirobot simulator using the 3.0.0-beta47 version on Intel Core™ i5 Processor, 4-GB of RAM and macOS Sierra operating system. The code run in ARGoS can be directly deployed on a real robot system.

An example scenario is shown in Figure 5, where the shaded portion in gray is the road (10 m × 5 m), obstacles are simulated by green movable cylinders of radius 0.2 m with a blue light on top. The robots are shown in blue. The overall process of removing an obstacle from the road is shown in Figure 5. The robots in ARGoS use the inbuilt range and bearing sensor (rab) to communicate among themselves.

Figure 5.

Illustration of multiple task execution in ARGoS.

The broadcast of the messages to all other robots is done by rab actuator. The broadcast of message is done within a certain range and in line of sight. We have used the 3 bytes for message within the range of 15 meters. The message is received by rab receiver within in the same network sent by rab sensors. Along with sending and receiving the message within range, rab sensors do the work of identifying the direction and distance from where the message is being sent. As the rab actuator allows the only broadcast, the address of the sender and that of the receiver needs to be specified in every message. Every robot in the simulation has a unique id of size 1 byte. Several sensors and actuators are used to control the movement and positioning of the robots. For example, proximity sensors are used to stay on the road and avoiding collisions with other robots, the omni-directional sensor is used to detect obstacles, gripper actuator is used to grip an obstacle, and turret actuator is used to turn the gripper actuator towards the direction of the obstacle.

In Figure 5a, the initial position of the robots and blocks is shown. Three robots detect the three obstacles and they start the formation for the same is shown in Figure 5b. We assume that all the obstacles require two robots to move. In Figure 5c, two initiator robots are able to form their teams. In Figure 5d, it is depicted that robots have reached to the location of obstacles and they are ready to move the obstacles. Figure 5e, clearly shows that both the obstacles have been shifted to one side of the road. After dropping the obstacles, the robots again visit the road and search for other obstacles if any. Finally, in Figure 5f, the third obstacle is also detected and removed. In this way, all the obstacles are removed from the road.

For the implementation we have written the required functions in Lua (a C-like language). These are: (i) to control the movement of a robot to avoid obstacle or another robot based on proximity sensor data, where the sensor detects an obstacle or another robot, (ii) control speed and velocity, (iii) synchronizing the robots for task execution, (iv) to control the movement of a robot when boundaries are detected using motor-ground sensors, (v) communication among robots based on the line of sight.

The implementation is carried out by writing the required function in Lua language. The different functions that are identified are as follows: (i) control of velocity and speed of the robot, (ii) control the movement of a robot so that obstacles and other robots could be avoided, (iii) synchronizing the robots in order to task execution, and (iv) communication among robots based on the line of sight.

Advertisement

6. Summary

Now, research in the field of robotics is going with a rapid rate. In many applications such as search and rescue, space, and automated warehouse, intelligent robots are being used. With the advancement of artificial intelligence domain, robots are becoming the good choice. A plenty of work has been carried out in the field of single robot. However, this chapter discuss the different aspects of work where multiple robots act on the same object at the same time. This problem becomes tough and different from normal multi-agent problem.

Cooperative transportation is common task in many challenging domains, i.e., rescue, mars and space, and autonomous warehouse etc. In this way the proposed framework becomes very much essential and important in such domains where multiple robots are required to execute a task.

The proposed approach also takes care of multiple task execution simultaneously, i.e., if multiple robots detect multiple different obstacles at the same time, the coalition formation process for each obstacle can be started. Each robot who detects the obstacle, starts the coalition formation, by executing the instance of the algorithms.

References

  1. 1. Kube, C. R., & Zhang, H. (1993). Collective robotics: From social insects to robots. Adaptive behavior, 2(2), 189-218
  2. 2. Mataric, M. J., Nilsson, M., & Simsarin, K. T. (1995, August). Cooperative multi-robot box-pushing. In Proceedings 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems. Human Robot Interaction and Cooperative Robots, Vol. 3, pp. 556-561
  3. 3. Gerkey, B. P., & Mataric, M. J. (2002). Sold!: Auction methods for multirobot coordination. IEEE transactions on robotics and automation, 18(5), 758-768
  4. 4. Chen, J., Gauci, M., Li, W., Kolling, A., & Gro, R. (2015). Occlusion-based cooperative transport with a swarm of miniature mobile robots. IEEE Transactions on Robotics, 31(2), 307-321
  5. 5. Kong, Y., Zhang, M., & Ye, D. (2016). An auction-based approach for group task allocation in an open network environment. The Computer Journal, 59(3), 403-422
  6. 6. Gunn, T., & Anderson, J. (2015). Dynamic heterogeneous team formation for robotic urban search and rescue. Journal of Computer and System Sciences, 81(3), 553-567
  7. 7. Brard, B., Bidoit, M., Finkel, A., Laroussinie, F., Petit, A., Petrucci, L., & Schnoebelen, P. (2013). Systems and software verification: model-checking techniques and tools. Springer Science & Business Media
  8. 8. Pinciroli, C., Trianni, V., OGrady, R., Pini, G., Brutschy, A., Brambilla, M., Dorigo, M. (2012). ARGoS: a modular, parallel, multi-engine simulator for multi-robot systems. Swarm intelligence, 6(4), 271-295

Written By

Amar Nath and Rajdeep Niyogi

Submitted: 11 December 2020 Reviewed: 05 May 2021 Published: 23 July 2021