Estimation of robot execution time for close proximity human-robot collaboration

Abstract

Task time is essential information for the optimal planning and scheduling of industrial scenarios, such as assembly cells. In Human-Robot Collaboration (HRC), the robot execution time, i.e. the robot task time, depends on the task the human is executing simultaneously to the robot and on the human movements. Indeed, the robot may be requested to modify its speed along a predefined path (i.e. to slow down or to stop its motion) in order to avoid possible collisions with the human. This paper presents an approach for the estimation of the robot execution time, when the robot path and the human task are assigned. Specifically, a workspace segmentation is performed considering the volume occupied by the human and the robot during their motion. Then, this segmentation is exploited for the definition of a set of Markov chains modeling human-robot interaction and allowing the estimation of the robot execution time. Simulated and real test beds are presented and discussed.

Keywords

Robotics human-robot cooperation motion planning

1. Introduction

Collaborative robots are currently used in assembly and disassembly, pick&place, and sorting lines as human companions and helpers, making the human and a robot a team [1, 2]. In such a context, human’s and robot behaviors are strictly coupled. Indeed, the way in which the robot trajectory is designed may influence human comfort and ergonomics, whilst the way in which the worker moves may affect the robot trajectory, i.e. it may be necessary to stop or to slow down the robot in order to grant human safety.

This coupling has a relevant impact on task planning and scheduling (P&S) activities, that are not generally able to reason on uncertain robot execution times and changing human behaviours [3]. Indeed, currently available task planning approaches (hierarchical [4, 5] or integrated [6, 7]) only reason on the robot trajectory at spatial level, i.e. on the geometrical feasibly of the robot trajectory and of the plan, disregarding (i) changes in the human behaviour due to the robot presence and (ii) the influence that the variability generated by the human presence on the robot execution time may have on the whole plan.

If the influence of robot behavior on the human has been widely studied in the last decade [8, 9], the dependence of the robot trajectory and of the robot execution time on the human behavior seems to be quite unexplored and solutions neither at a research stage nor at industrial level can be identified.

From the industrial point of view, Catia Delmia [10] and Tecnomatix Siemens [11] provide human modeling tools for the digitalization of human beings and their inclusion into a virtual environment for the analysis of safety and ergonomics issues [12]; SIMATIC Siemens is ideal for task planning and scheduling (P&S) in highly automated systems, even if it does not provide algorithms and solutions for the P&S of tasks also involving human operators; Industrial Path Solutions [13] provides some modules for the automatic generation of robot paths with limitations to the impact of the motion planning on human perception and cognition as well as on the achievable production cycle time. Thus, even if the computer-aided technology market is proposing a set of solutions for the design and planning of human-robot collaborative (HRC) tasks [14, 15] commercial software tools seem far away from being able to address the evaluation of the robot execution time in HRC tasks.

Similarly, in scientific literature, a limited number of approaches are able to provide an estimation of the robot execution time [16] and few tools for P&S of industrial tasks deal with time-uncertainty in task duration [17, 18] and resources that may not respect time-constraints during execution phase, like humans [19, 20].

The aim of this paper is to describe a new approach for the estimation of the robot execution time, when the human and the robot share the workspace. Specifically, the developed method is able to off-line provide an estimation of the robot execution time, given the robot trajectory and the simultaneous human task (i.e. the human’s gestures). It is suitable for industrial applications characterized by repetitive movements of the human workers, such as assembly lines, logistics, quality inspection, etc. It has the longterm goal to be the core for a new generation of P&S computer-aided tools able to optimally manage the effects of the human presence on the system performance.

This paper is an extension of [16] in terms of the method developed for the estimation of the robot execution time. Indeed, differently from [16], a set of Markov chains is built to better formalize HRC tasks and the worker impact on the robot execution time.

The paper is structured as follows: Section 2 and Section 3 give an analysis of the state of the art and of the contributions of this paper to literature advances; Section 4 is an overview and a formalization of the problem; Section 5 describes the method and the developed algorithms; Section 6 contains the description of the experiments, the results and the discussion. Finally, in Section 7, conclusions are presented together with possible directions for future work.

2. Literature review

Human satisfaction and perceived safety and comfort strictly depend on the ability of the robot to adapt its motion [21]. Arai et al. [22] studied the relevance of the robot speed with respect to the robot acceptability by the human. In [23], the mutual influence of the human-robot team was analyzed, thus taking into account human adaptation to changes in robot trajectories.

Extending the aim of these papers, a large part of the literature focused on how to generate robot trajectories [24] for HRC tasks. Dragan et al. [25] introduced the concepts of legibility and predicibility, i.e. the correct identification of the final goal of the robot on the basis of its initial trajectory – action to goal – and the expectancy of the human on the robot followed trajectory – goal to action. They proposed an approach for the generation of robot trajectories coping with these criteria. Mainprice et al. [26] worked on the automatic generation of robot paths when the robot has to hand an object over to the human. They proposed the generation of a three-dimensional map representing human’s visibility, human’s arm comfort and human-robot distance. A robot trajectory is planned on the basis of this map with the idea that the robot has to stay as visible as possible, as far as possible and that the goal has to be in a comfortable position to be reached by the human. Possible collisions between human and robot are not considered since human’s movements are not supposed to be simultaneous to robot movements, i.e. the human will grab the object after the robot has placed it, avoiding simultaneous motion. In other words, the robot and human actions are synchronized, i.e. the human determines the cycle time of the robot and the cycle time of the collaborative task. Mainprice et al. [27] formalize human adaptation strategies to plan the optimized motion of the robot. Another approach based on the generation of maps was presented by Pandey and Alami [28]. These maps, called “Mightability Maps”, aim at facilitating the communication between the robot and the human partner. The method is based on the construction of two maps representing human and robot perceived reachability and visibility.

Several approaches are based on the analysis of the human motion and the generation of robot trajectories according to the predicted human’s intention. Human’s intention can be addressed as the goal towards which the human is going as well as the movements that the human will probably use to approach a goal (known or unknown). Mainprice et al. [29] proposed an approach where human motion is predicted and integrated into a robot motion planning framework. The approach concerns human-robot unsynchronized tasks in which the human and the robot perform their tasks on different goals in a shared workspace. The movements of the worker’s arm are categorized through the use of Gaussian Mixture Models (GMMs) and Regression (GMR). During task execution, the category that best fits the real movements of the human is selected and used as a predictor of the human movements. Lasota et al. [30] used a Markov Decision Process (MDP), where human actions are modeled as stochastic transition functions influencing robot actions and states. The approach, valid for unsynchronized tasks, was proved to increase human comfort and concurrent motion. This was then further studied in [31], where a HRC framework was developed based on the ability of the robot to avoid portions of the shared workspace that the human is expected to occupy. Also Mcghan et al. [32] adopted a MDP to model unsynchronized but independent HRC tasks (i.e. the human and the robot have to work on different pre-allocated tasks sharing the workspace). They used two MDPs: the first MDP is used to predict the human’s behavior, the second MDP is used to determine the robot action. Nikolaidis et al. [23] proposed a mixed observability Markov decision process to learn user models from joint-action demonstrations and to exploit these models to predict user types and to plan a robot anticipatory action. In [33, 34], the best robot action is determined by a Partially Observable Markov Decision Process (POMDP), whose belief state is related to human’s intention. It was tested on a real case where the human has few tasks to choose among, thus showing limited applicability. Finally, Pellegrinelli et al. [35] introduced a framework for human-robot workspace sharing (unsynchronized tasks) based on hindsight optimization. The approach defines a distribution probability on human’s goal based on the movements of the human’s hand. This distribution probability is used by a POMDP to define the belief state of the robot and to select the best robot action (i.e. twist). This approach was compared via several experiments with existing approaches showing its ability to increase the minimum distance between the human and the robot. An extended review of human-aware motion planning approches can be found in [36].

All the described approaches for synchronized or unsynchronized HRC tasks present limited applicabil- ity to real industrial contexts due to the impossibility to estimate the robot execution time. Indeed, for all the considered approaches based on the continuous defini- tion of robot actions or the continuous replanning of robot paths according to human’s intention or maps, it is hard to be aware of the time required by the robot to execute the assigned task.

3. Objectives

This paper aims at providing a new off-line method for the estimation of the robot execution time when the robot is influenced by the presence of a worker and by the worker’s task and movements, i.e. the robot has to modify its trajectory in order to avoid possible collisions with the worker. Specifically, the approach will be able to provide an estimation of the robot execution time in all those industrial scenarios characterized by human-robot repetitive tasks, such as assembly lines, which may benefit from HRC in terms of physical proximity between the human and the robot. This estimation may lead to the achievement of more accurate results in task planning and scheduling, thus possibly increasing the system throughput.

4. Problem statement and formalization

It is possible to denote $\mathcal{U}^{h}:=\left\{u^{h}_{i},i=1\ldots,n^{h}\right\}$ and $\mathcal{U}^{r}:=\left\{u^{r}_{j},j=1,\ldots,n^{r}\right\}$ realistically as the set of human and robot tasks respectively and to define the list of all the feasible couples of tasks $\left(u^{h}_{i},u^{r}_{j}\right)$ , i.e. all the couples of tasks that may happen simultaneously and cope with possible constraints. Furthermore, three assumptions that rely on the industrial practice are introduced.

(Time variability).

The start and end time of the human and robot tasks may be uncorrelated for each considered feasible couple $\left(u^{h}_{i},u^{r}_{j}\right)$ .

The human and the robot often just share the workspace and, even if the tasks are functionally related, the start time of the human task may display a large time variability with respect to the robot task. As a general remark, only few applications display a hard synchronization of the robot and human execution times, e.g. when the tasks are serialized (e.g. hand over).

(Safety through Speed Variation Monitoring).

Considering a feasible couple of tasks $(u^{h}_{i},u^{r}_{j})$ , the robot may modify the speed (up to hold the movement), when necessary, remaining on the nominal path to preserve human safety conditions.

Speed and Separation Monitoring (SSM, ISO/TS 15066) is the most common and robust safe collision avoidance method used in industrial scenarios [37, 38]. It consists in the on-line management of the robot speed along a predetermined path to avoid collisions with the human. Several factors are considered to decide about the robot speed: the robot position, the human position, the robot current speed and direction, the human current speed and direction, possible delays/errors in the system communications. SSM is more suitable than on-line re-planning of the robot path (i.e. on-line modification of the geometric curve in the workspace) due to its straightforward integration with industrial controllers, and to its simplicity compared to the on-line re-planning of the path, which requires to take into account the potential collisions of the robot with the environment.

(Human Imperturbability).

Robot trajectories are planned maximizing human comfort, so that the movements of expert workers (i.e. workers that are used to operate with a robot) are not affected by the robot motion.

Specifically, it is assumed that skilled workers move similarly both with and without the robot, and that the repeatability of their gestures is granted. This assumption is realistic if the human is aware of the robot, i.e. the human trusts the robot and his/her behavior is not influenced by the presence of the robot [25]. Namely, this is a precondition for having the robot accepted and used by the human. Human trustiness may be achieved exploiting robot abilities to cope with human ergonomics and to program the robot to behave naturally and in a safe way, for instance, through speed reduction and movement holding.

Under these assumptions, the next sections introduce simple models for HRC tasks.

4.1 Human task representation

Denote $\mathcal{C}^{h}$ as the human configuration space, i.e. the space describing the human’s posture and gesture at a generic instant of time.

Generally, human movements are described through the use of human skeleton joints, making $\mathcal{C}^{h}$ the set of whole human joint coordinates. However, humans’ motor abilities are more focused on goal achievement rather than on the accuracy of the gestures, and skeleton reconstruction algorithms from 3D point clouds are generally inaccurate [39]. Different methodologies address these sources of inaccuracy [29], reducing the number of variables describing the gesture and calculating a “mean gesture” associated to the task.

However, during the analysis of human’s gestures in HRC, the offset between the human and the robot task start times cannot be constrained (Assumption 1), making difficult the use of “mean gestures”. Indeed, the interaction model should integrate all the relative combinations of human and robot task start times [29].

Thus, a probabilistic time-independent model for $\mathcal{C}^{h}$ and for $u^{h}_{i}$ based on voxel maps is proposed. The method consists of four steps:

1.
The human-robot shared space is divided in a 3D grid of $G$ elements, hereafter called Occupancy Grid. An unique index $k\leqslant G$ is used to label each node of the grid. Then, the voxelization operator $V(\cdot)$ is defined as the function that projects a generic point $x$ onto the Cartesian space onto the closest node of the grid

$\begin{array}[]{llcl}V:&\mathbb{R}^{3}&\longrightarrow&\left\{1,\ldots,G\right% \}\subset\mathbb{N}\\ &x&\longmapsto&k.\end{array}$ (1)
2.
At each instant of time $t$ , the whole human body is binarized into a vector $\mathbf{c}$ of $G$ elements so that the $k$ -th element is 1 if crossed by the human body and 0 otherwise. Therefore, $\mathbf{c}(t)$ results in the time-map of the human’s postures projected onto the grid nodes:

$\begin{array}[]{llcl}\mathbf{c}:&\mathbb{R}&\longrightarrow&\left\{0,1\right\}% ^{G}\\ \\ &t&\longmapsto&{\begin{bmatrix}\scriptstyle c_{1}\\ \scriptstyle\vdots\\ \scriptstyle c_{G}\end{bmatrix}}.\end{array}$ (2)

At each instant of time $t$ , the human body may cross a different number of nodes, i.e. the sum of $\mathbf{c}$ may change over the time.
3.
In order to obtain a bounded description of the task $u^{h}_{j}$ , the function $\bm{\gamma}^{h}$ is introduced as the integral value of $\mathbf{c}$ over the time:

$\begin{array}[]{llcl}\bm{\gamma}^{h}:&\mathbb{R}&\longrightarrow&\mathbb{R}^{G% }\\ &t&\longmapsto&\cfrac{1}{t}\displaystyle\int_{0}^{t}\mathbf{c}\left(\tau\right% )\,d\tau.\end{array}$ (3)

$\bm{\gamma}^{h}$ associates a value in the range $[0,1]$ to the $k$ -node of the Occupancy Grid corresponding to the normalized temporal occupancy of the node by the human.
4.
The value that $\bm{\gamma}^{h}$ achieves at the end of the human movement, $t={T}^{h}$ , depicts the probability to have the human crossing the node $k$ during the whole task execution:

$P^{h}_{k}:=\bm{\gamma}^{h}_{k}\left({T}^{h}\right)$ (4)

The method, therefore, assumes that $\mathcal{C}^{h}:=\left[0,1\right]^{G}$ , and the human task $u^{h}_{i}$ can be uniquely represented by the probability distribution $P^{h}_{k}$ , i.e. $u^{h}_{i}:=\left(\bm{\gamma}^{h}_{k},{T}^{h}\right)$ . Such model of the human task provides the property that the “mean” human movement is obtained just concatenating the acquired data.
4.2 Robot task representation

Denote $\mathcal{C}^{r}$ as the robot configuration space, i.e. the variable grouping the values of the robot state variables like the arm joint positions, the gripper position, etc. Under Assumption 2, it is possible to define $\bm{\gamma}^{r}$ as a time-independent parametrization of the curve in $\mathcal{C}^{r}$

$\begin{array}[]{llcl}\bm{\gamma}^{r}:&\mathbb{R}&\longrightarrow&\mathcal{C}^{% r}\\ &\xi&\longmapsto&\bm{\gamma}^{r}(s)\end{array}$ (5)

such that $\bm{\gamma}^{r}$ is off-line computed and unchangeable. Then, the nominal off-line computed evolution of the $\xi$ -parametrization of the curve can be expressed as

$\begin{array}[]{llcl}\xi^{nom}:&\mathbb{R}&\longrightarrow&\mathbb{R}\\ &t&\longmapsto&\xi^{nom}.\end{array}$ (6)

Finally, it is possible to denote $d(t)$ as the minimum distance between the human and the robot and to define $\lambda:=\lambda(d)$ as a speed scale function bounded in the interval $\left[0,1\right]$ that on-line overrides the nominal robot speed to avoid collisions. The real motion law results in

$\xi\left(t\right):=\int_{0}^{t}\lambda(d(\tau))\,\cfrac{d}{d\tau}\,\xi^{nom}\,% d\tau.$ (7)

Therefore, the robotic task $u^{r}_{i}$ can be expressed as a group of four functions $u^{r}_{i}:=(\bm{\gamma}^{r},\xi^{nom},\lambda,d)$ .

4.3 Probabilistic modeling of the human-robot interaction

The aim of the method is to identify a statistical estimator of ${T}^{r}$ so that $\xi\left({T}^{r}\right)=\xi^{\rm goal}$ where $\xi^{\rm goal}$ is the length of the curve. With such an aim, it is assumed that the robot may collide with the human only in the $k$ -th node of the Occupancy Grid. Then, it is possible to apply the voxelization operator $V$ defined in Eq. (1) to each node of the trajectory in order to have a common underlying representation of $\mathcal{C}^{r}$ and $\mathcal{C}^{h}$ . Denoting $l:=V({\scriptstyle\bm{\gamma}^{r}(\xi(t_{i}))})$ and $q:=V({\scriptstyle\bm{\gamma}^{r}(\xi(t_{i+1}))})$ as the two sequential nodes of the robot trajectory projected onto the nodes of the Occupancy Grid, and considering Eq. (4), it is possible to estimate the probability that the robot moves from $l$ to $q$ or holds in $l$ as

$\begin{array}[]{lcl}P^{r}_{l,q}&:&\left\{\begin{array}[]{ll}1-P^{h}_{k},&q=k,% \\ 1,&q\neq k,\\ \end{array}\right.\\ \\ P^{r}_{l,l}&:&\left\{\begin{array}[]{ll}P^{h}_{k},&\quad\quad q=k,\\ 0,&\quad\quad q\neq k.\\ \par \end{array}\right.\end{array}$ (8)

For instance, the human, always in the $k$ -node ( $P_{k}=1$ ), will lead to the holding of the robot, if and only if the robot is crossing the $k$ -node.

It is easy to see that such formalization is equivalent to a Markov chain1 where the states are the nodes of the Occupancy Grid and the goal is an absorbing state [40]. Specifically, P, i.e. the transition probability matrix of the absorbing chain, can be expressed in the canonical form as:

$\textbf{P}=\left[\begin{array}[]{cc}\textbf{Q}&\quad\textbf{R}\\ \textbf{0}&\quad 1\end{array}\right].$ (9)

where R represents the vector of the transition probabilities towards the considered absorbing state, while Q is the matrix of the transition probabilities among the non-absorbing states. Based on such model for the interaction, the expected time needed to the robot to move from the start point, i.e. the first node of the Markov chain, to the end point, i.e. the absorbing state of the Markov chain, can be estimated through the fundamental matrix N

$\textbf{N}=\left[\textbf{I}-\textbf{Q}\right]^{-1}$ (10)

where the $(i, j)$ entry of matrix N is the expected number of times the chain is in state $j$ , given that the chain started in state $i$ . Therefore, if w is the time vector gathering the duration of the robot dwell in each state, the robot expected execution time to move from the entering state of the chain to the goal (the absorbing state) is equal to

$T^{r}_{chain}=\textbf{N}\left(1,:\right)\,\textbf{w}.$ (11)

Finally, it is possible to release the hypothesis made at the beginning of this section, according to which the robot may collide with the human only in the $k$ -node. With such an aim, since in real world it is hard to predefine potential collision nodes due to human’s gestures spanning a large workspace in few instant time, a further assumption is introduced.

(Collision Probability).

During the execution, the probability to have 1, 2 or even $n$ collisions within $\mathcal{C}^{h}$ follows a uniform distribution, i.e. there is the same probability that a different discrete limited number of collisions may happen.

Two main remarks:

The maximum $n$ depends on the system properties. Each robot stop takes few seconds (to stop, hold, and resume the motion). If the delay time due to the number of collisions is longer that the human execution time plus the robot execution time, it means that such a number of collisions cannot happen;

$n$ mainly depends on the phasing between human and robot movements that, modifying the human-robot overlapping, causes a different number of potential collisions.

Table 1

Nomenclature: general definitions

Variable	Definition
$\mathcal{U}^{h}$	Set of human tasks
$u^{h}_{i}$	i-th human task
$\mathcal{U}^{r}$	Set of robot tasks
$u^{r}_{i}$	i-th robot task
$\mathcal{C}^{h}$	Human configuration space
$\bm{\gamma}^{h}$	Human occupancy into the configuration space $\mathcal{C}^{h}$
$\mathcal{C}^{r}$	Robot configuration space
$\bm{\gamma}^{r}$	Robot path

Table 2

Nomenclature: time variables

Variable	Definition
${T}^{h}$	The time needed by the human to execute his/her task
${T}^{r}_{\exp}$	Estimation of the time required by the robot to execute the whole trajectory
${T}^{r}_{\max}$	Estimation of the upper threshold of the time required by the robot to execute the whole trajectory
${T}^{r}_{\rm free}$	Time required by the robot to execute the portion of the trajectory that does not enter the workspace shared with the human
${T}^{r}_{\rm stop}$	Time needed by the robot to stop its motion during trajectory execution to avoid collisions with the human
${T}^{r}_{\rm start}$	Time needed by the robot to restart its motion during trajectory execution after a stop due to the presence of the human
$v^{\max}$	Maximum velocity of the robot at the end effector. This velocity is equal to 250 mm/s in order to cope with safety regulations
$a^{\max}$	Maximum acceleration of the robot at the end effector

Table 3

Nomenclature: Markov chain definitions

Variable	Definition
${l}_{b}$	Leaf bin of the octree that may be simultaneously occupied by the robot and the human (thus, labeled as visited by both the human and the robot). The total number of leaf bins is $B$
${T}^{r}_{b}$	Time spent by the robot in the leaf bin ${l}_{b}$
${T}^{h}_{b}$	Time spent by the human in the leaf bin ${l}_{b}$
${P}^{h}_{b}$	Probability to find the human in the leaf bin ${l}_{b}$
$m$	Markov chain $m\in\{1,\ldots,M\}$ , where $M$ is the total number of Markov chains to be built
$o^{m}$	Order $o$ of the Markov chains $m$
${s}^{m}_{i}$	State $i$ of the Markov chain $m$ . The total number of states is ${{S}}^{m}$
$T^{m}_{i}$	Time associated to the state ${s}^{m}_{i}$ of the Markov chain $m$
${T}^{r}_{\exp}(m)$	Estimation according to the Markov chain $m$ of the time required by the robot to execute the whole trajectory
$\textbf{w}^{m}$	Vector of the time associated to each state of the Markov chain $m$ : $[T^{m}_{1},\dots,T^{m}_{{S}}]$
$\textbf{P}^{m}$	Transition matrix for the Markov chain $m$

Based on the four listed assumptions, this paper introduces a formalism to evaluate the robot execution time ${T}^{r}$ as the mean of the times deriving from a set of Markov chains that describe all the equiprobable combinations of collisions.

Specifically, denote $\nu\subset\left\{1,\ldots,G\right\}$ as a subset of the Occupancy Grid that corresponds to the set of nodes where collisions may happen. Then, it is possible to define:

.

$\textit{MC}_{\nu}$ as a Markov Chain describing the system where the collisions may happen in the nodes described by $\nu$ . Hereafter, the number of possible collisions, $o:=\textit{length}\left(\nu\right)$ , is called order of the $\textit{MC}_{\nu}$ .

For instance, $\textit{MC}_{\left\{2,5,7\right\}}$ describes the Markov Chain of order 3 that corresponds to the system where the collisions may happen in the 2nd, 5th or 7th node of the Occupancy Grid. Therefore, the method here presented computes all the feasible (e.g. physical) $\textit{MC}_{\nu}$ . Then, under Assumption 4, the expected robot execution time is estimated by the mean of the expected robot execution time of each chain (details in Section 5.4).

5. Method

The nomenclature presented in Tables 1–3 is used during the method description. The method is characterized by four main steps:

1.
Human task representation, i.e. $\bm{\gamma}^{h}$ calculus;
2.
Robot task representation, i.e. $V\left(\bm{\gamma}^{r}\right)$ calculus;
3.
Workspace segmentation: the use of a 3D Occupancy Grid for the human and the robot representations leads to high computational complexity. Therefore, a clustering method based on octree [41] has been designed to preserve the properties of $\mathcal{C}^{h}$ and $\mathcal{C}^{r}$ ;
4.
Markov chain modeling and robot time estimation, i.e. the calculus of all the feasible $\textit{MC}_{\nu}$ and the expected robot execution time.

A subsection for each step of the method is hereafter presented.
5.1 Human task representation

First, the Occupancy Grid representing the collaborative workspace is defined with a step of few millimeters, typically 5 mm. This resolution is sufficient to track properly the human movements as needed by the method, and it is coherent with the resolution of the Kinect One sensor. It is worth to note that possible noise introduced during the Kinect One acquisition is filtered in the next step of the method (Section 5.3.) Then, at each instant time the binary description of the 3D human image is computed using Eq. (2) through a proper elaboration of the data acquired by two Kinect One [42] (frame rate of 70 Hz). The two Kinect One are placed so that occlusions are avoided, i.e. at least one Kinect One is always able to track human movements. The Microsoft standard library provides both a 3D point cloud of the scene and the human skeleton (as shown in Fig. 1b) of the worker in the scene. According to Eq. (3), $P^{h}_{k}$ may be simply calculated as a mean integral of the 3D point cloud. The drawback of such an approach is that the raw 3D point cloud acquired by the Kinect One is subject to noise. Since the skeleton estimated by the standard library provided by Microsoft is quite robust, a filtering procedure of the 3D raw data given by the Kinect One is developed with the aim to exploit the nominal skeleton and to achieve a robust and not distorted 3D human point cloud.

Figure 1.

Example of HRC: unscrewing of a multi-fixturing system. On the left, the human performing at task; on the right, the skeleton estimated by the driver of the Kinect One.

Finally, once the 3D human point cloud is reconstructed, each point is projected onto the closest node of the Occupancy Grid and $\bm{\gamma}^{h}$ is on-line computed (Eq. (3)).

Figure 2.

The volume occupied by the human and the robot during the execution of their tasks is represented by two cloud points, than merged and organized into an octree. The leaf bins of the octree occupied by both the human and the robot will be used as nodes in a set of Markov chains.

5.2 Robot task representation

Given the robot trajectory $\bm{\gamma}^{r}$ , expressed in the workspace, a method to implement $V\left(\bm{\gamma}^{r}\right)$ is hereafter described.

First, the robot trajectory $\bm{\gamma}^{r}$ is split in a discrete number of nodes, few millimeters away from each other. Then, for each node of $\bm{\gamma}^{r}$ , the 3D rigid model of the robot in the corresponding configuration is transformed into a point cloud with few millimeters steps. Finally, each point of the 3D robot point cloud is projected onto the closest node of the Occupancy Grid defining $V\left(\bm{\gamma}^{r}\right)$ .

5.3 Workspace segmentation

In Sections 5.1 and 5.2, both $\mathcal{C}^{h}$ and $\mathcal{C}^{r}$ representations are based on the definition of the Occupancy Grid. However, the use of a high resolution voxelization may introduce computational problems. For instance, with a grid of 5 mm, and a robot trajectory crossing the human workspace for about 1000 mm, more than 200 different nodes (i.e. 200 states for the Markov chain) have to be evaluated.

Therefore, an octree [41] for the clustering of the nodes of the Occupancy Grid has been implemented2. The built octree considers $\bm{\gamma}^{h}$ , $V\left(\bm{\gamma}^{r}\right)$ and the Occupancy Grid underlaying their representation. First, these two point clouds are merged and only the space that may be simultaneously occupied by the human and the robot is considered. Second, an octree is implemented to divide the 3D merged point cloud in a small set of bins. The octree is generated fixing the dimensions of the smaller cell (i.e. the leaf bins) to 50 mm (Fig. 2a). Then, all the leaf bins are analyzed to verify their occupancy by both the robot and the human (Fig. 2b). Only the leaf bins ${l}_{b}$ containing both the human and the robot point clouds are considered and exploited in the approach. In such a way, the problem domain is restricted to those $B$ different bins where a human-robot collision may happen. For each of these $B$ different bins, the following variables are estimated:

•
Probability ${P}^{h}_{b}$ calculated as the average over the points in the bin ${l}_{b}$ of Eq. (4);
•
The time ${T}^{h}_{b}$ spent by the human in the leaf bin ${l}_{b}$ ;
•
The time ${T}^{r}_{b}$ spent by the robot in the leaf bin ${l}_{b}$ .

The segmentation of the workspace is done off-line. All the data related to the volume occupied by the human are collected from real-time experiments and stored in a file. The file is then post-processed together with the file containing the robot trajectory information. The computational time is linear with the amount of data to be post-processed and is exponential with the minimum dimension of the octree leaf bins.
5.4 Robot time estimation through Markov chains

On the basis of the octree representation, the set of all the feasible Markov chains $\textit{MC}_{\nu}$ is built in order to estimate the mean robot execution time. The method provides 4 steps:

1.
Enumeration of all the feasible $\textit{MC}_{\nu}$ ;
2.
Design of the zero-order Markov chain (i.e. without collisions);
3.
Design of the remaining Markov chains;
4.
Estimation of the robot execution time.

Hereafter the steps are described in detail.

Definition of the number of Markov chains.

It is assumed that the robot may stop only once in each ${l}_{b}$ , i.e. when the robot resumes the motion, it moves at least up to the next bin before a further stop happens.

Since collisions may happen in any of the $B$ different bins, the total number $M$ of Markov chains to be generated and analyzed is equal to all the combinations of $o$ robot stops in $B$ leaf bins without order and repetitions (Eq. (12)), where $o\in\{0,\dots,B\}$ :

$M=\sum_{o=0}^{B}\left(\begin{array}[]{c}B\\ o\end{array}\right)=\sum_{o=0}^{B}{\displaystyle\frac{B!}{o!(B-o)!}}.$ (12)

For instance, in case of $B=$ 4, the total number of Markov chains to be analyzed is 16 (Fig. 5): 1 chain with $o=$ 0 (i.e. 0 robot stops), 4 chains with $o=$ 1 (i.e. 1 robot stop), 6 chains with $o=$ 2, 4 chains with $o=$ 3, 1 chain with $o=$ 4.

Figure 3.
Example of an octree with only leaf bins and a zero-order Markov chain built on it ( $B=4$ ). The last state is external to the Occupancy Grid.

Finally, it is possible to denote:

1.
$\textit{MC}^{m}$ as the $m$ -th feasible Markov Chain, with $m=1,\ldots,M$ .
2.
$o^{m}$ as the order of the $m$ -th feasible Markov Chain.
3.
$s^{m}_{l}$ as the $l$ -th state of the $m$ -th Markov Chain.

Design of the zero-order Markov chain.

The first Markov chain $m=1$ to be designed is the zero-order Markov chain ( $o^{1}=0$ ), i.e. the Markov chain for which no robot stops are foreseen. For this chain, the number of states is equal to the number of leaf bins $B$ plus $1$ , i.e. an additional state is added and represents the final goal (the absorbing state). Such state $s^{1}_{B+1}$ is the absorbing state, and it may be located internally or externally to the Occupancy Grid. In the case the state is internal, it means that the bin $B$ will be counted twice in order to take into account that a collision could happen just before the goal within the same bin (Fig. 3).

The states are then connected so to represent the robot moving along its trajectory, i.e. the sequence according to which the robot visits the bins. Since robot stops are not considered, the transition probability among two adjacent states (and leaf bins) is equal to 1, i.e. $p_{b,b+1}=1$ .

Design of the remaining Markov chains.

To model the $o^{m}$ possible collisions of the $m$ -th Markov Chain, the states of the zero-order Markov Chain are extended. Specifically, every time a robot stop is foreseen in ${l}_{b}$ (Fig. 4), a new state ${s}^{m}_{c}$ is added to the $m$ -th chain. Therefore, it is possible to denote:

1.
$p^{m}_{b,c}$ as the probability to move from the state ${s}^{m}_{b}$ to ${s}^{m}_{c}$ (i.e. the probability to remain in the leaf ${l}_{b}$ because of the robot stop), with $p^{m}_{b,c}:={P}^{h}_{b}$ .
2.
$p^{m}_{b,b+1}$ as the probability not to have a robot stop and thus to move to ${s}^{m}_{b+1}$ (i.e. to the leaf $l_{b+1}$ ) with $p^{m}_{b,b+1}:=1-{P}^{h}_{b}$ .
3.
$p^{m}_{c,b+1}:=1$ as the probability to move from the state ${s}^{m}_{c}$ to the state ${s}^{m}_{b+1}$ given the assumption to have one robot stop per bin.

Figure 5 shows an example of the set of Markov chains according to the foreseen number of robot stops and their combinations with respect to the leaf bins. The corresponding probability matrix $\textbf{P}^{2}$ results in

$\textbf{P}^{2}=\bordermatrix{&s^{2}_{1}&s^{2}_{6}&s^{2}_{2}&s^{2}_{3}&s^{2}_{4% }&s^{2}_{5}\cr s^{2}_{1}&{\scriptstyle 0.0}&{\scriptstyle{P}^{h}_{1}}&{% \scriptstyle 1-{P}^{h}_{1}}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{% \scriptstyle 0.0}\cr s^{2}_{6}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{% \scriptstyle 1.0}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{\scriptstyle 0.0}\cr s% ^{2}_{2}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{% \scriptstyle 1.0}&{\scriptstyle 0.0}&{\scriptstyle 0.0}\cr s^{2}_{3}&{% \scriptstyle 0.0}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{% \scriptstyle 1.0}&{\scriptstyle 0.0}\cr s^{2}_{4}&{\scriptstyle 0.0}&{% \scriptstyle 0.0}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{% \scriptstyle 1.0}\cr s^{2}_{5}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{% \scriptstyle 0.0}&{\scriptstyle 0.0}&{\scriptstyle 0.0}&{\scriptstyle 1.0}}$

Estimation of robot execution time.

Denote ${T}^{r}_{\rm stop}$ and ${T}^{r}_{\rm start}$ as the times to resume and stop the robot motion. They are evaluated taking into account the maximum robot velocity and acceleration:

${T}^{r}_{\rm start}={T}^{r}_{\rm stop}={\displaystyle\frac{v^{\max}}{a^{\max}}}.$ (13)

The time the robot stays in each state of the $\textit{MC}^{m}$ results in (Fig. 4):

ii. i.
$T^{m}_{b}=T^{r}_{b}$ , i.e. the time the robot stays within the state $s^{m}_{b}$ is the time the robot stays in the bin;
ii.
$T^{m}_{c}={T}^{r}_{\rm start}+\max[{T}^{h}_{b},{T}^{r}_{\rm stop}]$ , i.e. the time the robot stays in the state $T^{m}_{c}$ is equal to the time that the robot spends in ${l}_{b}$ because of its stop. The maximum between ${T}^{h}_{b}$ and ${T}^{r}_{\rm stop}$ is considered since the robot starts to stop its motion when the human is already occupying the cell, making one of these times a hidden time.

Therefore, given the topology of the $\textit{MC}^{m}$ , it is possible to define $\textbf{w}^{m}$ as the vector sorting all the times the robot may stay in each state. Then, the expected execution time of the robot for the $m$ -th Markov chain can be evaluated as:

${T}^{r}_{\exp}(m)={T}^{r}_{\rm free}+\textbf{N}^{m}(1,:)\cdot\textbf{w}^{m}$ (14)

where the first addendum is the time required by the robot to execute the portion of the trajectory that does not enter the workspace shared with the human, and the second addendum is time the robot needs to execute the part of the trajectory that overlaps the human workspace, calculated using Eq. (11).

Figure 4.
Example of the changes to be applied to the states and the transition probabilities of a Markov chain with $o>0$ in order to model a robot stop in the leaf bin ${l}_{b}$ .

Figure 5.
Example of the generated set of Markov chains for $B=4$ . For each order the first two combinations (if existing) are shown.

Figure 6.
Experimental environment.

Finally it is possible to calculate the expected execution time ${T}^{r}_{\exp}$ as follow:

1.
First, the maximum robot time ${T}^{r}_{\max}(m)$ is evaluated as

${T}^{r}_{\max}={T}^{r}_{\exp}(1)+{T}^{h}$ (15)

i.e. the robot execution time in case of no robot stops (the zero-order Markov chain) and the time ${T}^{h}$ required to the human to finish his/her task.
2.
Then, the solution of all the Markov chains for which ${T}^{r}_{\exp}(m)>{T}^{r}_{\max}$ are discarded. Indeed, in the worst case, ${T}^{r}_{\max}={T}^{r}_{\exp}(m)$ , i.e. the robot has to be stopped for the whole duration of the human task. Thus, if ${T}^{r}_{\exp}(m)$ is bigger than ${T}^{r}_{\max}$ , the solution is not consistent (too many collisions are foreseen) and it must be discarded.
3.
Finally, the robot expected time ${T}^{r}_{\exp}$ is evaluated as the mean of the means on ${T}^{r}_{\exp}(m)$ for each Markov order (Assumption 4).

6. Experiments

A set of experiments were conducted with the aim to validate the proposed approach. The reference selected application is the preparation of the load unload station (LUS) of a flexible manufacturing system (FMS) (Section 6.1).

Two sets of experiments were run. First (Section 6.2), the approach was tested using a high number of simulated experiments. Specifically, a simulator of the real behavior of the robot was created and used to obtain an estimation of the robot expected time for randomly generated trajectories. The results coming from the simulation and from the proposed approach were compared in terms of mean execution time and standard deviation. This simulator may be used in the future in order to compare different methods on huge set of trajectories. Second (Section 6.3), a set of restricted experiments were conducted on a real setup and compared in terms of obtained mean execution time with the results coming from the approach, the simulated environment and [16].

Figure 7.

Representation of the three tasks in the scenario.

6.1 Experimental task description

At the LUS, machined parts and raw parts are respectively unmounted and mounted on ad-hoc fixturing systems, called pallet, in order to be machined by the FMS. Pallet preparation is critical for any Computer Numerical Control (CNC) operation and it is the only manual task left in FMSs. Pallet setup involves hundreds of configurations, continuously changed for the production of small batches. Mounting errors may generate production losses and clamping/removal of metal parts and fixtures is cognitively and physically demanding.

Thus, pallet preparation before machining has very much to gain from robotics, mainly in terms of flexibility and ergonomics. Such tasks are however very difficult from the control perspective, because both human operators and robots need a concurrent access to the pallet in a small layout. Manipulation tasks are done very close to the human body, yet need to be fast for the production rate.

Figure 6 shows the considered environment, made of a collaborative robot mounted on a carrier (Kuka IIWA 14 R820) and of a multi-fixturing system (pallet). This setup represents the load/unload station of a flexible manufacturing systems. Three different human tasks are taken into account:

A3h $A^{h}_{1}$
The human performs one screwing and one unscrewing task on two different sides of a multi-fixturing pallet
$A^{h}_{2}$
The human picks a tool from the robot carrier and moves towards the pallet
$A^{h}_{3}$
The human moves a machined part from a side of the pallet to the robot carrier

A worker is asked to execute the task 10 times, and his/her skeleton is captured by two Kinect One (Section 5.1).

Table 4
Expected execution time of the robot and standard deviation considering 30 trajectories per human task

Human tasks Simulator [s] Approach [s] Mean error [s]

$A^{h}_{1}$ 5.14 $\pm$ 1.13 4.98 $\pm$ 0.57 0.17

$A^{h}_{2}$ 4.81 $\pm$ 0.54 4.92 $\pm$ 0.54 $-$ 0.11

$A^{h}_{3}$ 4.47 $\pm$ 0.44 4.66 $\pm$ 0.40 $-$ 0.19

Mean 4.80 $\pm$ 0.70 4.85 $\pm$ 0.50 $-$ 0.05

6.2 Simulated experiments

Human tasks	Simulator [s]	Approach [s]	Mean error [s]
$A^{h}_{1}$	5.14 $\pm$ 1.13	4.98 $\pm$ 0.57	0.17
$A^{h}_{2}$	4.81 $\pm$ 0.54	4.92 $\pm$ 0.54	$-$ 0.11
$A^{h}_{3}$	4.47 $\pm$ 0.44	4.66 $\pm$ 0.40	$-$ 0.19
Mean	4.80 $\pm$ 0.70	4.85 $\pm$ 0.50	$-$ 0.05

In order to provide an extensive number of experimental results to be used as a reference for the approach results, a simulator of the real behavior of the robot during human robot collaborative tasks was built. On the one hand, the use of the simulator has the advantage not to require a physical setup to run the experiments and to provide a comparison for the results deriving from the application of the developed method. On the other hand, the computational time required by the simulation is definitely higher than the computational time required by the proposed approach, thus limiting the usability of the simulation as an approach for the estimation of the robot execution time.

Table 5
Expected execution time [s] of the robot considering 4 trajectories to be executed simultaneously to $A^{h}_{3}$ according to real experiments (RE), simulator results (SM), results from [16] (AP[16]) and the results of the proposed method (AP). In the forth and last columns of the table, the mean time [s] and the mean absolute time error [s][%] on the four considered trajectories are respectively presented

	Trajectory 1	Trajectory 2	Trajectory 3	Trajectory 4	Mean time [s]	Mean absolute time error
	time [s]	time [s]	time [s]	time [s]	$\textit{MT}_{X}$	$\|\textit{MT}_{\textit{RE}}-\textit{MT}_{X}\|$
Real exp. (RE)	7.09	7.72	8.13	7.36	7.57	–
Simulation (SM)	7.52	7.22	7.40	7.22	7.16	0.41 s (7.4%)
Approach [16] (AP[16])	9.5	8.6	7.62	9.2	8.73	1.66 s (19.1%)
Approach (AP)	7.39	7.24	7.13	6.86	7.34	0.23 s (5.9%)

Figure 8.

Simulation. The human starts executing his/her task at 0.3 s, whilst the robot starts at 0.9 s. At 2.3 s the human-robot distance (black line) goes beyond the critical threshold of 0.25 m (red line) and the robot slows down and stops at 3.1 s (blue line). Remarkably, the 1 s between the identification of the dangerous collision and the actual robot stop is the number we measured on Kuka IIWA 14 R820 robot. Then, at 3.2 the robot resume the motion since the danger condition was solved. The human finishes his/her task in 6.1 s and leaves the shared workspace. The robot finishes its own task (curve parametrization equal to 1).

Figure 9.

Simulation. Example of the different robot behaviors during trajectory execution based on random start time. Each line in the figure represents the a different robot behavior during execution. The trajectory is parametrized, i.e. the start point is 0 and the end point is 1. During the first 4 s, the trajectory is interested by several robot stops due to presence of the human. After 4 s, robot stops are not present, since the human task is completed and the human is not anymore in the scene. For the considered example, the expected execution time of the robot e is 7.06 s with a standard deviation of 1.28 s.

Figure 10.

Robot trajectories – simulated experiments. Set of robot generated trajectories (colored family of straight lines) intersecting the volume occupied by the worker (yellow cloud point).

Figure 11.

Robot trajectories – real experiments: (a) Robot trajectories (light blue, violet and light green lines) with reference to the human task occupancy volume (green point cloud); (b) One of the trajectories and the human occupancy volume in the considered environment.

The simulator.

The simulator, implemented in Matlab and Simulink, requires two inputs: the description of the human movements during the execution of the task and the robot trajectory. Human movements have to be provided as the captured human joint positions for the whole duration of the human task.

Robot paths $\bm{\gamma}^{r}$ are randomly generated so that they may cross the human workspace or not. The motion law of the path parametrization $\xi(t)$ has been provided by the Reflexxes Library [43]. This library is able to simulate the actual motion law of industrial robots, replicating their acceleration and velocity profiles. Furthermore, the library allows the on-line re-planning of the motion law, i.e. it allows the simulation of the velocity reduction and of the robot stop. The delay between the robot stop command and the actual robot stop and the delay in the robot resume were modeled.

The simulated experiments.

The simulator replicates the full set of captured human movements while executing a randomly generated robot trajectory, with a random start time.

During the execution, when the minimum distance between the robot and the human is lower than a threshold (250 mm), the robot velocity is first reduced and then stopped. The motion is resumed only when the distance returns to be above the identified threshold (Fig. 8). Since the number of robot stops depends on the start time of the robot trajectory, the simulator runs a predefined number of times (e.g. 100 times), randomly changing the start time of the robot trajectory (Fig. 9). At the end of the simulation, the mean execution time of the trajectory and its standard deviation are provided to be used as a reference value.

The same trajectories used by the simulator are then analyzed by the proposed approach, generating for each considered human task a mean execution time and a standard deviation. The set of the trajectories generated for each considered human task are represented in Fig. 10.

Results and discussion.

The expected time for the execution of the previously described cases is evaluated through the use of the simulator and by the proposed approach.

The results provided by the developed method (Table 4) are in line with the results provided by the simulator. The expected execution time in one case out of three is underestimated, whilst, in two cases, it is overestimated. Both underestimations and overestimations are quite limited (mean error equal to 0.05 s and mean absolute error equal to 0.17 s), thus possibly minimally impacting on the quality of the results of task planning and scheduling as well as on the ability of human-robot team to comply with the cell takt time. The mean absolute percentage error is lower than 10% (i.e. 3.5%), thus being acceptable [44].As a general remark, in industrial practice the accuracy in the estimation of the time is not a mandatory requirement. A tolerance of about 10% is considered acceptable in almost all the industrial production lines. In terms of standard deviation, the results are comparable both in the second and in the third experiment. Standard deviation seems to be slightly underestimated in the first experiment.

6.3 Physical experiments

The aim of this section is to compare the expected execution time identified by the proposed approach with the robot execution time coming from real experiments and from [16]. The experimental environment previously described is taken into account.

6.3.1 Human and robot tasks

In order to compare the results of the proposed approach with the results coming from real experiments, human task $A^{h}_{3}$ was selected among the previously defined human activities. Moreover, 4 different robot trajectories were designed, in order to cross the human workspace and to have a physical meaning (Fig. 11). Specifically, the robot has to pick a raw part from the table and to place it on the pallet. The task is described in Fig. 7 in terms of robot start and end points on which all the three considered trajectories rely.

During the experiments, both the robot and the human are asked to repeat the task 10 times. The robot repeats the trajectory without stopping in the initial/final points. As previously defined for the simulator, the robot stops when the minimum distance between the central line of each robot link and the skeleton of the human is lower than 250 mm. This distance takes into account the uncertainty on the position of the worker deriving from the accuracy of the Kinect One as well as the dimensions of the robot links and of the human body. A Kuka IIWA 14 R820 robot is used.

6.3.2 Results and discussion

The times for the execution of the previously described trajectories during HRC in real experiments (RE), in simulation (SM), in [16] (AP[16]) and in the proposed method (AP) are resumed in Table 5. The table also provides a comparison over the four different considered methodologies in terms of mean absolute error.

Four main considerations can be performed through the observation of Table 5. First, the results of the proposed approach (AP) can be compared with the results coming from the simulation (SM). As already stated in the previous section, the approach is able to provide a good estimation of the robot expected time, even if in this case, the robot expected time seems to be slightly overestimated (the mean error and the mean absolute errors present similar values, respectively $-$ 0.189 s and 0.194 s). Second, the results of the proposed approach (AP) can be compared with the results coming from the physical experiments (RE). The mean absolute error is equal to 0.45 s, i.e. 5.9%. This error is still acceptable (lower than 10%). Third, the proposed approach (AP) performs better than [16] (AP[16]). Indeed, the absolute mean error with respect to real experiments decreases from 19.1% to 5.9%.Finally, the simulation (SM) is able to provide a good estimation of the robot execution time, when compared to the real experiments (RE). This suggests to possibly use in future works the simulation in order to run new and extend experimental campaigns for the comparison of different approaches. The results of these comparisons will not suffer from the variably introduced by differences in human movements. Indeed, the same human movements may be used for the simulation and for the evaluation of the approaches in comparison.

7. Conclusions and future work

This paper presents an approach for the estimation of the robot execution time for HRC tasks in which the robot is allowed to reduce and modify its speed in order to avoid possible collisions with the human and to grant human safety (i.e. speed variation monitoring). The approach is divided in two main steps. The first step consists in the analysis of the human movements and in the generation of an octree based on the point clouds representing the volume occupied by the robot and by the human. The second step is based on the use of this octree for the generation of a set of Markov chains, allowing the estimation of the expected robot execution time.

The proposed approach shows an error of about 5.9% in the estimation of the robot execution time when compared to the results coming from real experiments.The error is generally acceptable as discussed above, and it has to be considered as a preliminary result. A proper statistical analysis of the error over tens of experiments is now ongoing, and it will be published in a next work. Furthermore, future work will consist in the modeling of the dynamics underlying human movements so that the current error can be reduced.

Finally, the presented approach may provide valuable data for task planning and scheduling activities, whose results strictly depend on the quality of the estimation made for the execution of human and robot tasks. Moreover, this method may be used to evaluate different trajectories, that will be then selected at run time by the task planner and scheduler based on current needs and on the worker related information, such as the propensity of the worker to cooperate with a robot, the requested talk time of the cell, or the level of risk connected to handle an object with the robot.

The Matlab code implementing the methods is available at https://github.com/CNR-ITIA-IRAS/human-aware-robot-planning.

Footnotes

A Markov chain is a stochastic process where the future state is based on its present state independently from its history.

A octree is a treelike data structure. It is generally used to partition a three-dimensional space by recursively subdividing it in octants. The bins in the last level of subdivisions are called leaves or leaf bins. For more information related to the octree, see [].

Acknowledgments

The research has been funded by the European Projects EuRoC, FP7-2013-NMP-ICT-FOF and FourByThree, H2020-FoF-06-2014.

References

Geerinck

Colon

Berrabah

Cauwerts

Sahli

. Tele-robot with shared autonomy: Distributed navigation development framework. Integrated Computer-Aided Engineering 2006; 13(4): 329-345.

Zeigler

. A simulation-based virtual environment to study cooperative robotic systems. Integrated Computer-Aided Engineering 2005; 12(4): 353-367.

Tsarouchi

Makris

Chryssolouris

. On a human and dual-arm robot task planning method. Procedia CIRP 2016; 57: 551-555. Factories of the Future in the digital environment – Proc of the 49th CIRP Conf on Manufacturing Systems.

Srivastava

Fang

Riano

Chitnis

Russell

Abbeel

. Combined task and motion planning through an extensible planner-independent interface layer. 2014 IEEE Int Conf on Robotics and Automation 2014; 639-646.

de Silva

Lallement

Alami

. The hatp hierarchical planner: Formalisation and an initial study of its usability and practicality. In 2015 IEEE/RSJ Int Conf on Intelligent Robots and Systems (IROS) 2015; 6465-6472.

Nedunuri

Prabhu

Moll

Chaudhuri

Kavraki

. Smt-based synthesis of integrated task and motion plans from plan outlines. 2014 IEEE Int Conf on Robotics and Automation (ICRA) 2014; 655-662.

Dantam

Kingston

Chaudhuri

Kavraki

. Incremental task and motion planning: A constraint-based approach. In Hsu

Amato

Berman

Jacobs

, editors, Robotics: Science and Systems XII, University of Michigan, Ann Arbor, Michigan, USA, 18 June 2016–22 June 2016.

Stein

Ohler

. Venturing into the uncanny valley of mind – The influence of mind attribution on the acceptance of human-like characters in a virtual reality setting. Cognition 2017; 160(Supplement C): 43-50. Available from: https://www-sciencedirect-com.web.bisu.edu.cn/science/article/pii/S0010027716303055.

Lopez

Ccasane

Paredes

Cuellar

. Effects of using indirect language by a robot to change human attitudes. Proceedings of the Companion of the 2017; ACM/IEEE International Conference on Human-Robot Interaction 2017; 193-194. Available from: http://doi.acm.org/10.1145/3029798.3038310.

10.

Chang

Wang

MJJ

. Digital human modeling and workplace evaluation: Using an automobile assembly task as an example. Human Factors and Ergonomics in Manufacturing & Service Industries 2007; 17(5): 445-455.

11.

Badler

Becket

Webber

. Simulation and analysis of complex human tasks for manufacturing. Modeling, Simulation, Control Technologies for Manufacturing 1995; 2596: 225-233.

12.

Duffy

. Human digital modeling in design. John Wiley & Sons, Inc 2012; 1016-1030.

13.

Spensieri

Carlson

Bohlin

Kressin

Shi

. Optimal robot placement for tasks execution. Procedia CIRP 2016; 44: 395-400.

14.

Khalid

Caliskan

Ore

Hanson

. Simulation and evaluation of industrial applications of human-industrial robot collaboration cases. In Nordic Ergonomics Society 47th Annual Conf 2015.

15.

Michalos

Makris

Tsarouchi

Guasch

Kontovrakis

Chryssolouris

. Design considerations for safe human-robot collaborative workplaces. Procedia CIRP 2015; 37: 248-253. CIRPe 2015 – Understanding the life cycle implications of manufacturing.

16.

Pellegrinelli

Moro

Pedrocchi

Molinari Tosatti

Tolio

. A probabilistic approach to workspace sharing for human-robot cooperation in assembly tasks. CIRP Annals – Manufacturing Technology 2016; 65(1): 57-60.

17.

Umbrico

Cesta

Mayer

Orlandini

. Steps in assessing a timeline-based planner. In Adorni

Cagnoni

Gori

Maratea

, editors, AI*IA 2016: Advances in Artificial Intelligence – Int Conf of the Italian Association for Artificial Intelligence 2016, 508-522.

18.

Tsarouchi

Spiliotopoulos

Michalos

Koukas

Athanasatos

Makris

Chryssolouris

. A decision making framework for human robot collaborative workplace generation. Procedia CIRP 2016; 44: 228-232.

19.

Pellegrinelli

Orlandini

Pedrocchi

Umbrico

Tolio

. Motion planning and scheduling for human and industrial-robot collaboration. CIRP Annals – Manufacturing Technology 2017; 66(1): 7-10.

20.

Akkaladevi

Plasch

Pichler

Rinner

. Human Robot Collaboration to Reach a Common Goal in an Assembly Process. European Starting AI Researcher Symposium 2016; 3-14.

21.

Lasota

Shah

. Analyzing the effects of human-aware motion planning on close-proximity human – robot collaboration. Human Factors: The Journal of the Human Factors and Ergonomics Society 2015; 57(1): 21-33.

22.

Arai

Kato

Fujita

. Assessment of operator stress induced by robot collaboration in assembly. CIRP Annals – Manufacturing Technology 2010; 59(1): 5-8.

23.

Nikolaidis

Kuznetsov

Hsu

Srinivasa

. Formalizing Human-Robot Mutual Adaptation: A Bounded Memory Model. Human-Robot Interaction 2016.

24.

Wang

Zhang

Neri

Jiang

Zhao

Gheorghe

Ipate

Lefticaru

. Design and implementation of membrane controllers for trajectory tracking of nonholonomic wheeled mobile robots. Integrated Computer-Aided Engineering 2016; 23: 15-30.

25.

Dragan

Bauman

Forlizzi

Srinivasa

. Effects of Robot Motion on Human-Robot Collaboration. Human Robot Interaction 2015; 1: 51-58.

26.

Mainprice

Sisbot

Jaillet

Cortés

Alami

Siméon

. Planning human-aware motions using a sampling-based costmap planner. Robotics and Automation (ICRA), 2011 IEEE Int Conf on 2011; 5012-5017.

27.

Mainprice

Hayne

Berenson

. Predicting human reaching motion in collaborative tasks using inverse optimal control and iterative re-planning. Int Conf on Robotics and Automation 2015; 885-892.

28.

Pandey

Alami

. Mightability maps: A perceptual level decisional framework for co-operative and competitive human-robot interaction. IEEE/RSJ 2010; Int Conf on Intelligent Robots and Systems, IROS 2010 – Conf Proc 2010; 5842-5848.

29.

Mainprice

Berenson

. Human-robot collaborative manipulation planning using early prediction of human motion. IEEE/RSJ Int Conf on Intelligent Robots and Systems (IROS) 2013; 299-306.

30.

Lasota

Nikolaidis

Shah

. Developing an adaptive robotic assistant for close proximity human-robot collaboration in space. AIAA Infotech@Aerospace (I@A) Conf 2013; 1-8.

31.

Lasota

Rossano

Shah

. Toward safe close-proximity human-robot interaction with standard industrial robots. IEEE Int Conf on Automation Science and Engineering 2014; 339-344.

32.

Mcghan

Nasir

Atkins

. Human intent prediction using Markov decision processes. Journal of Aerospace Information Systems 2015; 12(5): 393-397.

33.

Karami

Jeanpierre

Mouaddib

. Partially observable markov decision process for managing robot collaboration with human. Proc – Int Conf on Tools with Artificial Intelligence, ICTAI 2009; 518-521.

34.

Karami

A-B

Jeanpierre

Mouaddib

A-I

. Human-robot collaboration for a shared mission. Human-Robot Interaction (HRI), 2010 5th ACM/IEEE Int Conf on 2010; 155-156.

35.

Pellegrinelli

Admoni

Javdani

Srinivasa

. Human-robot shared workspace collaboration via hindsight optimization. IEEE/RSJ Int Conf on Intelligent Robots and Systems 2016.

36.

Lasota

Fong

Shah

. A survey of methods for safe human-robot interaction. Foundations and Trends in Robotics 2017; 5(3): 261-349.

37.

Iannacci

Giussani

Vicentini

Tosatti

. Robotic cell work-flow management through an iec 61499-ros architecture. 2016 IEEE 21st Int Conf on Emerging Technologies and Factory Automation (ETFA) 2016; 1-7.

38.

Ragaglia

Zanchettin

Rocco

. Safety-aware trajectory scaling for human-robot collaboration with prediction of human occupancy. In Proc of the 17th Int Conf on Advanced Robotics, ICAR 2015; 85-90.

39.

Scano

Caimmi

Chiavenna

Malosio

Tosatti

. Kinect one-based biomechanical assessment of upper-limb performance compared to clinical scales in post-stroke patients. In 2015; 37th Int Conf of the IEEE Engineering in Medicine and Biology Society (EMBC) 2015; 5720-5723.

40.

Gagniuc

. Markov Chains: From Theory to Implementation and Experimentation. Wiley 1985.

41.

Franklin

Akman

. Octree Data Structures and Creation by Stacking. Springer Japan, Tokyo 1985; 176-185.

42.

Microsoft. KinectOne SDK Libraries, www.xbox.com/en-US/xbox-one/accessories/kinect.

43.

Mathworks. Reflexxes, it.mathworks.com/matlabcentral/fileexchange/50358-trajectory-generator-block-using-the-reflexxes-motion-library.

44.

Callou

Maciel

Andrade

Nogueira

Tavares

. Estimation of energy consumption and execution time in early phases of design lifecycle: An application to biomedical systems. Electronics Letters 2008; 44(23): 1343-1344.