Cooperative Multiagent Patrolling for Detecting Multiple Illegal Actions Under Uncertainty

Aurélie Beynier Sorbonne Universités, UPMC Univ Paris 06 CNRS, UMR 7606, LIP6 F-75005, Paris, France aurelie.beynier@lip6.fr

Abstract-Multiagent patrolling in adversarial domains has been widely studied in recent years. However, little attention has been paid to cooperation issues between patrolling agents. Moreover, most existing works focus on one-shot attacks and assume full rationality of the adversaries. Nonetheless, when patrolling frontiers, detecting illegal fishing or poaching; security forces face several adversaries with limited observability and rationality, that perform multiple illegal actions spread in time and space. In this paper, we develop a cooperative approach to improve defenders efficiency in such settings. We propose a new formalization of multiagent patrolling problems allowing for effective cooperation between the defenders. Our work accounts for uncertainty on action outcomes and partial observability of the system. Unlike existing security games, a generic model of the opponents is considered thus handling limited observability and bounded rationality of the adversaries. We then describe a learning mechanism allowing the defenders to take advantage of their observations about the adversaries and to compute cooperative patrolling strategies consequently.

I. INTRODUCTION

During the past years an increasing focus has been put on multiagent patrolling and threat detection. Security Games have mainly been interested in detecting a single adversary trying to perform a one-shot attack such as a terrorism attack [START_REF] Jain | An overview of recent application trends at the AAMAS conference: Security, sustainability and safety[END_REF]. More recently, some works have investigated a wider variety of patrolling domains like preventing crime in urban areas [START_REF] Zhang | Keeping pace with criminals: Designing patrol allocation against adaptive opportunistic criminals[END_REF], avoiding intrusions on frontiers [START_REF] Agmon | The impact of adversarial knowledge on adversarial planning in perimeter patrol[END_REF], detecting illegal fishing or poaching [START_REF] Fang | When security games go green: Designing defender strategies to prevent poaching and illegal fishing[END_REF]. In such settings, the defenders face multiple adversaries performing frequently and repeatedly illegal actions. For instance, illegal fishing may occur simultaneously on different sites and is a daily problem for cost guards. When patrolling frontiers, police forces have to repeatedly face multiple intrusions on various crossing points. In these contexts, deploying several patrollers able to effectively coordinate and plan their strategies, provide promising opportunities to reinforce security.

Indeed, as shown by Shieh et al. [START_REF] Shieh | An extended study on addressing defender teamwork while accounting for uncertainty in attacker defender games using iterative dec-mdps[END_REF] in the context of a one-shot attack, defender teamwork leads to significant improvement over other approaches. Nonetheless, even if there has been an increasing focus on approaches handling multiple adversaries and frequent illegal actions [START_REF] Fang | Deploying paws to combat poaching: Gametheoretic patrolling in areas with complex terrains[END_REF], [START_REF] Fang | When security games go green: Designing defender strategies to prevent poaching and illegal fishing[END_REF], existing works do not allow for an effective teamwork among defenders. In this paper, we introduce an approach allowing for effective cooperation among several defenders to cope with multiple illegal actions spread in time and space. We consider mobile patrollers that are able to move across their environment. Patrollers will thus have to cooperate in order to choose which sites to visit next. Obviously, in real settings, patrollers will have to cope with partial observability of their environment and uncertainty on action outcomes. For instance, when fighting illegal fishing, cost guards' moves depend on weather conditions. Move duration between fishing spots is thus uncertain. Moreover, cost guards cannot observe all fishing spots at any time of their patrol. In order to compute valuable strategies, there is a need to handle uncertainty on action outcomes and partial observability of the system.

We thus aim at developing cooperative patrolling strategies that detect as much illegal actions as possible, under uncertainty. Patrollers will have to anticipate possible actions of the adversaries at each time-step. To deal with this issue, most existing approaches assume that adversaries are fully rational and fully observe the patrolling strategy. A best response can then be anticipated and a defender strategy is computed using Game Theory. In fact, it is often difficult for the adversaries to obtain full knowledge of the patrolling strategy. Indeed, adversaries are often unable to fully observe the patrolling strategy since they have limited observation capacities, observing the patrolling strategy is risky (the adversary may be detected) and costly (it takes time and consumes resources) [START_REF] An | Security games with surveillance cost and optimal timing of attack execution[END_REF], [START_REF] Fang | When security games go green: Designing defender strategies to prevent poaching and illegal fishing[END_REF]. Moreover, adversaries (mostly humans) often have bounded rationality. Existing approaches assuming full observability and rationality of the adversary thus fail to develop efficient strategies in many real-world settings. Besides that adversaries may have bounded rationality and do not act optimally, their strategies may evolve over time. For instance, illegal fishermen can change their fishing spots based on their accumulated knowledge about cost guard patrols. It is thus difficult for the defenders to anticipate the response of the adversaries to their patrolling actions.

In this paper, we attempt to improve the applicability and efficiency of patrolling teams while facing multiple adversaries that perform multiple illegal actions. To reach that aim, our work makes the following contributions:

• We propose a new formalization of the defenders' decision problem allowing for effective cooperation between the defenders while facing multiple adversaries performing repeated illegal actions over time and space.

• Our approach handles uncertainty on action outcomes and partial observability of the environment. Moreover, we do not make specific assumptions on the observation capacities and on the rationality of the adversaries. • We propose a distributed solving algorithm able to compute online and update patrolling strategies. • We develop a mechanism allowing defenders to build online a model of the adversaries and to detect changes in adversary strategies. Our approach is thus able to handle non-stationary adversary strategies i.e. strategies of the adversaries that evolve over time. This paper first reviews related works and introduces our problem settings. Second, it provides a new formalization of the multiagent patrolling problem with adversaries based on Decentralized Partially Observable Markov Decision Processes (DEC-POMDPs). Third, methods are proposed for the patrollers to compute their action policies and to adapt them to possible changes in adversary strategies. Fourth, experiments on the efficiency of our approach are presented.

II. RELATED WORK

Several approaches have recently been proposed to deal with patrolling in adversarial settings. They involve two kinds of agents: the patroller and the intruder (i.e. the adversary). Existing works make different assumptions about the agents' observability of the system, leading to different kinds of solutions. Many approaches assume that the adversary is able to perform extensive observation of the patrollers and then conducts a one-shot attack [START_REF] Paruchuri | An efficient heuristic approach for security against multiple adversaries[END_REF], [START_REF] Basilico | Leader-follower strategies for robotic patrolling in environments with arbitrary topologies[END_REF], [START_REF] Kiekintveld | Computing optimal randomized resource allocations for massive security games[END_REF], [START_REF] An | Security games with surveillance cost and optimal timing of attack execution[END_REF]. Such a strong adversary has thus full knowledge of the patrolling strategy and the problem can be represented as a leaderfollower decision problem. These approaches refer to "security games". However, in many domains, considering such a strong adversary is not realistic nor optimal. Agmon et al. [START_REF] Agmon | The impact of adversarial knowledge on adversarial planning in perimeter patrol[END_REF], [START_REF] Agmon | Adversarial uncertainty in multi-robot patrol[END_REF] have studied the impact of adversarial knowledge on the patrolling strategies in the specific setting of perimeter patrols. They demonstrated that if the adversary is not a strong one and has no knowledge about the patrol scheme, an optimal deterministic strategy exists. Computing mixed strategies is thus not required.

Most multiagent patrolling approaches do not tackle the issue of cooperation between multiple patrollers since they assume only one patrolling agent or they consider that the same strategy is executed by all patrollers [START_REF] Agmon | Adversarial uncertainty in multi-robot patrol[END_REF]. Recently, Shieh et al. [START_REF] Shieh | An extended study on addressing defender teamwork while accounting for uncertainty in attacker defender games using iterative dec-mdps[END_REF] proposed to combine security games and Decentralized MDPs to enable effective cooperation between several patrollers under uncertainty. The approach computes a defender's team strategy facing a single adversary that performed a prior extensive surveillance phase. In Shieh et al.'s work, the adversary is assumed to be fully rational and chooses to attack the target with the lowest coverage.

When patrolling frontiers or fighting against illegal fishing or poaching, defenders face multiple intruders [START_REF] Fang | When security games go green: Designing defender strategies to prevent poaching and illegal fishing[END_REF]. The objective of the defenders is then slightly different as it consists in maximizing the number of detected illegal actions instead of preventing a one-shot attack. Moreover, the observability and knowledge of the system are often limited: attackers do not have enough time nor resources to fully observe the patrolling strategies. Defenders can thus not count for a best response strategy from the intruders. The defenders have then to consider bounded rationality and limited obsevability of the intruders. CAPTURE framework [START_REF] Nguyen | Capture: A new predictive anti-poaching tool for wildlife protection[END_REF] has been proposed to prevent poaching while facing an uncertain number of poachers and limited observability of the poachers. However, the approach again considers a one-shot attack and does not allow for effective teamwork between the patrollers. Qian et al. [START_REF] Qian | Online planning for optimal protector strategies in resource conservation games[END_REF] relaxed the assumption of a one-shot attack following a prior extensive surveillance and considered several illegal actions while a single protector and an adversary fully observe their opponent's actions. Recently, Nguyen et al. [START_REF] Nguyen | Capture: A new predictive anti-poaching tool for wildlife protection[END_REF] tackled the issue of multiple adversaries performing frequent and repeated illegal actions. The problem is formalized as a repeated game where defense resources have to be deployed on targets at each turn. While this work accounts for learning adversarial strategies, it does not consider effective cooperation between defenders nor uncertainty on action outcomes.

III. PROBLEM SETTING

We address the problem of computing patrolling strategies for m heterogeneous defenders (agents i with i ∈ [1, m]) that have to coordinate to patrol a set of n (with m n) target sites t j (with j ∈ [1, n]) to detect illegal actions. Defenders consist of mobile agents able to conduct surveillance on the targets. The environment topology is represented as a graph G = (N , E) formalizing possible routes between the targets. N = {t 1 , • • • , t n } denotes the set of targets and E is the set of possible routes between the targets.

We consider that uncertainty arises from imperfect action execution and limited observation. A probability distribution C k,j on possible travel durations is thus assigned to each edge e = (t k , t j ) ∈ E of the graph. Since moving from one target to another can take several time steps, it should be noticed that a patrolling agent does not make a new decision at each time step and agents are not fully synchronized.

Like previous works dealing with patrolling in adversarial domains, it is assumed that performing an illegal action is not instantaneous and takes ∆ int time steps [START_REF] Agmon | The impact of adversarial knowledge on adversarial planning in perimeter patrol[END_REF].

As mentioned previously, we are interested in realistic settings where patrollers and intruders have partial observability of each other. Thus, each patrolling agent is assumed to know her own location and only observes adversaries performing illegal actions on the target she is currently patrolling. Note that illegal actions can be performed several times on a same target and several illegal actions can be performed on different targets at the same time. Our framework is thus generic and does not assume a fixed known number of adversaries. The number of adversaries can then evolve over time and is unknown to the patrollers. We do not make any assumption on the full rationality of the adversaries nor their possible cooperation. Instead, defenders will try to anticipate the adversary behavior from the observations made during the patrol.

IV. DECISION PROBLEM FORMALIZATION

Patrolling systems are inherently distributed: at each decision step, each patrolling agent must decide in an autonomous but cooperative way, which target to visit next in order to maximize the global performance of the defenders. Each agent's decision is based on her local knowledge about the adversaries and about the environment. In the following, we show that this distributed and cooperative decision problem can be formalized as a Decentralized Partially Observable Markov Decision Process (DEC-POMDP) [START_REF] Bernstein | The complexity of decentralized control of mdps[END_REF]. In fact, DEC-POMDPs allow for formalizing sequential multiagent decision problems under uncertainty where a set of cooperative agents has to make decisions in a distributed way with partial observabilty of the system.

In real settings, because of limited observability and bounded rationality, it is very difficult for the patrollers to build a full model of the adversaries (and thus to include it in their model of the environment). In fact, patrolling agents cannot observe all the actions of the adversaries and have to make decisions based on limited knowledge about adversary behaviors. On the other hand, the adversaries have bounded rationality and may not always commit to an optimal policy. They also continuously adapt their strategy from their local observations. One of the main difficulty to overcome is that patrolling agents cannot compute a best response of the adversaries to anticipate their behavior. In this paper, we introduce the notion of context formalizing the knowledge of the patrollers about the adversary policy. Patrolling strategies will then be computed based on the current context. In order to cope with the dynamics of the adversary strategy, our approach also proposes mechanisms for the patrolling agents to be able to detect policy changes as soon as possible, to update the context and to adapt patrolling strategies consequently.

A. Background on DEC-POMDPs

A DEC-POMDP is defined as a tuple Ag, S, A, T, O, Ω, R where: Ag = {1, ..., m} is a set of m agents, S is the set of world states, A = {A 1 × • • • × A m } is the set of possible joint actions a = {a 1 , ..., a m } such as a i is the action of agent i, T is the transition function giving the probability T (s |s, a) that the system moves to s while executing a from s

, O = {O 1 × • • • × O m } is the set of joint observations o = {o 1 , ..., o m }, Ω
is the observation function giving the probability Ω(o|s, a) of observing o when executing a from s, R(s |s, a) is the reward obtained when executing action a from s and moving to s .

Optimally solving a DEC-POMDP consists in finding a joint policy π = {π 1 , ..., π m } that maximizes the common performance measure of the agents where π i is the individual cooperative policy of agent i. It has been proved that optimally solving a DEC-POMDP is NEXP-Complete [START_REF] Bernstein | The complexity of decentralized control of mdps[END_REF]. Many works have thus focused on developing efficient solving methods. Despite major advances in the scalability of the algorithms, the size of the problems that can be optimally solved remains limited [START_REF] Dibangoye | Exploiting separability in multi-agent planning with continuous-state MDPs[END_REF]. In fact, approximate approaches often better scale to large number of agents and planning horizon. Moreover, it has to be noticed that most existing approaches perform centralized off-line planning i.e. planning is performed in a centralized way before the execution. Strategy computation can then not be distributed among the agents. Finally, the issues of learning or re-planning during the execution have received little attention so far.

Related models could be considered to formalize our decision problem but they do not fulfill all the requirements of our settings. Interactive POMDPs (I-POMDPs) [START_REF] Doshi | A framework for sequential planning in multi-agent settings[END_REF] include a model of the other agents in the belief state of each agent. However, I-POMDPs assume a fixed set of adversarial models known beforehand. Stackelberg Security Games [START_REF] Jain | An overview of recent application trends at the aamas conference: Security, sustainability and safety[END_REF] assume a known model of the adversary and do not account for effective cooperation during action execution.

B. Patrollers' DEC-POMDP formulation

We now describe how the cooperative patrolling problem can be represented as a DEC-POMDP. Of course, patrolling strategies rely on the current knowledge about the adversaries. However, in our settings, the only observed information about the adversary strategies consists in detected illegal actions. To formalize the information the patrollers have about the adversaries, we propose to use a probability distribution P I defined for each target. P I i (t) is the probability that the adversaries initiate an intrusion on target t i at step t. The probability that none adversary initiates an intrusion on target t i at t is then given by 1 -P I i (t). The probabilities P I i may evolve over time as the patrollers get more and more observations about the adversaries. Moreover, the adversaries may change their strategy. P I is thus non-stationary over time.

Inspired by the notion of modes used in mono-agent POMDP [START_REF] Hadoux | Solving Hidden-Semi-Markov-Mode Markov Decision Problems[END_REF], our approach consists in defining a DEC-POMDP for a given distribution P I which will be referred as the current context of the decision making. As discussed later in the paper, the DEC-POMDP definition will have to be updated as the context evolves.

Actions: At each decision step, an agent must decide for the next target to patrol. An individual action a i thus consists in moving to target t j (t j ∈ N ). Since the execution of an action may last over several time steps, agents may not be synchronized. DEC-POMDPs consider one time unit action duration so, we propose to decompose individual moves from a target to another into a set of consecutive unitary actions. In fact, if moving from a target t k to a target t j takes c kj ∈ C k,j time units, the move is decomposed into c kj successive unitary moves. Although an agent has prior knowledge on the possible durations c kj , she actually knows the effective duration of the move only once it has been fully executed (the agent has reached t j ). During the execution of the unitary moves, the agent does not change her decision and keeps executing the action moving to target t j .

States: A state s t at time t is defined as: the position of each agent, the list of targets where an illegal action has been currently observed, the idleness of each target, the elapsed time of each current move. The position p i of each agent i is a target or an edge of the graph, i.e. p i ∈ {N ∪ E}. The tuple of positions of the agents is denoted by p with p = p 1 , ..., p m . For each target currently patrolled (t i such as t i ∈ p), the state indicates whether an illegal action has been currently observed on this target. The state thus contains the list int of targets where intrusions have been observed at t. The time elapsed since the last visit of each target is called idleness. Each target is assigned an idleness value thus leading to the tuple idle with idle = idle 1 , ..., idle n . δ i denotes the time elapsed since each patrolling agent has left her last visited target, leading to the tuple δ = δ 1 , ..., δ m . The highest possible travel time between two targets gives an upper bound on possible values for δ i . A state s t is thus a tuple of the form p = p 1 , ..., p m , int, idle = idle 1 , ..., idle n , δ = δ 1 , • • • , δ m . To avoid overloading equations, we will denote this state by s t = p, int, idle, δ .

Observations: Each agent observes her current position. If the agent has reached a target, she observes whether an illegal action is currently performed on that target. When an agent is moving from a target to another, she is assumed not to observe adversaries (we limit illegal actions to be performed on the nodes of the graph).

Transition function: Transition probabilities are defined from probabilities on move durations and from probabilities on detection of illegal actions. At each decision step, some agents reach new targets to visit whereas other agents are still on the road between two targets. From a state s t , if an agent i reaches a new target t j , the system moves to a state s t where the idleness of t j is 0, δ i = 0 and p i = t j . Otherwise (i does not reach her next target), δ i is incremented by 1, p i corresponds to the current edge of the agent and the agent does not reset any idleness value (although other agents could change these values). The probability that an agent reaches her target is defined from probability distributions C k,j .

Probabilities on the detection of illegal actions are estimated using the current context P I. When the agent i reaches her destination t j , she may observe an illegal action on t j . The probability w j of observing an illegal action on t j at t is the probability that an adversary initiated such an action within the last ∆ int time steps and it has not been detected yet:

w j (t) = P( min(∆int,idlej ) w=0 I j (t -x))
where Ij(t -x) denotes the event "an illegal action is initiated at t -x on t j ". Using the inclusion -exclusion principle applied to probabilities, w j (t) can be re-written as a sum of probabilities on conjunctions of events I j . The probability of such an event is then given by P I j .

Observation function: Since agents are assumed to always detect illegal actions on the targets they patrol, there is no uncertainty on observations.

Reward function: The reward function is defined in order to reward detected illegal actions. The reward obtained when executing action a from a state s t = p, int, idle, δ and moving to s t = p , int , idle , δ is defined as:

R(s t |a, s t ) = ti∈int R D (t i ) + ti∈p and / ∈int •R P (t i , idle i ) (1)
where R D (t i ) ∈ R * + denotes the reward for detecting an illegal action on the target t i and R P (t i , idle i ) ∈ R * + is the reward for patrolling target t i without detecting any illegal action. In order to guarantee patrolling all targets, R P (t i , idle i ) is proportional to the idleness of the target before being patrolled. Agents are thus encouraged to patrol the targets that were visited a long time ago. Different rewards over the sites can be defined so as to represent the relative significance of the targets.

Since agents have limited observability of the targets and of the adversaries, it has to be noticed that it is not possible to represent non-detected illegal actions in the DEC-POMDP and to take them into account in the reward function.

C. Computation of the current context

Our DEC-POMDP formalization assumes a fixed model P I of the adversaries strategy. This model (also referred as "context") is built by the patrolling agents during the execution of their actions. Of course, as patrolling agents make more and more observations, they obtain a more accurate model of the adversaries.

If patrolling agents are only aware of detected illegal actions, they cannot have prefect knowledge of the probability distribution P I. However, the number of detected illegal actions over the last H time steps can be used to compute an estimate of P I for each target. Let N I i (t -H, t) be the number of detected adversaries on target t i (defined for all t i in N ) between t -H and t. We define the following estimate:

P I i (t) = N I i (t -H, t) t k ∈N N I k (t -H, t) (2)
This definition may appear as a rough estimate but it guarantees the relation: N I i (t-H, t) > N I k (t-H, t) ⇒ P I i (t) > P I k (t). Moreover, this estimate meets our assumption on limited observability and fits nicely to the patrolling agents' objective consisting in detecting as much illegal actions as possible. However, our DEC-POMDP formalization allows for other definitions of P I exploiting possible higher degrees of observability or external knowledge about the adversaries.

Since updating the DEC-POMDP model and the patrolling strategies at each time step from the new current context is too costly (in terms of time and computational resources), we introduce a context horizon T that sets the period of validity of the current context. The DEC-POMDP model is then updated every T steps using the new context computed from the observations made by the patrolling agents over the last H steps. New patrolling strategies will then be executed. Note that T is the planning horizon whereas H is the length of the observation history used to define a context P I.

It has to be pointed out that our approach allows patrolling agents to adapt online their strategies. From the point of view of the attackers, even if they had full observability of the patrollers, the patrolling strategy will then not seem deterministic all along the execution.

V. POLICY COMPUTATION AND UPDATES

For a current context P I, solving the corresponding DEC-POMDP returns a joint policy π = {π 1 , ..., π m } maximizing the global expected reward derived from Equation 1. An individual policy π i allows agent i to decide, from her observations of the system, how to act in a cooperative way. Note that agents usually end with different strategies: the nodes of the graphs are dispatched among the agents taking into account action uncertainty, target rewards and threat levels. Several algorithms have been developed to solve DEC-POMDPs [START_REF] Dibangoye | Exploiting separability in multi-agent planning with continuous-state MDPs[END_REF], [START_REF] Amato | Decentralized control of partially observable markov decision processes[END_REF], [START_REF] Kumar | Point-based backup for decentralized POMDPs: Complexity and new algorithms[END_REF]. They can be used to solve our DEC-POMDP formalization described in the previous section. An optimal policy can then be computed for a given context P I. Each time a new context is deduced from new observations, the patrolling strategy has to be computed again given the new context. However, in our settings, existing approaches suffer from several limitations. First, they perform centralized computation of the patrolling strategy. In fact, even if patrolling strategies can be executed in a distributed way, most existing approaches consider a central entity computing the individual strategies and then broadcasting them to the agents. Each time a new context is considered, such a central entity would thus have to collect all the observations of the patrollers, to compute a new strategy and to broadcast it. This would create a bottleneck in the system and would result in high communication cost. The second drawback of these algorithms is that they have not been developed to exploit learned information and to update strategies during the execution. They cannot re-use previously computed strategies to speed up the computation of a new joint strategy for a new context. Finally, despite recent advances, existing approaches fail to scale to large sizes of problems.

In this section, we investigate evolutionary algorithms to compute approximate patrolling strategies in a distributed way. Such algorithms have already been used to compute approximate solutions for DEC-POMDPs [START_REF] Mazurowski | Solving decentralized multi-agent control problems with genetic algorithms[END_REF], [START_REF] Eker | Solving decentralized pomdp problems using genetic algorithms[END_REF] and showed significance improvement in the size of the horizon that can be considered. In addition, our algorithm allows for exploiting previously computed strategy when considering a new context. We then propose to reduce communication overhead and to improve patrolling performance.

A. Evolutionary Algorithm for policy computation

We propose to adapt the (1+1) evolutionary algorithm [START_REF] Droste | On the analysis of the (1+1) evolutionary algorithm[END_REF] to optimize the patrolling strategy over horizon T . The evolutionary algorithm (see Algorithm 1) selects an initial solution (called champion) and then iterates to improve the champion until a computation deadline is reached. At each iteration, a mutation operator is applied to the current champion thus obtaining a challenger. This new solution is evaluated and becomes the new champion if its value is higher than the one of the current champion. The population of individuals (i.e. set of policies) consists in the set of joint policies that comply with temporal and spatial constraints of the problem. Spatial constraints are fulfilled if each agent always executes an admissible action at each decision step i.e. decides to move to a target directly connected to her current target. Temporal constraints arise from uncertainty on action durations: an agent cannot decide for a new target to visit until she has reached her current target. The initial solution is built from a probability distribution over the nodes reflecting the likelihood of an illegal action on each site deduced from observations. In fact, the higher the probability of an illegal action on a target t k , the higher the probability of selecting t k . Probabilities are also weighted by the visit frequency of the target in the previous context. The mutation of the current champion strengthens the weakest targets: the targets with the lowest probabilities of threats are replaced by the targets with the highest probabilities of threats. This algorithm has the advantage of being anytime and better scales to large numbers of agents and long planning horizon T because of its low complexity. However, it does not provide any guarantee on the quality of the solution regarding the optimum. This issue will be investigated in our experiments.

B. Communication models

Executing our evolutionary algorithm in a distributed way requires the agents to communicate their observations about detected illegal actions. In fact, this information is necessary to deduce the new context. However, communication can be risky (adversaries may listen) and resource-consuming. In order to limit the number of messages, we propose to measure the relevance of the communicated information. An information is communicated to the other agents if it is considered as relevant. We thus measure the distance between the current probability distribution P I and the new probability distribution P I obtained by exploiting the information not communicated so far. To compute the distance between two probability distributions, we use the Kullback-Leibler divergence [START_REF] Kullback | On information and sufficiency[END_REF] which measures the difference between two probability distributions P and Q. The divergence from P to Q is defined as:

i P (i)log P (i) Q(i) .
In order to preserve the symmetry property, we use the pseudo-distance:

D(P, Q) = i P (i)log P (i) Q(i) + i Q(i)log Q(i) P (i)
If the Kullback-Leibler distance is greater than a small β parameter value, the information is considered as being relevant and it is communicated to all teammates. Other measures have been investigated, like the Bhattacharyya distance or the Hellinger distance but, we did not notice any significant difference in the solutions we obtained.

C. Detection of context changes

Although adversaries are assumed to partially observe the patrollers, they may adapt their strategy from their observations of the system. As explained in Section IV-C, observations about the adversaries over the last H steps are used to define a new context every T time steps. In this section, we propose to improve patrolling performance by detecting adversary policy changes during the T time steps of a context. We thus define a mathematical method that studies the variations of the number of detected adversaries det over the H last time steps considered in Equation 2. Empirical studies of the variations of det showed that this quantity significantly decreases when the adversaries change their strategy. The objective of the following method is thus to better detect such decreases by applying the four successive processing operations:

1) Compute a moving average of det t (H) values over the last H time steps for each time step t. 2) Decompose det t values using a finite adaptation of Stieltjes decomposition 1 . This decomposition allows us to identify decreasing components det -of det. 3) Apply a backward finite difference operator:

∇ det -[t] = det - t (H) -det - t-1 (
H) to quantify variations. 4) Threshold the values obtained in the previous step to detect adversarial policy changes. When an adversarial policy change is detected, the current context P I is updated even if the deadline T has not been reached. Note that this method can be applied irrespectively of the solving algorithm. The threshold of the procedure has to be tuned considering the DEC-POMDP formalization of the problem. Small thresholds lead to more sensitive detection but could lead to "false" detection of strategy changes. High thresholds might miss some strategy changes. Anyway, the context will be updated and new policies will be computed once the horizon T is reached.

VI. EXPERIMENTS

We experimented our approach on different sizes of randomly generated graphs. Graph connections and probabilities on action durations were randomly generated. Each node is connected in average to 2/3 of the other nodes. Action durations were randomly drawn in the interval [START_REF] Jain | An overview of recent application trends at the AAMAS conference: Security, sustainability and safety[END_REF][START_REF] Shieh | An extended study on addressing defender teamwork while accounting for uncertainty in attacker defender games using iterative dec-mdps[END_REF]. Initial adversarial strategies were also randomly defined assuming that intrusion probabilities belong to the interval [0.1, 0.5] for a subset of the targets and are 0 elsewhere. For each experiment, the system was executed over at least 400 time steps and the adversaries changed their policies at least once during the execution. Performing an illegal action was assumed to take 10 time steps. Experiments were performed on a computer equipped with an Intel(R) Core(TM)2 Duo processor, 2000 MHz, 8Gb.

A. Performances and scalability

We first studied the detection ratio (number of detected illegal actions / number of illegal actions) over the patrolling mission. We compared the results obtained by our evolutionary algorithm with the optimal solution computed using the MADP toolbox [START_REF]Madp toolbox[END_REF]. Figure 1 gives the detection ratio for small scenarios (2 agents and 5, 6 or 7 targets) executed over 530 time steps. It can be seen that our evolutionary algorithm leads to high detection ratios. In fact, the detection ratio is decreased by only 3% over the optimal 1 For space reasons, we do not detail this decomposition. solution for 5 targets and by 6% for 7 targets. Note that even the optimal approach does not lead to full detection of illegal actions since agents cannot cover all targets within 10 time steps (duration of an illegal action). We then studied the scalability of our approach and tested the performances of the solutions. We were not able to optimally solve problems larger than 2 agents and 7 targets. Nonetheless, our evolutionary algorithm successfully solved problems up to 50 targets and 7 agents (with a deadline of 10 seconds). Larger problems can even be solved by enlarging the deadline of the evolutionary algorithm. We experimented our approach on several sizes of graphs (Figure 2) considering a fixed number of 4 agents. The larger the number of targets, the lower the detection ratio. In fact, as the number of targets increases, it becomes more and more difficult for the 4 agents to cover all the targets and to obtain high detection ratios. In order to guarantee good performances of patrolling agents, a minimum number of agents is required. This number is closely related to the number of targets to patrol and to move durations. In our 4-agent experimental setting, it can be observed that good performances are obtained for graphs smaller or equal to 16 targets. Indeed, our approach is thus able to provide detection ratio of 80% and more. We investigated deeper the influence of the number of agents on the detection ratio. Although all targets cannot be covered at each time step and moving from one target to another takes time (without the ability to make detection), our approach provides good detection ratios for m n. As shown in Figure 3 for a 16-target graph, if m = n, the detection ratio obviously equals to 1. Nonetheless, it can be observed that this value is almost reached with 12 agents. Moreover, considering 6 agents leads to a detection ratio greater than 0.9.

Since the deadline of the evolutionary algorithm and the planning horizon both influence solution quality, we varied Fig. 3: Influence of the number of agents Fig. 4: Influence of the deadline and of the planning horizon the value of these parameters and studied the average detection ratio. As it can be seen on Figure 4 for 5 agents and 16 targets, increasing the deadline of the evolutionary algorithm over 1 second does not significantly improve solutions. Indeed, good solutions are computed within a short delay. Furthermore, increasing the planning horizon T over 10 time steps does not improve the detection ratio neither. In fact, a good setting of the planning horizon results from a trade-off between the number of steps looked ahead in strategy computation and the frequency of updates. Longer planning horizon reduces the frequency of strategy updates (planning is performed every T steps). On the other hand, shorter planning horizons increases the frequency of context and policy updates. More variations are then observed in the detection ratio since agents become more and more myopic and are unable to anticipate future action outcomes and opportunities.

B. Communication model

We have then experimented the influence of using Kullback-Leibler divergence on the number of messages and on the detection ratio. Figure 6 and Table 5 illustrate the impact of limiting communication in a problem composed of 16 targets considering different number of agents. Note that a logarithmic scale is used in Figure 6. We varied the β threshold used to decide whether the message must be sent (β ∈ {5, 10, 15}) and we compared with the approach consisting in always broadcasting observations about the adversaries ("Com"). As shown in Table 5, limiting the number of messages does not significantly decrease the performances of the agents since important information is still exchanged. In fact, new observations are only taken into account once they substantially change the current context. Nonetheless, we noticed a significant decrease in the number of sent messages (Figure 6). In the 5-agents case, the number of messages has been reduced from 574 to 16. β value can be used as a parameter to tune the frequency of communication. In the 5-agents case, while varying β between 5 and 15, the number of messages decreases from 32 to 16. Settings without any communication have also been experimented leading to detection ratios between 0.2 and 0.5.

C. Adversary policy changes

We also studied how the detection ratio evolves over time during the execution (Figure 7). The detection ratio remains stable over the execution except when the adversaries change their strategy. In Figure 7, the sharp decrease in detection ratio around 270 is due to changes in the adversaries policy. This drop is successfully detected using the method described in Section V-C and the agents quickly adapt their strategy. The detection ratio thus returns to its previous level. The less the adversaries change their strategies, the higher the detection ratio. In fact, when the adversaries often change their strategy it becomes more and more difficult to deduce the current context. In highly dynamic problems, the detection ratio falls behind 0.6. Performances could then be improved by introducing more patrolling agents. We presented a new framework for effective cooperation between patrolling agents in uncertain and partially observable domains. We relaxed the hypothesis of a single strong and rational opponent, usually done in existing approaches. We also proposed a more realistic model that accounts for uncertainty on action outcomes. Our approach thus extends existing multiagent patrolling works along several dimensions: multiple cooperative patrollers with limited observability, multiple adversaries performing multiples illegal actions, partially observable adversary strategies which may not be rational and evolving over time, uncertainty on action duration. To our knowledge, our framework is the first attempt to address all these issues together. We formalized the multiagent decision problem as a DEC-POMDP defined for a fixed context formalizing the adversary behavior. We showed how this context can be built from the observations made by the patrollers and we proposed a method to cope with the non-stationarity of adversary behaviors i.e. contexts. Patrollers are thus able to detect changes of adversary strategies and adapt their behavior consequently. We then proposed an evolutionary algorithm which offers an alternative to existing solving algorithms. Our algorithm computes patrolling strategies in a distributed way and is able to re-use strategies of previous contexts to compute a new patrolling strategy adapted to the current context. Future work will explore more complex representations of the adversaries including the temporal dimension in the context. Intuitively, time influences the actions of the adversaries and the likelihood of changes in the adversaries strategies (an illegal action is less likely to occur on a target if such an action has just been detected on that target).

Algorithm 1 (

 1 1+1) evolutionary algorithm champion = RamdomIndividual() championValue = Evaluate(champion) while deadline non reached do challenger = Mutation(champion) challengerValue = Evaluate(challenger) if challengerValue > championValue then champion = challenger championValue = challengerValue end if end while

Fig. 1 :

 1 Fig. 1: Detection ratios of the executed strategies

Fig. 2 :

 2 Fig. 2: Influence of the number of targets

Fig. 5 :Fig. 6 :

 56 Fig. 5: Average detection ratio

Fig. 7 :

 7 Fig. 7: Detection ratio over timeAs shown in Figure8for 4 agents and 16 targets, we varied the number of times the adversaries change their strategy and we studied the impact on the detection ratio. The less the adversaries change their strategies, the higher the detection ratio. In fact, when the adversaries often change their strategy it becomes more and more difficult to deduce the current context. In highly dynamic problems, the detection ratio falls behind 0.6. Performances could then be improved by introducing more patrolling agents.

Fig. 8 :

 8 Fig. 8: Influence of the number of strategy changes


Kei-Léo Brousmiche
email: kei-leo.brousmiche@lip6.fr

Jean-Daniel Kant
email: jean-daniel.kand@lip6.fr

Nicolas Sabouret
email: nicolas.sabouret@limsi.fr

François Prenot-Guinard
email: francois.prenot-guinard@airbus.com

Stéphane Fournier
email: stephane.fournier@airbus.com

The role of emotions on communication and attitude dynamics: an agent-based approach

This paper presents a multi-agent model for simulating attitude formation and change based on individual's affective response to the perception and communication of information. Individuals observe actions performed by social objects, they exchange beliefs about the actions depending on their narrative interest and compute attitude values toward the social objects. The affective response considers the emotional impact of the action for the participants and its unexpectedness. We illustrate, through several simulation experiments, the role of these affective components on attitude dynamics.

Introduction

How would a population react to information from a government or a company (ads) about e.g. any action, product, or innovation? This could be tackled through the concept of attitude dynamics. This notion of attitude derives from social psychology and could be defined as "a mental and neural state of readiness organized through experience, exerting a directive or dynamic influence upon the individual's response to all objects and situations with which it is related" [START_REF] Allport | [END_REF].

In this paper, we propose a multi-agent based simulation model that will help us to better comprehend attitudes dynamics. Our goal is to propose a model that articulates the cognitive and emotional dimensions of attitudes within a population. To do so, we consider agents that construct their attitudes through a rational process as proposed by Fazio [START_REF] Russell | Attitudes as object-evaluation associations of varying strength[END_REF], and we combine this with Dessalles' approach of information interest as a basis for estimating the affective response. We illustrate our approach in the context of stabilization operations simulation: we study how so called "non-kinetic" actions (i.e. that do not rely on effective usage of force) alters population's perception, attitudes and behaviors toward the UN Force.

The next section presents related works on attitude dynamics and on communication for attitude formation. Section 3 presents our agent model and the attitude dynamics. Section 4 presents a first validation of our model on concrete scenarios.

Related works

Attitude dynamics studies diverse complex social phenomena such as the vote, the expansion of extremism or the diffusion of information and could be studied along three different axes [START_REF] Xia | Opinion dynamics: Disciplinary origins, recent developments, and a view on future trends[END_REF]: the representation model of attitude, the communication mechanism and the impact of the interaction network topology. In our work, we will focus on communication mechanism and the attitude model.

Communication mechanism

One dimension we consider in our research for attitude dynamics is the diffusion mechanism where actors influence each other. In most works, the exchanged information is the attitude's value itself [START_REF] Xia | Opinion dynamics: Disciplinary origins, recent developments, and a view on future trends[END_REF][START_REF] Castellano | Statistical physics of social dynamics[END_REF]. While it is true that daily communication is heavily based on attitudinal information (e.g. assessment without arguments, commercials etc.), conversational narratives (reporting facts) also represent a significant part of communication, maybe up to 40% according to Eggins [START_REF] Eggins | Analysing casual conversation[END_REF]. For this reason, we propose to base our attitude dynamics and communication mechanism on beliefs exchange and update rather than direct attitudinal influence. However, social and cognitive psychology have extensively worked on the topic of the interest of information in social communication (e.g. [START_REF] Graesser | Memory for typical and atypical actions in scripted activities[END_REF]). These works tend to define factors and mechanism that intervene in individual's selection of information that are worth to be retained or communicated. In this context, the Simplicity Theory proposed by Dessalles [START_REF] Dimulescu | Understanding narrative interest: Some evidence on the role of unexpectedness[END_REF] seems to present a promising approach to fulfil this task. The main idea of this model is to define information's interest to be communicated or retained by an individual as a function of its emotional impact and unexpectedness level experienced by the individual. Integrating this theory in the communication protocol in our model would enable the agents to select the most convincing beliefs to communicate and also to retain. In this paper, agents will exchange beliefs and will select them according to the Simplicity Theory.

Attitude model

Attitude dynamics mostly depends on the representation model of attitude. The first models of attitudes (e.g. [START_REF] Nowak | From private attitude to public opinion: A dynamic theory of social impact[END_REF]) were based on binary or real values. During the last decade, several works proposed more complex representations of attitudes (e.g. [START_REF] Kottonau | Simulating political attitudes and voting behavior[END_REF]). However, as was pointed out by [START_REF] Castellano | Statistical physics of social dynamics[END_REF], most of these models' focus is limited to the interaction between individuals: they do not consider the construction mechanism of the attitude itself.

Other researches in social psychology study the formation of attitudes at an individual level (e.g. [START_REF] Rosenberg | Cognitive, affective, and behavioral components of attitudes. Attitude organization and change: An analysis of consistency among attitude components[END_REF][START_REF] Russell | Attitudes as object-evaluation associations of varying strength[END_REF]). In these models, attitudes are composed of three components: cognitive, affective and conative. The cognitive part is based on factual information (e.g. beliefs) concerning the social object. The affective dimension corresponds to the emotional response of the subject when he is confronted to the representation of the social object. The conative component refers to previous or intended behaviors that are related to the social object. However, this component is controversial due to its closeness to the cognitive part.

Urbig and Maltz [START_REF] Urbig | Drifting to more extreme but balanced attitudes: Multidimensional attitudes and selective exposure[END_REF] achieved to take into account the cognitive aspect in their model of attitude based on beliefs. Indeed, they proposed to represent attitudes as the sum of the evaluations of the object's features that can be seen as beliefs on the object. While this model constitutes an interesting view on attitude formation, it has two limits with respect to our objectives.

First, the attitude revision is based on the bounded confidence model (e.g. [START_REF] Deffuant | Mixing beliefs among interacting agents[END_REF]): when two individuals have attitude values close to each other, agents converge their attitudes. As a consequence, the attitudes' values are no longer connected to the beliefs of each agents. However, Fazio's model [START_REF] Russell | Attitudes as object-evaluation associations of varying strength[END_REF] of attitude would enable to keep the attitude connected to its forming beliefs, as a set of memory associations between the object and its evaluations based on information concerning the object. Each of these evaluations is weighted by an accessibility value determining the evaluation's degree of reminiscence. By essence, this model maintains a balance between the cognitive representation of the object of the individual and its corresponding attitude.

Second, their attitude model does not embody an emotional component since it represents only the cognitive dimension. Indeed, the evaluation of features does not take into account the affective response to the information. The agents compute their attitudes in a purely rational way. Here again, the Simplicity Theory proposed by Dessalles [START_REF] Dimulescu | Understanding narrative interest: Some evidence on the role of unexpectedness[END_REF] seems to present a promising approach to overcome this weakness. As mentioned above, this theory embodies an emotional component in the computation of the information's interest. Integrating this theory into the beliefs evaluation mechanism of the attitude formation would enable individuals to express their affective reaction.

Hence, we choose to base our attitude representation on the combination of Dessalles' Simplicity Theory and Fazio's attitude representation.

Model

General approach

Our model is based on the following principle: a simulation corresponds to the execution of actions (e.g. tax decrease, recall campaign of a product, attack etc.) by actors (e.g. a political party, a brand, policemen, terrorists or others) on a population. Individuals of the population communicate about these actions with the others and form an attitude toward the actors. In our model, we focus on the interest of an action, i.e. the tendency for individuals to remember it and to communicate about it.

In our model, we consider a set of actors A and a set of individuals Ind. For each i ∈ Ind and actor ∈ A, we denote att(i, actor) ∈ R the attitude of the individual i toward the actor actor. Individuals are characterized by their social group (e.g. ethnic group) and are organized following a small-world communication network topology [START_REF] Milgram | The small world problem[END_REF]. Concretely, each individual i ∈ Ind is represented by a computational agent and is characterized by his neighbors in the communication network Cnt(i) ⊂ Ind -{i} and a social group sg(i) ∈ SG with SG the set of social groups. Each group has a static attitude toward the members of the other group, defined as att(sg 1 , sg 2 ).

As actors perform actions on the population, or communicate about such actions, individuals will build a representation of these actions, which forms their set of beliefs. Beliefs about actions will be the core element in our model: attitudes and communications will be based on these beliefs. We note a(i) the belief of individual i about an action a. Each a(i) is a tuple:

a(i) = name(a), actor(a), bnf (a), payof f (a), date(a)
with:

name the unique name of the action actor ∈ A the actor who performed the action bnf ∈ Ind the beneficiary of the action, i.e. the individual which undergoes the action payof f ∈ R the impact value of the action, negative when the action is harmful (e.g. attack) and positive when it is beneficial (e.g. tax decrease) date ∈ N the occurrence date of the action.

We also compute a perso (a, i) the last occurrence of the action a on the individual i himself (i.e. bnf (a) = i), nbOcc(a(i)) the number of occurrences of the same action and nbOcc SG (a(i), sg) the number of occurrences per social group sg. For this computation, we consider two different a(i) in the belief base to represent the "same action" if they have the same name, actor and bnf.sg. These numbers of occurrences are considered from the agent's point of view only.

Interest of an action

In order to determine what to base their attitude on and what to communicate to other individuals, agents estimate a model of interest of the actions in their belief base. The model of interest is based on the Simplicity Theory of Dessalles [START_REF] Dimulescu | Understanding narrative interest: Some evidence on the role of unexpectedness[END_REF]. This theory proposes to define the narrative interest N I of an information according to the emotion E and the surprise level S it causes to the individual using the following formula:

N I(a) = 2 E(a)+S(a) (1)
E corresponds to the emotional response intensity of the individual when faced to an information, in our model it is based on the payoff amplitude of an action's impact. The surprise level S translates the sentiment of unexpectedness felt by the individual.

Emotional intensity

The emotional intensity E corresponds to the emotional amplitude (non-zero) experienced by the individual when exposed to the event.

Dessalles [START_REF] Dimulescu | Understanding narrative interest: Some evidence on the role of unexpectedness[END_REF] shows that, when the stimulus impact is unbound, the emotional intensity follows a logarithmic law in conformity with Weber-Fechner's law of the stimuli (in our case, the stimuli values correspond to the emotional intensity of an action through its payoff):

E(a) = log 1 + |pyf (ip(a))| ξ (2)
The parameter of sensibility ξ ∈ [0, 1] modulates the emotional response's intensity value.

Surprise Following Dessalles' theory, the surprise experienced by an individual when exposed to an event derives from a level of raw unexpectedness U raw (e.g. "It is surprising that a Taliban saves a citizen"). This level is reduced by a personal reference of unexpectedness U perso based on a personal experience (e.g. "But I have once been saved by a Taliban before"):

S = U raw -U perso (3)
In the Simplicity Theory, several dimensions are considered for the computation of surprise (e.g. geographical distance, recency etc). In our model, we use two dimensions: the temporal distance and the social distance, which lead to four unexpected values: U time raw , U social raw , U time perso and U social perso . The following subsection presents the computation of these four elements.

In all four cases, the unexpectedness of the event (in our model, the action) can be defined by the contrast between its generation complexity and its description complexity: U x = C x w -C x d with x the dimension. The generation complexity C w defines the level at which it could be anticipated by the individual based on its current knowledge base. The description complexity C d must be understood in the meaning of Shannon's information theory [START_REF] Shannon | The mathematical theory of information[END_REF], i.e. the size of the smallest computational program that could generate this event.

Raw temporal distance (U time

raw ) The temporal complexity of generation refers to the probability that the action occurs at a given instant. This notion could be interpreted as the usual time gap between two occurrences of the action: the more the action is rare, the bigger the gap is, the less it is probable, the more it is unexpected.

Therefore we define the usual time gap using the difference between the occurrence date date(a) of the action a and its last occurrence date date(a old ): C time w = log 2 (date(a) -date(a old )). The temporal complexity of description corresponds simply to the elapsed time between the action and the current time t:

C time d = log 2 (t -date(a)).
Thus, the unexpectedness level for the temporal dimension is obtained by:

U time raw (a) = log 2 (date(a) -date(a old )) -log 2 (t -date(a)) (4)
Raw social distance (U social raw ) The social complexity of generation refers to the probability that the action occurs on a beneficiary who belongs to a particular social group (e.g. "It is rare that Pashtuns are victims of a Taliban attack"). We define it with C social w = -log 2 ( nbOcc SG (a,sg(i)) nbOcc(a)

) with nbOcc SG (a, sg(i)) the occurrence number of the action a whose beneficiary is a member of the same social group sg(i) as the agent.

The description complexity C social d corresponding to the social distance between the individual and the beneficiary of the action depends on two factors: the distance in the social graph and the average degree in the graph. Indeed, the higher the degree, the more complex it will be to describe a single step in the graph (in terms of information theory) and this influence is linear. However, the distance in the graph has an exponential impact on the social distance generation (since it requires to describe all possibilities at each node). Thus, C social d = log 2 (v d ) with v the degree of the graph and d the shortest distance between i and bnf (a(i)) in the graph.

Hence we obtain the following formula:

U social raw (a) = -log 2 nbOcc SG (a, sg(i)) nbOcc(a) -log 2 (v d ) (5)
Personal temporal distance and personal social distance The personal unexpectedness is based on the last occurrence of the action a which has personally affected the individual, i.e. the last occurrence of the action (with the same name and actor) for which bnf (a) is the agent i itself. We denote a perso this particular occurrence. The computation of the unexpectedness values is the same as above, except that the search of experienced occurrences in the belief base is limited to actions with i as the beneficiary:

U time perso (a) = log 2 (date(a) -date(a perso )) -log 2 (t -date(a)) (6)
U social perso (a) = -log 2 nbOcc SG (a perso , i) nbOcc(a)

where date(a perso ) denotes the date of the last time the action happened to the subject, and nbOcc SG (a perso , i) the number of occurrences for this action. In the case where the individual has never personally experienced the action, his personal unexpectedness is nil, U perso = 0.

Subjective narrative interest

In order to take into account the attitude of the individual i toward the action's beneficiary, we propose to weight the narrative interest N I by the absolute value of his attitude. Indeed, the more the attitude toward the beneficiary is high, the more the interest of communicating it increases:

SN I(a, i) = |att(i, a.subj)| × N I (8)

Communication

In our model, actions can be perceived via direct perception (the agent is beneficiary of the action), actor's communication toward the population (the agent receives a message from the actors) or intra-population communication (the agent receives a message from another individual). While the first two cases are scripted in the scenario, the intra-population communication is based on the list of contacts of the agent (Cnt(i)) and the subjective interest of the action SN I(a(i)).

At each time step of the simulation, the agent considers all actions perceived at this step. It performs a probabilistic selection of some actions, based on their subjective interest, and distributes messages about the selected actions randomly to its contacts.

Let sni max (t) be the maximum sni for actions received at this time step. For each action a and for each contact j, the probability that agent i sends a message about a to j is p sending (a) = SN I(a) nimax .

Attitude computation

When the agent receives a new information about an action a, it adds it to its belief base (if the action is not already present) and, possibly, communicates about it. Moreover, the agent revises its attitude toward the actor of the action. Our model of attitude construction is based on the model proposed by Fazio [START_REF] Russell | Attitudes as object-evaluation associations of varying strength[END_REF] (see section 2.2) as in [START_REF] Brousmiche | Modelling the impact of beliefs and communication on attitude dynamics: a cognitive agent-based approach[END_REF]. In our case, the accessibility of an action is the subjective narrative interest SN I(a(i)) since the retention interest and the narrative interest are equivalent in cognitive psychology. Also, the benefit is the action payoff weighted by the attitude toward its beneficiary (as proposed by Fishbein and Ajzen [START_REF] Ajzen | The influence of attitudes on behavior[END_REF]):

benef it(a) = payof f (a) × att(i, bnf (a)) (9)
Let aList(i, actor) be the list containing the actions performed by the actor in the belief base of agent i. The attitude att(i, actor) of the individual i toward the actor is given at each time of the simulation by:

att(i, actor) = a(i)∈aList(i,actor) benef it(a) × SN I(a, i)) |aList(i, actor)| (10)

Simulation results

This section presents two experimental studies of our model to analyze the impact of some key parameters on the attitude dynamics in the context of a stabilization operation. First we evaluate separately the impact of emotion E versus surprise in the narrative interest N I (4.2). Second, we consider the impact of social groups by comparing two different scenarios. Beforehand let us describe the experimental settings.

Simulation settings

All experiments are based on a set of shared parameters settings:

Population: The population is split into three social groups (ethnic group A, B and C) each composed of 33 individuals connected by an interaction network based on a small-world topology. In the first experiment, there is no inter-group attitude (the population behaves as a single social group). In the second experiment, we introduce inter-social group attitudes. We denote the attitude of the individual i belonging to the social group SG X toward the individual j belonging to SG Y att(i, j) = sgAtt(X, Y ). Theses static attitudes are defined as follows: sgAtt(A,B)=0.8 ; sgAtt(A,C)=-0.5 ; sgAtt(B,C)=-0.2 (i.e. social groups A and B are allied against a third group C).

Actor: Only one actor representing the Blue Force (e.g. UN) is sufficient for our experimental needs. The initial attitudes of all individuals toward this actor is set to zero.

Scenario: People are confronted to a series of actions with a payof f = 1 performed by the actor every 5 time steps (e.g. the UN brings food and medic once every two days). In the first experiment all the social groups are affected evenly (random selection on the whole population). In the second experiment we will compare two alternative scenarios: in the first version (called S1) the actor affects only random individuals of social group A ; in version S2, three phases will affect in order the social group SG A , SG B and finally SG C . Each phase last 30 ticks and affects random people of the corresponding social group. The total amount of action that occurs remains the same across the two scenarios.

Default parameter: ξ is set to 1. In this paper we do not study the sensibility of the model to ξ.

Analysis of narrative interest components' impacts

The narrative interest is composed of two key components (see section 3.2): the emotional impact E and the surprise S. To analyze the impact of these components on the attitude dynamics, we introduce α and we change the definition of N I into: N I = 2 E+α×S . Varying α comes to modify the balance between the emotional intensity and the surprise factors in the narrative interest. The smaller is α, the more emotional and the less surprised will be the agents. When α is very small, the agents tend to ignore the impact of past occurrences of the actions to compute their attitudes. In the case where α = 0, the agents will base their attitude only on the emotional impact of the action's occurrences which remains static. Therefore, their attitudes reach the top value and remain stable once all agents have been aware of the information (see figure 1a). The figures 1 show the evolution of attitudes dynamics with α ranging from 0 to 1. Since the communication mechanism is stochastic, each presented result corresponds to a mean curve obtained over a hundred simulation runs. We can notice three phenomena:

-The attitude value is boosted with the surprise factor: with α growing, the mean of attitudes reaches a higher value. This was predictable since the surprise factor is added to the accessibility of beliefs: its effect results in increasing the attitude value. Moreover, the figure 1f shows that the attitudes' mean increases following a logarithmic law between 0 and 30. This shape is due to the logarithmic components of the surprise. -Habituation effect: in all simulations, the attitudes decrease after t 30. The repeated perception of the action's occurrences are no more beneficial for the actor since additional occurrences only affects negatively the attitudes. This effect is due to the growing number of people directly affected by the occurrences. Thus they reduce their surprise using their personal occurrences (see equation 3). -The mean value reaches a plateau: when t > 40, the attitudes' mean remains stable. This stationary state is due to the fact that all the agents have experienced personally the action and also to the fact that the time period between occurrences is stable: the values of both time distance and social distance surprises have reached a threshold value among the whole population.

In further experiments, we analyzed the effect of α > 1 and discovered that it has only an impact on the scaling: the shape of the attitudes means' curves remain unchanged while the scale increases. Therefore, we will use α = 1 in the following simulations. In our model, agents are sensible to the beneficiary's social group, and their attitude toward this group. To understand the sensibility to this factor, we propose to compare the two scenarios S1 and S2 presented above with the intersocial group attitudes. their different inter-group attitudes toward SG A as presented in section 4.1: the evaluation of beneficial actions on SG A is positive for its ally SG B and negative for its enemy SG C . Since SG B is allied to SG A , its attitude toward the actor follows SG A due to the positive evaluation of the action's benefit (see equation 9). Conversely, SG C being the enemy of SG A , the action's benefit is evaluated negatively, thus leading to a negative attitude. This phenomenon is also visible on the three phases of the S2 (figure 2b).

The impact of social groups

Agreement While the three social groups have very different attitudes at the end of S1 (figure 2a) as it was predictable since only SG A is positively impacted, they seem to reach a consensus in the scenario S2. Indeed, the figure 2b shows that despite conflicting evolutions among groups, they converge to 1.5 since they are equitably affected. However, we can notice that the final attitude values of SG A and SG B are very close as they are allied while the "enemy" SG C is apart with a lower attitude.

Conclusion

We proposed a simulation model of attitude dynamics based on socio psychological theories. This model introduces an affective component in the formation of attitude and the diffusion of beliefs through the concept of information's interest which embodies an emotional and an unexpectedness components. Moreover, the introduction of the Simplicity Theory enabled us to only have two paramaters : ξ ¡and α.

We studied the dynamics of this model on several examples that illustrate the impact of theses cognitive components and the inter-social conflicts on the attitudes toward an external protagonist. The first experiment especially showed that repeated actions impacts are not linear. At the beginning, people accentuate their attitudes due to the surprise factor but, after a while, the evaluation is reduced due to an habituation effect. The second experiment presented the impact of having conflicting social groups on the general attitudes dynamics. In particular, we showed that despite diverging evolutions of attitude, when the groups are equitably affected, they tend to reach a consensus. Yet the validation of the socio-cognitive model is a challenging issue. In future works 4 , we intend to conduct deeper analysis the sensitivity of the model and also calibrate it using real world data such as opinion polls and action sequences of individuals. Furthermore, we would like to add a behavioral component to enable population agents to express their attitudes through actions.

Fig. 1 :

 1 Fig. 1: Mean of attitudes in S1 with a varying α

Fig. 2 :

 2 Fig. 2: Scenario comparison

Note that our model is not limited to military applications and can be applied to civilian use: the actors can represent any kind of active social object such as political parties, institutions, companies or brands

Conflicts Figures 2 show the evolution of attitude means per social group in the two scenarios. We can notice that the attitudes of social groups vary in a conflicting manner. At the beginning of both scenario, SG A being affected positively, its attitude towards the actor increases as explained in section 4.2. Besides, we can notice that SG B and SG C 's attitudes are also affected despite that these social groups are not directly affected by the action's occurrences. This is due to the intra-population communication that makes them aware of the ongoing actions on SG A . Along time, more and more individuals come to know the actions, therefore impacting their attitudes. We can notice that the evolution of attitudes of SG B and SG C are opposite. This can be explained by


Fabien Baldacci
email: baldacci@labri.fr

Achille Braquelaire
email: braquelaire@labri.fr

Guillaume Damiand
email: guillaume.damiand@liris.cnrs.fr

3D Topological Map Extraction from Oriented Boundary Graph

Keywords: 3D split and merge, image segmentation, topological structuring

The extraction of a 3D topological map from an Oriented Boundary Graph can be needed to rene a 3D Split and Merge segmentation using topological information such as the Euler characteristic of regions. A presegmentation could thus be eciently obtained using a light structuring model, before proceeding to the extraction of more information on some regions of interest. In this paper, we present the topological map extraction algorithm which allows to reconstruct locally a set of regions from the Oriented Boundary Graph. A comparison of the two models is also presented.

Introduction

The Segmentation process consists in defining a partition of the image into homogeneous regions. Split and merge methods [START_REF] Horowitz | Picture segmentation by a directed split and merge procedure[END_REF] are widely used in segmentation. It consists in alternatively splitting a region, and merging adjacent ones according to some criteria, in order to define a partition of the image. To be efficient, it needs a topological structuring of the partition in order to retrieve some information such as: the region containing a given voxel, the list of regions adjacent to a given one, the list of surfaces defining the boundary of a region, etc [START_REF] Baldacci | 3d image topological structuring with an oriented boundary graph for split and merge segmentation[END_REF].

Several models have been proposed to represent the partition of an image. A popular model is the Region Adjacency Graph [START_REF] Rosenfeld | Adjacency in digital pictures[END_REF], which is not sufficient for most of 3D segmentation algorithms due to the lack of information encoded. A more sophisticated model is the topological map model [START_REF] Damiand | Topological model for 3d image representation: Denition and incremental extraction algorithm[END_REF] that uses combinatorial maps in order to encode the topology of the partition and an intervoxel matrix [START_REF] Brice | Scene analysis using regions[END_REF] for the geometry. It encodes all information required to design split and merge segmentation algorithm including high topological features allowing to retrieve Euler characteristic and Betti numbers of a region [START_REF] Desbarats | Retrieving and using topological characteristics from 3D discrete images[END_REF]. Since high level topological features are not necessary for basic split and merge segmentation algorithms, an other model have been proposed [START_REF] Baldacci | 3d image topological structuring with an oriented boundary graph for split and merge segmentation[END_REF]. This model uses a multigraph called Oriented Boundary Graph (OBG) to encode the topology associated with the same geometrical level than in the topological map model. This second model is both more efficient (table 1) and less space consuming. The space consumption difference cannot be exactly computed because the memory optimized implementation of the OBG is still under development, but unoptimized version show that it will be at least two to four times less space consuming depending on the number of regions and surfaces of the partition. The space consumption can be a critical constraint with large image or with algorithms needing a highly oversegmented partition during the segmentation process. The OBG model is more efficient than the topological map one, it can be efficiently parallelized [START_REF] Baldacci | Parallel 3d split and merge segmentation with oriented boundary graph[END_REF] and is sufficient for split and merge segmentation that does not use topological characteristics of regions as criteria. But this missing information could in some cases be necessary and that is the reason why we have studied the extraction of the topological map of some regions of interest from the OBG. It could also be useful for the topological map model to use a more efficient model for a presegmentation step and extract the topological map from the simplified partition using an algorithm avoiding to traverse all the voxels. Thus this work is suitable both for the OBG model in order to have an on-demand high topological features extraction, and for the topological map model in order to be efficiently extracted from a presegmented image, for which the equivalent presegmentation using topological map is too much time or space consuming.

Image size Image complexity

This paper is organized as follow. In section 2, we describe and briefly compare the two topological models. Then in section 3 we describe the topological map extraction algorithm from the OBG. We conclude in section 4.

Presentation of the Two Models

Let us present some usual notions about image and intervoxels elements. A voxel is a point of discrete space Z Z 3 associated with a value which could be a color or a gray level. A three dimensional image is a finite set of voxels. In this work, combinatorial maps are used to represent voxel sets having the same labeled value and that are 6-connected. We define region as a maximal isovalued set of 6-connected voxels.

To avoid particular process for the image border voxels, we consider an infinite region R 0 that surrounds the image. If a region R j is completely surrounded by a region R i we say that R j is included in R i .

Recalls on 3D Topological Maps

A 3D topological map is an extension of a combinatorial map used to represent a 3D image partition. Let us recall the notions on combinatorial maps, 3D images, intervoxel elements and topological maps that are used in this work.

A combinatorial map is a mathematical model describing the subdivision of space, based on planar maps. A combinatorial map encodes all the cells of the subdivision and all the incidence and adjacency relations between the different cells, and so describe the topology of this space.

The single basic elements used in the definition of combinatorial maps are called darts, and adjacency relations are defined onto darts. We call β i the relation between two darts that describes an adjacency between two i-dimensional cells (see Fig. 1B for one example of combinatorial map and [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF] for more details on maps and comparison with other combinatorial models). Intuitively, with this model, the notion of cells is represented by a set of darts linked by specific β i relations. For example, a face incident to a dart d is represented by the set of darts accessible using any combination of β 1 and β 3 relations. Moreover, given a dart d, which belongs to an i-cell c, we can find the i-cell adjacent to c along the (i -1)-cell which contains d by using β i (d). For example, given a dart d that belongs to a face f and a volume v, the volume adjacent to v along f is the 3-cell containing β 3 (d). Lastly, we call i-sew the operation which puts two darts in relation by β i .

In the intervoxel framework [START_REF] Khalimsky | Boundaries in digital planes[END_REF], an image is considered as a subdivision of a 3-dimensional space in a set of unit elements: voxels are the unit cubes, surfels the unit squares between two voxels, linels the unit segments between surfels-cells and pointels the points between linels (see example in Fig. 1C).

The topological map is a data structure used to represent the subdivision of an image into regions. It is composed of three parts:

a minimal combinatorial map representing the topology of the image; an intervoxel matrix used to retrieve geometrical information associated to the combinatorial map. The intervoxel matrix is called the embedding of the combinatorial map; an inclusion tree of regions. Fig. 1 presents an example of topological map. The 3D image, composed of three regions plus the infinite region R 0 (Fig. 1A), is represented by the topological map which is divided in three parts labeled B, C and D. The minimal combinatorial map extracted from this image is shown in Fig. 1B. The embedding of the map is represented in Fig. 1C, and the inclusion tree of regions in Fig. 1D. The combinatorial map allows the representation of all the incidence and adjacency relations between cells of an object. In the topological map framework, we use the combinatorial map as a topological representation of the partition of an image into regions. Each face of the topological map is separating two adjacent regions and two adjacent faces do not separate the same two regions. With these rules, we ensure the minimality (in number of cells) of the topological map (see [START_REF] Damiand | Topological model for 3d image representation: Denition and incremental extraction algorithm[END_REF] for more details on topological maps).

R 1 R 2 R 3 R 0 00 00
R 1 R 3 R 0 R 2 A B C D
The intervoxel matrix is the embedding of the combinatorial map. Each cell of the map is associated with intervoxel elements representing geometrical information of the cell.

The inclusion tree of regions represents the inclusion relations. Each region in the topological map is associated to a node in the inclusion tree. The nodes are linked together by the inclusion relation previously defined.

Oriented Boundary Graph Model

The second model is composed of a multigraph called Oriented Boundary Graph [START_REF] Baldacci | 3d image topological structuring with an oriented boundary graph for split and merge segmentation[END_REF]. Each node of the graph corresponds to a region of the partition. Each surface of the segmented image corresponds to an oriented edge of the graph. Surfaces and edges are linked by associating an oriented surfel to each edge. Each edge is also linked to a representative linel for each border of its corresponding surface; this is necessary to retrieve the surface adjacency relation (which is used to compute the inclusion relation). Geometrical position of the region relating to its boundary surfaces is retrieved according to the orientation of the embedding surfel and the position of the node (beginning or end of the oriented edge). This graph is sufficient to encode the multiple region adjacency relation, the surface adjacency relation and thus the inclusion relation could efficiently be computed. The geometrical level encoded by an intervoxel matrix is the same as the one used with topological map, and links are defined in order to go both from the geometrical level to the topological one and reciprocally. An example is shown on Fig. 2. This model, contrary to the precedent one, can be directly extracted from the description of the image partition without treatments on the resulting sur- faces. It only needs a strong labelling of the voxels and linels that can be locally computed (by looking at the neighbors of the considered element). For each new label, the corresponding topological element have to be created, and the topological and geometrical elements to be linked themselves. This model requires less processing than the topological map one to be maintained and is so more efficient by avoiding to have each surface homeomorphic to a topological disc. Furthermore, this split algorithm requires only local treatment and could be efficiently computed in parallel [START_REF] Baldacci | Parallel 3d split and merge segmentation with oriented boundary graph[END_REF]. Information encoded by the OBG model are sufficient to design basic split and merge segmentation algorithms. But it could be necessary for some segmentation algorithms to use some high topological features such as Euler characteristic of some regions, either as a segmentation criteria or as a constraint on regions in a merge step. In order to design efficiently those segmentation algorithms it is necessary to build the topological map of a set of selected regions.

Comparison of Both Models

Let us recall advantages and drawbacks of each model. The Topological Map model encodes the whole topology of the partition, from the regions and surfaces adjacencies to the Euler characteristic and Betti number of regions. Computing this map consumes an important memory space and requires a time consuming extraction algorithm. The OBG is an enhanced multiple adjacency graph with an intervoxel matrix associated. It is intended to be simpler than the topological map but also less expressive. It has an efficient extraction algorithm and uses low memory space. But some high topological features such as the characteristics of regions are not encoded. Given a description of the image partition with a matrix of labels, the OBG extraction algorithm have a O(v + s + l) complexity with v the number of voxels, s the number of surfels and l the number of linels, because each operation is proceeded once by element and takes O(1). The topological map extraction algorithm has the same theoretical complexity than the the OBG extraction algorithm, O(v + s + l), for the same reason: each cell of the intervoxel subdvision is processed exactly once. However, the number of operations achieved for each cell is more important, which explains the difference in extraction times.

Advantages and drawbacks of each model could be summarized as follows:

-OBG: enhanced multiple region adjacency graph with an intervoxel matrix embedding • advantages: simple, efficient extraction algorithm, low memory space consumption • drawbacks: does not represent topological characteristics of regions -Topological map: combinatorial map describing the subdivision of an image into sets of vertices, edges, faces and volumes • advantages: represent topological characteristics of region, represent all the cells (vertices, edges, faces and volumes) • drawbacks: high memory space and time consumption required for the extraction algorithm

Converging to an optimal model that have the efficiency of an OBG and the expression of a Topological Map is not possible. That is the reason why we need a conversion algorithm allowing to take advantages of the two models, by not using the same model during the whole segmentation process.

The Conversion Algorithm

The principle of the algorithm is to start with an OBG G embedded in an intervoxel matrix I, and a set of connected regions S, and to compute the local 3D topological map M representing S, but taking into account neighbors regions not included in S.

The extraction of the topological map is achieved by building the map of each surface in S, and linking them together using corresponding β i in order to represent S. Surfaces and real edges already exists in the OBG, thus only fictive edges have to be computed and the β i relations need to be fixed in order to have the 3D topological map corresponding to S.

The algorithm is divided into two subtasks: the main task reconstructs the map corresponding to a set of regions. This task uses a second task which reconstruct one face of the region.

Region Reconstruction

Algorithm 1 is the main part which reconstructs the part of topological map representing a given set of regions.

To reconstruct a given region R, we run through edges of the OBG. Indeed, each edge corresponds to a surface of R. Now, two cases have to be considered depending if the surface is closed or not. 1. if the surface is closed, there is no linel associated to the surface in the OBG (because linels represent border of surfaces). In such a case, we need to construct a map composed of 2 × g(e) edges, 1 vertex and 1 face (with g(e) the genus of the current surface). 2. if the surface is open, let us denote by k the number of boundaries, each one being a list of consecutive linels forming a loop. Each boundary is reconstruct by using Algorithm 2. Moreover, each new face is linked with previous map by adding a fictive edge. This ensures to obtain a connected map. Then, we may need to add some edges in order to obtain a surface with the "correct topology". In order to do so, as in the previous case, we construct a map composed of 2 × g(e) edges, 1 vertex and 1 face, but in this case we link this new map with the map already build and corresponding to boundaries in order both to obtain a connected map and having the correct topology.

Adding fictive edges to the existing edges in the OBG allows to retrieve the two properties of the topological map that are missing in the OBG. Indeed, fictive edges (i) link the different boundaries of a surface and (ii) conserve a valid Euler characteristic for each surface.

Before applying Algorithm 1, we need to compute the Euler characteristic of each surface since this information is not present in the OBG but it is needed during the map reconstruction. For that, we compute for each edge e of G, #v #e and #f (respectively the number of vertices, edges and faces of the surface associated to e).

The Euler characteristic of the face associated to e is denoted by χ(e) = #v -#e + #f . The genus associated to this surface is denoted by g(e) and computed with the Euler formula formula: g(e) = 2-χ(e)

2

. The Euler characteristic of the surface of a region r is the sum of the Euler characteristic of all its faces (the fact that vertices and edges incident to two faces are counted twice is not a problem for the Euler characteristic since it uses the difference between these two numbers).

Face reconstruction

The principle of the face reconstruction given in Algorithm 2 is to traverse the geometry (the linels) and to reconstruct darts and β 1 relations. Each created dart is linked with the associated triplet in the OBG. For each linel, if some neighbors triplets have already been treated, β 2 and β 3 are updated. (p,l,s) is the triplet associated to current dart d, and pprev is the pointel incident to dart dprev. We want to sew dprev by β2 and β3 if corresponding darts are already created. s3 is the rst surfel found from s, by turning around linel l in the direction of -→ n (the normal of s, oriented towards the current region r). lprev is the linel incident to p and s3 (i.e. the previous linel of the current border). s2 is the rst surfel found from s3, by turning around linel lprev in the opposite direction of -→ n (the opposite of the normal of s3. Indeed, the normal of s3 is oriented towards the adjacent region of r, thus the opposite is oriented towards r).

regions. Indeed, Algorithm 2 passes through all linels of the process border. Each operation is atomic, and finding triplet (p, l prev , s 2 ) and (p, l prev , s 3 ) can be achieved in at most 4 operations (since there are at most 4 surfels around a linel). In Algorithm 1, we process successively and exactly once each border of the reconstructed region. This give the first part of the complexity O(n l ). The second part is due to the adding of 2 × g edges which is done in linear time depending on g. The last part corresponds to the computation of g, which required each surfel to be considered once leading to a complexity in O(n s ).

Proof of correctness. Firstly, Algorithm 1 build a combinatorial map where each dart is sew for β 1 and β 2 . For β 1 , this is directly due to Algorithm 2 which follows one cycle of closed linels. At the end of this step, we have created a closed list of darts which are β 1 sew. Moreover, since in Algorithm 1 we process each face of reconstructed region, and since the border of a region is closed, we are sure that given a face f , we process all the adjacent faces of f and thus each dart is β 2 -sew.

Secondly, we need to prove that the Euler number of the reconstructed region is correct. We note g the genus of the region. Algorithm 2 computes only faces which are homeomorphic to topological disks (each face has one closed boundary). Thus, if we do not add fictive edges, we obtain a sphere, with χ = #v -#e + #f = 2. To this surface, we add 2 × g edges (more precisely we add the sum of 2 × g(e) for each edge e of the model, and this sum is equal to 2 × g as explain above), without modifying the number of vertices nor the number of faces. Thus, the new Euler characteristic is χ = #v -(#e + 2g) + #f and so χ = χ -(2 × g) = 2 -2g: we obtain the correct Euler characteristic of a surface of genus g.

Conclusion

Split and merge segmentation in the 3D case could be a highly time consuming method without the use of a topological structuring. But an optimal structuring both in term of time and space consumption and in term of topological features representation could not be achieved. That is the reason why two models have been developed: the Topological map one which represent the whole topology of an image partition and the OBG model which is more efficient according to time and space consumption.

In this article we have developed an algorithm that allows to extract the Topological Map from the OBG. This operation allows to have an on-demand extraction of the Topological Map from some regions of the OBG, which allows to locally retrieve all the topological features of some regions of interest in the image partition.

The other utilization of this algorithm is to extract the Topological Map of the whole image partition but only a the step of the segmentation process where it is needed. The presegmentation will be done using the OBG in order to have a lower time consumption or in order to avoid a lack of memory.

In future works, we want to study the possibility to modify the topological map reconstructed, for example by an algorithm which take into account a topological criterion, and then to update locally the OBG model to reflect the image modifications.

Fig. 1 .

 1 Fig. 1. The dierent parts of the topological map used to represent an image. (A) 3D image. (B) Minimal combinatorial map. (C) Intervoxel matrix (embedding). (D) Inclusion tree of regions.

Fig. 2 .

 2 Fig. 2. Example of image partition with the corresponding representation using the Oriented Boundary Graph model.

Algorithm 1 :

 1 Region set reconstruction Input: G an OBG S a set of connected regions Output: The topological map representing S foreach edge e adjacent to a region of S do if ∃ at least a linel associated to e then l ← rst linel of e; b ← build the face associated to l; foreach linel l associated to e (except l) do b ← build the face associated to l ; insert a ctive edge between b and b ; else b ← NULL; 1 if g(e) = 0 then create 2 × g(e) edges, loop sewed on themselves; insert them around b;

Fig. 3 .

 3 Fig.3. How to compute triplets (p, lprev, s2) and (p, lprev, s3). (p, l, s) is the triplet associated to current dart d, and pprev is the pointel incident to dart dprev. We want to sew dprev by β2 and β3 if corresponding darts are already created. s3 is the rst surfel found from s, by turning around linel l in the direction of -→ n (the normal of s, oriented towards the current region r). lprev is the linel incident to p and s3 (i.e. the previous linel of the current border). s2 is the rst surfel found from s3, by turning around linel lprev in the opposite direction of -→ n (the opposite of the normal of s3. Indeed, the normal of s3 is oriented towards the adjacent region of r, thus the opposite is oriented towards r).

Table 1 .

 1 Construction time comparison between the two models.

			Topological map model	OBG model
	(nb of voxels) (nb of regions) construction time (s) construction time (s)
	256x256x256	34390	35.8	3.2
	324x320x253	103358	69.15	5.26
	512x512x475	279618	277.88	23.15
	512x512x475	518253	301.27	24.37
	512x512x475	1121911	317.01	27.11

During this computation, new created darts are associated to their triplets (that have to be oriented) in order to retrieve, when a new dart is created, incident darts to the same triplet, and thus update the β 2 and β 3 links.

This algorithm is local: when processing dart d associated to triplet (p, l, s), we search for darts already existing in the neighborhood of d and sew found darts with d. In Fig. 3, we explain how triplets (p, l prev , s 2 ) and (p, l prev , s 3 ) are computed from (p, l, s).

Complexity and Proof of Correctness of the Algorithm

Complexity. Algorithm 1 is in time O(n l + g + n s ) with n l the number of linels of reconstructed regions, g its genus, and n s the number of surfels of reconstructed