# Plan Generation for Multi-Robot Missions Requiring Active Operator Involvement

Émile Siboulet, Arthur Bit-Monnot, Marc-Emmanuel Coupvent des Graviers,
Jacques Yelloz, Christophe Guettier, Simon Lacroix

► To cite this version:

Émile Siboulet, Arthur Bit-Monnot, Marc-Emmanuel Coupvent des Graviers, Jacques Yelloz, Christophe Guettier, et al.. Plan Generation for Multi-Robot Missions Requiring Active Operator Involvement. ICAPS'24 Workshop on Planning and Robotics (PlanRob), 2024. hal-04587729

HAL Id: hal-04587729

https://laas.hal.science/hal-04587729

Submitted on 24 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Plan Generation for Multi-Robot Missions Requiring Active Operator Involvement

Émile Siboulet, Arthur Bit-Monnot, Marc-Emmanuel Coupvent des Graviers,
Jacques Yelloz, Christophe Guettier, Simon Lacroix

► To cite this version:

Émile Siboulet, Arthur Bit-Monnot, Marc-Emmanuel Coupvent des Graviers, Jacques Yelloz, Christophe Guettier, et al.. Plan Generation for Multi-Robot Missions Requiring Active Operator Involvement. ICAPS'24 Workshop on Planning and Robotics (PlanRob), 2024. hal-04587729

HAL Id: hal-04587729

https://laas.hal.science/hal-04587729v1

Submitted on 24 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Plan Generation for Multi-Robot Missions
Requiring Active Operator Involvement

Emile Siboulet,¹² Arthur Bit-Monnot,¹ Marc-Emmanuel Coupvent des Graviers,² Jacques Yelloz,³ Christophe Guettier,² Simon Lacroix¹

¹ LAAS-CNRS, Université de Toulouse, CNRS, INSA, Toulouse, France

{emile.siboulet, arthur.bit-monnot, simon.lacroix}@laas.fr

² Safran Electronics & Defense, Massy, France

{emile.siboulet, marc-emmanuel.des-graviers, christophe.guettier}@safrangroup.com

³ Safran Tech, Châteaufort, France

jacques.yelloz@safrangroup.com

## Abstract

This paper extends a constraint-based planning approach to deal with mixed-initiative for complex multi-robot missions. Operators in the loop with multi-robot systems may have to interact intensively: explicitly considering their cognitive load while planning the missions is a critical problem to address. The purpose of this work is to take into account at mission planning time the operator capacity to supervise the mission execution, to ensure efficient and safe operations. We introduce new mental load related metrics in an automatic constraint-based planner. The optimization of these metrics yields better quality plans for the operators to supervise and interact during execution. The planning feasibility and performances are evaluated on realistic scenarios.

systems offer speed, consistency, and the ability to efficiently consider complex constrained situations or large volumes of information.

Beyond planning, the principles of mixed-initiative also apply to mission supervision and execution (Dixon, Wickens, and Chang 2005; Cummings and Guerlain 2007; Wilkins, Lee, and Berry 2003). Planning aims at harnessing the complementary capabilities of humans and robots, thereby enhancing performance, efficiency and safety in the proper achievement of the mission. It primarily allows to quickly repair jobs without jeopardizing the overall plan, and also to handle collaborative human/robot plan repair or even replanning when needed.

For both planning and supervision activities, a key aspect in mixed-initiative approaches is to endow the operator with the ability to properly interact with the planner and the robots. Apart from adequate ergonomics, this calls for information sharing, control algorithms, and interaction protocols. In addition, and especially for mixed-initiative execution supervision, the operator must be in a mental state that allows its intervention.

Two important notions come into play: the Situation Awareness (SA) and the NASA Task Load index (NASA-TLX) (Ruff, Narayanan, and Draper 2002). SA involves understanding the current state of the environment and the robots, interpreting data to project future states, so as to make decisions that align with the robots' capacities and goals. The NASA-TLX is a widely used workload assessment tool that evaluates the perceived workload experienced by individuals performing tasks. It provides a multidimensional rating system that encompasses different aspects of workload to capture a comprehensive view of the task demands placed on an individual. These dimensions include mental demand, physical demand, temporal demand, performance, effort and frustration. The NASA-TLX is a valuable tool in the development and evaluation of mixed-initiative systems, offering insights into how automated systems impact human operators. It should be noted that the analysis of the mental load of an operator on the field is an active research topic in the cognitive models community (Kokar and

## Introduction

### Mixed-Initiative Planning and Acting

Mixed-initiative, as described by Jiang and Arkin (2015), refers to collaborative frameworks in which both human operators and robotic agents possess the autonomy to initiate, modify, or discontinue tasks based on a dynamic assessment of the situational context. It improves operational efficiency, ensuring that both human and robotic agents can proactively contribute to achieving common objectives. For instance, mixed-initiative can be used with purely reactive systems that simply suggest to the user the best choice to make. It can also be part of a deliberative approach to mission planning and execution.

In planning activities, mixed-initiative refers to an approach in which humans and automated planning systems contribute actively to the creation or modification of plans. Examples are the SHERPA project (Bevacqua et al. 2015), where an operator finds plans with the help of an exploration system to search for missing people in the mountains, or in the context of Mars exploration (Bresina et al. 2004). Mixed-initiative planning leverages the strengths of humans and computers: humans provide contextual understanding, creative problem-solving and flexibility, while automated
# Plan Generation for Multi-Robot Missions
Requiring Active Operator Involvement

Emile Siboulet,¹² Arthur Bit-Monnot,¹ Marc-Emmanuel Coupvent des Graviers,² Jacques Yelloz,³ Christophe Guettier,² Simon Lacroix¹

¹ LAAS-CNRS, Université de Toulouse, CNRS, INSA, Toulouse, France

{emile.siboulet, arthur.bit-monnot, simon.lacroix}@laas.fr

² Safran Electronics & Defense, Massy, France

{emile.siboulet, marc-emmanuel.des-graviers, christophe.guettier}@safrangroup.com

³ Safran Tech, Châteaufort, France

jacques.yelloz@safrangroup.com

## Abstract

This paper extends a constraint-based planning approach to deal with mixed-initiative for complex multi-robot missions. Operators in the loop with multi-robot systems may have to interact intensively: explicitly considering their cognitive load while planning the missions is a critical problem to address. The purpose of this work is to take into account at mission planning time the operator capacity to supervise the mission execution, to ensure efficient and safe operations. We introduce new mental load related metrics in an automatic constraint-based planner. The optimization of these metrics yields better quality plans for the operators to supervise and interact during execution. The planning feasibility and performances are evaluated on realistic scenarios.

systems offer speed, consistency, and the ability to efficiently consider complex constrained situations or large volumes of information.

Beyond planning, the principles of mixed-initiative also apply to mission supervision and execution (Dixon, Wickens, and Chang 2005; Cummings and Guerlain 2007; Wilkins, Lee, and Berry 2003). Planning aims at harnessing the complementary capabilities of humans and robots, thereby enhancing performance, efficiency and safety in the proper achievement of the mission. It primarily allows to quickly repair jobs without jeopardizing the overall plan, and also to handle collaborative human/robot plan repair or even replanning when needed.

For both planning and supervision activities, a key aspect in mixed-initiative approaches is to endow the operator with the ability to properly interact with the planner and the robots. Apart from adequate ergonomics, this calls for information sharing, control algorithms, and interaction protocols. In addition, and especially for mixed-initiative execution supervision, the operator must be in a mental state that allows its intervention.

Two important notions come into play: the Situation Awareness (SA) and the NASA Task Load index (NASA-TLX) (Ruff, Narayanan, and Draper 2002). SA involves understanding the current state of the environment and the robots, interpreting data to project future states, so as to make decisions that align with the robots' capacities and goals. The NASA-TLX is a widely used workload assessment tool that evaluates the perceived workload experienced by individuals performing tasks. It provides a multidimensional rating system that encompasses different aspects of workload to capture a comprehensive view of the task demands placed on an individual. These dimensions include mental demand, physical demand, temporal demand, performance, effort and frustration. The NASA-TLX is a valuable tool in the development and evaluation of mixed-initiative systems, offering insights into how automated systems impact human operators. It should be noted that the analysis of the mental load of an operator on the field is an active research topic in the cognitive models community (Kokar and

## Introduction

### Mixed-Initiative Planning and Acting

Mixed-initiative, as described by Jiang and Arkin (2015), refers to collaborative frameworks in which both human operators and robotic agents possess the autonomy to initiate, modify, or discontinue tasks based on a dynamic assessment of the situational context. It improves operational efficiency, ensuring that both human and robotic agents can proactively contribute to achieving common objectives. For instance, mixed-initiative can be used with purely reactive systems that simply suggest to the user the best choice to make. It can also be part of a deliberative approach to mission planning and execution.

In planning activities, mixed-initiative refers to an approach in which humans and automated planning systems contribute actively to the creation or modification of plans. Examples are the SHERPA project (Bevacqua et al. 2015), where an operator finds plans with the help of an exploration system to search for missing people in the mountains, or in the context of Mars exploration (Bresina et al. 2004). Mixed-initiative planning leverages the strengths of humans and computers: humans provide contextual understanding, creative problem-solving and flexibility, while automated
Endsley 2012; Hollands, Spivak, and Kramkowski 2019; Endsley, Garland et al. 2000). These are still to be adapted to a decision support context such as ours.

## Contributions

In this paper, we propose a method to plan complex multi-robot missions that explicitly consider the operator constraints, aiming at making possible the mixed initiative supervision of the plan execution. This is done by introducing operator-related metrics that produce plans which do not overwhelm the operator during execution monitoring. Considered missions involve a team of aerial and ground robots that must ensure a progression throughout a terrain structured as a navigation graph. A mission involves the accomplishment of specific tasks at a number of nodes, some of which are constrained relative to each other. Main contributions of the paper are

* The definition of the mission with a Constraint Satisfaction Problem (CSP) based planning models,

* the introduction of metrics to quantify the operator's operational workload and information gain, and

* the evaluation of the method on a realistic mission use case.

## Outline

In the next section, we take a brief look at the literature on methods of interaction between an operator and a team of robots, and the ways in which they can be quantified. The two following sections state the considered problem, formalize it and present the operational planning model. Metrics of operator mental load and informational gain are then introduced, and mission planning results are presented, on a simple use case first, and then for a full-scale scenario.

# Problem Statement

## General Problem

We address the challenge of planning missions for heterogeneous robot teams tasked with traversing a designated area under specific constraints and auxiliary objectives. The scenario involves a group of robots operating autonomously in a specified zone, supported by a remote operator situated nearby to the area. The operator possesses the capability to teleoperate the robots. He is familiar with these kinds of missions and provides strategic support during the mission. The heterogeneity of the robot team is a critical aspect, as certain tasks within the mission can only be executed by specific robots, necessitating task allocation among the team members.

The exploration zone presents its own set of contingencies related to terrain, which may obstruct the execution of a pre-defined plan and require operator advice to achieve mission objectives. Furthermore, the robots face the possibility of losing functionality either through the depletion of resources or mechanical failures, introducing a layer of unpredictability that the mission planning process must account for. Such deviations from the initial plan can be detected by an experienced operator, who might take extra steps to

modify the plan before problems arise. While telecommunication issues are present in these scenarios, they are not deemed significant enough to impede the ability to teleoperate the robots effectively and will not be considered into the planning model.

A pivotal element of the mission is the execution of durable tasks, which may necessitate the completion of prerequisite tasks or the simultaneous execution of multiple tasks. Another objective of the mission is to respect some temporal exclusion in designated areas, in which certain robots are expected to be outside for a given time.

## Role of the Operator

During the mission, the operator's responsibilities encompass the verification of task completion, the maintenance of a comprehensive understanding of the mission's progress, and ensuring the safety of all involved agents. This multifaceted role requires the operator to continuously monitor task execution while ensuring they are performed accurately and efficiently.

In situations where multiple task execution paths are available, the operator must take informed decisions, prioritizing the safety of the agents while considering the mission's objectives and the current situational context. To be able to take the proper decisions, he must have a high level of situational awareness to adapt to dynamic mission environments. He must therefore possess a holistic view of the mission's advancement, integrating information from various sources to form a coherent picture of the current state and foresee potential issues that may arise. Hence, besides the consideration of the operator's mental load during the mission planning process, ensuring he is aware of the situation to be able to take decisions is also an important concern.

## Problem Formalization

Let us consider a set of *nr* robots navigating directed graphs, each denoted by $G_i = (V, E_i)$, where *i* serves as the index for individual robots. In this context, $e_{ik} \in E_i$ represents the *k*-th edge available to robot *i*, with $v, v' \in V^2$ forming edges as $e_{ik} = (v, v')$. The traversal time for the *k*-th edge by robot *i* is denoted by a constant $Tt_{ik}$.

Each robot *i* have specific entry and exit points associated with respective vertices.

Let *v*, *v'* and *v''* denote respectively entry, exit and any other random vertex. *v* and *v'* are indirectly identified by a variable $B_{iv}$ defined for every vertex as: $B_{iv} = 1, B_{iv'} = -1$ and $B_{iv''} = 0$.

We assume a discrete time representation as natural numbers, where 0 is the initial time and $tmax$ denotes the planning horizon, at which all robots must have reached their exit nodes.

The mission incorporates a total of *nt* tasks, each needing to be performed at a specific position $T_m \in V$ where *m* indexes each task. Each task duration is specified by $Dt_m \in [0, tmax]$. Each task is associated with a valid initiation window, denoted as $Wt_m \subseteq [0, tmax]$, ensuring that tasks are started within specified time slots. Additionally, particu-
Endsley 2012; Hollands, Spivak, and Kramkowski 2019; Endsley, Garland et al. 2000). These are still to be adapted to a decision support context such as ours.

## Contributions

In this paper, we propose a method to plan complex multi-robot missions that explicitly consider the operator constraints, aiming at making possible the mixed initiative supervision of the plan execution. This is done by introducing operator-related metrics that produce plans which do not overwhelm the operator during execution monitoring. Considered missions involve a team of aerial and ground robots that must ensure a progression throughout a terrain structured as a navigation graph. A mission involves the accomplishment of specific tasks at a number of nodes, some of which are constrained relative to each other. Main contributions of the paper are

* The definition of the mission with a Constraint Satisfaction Problem (CSP) based planning models,

* the introduction of metrics to quantify the operator's operational workload and information gain, and

* the evaluation of the method on a realistic mission use case.

## Outline

In the next section, we take a brief look at the literature on methods of interaction between an operator and a team of robots, and the ways in which they can be quantified. The two following sections state the considered problem, formalize it and present the operational planning model. Metrics of operator mental load and informational gain are then introduced, and mission planning results are presented, on a simple use case first, and then for a full-scale scenario.

# Problem Statement

## General Problem

We address the challenge of planning missions for heterogeneous robot teams tasked with traversing a designated area under specific constraints and auxiliary objectives. The scenario involves a group of robots operating autonomously in a specified zone, supported by a remote operator situated nearby to the area. The operator possesses the capability to teleoperate the robots. He is familiar with these kinds of missions and provides strategic support during the mission. The heterogeneity of the robot team is a critical aspect, as certain tasks within the mission can only be executed by specific robots, necessitating task allocation among the team members.

The exploration zone presents its own set of contingencies related to terrain, which may obstruct the execution of a pre-defined plan and require operator advice to achieve mission objectives. Furthermore, the robots face the possibility of losing functionality either through the depletion of resources or mechanical failures, introducing a layer of unpredictability that the mission planning process must account for. Such deviations from the initial plan can be detected by an experienced operator, who might take extra steps to

modify the plan before problems arise. While telecommunication issues are present in these scenarios, they are not deemed significant enough to impede the ability to teleoperate the robots effectively and will not be considered into the planning model.

A pivotal element of the mission is the execution of durable tasks, which may necessitate the completion of prerequisite tasks or the simultaneous execution of multiple tasks. Another objective of the mission is to respect some temporal exclusion in designated areas, in which certain robots are expected to be outside for a given time.

## Role of the Operator

During the mission, the operator's responsibilities encompass the verification of task completion, the maintenance of a comprehensive understanding of the mission's progress, and ensuring the safety of all involved agents. This multifaceted role requires the operator to continuously monitor task execution while ensuring they are performed accurately and efficiently.

In situations where multiple task execution paths are available, the operator must take informed decisions, prioritizing the safety of the agents while considering the mission's objectives and the current situational context. To be able to take the proper decisions, he must have a high level of situational awareness to adapt to dynamic mission environments. He must therefore possess a holistic view of the mission's advancement, integrating information from various sources to form a coherent picture of the current state and foresee potential issues that may arise. Hence, besides the consideration of the operator's mental load during the mission planning process, ensuring he is aware of the situation to be able to take decisions is also an important concern.

## Problem Formalization

Let us consider a set of *nr* robots navigating directed graphs, each denoted by $G_i = (V, E_i)$, where *i* serves as the index for individual robots. In this context, $e_{ik} \in E_i$ represents the *k*-th edge available to robot *i*, with $v, v' \in V^2$ forming edges as $e_{ik} = (v, v')$. The traversal time for the *k*-th edge by robot *i* is denoted by a constant $Tt_{ik}$.

Each robot *i* have specific entry and exit points associated with respective vertices.

Let *v*, *v'* and *v''* denote respectively entry, exit and any other random vertex. *v* and *v'* are indirectly identified by a variable $B_{iv}$ defined for every vertex as: $B_{iv} = 1, B_{iv'} = -1$ and $B_{iv''} = 0$.

We assume a discrete time representation as natural numbers, where 0 is the initial time and $tmax$ denotes the planning horizon, at which all robots must have reached their exit nodes.

The mission incorporates a total of *nt* tasks, each needing to be performed at a specific position $T_m \in V$ where *m* indexes each task. Each task duration is specified by $Dt_m \in [0, tmax]$. Each task is associated with a valid initiation window, denoted as $Wt_m \subseteq [0, tmax]$, ensuring that tasks are started within specified time slots. Additionally, particu-
lar tasks are required to be executed by specific robots, these assignments are detailed in the set $At_m \subseteq [1, nr]$.

In parallel, the mission features nra temporal restrictions, represented as $Ar_n \in V$, where n indexes each temporal exclusion. The implication of a temporal exclusion varies, impacting only a subset of robots. Robots that must respect temporal exclusions are identified in the set $Mar_n \subseteq [1, nr]$ for the n-th area. The position must not be occupied by robots that have to comply with the temporal exclusion during a time window $War_n \subseteq [0, tmax]$.

Coordination between task execution is categorized into two types to streamline the framework, focusing on pairwise interactions. The sets S and P encompass action pairs that require synchronous and successive execution, respectively.

Furthermore, the mission strategy includes deploying agents for recognition. The corresponding boolean constant $Af_{iv}$ is true iff the robot i is allowed to arrive first at position v.

The assignment must be carried out within a predefined timeframe, but the plan quality will be assessed in relation to the speed of its planned execution.

## Planning Problem Formulation

In this section, we propose an encoding of the problem into a CSP formalism with finite-domain integer variables, inspired by the one of Guettier (2007) on related progression problems. This approach is particularly efficient for producing plans. Boolean variables are represented as binary integer variables where 1 encodes true and 0 encodes false. We denote disjunctions by vertical lines to the left of the equation. All constants are denoted by non-qualigraphic letters. Variables are denoted by qualigraphic letters.

## Navigation Graph

The planning of the actions carried out by the agents is done using a flow model. We define $F_{ik} \in [0, 1]$ the flow representing the path of the robot i on the k-th edge. Thus, ensuring flow consistency is equivalent to compare incoming, outgoing and balance flow. To do so, for each position, we have to constraint incoming and outgoing flow to be equal to balances.

$$ \sum_{k|e_{ik}=(v',v)} F_{ik} - \sum_{k|e_{ik}=(v,v'')} F_{ik} = B_{iv} \quad (1) $$

## Propagation of Operational Metrics

The primary objective of this mission planning model is to produce schedules for the robot actions. It is therefore necessary to have a time metric based on the robots' achievements. To do this, we have chosen to represent time with two variables $T_{iv}, D_{iv} \in [0, tmax]^2$ that represent the time of arrival and the duration of the time spent on the node v of the robot i. It has to be propagated on the graph as:

$$ T_{iv} = \sum_{k|e_{ik}=(v',v)} F_{ik}(T_{iv'} + D_{iv'} + Tt_{ik}) \quad (2) $$

By the network flow definition, $T_{iv}$ is 0 where the agent does not use the position v. We need to add a constraint on $D_{iv}$ so it's also 0 where agent does not pass. This is the case for every point where $T_{iv}$ is 0 except the entry point. As $B_{iv}$ represent flow bias it could be used in the logic equation to represent the entry point where $B_{iv} = 1$. Thus the constraint asserting null duration on none pass by positions.

$$ T_{iv} = 0 \land B_{iv} \neq 1 \Rightarrow D_{iv} = 0 \quad (3) $$

## Task Constraint Expression

Considering the task m, we designate $Rt_{im} \in [0, 1]$ that reify task completion by the agent i. We first add the constraint that it has to be completed by one agent that is allowed to do so.

$$ \sum_{i} Rt_{im} = 1 \quad (4) $$

$$ i \notin At_m \Rightarrow Rt_{im} = 0 \quad (5) $$

In our planning model, we consider the task to be completed if the robot remains on the point longer than the duration of the task to be carried out. Thus durative task realization constraint is

$$ Rt_{im} \Rightarrow D_{iT_m} \geq Dt_m \quad (6) $$

We define the variable $T_{m} \in [0, tmax]$ the starting time of realization of the task m. This variable will be used later for verification of synchronization. In addition to the storage of the time of the realization, we have to ensure that this is performed in the appropriate time window.

$$ Rt_{im} \Rightarrow T_{m} = T_{iT_m} \land T_{iT_m} \in Wt_m \quad (7) $$

We also need to consider the limiting case of the starting point. The robot is at the starting position at t=0. This is also the case for all positions not taken by the robot. It is therefore necessary to make the task feasible at t=0 for the starting point, or to ensure that it is carried out at a later time to ensure the robot's passage.

$$ Rt_{im} \Rightarrow T_{iT_m} \geq 1 \lor B_{iT_m} = 1 \quad (8) $$

Tasks cannot be performed simultaneously by the same agent at the same location, therefore, we prohibit an agent from executing two tasks at the same node.

$$ m \neq m' \land Tt_m = Tt_{m'} \Rightarrow Rt_{im} + Rt_{im'} \leq 1 \quad (9) $$

## Temporal Exclusion Constraint

Temporal exclusion constraints on a given position is expressed by the following disjunction. The robot must pass before or after the temporal exclusion window $War_n$.

$$ i \in Mar_n \Rightarrow T_{iAr_n} + D_{iAr_n} < War_n \lor T_{iAr_n} > War_n \quad (10) $$
lar tasks are required to be executed by specific robots, these assignments are detailed in the set $At_m \subseteq [1, nr]$.

In parallel, the mission features nra temporal restrictions, represented as $Ar_n \in V$, where n indexes each temporal exclusion. The implication of a temporal exclusion varies, impacting only a subset of robots. Robots that must respect temporal exclusions are identified in the set $Mar_n \subseteq [1, nr]$ for the n-th area. The position must not be occupied by robots that have to comply with the temporal exclusion during a time window $War_n \subseteq [0, tmax]$.

Coordination between task execution is categorized into two types to streamline the framework, focusing on pairwise interactions. The sets S and P encompass action pairs that require synchronous and successive execution, respectively.

Furthermore, the mission strategy includes deploying agents for recognition. The corresponding boolean constant $Af_{iv}$ is true iff the robot i is allowed to arrive first at position v.

The assignment must be carried out within a predefined timeframe, but the plan quality will be assessed in relation to the speed of its planned execution.

## Planning Problem Formulation

In this section, we propose an encoding of the problem into a CSP formalism with finite-domain integer variables, inspired by the one of Guettier (2007) on related progression problems. This approach is particularly efficient for producing plans. Boolean variables are represented as binary integer variables where 1 encodes true and 0 encodes false. We denote disjunctions by vertical lines to the left of the equation. All constants are denoted by non-qualigraphic letters. Variables are denoted by qualigraphic letters.

## Navigation Graph

The planning of the actions carried out by the agents is done using a flow model. We define $F_{ik} \in [0, 1]$ the flow representing the path of the robot i on the k-th edge. Thus, ensuring flow consistency is equivalent to compare incoming, outgoing and balance flow. To do so, for each position, we have to constraint incoming and outgoing flow to be equal to balances.

$$ \sum_{k|e_{ik}=(v',v)} F_{ik} - \sum_{k|e_{ik}=(v,v'')} F_{ik} = B_{iv} \quad (1) $$

## Propagation of Operational Metrics

The primary objective of this mission planning model is to produce schedules for the robot actions. It is therefore necessary to have a time metric based on the robots' achievements. To do this, we have chosen to represent time with two variables $T_{iv}, D_{iv} \in [0, tmax]^2$ that represent the time of arrival and the duration of the time spent on the node v of the robot i. It has to be propagated on the graph as:

$$ T_{iv} = \sum_{k|e_{ik}=(v',v)} F_{ik}(T_{iv'} + D_{iv'} + Tt_{ik}) \quad (2) $$

By the network flow definition, $T_{iv}$ is 0 where the agent does not use the position v. We need to add a constraint on $D_{iv}$ so it's also 0 where agent does not pass. This is the case for every point where $T_{iv}$ is 0 except the entry point. As $B_{iv}$ represent flow bias it could be used in the logic equation to represent the entry point where $B_{iv} = 1$. Thus the constraint asserting null duration on none pass by positions.

$$ T_{iv} = 0 \land B_{iv} \neq 1 \Rightarrow D_{iv} = 0 \quad (3) $$

## Task Constraint Expression

Considering the task m, we designate $Rt_{im} \in [0, 1]$ that reify task completion by the agent i. We first add the constraint that it has to be completed by one agent that is allowed to do so.

$$ \sum_{i} Rt_{im} = 1 \quad (4) $$

$$ i \notin At_m \Rightarrow Rt_{im} = 0 \quad (5) $$

In our planning model, we consider the task to be completed if the robot remains on the point longer than the duration of the task to be carried out. Thus durative task realization constraint is

$$ Rt_{im} \Rightarrow D_{iT_m} \geq Dt_m \quad (6) $$

We define the variable $T_{m} \in [0, tmax]$ the starting time of realization of the task m. This variable will be used later for verification of synchronization. In addition to the storage of the time of the realization, we have to ensure that this is performed in the appropriate time window.

$$ Rt_{im} \Rightarrow T_{m} = T_{iT_m} \land T_{iT_m} \in Wt_m \quad (7) $$

We also need to consider the limiting case of the starting point. The robot is at the starting position at t=0. This is also the case for all positions not taken by the robot. It is therefore necessary to make the task feasible at t=0 for the starting point, or to ensure that it is carried out at a later time to ensure the robot's passage.

$$ Rt_{im} \Rightarrow T_{iT_m} \geq 1 \lor B_{iT_m} = 1 \quad (8) $$

Tasks cannot be performed simultaneously by the same agent at the same location, therefore, we prohibit an agent from executing two tasks at the same node.

$$ m \neq m' \land Tt_m = Tt_{m'} \Rightarrow Rt_{im} + Rt_{im'} \leq 1 \quad (9) $$

## Temporal Exclusion Constraint

Temporal exclusion constraints on a given position is expressed by the following disjunction. The robot must pass before or after the temporal exclusion window $War_n$.

$$ i \in Mar_n \Rightarrow T_{iAr_n} + D_{iAr_n} < War_n \lor T_{iAr_n} > War_n \quad (10) $$
## Position Discovery

To ensure the constraint of first arrival it is necessary to define two new variables $Tf_v, If_{iv} \in [0, t_{max}] \times \mathbb{B}$ which respectively represent the time of the first robot's arrival time and whether $i$ is the first robot arriving at position $v$.

We state the disjunction between three cases. Either the robot is the first to arrive at the position, and the moment of first arrival is when the robot enters the position. Or it passes over the position and is not the first, hence the time of first arrival is lower than the robot's arrival time. Or it does not pass through this position.

$$ \left| \begin{array}{l} \mathcal{I}f_{iv} \wedge \mathcal{T}_{iv} = \mathcal{T}f_v \\ -\mathcal{I}f_{iv} \wedge \mathcal{T}_{iv} > \mathcal{T}f_v \\ -\mathcal{I}f_{iv} \wedge \mathcal{T}_{iv} = 0 \end{array} \right. \qquad (11) $$

It is therefore only possible for an agent to arrive alone on a position first. It is also necessary to force the use of these variables if a robot passes through this position.

$$ \sum_{i} \mathcal{T}_{iv} \geq 1 \Rightarrow \sum_{i} \mathcal{I}f_{iv} = 1 \qquad (12) $$

It is also necessary to add constraints on position never visited. We need to enforce that if no robot passes by the position then there is no first arrived at this position.

$$ \sum_{i} \mathcal{T}_{iv} = 0 \Rightarrow \sum_{i} \mathcal{I}f_{iv} = 0 \qquad (13) $$

## Coordination Between Tasks

For the succession of 2 tasks $(m, m') \in P$ we want to ensure that the first task is completed before starting the second one. Thus the constraint for every pair of successive tasks m and m'

$$ \mathcal{T}t_m + \mathcal{D}t_m \leq \mathcal{T}t_{m'} \qquad (14) $$

For the synchronization of 2 tasks $(m, m') \in S$ we want to ensure that both tasks start at the same time. Thus the constraint

$$ \mathcal{T}t_m = \mathcal{T}t_{m'} \qquad (15) $$

## Mission Metrics

We want the robots to arrive as soon as possible at the end of the mission thus reducing the mission's makespan. The makespan takes into account moving and task completion. It may be necessary to leave robots possibility of staying on the finish line if a task needs to be completed at the mission exit point.

$$ Mm = \max_{iv}(\mathcal{T}_{iv} + \mathcal{D}_{iv}) \qquad (16) $$

## Resolution of the Constraint Problem

The constraint problem is solved using OrTools (Google LLC 2023). The model is expressed in Minizinc(min 2023; Nethercote et al. 2007).

<figure><img src="image_2.png" /><figcaption>Figure 1: Test Navigation Graph</figcaption></figure>

## Problem Instance

We investigate planning outcomes on a demonstration scenario effects of the metrics introduced previously. The navigation graph for this example is shown in Figure 1.

The scenario includes five agents: two ground unmanned vehicles (UGVs) traveling at 1 m/s and three unmanned aerial vehicles (UAVs) at 3 m/s. These agents adhere to a consistent navigation graph, entering at point pe and exiting at ps.

Throughout the mission, tasks are allocated at various numbered points, each taking 2s to complete. Some tasks have specific temporal requirements, such as simultaneous tasks at p23 and p11, and at p33 and p31. Moreover, the task at p32 must precede the task at p12. Access to point pr is prohibited between 10s and 20s.

The optimal plan solution for this problem is shown in Figure 2a, with numerous tasks executed concurrently. Go to position tasks are displayed in blue and durative tasks in green. The resulting plan proposes a solution that satisfies all operational objectives. Temporal exclusions are represented in gray on a dedicated timeline below the agent, they are respected by every agent.

We represent with blue dot the maximum level of mental load desired that will be presented in the next section. The plan to minimize the makespan does not meet this criterion. It is necessary to define measurable mental load metrics, with associated desired threshold, to ensure effective operator mission supervision during execution.

## Planning with Operator Based Metrics

In our target scenarios, plan execution requires an operator responsible for overseeing operations, to guarantee the safety of the robots and efficiency of the mission. In this section we define operator based metrics that can be optimized to improve plan quality.

## Metrics Overview

We propose three new metrics to optimize a plan along operator supervision. The metrics are inspired from ergonomics observations during real life experimentation such as described in (Ruff, Narayanan, and Draper 2002; Dixon, Wickens, and Chang 2005; Cummings and Guerlain 2007). We hypothesize that the automatic system is able of carrying out the mission in complete autonomy. The operator is responsible for ensuring robot safety and plan completion. To do this, it has robot positions and robots states and completion
## Position Discovery

To ensure the constraint of first arrival it is necessary to define two new variables $Tf_v, If_{iv} \in [0, t_{max}] \times \mathbb{B}$ which respectively represent the time of the first robot's arrival time and whether $i$ is the first robot arriving at position $v$.

We state the disjunction between three cases. Either the robot is the first to arrive at the position, and the moment of first arrival is when the robot enters the position. Or it passes over the position and is not the first, hence the time of first arrival is lower than the robot's arrival time. Or it does not pass through this position.

$$ \left| \begin{array}{l} \mathcal{I}f_{iv} \wedge \mathcal{T}_{iv} = \mathcal{T}f_v \\ -\mathcal{I}f_{iv} \wedge \mathcal{T}_{iv} > \mathcal{T}f_v \\ -\mathcal{I}f_{iv} \wedge \mathcal{T}_{iv} = 0 \end{array} \right. \qquad (11) $$

It is therefore only possible for an agent to arrive alone on a position first. It is also necessary to force the use of these variables if a robot passes through this position.

$$ \sum_{i} \mathcal{T}_{iv} \geq 1 \Rightarrow \sum_{i} \mathcal{I}f_{iv} = 1 \qquad (12) $$

It is also necessary to add constraints on position never visited. We need to enforce that if no robot passes by the position then there is no first arrived at this position.

$$ \sum_{i} \mathcal{T}_{iv} = 0 \Rightarrow \sum_{i} \mathcal{I}f_{iv} = 0 \qquad (13) $$

## Coordination Between Tasks

For the succession of 2 tasks $(m, m') \in P$ we want to ensure that the first task is completed before starting the second one. Thus the constraint for every pair of successive tasks m and m'

$$ \mathcal{T}t_m + \mathcal{D}t_m \leq \mathcal{T}t_{m'} \qquad (14) $$

For the synchronization of 2 tasks $(m, m') \in S$ we want to ensure that both tasks start at the same time. Thus the constraint

$$ \mathcal{T}t_m = \mathcal{T}t_{m'} \qquad (15) $$

## Mission Metrics

We want the robots to arrive as soon as possible at the end of the mission thus reducing the mission's makespan. The makespan takes into account moving and task completion. It may be necessary to leave robots possibility of staying on the finish line if a task needs to be completed at the mission exit point.

$$ Mm = \max_{iv}(\mathcal{T}_{iv} + \mathcal{D}_{iv}) \qquad (16) $$

## Resolution of the Constraint Problem

The constraint problem is solved using OrTools (Google LLC 2023). The model is expressed in Minizinc(min 2023; Nethercote et al. 2007).

<figure><img src="image_2.png" /><figcaption>Figure 1: Test Navigation Graph</figcaption></figure>

## Problem Instance

We investigate planning outcomes on a demonstration scenario effects of the metrics introduced previously. The navigation graph for this example is shown in Figure 1.

The scenario includes five agents: two ground unmanned vehicles (UGVs) traveling at 1 m/s and three unmanned aerial vehicles (UAVs) at 3 m/s. These agents adhere to a consistent navigation graph, entering at point pe and exiting at ps.

Throughout the mission, tasks are allocated at various numbered points, each taking 2s to complete. Some tasks have specific temporal requirements, such as simultaneous tasks at p23 and p11, and at p33 and p31. Moreover, the task at p32 must precede the task at p12. Access to point pr is prohibited between 10s and 20s.

The optimal plan solution for this problem is shown in Figure 2a, with numerous tasks executed concurrently. Go to position tasks are displayed in blue and durative tasks in green. The resulting plan proposes a solution that satisfies all operational objectives. Temporal exclusions are represented in gray on a dedicated timeline below the agent, they are respected by every agent.

We represent with blue dot the maximum level of mental load desired that will be presented in the next section. The plan to minimize the makespan does not meet this criterion. It is necessary to define measurable mental load metrics, with associated desired threshold, to ensure effective operator mission supervision during execution.

## Planning with Operator Based Metrics

In our target scenarios, plan execution requires an operator responsible for overseeing operations, to guarantee the safety of the robots and efficiency of the mission. In this section we define operator based metrics that can be optimized to improve plan quality.

## Metrics Overview

We propose three new metrics to optimize a plan along operator supervision. The metrics are inspired from ergonomics observations during real life experimentation such as described in (Ruff, Narayanan, and Draper 2002; Dixon, Wickens, and Chang 2005; Cummings and Guerlain 2007). We hypothesize that the automatic system is able of carrying out the mission in complete autonomy. The operator is responsible for ensuring robot safety and plan completion. To do this, it has robot positions and robots states and completion
<figure><img src="image_3.png" /><figcaption>Figure 2: Temporal Representation of Task Completion</figcaption></figure>

information in progress tasks. In addition, it can directly supervise the tasks to be carried out. For material reasons, we consider that only one task can be supervised at a time.

* The first metric deals with **tasks or temporal exclusion supervision** by the operator. Ideally, the operator should supervise as many tasks and exclusions as possible, with a preference for complex tasks. However, due to hardware constraints, an operator can only supervise one task or temporal exclusion at a time. The aim of this metric is primarily to secure task completion, with positive effects on operator situation awareness.

* The second metric represents **situational knowledge acquisition**. Some terrain key positions provide important insights into mission status, and it is important to explore them regardless of task completion. While the operator supervises the robots, discovering some key positions increase operator awareness levels. We define a new task that doesn't correspond to any operational action in the mission. Supervision on position discovery consists of a brief consideration of robot perception. It is necessary

to supervise as many positions discoveries as possible, preferably those who are the more interesting. The aim of this metric is to improve the situation awareness of the operator.

* The third metric represents the **operator background mental load**. During a mission, the operator is constantly trying to keep in mind what robots are doing. This is particularly problematic during critical operations when the operator would like to focus on a single robot. When the operator is overcommitted by the mission, the results are even worse. In fact, instead of providing a decision support, robots are abandoned until the critical task is resolved. Constraints over the metric aim to decrease task load index.

## Formalization

Regarding background mental load metrics, we associate to each task a scalar $L_a \in \mathbb{N}$, for each action $a \in [1, nt + nar]$. Each robot performing a *move to a position* task is counted as 1. The background mental load metric maximum
<figure><img src="image_3.png" /><figcaption>Figure 2: Temporal Representation of Task Completion</figcaption></figure>

information in progress tasks. In addition, it can directly supervise the tasks to be carried out. For material reasons, we consider that only one task can be supervised at a time.

* The first metric deals with **tasks or temporal exclusion supervision** by the operator. Ideally, the operator should supervise as many tasks and exclusions as possible, with a preference for complex tasks. However, due to hardware constraints, an operator can only supervise one task or temporal exclusion at a time. The aim of this metric is primarily to secure task completion, with positive effects on operator situation awareness.

* The second metric represents **situational knowledge acquisition**. Some terrain key positions provide important insights into mission status, and it is important to explore them regardless of task completion. While the operator supervises the robots, discovering some key positions increase operator awareness levels. We define a new task that doesn't correspond to any operational action in the mission. Supervision on position discovery consists of a brief consideration of robot perception. It is necessary

to supervise as many positions discoveries as possible, preferably those who are the more interesting. The aim of this metric is to improve the situation awareness of the operator.

* The third metric represents the **operator background mental load**. During a mission, the operator is constantly trying to keep in mind what robots are doing. This is particularly problematic during critical operations when the operator would like to focus on a single robot. When the operator is overcommitted by the mission, the results are even worse. In fact, instead of providing a decision support, robots are abandoned until the critical task is resolved. Constraints over the metric aim to decrease task load index.

## Formalization

Regarding background mental load metrics, we associate to each task a scalar $L_a \in \mathbb{N}$, for each action $a \in [1, nt + nar]$. Each robot performing a *move to a position* task is counted as 1. The background mental load metric maximum
is defined by $Mlmax \in \mathbb{N}$.

The informational gained by the discovery of the $v^{th}$ position is specified in $G_v \in \mathbb{N}$. When the discovery is made through a supervised action, we consider that the information gain to be scaled by a factor $Ig$.

## Supervised Action

We define an action as a task or a temporal exclusion. To represent the operator's supervised action, we define the boolean variable $S_a \in \mathbb{B}$ which is true iff the action is supervised. Due to hardware constraints, only a single action supervision is possible at any point in time. This constraint is asserted on every pair of tasks $m, m'$. So either some tasks are not supervised, or their execution times do not overlap, which is enforced by the disjunctive constraint.

$$ \left| \begin{array}{l} S_m + S_{m'} \le 1 \\ \mathcal{T}t_m + Dt_m < \mathcal{T}t_{m'} \\ \mathcal{T}t_{m'} + Dt_{m'} < \mathcal{T}t_m \end{array} \right. \qquad (17) $$

The same need to be done for temporal exclusions but on their time windows.

$$ \left| \begin{array}{l} S_n + S_{n'} \le 1 \\ War_n < War_{n'} \\ War_{n'} < War_n \end{array} \right. \qquad (18) $$

Cross concurrency also needs to be addressed by combining previous approach.

$$ \left| \begin{array}{l} S_m + S_n \le 1 \\ War_n < \mathcal{T}t_m \\ \mathcal{T}t_m + Dt_m < War_n \end{array} \right. \qquad (19) $$

The metric representing task and temporal exclusion supervision is obtained by adding the performed supervision weighted by their relevance.

$$ Ms = \sum_m S_m L_m + \sum_n S_n L_n \qquad (20) $$

## Situational Knowledge Acquisition

We define the variable $Fs_{iv} \in \mathbb{B}$ representing the supervised discovery of the position $v$ by the robot $i$. As it is concurrent with task supervision, we have to enforce temporal separation. As for tasks or temporal exclusion supervision, we first ensure that both are not done in the plan or they are not overlapping.

$$ \left| \begin{array}{l} \neg(Fs_{iv} \land S_m) \\ \mathcal{T}_{iv} > \mathcal{T}t_m + Dt_m \\ \mathcal{T}_{iv} \le \mathcal{T}t_m \end{array} \right. \qquad (21) $$

A similar constraint is used to prevent overlapping supervised discovery and temporal exclusion supervision:

$$ \left| \begin{array}{l} \neg(Fs_{iv} \land S_n) \\ \mathcal{T}_{iv} > Wra_n \\ \mathcal{T}_{iv} \le Wra_n \end{array} \right. \qquad (22) $$

It is only possible to perform one supervision at a time, so it is necessary to specify the disjunction of discovery supervision two by two.

$$ \left| \begin{array}{l} \neg(Fs_{iv} \land Fs_{i'v'}) \\ \mathcal{T}_{iv} \neq \mathcal{T}_{i'v'} \end{array} \right. \qquad (23) $$

The associated metric is denoted $Mfs$ and defined as follows.

$$ Mfs = \sum_v G_v \sum_i \mathcal{I}_{f_{iv}}[IgFs_{iv} + (1 - Fs_{iv})] \qquad (24) $$

## Background Mental Load

As described beforehand, background mental load is the action performed by each robot at a specific time. For a given time $t \in [1, tmax]$, we define $actT(t)$ as the set of tasks executing at $t$:

$$ actT(t) = \{m \in [1, nt] \mid t \in [\mathcal{T}t_m, \mathcal{T}t_m + Dt_m - 1]\} \qquad (25) $$

$actAr(t)$ as the set of active temporal exclusions:

$$ actAr(t) = \{n \in [1, nar] \mid t \in War_n\} \qquad (26) $$

and $move(t)$ as the set of ongoing displacement at $t$:

$$ move(t) = \left\{ v \in [1, nr] \mid \begin{array}{l} t \in [\mathcal{T}_{iv}, \mathcal{T}_{iv} + D_{iv} - 1] \\ \lor t \ge \mathcal{T}_{iv} \land B_{iv} = -1 \end{array} \right\} \qquad (27) $$

The background mental load $Ml(t)$ is modeled as the sum of the contribution of all these activities at a given time $t$:

$$ Ml(t) = \sum_{m \in actT(t)} L_m + \sum_{n \in actAr(t)} L_n + \sum_{v \in move(t)} 1 \qquad (28) $$

We do not optimize this metric but constraint its value below a certain threshold defined during mission preparation.

$$ Mlmax \ge \max_t(Ml(t)) \qquad (29) $$

## Metrics optimization

While optimizing operator metrics, optimal makespan is no longer feasible. The cognitive load is not optimized, it is limited so as not to overload the operator such as described in equation 29. Optimization step has to be conducted iteratively to achieve the best quality plan. Optimal makespan value might not be reached.

1. Maximizing supervision score ($M$),

2. Maximizing informational gain ($Mfs$),

3. Minimizing makespan ($Mm$),

4. We have tie-breaking metric to that indirectly favors a fair repartition of tasks among agents.

Thus the global metrics to be maximized is of the shape

$$ M = AMs + BMfs - CMm - \sum_{iv} (T_{iv}^2) \qquad (30) $$

With constants $A, B, C$ such that the resolution is lexicographic ($A \gg B \gg C \gg 1$).
is defined by $Mlmax \in \mathbb{N}$.

The informational gained by the discovery of the $v^{th}$ position is specified in $G_v \in \mathbb{N}$. When the discovery is made through a supervised action, we consider that the information gain to be scaled by a factor $Ig$.

## Supervised Action

We define an action as a task or a temporal exclusion. To represent the operator's supervised action, we define the boolean variable $S_a \in \mathbb{B}$ which is true iff the action is supervised. Due to hardware constraints, only a single action supervision is possible at any point in time. This constraint is asserted on every pair of tasks $m, m'$. So either some tasks are not supervised, or their execution times do not overlap, which is enforced by the disjunctive constraint.

$$ \left| \begin{array}{l} S_m + S_{m'} \le 1 \\ \mathcal{T}t_m + Dt_m < \mathcal{T}t_{m'} \\ \mathcal{T}t_{m'} + Dt_{m'} < \mathcal{T}t_m \end{array} \right. \qquad (17) $$

The same need to be done for temporal exclusions but on their time windows.

$$ \left| \begin{array}{l} S_n + S_{n'} \le 1 \\ War_n < War_{n'} \\ War_{n'} < War_n \end{array} \right. \qquad (18) $$

Cross concurrency also needs to be addressed by combining previous approach.

$$ \left| \begin{array}{l} S_m + S_n \le 1 \\ War_n < \mathcal{T}t_m \\ \mathcal{T}t_m + Dt_m < War_n \end{array} \right. \qquad (19) $$

The metric representing task and temporal exclusion supervision is obtained by adding the performed supervision weighted by their relevance.

$$ Ms = \sum_m S_m L_m + \sum_n S_n L_n \qquad (20) $$

## Situational Knowledge Acquisition

We define the variable $Fs_{iv} \in \mathbb{B}$ representing the supervised discovery of the position $v$ by the robot $i$. As it is concurrent with task supervision, we have to enforce temporal separation. As for tasks or temporal exclusion supervision, we first ensure that both are not done in the plan or they are not overlapping.

$$ \left| \begin{array}{l} \neg(Fs_{iv} \land S_m) \\ \mathcal{T}_{iv} > \mathcal{T}t_m + Dt_m \\ \mathcal{T}_{iv} \le \mathcal{T}t_m \end{array} \right. \qquad (21) $$

A similar constraint is used to prevent overlapping supervised discovery and temporal exclusion supervision:

$$ \left| \begin{array}{l} \neg(Fs_{iv} \land S_n) \\ \mathcal{T}_{iv} > Wra_n \\ \mathcal{T}_{iv} \le Wra_n \end{array} \right. \qquad (22) $$

It is only possible to perform one supervision at a time, so it is necessary to specify the disjunction of discovery supervision two by two.

$$ \left| \begin{array}{l} \neg(Fs_{iv} \land Fs_{i'v'}) \\ \mathcal{T}_{iv} \neq \mathcal{T}_{i'v'} \end{array} \right. \qquad (23) $$

The associated metric is denoted $Mfs$ and defined as follows.

$$ Mfs = \sum_v G_v \sum_i \mathcal{I}_{f_{iv}}[IgFs_{iv} + (1 - Fs_{iv})] \qquad (24) $$

## Background Mental Load

As described beforehand, background mental load is the action performed by each robot at a specific time. For a given time $t \in [1, tmax]$, we define $actT(t)$ as the set of tasks executing at $t$:

$$ actT(t) = \{m \in [1, nt] \mid t \in [\mathcal{T}t_m, \mathcal{T}t_m + Dt_m - 1]\} \qquad (25) $$

$actAr(t)$ as the set of active temporal exclusions:

$$ actAr(t) = \{n \in [1, nar] \mid t \in War_n\} \qquad (26) $$

and $move(t)$ as the set of ongoing displacement at $t$:

$$ move(t) = \left\{ v \in [1, nr] \mid \begin{array}{l} t \in [\mathcal{T}_{iv}, \mathcal{T}_{iv} + D_{iv} - 1] \\ \lor t \ge \mathcal{T}_{iv} \land B_{iv} = -1 \end{array} \right\} \qquad (27) $$

The background mental load $Ml(t)$ is modeled as the sum of the contribution of all these activities at a given time $t$:

$$ Ml(t) = \sum_{m \in actT(t)} L_m + \sum_{n \in actAr(t)} L_n + \sum_{v \in move(t)} 1 \qquad (28) $$

We do not optimize this metric but constraint its value below a certain threshold defined during mission preparation.

$$ Mlmax \ge \max_t(Ml(t)) \qquad (29) $$

## Metrics optimization

While optimizing operator metrics, optimal makespan is no longer feasible. The cognitive load is not optimized, it is limited so as not to overload the operator such as described in equation 29. Optimization step has to be conducted iteratively to achieve the best quality plan. Optimal makespan value might not be reached.

1. Maximizing supervision score ($M$),

2. Maximizing informational gain ($Mfs$),

3. Minimizing makespan ($Mm$),

4. We have tie-breaking metric to that indirectly favors a fair repartition of tasks among agents.

Thus the global metrics to be maximized is of the shape

$$ M = AMs + BMfs - CMm - \sum_{iv} (T_{iv}^2) \qquad (30) $$

With constants $A, B, C$ such that the resolution is lexicographic ($A \gg B \gg C \gg 1$).
## Results

Problem's optimal solution is depicted in Figure 2b. In addition to Figure 2a color convention, we display supervised tasks in purple and supervised position discovery in orange.

Operator maximal background mental load criterion is respected which causes the makespan to be larger. Not all tasks are supervised, as some are performed synchronously. This synchronicity is a hard constraint of the planning problem. The final optimization step separates the different tasks and produces a plan that is more resilient to minor variations in execution time.

# Application to a Realistic Operation

## CoHoMa II Mission

French Army introduced a new challenge within a military context that involves navigating through hostile territories. This requires coordinating robots to ensure the safety of the operator's vehicle, as presented by Godet, Lesire, and Bit-Monnot (2023).

It involves a robotic combat group tasked with progressing 1.5 km in enemy territory while ensuring the protection of operators inside a command vehicle. Contingencies are simulated by disseminated red cubes, discovered during the progression. Instructions on the cubes detail the operations required for their deactivation, which may require the collaboration of multiple robots. The vehicle is considered vulnerable and must avoid proximity to the red cubes unless they have been deactivated beforehand.

## Model

To model the CoHoMa mission, we used distinct navigation graphs for UAVs and UGVs. For UGVs, their real geometry is obtained by representing the different paths in a forest. For UAVs, the navigation graph is obtained by connecting all nearby points which gives them greater freedom of trajectories. The speed settings are 1 meter per second for UGVs and 3 meters per second for UAVs.

We introduce a new agent in the planning model that represents the operator who has to cross the area. All reached position by this agent has to be discovered by another one. This agent is not able to be performed durative tasks and has a speed of 1 m/s.

The mission involves various entry and exit points for the agents, which are not further elaborated upon in this text. It involves achieving 13 tasks, each with the duration of 120 seconds. Two tasks have a specific order of execution and three tasks are on the same position and have to be synchronized. There is a temporal exclusion from t=200s to t=400s where no task has to be conducted. The makespan of the plan is required to be below 2500 seconds, with a time step of 20 seconds.

## Results

On this representative problem, when ignoring operator metrics, optimal makespan is computed in 970s. An optimal solution with respect to operator metrics is displayed in Figure 3. This solution was computed in 1800s on a machine with 10 physical core of 2.6 GHz, with OrTools v9.8.

This plan, while being 120% longer to execute links to the optimal plan, effectively reduces the peak of the operational workload by three which greatly facilitates comprehensive exploration of the zone. The strong impact of the max load on the makespan is due to the fact that there are more agents than the max load. This means that not all agents can move in parallel. In addition, the tasks modeled are particularly demanding, which makes it even more difficult for robots to move.

It should be noted that incorporating operator metrics into the constraint problem presents significant complexity for the solver. Indeed, it is easier for a CSP solver to take into account metrics correlated to the task progression such as the makespan or the fuel usage. On the other hand, operator metrics are orthogonal to the propagation of space progression since they depend on time. Consequently, scaling emerges as a critical and complex aspect to consider. Our effort has been toward an implementation that facilitates problem resolution. Implementing dedicated resolution strategies for these metrics could be a way of greatly optimizing solutions search. Precisely characterizing these tradeoffs between the model accuracy and the runtime of the solver will be the purpose of a more detailed empirical analysis on a more diverse set of problems.

## Discussion

This method has not been tested during the CoHoMa II mission but was designed based on the feedback from two teams who participated in the challenge. During this challenge, it became apparent that the operators were unable to fulfill their critical roles when resorting to existing planning approaches without operator-specific metrics.

The proposed operator metrics significantly advance the usability of planning in this context, by better aligning the plan with the capabilities of the operator to supervise plan execution. This enables the direct involvement of the operator, e.g., by means of teleoperation, to deal with contingent events and situations not anticipated in the generated plan. Beside our own scenario, the need for such direct involvement of the operator at execution time is notably justified in a military context by (Dixon, Wickens, and Chang 2005; Wilkins, Lee, and Berry 2003; Cummings and Guerlain 2007).

Our approach to take the operator into account in planning considers a simplistic model of mental load. Finer cognitive and mental load models should be considered, such as the ones proposed for stressful situations involving high levels of responsibility in (Kokar and Endsley 2012; Hollands, Spivak, and Kramkowski 2019; Endsley, Garland et al. 2000).

But even with more elaborated models, a more fundamental limitation is the difficulty of precisely capturing the desires of the operator in the optimization metric. One could even advocate that this is impossible to do, as the role of the operator is precisely to bring a different perspective than what can be currently captured in a computer system. To tackle this challenge, we believe it is interesting to push forward mixed-initiative planning techniques. Mixed-initiative planning has been a subject of interest for many years, especially in the context of space operations (Ai-Chang
## Results

Problem's optimal solution is depicted in Figure 2b. In addition to Figure 2a color convention, we display supervised tasks in purple and supervised position discovery in orange.

Operator maximal background mental load criterion is respected which causes the makespan to be larger. Not all tasks are supervised, as some are performed synchronously. This synchronicity is a hard constraint of the planning problem. The final optimization step separates the different tasks and produces a plan that is more resilient to minor variations in execution time.

# Application to a Realistic Operation

## CoHoMa II Mission

French Army introduced a new challenge within a military context that involves navigating through hostile territories. This requires coordinating robots to ensure the safety of the operator's vehicle, as presented by Godet, Lesire, and Bit-Monnot (2023).

It involves a robotic combat group tasked with progressing 1.5 km in enemy territory while ensuring the protection of operators inside a command vehicle. Contingencies are simulated by disseminated red cubes, discovered during the progression. Instructions on the cubes detail the operations required for their deactivation, which may require the collaboration of multiple robots. The vehicle is considered vulnerable and must avoid proximity to the red cubes unless they have been deactivated beforehand.

## Model

To model the CoHoMa mission, we used distinct navigation graphs for UAVs and UGVs. For UGVs, their real geometry is obtained by representing the different paths in a forest. For UAVs, the navigation graph is obtained by connecting all nearby points which gives them greater freedom of trajectories. The speed settings are 1 meter per second for UGVs and 3 meters per second for UAVs.

We introduce a new agent in the planning model that represents the operator who has to cross the area. All reached position by this agent has to be discovered by another one. This agent is not able to be performed durative tasks and has a speed of 1 m/s.

The mission involves various entry and exit points for the agents, which are not further elaborated upon in this text. It involves achieving 13 tasks, each with the duration of 120 seconds. Two tasks have a specific order of execution and three tasks are on the same position and have to be synchronized. There is a temporal exclusion from t=200s to t=400s where no task has to be conducted. The makespan of the plan is required to be below 2500 seconds, with a time step of 20 seconds.

## Results

On this representative problem, when ignoring operator metrics, optimal makespan is computed in 970s. An optimal solution with respect to operator metrics is displayed in Figure 3. This solution was computed in 1800s on a machine with 10 physical core of 2.6 GHz, with OrTools v9.8.

This plan, while being 120% longer to execute links to the optimal plan, effectively reduces the peak of the operational workload by three which greatly facilitates comprehensive exploration of the zone. The strong impact of the max load on the makespan is due to the fact that there are more agents than the max load. This means that not all agents can move in parallel. In addition, the tasks modeled are particularly demanding, which makes it even more difficult for robots to move.

It should be noted that incorporating operator metrics into the constraint problem presents significant complexity for the solver. Indeed, it is easier for a CSP solver to take into account metrics correlated to the task progression such as the makespan or the fuel usage. On the other hand, operator metrics are orthogonal to the propagation of space progression since they depend on time. Consequently, scaling emerges as a critical and complex aspect to consider. Our effort has been toward an implementation that facilitates problem resolution. Implementing dedicated resolution strategies for these metrics could be a way of greatly optimizing solutions search. Precisely characterizing these tradeoffs between the model accuracy and the runtime of the solver will be the purpose of a more detailed empirical analysis on a more diverse set of problems.

## Discussion

This method has not been tested during the CoHoMa II mission but was designed based on the feedback from two teams who participated in the challenge. During this challenge, it became apparent that the operators were unable to fulfill their critical roles when resorting to existing planning approaches without operator-specific metrics.

The proposed operator metrics significantly advance the usability of planning in this context, by better aligning the plan with the capabilities of the operator to supervise plan execution. This enables the direct involvement of the operator, e.g., by means of teleoperation, to deal with contingent events and situations not anticipated in the generated plan. Beside our own scenario, the need for such direct involvement of the operator at execution time is notably justified in a military context by (Dixon, Wickens, and Chang 2005; Wilkins, Lee, and Berry 2003; Cummings and Guerlain 2007).

Our approach to take the operator into account in planning considers a simplistic model of mental load. Finer cognitive and mental load models should be considered, such as the ones proposed for stressful situations involving high levels of responsibility in (Kokar and Endsley 2012; Hollands, Spivak, and Kramkowski 2019; Endsley, Garland et al. 2000).

But even with more elaborated models, a more fundamental limitation is the difficulty of precisely capturing the desires of the operator in the optimization metric. One could even advocate that this is impossible to do, as the role of the operator is precisely to bring a different perspective than what can be currently captured in a computer system. To tackle this challenge, we believe it is interesting to push forward mixed-initiative planning techniques. Mixed-initiative planning has been a subject of interest for many years, especially in the context of space operations (Ai-Chang
<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /><figcaption>Figure 3: Time usage of different robots when taking account operators on CoHoMa mission</figcaption></figure>

et al. 2004). A critical enabling feature for mixed-initiative planning is the ability for the automated planner to explain its decision to the operator. This has been the subject of recent work in both the automated planning (Eifler et al. 2020) and constraint programming (Guns et al. 2023; Gamba, Bogaerts, and Guns 2023) communities, which appear very relevant for our needs. Our interest is also the work of Lerouge et al. (2023), who considers the generation of explanations for flow-model similar to the one of Guettier (2007) and our own.

Besides, an underlying assumption of our approach is that, if a sufficient time is allocated for an action, the execution layer will successfully accomplish the task, possibly with the help of the operator. Should it fail nevertheless, we advocate for a strategy that involves replanning the mission considering the current state and any diminished capabilities.

Finally, several improvements could be brought to our planning model to tackle a more diverse set of problems. Notably, explicit representation of resources, such as fuel, would be important for a number of scenarios. Such resource constraints are very common in the constraint programming and operations research communities and would naturally fit in our formalism.

## Conclusion

We have presented an operational planning model that is capable of modeling realistic planning problems as demonstrated on a complex progression mission. Its domain-dependent approach enables its efficient resolution by a constraint solver.

Through the introduction of operator-centric metrics, we presented contributions toward enabling operator's involvement at plan execution. A natural evolution of this work

would be toward mixed-initiative planning, empowering the operator to refine the generated plan through direct interaction with the planning system. Typical interactions could be, e.g., changing the priorities of optimization metrics or assigning a task to particular robots.

## References

2023. MiniZinc. http://www.minizinc.org/. Accessed: 2024-03-12.

Ai-Chang, M.; Bresina, J.; Charest, L.; Chase, A.; Hsu, J.-J.; Jonsson, A.; Kanefsky, B.; Morris, P.; Rajan, K.; Yglesias, J.; Chafin, B.; Dias, W.; and Maldague, P. 2004. MAPGEN: mixed-initiative planning and scheduling for the Mars Exploration Rover mission. *IEEE Intelligent Systems*, 19(1): 8–12.

Bevacqua, G.; Cacace, J.; Finzi, A.; and Lippiello, V. 2015. Mixed-Initiative Planning and Execution for Multiple Drones in Search and Rescue Missions. *Proceedings of the International Conference on Automated Planning and Scheduling*, 25(1): 315–323.

Bresina, J. L.; Jónsson, A. K.; Morris, P. H.; and Rajan, K. 2004. Activity planning for the mars exploration rovers. In *ICAPS-2005 Conference*.

Cummings, M. L.; and Guerlain, S. 2007. Developing operator capacity estimates for supervisory control of autonomous vehicles. *Human factors*, 49(1): 1–15.

Dixon, S. R.; Wickens, C. D.; and Chang, D. 2005. Mission control of multiple unmanned aerial vehicles: A workload analysis. *Human factors*, 47(3): 479–487.

Eifler, R.; Cashmore, M.; Hoffmann, J.; Magazzeni, D.; and Steinmetz, M. 2020. A new approach to plan-space explanation: Analyzing plan-property dependencies in oversubscription planning. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 34, 9818–9826.
<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /><figcaption>Figure 3: Time usage of different robots when taking account operators on CoHoMa mission</figcaption></figure>

et al. 2004). A critical enabling feature for mixed-initiative planning is the ability for the automated planner to explain its decision to the operator. This has been the subject of recent work in both the automated planning (Eifler et al. 2020) and constraint programming (Guns et al. 2023; Gamba, Bogaerts, and Guns 2023) communities, which appear very relevant for our needs. Our interest is also the work of Lerouge et al. (2023), who considers the generation of explanations for flow-model similar to the one of Guettier (2007) and our own.

Besides, an underlying assumption of our approach is that, if a sufficient time is allocated for an action, the execution layer will successfully accomplish the task, possibly with the help of the operator. Should it fail nevertheless, we advocate for a strategy that involves replanning the mission considering the current state and any diminished capabilities.

Finally, several improvements could be brought to our planning model to tackle a more diverse set of problems. Notably, explicit representation of resources, such as fuel, would be important for a number of scenarios. Such resource constraints are very common in the constraint programming and operations research communities and would naturally fit in our formalism.

## Conclusion

We have presented an operational planning model that is capable of modeling realistic planning problems as demonstrated on a complex progression mission. Its domain-dependent approach enables its efficient resolution by a constraint solver.

Through the introduction of operator-centric metrics, we presented contributions toward enabling operator's involvement at plan execution. A natural evolution of this work

would be toward mixed-initiative planning, empowering the operator to refine the generated plan through direct interaction with the planning system. Typical interactions could be, e.g., changing the priorities of optimization metrics or assigning a task to particular robots.

## References

2023. MiniZinc. http://www.minizinc.org/. Accessed: 2024-03-12.

Ai-Chang, M.; Bresina, J.; Charest, L.; Chase, A.; Hsu, J.-J.; Jonsson, A.; Kanefsky, B.; Morris, P.; Rajan, K.; Yglesias, J.; Chafin, B.; Dias, W.; and Maldague, P. 2004. MAPGEN: mixed-initiative planning and scheduling for the Mars Exploration Rover mission. *IEEE Intelligent Systems*, 19(1): 8–12.

Bevacqua, G.; Cacace, J.; Finzi, A.; and Lippiello, V. 2015. Mixed-Initiative Planning and Execution for Multiple Drones in Search and Rescue Missions. *Proceedings of the International Conference on Automated Planning and Scheduling*, 25(1): 315–323.

Bresina, J. L.; Jónsson, A. K.; Morris, P. H.; and Rajan, K. 2004. Activity planning for the mars exploration rovers. In *ICAPS-2005 Conference*.

Cummings, M. L.; and Guerlain, S. 2007. Developing operator capacity estimates for supervisory control of autonomous vehicles. *Human factors*, 49(1): 1–15.

Dixon, S. R.; Wickens, C. D.; and Chang, D. 2005. Mission control of multiple unmanned aerial vehicles: A workload analysis. *Human factors*, 47(3): 479–487.

Eifler, R.; Cashmore, M.; Hoffmann, J.; Magazzeni, D.; and Steinmetz, M. 2020. A new approach to plan-space explanation: Analyzing plan-property dependencies in oversubscription planning. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 34, 9818–9826.
Endsley, M. R.; Garland, D. J.; et al. 2000. Theoretical underpinnings of situation awareness: A critical review. *Situation awareness analysis and measurement, 1*(1): 3–21.

Gamba, E.; Bogaerts, B.; and Guns, T. 2023. Efficiently explaining CSPs with unsatisfiable subset optimization. *Journal of Artificial Intelligence Research*, 78: 709–746.

Godet, R.; Lesire, C.; and Bit-Monnot, A. 2023. Multi-Robot Task Planning to Secure Human Group Progress. *arXiv preprint arXiv:2310.07731*.

Google LLC. 2023. OR-Tools. https://developers.google.com/optimization/. Accessed: 2024-03-12.

Guettier, C. 2007. Solving planning and scheduling problems in network based operations. *Proceedings of Constraint Programming (CP)*.

Guns, T.; Gamba, E.; Mulamba, M.; Bleukx, I.; Berden, S.; and Pesa, M. 2023. Sudoku Assistant–an AI-Powered App to Help Solve Pen-And-Paper Sudokus. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 37, 16440–16442.

Hollands, J. G.; Spivak, T.; and Kramkowski, E. W. 2019. Cognitive load and situation awareness for soldiers: effects of message presentation rate and sensory modality. *Human factors*, 61(5): 763–773.

Jiang, S.; and Arkin, R. C. 2015. Mixed-initiative human-robot interaction: definition, taxonomy, and survey. In *2015 IEEE International conference on systems, man, and cybernetics*, 954–961. IEEE.

Kokar, M. M.; and Endsley, M. R. 2012. Situation awareness and cognitive modeling. *IEEE Intelligent Systems*, 27(3): 91–96.

Lerouge, M.; Gicquel, C.; Mousseau, V.; and Ouerdane, W. 2023. Counterfactual Explanations for Workforce Scheduling and Routing Problems. In *12th International Conference on Operations Research and Enterprise Systems*, 50–61. SCITEPRESS-Science and Technology Publications.

Nethercote, N.; Stuckey, P. J.; Becket, R.; Brand, S.; Duck, G. J.; and Tack, G. 2007. MiniZinc: Towards a Standard CP Modelling Language. In *Principles and Practice of Constraint Programming – CP 2007*, Lecture Notes in Computer Science, 529–543. Springer.

Ruff, H. A.; Narayanan, S.; and Draper, M. H. 2002. Human interaction with levels of automation and decision-aid fidelity in the supervisory control of multiple simulated unmanned air vehicles. *Presence*, 11(4): 335–351.

Wilkins, D. E.; Lee, T. J.; and Berry, P. 2003. Interactive execution monitoring of agent teams. *Journal of Artificial Intelligence Research*, 18: 217–261.
Endsley, M. R.; Garland, D. J.; et al. 2000. Theoretical underpinnings of situation awareness: A critical review. *Situation awareness analysis and measurement, 1*(1): 3–21.

Gamba, E.; Bogaerts, B.; and Guns, T. 2023. Efficiently explaining CSPs with unsatisfiable subset optimization. *Journal of Artificial Intelligence Research*, 78: 709–746.

Godet, R.; Lesire, C.; and Bit-Monnot, A. 2023. Multi-Robot Task Planning to Secure Human Group Progress. *arXiv preprint arXiv:2310.07731*.

Google LLC. 2023. OR-Tools. https://developers.google.com/optimization/. Accessed: 2024-03-12.

Guettier, C. 2007. Solving planning and scheduling problems in network based operations. *Proceedings of Constraint Programming (CP)*.

Guns, T.; Gamba, E.; Mulamba, M.; Bleukx, I.; Berden, S.; and Pesa, M. 2023. Sudoku Assistant–an AI-Powered App to Help Solve Pen-And-Paper Sudokus. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 37, 16440–16442.

Hollands, J. G.; Spivak, T.; and Kramkowski, E. W. 2019. Cognitive load and situation awareness for soldiers: effects of message presentation rate and sensory modality. *Human factors*, 61(5): 763–773.

Jiang, S.; and Arkin, R. C. 2015. Mixed-initiative human-robot interaction: definition, taxonomy, and survey. In *2015 IEEE International conference on systems, man, and cybernetics*, 954–961. IEEE.

Kokar, M. M.; and Endsley, M. R. 2012. Situation awareness and cognitive modeling. *IEEE Intelligent Systems*, 27(3): 91–96.

Lerouge, M.; Gicquel, C.; Mousseau, V.; and Ouerdane, W. 2023. Counterfactual Explanations for Workforce Scheduling and Routing Problems. In *12th International Conference on Operations Research and Enterprise Systems*, 50–61. SCITEPRESS-Science and Technology Publications.

Nethercote, N.; Stuckey, P. J.; Becket, R.; Brand, S.; Duck, G. J.; and Tack, G. 2007. MiniZinc: Towards a Standard CP Modelling Language. In *Principles and Practice of Constraint Programming – CP 2007*, Lecture Notes in Computer Science, 529–543. Springer.

Ruff, H. A.; Narayanan, S.; and Draper, M. H. 2002. Human interaction with levels of automation and decision-aid fidelity in the supervisory control of multiple simulated unmanned air vehicles. *Presence*, 11(4): 335–351.

Wilkins, D. E.; Lee, T. J.; and Berry, P. 2003. Interactive execution monitoring of agent teams. *Journal of Artificial Intelligence Research*, 18: 217–261.