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.
- cooperative transportation
- distributed algorithm
- dynamic environment
- multi-agent coordination and cooperation
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 , consists of 12 locations marked as . 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.
The snapshots of the environment at different instants of time is shown in Figure 1. At time , two tasks and arrive at locations and respectively, 4 robots are present at the locations , , and . The robots and detect the tasks and respectively. At time , and move to locations and to attend the tasks. Now, and determine the team sizes to be 2 and 3, and the goal locations to be and for the tasks and respectively. At this time, exits and and enter at locations and respectively.
At , and 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 , and both form their teams successfully and the members reach the locations of the tasks as shown in the Figure. Finally, at time , execution of the tasks are completed and the team members for and reach their respective goal locations.
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  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  demonstrate that coordinated effort is not possible without explicit communication.
The work  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  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 , 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) , 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 . 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 , 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 , 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.
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 , with a set of locations , taken at time , is given by a 3-tuple , where is the set of robots present in the environment at time , and is the set of tasks that arrive in the environment at time , , is a function that gives the location of a robot at a discrete instant of time represented by the set of natural numbers .
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 . A robot can enter the environment at any time, but can leave only if its state is . 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 where is the name of a task (e.g., move (carry) box B to location , lift desk d), is the location where the task arrived, is the time at which the task arrived, 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 can be executed, if there exists a set of available robots, such that for all , at some time , and for all , location of , at some time .
The first condition in the
Definition 3.4. (Condition for multiple task execution) The tasks and can be executed if the following conditions hold:
there exists a set of available robots, such that for all , at some time , and for all , at some time .
there exists a set of available robots, such that for all , at some time , and for all , at some time .
Definition 3.5. (Utility of a team for task execution) Let be a team that can execute a task where each member of the team was located at . The utility of a team for executing is , where and .
where denote remaining battery coefficient and battery consumption rate respectively of (a robot) , is the price of for , is the distance covered when moving from to .
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.
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 attend a task where . To execute the task (cooperative transportation), initiator communicates with other robots in order to form a runtime team. Here, the is named as an initiator, and the other robots as non-initiators.
After task detection, broadcasts a 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 message, a non-initiator takes the necessary actions. A non-initiator who has the desired skill will send a and an message if its state is other then .
The counter of initiator is increased on receipt of message. The parameter () is checked after time has elapsed. Now, if the value of () is true then team formation that has maximum utility is possible and sends
Transitions in CA are very general form , where can either be an input (send message , receive message ), or a state condition , or , and can either be a sequence of actions , or a sequence of actions that is to be performed atomically , or empty. Similarly, semantics are defined.
4.1 Analysis of the algorithm
4.1.1 Message complexity
Let there be initiators at some instant of time, say . Each initiator broadcasts a message, which is sent to robots, where is the total number of robots present at time . So, the total number of such messages would be which is . The total number of replies obtained from non-initiators would be at most which is . An initiator sends number of and
4.1.2 Handling multiple initiators
Let us consider the snapshot of the environment at in Figure 1, where invoke the function (Algorithm 1) simultaneously; need one, two other robots respectively. The initiators broadcast messages corresponding to their respective tasks. Let all the other robots be in state initially and they can satisfy the requirements of both the tasks. Eventually becomes part of the team with because it received the message from before it received the message from . Similarly, eventually and become part of the team with .
The complete execution trace of algorithms 1,2 is shown in Figure 4 using message sequence chart (MSC).
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) , 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 () to communicate among themselves.
The broadcast of the messages to all other robots is done by 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 receiver within in the same network sent by sensors. Along with sending and receiving the message within range, sensors do the work of identifying the direction and distance from where the message is being sent. As the 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.
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.