<figure><img src="image_25.png" /><figcaption>Figure 4.13: An illustration of Markov decision models and POSGs: MDP is a subset of POMDP, which is again a subset of Dec-POMDP. Dec-POMDP is a special case of POSG, in which all agents share a same reward function.</figcaption></figure>

pair $\langle fsc_i^1, fsc_j^2 \rangle_{i,j=1}^N$ to see how good they perform. High overall scores would mean that no prior coordination is necessary in that problem.

We believe this approach will be useful in human-robot collaboration settings, where the human partner may often behave differently than a computed joint policy. For example, in a high-score collaboration problem, it is “safe” to equip the robot with a policy computed from a Dec-POMDP solver. However, if a low score is evaluated using this approach, it warns that the robot must be cautious and need to consider how to coordinate with the human.

## Solving Some Partially Observable Stochastic Games (POSGs)

POSGs (partially observable stochastic games) provide a more general framework for multi-agent decision-making that each agent having its own reward function. A Dec-POMDP is a special case of POSG where all agents share the same reward function, thus, are willing to collaborate (see Fig. 4.13). In general POSGs, the notion of optimal solution does not exist, and one typically searches for a Nash equilibrium. Also, solution policies often need to be stochastic, particularly in competitive settings.

In this thesis, Inf-JESP or MC-JESP search for deterministic Nash equilibria for Dec-POMDPs. One question is whether they could be adapted for “collaborative POSGs”, where the agents’ objectives (reward functions) are close to each other, in particular, to avoid unstable behaviors (oscillations). For more general cases in POSGs, a tentative approach is to ensure that each iteration of Inf-JESP or MC-JESP will not decrease the value for any agent. However, how to modify the value function to achieve this purpose is still an open question.
# Related Work on Task Planning for Human-Robot Collaboration

## 5.1 Overview of Task Planning in HRC

In Chapter 2, we describe several decision-making frameworks, including MDPs and POMDPs for the single-agent setting, and Dec-POMDPs for the multi-agent setting. For the multi-agent setting, we also provide a review of representative algorithms for solving Dec-POMDPs in Chapter 3 and give our contribution in this domain (see Chapter 4). In the HRC context, such a Dec-POMDP framework cannot be directly used since human partners may behave differently than the computed Dec-POMDP policies for several reasons:

* the computed policies are too complex for the human to learn;

* the human wants to be autonomous and is unwilling to blindly follow a pre-computed policy.

In some problems, there are unique and obvious ways of collaborating, but, in general, there may be multiple solutions, in particular, if the human also considers sub-optimal ones because he/she is not fully rational. As a consequence, for a given objective in HRC, the robot faces uncertain human behaviors, and we need to consider approaches that anticipate the human's possible behaviors. Moreover, unlike in a Dec-POMDP, where all agents optimize a shared objective function, the humans' real objectives in an HRC task may be hidden from the robots. Due to those factors, from the robot's point of view, to enable a successful collaboration in an HRC task: 1. the robot should have an idea about all the possible human objectives and behaviors and; 2. the robot needs to infer the human's current objective by considering these possibilities during execution.

However, a real question is how can we make the robot consider this uncertainty regarding human objectives and induced behaviors? In this thesis, inspired by Tabrez et al.'s work, we try to answer this question using the concept of *mental model* [Tabrez et al., 2020] to describe an explicit human model for the robot to predict human behaviors and infer his/her objective. Theoretically, in HRC, a robot could possess a mental model of a human (which may differ from actual human behaviors) among one of the following types:

* first-order mental model (1oMM): if a robot has a 1oMM of the human, then the robot assumes the human only considers himself when taking actions, i.e., the robot thinks the human behaves independently without considering the robot;
<figure><img src="image_26.png" /><figcaption>Figure 5.1: An illustration of the three types of mental models: first-order mental model (1oMM), second-order mental model (2oMM), and shared mental model (SMM).</figcaption></figure>

* second-order mental model (2oMM): in this case, the robot assumes the human also takes the robot into account, *i.e.*, the robot thinks the human also has a mental model of the robot, which makes the human behaviors are not independent and will be influenced by the robot's actions;

* shared mental model (SMM): in the shared mental model setting, the human and the robot rely on common knowledge and common reasoning to make coordinated decisions.

An illustration of those mental models (for modeling a human) from the robot's point of view is presented in Figure 5.1.

One can use mental models for human-robot collaboration for several purposes. For example, when robots are equipped with proper mental models of the human, they can better fit the collaboration task with improved performance and gain the trust of the human partner [Arnold et al., 2018, Tabrez and Hayes, 2019, Tabrez et al., 2020, Chen et al., 2020]. In this thesis, besides the uncertainty about human objectives and behaviors, we would like to address another challenge regarding coordination. In many HRC tasks, it is required that the human and robot work properly to adapt to each other's behaviors. For example, a repairing task needs the human and the robot to perform correctly repairing actions simultaneously; otherwise, the reparation will fail. The human and the robot should thus coordinate their behaviors at some point in order to successfully achieve the collaboration task. Therefore, for each mental model, we are interested in the following questions:

* How is the considered agent's *uncertainty* presented in the mental model?

* Does this mental model enable the **coordination** between humans and robots?

This chapter is organized as follows. A review of related works using 1oMMs or 2oMMs is given in Sec. 5.2 and Sec. 5.3. In Sec. 5.4, we present related works linked to SMM. We conclude by discussing the pros and cons of those mental models and position our contributions in Section 5.5.

## 5.2 HRC with first-order mental model

The first-order mental model (1oMM) is the most basic form for modeling other agents. The robot with a 1oMM of the human will assume its human partner only considers himself when
<figure><img src="image_27.png" /><figcaption>Figure 5.2: A collaborative collecting task [Karami et al., 2009]: In the grid-world environment, there are three objects $I_1$, $I_2$, and $I_3$. The human and the robot need to collect them to the box at the top right corner.</figcaption></figure>

taking actions. This simple assumption allows computing a human model by reasoning on a single-agent problem since the human does not consider the robot's presence or the actions the robot can perform. This implies that the problem can be solved without any help from the robot.

**Planned human policy inside a robot POMDP** Karami et al. propose such an HRC scenario, as shown in Figure 5.2, where the robot has a 1oMM of its human partner [Karami et al., 2009, Karami, 2011]. In this work, the goal of the human-robot team is to collect all items to the target box, and an MDP is used to define the collaboration task's underlying transition and reward functions. During the task, the robot must respect the human's current intention $I_h$, which means the robot should avoid collecting the same object as the human. The robot could observe the executed human action at each time step. However, from the robot's point of view, the human's intention $I_h$ is hidden. Therefore, they model the robot's decision process as a POMDP where $I_h$ is an unobservable variable.

More specifically, Karami designs the robot decision framework as shown in Figure 5.3 with following steps:

* A set of human MDPs is built for each human intention. In each human MDP, the human has full observability of the environment and does not account for robot behaviors.

* The human MDPs are solved to generate a library of Q-values (human action values), which is a mapping from pairs of environment states and human intentions to values.

* Those Q-values are used to derive a probability distribution of human actions in each situation (environment state + human intention) and are considered as parts of the dynamics in robot POMDP. One should note that, in Karami's work, the robot can observe the human action performed.

The robot policy is then computed by solving this robot POMDP. Through experiments in this specific scenario, they show that the robot can estimate the human intention and make its decisions accordingly.
<figure><img src="image_28.png" /><figcaption>Figure 5.3: The high-level process of the robot decision system [Karami, 2011]</figcaption></figure>

**Other related works** Similar “robot POMDPs” are solved in other existing works [Nikolaidis et al., 2016, 2017]. For example, Nikolaidis et al. introduces a bounded memory adaption model (BAM), which captures human adaptive behaviors based on an assumption of bounded memory during interactions [Nikolaidis et al., 2016]. Then, the robot integrates BAM into a POMDP decision framework to reason about its actions. But in this work, another interesting idea is the human’s bounded rationality (linked to bounded memory). Their HRC experiments demonstrate that the robot can adapt to erratic human behaviors that are not optimal for a given human objective function. One can identify similar approaches to adding noise in considered human behaviors or parameterized human action selection function [Osogami and Otsuka, 2014, Otsuka and Osogami, 2016, Nikolaidis et al., 2017, Chen et al., 2018].

**Limitations of 1oMMs for HRC** However, coordination between the real human and robot may be difficult when the robot uses a 1oMM of the human. For example, in a cooperative repairing scenario, only both agents simultaneously repairing could fix a damaged device. But if the robot (with a 1oMM about the human) assumes that the human does not consider the robot’s behaviors (which may differ from the real human), then the robot will deduce that the human will not be able to carry out the repair action in time. Consequently, the robot has no reason to attempt the repair action since it assumes this action cannot bring any benefit. Some existing works, including the one we mentioned above [Karami et al., 2009, Karami, 2011], do not require coordination between humans and robots to finish the task. The robot’s role is more like a helper or assistant who accelerates or simplifies the ongoing tasks.

**How to Derive a 1oMM of the human** In HRC, there are several ways to build a 1oMM about the human (for the robot):

1. a hand-made human policy [Nikolaidis et al., 2016, Chen et al., 2018], where the designer uses expert knowledge to implement a 1oMM of the human;

2. a learned human policy by observing one's behaviors [Chen et al., 2020], or human's reward function using inverse reinforcement learning (IRL) [Russell, 1998, Ng and Russell, 2000], which estimates the parameters of a function that best explains the observed behaviors;

3. a planned human policy where human behaviors are derived by solving specific problems, i.e., human-MDPs [Karami et al., 2009].
To sum up, the 1oMM is easy to understand and effective in several scenarios. Moreover, to let the robot consider a variety of human behaviors, the action selection function can be parameterized with different factors such as “memory” or “trust” in the robot’s 1oMM of the human or simply adding noises. However, the main drawback of 1oMMs is also obvious. It will fail in many tasks requiring explicit collaborative behaviors from the human. In other words, 1oMMs are suitable for those tasks that a human could achieve on his own, and the robot helps to accelerate or simplify the process.

## 5.3 HRC with Second-order Mental Model

Compared with a 1oMM, a robot with a 2oMM of the human will consider that the human behaves while taking the robot into account. But then, a question is raised: what is the human’s mental model of the robot? Is it a 1oMM, a 2oMM or an SMM? As can be observed, 2oMMs can be recursively nested with an infinite depth, as illustrated in Figure 5.1 (middle), which may be interpreted as “I believe that you believe that I believe ...” [Tabrez et al., 2020]. The nesting can be finite if stopped with a final 1oMM or SMM. Such nested consideration is essential and often used in our daily lives, such as in negotiations or playing chess. In those cases, one must consider the possible actions the others might take and how their behaviors may trigger others’ different strategies.

**Reasoning about Others** In 1980s, researchers already paid attention to this kind of nested-reasoning decision problem [Maida, 1986, Wilks and Ballim, 1987]. For example, Wilks and Ballim propose a method to generate nested beliefs heuristically for natural language understanding about “what some agents believe on others’ beliefs given a specific topic”. Then, with the progress of the decision-making community, especially in the Markov decision process domain, based on the POMDP framework, Doshi and Gmytrasiewicz proposed the *Interactive POMDP* (I-POMDP) formalism [Doshi and Gmytrasiewicz, 2005], which models the decision-making problem with one agent with recursive reasoning about other agents. An interactive POMDP for agent *i*, denoted $I-POMDP_i$, is defined as follows:

$$I-POMDP_i = \langle IS_i, A, T_i, \Omega_i, O_i, R_i \rangle,$$

where $A = A_i \times A_j$ is the joint action set of all agents, and $\Omega_i$ is agent *i*'s observation space. $T_i$, $O_i$ and $R_i$ are the underlying dynamics in agent *i*'s view. Here, one may wonder how to describe these dynamics with only agent *i*'s action since we are in a multi-agent setting. This is linked to the *interactive states* $is_i$, which belongs to $IS_i$, a set of interactive states which is a combination of world states and other agent *j*'s possible models $IS_j = S \times M_j$. An agent *j*'s model $m_j$ is defined as

$$m_j = \langle h_j, f_j, O_j \rangle, \quad m_j \in M_j, h_j \in H_j,$$

where:

* $h_j$ is agent *j*'s observation history, and $H_j$ is the set of all the possible histories of agent *j*;

* $f_j$ is agent *j*'s action-selection function, assumed computable, which maps possible observation histories of agent *j* to distribution over its actions;

* $O_j$ is the observation function of agent *j*.
To that end, one can construct $M_j$ with two approaches, either the agent $j$ models other agents again (recursive modeling) or simply uses a naive assumption such as agent $j$ behaves with a uniform action distribution (in this case, any $m_j \in M_j$ is a 1oMM for agent $i$). Although this is a complex formalization, it is generic enough to represent agent $i$'s decision, and its belief over the interactive states is a sufficient statistics. Therefore, many works for interactive applications adapt the I-POMDP formalization, such as in dialogue systems [Wang, 2013] and turn-based games [Rosello, 2016], and provide scaling-up extensions [Hoang and Low, 2013, Han and Gmytrasiewicz, 2019].

**Comparison with 1oMMs** Regarding coordination, 2oMMs give one possible path to let agents consider each other. This inter-consideration enables the coordination between agents. However, as already mentioned, a chicken-and-egg problem becomes unavoidable with 2oMMs. When we build a 2oMM of a human for the robot, the human behaviors are also influenced by the robot's behaviors which we are trying to derive in the first place. For example, learning a 2oMM from real human behaviors would require that a working collaborative robot already exists to demonstrate collaborative behaviors. This issue is also unavoidable when we model the robot's decision-making with 2oMM of the human as an I-POMDP described above.

Regarding the diversity of human behaviors, 2oMMs share the same properties as 1oMMs. The considered agent may have different probabilities on his action selections. But compared with 1oMMs, the reward which drives the agents' behaviors in 2oMMs can be related not only to its actions but also to the actions of all agents.

Given those pros and cons, 2oMMs are suitable for complex collaboration HRC tasks where humans and robots must consider each other's behaviors and coordinate their actions. The main disadvantage is that we need to address the chicken-and-egg problem when building a 2oMM.

## 5.4 HRC with Shared Mental Model

In a shared mental model, all team members assume they have the same expectation and reason in the same manner. This setting enables all agents in a team can coordinate their behaviors and lead to performance improvement regarding the joint policy [Tabrez et al., 2020]. For example, if we solve a multi-agent problem modeled using a Dec-POMDP and obtain an optimal joint policy, then it implies that each agent knows other agents will behave according to the computed joint policy, which naturally means all agents have a shared mental model.

**Human-Robot Cross-Training** Based on the SMM assumption, Nikolaidis and Shah propose a human-robot cross-training framework where the shared mental model is formulated as an MDP [Nikolaidis and Shah, 2013]. In their work, the robot policy is aligned with human preferences, and the robot will switch its role with the human iteratively during training. Compared with the standard reinforcement learning method, in which the human and the robot never switch their roles. They show that this cross-training approach helps the team learn a shared plan for a collaborative task and significantly improves performance in different aspects, including trust and fluency.

**Cooperative Inverse Reinforcement Learning** Another well-known work based on the SMM is the cooperative inverse reinforcement learning (CIRL) framework proposed by Hadfield-Menell et al., which is designed for a cooperative human-robot team setting [Hadfield-Menell et al., 2016]. All state variables are visible in a CIRL problem except the human's actual reward
function, represented by a generalized parameter $\theta$, which is hidden to the robot. Both the human and the robot should maximize the human's reward function. Since only $\theta$ is hidden from the robot, CIRL reduces this two-agent cooperative decision problem to a POMDP and seeks a pair of policies $(\pi_H, \pi_R)$ for the human and robot. Under the shared mental model assumption, CIRL assumes that the human will follow the computed policy $\pi_H$. Therefore, the computed joint policy of the human and robot is optimal, which maximizes the human's true objective $\theta$. Moreover, they point out that such a solution can be used for active teaching (human) and active learning (robot) behaviors.

**Pros and Cons** Technically, the main disadvantage of using the shared mental model in human-robot collaboration is its strong assumption of sharing policies (or action selection functions) among all agents. In practice, this condition is often too difficult to satisfy or requires specially designed scenarios [Nikolaidis and Shah, 2013]. But if this assumption is satisfied, SMMs seem to be an ideal tool for enabling coordination between humans and robots (Using SMMs allows, in theory, for optimal coordination, but computing an optimal solution may be very difficult, cf. Dec-POMDP solving complexity). Given a known objective for the human-robot team, there is no need to consider others' diversities in their behaviors since the knowledge of action selection during the task is shared. On the other hand, to build an SMM between the human and robot, one way is to relax the HRC problem to a multi-agent problem, for which we compute a joint policy of all agents. Then, depending on the uncertainties and observations, standard methods for POMDPs or Dec-POMDPs can be used for such purposes. Or another approach is to use the cross-training method as presented in Nikolaidis and Shah's work so that the human and the robot can all agree to converge on a shared plan.

## 5.5 Conclusion

To sum up, for robots' decision-making in an HRC task, robots equipped with 1oMM can provide effective policies for simple tasks where no mandatory coordination is needed between humans and robots. 2oMMs, on the other hand, let the robot consider the possible behaviors of the human and vice-versa, thus enabling necessary coordination, but a chicken-and-egg problem will appear, and one needs to design a specific solution at a certain depth to stop this recursive nesting. SMMs rely on a strong assumption of common expectations, thus, they are suitable for teaching or being guidelines for the human partner to learn, but it may be complex given the HRC problem at hand.

We conclude by presenting Markov decision models that correspond to the three types of mental models as in Table 5.1:

* Single-agent models (MDPs and POMDPs) allow modeling robots with a 1oMM or 2oMM of the human, by incorporating the human model in the system dynamics (human is seen as part of the robot's environment).

* I-POMDPs are meant to model finitely nested 2oMMs. But one can also transform an I-POMDP into a POMDP with an extended state to express that recursive reasoning information.

* M(PO)MDPs and Dec-POMDPs are meant to model collaborative problems, thus SMMs (assuming that all agents fully collaborate and optimize the exact same performance criterion). In MPOMDPs, all agents have access to the same information at execution time, so
<table><caption>Table 5.1: Table of relations between mental models and Markov decision frameworks</caption><thead><tr><th>Mental Model Type</th><th>1oMM</th><th>2oMM</th><th>SMM</th></tr></thead><tbody><tr><td>Decision Making Framework</td><td>(PO)MDP</td><td>POMDP, I-POMDP</td><td>M(PO)MDP, Dec-POMDP</td></tr></tbody></table>

solving an MPOMDP amounts to solving a POMDP; In MMDPs, all agents can directly access the real environment state at each time step, which equals solving an MDP; Dec-POMDPs represent problems where each agent has its own view of the current situation.

In this thesis, we are interested in collaboration tasks where one human and one robot need to coordinate their behaviors, and the ability to consider others' behaviors is necessary. Therefore, in the robot's view, a 1oMM of the human is unfit in this case, and SMM's assumption of common exceptions is too strong and unrealistic in our setting. Thus, we have chosen a 2oMM to model the human for the robot, and propose our contributions to solve the chicken-and-egg problem in Chapter 6.

One could view our approach as improving Karami et al.'s work (see Section 5.2, page 67) on the following aspects:

* We choose to equip the robot with a 2oMM of the human, which enables necessary coordination, but is not possible in Karami et al.'s work with 1oMMs;

* We extend their work to partial observability settings where each agent only observes partial information;

* We provide a tunable method to adjust the rationality of the human considered by the robot.

Moreover, no prior human behavior is needed in our approach, therefore it can tackle various HRC problems.
Robust Decision Making for
Human-Robot Collaboration

In this chapter, we present our contributions to generate robust robot policies for human-robot collaboration (HRC) tasks. Unlike the multi-agent decision problems modeled as Dec-POMDPs, where optimal policies are computed for all agents, we can only control the robot in HRC, and the human exhibits uncertain behaviors. This being said, from the robot's point of view, an issue is how to be robust against uncertain human objectives or uncertain human behaviors, even given a known objective. Usually, the robot relies on a mental model of the human partner to predict human actions and then make its own decisions. In Chapter 5, we have discussed three possible (robot's) human mental models as follows:

* First-order mental model (1oMM): the robot considers that the human behaves independently and does not account for the robot's possible actions;

* Second-order mental model (2oMM): the robot thinks that the human also accounts for the robot, which induces recursive modeling up to a certain depth;

* Shared mental model (SMM): all agents have common expectations and reason in the same manner, thus ensuring optimal coordination between the human and the robot.

In our work, we do not consider 1oMMs since our HRC task needs the human and the robot to coordinate their behaviors, requiring the human to consider the robot's behaviors, and the SMMs' assumption about common expectations is too strong for collaborations with real humans. Therefore, we choose to equip the robot with a 2oMM of the human partner. However, as we mentioned in Chapter 5, a 2oMM raises a chicken-and-egg problem since modeling required human behaviors implies reasoning about the robot behavior we are trying to derive in the first place, as shown in Figure 6.1 (a).

In this thesis, we propose a way to address this chicken-and-egg problem by answering the question: "What would be the human policy if he or she could also control the robot?" To do this, we temporarily assume that the human and the robot share their observations, which makes the human (the one in the robot's mental model, not the real human) consider a particular SMM, as presented in Figure 6.1 (b). Then, we develop a general 3-step scheme for HRC tasks as follows:

1. solving the collaboration problem under the SMM assumption;

2. extracting a human model from the SMM solution;
<figure><img src="image_29.png" /><figcaption>Figure 6.1: A comparison of two 2oMMs: (a) the first 2oMM has a chicken-and-egg issue with an infinite loop of considerations; (b) the robot in the second one assumes that the considered human behaves according to an SMM.</figcaption></figure>

3. computing a robot policy using the generated human model.

Based on this general scheme, two algorithms (see Section 6.1 and Section 6.2) are proposed in this thesis for deriving such human mental models and robot policies, which respectively operate in an offline and online manner. The human mental model is dedicated to deriving robot policies robust to a variety of possible actual human behaviors. This model is thus not meant to represent any human in particular. Our approach should ideally be evaluated against a variety of actual human behaviors

This chapter is organized as follows: In Section 6.1 and Section 6.2, we present two original methods: an offline and online robot robust planning algorithm for HRC tasks. Finally, Section 6.3 presents empirical results obtained with both synthetic and real humans on a high-level task in a simulated environment.

## 6.1 Offline Robust Planning for HRC

As previously mentioned, this chapter aims to address the uncertainty of the human's actual objective and exhibited human behaviors to derive a robust robot policy for HRC tasks. To do so, we first present the offline algorithm for building a robust robot policy, which is illustrated in Figure 6.2. First, we use Dec-POMDPs to model the collaboration problem for the various possible human objectives. These Dec-POMDPs only differ in their reward functions, each modeling a specific human objective. Then, for each human objective (each Dec-POMDP), we generate a stochastic FSC representing a variety of possible human behaviors as described in Section 6.1.1. A robust robot POMDP decision model is built in Section 6.1.2 based on the Dec-POMDP task model and the generated human stochastic FSCs. In the end, we use SARSOP [Kurniawati et al., 2008] to solve this robot POMDP and get a robust robot policy.
<figure><img src="image_30.png" /><figcaption>Figure 6.2: The structure of the offline robust robot planning algorithm</figcaption></figure>

### 6.1.1 Generating Human Stochastic FSCs with a Bounded Size

As stated before, an issue when building the human mental model for the robot is that the human policies depend on the robot policies we don't have in the first place. To overcome this chicken-and-egg problem:

* We make a temporary assumption that the human in the mental model behaves according to an SMM, in which the human can control the robot with direct access to its observations (see Figure 6.1(b) - Step 1);

* Then, we extract a human policy presented by a stochastic FSC from the SMM solution, corresponding to the human model presented in Figure 6.1(b) - Step 2.

This approach ensures that the generated human FSC considers robot behaviors since this human FSC is extracted from the SMM solution, which accounts for both agents' behaviors.

To be more specific, for each human objective, the corresponding Dec-POMDP is relaxed to an MPOMDP (Multi-agent POMDP) [Pynadath and Tambe, 2002], i.e., a single-agent problem that an agent has access to the joint observation and control the joint action (the first part in Figure 6.2) given the SMM assumption. This MPOMDP can be fed to a POMDP solver to compute an optimal joint policy, which maps beliefs (or joint action-observation histories) to joint actions of the human and the robot, corresponding to the Step 1 part of Figure 6.1(b).
However, this joint policy is not directly usable for the robot since it's not a proper human behavior model, i.e., a mapping from human action-observation histories (alone) to human actions. To do so, we extract a human policy (Figure 6.1(b) - Step 2) from the joint policy assuming that the human:

1. does not control the robot anymore; and

2. considers that the robot still has access to the same belief b as inferred by the human.

Then, given a belief b, we can model the uncertainty over human behaviors using a softmax function over action values to obtain a distribution over multiple optimal or near-optimal actions:

$$f(a|T, b) = \frac{e^{\frac{Q^{*}(b,a)}{T}}}{\sum_{a'} e^{\frac{Q^{*}(b,a')}{T}}}$$

where $T > 0$ is a temperature parameter that makes the human more rational if $T$ is low, only optimal actions being selected, and more erratic if $T$ is high, with a distribution close to uniform. The robot considers that the human selects actions according to this softmax distribution. Moreover, since the human and the robot are now independent, and the human considers the robot has access to the same belief that $b_H = b_R = b$, we can define their action sampling rules $\sigma_H^T$ and $\sigma_R^T$ as follows:

$$\sigma_H^T(a_H|b) \stackrel{\text{def}}{=} \sum_{a_R} f(a_H, a_R|T, b), \text{ and}$$

$$\sigma_R^T(a_R|b) \stackrel{\text{def}}{=} \sum_{a_H} f(a_H, a_R|T, b).$$

Knowing these two action sampling rules, the human is able to update his belief in a Dec-POMDP given his last pair $(a_H, o_H)$ by marginalizing the robot's private actions and observations as follows:

$$b'(s') = \mathrm{Pr}(s'|b, a_H, o_H, \sigma_R^T(\cdot|b)) = \frac{\mathrm{Pr}(s', o_H|b, a_H, \sigma_R^T(\cdot|b))}{\sum_{a_H} \mathrm{Pr}(s', o_H|b, a_H, \sigma_R^T(\cdot|b))} \quad (6.1)$$

$$\propto \sum_{s,a_R} \mathrm{Pr}(s', o_H|s, \langle a_H, a_R \rangle) \cdot \sigma_R^T(a_R|b) \cdot b(s) \quad (6.2)$$

$$= \sum_{s,a_R,o_R} \mathrm{Pr}(s', \langle o_H, o_R \rangle | \langle a_H, a_R \rangle) \cdot \mathrm{Pr}(s'|s, \langle a_H, a_R \rangle) \cdot \sigma_R^T(a_R|b) \cdot b(s) \quad (6.3)$$

$$= \sum_{a_R} \left( \sum_{o_R} O(\langle a_H, a_R \rangle, s', \langle o_H, o_R \rangle) \right) \cdot \left( \sum_{s} T(s, \langle a_H, a_R \rangle, s') \cdot b(s) \right) \cdot \sigma_R^T(a_R|b). \quad (6.4)$$

As expected, it relies solely on the Dec-POMDP's transition and observation functions, the previous belief b, and the robot's action sampling rule for that belief (and conditioned on the current human action).

**Sampling a Stochastic Human FSC** Following these ideas and processes we mentioned above to pick a human action and to update his belief, we first designed Algorithm 14, which recursively extracts a human policy (represented as a stochastic FSC) building on the method
presented in Section 4.1.3 for standard POMDPs. In the beginning, a unique start node $n_0$ is created (line 2) with $\sigma_H^T(\cdot|b_0)$, $\sigma_R^T(\cdot|b_0)$, $b_0$ and the initial weight $w = 1$. Then $n_0$ is added to both the new FSC ($N$) and an open list ($G$) (line 3). Getting inspiration from LAO* [Hansen and Zilberstein, 2001], we would like to expand the node with the greatest contribution to $b_0$'s value at each iteration. Thus, while $G$ is not empty, we select the node $n \in G$ that has the highest estimated value $V^*(n.b)$, weighted by the probability of reaching that node (estimated through $n.w$) (line 6), then process that node with possible observation-action pairs under current belief $b$ (lines 7–9), impossible observation-action pairs inducing a self-loop (line 22). Those self-loops ensure that the resulting human FSC can be used whatever the robot's actual behavior (which may cause unexpected human observations). Lines 10 and 11 compute the updated belief $b'$ and its weight $w'$ (see detailed formulas below). Before creating a new node $n'$ with those new computed components, we also need to check:

1. if the new belief $b'$ does not already exist inside the FSC ($N$) considering a Norm-1 distance threshold $\epsilon$:

$$b' \in N(\epsilon) \text{ iff } \exists n \in N \text{ s.t. } \|n.b - b'\|_1 (\stackrel{\text{def}}{=} \sum_s |n.b(s) - b'(s)|) \le \epsilon;$$

2. if the FSC does not already contain the maximum node size $N_{max}$.

If both conditions are satisfied (line 12), we create a new node $n'$ and add it to $N$. Otherwise, we find and process the node $n'$ in $N$ which has the closest belief to the new computed belief $b'$. The probability used for updating weights in line 11 is derived from

$$\Pr(o_H, a_H|b, \sigma_H^T(\cdot|b), \sigma_R^T(\cdot|b)) = \sum_{a_R} \Pr(o_H, \langle a_H, a_R \rangle|b, \sigma_H^T(\cdot|b), \sigma_R^T(\cdot|b)) \quad (6.5)$$

$$= \sum_{a_R, o_R, s, s'} \Pr(s, s', \langle o_H, o_R \rangle, \langle a_H, a_R \rangle|b, \sigma_H^T(\cdot|b), \sigma_R^T(\cdot|b)) \quad (6.6)$$

$$= \sum_{a_R, o_R, s, s'} b(s) \cdot \Pr(s', \langle o_H, o_R \rangle|s, \langle a_H, a_R \rangle) \cdot \sigma_H^T(a_H|b) \cdot \sigma_R^T(a_R|b) \quad (6.7)$$

$$= \sum_{a_R, o_R, s, s'} b(s) \cdot \Pr(\langle o_H, o_R \rangle|s, \langle a_H, a_R \rangle, s') \cdot \Pr(s'|s, \langle a_H, a_R \rangle) \cdot \sigma_H^T(a_H|b) \cdot \sigma_R^T(a_R|b) \quad (6.8)$$

$$= \sum_{a_R, o_R, s, s'} b(s) \cdot O(\langle a_H, a_R \rangle, s', \langle o_H, o_R \rangle) \cdot T(s, \langle a_H, a_R \rangle, s') \cdot \sigma_H^T(a_H|b) \cdot \sigma_R^T(a_R|b). \quad (6.9)$$

This approach extracts a bounded-size stochastic FSC $\langle N, \eta, \psi \rangle$, which includes $|N|$ nodes, encoding several human behaviors. For each node $n \in N$, the human's stochastic action selection function is defined as $\psi(n, a_H) = \sigma_H^T(a_H|n.b)$. Deterministic transitions between nodes are stored in $\eta$ and depend on the human action-observation pair $\langle a_H, o_H \rangle$. Note that our algorithm allows trading of the FSC quality with its complexity through

1. bounding the FSC's number of nodes by $N_{max}$;

2. merging nodes when their reference beliefs (the beliefs used when creating the nodes) are within $\epsilon$ of each other.

In our experiments, all $Q^*(b, a)$ and $V^*(b)$ values are estimated using 1. SARSOP for offline pre-computations [Kurniawati et al., 2008], and 2. POMCP to obtain good estimates online quickly, even in beliefs not visited by an optimal policy [Silver and Veness, 2010].
<caption>**Algorithm 14:** Extract a human stochastic FSC</caption>

1 **[Input:]** T: softmax temperature | N<sub>max</sub>: max # of nodes | ϵ: max belief gap
2 n<sub>0</sub> ← node(⟨σ<sub>H</sub><sup>T</sup>(·|b<sub>0</sub>), σ<sub>R</sub><sup>T</sup>(·|b<sub>0</sub>), b<sub>0</sub>, w = 1⟩)
3 N ← {n<sub>0</sub>}
4 G.pushback(n<sub>0</sub>)
5 **while** |G| > 0 **do**
6   G.sort() // sort nodes according to w · V<sup>*</sup>(b)
7   n ← ⟨σ<sub>H</sub><sup>T</sup>, σ<sub>R</sub><sup>T</sup>, b, w⟩ ← G.popfront()
8   **forall** ⟨o<sub>H</sub>, a<sub>H</sub>⟩ ∈ Ω<sub>H</sub> × A<sub>H</sub> **do**
9   if Pr(o<sub>H</sub>, a<sub>H</sub>|b, σ<sub>H</sub><sup>T</sup>) > 0 **then**
10    b' ← updateBelief(b, a<sub>H</sub>, o<sub>H</sub>, σ<sub>R</sub><sup>T</sup>(·|b))
11    w' ← w · Pr(o<sub>H</sub>, a<sub>H</sub>|b, σ<sub>H</sub><sup>T</sup>(·|b), σ<sub>R</sub><sup>T</sup>(·|b))
12   if (b' ∉ N(ϵ)) ∧ (N.size() < N<sub>max</sub>) **then**
13    n' ← node(⟨ψ(n', ·) def= σ<sub>H</sub><sup>T</sup>(·|b'), σ<sub>R</sub><sup>T</sup>(·|b'), b', w'⟩)
14    N ← N ∪ {n'}
15    G.pushback(n')
16    η(n, ⟨a<sub>H</sub>, o<sub>H</sub>⟩, n') ← 1
17   else
18    n' ← N.findClosest(b')
19    n'.w ← n'.w + w'
20    η(n, ⟨a<sub>H</sub>, o<sub>H</sub>⟩, n') ← 1
21   else
22    η(n, ⟨a<sub>H</sub>, o<sub>H</sub>⟩, n') ← 1
23 **return** ⟨N, η, ψ⟩

**Sampling a Deterministic Human FSC** We also designed another method to extract a deterministic human FSC as in Algorithm 15. This algorithm will be used for generating human policies to simulate various humans in our experiments. As shown in red, it differs from Algorithm 14 only in that, in any node, a single human action is used, rather than a probability distribution over human actions. In other words, this method is achieved by replacing each node's distribution over human actions by a single action sampled from that distribution.

6.1.2 Building a robot best response policy

Here we want the robot to be robust to different possible (hidden) human objectives, each
attached to different behaviors, trying to adapt to the human's actual objective. Please note
that the collaboration task itself is modeled as a Dec-POMDP, except that:

* the exact reward function (among ρ candidates) is only known by the human;

* for each possible reward function rᵢ, we can compute a human behavior model (in the form of a stochastic FSC fscᵢ); and

* the robot knows a probability distribution over the finitely many possible reward-FSC pairs: P({(r₁, fsc₁), ..., (rρ, fscρ)}).
<caption>**Algorithm 15:** Sample a human deterministic FSC</caption>

1 **[Input:]** *T*: softmax temperature | *N*<sub>max</sub>: max # of nodes | *ε*: max belief gap
2 *n*<sub>0</sub> ← node(<span style="text-decoration: overline;">⟨a<sub>H</sub> ~ σ<sub>H</sub><sup>T</sup>(·|b<sub>0</sub>), σ<sub>R</sub><sup>T</sup>(·|b<sub>0</sub>), b<sub>0</sub>, w = 1⟩</span>)
3 *N* ← {*n*<sub>0</sub>}
4 *G.pushback*(*n*<sub>0</sub>)
5 **while** |*G*| > 0 **do**
6   *G.sort*() // sort nodes according to *w* · *V*<sup>*</sup>(*b*)
7   *n* ≡ ⟨a<sub>H</sub>, σ<sub>R</sub><sup>T</sup>, b, w⟩ ← *G.popfront*()
8   **forall** *o*<sub>H</sub> ∈ Ω<sub>H</sub> **do**
9      **if** Pr(*o*<sub>H</sub>, *a*<sub>H</sub>|*b*, σ<sub>H</sub><sup>T</sup>) > 0 **then**
10         *b'* ← updateBelief(*b*, *a*<sub>H</sub>, *o*<sub>H</sub>, σ<sub>R</sub><sup>T</sup>(·|*b*))
11         *w'* ← *w* · Pr(*o*<sub>H</sub>, *a*<sub>H</sub>|*b*, σ<sub>H</sub><sup>T</sup>(·|*b*), σ<sub>R</sub><sup>T</sup>(·|*b*))
12      **if** (*b'* ∉ N(*ε*)) ∧ (N.size() < *N*<sub>max</sub>) **then**
13         *n'* ← node(<span style="text-decoration: overline;">⟨a<sub>H</sub> ~ σ<sub>H</sub><sup>T</sup>(·|*b*'), σ<sub>R</sub><sup>T</sup>(·|*b*'), *b'*, *w'*⟩</span>)
14         *N* ← *N* ∪ {*n'*}
15         *G.pushback*(*n'*)
16         η(*n*, ⟨*a*<sub>H</sub>, *o*<sub>H</sub>⟩, *n'* ← 1
17      **else**
18         *n'* ← *N.findClosest*(*b'*)
19         *n'.w* ← *n'.w* + *w'*
20         η(*n*, ⟨*a*<sub>H</sub>, *o*<sub>H</sub>⟩, *n'* ← 1
21   **else**
22      η(*n*, ⟨*a*<sub>H</sub>, *o*<sub>H</sub>⟩, *n* ← 1
23 **return** ⟨*N*, η, ψ⟩

As detailed below, this robust robot behavior is obtained by

1. first turning this distribution over stochastic FSCs into a single FSC,

2. then using this FSC to derive a POMDP, and

3. finally solving this POMDP.

A candidate solution method to obtain one FSC for each reward function is presented in Sec. 6.1.1.

To turn this probability distribution over human FSCs into a single FSC, we take the “union” of these FSCs, the new distribution over initial nodes amounting to 1. sampling one FSC *fsc*<sub>*i*</sub> from the distribution *P*({*fsc*<sub>1</sub>, ..., *fsc*<sub>*ρ*</sub>}), and 2. sampling a node from *β*<sub>*i*</sub>. More formally, noting a base FSC *fsc*<sub>*i*</sub> ≡ ⟨*N*<sub>*i*</sub>, *β*<sub>*i*</sub>, *η*<sub>*i*</sub>, *ψ*<sub>*i*</sub>⟩, the *union FSC* is defined as:

$$
\begin{align*}
N &\stackrel{\text{def}}{=} \bigcup_{i=1}^{\rho} N_i, \\
\beta(n_i) &\stackrel{\text{def}}{=} \beta_i(n_i) \cdot P(fsc_i), \\
\eta(n, \langle a, o \rangle, n') &\stackrel{\text{def}}{=} \begin{cases} \eta_{i(n)}(n, \langle a, o \rangle, n') & \text{if } n' \in N_{i(n)}, \\ 0 & \text{otherwise,} \end{cases}
\end{align*}
$$
(where $i(n) \stackrel{\text{def}}{=} i$ s.t. $n \in N_i$, i.e., $i(n)$ is the id of $n$'s parent FSC), and

$$ \psi(n, a) \stackrel{\text{def}}{=} \psi_{i(n)}(n, a). $$

Moreover, as detailed in Algorithm 14, each stochastic FSC node is linked to a specific human belief $b_H^t$, and each stochastic human FSC is linked to a human objective $\theta_H$. Thus, using this union FSC, the pair of human's objective and internal belief $\langle \theta_H, b_H^t \rangle$ is now represented by the human union FSC node $n_H$. Given this union FSC, we can now formalize the robot's decision problem as a POMDP where each extended state $e^t \in \mathcal{E}$ contains a current world state $s^t$, a current robot observation $o_R^t$, and the current node $n_H^t$ inside the human union FSC: $e^t = \langle s^t, n_H^t, o_R^t \rangle$. Based on the Dec-POMDP defining the task and on the associated union FSC, the dynamics and the reward function of the robot's decision problem can be written as follows:

$$
\begin{align*}
T_e(e^{t+1}, e^t, a_R^t) &\stackrel{\text{def}}{=} \Pr(e^{t+1} | e^t, a_R^t) \\
&= \sum_{a_H^t} \sum_{o_H^{t+1}} T(s^t, \langle a_H^t, a_R^t \rangle, s^{t+1}) \cdot \eta(n_H^t, \langle a_H^t, o_H^{t+1} \rangle, n_H^{t+1}). \\
O(s^{t+1}, \langle a_H^t, a_R^t \rangle, \langle o_H^{t+1}, o_R^{t+1} \rangle) &\cdot \psi(n_H^t, a_H^t), \\
O_e(e^{t+1}, a_R^t, o_R^{t+1}) &\stackrel{\text{def}}{=} \Pr(o_R^{t+1} | e^{t+1}, a_R^t) \\
&= \mathbf{1}_{o_R^{t+1} = \tilde{o}_R^{t+1}}, \text{ and} \\
r_e(e^t, a_R^t) &\stackrel{\text{def}}{=} \sum_{a_H^t} r_i(n_H^t)(s^t, \langle a_H^t, a_R^t \rangle) \cdot \psi(n_H^t, a_H^t).
\end{align*}
$$

Solving this robot POMDP gives a robust robot policy that best responds to the initial probability distribution over the given human policies. This offline algorithm is evaluated in Section 6.3.

## 6.2 Online Robust Planning for HRC

The last section presents an offline algorithm for building a robust robot policy. As we discussed in Section 6.1.2, if a human model (presented by a stochastic FSC) is known, we can build an extended state POMDP for the robot and derive a best-response robot policy offline. However, those computations may be expensive since we must consider all possible human behaviors (in an FSC). Moreover, even if we acquired all the elements for large problems, building an explicit model for this extended POMDP may cost a lot of time and resources (which is confirmed by our experiments in Section 6.3, see Table 6.2).

This section proposes our second contribution, an online algorithm for deriving robust robot policies, to address the heavy computation costs issue in offline settings. The core idea is that, instead of building the entire explicit extended POMDP, we develop a generative model of this extended POMDP denoted $G_e$ (extended generative model). Then, we apply online POMDP planning to $G_e$ to give robust robot decisions. This method has two main advantages compared with the offline approach:

1. An explicit Dec-POMDP model is not required for our method. Only a black-box simulator is needed, as many sampling-based planning methods. Thus, it has the potential to scale up to large collaboration problems.
2. Since the online algorithm only searches reachable branches based on the current situation, the robot does not need to explore and consider all possible human behaviors. Therefore, this method enables the robot to interact with humans online within a limited time.

The process for generating the robot's extended generative model $G_e$ is presented in Section 6.2.1, and we evaluate our algorithm in Section 6.3.2.

## 6.2.1 Robot Extended Generative Model

A generative model (black box simulator) is usually required for online planning. For a Dec-POMDP, its generative model $G$ is defined by

$$s', o, r \leftarrow G(s, a),$$

where $G$ takes as input the current state $s$ and joint action $a$, returning the next state $s'$, joint observation $o$, and an instant reward $r$. However, in HRC tasks, the robot cannot directly use $G$ to make its plans since it should reason about its actions using its own observations. Therefore, to build an online robot algorithm, the question is how to construct such a robot generative model.

In Section 6.1.2, we have presented an offline framework for building an explicit extended POMDP for the robot, which accounts for the uncertainty of human objectives and behaviors by integrating a human union FSC. We showed that this robot POMDP has an extended state space $S_e$:

$$s_e^t = \langle s^t, n_H^t, o_R^t \rangle, \quad s_e^t \in S_e,$$

where $s^t$ is the real current state, $n_H^t$ is the current internal node of the human union FSC, and $o_R^t$ is the robot's observation. Moreover, each internal node $n_H^t$ in the union FSC represents a pair of the human's objective $\theta_H$ and internal belief $b_H^t$, and stores the probability distribution of human actions given $\langle \theta_H, b_H^t \rangle$. Solving this robot POMDP gives a robust robot policy which is the best response to all possible human policies considered in the union FSC.

In the online setting, we can not use this representation directly since it requires computing a human FSC to cover all possible human objectives and induced behaviors. This being said, for online planning, the robot should infer the human's objective $\theta_H$ and internal belief $b_H^t$ online. Thus, the robot's extended state is now defined as:

$$s_e^t = \langle s^t, \theta_H, b_H^t, o_R^t \rangle,$$

and we derive the dynamics of the robot's extended POMDP as follows:

$$ 
\begin{aligned}
T_e(s_e^t, a_R^t, s_e^{t+1}) &= Pr(s_e^{t+1} | s_e^t, a_R^t) \\
&= \frac{Pr(s^{t+1}, b_H^{t+1}, \theta_H, o_R^{t+1}, s^t, b_H^t, o_R^t, a_R^t)}{Pr(s^t, b_H^t, \theta_H, o_R^t, a_R^t)} \\
&= \frac{\sum_{a_H^t} \sum_{o_H^{t+1}} Pr(s^{t+1}, b_H^{t+1}, \theta_H, o_R^{t+1}, o_H^{t+1}, s^t, b_H^t, o_R^t, a_H^t, a_R^t)}{Pr(s^t, b_H^t, \theta_H, o_R^t, a_R^t)} \\
&= \sum_{a_H^t} \sum_{o_H^{t+1}} Pr(b_H^{t+1} | o_H^{t+1}, a_H^t, b_H^t) \cdot Pr(s^{t+1} | s^t, \langle a_H^t, a_R^t \rangle) \\
&\quad \cdot Pr(\langle o_R^{t+1}, o_H^{t+1} \rangle | s^{t+1}, \langle a_H^t, a_R^t \rangle) \cdot Pr(a_H^t | \theta_H, b_H^t) \\
&= \sum_{a_H^t} \sum_{o_H^{t+1}} \eta(b_H^t \langle a_H^t, o_H^{t+1} \rangle, b_H^{t+1}) \cdot T(s^t, \langle a_H^t, a_R^t \rangle, s^{t+1}).
\end{aligned}
$$
<figure><img src="image_31.png" /><figcaption>Figure 6.3: Structure of the extended generative model $G_e$ for the robot: The black arrows are the inputs and outputs of the robot’s extended generative model; The blue arrows show the inputs and outputs of a Dec-POMDP simulator $G$; The green arrows show the evolution of the human model.</figcaption></figure>

$$O(s^{t+1}, \langle a_R^t, a_H^t \rangle, \langle o_R^{t+1}, o_H^{t+1} \rangle) \cdot \psi_H(b_H^t, \theta_H, a_H^t),$$

$$\begin{aligned}
O_e(s_e^{t+1}, a_R^t, o_R^{t+1}) &= \mathrm{Pr}(o_R^{t+1} | s_e^{t+1}, a_R^t) \\
&= \mathrm{Pr}(o_R^{t+1} | \langle s^{t+1}, \tilde{o}_R^{t+1}, b_H^{t+1}, \theta_H \rangle, a_R^t) \\
&= \mathbf{1}_{o_R^{t+1} = \tilde{o}_R^{t+1}},
\end{aligned}$$

$$\begin{aligned}
r_e(s_e^t, a_R^t) &= \sum_{a_H^t} r(s^t, \langle a_H^t, a_R^t \rangle) \mathrm{Pr}(a_H^t | \theta_H, b_H^t) \\
&= \sum_{a_H^t} r(s^t, \langle a_H^t, a_R^t \rangle) \cdot \psi_H(b_H^t, \theta_H, a_H^t),
\end{aligned}$$

where we define $\psi_H$ is a human action selection function that $\psi_H(b_H^t, \theta_H, a_H^t) = \mathrm{Pr}(a_H^t | \theta_H, b_H^t)$ (details are given in Algorithm 16). Following this idea, we build an extended generative model $G_e$ as presented in Figure 6.3 with the following definitions:

* inputs: current extended state $s_e^t$ and robot action $a_R^t$,

* outputs: next extended state $s_e^{t+1}$, robot observation $o_R^{t+1}$, and instant reward $r$.

Algorithm 16 details the internal processes of $G_e$. First, $G_e$ takes as input the current extended state $s_e^t$ and robot action $a_R^t$. Then, the algorithm decomposes $s_e^t$ (line 3) and computes the Q
values for $b_H^t$ using a POMCP, considering the Dec-POMDP is an MPOMDP for the human. A softmax distribution $P_{AH}$ of human actions is computed based on obtained Q values (line 4). Then, a human action $a_H^t$ is sampled from $P_{AH}$ (line 5), and the algorithm passes the state $s^t$ and joint action $\langle a_H^t, a_R^t \rangle$ to $G$ (line 6). In this step, the next state $s^{t+1}$, all agents' observations $\langle o_H^{t+1}, o_R^{t+1} \rangle$, and an instant reward $r$ are sampled. Then, to build the next extended state $s_e^{t+1}$, a particle filter is used to compute an updated human belief $b_H^{t+1}$ using his observation $o_H^{t+1}$ (corresponding to the function $\eta_H$ in Figure 6.3). It samples a state $\tilde{s}$ from $b_H^t$ at line 10 and passes it to $G$ with the same joint action $\langle a_H^t, a_R^t \rangle$, if the sample observation $\tilde{\theta}_H$ is identical to $o_H^{t+1}$, the generated next state $\tilde{s}'$ is kept and added as a particle to $b_H^{t+1}$ until the maximum particle size (lines 12–14) is reached. At this stage, all the elements for building the next extended state $s_e^{t+1}$ are obtained (line 15). The algorithm then returns the step results.

<table><caption>**Algorithm 16:** Robot's Extended Generative Model $G_e$ in HRC</caption>
  <thead>
    <tr>
      <th>Step</th>
      <th>Description</th>
      <th>Notation</th>
      <th>Value</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>1</td>
      <td>[Input:] $s_e^t$: extended state | $a_R^t$: robot's action</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>2</td>
      <td>[Parameter:] $G$: Dec-POMDP simulator | $T$: softmax parameter</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>3</td>
      <td>$\langle s^t, b_H^t, \theta_H, o_R^t \rangle \leftarrow s_e^t$</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>4</td>
      <td>$P_{AH} \leftarrow \psi_H(\cdot | b_H, \theta_H)_T$</td>
      <td>&#8652;</td>
      <td>POMCP solves MPOMDP with $b_H$ and get Q values</td>
    </tr>
    <tr>
      <td>5</td>
      <td>$a_H^t \leftarrow \text{Sample}(P_{AH})$</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>6</td>
      <td>$s^{t+1}, \langle o_H^{t+1}, o_R^{t+1} \rangle, r \leftarrow G(s^t, \langle a_H^t, a_R^t \rangle, \theta)$</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>7</td>
      <td>$k \leftarrow 0$</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>8</td>
      <td>$b_H^{t+1} \leftarrow \emptyset$</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>9</td>
      <td><b>while</b> $k < k_{particles}$ <b>do</b></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>10</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;$\tilde{s} \leftarrow \text{Sample}(b_H^t)$</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>11</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;$\tilde{s}', \langle \tilde{\theta}_H, \tilde{\theta}_R \rangle, \tilde{r} \leftarrow G(\tilde{s}, \langle a_H^t, a_R^t \rangle)$</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>12</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<b>if</b> $\tilde{\theta}_H = o_H^{t+1}$ <b>then</b></td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>13</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$b_H^{t+1} \leftarrow b_H^{t+1} \cup \{\tilde{s}'\}$</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>14</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k \leftarrow k + 1$</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>15</td>
      <td>$s_e^{t+1} \leftarrow \langle s^{t+1}, b_H^{t+1}, \theta_H, o_R^{t+1} \rangle$</td>
      <td></td>
      <td></td>
    </tr>
    <tr>
      <td>16</td>
      <td><b>return</b> $s_e^{t+1}, o_R^{t+1}, r$</td>
      <td>&#8652;</td>
      <td>return step results</td>
    </tr>
  </tbody>
</table>

At time $t=0$, the extended state $s_e^0 = \{s^0, b_H^0, \theta_H, \emptyset\}$ where $s^0 \in b^0$, $\theta_H \in P_\theta$, and $b_H^0 = b^0$. The robot's initial belief $b_R^0$ is the probability distribution over $s_e^0$, which is defined as follows:

$$ 
\begin{align*}
b_R^0(s_e^0) &= \operatorname{Pr}(s, b_H^0, \theta_H, \emptyset) \\
&= \operatorname{Pr}(s, b_0, \theta_H, \emptyset) \\
&= \operatorname{Pr}(s|b_0)\operatorname{Pr}(\theta_H) \\
&= b_0(s)P_\theta(\theta_H),
\end{align*} $$

where $P_\theta$ is the probability distribution over human objectives. We thus built a valid POMDP generative model $G_e$ for the robot. Modern online POMDP solvers such as POMCP can be used to plan the robot's action online, which accounts for possible human objectives and behaviors.

### 6.2.2 Online Main Algorithm

The method described in Algorithm 16 constructs an extended generative model $G_e$ for the robot. As mentioned in the previous section, one can then use an online POMDP solver to plan robot actions using $G_e$. This will lead to nested online planning on two levels:
* the top-level online planning takes place for the robot to plan using $G_e$;

* the bottom-level planning is inside $G_e$, where another online planner is used to compute the probability distribution over human actions based on the SMM assumption (line 4 in Algorithm 16).

Using POMCP as an online POMDP solver, we propose an online solver for the robot in our HRC tasks, as shown in Algorithm 17. Its main ideas are the following:

* Each robot's extended state $s_e$ contains a human belief $b_H$, which is used within $G_e$ by the bottom-level POMCP to compute a policy tree.

* If in a leaf node, rather than performing rollouts using a random policy to obtain a first (rough) estimate of that node's value in the robot POMDP, we use the value of $b_H$ (for the MPOMDP guiding the human) as a heuristic estimate as shown in red in line 17. To avoid re-computations, this is achieved by re-using the policy tree constructed in the last call to the bottom-level POMCP, which stores estimated values for all visited human beliefs.

## 6.3 Experiments

Our experiments were conducted on a laptop with a 2.3 GHz i9 CPU. The source code will be made available under an MIT license.

To test our approach, we have designed a scenario presented in Figure 6.4. In this scenario, a robot and a human have to repair two devices and maintain a third one located in a grid world:

* To maintain a device, the robot should be on the device's cell and perform a maintenance action. The human is not required.

* To repair a broken device, first the human needs to pick a component in a toolbox at a specific location; second the human and robot need to be at the device location and simultaneously perform repair actions.

Note also that both the human and the robot have limited observation of the environment. This task is specified as the following Dec-POMDP:

* **States ($S$):** The state $s \in S$ of the problem is made up of: 1. the human location, 2. the robot location, 3. the status of the devices, and 4. whether the human has a component or not. The human and robot locations are represented by integer coordinates $(x, y)$. They can be on the same cell. The state of each device is either “good”, “broken”, or “needs maintenance”.

* **Human observations ($\Omega_H$):** The human observes 1. his location; 2. whether the robot is on his cell or not; 3. the status of the device in his cell (if any).

* **Robot observations ($\Omega_R$):** The robot observes 1. its location; 2. the human's location; 3. the status of the device in its cell (if any).

* **Actions and Dynamics:** Both the human and the robot have the following actions: *Up*, *Down*, *Left*, *Right* are the agents 4 move actions; *Wait*: the agent stays in his current position; *Repair*: repairs a broken device if: 1. the human holds a new component; 2. the human and the robot are in the same cell as the broken device; 3. the human and the
<caption>**Algorithm 17:** Online Robot Search For HRC</caption>

1 N(): counts visits to a history or history-action pair | T: policy tree | b₀: initial belief of the problem | B(h): estimated belief given an action-observation history h
2 Fct Search(h)
3   repeat
4     if h = empty then
5       sₑ ~ b₀
6     else
7       sₑ ~ B(h)
8     Simulate(sₑ, h, 0)
9   until Timeout()
10 Fct Simulate(sₑ, h, depth)
11   if γdepth < ε then
12     return 0
13   if h ∉ T then
14     for a ∈ A do
15       T(h, a) ← (N init (h, a), Q init (h, a), ∅)
16       bₕ ← sₑ.bₕ
17     V(bₕ) ← POMCP M // Get heuristic value from the built POMCP policy tree for MPOMDP
18   return V(bₕ)
19   a ← arg maxₐ [Q(h, a) + c√log N(h) N(h,a)]
20   (s'ₑ, o, r) ~ Gₑ(sₑ, a)
21   R ← r + γSimulate(s'ₑ, hao, depth + 1)
22   N(h) ← N(h) + 1
23   N(h, a) ← N(h, a) + 1
24   Q(h, a) ← Q(h, a) + R-Q(h,a) N(h,a)
25   return arg maxₐ Q(h, a)

robot both perform the repair action. Upon success, the broken device turns to *good* and the human's component is consumed.

The human can *Pick a Component* if he is in the toolbox area and if he does not already hold one. The robot can *Maintain* a device individually if it needs to be maintained and if in the same location. Upon success, the device status turns to *good*.

* **Rewards R:** A reward of +100 is given when all devices have been repaired or maintained. A reward (penalty) of -2 is given for each action except for the human's *Wait*, and a penalty of -20 is given in case of invalid action. A penalty of -1 is given if the human waits before having repaired all the broken devices. If all devices are in "good" status, no penalty (0) is given to the human wait action. The penalty associated to the wait action encourages the robot to postpone maintenance actions if this helps the human finish repair actions early.

This large Dec-POMDP has 2304 states, 49 joint actions (7 individual actions per agent), and 5400 joint observations (30 individual observations for the human and 180 for the robot).
<figure><img src="image_32.png" /><figcaption>Figure 6.4: A collaboration task: A robot and a human evolve in a 4 × 3 grid world. The top-left cell (0,0) and the top-right cell (3,0) both contain a broken device. A device to be maintained is also located in cell (1,0). A toolbox is located in cell (2,2) where the human can pick components.</figcaption></figure>

Note: This state space grows quadratically with the number of cells and exponentially with the number of devices.

To represent uncertainty about the human objectives (see Figure 6.5), we replaced the reward function described previously with two variants. In the first case, the human prefers to repair the broken device on the left first, receiving a +10 reward in that case. In the second case, symmetrically, the human prefers to repair the broken device on the right first. These objectives generate different human policies using Algorithm 14. Initially, the robot only has a prior over the human's rewards and associated policy (each with a probability 0.5). Due to the required coordination for repairing devices, these human policies have to account for the robot's ability to help the human when needed.

We evaluate both the offline and online robust planning algorithms described in Section 6.1 and Section 6.2. But for experiments with real humans, only the offline method is evaluated. Real human experiments using the online algorithm is kept for future work.

### 6.3.1 Experiments with Synthetic Humans – Offline Algorithm

#### Qualitative results

We used Algorithm 14 to compute the stochastic human FSCs associated with each human objective, and the method described in Section 6.1.2 to compute the robust robot policy with the POMDP solver SARSOP [Kurniawati et al., 2008]. To save resources, an *action-threshold* (here always set to 0.1) is used to prune low-probability human actions when computing the stochastic human FSCs. We conducted experiments with 2 values for the softmax parameter *T* (0.3 and 0.5), and 5 values for the maximum stochastic FSC size *N*<sub>max</sub> (see Table 6.1).

We first observed that the extracted human stochastic FSC can effectively encode possible trajectories of the human to solve the task if $N_{\max}$ is high enough for the current $T$. For instance,
<figure><img src="image_33.png" /><figcaption>Figure 6.5: An illustration of the uncertainties about the human behavior in this HRC task: 1. Uncertainty on the human objective (presented with blue and orange colors); 2. Uncertainty on human behaviors (different trajectories)</figcaption></figure>

when $T = 0.3$ and $N_{max} = 100$, the extracted human stochastic FSCs reach depths$^4$ of 22 and 18 (for each objective), which are sufficient for the human to finish the task if the robot collaborates. However, when $N_{max} = 50$, the depth covered by the FSC of the *repair-left-device-first* objective is only 13 (15 for the 2nd objective), which does not allow the human to finish the task (a depth of 15 is required). We also observed that the higher the temperature $T$, the higher the $N_{max}$ value needed for the human stochastic FSC. Indeed, when $T$ increases, more actions are considered at each node, generating more branches and preventing the expansion process from reaching the end of the task. Note also that, even if we set $T$ to a very low value (near 0), the softmax distribution may contain several optimal actions. This allows encoding several optimal human policies in a single FSC.

When $N_{max}$ is large enough for the current $T$, we observed that the computed robust robot policy can successfully solve the task, accounting for the uncertainties over human objectives and behaviors. It helps the human repair all the devices and performs the required maintenance operation. For example, when $T = 0.3$ and $N_{max} = 100$, the robot following the generated robust policy first goes to cell (0, 0) and waits for the human to pick a component at cell (2, 2). Afterwards, if the robot observes that the human is approaching, it keeps waiting for him and then helps him repair the left device when the human reaches cell (0, 0). But if it observes the human moving to the top-right corner, then the robot decides to go right and help the human repair the right device first. The robot then moves to cell (1, 0) to perform a maintenance operation while the human is going to pick a second component. Finally, the robot helps the human repair the other broken device to finish the task.

Even if this seems like a simple pattern for the robot, it still requires the robot to reason on many possible human trajectories. For example, if there are 2 optimal actions in each state, even for 5 time steps, there are $2^5$ possible optimal trajectories (and this number can increase dramatically when considering sub-optimal actions). Moreover, in this complex collaboration

<footnote>$^4$The depth of an FSC is the maximum distance between the (here unique) initial node and any node.</footnote>
scenario, agents make decisions only based on partial observations, and, as illustrated above, the
robot infers the human objective despite his uncertain behavior.

Robustness Analysis

We also wanted to quantitatively analyze the robustness of our approach by comparing the
method described in Algorithm 14 with a method computing a robot policy only based on
deterministic human policies. To that end, we extracted 50 pairs of deterministic human policies,
one per objective, using T = 0.5 and Nmax = 600 (cf. Algorithm 15), but obtaining less than
200 nodes in all cases; then, for each pair, we computed a best-response robot policy to the
equiprobable union of these two human policies (cf. beginning of Section 6.1.2). The resulting
set of 3 × 50 policies is thus Π<sub>H</sub> = {\langleπ<sup>1</sup><sub>H,l</sub>, π<sup>1</sup><sub>H,r</sub>, π<sup>1</sup><sub>H,l+r</sub>\>, ..., \langleπ<sup>50</sup><sub>H,l</sub>, π<sup>50</sup><sub>H,r</sub>, π<sup>50</sup><sub>H,l+r</sub>\>}. For each human
union policy π<sup>i</sup><sub>H,l+r</sub>, we also compute a robot best response π<sup>i</sup><sub>R,BR</sub> by solving a POMDP obtained
as in Section 6.1.2.

In our experiments, we compare the robust robot policies $\pi_R^*$ obtained for different values of $T$ and $N_{\max}$ against

1. the 50 best responses $\pi_{R,BR}^i$ described above (averaging over all of them), and

2. the robot policy obtained by solving (with Inf-JESP [You et al., 2021a]) the corresponding Dec-POMDP.<fnref n="5" />

The obtained results and standard deviations are presented in Table 6.1 (ignoring the last three rows, which correspond to the online algorithm and will be discussed later). For each robot FSC and each human preference (left or right first):

* we compute the exact value against each human FSC (through an iterative process, see Equation (2.21), page 19), then obtain the average value and standard deviation over the various humans;

* we simulate its behavior once against each human FSC (which is sufficient since both agents' FSCs are deterministic) to obtain the success rate over all considered human FSCs.

Then, the result for the third setting $\pi_{H,l+r}^{\text{Sample}}$ (uncertain preference) is obtained as the average of the first two columns (as expected from the theory, but also empirically validated).

First, as expected, the worst results are obtained with the Dec-POMDP and Best-Response
solutions ($\pi_{R,Dec-POMDP}$ and $\pi_{R,BR}$), with near-zero success rates. Our approach improves a
little bit in terms of success rate when using $T = 0$, i.e., when assuming that the human only
chooses among a small subset of actions at each time step, which leads to fairly small human
FSCs (24 and 23 nodes for the two independent objectives). The average reward remains very
low, though. Using $T = 0.3$ or $0.5$ leads to much better results. In the *prefer-right* scenario,
human FSCs with 200 nodes are even sufficient to get very good solutions (90% success rate).
Moving from $T = 0.3$ to $T = 0.5$, this phenomenon is all the more important that more erratic
behaviors require larger FSCs to better account for most likely trajectories. In the *prefer-left*
scenario, the success rates and values drop significantly. This is due to the longer trajectories
needed in this case, which in turn require large human FSCs to encode good enough policies.
Then, in the “union” scenario where the human’s preference is randomly sampled, the results are
a simple combination of the results in the *prefer-left* and *prefer-right* scenarios.

<footnote n="5"><sup>5</sup>This solution assumes a strong a priori coordination since the human and robot agree on their individual policies.</footnote>
<table><caption>Table 6.1: Average value (and success rates in parentheses) of various robot policies vs. various human behaviors. For each offline robust robot policy $\pi_R^*(T, N_{max})$, we also indicate the sizes of both generated human FSCs as $N = (N_{left}, N_{right})$. For the online method, we present the different timeouts used in each $\pi_{R,Online}^*$.</caption><thead><tr><th rowspan="2"></th><th colspan="3">3 × 50 synthetic human FSCs sampled using T = 0.5</th><th>10 real humans</th></tr><tr><th>π<sup>Sample</sup><sub>H,l</sub></th><th>π<sup>Sample</sup><sub>H,r</sub></th><th>π<sup>Sample</sup><sub>H,l+r</sub></th><th>π<sup>Real</sup><sub>H</sub></th></tr></thead><tbody><tr><td>π<sub>R,Dec-POMDP</sub></td><td>-34.9 ± 6.7 (0%)</td><td>-82.5 ± 14.4 (0%)</td><td>-58.7 ± 10.5 (0%)</td><td></td></tr><tr><td>π<sub>R,BR</sub></td><td>-172.1 ± 2.5 (3%)</td><td>-174.4 ± 2.5 (3%)</td><td>-173.3 ± 2.5 (3%)</td><td></td></tr><tr><td>π<sup>*</sup><sub>R</sub>(T = 0.0, N<sub>max</sub> = 100, N = (24, 23))</td><td>-110.0 ± 12.5 (10%)</td><td>-179.4 ± 15.4 (18%)</td><td>-144.7 ± 14.0 (14%)</td><td>-55.3 ± 6.5 (16%)</td></tr><tr><td>π<sup>*</sup><sub>R</sub>(T = 0.3, N<sub>max</sub> = 200, N = (200, 200))</td><td>-38.1 ± 9.8 (52%)</td><td><b>10.0</b> ± 2.0 (90%)</td><td>-14.0 ± 5.9 (71%)</td><td></td></tr><tr><td>π<sup>*</sup><sub>R</sub>(T = —, N<sub>max</sub> = 400, N = (400, 400))</td><td>-11.9 ± 7.2 (68%)</td><td><b>10.0</b> ± 2.0 (90%)</td><td>-0.9 ± 4.6 (79%)</td><td></td></tr><tr><td>π<sup>*</sup><sub>R</sub>(T = —, N<sub>max</sub> = 600, N = (600, 443))</td><td>-11.9 ± 7.2 (68%)</td><td><b>10.0</b> ± 2.0 (90%)</td><td>-0.9 ± 4.6 (79%)</td><td><b>-20.8</b> ± 7.4 (81%)</td></tr><tr><td>π<sup>*</sup><sub>R</sub>(T = 0.5, N<sub>max</sub> = 200, N = (200, 200))</td><td>-36.6 ± 5.6 (16%)</td><td><b>10.0</b> ± 2.0 (90%)</td><td>-13.3 ± 3.8 (53%)</td><td></td></tr><tr><td>π<sup>*</sup><sub>R</sub>(T = —, N<sub>max</sub> = 400, N = (400, 400))</td><td>2.7 ± 2.5 (76%)</td><td><b>10.0</b> ± 2.0 (90%)</td><td>6.3 ± 2.3 (83%)</td><td></td></tr><tr><td>π<sup>*</sup><sub>R</sub>(T = —, N<sub>max</sub> = 600, N = (600, 600))</td><td><b>9.5</b> ± 2.2 (84%)</td><td><b>10.0</b> ± 2.0 (90%)</td><td><b>9.8</b> ± 2.1 (87%)</td><td>-33.7 ± 11.9 (75%)</td></tr><tr><td>π<sup>*</sup><sub>R,Online</sub>(T = 0.5, timeout = 10 s)</td><td>5.6 ± 2.4 (80%)</td><td>7.3 ± 2.3 (84%)</td><td>6.5 ± 2.3 (82%)</td><td></td></tr><tr><td>π<sup>*</sup><sub>R,Online</sub>(T = —, timeout = 30 s)</td><td>7.0 ± 2.4 (84%)</td><td>6.7 ± 2.2 (86%)</td><td>6.9 ± 2.3 (85%)</td><td></td></tr><tr><td>π<sup>*</sup><sub>R,Online</sub>(T = —, timeout = 60 s)</td><td><b>10.2</b> ± 2.0 (90%)</td><td><b>9.1</b> ± 2.1 (90%)</td><td><b>9.7</b> ± 2.1 (90%)</td><td></td></tr></tbody></table>

<table><caption>Table 6.2: CPU Time (in seconds) for different experiments with our offline method</caption><thead><tr><th rowspan="2">Step</th><th colspan="3">π<sup>*</sup><sub>R</sub>(T, N<sub>max</sub>)</th></tr><tr><th>(0.0, 100)</th><th>(0.3, 600)</th><th>(0.5, 600)</th></tr></thead><tbody><tr><td>Dec-POMDP→MPOMDP</td><td>13</td><td>13</td><td>13</td></tr><tr><td>Get Human Stoc. FSCs</td><td>83</td><td>2032</td><td>6144</td></tr><tr><td>Build Robot POMDP</td><td>3</td><td>178</td><td>203</td></tr><tr><td>Solve Robot POMDP</td><td>2</td><td>57</td><td>105</td></tr><tr><td>Total time</td><td>101</td><td>2280</td><td>6465</td></tr></tbody></table>

Note that, in these experiments, the synthetic humans used for evaluation are rather erratic ($T = 0.5$), which explains that the best success rates are obtained with robot policies derived for that same temperature, while robots derived for $T = 0.3$ are not robust enough.

Table 6.2 presents the recorded computational time used in each step of our offline method. The 1st step consists in converting each Dec-POMDP task model to an MPOMDP (one by human objective); the 2nd step in generating stochastic human policies (FSCs) as presented in Sec. 6.1.1 (the most time-consuming process); the 3rd step in building the robot POMDP using the task models (Dec-POMDPs) and the human FSCs; and, the final step in solving the robot POMDP using SARSOP to get a robust robot policy. Here, most of the time is spent calling POMCP in the FSC extraction.

### 6.3.2 Experiments with Synthetic Humans – Online Algorithm

We use Algorithm 17 to plan the robot's actions online with a softmax temperature $T = 0.5$, and three different POMCP timeouts (10 s, 30 s and 60 s) are tested in the experiments. We evaluate our online approach using the same synthetic human policies as our offline method. The results of our online approach are presented at the bottom of Table 6.1 (the last three rows). We first observe that:

* our online method gives relatively good solutions even with a short timeout, i.e., with a
timeout of 10 seconds, our online approach achieves 82% success rate on both objectives
(evaluation with $\pi_{H,l+r}^{Sample}$);

* the performance of our online method increases with the timeout; from the timeout of 10 s to 60 s, the online method improves its success rate from 82% to 90% on sets $\pi_{H,l+r}^{Sample}$, and the average value is increased from 6.5 to 9.7.

Second, we observe that in the *prefer-right* scenario, our online method can achieve the same success rate as our offline method (90%), but with a lower average value (9.1 compared with 10.0). However, in the *prefer-left* scenario, the online approach can reach a success rate of 90% with a value of 10.2, which outperforms the offline method $\pi_R^*(0.5, 600)$. An explanation for this phenomenon is that, in the *prefer-left* case, the offline method $\pi_R^*(0.5, 600)$ cannot cover all possible human policies with a max FSC size of 600, and thus may perform poorly in some situations, while the online method keeps on replanning both for the human and the robot, which provides a human behavioral model making good decisions in more situations. In the *prefer-right* scenario, although both methods can achieve the same success rate, the offline approach is equipped with an explicit POMDP model that properly covers the human behavior and, therefore, can compute a better policy thanks to SARSOP with a higher value compared with the online algorithm.

### 6.3.3 Real Human Experiments

To further evaluate our approach, we implemented this collaboration task as a computer game played in a terminal where the human is controlled through the keyboard. To make a friendly user interface, the human player can directly observe the state of the environment, as shown in Fig. 6.4, but the robot still faces partial observability as defined in the Dec-POMDP problem, and behaves accordingly. A screenshot of this terminal game interface is presented in Figure 6.6.

Then, we selected three offline robot policies, $\pi_R^*(0.0, 100)$, $\pi_R^*(0.3, 600)$ and $\pi_R^*(0.5, 600)$, from the previous experiment, and we invited 10 real human subjects to collaborate with those robot policies. Each subject was informed that the goal of this collaboration task was to turn each device status to “good” within at most 30 time steps, but did not know or observe the instant reward. Each human subject needed to play 8 consecutive rounds of this collaboration game per robot policy (for a total of 24 rounds), i.e., 8 times a first robot, then 8 times a second robot, then 8 times a third robot. The order of robot policies was randomly selected so as to remove the side effects of starting with the same robot policy:

1. the first few games may be more difficult since the human subject needs some rounds to get familiar with the task, and

2. the ordering may influence how a player acts.

Moreover, to make this HRC game more fun, we introduce vertical and horizontal flipping to the environment for every 2 rounds, in which the locations of the human, robot, and devices are different in the beginning. By doing so, we expect that our subjects will not feel bored during the experiment, which may have a negative effect on their decisions. Figures 6.7 to 6.9 present the results of the different sessions and the answers the human subjects gave to our questions after each series of 8 rounds.

Qualitatively, the robot behaviors of the online planning method are not very different from the best robot policy computed offline, so we decided to keep human experiments with the online planning method for future work.
<figure><img src="image_34.png" /><figcaption>Figure 6.6: A screenshot of the human-robot collaboration game: The top part illustrates the current environment state for the human player; The middle part provides information on available human actions; The bottom part is a legend explaining how to read the map. In each time step, the top part will refresh according to the executed human and robot actions.</figcaption></figure>

Qualitative results

We first observed that the robot policy $\pi_R^*(0.0, 100)$ was unable to help the human subjects since it only accounts for a few high-quality human actions. For example, a common mistake of human subjects was to forget to pick a component necessary to repair a broken device. To fix that mistake, the human subject had to go back to the toolbox, thus generating an unexpected human behavior for robot policy $\pi_R^*(0.0, 100)$, and leading to a failure due to the robot policy getting stuck in a self-loop. On the contrary, while no specific information regarding human behaviors was provided, robot policies $\pi_R^*(0.3, 600)$ and $\pi_R^*(0.5, 600)$ managed to recover and help the human to solve the task because they considered more possible human actions in each situation. In most cases, those policies adapted to different human behaviors and were able to tolerate human mistakes such as the one mentioned above.

Moreover, after the experiments, we asked our subjects how they felt about the 3 tested robot policies. Figure 6.7 presents the detailed subjects' evaluation of both players' adaptation during the experiments. After each series of 8 rounds, we asked the human subjects to assess the interaction with the robot. Each human subject had to pick one choice representing his or her
<figure><img src="image_35.png" /><figcaption>Figure 6.7: All subjects’ evaluations regarding both players’ adaptation during the collaboration task for each robot policy.</figcaption></figure>

impression among the following four choices: “no adaptation”, “human adapts to robot”, “robot
adapts to human”, and “mutual adaptation”. The results of our questionnaire are as follows:

• When playing with $\pi_R^*(0.0, 100)$:

- 60% of our subjects reported that there was no adaptation at all; and

- the other 40% felt that they needed to adapt to the current policy to finish the task.

• Same distribution of choice for the robot policies $\pi_R^*(0.3, 600)$ and $\pi_R^*(0.5, 600)$:

- 50% of the subjects reported mutual adaptation;

- 30% felt they needed to adapt to the robot; and

- 20% reported that $\pi_R^*(0.3, 600)$ and $\pi_R^*(0.5, 600)$ were adapting to their behaviors.

This confirms that it makes little difference for the humans to play with these last two robots,
while their results were significantly different in experiments with (erratic) synthetic humans
(designed with $T = 0.5$).

Last but not least, we asked our subjects to choose one robot policy that makes them feel
comfortable during the collaboration task. The results are shown in Figure 6.8. As expected by
the previous results, no one picked robot policy $\pi_R^*(0.0, 100)$ since it was hard to collaborate with
the robot, and the interactions often led to a failure of the task, as shown in Figure 6.9. Then,
60% of our subjects picked $\pi_R^*(0.3, 600)$ and 40% picked $\pi_R^*(0.5, 600)$. The fact that $\pi_R^*(0.3, 600)$
was the most selected policy could imply that computing the robot policy based on overly erratic
human models might be counterproductive (since the robot might be seen as being too indecisive),
as also highlighted by the success rate presented in Table 6.1. However, more subjects and more
investigations are needed to verify that assumption.
<figure><img src="image_36.png" /><figcaption>Figure 6.8: All subjects' choices when asked to pick the robot policy they preferred at the end of the experiments.</figcaption></figure>

Quantitative results

The average cumulative rewards and success rates of human subjects are shown in the right part of Table 6.1. For the same three robot policies, the cumulative rewards are lower than with synthetic human experiments (−55.3, −20.8, and −33.7 respectively). There are multiple reasons causing this drop in values: first, the human subjects needed some rounds to get familiar with the game, therefore, in early rounds, humans usually make more mistakes and received penalties; moreover, since human subjects were not informed of the exact reward function, they were not aware of penalties (negative rewards) obtained when waiting or when going outside of the grid world.

Figure 6.9 presents each subject’s number of successes for the collaboration task with the different robot policies. Since each subject encountered each robot policy 8 times, a value of 8 means that this human subject managed to solve the task each round, while a value of 0 means this human subject never managed to solve the task while collaborating with this robot policy. When human subjects tried to collaborate with $\pi_R^*(0.0, 100)$, 30% of the subjects (3 out of 10) never succeeded in solving the collaboration task, another 30% succeeded only once, and 40% succeeded 2 or 3 times. This shows that this robot policy does not adapt to spontaneous human behavior and that the human subjects have difficulties finding behaviors that would trigger appropriate robot reactions. However, when human subjects collaborated with robot policies $\pi_R^*(0.3, 600)$ and $\pi_R^*(0.5, 600)$, they all succeeded in more than 4 rounds, and some of them even successfully accomplished all 8 rounds with one of those two robot policies. These similar results suggest that increasing temperature $T$ from 0.3 to 0.5 does not improve the robot’s robustness to actual human behaviors.

Overall, the observed success rates of human subjects with robot policies $\pi_R^*(0.3, 600)$ and $\pi_R^*(0.5, 600)$ are 81% and 75% respectively. This shows that, even if the cumulative rewards are low, or if the human performs mistakes, $\pi_R^*(0.3, 600)$ and $\pi_R^*(0.5, 600)$ could still help the human to accomplish the task most of the time. The higher success rate (and cumulative reward) with
<figure><img src="image_37.png" /><figcaption>Figure 6.9: Each subject’s number of successes when he or she collaborates with different robot policies.</figcaption></figure>

$\pi_R^*(0.3, 600)$ than with $\pi_R^*(0.5, 600)$ (contrary to the results with synthetic humans obtained with $T = 0.5$) suggests that the robot’s mental model of humans is better when it builds human FSCs using $T = 0.3$ than $T = 0.5$.

## 6.4 Conclusion

In this chapter, we discuss and address the problem of uncertainty over human objectives and induced behaviors in human-robot collaboration with partial observabilities. The contribution can be mainly divided into three parts:

* We discuss the pros and cons of various mental models in human-robot collaboration applications. In this thesis, we choose to equip the robot with a second-order mental model (2oMM) for modeling the human partner. We discuss the chicken-and-egg problem raised by using nested 2oMMs and provide two methods to overcome this obstacle. The first method automatically generates a human FSC, aggregating various possible behaviors for a given human objective. The second method gives a probability distribution of human actions online based on a sampling-based planner given a human objective. For both methods, parameters can be tuned to adjust the diversity of the generated human behaviors;

* We propose an offline robust robot planning algorithm that relies on an explicit POMDP model with uncertainties on the human’s actual objective and behavior. We formally detail how to build this robot POMDP based on the task models (Dec-POMDPs) and a distribution over human stochastic policies (FSCs), one per possible objective. An offline robust robot policy is obtained by solving this robot POMDP;

* We also propose an online robust robot planning algorithm for the HRC tasks. Compared with the offline method, which relies on an explicit POMDP, our online approach only requires a generative model and, therefore, can scale up to large problems. We demonstrate
the process of constructing a valid POMDP generative model for the robot with an extended state space that includes the human's internal state. We also provide an online robot planning algorithm based on POMCP. Using this POMDP generative model, the robot plans its actions at each time step by estimating the human's actual objective and his/her actions online.

Through experiments, we demonstrate that our approaches are robust to uncertain human behaviors with different objectives. While, in our scenario, the two possible human objectives correspond to the same task under different preferences, different objectives could also correspond to different tasks. We believe this work is important for collaboration settings where the robot and the human need to reason about each other's possible actions, and where considering myopic or deterministic human policies is insufficient to generate robust robot policies. Moreover, our approach only requires a Dec-POMDP describing the human-robot collaboration task, with no need for prior human behavior. This makes our method generic to tackle various human-robot collaboration problems.

## 6.5 Perspectives

In this chapter, we contribute to deriving robust robot policies for human-robot collaboration with offline and online approaches. Let us now describe various directions for future works.

### 6.5.1 Experiments with more problems

Through experiments with synthetic or real humans in a simulated environment, we demonstrate that our methods are robust to adapt to different human objectives and behaviors. Therefore, the next step is conducting further experiments on more benchmark problems. In this direction, we could possibly adapt classical Dec-POMDP problems and provide graphic interfaces to real human subjects. Moreover, as a long-term goal, we would like to validate our approach in a real-world scenario where a drone has to help a human to repair devices as part of the Flying Co-Worker project.

### 6.5.2 Improving the robot planning by learning the human data

One could design a robust robot for HRC tasks using our approaches (either offline or online) without prior knowledge of human behaviors. This means that our methods provide an important starting step for the HRC problems where the robot and human need to coordinate to achieve the goal since we address the chicken-and-egg issue for deriving robot policies. Therefore, we project that a second step would be to use learning techniques to use the human data collected during interactions with the robot. More precisely, one could maybe learn:

1. the probability of each reward function (and thus the human preferences);

2. how erratic the human seems to be (temperature *T* that best models his/her behavior); or

3. more generally human's reward function (by inverse reinforcement learning) or his/her policy.

Improvements on those directions could provide a more accurate human model for the robot and generate better robust robot policies.
6.5.3 Extension to large and continuous problems

Our online robust robot planning algorithm currently relies on a generative model to plan robot
actions, which can handle large state-space problems. One promising direction is further scaling
up to continuous actions and observations. To that end, we can combine the double progres-
sive widening technique used in POMCPOW [Sunberg and Kochenderfer, 2018], which extends
POMCP to solve continuous problems (continuous states, actions, and observations). This adap-
tation seems interesting and not difficult since our online robust robot planning algorithm is also
built based on POMCP.

Moreover, currently, the robot considers that the human behaves according to a probability
distribution computed by a softmax function with a given temperature T. One issue is that,
to handle erratic behaviors, we need to reason about many possible human trajectories. Maybe
we could let the robot algorithm start, by default, a not-so-erratic human (low T value) and
gradually increase the value T until matching realistic human behaviors. This will create an
“adaptive” robot policy that can work with humans with different levels of rationality. A potential
issue that remains is how to behave when facing unexpected observations.
# 7

# Conclusion and Perspectives

## 7.1 Conclusion

In this thesis, we investigate the robot decision-making questions in two research fields, robot-robot collaboration (RRC) and human-robot collaboration (HRC).

In RRC, multiple robots are meant to work collaboratively to achieve a task. Moreover, this thesis focuses on the RRC problems where each robot has only partial observations in an uncertain environment. Relying on Markov decision models, we use the Dec-POMDP framework to model such RRC problems and propose two novel algorithms for solving Dec-POMDPs:

* First, based on the JESP scheme, we propose an algorithm called *Infinite-horizon JESP* (Inf-JESP) for solving infinite-horizon Dec-POMDPs. Inf-JESP searches Nash equilibrium solutions by iteratively building each agent's best-response policies to other agents' policies. Compared with JESP, instead of using policy trees for finite-horizon settings, in Inf-JESP each agent policy is represented by a finite-state controller (FSC), which overcomes the curse of dimensionality and can encode infinite-horizon policies. This work has been published in JFPDA [You et al., 2021b] and ICTAI [You et al., 2021a] (an extended version can be found in arXiv [You et al., 2021c]).

* The second algorithm, Monte-Carlo JESP (MC-JESP), extends Inf-JESP to the generative model setting. Like Inf-JESP, MC-JESP searches Nash equilibrium solutions through an iterative process. In each iteration, MC-JESP builds each agent's FSC node by node using a Monte-Carlo approach (POMCP). Unlike in Inf-JESP, where an explicit Dec-POMDP model is needed, MC-JESP only requires a black-box simulator, enabling us to scale up to large Dec-POMDP problems.

We observe through experiments with state-of-the-art benchmark problems that both Inf-JESP and MC-JESP are competitive with existing Dec-POMDP solvers. MC-JESP even outperforms some solvers that rely on explicit models. Moreover, through the research conducted to solve infinite-horizon Dec-POMDPs for RRC, we provide tools to generate a best-response POMDP for a given agent knowing others' fixed policies. This is an important foundation for our contributions to HRC.

In HRC, we are interested in scenarios where a human and a robot need to coordinate their behaviors to achieve a task. Indeed, only the robot can be controlled in this setting, while the human may have uncertain objectives and behaviors. Nevertheless, the robot's policy should be robust to adapt to the uncertainties about the human partner. In this case, we cannot directly solve a Dec-POMDP to derive each agent's optimal policy as in an RRC problem because the
computed robot policy is not robust, and the actual human may not behave according to the computed policy. To derive robust robot policies, we analyze various mental models for the robot to model its human partner. We choose to equip the robot with a second-order mental model (2oMM) for modeling the human. Using a 2oMM means that the robot models the human as reasoning about the robot's possible behaviors, and to avoid the chicken-and-egg problem raised by **nested** 2oMMs, the human is here assumed to have a SMM of himself and the robot, *i.e.*, he reasons as if controlling the robot. More specifically, we propose two novel algorithms as follows:

* We propose an offline algorithm consisting of two parts: 1. A method to overcome the chicken-and-egg problem through a shared mental model (SMM) assumption of the considered human, which automatically generates a stochastic human FSC model that encodes possible behaviors for each human objective provided in an initial distribution. The human's action selection function is parameterized and tunable with a softmax temperature to create more rational or erratic human behaviors. 2. A robust robot planning algorithm that relies on a POMDP with uncertainties on the human's objective and behavior. Based on the best-response POMDP framework we built for RRC, we demonstrate how to build this robot POMDP in the HRC setting given the HRC task model and a distribution over human FSCs (each stochastic FSC is linked to a human objective). The robust robot policy is derived by solving this robot POMDP. A preliminary version of this work has been published in JFPDA [You et al., 2022], and an improved version with real human experiments has been submitted and accepted in ICRA 2023.

* Based on the offline method, we propose a nested online algorithm for deriving robust robot policies. We construct a robot POMDP generative model with an extended state space in this online method. The human's objective and actions are estimated inside the robot's extended generative model through a nested online planning. Based on POMDP, we then provide an online planning algorithm (top-level) for the robot to plan its actions. Moreover, compared with our offline approach, this online variation relaxes the requirement of explicit models to black-box simulators.

Through experiments with synthetic and real humans, we show that our approaches are robust to uncertain human objectives and induced behaviors. In our works, only a Dec-POMDP is required to present the HRC task, and no prior knowledge of human behaviors is needed. We thus believe that our contributions are generic to tackle different HRC problems.

Beyond the contributions listed above, I also cooperated with other authors and published a review article regarding human-humanoid interaction and cooperation in the journal *Current Robotics Reports* [Vianello et al., 2021].

## 7.2 Perspectives

At the end of this thesis, we take one step further to have a global view of perspectives for all of our contributions.

In the thesis, we provide several algorithms for solving RRC and HRC problems, and various experiments, including evaluations with real human subjects, are conducted in simulated environments to validate our approaches. In the future, we would like to apply our contributions to real-world scenarios with real robots. Various questions and directions could be further investigated in this interesting but challenging topic, including:

* Different action durations: this thesis assumes that all agents have the same action duration in RRC and HRC. This enables us to use standard POMDP or Dec-POMDP frameworks to
model our problems. However, in real-world applications, actions may have different dura-
tions. In this direction, Omidshafiei et al. [2015] propose integrating semi-Markov models
and macro actions (solving a Dec-POSMDP). Another related direction is hierarchical
planning, where we decompose the task into sub-tasks.

* Large or continuous problems: in real applications, the state, action, and observation spaces may be large or continuous. To our knowledge, continuous problems have been investigated in the POMDP setting, e.g., through POMCPOW [Sunberg and Kochenderfer, 2018], which extends POMCP to solve continuous problems. However, there is still a lack of work addressing such problems in multi-agent settings (Dec-POMDPs) or complex HRC tasks.

* Communication during execution: in this thesis, we do not have any assumption of communication between agents in RRC or HRC. In real scenarios, it may be useful and important that agents can communicate with each other to exchange information in order to have better collaborations. A generic approach is introducing generic communication actions whose purpose is decided by the planning process, which may become expensive and degrade performance if too many communications have been executed [Unhelkar et al., 2020]. Another approach is to seek heuristics to decide when and what to communicate (e.g., detecting situations that need disambiguation to avoid catastrophic decisions).

Second, various questions more specific to human-robot collaboration could be investigated:

* We would like to extend our work to settings with multiple humans and robots. Intuitively, considering multiple robots would mean solving a Dec-POMDP for these robots, the humans being considered as part of the environment. Then, considering multiple humans would require a second-order mental model taking into account the whole group of humans, unless they achieve independent tasks and can thus be considered separately.

* Also, our approach could be more human-aware. It could for example try to account for human fatigue, for instance by letting the robot intervene more often (which maybe at the expense of less human autonomy), and for human emotions, for instance by letting the human be more autonomous and making sure that the human understands the robot's behavior. This last point would naturally lead to considering questions such as trust, acceptability, and explainability of the robot's behavior.

Last but not least, we could improve our methods via a learning approach, e.g., if repeating
some tasks with the same human or different humans, we can gather data from interactions. The
collected human data can be used to learn human objective distribution, level of rationality, and
reward function or policy.
## A.1 Notes about the Candidate POMDP Formalizations

We here look in more details at how, given the Dec-POMDP and FSCs for all agents but $i$, one can derive a valid best-response POMDP from agent $i$'s point of view. First, note that, in the POMDP formalization:

* we have *no choice* for the observation ($o_i^t$) and for the action ($a_i^t$), which are pre-requisites;

* the *only choice* that can be made is that of the variables put in the (extended) state $e_i^t$;

* the transition, observation and reward functions are *consequences* of this choice.

Also, note that, in a POMDP formalization, the state and observation variables need be distinguished. One cannot write that $X$ is an observed state variable (contrary to the MOMDP formalism). In the following, it is thus important to distinguish the different types of random variables. In particular,

* $O_i^t$ always denotes (of course) the *observation variable*, yet

* $\tilde{O}_i^t$ denotes either an *intermediate variable*<fnref n="6" /> or a *state variable* (which, in both cases, is strongly dependent on observation variable $O_i^t$ since their values are always equal).

The main issue when designing our BR POMDP is to verify that the dependencies in the transition, observation, and reward functions are the appropriate ones (see Fig. A.1 (top left)). In the following paragraphs, we consider 3 choices for the *extended state* of the POMDP, check whether they indeed induce valid POMDPs, and derive the induced transition, observation and reward functions when appropriate.

$e^t = \langle s^t, n_{\neq i}^t \rangle$? To show that $e^t = \langle s^t, n_{\neq i}^t \rangle$ does not induce a proper POMDP, let us write the transition function:

$$ 
\begin{aligned}
T_e(e^t, a_i^t, e^{t+1}) &\stackrel{\text{def}}{=} \operatorname{Pr}(e^{t+1} | e^t, a_i^t) \\
&= \operatorname{Pr}(s^{t+1}, n_{\neq i}^{t+1} | s^t, n_{\neq i}^t, a_i^t) \\
&= \sum_{\tilde{o}^{t+1}} \operatorname{Pr}(s^{t+1}, n_{\neq i}^{t+1}, \tilde{o}^{t+1} | s^t, n_{\neq i}^t, a_i^t)
\end{aligned}
$$

<footnote n="6">⁶Such a variable does not usually appear in the POMDP formalism, but is required here to compute the transition and observation functions based on the Dec-POMDP model and the FSCs.</footnote>
$$
\begin{align*}
&= \sum_{\tilde{o}^{t+1}} \Pr(n_{\neq i}^{t+1} | s^t, n_{\neq i}^t, a_i^t, s^{t+1}, \tilde{o}^{t+1}) \cdot \Pr(s^{t+1}, \tilde{o}^{t+1} | s^t, n_{\neq i}^t, a_i^t) \\
&= \sum_{\tilde{o}^{t+1}} \Pr(n_{\neq i}^{t+1} | s^t, n_{\neq i}^t, a_i^t, s^{t+1}, \tilde{o}^{t+1}) \cdot \Pr(\tilde{o}^{t+1} | s^t, n_{\neq i}^t, a_i^t, s^{t+1}) \cdot \Pr(s^{t+1} | s^t, n_{\neq i}^t, a_i^t) \\
&= \sum_{\tilde{o}^{t+1}} \left( \prod_{j \neq i} \eta(n_j^t, \tilde{o}_j^{t+1}, n_j^{t+1}) \right) \\
&\quad \cdot O(\langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}, \tilde{o}^{t+1}) \cdot T(s^t, \langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}),
\end{align*}
$$

where $\tilde{O}^{t+1}$ is a temporary variable, not a state or an observation variable. Here, as illustrated by Fig. A.1 (top right), the issue is that the actual observation variable $O_i^{t+1}$ is not independent on $E^t$ given $E^{t+1}$ and $A^t$.

$\frac{e^t = \langle s^t, n_{\neq i}^t, \tilde{o}_i^t \rangle}{e^t = \langle s^t, n_{\neq i}^t, \tilde{o}_i^t \rangle}$ We correct the first attempt by adding a state variable $\tilde{O}_i^t$, thus defining hence:

$$
\begin{align*}
T_e(e^t, a_i^t, e^{t+1}) &\stackrel{\text{def}}{=} \Pr(e^{t+1} | e^t, a_i^t) \\
&= \Pr(s^{t+1}, n_{\neq i}^{t+1}, \tilde{o}_i^{t+1} | s^t, n_{\neq i}^t, \tilde{o}_i^t, a_i^t) \\
&= \sum_{o_{\neq i}^{t+1}} \Pr(s^{t+1}, n_{\neq i}^{t+1}, o_{i-1}^{t+1}, \tilde{o}_i^t | s^t, n_{\neq i}^t, \tilde{o}_i^t, a_i^t) \\
&= \sum_{o_{\neq i}^{t+1}} \Pr(n_{\neq i}^{t+1} | s^t, n_{\neq i}^t, \tilde{o}_i^t, a_i^t, s^{t+1}, o^{t+1}) \cdot \Pr(s^{t+1}, o_{\neq i}^{t+1}, \tilde{o}_i^{t+1} | s^t, n_{\neq i}^t, \tilde{o}_i^t, a_i^t) \\
&= \sum_{o_{\neq i}^{t+1}} \Pr(n_{\neq i}^{t+1} | s^t, n_{\neq i}^t, \tilde{o}_i^t, a_i^t, s^{t+1}, o^{t+1}) \\
&\quad \cdot \Pr(o_{\neq i}^{t+1}, \tilde{o}_i^{t+1} | s^t, n_{\neq i}^t, \tilde{o}_i^t, a_i^t, s^{t+1}) \cdot \Pr(s^{t+1} | s^t, n_{\neq i}^t, \tilde{o}_i^t, a_i^t) \\
&= \sum_{o_{\neq i}^{t+1}} \left( \prod_{j \neq i} \eta(n_j^t, o_j^{t+1}, n_j^{t+1}) \right) \\
&\quad \cdot O(\langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}, o^{t+1}) \cdot T(s^t, \langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}).
\end{align*}
$$

The formula above does not raise the same issue as $\tilde{O}_i^t$ is a state variable, and the observation variable $O_i^t$ now does not depend on the previous state given the new one and the action (cf. Fig. A.1 (bottom right)). Also, we have the following observation function:

$$
\begin{align*}
O_e(a_i^t, e_i^{t+1}, o_i^{t+1}) &\stackrel{\text{def}}{=} \Pr(o_i^{t+1} | a_i^t, e_i^{t+1}) \\
&= \Pr(o_i^{t+1} | a_i^t, \langle s^{t+1}, n_{\neq i}^{t+1}, \tilde{o}_i^{t+1} \rangle) = \mathbf{1}_{o_i^{t+1}=\tilde{o}_i^{t+1}},
\end{align*}
$$

and the trivial reward function:

$$
r_e(e^t, a_i^t) = r(s^t, a_i^t, \psi_{\neq i}(n_{\neq i}^t)).
$$

$\frac{e^t = \langle s^t, n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t \rangle}{e^t = \langle s^t, n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t \rangle}$ In this work, we have also considered a third choice for the extended state, defined as $e^t = \langle s^t, n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t \rangle$, where $\tilde{O}_{\neq i}^t$ is a state variable (not an observation variable) corresponding to other agents' observations at time $t$:

$$
T_e(e^t, a_i^t, e^{t+1}) \stackrel{\text{def}}{=} \Pr(e^{t+1} | e^t, a_i^t)
$$
$$
\begin{align*}
&= \Pr(s^{t+1}, n_{\neq i}^t, \tilde{o}_{\neq i}^{t+1} | s^t, n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t, a_i^t) \\
&= \Pr(\tilde{o}_{\neq i}^{t+1} | s^{t+1}, n_{\neq i}^t, s^t, n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t, a_i^t) \cdot \Pr(s^{t+1}, n_{\neq i}^t | s^t, n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t, a_i^t) \\
&= \Pr(\tilde{o}_{\neq i}^{t+1} | s^{t+1}, n_{\neq i}^t, s^t, n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t, a_i^t) \cdot \Pr(s^{t+1} | n_{\neq i}^t, s^t, n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t, a_i^t) \\
&\qquad \cdot \Pr(n_{\neq i}^t | s^t, n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t, a_i^t) \\
&= \Pr(s^{t+1} | s^t, n_{\neq i}^t, a_i^t) \cdot \Pr(n_{\neq i}^t | n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t) \cdot \Pr(\tilde{o}_{\neq i}^{t+1} | s^{t+1}, n_{\neq i}^t, a_i^t) \\
&= \Pr(s^{t+1} | s^t, n_{\neq i}^t, a_i^t) \cdot \Pr(n_{\neq i}^t | n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t) \cdot \sum_{\tilde{o}_i^{t+1}} \Pr(\tilde{o}_{\neq i}^{t+1} | \tilde{o}_i^{t+1} | s^{t+1}, n_{\neq i}^t, a_i^t) \\
&= T(s^t, \langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}) \cdot \prod_{j \neq i} \eta(n_j^{t-1}, o_j^t, n_j^t) \\
&\qquad \cdot \sum_{\tilde{o}_i^{t+1}} O(\langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}, \langle \tilde{o}_{\neq i}^{t+1}, \tilde{o}_i^{t+1} \rangle).
\end{align*}
$$

The formula above does not raise issues. As illustrated by Fig. A.1 (bottom right), the actual observation variable $O_i^{t+1}$ is independent on $E^t$ given $E^{t+1}$ and $A^t$. Also, we have the following observation function:

$$
\begin{align*}
O_e(a_i^t, e_i^{t+1}, o_i^{t+1}) &\stackrel{\text{def}}{=} \Pr(o_i^{t+1} | a_i^t, e_i^{t+1}) \\
&= \Pr(o_i^{t+1} | a_i^t, \langle s^{t+1}, n_{\neq i}^t, \tilde{o}_{\neq i}^{t+1} \rangle) \\
&= \frac{\Pr(\tilde{o}_{\neq i}^{t+1}, o_i^{t+1}, s^{t+1}, n_{\neq i}^t, a_i^t)}{\Pr(\tilde{o}_{\neq i}^{t+1}, s^{t+1}, n_{\neq i}^t, a_i^t)} \\
&= \frac{\Pr(\tilde{o}_{\neq i}^{t+1}, o_i^{t+1} | s^{t+1}, n_{\neq i}^t, a_i^t)}{\sum_{o_i^{t+1}} \Pr(\tilde{o}_{\neq i}^{t+1}, o_i^{t+1} | s^{t+1}, n_{\neq i}^t, a_i^t)} \\
&= \frac{O(\langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}, \langle \tilde{o}_{\neq i}^{t+1}, o_i^{t+1} \rangle)}{\sum_{\tilde{o}_i^{t+1}} O(\langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}, \langle \tilde{o}_{\neq i}^{t+1}, \tilde{o}_i^{t+1} \rangle)}.
\end{align*}
$$

We can see that the denominator is identical to the last part of the transition function. In practice, when computing transition probabilities, we will store the values for

$$
\sum_{\tilde{o}_i^{t+1}} O(\langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}, \langle \tilde{o}_{\neq i}^{t+1}, \tilde{o}_i^{t+1} \rangle)
$$

so as to reuse them when computing the observation function. In the end, the reward function is obtained with:

$$
\begin{align*}
r_e(e^t, a_i^t) &= r(\langle s^t, n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t \rangle, a_i^t) \\
&= \sum_{n_{\neq i}^t} \Pr(n_{\neq i}^t | n_{\neq i}^{t-1}, \tilde{o}_{\neq i}^t) \cdot r(s^t, n_{\neq i}^{t-1}, a_i^t) \\
&= \sum_{n_{\neq i}^t} \left( \prod_{j \neq i} \eta(n_j^{t-1}, \tilde{o}_j^t, n_j^t) \right) \cdot r(s^t, \langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle).
\end{align*}
$$

Different formalizations lead to different state spaces with different sizes, so that the time and space complexities of the generation of this best-response POMDP or of its solving will depend on the choice of formalization. Which choice is best shall depend on the Dec-POMDP at hand,
<figure><img src="image_38.png" /><figcaption>Figure A.1: (top left) Standard POMDP dependencies, including intermediate variables used to compute the transition function (only); and candidate Best-Response POMDP formalizations with: (top right) $e_i^t \stackrel{\text{def}}{=} \langle s^t, n_{\neq i}^t \rangle$, (bottom left) $e_i^t \stackrel{\text{def}}{=} \langle s^t, n_{\neq i}^t, o_i^t \rangle$, and (bottom right) $e_i^t \stackrel{\text{def}}{=} \langle s^t, n_{\neq i}^{t-1}, o_{\neq i}^t \rangle$.</figcaption></figure>

and possibly on the current FSCs. We have opted for the simplest of the two formalizations presented above (which we call the “MOMDP formalization” because one state variable is fully observed), but observed little differences in practice in our experiments.
Bibliography

Rachid Alami, Raja Chatila, Sara Fleury, Malik Ghallab, and Félix Ingrand. An architecture for autonomy. *The International Journal of Robotics Research*, 17(4):315–337, 1998.

Alexandre Albore, Héctor Palacios, and Hector Geffner. A translation-based approach to contingent planning. In *Twenty-First International Joint Conference on Artificial Intelligence*, 2009.

Christopher Amato. *Increasing scalability in algorithms for centralized and decentralized partially observable Markov decision processes: Efficient decision-making and coordination in uncertain environments*. University of Massachusetts Amherst, 2010.

Christopher Amato and Shlomo Zilberstein. Achieving goals in decentralized pomdps. In *Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 1*, pages 593–600, 2009.

Christopher Amato, Jilles Steeve Dibangoye, and Shlomo Zilberstein. Incremental policy generation for finite-horizon dec-pomdps. In *Nineteenth International Conference on Automated Planning and Scheduling*, 2009.

Christopher Amato, Blai Bonet, and Shlomo Zilberstein. Finite-state controllers based on Mealy machines for centralized and decentralized POMDPs. In *Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence*, 2010.

Christopher Amato, Daniel Bernstein, and Shlomo Zilberstein. Optimizing memory-bounded controllers for decentralized POMDPs. *Proceedings of the Conference on Uncertainty in Artificial Intelligence, (UAI-07)*, 06 2012.

Mauricio Araya-López, Vincent Thomas, Olivier Buffet, and François Charpillet. A closer look at MOMDPs. In *Proceedings of the IEEE International Conference on Tools with Artificial Intelligence (ICTAI)*, 2010.

Matthew Arnold, Rachel K. E. Bellamy, Michael Hind, Stephanie Houde, Sameep Mehta, Aleksandra Mojsilovic, Ravi Nair, Karthikeyan Natesan Ramamurthy, Darrell Reimer, Alexandra Olteanu, David Piorkowski, Jason Tsay, and Kush R. Varshney. Factsheets: Increasing trust in AI services through supplier's declarations of conformity, 2018. URL https://arxiv.org/abs/1808.07261.

Hagai Attias. Planning by probabilistic inference. In Christopher M. Bishop and Brendan J. Frey, editors, *Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics*, Proceedings of Machine Learning Research, pages 9–16. PMLR, 2003. Reissued by PMLR on 01 April 2021.
Andrea Bauer, Dirk Wollherr, and Martin Buss. Human-robot collaboration: a survey. *I. J. Humanoid Robotics*, 5:47–66, 03 2008. doi: 10.1142/S0219843608001303.

Richard Bellman. A Markovian decision process. *Journal of Mathematics and Mechanics*, 6(5): 679–684, 1957. URL http://www.jstor.org/stable/24900506.

Ron Berenstein and Yael Edan. Human-robot cooperative precision spraying: Collaboration levels and optimization function. *IFAC Proceedings Volumes*, 45(22):799–804, 2012. ISSN 1474-6670. doi: https://doi.org/10.3182/20120905-3-HR-2030.00084. URL https://www.sciencedirect.com/science/article/pii/S1474667016337077. 10th IFAC Symposium on Robot Control.

Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of Markov decision processes. *Math. of Operations Research*, 27(4), 2002.

Daniel S. Bernstein, Eric A. Hansen, and Shlomo Zilberstein. Bounded policy iteration for decentralized POMDPs. In *Proceedings of the 19th International Joint Conference on Artificial Intelligence*, IJCAI'05, page 1287–1292. Morgan Kaufmann Publishers Inc., 2005.

Daniel S. Bernstein, Christopher Amato, Eric A. Hansen, and Shlomo Zilberstein. Policy iteration for decentralized control of Markov decision processes. *Journal of Artificial Intelligence Research*, 34:89–132, 2009. doi: 10.1613/jair.2667.

Aaron Bestick, Ruzena Bajcsy, and Anca Dragan. Implicitly assisting humans to choose good grasps in robot to human handovers. In *2016 Int. Symp. on Experimental Robotics*, 2017. ISBN 978-3-319-50114-7. doi: 10.1007/978-3-319-50115-4_30.

Craig Boutilier, Thomas Dean, and Steve Hanks. Decision-theoretic planning: Structural assumptions and computational leverage. *J. Artif. Int. Res.*, 11(1):1–94, 1999. ISSN 1076-9757.

Cameron Browne, Edward J. Powley, Daniel Whitehouse, Simon M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of Monte Carlo tree search methods. *IEEE Trans. Comp. Intell. AI Games*, 4(1): 1–43, 2012. doi: 10.1109/TCIAIG.2012.2186810. URL http://ieeexplore.ieee.org/xplabs_all.jsp?arnumber=6145622.

Jonathan Cacace, Alberto Finzi, Vincenzo Lippiello, Giuseppe Loianno, and Dario Sanzone. Aerial service vehicles for industrial inspection: Task decomposition and plan execution. *Applied Intelligence*, 42:49–62, 01 2015. doi: 10.1007/s10489-014-0542-0.

Sotirios P. Chatzis and Dimitrios Kosmopoulos. A non-stationary infinite partially-observable Markov decision process. In Stefan Wermter, Cornelius Weber, Włodzisław Duch, Timo Honkela, Petia Koprinkova-Hristova, Sven Magg, Günther Palm, and Alessandro E. P. Villa, editors, *Artificial Neural Networks and Machine Learning (ICANN)*, pages 355–362, Cham, 2014. Springer International Publishing. ISBN 978-3-319-11179-7.

Min Chen, Stefanos Nikolaidis, Harold Soh, David Hsu, and Siddhartha Srinivasa. Planning with trust for human-robot collaboration. In *2018 13th ACM/IEEE International Conference on Human-Robot Interaction (HRI)*, pages 307–315, 2018.

Min Chen, Stefanos Nikolaidis, Harold Soh, David Hsu, and Siddhartha Srinivasa. Trust-aware decision making for human-robot collaboration: Model learning and planning. *J. Hum.-Robot Interact.*, 9(2), January 2020. doi: 10.1145/3359616.
Alessandro Cimatti and Marco Roveri. Conformant planning via symbolic model checking. *Journal of Artificial Intelligence Research*, 13:305-338, 2000.

Jean-Alexis Delamer, Yoko Watanabe, and Caroline P. Carvalho. Solving path planning problems in urban environments based on a priori sensors availabilities and execution error propagation. In *AIAA Scitech 2019 Forum*, page 2202, 2019.

Eric V Denardo. Contraction mappings in the theory underlying dynamic programming. *Siam Review*, 9(2):165-177, 1967.

Jilles Dibangoye and Olivier Buffet. Learning to act in decentralized partially observable MDPs. In Jennifer Dy and Andreas Krause, editors, *Proceedings of the 35th International Conference on Machine Learning*, volume 80 of *Proceedings of Machine Learning Research*, pages 1233-1242. PMLR, 2018.

Jilles Steeve Dibangoye, Olivier Buffet, and François Charpillet. Error-bounded approximations for infinite-horizon discounted decentralized POMDPs. In *European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD)*, volume 8724 of *Machine Learning and Knowledge Discovery in Databases*, pages 338-353, Nancy, France, September 2014. doi: 10.1007/978-3-662-44848-9\_22. URL https://hal.inria.fr/hal-01096610.

Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet. Optimally solving Dec-POMDPs as continuous-state MDPs. *Journal of Artificial Intelligence Research*, 55:443-497, 2016.

Chuong B Do and Serafim Batzoglou. What is the expectation maximization algorithm? *Nature biotechnology*, 26(8):897-899, 2008.

Prajant Doshi and Piotr Gmytrasiewicz. A framework for sequential planning in multi-agent settings. *Journal of Artificial Intelligence Research*, 24, 07 2005.

Kai-ping Feng and Fang Yuan. Static hand gesture recognition based on hog characters and support vector machines. In *2013 2nd international symposium on instrumentation and measurement, sensor network and automation (IMSNA)*, pages 936-938. IEEE, 2013.

Javier García, José E. Florez, Álvaro Torralba, Daniel Borrajo, Carlos Linares López, Ángel García-Olaya, and Juan Sáenz. Combining linear programming and automated planning to solve intermodal transportation problems. *European Journal of Operational Research*, 227 (1):216-226, 2013. ISSN 0377-2217. doi: https://doi.org/10.1016/j.ejor.2012.12.018. URL https://www.sciencedirect.com/science/article/pii/S0377221712009496.

J. Goetz, S. Kiesler, and A. Powers. Matching robot appearance and behavior to tasks to improve human-robot cooperation. In *The 12th IEEE International Workshop on Robot and Human Interactive Communication, 2003. Proceedings. ROMAN 2003.*, pages 55-60, 2003. doi: 10.1109/ROMAN.2003.1251796.

José Carlos González, Fernando Fernández, Ángel García-Olaya, and Raquel Fuentetaja. On the application of classical planning to real social robotic tasks. In *Proceedings of the 5th Workshop on Planning and Robotics (PlanRob), ICAPS Conference, Pittsburgh, Pennsylvania, USA*, pages 38-47, 2017.
O Can Görür, Benjamin Rosman, Fikret Sivrikaya, and Sahin Albayrak. Social cobots: Anticipatory decision-making for collaborative robots incorporating unexpected human behaviors. In *Proceedings of the 2018 ACM/IEEE International Conference on Human-Robot Interaction*, pages 398–406, 2018.

Marek Grześ, Pascal Poupart, Xiao Yang, and Jesse Hoey. Energy efficient execution of POMDP policies. *IEEE Transactions on Cybernetics*, 45, 2015. doi: 10.1109/TCYB.2014.2375817.

Kelleher R. Guerin, Colin Lea, Chris Paxton, and Gregory D. Hager. A framework for end-user instruction of a robot assistant for manufacturing. In *2015 IEEE International Conference on Robotics and Automation (ICRA)*, pages 6167–6174, 2015. doi: 10.1109/ICRA.2015.7140065.

Dylan Hadfield-Menell, Stuart J Russell, Pieter Abbeel, and Anca Dragan. Cooperative inverse reinforcement learning. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 29. Curran Associates, Inc., 2016.

Yanlin Han and Piotr Gmytrasiewicz. IPOMDP-Net: A deep neural network for partially observable multi-agent planning using interactive POMDPs. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 33, pages 6062–6069, 2019. doi: 10.1609/aaai.v33i01.33016062. URL https://ojs.aaai.org/index.php/AAAI/article/view/4562.

Eric A. Hansen. An improved policy iteration algorithm for partially observable MDPs. In M. Jordan, M. Kearns, and S. Solla, editors, *Advances in Neural Information Processing Systems*, volume 10. MIT Press, 1997.

Eric A. Hansen. Solving POMDPs by searching in policy space. In *Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence*, UAI'98, page 211–219, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc. ISBN 155860555X.

Eric A. Hansen and Shlomo Zilberstein. LAO*: A heuristic search algorithm that finds solutions with loops. *Artificial Intelligence*, 129(1):35–62, 2001. doi: https://doi.org/10.1016/S0004-3702(01)00106-0.

Malte Helmert. Concise finite-domain representations for PDDL planning tasks. *Artificial Intelligence*, 173(5):503–535, 2009. ISSN 0004-3702. doi: https://doi.org/10.1016/j.artint.2008.10.013. URL https://www.sciencedirect.com/science/article/pii/S0004370208001926. Advances in Automated Plan Generation.

Trong Nghia Hoang and Kian Hsiang Low. Interactive POMDP lite: Towards practical planning to predict and exploit intentions for interacting with self-interested agents. *Proc. of the International Joint Conference on Artificial Intelligence (IJCAI)*, 04 2013.

Jörg Hoffmann and Ronen Brafman. Contingent planning via heuristic forward search with implicit belief states. In *Proc. ICAPS*, volume 2005, pages 71–80, 2005.

Jörg Hoffmann and Ronen I Brafman. Conformant planning via heuristic forward search: A new approach. *Artificial Intelligence*, 170(6-7):507–541, 2006.

R. A. Howard. *Dynamic Programming and Markov Processes*. MIT Press, Cambridge, MA, 1960.

ISO 10218-1:2011. Robots and robotic devices – safety requirements for industrial robots. Standard, International Organization for Standardization, 2011.
ISO 10218-2:2011. Robots and robotic devices – safety requirements for industrial robots. Standard, International Organization for Standardization, 2011.

Mithun George Jacob, Yu-Ting Li, George A Akingba, and Juan P Wachs. Collaboration with a robotic scrub nurse. *Communications of the ACM*, 56(5):68–75, 2013.

Glenn Jocher. ultralytics/yolov5: v3.1 - bug fixes and performance improvements. https://github.com/ultralytics/yolov5, October 2020. URL https://doi.org/10.5281/zenodo.4154370.

Yong Gyu Jung, Min Soo Kang, and Jun Heo. Clustering performance comparison using K-means and expectation maximization algorithms. *Biotechnology & Biotechnological Equipment*, 28 (sup1):S44–S48, 2014.

Abir-Beatrice Karami. Modèles Décisionnels d'Interaction Homme-Robot. Theses, Université de Caen, December 2011. URL https://hal.archives-ouvertes.fr/tel-01076430.

Abir-Beatrice Karami, Laurent Jeanpierre, and Abdel-Illah Mouaddib. Partially observable Markov decision process for managing robot collaboration with human. In *2009 21st IEEE International Conference on Tools with Artificial Intelligence*, pages 518–521, 2009. doi: 10.1109/ICTAI.2009.61.

Azfar Khalid, Pierre Kirisci, Zied Ghrairi, Klaus-Dieter Thoben, and Jürgen Pannek. A methodology to develop collaborative robotic cyber physical systems for production environments. *Logistics Research*, 9(1):1–15, 2016.

Levente Kocsis and Csaba Szepesvári. Bandit based Monte-Carlo planning. In *Proceedings of the 17th European Conference on Machine Learning*, ECML’06, pages 282–293. Springer-Verlag, 2006. doi: 10.1007/11871842_29. URL http://dx.doi.org/10.1007/11871842_29.

David M. Kreps. Nash Equilibrium, pages 167–177. Palgrave Macmillan UK, London, 1989. ISBN 978-1-349-20181-5. doi: 10.1007/978-1-349-20181-5_19. URL https://doi.org/10.1007/978-1-349-20181-5_19.

Akshat Kumar and Shlomo Zilberstein. Anytime planning for decentralized POMDPs using expectation maximization. In *Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence*, UAI’10, page 294–301. AUAI Press, 2010. ISBN 9780974903965.

Akshat Kumar, Shlomo Zilberstein, and Marc Toussaint. Scalable multiagent planning using probabilistic inference. In *Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume Three*, IJCAI’11, page 2140–2146. AAAI Press, 2011. ISBN 9781577355151.

Hanna Kurniawati, David Hsu, and Wee Sun Lee. SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In *In Proc. Robotics: Science and Systems*, 2008.

Sonya S Kwak. The impact of the robot appearance types on social interaction with a robot and service evaluation of a robot. *Archives of Design Research*, 27(2):81–93, 2014.

Erwan Lecarpentier and Emmanuel Rachelson. *Non-Stationary Markov Decision Processes a Worst-Case Approach Using Model-Based Reinforcement Learning*. Curran Associates Inc., Red Hook, NY, USA, 2019.
Dongheui Lee, Christian Ott, Yoshihiko Nakamura, and Gerd Hirzinger. Physical human robot interaction in imitation learning. In *2011 IEEE International Conference on Robotics and Automation*, pages 3439-3440. IEEE, 2011.

Yee Yeng Liau and Kwangyeol Ryu. Status recognition using pre-trained yolov5 for sustainable human-robot collaboration (hrc) system in mold assembly. *Sustainability*, 13(21), 2021. ISSN 2071-1050. doi: 10.3390/su132112044. URL https://www.mdpi.com/2071-1050/13/21/12044.

Kai Lin, Yihui Li, Jinchuan Sun, Dongsheng Zhou, and Qiang Zhang. Multi-sensor fusion for body sensor network in medical human-robot interaction scenario. *Information Fusion*, 57: 15-26, 2020.

Miao Liu, Christopher Amato, Xuejun Liao, Lawrence Carin, and Jonathan P How. Stick-breaking policy learning in Dec-POMDPs. *Ijcai*, page 7, 2015.

Zhihao Liu, Quan Liu, Lihui Wang, Wenjun Xu, and Zude Zhou. Task-level decision-making for dynamic and stochastic human-robot collaboration based on dual agents deep reinforcement learning. *The International Journal of Advanced Manufacturing Technology*, 115, 08 2021. doi: 10.1007/s00170-021-07265-2.

Honghao Lv, Geng Yang, Huiying Zhou, Xiaoyan Huang, Huayong Yang, and Zhibo Pang. Tele-operation of collaborative robot for remote dementia care in home environments. *IEEE Journal of Translational Engineering in Health and Medicine*, 8:1-10, 2020. doi: 10.1109/JTEHM.2020.3002384.

Liam C. MacDermed and Charles L. Isbell. Point based value iteration with optimal belief compression for Dec-POMDPs. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, *Advances in Neural Information Processing Systems*, volume 26. Curran Associates, Inc., 2013. URL https://proceedings.neurips.cc/paper/2013/file/c9e1074f5b3f9fc8ea15d152add07294-Paper.pdf.

Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilistic planning and related stochastic optimization problems. *Artificial Intelligence*, 147(1):5-34, 2003. ISSN 0004-3702. Planning with Uncertainty and Incomplete Information.

Anthony S Maida. Introspection and reasoning about the beliefs of other agents. In *Proceedings of the Eights Annual Conference of the Cognitive Science Society*, pages 187-195, 1986.

Nicholas Metropolis and Stanislaw Ulam. The Monte Carlo method. *Journal of the American Statistical Association*, 44(247):335-341, 1949.

Abdullah Mohammed, Bernard Schmidt, and Lihui Wang. Active collision avoidance for human-robot collaboration driven by vision sensors. *International Journal of Computer Integrated Manufacturing*, 30(9):970-980, 2017.

Saeid Mokaram, Jonathan M. Aitken, Uriel Martinez-Hernandez, Iveta Eimontaite, David Cameron, Joe Rolph, Ian Gwilt, Owen McAree, and James Law. A ROS-integrated API for the KUKA LBR iiwa collaborative robot. *IFAC-PapersOnLine*, 50(1):15859-15864, 2017. ISSN 2405-8963. doi: https://doi.org/10.1016/j.ifacol.2017.08.2331. URL https://www.sciencedirect.com/science/article/pii/S2405896317331464. 20th IFAC World Congress.
Masahiro Mori. The uncanny valley. *IEEE Robotics & Automation Magazine*, 19(2):98-100, 2012.

Ranjit Nair, Milind Tambe, Makoto Yokoo, David Pynadath, and Stacy Marsella. Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings. In *IJCAI*, volume 3, pages 705-711. Citeseer, 2003.

Hugo Nascimento, Martin Mujica, and Mourad Benoussaad. Collision avoidance in human-robot interaction using Kinect vision system combined with robot's model and data. In *2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*, pages 10293-10298, 2020. doi: 10.1109/IROS45743.2020.9341248.

Andrew Y. Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In *in Proc. 17th International Conf. on Machine Learning*, pages 663-670. Morgan Kaufmann, 2000.

Stefanos Nikolaidis and Julie Shah. Human-robot cross-training: Computational formulation, modeling and evaluation of a human team training strategy. In *Proceedings of the 8th ACM/IEEE International Conference on Human-Robot Interaction*, HRI '13, page 33-40. IEEE Press, 2013. ISBN 9781467330558.

Stefanos Nikolaidis, Anton Kuznetsov, David Hsu, and Siddhartha Srinivasa. Formalizing human-robot mutual adaptation: A bounded memory model. In *2016 11th ACM/IEEE International Conference on Human-Robot Interaction (HRI)*, pages 75-82. IEEE, 2016.

Stefanos Nikolaidis, Yu Xiang Zhu, David Hsu, and Siddhartha Srinivasa. Human-robot mutual adaptation in shared autonomy. In *Proceedings of the 2017 ACM/IEEE International Conference on Human-Robot Interaction*, HRI '17, page 294-302. Association for Computing Machinery, 2017. ISBN 9781450343367. doi: 10.1145/2909824.3020252. URL https://doi.org/10.1145/2909824.3020252.

Frans A. Oliehoek and Christopher Amato. *A Concise Introduction to Decentralized POMDPs*. Springer Publishing Company, Incorporated, 1st edition, 2016. ISBN 3319289276.

Frans A. Oliehoek, Matthijs Spaan, and Nikos Vlassis. Best-response play in partially observable card games. In *Benelearn*, 2005.

Shayegan Omidshafiei, Ali-akbar Agha-mohammadi, Christopher Amato, and Jonathan P. How. Decentralized control of partially observable Markov decision processes using belief space macro-actions, 2015. URL https://arxiv.org/abs/1502.06030.

Sylvie C.W. Ong, Shao W. Png, David Hsu, and Wee S. Lee. POMDPs for robotic tasks with mixed observability. In *Robotics: Science and Systems (RSS)*, 2009.

Takayuki Osogami and Makoto Otsuka. Restricted Boltzmann machines modeling human choice. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, *Advances in Neural Information Processing Systems*, volume 27. Curran Associates, Inc., 2014. URL https://proceedings.neurips.cc/paper/2014/file/3295c76acbf4caaed33c36b1b5fc2cb1-Paper.pdf.

Makoto Otsuka and Takayuki Osogami. A deep choice model. *Proceedings of the AAAI Conference on Artificial Intelligence*, 30(1), 2016. doi: 10.1609/aaai.v30i1.10059. URL https://ojs.aaai.org/index.php/AAAI/article/view/10059.
Joni Pajarinen and Jaakko Peltonen. Periodic finite state controllers for efficient POMDP and DEC-POMDP planning. In *Advances in Neural Information Processing Systems 24*, volume 24, 2011.

Joelle Pineau, Geoff Gordon, and Sebastian Thrun. Point-based value iteration: An anytime algorithm for POMDPs. In *Proceedings of the 18th International Joint Conference on Artificial Intelligence*, IJCAI'03, page 1025–1030. Morgan Kaufmann Publishers Inc., 2003.

Pascal Poupart and Craig Boutilier. Bounded finite state controllers. In S. Thrun, L. Saul, and B. Schölkopf, editors, *Advances in Neural Information Processing Systems*, volume 16. MIT Press, 2003. URL https://proceedings.neurips.cc/paper/2003/file/4c5bcfec8584af0d967f1ab10179ca4b-Paper.pdf.

David V. Pynadath and Milind Tambe. The communicative multiagent team decision problem: Analyzing teamwork theories and models. *Journal of Artificial Intelligence Research*, 16, 2002. ISSN 1076-9757. doi: 10.1613/jair.1024.

Alina Roitberg, Alexander Perzylo, Nikhil Somani, Manuel Giuliani, Markus Rickert, and Alois Knoll. Human activity recognition in the context of industrial human-robot interaction. In *Signal and Information Processing Association Annual Summit and Conference (APSIDA), 2014 Asia-Pacific*, pages 1–10. IEEE, 2014.

Pol Rosello. Fully-nested interactive POMDPs for partially-observable turn-based games. Technical report, CS 238, Stanford University, 2016.

Stéphane Ross, Joelle Pineau, Sébastien Paquet, and Brahim Chaib-draa. Online planning algorithms for POMDPs. *Journal of Artificial Intelligence Research*, 2008.

Stuart Russell. Learning agents for uncertain environments (extended abstract). In *Proceedings of the Eleventh Annual Conference on Computational Learning Theory*, COLT' 98, page 101–103. Association for Computing Machinery, 1998. ISBN 1581130570. doi: 10.1145/279943.279964. URL https://doi.org/10.1145/279943.279964.

John Rust. Using randomization to break the curse of dimensionality. *Econometrica: Journal of the Econometric Society*, pages 487–516, 1997.

Mohammad Safeea and Pedro Neto. Minimum distance calculation using laser scanner and imus for safe human-robot interaction. *Robotics and Computer-Integrated Manufacturing*, 58:33–42, 2019.

Bernard Schmidt and Lihui Wang. Depth camera based collision avoidance via active robot control. *Journal of Manufacturing Systems*, 33(4):711–718, 2014. ISSN 0278-6125. doi: https://doi.org/10.1016/j.jmsy.2014.04.004. URL https://www.sciencedirect.com/science/article/pii/S0278612514000417.

Sven Seuken and Shlomo Zilberstein. Improved memory-bounded dynamic programming for decentralized pomdps. *ArXiv*, abs/1206.5295, 2007.

Guy Shani, Joelle Pineau, and Roberta Kaplow. A survey of point-based POMDP solvers. *Autonomous Agents and Multi-Agent Systems*, 27:1–51, 2012.

David Silver and Joel Veness. Monte-Carlo planning in large POMDPs. In *Advances in Neural Information Processing Systems*, volume 23. Curran Associates, Inc., 2010.
Trey Smith and Reid Simmons. Heuristic search value iteration for POMDPs. In *Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence*, UAI '04, page 520–527. AUAI Press, 2004. ISBN 0974903906.

Adhiraj Somani, Nan Ye, David Hsu, and Wee Sun Lee. DESPOT: Online POMDP planning with regularization. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, *Advances in Neural Information Processing Systems*, volume 26. Curran Associates, Inc., 2013. URL https://proceedings.neurips.cc/paper/2013/file/c2aee86157b4a40b78132f1e71a9e6f1-Paper.pdf.

Edward Sondik. The optimal control of partially observable Markov process over the infinite horizon: Discounted costs. *Operations Research*, 26:282–304, 04 1978. doi: 10.1287/opre.26.2.282.

Matthijs TJ Spaan and Nikos Vlassis. Perseus: Randomized point-based value iteration for POMDPs. *Journal of artificial intelligence research*, 24:195–220, 2005.

Zachary N Sunberg and Mykel J Kochenderfer. Online algorithms for pomdps with continuous state, action, and observation spaces. In *Twenty-Eighth International Conference on Automated Planning and Scheduling*, 2018.

Richard S. Sutton and Andrew G. Barto. *Reinforcement Learning: An Introduction*. The MIT Press, second edition, 2018. URL http://incompleteideas.net/book/the-book-2nd.html.

Daniel Szer, François Charpillet, and Shlomo Zilberstein. MAA*: A heuristic search algorithm for solving decentralized POMDPs. In *Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI-05)*, 2005.

Aaquib Tabrez and Bradley Hayes. Improving human-robot interaction through explainable reinforcement learning. In *2019 14th ACM/IEEE International Conference on Human-Robot Interaction (HRI)*, pages 751–753, 2019. doi: 10.1109/HRI.2019.8673198.

Aaquib Tabrez, Matthew Luebbers, and Bradley Hayes. A survey of mental modeling techniques in human-robot teaming. *Current Robotics Reports*, 1, 12 2020. doi: 10.1007/s43154-020-00019-0.

Tapio Taipalus and Kazuhiro Kosuge. Development of service robot for fetching objects in home environment. In *2005 International Symposium on Computational Intelligence in Robotics and Automation*, pages 451–456. IEEE, 2005.

Adriana Tapus, Maja J Mataric, and Brian Scassellati. Socially assistive robotics [grand challenges of robotics]. *IEEE robotics & automation magazine*, 14(1):35–42, 2007.

Adriana Tapus, Cristian Tapus, and Maja J Mataric. The use of socially assistive robots in the design of intelligent cognitive therapies for people with dementia. In *2009 IEEE international conference on rehabilitation robotics*, pages 924–929. IEEE, 2009.

Rundong Tian and Eric Paulos. Adroid: Augmenting hands-on making with a collaborative robot. In *The 34th Annual ACM Symposium on User Interface Software and Technology*, UIST '21, page 270–281. Association for Computing Machinery, 2021. ISBN 9781450386357. doi: 10.1145/3472749.3474749. URL https://doi.org/10.1145/3472749.3474749.
Marc Toussaint, Stefan Harmeling, and Amos Storkey. Probabilistic inference for solving (PO) MDPs. Technical report, Technical Report EDI-INF-RR-0934, School of Informatics, University of Edinburgh, 2006.

Rudolph Triebel, Kai Arras, Rachid Alami, Lucas Beyer, Stefan Breuers, Raja Chatila, Mohamed Chetouani, Daniel Cremers, Vanessa Evers, Michelangelo Fiore, et al. Spencer: A socially aware service robot for passenger guidance and help in busy airports. In *Field and service robotics*, pages 607–622. Springer, 2016.

Vaibhav V. Unhelkar, Shen Li, and Julie A. Shah. Decision-making for bidirectional communication in sequential human-robot collaborative tasks. In *Proceedings of the 2020 ACM/IEEE International Conference on Human-Robot Interaction*, HRI '20, page 329–341. Association for Computing Machinery, 2020. ISBN 9781450367462. doi: 10.1145/3319502.3374779. URL https://doi.org/10.1145/3319502.3374779.

Lorenzo Vianello, Luigi Penco, Waldez Gomes, Yang You, Salvatore Maria Anzalone, Pauline Maurice, Vincent Thomas, and Serena Ivaldi. Human-Humanoid Interaction and Cooperation: a Review. *Current Robotics Reports*, 2(4):441–454, 2021. ISSN 2662-4087. doi: 10.1007/s43154-021-00068-z. URL https://doi.org/10.1007/s43154-021-00068-z.

Valeria Villani, Fabio Pini, Francesco Leali, and Cristian Secchi. Survey on human-robot collaboration in industrial settings: Safety, intuitive interfaces and applications. *Mechatronics*, 55:248–266, 2018. ISSN 0957-4158. doi: https://doi.org/10.1016/j.mechatronics.2018.02.009. URL https://www.sciencedirect.com/science/article/pii/S0957415818300321.

Ales Vysocky and Petr Novak. Human - robot collaboration in industry. *MM Science Journal*, 2016:903–906, 06 2016. doi: 10.17973/MMSJ.2016_06_201611.

Michael L Walters, Dag S Syrdal, Kerstin Dautenhahn, René Te Boekhorst, and Kheng Lee Koay. Avoiding the uncanny valley: robot appearance, personality and consistency of behavior in an attention-seeking home scenario for a robot companion. *Autonomous Robots*, 24(2):159–178, 2008.

Michael L Walters, Kheng Lee Koay, Dag Sverre Syrdal, Kerstin Dautenhahn, and René Te Boekhorst. Preferences and perceptions of robot appearance and embodiment in human-robot interaction trials. *Procs of New Frontiers in Human-Robot Interaction*, 2009.

Fangju Wang. An I-POMDP based multi-agent architecture for dialogue tutoring. In *2013 International Conference on Advanced ICT and Education (ICAICTE-13)*, pages 469–472. Atlantis Press, 2013.

Haoyu Wang, Biao Zhang, Tingshen Zhang, and Austin Jakacky. Tele-operating a collaborative robot for space repairs with virtual reality. In *2019 IEEE 9th Annual International Conference on CYBER Technology in Automation, Control, and Intelligent Systems (CYBER)*, pages 175–180. IEEE, 2019.

Lihui Wang. Collaborative robot monitoring and control for enhanced sustainability. *The International Journal of Advanced Manufacturing Technology*, 81:1433–1445, 12 2015. doi: 10.1007/s00170-013-4864-6.

Weitian Wang, Rui Li, Zachary Max Diekel, Yi Chen, Zhujun Zhang, and Yunyi Jia. Controlling object hand-over in human-robot collaboration via natural wearable sensing. *IEEE Transactions on Human-Machine Systems*, 49(1):59–71, 2018.
Xi Vincent Wang, Zsolt Kemény, József Váncza, and Lihui Wang. Human-robot collaborative assembly in cyber-physical production: Classification framework and implementation. *CIRP Annals*, 66(1):5–8, 2017.

Yorick Wilks and Afzal Ballim. Multiple agents and the heuristic ascription of belief. In *Proceedings of the 10th International Joint Conference on Artificial Intelligence - Volume 1*, IJCAI'87, page 118–124. Morgan Kaufmann Publishers Inc., 1987.

Feng Wu, Shlomo Zilberstein, and Nicholas R. Jennings. Monte-Carlo expectation maximization for decentralized POMDPs. In *Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence*, IJCAI '13, page 397–403. AAAI Press, 2013. ISBN 9781577356332.

Bo Yang and Zheng Qin. Composing semantic web services with PDDL. *Information Technology Journal*, 9(1):48–54, 2010.

Yang You, Vincent Thomas, Francis Colas, and Olivier Buffet. Solving infinite-horizon Dec-POMDPs using finite state controllers within JESP. In *2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI)*, pages 427–434, 2021a. doi: 10.1109/ICTAI52525.2021.00069.

Yang You, Vincent Thomas, Francis Colas, and Olivier Buffet. Résolution de Dec-POMDP à horizon infini à l'aide de contrôleurs à états finis dans JESP. In *Actes des seièmes journées francophones planification, décision, apprentissage pour la conduite de systèmes (JFPDA-21)*, 2021b.

Yang You, Vincent Thomas, Francis Colas, and Olivier Buffet. Solving infinite-horizon dec-pomdps using finite state controllers within jesp, 2021c.

Yang You, Vincent Thomas, Francis Colas, Olivier Buffet, and Rachid Alami. Planification robuste pour la collaboration homme-robot. In *Actes des dix-septièmes journées francophones planification, décision, apprentissage pour la conduite de systèmes (JFPDA-22)*, 2022.

Andrea Maria Zanchettin and Paolo Rocco. Path-consistent safety in mixed human-robot collaborative manufacturing environments. In *Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems*, pages 1131–1136, 2013. doi: 10.1109/IROS.2013.6696492.

Andrea Maria Zanchettin, Nicola Maria Ceriani, Paolo Rocco, Hao Ding, and Björn Matthias. Safety in human-robot collaborative manufacturing environments: Metrics and control. *IEEE Transactions on Automation Science and Engineering*, 13(2):882–893, 2016. doi: 10.1109/TASE.2015.2412256.

Yan Zhao, Shuxiang Guo, Yuxin Wang, Jinxin Cui, Youchun Ma, Yuwen Zeng, Xinke Liu, Yuhua Jiang, Youxinag Li, Liwei Shi, et al. A CNN-based prototype method of unstructured surgical state perception and navigation for an endovascular surgery robot. *Medical & Biological Engineering & Computing*, 57(9):1875–1887, 2019.

Wei Zheng, Bo Wu, and Hai Lin. POMDP model learning for human robot collaboration. In *2018 IEEE Conference on Decision and Control (CDC)*, pages 1156–1161. IEEE, 2018.

K.J Åström. Optimal control of Markov processes with incomplete state information. *Journal of Mathematical Analysis and Applications*, 10(1):174 – 205, 1965. ISSN 0022-247X. doi: https://doi.org/10.1016/0022-247X(65)90154-X. URL http://www.sciencedirect.com/science/article/pii/0022247X6590154X.
# Résumé étendu

## 1 Introduction

Les robots collaboratifs sont largement utilisés dans la société moderne dans divers domaines. Par exemple, les robots peuvent travailler comme pulvérisateurs pour aider les agriculteurs à se débarrasser des insectes nuisibles [Berenstein and Edan, 2012], fournir des services dans les hôpitaux et les aéroports [Tapus et al., 2007, Triebel et al., 2016], soulever des objets lourds ou effectuer des manipulations d'objets de haute précision dans l'industrie [Vysocky and Novak, 2016]. Nous pouvons classer les contextes d'application des robots collaboratifs en deux catégories :

* collaboration robot-robot (RRC) : plusieurs robots travaillent ensemble pour réaliser une tâche ou un objectif spécifique en collaboration;

* collaboration homme-robot (HRC) : des humains et des robots travaillent ensemble de manière coopérative; généralement, un but est spécifié par les utilisateurs humains ou lié aux objectifs des utilisateurs humains.

Cette thèse est financée par le projet ANR *Flying Co-Worker*, dont le but à long terme est de proposer un robot manipulateur aérien capable d'aider un travailleur humain à réaliser des tâches complexes. Dans cette thèse, nous nous intéressons à la manière de concevoir le système de prise de décision d'un robot de ce type dans un contexte général, aussi bien dans le cadre de collaborations robot-robot que de collaborations homme-robot. En d'autres termes, nous étudions comment le robot doit décider de ses actions afin d'accomplir une tâche collaborative, que les partenaires soient d'autres robots ou des humains. Nous nous plaçons plus particulièrement dans le cadre de problèmes collaboratifs de prise de décision séquentielle, car (1) les tâches de collaboration nécessitent plusieurs étapes pour être accomplies, et car (2) nous cherchons des politiques permettant de maximiser la performance globale de l'équipe. L'objectif est de calculer, pour chaque agent, une politique indiquant les actions qu'il doit effectuer pour chaque situation qu'il est amené à rencontrer.

De plus, on peut décomposer le processus de décision de manière hiérarchique en décisions bas-niveau et décisions haut-niveau [Cacace et al., 2015]. Dans le cadre de la robotique, les décisions bas-niveau correspondent au contrôle de bas niveau, c'est-à-dire aux commandes motrices, et les décisions haut-niveau correspondent à la planification des tâches, c'est-à-dire au choix d'actions à grosse granularité qui déclencheront des appels aux contrôleurs bas-niveau en charge de réaliser l'action (comme se déplacer vers un lieu ou réparer un dispositif). Notre thèse se concentre sur la prise de décision haut-niveau (donc la planification des tâches) pour la robotique à la fois en RRC et en HRC.

Cette thèse utilise des modèles de prise de décision markoviens pour formaliser de tels problèmes de décision et calculer les stratégies des robots collaboratifs. Cependant, les questions de recherche posées en RRC et HRC sont différentes en raison de leurs caractéristiques propres.
Dans une tâche de collaboration robot-robot (RRC), l'ensemble des robots constitue un système multi-agent (MAS) : ils doivent travaillent ensemble pour atteindre un objectif commun. Il s'agit alors d'attribuer des politiques individuelles à chacun des robots du système pour qu'ils sachent ensuite comment se comporter dans leur environnement. Ainsi, nous étudions comment concevoir des algorithmes qui calculent des politiques optimales pour chaque agent afin de maximiser la performance globale lors de l'exécution décentralisée de ces politiques. D'autre part, dans une tâche de collaboration homme-robot, seuls les robots peuvent être contrôlés, mais pas les hommes. Par conséquent, le défi consiste à concevoir un système de prise de décision uniquement pour le robot pour qu'il soit capable de réaliser la tâche collaborative, tout en étant incertain quant aux comportements de l'utilisateur humain ou à ses objectifs.

La table 1 donne une vue synthétique des contributions que nous résumons ci-après. Pour la collaboration robot-robot, cette thèse fournit de nouvelles techniques pour résoudre les problèmes de décision multi-agents dans lesquels les agents n'ont que des observations partielles de l'environnement (Dec-POMDP). Plus spécifiquement, en s'inspirant de JESP [Nair et al., 2003], nous cherchons des solutions à l'équilibre de Nash en optimisant itérativement la politique de chaque agent jusqu'à ce qu'aucune amélioration ne puisse être apportée. De plus, JESP posede un inconvénient majeur : il ne peut résoudre que des problèmes à horizon fini car il utilise des politiques représentées par des arbres sur l'historique des actions-observations passées. Dans cette thèse, pour contourner ce problème, nous utilisons des contrôleurs à états finis pour représenter chaque politique, et proposons deux nouveaux algorithmes (Inf-JESP et MC-JESP) pour résoudre les problèmes à horizon infini. Ces deux algorithmes originaux diffèrent en ce que l'un utilise un modèle explicite tandis que l'autre utilise un modèle génératif (un simulateur de type boîte noire qui permet de modéliser de grands problèmes). Nous démontrons expérimentalement la validité de nos approches sur des problèmes de référence.

Pour la collaboration homme-robot, nous nous concentrons sur la prise de décision du robot et cherchons à calculer les politiques du robot robustes à des objectifs et comportements humains incertains. Contrairement à d'autres approches [Nikolaidis et al., 2017, Chen et al., 2018], qui nécessitent les connaissances d'experts ou des données collectées pour fournir un modèle humain sur lequel bâtir la stratégie du robot collaboratif, nous fournissons une approche capable de générer, automatiquement et en s'appuyant sur des modèles de prise de décision de Markov, un modèle de comportement humain incertain (une politique) pour chaque objectif humain possible et qui tienne compte du comportement possible du robot. Ensuite, pour dériver des politiques robustes pour le robot, nous formalisons le problème de prise de décision du robot (sous la forme d'un POMDP) en considérant que ce robot fait face à ces comportements humains incertains générés à l'étape précédente. Nous distinguons deux variantes de cette méthode de génération de stratégie robuste. Le premier algorithme est basé sur la connaissance explicite du modèle de la tâche de collaboration et sur le calcul d'une politique robuste du robot en estimant les comportements humains possibles. Cette méthode fonctionne hors ligne, nous calculons donc d'abord une politique de robot robuste et l'assignons au robot avant l'exécution réelle. Le second algorithme fonctionne en ligne, et un simple simulateur de type boîte noire est suffisant. À chaque pas de temps, le robot simule les évolutions possibles de la situation en considérant ce simulateur du monde et le comportement de l'agent, puis décide de son action à partir de ces simulations. Pour évaluer nos méthodes, un scénario de résolution d'une tâche collaborative a été conçu pour mener des expériences et présenter des résultats qualitatifs et quantitatifs.
<table><caption>TABLE 1 : Relations des différentes contributions</caption><thead><tr><th>Task Type</th><th>RRC</th><th>HRC</th></tr></thead><tbody><tr><td>Explicit Model</td><td>Inf-JESP</td><td>Robust Robot Planning - Offline</td></tr><tr><td>Generative Model</td><td>MC-JESP</td><td>Robust Robot Planning - Online</td></tr><tr><td>Research Interest</td><td>Optimality</td><td>Robustness</td></tr></tbody></table>

# 2 Contexte - Modèles de prise de décision markoviens

Cette thèse s'appuie principalement sur des modèles de prise de décision markoviens (POMDP et Dec-POMDP) pour dériver des politiques, grâce auxquelles l'agent prendra des décisions à partir d'observations provenant de l'état de l'environnement. Dans de tels modèles, la dynamique de l'environnement est modélisée par une fonction de transition probabiliste et une fonction d'observation probabiliste. La fonction de récompense définit l'objectif des agents, qui doivent maximiser l'espérance de la récompense cumulée pendant l'exécution de la tâche. La caractéristique clé des modèles de prise de décision markoviens, appelée *Propriété de Markov*, est que la distribution de probabilité sur l'état suivant ne dépend que de l'état actuel à l'instant *t* et des actions entreprises par les agents au même instant, et non de l'historique.

## 2.1 Processus de décision markoviens partiellement observables

Dans certains cas, l'information complète sur l'environnement n'est pas directement accessible, et l'agent ne dispose que d'une information partielle sur l'état courant [Åström, 1965]. Le modèle POMDP (Partially Observable Markov Decision Process) est conçu pour formaliser de tels problèmes de décision. Un POMDP est défini par un tuple $\langle S, A, \Omega, T, O, r, b_0 \rangle$ où :

* $S$ est un ensemble fini d'états;

* $A$ est un ensemble fini d'actions;

* $T: S \times A \times S \rightarrow \mathbb{R}$ désigne la fonction de transition ; $T(s, a, s')$ est la probabilité de transiter vers l'état suivant $s'$ à partir de l'état $s$ si l'action conjointe $a$ est exécutée;

* $r: S \times A \rightarrow \mathbb{R}$ est la fonction de récompense ; $r(s, a)$ donne la récompense immédiate pour l'exécution de l'action $a$ dans l'état $s$;

* $\Omega$ est un ensemble fini d'observation;

* $O(o, a, s') = Pr(o|s', a)$ est la fonction d'observation ; elle indique la probabilité de recevoir une observation $o$ étant donné le prochain état $s'$ atteint en effectuant l'action $a$;

* $b_0$ est une distribution initiale sur les états.

À chaque pas de temps $t$, l'exécution d'une action $a$ dans l'état $s$ induit une récompense $r(s, a)$ et conduit à l'état $s'$ avec une probabilité $T(s, a, s')$. L'agent reçoit ensuite une observation $o$ qui contient une information partielle ou bruitée sur l'état du système.

Dans les POMDP, puisque l'état réel n'est plus accessible par l'agent, toute l'information dont dispose l'agent au moment de l'exécution est l'historique action-observation (AOH), et ses décisions dépendront donc de cet historique. Un POMDP définit un problème consistant à
trouver une politique, c'est-à-dire une fonction de l'historique vers les actions, dont l'exécution maximise l'espérance des récompenses cumulées.

Cependant, dans les problèmes de prise de décision à long terme, le stockage de ces historiques est coûteux. Par conséquent, une autre approche classique consiste à utiliser une distribution de probabilité sur les états possibles, appelée état de croyance (ou croyance) b, pour condenser l'information sur l'état actuel du système. De plus, l'agent doit mettre à jour sa croyance après l'exécution d'une action a et la réception d'une observation o. Ce processus de mise à jour de la croyance est détaillé comme suit, où $b^{a,o}$ est une nouvelle croyance et $b^{a,o}(s')$ est la probabilité d'être dans l'état $s'$ dans cet état de croyance :

$$b^{a,o}(s') = \mathrm{Pr}(s'|o, a, b) = \frac{\mathrm{Pr}(s', o, a, b)}{\mathrm{Pr}(o, a, b)}, \quad (1)$$

$$= \frac{\mathrm{Pr}(o|s', a, b) \mathrm{Pr}(s'|a, b) \mathrm{Pr}(a, b)}{\sum_{s'} \sum_s \mathrm{Pr}(o, s, s', a, b)}, \quad (2)$$

$$= \frac{\mathrm{Pr}(o|s', a) \sum_s \mathrm{Pr}(s'|a, b, s) \mathrm{Pr}(s|a, b)}{\sum_{s'} \mathrm{Pr}(o|s', a) \sum_s \mathrm{Pr}(s'|a, b, s) \mathrm{Pr}(s|a, b)}, \quad (3)$$

$$= \frac{O(s', a, o) \sum_s T(s, a, s') b(s)}{\sum_{s'} O(s', a, o) \sum_s T(s, a, s') b(s)}. \quad (4)$$

La fonction de valeur optimale d'un POMDP est définie par l'équation d'optimalité de Bellman :

$$V^*(b) = \max_{a \in \mathcal{A}} \left[ r(b, a) + \gamma \sum_{o \in \Omega} \mathrm{Pr}(o|b, a) V^*(b') \right] \quad (5)$$

et une politique optimale est obtenue comme suit :

$$\pi^*(b) = \arg \max_{a \in \mathcal{A}} \left[ r(b, a) + \gamma \sum_{o \in \Omega} \mathrm{Pr}(o|b, a) V^*(b') \right], \quad (6)$$

où la fonction $r(b, a)$ spécifie l'espérance de récompense immédiate reçue lorsque l'action a est exécutée dans l'état de croyance b :

$$r(b, a) = \sum_{s \in \mathcal{S}} b(s) r(s, a),$$

et la fonction $\mathrm{Pr}(o|b, a)$ est la probabilité de recevoir une observation o après avoir exécuté l'action a dans l'état de croyance b :

$$\mathrm{Pr}(o|b, a) = \sum_{s' \in \mathcal{S}} O(s', a, o) \sum_{s \in \mathcal{S}} T(s, a, s') b(s).$$

Les solveurs POMDP les plus récents sont des algorithmes à base de points, notamment PBVI [Pineau et al., 2003], HSVI [Smith and Simmons, 2004] et SARSOP [Kurniawati et al., 2008]; et les méthodes fondées sur l'échantillonnage, telles que POMCP [Silver and Veness, 2010] et DESPOT [Somani et al., 2013]. Ces deux types de méthodes peuvent résoudre des problèmes POMDP complexes comportant des milliers d'états. Dans cette thèse, SARSOP et POMCP sont utilisés comme outils pour dériver efficacement des politiques POMDP.
## 2.2 Processus de décision markoviens décentralisés partiellement observables

Le formalisme Dec-POMDP est une extension du formalisme POMDP où plusieurs agents interagissent dans le même environnement et partagent la même fonction de récompense. Par rapport à un POMDP, un Dec-POMDP présente les caractéristiques suivantes :

* l'action (jointe) est décomposée en une action par agent,

* l'observation (jointe) est décomposée en une observation par agent, et

* la politique (jointe) est décomposée en des politiques individuelles séparables, une par agent.

Un Dec-POMDP avec $|\mathcal{I}|$ agents est représenté comme un tuple $M = \langle \mathcal{I}, S, A, \Omega, T, O, R, b_0, H, \gamma \rangle$ [Bernstein et al., 2002], où :

* $\mathcal{I} = \{1, \dots, |\mathcal{I}|\}$ est un ensemble fini d'agents;

* $S$ est un ensemble fini d'états;

* $A^i$ est l'ensemble fini des actions de l'agent $i$; $A = \times_i A^i$ est l'ensemble fini des actions conjointes;

* $\Omega^i$ est l'ensemble fini des observations de l'agent $i$; $\Omega = \times_i \Omega^i$ est l'ensemble fini des observations conjointes;

* $T: S \times A \times S \to \mathbb{R}$ désigne la fonction de transition; $T(s, a, s')$ est la probabilité de transiter vers l'état suivant $s'$ à partir de l'état $s$ si l'action conjointe $a$ est exécutée;

* $O: A \times S \times \Omega \to \mathbb{R}$ est la fonction d'observation; $O(a, s', o)$ est la probabilité d'observer $o$ si l'action conjointe $a$ est effectuée et l'état résultant est $s'$;

* $R: S \times A \to \mathbb{R}$ est la fonction de récompense; $R(s, a)$ donne la récompense immédiate pour l'exécution de l'action commune $a$ dans l'état $s$;

* $b_0$ est la distribution de probabilité initiale sur les états;

* $H \in \mathbb{N} \cup \{\infty\}$ est l' horizon de temps (éventuellement infini);

* $\gamma \in [0, 1)$ est le facteur d'actualisation, lequel définit l'escompte appliqué aux récompenses futures.

Chaque agent $i$ peut être équipé d'une politique $\pi^i$ qui fait correspondre ses historiques d'observation et d'action possibles à des actions. L'objectif est alors de trouver une politique jointe $\pi = \langle \pi^1, \dots, \pi^{|S|} \rangle$ qui maximise un critère de performance correspondant à la somme décomptée des récompenses :

$$V_H^\pi(b_0) \stackrel{\text{def}}{=} \mathbb{E} \left[ \sum_{t=0}^{H-1} \gamma^t r(S_t, A_t) \mid S_0 \sim b_0, \pi \right].$$
# 3 Travaux connexes

## 3.1 Prise de décision pour la collaboration robot-robot

L'un des principaux intérêts de cette thèse est la prise de décision multi-agent dans le contexte de la collaboration robot-robot. Nous utilisons le cadre Dec-POMDP pour modéliser les problèmes de collaboration robot-robot dans cette thèse car il s'agit du cadre, parmi les modèles de décision markoviens, où plusieurs agents optimisent un critère de performance partagé sous des incertitudes dues à la dynamique de l'environnement et aux observations partielles et bruitées des agents. Cependant, la résolution d'un Dec-POMDP est difficile. Même pour un Dec-POMDP à horizon fini, il a été prouvé que le processus de résolution est NEXP dans le pire des cas [Bernstein et al., 2002] et la résolution d'un Dec-POMDP à horizon infini est indécidable [Oliehoek and Amato, 2016, Madani et al., 2003]. Une différence essentielle par rapport aux POMDP est que l'utilité de la politique d'un agent n'est pas seulement liée à la dynamique de l'environnement, mais dépend également des interactions avec les autres agents et de leurs politiques. Dans cette thèse, nous classons les solveurs Dec-POMDP représentatifs comme suit :

* les algorithmes qui optimisent les politiques de tous les agents simultanément, incluant MAA* [Szer et al., 2005], FB-HSVI [Dibangoye et al., 2016], et PBVI-BB [MacDermed and Isbell, 2013]. MAA* cherche une solution optimale pour les Dec-POMDP à horizon fini en utilisant un schéma A* standard. FB-HSVI et PBVI-BB transforment un Dec-POMDP en un (PO)MDP et le résolvent avec les techniques POMDP. FB-HSVI et PBVI-BB peuvent tous deux être utilisés pour les Dec-POMDP à horizon infini, et FB-HSVI donne des solutions dont l'erreur est bornée à $ε$ près en approchant l'horizon infini à l'aide d'horizons finis. oSARSA [Dibangoye and Buffet, 2018] étend l'algorithme FB-HSVI au cadre des modèles génératifs où un Dec-POMDP explicite n'est pas disponible. Cependant, toutes ces méthodes doivent faire face à un problème d'explosion combinatoire lorsqu'elles sont confrontées à de grands problèmes.

* les algorithmes qui alternent entre les agents, incluant JESP [Nair et al., 2003] et Dec-BPI [Bernstein et al., 2005]. Ces algorithmes évitent cette explosion combinatoire en optimisant itérativement la politique de chaque agent en considérant que les politiques des autres sont fixées. Mais l'inconvénient associé est que ces méthodes ne peuvent trouver que des équilibres de Nash au mieux. Dans cette catégorie, JESP est limité aux horizons finis, et Dec-BPI peut être utilisé pour les Dec-POMDP à horizon infini avec n'importe quelle distribution sur les états de départ.

* les algorithmes fondés sur des techniques de type Expectation-Maximisation (EM) et qui transforment le problème de planification Dec-POMDP en un problème d'inférence probabiliste [Kumar and Zilberstein, 2010, Kumar et al., 2011, Pajarinen and Peltonen, 2011]. La politique de chaque agent est représentée par un FSC, et ses paramètres sont optimisés à l'aide de l'algorithme EM. Les méthodes basées sur EM peuvent être utilisées pour des Dec-POMDP à horizon infini, et une adaptation des approches de type Monte-Carlo étend leur utilisation à des modèles génératifs. Cependant, les méthodes EM ne garantissent que la convergence vers des optima locaux ou, pire encore, vers des points selle.

À notre connaissance, le schéma JESP n'a été introduit ni dans un cadre à horizon infini ni dans un cadre basé sur un simulateur. Par conséquent, dans cette thèse, deux de nos principales contributions (voir chapitre 4) consistent à : 1. proposer un premier algorithme qui étend l'approche JESP au cadre de l'horizon infini appelé Inf-JESP ; 2. proposer une extension de Inf-JESP qui fonctionne avec des modèles génératifs (MC-JESP).
## 3.2 Prise de décision pour la collaboration homme-robot

Dans le contexte de la collaboration homme-robot (HRC), contrairement à la collaboration robot-robot, le cadre Dec-POMDP ne peut pas être utilisé directement car le partenaire humain peut se comporter différemment des politiques Dec-POMDP calculées, et ce pour plusieurs raisons :

* les politiques calculées sont trop complexes pour que l'humain puisse les apprendre;

* l'humain veut conserver son autonomie et ne veut pas suivre aveuglément une politique pré-calculée.

De plus, contrairement à un Dec-POMDP, où tous les agents optimisent une fonction objectif partagée, les objectifs réels des humains dans une tâche HRC peuvent être cachés aux robots. En raison de ces facteurs, dans une tâche HRC, le robot doit tenir compte de l'incertitude sur les objectifs et les comportements humains. Dans cette thèse, inspiré par le travail de Tabrez et al. [2020], nous nous fondons sur le concept de *modèle mental* et sur les catégories qu'il décrit. Théoriquement, en HRC, un robot pourrait posséder un modèle mental d'un humain (qui peut différer des comportements humains réels) parmi l'un des types suivants :

* *Modèle mental de premier ordre (1oMM)* : le robot considère que l'humain se comporte de manière indépendante et ne tient pas compte des actions possibles du robot;

* *modèle mental de second ordre (2oMM)* : le robot considère que l'humain tient compte du robot, ce qui induit une forme de modélisation récursive jusqu'à une certaine profondeur;

* *Modèle mental partagé (SMM)* : un SMM suppose que tous les agents de l'équipe ont des attentes communes et raisonnent donc de la même manière, ce qui assure une coordination optimale.

Bien entendu, cette catégorisation s'applique symétriquement à la façon dont l'humain modélise le robot. Nous nous concentrons ici sur les problèmes de dynamique stochastique et d'observabilité partielle, ce qui nous amène à considérer des modèles de décision markoviens. Dans ce contexte, un 1oMM correspond typiquement à un POMDP où l'objectif est de trouver la politique d'un agent d'intérêt, tandis que la politique (connue a priori) de l'autre agent fait partie de la dynamique du système. Par exemple, un "POMDP robot" supposant un comportement humain connu est résolu dans [Unhelkar et al., 2020, Nikolaidis et al., 2017, Chen et al., 2018, 2020]. Les SMM peuvent être formalisés comme des POMDP décentralisés (Dec-POMDP), typiquement utilisés pour optimiser la politique jointe d'une équipe d'agents (avec une fonction de récompense commune). CIRL [Hadfield-Menell et al., 2016] peut être considéré comme un cas particulier où l'humain a une observabilité totale et où le robot n'a qu'une fonction de récompense. L'observabilité de l'état du monde est complète et la seule variable cachée du robot correspond à l'objectif réel de l'homme (sa fonction de récompense), ce qui permet d'utiliser techniques de résolution dédiées proches de la résolution d'un POMDP. Pour leur part, les 2oMM peuvent être formalisés en tant que POMDP interactifs (I-POMDP) [Doshi and Gmytrasiewicz, 2005], où les agents se modélisent les uns les autres de manière imbriquée.

Les 1oMM échoueront dans de nombreuses tâches nécessitant un comportement collaboratif explicite de la part de l'humain, et l'hypothèse principale des SMM est généralement trop forte lorsque des robots et des humains collaborent ensemble. Nous proposons donc d'équiper le robot d'un 2oMM de l'humain. Notre approche de la planification robuste des robots pourrait être formalisée comme un I-POMDP, ce que nous évitons principalement pour simplifier les notations. Cependant, l'utilisation d'un 2oMM doit faire face au paradoxe de l'œuf et de la poule car dériver
le comportement humain requis implique de raisonner sur le comportement du robot que nous essayons de dériver en premier lieu. Ceci est vrai par exemple dans le cas 1. de politiques écrites manuellement et devant décrire le comportement humain [Unhelkar et al., 2020, Nikolaidis et al., 2017], pour lesquelles le concepteur doit raisonner sur le comportement du robot et les réactions de l'humain ; 2. de politiques humaines ou de récompenses humaines apprises (par IRL par exemple) [Russell, 1998, Ng and Russell, 2000], qui nécessitent un robot collaboratif en premier lieu pour démontrer un comportement collaboratif ; ou 3. de politiques humaines planifiées qui nécessitent de disposer d'un modèle de l'environnement incluant le comportement du robot.

Dans cette thèse, nous générons des comportements humains plausibles qui serviront de
modèle mental du robot à travers la planification, et abordons le problème de la poule et de
l'œuf en se demandant quel serait le comportement de l'humain s'il pouvait aussi contrôler le
robot et en supposant ainsi temporairement que l'humain et le robot partagent leurs observations,
ce qui revient, pour le robot, à considérer que l'humain adopte un SMM particulier.

4 Contributions

4.1 Recherche d'un équilibre de Nash dans un problème multi-agent à horizon infini

Dans cette thèse, nous modélisons les tâches RRC comme des Dec-POMDP, et nous nous sommes intéressés à la recherche d'une solution correspondant à un équilibre de Nash pour lequel la politique de chaque agent constitue la meilleure réponse aux politiques des autres agents. A cette fin, nous proposons de résoudre les Dec-POMDP par une approche JESP (Joint Equilibrium-Based Search for Policies) [Nair et al., 2003], laquelle recherche des solutions en équilibre de Nash en optimisant itérativement la politique de chaque agent tout en fixant les politiques des autres agents, et ce, jusqu'à convergence. Cependant, JESP présente deux faiblesses :

1. dans JESP, les politiques sont représentées par des arbres; par conséquent, cet algorithme ne traite que les Dec-POMDP à horizon fini;

2. les solutions d'équilibre de Nash obtenues par JESP sont des optima locaux mais pas globaux.

Cette thèse propose deux nouveaux algorithmes qui répondent au premier inconvénient de JESP en l'étendant au cadre de l'horizon infini. Pour ce faire, nos méthodes ne s'appuient pas sur des arbres de politique mais sur des contrôleurs à états finis (FSC), lesquels représentent des politiques à horizon infini, et nous essayons de contrôler leur taille.

Notre premier algorithme, appelé *Infinite-Horizon JESP* (Inf-JESP), résout les Dec-POMDP avec un modèle explicite du Dec-POMDP correspondant au problème collaboratif à résoudre. L’algorithme principal de Inf-JESP optimise de manière itérative la politique d’un agent représentée sous la forme d’un FSC tout en fixant les FSC des autres agents jusqu’à ce qu’aucune amélioration ne soit possible. Plus précisément, à chaque itération, nous combinons les politiques FSC des autres agents avec un Dec-POMDP pour générer un POMDP avec un espace d’état étendu. Chaque état étendu $e^t \in \mathcal{E}$ contient ainsi :

• $s^t$, l'état actuel du Dec-POMDP représentant le problème collaboratif à résoudre ;

* $n_{i \neq i}^t \equiv \langle n_1^t, \dots, n_{i-1}^t, n_{i+1}^t, \dots, n_n^t \rangle$, les nœuds internes des automates des $|\mathcal{I}| - 1$ autres agents ($\text{agents } (\text{agents} \neq i)$ à l'instant $t$, et ;
* $o_i^t$, l'observation actuelle de l'agent i.

Nous avons donc $\mathcal{E} \stackrel{\text{def}}{=} \mathcal{S} \times N_{\neq i} \times \Omega_i$. Étant donné une action $a_i^t$, l'état de ce POMDP $e^t \equiv \langle s^t, n_{\neq i}^t, o_i^t \rangle$ évolue selon les étapes suivantes :

1. chaque agent $j \neq i$ choisit son action $a_j$ en fonction de son automate et de son nœud interne actuel;

2. $s^t$ évolue vers $s^{t+1}$ selon $T$ et l'action jointe sélectionnée par les agents $a^t = \langle a_i^t, a_{\neq i}^t \rangle$; et

3. les nœuds internes des automates des agents $j$ ($i$ inclus) évoluent simultanément selon les observations $o_j^{t+1}$ reçues, inférées à partir de $s^{t+1}$ et de l'action jointe $a^t$; ces observations peuvent ne pas être indépendantes les unes des autres, de telle sorte que les automates peuvent évoluer de manière dépendante les uns des autres.

Le choix de $e^t$ comme état étendu fait que ce système correspond effectivement à un POMDP du fait des propriétés suivantes :

* cela induit un processus décisionnel de Markov contrôlé par l'action de l'agent $i$ (cf. la dynamique ci-dessous);

* l'observation $o_i^t$ ne dépend que de $a_i^t$ et de $e^{t+1}$; et

* la fonction de récompense ne dépend que de $e^t$ et de $a_i^t$.

En effet, dériver les fonctions de transition, d'observation et de récompenses de ce POMDP conduit à :

$$ T_e(e^t, a_i^t, e^{t+1}) = \mathrm{Pr}(e^{t+1}|e^t, a_i^t) = \sum_{o_{\neq i}^{t+1}} T(s^t, \langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}) \cdot \eta_{\neq i}(n_{\neq i}^t, o_{\neq i}^{t+1}, n_{\neq i}^{t+1}) $$

$$ \cdot O(s^{t+1}, \langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, \langle o_{\neq i}^{t+1}, o_i^{t+1} \rangle), $$

$$ O_e(a_i^t, e_i^{t+1}, o_i^{t+1}) = \mathrm{Pr}(o_i^{t+1}|a_i^t, e_i^{t+1}) = \mathrm{Pr}(o_i^{t+1}|a_i^t, \langle s^{t+1}, n_{\neq i}^{t+1}, \tilde{o}_i^{t+1} \rangle) $$

$$ = \mathbf{1}_{o_i^{t+1}=\tilde{o}_i^{t+1}}, $$

$$ r_e(e^t, a_i^t) = r(s^t, a_i^t, \psi_{\neq i}(n_{\neq i}^t)), $$

où $\eta_{\neq i}(n_{\neq i}^t, o_{\neq i}^{t+1}, n_{\neq i}^{t+1}) = \prod_{j \neq i} \eta(n_j^t, \tilde{o}_j^{t+1}, n_j^{t+1})$ and $\psi_{\neq i}(n_{\neq i}^t) = a_{\neq i}^t$. Ensuite, pour tirer parti des solveurs POMDP modernes à base de points, nous proposons un algorithme (voir algorithme 7) pour générer l'automate à états fini d'un agent à partir d'un ensemble d'α-vecteurs. De plus, des méthodes d'initialisation heuristiques sont également fournies pour donner de bonnes politiques de départ.

## 4.2 Planification robuste des robots pour la collaboration homme-robot

Cette thèse aborde le problème de l'incertitude sur les objectifs humains et les comportements induits dans la collaboration homme-robot en observabilité partielle. La contribution peut être principalement divisée en trois parties :
* Nous discutons des avantages et des inconvénients des différents modèles mentaux dans les applications de collaboration homme-robot. Dans cette thèse, nous choisissons d'équiper le robot d'un modèle mental du second ordre (2oMM) pour modéliser le partenaire humain. Nous discutons du paradoxe de la poule et de l'œuf soulevé par l'utilisation de 2oMM imbriqués et fournissons deux méthodes pour surmonter cet obstacle. La première méthode génère automatiquement un FSC humain, en agrégeant plusieurs comportements possibles pour un objectif humain donné (voir algorithme 14). La deuxième méthode fournit, en ligne, une distribution de probabilité des actions humaines étant donné un objectif humain à partir d'un planificateur fondé sur des techniques d'échantillonnage (voir algorithme 16). Pour ces deux méthodes, les paramètres peuvent être réglés pour ajuster la diversité des comportements humains générés par une fonction softmax;

* Nous proposons un algorithme de planification de robot robuste hors ligne dans la section 6.1.2, lequel repose sur un modèle POMDP explicite avec des incertitudes sur l'objectif et le comportement de l'humain. Nous détaillons formellement comment construire ce POMDP, centré sur le point de vue du robot, à partir des modèles de tâches (Dec-POMDP) et d'une distribution sur les politiques stochastiques humaines (FSCs), une par objectif possible. Une politique d'un robot robuste est ensuite obtenue hors ligne en résolvant ce POMDP;

* Nous proposons également un algorithme de planification en ligne de robot robuste pour les tâches HRC (voir algorithme 17). Par rapport à la méthode hors ligne qui repose sur un POMDP explicite, notre approche en ligne ne nécessite qu'un modèle génératif et peut donc s'adapter à des problèmes de grande taille. Nous détaillons le processus de construction d'un modèle génératif POMDP valide pour le robot avec un espace d'état étendu qui inclut l'état interne de l'humain. Nous fournissons également un algorithme de planification de robot en ligne basé sur POMCP. En utilisant ce modèle génératif POMDP, le robot planifie ses actions à chaque pas de temps en estimant, en ligne, l'objectif réel de l'humain et ses actions futures possibles.

Grâce à des expériences menées avec des humains synthétiques et réels, nous démontrons que nos approches sont robustes aux comportements humains incertains avec différents objectifs. Nous pensons que ce travail est important pour les contextes de collaboration où le robot et l'humain doivent raisonner sur leurs actions possibles mutuelles, et où la prise en compte de politiques humaines myopes ou déterministes est insuffisante pour générer des politiques robustes pour le robot. De plus, notre approche ne nécessite qu'un Dec-POMDP décrivant la tâche de collaboration homme-robot, sans avoir besoin d'un comportement humain préalable. Cela rend notre méthode générique pour aborder divers problèmes de collaboration homme-robot.

# 5 Conclusion

Dans cette thèse, nous étudions les questions de prise de décision des robots dans deux domaines de recherche, la collaboration robot-robot (RRC) et la collaboration homme-robot (HRC).

Dans la RRC, plusieurs robots sont censés travailler en collaboration pour réaliser une tâche. Plus précisément, cette thèse se concentre sur les problèmes de RRC où chaque robot ne dispose que d'observations partielles dans un environnement incertain. En s'appuyant sur les modèles de prise de décision markoviens, nous utilisons le cadre Dec-POMDP pour modéliser de tels problèmes RRC et proposons deux nouveaux algorithmes (Inf-JESP et MC-JESP) pour résoudre les Dec-POMDP. Nous observons, à travers des expériences avec des problèmes de référence de
l'état de l'art, que Inf-JESP et MC-JESP sont compétitifs par rapport aux solveurs Dec-POMDP existants. MC-JESP surpasse même certains solveurs qui reposent sur des modèles explicites. De plus, grâce à ces recherches menées pour résoudre les Dec-POMDP à horizon infini pour RRC, nous fournissons des outils pour générer un POMDP à partir duquel construire la meilleure réponse d'un agent donné aux politiques supposées fixes et connues des autres agents. Ceci constitue une base importante pour nos contributions en HRC.

Dans le cadre de la HRC, nous nous intéressons aux scénarios où un humain et un robot doivent coordonner leurs comportements pour réaliser une tâche. Dans ce contexte, désormais, seul un agent, le robot, peut être contrôlé, tandis que l'humain peut avoir des objectifs et des comportements incertains. Dans ce cas, nous proposons deux nouveaux algorithmes pour dériver des politiques robustes pour les robots en raisonnant uniquement sur le descriptif de la tâche collaborative et sans nécessiter d'information préalable sur le comportement de l'humain. Nous montrons que nos approches sont robustes à des objectifs humains incertains et des comportements induits par ces objectifs. Nous avons observé expérimentalement que cette approche fournit aussi des décisions adaptées lorsque le robot doit interagir, en simulation, avec des sujets humains.

Dans le futur, nous aimerions étendre ces travaux dans différentes dimensions entre autres en abordant des problèmes continus et en considérant explicitement les durées des actions, ce qui permettrait d'appliquer nos contributions à des scénarios réels impliquant de vrais robots.