Daniel Le Berre

Pierre Marquis

Stéphanie Roussel

Planning Personalised Museum Visits

In this paper, we consider the problem of designing personalised museum visits. Given a set of preferences and constraints a visitor might express on her visit, the aim is to compute the tour that best matches her requirements. The museum visits problem can be expressed as a planning problem, with cost optimization. We show how to bound the number of steps required to find an optimal solution, via the resolution of an instance of the shortest complete walk problem. We also point out an alternative encoding of the museum visits problem as an optimization problem with pseudo-Boolean constraints and a linear objective function. We have evaluated several constraints solvers, a planner and a tailored solver on a number of benchmarks, representing various instances of the museum visits problem corresponding to real museums. Our empirical results show the feasibility of both the planning and the constraint programming approaches. Optimal solutions can be computed for short visits and "practically good" solutions for much longer visits. 1

Introduction

We present a novel application of planning for the design of personalized museum visits. The need for such personalized visits comes from the fact that for a large number of museums, it is not conceivable to spend time in front of every art piece, especially because of their number which can be huge (exceeding thousands of items in some museums). This is why it makes sense to prepare a visit. To make things more concrete, ask yourself about what you would be doing if you just have one hour and a half to spend at Le Louvre? Our purpose is to help a visitor finding a "good answer" to such a question. While a few museums already offer some pieces of software enabling the user to prepare her visit, only a limited number of predefined tours are considered, and those which best match the user preferences and constraints are pointed out. An example of such a software can be found on Le Louvre website http://www.louvre.fr/en/parcours. An accurate handling of the user preferences and constraints (bearing on the visit duration, the selection of specific art pieces, Copyright c 2013, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. etc.) is out of reach of such simple approaches, which may output tours which are rather unsatisfactory from the user point of view because they mismatch her preferences in a significant way or do not satisfy by a large amount the expected duration constraint (predefined tours are often several hours long).

We have developed both a planning approach and a constraint programming approach to the design of personalised museum visits. Our approaches start with a number of input pieces of information, including the museum topology, and the user type, preferences and constraints. The museum topology can be modeled as a valued, oriented graph where each room corresponds to a vertex and each "alley" between rooms is an arc. Arcs are valued with durations which depend on the length and the nature of the corresponding "alley" (it can be a corridor, a stair or a lift) and also on the visitor type (individual, group, disabled people, etc.). The graph must be oriented since it can be the case that a flow direction is imposed between some rooms. The museum topology also makes precise the location of every art piece. In our setting, the user preferences are modeled by a utility function supposed to satisfy full additive independence (i.e., the utility of a tour is the sum of the utilities of each art piece considered during the visit). It is obtained via an anytime elicitation process (collaborative filtering is used to suggest default values depending on the visitor type) and results in a mapping associating with each art piece a value (its utility for the visitor). Some constraints on the admissible tours are directly induced from the museum topology: a sequence of rooms is feasible only if there is an "alley" between each pair of successive rooms. Visitors impose some constraints: some of them are automatically triggered from the visitor type, e.g. arcs corresponding to stairs must be ignored for wheel-chaired visitors, other constraints emerge from an interaction with her (expected duration of the tour, inclusion/exclusion of some art pieces, etc.). From all those data, the purpose is to output a tour which respects all the constraints and maximizes the overall utility.

Many recommendation systems have been developed so far to capture the artworks a visitor might be able to appreciate the most (a detailed list of recommendation systems dedicated to museums is given in [START_REF] Hage | Finding your way through the Rijksmuseum with an adaptive mobile museum guide[END_REF]). Among them is the CHIP Art Recommender [START_REF] Wang | Enhancing content-based recommendation with the task model of classification[END_REF] where a visitor profile is built using rated artworks and rated features. A major bottleneck shared by all those recommendation tools is the tour generation issue, which is not always considered or does not guarantee that the visitor preferences are satisfied in the best way. Thus, the tour wizard [START_REF] Hage | Finding your way through the Rijksmuseum with an adaptive mobile museum guide[END_REF]) associated to CHIP orders the artworks by decreasing utility order, starting from an empty tour, it tries to add each of them in an iterative way to the current tour when this is possible (i.e., when the constraints are not violated). Clearly enough, such a greedy approach does not offer any optimality guarantee.

The museum visits problem (as informally described above) looks quite similar to some well-known transportation problems considered in operations research (the traveling salesman problem with bounded resources for instance). Indeed, the museum visits problem can be considered as a specific orienteering problem (Vansteenwegen, Souffriau, and Oudheusden 2011), where the objective is to determine visit tours in towns or countries, which maximize the user utility. A detailed list of tools for tourist transportation problems is given in [START_REF] Kabassi | Personalizing recommendations for tourist[END_REF] and one of the most recent tools is described in [START_REF] Garcia | Personalized tourist route generation[END_REF]) and (Vansteenwegen et al. 2011). The authors of [START_REF] Jaén | Digital ants as the best cicerones for museum visitors[END_REF] suggest to reduce the museum visits problem to the orienteering problem approach, so that solving the latter enables solving the former. However, the number of art pieces in a museum can be much larger (by several orders of magnitude) than the number of sites interest in a town so that the solution proposed by [START_REF] Jaén | Digital ants as the best cicerones for museum visitors[END_REF] does not apply to large museums. The reason is that existing encoding schemes for the orienteering problem require a quadratic number of binary variables in the number of sites. The point is that large museums present thousands of art pieces, so that the corresponding encodings would include millions of variables, making their resolution out of reach of existing solvers, for space reasons.

In the following, the museum visits problem is modeled as a planning problem with cost optimization. We also model it as an optimization problem with pseudo-Boolean constraints and a linear objective function. We note that the corresponding decision problem is NP-complete, which justifies to tackle it using "classical" planning or constraint programming techniques. We model first the museum visits problem as a planning problem with two actions (moving from on room to another one and looking at an artwork), a time constraint and an optimization function. We also point out a specific constraint programming encoding scheme for the museum visits problem, where each art piece corresponds to a Boolean variable; it allows us to escape from the size issue raised up by the encoding scheme suited to the orienteering problem, as discussed above. Our encoding scheme requires the computation of a bound on the number of visit steps, which is performed via the resolution of an instance of a shortest complete walk problem. We prove that the decision problem associated with the shortest complete walk problem NP-complete, so it makes sense to solve it as well using constraint programming techniques.

We have evaluated several state-of-the-art constraint solvers, a planner and a tailored solver on a number of benchmarks, representing various instances of the museum visits problem corresponding to real museums. Our empir-ical results show the feasibility of both the planning and the constraint programming approaches. Optimal solutions can be computed for short visits using linear programming, and "practically good" solutions for much longer visits look reachable using a hybrid approach combining a constraint programming solver with incremental horizon handling as in planning.

The rest of the paper is organized as follows. In Section 2 we define the museum visits problem in formal terms and identify the complexity of the corresponding decision problem. In Section 3 we describe the methodology followed to solve the museum visits problem; especially, we present both a planning encoding and a constraint programming encoding suited to this problem. In Section 4 we present the benchmarks generated to evaluate our approaches and some empirical results are also pointed out. Finally, in Section 5, we conclude the paper and present some perspectives for further research.

The Museum Visits Problem

The museum topology is modeled as a so-called museum graph:

Definition 1 A museum graph is a 5-tuple G = V, A, E, S, w where:

• V is a set of vertices, each vertex representing a room of the museum. • A is a set of arcs. An arc a i,j between two vertices i and j belongs to A iff it is possible in the museum to go directly from room i to room j (i.e., without going through a third room). Observe that we do not consider edges but oriented arcs. This is because large museums can impose some flow directions. • w is a mapping w : A → N * where w(a i,j ) represents the duration to go from room i to room j. We suppose that this duration is strictly greater than 0: going from a room to another one is not instantaneous. • E is a subset of V representing entrances of the museum.

• S is a subset of V representing exits of the museum.

It is assumed that G has a complete walk, i.e., a walk starting at one entrance, finishing at one exit and including all the vertices. Formally, a complete walk is a finite sequence of vertices

(v 1 , v 2 , . . . , v n-1 , v n ) of V with v 1 ∈ E, v n ∈ S,
for all i ∈ 1; n -1 , a vi,vi+1 ∈ A and for all v ∈ V, there exists i ∈ 1; n such that v i = v. In museum terms, this simply means that there exists a tour of the museum which starts at an entrance, finishes at an exit and includes every room of the museum. Obviously enough, this assumption holds for every existing museum.

A toy example is given in Figure 1(a). The set of vertices is V = {1, 2}, the set of arcs is A = {a 1,2 }, the set of entrances is E = {1} (represented by a thick circle), the set of exits is S = {2} (represented by a double circle), the function w is such that w(a 1,2 ) = 5. Such a graph has a unique complete walk which is (1, 2).

Note that a complete walk can be a non-simple path (a simple path is a walk in which all edges are distinct) hence a

1 2 5 (a) Graph mu- seum G P r(p i ) u(p i ) t(p i ) p 1 1 5 3 p 2 1 15 8 p 3 2 11 3 (b) Art pieces
Figure 1: A toy museum non-elementary path (an elementary path is a walk in which all vertices are distinct).

Definition 2 A museum visit instance is a 6-tuple G, P, r, u, t, TMAX where:

• G = V, A, E, S, w is a museum graph.

• P is a finite set of art pieces.

• r is a mapping P → V. For each art piece p ∈ P, r(p) is the room where p is located. • u is a mapping P → N. For each art piece p ∈ P, u(p)

represents the satisfaction brought by p to the visitor. The higher u(p), the more satisfied the visitor. • t is a mapping P → N. For each art piece p ∈ P, t(p) (denoted t p ) represents the duration that the visitor would spend by visiting p. • TMAX is a non-negative integer representing the maximum amount of time (in time units) the visitor is willing to spend in the museum.

An example is given at Figure 1(b).

Definition 3 A solution to a museum visit instance G, P, r, u, t, TMAX is a pair sol = walk , O where walk is a sequence (v 1 , . . . , v n ) of vertices V and O a subset of P such that: 1. v 1 ∈ E, v n ∈ S and ∀i ∈ 1; n -1 , a vi,vi+1 ∈ A 2. if p ∈ O then r(p) ∈ walk 3. n-1 i=1 w(a vi,vi+1 ) + p∈O t(p) ≤ TMAX With each sol = walk , O , is associated score(sol) = p∈O u(p).
A best solution to G, P, r, u, t, TMAX is a maximal solution in terms of score.

Intuitively, the first condition constrains the walk to start at an entrance and to finish at an exit. The second condition ensures that every art piece of the solution is in a room of the walk. The third condition guarantees that the total time spent in the museum (duration of the walk and duration in front of each art piece of O) does not exceed the limit given by the visitor.

Solving a museum visits problem consists in computing a best solution given a museum visit instance. Given the museum graph of Figure 1(a) and the set of art pieces of Figure 1

(b), an museum visit instance is I = G, {p 1 , p 2 , p 3 }, r, u, t, 15 . A solution of this in- stance is (1, 2), {p 1 } .
The score of this solution is 5. The reader can check that a best solution for the instance I is (1, 2), {p 1 , p 3 } . No solution has a score higher than 16.

The decision problem MUSEUM associated with the museum visits problem (which is basically an optimization problem) consists in determining whether a solution having a score greater than or equal to u, where u is a given integer, exists, given a museum visit instance. This problem

E 2 3 S 0 5 0 0 (a) Graph museum G E,S P r E,S (p i ) u(p i ) t(p i ) p 1 2 5 3 p 2 2 15 8 p 3 3 11 3 (b) Art pieces
Figure 2: The toy museum, updated is computationally difficult in the sense that no polynomialtime (deterministic) algorithm exists for it, unless P = NP; indeed, MUSEUM is NP-complete. It is easy to show that MUSEUM remains NP-hard under the restriction when set V contains a unique room since, in such a case, it can be viewed as (the decision version of) a knapsack problem.

The complexity of MUSEUM justifies resorting to planning or constraint programming as an approach suited to the resolution of the museum visits problem.

Solving the Museum Visits Problem

In order to make the encoding scheme easier to grasp, we add to the museum graph two specific vertices E and S to V, which respectively represent a virtual entrance and a virtual exit ("sink"). For each entrance e of E, we add an arc a E,e to A such that w(a E,e ) = 0. For each exit s of S, we add an arc a s,S to A such that w(a s,S ) = 0. We also add an arc a S,S to A such that w(a S,S ) = 0. This allows us to consider a unique entrance and a unique exit. The updated set of arcs and the updated weight function are respectively denoted by A E,S and w E,S . We consider now that solution walks begin at E and finish at S instead of beginning at any entrance and finishing at any exit. As well, we can re-use the notion of complete walk: a complete walk now begins at E and finishes at S. The updated set of vertices, the updated set of arcs and the updated weight function are respectively denoted V E,S , A E,S and w E,S . The updated graph is denoted G E,S . The room mapping r can also be modified by the introduction of E and S. The updated mapping is denoted r E,S .

The update of the toy museum example given at Figure 1 is presented at Figure 2. A complete walk in this museum is now (E, 2, 3, S). The update of instance I is I E,S = G E,S , P, r E,S , u, t, 15 and the best solution for this instance is sol E,S = (E, 2, 3, S), 16 . Notice that the only difference with the best solution of I is the presence of E and S respectively at the beginning and at the end of the solution walk.

Planning modeling

The museum visits problem can be easily modeled as a planning problem with two actions. The action move allows the visitor to move from one room r 1 to another room r 2 and the action look-artwork allows the visitor to look at an artwork. In both cases, a precondition is to make sure that the remaining time is sufficient to execute the action, while an effect is to decrease the value of the remaining available time. The remaining time is modeled using numeric expres-sions as offered by PDDL 2.1 [START_REF] Fox | PDDL2.1: An extension to PDDL for expressing temporal planning domains[END_REF]. The complete PDDL domain is given below.

(define (domain museum) (:requirements :typing :numerical-fluents) (:types room artwork) (:predicates (visitor-at ?r -room) (inroom ?a -artwork ?r -room) (unseen ?a -artwork) (connected ?r1 ?r2 -room)) (:functions (total-utility) (remaining-time) (utility ?a -artwork) (time-look ?a -artwork) (time-move ?r1 ?r2 -room)) (:action move :parameters (?r1 ?r2 -room) :precondition (and (visitor-at ?r1) (connected ?r1 ?r2) (>= remaining-time (time-move ?r1 ?r2))) :effect (and (not (visitor-at ?r1))

(visitor-at ?r2) (decrease (remaining-time) (time-move ?r1 ?r2) ))) (:action look-artwork :parameters (?a -artwork ?r -room) :precondition (and (inroom ?a ?r) (visitor-at ?r) (unseen ?a) (>= remaining-time (time-look ?a))) :effect (and (not (unseen ?a)) (increase (total-utility) (utility ?a)) (decrease (remaining-time) (time-look ?a)) )))

The example given at Figure 2 can then be described the following way:

Constraint programming modeling

Let us now present a constraint programming encoding of the museum visits problem, which associates with each instance a set of pseudo-Boolean constraints and a linear objective function, such that every variable assignment maximizing the function corresponds to a best solution of the input instance. Let K denote the maximum number of move steps allowed for the visitor. In the encoding scheme, we consider three types of binary decision variables: • x p for p ∈ P. x p = 1 if the artwork p belongs to the solution subset of art pieces, x p = 0 otherwise; • x p,k for p ∈ P, k ∈ 1; K . x p,k = 1 if the artwork p belongs to the solution subset of art pieces and r(p) is the k th element of the solution walk, i.e., the art piece p is visited at step k, x p,k = 0 otherwise;

• c i,j,k for i, j ∈ V 2
E,S such that a i,j ∈ A E,S and k ∈ 1; K . c i,j,k = 1 if room i and room j are respectively at positions k th and (k + 1) th in the solution walk, i.e., the solution walk arc a ij is taken just after step k, c i,j,k = 0 otherwise.

max p∈P u(p).x p (1)   K-1 k=2 ai,j ∈A w(a i,j ).c i,j,k   + p∈P t(p).x p ≤ TMAX (2) ∀k ∈ 1; K , ai,j ∈A c i,j,k = 1 (3) ∀a i,j ∈ A, ∀k ∈ 1; K -1 , c i,j,k ≤ a j,l ∈A c j,l,k+1 (4) ∀k ∈ 2; K , ∀p ∈ P, x p,k ≤ a r(p),j ∈A c r(p),j,k (5) aE,j ∈A c E,j,1 = 1 (6) a i,S ∈A c i,S,K = 1 (7) ∀p ∈ P, x p = K k=2 x p,k (8)
The objective function (1) measures the visitor satisfaction. Constraint (2) ensures that the total amount of time spent in the museum is not larger than TMAX. We sum from k ≥ 2 because ∀a E,j ∈ A, w(a E,j ) = 0. Constraint (3) represents non-ubiquity, i.e., the fact that the visitor cannot be at two locations at the same time. Constraint (4) guarantees that the visitor comes out from any room she has come in, so that the solution found is a walk in the museum. Constraint (5) ensures that art pieces can be seen only if the visitor is in the corresponding room. Constraint (6) forces the walk to begin in E at step 1. Constraint (7) guarantees that the visitor is in S just after step K. The last constraint (8) ensures that i) an artwork is only visited once, and ii) an artwork utility is taken into account in the objective function iff the artwork has been visited at some k.

With this encoding, the number of variables equals to (|P| + |A|) × K. The number of constraints equals to |A| × (K -1) + |P| × (2K -1) + K + 3. In real museums, the number of art pieces is usually much larger than the number or alleys or the length of the shortest complete walk. Hence, the size of the encoding mainly is linear in the number of art pieces.

As we will see on the following, the encoding size of a museum visit instance may have a strong impact on the efficiency of its resolution: the smaller, the better. In order to maintain the encoding size as small as possible, it is important to derive a "good" upper bound for K.

Computing move bounds

A simple, user-dependent, bound on the number of moves to be considered is given by K 1 = TMAX min-time-move + 2. For instance, if the maximal time dedicated to the visit is 15 and each move (except those from the virtual entrance and to the virtual exit) lasts at least 2, then any admissible plan cannot contain more than 9 moves (including those from the virtual entrance and to the virtual exit). While this bound proves efficient when TMAX is rather small, it does not prove useful otherwise.

This explains why we also focused on another, more sophisticated and user-independent, bound K 2 and we consider as the actual bound the minimum of the two: K = min(K 1 , K 2 ). The rationale for K 2 is that the number of moves to be considered to reach an optimal plan cannot exceed the minimal number of moves required to visit each room of the museum. This calls for the computation of the length K 2 of a shortest complete walk of the graph museum: Definition 4 F-SCW is the following function problem:

• Input: an updated museum graph G E,S

• Output: the length K 2 of a shortest complete walk of G E,S By definition, K 2 equals to the smallest integer u such that there exists a complete walk of length u in G E,S and that there does not exist a complete walk of length u -1 in G E,S . Hence, determining K 2 can be achieved by finding out in an iterative way the maximal value u for which a complete walk of length u exists. The corresponding decision problem (determining whether a complete walk of length ≤ u exists in a given oriented graph with a unique source and a unique sink) is referred to as SCW (shortest complete walk). As far as we know, SCW has never been addressed in the graph/OR literature.

If u denotes the tested length, we consider |V E,S |.u binary variables b v,i , v ∈ V E,S and i ∈ 1; u . b v,i equals 1 if room v is visited at step i, 0 otherwise. For readability reasons, we denote n the mapping V E,S → 2 V E,S that associates with each room v of V E,S the set {n|a v,n ∈ A E,S }, i.e., the set of rooms directly accessible from room v.

The problem of determining whether a complete walk of length u exists in the graph consists in determining whether the following set of constraints is satisfiable:

∀v ∈ V E,S , u i=1 a v,i ≥ 1 (9) ∀v ∈ V E,S , ∀i ∈ 1; u -1 , a v,i ≤ n∈n(v) a n,i+1 (10) ∀i ∈ 1; u , v∈V E,S a v,i = 1 (11) a E,1 = 1 (12)
a S,u = 1 (13) Constraint ( 9) enforces every room to be visited at least once. Constraint (10) ensures the walk connectivity: if a room v is visited at step j then the room visited at step j + 1 must be directly accessible from v. Constraint (11) enforces that a unique room is visited at each step. Finally, constraints ( 12) and ( 13) respectively ensure that the walk begins in E at step 1 and ends in S at step u. For a given u, the encoding contains u.(|V E,S | + 1) + 2 constraints.

That SCW is solved using a constraint programming approach is justified by: Proposition 1 SCW is NP-complete.

Proof 1 • SCW is obviously in NP: it can easily be checked in polynomial time that the guessed sequence (v 1 , . . . , v n ) is a complete walk of the input graph satisfying n ≤ u. • SCW is NP-hard. We reduce in polynomial time the problem of deciding whether an oriented graph with a unique source and a unique sink has a Hamiltonian path (i.e., a path starting from the source, finishing at the sink and including every vertex of the graph exactly once) to SCW. This Hamiltonian path problem is known as NP-hard [START_REF] Karp | Reducibility Among Combinatorial Problems[END_REF]). The reduction is obvious: the input graph is unchanged and the value of u is assigned to the number n of vertices in the graph. Indeed, no complete walk of size < n may exist, hence every complete walk of size n (when it exists) is a shortest complete walk. Furthermore, by construction, a complete walk of size n also is a Hamiltonian path of the graph, and the converse also holds.

The following result shows that F-SCW belongs to the same complexity class as the traveling salesman problem.

Proposition 2 F-SCW is in FP NP[O(n 2 )] .
Proof 2 Let w = (v 1 , . . . , v K2 ) be a shortest complete walk of the input graph G E,S . We show that K 2 is at most quadratic in the number of vertices of G E,S . w may contain two kinds of vertices: multi-occurrent vertices are those vertices appearing more than once in w and mono-occurrent vertices appearing exactly once. If w contains only monooccurrent vertices, then its length K 2 is bounded by the number of vertices of G E,S , and the conclusion follows. In the remaining case, let v j be the last occurrence of a multioccurrent vertex v in w and let v i (1 ≤ i < j) be the previous occurrence of v in w. If the subpath (v i+1 , . . . , v j ) of w contains only vertices that already occur in the sequence (v 1 , . . . , v i ), then w = (v 1 , . . . , v K2 ) cannot be a shortest complete walk of G E,S since (v 1 , . . . , v i , v j+1 , . . . , v K2 ) is a complete walk of G E,S (it contains the same vertices as w) but is shorter than w. Hence there must exist at least one vertex v i,j of the sequence (v i+1 , . . . , v j ) which does not occur in (v 1 , . . . , v i ). Thus, with every pair v i , v j of successive multi-occurrent vertex v in w, we can associate a vertex v i,j of G E,S which does not occur in w before rank i. Hence the number of such pairs is bounded by the number of vertices of G E,S . Therefore the number of occurrences of any vertex v in w cannot exceed the number of vertices in G E,S . This implies that K 2 is at most quadratic in the number of vertices of G E,S , so that |A E,S | 2 can be used as the initial value of u.

Experimental Results

Benchmarks design

No benchmarks for the museum visits problem are currently available. The authors of [START_REF] Jaén | Digital ants as the best cicerones for museum visitors[END_REF]) have re-used orienteering problem benchmarks. However, those benchmarks do not represent real museum visit instances (they were not designed in this objective). Furthermore, our modeling needs more information than the ones needed by the orienteering problem. Thus, we have designed several benchmarks to test our encoding schemes.

We have considered two museums: a small one, the "Palais des Beaux Arts de Lille" (Bea 2012), and a much bigger one, the "National Gallery" (Nat 2012) of London. The characteristics of Palais des Beaux Arts are: 53 rooms, 121 alleys, 1 entrance, 1 exit and 486 artworks. The characteristics of National Gallery are: 119 rooms, 304 alleys, 4 entrances, 4 exits and 1783 artworks.

We used those two museums to test our encoding scheme of the shortest complete walk problem. For this problem, the input is the museum graph as presented in Section 2. Starting with the floor plans available on museum websites, we used the dot language specified in [START_REF] Gansner | An open graph visualization system and its applications to software engineering[END_REF] to represent the museum topology,1 as shown on Figure 3. artworks are located. For the Beaux Arts museum, we did not have access to the real museum database but went onsite and estimated the number of artworks in each room. We created the National Gallery artworks database from the information available on the website of this museum. Then, we enriched dot files representing the topology of each museum with the different elements needed for the museum visit instances, i.e., the artworks information, the maximum time bound and the length of the shortest complete walk. Many visitors profiles can be envisioned, associated with many different utility distributions. We considered three distribution types, which differ according to the balance ability they offer. The first one, unif, corresponds to users with weak preferences on art pieces (i.e., utility compensations are often feasible). To be more precise, a random integer between 0 and 1000 is associated to each artwork following a uniform distribution. The second utility profile (fibo) corresponds to users with mild preferences. We consider 20 utility levels and the utility values for these levels match the first integers of Fibonacci sequence. The artworks number for each of these levels is the same one. Finally, the third profile (luby) corresponds to users with marked preferences on art pieces. It is based on a Luby sequence as presented in [START_REF] Luby | Optimal speedup of Las Vegas algorithms[END_REF]. The higher the level, the fewer the number of artworks.

u(p i ) = 2 k-1 if i = 2 k -1, u(p i ) = u(p i-2 k-1 +1 ) otherwise.
In order to generate a wide family of profiles, we fixed the percentage of artworks that do not interest the visitor at all (null) and the percentage of artworks that the visitor considers being the most interesting ones (master). Independently of the function used to define the visitor satisfaction, noninteresting artworks are attributed a null utility and the most interesting artworks are given the maximum utility value. We used the same percentages 0, 10, 20 and 50 for both kinds of artwork, leading to 16 different combinations.

Another parameter to be made precise is the time the visitor is willing to spend in front of each artwork. This time depends on the utility given to an artwork: it seems reasonable to spend more time in front of a very interesting art piece and less time in front of a less interesting one. Nevertheless, this time cannot be null. We consider two cases. In the first case, times to spend in front of artworks and times to go from one room to another are approximately the same. In the second case, times to spend in front of artworks are twice as long as times to go from a room to an adjacent room in the museum. The objective is to observe the impact of different visit rhythms on the behavior of the solvers.

Finally, the complexity of the museum visit instance also depends on the total duration of the visit. Thus, we considered durations of 15, 60, 120, 180 and 300 time units. We generated 480 = |0, 10, 20, 5| 2 ×|0, 10, 20, 50|×|1.0, 2.0|× |unif, f ibo, luby| × |15, 60, 120, 180, 300| benchmarks for each museum, for a total of 960 benchmarks.

Empirical results

We used the format of the pseudo-Boolean competition [START_REF] Manquinho | The first evaluation of pseudo-Boolean solvers (PB'05)[END_REF] to allow us to try different solvers. We ran the pseudo-Boolean solver SAT4J (Le Berre and Parrain 2010) version 2.3.2 and CLASP [START_REF] Gebser | Conflict-driven answer set solving[END_REF]) 2.1.0 two open source CDCL solvers with native pseudo-Boolean constraints. We also tried CPLEX 12 (CPL 2012) using the PB competition front end to CPLEX written by Vasco Manquinho. Those instances have been generated with steps bound K = min(K 1 , K 2 ) with K 2 = 67 for Beaux Arts museum and K 2 = 192 for National Gallery. 2 The museum visits instances (without the steps bound) have been encoded as planning instances in PDDL. We ran LPG [START_REF] Gerevini | Planning through stochastic local search and temporal action graphs in LPG[END_REF] on those instances using the parameters -n 100 -seed 1234 where n represents the number of plans to compute and seed is the number used to initialize the random number generator. The other programs used their default settings. All programs ran on a cluster of bi-Xeon 3.0 GHz processors with 2GB of RAM running Centos. The timeout was set to 900s per instance.

An optimal solution could be computed for 265 out of 960 benchmarks (Table 2), all but one solved by CPLEX. Most of them are "small" instances (TMAX = 15). The pseudo-Boolean solvers were able to provide an answer (not necessarily optimal) for most benchmarks. Such behavior is expected, since CPLEX takes advantage of cutting planes to prove optimality but cannot always provide an answer because it does not explore the Boolean search space. On the other hand, the pseudo-Boolean solvers work on the Boolean search space, guided by the objective function. CLASP solved many more benchmarks than SAT4J, especially on large NG benchmarks. Notably, while LPG did not find any optimal plan, it was able to provide a plan for all benchmarks. We assumed that it was because LPG was looking for solutions with increasing plan length. To check that assumption, we built a dedicated solver called PMV based on SAT4J, because PMV requires a tight integration with the SAT solver and we have a strong expertise with SAT4J; PMV solves the museum visits problem with increasing steps k using a quick timeout, until the bound is reached. We used a timeout of 5 seconds for the first 10 steps, 20 seconds for the following 10 steps and finally 80 seconds per remaining step. That increasing timeout is made to adapt the solver to the increasing search space. The solver also has a timeout for optimizing the solution found, equals to 1 5 of the global timeout. PMV was also able to provide a solution for all benchmarks, and interestingly outperformed all other approaches.

Figures 4 and5 reports for each solver under consideration the number of benchmarks for which a solution of given quality (or, dually, of given "regret") has been found. The "regret" of a solution s is assessed by u * -u(s)

u *
, where u * is the utility of the best solution found. On this figure, values are aggregated so that the "column" OPT (resp. BEST) corresponds to the instances for which no better solution has 2 We generated benchmarks for the (decision version of the) shortest complete walk problem and ran CPLEX and CLASP on them using a timeout of 24 hours. We considered 16 step bounds for the BA museum (k = 65 to k = 80) and 76 for NG (k = 125 to k = 200). While the value of K2 could be computed for BA, K2 = 192 is the best upper bound of K2 we could compute for NG. They confirm that this problem is difficult, especially for large museums. been found and the solution found has been proved (resp. not proved) optimal, while the "column" 10 (resp. 20, 50 and 50+) corresponds respectively to the number of instances for which the "regret" of the solution found is strictly greater than 0% and less than 10% (resp. strictly greater than 10% and less than 20%, strictly greater than 20% and less than 50%, and greater than 50%). In the light of our experiments, finding out optimal tours is not that hard in practice when short-time visits are considered. To be more precise, when TMAX= 15, CPLEX found optimal solutions for all instances (96 BA instances + 96 NG instances). CLASP also exhibited quite good behavior for the BA museum: it found and proved optimal 88 solutions, and found 7 additional optimal solutions without proving them as optimal; however, for the NG museum, its performances decreased significantly: it found and proved optimal 3 solutions, and found 6 additional optimal solutions without proving them as optimal. SAT4J presents a similar performance profile; for the BA museum: it found and proved optimal 57 solutions, and found 7 additional optimal solutions without proving them as optimal; for the NG museum: it found and proved optimal 3 solutions, and found 1 additional optimal solutions without proving it as optimal. LPG found 56 optimal solutions for the BA museum and 10 optimal solutions for the NG museum. Finally, PMV found 82 optimal solutions for the BA museum and 15 optimal solutions for the NG museum. For larger values of TMAX, the number of optimal solutions found decreases: 13 BA and 11 NG instances are proven optimal by CPLEX for TMAX=60, 9 BA and 3 NG for TMAX=120, 7 BA for TMAX=180 and finally 3 BA for TMAX=300. However, non optimal solutions can still be computed for those large TMAX. Globally speaking, PMV showed rather impressive performances compared to the other algorithms when the purpose is to determine "practically good" solutions. On the one hand, the utility value of solutions found by this algorithm are typically very close to the optimal utility value. Of course, this can be measured only for those instances for which optimal solutions can be computed, and they are not so numerous when the time bound is large. On the other hand, whatever the museum, PMV appears by and large as the best performer; indeed, it outputs the best solution found or a solution close to it for a large majority of instances.

It is interesting to note that LPG and PMV behave differently on benchmarks with unif profile. Figure 6 depicts the number of best solutions found by LPG and PMV for each utility profile and each museum. We limit ourselves to those solvers because they were able to provide a solution for all benchmarks, unlike the other ones. LPG performs much better than PMV on unif profiles for the NG museum. After checking the plans produced by LPG on this profile, we found that LPG was able to produce plans with very few moves. This can be explained by the fact that one room close to an entrance of NG contains many artworks. Since PMV is utility driven and the profile is uniform, it is unlikely that PMV chooses directly artworks in the same room, and such wrong choices cannot be corrected during its limited timeout at a given k.

Conclusion

In this paper, we have defined the museum visits problem and modeled it both as a planning problem and a constraint programming problem. Even if the action space is simple, the planning formulation of MUSEUM looks quite natural. The PDDL encoding is much more concise than the constraint-based one we obtained, and as such, it is easier to grasp. In our opinion, the fact that MUSEUM is an optimization problem does not prevent from viewing it as a planning problem as well: from a computational point of view, many planning problems are optimization ones. In some sense, our empirical results suggest that, from the practical side, the right way to consider MUSEUM is both as a planning problem and as a CP one.

Our encoding scheme requires as many Boolean variables as artwork pieces and rooms per step in the museum; it thus improves the encoding scheme which is reached by considering the museum visits problem as an orienteering problem; indeed, this last encoding scheme requires a number of Boolean variables which is quadratic with the number of artwork pieces, which makes it impractical (for space reasons) for many museums. We generated benchmarks derived from two real museums. 3 We experimented with several constraints solvers and a planner on those benchmarks, allowing us to show the feasibility of the approach. The planning approach provides very good results on those problems: LPG was always able to provide a plan within the timeout. Such good results could also be achieved using the constraints encoding via an incremental approach, tailored for this problem. Interestingly, the museum visits problem provides challenging optimization benchmarks for the community. CPLEX seems to be the right choice to get an optimal solution. However, in practice, optimality is not a hard requirement, and using a planner or a pseudo-Boolean solver allows us to retrieve quickly reasonably good solutions.

This work calls for a number of perspectives. Generating more accurate visitor profiles (especially, in terms of utility distributions and time spent in front of the art pieces) would be useful to discard profiles which are quite unlikely and may lead to artificial, yet practically hard instances; this generation nevertheless requires to perform a time-consuming data collection and analysis. Another perspective is to relax the full additive independence assumption on the utility function, in order to take account of possible synergetic effects. Generalized additive independence could be targeted, requiring sophisticated and complex optimization techniques to be designed and implemented. Our perspective is to take advantage of collaborative filtering techniques and feedback analyses to improve our preference elicitation procedure and derive utility models that are quite good in practice. Taking into account graph decomposition techniques within PMV is also an important issue to consider. Finally, partnering with a museum is on-going. A prototype, Tech-A-Way, has already been developed.

  (define (problem museum) (:domain museum) (:objects rE r2 r3 rS -room a1 a2 a3 -artwork) (:init (= (total-utility) 0) (= (remaining-time) 15) (= (utility a1) 5) (= (utility a2) 15) (= (utility a3) 11) (= (time-look a1) 3) (= (time-look a2) 8) (= (time-look a3) 3) (= (time-move rE r2) 0) (= (time-move r2 r3) 5) (= (time-move r3 rS) 0) (= (time-move rS rS) 0) (connected rE r2)(connected r2 r3) (connected r3 rS)(connected rS rS) (unseen a1)(unseen a2)(unseen a3) (inroom a1 r2)(inroom a2 r2)(inroom a3 r3) (visitor-at rE)) (:goal (and (visitor-at rS))) (:metric maximize (total-utility)))

Figure 4 :

 4 Figure 4: Quality of solutions found on BA museum

Figure 6 :

 6 Figure 5: Quality of solutions found on NG museum #best solutions

Table 1 :

 1 Solutions in terms of solver

	Museum CPLEX CLASP SAT4J	LPG	PMV
	Encoding		Pseudo Boolean		PDDL Custom
	Number of optimal solutions found (265 out of 960)
	BA	131	88	57	-	-
	NG	133	3	3	-	-
	Number of solutions found (960 out of 960)
	BA	132	452	408	480	480
	NG	134	473	183	480	480

Note that we have used subgraphs to model different buildings or different floors of the museum. The visualization has been realized using Graphviz.

Some sample benchmarks in OPB and PDDL formats and some sample dot files for the two museums are available at http: //www.cril.fr/PMV/.

We would like to thank the anonymous reviewers for their helpful comments and Vincent Vidal for his advices on state-of-the-art planners. This work has partly been supported by the Conseil Régional du Nord/Pas-de-Calais and an EC FEDER grant.


Henri Azaïs

Geoffroy Canlorbe

Marianne Nikpayam

Clémentine Gonthier

Jérémie Belghiti

Catherine Uzan
email: catherine.uzan@aphp.fr

Catherine Professeur

Uzan

Reste-t-il des indications de curage ganglionnaire dans les cancers épithéliaux de l'ovaire après l'essai LION ?

Keywords: Ovarian cancer, Lymphadenectomy, Gynecologic surgery, Gynecologic oncology, Cytoreductive surgery, Peritoneal carcinomatosis

RÉSUMÉ

En mars 2019, Harter et al. publient les résultats de l'essai LION (Lymphadenectomy in patients with advanced ovarian neoplasms) qui remettent en cause l'intérêt des lymphadénectomies pelviennes et lombo-aortique pour certaines patientes présentant un cancer épithélial de l'ovaire à un stade avancé. Ces résultats ont influencé les nouvelles recommandations françaises publiées en décembre 2018 par l'Institut National du Cancer (INCa). Ainsi, il ne paraît plus cohérent de pratiquer un geste ganglionnaire pour les patientes pour lesquelles il n'existe pas d'argument pour un envahissement ganglionnaire, lorsqu'une chirurgie de cytoréduction péritonéale macroscopiquement complète a pu être effectuée. La question de l'évaluation ganglionnaire préopératoire apparaît donc essentielle alors que plus de la moitié des patientes de l'étude LION présentaient une atteinte métastatique ganglionnaire prouvée histologiquement. On note, pour l'évaluation du statut ganglionnaire par imagerie, une sensibilité supérieure pour la Tomographie par Émission de Positons couplée au scanner (TEP-scanner) que pour le scanner ou l'Imagerie par Résonance Magnétique (IRM). Néanmoins, le scanner thoraco-abdomino-pelvien avec injection de produit de contraste reste l'examen de référence dans cette indication. En l'absence d'atteinte suspectée, les lymphadénectomies supra-rénale, mésentérique, coelio-hépatique, de l'angle cardiophrénique, ne sont pas recommandées. Les curages ganglionnaires doivent toujours être réalisés dans les autres situations de prise en charge d'un cancer épithélial de l'ovaire en dehors du rare cas d'un carcinome mucineux de type expansif de stade 1. L'objectif de cette revue est de discuter des indications de lymphadénectomie pour la prise en charge chirurgicale des cancers épithéliaux de l'ovaire en prenant en compte les nouvelles données de la littérature scientifique.

INTRODUCTION

En décembre 2018 ont été publiées par l'Institut National du Cancer (INCa) les conduites à tenir devant des patientes atteintes d'un cancer épithélial de l'ovaire [1].

Toujours présenté à raison comme un cancer de mauvais pronostic, et malgré le développement des thérapies ciblées, la chirurgie garde un rôle central dans la prise en charge des patientes, et la qualité de sa mise en oeuvre est un facteur influençant le pronostic. Elle repose schématiquement sur deux notions principales : la cytoréduction péritonéale, et la chirurgie des aires ganglionnaires pelvienne et lombo-aortique (figure 1). Si l'impact de la réduction du résidu tumoral péritonéal (avec l'objectif d'un reliquat macroscopiquement nul en fin d'intervention) est bien démontré [START_REF] Du Bois | Role of surgical outcome as prognostic factor in advanced epithelial ovarian cancer: a combined exploratory analysis of 3 prospectively randomized phase 3 multicenter trials: by the Arbeitsgemeinschaft Gynaekologische Onkologie Studiengruppe Ovarialkarzinom (AGO-OVAR) and the Groupe d'Investigateurs Nationaux Pour les Etudes des Cancers de l'Ovaire (GINECO)[END_REF], celui de la chirurgie ganglionnaire fait toujours l'objet d'un débat. L'actualité scientifique dans le domaine du cancer de l'ovaire a été particulièrement riche ces derniers mois avec la communication de résultats d'études cliniques qui modifient en profondeur l'approche à la fois médicale et chirurgicale du traitement. Ainsi, si l'apport des inhibiteurs de PARP est indiscutable pour les patientes porteuses d'une mutation BRCA [START_REF] Moore | Maintenance Olaparib in Patients with Newly Diagnosed Advanced Ovarian Cancer[END_REF], la place de la chimiothérapie hyperthermique intrapéritonéale reste débattue après la publication de Van Driel et al. [START_REF] Van Driel | Hyperthermic Intraperitoneal Chemotherapy in Ovarian Cancer[END_REF].

En mars 2019, Harter et al. publient les résultats de l'essai LION (Lymphadenectomy in patients with advanced ovarian neoplasms) qui remet en cause l'intérêt des curages ganglionnaires pour certaines patientes présentant un cancer épithélial de l'ovaire à un stade avancé [START_REF] Harter | A Randomized Trial of Lymphadenectomy in Patients with Advanced Ovarian Neoplasms[END_REF].

L'objectif de cette mise au point est de discuter l'indication des curages ganglionnaires dans les cancers épithéliaux de l'ovaire, à la lumière des questions soulevées par cette récente publication.

INDICATION JUSQU'A L'ESSAI LION

Les recommandations pour la prise en charge des cancers épithéliaux de l'ovaire en France, publiées en décembre 2018 détaillent les indications à la réalisation des curages ganglionnaires. Il est ainsi noté qu'ils doivent être réalisés en cas de cancer épithélial de l'ovaire à un stade présumé précoce afin de réaliser une stadification initiale chirurgicale complète, hormis pour le sous-type mucineux expansif. En cas de stade avancé, quel que soit le type histologique, les curages sont recommandés en cas de suspicion clinique ou radiologique d'adénopathie métastatique pelvienne ou lomboaortique. En l'absence d'adénopathie suspecte, et en cas de chirurgie péritonéale complète, la lymphadénectomie peut être omise car elle ne modifie pas le traitement médical ni la survie globale, tout en augmentant la morbidité [1].

Ce dernier point représente une modification importante des pratiques et repose essentiellement sur les résultats de l'essai LION. Avant la présentation des résultats au congrès de l'American Society of Clinical Oncology (ASCO) en 2017 [START_REF] Harter | LION: Lymphadenectomy in ovarian neoplasms-A prospective randomized AGO study group led gynecologic cancer intergroup trial[END_REF], il était en effet réalisé une stadification ganglionnaire lors de la chirurgie des patientes présentant un cancer de stade avancé, indépendamment de la notion de suspicion clinique ou radiologique d'atteinte ganglionnaire préopératoire. Cette attitude reposait sur les données de la littérature scientifique, encore récente [START_REF] Zhou | The effect of lymphadenectomy on survival and recurrence in patients with ovarian cancer: a systematic review and meta-analysis[END_REF][START_REF] Gao | Systematic lymphadenectomy in the treatment of epithelial ovarian cancer: a metaanalysis of multiple epidemiology studies[END_REF], semblant observer un bénéfice à la réalisation des curages sur la survie des patientes. La lymphadénectomie est en effet envisagée théoriquement pour son intérêt thérapeutique par la diminution de la charge tumorale, mais également pour son rôle pronostique et pour affiner la stadification de la maladie. On sait en effet que la dissémination lymphatique ganglionnaire est fréquente dans les cancers épithéliaux de l'ovaire et que ni l'imagerie préopératoire, ni la palpation peropératoire des aires ganglionnaires ne sont efficaces pour affirmer une atteinte ganglionnaire avec précision. L'analyse rétrospective de Chan et al. à partir de la SEER (Surveillance, Epidemiology and End Results) database, portant sur 13 918 patientes atteintes d'un cancer épithélial de l'ovaire de stade III-IV avait ainsi montré en 2007 le bénéfice de la lymphadénectomie systématique sur la survie des patientes, mais également le rôle d'une lymphadénectomie exhaustive car le gain sur la survie était d'autant plus important que le nombre de ganglions prélevés était grand [START_REF] Chan | The potential therapeutic role of lymph node resection in epithelial ovarian cancer: a study of 13918 patients[END_REF]. L'extension du curage apparaissait comme un facteur pronostique indépendant influençant la survie, et donc imposant à ce titre un effort chirurgical pour pratiquer des curages complets.

La réflexion ayant conduit à l'essai LION et son protocole repose principalement sur des résultats de deux études : l'une rétrospective mais portant sur trois essais prospectifs randomisés [START_REF] Harter | LION: Lymphadenectomy in ovarian neoplasms-A prospective randomized AGO study group led gynecologic cancer intergroup trial[END_REF] et la seconde prospective [START_REF] Zhou | The effect of lymphadenectomy on survival and recurrence in patients with ovarian cancer: a systematic review and meta-analysis[END_REF].

Les résultats publiés par du Bois et al. en 2010 et portant sur l'analyse rétrospective de trois essais prospectifs randomisés multicentriques pour connaître le bénéfice de la réalisation d'une stadification ganglionnaire étaient en faveur d'un bénéfice de cette attitude sur la survie, en l'absence de lésion péritonéale résiduelle [START_REF] Du Bois | Potential Role of Lymphadenectomy in Advanced Ovarian Cancer: A Combined Exploratory Analysis of Three Prospectively Randomized Phase III Multicenter Trials[END_REF]. Ainsi, sur un total de 1 924 patientes prises en charge entre 1995 et 2002, la comparaison entre celles ayant eu une lymphadénectomie et celles n'en ayant pas eu, montre une survie médiane de 103 et 84 mois respectivement (p=0,0166), avec un effet significatif de la lymphadénectomie sur la survie globale en analyse multivariée (hazard ratio [HR] = 0,74; 95% IC, 0,59 -0,94; p =0,0123). Pour les patientes présentant un résidu tumoral inférieur à un centimètre, l'effet de la lymphadénectomie sur la survie atteignait tout juste la significativité, (HR = 0,85 ; 95% CI, 0,72 to 1,00 ; P = 0,0497), Parmi ces patientes, lorsqu'il existait une suspicion clinique d'atteinte ganglionnaire, la lymphadénectomie permettait un gain sur la survie globale à cinq ans de 16 % (log-rank test, P = 0,0038). L'analyse des différentes sous populations a permis aux auteurs d'identifier les situations semblant ou non tirer profit de la réalisation d'une lymphadénectomie et de soulever les hypothèses conduisant à l'élaboration du protocole de l'essai LION. En effet, la réflexion sur le bénéfice de la lymphadénectomie doit prendre en compte d'autres variables telles que la qualité de la cytoréduction péritonéale, qui influence à elle seule le pronostic [START_REF] Du Bois | Role of surgical outcome as prognostic factor in advanced epithelial ovarian cancer: a combined exploratory analysis of 3 prospectively randomized phase 3 multicenter trials: by the Arbeitsgemeinschaft Gynaekologische Onkologie Studiengruppe Ovarialkarzinom (AGO-OVAR) and the Groupe d'Investigateurs Nationaux Pour les Etudes des Cancers de l'Ovaire (GINECO)[END_REF], et la présence d'une authentique atteinte ganglionnaires avec le bénéfice attendu de la réduction chirurgicale de ce volume tumoral en particulier compte tenu de l'incertitude concernant l'efficacité de la chimiothérapie sur les métastases ganglionnaires [START_REF] Morice | Are nodal metastases in ovarian cancer chemoresistant lesions? Analysis of nodal involvement in 105 patients treated with preoperative chemotherapy[END_REF][START_REF] Keyver-Paik | Impact of Chemotherapy on Retroperitoneal Lymph Nodes in Ovarian Cancer[END_REF]. Ainsi, l'analyse de la survie en fonction du résidu tumoral péritonéale montre un bénéfice de la lymphadénectomie en l'absence de résidu La deuxième étude d'intérêt est celle de Panici et al., prospective, randomisée, multicentrique, comparant l'effet de la réalisation ou non de la lymphadénectomie pour les patientes présentant un cancer épithélial de l'ovaire de stade avancé et ayant fait l'objet d'une cytoréduction péritonéale complète [START_REF] Panici | Systematic Aortic and Pelvic Lymphadenectomy Versus Resection of Bulky Nodes Only in Optimally Debulked Advanced Ovarian Cancer: A Randomized Clinical Trial[END_REF]. Il a été observé une amélioration de la survie sans récidive dans le groupe lymphadénectomie sans impact sur la survie globale. Cette étude a été critiquée, en particulier sur le fait que les centres n'avaient pas fait l'objet d'une validation externe attestant de la qualité de leur prise en charge chirurgicale, avec en particulier un taux faible (37 %) de chirurgie complète.

Ces études n'avaient donc pas permis de mettre en évidence une non-infériorité de l'attitude conservatrice en comparaison avec la lymphadénectomie systématique en cas de cancer épithélial de l'ovaire de stade avancé. Dans l'essai LION, les auteurs se sont intéressés spécifiquement à la population de patientes n'ayant pas d'atteinte ganglionnaire suspectée cliniquement ou radiologiquement (en sachant les limites en sensibilité), pour évaluer si la lymphadénectomie avait un impact pronostique.

L'ESSAI LION EN BREF

Publié en mars 2019, l'essai LION suggère avec un haut niveau de preuve scientifique l'absence de bénéfice sur la survie globale ou sans récidive à la réalisation des curages ganglionnaires après chirurgie de cytoréduction péritonéale macroscopiquement complète pour les patientes présentant un cancer épithélial de l'ovaire à un stade avancé (IIB -IV) de la Fédération internationale des Gynécologues-Obstétriciens (FIGO) [START_REF] Prat | Staging classification for cancer of the ovary, fallopian tube, and peritoneum[END_REF], en l'absence d'argument préopératoire ou peropératoire Cette étude, particulièrement pertinente sur le plan de la méthodologie, apporte un argument fort pour l'abandon de la lymphadénectomie pour les patientes correspondant au spectre de l'étude [START_REF] Eisenhauer | Ovarian Cancer Surgery -Heed This LION's Roar[END_REF]. À l'inverse de la démarche de l'étude de Panici et al., les centres participant à l'essai LION faisaient l'objet d'une validation pour attester de leur compétence chirurgicale. Le nombre prévu de patientes à inclure a été respecté, ainsi que la durée de suivi, et les résultats en termes de survie globale et sans récidive sont cohérents avec ceux communément rapportés. La sélection de patientes ayant un reliquat tumoral péritonéal nul en fin d'intervention permet de s'affranchir du poids pronostique d'une cytoréduction incomplète qui rend délicate l'interprétation de l'impact de la chirurgie ganglionnaire sur la survie des patientes. Néanmoins, certains observateurs ont mis en avant certaines limites [START_REF] Atallah | Is the LION strong enough?[END_REF] : le grand nombre de centres participant avec finalement peu de patientes par centre, l'absence d'information sur le type histologique, le grade, et le CA 125. L'absence d'atteinte ganglionnaire suspectée à l'imagerie pourrait représenter un biais de sélection de patientes avec un profil de biologie tumorale moins agressif que celui des patientes avec une atteinte ganglionnaire macroscopique. Enfin, le traitement adjuvant (8 cycles de chimiothérapie en moyenne) est peu détaillé, et la discussion ne prend pas en compte l'impact des nouveaux traitements disponibles. Néanmoins, il s'agit d'un essai bien conduit, de haut niveau de preuve, mis en oeuvre par un collectif d'experts reconnus pour la rigueur et la radicalité de leur prise en charge chirurgicale. Ces résultats représentent à ce titre un argument majeur pour ne plus pratiquer de lymphadénectomie aux patientes présentant les critères d'inclusion de l'étude.

QUELLE STRATÉGIE EN DEHORS DU SPECTRE DE L'ETUDE ?

Il est discutable d'élargir les conclusions de l'essai LION aux indications qui ne relèvent pas du protocole de l'étude. Les patientes incluses dans l'essai présentaient dans près de 95 % des cas un carcinome tubaire, ovarien ou péritonéale, sans information disponible sur le grade, bien que par argument de fréquence, on puisse considérer qu'il s'agissait de carcinome séreux de haut grade dans la majorité des cas. De la même manière, les patientes ont été opérées avant l'administration d'une chimiothérapie néoadjuvante, ce qui pose la question de l'extension des conclusions à la situation des chirurgies d'intervalle. Il convient donc de repréciser, à la lumière de ces nouvelles données, les indications de lymphadénectomie en dehors du spectre de l'étude (Figure 1).

Chirurgie d'intervalle

Il est admis que la qualité de la cytoréduction chirurgicale impacte le pronostic des patientes répondeuses à la chimiothérapie davantage que la séquence thérapeutique entre chimiothérapie et chirurgie. Ainsi, en cas de non résecabilité initial, il est d'usage de débuter une chimiothérapie néoadjuvante avant de rediscuter des conditions opératoires en situation d'intervalle (après trois à quatre cycles de chimiothérapie) ou de clôture (après six cycles de chimiothérapie). Il paraît raisonnable de considérer que les conclusions de l'essai LION pourraient être étendues à ces situations dans la mesure où la démarche chirurgicale reste la même. L'impossibilité à entreprendre une chirurgie de cytoréduction complète en première intention est un marqueur de l'importance de l'atteinte péritonéale. La population des patientes présentant une contre-indication à la chirurgie initiale (et en l'absence de suspicion d'atteinte ganglionnaire) pourrait donc, à la lumière des observations de l'essai LION, tirer profit de l'abandon des curages, avec le bénéfice de pouvoir concentrer l'effort chirurgical sur le temps péritonéal.

Stades précoces (Stades I à IIA)

Les lymphadénectomies pelviennes et lombo-aortique dans le cas des cancers présumés de stade précoce permettent de corriger la stadification en stade IIIA1 en cas d'atteinte ganglionnaire pour 8,5 % à 13 % des patientes et contribuent à améliorer la survie des patientes. Elles sont indiquées lors de la prise en charge initiale ou la re-stadification des cancers de stade précoce en dehors des cas de sous-type mucineux expansif [1]. L'essai de Maggioni et al., prospectif et randomisé, conduit sur 268 patientes présentant un cancer épithélial de l'ovaire de stade précoce avait pour but de comparer la pratique d'une lymphadénectomie systématique avec la réalisation d'un échantillonnage ganglionnaires [START_REF] Maggioni | Randomised study of systematic lymphadenectomy in patients with epithelial ovarian cancer macroscopically confined to the pelvis[END_REF]. Les auteurs n'ont pas mis en évidence de différence significative en termes de survie globale ou sans récidive avec néanmoins une tendance à une survie améliorée pour les patientes pour qui un geste systématique avait été accompli. Il est vraisemblable que l'absence de significativité soit en rapport avec un manque de puissance de cette étude.

L'étude publiée en 2007 par Chan et al. portant sur le suivi de 6 686 patientes présentant un cancer épithélial de l'ovaire de stade I parmi lesquelles une lymphadénectomie a été réalisée dans 42,8 % des cas était en faveur d'une amélioration de la survie à cinq ans en comparaison avec l'absence de lymphadénectomie (92,6 % vs 87 % ; p < 0,001). Un plus grand nombre de ganglions prélevés avait un effet positif sur la survie et était ainsi un facteur pronostique significatif d'amélioration de la survie.

Ce bénéfice sur la survie n'était pas observé en cas de carcinome à cellules claires, de cancers germinaux, des cordons sexuels ou de sarcomes [START_REF] Chan | Association of lymphadenectomy and survival in stage I ovarian cancer patients[END_REF].

Tumeurs rares

Les récentes recommandations françaises ne traitent pas différemment les différents sous types histologiques pour la question de l'indication des curages ganglionnaires, en dehors de la situation rare des carcinomes mucineux expansifs de stade I. Nous rappelons ici que pour les indications de traitement d'une manière générale pour ces tumeurs, il convient de valider la prise en charge en réunion de concertation pluridisciplinaire (www.ovaire-rare.org) d'un des centres spécialisés du réseau « Tumeurs rares de l'ovaire ».

Cancer de l'ovaire mucineux

Les cancers de type mucineux sont des cancers rares, représentant 3 % des tumeurs ovariennes épithéliales. Les indications de lymphadénectomie pour les cancers de l'ovaire mucineux ont récemment été précisées dans une mise au point de Morice et al. [START_REF] Morice | Mucinous Ovarian Carcinoma[END_REF]. Les auteurs rapportent un taux d'envahissement ganglionnaire très faible (<2% des cas) dans les cancers de stade 1. Ce taux est plus élevé pour les formes infiltratives (17 à 30 %) ce qui impose l'indication de lymphadénectomie pelvienne ou lombo-aortique dans ce cas quel que soit le stade. À l'inverse, dans les formes expansives, la lymphadénectomie n'est pas indiquée pour les tumeurs de stade 1 en raison de l'absence d'atteinte ganglionnaire mise en évidence dans les publications dans cette situation [START_REF] Gouy | Staging surgery in early-stage ovarian mucinous tumors according to expansile and infiltrative types[END_REF][START_REF] Muyldermans | Primary invasive mucinous ovarian carcinoma of the intestinal type: importance of the expansile versus infiltrative type in predicting recurrence and lymph node metastases[END_REF].

Cancer de l'ovaire endométrioïde, à cellules claires, carcinosarcomes, séreux de bas grade Les données de la littérature incluent le plus souvent des patientes sans prendre en compte les soustypes histologiques et le grade. Pour cette raison, il n'existe pas de différence de recommandation pour la réalisation des curages en fonction de l'histologie. Certaines études, comme celle de Grabowski et al. se sont intéressées à la réponse des carcinomes séreux de bas grade à la chimiothérapie habituellement proposée, mais il n'y a pas de données concernant l'intérêt de la lymphadénectomie dans ces sous-groupes spécifiques [START_REF] Grabowski | Operability and chemotherapy responsiveness in advanced low-grade serous ovarian cancer. An analysis of the AGO Study Group metadatabase[END_REF]. On peut revenir sur l'étude de Chan et al.

discutée précédemment qui n'a pas montré de bénéfice sur la survie d'une lymphadénectomie en cas de carcinome à cellules claires à un stade précoce [START_REF] Chan | Association of lymphadenectomy and survival in stage I ovarian cancer patients[END_REF]. Cette observation s'explique probablement par la plus grande agressivité de ces tumeurs et donc la difficulté plus importante à montrer l'effet de la lymphadénectomie.

QUELLE STRATÉGIE POUR LES AUTRES AIRES GANGLIONNAIRES ?

Quelle attitude en cas d'atteinte ganglionnaire suspectée ou démontrée en dehors des territoires pelviens et lombo-aortique ? En l'absence d'envahissement, les lymphadénectomies supra-rénale, mésentérique [START_REF] Baiocchi | Surgical implications of mesenteric lymph node metastasis from advanced ovarian cancer after bowel resection[END_REF][START_REF] Gallotta | Mesenteric lymph node involvement in advanced ovarian cancer patients undergoing rectosigmoid resection: prognostic role and clinical considerations[END_REF][START_REF] Gouy | Prognostic factors for and prognostic value of mesenteric lymph node involvement in advanced-stage ovarian cancer[END_REF][START_REF] Salani | Surgical management of mesenteric lymph node metastasis in patients undergoing rectosigmoid colectomy for locally advanced ovarian carcinoma[END_REF], coelio-hépatique [START_REF] Martinez | Celiac lymph node resection and porta hepatis disease resection in advanced or recurrent epithelial ovarian, fallopian tube, and primary peritoneal cancer[END_REF][START_REF] Martínez | Prognostic relevance of celiac lymph node involvement in ovarian cancer[END_REF], de l'angle cardio-phrénique, ne sont pas recommandées [1].

Néanmoins, en pratique clinique et lors des discussions en réunion de concertation pluridisciplinaire, il peut être discuté d'entreprendre l'exérèse d'un ganglion suspect situé dans une région anatomique autre qu'abdomino-pelvienne (ganglion cardio-phrénique, axillaire, …), en particulier en cas de lésion unique, et si la chirurgie péritonéale peut être réalisée sans reliquat macroscopique.

Concernant la localisation cardio-phrénique, qui classe la maladie au stade IVB, Prader et al. ont récemment apporté des éléments de réponse en publiant les résultats d'une étude rétrospective comparant deux groupes de 52 patientes appariées présentant des cancers épithéliaux de l'ovaire de stade IIIB-IV et ayant fait l'objet d'une chirurgie de cytoréduction première complète [START_REF] Prader | Pattern and impact of metastatic cardiophrenic lymph nodes in advanced epithelial ovarian cancer[END_REF]. Les patientes présentaient toutes une atteinte ganglionnaire cardio-phrénique. Les auteurs concluent en premier lieu sur l'impact péjoratif de cette localisation sur la survie globale et sans récidive des patientes ayant fait l'objet de chirurgie de cytoréduction complète, la qualité de la cytoréduction péritonéale restant un facteur pronostique supérieur à l'atteinte cardio-phrénique. Enfin, ils n'ont pas réussi à démontrer un impact significatif de la résection des atteintes ganglionnaires cardiophrénique sur la survie.

QUELLE STRATÉGIE POUR L'ÉVALUATION GANGLIONNAIRE PRÉ-OPÉRATOIRE ?

Comment traiter le concept de ganglion lymphatique « négatif cliniquement » quand on sait que les ganglions métastatiques et non métastatiques ont souvent une taille équivalente et que l'évaluation pré ou peropératoire a une sensibilité limitée. Dans l'étude de Eisenkop et al., évaluant la capacité peropératoire à apprécier l'atteinte ganglionnaire macro métastatique chez les patientes opérées pour un cancer épithélial de l'ovaire, le caractère métastatique a pu être suspecté par la palpation dans 31,1 % des cas, par l'inspection dans 26,2 % (après ouverture du rétropéritoine) et dans 42,6 % par la dissection. Cela indique que la dissection était nécessaire pour suspecter l'atteinte métastatique ganglionnaire dans un grand nombre de cas et que par conséquent, l'inspection seule, comme pratiquée lors de l'essai LION, est insuffisante pour cette évaluation [START_REF] Eisenkop | The clinical significance of occult macroscopically positive retroperitoneal nodes in patients with epithelial ovarian cancer[END_REF].

Porter l'indication de lymphadénectomie sur la suspicion clinique d'atteinte ganglionnaire impose de soulever la question des évaluations nécessaires et justifiées pour juger le statut ganglionnaire présumé. Cette réflexion est rendue délicate quand on sait que tous stades confondus, on rapporte 44 % à 53 % d'atteintes ganglionnaires à l'examen anatomo-pathologique des lymphadénectomies systématiques réalisées pour la prise en charge des cancers épithéliaux de l'ovaire [START_REF] Harter | Pattern and clinical predictors of lymph node metastases in epithelial ovarian cancer[END_REF][START_REF] Morice | Lymph node involvement in epithelial ovarian cancer: analysis of 276 pelvic and paraaortic lymphadenectomies and surgical implications[END_REF] Concernant l'évaluation de l'atteinte ganglionnaire, on note une sensibilité supérieure pour la Tomographie par Émission de Positons couplée au scanner (TEP-scanner) (77 -83,8 %) [START_REF] Signorelli | Detection of nodal metastases by 18F-FDG PET/CT in apparent early stage ovarian cancer: a prospective study[END_REF][START_REF] Nam | Diagnosis and staging of primary ovarian cancer: correlation between PET/CT, Doppler US, and CT or MRI[END_REF][START_REF] Michielsen | Whole-body MRI with diffusionweighted sequence for staging of patients with suspected ovarian cancer: a clinical feasibility study in comparison to CT and FDG-PET/CT[END_REF] que pour le scanner (54-62,5 %) [START_REF] Nam | Diagnosis and staging of primary ovarian cancer: correlation between PET/CT, Doppler US, and CT or MRI[END_REF][START_REF] Michielsen | Whole-body MRI with diffusionweighted sequence for staging of patients with suspected ovarian cancer: a clinical feasibility study in comparison to CT and FDG-PET/CT[END_REF] ou l'Imagerie par Résonance Magnétique (IRM) (62,5-77 %) [START_REF] Nam | Diagnosis and staging of primary ovarian cancer: correlation between PET/CT, Doppler US, and CT or MRI[END_REF][START_REF] Michielsen | Whole-body MRI with diffusionweighted sequence for staging of patients with suspected ovarian cancer: a clinical feasibility study in comparison to CT and FDG-PET/CT[END_REF]. Néanmoins, les recommandations françaises n'ont pas retenu l'intérêt du TEP-scanner pour évaluer l'extension des cancers de l'ovaire et le scanner thoraco-abdomino-pelvien avec injection de produit de contraste reste l'examen de référence dans cette indication [1]. On peut penser, par analogie avec l'attitude adoptée pour l'évaluation des autres cancers pelviens [START_REF] Gouy | Nodal-staging surgery for locally advanced cervical cancer in the era of PET[END_REF], que le TEPscanner pourrait trouver une indication dans l'évaluation ganglionnaire préopératoire, à la lumière des résultats de l'essai LION. Pourtant, si les patientes de l'essai LION ne semblent pas avoir bénéficié de la lymphadénectomie, la question de la sensibilité toujours plus importante des outils d'imagerie interroge. La capacité à détecter des lésions de petit volume pourrait ainsi inciter à réaliser une lymphadénectomie pour une patiente éligible selon les critères de l'essai LION à une désescalade, rendant alors l'essai caduc et conduisant une nouvelle tendance au surtraitement. Il s'agit alors de définir la notion de « normal lymph nodes both before and during surgery », et de discuter son application en prévision de l'amélioration attendue des outils de détection. Si l'évaluation clinique est et restera hasardeuse pour définir le statut ganglionnaire, il est vraisemblable que les outils d'imagerie contribueront à détecter à l'avenir des métastases de petit volume. Faudra-t-il alors réaliser une lymphadénectomie pour ces patientes ? Cette discussion aura inévitablement lieu et nécessitera de mettre en balance la question reposée du bénéfice de la chirurgie ganglionnaire sur la survie avec la morbidité induite par la procédure, sans équivoque dans la publication de Harter et al. [START_REF] Harter | A Randomized Trial of Lymphadenectomy in Patients with Advanced Ovarian Neoplasms[END_REF].

CONCLUSION

De la part d'une équipe convaincue par l'intérêt des curages ayant publié à plusieurs reprises des données dans ce sens, les résultats de l'essai LION sont très significatifs et confirment l'importance de mener à bien des études de haut niveau de preuve pour apporter une réponse claire à une problématique clinique ancienne et souvent débattue. Il ne paraît plus cohérent de pratiquer les curages systématiques, après la publication de ces résultats, pour les patientes appartenant au spectre d'inclusion de l'étude. La question de l'évaluation ganglionnaire préopératoire est essentielle, et probablement soumise à discussion, alors que la moitié des patientes présentaient finalement une atteinte métastatique ganglionnaire prouvée histologiquement. Cette étude renforce indirectement, et il convient ici de le rappeler, l'importance de l'objectif de cytoréduction péritonéale complète pour obtenir le bénéfice maximal de la chirurgie sur la survie des patientes.

RÉFÉRENCES

1.

Institut national du cancer. Thésaurus -Conduites à tenir initiales devant des patientes atteintes d'un cancer épithélial de l'ovaire. 2018;

  tumoral péritonéal. Cet effet est moins évident en cas de résidu tumoral. En prenant en compte la suspicion clinique d'atteinte ganglionnaire, du Bois et al. ont observé que la lymphadénectomie avait un impact positif significatif sur la survie en l'absence de résidu tumoral et en l'absence d'atteinte ganglionnaire suspectée (survie médiane 108 vs 83 mois en l'absence de lymphadénectomie, p=0,0081). En présence d'un résidu tumoral péritonéal, la lymphadénectomie gardait un effet positif sur la survie indépendamment du statut ganglionnaire suspecté. Néanmoins, cet effet n'était significatif que dans le sous-groupe de patientes ayant une suspicion clinique d'atteinte ganglionnaire. En analyse multivariée, la lymphadénectomie n'avait un impact sur la survie significatif que chez les patientes avec une suspicion clinique d'atteinte ganglionnaire.

  pour une atteinte ganglionnaire. Les résultats sont également en faveur d'une augmentation du taux de complications post-opératoires et du taux de mortalité à 60 jours dans le groupe de patientes ayant eu une chirurgie ganglionnaire. Il s'agit d'une étude clinique de phase 3, multicentrique, prospective, randomisée, ouverte, menée entre décembre 2008 et janvier 2012. Le critère d'évaluation principal était la survie globale, et les critères d'évaluation secondaire étaient la survie sans récidive, la qualité de vie et le nombre de ganglions réséqués. Les patientes éligibles présentaient un cancer épithélial de l'ovaire prouvé histologiquement à un stade avancé (IIB -IV), sans métastases extra-péritonéales non résécables et pouvant faire l'objet d'une chirurgie première. Elles étaient âgées de 18 à 75 ans, en bon état général, et avaient donné un consentement écrit. En l'absence de métastase ganglionnaire à l'imagerie préopératoire, le tirage au sort entre les groupes « avec lymphadénectomie » et le groupe « sans lymphadénectomie » avait lieu avant l'intervention. Le résultat n'était donné à l'équipe chirurgicale en peropératoire, qu'après confirmation que la chirurgie de cytoréduction péritonéale macroscopiquement complète avait pu être conduite et en l'absence de suspicion peropératoire d'atteinte ganglionnaire. Ainsi, Pour évaluer la survie globale, il a été calculé un nombre de sujet nécessaire à inclure de 640 patientes. Au final, 323 patientes ont été incluses dans le groupe « avec lymphadénectomie » et 324 dans le groupe « sans lymphadénectomie » avec des caractéristiques de population équivalentes. Dans le groupe « avec lymphadénectomie », 57 ganglions ont été retirés en moyenne (22 en région para-aortique et 35 en région pelvienne), et une atteinte ganglionnaire microscopique a été observée dans 55,7 % des cas. La survie globale médiane était de 65,5 mois dans le groupe « avec lymphadénectomie » et de 69,2 dans le groupe « sans lymphadénectomie ». Ainsi, la réalisation d'une lymphadénectomie n'a pas montré d'amélioration ni sur la survie globale (HR: 1,06; IC 95 %: 0,83 à 1,34) ni sur la survie sans progression (HR: 1,06; IC à 95 %: 0,83-1,34) malgré la mise en en évidence d'une atteinte ganglionnaire rétropéritonéale microscopique chez 55,7 % des patientes. La lymphadénectomie était associée à une chirurgie plus longue, avec des pertes sanguines plus importantes, un taux plus élevé de transfusion et d'événements indésirables, en particulier le recours à une nouvelle laparotomie, et le taux de décès dans les 60 jours post-opératoire.

  avec un taux fréquemment supérieur à 50 % en cas de cancer de stade avancé, et que malgré l'absence de suspicion clinique ou radiologique d'envahissement ganglionnaires, Harter et al. rapportent dans l'essai LION une atteinte ganglionnaire chez 55,7 % des patientes du groupe « lymphadénectomie » [5]. On précisera que dans l'essai LION, les espaces pelviens et lombo-aortique étaient systématiquement chirurgicalement ouverts pour vérifier l'absence de ganglions suspects (et pas une simple palpation).

Légende de la figure

Indication de lymphadénectomie en cas de cancer épithélial de l'ovaire (en dehors du rare cas de carcinome ovarien mucineux de type expansif au stade I pour lequel il ne faut pas réaliser de curage)