{'fraction_non_alphanumeric': 0.034478620855165794, 'fraction_numerical': 0.006799728010879565, 'mean_word_length': 4.424604035582556, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cooperative Queuing Policies for Effective Human-Multi-Robot Interaction

We consider multi-robot applications, where a team of robots can ask for the intervention of a human operator to handle difficult situations. As the number of requests grows, team members will have to wait for the operator attention, hence the operator becomes a bottleneck for the system. Our aim in this context is to make the robots learn cooperative strategies to decrease the time spent waiting for the operator. In particular, we consider a queuing model where robots decide whether or not to join the queue and use multi-robot learning to estimate the best cooperative policy. In more detail, we formalize the problem as Decentralized Markov Decision Process and provide a suitable state representation, so to apply an independent learners approach. We evaluate the proposed method in a robotic water monitoring simulation and empirically show that our approach can significantly improve the team performance, while being computationally tractable.


Introduction
In many multi-robot scenarios, such as environmental monitoring [23] or search and rescue [24,11], one or few operators are required to interact with a team of robots to perform complex tasks in challenging environments. Robots, specially at field sites, are often subject to unexpected events, that can not be managed without the intervention of operators. For example, in an environmental monitoring application, robots might face extreme environmental events (e.g., water currents) or moving obstacles (e.g., animal approaching the robots). In such scenarios, the operator often needs to interrupt the activities of individual team members to deal with particular situations.
The operator's monitoring and supervisory role in these scenarios becomes critical, particularly when the team size grows larger. To decrease the operator's monitoring task and give him/her more time to focus on robots that need attention, several approaches consider the concept of self-reflection [19], where robots are able to identify their potential issues and ask for the intervention of the operator by sending a request. However, large teams can easily overwhelm the operator with several requests, hence hindering the team performance. Consequently, team members have to wait for the operator's attention, and the operator becomes a bottleneck for the system. Queuing is a natural way to manage and address this problem. Previous research try to enhance the performance of the system (i.e., decreasing the time spent by robots waiting for the operator) considering various queue disciplines (e.g. First in First Out (FIFO) and Shortest Job First (SJF)) [13,4] or prioritizing such requests [17]. In both cases, the queue size may grow indefinitely as no robot will leave the queue before receiving the operator's attention.
To deal with this problem, we focus on balking queue model [14], in which the users/agents (i.e robots requesting attention) can decide either to join the queue or balk. Such decisions are typically based on a threshold value, that is computed by assigning a generic reward for receiving the service and a cost for waiting in the queue to each agent. When applying this model to a robotic application, there is no clear indication how such thresholds can be computed. More important, this model does not consider the cost of balking (i.e. the cost of a potential failure that robots can suffer by trying to overcome difficult situations without human intervention). Considering this, our focus is to devise an approach that allows the team of robots to learn cooperative balking strategies to make better use of a shared queue. Therefore, we frame the above problem as a Decentralized Markov Decision Process (Dec-MDP) in which, the team of robots must cooperate to optimize the team idle time. Finding optimal decentralized policies is often hard due to the partial observability and limited communications. Thus, our goal is to provide a scalable state representation by adding the state of the queue as an extra feature to the robots' local states and solve the underlying Dec-MDP problem using multiple independent learners 1 . We illustrate that, this additional feature will improve the team performance over our main evaluation metric (i.e. team idle time). In more detail, this paper provides the following contributions to the state of the art: (i) We model the human-multi-robot interaction as a balking queue, in which the robots identify their needs and decide whether to interrupt the human operator or not. (ii) We formalize the problem as Dec-MDP and provide a tractable state representation to learn the balking policies for each robot. (iii) Finally, we evaluate the performance of our model by comparing the team idle time to the state-of-theart queue disciplines. Overall, the experimental results show that, the use of our model decreases the total idle time upto 68% over FIFO (without balking) and increases the team reward upto 56% comparing to the other learning models.

Background
In this section, first we review the state of the art in robotic studies, where robots ask for operator's attention. Afterwards, we present a brief introduction to the Balking Queue [14] model in which, users/agents decide to join the queue or not. Then, we present a brief review of Dec-MDP [1,7] as the basis model for decision making under uncertainty in multi-robot scenarios.

Human-Multi-Robot Interaction
Human-multi robot interaction is an active field of research with many different research issues, including team plan rep-1 Some part of this work appears in [16]. That work describes basic ideas and preliminary results, here we provide a more detailed description of the methodologies, and more extensive empirical analysis. resentation [22,12], multi-modal interaction [20,8] and mixed initiative planning [2]. Here, we consider approaches, which focus on how to allocate operator attention to a set of robots. Many work in this area consider that, the robots can perceive their situations and inform or ask the operator for help. For example, the work by [18] proposes the idea of a single service robot asking for the help of humans.
Considering larger multi-robot teams with small number of operators, several robots may need the operator's attention at the same time. Hence, the requests must be queued for being processed later on. Authors in [4,13] explore different queue disciplines to enhance the performance of the system. However, keeping robots idle until the operator becomes available might decrease the overall team efficiency. In contrast, we focus on a specific queuing model with balking property [14], where robots decide either to join the queue or not.
The concept of Adjustable Autonomy or mixed initiative has been the basis of many research in the field of humanmulti-robot interaction. The key issue in this setting is to devise effective techniques to decide whether a transfer of control should occur and when this should happen. Different techniques have been proposed to address this challeng, for example, [10,5,21] consider that the robot will ask for human help/intervention when the expected utility of doing so is higher than performing the task autonomously, or when the uncertainty of the autonomous decision is high [9,3] or when the autonomous decision can cause significant harm [6]. However, these decision making solutions usually have been considered as individual one-step decisions without considering the long-term cost or the consequences of decisions on other team members (if any). Our work also belongs to the this category, where autonomous robots in a multi-robot scenario can decide whether to wait for the operator or not. In particular, we focus on a specific queuing model with balking property [14]. However, our focus is on finding cooperative strategies, where all robots learn concurrently to optimize the idle time of the system.

Balking Queue Model
The first mathematical model of a queuing system with rational users was formulated by Naor [14]. In his model, users upon their arrival decide according to a threshold value whether to join the queue or not (balk). The individual's optimizing strategy is straightforward, a customer will join the queue while n other customers are already in the system if where a uniform cost C for staying in the queue and a similar reward R for receiving service are assigned to each user and µ is the intensity parameter of exponentially distributed service time. Thus, n = Rµ C serves as a threshold value for balking, that is if the number of users waiting in the queue is greater than n, the newly arrived user will not join the queue. In a multi-robot application, this threshold and decision must be computed carefully. Our focus is on showing how the elements (i.e. reward and cost) of balking strategy should be adjusted according to a practical robotics scenario.

Decentralized Markov Decision Process (Dec-MDP)
The decision of whether to join the queue or not for each situation of each robot will impact the future decisions of the entire team. As a result, we are concerned here with team sequential decision making problems, in which the team's utility depends on a sequence of decisions.
A Dec-MDP is defined by a tuple S, A, P, R where: S is the set of world states which is factored into n components, S = S 1 ×...×S n . In a special case (i.e. Factored n-agent Dec-MDP), S i refers to the local state of agent i. In Dec-MDP, the state is jointly fully observable which means that the aggregated observations made by all agents determines the global The complexity of Dec-MDP is nondeterministic exponential (NEXP) hard [1], hence learning is crucial.

Problem Formulation
We consider a water monitoring scenario, where several autonomous surface vessels are supervised by a human operator (see Fig. 1). A set of events can happen to the platforms, such events may affect the normal behavior of the platforms and hinder their performance. Each event has a different probability of failure (see Table 1), where requests with the higher probability of failure are more crucial to receive the operator's attention Following previous works [4,13], a central queue is provided to both the operator and the boats, where the operator can select one request at a time (i.e., in FIFO order) and assigns a specific sub-mission to resolve that request. A submission is a plan specific recovery procedure, and this often requires a human interaction (i.e., the human directly selects which platforms should execute the interrupt submission). We used three sub-missions, one for each class of requests, including: (i) sending a boat to the closest station to change/charge its battery. (ii) allowing/not-allowing a boat to go further (to the area that it might loose connection), and (iii) teleoperating a boat for traversing a specific area. We assume that, whenever an event happens, the platform can detect the event. For example, a robot can perceive that its battery level is in a critical state, it must then decide whether to join the queue (i.e. sending the request and waiting for the operator) or balk (i.e., not sending the request) 2 . The consequences or costs of balking are problem specific. In our model, when a failure happens, the operator should spend more time to fix the problem, hence failure as a result of balking, increases the idle time of the system. The goal is to minimize the time spent in the queue.
Our proposal is then to train the robots in a stationary environment (i.e., stationary distribution functions with fixed arrival rate and service time), so that the robots can learn appropriate balking policies. Then, by applying the learned policies in similar scenarios, they will be able to optimize the team objective. More specifically, we consider the following model in our domain: The state space S = S 1 × S 2 × ... × S n . n is the number of boats. The local state of each boat S i is a tuple S b , N tasks . N tasks shows the number of remaining tasks of boat i. In this application domain, each task is a location that should be visited by a specific boat. S b is the current internal state of boat i. More specifically S b ∈ {E j , Waiting, Failed, Autonomy}, where E j refers to on of the request/event type in Table 1. For example, the state tuple of a boat when it has 3 tasks to finish and the event Battery Recharge occurs, would be s = E 1 , 3 . A i is the set of actions for boat i where A i ∈ {Join, Balk}. The reward function is designed to decrease the idle time (i.e. the time spent waiting for the operator).
In general, there are two major approaches for learning in multi-robot scenarios [15]. The first approach is called team learning and uses a single learner to learn the behavior for the entire team. In contrast, the second approach uses multiple concurrent learners, usually one for each robot, where each learner tries to learn its behavior. Each of these methods has its own advantages and disadvantages which make it preferable in different domains [25,15]. In particular, the major problems with team learning approach are the explosion of the state space (i.e., it keeps the states of the entire team), and the centralization of the learning approach that needs to access the states of all team members. Using the team learner in our application, the state space will be very large which decelerates the convergence to the optimal value. For example, for 5 boats with the above state representation, the state space will include more than one million states, hence requiring a prohibitive long time to estimate the optimal strategies for each state and action permutations. The main advantage of independent learners in our domain is that, this domain can be decomposed into subproblems (e.g. each boat holds its own state space) and each subproblem can be solved by one boat. In general, two main challenges arise in concurrent learning: credit assignment and non-stationary dynamics of the environment [15]. However, our application scenario has some special properties, that can be exploited to design a tractable model. First, the action selection at each step (i.e. when an event happens) only requires one agent to select either to join or balk. Hence, the reward can go directly to that agent. It is different from the situations, where all agents should decide at each step (i.e. joint actions), which results in the well-known credit assignment issue. However, when each boat considers only its local state without knowing the state of the queue, finding the optimal behavior for the team may become impossible, or the model may compute lower quality solutions. Therefore, we add the state of the queue to the local state of each boat, and then we use independent learners approach. To sum up, we consider three possible models: Team Learner (TL): a team learner has access to the joint state of all robots which is S = S 1 × S 2 × ... × S n . When an event happens to a boat, the action Join, Balk for the corresponding boat will be selected and the state of the system will be updated. The update will only change the part of the state related to the corresponding boat. The Q-value of the team learner will be updated accordingly. Independent Learners -Unobservable Queue (IL-U): an independent learner) is used for each boat. Each boat observes only its local state S i = S b , N tasks . In this model, each boat updates its local Q-values interacting to the system and receiving the reward. Independent Learners -Observable Queue (IL-O): in this model, each boat in addition to observing its local state, has access to the size of the queue. The queue size shows the number of waiting boats inside the queue. The state representation of each boat in this model is: S i = S b , N tasks , S q . These models are different in their state representation, while the reward structure is the same for all of them: µ andλ are average service time and events arrival rate respectively. N q is the number of boats waiting, and t serv is the average time needed to resolve the request. R S = 1, R F = −2 and R T = 0.3 are application specific parameters that must be tuned empirically.
Finally, we use Q-Learning as the basis learning approach, while the same reward structure, same distribution functions for generating events and same distribution function for the service time are used for all models. We use Q-Learning because of its simplicity and good real time performance. Moreover, our goal is to propose the use of reinforcement learning in this novel context and not to provide a novel learning algorithm. In Q-Learning, each learner interacts with the environment (i.e. selects an action), receives the immediate reward and updates its state-action values (i.e. Q-values) as Eq.2: where r i and s are respectively the reward and the state observed by robot i after performing action a i in state s i ; a is the action in state s that maximizes the future expected rewards; α is the learning rate and γ is the discount factor. Notice that, for Team Learner, there is only one Q-table (i.e., table of state-action values) to be updated, where, s i refers to full state representation (i.e. state of all robots) and a i is the action selected by learner for the specific robot with a request. This action will either add the event to the queue or not. As mentioned before, by exploiting specific feature of our domain, we can use an independent learner approach that is tractable and scalable.
In the simulation,λ andμ in the reward function are the same as λ and µ for generating the requests and service. However, for a field deployment, these two parameters should be estimated by considering the average number of events being generated during an interval as lambda (e.g. 20 events have been generated in 1 hour (or 60 minutes)), and the average time spent to fix each request as 1 µ (e.g. 5 minutes to fix each request, hence 12 events can be fixed in 60 minutes).
The state of the queue, S q , can be modified by robots' action (joining the queue) and the operator's action (leaving the queue). However, under the reasonable assumption that an arrival and a departure cannot happen exactly at the same time, only one entity can change the value of S q at a time. Moreover, the possibility of having more than one event at the exact same time is very low. In particular, for our scenario, it is safe to assume that, the time to change the state of the queue, is much lower than the time for a new event arrival. Under this assumption, even if two events happen within a short time interval, the first one will affect the state of the queue before the second arrives, hence the other robots will base their decisions on the updated queue size.

Learning Phase
The learning phase of balking models starts by defining a list of locations (i.e., to be visited), and assigning those locations to boats. We consider 30 locations and 5 boats. Events,   as in table 1, will be generated within an exponential distribution with parameter λ = 0.25. The operator's speed, for resolving a request is selected from an exponential distribution with parameter µ = 0.27. An episode (i.e., a run of the algorithm beginning from a start state to a final state) ends after the system encounters 20 events. For action selection in our model, we use ε greedy method with parameter ε = 0.1. Our algorithm uses the learning rate α = 0.1 and discount factor γ = 0.9 throughout the experiments, which are tuned empirically. Each episode of the learning phase starts with all boats in their Autonomy state (i.e. they do not need the attention of the human operator), then with arrival rate λ an event may happen to one boat. We used a realistic estimation for parameter λ and µ based on some experience on the total mission time, number of boats and number of locations. These numbers define well the type of scenarios we are interested in, where boats can operate most of the time in autonomy, but frequently need user's intervention. Fig. 2 shows the team rewards of each model, TL, IL-U and IL-O, during the learning phase. The oscillation in the reward is due to the fact that, the robots learn their policies by trying new potentially sub-optimal actions. The training time (the sum over 4000+ episodes) for each model was about 88-95 hours. As we expected, the convergence rate of IL-O is much faster than the TL, while they both reach a similar team reward. This is due to the larger state space of TL which needs more iterations to estimate the value for each state and action. Results also clearly show the importance of having access to the state of the queue to make better decisions. Since, the reward given to each action is related to the parameters λ and µ, we expect our policy to be dependent on these two parameters. Fig. 3 shows how IL-O adapts to changes in µ, where we increase and decrease its value by 40% during the learning phase. A sudden rise and drop happen respectively for each value, but then the system converges to a stationary state. Fig. 4 shows another experiment, where we vary the ratio of event types during the learning phase. The events were generated with a uniform distribution up to episode 2150. After that, we vary the percentage of events from type 1(E 1 ), which has the higher probability of failure (see Table 1), while the rest of the events are uniformly distributed among E 2 and E 3 . In more detail, we consider E 1 -100, E 1 -80, E 1 -50, E 1 -10 and E 1 -0, where each shows the rate of E 1 . Fig. 4 illustrates that, as there are more E 1 , the system will gain less reward due to the increasing rate of failures. After several iterations, the learning curve becomes stationary.

Test Phase
After the learning phase, we run 30 simulation executing the policy learned previously. In this first experiment, we use the same values for λ and µ as used during the learning phase. Fig. 5(a) demonstrates the team reward for each learning models. A comparison on team reward between IL-O and IL-U, shows 56% gain for IL-O. Besides, a significant decrease (i.e. 40%) on average waiting time is shown in Fig. 5   which are in their Waiting state (i.e. S b = W). For example, whenever two boats waiting in the queue (assuming the other features, e.g., severity are the same), IL-O will map the state to S q = 2, while TL will differentiate the states depending on which two boats are inside the queue. Since, the boats are homogeneous in our domain, IL-O results in better performance by abstracting away features that do not have a significant impact on the reward. This also makes TL to converge slower than IL-O, due to the larger state space of TL which needs more iterations to estimate the value for each state and action. Next, we compare the behavior of queues with and without balking property (e.g., FIFO and SJF). For FIFO and SJF, we use the same event rate λ and service rate µ. In these two queuing models, boats always join the queue regardless of their request types and the queue size. Fig. 5(c) shows the team idle time for FIFO, SJF and three learning models. FIFO without balking, has the worst performance, since boats wait for the operator until he/she becomes available. In contrast, IL-O approach outperforms all other models. In more detail, it decreases the time up to 68% comparing to FIFO. In general, the results in Fig. 5(c) indicate that, using balking models significantly decreases the idle time of the team even though, some events may result in failures. This is acceptable in our domain, since the penalties for failures are not critical but only result in a finite increase of time.
To validate the noise sensitivity of our proposed model IL-O, we consider a set of experiments as follow. We consider adding the same level of noise, according to a uniform distribution, to both parameters λ and µ during the test phase. Fig. 6 shows the team reward and Fig. 7 shows the team idle time for different levels of noise. The results show that, the approach is able to cope with a significant amount of noise on both λ and µ.

Conclusions
In this paper, we propose the use of balking queue to model human-multi-robot interactions when the autonomy of robots allow them to decide whether to wait for the operator or not. We frame the problem as a Dec-MDP in which, each robot observes its local state and the state of the queue and cooperates with other agents to optimize the use of a shared queue. We apply independent Q-Learning to find these cooperative strategies in a water monitoring multi-robot simulation. We consider three different models (TL, IL-U, IL-O), and our results clearly show that an independent learner approach where the state of the queue is accessible to the platforms performs best. Furthermore, the empirical results related to the noisy estimation for λ and µ ( Fig. 6 and 7), suggest that the approach is able to cope with a significant amount of noise.