domain: spi info math phys

text:
Félix Quinton

Christophe Grand

Charles Lesire

Communication-Preserving Bids in Market-Based Task Allocation

In this paper, we study the effects of impaired communications on the performances of auction-based task allocation in a dynamic surveillance scenario. We propose a novel connectivity term to include in the bid valuation formula, that aims at improving communications in the multi-robot team. We evaluate our method as well as another state-of-the-art method using robot inter-distance to maintain communication, on randomly generated scenarios and on a real-world scenario. We demonstrate that including our connectivity term in the bid valuation formula improves the performances of the auction scheme.

I. INTRODUCTION

Multi-robot systems (MRSs) are a long active field of research, and their application to surveillance missions have been extensively studied [START_REF] Noreils | Toward a robot architecture integrating cooperation between mobile robots: Application to indoor environment[END_REF], [START_REF] Parker | Adaptive heterogeneous multi-robot teams[END_REF]. However, a reliable coordination strategy is needed for an MRS to operate safely and efficiently. An important part of MRS coordination is the Multi-Robot Task Allocation (MRTA) problem, that consists in assigning a set of tasks to the MRS agents [START_REF] Khamis | Multi-robot task allocation: A review of the state-of-the-art[END_REF]. As MRTA is NP-hard, most of the research interested in solving it in real-time scenarios focus on approximate methods.

Among the many methods proposed for MRTA throughout the years, the Market-Based Approaches (MBAs) stand out as some of the most investigated methods. In MBAs, the robots composing the MRS compete for the tasks to be allocated through a market scheme that emulates realworld economic transactions. In particular, a sub-category of MBAs that received much attention are the Auction-Based Approaches (ABAs): the tasks are sold through an auction scheme in which the bidders are the robots [START_REF] Smith | The contract net protocol: High-level communication and control in a distributed problem solver[END_REF]. ABAs excel at efficiently and robustly allocating single tasks [START_REF] Dias | Market-based multirobot coordination: A survey and analysis[END_REF]. However, ABAs require a reliable communication network (CN) for the market scheme to operate properly. For instance, if a robot is disconnected from its teammates, it might be unable to communicate its bids. As a result, an ABA might not allocate any task to this robot. Hence, a degraded CN leads to a surge in inefficiencies. Moreover, the CN typically evolves dynamically, as robots move farther apart. Yet, few works are dedicated to improve the CN in ABAs for MRS.

To address this issue, Sheng et al. proposed an improved ABA that accounts for the CN connectivity by managing the pairwise distance between robots [START_REF] Sheng | Distributed multi-robot coordination in area exploration[END_REF]: robots are rewarded for staying close to their teammates. However, this approach does not account for a major element that disturbs communication: physical obstacles may block two robots from communicating regardless of their closeness. In real-world scenarios, such obstacles could severely degrade the CN and 1 Authors are with ONERA/DTIS, University of Toulouse, France firstname.name@onera.fr create isolated areas. In this paper, we will study a surveillance scenario taking place in the environment displayed in Fig. 1. In this environment, buildings can prevent teammates that are very close, in terms of distance, from communicating. To address this issue in the context of auctionbased approaches, we introduce a pricing method that aims at preserving a well-connected CN by considering the CN topology. Our method consists in penalizing allocations that may partition the CN into smaller components connecting disjointed robotic sub-teams, while rewarding allocations that merge CN components into larger components connecting robots through multi-hop communications. We apply this pricing method to a dynamic surveillance mission performed by a team of heterogeneous robots with different moving and sensing capabilities. During the mission, the requirements for surveying some positions evolve dynamically. After a review of the relevant literature, we will explicit the mission that we study and describe the ABA scheme that we use. We then present the bid valuation processes, including the evaluation of our communication-preserving term. Next, we detail our experiments and discuss our experimental results. We conclude our paper by summarizing our main results and proposing directions for future research.

II. RELATED WORK

The use of MBAs to solve MRTA is a long-studied issue [START_REF] Dias | Market-based multirobot coordination: A survey and analysis[END_REF], and many improvements to ABAs were introduced to adapt them to more sophisticated requirements that arise in multi-robot surveillance missions: allocating complex tasks using task tree decomposition [START_REF] Elmogy | Market-based dynamic task allocation in mobile surveillance systems[END_REF], managing robots joining or leaving the team [START_REF] Poulet | Auction-based strategies for the open-system patrolling task[END_REF], re-auctioning tasks to robots with lengthy patrol paths to improve a minimax criterion [START_REF] Hwang | Cooperative patrol planning of multi-robot systems by a competitive auction system[END_REF], or including a monitoring agent that redistributes tasks of underperforming robots [START_REF] Pippin | Performance based task assignment in multi-robot patrolling[END_REF].

However, ABAs depend heavily on reliable communications, as the quality of the obtained allocations depends greatly on the loss rate of bid messages. In general, the performances achieved by ABAs decrease as the CN becomes less reliable [START_REF] Kalra | Comparative study of market-based and threshold-based task allocation[END_REF]. Otte et al. [START_REF] Otte | Auctions for multi-robot task allocation in communication limited environments[END_REF] conduced a comparative study including many ABAs variants, in a context of degraded communications. The authors showed that all variants perform worst as the message loss probability increased. When the mission objective is to minimize the robots path length on a randomly generated map, the numerical experiments of [START_REF] Otte | Auctions for multi-robot task allocation in communication limited environments[END_REF] produced mixed results, as no ABA variant was better than the others across the whole spectrum of message loss probabilities. It is clear that unreliable communications are very detrimental to the quality of the MRTA solutions produced by ABAs, which motivates works aiming at developing and assessing strategies that account for communications when solving MRTA.

To address these issues, many authors have focused on improving the communication protocols among teammates. Ferri et al. [START_REF] Ferri | A market-based task allocation framework for autonomous underwater surveillance networks[END_REF] proposed a method to reduce communication requirements using a Single-Item Auction (SIA) scheme. Auctioneers only send the announcement messages to the bidders with which they immediately share a communication link in the network. The method proposed in [START_REF] Madhyastha | Online scheduling of a fleet of autonomous vehicles using agent-based procurement auctions[END_REF], built upon an SIA scheme, allows for proxy agents to gather and filter bids from neighbor agents. Mezei et al. [START_REF] Mezei | Auction aggregation protocols for wireless robot-robot coordination[END_REF] allowed robots receiving an announcement to decide whether they must relay it to subsequent teammates in the network based on an estimation of their bids. Bai et al. [START_REF] Bai | Distributed task assignment for multiple robots under limited communication range[END_REF] used an information consensus procedure to merge the local data of neighboring robots before carrying auction rounds. A score that accounts for the availability of robots has been introduced in [START_REF] Yun | A contract net protocol based on information intermediary service in multi-agent system[END_REF]; this score depends on the number of task announcements received by a robot: robots with a bad availability score do not engage in further auctions. However, these approaches decrease the communication requirements, but does not improve the ability of robots to share information.

An alternative to ensure a stable CN would be to design a bid valuation formula that accounts for the network's quality, and encourages robots to favor tasks that would maintain a well connected CN. To the extend of our knowledge, the only work proposing such a communication-related bid formulation is the work by Sheng et al. [START_REF] Sheng | Distributed multi-robot coordination in area exploration[END_REF]. In their study, the authors defined a measure called the nearness measure, whose purpose is to evaluate the proximity of a robot to its neighbors. More precisely, robots receive rewards that increase when the distances between them and their teammates decrease, multiplied by a factor that decreases for each subsequent neighbor after the nearest. This allows for robots to spread evenly on the map. This measure is used in the bid formula to try to maintain a connected CN during the task allocation process. Simulation experiments showed that it improved the quality of the produced solutions [START_REF] Sheng | Distributed multi-robot coordination in area exploration[END_REF]. However, this method takes the distance between robots as the metric for communication quality, which does not hold when obstacles prevent communications, as discussed in the introduction.

In this paper, we then propose to integrate in the bid formula a new communication-preserving term based on the connectivity of the CN, and in particular on the number of robots in the connected components of the CN, rather than on the distance between robots. We then evaluate and discuss the interest of this new term in a real-world scenario including obstacles that may disrupt communications, preventing neighbor robots from communicating even if they are very close.

III. PROBLEM FORMULATION A. Surveillance Scenario

In this paper, we consider an area surveillance mission performed by a team of robots. Robots are able to communicate via a multi-hop CN. The mission takes place on a known area represented by a graph G = {W, E}. Robots must survey the waypoints W as often as possible and are only allowed to move through the edges E of the graph. We consider the instantaneous idleness of the waypoints, defined by Equation ( 1), as the metric to determine the effectiveness of the proposed algorithms,

I w (t) = t -t w last (1)
where t ∈ R + is the current time, and t w last ≤ t is the last visit date of waypoint w. We denote by t last the vector of last visit times t w last , w ∈ W. The mission's objective is to minimize the maximum idleness among all waypoints during the whole mission, as described by Equation ( 2). This objective ensures that any allocation that left a waypoint without surveillance is disincentivized. Such modeling have been long used in multi-robot surveillance missions [START_REF] Machado | Multiagent patrolling: An empirical analysis of alternative architectures[END_REF], [START_REF] Sempe | Adaptive patrol for a group of robots[END_REF], [START_REF] Yan | Multi-robot patrol: A distributed algorithm based on expected idleness[END_REF].

min max

w∈W I w (t), ∀t ∈ [0, t e ] (2)
with t e the ending date of the mission. To solve this problem, we use a team of robots denoted R. Each robot r ∈ R is described by its type T ∈ T . Robots of the same type have identical moving speed v T and communication range c T . They are also equipped with the same set of sensors S T . Each waypoint w ∈ W requires a specific set of sensors to be surveyed, that we denote S w ⊂ S. The minimization of the maximum idleness described in Equation ( 2) is constrained by the ability of different robot types to survey each waypoint. Robots that are not equipped with at least one relevant sensor for a given waypoint, i.e. S T ∩ S w = ∅, are not able to survey it. We also assume in this paper that robots are able to determine their position exactly.

ABAs are distributed decision making algorithms. Therefore, robots need to share information with their teammates through a multi-hop network, in order to build a local knowledge of their environment and of their teammates' behavior. In ABAs, robots must share the auction announcements and bids among as many robots as possible to allow the auction round to result in the most efficient feasible allocation [START_REF] Otte | Auctions for multi-robot task allocation in communication limited environments[END_REF]. In the multi-robot patrol scenario, the allocated tasks, and the latest visit dates of waypoints are also essential to compute relevant auction bids [START_REF] Yan | Multi-robot patrol: A distributed algorithm based on expected idleness[END_REF]. For these reasons, we want to ensure that the communication network that connects the robots is highly connected.

B. Dynamic events

In real-world environments, robots encounter unexpected events while executing their tasks. Such events are unpredictable and cannot be accounted for when solving the MRTA problem. In particular, we modeled dynamic events representing real-world situations that alter the sensors needed to survey a waypoint. For instance, a change in lighting conditions may prevent standard visual cameras to survey a waypoint, while night vision cameras will still be able to do so. Also, in the presence of smoke, that may appear during the mission, a specific sensor, such as a thermal camera, is needed to gather data.

A dynamic event is then characterized by the triplet (w ∈ W, t > 0, s -∈ S w ). The location of the event is given by w, and its date by t, while s -represents a set of sensors unable to survey w. In other words, this means that at time t, the list of sensors able to survey w will be updated such that S w ← S w \ s -. We consider that the robots are only able to detect these events when trying to survey the concerned waypoint.

IV. AUCTION PROTOCOL

To solve the problem described in Section III-A, we use a Sequential Single-Item Auction (SSIA) scheme [START_REF] Sujit | Distributed sequential auctions for multiple UAV task allocation[END_REF]. SSIAs are a simple scheme to consider task synergies in an ABA. In SSIA, robots auction tasks one after the other, in subsequent auction rounds. Tasks are auctioned one by one, and robots send their bids one at a time, considering their current plan to value the auctioned task. The auctioneer closes a round after waiting for bids for a fixed amount of time, in order to account for unavailable communications.

In the following, we denote by L r the list of items to auction of robot r, and by exec r its list of tasks to execute. To ensure that tasks are reallocated, robots start an auction for each waypoint that they survey successfully. More precisely, when a robot r reaches a waypoint w ∈ exec r , there are two possible outcomes. If r is equipped with one of the sensors required to survey the waypoint, i.e. S T ∩ S w ̸ = ∅ with T the type of r, then the waypoint is considered as surveyed. In consequence, its idleness is reset to 0, it is removed from exec r , and inserted at the end of L r . Otherwise, if the robot does not have one of the required sensors for w, the idleness of w if not reset, it is removed from exec r and inserted at the end of L r . The robot updates its local knowledge of S w , and will not bid for this waypoint in future auction rounds. It also broadcasts this information so that its teammates can do the same.

At each auction round, one of the robots with tasks to sell (i.e. L r ̸ = ∅) takes on the auctioneer role, which means that it is in charge of the announcement of the auction: this robot sends task specifications to as many teammates as possible. The auctioneer gathers its teammates' bids, and evaluates them to determine which teammates will receive the task. The teammate receiving the task adds it to its execution set exec r .

The bid valuation function is one of the most important elements of an ABA. It determines the winner of each auction round. In this section, we present two terms proposed in the state-of-the-art to estimate waypoints idleness and the CN quality through a nearness measure. We then present the novel term we propose to estimate the CN quality through a computation of its connected components.

A. Idleness term adapted from Yan and Zhang (2016) [START_REF] Yan | Multi-robot patrol: A distributed algorithm based on expected idleness[END_REF] When robot r has to bid on waypoint w, the term proposed in [START_REF] Yan | Multi-robot patrol: A distributed algorithm based on expected idleness[END_REF] estimates the idleness of w when r will survey it. To do so, this term compares the instantaneous idleness of w (as known by r) with the travel time needed by r to reach waypoint w. We adapted the term proposed in [START_REF] Yan | Multi-robot patrol: A distributed algorithm based on expected idleness[END_REF] to our SSIA protocol, resulting in the formula given in Equation (3),

J r (t, w) = 1 + t -t r last (w) d(r, w)/v T (3)
where t ∈ R + is the time at which the computation occurs, t r last (w) ≤ t is the last visit date of waypoint w, T ∈ T is the type of robot r, and d(r, w) ∈ R + is the length of the shortest path from the position of r's last target, to w. However, Equation (3) gives much higher values than the other terms described further in Equations ( 5) and ( 6), making them irrelevant. Therefore, we must normalize J r between 0 and 1 so that its values are consistent with the other terms used in our bid formula, resulting in the term given in Equation ( 4),

I r (t, w) = J r (t, w) 1 + J r (t, w) . (4)
B. Nearness measure from Sheng et al. ( 2006) [START_REF] Sheng | Distributed multi-robot coordination in area exploration[END_REF] In this paragraph, we describe the nearness measure as defined in [START_REF] Sheng | Distributed multi-robot coordination in area exploration[END_REF]. The nearness measure is given by Equation (5),

S r (t, w, d) = e - d 1 c T + λe - d 2 c T + ... + λ n k -2 e - dn k c T (5)
where d = {d 1 , ..., d n k } denotes the pairwise distances between robot r and the robots it is able to communicate with through multi-hop communications, sorted in increasing order. λ is a factor smaller than 1, such that each subsequent robot after the nearest neighbor is valued exponentially less than its predecessor. This ensures that robots are not rewarded for staying in very tight groups, and instead spread quite evenly on the map.

C. Term rewarding the network's connectivity

To preserve a highly connected CN, we introduce a communication term K r (t, w) described in Equation ( 6),

K r (t, w) = C N t + d(r,w) vr , r |C (N (t), r)| -1. (6)
In this term, N (t) = (R, F) is a graph describing the communication network at time t, with F the pairs of robots able to communicate with each other, and C(Γ, r) the connected component of graph Γ that contains robot r. Note that each robot maintains a local version of N (t), so the computation of K r (t, w) is done using only r's local knowledge. To keep N (t) up-to-date, robots may periodically broadcast pings to check with which teammates they can communicate. However, for simplicity, this aspect was handled through a centralized dispatcher that feeds the CN to each robot. This term is the ratio between the number of robots in the same sub-CN as the bidder robot r at the starting date t of the auction, and an estimation of the number of robots in the same sub-CN as r at the future date t + d(r,w) vr when r will reach the auctioned waypoint w. To compute this second number, we must predict the positions of r's teammates in the future, which necessitates an up-to-date local knowledge of teammates' arrival dates. Formally, we define the number of robots in r's sub-CN as the cardinal of the connected component that contains r in the topological representation of the CN. Note that we subtract 1 to the ratio to ensure that K r (t, w) is negative if allocating w to r would decrease the number of robots in its sub-CN.

D. Aggregated bid formula

In the forthcoming experiments, we will combine the idleness cost I r with the communication-oriented costs, S r and K r , to build the bid valuation formula. More precisely, the main contribution of this paper is to demonstrate the benefits of using K r together with I r to build the bid valuation formula, as described in Equation (7a), in order to solve dynamic scenarios through an SSIA scheme. We will compare our approach with a bid valuation consisting of I r alone, and with a bid valuation consisting of I r together with S r , as described in Equation (7b),

B r (t, w) = I r (t, w) + K r (t, w), ( 7a
) B r (t, w, d) = I r (t, w) + S r (t, w, d). ( 7b
)

E. Shared Data

In order to compute their bids on the auctioned tasks, the robots need to share data about the current state of the mission. Robots share their local knowledge to the best of their abilities through multi-hop communications, i.e., to every teammate that is in the same sub-CN. First, to evaluate the idleness cost I r described in Section IV-A, robots have to share their knowledge of the last visit dates for each waypoint w in order to assess the idleness of the waypoints. To do so, each robot r ∈ R maintains a local version of t last , denoted t r last , that is updated when receiving this value from another robot. Robots send an updated version of t r last to their teammates after surveying a waypoint. Upon reception of such message, robots update their list of last visit dates by keeping the element-wise minimum of the received list and their local list. In addition to the last visits dates, robots also need to know the expected paths of their teammates, as they are needed to predict the robots' future positions in order to compute the communication costs presented in Sections IV-B and IV-C. The expected path of a robot is modified only when it receives an award after winning an auction. In consequence, sharing this information do not add much to the communication load, as a unique message is necessary per auction round to maintain an up-to-date version of the expected paths among all robots. Note that the maximum size of this message is attained when a single robot is awarded all the waypoints, and therefore the maximum size of the message is |W|.

V. SIMULATION EXPERIMENTS

A. Simulation set up

The goal of the experiments described in this section is to evaluate the impact of accounting for the CN's connectivity using the connectivity term K r proposed in Section IV-C. We will compare it with existing ABAs that used the idleness term I r [START_REF] Yan | Multi-robot patrol: A distributed algorithm based on expected idleness[END_REF] described in Section IV-A and the nearness measure [START_REF] Sheng | Distributed multi-robot coordination in area exploration[END_REF] described in Section IV-B. To do so, we made a first set of experiments on randomly generated scenarios in which the environment is structured as a grid. These scenarios consist of 5 × 5 grid graphs from which we remove 8 randomly selected edges and on which we randomly place from 4 to 8 physical obstacles that will block communications. 50 such scenarios were generated for the simulation experiments described in this Section. Figure 2 shows one of the generated environments. Note that the area of the real-world missions is much smaller than the area of the grid graphs. Secondly, we used the realistic surveillance scenario whose graph is given in Fig. 1, with a team of five robots.

We evaluated 3 different methods: a simple SSIA scheme using only the idleness term (denoted B = I in the results), an SSIA scheme using Sheng's nearness measure (denoted B = I + S), and finally the SSIA scheme containing our contribution, i.e. our CN's connectivity term to improve communications in the MRS (denoted B = I + K). To determine the performance of these approaches, we measured the evolution of the maximum idleness among all waypoints. The objective of each method would then be to minimize this maximum idleness.

We set up dynamic events to ensure that the scenario is dynamic, as described in Section III-B. Events are randomly generated such that in average, half the waypoints will require a night vision camera, and a fourth will require a thermal camera. These events have an occurrence date distributed from t = 0 seconds to t = 300 seconds, and each run lasts 1800 seconds so that the MRTA process has time to converge back to a stable solution. Also, this allows us to examine the impacts of the dynamics events on the idleness of the waypoints. The robot's communication range was set to c T = 250 for all robot types.

In our simulations, the ability for a pair of robots to communicate depends on their communication range, and on physical obstacles that may disrupt communications. In particular, we consider that a pair of robots that does not have a line of sight are not able to communicate. In the randomly generated grid instances, physical obstacles are placed randomly on the grid (see Fig. 2). In our real-world scenario, physical obstacles correspond to buildings as shown on the map of Fig. 1, for instance in the top left corner. Once this random selection is done, we keep the same pairs for the three SSIA variants, ensuring that the methods are evaluated on the same configurations.

Figure 3 shows the evolution of the maximum idleness of waypoints, averaged over 50 runs for each SSIA variant. The 99% confidence intervals of these averages are plotted around the main curves.

B. Results

The results for randomly generated instances represented on Fig. 3a indicate that our approach (blue line) allows for a smoother handling of dynamic events when compared with the two other approaches, as it yields consistently lower values for the maximum idleness. The approach using the nearness measure (red line) is largely dominated by both our approach and the baseline SSIA (green line). This was expected: as it tries to improve communication without accounting for the obstacles, the nearness measure is ineffective in improving communications. Therefore, it only disrupts the optimization of the idleness without bringing any benefits. After some time, the three approaches converge to stable MRTA solutions with similar maximum idleness values.

The results from our real-world scenarios of Fig. 3b are quite different. Our approach (blue line) pics higher than the others, but also sooner. This means that it solved many dynamic events at once. In one hand, the height of the pic is explained by quite a few events not being handled before the pic. In the other hand, the earliness of the pic is evidence that all events were handled swiftly. The other approaches handled events more smoothly but also more slowly, as the pic is lower and happens later. In addition, we can see that our approach consistently manages to converge to a much more efficient MRTA solution as time passes. This indicates that the reallocations made by the approach using the nearness measure (in red) and the baseline SSIA (in green) in order to handle the dynamic events, locked them into local minima. Also, the physical obstacles are distributed on the edges of the map, reducing the benefits of the connectivity term with respect to the nearness measure. Obstacles placed on the edges of map do not split the CN into long-lasting disconnected sub-CNs ; robots quickly move around the obstacle and regain access to the full CN. On the contrary, obstacles placed in the middle on the map tend to cause long-term splits in the CN. For instances, on the graph depicted in Figure 2, robots surveying the top left corner of the graph will be disconnected from robots surveying the lower part of the graph. Despite that, our approach was able to outperform the baseline and the approach using the nearness measure by ≈ 34% at the end of the mission.

These results show that using the connectivity cost that we introduced in Section IV-C allows for clear improvements in the maximum idleness yielded by the SSIA scheme. Indeed, our method outperforms the approach using only the idleness term adapted from [START_REF] Yan | Multi-robot patrol: A distributed algorithm based on expected idleness[END_REF] as well as the approach combining the idleness term and the nearness measure proposed by [START_REF] Sheng | Distributed multi-robot coordination in area exploration[END_REF] during most of the duration of the mission. This is true in both the randomly generated grid scenarios, as shown in Figure 3a and the real-world inspired scenarios shown in Figure 3b.

VI. CONCLUSION

In this paper, we studied a dynamic surveillance MRS mission accounting for physical obstacles blocking communications. State of the art methods to solve MRTA for such MRS missions include ABAs, that need a highly connected CN to perform reliably. However, there is no contribution that aims at improving the connectivity of the CN in the existing literature.

To address the issue of maintaining a connected communication network throughout the mission duration, we proposed the network connectivity term, designed to reward allocations that improve the connectivity of the CN. We considered two types of scenarios: randomly generated grids and realworld inspired scenarios. In both scenarios types, a number of dynamic events were randomly generated, causing most of the waypoints to require a specific sensor to be surveyed. To handle these dynamic events, robots had to re-allocate their tasks through an SSIA scheme. However, their communication capabilities were limited by their communication range, and by physical obstacles that may block messages. We produced simulation experiments to compare SSIA schemes using our network connectivity term with similar schemes that either do not consider communication at all, or try to improve communication using the nearness measure, that relies on the pairwise distance between robots [START_REF] Sheng | Distributed multi-robot coordination in area exploration[END_REF].

The results obtained from these experiments show that monitoring the connectivity of the CN using the network connectivity term that we introduced yields better MRTA solutions, as they produce a lower maximum idleness. Our approach allows for a swift and efficient handling of dynamic events in the grid scenarios, and converges to much more efficient allocations in the real-world inspired scenarios.

In future work, it would be interesting to evaluate these methods on a wider range of parameters. Such parameters could include robots' communication ranges, density of physical obstacles in the mission's environment, and proportion of nodes concerned by a dynamic event. We could also explore different graph topologies, such as starshaped graphs. It would also be useful to define new metrics, in addition to the maximum idleness, that account for the robustness of the approach. Finally, it would be interesting to compare the performances of auction-based approaches with some decentralized optimization-based approaches.

Fig. 1 .

 1 Fig. 1. Real-world surveillance scenario. The graph's nodes must be visited by the robots, but require specific sensors. Robots can navigate on the graph's edges. Buildings on the top, left and bottom of the area may block messages.

Fig. 2 .

 2 Fig. 2. Randomly generated patrolling scenario. The cells of the grid that are filled in grey represent obstacles that block communication.

  (a) Randomly generated grid instances. (b) Instances modeling the real-world mission presented in Fig. 1

Fig. 3 .

 3 Fig. 3. Results for the maximum idleness. 50 runs were averaged to obtain each curve. The band around each curve represents the 99% confidence interval of the corresponding mean.


domain: shs.gestion scco nlin

text:
• We can position multinationals at a maximum level of severity while the level of complexity is multiplied by the quantity of national policies with which the company must deal

• Multinationals are among the organizations most particularly exposed to crises : because of their coverage and the interdependence of their activities, they are sensitive to a greater number of possible disruptions.

The special case of multinational a complex system evolving in multiples contexts with multiple dynamics

Keep coherency and promote local adaptation the glocal approach

• Crisis guidelines are most of the time proposed from a unidimensional perspective which is national, and rarely from a multinational, national and regional point of view Performance & subsidiarity ▪ According to the public sanitary data, we consider the Michelin questionnaire's answers legitimates.

▪ A "stroke of luck effect" could evidently preserved the sanitary results of the Michelin workforces in certain areas. However, it is difficult to conceive that such a "stroke of luck effect" manifesting itself in the 13 countries. ▪ The Michelin sanitary results compared to the contamination peaks of the related countries show that a coherent approach of the Group toward the pandemic management was efficient. ▪ According to the heterogeneous legal and sanitary requirements of the 13 countries analyzed, we can consider that the local adjustments to respect these local sanitary and legal contexts were done at the appropriate level.

The subsidiarity didn't generate any loss of coherency of the Michelin pandemic management approach.

Subsidiarity vs Commando-like crisis team

A "corporate commando-like crisis cell" would generate difficult times :

▪ to understand and interpret the context (culture, language, regulation, etc.) which is crucial for the sensemaking, ▪ as it would generate difficulties to get such team legitimate to manage teams and activities they don't know in place of the usual local management teams.

"Responses will be different between governments, multinational companies and individuals, making a variegated response important" Elbe et al. (2013) .

Multinational ransomware preparation

Corporate level

• Central CERT

• Insurance (negociator)

• Red / yellow buttons

Local level

• Local awareness (employees) and surveillance (local IT)

• Local context influence (dependance, regulation, law)

• Red / yellow buttons

Real cases study

Vicitms Attackers

Saudi Aramco Cutting Sword of Justice

Merck & Co. Inc.

Russian services (presumed)

Saint-Gobain Russian services (presumed)

Norsk Hydro FIN6

Altran FIN6

Bouygues construction Maze

Colonial Pipeline Darkside (presumed)

A customized multilayer simulation Based on real events

▪

  South Korea (x3), Japan (x3), Malaysia, Thailand, Australia (x2), Philippines (x2), Singapore, Indonesia, successively exceed the reproduction rate of 1. ▪ These countries represent 8 of the 13 countries covered by the ME2AR. ▪ Some of them even exceed an infection rate of 2 (Malaysia, Australia, Thailand and Philippines in March and Singapore in April) and even 3 (South Korea in February) while no infection or infection rate increasing is recorded within the Michelin statistics during all this period of time. Data from OurWorldInData.org Triangulation From the end of February to the end of June 2020

• 2

 2 days simulation (Regions crisis cell, Corporate crisis cell & key corporate dpts) • Pitch : o Romanian HQ managers are informed by their employees that several applications are becoming inoperative o A ransomware screen appears on their monitor o Soon all of Europe ERP is shut down o An employee discloses the information on social networks o A video of the hackers claiming the attack is broadcast on YouTube o These hackers are linked to the terrorist group Daesh • 2 extorsions : o demand of ransom to decipher data o demand of ransom to don't share critical information

glocal approach as a new internodal governance approach (Carney & Bennett, 2014) is totally suitable in the context of a complex crisis with non-linear development

  as it get the benefit of top-down approach (coherence) and the flexibility of bottom-up adaptation (flexibility)

• Multinational have to deal with different regulations, cultures, contexts, and technical environments at the same time. Therefore a bottom-up approach is also required

• A

Crisis management glocal approach model Michelin cases studies Covid-19 pandemic management Michelin E2A Region crisis management 1 Regional

Headquarters (located in Bangkok, Thailand) 8 factories, 10 languages (English, Bahasa, Japanese, Korean, Thai, Vietnamese, Burmese, Khmer, Lao, Tagalog) 13 countries (Australia, New Zealand, Indonesia, Japan, Korea, Malaysia, Singapore, Thailand, Vietnam, Myanmar, Cambodia, Laos, the Philippines)

The Top 5 Take-Aways for Your Organization I. Global coherency is necessary (top-down) II. Local flexibility is mandatory (bottom-up) III. Direction of influence can evolve during the crisis IV. Organizational fractality / subsidiarity helps


text:
Charles Lesire

Rafael Bailon-Ruiz

Magali Barbier

Christophe Grand

A Hierarchical Deliberative Architecture Framework based on Goal Decomposition

Performing a complex autonomous mission with a multi-robot system requires to integrate several deliberative approaches to perform task allocation, optimization, and execution control. Implementing such a deliberative architecture is a complex task: it requires the developer to master the decision algorithms themselves (e.g., automated planning models), to have a good knowledge of the involved robotic platforms, and to think about how these elements will be assembled as a system architecture. We propose a framework to help designing such deliberative architectures. The framework relies on the concept of a hierarchical structure of actors, each actor managing goals with specific planning or optimization approaches, and delegating sub-goals to other actors.

I. INTRODUCTION

The use of autonomous robots (being independent robots or a multi-robot system -MRS) into real-life applications raises the challenge of designing complex deliberative capacities that may cope with different missions, the evolution of the environment, and long-term decision making. Applications like Mars exploration [START_REF] Ceballos | A Goal-Oriented Autonomous Controller for space exploration[END_REF], search-and-rescue [START_REF] Kitano | RoboCup Rescue: A Grand Challenge for Multiagent and Intelligent Systems[END_REF], naval defense [START_REF] Chauveau | Integration of Autonomous Heterogeneous Systems for Decision Making Autonomy in Naval Defense: a Position Paper[END_REF], or service/assistance robotics [START_REF] Di Rocco | When robots are late: Configuration planning for multiple robots with dynamic goals[END_REF], show that such deliberative skills must manage several mission specifications with several objectives and tasks (e.g., search, observe, report).

Hierarchical approaches have been largely used to manage such complex missions. Decomposing tasks or goals through hierarchical reasoning is indeed suited to model missions operational description. Examples of these approaches use Hierarchical Task Network (HTN) planning [START_REF] Erol | HTN planning: Complexity and expressivity[END_REF], [START_REF] Lesire | A distributed architecture for supervision of autonomous multi-robot missions[END_REF], HTN planning combined with motion planning [START_REF] Kaelbling | Hierarchical task and motion planning in the now[END_REF], [START_REF] Silva | An interface for interleaved symbolic-geometric planning and backtracking[END_REF], [START_REF] Bidot | Geometric backtracking for combined task and motion planning in robotic systems[END_REF] or the use of specific procedures within a classical search approach [START_REF] Bernardini | Combining temporal planning with probabilistic reasoning for autonomous surveillance missions[END_REF]. Other works combine task or role allocation at the MRS level with some local planning algorithms [START_REF] Zlot | Market-Based Multirobot Coordination Using Task Abstraction[END_REF], [START_REF] Hunsberger | A combinatorial auction for collaborative planning[END_REF], [START_REF] Carreno | A Decentralised Strategy for Heterogeneous AUV Missions via Goal Distribution and Temporal Planning[END_REF]. More reactive approaches for decision-making also use some hierarchical decomposition of tasks or behaviors. For instance, Behavior Trees implement the autonomous behavior of a system in [START_REF] Colledanchise | How behavior trees modularize hybrid control systems and generalize sequential behavior compositions, the subsumption architecture, and decision trees[END_REF], [START_REF] Albore | Skill-Based Architecture Development for Online Mission Reconfiguration and Failure Management[END_REF].

However, using one of these approaches in a different context or mission may lead to rethink the whole deliberative architecture. In this paper, we propose an architectural framework for hierarchical reasoning that helps to design and manage the evolution and customization of the deliberative reasoning of an autonomous (mono-or multi-) robotic system. Actors [START_REF] Ghallab | The actor's view of automated planning and acting: A position paper[END_REF], the main elements of this architecture, are reasoning components that manage planning and acting of specific tasks within a hierarchical goal decomposition *This work was not supported by any organization 1 Authors are with ONERA/DTIS, University of Toulouse, France firstname.lastname@onera.fr scheme. The architecture thus integrates consistently reactive behaviors and more deliberative processes within the same decision-making architecture.

The state-of-the-art related to hierarchical reasoning and architectures is first discussed in Section II. Section III then presents the architecture designed for a MRS performing a protection mission: this application introduces the main concepts of the proposed framework. Section IV details these concepts and their implementation. Finally, Section V highlights the interest of this original framework through an estimation of the effort to develop 3 robotic use-cases: 2 mono-robot systems, plus the aforementioned MRS protection mission.

II. RELATED WORKS

Hierarchical decision-making that focuses on integrating several planning processes are often limited to the integration of two processes, one for high-level abstract decision-making, and the other for motion or trajectory planning. A planner based on the Planning Domain Definition Language (PDDL) with pre-computed trajectory patterns as basic actions is used in [START_REF] Bernardini | Combining temporal planning with probabilistic reasoning for autonomous surveillance missions[END_REF] to solve searchand-rescue missions. Partially-Observable Markov Decision Process (POMDP) policies for each individual task are called by a classical planner for high-level decision-making and task allocation in [START_REF] Hanheide | Robot task planning and explanation in open and uncertain worlds[END_REF]. Other approaches explicitly use HTNs as decomposition models, either by integrating a specific planner to select leaf tasks of the HTN, mainly for motion planning [START_REF] Kaelbling | Hierarchical task and motion planning in the now[END_REF], [START_REF] Silva | An interface for interleaved symbolic-geometric planning and backtracking[END_REF], [START_REF] Bidot | Geometric backtracking for combined task and motion planning in robotic systems[END_REF], or combining HTN planning with other approaches, like Partial-Order Planning [START_REF] Bechon | Hybrid planning and distributed iterative repair for multi-robot missions with communication losses[END_REF]. While these works may give some hints for the integration of several planning processes using several abstract models, they do not really provide a framework or methodology to integrate more diverse planning processes, and do not allow to integrate acting and reactive processes. T-REX [START_REF] Mcgann | A deliberative architecture for AUV control[END_REF] is an architectural concept where each reactor manages one part of the mission by planning the corresponding system activities and controlling their execution. Reactors form a hierarchical architecture, where higher-level reactors reason on the long-term for the global mission, while lower-level reactors reason on the short-term for specialized systems. Its applications to MRS are limited to architectures where: (1) each robot has its own T-REX deliberative architecture and only exchange data with its teammates [START_REF] Ferreira | Advancing multi-vehicle deployments in oceanographic field experiments[END_REF], [START_REF] Das | Coordinated sampling of dynamic oceanographic features with underwater vehicles and drifters[END_REF], [START_REF] Belbachir | A cooperative architecture for target localization using multiple AUVs[END_REF], or (2) one robot is the leader, owning the complete deliberative architecture, and sending low-level commands to a follower robot [START_REF] Ropero | ARIES: An Autonomous Controller For Multirobot Cooperation[END_REF]. Furthermore, T-REX reactors are restricted to use timeline models for planning and acting.

A similar work proposed in the Mlaras architecture [START_REF] González | Multi-Layered Multi-Robot Control Architecture for the Robocup Logistics League[END_REF] is structured into layers, each layer corresponding to one deliberation. It hence refines the global planning problem into more concrete actions from top to bottom. The design of the architecture is essentially declarative, by relying intensively on PDDL to define the blocks of the system. But we claim that we also need more operational means to define some behaviors that cannot rely on pure automated planning. Also, their architecture contains only one deliberation per layer, which prevents dispatching goals or tasks in parallel to several sub-systems, a mandatory feature in multi-robot systems.

ROSPlan [START_REF] Cashmore | Rosplan: Planning in the robot operating system[END_REF] allows to integrate planners based on the temporal PDDL into a ROS architecture. Its use in a two-tier MRS has been evaluated in [START_REF] Carreno | Multi-agent Strategy for Marine Applications via Temporal Planning[END_REF]. The architecture contains only a goal allocation node at mission level and a temporal planner node at vehicles level, and no real guideline to design MRS deliberative architecture is given. The MoBaR system [START_REF] Muñoz | MOBAR: a Hierarchical Action-Oriented Autonomous Control Architecture[END_REF] is a three-tier architecture that combines a PDDL planner, the PLEXIL executive, and GenoM or ROS to build autonomous control architectures, but it is limited to mono-robot systems.

In conclusion, none of these works offers a real framework helping the design of hierarchical deliberative architectures that can moreover be used both for mono-robot systems and to decentralize the deliberation for a MRS. In this paper, our objective is to provide such a framework. Our approach combines the concept of the reasoning components actor (introduced in [START_REF] Ghallab | The actor's view of automated planning and acting: A position paper[END_REF] and used for instance in [START_REF] Patra | Acting and Planning Using Operational Models[END_REF]) with the concept of goal lifecycles [START_REF] Roberts | Goal Reasoning, Planning, and Acting with ActorSim, The Actor Simulator[END_REF] to supplement planning capabilities with acting capabilities. Controlling the execution, decomposing planned tasks into executable operations, and reacting to failures and disturbing events remain indeed critical to close the decision loop.

III. APPLICATION TO A MULTI-ROBOT PROTECTION MISSION

Let's introduce the main concepts of the deliberative architecture framework on a protection mission to be performed by a MRS. A team of ground and aerial robots have to protect an area: some robots placed at sentry positions such as buildings and crossroads detect intruders while others perform patrols surrounding the area. An example with three sentries and two patrols is given in Fig. 1. In this mission, when an intruder is detected, an identification task must be performed by some robots to identify the possible threat. Moreover, given the current situation assessment and the possible detected or identified threat, the operator can ask for the exploration of a specific area.

The MRS deliberative architecture for a team of Unmanned Ground Vehicles (UGVs) and Unmanned Aerial Vehicles (UAVs) is depicted in Fig. 2. Its components are either actors (rounded rectangles) or observers (sharp rectangles with italic labels). Deliberative functions are structured as a hierarchy of actors: each actor manages one kind of goal and delegates the management of sub-goals to child actors.

For their part, observers analyze robot state and sensors data to generate adequate events.

The root actor, namely the Mission Control System (MCS), orchestrates the realization of the mission in interaction with human operators through a dedicated user interface. Decision-making in the MCS is described by simple rules that link the activation of sub-goals to either operator inputs or new detected events. Execution of these sub-goals are then delegated to the Protection, Exploration or Identification actors. Events triggering the execution of sub-goals in the MCS actor are generated by the EnvDB observer that manages information about the environment.

The Protection actor manages the execution of a protection goal by first expanding this goal, i.e. decomposing its specification (as illustrated in Fig. 1) into sub-goals allocated to each robot. To do so, it needs information about available robots (including their navigation skills and sensors) and the environment model (navigable paths, associated costs), which comes from the corresponding observers. In practice, this decomposition is computed by solving a Mixed-Integer Linear Programming (MILP) problem that minimizes the time to reach the sentry and patrol locations. The structure of the resulting decomposition is in this case a Partial-Order Schedule that ensures some precedence constraints between sub-goals (e.g., sentries must start before patrols). Once decomposed, the goal is dispatched by delegating the management of sub-goals to child actors. These actors, here directly embedded on robots, manage the execution of goals corresponding to reaching waypoints, patrolling, and performing a sentry.

Focusing on UGVs architecture, the Patrol actor manages a patrol goal by expanding it into a transit to reach the patrol initial position, then the patrol itself on the given trajectory, forward and backward, until a stop condition (a defined time or battery level). Patrol and Transit actors basically use some path planning on graphs to compute paths, using the robot current navigation graph as well as its state (position, battery) available in the StateObs observer. Lowest-level actors that execute elementary goals through a dedicated interface with robots functional layers are called controllers. For instance, they execute path following or sentries by calling services or publishing to topics in a ROSbased robot architecture or using a skill-based interface [START_REF] Lesire | Formalization of Robot Skills with Descriptive and Operational Models[END_REF].

Actors report on the execution of a goal to their parent actor in the hierarchy, so that the latter can monitor the progress of the goal being delegated. These reports can include failures, e.g., if moving on a path becomes impossible due to an environment change or a robot issue. The upper actor can then decide whether to resolve this goal, e.g., by computing a new path, or report again the failure to its parent actor that will for instance allocate the goal to another robot.

IV. A HIERARCHICAL DELIBERATIVE ARCHITECTURE FRAMEWORK

This section details the developed framework to design deliberative architectures such as the one presented for the MRS protection mission. This original framework is based on the concepts of actors hierarchically structured to support goal decomposition, and of observers managing data flow in the deliberative architecture. This framework comes with a practical implementation using the ROS2 middleware.

A. Goal Management in Actors

The proposed architectural framework relies on a hierarchy of actors that leads to a hierarchical goal decomposition. Each actor manages one type of goal and is implemented by the goal lifecycle presented in Fig. 3. This lifecyle has been originally proposed in [START_REF] Roberts | Goal Reasoning, Planning, and Acting with ActorSim, The Actor Simulator[END_REF], where a unique agent, the goal reasoner (GR), manages goals for a unique robotic system. While top goals are formulated by a user, sub-goals are managed internally, the GR inserting these sub-goals in its own queue of goals. We have leveraged this goal lifecycle concept into a hierarchical multi-actor architecture. In the description of lifecycle steps given below, A refers to the current actor that implements this lifecycle, and P refers to its parent actor that delegates to A the management of goals.

1) Formulation: P delegates a new goal to A, through the FORMULATE request, and this goal is added to A's memory as a formulated goal.

2) Selection: P requests A to SELECT a formulated goal. It is then up to A to accept or reject this request. This is typically implemented as checking that there is no mutual exclusion with a goal already selected, or that the goal is valid in the current context (e.g., not out of bounds). For instance, the Protection actor of Fig. 2 verifies that enough robots are available to perform all sub-goals, while the Transit actors check that the target point is reachable in the robot navigation graph.

3) Expansion: P requests A to compute some (generally one, possibly multiple) decomposition of a selected goal into sub-goals. To do so, A's developer implements the EXPAND function with the method of their choice. In the protection mission, such functions are implemented using MILP, graph theory, or hand-written parametric plans. Whatever the decomposition succeeds or fails, the result is notified to P .

4) Commitment: Given the possible decomposition returned when expanding the goal, P confirms (or chooses in case of several plans) the commitment of the goal. A must then be ready for execution, by checking the validity of the plan or asking child actors to commit sub-goals.

5) Dispatching: P requests A to actually start the goal execution. In most of the cases, it consists in A formulating its sub-goals to child actors, then going through their lifecycle until dispatching them, according to the plan structure (e.g., managing sub-goals precedence relation).

6) Monitoring: The MONITOR transition is periodically triggered by actor A while the goal is dispatched. It checks the execution status of sub-goals and reacts to reports. When the current goal is completed (i.e., all the sub-goals succeeded), the goal is finished: the FINISHED state is reported to P , and the goal is removed from A's memory. If any mistake or failure is reported from the sub-goal management (e.g., a sub-goal that cannot be selected or expanded), then the Evaluate transition is triggered.

7) Evaluation:

The Evaluate transition is an internal transition that is triggered by the developer of A when events or reports jeopardize the goal execution. In the Evaluate function, the developer determines which transition to perform given the current information among the possible resolvers that can put back the goal upper in its lifecycle. These resolvers have the same behavior: (1) they try to put the goal back in their corresponding step, calling the corresponding transition as if it was requested by P ; (2) in case of success, they trig the successive transitions to put the goal in the dispatched state again; (3) in case of failure, the resolver just above is applied, following the same behavior. For instance, resolving a goal with Replan will call again the expansion function, computing a new decomposition for this goal. If a decomposition is found, the goal is first committed, then dispatched. If no decomposition is found, the goal is deferred: it is selected, then expanded, down to dispatch. If a transition fails again, the goal is reformed. Reforming a goal is a specific resolver, as it does not try to select the goal again, but reports to P that the goal has been reformed. It is then up to P to decide if the goal must be dropped, or if it must be tried again.

The behavior of resolvers is automatically managed in the framework implementation: the developer has just to call the desired resolver in its Evaluate implementation, and lifecycle management and reports toward P are automatically performed according to the success or failure of transitions.

8) Dropping:

The DROP transition is tailored by actor A's developer to remove the goal from memory and to drop sub-goals that have already been delegated to other actors, when it is required by actor P . 9) Processing events: Actors can subscribe to events (described later). The arrival of new events is managed in the PROCESS transition. According to current situation and state of goals, A's developer decides to call the Evaluate transition of some goals to determine how to react to events.

In the protection mission (Fig. 2), when receiving an event about the detection of a new intruder, MCS replans the current mission to include an identification sub-goal in addition to the existing sub-goals (protection and/or exploration).

B. Actor Patterns

In most cases, a full goal lifecycle is not necessary. We defined then two specific lifecycle patterns in the framework: controllers, and plan/replan behaviors based on Partial-Order Schedules (POS).

Controllers are the actors at the lowest level of the deliberative architecture. They cannot create sub-goals and delegate them to other actors, but instead manage one goal execution with a direct interface to the robot functional layer. Therefore, in their lifecycle shown in Fig. 4a, the EXPAND and COMMIT transitions do nothing specific, as no decomposition must be computed. Also, the controller cannot process external events but only reacts to execution reports from the functional layer, handled in the MONITOR transition. Only reactions are then to Finish the goal in case of success, or to Reform it in case of failure. Fig. 4: Specific lifecycles of some actor patterns (same legend as in Fig. 3).

POS actors manage goal decomposition where sub-goals have precedence relations. Their corresponding lifecycle is depicted in Fig. 4b: due to the known structure of the plan, the COMMIT, DISPATCH, MONITOR and DROP transitions are already implemented: a sub-goal can be executed only once all its predecessors have finished (i.e., successfully). When an error is reported on a sub-goal (which has then been reformed), the evaluation may lead to either consider the subgoal is finished and continue the plan execution, replan to find a new plan, or reform the goal itself and report to the parent actor.

Timed POS actors extend POS actors by considering that sub-goals have an optional dispatch time. They behave as POS actors regarding the precedence checks of sub-goals, but instead of dispatching immediately, the actors set up a timer that delays the execution of sub-goals. These actors are useful for plans that contain time-constrained actions. They can also handle hybrid plans with timed and not timed sub-goals.

C. Data Management

The hierarchy of actors manages goal decomposition, including planning (in the expansion step) and execution control (when dispatching and then monitoring sub-goals). Goals and their current state in their respective lifecycles are the only data exchanged between actors in this hierarchy.

However, actors have to manage other information to reason and to take decisions. Components that provide data on-demand to the actors are called observers.

In the protection mission architecture (Fig. 2), StateObs observers at the robot level manage data related to the robot internal state: current position, battery level, current map, state of sensors, etc. These data are gathered through a specific interface, typically by subscribing to ROS topics. Observers can for instance provide data that actually aggregate information coming from several ROS topics. From the point of view of the design process, having these data centralized into observers has the advantage to make actors independent on how data must be gathered: actors are not bound to specific ROS topics but instead use the data management interface provided by the framework. This makes the actors easier to maintain and reusable between architectures, following the separation of concerns paradigm [START_REF] Radestock | Coordination in evolving systems[END_REF].

For their part, EnvDB and RobotDB observers manage static data that describe the environment in which the mission takes place (e.g., known and unknown areas, reachable zones) and the set of available robots along with their features (e.g., equipped with sensors needed for sentries, nominal speed or battery consumption rate). These information are used by the multi-robot actors that are implementing the task allocation algorithms.

D. Event Management

In some situations, actors do not want to demand the data values, but instead want to be informed when these values change or satisfy some given properties. In our framework, this is formalized using the concept of events. Events are specified using the Metric Temporal Logic (MTL) evaluated on data values [START_REF] Ouaknine | On the decidability of metric temporal logic[END_REF]. This logic allows to have a clear specification of what these events represent, and to use standard tools for their runtime evaluation [START_REF] Ulus | Online monitoring of metric temporal logic using sequential networks[END_REF].

Events are then defined using MTL within observers, based on the data they manage. When actors subscribe to events, they are notified each time the event MTL formula becomes true, through the actors' PROCESS transition. It is then up to the actor's developer to decide how to react to these events. Some default behaviors are already implemented in the framework and can be used by the developer, such as systematically replanning the dispatched goals.

In the protection mission architecture (Fig. 2), the intruder detection event is defined using the MTL formula H 5 (intruder = ∅), specifying that the value of data intruder has not been empty for the last 5 time steps (using the historically operator).

E. Framework Implementation

The framework has been implemented in Python language using ROS2 middleware. Each component, actor or observer, is then a ROS2 node. Communications between these components (i.e., goal requests, getting data, events) are available through a high-level interface: the component developer has never to manipulate ROS primitives to make these connections. The use of bare ROS functions is only needed when developing a controller that must interface with the functional layer through ROS, or when observers need to gather data values in the functional layer from ROS.

Framework implementation only relies on ROS2 topics, with a fine tuning of the underlying Data Distribution Service (DDS) quality of service: it allows to setup the level of reliability depending on the requirements of each connection, and makes use of the liveliness property to detect (dis)connections between actors. The framework library is available at: http://oara-architecture.gitlab.io/

V. DESIGN OF DELIBERATIVE ARCHITECTURES

The framework has been applied to 4 use-cases: (1) the travel standard problem in HTN planning used as a tutorial in the library documentation, (2) the MRS protection mission of Section III, (3) an Earth Observing Satellite (EOS) mission controller that manages the dynamic acquisition of the best targets to photograph, and (4) an Autonomous Underwater Vehicle (AUV) surveying an area.

Use-cases (3) and ( 4) are mono-robot architectures in environments where a high level of autonomy is required, while use-case (2) is a MRS with the need to decentralize the decision between multi-robot components and individual tasks. In this latter case, field experiments with 4 UGVs and 2 UAVs implemented the architecture illustrated in Fig. 2. During these experiments, 44 ROS2 nodes (excluding robots functional layers nodes) were deployed and distributed over 7 computing units.

We assess the relevance of the proposed framework by estimating the development effort of its library as well as of use-cases instances. To do so, we counted the number of Lines of Code (LoC) of ROS packages and estimated the effort in person-month (p.m) using the COCOMO approach [START_REF] Boehm | Software Engineering Economics[END_REF]. Results are reported in Tables I andII Even if the estimated effort is not to be taken as an absolute indication, it allows to evaluate the benefit of using the proposed framework. The development of each use-case required little effort regarding to quite complex architectures. Given the estimated effort of the framework itself, we can guess that the effort of developing each usecase architecture without any framework would have been several times higher.

VI. CONCLUSION

This paper describes a framework to design deliberative architectures for robotic systems. This framework relies on the concept of a hierarchical structure of actors. Each actor manages one type of goal, through a formal goal lifecycle, in which the actor developer can implement specific steps. Sub-goals are then delegated to child actors in the hierarchical architecture. In addition to actors, the framework uses observers to store data and emit events.

This framework has been applied to several use-cases, and the identified advantages are twofold: first, the framework concepts help to design effective deliberative architectures, and second, it reduces the development effort, as shown by measuring the lines of codes of each application.

Fig. 1 :

 1 Fig. 1: Specification of the Protection goal: the MRS must be allocated three sentry positions (depicted with yellow triangles) and two patrolling trajectories (in green and blue).

Fig. 2 :

 2 Fig.2: MRS deliberative architecture for the protection mission. The four UGV architectures are similar, as well as the two UAV architectures, and they have then been grouped to make the figure easier to read. Plain arcs represent goal decomposition requests. Dotted arcs represent data sent from observers to actors.

Fig. 3 :

 3 Fig.3: Goal Lifecycle, adapted from[START_REF] Roberts | Goal Reasoning, Planning, and Acting with ActorSim, The Actor Simulator[END_REF]. Plain transitions are requests coming from a parent actor. Dashed transitions are internal to the actor. Transitions highlighted in pink must be implemented by the actor developer, whereas transitions with italic labels are only triggered in the developer's code.

  .

	Package	LoC	Estimated effort (p.m)
	oara	3, 404	15.66 *
	oara interfaces	162	0.35 †
	oara common interfaces	432	0.99 †
	Total	3, 998	17.01

TABLE I :

 I LoC and estimated development effort of framework packages. The oara package contains the complete library to develop actors and observers, while other packages contain ROS message and service types.

	Use-case Components	LoC	Estimated effort (p.m)
	Travel	5	170	0.37 †
	MRS	20 1, 853	4.59 †
	EOS	11 1, 235	2.99 †
	AUV	5	307	0.69 †

TABLE II :

 II Number of actor and observer components, LoC and estimated development effort of use-cases.

* estimated using the COCOMO basic Embedded model, which corresponds to complex systems, as the oara library has required a deep understanding of the ROS2 and DDS primitives.† estimated using the COCOMO basic Organic model, which corresponds to small and simple software units.