Open access peer-reviewed chapter

A Distributed Approach for Autonomous Cooperative Transportation

By Amar Nath and Rajdeep Niyogi

Submitted: December 11th 2020Reviewed: May 5th 2021Published: July 23rd 2021

DOI: 10.5772/intechopen.98270

Downloaded: 68

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 τ1and τ2arrive at locations aand grespectively, 4 robots are present at the locations b, c, fand h. The robots r1and r4detect the tasks τ1and τ2respectively. At time t2, r1and r4move to locations aand gto attend the tasks. Now, r1and r4determine the team sizes to be 2 and 3, and the goal locations to be hand lfor the tasks τ1and τ2respectively. At this time, r3exits and r5and r6enter at locations kand jrespectively.

At t2, r1and r4do 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, r1and r4both 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 τ1and τ2reach 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 Rtis the set of robots present in the environment at time t, and Ttis 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 Eat 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), lLis the location where the task arrived, tis the time at which the task arrived, k>1is 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 Rof kavailable robots, such that for all rR, ψrΨat some time t>t, and for all rR, location of r, locr=lat some time t>t.

The first condition in the ifis 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Ψ1and τ2=ν2l2tk2Ψ2can be executed if the following conditions hold:

  1. there exists a set R1of k1available robots, such that for all rR1, ψrΨ1at some time t1>t, and for all rR1, locr=l1at some time t1>t1.

  2. there exists a set R2of k2available robots, such that for all rR2, ψrΨ2at some time t2>t, and for all rR2, locr=l2at some time t2>t2.

  3. R1R2=.

Definition 3.5. (Utility of a team for task execution) Let Γ=x1xkbe 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,βxi01denote remaining battery coefficient and battery consumption rate respectively of (a robot) xi, pxiτis the price of xifor τ, dl1l2is the distance covered when moving from l1to 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 iattend 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 iis named as an initiator, and the other robots as non-initiators.

After task detection, ibroadcasts a Requestmessage 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 Requestmessage, a non-initiator jtakes the necessary actions. A non-initiator who has the desired skill will send a Willingand an Engagedmessage if its state is other then Idle.

The counter cof initiator is increased on receipt of Willingmessage. 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 Confirmmessage to the members of the team and sends a Not-Requiredmessage to (ck1) robots, if any. However, if the value of the condition (ck1) is false, isends a Not-Requiredmessage to all crobots who expressed their willingness to help. Also, ichanges its state from state Readyto IdleThe 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 receivefunction 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 Requestmessage in Idle, the identifier of the sender is enqueued, and flagis set to true; if it has appropriate skills then it sends the Willingmessage to the sender (initiator) and flagis 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 Iinitiators at some instant of time, say t. Each initiator broadcasts a Requestmessage, which is sent to N1robots, where Nis the total number of robots present at time t. So, the total number of such messages would be N1Iwhich is ONI. The total number of replies obtained from non-initiators would be at most N1Iwhich is ONI. An initiator sends cnumber of Confirmand Not-Requiredmessages, 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 t2in Figure 1, where r1,r4invoke the sendfunction (Algorithm 1) simultaneously; r1,r4need one, two other robots respectively. The initiators r1,r4broadcast Requestmessages corresponding to their respective tasks. Let all the other robots be in Idlestate initially and they can satisfy the requirements of both the tasks. Eventually r2becomes part of the team with r1because it received the Requestmessage from r1before it received the Requestmessage from r4. Similarly, eventually r5and r6become 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 IntelCore™ 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 rabactuator. 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 rabreceiver within in the same network sent by rabsensors. Along with sending and receiving the message within range, rabsensors do the work of identifying the direction and distance from where the message is being sent. As the rabactuator 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.

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Amar Nath and Rajdeep Niyogi (July 23rd 2021). A Distributed Approach for Autonomous Cooperative Transportation, Robotics Software Design and Engineering, Alejandro Rafael Garcia Ramirez and Augusto Loureiro da Costa, IntechOpen, DOI: 10.5772/intechopen.98270. Available from:

chapter statistics

68total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Interaction Protocols for Multi-Robot Systems in Industry 4.0

By Edi Moreira M. de Araujo, Augusto Loureiro da Costa and Alejandro R.G. Ramirez

Related Book

First chapter

Introductory Chapter: The Role of Assistive Technologies in Smart Cities

By Marion Hersh, Marcelo Gitirana Gomes Ferreira and Alejandro Rafael Garcia Ramirez

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us