# Determining Minimal Cost of Action for Task Allocation Within Mobile Robot Swarm in Production Environments

Elmir Babović, Denis Mušić, Bahrudin Hrnjica, Adil Joldić

► To cite this version:

Elmir Babović, Denis Mušić, Bahrudin Hrnjica, Adil Joldić. Determining Minimal Cost of Action for Task Allocation Within Mobile Robot Swarm in Production Environments. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.64-70, 10.1007/978-3-030-85906-0_7. hal-04022122

HAL Id: hal-04022122

https://inria.hal.science/hal-04022122

Submitted on 9 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Determining Minimal Cost of Action for Task Allocation
Within Mobile Robot Swarm in Production
Environments

Elmir Babović¹, Denis Mušić¹, Bahrudin Hrnjica², Adil Joldić¹

¹ “Dzemal Bijedic” University, Faculty of Information Technologies, Bosnia and Herzegovina

² University of Bihać, Faculty of Technical Sciences, Bosnia and Herzegovina

¹{elmir.babovic}{denis}{adil}@edu.fit.ba

²{bahrudin.hrnjica}@unbi.ba

**Abstract.** This paper describes the continuation of a series of research in which human behavior, in the form of models and algorithms, endeavor to be mapped into the field of mobile robotics, all with the aim of more efficient path prediction with collision detection in a dynamic obstacle environment. In our latest research [1] we proposed a new approach called Sliding Holt (SH) algorithm which is used for calculation of future spatiotemporal state of dynamic obstacle. Besides SH algorithm we also proposed method for (non)collaborative collision detection with dynamic obstacles in 2D and 3D space which ensures full de-centralization of the collision detection process. Research described in this paper focuses on the application of Computer Vision for detecting the position and movement direction of mobile robots in order to create assumptions for collision detection and path planning with within the production environment. We propose a new approach for detecting mobile robot direction based on triangular shape and use of Cost of Action in order to allocate tasks within robotic swarm.

**Keywords:** mobile robots, robot swarm, computer vision, collision detection, path planning, robot direction, cost of action.

## 1 Introduction

Some of the most significant discoveries of today have been made by observing natural phenomena and movements. The mechanisms that exist in nature exude harmony and precision which, even after a long and detailed observation, is not easy to model or even to understand completely. As a proof, we can mention a human who represents the most intelligent and at the same time the most complex being on Earth. The complexity of the human body is nothing special until we try to replicate in another environment or context some of the actions that a human performs with such ease and superiority. The way people make movements, path prediction, avoid static and dynamic obstacles represent particularly interesting features for the field of robotics and have been subject of much research over past decades. In order to provide modest contribution to this area, our previous research [2, 4, 6, 8] focused on the analysis of human behavior which
resulted in creation of adequate mathematical models and algorithms applicable in the field of mobile robotics.

A new industrial era called the 4th industry generation is completely dependent on the interconnectedness of all participants in the process and implies an enviable degree of intelligence and collaboration. This implies a symbiosis of human and robotic work environment that is completely safe, optimized in terms of eliminating unnecessary movement and loss of time, and making adequate decisions in real time.

The application of different types of sensors is an industry standard which brings a significant degree of autonomy and efficiency, especially when it comes to robot movement. As discussed in [5] pick and place, as one of the basic operations in most robotic applications, whether in industrial setups or in service robotics domains, are not easy to implement when it comes to manipulating parts with high variability or in less structured environments. These kind of picking systems only exist at laboratory level and have not reached the market due to factors such as lack of efficiency, robustness and flexibility of currently available manipulation and perception technologies. In fact, the manipulation of goods is still a potential bottleneck to achieve efficiency in the industry and the logistic market.

Parts of the system that oversee production management and accompanying processes to perform tasks in the shortest possible time need to consider energy consumption which usually means choosing the shortest path.

The movement of robots in a production environment brings multiple challenges, and one of the most important relates to determining the priority of performing tasks within a swarm of robots. If the robots were in charge of moving objects within the production or storage space, one of the possible solutions could be to assign the task of moving to the robot that is closest to the given object in terms of location. In the mentioned context, usage of holonomic or non-holonomic robots significantly determine the approach to problem solving. Namely, most of today's experimental or production implementations of robot applications, whether robots are intended for indoor or outdoor use, such as a Dispatch product called "Carry" or Seegrid GP8 vision-guided pallet truck, etc., involve the use of non-holonomic types of mobile robots.

In the next section of the paper, previous research in this area will be presented, after which the application of Computer Vision for detecting the position and movement direction of mobile robots and task allocation based on Cost of Action will be described.

## 1.1 Previous Research

Models and algorithms for collision detection in a dynamic 2D and 3D environment have been proposed in several of our previous studies [1-4, 6]. We introduced the new method of collision detection with dynamic obstacles for mobile objects space based on mathematical model of spatiotemporal de-composition of recorded motion coordinates, their respective forecast prediction using statistical methods and re-composition of future path forming metamorphous hyperspace.

Method described in [6] involves several key steps: spatiotemporal decomposition, forecast prediction using statistical methods, re-composition in metamorphous
hyperspace. The inspiration for this work came from human cognitive activities ex-
cuted while single unit is moving in a group of other moving units and simultaneously
detecting and avoiding collision. In majority of cases, this collision detection and avoid-
ance is done by human objects naturally without prior high level cognitive activities
which lead us to the conclusion that this model is one of the most natural way of exe-
cuting these activities. Path detection of object is done in non-collaborative manner as
described in previous work 1. Main research hypothesis is that human behavior in col-
lision detection can be described by statistical mathematical model and that given
model can be expressed in form of algorithm and implemented in mobile robotics. In
order to achieve requested results base research was divided into four segments. Since
the proposed method considers two main operating modes: collaborative and non-col-
laborative, all model elements are analyzed from two different perspectives, as well as
their similarities and differences.

Due to resolve the issue of creating metamorphous hyperspace, we proposed new
approach called Sliding Holt algorithm [1] to calculate future spatiotemporal state of
dynamic obstacle. Within first experimental phase, single exponential smoothing did
not show satisfying results in extreme cases of dynamic obstacles with high coefficient
of agility (even with high sampling frequencies of 1KHz). Therefore, we implemented
double exponential smoothing with sliding motion coordinate records in which we pro-
pose discarding of old data before motion vector alteration occurs.

## 2 Computer Vision Based Location and Direction Detection

As discussed in [8] robots in the industrial sector have evolved from powerful, sta-
tionary machines into sophisticated, mobile platforms to address a broader range of
automation needs. Autonomous mobile robots utilize feedback from sensors to navigate
their environment. State of the art mobile robots has an envious level of intelligence
and are able to detect obstacles present on their path and recalculate a route around the
obstacle to get it to its destination. Nevertheless, the real environment brings with it a
multitude of cases that have not yet been adequately researched in terms of the existence
of models and / or algorithms for solving them.

Previous research [7] described universal experimental environment for algorithm
testing in the field of mobile robotics which is appropriate for tracking, collision detec-
tion and avoidance, and path planning. In order to provide precise positioning and di-
rection detection, we proposed two-color markers which are positioned on the top of
mobile robot. The initial experiment with single color marker showed low level motion
path stability in the sense that it was unclear in which direction mobile object is moving.
With the addition of second color marker, it became clear what is front and what is rear
of the object, thus enabling straightforward definition of motion vector direction.

Although the use of two-color markers gave satisfactory results, continued research
revealed some disadvantages. The main disadvantage relates to the need for fine tuning
of colors and the sensitivity of the detection process to the intensity of ambient light. In
order to eliminate the mentioned disadvantage, in this paper we proposed the
implementation of shape detection using a triangular marker of any color. Fig. 1. shows
the experimental environment in which the use of triangular markers was tested. The
figure illustrates a part of an application that uses the Computer Vision OpenCV library
to capture a video stream that will be processed and used to detect the location and
direction of the robots.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Picture from video stream with indicated triangular markers</figcaption></figure>

Processing an image from a video stream involves several stages that are described
within the following pseudocode.

listOfCountours = DetectCountours(stream)
foreach(contour in listOfCountours)
    if (contour == triangle)
        (shortestLine,frontPoint) = AnalyzeShape(triangle)
        contour.Tail.X =(shortestLine.Begin.X+shortestLine.End.X)/2
        contour.Tail.Y =(shortestLine.Begin.Y+shortestLine.End.Y)/2
        contour.Front.X = frontPoint.X
        contour.Front.Y = frontPoint.Y
        DrawLine (shortestLine, color : green)
        DrawLine (contour.Tail, contour.Front, color : red)
        listOfTriangles.Add(contour)

The first phase in processing involves the detection of all shapes followed by their
analysis. If the shape has a triangular form, then a more detailed analysis is performed,
within which the shortest side and its corresponding points are identified. The remain-
ing, third point is declared as the front point of the robot. Subsequently, the absolute
mean between the points on the shortest line is calculated, which determines their po-
sition on the X and Y axes, and it becomes the rear point. The mentioned calculations
created a precondition for plotting the location and orientation of the robots detected on
the stream as indicated on **Fig. 2**.

<figure><img src="image_4.png" /><figcaption>Fig. 2. Detection of robot’s position and direction</figcaption></figure>

By applying Computer Vision and defined processing phases, we can detect the lo-
cation and direction of all members of the robot swarm which have been identified in
the video stream. After detecting them, it is necessary to define a model for assigning
tasks (e.g., moving a certain object from one location to another) with maximum degree
of efficiency, which means determining the Cost of Action (CoA) for each of the de-
tected/available robots.

3 Cost of Action

Within this chapter, the result of initial research in the field of implementation of
more efficient distribution of tasks in a swarm of robots is presented. Namely, assigning
tasks to non-holonomic robots requires an analysis of several factors, not just the abso-
lute distance from its current position to the defined location (e.g., target). The autono-
mous movement of non-holonomic mobile robots will very often lead to a case in which
the task of moving a certain object will be assigned to a more distant robot. As shown
in **Fig. 3**, the robot r₁ is further away from the object (e.g., target) in relation to the robot
r₂ (i.e., d₁ > d₂) but the angle (i.e., β₁) between the shortest distance (i.e., d₁) to the
destination and the movement direction (i.e., md₁) of the robot r₁ is much smaller than
the angle between the shortest distance (i.e., d₂) to the destination and the movement
direction (i.e., md₂) of the robot r₂.

Considering the aforementioned, it can be concluded that a higher value of the angle
β will lead to a higher Cost of Action in terms of required energy (battery consumption),
time to execute the action (ignoring the need to wait to avoid collisions with static or dynamic obstacles), energy caused by friction, current state of motion etc.

<figure><img src="image_5.png" /><figcaption>Fig. 3. Parameters used to determine Cost of Action in task allocation process</figcaption></figure>

Analyzing the case in which the mobile robot has the possibility of free rotation (caster wheel or tracks), in order to calculate the CoA for the robot r to reach from the current to the target location, the following calculation was used:

$$CoA_r = \frac{d}{v} + \frac{\beta}{\omega} \qquad (1)$$

*CoA*<sub>r</sub> – Cost of Action that robot r needs to reach the target location

d – distance to target location

v – linear velocity

β – angle between orientation and target direction

ω – angle velocity

$$minCostOfAction = \min([CoA_{r1}, CoA_{r2}, ..., CoA_{rn}]) \qquad (2)$$

The current experimental environment is a special case of a general concept in which the CoA per unit of time for each mobile robot is identical. This implies that all robots within the production environment have identical technical characteristics meaning identical weight, battery life, vehicle frame, friction of the drive mechanism against the ground, etc. To assign a task, it is necessary to calculate CoA<sub>r</sub>, which, in this case, represents time to reach the target, for each unallocated/idle mobile robot. The task will
be assigned to the robot for which the lowest CoA value (minCostOfAction) was calculated. Taking into account the fact that the current research considered only time, in future research, a general case will be analyzed, which implies the existence of an unstructured environment with mobile robots of different technical performance.

## 4 Conclusion

Efficient management of production environments is a goal that is not easy to achieve. However, some of the basic prerequisites are certainly the interconnection between all participants in the production process, the application of autonomous robots that will coexist with humans within a secure work environment, maximum utilization of all resources and elimination of unnecessary actions or waiting. The movement of autonomous robots in a production facilitates the management of such environments, but it is also necessary to provide a systematic environment that will allow smooth movement and efficient assignment of tasks (e.g., moving a particular object from one location to another). In this paper, we have proposed a new approach for detecting the location and direction of a mobile robot, and calculation of Cost of Action in order to select the most appropriate robot for the task.

Future research will be focused on the introduction of new parameters such as: battery status, speed of the mobile robot (which refers to the energy needed to overcome inertia), the necessity to wait for certain actions (e.g., making turn or alter velocity) in order to avoid collisions etc.

## References

1. E. Babovic, D. Music, A. Joldic, S. Nogo: "Sliding Holt Algorithm Implementation in Mobile Robots Collision Detection with Dynamic Obstacles Based on Computer Vision Technologies", IEEE, 20th International Symposium INFOTEH-JAHORINA, Jahorina (2021).

2. Babovic, E.: Collaborative and Non-Collaborative Dynamic Path Prediction Algorithm for Mobile Agents Collision Detection with Dynamic Obstacles in a Two-dimensional Space, IEEM 2011, Singapore (2011).

3. Babovic, E.: Collaborative and Non-Collaborative Dynamic Path Prediction Algorithm for Mobile Agents Collision Detection with Dynamic Obstacles in 3D Space, CISSE2011, Bridgeport (2011)

4. Babovic, E.: Coefficient of Agility and Sampling Frequency issues in Mobile Agents Collision Detection with Dynamic Obstacles in 3D Space, AMC 2012, Sarajevo (2012).

5. Iriondo, Ander & Lazkano, Elena & Susperregi, Loreto & Urain, Julen & Fernandez, Ane & Molina, Jorge. Pick and Place Operations in Logistics Using a Mobile Manipulator Controlled with Deep Reinforcement Learning. Applied Sciences. 9. 348. 10.3390/app9020348. (2019).

6. Babovic, E.: New method and algorithm for Mobile Agents Collision Detection with Dynamic Obstacles in 3D Space, 4TH INTERNATIONAL CONGRES ON ULTRA MODERN TELECOMMUNICATIONS AND CONTROL SYSTEMS, ICUMT, pp.370-376. Sankt Petersburg (2012).
7. A. Joldic, E. Babovic, N. Bijedic and A. Bejenaru-Vrabie: "Laboratory Environment for Algorithms Testing in Mobile Robotics," 2019 IEEE 17TH INTERNATIONAL SYMPOSIUM ON INTELLIGENT SYSTEMS AND INFORMATICS, SISY, pp. 41-46, Subotica (2019)

8. Siegwart, Roland, Illah Reza Nourbakhsh, and Davide Scaramuzza: Introduction to autonomous mobile robots. MIT press, 2011.

9. Hrnjica B., Music D., Softic S.: Model-Based Recommender Systems. In: Al-Turjman F. (eds) Trends in Cloud-based IoT. EAI/Springer Innovations in Communication and Computing, Springer (2020)

10. Hrnjica B., Softic S.: Explainable AI in Manufacturing: A Predictive Maintenance Case Study. In: Lalic B., Majstorovic V., Marjanovic U., von Cieminski G., Romero D. (eds) Advances in Production Management Systems. Towards Smart and Digital Manufacturing. APMS 2020. IFIP Advances in Information and Communication Technology, vol 592. Springer