Nicolas Côté

Maroua Bouzid

Abdel-Illah Mouaddib

Integrating the Human Recommendations in the Decision process of autonomous agents: A Goal Biased Markov Decision Process

come

world. These different papers do not give a general approach that can be used in multiple robot settings, but only method applied to specific issues. (A. Mouaddib et al. 2010) or [START_REF] Thrun | Probabilistic Robotics[END_REF] give framework developed for real world and take into account the uncertainty of the world model. In these papers, the agent asks the human for teleoperation.

The goal biased approach [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF]) describes some behavior-based robotic. [START_REF] Crandall | Experiments in adjustable autonomy[END_REF] presents an implementation of this work where the human gives waypoints to a robot, guiding it through a maze. The robot has no ability of reasoning since it is controlled by the human: it changes its action when the human recommends it. There are no studies about integrating adjustable autonomy in the robot decision problem. From those different ideas, our aim is to show how to give some information to an agent about the real-world and how the agent takes them into consideration. A fully autonomous agent requires no time from a human in contrast to a teleoperated agent which requires the permanent attention of the human. The goal biased is a middle ground between full autonomy and teleoperation. The following table summarizes the advantage and drawbacks of each approach. The neglect time has been studied for how to supervise more than one agent. [START_REF] Crandall | Validating human-robot interaction schemes in multitasking environments[END_REF]) studies the neglect time, but not under uncertainty. In the next section, we present the Markov Decision Process (MDP) and the notion of goal biased. After this section, we explain how an agent and a human can interact without teleoperation.

MDP and Goal Biased Autonomy

An MDP (Puterman 1994) is a tuple < S, A, T, R > where (1) S is a finite set of all possible states, (2) A is a finite set of all possible actions, (3) T : S ×A×S → [0; 1] is a transition function giving for an action a and a state s, the probability to move to s , and (4) R : S × A → R is a function giving the reward associated to an action a taken in a state s. Solving a problem represented by an MDP means computing an optimal policy. Usually, the Bellman equation is used to compute the value V of a state, with 0 < γ ≤ 1 the discount factor :

V (s) = R(s, a) + γ maxa s T (s, a, s )V (s ).
Solving the Bellman equation allows us to compute an optimal policy π which determines for each state, the best action to execute. Similarly, Q(s, a) is the expected cumulative value reward received by taking action a in state s. When the expectation gives a weak reward, the human can give recommendation to improve the agent's performances. The human gives recommendations concerning the environment. The agent takes into account these recommendations and updates its optimal policy by updating only some states due to the recommendations. In the first section, we present this idea in detail.

The Human Recommendations

The principle of the Goal Biased Autonomy is that a human gives some recommendations to the autonomous agent. We distinguish two kind of recommendations :the desirable and undesirable states. First, we explain how a human expresses recommendations that are in two types. Second, we explain how an agent uses the recommendations to update its policy. Assuming that the human is rational.

Human Recommendations We define two kind of human recommendations as follows:

• Recommendation expressing a weak constraint : The human recommends that a state is desirable. The agent could not follow this recommendation. • Recommendation expressing a strong constraint : The human recommends that a state is undesirable and the agent should never reach this state.

If the human recommends that a state is desirable, it means that the agent should reach this state before reaching its goal. In the opposite, for unreachable state, an agent will find another way to reach its goal if the human forbids some states in its policy. This shows that if a recommendation is given on a state, it can directly modify the probability to reach the goal. If there is no path to the desirable state, the agent asks the human for teleoperation. A state is undesirable if the human forbids the agent to reach this state. As we are in a stochastic environment, the agent can even reach this state. In this case, it asks the human for teleoperation.

These two recommendations are really useful for the autonomous agent when meeting difficult situations. In the VC problem, the human indicates to the agent where it should never go (stairs, ...) or where it must necessarily go (ground dirty). An agent can partially update its policy depending on the human recommendations. It means that we have to find all the states where the expected value would be affected by those recommendations. Our aim is to define accurately the set of states to update. When the agent has this list, it uses the value iteration algorithm restricted to this list to update the policy.

Updating the set of undesirable states

The objective is to compute the set of states affected by the list of undesirable states. The human's recommendations can entirely change the policy of the agent. We define an absorbing state named w. When the agent attains this state, it can't move to another state, and its reward is null. More formally, an absorbing state w is such that:

∀a ∈ A, ∀s ∈ S \ {w}, T (w, a, s) = 0, T (w, a, w) = 1 and ∀a ∈ A, R(w, a) = 0 .
If the agent reaches the state w, then it would ask the human for teleoperation.

Let f be a forbidden state given by the human, and let T be the new transition function taking into account the human recommendations. For each state s, for each action a the probability to reach f is null. Formally: T (s, a, f ) = 0, T (s, a, w) = T (s, a, f ) and ∀s = f, s = w, T (s, a, s ) = T (s, a, s ) . To compute the set of undesirable states, we consider the policy graph of an agent where a state is represented by a node. Two nodes s 1 and s 2 are connected if the Figure 1: Example of the algorithm 1 probability to transit from s 1 to s 2 when following the optimal policy is not null. We introduce the algorithm 1 which allows the agent to compute a set of updated states called U . We define P arent(s, π(s

)) = {s ∈ S | T (s , π(s), s) > 0} such that a state s ∈ U iff s ∈ P arent(f, π(f )), or s ∈ P arent(s , π(s )) (where s ∈ U ).

Algorithm 1: Undesirable State Dependences Detection

Input: f : the recommended states, G: the policy graph Data: P : a stack of vertex Result: U : the set of states to update

P ← f while P not empty do sp ← pop(P ) foreach s ∈ P arents(sp, π(sp)) do if s / ∈ U then P ← P ∪ {sp} U ← U ∪ {sp} return U
We have to prove that a state s / ∈ U has a value of the optimal policy and doesn't need to be updated because of the human's recommendations. For this purpose, let Q(s, a) be the new expected cumulative value reward for an action a and a state s after the recommendations and V (s) the new expected cumulative value reward for a state s.

Lemma 1 For any state s / ∈ U and any action a ∈ A, the Q value in the new model is equal or less than the value in the old model:

∀a ∈ A,∀s / ∈ U , Q(s, a) ≤ Q(s, a)
Proof.

We assume without loss of generality ∀s, R(s, a) ≥ 0. By induction, at horizon i :

• i = 0 : Q0 (s, a) = R(s, a) = Q 0 (s, a) • induction hypothesis (IH) : Qi (s, a) ≤ Q i (s, a). Qi+1 (s, a) = R(s, a) + γ s T (s, a, s ) V i (s ) and (IH) ⇒ V i (s) ≤ V i (s) Qi+1 (s, a) ≤ R(s, a) + γ s T (s, a, s )V i (s ) = R(s, a) + γ T (s, a, f )V i (f ) + T (s, a, w)V i (w) + s =f,w T (s, a, s )V i (s )   = R(s, a) +γ s =f,w T (s, a, s )V i (s ) (1) ≤ R(s, a) +γ s T (s, a, s )V i (s ) = Q i+1 (s, a) (2)
Steps ( 1) and (2) come from :

(1) T (s, a, f ) = 0; V i (w) = 0 and ∀s = f, w, T (s, a, s ) = T (s, a, s )

(2) T (s, a, f ) = 0, T (s, a, w) = 0 because s / ∈ U .

Lemma 2 For any state in U , the Q value of the optimal policy is equal in the old and the new model:

∀s ∈ U, Q(s, π(s)) = Q(s, π(s)) Proof.
We proceed by induction on the horizon i :

• i = 0 : Q0 (s, π(s)) = R(s, a) = Q 0 (s, π(s))
• We assume the Induction Hypothesis:

Qi (s, π(s)) = Q i (s, π(s)) ⇒ V (s) = V (s) Qi+1 (s, π(s)) = R(s, π(s)) + γ s / ∈U T (s, a, s ) V i (s ) + s ∈U T (s, a, s ) V i (s ) = R(s, π(s)) + γ s / ∈U T (s, a, s ) V i (s ) (1) = R(s, π(s)) + γ s / ∈U T (s, a, s )V i (s ) = R(s, π(s)) + γ s ∈S T (s, a, s )V i (s ) = Q i+1 (s, π(s))
Step (1) come from:

(1) ∀s / ∈ U , T (s, a, s ) = 0; ∀s ∈ U , T (s, a, s ) = T (s, a, s )

We show that algorithm 1 selects the good set of states. Theorem 1 The policy of a state s not belonging to U remains optimal without an update operation.

Proof. We prove ∀a ∈ A, s /

∈ U, Q(s, π(s)) ≥ Q(s, a).
By definition of π, we know that ∀a ∈ A, s /

∈ U, Q(s, π(s)) ≥ Q(s, a). With lemma 2, Q(s, π(s)) ≥ Q(s, a) and with lemma 1, Q(s, π(s)) ≥ Q(s, a) ≥ Q(s, a). Then Q(s, π(s)) ≥ Q(s, a).
We can deduce that the policy of a state not belonging in U remains optimal without updating.

If there is more than one recommendation, there is only one set U of updated states. This set is the union of all the computed updating sets. Our detection algorithm of updated states is designed to improve efficiency of the value iteration algorithm: instead of sweeping all the updated states without order, we use the order defined by our detection algorithm. This allows us to optimize the number of iterations for a state, because in a first step we compute the states that are highly connected with the other states to update. [START_REF] Wingate | Prioritization methods for accelerating mdp solvers[END_REF] studies this methods for improving efficiency of the value iteration algorithm. We show the influence of this method in the experiments section.

Figure 2: Example of the algorithm for updating states. The goal state is bottom left, the state marked as necessarily available is in middle. We can see the stages of the propagation of states to update with the algorithm described above.

Updating the set of desirable states

The human recommends a desirable state as a weak constraint: this does not affect all the states, but only a subset of them. In our approach a recommendation of desirable states has been formalized as a goal-oriented decision process For a given Desirable State (DS), we compute the set of states U affected by the DS. First, we don't add in U the states with a smaller value than the one of s (the state of the agent). Those states won't be visited and don't need to be updated. Second, we don't add states with a bigger value than DS because their policy will not change.

Let s be a desirable state defined by the human and R c the new reward function of the agent. We formalize a recommendation of the human on a state s by changing the reward to reach s with ∀a ∈ A, Rc(s, a) = R(goal, a) where goal is the state with the highest reward. A limited number of states will be affected by this reward. They will be in the set U and respect the following conditions satisfied: c1 : Their probabilities to reach s is not null. c2 : Their expected values are less than the one of s.

To calculate the set U , we search all the states respecting conditions c1 and c2 as shown in Figure 2. If the probability of a state s to reach s is null, then its expected value remains unchanged. Moreover, if a state s has a higher expected value than the one of s, this means that the agent is closer to a goal in s than in s. Then, the agent tries to not reach s. Then, the list U computed with algorithm 2 contains all the states which must be updated using these conditions.

We guarantee that the agent does not go to the nearest recommended state and cycles there forever by not adding the state f in U . If there is more than one recommendation on desirable states, we consider them respecting the order of the recommendation. However, the list U of each state has to take into account the states already updated. To do that, we compute the states that respect the previous conditions and that have not been updated with another recommendation. After that we execute algorithm 2 and we don't take into account the state already updated. If the human gives contradictory recommendations, we can compute a bad policy. For example, the human gives two recommendations to an agent leading to two opposite paths.

Algorithm 2: Desirable States

Input: f : the recommended states, G: the policy graph Data: P : a stack of vertex Data: M arked: list of marked vertex Result: U : the set of states to update We add to P the vertex marked by the user. P ← P ∪ {s} while P not empty do s = pop(P ) marked ← marked ∪ s foreach v ∈neighbor(s) and v / ∈ marked do

P ← P ∪ {v} if EV (v) < EV (s) then U ← U ∪ {v}

Experimentation

We developed two types of experiments to present the quality of the solution and the complexity of our two algorithms.

For this purpose, we consider an agent moving in an environment and which reaches a goal state. It perceives the world but some walls in the environment are difficult to distinguish. When it acts, it has a low probability that the desired action is not executed as expected. We consider stochastic actions, left, right, up, down and stay.

The quality of the solution

We implemented the problem with the recommendations given by the human. First, the human recommended whether a state is undesirable. Then, we implemented the problem when the human recommends a state as a desirable state.

The undesirable recommendations We developed several experiments depicted in Figure 3. Twenty-one states have been updated because of the human's recommendations. In this example, the policy remains unchanged in only three states among the set of updated states. In theorem 1, we stated that the updated policy with this method gives the optimal policy. Our experiments confirm this statement.

The desirable recommendations Figure 6 shows how states are updated according to the recommendations.

The gains on computation time

We define a complexity parameter which is the distance from an agent to the goal. This distance is the Manhattan distance of a state relative to the objective. It is the average number of states visited before reaching the goal. There is 10% of the state space with a distance less than 5. In this part, we show the benefits of using our method to update the policy according to the human recommendations.

The undesirable recommendations The number of updated states in U depends on two parameters: the number of recommendations and the distance of the recommended state to the goal. When there are multiple recommendations, the set U of each recommendation is merged into one, so the number of recommendations has a minor impact than the distance of the updated states. Figure 4 shows the impact of Figure 4: The influence of the distance on the undesirable recommendations the distance on the number of updated states. In this problem, there is a 90 % chance to update less than 60 states. So the average reduction of state space to update is proportional to the distance to the goal. Figure 4 also shows the evolution of the state number where there are several recommendations.

While updating the policy, each iteration will be at least 40 percent faster than computing the overall policy. In the worst case (with a distance of 1 to the goal), the complexity of the algorithm is in O(| S | 2 ). The complexity of an iteration pass is O(| A | • | S | 2 ). We develop some experiments to compare our method to the traditional one. For the following experiments, we compute (in the worst case), the number of Bellman backups with 100 iterations, 5 actions and 100 states. The number of backup with the traditional method is 5000000 with those parameters. With our method, we obtain: Experiments in real states space We developed experiments to show how GBMDP is beneficial compared to the classical approach. To update a policy, the classical approach consists of a value iteration algorithm applied to all states. We show with the previous experiments that the number of updated states for the GBMDP model depends on the position of the state. For this experiment, we choose a forbidden Figure 5: The computation time relative to the states number state in the middle of the state space (50% from the top and 45% from the left). We use the previous benchmark in which we extend the size. The differences between our model and the classical one are described in Figure 5.

Here we show that the GBMDP approach is much faster than the classical one. On small problem (200 000 states), the agents updates its policy in 16 seconds with GBMDP while an agent using a classical approach needs more than 3 minutes and 30 seconds. Moreover, on large instances ( up to 1 700 000 states), our approach manages to keep the computation time under 4 minutes, while the classical approaches suffer from a combinational explosion (2 hours).

There are two reasons for this difference in computation times. With the classical methods, the number of updated states is bigger than the number obtained with the GBMDP model. Additionally, the iteration number is bigger in the classical method. In fact, our detection method allowing the agent to detect the states to update, find all states in specific order. U is sorted according to the number of states to be reached with nonzero probability. U is sorted in a decreasing order of this number. For example, the human recommendation for 40000 states takes 1 second to update with GBMDP model and 9 seconds for the classical model. For GBMDP model, there are 8460 states updated and 54 iterations, and for the classical model, there are 40000 states updated and 465 iterations. The classical model uses 40 times more Bellman backups than the GBMDP model. Morever, the time needed by GBMDP to detect which states need to The desirable recommendations The number of states to update in U depends on two parameters: recommendations number and the Manhattan distance of a state relative to the objective. Those two parameters have a big influence on the complexity. We developed experiments depicted in Figure 7.

With multiple human's recommendations, the algorithm in Figure 2 is executed one time for each recommendation. For one recommendation, the average number of states updated is smaller than for the undesirable states. In 90 % of our experiments, we have less than 60 states to update. The number of recommendations given by the human increases the size of the list of states to update. When there are several recommendations, in some case, the solution is not good because we have to recompute the entire policy. The complexity of the algorithm is in the worst case, O(| S | 2 )

Conclusion

In this paper, we discussed the problem of introducing human recommendations in the policy of an autonomous agent to increase its performances and robustness. Such recommendations are required in situations where the full autonomy is not desirable or not feasible. For this purpose, we present GBMDP where human can give two kinds of recommendations. He can recommend desirable states to the agent (in order to improve its performance), or undesirable states to avoid difficult situations which could lead to a major failure. We presented two algorithms inspired from value iteration where we find the set of states to update and we prove that the policy remains optimal in the other states. Experimental results show the effectiveness of our approach and the benefit of its use in terms of solution quality and computation complexity. Future work will concern a new direction where the human recommendations can be seen as a partially defined policy that the agent should optimally complete.

Figure 3 :

 3 Figure 3: a) Initial policy of an agent. b) The set of updated state. c)The initial policy is updated with human recommendation.

Figure 6

 6 Figure 6: a) Initial policy of an agent. b) The set of updated state. c)The initial policy updated with the human recommendation.

Figure 7 :

 7 Figure 7: The influence of the distance on the desirable recommendation


Nicolas Côté
email: nicolas.cote@unicaen.fr

Arnaud Canu
email: arnaud.canu@unicaen.fr

Maroua Bouzid
email: maroua.bouzid@unicaen.fr

Abdel-Illah Mouaddib
email: abdel-illah.mouaddib@unicaen.fr

Humans-Robots Sliding Collaboration Control in Complex Environments with Adjustable Autonomy

Autonomous agents dealing with partial knowledge about the environment are a classical subject of study for the decision making community. Moreover, such agents sometimes have to deal with unpredictable situations, which makes any previously computed behavior useless. In this paper, we address such problems using multi-human/multi-robot interactions, where the agents evolve in a complex environment and ask humans for help when they meet unpredicted situations. We introduce a model called HHP-MDP (Human Help Provider-MDP), that aims at handling the difficult situations met by the agents by using the human's help. For this purpose, we show how the agents can detect difficult situations and send different types of requests to the set of humans. The model describes how a controller can handle different requests and assign agent requests to the humans by taking into account their previously learned abilities. This controller is designed to reduce the human's cost of bother. Moreover, we show how to optimize the human's situation awareness and limit inconsistencies between her recommendations and the agent's plans.

I. INTRODUCTION

Robots autonomy has been widely studied in the artificial intelligence field, due to the increasing use of robots in everyday life. Despite this, computing an optimal agent behavior in a complex environment remains a highly complex task. In this paper, we study how the complexity of such planning problems can be reduced, and how the resulting performances of the agent can be improved, by adding a human in the decision making process. In such a problem, involving multiple humans and multiple agents, an efficient Human-Robot collaboration is crucial.

This collaboration is illustrated by the unmanned aerial vehicle (UAV) airport navigation problem. The UAV-an problem involves a set of autonomous aircrafts (UAVs), evolving on a set of taxiways. These aircrafts have to reach different objectives (runways), but a given taxiway can be obstructed by environmental factors (rain, or snow for example). When an agent meets such an obstacle, its effectors do not behave as planned. In our context, the agent can ask for help, and a human is selected to give a guidance.

More formally, this paper adresses a problem where the human and the agent have two different points of view. Punctual changes can occur in the environment. The agent receives limited information about these modifications, which prevents it from fully understanding the situation, while the human has more information. So, in order to reach its goal, the agent should ask the human for help when facing an unexpected situation.

The human can help the agent by teleoperating it or by giving recommendations (as introduced in [START_REF] Cote | Integrating the human recommendations in the decision process of autonomous agents: A goal biased markov decision process[END_REF]). Teleoperation is used when the agent reaches a critical situation (strongly limited actions). Otherwise, that is, when the agent has execution troubles but the situation is not critical, the human can use recommendation and give the agent a set of subgoals to be reached before the main goal, in order to escape the difficulties. Teleoperation requires more time of the human than recommendation: the required helping time determines the agent's autonomy quality.

We split the problem of requiring help while minimizing the human's cost of bother into three subproblems :

1) problem detection: an agent facing troubles while acting has to detect this, decide whether the situation is critical or only difficult , and finally send a request to the humans, 2) request allocation: the requests must be dispatched at best to the available humains, taking their individual abilities into account, 3) situation awareness and inconsistency reduction: the agent has to communicate all the relevant information to the human, in order to reduce her bother cost and the inconsistencies between her decisions and its own plans and goals. On the agent's side, we assume that the decision making problem is modelled by a Markovian Decision Process (MDP). Precisely, we assume that the agent is given an initial MDP describing the environment, the stochastic effects of its actions, and initial goals, and that it computes an initial action policy based on this. Then difficult situations may be foreseen at planning time, but they may also show up while the agent is executing its policy. This arises in particular when the environment suddenly changes (e.g., rain), implying unexpected changes in the behaviour of actions.

Our contribution is the HHP-MDP model, which gives a formalization of difficult situations, requests, and humans' abilities, together with strategies for problem detection, request allocation, and maximization of situation awareness. The model is flexible, and it optimizes the global system, which works well even when the controller receives more requests than the number of available humans.

The paper is organized as follows: first, we introduce related work and background material. Then we develop our contributions along the three problems of detection, allocation, and maximization of awareness. Finally, we describe a set of proof-of-concept experiments which show the good behaviour of our model.

II. BACKGROUND

Our work is based on a set of results coming from the Human-Robot Interaction (HRI) community and the Markovian Decision Process (MDP) community. In this section, we introduce these two fields and we describe the different approaches related to our model.

A. Human Robot Interaction

Human-Robot Interaction has been widely studied in the literature. Our model is based on adjustable autonomy, as described in [START_REF] Bradshaw | Policy-based explorations of a richer model for adjustable autonomy[END_REF], which allows one to dynamically change an agent's autonomy. [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF] introduced different kinds of autonomy (studied further by [START_REF] Goodrich | Experiments in adjustable autonomy[END_REF]), [START_REF] Dorais | Adjustable autonomy for humancentered autonomous systems[END_REF] demonstrated the advantages of adjustable autonomy as compared to traditional approaches.

The model which we describe in this paper switches the agent's autonomy between three levels: (i) full autonomy, (ii) teleoperation (as described by [START_REF] Goldberg | Collaborative teleoperation via the internet[END_REF]), and (iii) goal biased autonomy (introduced by [START_REF] Cote | Integrating the human recommendations in the decision process of autonomous agents: A goal biased markov decision process[END_REF]). This last level is a tradeoff between (i) and (ii), where the human only gives recommendations in the form of subgoals.

There are several parameters that a system involving humans should optimize. First, the neglect time [START_REF] Crandall | Validating human-robot interaction schemes in multitasking environments. Systems, Man and Cybernetics, Part A: Systems and Humans[END_REF] is the expected amount of time during which a request from an agent can be ignored before its performance drops down below some threshold. According to this definition, the neglected time should be minimized: it expresses the average time during which an agent needs human help, but has to work without it. Second, situation awareness [START_REF] Endsley | Design and evaluation for situation awareness enhancement[END_REF] must be maximized: it describes how well the human perceives its environment within a volume of time and space, understands its meaning, and projects its status in the near future. [START_REF] Holly | where am i? acquiring situation awareness using a remote robot platform[END_REF] showed that a lack of Situation Awareness has a negative effect on the quality of teleoperation or recommendations. Finally, the bother cost should be minimized: it describes how often the human is asked for help, with frequent requests reducing the overall system efficiency [START_REF] Cohen | A user modeling approach for reasoning about interaction sensitive to bother and its application to hospital decision scenarios[END_REF].

This paper deals with Human-Robot Collaboration, which is only one of the possible kinds of Human-Robot Interaction. Some works involving human-robot collaboration make the assumption that a robot is a "tool", used by the operator. In [START_REF] Bechar | Human-robot collaboration for improved target recognition of agricultural robots[END_REF] for example, a single human operator is working with a set of robots and controls them with different levels of autonomy. Other works are based on a dialogue between the human and the robot: in [START_REF] Fong | Collaborative control: A robot-centric model for vehicle teleoperation[END_REF][START_REF] Fong | Robot, asker of questions[END_REF] for example, the robot can ask questions to a single human operator when its autonomy is limited. In this paper, we use a collaboration control in which the robots see the available humans as resources, able to compensate for the limitations of their autonomy.

In [START_REF] Ishikawa | Development of a human and robot collaborative system for inspecting patrol of nuclear power plants[END_REF], the robots execute their tasks in a hazardous environment and the operator observes them. When an agent reaches a difficult situation, the human teleoperates it. In the same vein, [START_REF] Lee | Teams for teams performance in multi-human/multi-robot teams[END_REF] and [START_REF] Wang | How search and its subtasks scale in n robots[END_REF] describe a problem involving multihumans and multi-robots teams, where the humans observe the agents and assist them during the difficult situations. However, the humans have to detect when an agent is in a difficult situation: [START_REF] Ohba | Remote collaboration through time delay in multiple teleoperation[END_REF] showed the negative effect of the time-delay on such teleoperation systems. In our approach, such delays are minimized, because we seek to optimize Situation Awareness, Bother Cost and Neglected Time.

B. Markovian Decision Process

The Markovian Decision Process (MDP) model [START_REF] Puterman | Markov decision processes: Discrete stochastic dynamic programming[END_REF]] is an elegant framework, which is widely used for modelling decision-making problems of autonomous agents evolving in an uncertain environment. An MDP is a tuple S, A, T, R where (1) S is a finite set of states, (2) A is a finite set of actions, (3) T : S × A × S → [0; 1] is a transition function giving the probability to move from a state s to s ′ , when the action a is applied and (4) R : S × A → R is a reward function giving the positive or negative reward resulting of an action a taken in a state s.

Solving a problem described with an MDP means computing a policy π, that is, a function which gives, for each state s, an action a = π(s) to apply so as to maximize immediate and expected (discounted) future reward. Bellman's equation gives the expected value V (s) of a state (expected long-term discounted reward) with 0 < γ < 1:

V (s) = max a (R(s, a) + γ s ′ T (s, a, s ′ )V (s ′ )) (1)
An optimal policy π * , that is, a policy giving the best action to take in each state, can be computed using this equation. The intended behaviour of an agent is to compute π * off-line, given an MDP modelling its actions, goals, and the environment, and then, at execution time, to act reactively according to π * .

In this paper, we used goal-oriented MDPs, in which only one state (the goal) brings a positive reward, while each other state has a null or negative reward (whatever the action). Moreover, once the goal is reached, the agent can receive a new one, and then must re-compute the whole policy (as this changes the R component of the MDP).

In [START_REF] Mouaddib | A decision-theoretic approach to cooperative control and adjustable autonomy[END_REF], an MDP based approach is described which deals with agents asking the humans for teleoperation, but this model suffers from several limitations: in particular, the latency of the model is high, and it deals with only one robot and a permanently available human. OPOMDPs [START_REF] Armstrong-Crews | Oracular partially observable markov decision processes: A very special case[END_REF] were introduced for planning requests for human help under partial observability, but this model assumes that the human is permanently available and only plays the role of an observation provider. HOP-POMDPs [START_REF] Rosenthal | Modeling humans as observation providers using pomdps[END_REF] are similar to OPOMDPs, with a model of the human (a probability distribution on its availability), but here again the role of the human is strongly limited.

In this paper, we used an MDP based approach: this model not only allows the agents to evolve autonomously in complex environments, but we can also use its properties to quickly assign help requests to the humans (without needing any dialogue) and to maximize the human's Situation Awareness while he is helping an agent. Finally, our approach integrates goal-biased techniques: the human gives recommendations to the agent, as a set of sub-goals to be reached before the main goal. Hence we have an intermediate level of autonomy between full autonomy and teleoperation, which reduces the time spent by the humans helping the agents. In this section, we present the utility of human recommandation on a small example described on Figure 1 (excerpted from our experiments). The agent has just fallen into snow and now has a small probability to reach its goal in a reasonable amount of time if it follows its initial policy. Hence it sends a help request.

C. Teleoperation and recommandation

The human can help the agent in two different ways:

• By teleoperating it to its goal by following the dark edge. The human gives the actions to apply for each successive state to the agent.

• By giving the agent some waypoints, in this case the two extreme points on the left of the dark edge, as recommended subgoals. The agent changes its reward function by adding a new reward to the indicated subgoals. In both cases, the human decides to stop helping the agent as soon as she think that the agent can reach its goal alone.

III. CRITICAL STATES DETECTION (Neglected Time MINIMIZATION)

Efficient techniques for detecting critical states are crucial: the faster an agent detects such states and asks for help, the more it reduces its Neglected Time. Two complementary approaches are described here: we can detect a set of critical states off-line, during policy computation, and detect additional ones during the execution of this policy.

A. Absorbing states

A set of absorbing states is a "trap", from which an agent has a null probability to escape (to reach another state, out of this set). More formally, with g the goal of the agent, a state s is absorbing if P (g|s, π) = 0, that is, the probability to reach the goal from s is null, no matter how long the policy π is followed. This set can be computed straight forwardly with a backwards search from the goal in the policy graph.

If the agent is in such an absorbing state, then its capabilities are not good enough to reach the goal, so it must resort on the human's higher abilities and send her a request. Precisely in this case, the agent has no action allowing it to reach the goal even with a small probability, while the human has such actions. In the UAV-an problem, an agent could be in such an absorbing state if it does not have enough space on its taxiway to maneuver. Then it needs help from a human, until it reaches larger taxiways. However, such an approach only detects the "predictable" critical states: the agent could reach a critical state which was not predicted, because, say, of a new (intially unknown) obstacle.

B. Online detection

According to Bellman's equation (Eq. 1), an optimal policy maximizes the expected (long-term) value at each step. It follows that when everything goes well at execution time (random drawings of action outcomes are beneficial to the agent), the expected value of each state should grow higher and higher as the agent executes its policy. We will use this fact as a means to detect problems at execution time.

Formally, define an ideal trajectory of a policy as one which goes at each state from one state to the reachable one with maximal expected value:

Definition 1: Let S, A, T, R be a goal-oriented MDP (i.e., R(s g , ) = 1 and R(s, ) ≤ 0 for all s = s g ), let π * be an optimal policy for it, and let s ∈ S be a state. A sequence of states (s 0 , s 1 , . . . , s n ) is called an ideal trajectory for π * in s if s 0 = s, s n = s g , s t = s g for t = n, and for t = 1, . . . , n it holds that

s t ∈ argmax s ′ ,T (st-1,π(st-1),s ′ )>0 V (s ′ )
Proposition 1: Let S, A, T, R be a goal-oriented MDP with goal s g , and let (s 0 , s 1 , . . . , s n ) be an ideal trajectory for some optimal policy π * and state s.

Then V (s 0 ) ≤ V (s 1 ) ≤ • • • ≤ V (s n ) holds.
Proof. Because π * is optimal, it must satisfy Bellman's equation in the sense that for t = 0, . . . , n -1:

π * (s t ) ∈ argmax a∈A (R(s t , a) + γ s ′ T (s t , a, s ′ )V (s ′ ))
Now by definition of an ideal trajectory, we have V (s t+1 ) ≥ V (s ′ ) for all s ′ reachable from s t through the action π * (s t ), and because T (s, π * (s t ), •) is a probability distribution, we get

V (s t+1 ) ≥ s ′ T (s, π * (s t ), s ′ )V (s ′ ) (2)
Now because the MDP is goal-oriented and s t = s g we have R(s t , π * (s t )) ≤ 0, which together with 2 yields

γV (s t+1 ) ≥ R(s t , π * (s t ))γ s ′ T (s, π * (s t ), s ′ )V (s ′ )
Because π * is optimal, the right-hand side is at least V (s t ), and because γ is less than 1 we get V (s t+1 ) ≥ V (s t ), as desired. ✷ Based on this analysis, we take the changes of the current expected value as an indicator to at what extent the execution goes well. Whenever expected values do not grow as fast as expected as execution time, this may mean either that random drawings of action outcomes are adversarial to the agent (for instance, it fails to brake three times in a row while this has only a 0.1 probability, or that the agent is not executing an optimal policy and hence, that the model has changed without the agent detecting this (e.g., undetected water on the taxiway modifies the model of its effectors)).

The only exception to expected value growing along an ideal trajectory is when a goal is reached: then, a new goal is assigned to the agent, and the expected values temporary drop down (this new goal being usually far from the previous one). Figure 2 describes such an example of expected values changes.

Summarizing, if the expected values do not grow as fast as expected, the agent probably faces a problem. The growth can be too slow (in the UAV-an problem, undetected water on the taxiway forces the agent to slow down), or critical (snow on the taxiway, making the aircraft unable to move). Then help is required from the human, who we assume to be able to detect changes in the environment and help the agent accordingly. In order to detect such problems (slow or critical growth) while avoiding to require help as soon as a few random drawings of action outcomes are adversarial, we propose a strategy in which the agent keeps a restricted history of recent expected values, and compares the associated growth to the average one, on the whole history. When expected values remain constant or drop down (for another reason than goal completion), then the agent asks for help. Formally, write s i for the state in which the agent is at timestep i, t for the current timestep, and w for the size of the observation window. We define Average and Windowed Average by:

Avg = 1 t t i=0 (V (s i ) -V (s i-1 )) • 1I[R(s i-1 ) ≤ 0] WAvg = 1 w t i=(t-w) (V (s i ) -V (s i-1 )) • 1I[R(s i-1 ) ≤ 0]
where 1I[R(s i-1 ) ≤ 0] is 0 for R(s i-1 ) > 0 and 1 otherwise, hence excluding from the definition any timestep following a goal achievement. Then at execution time, the agent evaluates the current growth rate by comparing C := WAvg/Avg to some threshold. When C is low enough (for example, C < 0.5, meaning expected values grow twice slower than usual), then the agent asks for help (providing the value of C in the request). Moreover, for W Avg ≤ 0, meaning the agent moves away from the goal, the agent asks for a critical help. We discuss the value of C in the experiments section.

IV. CONTROLLER (Bother Cost MINIMIZATION)

Our model includes a centralized controller, which receives requests sent by the agents and assigns them to the available humans. In the simple case of one human and one agent, such a controller would be useless. However, most of the time, agents issue more requests than the number of available humans (or, sometimes, there are more available humans than pending requests). Then, we propose a controller for optimizing collaboration efficiency, by dispatching the requests to the available humans according to their abilities.

A. Request types

Recall that agents can send three kinds of requests, each one associated to a given priority:

• absorbing state: these requests are the most critical ones. The agent knows it will not be able to reach the goal with its own abilities. Usually, such a request implies a breakdown that requires human intervention, or a bad initial state of the agent. The resulting intervention can be a teleoperation, or repairing the robot. • Critical values changes (WAvg ≤ 0): such a request is critical, since the agent is not going towards its goal. Usually, the agent is in a difficult situation for which it cannot compute a solution with its limited sensors and actuators. The resulting intervention can be a teleoperation, until the agent can be autonomous again.

• Low values changes e.g., 0 < C < 0.5: these requests are not critical. The agent heads its goal, but too slowly. The human will only have to give recommendations to the agent, in order to help it find a new way to reach the goal. As an illustration of the latter case, assume an aircraft moves forward more slowly than expected because of undetected rain on the taxiway. A recommendation by a human (who can detect where the taxiway is wet) could be to go backwards (contrary to the agent's initial plan) so as to escape the wet taxiway, then go to another (dry) taxiway and finally meet the initial one again at a place where it is dry.

B. Request allocation

When many agents are involved, the controller will receive a lot of requests at the same time, usually more than the number of available human operators. In order to minimize the bother cost, we choose not to interrupt an operator while he is helping an agent. Then the controller has to choose an efficient allocation of requests to the operators, in order to maximize the impact of the collaboration. We formalize such expected efficiency through a model of each operator's abilities.

1) Models for operators: The efficiency of a collaboration depends on two factors:

• the time needed by the human to deal with the request,

• the resulting expected gain. Hence we assume the controller to be given two functions: time(r, o) gives the average time needed for the operator o to deal with a request r (depending on its type), and gain(r, o) gives the expected gain, when the operator o deals with r. We assume time(r, o) to be given on an absolute scale common to all request types and operators but not necessarily related to the timesteps of the agent. This indeed essentially measures the Bother Cost for the human. As for gain, we define this as an expected value of V (s end ) -V (s start ) with s start the state in which the agent asks for a teleoperation or recommendation, and s end the state in which the collaboration ends.

We assume these functions to have initial values estimated from average data. Moreover, these values can be updated each time a human indeed helps an agent, in a manner similar to reinforcement learning approaches. However, this part is not an important contribution of this paper, so we do not discuss it further.

2) Choosing the allocations: Given each operator's model, the controller is able to compute a weighted gain for each operator o and request r:

G(r, o) = gain(r, o) time(r, o)
Then when a human operator o becomes available and there are pending requests, the controller sends o the best pending request, given by r * (o) = argmax r G(r, o). Dually, when several human operators are available and a request r comes in, the chosen human operator is given by o * (r) = argmax o G(r, o).

V. INFORMATION SENT TO THE HUMAN (Situation Awareness MAXIMIZATION)

We have described how an agent detects problems and issues requests for help, and how these requests are allocated to human operators. However, if the human does not have enough information about the problem, its help will not be optimal. So we have to maximize the human's awareness of the situation faced by the agent. This Situation Awareness is a crucial factor for the performances of our system. Good awareness will lead to fast decisions, and limit inconsistencies with the policy of the agent. The HHP-MDP model takes this into account by using the MDP model to improve the human's understanding of the situation.

When a human is helping an agent, irrelevant information makes it difficult for her to find a good solution. Hence we must minimize the amount of information given by the agent to the human while giving the relevant data. Generally speaking, call an information relevant if it allows the human to identify the agent's problem. We split this information into two parts: global information (about the agent's longterm will) and local information (about its neighborhood).

A. Global information

Information about the long-term goal can be used for planning problems. Most of the time, such information is used when the human gives recommendations to the agent. Here there are two relevant kinds of data: the global strategy (planned to be) used by the agent to reach the goal, and information about the goal itself. We extract such data the MDP as follows:

• Information about the goal: only the goal has a positive reward, so we highlight any state s such that ∃a ∈ A, R(s, a) > 0.

• Information about the agent's strategy: we use the policy graph to extract the global strategy, by building clusters of adjacent states with the same action according to the agent's policy. Such clusters are easier for the human to understand than a full policy. As an example, Figure 3 (left) describes a full policy, and (right) gives the associated clusters, as communicated to the human operator (the smallest clusters -less than 5% of the state space -were ignored). Such a representation

B. Local information

When a human starts a teleoperation, he needs information in order to choose an action which will be as consistent as possible with the agent behavior. Moreover, again such data should be easy to understand. There are two kinds of such data:

• Agent's history: the human needs to understand the problem of the agent. For this purpose, we display the states reached by the agent during the last timesteps and the policy applied in each one. • Agent's policy: the human has to choose actions as consistent as possible with the agent's policy, hence she needs information about the reachable states (all the states with a nonzero probability to be reached in n timesteps), and about the agent's policy on these states. An example of the resulting display is depicted on figure 4. Here, we understand that the agent policy is to go down. It came from the left, tried to go down several times, but stayed in the same state, so it sends a critical ask for help.

Using these two views (local and global), we maximize the Situation Awareness of the human, in that we avoid giving useless information about the agent, and we keep the human focused on the problem he has to solve.

A. Experimental setting

We used a map of the Montpellier airport (Figure 5), which involves two possible airways connected by several taxiways around a central building. UAVs are randomly launched from the building and have to reach an airway. Usually, they are able to reach their objective using a fully autonomous approach. However, sometimes, the weather (rain or snow) makes it impossible for them to evolve safely on the taxiways. Human operators are then asked for help. When an agent reaches the airway, it receives a reward of 200. Moreover, the operator model is initialized as follows, based on collected data:

• low changes request: the average gain on the expected value is 5 and the average time needed is 20 timesteps, • critical changes: average gain = 8, average time = 15, • absorbing state: average gain = 12, average time = 10. We built a benchmark, based on this airport, as depicted in figure 6. Rain or snow start randomly during the execution of the problem: in figure 6, the blue spots are puddles due to the rain. One agent is currently evolving on the taxiways (the red square) towards the top airway (green square), but it is not able to move anymore, so it asks for help.

The agent can move forward, stay where it is and turn to the left or the right. In normal situations, it has a probability P = 0.1 to stay in its current state when trying to move forward, due to its own limitations. When it drives through a puddle, this probability not only rises to P = 0.3 (because the agent has to move slowly), but there is also a probability to deviate on the sides (with P = 0.1 for each side). Finally, when the agent drives on snow, it has a probability P = 0.4 to deviate on each side.

The initial policy is computed assuming all situations are normal, i.e., only a 0.1 probability not to move forward as desired. Moreover, the agent cannot directly detect snow or rain at execution time.

As concerns humans, we involved up to three persons, which used a specific graphical interface for teleoperating or recommending in the simulation. One of them (Human 1) we familiar with the problem and the interface, while Human 2 only experimented the interface a few times, and Human 3 had no prior experience with it.

B. Detecting a slow or critical changes

We ran a set of experiments, each one over 3,000 timesteps. For observation of expected value evoluation, we used a window of 4 timesteps. In our first experiment (Figure 6), we only used one agent and one operator. Each time the agent evolved through a puddle, it managed to detect it and sent a request for help. These requests were distributed as follows:

• 11.5 % of low changes requests, • 88.5 % of critical changes requests. This distribution depends on the bound above which an evolution is considered as critical (we used C = 0.5). This first test confirms the ability of the agents to detect problems at execution time and to send requests accordingly.

C. Influence of the number of agents

We ran another set of experiments, involving 1 to 15 agents at the same time. During these experiments, we computed the percentage of critical requests ignored by the controller, as depicted in figure 7.

With less than 10 agents, one operator is enough to deal with more than 70% of the critical requests. However, with Hence, naturally we need to add more operators: with k available humans, the number of ignored requests is divided by k. Still, the complexity of allocating them remains low (linear in the number of operators), making it possible to scale up.

D. Involving several humans

We ran a set of experiments with three persons, as described in the experimental setting. With a small number of agents, Human 1 deals with a lot of requests, while Human 2 deals with a smaller number and Human 3 deals with almost none. This is because Human 1 is more familiar with the simulation and hence, handles requests much faster. However, the number of handled requests seems to converge to 60 for each human when the number of agents is large enough, which appears to be the limit of a human for this problem.

The relative abilities of the humans, as computed from average data gathered in our own experiments, are given in Table I. This data is clearly consistent with the number of requests handled as depicted on Figure 8.

VII. CONCLUSION

In this paper, we described a new approach to deal with decision making problems where unpredictable situations can change the environment at execution time. We proposed a multi-agent/multi-human collaboration based approach, where the agents can ask humans operators for help. We described three main contributions: how an agent detects such an unpredictable situation and asks for help, how to choose which agent needs help the most, and how to give an efficient description of the problem to the human operator. Finally, we illustrated our approach on the UAVan benchmark: we investigated in particular the influence of the number of operators and agents. We are now working on a new approach, in order to reduce the number of help requests, in which the human sends information to the agent about its model when an event occurs.

Figure 1 .

 1 Figure 1. Example of teleoperation utility

Figure 2 .

 2 Figure 2. Expected values history and rewards history

Figure 3 .

 3 Figure 3. The long-term strategy of an agent

  4

Figure 4 .

 4 Figure 4. The short-term strategy of an agent

Figure

  Figure 5. Montpellier airport

Figure

  Figure 6. Our benchmark

Figure 7 .

 7 Figure 7. Percentage of ignored critical requests more than 10 agents, the performances of the system drop down (half the requests are ignored with 15 agents).Hence, naturally we need to add more operators: with k available humans, the number of ignored requests is divided by k. Still, the complexity of allocating them remains low (linear in the number of operators), making it possible to scale up.

  Figure 8 describes our results.

Figure 8 .

 8 Figure 8. Number of treated requests This figure shows the number of requests treated by Humans 1, 2 and 3, as a function of the number of agents.With a small number of agents, Human 1 deals with a lot of requests, while Human 2 deals with a smaller number and Human 3 deals with almost none. This is because Human 1 is more familiar with the simulation and hence, handles requests much faster. However, the number of handled requests seems to converge to 60 for each human when the number of agents is large enough, which appears to be the limit of a human for this problem.The relative abilities of the humans, as computed from average data gathered in our own experiments, are given in TableI. This data is clearly consistent with the number of requests handled as depicted on Figure8.

VIII. ACKNOWLEDGMENTS

This work has been supported by the NRA (French National Research Agency) and the DGA (Defense Procurement Agency) (ANR-09-CORD-103).


Nicolas Côté -Maroua
email: nicolas.cote@unicaen.fr

Bouzid -Abdel-Illah Mouaddib
email: abdel-illah.mouaddib@unicaen.fr

Integrating Human Recommendations in the Decision Process of Autonomous Agents

In order to help agents in a difficult situation, we integrate the human in the agent's decision process.

We develop a new model called Human Help Provider in a Markov Decision Process (HHP-MDP). We define HHP-MDP as a middle ground between an autonomous agent and a teleoperated agent called adjustable autonomy. The global approach of HHP-MDP is based on (1) a recommendation is translated into a partial policy,

(2)then, this partial policy is translated into transition and reward functions associated to the agent Markov Decision Process. This new model is quickly integrated into the agent's decision process.

Introduction

This paper is motivated by the problems where robots deployed in complex environments meet many difficulties coming from their limited ability to perceive or to act in these environments. Because of these limits and in some sensitive applications, a full autonomy is not desirable and sometimes computationally not feasible. In order to extend their ability, robots should take advantage from an external entity such as humans which can play a role of an operator (sending orders) or a companion sharing the mission. With external helps, robots can overcome many difficulties such as the environment uncertainty or the human preference changes.

In this paper, we propose a new model which allows the agents to overcome their limited capacity by sending them human's recommendations to act when the quality of their behavior is degraded. The agents evolve autonomously in a stochastic environment. To formalize the problem of deriving a behavior policy, we use a Markovian Decision Process (MDP) which assignes for each state an action to execute. We assume, in this paper, that the human observes the agents evolving in the world, and detects that an agent meet difficulties in some situations. In order to help him, we propose that the human sends recommendations.

Moreover, we focus on two situations where the human sends recommendations: he gives recommendations (1) to help the agent to overcome difficult situations due to the lack of information or (2) to reach some states respecting particular preferences. For these two cases, the cost is the human's time spent for helping one agent and depends on the agent's situation. This cost is less than that due to the situation where the agent the human teleoperates the agent, but higher than that where the agent is autonomous. In both situations, the cost of help is very low and thus she is able to send recommendations to more than one agent without considering their models nor their current states.

In this paper, we address the problem where the agent cannot react to unexpected events and can not take into account modification into its models. From its point of view, the agent has an optimal behavior, but human has more information about the situation, and from his point of view, the agent's behavior is not optimal in this situation. The purpose of this paper is to allow a human to share his perception model with the agent, in order to improve its behavior.

The difficulty of the human to help the agent comes from the fact that some unexpected events can require to modify the agent's policy at a large number of state. We introduce our approach HHP-MDP that allows a human to give recommendations to the agent to react properly to the unexpected events without specifying the policy at all concerned states. There is several assets of this approach:

• We give a framework which formalize humanagent recommendation and can be adapted to many types of recommendations.

• We reduce the agent's autonomy when its behavior is not desirable.

• We decentralize the recommendations integration in order to be executed in parallel on several processors.

In the following, we explain how human recommendations are integrated in the agent's decision process. To this aim, our approach is decomposed into three steps: (i)From Human's recommendations to partial policy: we present what is a recommendation and how a recommendation can be defined as a partial policy. In order to illustrate our explanation, we present three recommendations according to our UAV-an problem.(ii) From partial policy to a new model: We explain how the partial policy is translated into a new agent's model (a new transition and rewards function in a subset of states). (iii) Integrating a new model: we explain how the agent integrates a new model or a partial policy in its decision process. Before presenting our contributions, we present several related works in the next section.

Related Works

Our work is based on a set of results coming from the Human-Robot Interaction (HRI) community and the Markovian Decision Process (MDP) community. In this section, we introduce these two fields and we describe different approaches related to our model.

Human Robot Interaction

Human-Robot Interaction was widely studied in the literature. Our model is based on adjustable autonomy, as described in [START_REF] Bradshaw | Adjustable autonomy and human-agent teamwork in practice: An interim report on space applications[END_REF], which allows us to dynamically change the agent's autonomy. In their work, the adjustable autonomy allows the agent to change its autonomy from teleoperation to full autonomy.

Brooks introduced some other kinds of autonomy in [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF] (studied further in [START_REF] Goodrich | Experiments in adjustable autonomy[END_REF]) and demonstrated in [START_REF] Dorais | Adjustable autonomy for humancentered autonomous systems[END_REF] the advantages of adjustable autonomy compared to traditional approaches.

When an agent reaches a difficult situation, the human teleoperates it. In the same way, [START_REF] Lee | Teams for teams performance in multi-human/multi-robot teams[END_REF]; [START_REF] Wang | How search and its subtasks scale in n robots[END_REF] describe a problem involving multihumans and multi-robots teams where humans observe agents and assist them during the difficult situations.

HRI and MDP

In this subsection, we present several works where the human can interact with the agent in order to improve its strategy to accomplish its goal, where the agent models its environment with MDP or POMDP (Partially Observable MDP). In [START_REF] Mouaddib | A decision-theoretic approach to cooperative control and adjustable autonomy[END_REF], an MDP based approach is described and which deals with agents asking for teleoperation to the humans. However, this model suffers from several limitations (for example, the latency of the model is high and it deals with only one robot with a permanently available human).In Armstrong-Crews and Veloso [2007], a model OPOMDP was introduced to plan human help using partially observable MDPs, but this model makes the assumption that the human is permanently available and only plays the role of an observation provider. All these few works are proposed by the MDP community using some HRI methods. In our approach, we use the MDP properties to introduce a new Human Robot Interaction approach. In the next section, we present the human's recommendations that our approach can take into account in the next section.

Human's recommendations

In this paper, we consider that the agent has a partial observability on the environnement while the human has more information on the situation. To augment its observability, the human shares his information with the agent by sending his recommandations. These recommandations should help to improve the current policy of the agent. In the following, we present what is a recommendation, and we introduce three kinds of recommendations useful for sharing human's help to the agent in UAV-an problem.

What is a recommendation?

A robot has a policy π a considered optimal given its incomplete model M a . This policy could be not optimal from the human point of view because he has more information and richer model M h . To improve the policy π a , the human sends recommandations leading them to derive a new policy π ′ a to overcome the difficulty. Different recommandation types can be considered:

• Primitive Recommandations PR : these recommandations assign an action a to a state s such that PR = (s, a). For example: turn left at the next crossing.

• General Recommandation GR : these recommandations are a partial policy π p defined by specific states in the subspace. Such recommandations can be seen as a set of primitive recommandation such as GR = (S, recommandation) = (s 1 , a 1 ), (s 2 , a 2 ), ..., (s n , a n ). For example : follow the wall so GR = (wall, f ollow) = π f ollow such that s ∈ ad jacent(wall).

Transforming general recommandation into primitive recommandations

3.2.1. Giving a subgoal recommendation. We define a subgoal as a set of target states. The agent must reach one of its subgoal before its initial goal. In our UAVan problem, the human subgoal ensures that the agent takes the right direction by reaching the subgoal first. For example, in Figure 1 the agent (in black circle) has to reach its goal (in black rectangle). In the environment, the agent evolves in grid by executing four actions: left, right, up and down. It evolves in the white square with 0.1 probability that its action fails, and it evolves on the snow in blue square with a probability of 0.8 of deviating from its trajectory. The agent has computed its optimal policy which takes only the white square into account. The sensor of the agent are unable to detect snow. In order, to improve its policy, the human gives two subgoals (in gray rectangle) to the agent in order to avoid the snow. The agent changes its initial policy which takes it through the snow by reaching the two subgoal given by the human. When the human gives a subgoal, this recommendation has to be translated into a primitive recommandation, in order to be integrated in the agent's decision process.

Figure 1. Giving a subgoal

Definition 1 A subgoal is a recommendation where the agent has to reach at least one state of the set of states associated to subgoal before its goal.

More formally: the human gives a subgoal s g when the agent is in a state s i . We define π s g which allows the agent to reach its subgoal. To this aim, we change the reward function where ∀s ∈ s g , R ′ (s p ) = R(g) and ∀s ∈ S\{s g }, R ′ (s) = R(s). Moreover, the primitive recommandation associated to s g contains a state s iff ∀s p ∈ s g , ∃s ∈ S where P(s, π s g , s p ) > 0.

When we want to integrates primitives recommendation into the agent decision process, the traditionnal approach is simple: we execute the value iteration algorithm without changing the given partial policy. This computation shows a lack of performance, and this approach executes some unnecessary operations:

• We compute the expected value for each recommended states, even if we know the agent's policy.

• We update the set of all states, even if these states are not modified.

We study these two problems in the following, and we present an approach to solve them, and improve significantly the naive approach.

Efficient Algorithm for Human Integration

In this section, we present the algorithm translating the recommended partial policy into a new model of transition and reward functions. These modifications avoid the expected value computation for some unecessary states. This model is more easily integrated into the agent's decision process than the partial policy integration, because unlike naive approach, IHR-MDP does not compute the expected value for each state where the policy was given, but only in the necessary subspace. Unnecessary computation are then avoided. Thus our new algorithm is based on two main steps: computation of the new model (T ′ and R ′ ) and the integration of this new model in the agent's policy. The rest of this section is focused on the first step and section 5 is dedicated to the integration step.

To the end of the first steps, we define a set U as the human's recommended states where for each state in U, we know the given human policy π h where ∀s ∈ U, ∃a ∈ A, π h (s) = a.

The intuition of our algorithm is: for each state where the policy is given (U), we compute the new reward function R ′ and a new transition function T ′ according to the human policy π h . In order to integrate the human's recommendation, the agent has to integrate these functions R ′ and T ′ to computes a new π G . To this purpose, we define a set of entry states ES(r) of a recommended state r ∈ U :

s ′ ∈ ES(r) iff ∃s ′ ∈ S, s ′ = r, T (s ′ , π a (s ′ ), r) > 0.
In the same way, we define a set of output states OS(r) of a recommended state r: s ′ ∈ OS(r) iff ∃s ′ ∈ S, s ′ = r, T (r, π h (r), s ′ ) > 0. Note that ES is defined by π a and OS is defined by π h .

After the computation of sets OS and ES for a state r, we compute a transition T ′ and a reward R ′ function for each state in ES(r) to reach a state in OS(r).

The transition or reward function is easy to compute when no cycle exists, but some cycles can occur in the given human's partial policy. A recommanded state leads to a cycle when the following conditions holds : if ∃o ∈ OS(r), ∃e ∈ ES(r) where T (r, a, r) > 0 or T (o, π a (o), r) > 0 or T (r, π h (r), e) > 0 or T (o, π a (o), e) means that there is a cycle. Although this policy may contain small cycle number, the algorithm resolution has to integrate an iteration function to give the ε close result.

Our aim is to compute the probability for an agent to reach out states when it reaches entry state. To this end, we compute the new transition T ′ r (i, e) and reward R ′ r (i, e) functions for each state in r ∈ U, the state i ∈ {r} ∪ OS(r) and e ∈ ES(r) with the following equation:

T ′ r (i, e) = γ • ∑ ∀s∈OS(r) T ′ r (s, e) • T (r, π h (r), s) (1)
this equation is computed until

T ′ r (i, e) -γ • ∑ ∀s∈OS(r) T ′ r (s, e) • T (r, π h (r), s) < ε.
In the same way, we define R ′ (s) the reward function as follows:

R ′ r (i, e) = R(i) + γ • ∑ ∀s∈OS(r) T (r, π h (r), s) • R ′ r (s, e) (2)
with 0 < γ < 1 the discounted factor and we initialize

T ′ = T and R ′ = R. This equation is computed until R ′ r (i, e)-[R ′ (r)+γ •∑ ∀s∈OS(r) T (r, π(r) h , s)R ′ r (i, e)] < ε.
Finally, we compute T r (i, e) which describes the probability to reach the state i with the recommendation r for an entry state e and takes into account the possible cycles. In order to compute the probability to reach a state in OS from a state in ES, we replace the initial transition T and reward R function for each entry states of the recommended states: ∀e ∈ ES(r), o ∈ OS(r), T (e, π a (e), o) = T (e, π a (e), r) • T ′ r (o, e) and T (e, π a (e), r) = 0. In order to improve the performance of our algorithm, we aggregate some states in a partition G. With this approach, we reduce the new transition and reward computation by computing only for the partition G. The integration process is also improved.

We define a partition G = G 1 , ..., G n of S. G i is a set of states. A state s ∈ G i iff s ∈ U and ∃g ′ ∈ G i where T (s, π h (s), g ′ ) > 0 or ∃g ′ ∈ G i , T (g ′ , π h (g ′ ), s) > 0. We define ES and OS over G i rather than s as described previously as follows:

s ′ ∈ ES(G i ) iff ∃s ′ ∈ S, s ′ / ∈ G i ,∃s ∈ G i , T (s ′ , π a , s) > 0.
In the same way, we define

s ′ ∈ OS(G i ) iff ∃s ∈ S, s / ∈ G i ,∃s ′ ∈ G i , T (s ′ , π a , s) > 0.
When we know the agent's policy, we can compute the probability and the reward for an agent in a group G i to leave this group. In our approach, our goal is to reduce the state space for the agent by using given human's partial policy. For this end, we compute for each entry state in a partition G i , the reward and the probability to reach a state out of G i .

We use Equation 1 and 2 in order to compute T i (r) which describes the probability to reach the state i ∈ G i ∪ OS(r) with the recommendation r and takes into account the possible cycles. Then, we compute the probability ∀e ∈ ES(G i ), ∀o ∈ OS(G i )T ′ (e, o) and the reward R ′ (e). Then, we replace the initial transition T and reward R function for each entry state of the recommended states: ∀e ∈ ES(G i ), o ∈ OS(G i ), T (e, π a (e), o) = T (e, π a (e), r) • T ′ r (o, e) and T (e, π a (e), r) = 0.

In Figure 2, we present a small example of partial policy given by the human. The policy graph is represented where a vertex is a state and an edge is the transition probability. The states 1, 2 ,3 and 4 are in the set ES(g i ). The states o 1 , o 2 , o 3 , o 4 , o 5 and o 6 are in the set OS(g i ). We apply our algorithm to compute the transition function for the set g i of the partition G. The table of Figure 2 shows the results for each state in ES(g i ) and for each state in OS(g i ). For example, when the agent reaches the state 1, it has a probability of 0.6 to reach o 1 , 0.2 to reach o 2 and 0.2 to reach o 3 when it follows the human's recommendations. To improve our algorithm efficiency, we can avoid the computation of the states in OS(g i ). In this aim, we take into account the states reachable by the states in OS(g i ) when the policy π h is applicable. With our approach, the agent avoids the expected value computation of 11 states for this small policy. This number depends on the model transition function and the human's partial policy.

In our approach, we have presented how the human gives recommendations and how we translate these recommendations into a partial policy. Then a new agent's model is extracted from the human's recommendations in order to improve the integration time. Finally, in the next section, we present how the agents integrates a new model in its decision process. Another comment of this approach is that in general, the number of iteration is low. In order to be a good recommendation, the human's partial policy may avoid the cycle.

Human policy integration

In this section, we present how the agent integrates a new model computed with the algorithm described previously. We explain what are the conditions under which the agent's has to change its previously computed policy and how the agent updates its policy by taking the human's recommendations into account. We denote two steps in order to integrate the human's recommandation: how to compute the set of updating states affected by the recommandation and how to update the set of updating states.

The updated states definition

In this subsection, we present how to search the set D of states influenced by the human's recommendations. The states in D will needs to be updated when The updated algorithm is different because, the agent can use its policy and its expected value previously computed. For the agent point of view, its computed policy is the optimal policy. When the human gives recommendations on several states, she expresses that the agent has not all informations to compute the optimal policy. The expected value of the new global policy π G will always be lower than the expected value of π A from the agent point of view.

ES(g i ) OS(g i ) T 1 o 1 0.60 1 o 2 0.2 1 o 3 0.2 1 o 4 0 1 o 5 0 1 o 6 0 1 w 0 ES(g i ) OS(g i ) T 2 o 1 0 2 o 2 0 2 o 3 0.568 2 o 4 0.0648 2 o 5 0.1512 2 o 6 0.216 2 w 0 ES(g i ) OS(g i ) T 3 o 1 0 3 o 2 0 3 o 3 0.4 3 o 4 0.09 3 o 5 0.21 3 o 6 0.3 3 w 0 ES(g i ) OS(g i ) T 4 o 1 0 4 o 2 0 4 o 3 0.
Our aim is to update the agent policy by updating only the minimal subset of appropriate states (states which are affected with the recommendations). For this purpose, we consider the policy graph of an agent where a state is represented by a node. Two nodes s 1 and s 2 are connected if the probability to transit from s 1 to s 2 by following the policy is not null. The following Proposition concerns the choice of updated states. We define Parent(s, π(s)) as a function in which Parent(s, π(s)) = {s ′ ∈ S | T (s ′ , π(s), s) > 0}. Moreover, we define a rational policy π h when π h (s) = argmax a∈A,s∈U Q(s, a).

Proposition 1 When π H is good, π G is optimal.
Proof.

π G is optimal when ∀s ∈ S :

π G (s) = argmax a ∈ A, Q(s, a). • ∀s / ∈ D, π G (s) = argmax a∈A Q(s, a). That means π G is optimal. • ∀s ∈ D, π G (s) = π H (s). π H is rational means that π H is consistent and π H (s) = argmax a∈A,s∈U Q(s, a) , thus ∀s ∈ D, π G (s) = argmax a∈A Q(s, a). Consequently ∀s ∈ S : π G (s) = argmax a∈A Q(s, a).
In order to find all the updated states in the set D, we make a Breadth First Search from each states recommended in U in the policy graph of π A . We add a state in D if another action is not better than the optimal action with the new model.

More formally, we denote previously π A as the optimal policy. Let π A n the n-best policy where π A n (s) =

argmax a∈A\{π A n-1 (s)} Q(s, a)(π n < π n-1 < ... < π * ).
We deduce that π A = π A 1 . Let Q ′ (s, a) the Qvalue using the new transition and reward function where

Q ′ (s, a) = R ′ (s, a) + ∑ s ′ ∈OS(s) T ′ (s, a, s ′ )V (s ′ ) + ∑ s ′ / ∈OS(s) T (s, a, s ′ )V (s ′ )
In order to reduce the state space of reduced states, we present the following proposition.

Proposition 2 A policy π A (s) is optimal in s with s / ∈ U if and only if 1 < n <| A |: ∑ s ′ ∈S T (s, π A , s ′ )[V (s ′ )-V ′ (s)] > Q(s, π A (s))-Q(s, π A n (s))
Proof.

We know that π A is optimal if and only if

Q ′ (s, π A (s)) > Q ′ (s, π A n (s)) ⇔ Q ′ (s, π A (s)) > Q(s, π A n (s)) ⇔ Q(s, π A (s)) -∑ s∈S T (s, π A (s), s ′ )V ′ (s) -Q(s, π A n (s)) > 0 ⇔ ∑ s∈S T (s, π A (s), s ′ )[V (s) -V ′ (s)] > Q(s, π A (s)) -Q(s, π A n (s))
Discussion: The purpose of proposition 2 is to avoid as early as possible the useless states to update. We define a function called possibleChange(s) that gives a boolean if the policy change at states s. A state can added to D and the optimal policy doesn't change, but we detect this in the integration phase. We know that Q ′ (s, π A n (s)) < Q(s, π A n (s)), so we make the approximation Q ′ (s, π A (s)) > Q(s, π A n (s)) in order to reduce the computation time: the agent has already computed Q(s, π A n (s)). For each action, the agent evaluates only ∑ s∈S T (s, π A (s), s ′ )V ′ (s) -Q(s, π A n (s)). The transition often concerns a small subset of S (in our experimental test, this subset size is less than 4). We define T reachable the maximum number of states reachable with any transition. The computation of possibleChange(s) has a complexity of | A |• T reachable . We give the following definition based on proposition 1 and 2: Definition 2 A state s ∈ D if and only if:

• s ∈ Parent(s ′ , π(s ′ )) where s ′ ∈ D • ∑ s ′ ∈S T (s, π A , s ′ )[V (s ′ ) -V ′ (s)] > Q(s, π A (s)) - Q(s, π A n (s))
To compute the set of updated states D, we use an algorithm which finds all the states respecting the presented constraints.

Integrates the human's recommendation

In this section, we present how the agent update its policy already computed with the given human's recommendations. We present two different algorithms, one designed to integrate a partial policy, and another designed to integrates a model composed by a new transition and reward function. We present two different algorithms based on the updating state process using two steps : (i)defining a set of states D to update, (ii)updating the states in D and the state where the human gives her policy (U). The partial policy integration algorithm is mainly founded on this updating process while the new model integration algorithm improves the IHPP by combining the updatnig states process with the new model computation and integration.

The drawback of the IHPP algorithm is that the agent has to compute the expected value for the states where its policy is defined by human's recommendations (states in U). This computation is important in order to compute the expected value of the changing states (states in D). In this purpose, the computation of the new transition and reward function avoids the computation of the expected value of the states in U.

In the Integration Human's Transition and Reward function algorithm (IHTR), we can reduce the size of the updating states by taking advantage of the new transition and reward function. In the Efficient Algorithm for Human Integration section, we show how the agent computes a new transition and reward function. We take advantage of the new function previously computed in order to avoid the agent's policy computation. Moreover, we use this function to reduce the states to update: only the subset D is updated.

The advantage of the IHTR algorithm is that the agent integrates more quickly the new transition and reward function because the expected value of the set of state U is not computed. This difference is crucial, because the iteration number (n in our algorithm) is smaller in the IHTR than in IHPP algorithm.

Conclusion

In this paper, we have presented HHP-MDP: a new approach in order to integrate quickly human's help in the agent decision process. To this aim, we introduce the definition of recommendation which is the human's help given to the agent. We distinguish between these recommendations by three useful recommendations types for the UAV-an problem. Also, we present algorithms and methods which allow the agent to integrate quickly the human's recommendations. Our future work is to extends HHP-MDP with fuzzy recommendations and apply the recommendations into a complex model in order to solve problem of helping the agent in difficult situations. Another future works is to evaluate the human's recommandation and detect the inconsistancies.

Example of Space State Reduction in order to improve the agent's integration time the

  agent integrates the human recommendations.

			4
	4	o 4	0.0900
	4	o 5	0.21
	4	o 6	0.6
	4	w	0
	Figure 2.