Sage Journals: Discover world-class research

Abstract

Many applications for robots require them to work alongside people as capable members of human-robot teams and to collaborate in order to perform tasks and achieve common goals. These tasks can induce strain on the human due to time constraints. Additionally, humans can become highly stressed due to fatigue, resulting in decreased efficiency. The contribution of this paper is in the introduction of a human fatigue model and the application of this model to a mixed team coordination framework in order to predict team performance given the constraints of human fatigue. The human fatigue model - namely a FAtigue Prediction (FAP) model - is used to conduct numerical simulations that predict mixed team performances. Specifically, extensive simulations are performed to determine how human fatigue influences the choice of the number of agents for a given number of tasks. The novel mixed team coordination framework is a Stochastic Clustering Auction (SCA), which is based on a modification of the Swendsen-Wang method, called SW²SCA. It enables complex and efficient movement between clusters by connecting tasks that appear to be synergistic and then stochastically reassigning these connected tasks. In SW²SCA, the auctioneer makes stochastic movements with homogeneous or heterogeneous agents. The final discussion outlines a systematic procedure to predict the performance of human-robot systems with the FAP model in SCA.

Keywords

Human-robot Interaction Auctions and Market-based Systems Human Fatigue

1. Introduction

Many applications require robots to work alongside humans as capable members of mixed human-robot teams and to collaborate in order to perform tasks and to achieve common goals. Such applications have evolved from collaborative exploration and the military [9], space [15] and medical industries [16]. These tasks are often performed under strain due to time constraints. It is important to determine how human fatigue influences the choice of the number of agents utilized for such tasks. This paper introduces a human fatigue model into the mixed team coordination framework and uses it to predict team performance given the constraints of human fatigue. In this framework, humans and robots treat each other as partners, as opposed to a supervisor and subordinate relationship. There are three stages in predicting the performance of human-robot team collaboration while considering human fatigue. First, semi-structured questionnaires are conducted through personal digital assistants (PDAs) to collect information of the physiological condition of the human subjects so that the modelling parameters can be identified for the two-process model. Next, the human fatigue model is used to predict the task capabilities for the human-robot team. Afterwards, the task capabilities are used as constraints in coordinating the human-robot team.

In the first stage, the PDAs [9] are assumed to be already engaged in a dialogue between humans and robots, following which they then collect semi-structured questionnaires. These questionnaires are used to bring up new questions during the interview [11] to identify the modelling parameters.

In the second stage, our fatigue model is constructed based on the seminal two-process model of sleep regulation [3]. This model postulates that wakefulness and sleep are governed by two primary biological mechanisms: a homeostatic process and a circular process. The homeostatic process builds pressure for sleep during wakefulness and dissipates this pressure during sleep [2], while the circadian process modulates sleep pressure as a function of the time of day [8]. The two-process model has been successful in predicting individualized performance impairment for human fatigue [7, 12].

In the third stage, humans and robots treat each other as partners in the collaborative human-robot team. Existing approaches to human-robot team collaboration can be assigned according to three categories: fully centralized approaches [4], completely distributed approaches [14] and auction algorithms [5, 6, 17 –22]. Dias et al. presented the seminal works on auctioning methods [5, 6]. SCAs [17 –22] constitute a class of cooperative auction methods that enable the improvement of the global cost of the task allocations obtained using fast, greedy algorithms. SCAs fall within the class of Markov chain Monte Carlo methods [13] and optimize using simulated annealing [10]. By rearranging the clusters via transfer moves or swap moves, and by allowing both downhill and uphill movements, SCA algorithms provide some ability for avoiding local minima. SCAs provide an efficient framework for determining how human fatigue can influence the choice of the number of agents for a given number of tasks.

1.1. Related Works

Only a few studies have been found which cover mixed human-robot team coordination with human fatigue. A two-process model is proposed to characterize human fatigue and the cost function is constrained by the fatigue model [23]. A further study implements a similar fatigue model, but on a weighted cost function over boredom, forgetfulness, fatigue and situational awareness [24]. The two studies, however, have completely framed in the fully centralized approaches because a human operator or robot acts as a central allocator to determine the task distribution for the team [21]. There are three limitations to the fully centralized approaches. First, and foremost, fully centralized approaches require complete communication between the central allocator and each team member, which is not always feasible. Second, they require the central allocator to have substantial internal knowledge of each team member and to keep track of changes in the team members as the mission progresses, which may not be practical. Third, they are vulnerable to a single point failure.

The major contribution of this work lies in the development of a human fatigue model which is integrated in the context of human-robot interaction, whereby auction-based task allocation in a human-robot team is reformulated as an optimization problem.

1.2. Outline

The remainder of this paper is organized as follows. Section 2 formulates the basic optimization problem for task allocations in a collaborative human-robot team, introduces the bio-mathematical two-process model for human fatigue, provides a description of SCA, and discusses how SCA may be used for human-robot teams. Section 3 integrates the bio-mathematical two-process model for human fatigue with SCA in a mixed human-robot team, and it is seen that the integration of SCA with the bio-mathematical model can predict the performance of the mixed team in terms of cost. Section 4 summarizes a systematic engineering approach to human-robot system task allocation with the FAP model in SCA. Finally, Section 5 concludes the results.

2. Preliminaries

This section first presents the basic problem statement. Then, it introduces the bio-mathematical two-process model for human fatigue. After that, the SCA algorithm as constrained by human fatigue is presented and discussed.

2.1. Task Allocation Problem Statement

Let ℋ denote a set of k heterogeneous robots or humans, and let 𝒯 denote a set of n tasks, i.e., ℋ = h₁, h₂, …, h_k, 𝒯 = t₁, t₂, …, t_n. The tasks can be sequenced in any order and are categorized as “goto points”. Also, heterogeneity does not necessarily imply that the agents perform different tasks. It implies that they do not perform each task with the same efficiency. For example, the agents may move at different speeds, preventing them from reaching a destination (i.e., perform a task) with equal efficiency, even when starting from the same spatial location.

Let $C A P$ denote the allocation, where a_s is a cluster of tasks. This means that $\cup_{s = 1}^{k} a_{s} = T$ , a_s ∩ a_t = , (s ≠ t). and the cluster a_s is assigned to agent h_s. Each a_s is then decomposed into n_s connected components a_si such that $a_{s} = \cup_{i = 1}^{n_{s}} a_{s i},$ , where each a_si ⊆ a_s is connected to at least one other member of a_s by an edge e in an undirected graph for agent h_s, e ∊ ε(a_s), and ε(·) is the edge set for the cluster a_s. Note that an edge e ∊ ε(a_s) is denoted by < u, v >, where u ∊ a_s, v ∊ a_s and u ≠ v. Let 𝒞𝒫 denote the entire set of connected components for agent h_s, such that 𝒞𝒫 = a_si: s = 1,2, …, k; i = 1, …, n_s. 𝒜(a_si) = t is used to denote the allocation of the connected component a_si from agent h_s to agent h_t.

Let 𝒞𝒜𝒫 denote the task capability of the human-robot team:

C A P = {C A P (h_{1}, \hat{k}), C A P (h_{2}, \hat{k}), \dots, C A P (h_{k}, \hat{k})},

(1)

where $C A P (h_{k}, \hat{k})$ is the total time that the agent h_k can spend completing tasks at time $\hat{k}$ and $\hat{k} ∊ {0,1, \dots, \hat{k}, \dots, \hat{n}}$ and $\hat{n}$ is the whole period of total sleep deprivation in hours. The cost associated with A is given by:

C (A) = \max_{s} c_{s} (a_{s}),

(2)

where c_s(a_s) is the minimum cost for agent h_s to complete the set of tasks a_s. The individual cost function c_s(·) is based on the characteristics of each agent (e.g., the dynamic model of the agent, the state of the market, current task commitments and/or a human-inspired measure). The problem is to solve the optimization min 𝒞(𝒜). In practice, the cost function in (2) might be used to represent the maximum time taken to accomplish a task.

2.2. Bio-mathematical Two-process Model for human fatigue

This section introduces a FAP model. FAP uses a bio-mathematical two-process model to predict how long a human can handle a task in hours under the influence of fatigue in a mixed human-robot team. The two processes that govern the regulation of the sleep-wake cycle are a sleep/wake-dependent homeostatic process (Process SL) and a sleep/wake-independent circadian process (Process CI) [2, 12]. Process SL provides a sleep/wake pattern whereby sleep intensity is governed by a homeostatic mechanism, while Process CI regulates the period of the pattern, whereby the timing of sleep is controlled by the circadian clock. As the bio-mathematical model builds upon this work, the mathematical basis is briefly reiterated here.

Process SL, which is dependent on the duration of prior sleep and waking, is typically represented as a pair of difference equations [2, 7, 12]. $S L (\hat{k})$ denotes the value of the sleep homeostat at time $\hat{k}$ . $S L (\hat{k})$ rises during waking and declines during sleep. The definition of SL(k) is introduced in Definition 1:

Definition 1.

S L (\hat{k}) = {\begin{matrix} 1 - \exp (- T_{S L} / τ_{r} [1 - S L (\hat{k} - 1)]) & w h i l e a w a k e, \\ \exp (- T_{S L} / τ_{d}) [S L (\hat{k} - 1)] & w h i l e s l e e p i n g, \end{matrix}

(3)

where $S L (\hat{k})$ is usually scaled between 0 and 1 and is dimensionless, T_SL represents the sampling period (in hours), and τ_r and τ_d represent the time constants of Process SL during wakefulness and sleep, respectively.

Process CI is independent of any sleep/wake history and represents a self-sustaining oscillator with a 24-hour period. The definition of $C I (\hat{k})$ is introduced in Definition 2:

Definition 2.

C I (\hat{k}) = \sum_{\hat{i} = 1}^{5} {\hat{a}}_{\hat{i}} \sin (\frac{\hat{i} 2 π}{τ} ((\hat{k} - 1) T_{S L} + ϕ))

(4)

where $C I (\hat{k})$ is usually scaled between 0 and 1 and is dimensionless, $C I (\hat{k})$ denotes a periodic function represented by a five-harmonic sinusoidal equation that approximates the circadian oscillator under entrained conditions, and τ denotes the time period of the circadian oscillator (24 hours). â_î, where î = 1, …, 5, represents the amplitude of the five harmonics of the circadian process (â₁ = 0.97, â₂ = 0.22, â₃ = 0.07, â₄ = 0.03 and â₅ = 0.001) [1] and ϕ denotes the initial circadian phase.

Let $C A P (h_{k}, \hat{k})$ denote the task capability at some discrete time $\hat{k}$ , which is performed by a fatigued human h_k. It is represented by the additive interaction of the homeostatic pressure for sleep and the circadian rhythm input in Definition 3:

Definition 3.

\begin{array}{l} C A P (h_{k}, \hat{k}) = α S L (\hat{k}) + \hat{β} C I (\hat{k}) \\ = α - α S L (0) γ^{\hat{k} - 1} \\ + \hat{β} \sum_{\hat{i} = 1}^{5} {\hat{a}}_{\hat{i}} \sin (\frac{\hat{i} 2 π}{τ} (- (\hat{k} - 1) τ_{r} \ln γ + ϕ)) . \end{array}

(5)

where α and $\hat{β}$ denote real-valued positive parameters that control the relative effect of the two processes on performance.

$C A P (h_{k}, \hat{k})$ , representing the FAP model, describes how long the human h_k can handle tasks in hours at time $\hat{k}$ . Since the human occupied vehicle has limited speed and the visitation place has limited range, the duration of task capability can be translated as a limited number of visitation places.

The challenge is to correctly estimate the five unknown model parameters α, $\hat{β}$ , $γ$ , γ, SL(0) and ϕ. It is assumed that semi-structured questionnaires are designed, and the humans are subject to semi-structured questionnaires via a PDA [9] after certain periods of total sleep deprivation, whereby the data from the subjects in this study are used to derive the five unknown model parameters in (5). Further research is needed to determine what kinds of simulations are necessary for the questionnaires being mapped to the parameters in the FAP model.

With (5) and the known model parameters, the task capability $C A P (h_{k}, \hat{k})$ is predicted at time $\hat{k}$ . As such, $C A P (h_{k}, \hat{k})$ for agent h_k is updated in 𝒞𝒜𝒫. 𝒞𝒜𝒫 is utilized as a constraint for task allocation in a cooperative human-robot team. The allocation strategy is described in the following section.

2.3. A SCA

Steps 1 and 10 takes into account the task capability 𝒞𝒜𝒫 from the FAP model at time $\hat{k}$ in the following description of a SCA.

The auctioneer partitions 𝒯 into k clusters to form an initial allocation A⁽⁰⁾ = a₁⁽⁰⁾, a₂⁽⁰⁾, …, a_k⁽⁰⁾ with the task capability 𝒞𝒜𝒫⁽⁰⁾, where each cluster a_s⁽⁰⁾ is an unordered subset of 𝒯. Let 𝒜 = 𝒜⁽⁰⁾ and 𝒜^* = 𝒜⁽⁰⁾ (𝒜 is the current algorithm allocation, while 𝒜^* is the allocation that has the lowest cost).

Each agent h_p ∊ ℋ (p = 1, 2, …, k) uses a “constrained Prim's Algorithm” (a greedy algorithm) to efficiently approximate the cost c_p(a_p) and submits its cost to the auctioneer. During this bid valuation stage, each cluster a_p becomes an ordered subset of 𝒯. The auctioneer computes the global cost 𝒞(𝒜) using (2) and sets the temperature 𝒯 to a high initial value T₀.

The auctioneer randomly selects two agents h_s and h_t for either transfers or swaps and lets ℋ = h_s, h_t.

Each agent h_p ∊ ℋ constructs an adjacency graph 𝒢(a_p) = 〈(a_p), ε(a_p)〉 for each cluster a_p, where ε(a_p) is the edge set of 𝒯(a_p).

Each agent h_p ∊ ℋ submits l_min(a_p) to the auctioneer, where $l_{m i n} (a_{p}) = \min_{e ∊ ℰ (a_{p})} l (e)$ , and l(e) denotes the Euclidean length of the edge e.

For each e ∊ ε(a_p) (p = s, t), the agent turns the edge e off (such that the tasks at the end of the edges are no longer considered connected) with a probability 1 − p_e, e.g., $p_{e} = \frac{l_{m i n}}{l (e)}$ , where l_min = l_min(a_p). For p = s, t this results in the decomposition of a_p ∊ A into n_p connected components a_pi, such that $a_{p} = \cup_{i = 1}^{n_{p}} a_{p i}$ .

The auctioneer collects all the connected components in the set 𝒞𝒫.

With a 50%-50% probability, the auctioneer selects either a transfer or a swap.

Algorithm 1 describes the mechanism of SCAs within the framework of FAP.

Connected Component Transfer: Randomly select a connected component a_si ∊ 𝒞𝒫 from agent h_s with a probability in P(a_si CP), e.g., $P (a_{s i} | C P) = \frac{1}{C P}$ in a uniform distribution. Assume that a_si is reassigned to agent h_t with a probability in P(A(a_si) = t a_si, A), e.g., $P (A (a_{s i}) = t | a_{s i}, A) = \frac{1}{k}$ in a uniform distribution, resulting in the new allocation 𝒜_i^(s,t) which has two modified clusters a_s⁽⁻ⁱ⁾ and a_t⁽⁻ⁱ⁾. Assume that agent h_s computes c_s(a_s⁽⁻ⁱ⁾) and that for t = 1, 2, …, k (t ≠ s) agent h_t computes c_t(a_t⁽⁺ⁱ⁾), which the auctioneer uses to compute the corresponding cost C(A_i^(s,t)) (based on (2)). If the agent h_p (p = s, t) is human and $| c_{s} (a_{s}^{(- i)}) | \geq C A P (h_{s}, \hat{k})$ or $| c_{t} (a_{t}^{(+ i)}) | \geq C A P (h_{t}, \hat{k})$ , go to Step 3. Otherwise, the probability α_𝒮(𝒜 → 𝒜_i^(s,t)) of the acceptance of the transfer of the connected component a_si from agent h_s to agent h_t is computed (omitted for simplicity). If 𝒞(𝒜_i^(s,t)) is less than 𝒞(𝒜^*), then the new 𝒜^* is updated to 𝒜_i^(s,t).

Connected Component Swap: Select two connected components in a_s and a_t, one connected component a_si from agent h_s with a probability in 𝒫(a_si 𝒞𝒫) and the other connected component a_tj from agent h_t with a probability in 𝒫(a_tj 𝒞𝒫), and swap them, resulting in the new allocation 𝒜_i,j^(s,t) which has two modified clusters $a_{s}^{(- i, + j)}$ and $a_{t}^{(+ i, - j)}$ . Assume that agent h_s computes $c_{s} (a_{s}^{(- i, + j)})$ and agent h_t computes $c_{t} (a_{t}^{(+ i, - j)})$ , which the auctioneer uses to compute the corresponding cost $C (A_{i, j}^{(s, t)})$ (based on (2)). If the agent h_p (p = s, t) is human and $| c_{s} (a_{s}^{(- i, + j)}) | \geq C A P (h_{s}, \hat{k})$ or $| c_{t} (a_{t}^{(+ i, - j)}) | \geq C A P (h_{t}, \hat{k})$ , go to Step 3. Otherwise, the probability $α_{D} (A \to A_{i, j}^{(s, t)})$ of swapping the two connected components is computed (omitted for simplicity). If C(A_i,j^(s,t)) is less than C(A^*), then the new A^* is updated to A_i,j^(s,t).

Algorithm 1 Principal Mechanisms for the Non-greedy and Greedy Versions of a SCA within the Framework of FAP

Initialize the annealing suite. repeat Randomly select 2 agents for re-clustering Stochastically propose a re-clustering for the selected agents. if the cost is beyond the capability of human then Go to Step 3. end if Decide whether to accept the proposed cluster. if the solution is better (for greedy SCAs only) then Accept. else Accept with an acceptance probability. end if Update the annealing suite. until the termination is reached

For the non-greedy SCA, the auctioneer accepts the proposal with probability α_S(𝒜 → 𝒜_i^(s,t)) or α_𝒟(𝒜 → 𝒜_i,j^(s,t)) or 𝒫_𝒮(i, s, t, 𝒯) or 𝒫_𝒟(i, j, s, t, 𝒯), while for the greedy SCA the auctioneer accepts the proposal if 𝒞(𝒜_i^(s,t)) or 𝒞(𝒜_i,j^(s,t)) is less than 𝒞(𝒜^*). Then, 𝒜 is updated and the cost 𝒞(𝒜) is updated and stored. Otherwise, the auctioneer declines the proposal and the auctioneer keeps the current configuration.

If the auction evolution termination criterion is satisfied (i.e., 𝒯 < 𝒯_cut, where 𝒯_cut is some threshold temperature), then the auction is terminated and the final allocation is 𝒜^* with final cost 𝒞(𝒜^*) ≤ 𝒞(𝒜⁽⁰⁾). If the criterion is not satisfied, reduce 𝒯, using 𝒯 ← 𝒯/β where β > 1, and go to Step 3.

3. Simulation Results of a SCA for FAP

This section of the paper presents a simulation study for the verification of the SCA within the framework of FAP. First, the simulation setup and the setup metrics are introduced for FAP and a SCA. Then, Section 3.1 presents the simulation results before and after the total sleep deprivation. Afterwards, Section 3.2 concludes the results during the total sleep deprivation.

The simulated data set is generated by running the FAP of (5) with fixed and known parameters and superimposing random noise to emulate the variability observed in human performance, which is assumed to be obtained through PDAs. The five model parameters are configured as α = 30.30, $\hat{β} = 6.35$ , γ = 0.94, SL(0) = 0.82 and ϕ = 6.00. The determination of the model parameters has been validated in [7]. Performance data are generated for 82 hours of total sleep deprivation and sampled once every 2 hours. Data from each simulation is superimposed with random noise sampled from a normal distribution with zero mean and one of three (1, 4, or 16) levels of variance. Ultimately, reliable results are collected from noised measurements by comparing the level of signal to the level of background noise. A signal-to-noise variation ratio is introduced to compare signal with noise.

The measure of the SNVR is performed to compare the level of a desired signal to the level of background noise. The definition of the SNVR is as the reciprocal of the coefficient of variation introduced in Definition 4:

Definition 4. The measure of the SNVR is defined as: $S N V R = \frac{μ}{δ}$ where μ is the signal variance and δ is the level of variance of the background noise.

These variances correspond to signal-to-noise ratios of 59.10 (59.10/1), 14.77(59.10/4) and 3.7(59.10/16), where 59.10 is the variance of the performance data signal simulated in (5) with the above mentioned model parameters for 82 hours¹ [12].

𝒞𝒜𝒫 is utilized as a constraint for the allocation of tasks in a cooperative human-robot team. The simulation setup of the SCA is described as follows. For each simulation of a SCA, the stochastic random scenario appears in a 10000m × 10000m area involving 1,000 random scenarios for a given number of tasks and agents. The initial agent positions were evenly distributed along one edge of the area (when the initial agent positions are distributed differently, e.g., randomly, the qualitative results given below remain the same). Furthermore, for each simulation, the following SCA parameters were used: initial temperature, T = 1000; termination temperature, T_cut = 20; small cooling schedule ratio β = 1.001 with slow annealing, where T and T_cut are a priori knowledge regarding the scenario scale such that they are scenario-dependent. However, they are always the same for different agents, different tasks and different missions in a fixed scenario scale.

The concept of an agent type vector (ATV) is introduced in Definition 5 to measure the different types of agents that constitute a given human-robot team:

Definition 5. Let at(p) denote a type p agent for p ∊ 1, 2, …, v, where at(p) ≠ at(q) for p ≠ q. Assume that a team consists of k agents, where k ≥ v, and that m(p) denotes the number of agents of type at(p). The ATV for this k-agent team is denoted by M(k) and defined by: M(k) = [m(1) m(2) … m(i) … m(v)], where $\sum_{p = 1}^{v} m (p) = k$ .

The cost function is a MinMax cost function, as in (2), corresponding to the maximum time taken to accomplish the tasks. The speeds for each of the agents were assumed to be constant and were chosen randomly from the speed set 25m/s, 20m/s, 10m/s, 1m/s. In the subsequent simulations, v < 4 (i.e., the number of agent types is at most four), the agents were assumed to differ in terms of their speed of travel and whether they are human or not. In particular, at(1) travelled at 25m/s, at(2) travelled at 20m/s, at(3) at 10m/s and at(4) at 5m/s. at(1) is human occupied vehicle and the others are robots. Table 1 shows the assumed ATVs when the number of agents k varies from 2 to 10. The auctioneer was assumed to be of type at(2).

Table 1.
Assumed ATV, as the number of agents varies from 2 to 10 and at(1) is human occupied vehicle

No. of agents (k) ATV

2 M(2)=[1 1 0 0]

3 M(3)=[2 1 0 0]

4 M(4)=[2 1 1 0]

5 M(5)=[2 2 1 0]

6 M(6)=[2 2 2 0]

7 M(7)=[2 2 2 1]

8 M(8)=[2 2 2 2]

9 M(9)=[3 2 2 2]

10 M(10)=[3 3 2 2]

No. of agents (k)	ATV
2	M(2)=[1 1 0 0]
3	M(3)=[2 1 0 0]
4	M(4)=[2 1 1 0]
5	M(5)=[2 2 1 0]
6	M(6)=[2 2 2 0]
7	M(7)=[2 2 2 1]
8	M(8)=[2 2 2 2]
9	M(9)=[3 2 2 2]
10	M(10)=[3 3 2 2]

The next section will illustrate the costs of SCA before and after total sleep deprivation by prediction in the FAP model.

3.1. Simulation Results when Human Fatigue is Considered or Not Considered

In the subsequent simulations, the number of agents was variable. In particular, 1,000 random scenarios were again studied for a given number of agents and tasks, with the number of agents now ranging from two to 10 and the number of tasks ranging from 10 to 260 in increments of 10.

Figure 1 displays the costs of the SCA as a function of the number of agents and tasks when human fatigue is considered and not considered. It shows that, where human fatigue is considered, an additional number of agents is required to achieve the same level of overall performance. For example, in Figure 1(c) (which shows the costs for 200 tasks), if human fatigue is not taken into account, the cost corresponding to two agents is 217 hours, while similar costs are required for four agents to achieve the same level of mixed team performance if human fatigue is considered after total sleep deprivation. In contrast, consider Figure 1(d): two agents are required for the team performance cost in 100 hours if human fatigue is not considered, while three agents are required to maintain the same level of team performance if human fatigue is considered. The reason is that the sacrifice of adding robotic agents leverages the impaired individuals. In general, for a fixed number of tasks, the corresponding “slice” of a 3-D curve, such as in Figures 1(c) and 1(d), may be used to determine how human fatigue influences the choice of the number of agents in ATVs, and hence provides a guideline for choosing the number of agents in ATVs for the mission.

Figure 1.

Mean cost vs. the number of agents and the number of tasks for the SCA with FAP and the ATVs in Table 1

Comparison of the predicted costs of Figure 1 reveals that, when the number of tasks is large, the FAP model has a substantial impact on the performance of the mixed team. For example, in Figure 1(c) (which shows the costs for 200 tasks), the cost ranges in [0.7,217.5] hours if human fatigue is not considered, while the cost ranges in [1.1,523.4] hours if human fatigue is considered. This is a cost increase of [30.5%,140.6%], due to the number of tasks being far beyond the task capability of impaired individuals at the specified speed at(1). It should also be noted that the FAP model presented here can be used to predict mixed team performances based on fatigued individuals for other task and agent numbers. This capability is displayed in the next section, which shows the costs of the SCA as a function of the sleep deprivation time.

3.2. Simulation Results During Total Sleep Deprivation

Given specific ATVs and numbers of tasks, the costs of the SCA are a function of the sleep deprivation time. Figure 2 shows the simulated task capability profiles for the group and the various individuals at specified ATVs for 200 tasks. They are collected every two hours during 82 hours of total sleep loss for 200 tasks and 1,000 random scenarios. The simulated performance is represented with a signal-to-noise ratio of 14.77. The group profile is averaged for 11 people and the individual profile is a representative, single individual.

Figure 2.

Task capability of FAP in a group and for an individual collected every two hours during 82 hours of total sleep loss for 200 tasks and 1,000 random scenarios

The trend transitions of cost with respect to TIME AWAKE can be observed from Figure 2, such that cost increases as TIME AWAKE increases. Since the cost represents the task capability of a given human agent, it reveals that a human agent's capability degenerates as TIME AWAKE increases. This trend is characterized by four major phases, corresponding to three transition stages and four levels. A transition stage represents a time segment where the task capability rapidly degenerates, while a level represents a relatively stable range of magnitude for human task capability.

Phase I: The task starts at level I, and transition I takes place from hour 12 to hour 14. At hour 12, it sees a distinct degeneration as the cost rapidly increases to a higher level, called ‘level II’. This first transition happens within a very short time (i.e., about two hours), until hour 14. During the transition, cost jumps from 224 to 228 for M(2), 118 to 134 for M(3), and 1.38 to 1.52 for M(8), as shown in Figure 3.

Figure 3.

The costs of the SCA as a function of sleep deprivation time collected every two hours during 82 hours of total sleep loss for 200 tasks and 1,000 random scenarios

Phase II: Level II starts around hour 14, followed by transition II from hour 30 to hour 40. During transition II, the cost increases from 234 to 266 for M(2), 124 to 138 for M(3), and 1.46 to 1.64 for M(8).

Phase III: Level III starts at hour 40 and lasts until hour 48, followed by transition III from hour 48 to hour 56. During the transition, the cost jumps from 268 to 298 for M(2), 136 to 166 for M(3), and 1.64 to 1.65 for M(8).

Phase IV: For the remainder, the task capability is unable to maintain a relatively smooth pattern, oscillating randomly for the rest of the hours. The cost oscillates throughout as well.

We generalize the above observations with three main points: 1) the total TIME AWAKE has a negative effect on human agent task capability throughout. 2) TIME AWAKE's effect on human agent task capability can be classified in in terms of three stages with four levels. 3) TIME AWAKE's effect on human agent task capability takes conforms to two patterns: a rapid transient pattern and a gradual transition pattern. 4) When TIME AWAKE exceeds a limit (80 hours in a one hour simulation), the human agent is allocated few (or no) tasks and the SCA cost approaches a constant value.

From Figure 3, it is of interest to predict the performance of the SCA under the constraints of FAP model. There are two critical performance times: 20 hours and 52 hours. Before 20 hours, the FAP model has only a slight limitation effect on the costs of the SCA, while after 52 hours the FAP model has a great impact on the costs of the SCA because the human's capacity to handle tasks deteriorates as the sleep deprivation time increases.

4. Summary

Based on the results of this paper and the simulation gained in developing these results, we propose a systematic engineering approach to human-robot system task allocation using a SCA under FAP. It is assumed that a mission is given in which the physical scale of the distribution of tasks is known, along with the range of the number of tasks. It is also assumed that a set of candidate agents is potentially available for the mission, and guidelines are provided as to how human fatigue influences the choice of the number of agents. The approach is presented below in six steps.

Semi-structured Questionnaires to Derive the Five Unknown Model Parameters. Semi-structured questionnaires are designed, and the humans are subject to the semi-structured questionnaires via a PDA [9] following certain periods of total sleep deprivation, with the data from the subjects in this study used to derive the five unknown model parameters in FAP. Further research is needed to determine what kind of simulations are necessary in questionnaires to be mapped to the parameters.

Task Capability to Predict and Update. With the known model parameters obtained from Step 1 in FAP, the task capability is predicted and updated in the task capability. It is utilized as a constraint to bound the proposed movement of tasks allocated in a cooperative human-robot team.

Simulations to Determine Annealing Parameters. The humans and robots treat each other as partners in a collaborative human-robot team. For the human-robot task allocation problem considered in both this and prior SCA research, it has been observed that the choice of the annealing suite {T₀,T_cut,β} depends largely on the physical scale of the area over which the tasks are distributed, rather than on the number of tasks or the number of agents (it is revealed that different types of task allocation missions will have similar invariance [22]). Hence, T₀, T_cut and β may be chosen based on a relatively small number of randomly distributed tasks and - initially - randomly distributed agents, as long as the area of the task distribution is as that envisioned for the actual mission. For this problem, it feasible to solve for an optimal or nearly optimal task allocation using a combinatorial algorithm. Using non-greedy centralized SCA, this knowledge is helpful in using trial and error to choose T₀ and T_cut and determining values of β that correspond to slow and fast annealing. Slow annealing should yield a near optimal task allocation, while fast annealing should converge quickly (though with noticeable improvement over the initial task allocation, which will typically be chosen to be the best solution resulting from a suite of fast, greedy auctioning algorithms). T₀ and T_cut are not expected to change in the following steps, but β may be chosen for slow annealing, fast annealing or something in between.

Simulations to Determine the Mission Agents. Because the exact tasks to be performed are not known a priori, stochastic simulations are chosen to represent the possible task distributions and the number of tasks in the actual mission. The numbers of the different types of agents (and possibly their initial locations) are systematically varied in simulation. A non-greedy centralized SCA, using β chosen for slow annealing (or faster annealing if time does not permit), is then used to compute a (multi-dimensional) table that shows the expected cost vs. distribution of the numbers of each agent-type.

Task Allocation at the Beginning of the Mission. The agent team was determined in Step 4. At the beginning of an actual mission, it is assumed that a set of tasks are actually known and need to be assigned to the agents. Assuming full communication between agents, we can choose a non-greedy centralized SCA with β chosen for slow annealing (or faster annealing if time does not permit) to develop the initial task allocation under the constraints of task capability in FAP.

Task Allocation During the Mission. Once the mission commences, distributed auctioning using a greedy SCA with β chosen for fast annealing (or slower annealing if the time and communication are available) is used to reallocate tasks under the constraints of task capability in FAP, as the tasks and costs change during the mission.

5. Final Discussion

This paper first integrates a human fatigue model in a novel, mixed team coordination framework, and then uses this model to predict human performance under time constraints. The human fatigue model is a FAP model, which uses a bio-mathematical two-process model to predict the task capability and performance for human individuals and human-robot teams. A SW²SCA, based on a modified Swendsen-Wang method in a suite of SCAs, is utilized in the mixed team coordination framework to allocate and reassign tasks. It enables complex and efficient movements between clusters by connecting tasks that appear to be synergistic, and then stochastically reassigning these connected tasks. In the SW²SCA, the auctioneer makes stochastic movements with either homogeneous or heterogeneous agents.

The FAP model is validated in the presence of degradation in human capacity and provides a guideline for fatigue prediction in actual field operations relating to a mixed team's performance. The random simulation for a centralized SCA shows how human fatigue influences the choice of the number of agents. This enables an appropriate choice of the number of agents for a given mission that has an expected number of tasks when human fatigue is considered.

Footnotes

6.

This work was sponsored by the Army Research Office under grant W911NF-09-1-0568.

1

82 hours is chosen in consideration of extreme conditions of deprivation of sleep for humans.

References

[1] Achermann

Borbély

(1994) Simulation of daytime vigilance by the additive interaction of a homeostatic and a circadian process. Biol. cybern. 71(2):115–121.

[2] Achermann

Borbély

(2003) Mathematical models of sleep regulation. Front. biosci. 8:683–693.

[3] Borbély

(1982) A two process model of sleep regulation. Hum. neurobiol. 1(3):195–204.

[4] Chao

Golden

Wasil

(1993) A new heuristic for the multidepot vehicle routing problem that improves upon best-known solutions. Amer. j. math. management sci. 13(3–4):371–406.

[5] Dias

(2004) TraderBots: A New Paradigm for Robust and Efficient Multirobot Coordination in Dynamic Environments [PhD thesis]. Pittsburgh, PA: Robotics Institute, Carnegie Mellon University.

[6] Dias

Stentz

(2002) Opportunistic optimization for market-based multirobot control. In: Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2002); 2002 Sept 30-Oct 4; EPFL, Switzerland. IEEE Press. 3:2714–2720.

[7] Dongen

XMott

Huang

Mollicone

McKenzie

Dinges

(2007) Optimization of biomathematical model predictions for cognitive performance impairment in individuals: Accounting for unknown traits and uncertain states in homeostatic and circadian processes. SLEEP. 30(9):1129–1143.

[8] Edgar

Dement

Fuller

(1993) Effect of scn lessions on sleep in squirrel monkeys: Evidence for opponent processes in sleep-wake regulation. J. neurosci. 13(3):1065–79.

[9] Fong

Thorpe

Baur

(2001) Advanced interfaces for vehicle teleoperation: Collaborative control, sensor fusion displays, and remote driving tools. Auton. robot. 11(1):77–85.

10.

[10] Kirkpatrick

Gelatt

Vecchi

(1983) Optimization by simulated annealing. Science. 220(4598):671–680.

11.

[11] Lindlof

Taylor

(2002) Qualitative Communication Research Methods. Sage Publications, Inc., 2nd edition. 400.

12.

[12] Rajaraman

Gribok

Wesensten

Balkin

Reifman

(2008) Individualized performance prediction of sleep-deprived individuals with the two-process model. J. appl. physiol. 104(2):459–68.

13.

[13] Robert

Casella

(2005) Monte Carlo Statistical Methods (Springer Texts in Statistics). Secaucus, NJ, USA: Springer-Verlag New York, Inc. 629.

14.

[14] Wagner

Arkin

(2004) Multi-robot communication-sensitive reconnaissance. In: Proceedings of the IEEE International Conference on Robotics and Automation. 2004 April 26-May 1; New Orleans, LA. IEEE. pp. 4674–4681.

15.

[15] Wilcox

Ambrose

Kumar

(2006) Space Robotics in International Assessment of Research and Development in Robotics [Internet]. Baltimore, Maryland: WTEC, Inc.; Jan 2006[updated 10 Feb 2013; cited 10 Apr 2014]. Available from: http://www.wtec.org/robotics/report/screen-robotics-final-report-highres.pdf. Accessed on 15 May 2014.

16.

[16] Dong

Luo

Nagano

(2010) Adaptive attitude control of redundant time-varying complex model of human body in the nursing activity. J. rob. mech., 22(4):418–429.

17.

[17] Zhang

Collins

Shi

Liu

Chuy

(2008) A stochastic clustering auction for centralized and distributed task allocation in multi-agent teams. In: Asama

Kurokawa

Ota

Sekiyama

. Distributed Autonomous Robotic Systems 8. Tsukuba, Ibaraki, Japan: Springer. pp. 345–354.

18.

[18] Zhang

Collins

Barbu

(2010) A novel stochastic clustering auction for task allocation in multi-robot teams. In: 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010). 2010 Oct 18–22; Taipei, Taiwan. IEEE. pp. 3300–3307.

19.

[19] Zhang

Collins

Barbu

(2011) Efficient stochastic clustering auctions for agent-based collaborative systems. In: Proceedings of the Workshop on Agent Technology in Robotics and Automation. 2011 International Conference on Robotics and Automation (ICRA). 2011 May 9–13; Shanghai, China. IEEE.

20.

[20] Zhang

Collins

Barbu

(2012) An efficient stochastic clustering auction for heterogeneous robot teams. In: 2012 IEEE International Conference on Robotics and Automation (ICRA). 2012 May 14–18; Saint Paul, MN, 2012. IEEE. pp. 4806–4813.

21.

[21] Zhang

Collins

Shi

(2012) Centralized and distributed task allocation in multi-robot teams via a stochastic clustering auction. ACM t. auton. adap. sys. 7(2):21:1–21:22.

22.

[22] Zhang

Collins

Barbu

(2013) An efficient stochastic clustering auction for heterogeneous robotic collaborative teams. J. intell. robot. syst. 72(3–4):541–558.

23.

[23] Powel

Morgansen

(2012) Multiserver queueing for supervisory control of autonomous vehicles. In: American Control Conference. 2012 Jun; MontrŐal, Canada. pp, 3179–3185.

24.

[24] Srivastava

Surana

Eckstein

Bullo

(2013) Mixed Human-Robot Team Surveillance [Internet]. Nov 2013 [updated Nov 2013; cited 10 Jan 2014]. Available from: arxiv.org/pdf/1311.2796. Accessed on 15 May 2014.

Human-robot Team Coordination That Considers Human Fatigue

Abstract

Keywords

1. Introduction

1.1. Related Works

1.2. Outline

2. Preliminaries

2.1. Task Allocation Problem Statement

3. Simulation Results of a SCA for FAP

Table 1. Assumed ATV, as the number of agents varies from 2 to 10 and at(1) is human occupied vehicle No. of agents (k) ATV 2 M(2)=[1 1 0 0] 3 M(3)=[2 1 0 0] 4 M(4)=[2 1 1 0] 5 M(5)=[2 2 1 0] 6 M(6)=[2 2 2 0] 7 M(7)=[2 2 2 1] 8 M(8)=[2 2 2 2] 9 M(9)=[3 2 2 2] 10 M(10)=[3 3 2 2]

5. Final Discussion

Footnotes

6.

1

References

Table 1.
Assumed ATV, as the number of agents varies from 2 to 10 and at(1) is human occupied vehicle

No. of agents (k) ATV

2 M(2)=[1 1 0 0]

3 M(3)=[2 1 0 0]

4 M(4)=[2 1 1 0]

5 M(5)=[2 2 1 0]

6 M(6)=[2 2 2 0]

7 M(7)=[2 2 2 1]

8 M(8)=[2 2 2 2]

9 M(9)=[3 2 2 2]

10 M(10)=[3 3 2 2]